五子棋AI教程第二版二：博弈算法的前世今生

[lihongxun945]

从深蓝说起

从计算机问世后，博弈算法从来就没有停止过改进的步伐。最早打败人类顶级棋手的AI就是深蓝。以下内容摘自百度百科：

深蓝是美国IBM公司生产的一台超级国际象棋电脑，重1270公斤，有32个大脑（微处理器），每秒钟可以计算2亿步。"深蓝”输入了一百多年来优秀棋手的对局两百多万局。
1997年 6月，深蓝在世界超级电脑中排名第259位，计算能力为每秒113.8亿次浮点运算。
1997年的深蓝可搜寻及估计随后的12步棋，而一名人类象棋好手大约可估计随后的10步棋。每增加1步棋的搜寻能力约等于增加下棋强度约80 ELO分。

1997 年深蓝以一分总比分优势战胜当时的国际象棋之王 卡斯帕罗夫，这是电脑第一次在棋类中战胜顶尖人类选手，让世人见证了人工智能的威力。在这以后，计算机逐渐统治了除围棋意外的大部分棋类游戏。

可以看到，深蓝其实并不是一个很厉害的AI，因为它只搜索了12层，现在有名的 象棋旋风 等软件都可以超过这个搜索深度。深蓝的基本原理和本文介绍的方法类似，不过由于深蓝的运算速度远高于我们现在的个人电脑，并且他可以进行大量的并行运算，所以能达到比较高的棋力。我们的五子棋AI运算速度远低于深蓝的每秒2亿步，我在自己的MBP笔记本上大约每秒运算 3万步。可以认为深蓝作为一个早期的AI，靠的是堆硬件来提升棋力。

博弈算法

很多游戏都是"博弈"的，比如五子棋是双方博弈，斗地主也是。有些是双方竞争，有些会包含合作。在《人工智能-一种现代方法》一书中的第五章 《对抗搜索》中，介绍了博弈论专家们对博弈的一种定义：

有完备信息的，确定性的，轮流行动的，两个游戏者的零和游戏

这也是我们这套算法适用的场景，注意其中任何一个条件不满足，那么将无法直接使用这套算法进行设计。比如这些游戏就不行：

• 斗地主和德州等大部分牌类游戏，因为不是完备信息，看不到对方玩家的牌，而且还有随机性（摸牌不确定）
• 四国军棋，不是完备信息，不是双人游戏
• DOTA，不是完备信息，不是双人游戏，而且不是轮流行动

而五子棋，围棋，黑白棋，象棋等都是满足这些条件的，因此都可以用这套算法来实现。

围棋难题

那么为什么在神经网络出现前，围棋AI的棋力那么弱呢？要回答这个问题，我们先要了解下棋类游戏的复杂度。以下内容摘自维基百科：

名称	复杂度
黑白棋	58
五子棋	70
国际象棋	123
中国象棋	150
围棋	360

表格中的复杂度是的是以10为底数的指数，也就是10的次方

可以看到，哪怕是最简单的黑白棋，其状态空间的复杂度也是一个天文数字，而围棋的复杂度远远高于前面的几种棋类。我们把这个复杂度叫做空间复杂度，由于围棋的复杂度太高，因此很难在较短的步骤内评估出合适的走法，而且也很难搜索到较深的深度。 更直观点说，围棋的难点在于两部分：

• 围棋本身的局面评估很复杂，不像象棋一样可以简单的给每个子打一个分。围棋更注重“局势”，非常难用常规手段打分。由于连评分都不准，因此搜索的基础都不可靠
• 围棋很难达到较深的深度。围棋每一步的可能性非常多，平均一步需要考虑100+种可能，因此很难达到较深的搜索深度。

AlphaGO 通过两个神经网络，分别解决了这两个问题。

• 价值网络可以比较准确的进行局势的评分
• 策略网络可以让产生更少的分支，预测更合理的着法

如果现在不是很好理解这段话没关系，等你读完接下来的文章，再回头看这一段，就可以理解了。

卷积神经网络

AlphaGO 开启了卷积神经网络在围棋中应用的先例，后来所有的围棋AI都向这个方向前进，围棋AI们的棋力有了质的飞越。那么什么是卷积神经网络呢？

如果以后有时间我会写一个神经网络的教程，卷积神经网络是神经网络模型中的一种，本来是用来提取图片特征，进行图像识别的。卷积是一种矩阵运算，通过不同的卷积核，可以提取图片的不同特征。通过神经网络自动学习，就可以学到图像的特征从而学会识别图片。很凑巧地，棋盘不就是一个小图片吗？比如围棋就是一个 19x19 的图片，并且每一个像素只有三种值。对这个图片进行图像识别并评分，就变得是很自然的事情。

好了，背景介绍到这里，从下一章让我们真正开始学习算法并编写代码吧。

下一篇 五子棋AI设计教程第二版三：极小化极大值搜索

[Jexecellent]

前端还能这么玩吗 可怜了我这菜鸡代码搬运工..

[boh5]

可以看到，深蓝其实并不是一个很厉害的AI，因为它只搜索了12层，现在有名的 象棋旋风 等软件都可以超过这个搜索深度。深蓝的基本原理和本文介绍的方法类似，不过由于深蓝的运算速度远高于我们现在的个人电脑，并且他可以进行大量的并行运算，所以能达到比较高的棋力。我们的五子棋AI运算速度远低于深蓝的每秒2亿步，我在自己的MBP笔记本上大约每秒运算 3万步。可以认为深蓝作为一个早期的AI，靠的是堆硬件来提升棋力。

其中，不过由于深蓝的运算速度远高于我们现在的个人电脑 这句可能存在错误。
维基百科-深蓝 (超级电脑)中提到：

1997年6月，深蓝在世界超级电脑中排名第259位，计算能力为11.38 gigaflops。

维基百科-每秒浮点运算次数中的近几年一些 CPU 的浮点运算能力列表：

• Intel Core 2 Duo E8400 24 GFLOPS
• AMD Phenom 9950: 29.05 GFLOPS
• Intel Core i5-4210U: 36.77175 GFlops

由此可见，早期酷睿 CPU 的浮点性能就已经超过深蓝的浮点性能了。

[sinchb]

如果将棋盘放大到19*19，会对算法本身的复杂度有多大影响？ @lihongxun945