โกะและคณิตศาสตร์

Q: ความซับซ้อนในการคำนวณ

เกมโกะแบบทั่วไปเล่นบน กระดาน ขนาด n × n และ ความซับซ้อนในการคำนวณ เพื่อหาผู้ชนะในตำแหน่งที่กำหนดของเกมโกะแบบทั่วไปนั้นขึ้นอยู่กับ กฎโค เป็น อย่างมาก

เกมโกะเป็นหนึ่งในเกมที่ได้รับความนิยมมากที่สุดในโลก ด้วยกฎที่สง่างามและเรียบง่าย เกมนี้จึงเป็นแรงบันดาลใจให้กับการวิจัยทางคณิตศาสตร์ มาอย่างยาวนาน Shen Kuoนักวิชาการชาวจีนในศตวรรษที่ 11 ได้ประมาณการไว้ในเรียงความ Dream Pool ของเขา ว่าจำนวนตำแหน่งบนกระดานที่เป็นไปได้มีประมาณ 10 ¹⁷²ตำแหน่ง ในช่วงไม่กี่ปีที่ผ่านมา การวิจัยเกมโดยJohn H. Conwayนำไปสู่การพัฒนาจำนวนเหนือจริงและมีส่วนช่วยในการพัฒนาทฤษฎีเกมเชิงการจัดเรียง (โดย Go Infinitesimals ^{[ 1 ]}เป็นตัวอย่างเฉพาะของการใช้งานในเกมโกะ)

ความซับซ้อนในการคำนวณ

เกมโกะแบบทั่วไปเล่นบน กระดาน ขนาด n × nและความซับซ้อนในการคำนวณเพื่อหาผู้ชนะในตำแหน่งที่กำหนดของเกมโกะแบบทั่วไปนั้นขึ้นอยู่กับกฎโคเป็น อย่างมาก

เกมโกะ "เกือบ" จะอยู่ในPSPACEเพราะในการเล่นปกติ การเดินหมากไม่สามารถย้อนกลับได้ และมีเพียงการจับกินเท่านั้นที่จะทำให้เกิดรูปแบบซ้ำๆ ที่จำเป็นต่อความซับซ้อนที่มากขึ้นได้

โดยไม่มี ko

หากไม่มี ko เกมโกะจะ ยากใน ระดับPSPACE ^{[ 2 ]}สิ่งนี้ได้รับการพิสูจน์โดยการลดTrue Quantified Boolean Formulaซึ่งทราบกันดีว่าสมบูรณ์แบบในระดับ PSPACE ไปสู่ภูมิศาสตร์ทั่วไปไปสู่ภูมิศาสตร์ทั่วไปแบบระนาบ ไปสู่ภูมิศาสตร์ทั่วไปแบบระนาบที่มีดีกรีสูงสุด 3และสุดท้ายไปสู่ตำแหน่งโกะ

กฎโคของญี่ปุ่น

กฎโคของญี่ปุ่นระบุว่า มีเพียงโคพื้นฐานเท่านั้นที่ถูกห้าม นั่นคือ การเดินหมากที่ทำให้กระดานกลับไปสู่สถานการณ์ก่อนหน้าหนึ่งตาเดิน ส่วนสถานการณ์ที่ซ้ำซ้อนยาวกว่านั้นได้รับอนุญาต ซึ่งอาจทำให้เกมวนลูปไปเรื่อยๆ ได้ เช่น โคสามตัวพร้อมกัน (triple ko) ที่มีโคสามตัวเกิดขึ้นพร้อมกัน ทำให้เกิดวงจรการเดินหมาก 12 ตา

ด้วยกฎโคของญี่ปุ่น เกมโกะจะเสร็จสมบูรณ์ในเวลา EXPTIME ^{[ 3 ]}

กฎซูเปอร์โกะ

กฎซูเปอร์โกะ (หรือเรียกว่ากฎซูเปอร์โกะเชิงตำแหน่ง) ระบุว่าห้ามมิให้มีการซ้ำซ้อนของตำแหน่งบนกระดานที่เคยเกิดขึ้นมาก่อน นี่คือกฎโคที่ใช้ในกฎกติกาหมากรุกส่วนใหญ่ของจีนและสหรัฐอเมริกา

