7

我最近对游戏中应用的蒙特卡罗树搜索产生了兴趣。

我读过几篇论文，但我使用 Chaslot, G 的博士论文“蒙特卡洛树搜索”，因为我发现它更容易理解蒙特卡洛树搜索的基础知识

我试图对其进行编码，并坚持某些问题。该算法试图为每一个模拟将一个节点扩展到游戏树中。这很快升级为内存问题。我已经快速阅读了这篇论文，但它似乎没有解释如果该技术达到一定的内存限制会做什么。

如果该技术达到一定的内存限制，您能否建议该技术应该做什么？

你可以在这里看到这篇论文： http ://www.unimaas.nl/games/files/phd/Chaslot_thesis.pdf

4

3 回答 3

4

One very effective approach is to grow the tree more slowly. That is, instead of expanding the tree every time you reach a leaf node, you expand it once it has at least k visits. This will significantly slow the growth of the tree, and often does not reduce performance. I was told by one of the authors of the Fuego Go program that he tried the approach, and it worked well in practice.

This idea was originally described in this paper:

Remi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Computers and games, pages 72–83. Springer, 2007.

It was also used in:

Max Roschke and Nathan Sturtevant. UCT Enhancements in Chinese Checkers Using an Endgame Database, IJCAI Workshop on Computer Games, 2013.

于 2016-02-27T05:49:27.340 回答
2

论文Memory Bounded Monte Carlo Tree Search评估了该问题的各种解决方案：

  • 停止：当你达到内存限制时停止算法
  • 发育迟缓：当你达到内存限制时，你停止生长树（但继续更新它）
  • 合奏：当您达到内存限制时，您保留结果并从空树重新开始搜索（最后融合结果）
  • 扁平化：当你达到内存限制时，你会摆脱除根及其直接子节点之外的所有节点，并从这个新的基础重新开始搜索
  • 垃圾收集：当您达到内存限制时，您将删除所有未访问过给定次数的节点
  • 回收：添加节点时，删除最长时间未访问的节点
于 2019-04-22T10:09:21.493 回答
1

您可以丢弃访问次数小于最近未访问的某个阈值的所有节点（之前的播放次数）。这是一个快速但不高效的解决方案。最好也实施渐进式扩大。

于 2013-04-19T17:14:59.710 回答