Mak*_*s_F 20 java tree artificial-intelligence montecarlo
你能解释一下如何建树吗？
我完全理解如何选择节点,但更好的解释将真正帮助我实现这个算法.我已经有一个代表游戏状态的棋盘,但我不知道(理解)如何生成树.
有人能指出一个评论很好的算法实现(我需要用它来进行AI)吗？还是更好的解释/例子呢？
我没有在网上找到很多资源,这个算法比较新...
dan*_*ard 24
生成树的最佳方法是一系列随机播放.诀窍是能够在探索和利用之间取得平衡(这是UCT的用武之地).这里有一些很好的代码示例和大量的研究论文参考:https://web.archive.org/web/20160308043415/http : //mcts.ai : 80/index.html
当我实现算法时,我使用随机播放,直到我达到终点或终止状态.我有一个静态评估函数,可以计算此时的收益,然后从这一点开始将分数传播回树上.每个球员或"球队"都假设另一支球队将为自己发挥最佳动作,并为对手做出最糟糕的动作.
我还建议查看Chaslot的论文和他的博士论文以及一些参考他的工作的研究(从那时起基本上所有的MCTS工作).
例如:玩家1的第一次移动可以模拟未来10次移动,在玩家1移动和玩家2移动之间交替.每次你必须假设对方球员会尽量减少你的分数,同时最大化他们自己的分数.基于这种称为博弈论的整个领域.一旦你模拟到10场比赛结束,你再次从起点迭代(因为没有必要只模拟一组决定).每个树的分支都必须拿下其中分数传播了树和分数代表了玩家在做模拟假设其他球员也选择为自己的最佳动作最好的回报.
MCTS包含四个战略步骤,只要剩下时间就会重复.步骤如下.
在选择步骤中,树从根节点遍历,直到我们到达节点E,在那里我们选择尚未添加到树的位置.
接下来,在播放步骤期间,以自我播放的方式进行移动,直到到达游戏结束.对于Black(LOA中的第一个玩家)获胜,这个"模拟"游戏的结果R是+1,如果是平局,则为0,如果是白棋,则为-1.
随后,在扩展步骤中,将E的子项添加到树中.
最后,R在反向传播步骤中沿着从E到根节点的路径传播回来.当时间到了,程序播放的移动是具有最高值的根的子节点.(这个例子来自本文 - PDF
www.ru.is/faculty/yngvi/pdf/WinandsBS08.pdf
以下是一些实现:
使用一些MCTS实现的库和游戏列表 http://senseis.xmp.net/?MonteCarloTreeSearch
和一个独立于游戏的开源UCT MCTS库,名为Fuego http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html