เป็นปัญหาที่ยังเปิดอยู่ว่าคลาสความซับซ้อนของโกะภายใต้กฎซูเปอร์โกะคืออะไร แม้ว่าโกะที่มีกฎโคของญี่ปุ่นจะสมบูรณ์แบบ EXPTIME แต่ขอบเขตล่างและขอบเขตบนของการพิสูจน์ความสมบูรณ์ EXPTIME ของ Robson ^{[ 3 ]}ก็พังทลายลงเมื่อมีการเพิ่มกฎซูเปอร์โกะ

เป็นที่ทราบกันว่าอย่างน้อยก็มีความยากระดับ PSPACE เนื่องจากหลักฐานใน^{[ 2 ]}ของความยากระดับ PSPACE ของโกะไม่ได้อาศัยกฎ ko หรือการขาดกฎ ko นอกจากนี้ยังเป็นที่ทราบกันว่าโกะอยู่ใน EXPSPACE ^{[ 4 ]}

Robson ^{[ 4 ]}แสดงให้เห็นว่าหากกฎ superko ซึ่งก็คือ “ไม่สามารถสร้างตำแหน่งก่อนหน้าซ้ำได้อีก” ถูกเพิ่มเข้าไปในเกมสองผู้เล่นบางเกมที่ EXPTIME-complete แล้ว เกมใหม่เหล่านั้นจะเป็น EXPSPACE-complete ตามสัญชาตญาณแล้ว นี่เป็นเพราะต้องใช้พื้นที่จำนวนมหาศาลแม้กระทั่งในการกำหนดการเดินที่ถูกต้องจากตำแหน่งหนึ่ง เนื่องจากประวัติเกมที่นำไปสู่ตำแหน่งนั้นอาจยาวนานเป็นเลขชี้กำลัง

ด้วยเหตุนี้ ตัวแปร superko (การเดินหมากที่ซ้ำตำแหน่งกระดานก่อนหน้าไม่ได้รับอนุญาต) ของหมากรุกและหมากฮอส ทั่วไป จึงสมบูรณ์ใน EXPSPACE เนื่องจากหมากรุกทั่วไป^{[ 5 ]}และหมากฮอส^{[ 6 ]}สมบูรณ์ใน EXPTIME อย่างไรก็ตาม ผลลัพธ์นี้ใช้ไม่ได้กับโกะ^{[ 4 ]}

ความซับซ้อนของการกำหนดค่า Go บางอย่าง

เกมโกะช่วงท้ายเริ่มขึ้นเมื่อกระดานถูกแบ่งออกเป็นพื้นที่ต่างๆ ที่แยกออกจากพื้นที่อื่นๆ ด้วยหมากมีชีวิต โดยแต่ละพื้นที่จะมีต้นไม้เกมมาตรฐานที่มีขนาดเป็นพหุนาม ในทางทฤษฎีเกมเชิงการจัดเรียง เกมโกะช่วงท้าย จะเกิดขึ้นเมื่อเกมโกะแตกออกเป็นผลรวมของเกมย่อยที่มีต้นไม้เกมมาตรฐานที่มีขนาดเป็นพหุนาม

ด้วยคำจำกัดความนั้น เกมโกะช่วงท้ายจึงยากระดับ PSPACE ^{[ 7 ]}

สิ่งนี้ได้รับการพิสูจน์โดยการแปลง ปัญหา Quantified Boolean Formulaซึ่งเป็นปัญหา PSPACE-complete ให้เป็นผลรวมของเกมโกะย่อยขนาดเล็ก (ที่มีต้นไม้เกมมาตรฐานขนาดพหุนาม) โปรดทราบว่าบทความนี้ไม่ได้พิสูจน์ว่าเกมโกะช่วงท้ายเกมอยู่ใน PSPACE ดังนั้นจึงอาจไม่ใช่ปัญหา PSPACE-complete

