0

我在网上看到了一些 MCTS 实现以及它们是如何在游戏中使用的。根据当时的状态计算每个移动的最佳移动。如果您在人和计算机之间的游戏中有一系列动作，例如：

turn_h1,turn_c1,turn_h2,turn_c2,turn_h3,turn_c3,....turn_hn,turn_cn

turn_h(i)=human, turn_c(i)=computer and i 玩家的第 i 步（人/计算机）。

并且对于每台计算机的轮到 i，都有一个相应的状态，用于确定MCTS的第 i 个最佳移动。

问题：第（i-1）轮（bestmove）中构建的树是否应该用于第i轮（MCTS bestmove）？

我的意思是，是否应该将作为状态 (n-1) 中最佳移动结果的树用作确定第 i 个状态的最佳移动的输入？

换句话说，我可以重新使用之前回合/最佳移动计算中已经构建的树节点，这样我就不需要再次构建整个树了吗？

我在伪代码中创建了一系列转弯，只是为了弄清楚我使用第 (i-1) 个状态（树）来提供下一个 MCST bestmove 的含义。（当然在现实世界中，下面的逻辑将被实现为迭代/循环构造）：

#start game
initial_game_state.board= initialize_board()

#turn 1
#human play
new_game_state_1 = initial_game_state.board.make_move(move_1)

#computer play
move_1 = MCTS.determine_bestmove(new_game_state_1)
new_game_state_2 = game_state_1.board.make_move(move_1)

#turn 2
#human play
new_game_state_3 = new_game_state_2.board.make_move(move_2)
#computer play
move_3 = MCTS.determine_bestmove(new_game_state_3)
new_game_state_4 = new_game_state_4.board.makeMove(move_3)

#turn 3
# ....
4

1 回答 1

1

是的，你可以这样做。这通常被称为“树重用”（至少，我通常这么称呼它）。

您将通过从根节点导航到与您在“真实”游戏中实际到达的节点相对应的节点来开始您的 MCTS 调用（第一个调用除外，其中还没有“上一棵树”） .

请注意，在两人交替移动游戏中，这不仅涉及您的 MCTS 代理的移动，还包括对手的移动。由于 MCTS 的工作方式，如果对手通过选择 MCTS 没有预测到的移动来“惊讶”你的 MCTS 代理，这很可能会导致前一棵树的子树访问次数相对较少。在这种情况下，树的重用不会有太大的影响。但是如果对手没有让你吃惊，并且完全按照 MCTS 在之前搜索中预测的那样玩，你最终可能会得到一个相对较大的子树来初始化你的新搜索。

至于您是否“应该”这样做，就像您问题中的字面意思一样……您不必这样做。有许多 MCTS 实现不这样做。无论如何，我通常会推荐它。实施起来并不太难。它通常不会对性能有很大的提升（因为 MCTS 的演奏强度往往会随着“思考时间”的增加而呈亚线性增长），但它绝对也不应该受到伤害，并且可能会给演奏带来一点提升力量。

请注意，在非确定性游戏中，如果您实现 MCTS 的“开环”变体（没有明确的机会节点），您“重用”的子树部分将部分基于过时的信息。在此类游戏中，在开始新的搜索过程之前，最好将您之前搜索中收集的所有统计数据（即所有访问次数和累积分数乘以 0 到 1 之间的数字）打折。

重要的实现细节：重用前一棵树时，如果您的新根节点（曾经是前一棵树中间的一个节点）有一个指向其父节点的引用/指针，请确保将其设置为null. 如果您忘记了这一点，您之前所有搜索的所有搜索树将在整个游戏中完全保留在内存中，并且您可能会很快耗尽内存。

于 2019-08-16T20:00:57.470 回答