棋盘上的数学里程碑

导读： 一个棋盘，几个棋子就能拥有万千变化，而变化之中又有奇妙的规律等待着数学家与解谜者的探寻。游戏是人类的天性，几千年来，人们发明游戏、在游戏中取胜、挖掘着游戏背后的秘密。正是在游戏与对真理的追寻中，棋盘上树起了一个个数学里程碑。

约公元前1300年：圈叉游戏

圈叉游戏是由两位分别代表O方和X方的玩家在―个3×3的方格上轮流填上己方符号，最先让己方符号以水平、垂直或对角线方式连成一线的玩家即为胜方；而在3×3的方格上多半是以平手的局面结束。

圈叉游戏是人类史上解古老最广为人知的一项游戏。虽然产生现代化圈叉游戏操则的确切日期，可能没那么历史悠久，可是，考古学家却可以把这种“三个连成一列”的游戏，追溯到大约公元前1300年的古埃及，类似的游戏类型可以追溯到人类社会的最初阶段。

在古埃及法老王统治时期，棋弈游戏在日常生活中，就扮演着相当重要的角色，类似圈叉游戏之类的赛局，就是从那时候开始发扬光大，如里把圈叉游戏视为“原子”的话，经过几世纪的演变，我们现在已经进展到更高阶、相当于“分子”的各种游戏。只要稍微改变规则和棋盘大小简单的圈叉游戏就会变成需要花大量时间钻研的华丽挑战。

数学家和解谜狂已经把圈叉游戏扩展到更大更高维度的横盘，比如轮胎面、类似甜甜的环面或克莱恩瓶（单边、无法区别内外的表面）上的长方形或正方形。

回过头来谈谈圈叉游戏的一些特性。代表O方X方的两位玩家总共可以在棋盘上排出9!=362880种不同的棋形组合，而圈叉游戏分别在第五、六、七、八、九步棋结束的所有可能组合总数为25516。

在20世纪80年代初期，希利斯(Danny Hillis)、席维文(Brain Silverman)和他们的―群计算机天才朋友们共同开发一套由上万组Tinkertoy积木零件所组成、直接命名为Tinkertoy的圈叉游戏机。1998年，多伦多大学的研究人员和在校学生一起打造出能与人类在4×4×4三度空间对弈圈叉游戏的机器人。

公元前548年：围棋

围棋大约是公元前2000年源自于中国的双人棋弈，最早提到有关于围棋的历史记载是一本叫做《左传》的中国叙事古藉，当中提到公元前548年有个人下围棋的故事。围棋之后传到了日本，并在13世纪成为广受欢迎的游戏。围棋是由两位分别持黑子跟白子的玩家，在一个19x19的横盘上对弈，当某一方的棋子完全被另一方的棋子包围时，就要从棋盘上把被围住的棋子通通移除，游戏目的是尽可能比对手掌握更大的棋盘范围。

有很多因素可以说明围棋的复杂程度，像大范围的其盘、层出不穷的策略运用，以及大量又变化多端的对弈过程。所以，单单设法在棋盘上摆上比对手更多的棋子并不能保证获胜。如果把对称性纳入考虑的话，围棋总共有32940种不同的棋路，其中的992种被视为较常见的抢手棋；而变幻莫测的棋局据估算更有高达10172种不同的最终结果及10768种不同的走法。两位围穆高手对弈时，通常会在150手之内决胜负，其间的每―手棋大约有5种不同的选择棋艺高超的西洋棋软件有时可能击败最顶尖的西洋棋高手。不过，最厉害的围棋软件却往往会输给一位受过围棋训练的小朋友。

下围棋的计算机很难做到“先多想几步后”再作出判断。相较于西洋棋，围棋每下一子所需要考虑各种可能的合理变化更多，也由于在不同空位落子会对于整体布局造成不同的影响，因此，也不容易判断该在哪边落子比较有利。

匈牙利研究人员在2006年宣称可以通过一种名为UCT的演算法（Upper Confidence bounds applied to Trees，树状结构高阶信度分析）帮助计算机判断出最有可能获胜的棋路与职业围棋高手对弈，不过，这套算法目前只适用在9X9的棋盘上。

2007年：破解西洋棋

2007年，计算机科学家沙费尔和他的同事终于用计算机证明如果西洋跳棋玩家不犯错的话，最终一定会以平手局面作收。这代表西洋跳棋跟圈叉游戏一样，只要两位玩家都不犯错；游戏的结果―定是平手，没有胜方。

沙费尔的证明方式通过数以百计的计算机运算超过十八年的时间，使得西洋跳棋成为人类到目前为止破解过最复杂的游戏，这也表示理论上有可能设计出一台专门跟人类下西洋跳棋，而且永远不会落居下风的机器。

西洋跳棋的棋盘是8*8的方格，在16世纪时的欧洲相当流行，早期变形的版本则在现今伊拉克境内、古代吾珥城（City of UR，约公元前3000年）的废墟中出土。西洋跳棋的棋子通常是黑红两色的圆盘，棋子只能走斜线；两位玩家轮流下棋，只要跳过对手的棋子就能吃掉它。显而易见，由于西洋跳棋总共有5×1020种可能走法，要证明西洋跳棋保证和局的困难度远远超过证明圈叉游戏没有赢家这一回事。

西洋跳棋的研究团队总共考虑了39兆种棋盘上只剩＋颗或更少棋子的布局，借以判定黑红两色中哪一位会是最终赢家。；究团队也使用一种特殊的搜寻算法，研究棋局如何从原始状态“演变成”只剩下10颗棋子的决战阶段。顺利破解西洋跳棋的问题，代表人工智能这门经常与计算机复杂的问题解决策略有关的领域，总算跨越了一项非常重要的里程碑。

沙费尔在1994年用这套名为契努克（Chinook）的计算机程序挑战世界西洋跳棋的棋王汀斯雷（Marion Tinsley），结果计算机与人脑间的对抗不断以平手作收，八个月后江斯雷因有些人将他的死因归咎于沙费尔，因为来自契努克的挑战导致汀斯雷承受过大压力，也因此加速了他的死亡。

原文发布时间为：2015-12-19

本文来自云栖社区合作伙伴“大数据文摘”，了解相关信息可以关注“BigDataDigest”微信公众号