การตัดสินว่าฝ่ายใดชนะ การแข่งขันยึด บันไดนั้นถือว่าสมบูรณ์ใน PSPACE ไม่ว่าจะใช้กฎ ko ของญี่ปุ่นหรือกฎ superko ก็ตาม^{[ 8 ]}สิ่งนี้ได้รับการพิสูจน์แล้วโดยการจำลอง QBF ซึ่งเป็นที่รู้จักกันว่าสมบูรณ์ใน PSPACE ด้วยบันไดที่กระเด้งไปมาบนกระดานเหมือนลำแสง

ตำแหน่งทางกฎหมาย

เนื่องจากแต่ละตำแหน่งบนกระดานสามารถเป็นได้ทั้งว่าง สีดำ หรือสีขาว จึงมีตำแหน่งบนกระดานที่เป็นไปได้ทั้งหมด 3 ^{n ²}ตำแหน่งบนกระดานสี่เหลี่ยมจัตุรัสที่มีความยาวnอย่างไรก็ตาม ไม่ใช่ทุกตำแหน่งที่ถูกต้องTrompและ Farnebäck ได้กำหนดสูตรเวียนเกิดสำหรับตำแหน่งที่ถูกต้องของกระดานสี่เหลี่ยมผืนผ้าที่มีความยาวmและn ^[⁹ ] จำนวนที่แน่นอนของได้รับในปี 2016 ^[¹⁰^]พวกเขายังพบสูตรเชิงเส้นกำกับโดยที่และมีการประมาณการว่าเอกภพที่สังเกตได้มีอะตอมประมาณ 10 ^{80 อะตอม ซึ่งน้อยกว่าจำนวนตำแหน่งที่ถูกต้องที่เป็นไปได้ของกระดานขนาด}^ปกติ (m=n=19) มาก เมื่อกระดานมีขนาดใหญ่ขึ้น เปอร์เซ็นต์ของตำแหน่งที่ถูกต้องจะลดลง $L(m,n)$ $L(19,19)$ $L\approx AB^{m+n}C^{mn}$ $A\approx 0.8506399258457145$ $B\approx 0.96553505933837387$ $C\approx 2.975734192043357249381$

ขนาดกระดาน n×n	3 ^น²	เปอร์เซ็นต์ที่ถูกกฎหมาย	$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.43426488243 × 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 ตัวเลือกต่อตาเดิน ซึ่งบ่งชี้ถึงความซับซ้อนของต้นไม้เกมที่ 10 360 ^[^{12 ] สำหรับ}จำนวน เกม ที่เป็นไปได้ในทางทฤษฎีรวมถึงเกมที่ไม่สามารถเล่นได้ในทางปฏิบัติ Tromp และ Farnebäck ให้ขอบเขตล่างและขอบเขตบนที่ 10 ^{10 ⁴⁸}และ 10 ^{10 ¹⁷¹}ตามลำดับ^{[ 9 ]} ขอบเขตล่างได้รับการปรับปรุงเป็นgoogolplexโดย Walraet และ Tromp ^{[ 13 ]} ตัวเลขที่อ้างถึงบ่อยที่สุดสำหรับจำนวนเกมที่เป็นไปได้คือ 10 ⁷⁰⁰^{[ 14 ]}ได้มาจากการเรียงสับเปลี่ยนอย่างง่ายของ 361 ตาเดิน หรือ361! = 10 ⁷⁶⁸การคำนวณทั่วไปอีกวิธีหนึ่งคือการสมมติว่า มีจุดตัด Nจุด และ เกมที่ยาวที่สุด Lเกม สำหรับเกมทั้งหมดN ^L เกม ตัวอย่างเช่น การเดินหมาก 400 ครั้ง อย่างที่เห็นในเกมระดับมืออาชีพบางเกม จะคิดเป็นเพียง 1 ใน 361,400 ^หรือ 1 × ^10¹⁰²³เกมที่เป็นไปได้

จำนวนเกมทั้งหมดที่เป็นไปได้นั้นขึ้นอยู่กับทั้งขนาดของกระดานและจำนวนตาเดินที่เล่น แม้ว่าเกมส่วนใหญ่จะใช้เวลาน้อยกว่า 400 หรือ 200 ตาเดิน แต่ก็ยังมีเกมอีกมากมายที่เป็นไปได้

