N乘N路圍棋的合法局面總數

04-27

合法局面總數，即圍棋的狀態空間複雜度。

n number of legal n*n positions

1 1

2 57

3 12675

4 24318165

5 414295148741

6 62567386502084877

7 836877847847984287628595

8 990966953618170260281935463385

9 103919148791293834318983090438798793469

10 96498428501909654589630887978835098088148177857

11 793474866816582266820936671790189132321673383112185151899

12 57774258489513238998237970307483999327287210756991189655942651331169

13 37249792307686396442294904767024517674249157948208717533254799550970595875237705

14 212667732900366224249789357650440598098805861083269127196623872213228196352455447575029701325

15 10751464308361383118768413754866123809733788820327844402764601662870883601711298309339239868998337801509491

16 4813066963822755416429056022484299646486874100967249263944719599975607459850502222039591149331431805524655467453067042377

17 19079388919628199204605726181850465220151058338147922243967269231944059187214767997105992341735209230667288462179090073659712583262087437

18 669723114288829212892740188841706543509937780640178732810318337696945624428547218105214326012774371397184848890970111836283470468812827907149926502347633

19 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

來源：Counting Legal Positions in Go

這是John Tromp十餘年來的研究成果，確定了一至十九路圍棋的合法局面總數，精確到個位數。

五路棋盤的合法局面總數是4142億。五路棋盤是目前為止人類用計算機暴力搜索過的最大一塊正方形棋盤，由van der Werf 和 Winands 利用程序Migos在2003年完成。

六路棋盤的合法局面總數是五路盤的十五萬倍，達到625673865億，或者6*10^16. 尚無程序完成六路棋盤的窮舉。Ted Drange 和 Bill Spight等人合作，手工研究得到最優解是黑勝4子的結論（本文的結果均以中國規則、出入法論。比如黑20子、白16子，則記為黑勝4子）。

七路棋盤的合法局面總數是8*10^22, 六路盤的一百多萬倍，略大於國際跳棋（Draughts，已有窮舉結論）的複雜度。使用目前最先進的超級計算機列舉這些局面大概需要三個月。目前無程序完成七路棋盤的窮舉。

30年前，由數位日本業餘愛好者聯合研究，並由日本職業棋手工藤紀夫等人驗算，得到七路盤的最優解，並寫成書出版。2015年，由中國職業棋手李喆牽頭進行七路盤最優解的研究，非常細緻，發布在《圍棋天地》上。兩個獨立的研究得到了相同的結論，最優解是黑勝9子。由人類權威研究出的結論相當可信，但尚不構成嚴謹的數學證明。藉助計算機完成七路盤最優解的嚴格證明仍待進一步的研究。

七路棋盤是已知最優貼先的最大棋盤。

九路棋盤合法局面總數為10^38，略少於國際象棋。窮舉九路棋盤仍遠遠超出現有計算機的算力。目前我們完全不知道九路棋盤的公平貼先是多少。採用中國規則的各類比賽，貼5.5子、7子、7.5子（出入法）的都有。九路盤最優解也難以純靠人類專家的知識解決。事實上，每一局九路盤上的棋局，都好像做一道超級死活題，比《發陽論》里最難的題更難。部分棋迷對九路盤不屑一顧，淺薄。

十九路棋盤，合法局面總數10^170. 什麼概念？筆者曾說人類在一千年以內無法暴力破解十九路圍棋，遭到少數知友反駁曰「工業革命一二百年，人類科技進步何其迅猛」。可是，工業革命以來，人類的技術增長速度不過指數級，用計算機術語說是O(exp(n)). 而圍棋的狀態空間複雜度的增長速度是O(exp(n^2)), 指數上的平方級。即使摩爾定律不減速（維持每18個月翻倍），計算機硬體也要再發展一百餘年才能求解九路棋盤，八百餘年才能求解十九路棋盤，更遑論摩爾定律已經幾乎摸到了天花板。至於尚在襁褓中的量子計算，理論上可能提供的多項式時間級別的加速，對於較大的圍棋盤也是杯水車薪。千年，何其遙遠。

（評論區有朋友提到布萊曼極限，這個概念解釋得更清楚）

十九路合法局面總數208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935，可以用三進位表示為

0 0 0 0 2 2 2 0 1 1 0 0 2 0 1 1 1 0 1

2 1 1 2 1 2 0 0 2 1 2 1 0 0 0 2 2 0 2

2 1 0 0 2 1 0 1 1 1 1 1 0 1 1 1 1 1 2

0 0 2 2 0 1 1 0 2 0 0 1 2 1 0 2 0 1 0

1 0 2 0 2 0 1 2 0 1 1 2 2 1 0 0 1 2 1

1 0 0 0 1 1 1 2 0 2 2 0 0 0 2 0 1 2 2

0 0 2 1 2 0 0 2 0 0 1 1 1 0 2 0 2 0 0

0 0 2 2 0 2 2 2 0 0 0 2 1 0 1 0 0 0 2

2 1 0 0 2 0 2 2 2 2 1 0 0 2 1 1 1 2 1

2 0 0 1 0 2 2 1 2 1 1 2 2 0 2 0 1 2 0

2 1 1 1 0 0 2 1 0 0 2 2 1 2 2 2 0 1 1

2 2 1 2 0 1 1 1 0 2 0 1 2 0 2 2 2 0 2

2 0 1 0 1 2 1 1 0 1 1 0 2 1 2 0 0 2 1

2 0 0 0 1 2 2 1 1 2 0 2 2 0 0 1 0 1 0

1 1 2 2 0 0 1 2 2 0 2 0 2 0 1 2 2 1 0

2 0 1 0 0 1 1 0 2 1 2 1 2 1 1 0 2 2 0

2 2 1 1 2 0 1 0 2 0 1 2 0 2 1 2 1 0 0

0 0 0 1 1 2 2 1 0 2 1 0 1 0 2 1 1 2 0

2 2 0 2 1 0 2 2 0 0 2 1 1 1 1 1 2 2 2

令0=空，1=黑，2=白，就是下圖的局面：

也就是題圖。

最後說點最淺顯的：AlphaGo和暴力搜索沒有半毛錢關係。上面說了那麼多，我想這一點已經再顯然不過了。AlphaGo把人類爆得連渣都不剩，但離棋神還差得很遠很遠。