去年有一条新闻，2023年11月，日本的一名研究者攻研究了黑白棋，也叫奥赛罗棋（Othello）。通过电脑程序，其找出了双方从开局到终局的完美下法，最终结果是一个平局，黑白子一样多！
(图：黑白棋中，双方完美对弈的最终局面，黑白子一样多。)
在我看来，这是一个大事件，又一个棋类游戏被人类攻克了。我是各种棋类游戏的爱好者，而与棋类游戏相关的数学知识和成果也十分丰富，特别是有关算法的。而说到算法，又不得不提到复杂度一词。
直觉上来讲，我们都会都认为象棋比五子棋复杂，围棋比象棋复杂。但对科学研究来说，科学家需要对复杂度有个精确的度量方法，而确实科学家也对棋类游戏定义了好几种复杂度的度量，本文就聊聊棋类游戏的复杂度度量方法。
这些方法主要分两类：一类是关于状态组合的，一类是关于算法复杂度的。先说说状态组合方面的复杂度度量。
状态组合顾名思义，就是一个游戏能够出现的状态数量。状态数量越多，那么它就可能越复杂。一个游戏所有可能出现的状态的集合，被称为状态空间，这个集合的大小被称为状态空间数。但对很多游戏来说，难以确定其确切的状态空间数，所以经常使用上界来作为这个游戏复杂度的估算。以下以大家数字的井字棋为例，可以这样估计该游戏的状态空间上界：
9个格子，每个格子里可以有“空白”，“⭕️”或“❎”，三种符号，所以它的状态空间上界是。但实际上没有那么多，因为双方的符号数量最多相差一个。另外，一种符号的连线出现后游戏就应该结束，而不会出现两种符号的连线。排除这些情况，实际井字棋的状态空间数是5478。当然，还可以合并一些对称的情况，那么状态数只有765种。
除了棋盘状态数，还有一类与之相关的复杂度度量，它是关于游戏进程数量的，被称为博弈树的路径数。想象一下，从游戏初始状态开始，画一个点。从这个点开始，把游戏接下来的每一种合理变化，都与上一个状态的点之间画一条线，如此持续下去，一直到游戏的终局状态。可以想象，这样会得到一个非常大的树结构。
(上图：一个井字棋游戏的博弈树示意图)
树根结点就是游戏的初始状态，树叶结点就是游戏的终局状态。从根到叶子的每一条路径，就是这个游戏的一个进程。这种路径的数量，就是某个游戏的可能的对局进程数量，这个数字比状态数更难以计算，通常会比游戏状态数大。对大多数游戏，人类还无法计算出确切的游戏进程数量。
与游戏进程数量类似，但更有用的一个复杂度度量是“博弈树复杂度”，它是与寻找游戏最优玩法有关的。博弈树复杂度的意思是：如果要找到一个游戏的每一步的最佳玩法，到底需要搜索多少可能的游戏进程。
寻找一个游戏的最优下法时，有一种知名的算法，也是模拟人类思考模式的算法，称为"minimax算法"。即：我方下一步的最佳玩法是，对方在下一步采取最佳玩法时，我能获取最大收益的那一种选择。而对方的最佳玩法，又是我方再下一步进行最佳选择时，对方采取最佳选择时的那一步。
（图片转自我写的科普读物《学数学会上瘾》，机械工业出版社出版）
这样就出现递归了，理论上只有枚举到终局状态，才能回溯。这种算法就叫做“minimax/最小最大算法”。意思是，对方行动时，找我方收益最小的分支，而我方行动时，找我方收益最大的分支。这种算法好理解，但搜索量巨大。
但好在中途是有办法进行剪枝的，被称为“alpha-beta剪枝。
ChatGPT关于alpha-beta剪枝的介绍：
Alpha-beta 剪枝是博弈算法中的一种优化技术，用来减少在对抗性搜索（如棋类游戏的搜索树）中需要评估的节点数量，从而加快决策过程。它是一种用于改进 minimax 算法的剪枝方法，旨在避免对那些已经不可能影响最终决策的节点进行评估。
在使用 minimax 算法时，玩家假设对手总是做出最佳决策。每一轮搜索会交替计算最大化或最小化玩家的得分。alpha-beta 剪枝通过维护两个边界值——alpha 和 beta——来跟踪当前节点的最优得分范围：
Alpha 表示当前已知的对最大化玩家有利的最佳选择（即最低的可接受得分）， Beta 表示当前已知的对最小化玩家有利的最佳选择（即最高的可接受得分）。
在搜索过程中，如果某个节点的评估值落在已知的无效范围内（即，得分不可能再改进 alpha 或 beta），算法会跳过该分支的进一步搜索，因为进一步评估不会影响最终决策。这一过程称为“剪枝”，可以大幅减少搜索树的大小。
核心步骤：
从根节点开始搜索，分别为最大化玩家（通常是当前玩家）和最小化玩家（对手）交替选择最优策略。 在遍历每个节点时，根据评估函数计算可能的得分。 当某个节点的评估值超出 alpha 或 beta 的范围时，停止进一步搜索该节点的子节点，从而“剪枝”掉这些不必要的分支。
例子：
在一个棋类游戏中，假设我们已经确定了某些分支会使对手的得分超出当前的最佳选择范围，无论我们如何走，结果都不会比我们现有的最佳方案更好。此时我们可以跳过这些分支，避免浪费时间在无关紧要的计算上。
优势：
更高效：与传统的 minimax 算法相比，alpha-beta 剪枝能显著减少需要评估的节点数量，尤其是在搜索空间很大的复杂游戏中。 相同结果：尽管剪枝减少了搜索的节点数，但它不会改变最终的决策结果——结果与没有剪枝的 minimax 算法是一致的。
这种技术在棋类游戏如国际象棋、围棋等 AI 对抗性算法中应用广泛，能够在有限的时间内提升决策效率。
经过剪枝后，我们可以得到一棵优化过的博弈树，这棵博弈树的叶子数量，就被称为“博弈树复杂度”。它决定了，要找到某个游戏的完美下法，需要搜索的游戏进程数。
这个数字虽然比完整的博弈树小一点，但也是天文数字。一个比较简单的，估计博弈树复杂度的方法就是计算这样一个幂次数：
比如说围棋，开局时，每一步大概有300多种选择，下到后来，慢慢减少，官子结束时选择数为0。平均可以算作每一步有150种选择，围棋的平均对局长度大约也是150，那么围棋的博弈树就大约是那么大。
以上游戏的状态空间大小和博弈树复杂度就是两种关于游戏复杂度的两种基本度量。状态空间反映了游戏可能的变化数量，而博弈树复杂度反映了游戏的计算量有多大。
除此以外，还有一种关于算法的“计算复杂度”。计算复杂度是游戏自己跟自己比，看看游戏的规模扩大以后，寻找游戏的最佳玩法的计算量会如何增长。我之前写过一篇“价值百万美元的p vs np问题”的文章，其中有一些关于计算复杂度的介绍。
当然，你可能会说，围棋的棋盘可以扩大，象棋的棋盘怎么扩大呢？其实在这里，我们对棋类游戏采取的是一种更为抽象和一般化的考查方式。虽然没有很直接的，对象棋扩大棋盘的方法，但可以认为，扩大象棋棋盘后，无论是几个兵，多几个炮或马，对最终的结论并没有直接影响。因为这些具体棋子数量上的差异，不会导致计算复杂度的区别。计算复杂度考察的是计算规模的变化趋势，而不是具体计算量的多寡。
也许你已经知道了计算复杂度里两种最知名的复杂度，P和NP。但在棋类项目中，最常见的计算复杂度是：多项式空间/PSPACE和指数时间类/EXPTIME。以下是几种计算复杂度的粗糙但便于理解的说明：
P：多项式时间，即计算时间对计算规模呈多项式方式增长。
NP：计算结果（可能）需要指数时间增长，但验证结果正确性的算法在P内。
NP-Hard：如果所有NP问题都可以归约为某个问题，则这个问题称为NP-hard类。当然，你可以把一个简单的问题归约为一个很复杂的问题，比如把井字棋归约为围棋，这样不是很有意义，所以才有以下这种“完备”概念。
NP-Complete：NP-完备，既属于NP-hard又属于NP的问题。以下的概念就以此类推，相当简单了。
PSPACE：多项式空间，计算所需空间对计算规模呈多项式方式增长。
PSPACE-Hard：如果所有PSPACE问题都可以归约为某个问题，则这个问题称为PSPACE-Hard类。
PSPACE-Complete：既属于PSPACE-Hard又属于PSPACE的问题。
EXPTIME：指数时间，即计算所需时间对计算规模呈指数方式增长。
EXPTIME-Hard和EXPTIME-Complete的概念就不赘述了。
目前这些复杂度的包含情况如下图：
其中的“？”表示还未排除两者相等的情况。
此外，我还想介绍一个概念，也可能是大家最关心的事，即：这个游戏被AI解决了没有？这是好问题，但即使一个游戏被解决，根据解决程度，存在三种情况。
第一种：强解构（Strong Solution）。给出游戏的任何一个状态，人类或者AI能够找出接下来的完美走法。
第二种：弱解构（Weak Solution）。人类或AI已知这个游戏，从开局状态之后每一步的完美走法。但过程中，如果一方走了不完美走法，我们就可能不知道后续的完美走法了。这种情况就叫弱解构。
要达成强解构，需要要走完所有博弈树分支，这个计算量太大了。所以我们最关心的还是从游戏开始状态后，这个游戏的完美走法。后面我们会看到，这次的被解决黑白棋，就属于这种弱解构。
第三种，比弱解够还要弱，称为超弱解构（Ultra-weak solution）。能得知游戏中先行者或后行者有必胜、或必不败之策略，但是不知道具体策略。博弈论中有一条策梅洛定理，它让我们超弱解构了很多游戏。
ChatGPT关于策梅洛定理的介绍：
策梅洛定理（Zermelo's Theorem）是博弈论中的一个重要定理，最早由德国数学家恩斯特·策梅洛（Ernst Zermelo）在1913年提出。该定理应用于有限确定型二人对弈游戏，即两个玩家轮流行动，每个玩家都有固定的规则，且游戏不包含运气或随机性（例如象棋和围棋）。
策梅洛定理的核心内容是：
有限博弈必有胜者或平局：在有限的二人完全信息博弈中（双方都完全了解游戏规则和当前局势），其中至少一个玩家有确定的策略能够保证他不会输。具体地说，要么一方有必胜策略，要么双方都有避免失败的策略，导致平局。
必胜策略的存在：如果游戏不存在平局，那么至少有一方玩家拥有一个必胜策略，意味着无论对手怎么下，他都可以通过适当的应对赢得游戏。
该定理建立在完全信息和有限游戏的假设之上。策梅洛通过分析游戏的结构，证明了在这些条件下，总能推导出一个最终结果，排除了游戏无限进行或无法决出胜负的可能性。
以下来具体来看几种常见的游戏的复杂度和解构程度，大致按照样本空间从小到大的顺序介绍。
先说说最简单的井字棋。
井字棋的转态空间，在合并对称得情况下，只有几千的数量级。博弈树是的数量级，也就是井字棋对弈过程比状态数要多非常多，主要原因在于井字棋中途不好剪枝，不走到最后难以判断输赢。
算法复杂度上，井字棋是PSPACE-Complete。解决程度方面，当然是强解构。我相信读者只要玩过井字棋，应该知道，双方不走错的话，结局就是平局。而且也有非常多的完美下法，并非只有一种完美下法。
接下来看看跳棋（checkers）。
中国人比较熟悉的跳棋是那种六角型棋盘，最多可以6个人玩的那种:
还有一种英国跳棋，是正方形棋盘:
这两种跳棋的复杂度差不多，所以一起介绍。顺便说一句，跳棋的原型其实1883到1885年左右，由一个美国人发明的游戏，当时叫做Halma。棋盘是正方形的，也只能两人玩。后来逐步演变6角型棋盘的6人版本。1920年代，德国一家公司出于营销目的，增加游戏神秘感，把游戏名称改为“中国跳棋”。
英国跳棋和中国跳棋的状态空间数分别到达了和的数量级。英国跳棋的博弈树复杂度达到，我没有查到中国跳棋的博弈树复杂度，即使1 vs 1的结果也没有找到。这两种游戏的计算复杂度都是EXPTIME-Complete。
解构情况是这样，2007年4月29日，英国跳棋被加拿大的一个团队弱解构。整个计算持续了18年时间，最多时使用了200台式电脑，最少时也有50台。结果是，棋盘下的英国跳棋，如果两人完美地下，最终是平局。
对中国跳棋，我搜索了一下，哪怕是1对1的版本，我也没有看到解构的结果，虽然根据策梅洛定理，我们知道先行一方必有一个必胜策略，所以中国跳棋目前只是极弱解构。
我这次搜索到了一篇关于中国跳棋的论文，回答了我小时候考虑过的另一个问题。如果两人玩，互相配合，怎么下，才能让一方的棋子最快达成目标，跳到目标位置。论文作者考虑的是的正方形棋盘下的跳棋，答案是30步。
（跳棋最快达成目标的30步走法，蓝色先行，配合红色先跳到目标位置）
遗憾的是还没有人计算过六角型棋盘下，2人中国跳棋的最快玩法。有兴趣的读者，完全可以考虑解决一下，找出中国跳棋最快获胜步骤。
接下来说说黑白棋。它的状态空间是数量级，比跳棋高了3到5个数量级。它的博弈树复杂度是数量级，比英国跳棋高了18个数量级。但它却是一个PSPACE-complete的游戏，也就是说，极可能存在一个n，使得n×n的棋盘下，计算黑白棋的时间会低于跳棋。
关于解构情况，在2023年12月，日本研究者宣布，解决了黑白棋。结论是如果双方完美的落子，那么最终结果是双方子数量相等，是一盘和棋！
所以，人类终于弱解构了黑白棋，而这也是人类目前为止，完整搜索过所有状态空间的，状态数量最大的游戏。
再看看大家喜闻乐见的五子棋。
五子棋的官方规则是15×15的棋盘，这种棋盘大小条件下，它状态空间达到次方，有意思的是，博弈树大小却变小了，是次方。但原因是可以理解的：五子棋通常下不满棋盘，而且很多状态下，下一步的落子是命令式的，没有选择。比如对方连出四个子的一条线，那么你当然只能去堵它，没有任何选择。所以，五子棋的博弈树上，可以进行大范围的剪枝，最终导致博弈树的大小比状态空间树小非常多。
五子棋也是PSPACE-Complete的，这意味它对计算机程序是比较友好的。所以，早在1993年，由Allis, Louis Victor领导的团队就通过程序确认，五子棋是先手必胜，所以，五子棋是被弱解构了。
正因为有先手必胜问题，日本人对五子棋规则进行了改进，添加了很多禁手，即先行方禁止下出的形状。日本人把这种加入禁手规则的五子棋称为“连珠”。2001年，有人发论文声称解决了连珠游戏，结论仍然是先手胜，所以基本上可认为连珠也被弱解构了。
以下是维基百科上关于连珠与计算机程序的内容：
原始的没有附加规则的连珠被证明存在完美对策使得先手必胜。然而，对于专业比赛中采用的平衡开局规则，如目前世锦赛使用的Soosõrv-8的规则，并没有被证明存在必胜策略。
世界电脑连珠锦标赛（The Renju World Computer Championship）从1991年开始，至2004年终止共举办了4届。自2016起，五子棋人工智能比赛Gomocup增设了连珠组，比赛每年举行一次。
2000年，计算机程序Meijin-2000参与了莫斯科公开赛（Moscow Open Tournament），使得它成为首个在公开比赛中与人类棋手较量的程序。然而，2017年前，并没有计算机程序在公开比赛中战胜人类顶尖高手的记录。2017年7月，人工智能冠军程序弈心与台湾名人林书玄进行了4局比赛，弈心以3胜1负获胜。2018年4月，弈心与前世界冠军祁观进行了5局比赛，并以2.5:2.5的成绩战平。
接下来看看中国象棋和国际象棋。
国际象棋的状态空间是数量级，而中国象棋可能是受限于子的活动范围，状态空间要小一点，是数量级。而博弈树复杂度上，两者正好反过来，国际象棋比较小，是，而中国象棋达到，所以，可以说中国象棋要比国际象棋复杂一些。
计算复杂度方面，已经有人证明国际象棋是EXPTIME-Complete的，还没有人证明过中国象棋，不过一般也认为是一个EXPTIME-Complete类的游戏，这意味着这两种游戏对编程枚举来说，是不太友好的。
在解构方面，毫不意外，目前两个游戏距离弱解构还遥不可及。虽然所有人都相信，如果完美对弈，这两个棋类应该都是和棋。但是要找出并证明这样一个完美的下法，目前远非人类所能及。
但在国际象棋方面，有人计算了一些残局情况。现在，对所有剩3到7个子的残局局面，都已经强解构了。中国象棋方面，此类研究还非常空白，我没有查到相关信息。
最后，看看我最喜欢的围棋。
关于围棋的状态空间，一个简单的计算是，因为每个点有空白、黑、白这三种情况，棋盘有361个交叉点，所以总的组合数是。但这个计算中，包含了很多不可能的情况，其中有很多状态，会有死棋，这是不允许的，所以真实的状态数要小于。所以，就产生这样一个问题：围棋的合理变化状态数是多少？
其实我个人在20年前曾经考虑过这个问题。在2004年，我写过一个JAVA程序，计算了4×4棋盘下的围棋合理变化数，确切数值是24318165。使用当时的PC，用了8分多钟，才计算出这个结果。我当时预计，如果用我的程序，要计算5×5的情况，大概要好几年。
(上图：2004年我在CSDN上发表的blog截图，其中计算了4×4围棋的合理变化数为24318165)
而这个问题，直到2016年，才被两位研究者正式解决。他们算出19路围棋的合理变化数是数量级，要比小两个个数量级。
（上图：1到19路棋盘的确切变化数）
而围棋的博弈树大小，达到了的数量级，所以，枚举是没有希望的。
关于计算复杂度，围棋的情况也相当复杂，因为围棋中有打劫和同形再现的问题。简单说一下结论，在日本规则下，允许三劫循环或多劫循环，并且判为和棋，那么围棋是EXPTIME-Complete类的。
但在中国规则下，这个问题就无比复杂了。中国规则规定不允许同形再现。这意味着，即使每个局面下，要考虑哪些点可以走，都需要检查游戏的整个历史，这就非常复杂了。
在此规则下，目前只能证明围棋是EXPSPACE/指数空间类游戏。指数空间是比指数时间还要高一级的复杂度。属于指数时间类的问题，必然属于指数空间类；属于指数空间的问题，不一定属于指数时间。
现在没有人能严格证明，在中国规则下，围棋是指数时间类游戏。但有人证明，围棋至少是PSPACE-Hard，即所有PSPACE类问题都不会比围棋复杂。
最后，看看围棋的解构情况。5×5的情况下， 在2002年已经被强解构了。结论是黑棋第一手走在2-2路角落，最终能吃光白棋。研究者也提供了一个程序，可以计算在其他情况下的最佳下法，所以是强解构。程序作者在2009年说，这个程序最大可以处理30个交叉点的情况，所以还无法处理6×6的情况。
（左上是5路围棋的最佳着法，其他是一些有意思的局面，其中包含一些赵治勋错过的着法）
个人觉得，弱解构6路围棋还是有希望的，日本规则下，其计算规模应该与黑白棋不相上下，就看有没有人来挑战一下这个难度活了。
文章就到这里，可以看到，目前游戏的复杂度研究，国外远胜于中国。我很希望有人能把中国象棋的残局好好解构一下，或者解决一些有中国特色的智力游戏。
参考文献：
https://en.wikipedia.org/wiki/Solved_game
https://en.wikipedia.org/wiki/Game_complexity
https://zh.wikipedia.org/wiki/PSPACE
https://techxplore.com/news/2023-11-japanese-scientist-conquers-board-game.html
https://ics.uci.edu/~eppstein/cgt/hard.html
https://blog.csdn.net/Fortress/article/details/194528?spm=1001.2014.3001.5502
https://tromp.github.io/go/gostate.pdf
https://en.wikipedia.org/wiki/Go_and_mathematics
http://erikvanderwerf.tengen.nl/5x5/5x5solved.html （已失效）
https://arxiv.org/abs/0803.1245
