本文作者“终军弱冠”，发布于知乎和奇略研究所公众号，已得授权。
俗话说“千古无同局”，说的是有史以来所有的围棋棋局没有两局是一模一样的。但是这个说法很难证实，因为并非所有的对局都被保存和记录了下来，而且由于计算机和网络的出现，使得围棋的对局数量（无论是人类对人类、AI 对 AI 还是人类对 AI）都在迅速增加，我们没法确认是不是真有两局棋下得一模一样。所以“千古无同局”实际上是在感叹围棋的变化之多。那么问题就来了，围棋的变化到底有多少呢？
在本篇中，我们将介绍一些对围棋棋局数量的估计结果。需要特别指出的是，这里我们考察的是围棋棋局的理论数量，那些在人类对局中不可能出现的对局（但是只要是符合规则的）都将被计算在内。另外，从理论上讲，围棋棋局的长度可以是天文数字，而不是人类对局时的几百手。因此，我们这里讨论的棋局数量要比现实中可能出现的棋局数量多得多。
★介绍★
在讨论之前，我们首先明确一下使用的规则。围棋的基本规则在世界各地都是差不多的，无非是就没气的棋子需要被提走。但是在遇到“劫争”时，类中国规则是比较完备的规则，其中的“禁止全局同形”这一条保证了棋局可以在有限的着数内终止。
“禁全同”其实有两种解释—— PSK（positional superko）和 SSK（situational superko）。PSK 指的是落子后不能使局面与这局棋曾经出现过的局面一样；SSK 指的是落子后不能使对手面临的局面与这局棋中曾经面临过的局面一样。本文中，我们使用的是 PSK 解释的“禁全同”规则。
“禁全同”避免了棋局在发生劫争（或者多劫循环、长生劫等）时陷入到无限循环中。另外，“禁全同”规则要求行棋后形成的局面是未曾出现过的，而围棋的合法局面数量显然是有限的，所以“禁全同”从理论上保证了棋局不会无限地进行下去。
接着，我们来看一下博弈游戏的复杂度的概念。游戏的复杂度可以从多个角度进行讨论，我们这里简单介绍几个指标：
状态空间复杂度（state-space complexity）：这个比较好理解，就是指游戏的合法局面数量，有时候还要求局面是可达的（即可以从初始状态经过有限的着法到达）。2016年，Tromp 和 Farneback [1] 得到了 19 路标准围棋合法局面数量的精确值，并对合法局面数量的渐进作了猜测。本文中，我们用L（m，n）表示m×n路围棋的合法局面数量，另外我们定义 L（n）≡ L（m，n）。
博弈树的规模（game tree size）：我们把每个棋局状态看作是节点，而节点的每个分枝都表示一种可能的着法。博弈树指的是就是由这些状态节点形成的树形结构，而其规模指的是树上叶子节点的数量，也即符合规则的棋局总量。本文中，我们用N(m，n)表示m×n路围棋的棋局数量，另外我们定义N（n）≡N（n，n） 。由于N（n）非常巨大，所以在计算时我们经常对其取两次对数。
计算复杂性（computational complexity）：这个概念就比较抽象了，它指的是解决某个问题需要的计算资源（通常是时间和空间）的量。一般我们会用一些计算复杂性类来对问题进行分类。1980年，Lichtenstein 和 Sipser [3] 证明了“禁全同”规则下的围棋属于 PSPACE-hard 复杂性类。1983年，Robson [4] 证明了日本规则下的围棋属于 EXPTIME-complete 复杂性类。
本文我们主要讨论围棋的博弈树规模，我们介绍几个对围棋棋局总量的估计结果，这些估计的精度是逐步递进的。
第一节我们谈两个平凡的结论；第二节我们介绍 Tromp 和 Farneback 对棋局数量上下界的改进；第三节我们介绍 nested scheme 方法，以及应用该方法得到的结果；第四节我们简单总结一下。