设为首页 - 加入收藏
广告 1000x90
您的当前位置:二四六天天好彩308K文字资料 > 博弈树搜索 > 正文

python实现的基于蒙特卡洛树搜索(MCTS)与UCT RAVE的五子棋游戏

来源:未知 编辑:admin 时间:2019-05-09

  蒙特卡洛模拟对局就是从某一棋局出发,随机走棋。有人形象地比喻,让两个傻子下棋,他们只懂得棋规,不懂得策略,最终总是可以决出胜负。这个胜负是有偶然性的。但是如果让成千上万对傻子下这盘棋,那么结果的统计还是可以给出该棋局的固有胜率和胜率最高的着法。

  蒙特卡洛树搜索通过迭代来一步步地扩展博弈树的规模,UCT 树是不对称生长的,其生长顺序也是不能预知的。它是根据子节点的性能指标导引扩展的方向,这一性能指标便是 UCB 值。它表示在搜索过程中既要充分利用已有的知识,给胜率高的节点更多的机会,又要考虑探索那些暂时胜率不高的兄弟节点,这种对于“利用”(Exploitation)和“探索”(Exploration)进行权衡的关系便体现在 UCT 着法选择函数的定义上,即子节点\(N_{i}\)的 UCB 值按如下公式计算:

  可见 UCB 公式由两部分组成,其中前一部分就是对已有知识的利用,而后一部分则是对未充分模拟节点的探索。C小偏重利用;而C大则重视探索。需要通过实验设定参数来控制访问节点的次数和扩展节点的阈值。

  后面可以看到,在实际编写代码时,当前节点指的并不是具体的着法,而是当前整个棋局,其子节点才是具体的着法,它势必参与了每个子节点所参与的模拟,所以N就等于其所有子节点参与模拟的次数之和。当C取1.96时,置信区间的置信度达到95%,也是实际选择的值。

  蒙特卡洛树搜索(MCTS)仅展开根据 UCB 公式所计算过的节点,并且会采用一种自动的方式对性能指标好的节点进行更多的搜索。具体步骤概括如下:

  3.利用 UCB 公式计算每个子节点的 UCB 值,选择最大值的子节点;

  5.直到遇到叶节点,如果叶节点未曾经被模拟对局过,对这个叶节点模拟对局;否则为这个叶节点随机生成子节点,并进行模拟对局;

  6.将模拟对局的收益(一般胜为 1 负为 0)按对应颜色更新该节点及各级祖先节点,同时增加该节点以上所有节点的访问次数;

  由此可见 UCT 算法就是在设定的时间内不断完成从根节点按照 UCB 的指引最终走到某一个叶节点的过程。而算法的基本流程包括了选择好的分支(Selection)、在叶子节点上扩展一层(Expansion)、模拟对局(Simulation)和结果回馈(Backpropagation)这样四个部分。

  UCT 树搜索还有一个显著优点就是可以随时结束搜索并返回结果,在每一时刻,对 UCT 树来说都有一个相对最优的结果。

  实际运行时,当棋盘较小(6X6),需要连成一线)时,算法发挥的水平不错,但是当棋盘达到8X8进行五子棋游戏时,即使将算法运行的时间调整到10秒,算法的发挥也不太好,虽然更长的时间效果会更好,但是游戏体验就实在是差了。因此考虑增加一个简单的策略:当不是所有着法都有统计信息时,不再进行随机选择,而是优先选择那些在当前棋盘上已有落子的邻近位置中没有统计信息的位置进行落子,然后选择那些离得远的、没有统计信息的位置进行落子,总得来说就是尽可能快速地让所有着法具有统计信息。对于五子棋来说,关键的落子位置不会离现有棋子太远。

  图片引自论文《Monte Carlo Tree Search and Its Applications》,在经过A、B、C三步后得到当前的盘面状态,这三步的顺序是可能不相同的,但是得到的状态是相同的,所以不作区分。

  RAVE是基于AMAF的,它视一个着法在对当前盘面的所有模拟中是相同的,不论它出现在何种子状态下、或是由哪个玩家给出的,如下图:

  对于状态s来说,如果使用MC的统计方法,那么(a, s)出现的次数是2,胜利的次数是0,而(b, s)出现的次数是3,胜利的次数是2,根据胜率,应该选择着法b;如果使用RAVE的统计方法,那么着法a在状态s的所有子树中出现的次数5(不论它在第几层——即不论它的父节点是否是s,也不论是由哪个玩家进行的,只要是在状态s所进行的模拟中——也就是s的子树t(s)中即可),胜利的次数是3,着法b在状态s的所有子树中出现的次数5,胜利的次数是2,根据胜率,应该选择着法a。可以看到,对于相同的情况,两种方法可能给出不同的选择。

  可以根据算法实际运行的情况来选择k的值,论文给出的实验结果表明k大于1000的时候效果较好。

  在了解了RAVE之后,再看之前实现的算法,实际上是有问题的,它很像RAVE,也很像MC,但实际都没有实现正确:对于上面的t(s)树,之前的算法认为棋盘上所有合法的位置都是s的子节点,以a为例(对于之前的算法来说,这里的a实际上指的是棋盘上的某个位置),对于玩家player1,它统计的是(player1, a),当player1在某次模拟(无论是否是在模拟的第一步就走出了着法a)走出了a,它统计了,对于另一个玩家player2走出的a,它没有统计,如果以AMAF来考虑的话,a总的模拟次数应该是(player1, a)与(player2, a)之和,但是对于胜利次数,(player1,a)统计的是player1在走出a并获胜的次数,未统计player2在走出a且player1获胜的次数,和棋不进行统计,所以说之前的算法既不算是RAVE,也不是MC!

  问题是它的表现还不错,以至于我在继续看论文之前没有意识到它是有问题的,甚至在我意识到它有问题之前,还实现了一个基于它的UCT RAVE版本,而且表现进一步提升,下面是核心的代码;

  它在较短的时间内,如5s或10s内的表现是优于下面将要说明的实现的,因为短时间内它的模拟次数更多,这也符合蒙特卡洛方法的原理。完整的代码在Github中的n_in_row_uct_rave_not_so_correct.py。

  下面是根据论文以及我的理解重新实现的UCT RAVE,因为水平有限,不一定对,把核心代码放在这里,欢迎大家与我一起讨论。

  这个算法要得到一个较好的选择需要更多的时间/更多的模拟次数,同时在实际使用的过程中,\(\beta\)的选择也很关键的,如果使用前面介绍的公式,需要经过很多模拟比如10000次才能有一个较好的着法。其他的方法就比较复杂了,甚至可以结合机器学习。当总的模拟次数不多的时候,k的值不宜过大,我在模拟时间等于15s左右的时候,平均的模拟次数在3000次左右,这个时候取k=1000时算法表现较好。

  之所以同样的时间模拟次数比前面有问题的算法要少得多,是因为随着模拟的进行,plays等中的内容会远多于前面的算法,所以遍历就需要更多的时间。实际上算法在做出了选择之后,有一部分节点就不再需要了,这个时候就可以进行剪枝,下面是一种简单直接的剪枝方法:

  正是因为单位时间内模拟的次数较少,所以短时间内的表现上不如之前的算法,可以通过多线程等手段来进一步提高单位时间内的模拟次数,这也是下一讲要进行的工作之一。

  [2] 徐心和, 徐长明. 计算机博弈原理与方法学概述[J]. 中国人工智能进展, 2009: 1-13.

本文链接:http://mzi-ads.com/boyishusousuo/475.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top