囲碁と数学とは？わかりやすく解説

本項では、囲碁を数学的に研究する試みについて扱う。シンプルなルールゆえに、囲碁は長らく数学研究の対象となってきた。古くは11世紀の中国学者・沈括が『夢渓筆談』において19路盤の囲碁の合法な盤面の総数の計算を試みており、 3³⁶¹ から約 10¹⁷² と推定した。近年では、ジョン・H・コンウェイによる囲碁研究が超現実数の創出につながり、組合せゲーム理論（英語版）の発展に寄与した。囲碁におけるその応用例として、具体的なものにGo Infinitesimals^[1]がある。

計算複雑性

n 路盤（ n ✕ n のサイズの碁盤）の囲碁において、任意の局面での勝者を算出するための計算複雑性は、コウのルールに大きく依存する。

囲碁は「ほぼ」PSPACEに属する。一度盤面に打たれた石は基本的にそのままであり、より複雑な反復形が生じ得るのは、石取りが絡んだ場合に限られるからである。

コウを考慮しない場合

コウのない囲碁はPSPACE困難である^[2]。これは、PSPACE完全であることが知られているTQBF問題を、 generalized geography（英語版）、平面 generalized geography 、最大次数 3 の generalized geography 、最終的に囲碁の局面へと還元することで証明される。

超コウルールの碁がPSPACEに含まれるかどうかは知られていない。実際の対局が n² 手を超えることは稀であるが、総手数に多項式上界が存在するかも不明である。もし存在すればPSPACE完全となる。現状では、PSPACE完全、EXPTIME完全、あるいはEXPSPACE完全である可能性すらある。

日本ルール

日本ルールにおいては、コウは1手前の状態に戻す手のみが禁止されているだけであり、三コウや四コウのように、同じ盤面の循環が生じる可能性もある。

日本ルールでは、囲碁はEXPTIME完全である^[3]。

超コウルール

超コウルールは中国ルールや米国ルールなどで採用されており、以前に発生した盤面の再現をすべて禁じるルールである。

超コウルールにおける囲碁の複雑性クラスは未解決問題である。日本ルールであればEXPTIME完全であるが、 Robson (1983) によるEXPTIME完全性の証明^[3]における下界と上界の両方が、超コウルール下では破綻する。

ただし、少なくともPSPACE困難であることは知られている。囲碁がPSPACE困難であることを示す証明^[2]は、コウのルールに依存していないからである。また、EXPSPACEに属することも知られている。^[4]

Robson (1984)^[4] は、EXPTIME完全である任意の二人用ゲームに「超コウルール」、すなわち「過去の局面を再現してはならない」というルールを追加した場合、新たなゲームがEXPSPACE完全になることを示した。これは、ある局面から合法な着手を決定する際にも、その局面に至るまでの手数が指数関数的に長くなっている可能性があるため、結局は指数関数的な量の空間が必要となるためである。

したがって、一般化したチェスやチェッカーの超コウルール版（以前の盤面の再現を禁止したルール）は、一般化したチェス^[5]やチェッカー^[6]がEXPTIME完全であることから、EXPSPACE完全である。ただし、この結果は囲碁には適用されない^[4]。

特定の条件での複雑性

盤面が生き石によって孤立した各領域に分割されると、対局は終盤（ヨセ）へ入る。この時、各領域は、多項式レベルの正規化されたゲーム木を持つ。組合せゲーム理論の用語に言い換えれば、盤面が多項式レベルの正規化されたゲーム木を持つサブゲーム（英語版）の和に分解されると、終盤に入る。

この定義に従えば、囲碁の終盤はPSPACE困難である^[7]。

これは、PSPACE完全であるQBF問題を、小さな（多項式レベルの正規化されたゲーム木を持つ）サブゲームの和に変換することで証明される。ただし、囲碁の終盤がPSPACEであることは証明されていないため、実際にPSPACE完全であるかは不明である。

シチョウが成立しているかどうかの判定は、コウのルールとは無関係に、PSPACE完全である^[8]。これは、盤面を跳ね回るシチョウを、PSPACE完全であるQBF問題としてシミュレートすることで証明される。

合法な盤面の総数

盤上の各着点は黒、白、空点のいずれかであるため、 n 路盤には 3^n² の盤面図が存在する。ただし、その中には着手禁止点に石があるなどの非合法な盤面が含まれるため、合法な盤面の総数はそれよりも少なくなる。

