AlphaGo论文读后感及其应用
| | 分类于
字数统计:2.6k字 | 阅读时长:9 分钟 阅读量: 0 | 评论量: 0

AlphaGo论文读后感及其应用

with 0 comments
Word count: 2.6k | Reading time: 9min

论文摘要

  1. 这个方法使用估值神经网络来评估棋局,以及使用策略网络来选择如何落子。这些深度神经网络被一种新的组合来训练:使用了人类专业比赛数据的监督学习,以及自我对弈的强化学习。

  2. 在状态 s 时对搜索树进行剪枝,然后用一个近似估值函数v(s)≈v∗(s)取代状态 s 下面的子树,这个近似估值函数预测状态 s 之后的对弈结果。

  3. 搜索的宽度可以通过来自策略p(a|s)的样品动作来降低,这个策略是一个在位置 s 的可能下棋走子 a 概率分布。

  4. 蒙特卡洛树搜索使用蒙特卡洛走子方法,评估搜索树中每一个状态的估值。随着执行越来越多的模拟,这个搜索树成长越来越大,而且相关估值愈发精确。

  5. 然而,先前的工作已经受到了基于输入的线性组合的肤浅的策略或估值函数的限制。

  6. 它们使用很多层的神经网络,每一个安排在重叠的瓦片,用来构建愈发抽象的,局部代表的图片,我们为围棋程序部署了类似的体系架构。我们给程序传入了一个 19*19 大小棋局的图片,然后使用卷积神经网络来构建一个位置的代表。我们使用这些神经网络来降低搜索树的有效的深度和广度:通过估值网络来评估棋局,和使用策略网络来博弈取样。

  7. 我们的AlphaGo程序有效地把策略网络、估值网络,和蒙特卡洛搜索树结合在一起。

  8. 如果赢棋,结果等于 +1,如果输棋,结果等于 -1。然后权重在每一个步骤 t 更新:朝向最大化预期结果的方向随机梯度递增。

  9. 我们想出了新的自我对弈的数据集合,包含了三千万个不同的棋局,每一个都是从不同盘博弈中采样。每一盘博弈都是在 RL 策略网络和自己之间对弈,直到博弈本身结束。

  10. AlphaGo 在把策略网络、估值网络和 MCTS 算法结合,MCTS 通过预测搜索选择下棋动作。

  11. 基于高性能蒙特卡洛树搜索算法的、蒙特卡洛树搜索

  12. 基于一个深度神经网络和树搜索的结合开发了一个围棋程序。我们首次,对围棋开发了一个有效地下棋走子选择器和棋局评估函数,它是基于被一个创新型地监督学习和强化学习地组合训练的深度网络。我们引入了新的搜索算法,它成功的把神经网络评估和蒙特卡洛滚动走子结合在一起。我们的程序 AlphaGo 把这些组成部分按照比例集成在一起,成为了一个高性能的树搜索引擎。

  13. 一个有挑战性的决策任务;一个难以对付的解空间;和一个非常复杂的最优解,以至于它看上去不可能世界使用策略或者估值函数逼近。

  14. 通过把树搜索和策略估值网络结合在一起,AlphaGo最终达到了围棋职业选手的水平。

AlphaGo应用——五子棋

评估函数

  1. 是对一个可走的空位子进行打分,如果ai白子落在这个空位置的分数越高,说明这个位置就越好,每次ai走棋就找到一个最好的空位置就行了。

  2. 是对现在的棋盘局面进行打分。 ai白子首先找所有可以走的空位置,模拟走了这个位置以后,用f函数进行局面评分,如果走了这样的一个空位置的得分越高,说明这个位置就越好,每次ai走棋就找这样一个分数最高的位置。

如果你只是想实现一个只看一步的ai,那么你可以用第一个函数也可以用第二个函数。但是如果你想要实现基于博弈树的极大极小搜索和α-β剪枝算法的”聪明”ai,就只能用第二个函数,因为博弈树必须要对局面打分,而不是对位置打分

棋型权重设计

棋型代号 棋型说明 权重 棋型代号 棋型说明 权重
WIN 白赢 1000000 LOSE 黑赢 -10000000
FLEX4 白活4 50000 flex4 黑活4 -100000
BLOCK4 白冲4 400 block4 黑冲4 -100000
FLEX3 白活3 400 flex3 黑活3 -8000
BLOCK3 白眠3 20 block3 黑眠3 -50
FLEX2 白活2 20 flex2 黑活2 -50
BLOCK2 白眠2 1 block2 黑眠2 -3
FLEX1 白活1 1 flex1 黑活1 -3

权重设计表格

极大极小搜索

