算法|最强通用棋类AI,AlphaZero强化学习算法解读

译者:AI研习社(Champagne Jin)
双语原文链接:AlphaZero, a novel Reinforcement Learning Algorithm, in JavaScript
在本篇博文中,你将会了解并实现AlphaZero。AlphaZero是一个令人大开眼界且超乎寻常的强化学习算法,它以绝对的优势战胜了多名围棋以及国际象棋冠军。本文将会带你使用AlphaZero来解决一个益智小游戏(Dots and Boxes)并将其部署成一个纯JavaScript构建的Web应用。
AlphaZero最关键也是最令人诧异的一点,就是其能够在不依赖于外部先验知识的情况下在棋盘类游戏中获得超越人类的表现。AlphaZero通过自我博弈汲取经验知识来不断精通游戏。
算法|最强通用棋类AI,AlphaZero强化学习算法解读
文章插图
我们会借助于Github上由Surag Nair开发的一个“简化后的、高度灵活的、经过注释的且易于理解的”Python版AlphaZero来进行该项目。
你大可以先去这里玩一玩这个游戏。而Web应用以及具体的JavaScript实现代码可以在这里获取得到。这份代码是从该Python实现中移植过来的。
https://carlos-aguayo.github.io/alphazero/
有关AlphaZero的原理,你可以阅读这篇由Silver,David等人撰写的论文:“Mastering the game of Go without human knowledge” nature 550.7676 (2017): 354–359.
Dots and Boxes小游戏
Dots and Boxes是一个常见的儿童益智游戏,不过其具有令人讶异的复杂度。
该游戏中,两名玩家轮流在两个相邻点之间放置一条水平或垂直线。如果某个 1×1 的小正方形的 4 条边都被连上了,那么补齐这个小方块的一方就获得 1 分,得分的玩家被奖励多走一步,再连一条线。当棋盘已满时,游戏结束,并且得分最高的玩家获胜。
(译者注:这个游戏相当有意思,建议先去玩玩看,点这里。能不能战胜AlphaZero就看你了!)
算法|最强通用棋类AI,AlphaZero强化学习算法解读
文章插图
人工智能与棋盘游戏
机器是否能够产生智能,我们已经为此思考了很久很久。那么,该如何验证机器具有智能呢?一个常用方法就是玩棋盘游戏,比如国际象棋,看看其是否具有超人的能力,甚至击败世界冠军。
1957年,Herbert Simon预言计算机系统能够在十年内击败国际象棋冠军。虽说实际上花的时间长了点,但是在1997年5月,计算机击败了当时的国际象棋冠军——Garry Kasparov。
(译者注:战胜Kasparov的机器被命名为DeepBlue,意为“深蓝”)
尽管这一里程碑事件意义非凡,但人们仍可以争论这一计算机系统是否“智能”。
这一类计算机系统由以下三个组件构成:
1. 人为定义的评价函数;
2. 博弈树搜索算法;
3. 极为强悍的硬件设备。
评价函数会将棋盘盘面作为输入并输出该盘面的“价值”。高价值表示当前玩家处于非常有利的位置。例如,在国际象棋棋盘上,玩家即将进行“将死”时就会对应一个非常高的值。
博弈树搜索算法(比如 Minimax)在所有可能的走棋中进行搜索,寻找那些能够确保得到高价值棋盘盘面的路径。对于那些已经明知不可能有效的路径可以直接放弃搜索,从而使算法变得更有效率。这就是 Alpha-beta剪枝 的作用。
最后,搭配上异常强悍的硬件,你就将拥有一台能够打败国际象棋世界冠军的机器。
问题在哪儿?经验丰富的棋手人为地精心调制这些评价函数。这些计算机系统还依赖于一本本记录着最佳走棋的开局棋谱。游戏中局,还会用到通过研究大师们的博弈而精心构造的评价函数。这些函数还会经由象棋大师们进一步的优化调整。
例如,我们完全就可以为 Dots and Boxes 构造一个评价函数。一个合理而直接的选择就是做一个得分的比较。得分的正向差值越大,游戏盘面就对我们越有利。大多数情况下,这是可行的。然而,在 Dots and Boxes 中,就像许多其他棋盘类游戏一样,最佳的走法可能需要牺牲短期利益来换取长期利益。在 Dots and Boxes 游戏中,有时最好不要急于得分并获得额外先手,相反,要迫使对手走某一步棋。因此,我们必须考虑大量复杂场景并精心调制评价函数!
击败Kasparov的评价函数需要识别多达8000个盘面特征!而且其中绝大多数都是手动描述并调整的!
所以,倒也不是贬低这个击败国际象棋世界冠军重要里程碑的意思,只是,需要顶级玩家来定义这些计算机的行为并手动调整如此多的变量实在是有够折腾人的。
AlphaZero是什么?为何它如此令人心潮澎湃?
AlphaZero是首个能够在国际象棋、围棋等游戏中达到超越人类水平、击败世界冠军的计算机系统,且它仅依赖于游戏规则,无需任何人类先验知识。