五子棋AI教程第二版二:博弈算法的前世今生
lihongxun945 opened this issue · 3 comments
从深蓝说起
从计算机问世后,博弈算法从来就没有停止过改进的步伐。最早打败人类顶级棋手的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 开启了卷积神经网络在围棋中应用的先例,后来所有的围棋AI都向这个方向前进,围棋AI们的棋力有了质的飞越。那么什么是卷积神经网络呢?
如果以后有时间我会写一个神经网络的教程,卷积神经网络是神经网络模型中的一种,本来是用来提取图片特征,进行图像识别的。卷积是一种矩阵运算,通过不同的卷积核,可以提取图片的不同特征。通过神经网络自动学习,就可以学到图像的特征从而学会识别图片。很凑巧地,棋盘不就是一个小图片吗?比如围棋就是一个 19x19 的图片,并且每一个像素只有三种值。对这个图片进行图像识别并评分,就变得是很自然的事情。
好了,背景介绍到这里,从下一章让我们真正开始学习算法并编写代码吧。
前端还能这么玩吗 可怜了我这菜鸡代码搬运工..
可以看到,深蓝其实并不是一个很厉害的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 的浮点性能就已经超过深蓝的浮点性能了。
如果将棋盘放大到19*19,会对算法本身的复杂度有多大影响? @lihongxun945