本項では、囲碁を数学的に研究する試みについて扱う。シンプルなルールゆえに、囲碁は長らく数学研究の対象となってきた。古くは11世紀の中国学者・沈括が『夢渓筆談』において19路盤の囲碁の合法な盤面の総数の計算を試みており、 3361 から約 10172 と推定した。近年では、ジョン・H・コンウェイによる囲碁研究が超現実数の創出につながり、の発展に寄与した。囲碁におけるその応用例として、具体的なものにGo Infinitesimalsがある。
計算複雑性 n 路盤（ n ✕ n のサイズの碁盤）の囲碁において、任意の局面での勝者を算出するための計算複雑性は、コウのルールに大きく依存する。
囲碁は「ほぼ」PSPACEに属する。一度盤面に打たれた石は基本的にそのままであり、より複雑な反復形が生じ得るのは、石取りが絡んだ場合に限られるからである。
コウを考慮しない場合 コウのない囲碁はPSPACE困難である。これは、PSPACE完全であることが知られているTQBF問題を、 、平面 generalized geography 、最大次数 3 の generalized geography 、最終的に囲碁の局面へと還元することで証明される。
超コウルールの碁がPSPACEに含まれるかどうかは知られていない。実際の対局が n2 手を超えることは稀であるが、総手数に多項式上界が存在するかも不明である。もし存在すればPSPACE完全となる。現状では、PSPACE完全、EXPTIME完全、あるいはEXPSPACE完全である可能性すらある。
日本ルール
日本ルールにおいては、コウは1手前の状態に戻す手のみが禁止されているだけであり、三コウや四コウのように、同じ盤面の循環が生じる可能性もある。
日本ルールでは、囲碁はEXPTIME完全である。
超コウルール 超コウルールは中国ルールや米国ルールなどで採用されており、以前に発生した盤面の再現をすべて禁じるルールである。
超コウルールにおける囲碁の複雑性クラスは未解決問題である。日本ルールであればEXPTIME完全であるが、 Robson (1983) によるEXPTIME完全性の証明における下界と上界の両方が、超コウルール下では破綻する。
ただし、少なくともPSPACE困難であることは知られている。囲碁がPSPACE困難であることを示す証明は、コウのルールに依存していないからである。また、EXPSPACEに属することも知られている。
Robson (1984) は、EXPTIME完全である任意の二人用ゲームに「超コウルール」、すなわち「過去の局面を再現してはならない」というルールを追加した場合、新たなゲームがEXPSPACE完全になることを示した。これは、ある局面から合法な着手を決定する際にも、その局面に至るまでの手数が指数関数的に長くなっている可能性があるため、結局は指数関数的な量の空間が必要となるためである。
したがって、一般化したチェスやチェッカーの超コウルール版（以前の盤面の再現を禁止したルール）は、一般化したチェスやチェッカーがEXPTIME完全であることから、EXPSPACE完全である。ただし、この結果は囲碁には適用されない。
特定の条件での複雑性 盤面が生き石によって孤立した各領域に分割されると、対局は終盤（ヨセ）へ入る。この時、各領域は、多項式レベルの正規化されたゲーム木を持つ。組合せゲーム理論の用語に言い換えれば、盤面が多項式レベルの正規化されたゲーム木を持つの和に分解されると、終盤に入る。
この定義に従えば、囲碁の終盤はPSPACE困難である。
これは、PSPACE完全であるQBF問題を、小さな（多項式レベルの正規化されたゲーム木を持つ）サブゲームの和に変換することで証明される。ただし、囲碁の終盤がPSPACEであることは証明されていないため、実際にPSPACE完全であるかは不明である。
シチョウが成立しているかどうかの判定は、コウのルールとは無関係に、PSPACE完全である。これは、盤面を跳ね回るシチョウを、PSPACE完全であるQBF問題としてシミュレートすることで証明される。
合法な盤面の総数 盤上の各着点は黒、白、空点のいずれかであるため、 n 路盤には 3n² の盤面図が存在する。ただし、その中には着手禁止点に石があるなどの非合法な盤面が含まれるため、合法な盤面の総数はそれよりも少なくなる。
2007年、 Tromp と Farnebäck が、長さ m と n の長方形の碁盤における合法な盤面の総数 L(m, n) の再帰式を2007年に導出した。更に、2016年には同氏らにより19路盤の合法な盤面の総数の正確な値（およそ 2.08✕10170 正確な値：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 ）が得られたhttps://tromp.github.io/go/legal.html 。
L(m, n) については、以下のような漸近式も与えられている。
, ただし , ,
観測可能な宇宙には約 1080 個の原子があると推定されているが、これは19路盤の囲碁における合法な盤面の総数よりはるかに少ない。また、盤が大きくなるにつれて、合法的な盤面の割合は減少する。
盤の大きさ( n 路盤)3n2合法な盤面の割合 (合法な盤面の総数) 1333.33%128170.37%57319,68364.40%12,675443,046,72156.49%24,318,1655847,288,609,44348.90%414,295,148,74194.43426488243 × 103823.44%1.03919148791 × 1038134.30023359390 × 10808.66%3.72497923077 × 1079191.74089650659 × 101721.20%2.08168199382 × 10170
ゲーム木の複雑性 コンピュータ科学者のは、プロ同士の通常の対局は約150手続き、1手あたり平均約250の選択肢があると考え、ゲーム木の複雑性を 10360 程度であると推測したAllis 1994。 10700 という値が言及されることもあるが、これは という単純な順列から得られる値である。
非現実的な盤面や進行も含む、理論上可能なゲーム木の複雑性について、Tromp と Farnebäck は 101048 という下限と、1010171 という上限を与えた。のちに下限は Walraet と Tromp によって 1010100 まで改善された。
可能なゲームの総数は、盤の大きさ（合法な着点の数）と対局での手数をもとに算出が試みられることが多いが、その推定方法に決まった定義はない。以下に例を示す。
盤の大きさ( n 路盤)着点N = n2N!仮の平均手数 LN理論上の最長手数総ゲーム数の下限総ゲーム数の上限2424364386,356,909,593Tromp 1999386,356,909,5933954169525159814513169901936120010481010100101017121441250
ゲーム木の複雑性をある程度正確に考えようとするとき、最も単純な方法は盤面サイズ (N) と最長手数 (L) の組合せ NPL になるが、これは非合法な着手や盤面の変化を考慮しない値となる。より正確なゲーム数の上限は、 Tromp と Farnebäck の論文で提示されている。
以下は19路盤での最長手数とゲーム木の複雑性の関係である。
最長手数 L361PLゲーム数の下限ゲーム数の上限備考1361361362白が初手で投了。初手361種類（盤の対称性は考慮せず）にパスを加え362種類。2129960130682 361(黒1)× 360(白2) + 361(黒1がパス) + 361(白2がパス)50100150200211プロの対局の平均手数250300350361黒石181子・白石180子すべてを使った場合実際には、碁石をすべて使い切ったとしても、終局していない場合は双方のアゲハマを交換することで対局を続ける。コウが長引いたときなどに、実戦でも発生することがある。411n/aプロの対局の最長手数500n/a1000n/a47045881n/a101083613 = 47045881 1048n/a10101001010171理論上の最長手数
10700という見積りも、200手程度で終局すると考えれば過大評価である一方、361手まで対局を続けるという立場から考えれば過小評価であるし、それ以上の長手数を戦うことも不可能ではない。なお、4700万手の対局を行うならば、1秒に1手ずつ1日16時間対局したとしても、約2年3か月かかる計算となる。
関連項目 コンピュータ囲碁 - コンピュータ（人工知能）に囲碁を打たせる試み。
脚注 注釈
出典
参考文献 AGA. “Top Ten Reasons to Play Go”. (1994年). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 978-90-900748-8-7 (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. (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（英語）