MiniAlphaGo黑白棋 蒙特卡洛搜索

做个笔记。

---

一、蒙特卡洛在黑白棋的应用

输入：棋盘𝑏𝑜𝑎𝑟𝑑、当前执子方𝑐𝑜𝑙𝑜𝑟、搜索时间𝑡𝑖𝑚𝑒_𝑙𝑖𝑚𝑖𝑡、模拟策略𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦

创建蒙特卡洛树的根节点𝑟𝑜𝑜𝑡，表示当前棋局𝑏𝑜𝑎𝑟𝑑

在搜索时间内，循环以下步骤生成蒙特卡洛树：

（1）选择 Selection——根据 𝑼𝑪𝑩值 ，搜索返回值最大的叶子结点 𝑳

• 第一次蒙特卡洛搜索时，必返回根节点𝑟𝑜𝑜𝑡。
• 之后的每次，会计算并返回𝑈𝐶𝐵1值最大的节点𝐿。

（2）扩展 Expansion——扩展节点𝑳的子结点𝑴

• 当前执子方落子合法的位置，都作为𝐿的子结点。
• 随机扩展一个子结点作为𝑀，
• 其余子结点由于𝑈𝐶𝐵1值无穷，下次优先选择。

（3）模拟 Simulation——模拟当前棋局走向，记录输赢及胜子数量

• 从结点𝑀开始，模拟双方落子，直到胜负。
• 模拟策略可以多样化。
  比如，随机策略，贪心策略

（4）回溯 back propagation——从节点𝑴开始回溯

• 回溯过程为了保持𝑈𝐶𝐵1公式求解，
  不同执子层以相反效果加上回溯值。
• 计回溯值的策略也可以多样化。
  如以胜负记：胜方记1，负方记0，平局记0.5
  或以胜子数记：
  胜方记胜子数，负方记负子数，平局记0

---

二、项目

我放在了：Reversi_miniAlphaGo/algo.py，algo.py就是本地可以运行的一个版本。
如果要做前端，可以使用Reversi_miniAlphaGo/ forflask_algo.py。

---

原理参考：
《人工智能导论：模型与算法——吴飞》
《机器学习-蒙特卡洛搜索树 智能黑白棋》
《 蒙特卡洛树搜索算法（UCT）: 一个程序猿进化的故事》

代码参考并改进自：
《深度解析黑白棋AI代码原理（蒙特卡洛搜索树MCTS+Roxanne策略）》