在博弈树中,当ai走棋时选择对自己最有利的位置节点走,而当玩家走棋时,是ai模拟玩家选择对玩家最有利的位置节点走。由于评估函数F对局势的评分是对于ai白子来说的,所以ai走棋时选择F最大的节点,模拟玩家走棋时选择F最小的节点(F越小,对ai越不利,对玩家越有利,ai模拟玩家时是认为玩家是”聪明”的),这就是称为极大极小搜索的缘故。

α-β剪枝算法

α-β剪枝算法中每一个节点对应有一个α和一个β,α表示目前该节点的最好下界,β表示目前该节点的最好上界。在最开始时,α为负无穷,β为正无穷。然后进行搜索,max层节点每搜索它的一个子节点,就要更新自己的α(下界),而min层节点每搜索它的一个子节点,就要更新自己的β(上界)。如果更新之后发现α>=β了,说明后面的子节点已经不需要进行搜索了,直接break剪枝掉。这就是α-β剪枝算法的全部含义。

局部搜索和静态评价启发

a) 局部搜索是说,只考虑那些能和棋子产生关系的空位置,而不用考虑所有空位置,这样能极大减小b的值。

b) 静态评价启发是对于α-β剪枝算法而言的,意思是说,如果越早搜索到较优走法,剪枝就会越早发生。如果对可走节点的评估分数进行简单排序,就可以提高剪枝速度。

Bingo AI的实现

游戏规则

游戏双方分别在3x3的方格纸上依次画x或o,直到一方的x或o连成一条直线(3个子)获胜。

平局示意图

系统架构设计

Pygame

Pygame is a set of Python modules designed for writing video games. Pygame adds functionality on top of the excellent SDL library. This allows you to create fully featured games and multimedia programs in the python language.

TensorFlow

TensorFlow 是一个端到端开源机器学习平台。它拥有一个全面而灵活的生态系统,其中包含各种工具、库和社区资源,可助力研究人员推动先进机器学习技术的发展,并使开发者能够轻松地构建和部署由机器学习提供支持的应用。

编码阶段

界面设计图示

在规则设定上,默认玩家先手AI后手。玩家用”X”表示,AI用”O”表示。

博弈树的设计图示

在上图中,树的深度是9,因为最坏情况下要走9步。每个节点记录落子的方位和权值信息。由于是玩家先手,所以第一层的节点存储玩家的信息,由于AI的胜率要尽可能大,所以估值函数返回的值当中一定要是最小的才行;下一层是AI执棋,所以估值函数的返回值要选择大的。

AI必输局面

由以上局面和一般经验总结,占据最中间的位置赢面最大,所以可以设置在arr[1][1]时的初始权重最大;其次是边角位置,由于可以分别向两个方向落3个子,所以它的初始权重次之。边缘的位置不好判断,要结合具体的局面来设置权重。我们把所有的局面输入神经网络,通过神经网络的BP机制来动态调整权重。

AI自学习:

监督学习演示视频

如以上视频所示,一开始我们和AI下棋,AI通过随机函数来随机生成落子方位。随着棋局的增加,AI将局面数组、赢方、权重的信息记录进一个json文件,根据玩家赢得次数来设计每个局面的权重。然后进入神经网络学习,通过BP来调整权重,通过α-β剪枝来降低搜索时间复杂度。随着我们和AI对弈次数的增加,AI会变得越来越有赢面,最后不再使用随机函数。

参数设计:

参数名称 类型 说明
Arr Int[][] 游戏地图,0是空,1是玩家子,2是AI子
Hold Int 谁落子,1是玩家落子,2是AI落子

函数设计:

函数名称 参数 返回值 说明
judge_full Arr:棋局地图 Bool:是否平局 供judge_win调用
judge_win Arr:棋局地图 Int:哪方赢(0,1,2,-1) 判断局面情况
fill_zero Arr:棋局地图 NaN 游戏结束将地图填充0
computer_move Arr:棋局地图 NaN AI落子
process_res NaN NaN 游戏结束后的处理,是否继续
evaluate Arr:棋局地图 Int:权重 估值函数,里面要调用学习到的模型来输出权重

展望:

关于AI状态机的设定。

参考文献

  1. AlphaGo论文的译文

  2. Mastering the game of Go with deep neural networks and tree search

  3. 五子棋ai:极大极小搜索和α-β剪枝算法的思想和实现(qt和c++)

  4. Alpha-Beta剪枝算法(极大极小算法-人工智能)

  5. 用Python和Pygame写游戏-从入门到精通

  6. 井字棋真的有必胜方法吗?

  7. 有谁照着论文把 AlphaGo 重现出来了?

看了这么久,不请我喝杯茶吗?