ขนาดเกม	ขนาดกระดาน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.4 × 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เป็นจำนวนเกมที่ยาวที่สุดNLจะเป็นค่าขีดจำกัดบน ค่าขีดจำกัดที่แม่นยำกว่านี้ได้นำเสนอไว้ในบทความของ Tromp/Farnebäck

เกมที่ยาวที่สุดL (19 × 19)	( N )	ขีดจำกัดล่างของเกม	ขีดจำกัดสูงสุดของเกม	หมายเหตุ
1	361	361	362	ฝ่ายขาวถอนตัวหลังจากเดินหมากครั้งแรก 361 (362 ถ้ารวมการเดินผ่าน) โดยไม่คำนึงถึงความสมมาตรทั้งหมด รวมถึงy = xมิฉะนั้น (ระยะห่างจากมุม) 10×10−10=90 90/2=45 +10 (บวกจุดสมมาตร x = y กลับเข้าไป) = 55 (56 ถ้ารวมการเดินผ่าน)
2	129960		130682	361(ดำ)× 360(ขาว) + 361(ผ่านสีดำ) + 361(ผ่านสีขาว)
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 ⁵¹¹
211	2.5 × 10 ⁵⁰⁵		4.3 × 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 ²⁵⁵⁷
47045881	ไม่มีข้อมูล		10 ^{10 ⁸}	361 ³การเคลื่อนไหว
10 ⁴⁸	ไม่มีข้อมูล	10 ^{10 ¹⁰⁰}	10 ^{10 ¹⁷¹}	เกมที่ยาวที่สุด

ดังนั้น 10,700 จึงเป็นการประมาณค่าที่สูงเกินไปของจำนวนเกมที่เป็นไปได้ที่สามารถเล่นได้ใน 200 ตาเดิน และเป็นการประมาณค่าที่ต่ำเกินไปของจำนวนเกมที่สามารถเล่นได้ใน 361 ตาเดิน เนื่องจากมีประมาณ 31 ล้านวินาทีในหนึ่งปี จึงต้องใช้เวลา^{ประมาณ}2+ใช้ เวลา1/4 ปีเล่นวันละ 16 ชั่วโมง ด้วยความเร็ว 1 ตาเดินต่อวินาที รวมแล้วได้ 47 ล้านตาเดิน

ดูเพิ่มเติม

หมายเหตุ

^ "Go Infinitesimals ที่ห้องสมุดของอาจารย์" senseis.xmp.net . สืบค้นเมื่อ2022-02-10 .
^ ^a ^b Lichtenstein, David; Sipser, Michael (เมษายน 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). "ความซับซ้อนของเกมโกะ". รายงานการประชุม IFIP 9th World Computer Congress on Information Processing : 413– 417.
^ ^a ^b ^c Robson, J (1984). "เกมเชิงการจัดเรียงที่มีปัญหาการตัดสินใจที่สมบูรณ์แบบในพื้นที่เอกซ์โพเน นเชียล" พื้นฐานทางคณิตศาสตร์ของวิทยาศาสตร์คอมพิวเตอร์ 1984 บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์ เล่มที่ 176 หน้า 498–506 doi : 10.1007/BFb0030333 ISBN 978-3-540-13372-8.{{cite book}}: |journal=ละเลย ( ช่วยเหลือ )
^ Aviezri Fraenkelและ D. Lichtenstein (1981). "การคำนวณกลยุทธ์ที่สมบูรณ์แบบสำหรับหมากรุก n×n ต้องใช้เวลาแบบเลขชี้กำลังใน n" . J. Comb. Theory A . 31 (2): 199– 214. doi : 10.1016/0097-3165(81)90016-9 .
^ JM 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. (บรรณาธิการ). "เกมโกะช่วงท้ายเกมยากระดับ PSPACE" (PDF) More Games of No Chance, Mathematical Sciences Research Institute Publications 42 : 125– 136. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2017-08-10 สืบค้นเมื่อ2016-07-09
^ 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", Computers and Games , Lecture Notes in Computer Science, vol. 4630, Springer, Berlin, Heidelberg, pp. 84– 99, 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 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
^ "Combinatorics of Go" (PDF) . github.io . สืบค้นเมื่อ17 มิถุนายน 2023 .
^อัลลิส 1994
^ Walraet, M; Tromp, J (2016), "เกมโกะ Go ที่ซับซ้อนมหาศาล", คอมพิวเตอร์และเกม , บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์, เล่มที่ 10068, Springer, เบอร์ลิน, ไฮเดลเบิร์ก, หน้า 191–201 , doi : 10.1007/978-3-319-50935-8_18 , ISBN 978-3-319-50934-1
^ "หน้าหลัก - สมาคมโกะแห่งอเมริกา" . www.usgo.org . สืบค้นเมื่อ17 มิถุนายน 2023 .
^ทรอมป์ 1999
^ "สถิติเกี่ยวกับระยะเวลาของเกมโกะ "