2007年、 Tromp と Farnebäck が、長さ m と n の長方形の碁盤における合法な盤面の総数 L(m, n) の再帰式を2007年に導出した^[9]。更に、2016年には同氏らにより19路盤の合法な盤面の総数の正確な値（およそ 2.08✕10¹⁷⁰ ^{[注 1]}）が得られた^[10]。

L(m, n) については、以下のような漸近式も与えられている^[10]。

$L\approx AB^{m+n}C^{mn}$ , ただし $A\approx 0.8506399258457145$ , $B\approx 0.96553505933837387$ , $C\approx 2.975734192043357249381$

観測可能な宇宙には約 10⁸⁰ 個の原子があると推定されているが、これは19路盤の囲碁における合法な盤面の総数よりはるかに少ない。また、盤が大きくなるにつれて、合法的な盤面の割合は減少する。

盤の大きさ ( n 路盤)	3^n²	合法な盤面の割合	$L$ (合法な盤面の総数) ^[11]
1	3	33.33%	1
2	81	70.37%	57
3	19,683	64.40%	12,675
4	43,046,721	56.49%	24,318,165
5	847,288,609,443	48.90%	414,295,148,741
9	4.43426488243 × 10³⁸	23.44%	1.03919148791 × 10³⁸
13	4.30023359390 × 10⁸⁰	8.66%	3.72497923077 × 10⁷⁹
19	1.74089650659 × 10¹⁷²	1.20%	2.08168199382 × 10¹⁷⁰

ゲーム木の複雑性

コンピュータ科学者のヴィクター・アリス（英語版）は、プロ同士の通常の対局は約150手続き、1手あたり平均約250の選択肢があると考え、ゲーム木の複雑性を 10³⁶⁰ 程度であると推測した^[12]^{[注 2]}。 10⁷⁰⁰ という値が言及されることもあるが^[14]、これは 361! = 10⁷⁶⁸ という単純な順列から得られる値である。

非現実的な盤面や進行も含む、理論上可能なゲーム木の複雑性について、Tromp と Farnebäck は 10^10⁴⁸ という下限と、10^10¹⁷¹ という上限を与えた^[9]。のちに下限は Walraet と Tromp によって 10^10¹⁰⁰ まで改善された^[15]。

可能なゲームの総数は、盤の大きさ（合法な着点の数）と対局での手数をもとに算出が試みられることが多いが、その推定方法に決まった定義はない。以下に例を示す。

盤の大きさ ( n 路盤)	着点 N = n²	N!	仮の平均手数 L	N^L	理論上の最長手数	総ゲーム数の下限	総ゲーム数の上限
2	4	24	3	64		386,356,909,593^[16]	386,356,909,593
3	9	3.6×10⁵	5	5.9×10⁴
4	16	2.1×10¹³	9	6.9×10¹⁰
5	25	1.6×10²⁵	15	9.3×10²⁰
9	81	5.8×10¹²⁰	45	7.6×10⁸⁵
13	169	4.3×10³⁰⁴	90	3.2×10²⁰⁰
19	361	1.4×10⁷⁶⁸	200	3.2×10⁵¹¹	10⁴⁸	10^10¹⁰⁰	10^10¹⁷¹
21	441	2.5×10⁹⁷⁶	250	1.3×10⁶⁶¹

ゲーム木の複雑性をある程度正確に考えようとするとき、最も単純な方法は盤面サイズ (N) と最長手数 (L) の組合せ _NP_L になるが、これは非合法な着手や盤面の変化を考慮しない値となる。より正確なゲーム数の上限は、 Tromp と Farnebäck の論文で提示されている。

以下は19路盤での最長手数とゲーム木の複雑性の関係である。

最長手数 L	₃₆₁P_L	ゲーム数の下限	ゲーム数の上限	備考
1	361	361	362	白が初手で投了。初手361種類（盤の対称性は考慮せず）にパスを加え362種類。
2	129960		130682	361(黒1)× 360(白2) + 361(黒1がパス) + 361(白2がパス)
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⁵³⁹	プロの対局の平均手数^[13]
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子すべてを使った場合^{[注 3]}
411	n/a		1.3×10¹⁰⁵¹	プロの対局の最長手数^[13]
500	n/a		5.7×10¹²⁷⁸
1000	n/a		3.2×10²⁵⁵⁷
47045881	n/a		10^10⁸	361³ = 47045881
10⁴⁸	n/a	10^10¹⁰⁰	10^10¹⁷¹	理論上の最長手数

