电脑下象棋是靠暴力穷举吗？

电脑下象棋是靠暴力穷举吗？

前言：围棋的AI技术确实很高大上，深度学习、强化学习、蒙特卡洛树搜索等，但是象棋或者国际象棋真的是让机器简单地暴力穷举就行了吗？

棋类的人机大战，我们很多人听说过的至少有两次。

1996年2月17日，首次国际象棋人机大战落下帷幕。世界棋王卡斯帕罗夫对垒“深蓝”计算机。在这场人机对弈的6局比赛中，卡斯帕罗夫以4：2战胜电脑。在次年，也就是1997年5月，“深蓝”重新向卡斯帕罗夫发起挑战，最终“深蓝”以3.5：2.5的成绩获胜，成为首个在标准比赛时限内战胜国际象棋世界冠军的电脑系统。

国际象棋特级大师加里·卡斯帕罗夫与“深蓝”对战

2016年3月16日，谷歌旗下英国公司DeepMind 开发的AlphaGo计算机程序，在与世界顶尖天才棋手李世石的五番棋对决中，以4:1取得完胜，成为第一个击败人类职业围棋选手的电脑程序。2016年12月底，AlphaGo身披“Master”马甲，5天内横扫中日韩棋坛，最终取得了60场连胜纪录。2017年5月，在浙江嘉兴桐乡的“中国乌镇围棋峰会”上，柯洁与AlphaGo举行三番棋大战，最终0比3告负。

世界围棋第一人柯洁与AlphaGo对战

我们都或多或少地听说，AlphaGo如何使用深度学习（Deep Learning）、强化学习（Reinforcement Learning）、蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）等技术实现了其强大的对弈能力。为了凸显其惊人的能力，很多人描述围棋有多么复杂，不像象棋，机器通过穷举法就可实现。然而，象棋真是这么简单地就可穷举出来？

中国象棋、国际象棋与围棋

关于围棋与象棋的复杂度分析，其实至今我们也没办法定量地计算出来，但是可以定性地分析。国际象棋的棋盘大小为64，围棋的大小为361。由于棋盘大小的不同，每走一步国际象棋和围棋的计算量的要求是不一样的，围棋明显要求更高。这在博弈论中一般称之为分支因子（branching factor），即平均每个落子后的合法走法。国际象棋的分支因子约为35，而围棋大约是250。另外一个可以说明算力要求不同的指标是搜索空间，在该指标上两者也存在指数级的差异，国际象棋是10^43~10^50，而围棋大约是10^170。我们知道宇宙中的原子总数总共大约也才10^80，因此不管是象棋还是围棋，其搜索空间绝对算是天文数字。目前世界上最快的超级计算机大概是10^18次/秒，即百亿亿次每秒，已经很惊人了，但是放在象棋或者围棋的搜索空间来看，想要穷举，明显远远不够。

庞大的搜索空间

细心研究的朋友会发现，1997年的深蓝可搜寻及估计随后的12步棋，而一名人类象棋好手大约可估计随后的10步棋。很显然，深蓝的取胜并不是靠暴力穷举实现的。实际上，深蓝采用了并行处理、搜索优化（博弈树min-max算法、alpha-beta剪枝等）、评估函数、开局库与残局库以及人类大师的知识等多种技术，使得它能够在与卡斯帕罗夫的对局中取得胜利。换个角度来看，如果都已经穷举了象棋棋局的走法，那么其搜索空间已经能具体计算出来了，然而实际上并没有。

穷举围棋的变化，确实要比穷举象棋、国际象棋大很多个数量级，但象棋和国际象棋的变化数量也已经远超人类的极限了，以现代科技的发展速度，还远远看不到有任何能够穷举的可能性。