约公元前548年/围棋

围棋游戏非常复杂，其较大的棋盘、复杂的策略，以及变化多端的走法导致可能的选择太多。目前功能强大的国际象棋软件可以击败顶尖的棋手了，而最好的围棋程序往往会输给受过围棋训练的孩子。

井字棋（约公元前1300年），破解阿瓦里游戏（2002年），破解西洋跳棋（2007年）

围棋是一种两人制的棋类游戏，起源于公元前2000年左右的中国。最早提到围棋的文字记载是中国最早的编年体史书《左传》，它讲述了公元前548年一位棋手的故事。围棋从中国传入日本后在那里成为广受欢迎的游戏。对弈时两名棋手各持黑白两色的棋子，轮流在一块19×19的方格形状的棋盘的交叉点上落子。如果某一方的一枚或一组棋子被对方颜色的棋子完全围住，就将被移除棋盘。双方的目标都是控制比对手更大的棋盘范围。

围棋被认为是世界上最复杂的棋盘游戏。有很多因素造成了围棋的复杂性，比如棋盘范围较大、有多种的战略和战术，以及游戏中各种变化的可能性太多。仅仅是棋子的数量比对手多并不能保证赢棋。如果将对称性也考虑进去，围棋的开局就有32940种棋路，其中992种被认为是比较强势且常用的。最终可能的盘面数量大约有10172种之多，而算上不同的走法更是达到10768种。天才棋手之间的典型对弈大约会走到150步，平均每步约有250个不同的走法可选择。目前功能强大的国际象棋软件可以击败顶级棋手，而最好的围棋程序往往会输给受过围棋训练的孩子。下围棋的计算机程序很难做到“先多想几步”再做出判断。相比国际象棋，围棋每下一子需考虑的各种可能性更多，因为在格点上不同的空位落子对整体布局会造成不同的影响，所以机器不易判断在何处落子更有利。

2006年，两名匈牙利研究人员报告说，有一种名为UCT的算法（树状结构的上置信界算法），可以把计算机的搜索重点集中在最有希望取胜的下法上，因而可以和专业围棋选手竞争，但目前还只能用于9×9的棋盘上。[1]

[1] 2016年3月，谷歌的人工智能围棋软件Alpha Go已战胜了世界顶级围棋高手。——译者注