围棋的局面有多少

自古及今,弈者无同局。
《张拟·棋经十三篇·论局篇第一》

标准棋盘有361个点,每个点有黑白空3种状态,可能的状态组合成的局面有3^361个,但有些局面是围棋规则禁止的,如自杀、打劫。围棋的局面究竟有多少呢?

1. 古人的概算

《沈括·梦溪笔谈·技艺》

凡方二路,用四子,可变八十一局。
方三路,用九子,可变一万九千六百八十三局。
方三路,用九子,可变一万九千六百八十三局。
方四路,用十六子,可变四千三百四万六千七百二十一局。
方五路,用二十五子,可变八千四百七十二亿八千八百六十万九千四百四十三局。
方六路,用三十六子,可变十五兆九十四万六千三百五十二亿八千二百三万一千九百二十六局。
方七路以上,数多无名可纪。尽三百六十一路,大约连书万字四十三,即是局之大数。

2. 现代计算机的验证

John Tromp痴迷于探索围棋合法局面数上限,2016年1月20日,他宣布终于确定了一路至十九路棋盘的合法局面数!十九路的局面数是一个171位的十进制数字,约等于2.08×10^170。计算的源代码发布在github.com/tromp/golegal。如果自行验证,他建议使用15TB闪存磁盘、16核CPU、192GB内存的服务器,运算几个月的时间。

 1: 1
 2: 57
 3: 12675
 4: 24318165
 5: 414295148741
 6: 62567386502084877
 7: 8367784784798428762
    8595
 8: 9909669536181702602
    81935463385
 9: 1039191487912938343
    1898309043879879346
    9
10: 9649842850190965458
    9630887978835098088
    148177857
11: 7934748668165822668
    2093667179018913232
    1673383112185151899
12: 5777425848951323899
    8237970307483999327
    2872107569911896559
    42651331169
13: 3724979230768639644
    2294904767024517674
    2491579482087175332
    5479955097059587523
    7705
14: 2126677329003662242
    4978935765044059809
    8805861083269127196
    6238722132281963524
    55447575029701325
15: 1075146430836138311
    8768413754866123809
    7337888203278444027
    6460166287088360171
    1298309339239868998
    337801509491
16: 4813066963822755416
    4290560224842996464
    8687410096724926394
    4719599975607459850
    5022220395911493314
    3180552465546745306
    7042377
17: 1907938891962819920
    4605726181850465220
    1510583381479222439
    6726923194405918721
    4767997105992341735
    2092306672884621790
    9007365971258326208
    7437
18: 6697231142888292128
    9274018884170654350
    9937780640178732810
    3183376969456244285
    4721810521432601277
    4371397184848890970
    1118362834704688128
    2790714992650234763
    3
19: 2081681993819799846
    9947863334486277028
    6522453884530548425
    6394568209274196127
    3801537852564845169
    8519643907259916015
    6281285460898883144
    2712971531931755773
    6620397247064840935

19路棋盘的合法局面是一个9×19=171位的数字,如果转换为三进制数字,0表示空点,1表示黑子,2表示白子,可以呈现为一个19×19=361的棋盘。

图片来源于 tromp.github.io