囲碁と数学

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^{170 [注 1]}）が得られた^[10]。

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

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

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

盤の大きさ ( n 路盤)	3n2	合法な盤面 の割合	${\displaystyle 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 × 1038	23.44%	1.03919148791 × 1038
13	4.30023359390 × 1080	8.66%	3.72497923077 × 1079
19	1.74089650659 × 10172	1.20%	2.08168199382 × 10170

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

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

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

盤の大きさ ( n 路盤)	着点 N = n2	N!	仮の平均 手数 L	NL	理論上の 最長手数	総ゲーム数の 下限	総ゲーム数の 上限
2	4	24	3	64		386,356,909,593[16]	386,356,909,593
3	9	3.6×105	5	5.9×104
4	16	2.1×1013	9	6.9×1010
5	25	1.6×1025	15	9.3×1020
9	81	5.8×10120	45	7.6×1085
13	169	4.3×10304	90	3.2×10200
19	361	1.4×10768	200	3.2×10511	1048	1010100	1010171
21	441	2.5×10976	250	1.3×10661

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

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

最長手数 L	361PL	ゲーム数の下限	ゲーム数の上限	備考
1	361	361	362	白が初手で投了。初手361種類（盤の対称性は考慮せず）にパスを加え362種類。
2	129960		130682	361(黒1)× 360(白2) + 361(黒1がパス) + 361(白2がパス)
50	2.1×10126		7.5×10127
100	1.4×10249		5.6×10255
150	6.4×10367		4.2×10383
200	1.9×10481		3.2×10511
211	2.5×10505		4.3×10539	プロの対局の平均手数[13]
250	8.2×10587		2.4×10639
300	2.8×10684		7.8×10766
350	3.6×10760		1.3×10895
361	1.4×10768		1.8×10923	黒石181子・白石180子すべてを使った場合[注 3]
411	n/a		1.3×101051	プロの対局の最長手数[13]
500	n/a		5.7×101278
1000	n/a		3.2×102557
47045881	n/a		10108	3613 = 47045881
1048	n/a	1010100	1010171	理論上の最長手数

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

• コンピュータ囲碁 - コンピュータ（人工知能）に囲碁を打たせる試み。
• ゲーム木複雑性（英語版）
• 神のアルゴリズム（英語版）
• シャノン数（英語版）