가서 수학해

바둑은 세계에서 가장 인기 있는 게임 중 하나이다.우아하고 간단한 규칙의 결과로, 이 게임은 오랫동안 수학 연구에 영감을 주었다.11세기 중국 학자 심궈(沈國)는 '꿈의 풀(Dream Pool)'에서 이사직을 10명 안팎으로¹⁷² 추정했다.최근 몇 년 동안, 존 H. 콘웨이의 게임 연구는 초현실적인 숫자의 발명으로 이어졌고 조합^[1] 게임 이론의 발전에 기여했다.

계산의 복잡성

Generalized Go는 n × n개의 보드에서 진행되며, Generalized Go의 주어진 위치에서 승자를 결정하는 계산 복잡도는 ko 규칙에 따라 결정적으로 달라진다.

PSPACE에서 Go는 "거의"입니다. 일반 플레이에서는 이동이 되돌릴 수 없고, 더 어려운 복잡성에 필요한 반복 패턴의 가능성이 있는 것은 캡처를 통해서만 가능하기 때문입니다.

ko 없음

ko가 없으면 Go는 ^[2]PSPACE-hard입니다.이는 PSPACE-완전이라고 알려진 진정한 양자화된 부울 공식(True Quantified Boolean Formula)을 일반화 지리학, 평면 일반화 지리학, 최대 도수 3의 평면 일반화 지리학, 최종적으로는 Go 포지션으로 환원함으로써 입증된다.

Go with superko는 PSPACE에 없는 것으로 알려져 있습니다.실제 경기는 $({$ 디스플레이 $스타일$ n $^{2}})$ $n^{2}$ 지속되지 않는 것으로 보이지만 일반적으로 바둑의 길이에 다항식 구분이 있었는지 여부는 알려지지 않았다.있을 경우 Go는 PSPACE 완료입니다.현재 상태로는 PSPACE-complete, EXPTIME-complete 또는 EXPSPACE-complete일 수 있습니다.

일본식 코룰

일본의 KO 규칙은 기본 KO, 즉 보드를 한 수 이전 상태로 되돌리는 동작만 금지되어 있습니다.더 긴 반복 상황이 허용되므로, 3개의 Ko가 동시에 있는 트리플 Ko와 같이 12개의 이동 사이클을 허용하는 영원히 루프할 수 있습니다.

일본의 ko 규칙에서는 Go는 EXPTIME ^[3]완료입니다.

슈퍼코 규칙

Superko 규칙(위치적 Superko 규칙이라고도 함)은 이전에 발생한 보드 위치의 반복을 금지합니다.이것은 대부분의 중국 및 미국 규칙 집합에서 사용되는 ko 규칙입니다.

바둑의 복잡도가 슈퍼코 규칙에 따라 어떻게 되어 있는지는 미해결 문제다.일본어로 Go with Japanese ko 규칙은 EXPTIME-완전하지만 슈퍼코 규칙이 추가되면 롭슨의 EXPTIME-완전성 증명^[3] 하한과 상한 모두 깨진다.

Go의 PSPACE 경도 증명은^[2] ko 규칙이나 ko 규칙의 결여에 의존하지 않기 때문에 적어도 PSPACE-hard인 것으로 알려져 있다.또한 Go는 EXPSPACE에 ^[4]있는 것으로 알려져 있습니다.

롭슨은^[4] EXPTIME-complete인 특정 2인용 게임에 슈퍼코 규칙, 즉 "이전 포지션이 재생성되지 않을 수 있다"가 추가되면 새로운 게임은 EXPACE-complete가 된다는 것을 보여주었다.직감적으로, 포지션에서 법적 이동을 결정하는 데도 기하급수적인 공간이 필요하기 때문에 포지션으로 이어지는 게임 이력은 기하급수적으로 길어질 수 있다.

그^[5] 결과, 일반 체스와 체커는^[6] EXPTIME-완성이므로 일반 체스와 체커의 슈퍼코 바리안트(이전 보드 위치를 반복하는 동작은 허용되지 않음)는 EXPACE-완성이 된다.그러나 ^[4]이 결과는 Go에는 적용되지 않습니다.

특정 Go 구성의 복잡성