ลิงก์ภายนอก

เกมโกะและคณิตศาสตร์
จำนวนผลลัพธ์ที่เป็นไปได้ของเกม - บทความในห้องสมุดของอาจารย์

[1] "Go Infinitesimals ที่ห้องสมุดของอาจารย์" senseis.xmp.net . สืบค้นเมื่อ2022-02-10 .

[sipser1980-2] Lichtenstein, David; Sipser, Michael (เมษายน 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). "ความซับซ้อนของเกมโกะ". รายงานการประชุม IFIP 9th World Computer Congress on Information Processing : 413– 417.

[robson1984-4] Robson, J (1984). "เกมเชิงการจัดเรียงที่มีปัญหาการตัดสินใจที่สมบูรณ์แบบในพื้นที่เอกซ์โพเน นเชียล" พื้นฐานทางคณิตศาสตร์ของวิทยาศาสตร์คอมพิวเตอร์ 1984 บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์ เล่มที่ 176 หน้า 498–506 doi : 10.1007/BFb0030333 ISBN 978-3-540-13372-8.{{cite book}}: |journal=ละเลย ( ช่วยเหลือ )

[Fraenkel1981-5] Aviezri Fraenkelและ D. Lichtenstein (1981). "การคำนวณกลยุทธ์ที่สมบูรณ์แบบสำหรับหมากรุก n×n ต้องใช้เวลาแบบเลขชี้กำลังใน n" . J. Comb. Theory A . 31 (2): 199– 214. doi : 10.1016/0097-3165(81)90016-9 .

[robson1984checkers-6] JM 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. (บรรณาธิการ). "เกมโกะช่วงท้ายเกมยากระดับ PSPACE" (PDF) More Games of No Chance, Mathematical Sciences Research Institute Publications 42 : 125– 136. เก็บถาวรจากต้นฉบับ(PDF)เมื่อ 2017-08-10 สืบค้นเมื่อ2016-07-09

[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", Computers and Games , Lecture Notes in Computer Science, vol. 4630, Springer, Berlin, Heidelberg, pp. 84– 99, 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 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935

[11] "Combinatorics of Go" (PDF) . github.io . สืบค้นเมื่อ17 มิถุนายน 2023 .

[12] อัลลิส 1994

[13] Walraet, M; Tromp, J (2016), "เกมโกะ Go ที่ซับซ้อนมหาศาล", คอมพิวเตอร์และเกม , บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์, เล่มที่ 10068, Springer, เบอร์ลิน, ไฮเดลเบิร์ก, หน้า 191–201 , doi : 10.1007/978-3-319-50935-8_18 , ISBN 978-3-319-50934-1

[top_ten-14] "หน้าหลัก - สมาคมโกะแห่งอเมริกา" . www.usgo.org . สืบค้นเมื่อ17 มิถุนายน 2023 .

[15] ทรอมป์ 1999

[16] "สถิติเกี่ยวกับระยะเวลาของเกมโกะ "

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[

[ 11 ]

12 ] สำหรับ

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]