游戏树
如果先手A选择上方,游戏进入到一个由进行B进行决策的分支,这叫做一个子游戏。在这个子游戏中,B选上方就A获胜,B选下方就B获胜,B要选择对自己有利的,所以他一定选择下方。这个子游戏的结局是固定的,就是B获胜。
如果先手A选择下方,游戏进入到另一个由B做决策的子游戏中,这时B选上方就A获胜,B选下方就和棋,B要选择对自己有利的,所以这个子游戏的结局一定是和棋。
我们再来考虑A:若A走上方,进入子游戏1,一定B获胜;A走下方,进入子游戏2,一定和棋。A也要选择对自己有利的,所以A选择下方。最终的游戏就是和棋。
如果游戏复杂一些,也不过是分支变多,长度变长,但是只要我们从最后端的子游戏开始,一层层倒推,就一定能推算出在最优策略下,游戏到底是先手胜,还是后手胜,还是和棋,这种胜负是不可避免的。
比如五子棋:双方轮流下子,五子连线获胜。人们逐渐发现:先手有必胜法。为了游戏公平,就设计了三三禁手、四四禁手、长连禁手,先手走出禁手就算输。与五子棋相比,中国象棋、围棋的规则就复杂很多,但是它们依然是双人完全信息博弈。
无禁手时五子棋的两种先手必胜开局
虽然我们不知道最优套路是什么
但是我们确信:
一定存在那样一种最优的策略
如果双方都执行了这种策略
则一定是先手赢、或者后手赢
或者一定和棋
可是,为什么我们从来没听说过谁
掌握了象棋和围棋的必胜法呢?
井字棋
我们举一个最简单的棋——井字棋来说明。
井字棋非常简单。首先画一个井字,然后先手画叉,后手画圈,在九个格子中轮流画。谁的三个子横竖斜连成一条线,谁就赢了。如果画满了双方都没有赢,那就是和棋。比如,下面就是一个先手胜的井字棋局。
一个井字棋牌局
这个游戏的规则虽然简单,但是可玩性还是很高的,因为它其实也有不少变化,说准确一点,应该叫游戏的复杂度。
首先,我们讨论游戏的状态复杂度,它表示在这个棋盘上到底会出现多少种可能的局面。一般来讲,我们没办法准确算出一个游戏的状态复杂度,很多时候也没必要准确算出来,我们只要估算一个上限,或者一个数量级,就可以了。
比如井字棋:每一个格子都有叉、圈、空白3种可能,一共有9个格子,所以最多能够出现的局面也不会超过39=19683种。这里面有许多不符合规则的情况,比如叉的数量要么和圈相同,要么多1个,其他情况都不符合规则。对称的情况,其实应该算作一种情况。如果把这些不符合规则和对称都去掉,最终余下的状态数是765种——你在井字棋中只能看到这765种局面。
状态数并不是衡量游戏复杂程度的唯一方式,因为同一个局面状态,也可以从不同的路径得出。要考察游戏玩法总数,我们得计算游戏树的大小。
井字棋的一部分游戏树
大家看:先手画第一个叉时,去掉对称性,其实只有三种画法:中间、边中点和角。这是树的第一层,有3个分支。
如果先手在中间画叉,去掉对称性,后手的圈只有两种画法:角和边的中点。如果先手画在边上或者角上,后手分别如图所示的五种画法。这是树的第二层,有12个分支。
之后,游戏还有很多层,每层又有很多分支,直到最后有一方获胜或者和棋。游戏树有多少个不同路径,就表示了游戏一共有多少种可能的变化。
在井字棋游戏中,我们可以估算游戏树的复杂度:先手先选位置,有9种可能;后手只剩下8种可能,先手又剩下7种可能…直到最后填满9个格子,所以游戏树复杂度不超过9!=362880种。这里面有许多不符合规则的,比如已经有一方获胜了,就不用再下了,还要去掉重复和对称的,最终的游戏树复杂度是26830。
人们已经考察了井字棋的全部26830条路径,并发现:如果双方都采用最优策略,那么井字棋一定是和棋。