바둑 끝 게임은 보드가 살아있는 돌에 의해 다른 모든 지역으로부터 격리된 영역으로 분할되어 각 지역마다 다항식 크기의 표준 게임 트리가 있을 때 시작됩니다.조합 게임 이론의 언어로, 바둑 게임이 다항식 크기의 표준 게임 트리를 가진 하위 게임의 합계로 분해될 때 발생합니다.

이 정의에서는 Go 엔드게임은 PSPACE 하드입니다.^[7]

이는 PSPACE-완전인 Quantified Boolean Formula 문제를 작은(다항식 크기의 정규 게임 트리 포함) Go 서브게임의 합계로 변환함으로써 입증된다.이 문서에서는 Go 엔드게임이 PSPACE에 있는 것을 증명하지 않기 때문에 PSPACE-complete가 아닐 수 있습니다.

일본의 코 룰과 슈퍼코 룰 중 어느 쪽이 ^[8]래더 캡쳐 레이스에서 우승할지를 결정하는 것은 PSPACE 완료입니다.이는 PSPACE-complete로 알려진 QBF를 광선처럼 보드 주위를 튕기는 사다리로 시뮬레이션함으로써 입증되었습니다.

법적 지위

보드의 각 위치는 빈 위치, 검은색 위치 또는 흰색 위치 중 하나이므로 길이가 n인 정사각형 보드에는 총 3개의^n² 보드 위치가 있지만 모든 위치가 합법적인 것은 아닙니다.Tromp와 Farnebeck는 길이가 m과 ^[9]n인 직사각형 보드의 법적 $L(m,n)$ L ( $L(m,n)$ , $L(m,n)$ $)(\displaystyle$ L ( $m$ , $n))$ 에 $L(m,n)$ 대한 재귀 공식을 도출했습니다.L $, 19)$ 의 $L(19,19)$ $L(19,19)$ 한 숫자는 ^[10]2016년에 파악되었습니다 $.$ 또한 $L\approx AB^{m+n}C^{mn}$ L $L\approx AB^{m+n}C^{mn}$ $L\approx AB^{m+n}C^{mn}$ B $L\approx AB^{m+n}C^{mn}$ m + $L\approx AB^{m+n}C^{mn}$ C $L\approx AB^{m+n}C^{mn}$ { $displaystyle$ L \ $approx$ AB^ { $m$ + $n$ } $C^$ { $mn$ } （ $0$ 0 . 850 $A\approx 0.8506399258457145$ 258457145 $\ displaystyle$ A $）$ $B\approx 0.96553505933837387$ 0 . 850 $63959258457145$ 、 B $96$ 0 . $B\approx 0.96553505933837387$ ） $B\approx 0.96553505933837387$ $357249381$ 관측 가능한 우주에는 일반 보드 크기(m=n=19)의 법적 위치 수보다 훨씬 적은 10개⁸⁰ 정도의 원자가 포함되어 있는 것으로 추정되고 있습니다.이사회가 커짐에 따라 합법적인 직책의 비율은 감소합니다.

보드 크기 n×n	3개^n²	적법률	$L$ {\ $displaystyle$ L $}$ (법적 위치) (A094777)^[11]
1 × 1	3	33.33%	1
2 × 2	81	70.37%	57
3 × 3	19,683	64.40%	12,675
4 × 4	43,046,721	56.49%	24,318,165
5 × 5	847,288,609,443	48.90%	414,295,148,741
9 × 9	4.4342648243 × 10³⁸	23.44%	1.03919148791 × 10³⁸
13 × 13	4.30023359390 × 10⁸⁰	8.66%	3.72497923077 × 10⁷⁹
19 × 19	1.74089650659 × 10¹⁷²	1.20%	2.08168199382 × 10¹⁷⁰

게임 트리의 복잡성

컴퓨터 과학자인 Victor Allis는 전문가들 간의 일반적인 게임들은 약 150개의 게임을 지속하며, 한 동작당 평균 약 250개의 선택지를 가지고 있으며, 게임 트리의 ^[12]복잡도는 10개임을³⁶⁰ 시사한다고 말한다.실제로 플레이할 수 없는 게임을 포함하여 이론적으로 가능한 게임 수에 대해서는 트롬프와 파네벡이 ^[9]각각 10과^10¹⁷¹ 10의^10⁴⁸ 하한선을 부여한다.하한선은 Walraet와 Tromp에 ^[13]의해 googolplex로 개선되었습니다.가능한 게임 수에 대해 가장 일반적으로 인용되는 숫자인⁷⁰⁰^[14] 10은 361개의 이동 또는 361! = 10의⁷⁶⁸ 단순 순열에서 파생됩니다.또^L 다른 일반적인 파생은 총 N개의 게임에 대해 N개의 교차로와 L개의 최장 게임을 가정하는 것입니다.예를 들어, 일부 프로 게임에서 볼 수 있듯이 400개의 움직임은 361개의⁴⁰⁰ 게임 중 하나 또는 1 × 10개의¹⁰²³ 가능한 게임 중 하나일 것이다.

가능한 총 게임 수는 보드의 크기와 이동 수 모두 함수입니다.대부분의 게임들이 400, 심지어 200개 미만으로 지속되는 반면, 더 많은 게임들이 가능하다.

게임 크기	보드 크기 N(교차로)	N!	평균 게임 길이 L	N^L	최대 게임 길이(이동 수)	게임의 하한	게임의 상한
2 × 2	4	24	3	64		386,356,909,593^[15]	386,356,909,593
3 × 3	9	3.6×10⁵	5	5.9×10⁴
4 × 4	16	2.1×10¹³	9	6.9×10¹⁰
5 × 5	25	1.6×10²⁵	15	9.3×10²⁰
9 × 9	81	5.8×10¹²⁰	45	7.6×10⁸⁵
13 × 13	169	4.3×10³⁰⁴	90	3.2×10²⁰⁰
19 × 19	361	1.0×10⁷⁶⁸	200	3×10⁵¹¹	10개⁴⁸	10개^10⁴⁸	10개^10¹⁷¹
21 × 21	441	2.5×10⁹⁷⁶	250	1.3×10⁶⁶¹

가능한 총 게임 수는 보드 크기에서 여러 가지 방법으로 추정할 수 있으며, 일부는 다른 것보다 더 엄격합니다.가장 간단한 것은 보드 크기(N)_L의 순열로, 부정한 캡처와 위치가 포함되지 않습니다.N을 기판 크기(19 × 19 = 361)로 하고 L을 최장 게임으로 하면 N은^L 상한을 형성한다.보다 정확한 한계는 Tromp/Farnebeck 문서에 제시되어 있습니다.

최장 게임 L(19×19)	(N)_L	게임의 하한	게임의 상한	메모들
1	361	361	361	흰색은 첫 번째 이동 후 다시 나타나며, 361은 y = x else(구석에서 이동) 10×10-10=90 90/2=45 +10(뒤로 이동 x = y 대칭점) = 55를 포함한 모든 대칭을 무시합니다.
2	722		721	검은색은 흰색의 첫 번째 움직임 후에 다시 나타나며, 721은 y=x other 19×19=342 342/2=171+19=190-1=189를 포함한 모든 대칭을 무시합니다.
50	2.1×10¹²⁶		7.5×10¹²⁷
100	1.4×10²⁴⁹		5.6×10²⁵⁵
150	6.4×10³⁶⁷		4.2×10³⁸³
200	1.9×10⁴⁸¹		3.2×10⁵¹¹
250	8.2×10⁵⁸⁷		2.4×10⁶³⁹
300	2.8×10⁶⁸⁴		7.8×10⁷⁶⁶
350	3.6×10⁷⁶⁰		1.3×10⁸⁹⁵
361	1.4×10⁷⁶⁸		1.8×10⁹²³	181개의 블랙 스톤과 180개의 화이트 스톤을 사용한 최장 게임
411	없음		1.3×10¹⁰⁵¹	최장^[16] 프로 게임
500	없음		5.7×10¹²⁷⁸
1000	없음		3.2×10²⁵⁵⁷
4700만	없음		10개^10⁸	361³ 무브
10개⁴⁸	없음	10개^10⁴⁸	10개^10¹⁷¹	최장수 게임

따라서⁷⁰⁰ 10은 200개의 이동으로 플레이할 수 있는 게임 수를 과대평가하고 361개의 이동으로 플레이할 수 있는 게임 수를 과소평가하는 것입니다.1년에 약 3천100만 초가 있기 때문에, 약 3천100만 초가 걸립니다.2+1⁄4년, 1초에 16시간씩 플레이하여 4700만 번의 플레이를 합니다.

「」를 참조해 주세요.

메모들

^ "Go Infinitesimals at Sensei's Library". senseis.xmp.net. Retrieved 2022-02-10.
^ ^a ^b Lichtenstein, David; Sipser, Michael (April 1980). "Go Is Polynomial-Space Hard" (PDF). Journal of the ACM. 27 (2): 393–401. doi:10.1145/322186.322201. S2CID 29498352.
^ ^a ^b Robson, John (1983). "The complexity of Go". Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417.
^ ^a ^b ^c Robson, J (1984). "Combinatorial games with exponential space complete decision problems". Mathematical Foundations of Computer Science 1984. Proceedings of the Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. Vol. 176. pp. 498–506. doi:10.1007/BFb0030333. ISBN 978-3-540-13372-8.
^ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Theory A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9.
^ J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018.
^ Wolfe, David (2002). Nowakowski, Richard J. (ed.). "Go endgames are PSPACE-hard" (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125–136.
^ Crâşmaru, Marcel; Tromp, John (2000). Ladders are PSPACE-Complete. Computers and Games. Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 241–249. CiteSeerX 10.1.1.24.4665. doi:10.1007/3-540-45579-5_16. ISBN 978-3-540-43080-3.
^ ^a ^b Tromp, J; Farnebäck, G (2007), Combinatorics of Go, Springer, Berlin, Heidelberg, doi:10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1
^ https://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 678 633 344 862 770 286 522 453 884 530 548 639 820 927 412 738 378 525 648 451 519 643 903 909 015 628 546 888 314 129 7157 3157
^ https://tromp.github.io/go/gostate.pdf^{[베어 URL PDF]}
^ 앨리스 1994
^ Walraet, M; Tromp, J (2016), A Googolplex of Go Games, Springer, Berlin, Heidelberg, doi:10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1
^ AGA – 바둑을 두는 10가지 이유
^ 트롬프 1999
^ "Statistics on the length of a go game".

레퍼런스

AGA. "Top Ten Reasons to Play Go".
Allis, Victor (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 978-90-900748-8-7.
Hearn, Robert A. (2006). "Games, Puzzles, and Computation" (PDF). [박사 논문, MIT]
Johnson, George (1997-07-29). "To Test a Powerful Computer, Play an Ancient Game". New York Times.
파파디미트리우, 크리스토스(1994), 계산 복잡도, 애디슨 웨슬리.
Tromp, John (1999). "Number of 2×2 games with positional superko".
Tromp, John (2016). "Number of legal Go positions (up to 19×19)".
Tromp, John; Farnebäck, Gunnar (2007). "Combinatorics of Go".

외부 링크

바둑과 수학하기
Sensei's Library 게임 결과 수 - 기사

[1] "Go Infinitesimals at Sensei's Library". senseis.xmp.net. Retrieved 2022-02-10.

[sipser1980-2] Lichtenstein, David; Sipser, Michael (April 1980). "Go Is Polynomial-Space Hard" (PDF). Journal of the ACM. 27 (2): 393–401. doi:10.1145/322186.322201. S2CID 29498352.

[robson1983-3] Robson, John (1983). "The complexity of Go". Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417.

[robson1984-4] Robson, J (1984). "Combinatorial games with exponential space complete decision problems". Mathematical Foundations of Computer Science 1984. Proceedings of the Mathematical Foundations of Computer Science. Lecture Notes in Computer Science. Vol. 176. pp. 498–506. doi:10.1007/BFb0030333. ISBN 978-3-540-13372-8.

[Fraenkel1981-5] Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Theory A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9.

[robson1984checkers-6] J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018.

[7] Wolfe, David (2002). Nowakowski, Richard J. (ed.). "Go endgames are PSPACE-hard" (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125–136.

[8] Crâşmaru, Marcel; Tromp, John (2000). Ladders are PSPACE-Complete. Computers and Games. Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 241–249. CiteSeerX 10.1.1.24.4665. doi:10.1007/3-540-45579-5_16. ISBN 978-3-540-43080-3.

[Tromp_and_Farnebäck_2007-9] Tromp, J; Farnebäck, G (2007), Combinatorics of Go, Springer, Berlin, Heidelberg, doi:10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1

[10] ttps://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 678 633 344 862 770 286 522 453 884 530 548 639 820 927 412 738 378 525 648 451 519 643 903 909 015 628 546 888 314 129 7157 3157

[11] ttps://tromp.github.io/go/gostate.pdf^{[베어 URL PDF]}

[12] 앨리스 1994

[13] Walraet, M; Tromp, J (2016), A Googolplex of Go Games, Springer, Berlin, Heidelberg, doi:10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1

[top_ten-14] AGA – 바둑을 두는 10가지 이유

[15] 트롬프 1999

[16] "Statistics on the length of a go game".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v t 가세요
개요	핸디캡 코미 규칙.
장비.	그릇 고반 카츠라 카야 스톤즈 클램셸 슬레이트 윤지
조건.	아지 아타리 보드의 위치 다메 신의 한 수 더블 헤인 눈 고테, 센테, 테누키 하네 하야고 지고 호세키 카카리 케이마 기아이 키카시 고 코미 코리가타치 코스미 사다리 자유 미아이 몽키점프 모요 묘슈 나카데 네라이 묘슈 삑삑이 핀처 프로브 사바키 세키 센테 모양. 숄더 히트 테수지 두께 요세
전략과 전술	레이스 캡처 후세키 중국인 고바야시 신후세키 슈사쿠 조세키 나다레 타이샤 Ko fight 사다리 생사 미러 고 오프닝 이론 속담 모양. 빈 삼각형 폰누키 테누키 쓰메고
역사	클래식 오브 아트 둔황고 매뉴얼 야오 천황제 포고 하우스 사예 호엔샤 9핀지 오스카 코르셸트 오시로고 플레이어 유럽 선수 여자 선수 일본기원 명예의 전당 프로페셔널 핸디캡
경쟁.	프로페셔널하게 등급 및 평가 댄. 규 명예 직함 주방고 직함 보유자 토너먼트
게임과 경기	알파고 vs. 판후이 알파고 대 커제 알파고와이세돌 원폭 게임 피를 뽑는 게임 귀를 찢는 게임 세기의 게임 가마쿠라 주반고 리의 깨진 사다리 게임
아트 및 미디어	알파고 더 디바인 무브 바둑을 둔 소녀 바둑의 달인 바둑 기사 Go World(고월드) 고스트바둑왕 이고 하쓰요론 웨이지 관전 송가 바둑의 달인 란카 선생님 도서관 시부미 서라운드 게임 웨이지 데빌
컴퓨터	컴퓨터 Go UEC컵 엔진 알파고 알파고 마스터 알파고 제로 알파제로 크레이지 스톤 다크 포레스트 파인 아트 GNU Go 카타고 릴라 릴라 제로 선 바둑 서밋의 미래 몬테카를로 트리 검색 스마트 게임 포맷 서버 KGS Go 서버 판다넷 타이젬
단체들	미국 바둑 협회 오스트레일리아 바둑 협회 영국 바둑 협회 중국 중국 치위안 중국 웨이지 협회 홍콩 바둑 협회 유럽 바둑 연맹 프랑스 바둑 연맹 국제 바둑 연맹 아일랜드 바둑 협회 일본. 전일본 학생 바둑 연맹 간사이 기인 니혼기인 코리아 한국기원 명지대 마인드 스포츠 조직 뉴질랜드 바둑 협회 싱가포르 웨이지 협회 대만 지위안 문화재단
다른.	벤슨 알고리즘 경기기록(키후) 바둑 기기로 하는 경기 가서 수학해 변종 바투 캡처 Go 시고
포털로 이동 카테고리

Search

가서 수학해

네임스페이스

더

목차

계산의 복잡성

ko 없음

일본식 코룰

슈퍼코 규칙

특정 Go 구성의 복잡성

법적 지위

게임 트리의 복잡성

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

가서 수학해

계산의 복잡성

ko 없음

일본식 코룰

슈퍼코 규칙

특정 Go 구성의 복잡성

법적 지위

게임 트리의 복잡성

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.