蒙特卡罗树搜索UCT实施

3 回答

• 3

  生成树的最佳方法是一系列随机播放 . 诀窍是能够在探索和利用之间取得 balancer （这是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，对于White获胜则为-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

  回复于 2024-05-03T12:59:54+08:00
• 3

  来自http://mcts.ai/code/index.html：

  Below are links to some basic MCTS implementations in various
  programming languages. The listings are shown with timing, testing
  and debugging code removed for readability.
  

  Java

  Python

  回复于 2024-05-03T12:59:54+08:00
• 24

  如果你有兴趣我写了这篇文章：https://github.com/avianey/mcts4j

  回复于 2024-05-03T12:59:54+08:00