013 约公元前548年 围棋

围棋的复杂度在于大范围棋盘、复杂的策略，以及数量庞大又变化多端的对弈过程。尽管棋艺高超的西洋棋软件有能力击败西洋棋高手，但是，最厉害的围棋软件却往往会输给受过围棋训练的小朋友。

圈叉游戏（约公元前 1300 年），破解艾瓦里游戏（2002 年）及破解西洋跳棋（2007 年）

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

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

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

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