蒙特卡洛树搜索（MCTS）在井字棋中是预建树还是随局构建？

• 核心结论：随对局进程实时构建搜索树
  井字棋场景下的MCTS不会预构建全局完整搜索树，而是每回合以当前实际游戏状态为根节点，临时构建局部搜索树。原因在于井字棋每一步都会改变局面，预构建的树会包含大量不可能出现的分支（比如对手不会选择的走法），完全没必要；实时构建反而能聚焦当前局面的有效分支，效率更高。

• 每回合的具体执行流程
  假设当前轮到MCTS控制的一方落子：

  1. 初始化根节点：将当前棋盘的实际状态（比如已经有3枚棋子的局面）作为搜索树的根节点。
  2. 迭代执行MCTS四步流程：在设定的时间限制或迭代次数内，重复运行以下步骤：
     • Selection（选择）：从根节点出发，用UCT（Upper Confidence Bound for Trees）公式选择最优子节点，直到找到一个未完全扩展的节点（即仍有合法落子未被探索）。
     • Expansion（扩展）：在该未完全扩展的节点上，生成一个对应合法落子的新子节点（比如在空格子上模拟落子）。
     • Simulation（模拟）：从新生成的节点开始，模拟对局直到结束（可随机落子，也可加入简单策略如优先堵截或赢棋），记录最终结果（赢、输、平）。
     • Backpropagation（回溯）：将模拟结果反向更新到从根节点到新节点的所有路径节点上，更新它们的胜场数、访问次数等统计数据。
  3. 确定实际落子：迭代结束后，在根节点的所有子节点（对应所有合法落子选项）中，选择访问次数最多（或胜率最高，依实现而定）的节点对应的落子，作为实际对局的走法。
  4. 切换根节点：对手落子后，新的棋盘状态将成为下一轮MCTS的根节点，重复上述流程。

• 为何不预构建全局树？

  • 井字棋总状态数约5472种，看似不多，但预构建全局树会包含大量无效分支（对手不会选择的走法），浪费内存与计算资源。
  • 实时构建能针对性聚焦当前局面的可能分支，灵活应对对手的任意走法，计算效率更高。

• 井字棋场景的细节优化

  • 可缓存已计算过的局面节点，避免不同路径到达同一棋盘状态时重复计算，复用之前的统计数据。
  • 模拟阶段可加入简单启发式策略，比如优先选择能直接赢棋的落子，或优先堵截对手的赢棋路线，提升模拟结果的可信度。

内容的提问来源于stack exchange，提问作者Riccardo Caiulo