2

I'm trying to implement the MCTS algorithm on a game. I can only use around 0.33 seconds per move. In this time I can generate one or two games per child from the start state, which contains around 500 child nodes. My simulations aren't random, but of course I can't make a right choice based on 1 or 2 simulations. Further in the game the tree becomes smaller and I can my choices are based on more simulations.

So my problem is in the first few moves. Is there a way to improve the MCTS algorithm so it can simulate more games or should I use another algorithm?

4

1 回答 1

4

是否有可能为状态提出一些启发式评估函数？我意识到 MCTS 的主要好处之一是理论上你不需要这个，但是：如果你无论如何都可以创建一个合理的评估函数，这将允许你在模拟达到终端游戏状态之前尽早停止模拟. 然后您可以备份对这种非终端游戏状态的评估，而不仅仅是输赢。如果您像这样提前停止模拟，您可能能够运行更多模拟（因为每个单独的模拟花费的时间更少）。

除此之外，您还需要尝试找到“概括”的方法。如果您运行一个模拟，您应该尝试查看是否还可以从该模拟中提取一些有用的信息，用于树中您没有经过的其他节点。本着这种精神，您可能要考虑的增强示例包括 AMAF、RAVE、Progressive History、N-Gram 选择技术。

您是否碰巧知道性能的瓶颈在哪里？您可以使用探查器对此进行调查。如果您的大部分处理时间都花在与游戏相关的功能上（移动生成、从一种状态前进到下一种状态等），那么您肯定会知道您可以进行的模拟数量会受到限制. 然后，您应该尝试实施增强功能，使每个单独的模拟尽可能地提供信息。例如，这可能意味着使用非常好的、计算量大的评估函数。如果游戏代码本身已经得到很好的优化和快速，那么将额外的计算时间转移到评估函数之类的东西对您的模拟计数将更加有害，并且可能会减少回报。

关于最后一个想法的更多信息，看看我在 General Video Game AI 中基于 MCTS 的代理上写的一些东西可能会很有趣，这也是一个计算量非常大的游戏的实时环境，这意味着模拟计数受到严格限制（但分支因子比您的情况看起来要小得多）。我在这方面的出版物的 pdf 文件也可以在线获得。

于 2017-11-22T10:32:10.260 回答