10⁷⁰⁰という見積りも、200手程度で終局すると考えれば過大評価である一方、361手まで対局を続けるという立場から考えれば過小評価であるし、それ以上の長手数を戦うことも不可能ではない。なお、4700万手の対局を行うならば、1秒に1手ずつ1日16時間対局したとしても、約2年3か月かかる計算となる。

脚注

注釈

^ 正確な値：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
^ ただし、実際には19路盤の平均手数は200手を超えており^[13]、ゲーム木の複雑性はより大きいと考えられる。
^ 実際には、碁石をすべて使い切ったとしても、終局していない場合は双方のアゲハマを交換することで対局を続ける。コウが長引いたときなどに、実戦でも発生することがある。

出典

^ “Go Infinitesimals at Sensei's Library”. senseis.xmp.net. 2022年2月10日閲覧。
^ ^a ^b Lichtenstein, David; Sipser, Michael (April 1980). “Go Is Polynomial-Space Hard”. Journal of the ACM 27 (2): 393–401. doi:10.1145/322186.322201.
^ ^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. Lecture Notes in Computer Science. 176. 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”. More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125–136. オリジナルの2017-08-10時点におけるアーカイブ。 2016年7月9日閲覧。.
^ Crâşmaru, Marcel; Tromp, John (2000). “Ladders Are PSPACE-Complete”. Computers and Games. Lecture Notes in Computer Science. 2063. Springer. pp. 241–249. 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, 4630, Springer, Berlin, Heidelberg, pp. 84–99, doi:10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1
^ ^a ^b https://tromp.github.io/go/legal.html
^ “Combinatorics of Go”. github.io. 2023年6月17日閲覧。
^ Allis 1994
^ ^a ^b ^c “Statistics on the length of a go game”. 2025年11月23日閲覧。
^ “Home - American Go Association”. www.usgo.org. 2023年6月17日閲覧。
^ Walraet, M; Tromp, J (2016), “A Googolplex of Go Games”, Computers and Games, Lecture Notes in Computer Science, 10068, Springer, Berlin, Heidelberg, pp. 191–201, doi:10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1
^ Tromp 1999

参考文献

AGA. “Top Ten Reasons to Play Go”.
Allis, Victor（英語版） (1994年). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 978-90-900748-8-7
Hearn, Robert A（英語版） (2006年). “Games, Puzzles, and Computation”. Ph.D. Thesis, MIT.
Johnson, George (1997年7月29日).“To Test a Powerful Computer, Play an Ancient Game”. ニューヨーク・タイムズ.
Papadimitriou, Christos (1994年), Computational Complexity, Addison Wesley.
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".

外部リンク

Go and Mathematics（英語）
Number of possible outcomes of a game - Sensei's Library（英語）

[10] 正確な値：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

[15] ただし、実際には19路盤の平均手数は200手を超えており^[13]、ゲーム木の複雑性はより大きいと考えられる。

[19] 実際には、碁石をすべて使い切ったとしても、終局していない場合は双方のアゲハマを交換することで対局を続ける。コウが長引いたときなどに、実戦でも発生することがある。

[1] “Go Infinitesimals at Sensei's Library”. senseis.xmp.net. 2022年2月10日閲覧。

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

[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. Lecture Notes in Computer Science. 176. 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”. More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125–136. オリジナルの2017-08-10時点におけるアーカイブ。 2016年7月9日閲覧。.

[8] Crâşmaru, Marcel; Tromp, John (2000). “Ladders Are PSPACE-Complete”. Computers and Games. Lecture Notes in Computer Science. 2063. Springer. pp. 241–249. 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, 4630, Springer, Berlin, Heidelberg, pp. 84–99, doi:10.1007/978-3-540-75538-8_8, ISBN 978-3-540-75537-1

[:1-11] ttps://tromp.github.io/go/legal.html

[12] “Combinatorics of Go”. github.io. 2023年6月17日閲覧。

[13] Allis 1994

[:0-14] “Statistics on the length of a go game”. 2025年11月23日閲覧。

[top_ten-16] “Home - American Go Association”. www.usgo.org. 2023年6月17日閲覧。

[17] Walraet, M; Tromp, J (2016), “A Googolplex of Go Games”, Computers and Games, Lecture Notes in Computer Science, 10068, Springer, Berlin, Heidelberg, pp. 191–201, doi:10.1007/978-3-319-50935-8_18, ISBN 978-3-319-50934-1

[18] Tromp 1999

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[注 1]

[10]

[11]

[12]

[注 2]

[14]

[15]

[16]

[13]

[注 3]

囲碁と数学とは？わかりやすく解説