蒙特卡洛与UCB适用于复杂的纸牌游戏

Question

我试图了解MCTS算法的工作原理以及如何在纸牌游戏中实现它以改进AI引擎.

我已经阅读了mcts.ai/网站和许多关于它的论文,其中一篇展示了一些关于在智能卡游戏的AI中应用蒙特卡洛搜索与UCB成功的结果,这或多或少是我需要做的但是,我在尝试理解某些要点以及如何应用它时遇到了一些麻烦,以便解决我的需求.我在数学方面也没那么多经验,所以当论文用复杂的公式解释所有这些东西时我会迷失方向.

这是我到目前为止所提出的:

1. 给定一个游戏状态(游戏中的用户手),确定哪些是可以进行的所有可能的合法游戏,然后我将创建一个节点列表(一个代表每个游戏)作为MCTSTree的根节点中的属性,每个节点的结果(得分值？)

2. 使用随机播放器模拟每个合法游戏的完整(直到结束)游戏玩法,并将结果记录在每个节点中,无论玩家是赢还是输,以获得完整的图片.

这里是"我认为"应该应用蒙特卡洛+ UCB的地方:

1. 使用UCB递归地选择更有前途的游戏(节点),并且在其叶子的情况下,从其gameState扩展具有所有可能游戏的节点.

2. 模拟所选节点的n个播出,直到达到一定的时间.

   • 在这个阶段我有一些疑问...说我尝试随机播放给出一个可能的播出列表...为了继续模拟,我该如何处理第一个结果？我应该让树长大吗？

3. 我如何反向传播结果？

然后,

• 记住,因为这是一个复杂的纸牌游戏,我有这么多可能的动作......它是否有足够好的性能在任何节点中拥有这么多的孩子？

• 如果每个模拟都基于游戏状态,并且每次玩家应用移动时游戏都会改变状态,那么我怎么知道树是否真的有用？

我真的很感激任何帮助.

非常感谢你!

Answer 1

MCTS就是以下内容:

我描述它与图像建议的有点不同,可能更适合实现.

1. 从根节点下降(游戏的当前状态),在每个步骤使用UCB,直到您决定未实例化的节点l.(选择)
2. 添加l到您的树.(扩大)
3. 来自l,玩随机游戏.(模拟)
4. l使用播出结果更新路径上从回到根节点的所有节点.
5. 重复,直到时间用完.

如果你的分支因子很大,正如你所提到的那样,你可能需要考虑其他策略来选择继承者,同时下降树,比如RAVE.