围棋的状态空间复杂度

5.2.1　围棋的状态空间复杂度

状态空间复杂度指的是从博弈初始状态开始所能达到的所有不同的合法博弈状态的个数。状态空间复杂度描述了通过枚举所能解决博弈的复杂度范围。对于一种博弈，在很多情况下，准确地计算该博弈的状态空间复杂度是比较困难的，也经常是不必要的。研究人员通常可以通过近似的方法，估计该博弈的状态空间复杂度。

远在北宋，沈括已在其巨著《梦溪笔谈》中详细描述了如何计算围棋的状态空间复杂度：

唐僧一行曾算棋局都数，凡若干局尽之。余尝思之，此固易耳，但数多，非世间名数可能言之，今略举大数。凡方二路，用四子，可变八十一局，方三路，用九子，可变一万九千六百八十三局。方四路，用十六子，可变四千三百四万六千七百二十一局。方五路，用二十五子，可变八千四百七十二亿八千八百六十万九千四百四十三局；古法：十万为亿，十亿为兆，万兆为秭。算家以万万为亿，万万亿为兆，万万兆为垓。今且以算家数计之。方六路，用三十六子，可变十五兆九十四万六千三百五十二亿八千二百三万一千九百二十六局。方七路以上，数多无名可纪。尽三百六十一路，大约连书万字四十三，即是局之大数。万字四十三，最下万字是万局，第二是万万局，第三是万亿局，第四是一兆局，第五是万兆局，第六是万万兆，谓之一垓，第七是万垓局，第八是万万垓，第九是万亿垓。此外无名可纪，但四十三次万倍乘之，即是都大数，零中数不与。其法：初一路可变三局，一黑、一白、一空。自后不以横直，但增一子，即三因之。凡三百六十一增，皆三因之，即是都局数。

按照沈括的计算，十九路围棋共有361个点，每个点有3种可能的状态：或黑、或白、或空。因此，十九路围棋的状态空间复杂度是3³⁶¹，约为1.74×10¹⁷²，即1.74×10 000⁴³。

由于围棋规则的限制，没有气的死子需从棋盘上拿开（参见第3章），因此以上沈括所计算的棋局数目中包含不合法的棋局，所以该计算结果只是围棋状态空间复杂度的一个上限。通过蒙特卡洛方法（参见第7章），我们可以估计在所有围棋棋局状态下合法围棋棋局状态的比率p，因此十九路围棋的状态空间复杂度不超过3³⁶¹×p。蒙特卡洛方法的结果表明，p≈0.012，因此十九路围棋的状态空间复杂度约为0.012×3³⁶¹≈2.089×10¹⁷⁰。