人工智能应用- 人机对战：04. 蒙特卡洛树搜索
蒙特卡洛树搜索（MCTS）是 AlphaGo 成功的核心技术之一。围棋中的最大挑战在于如何评估当前局势，而MCTS 通过模拟走棋到终局来进行评估。为了提高模拟走棋的效率，MCTS 并不会扩展所有可能的路径，而是通过随机采样的方式估计每种走棋方式的胜率，并优先扩展那些胜率较高的走法。
MCTS 的基本步骤包括：选择、扩展、模拟和回传。首先，从当前棋局出发，按照某种策略选择路径，直到遇到未扩展的节点。接着，生成新的子节点，并通过自我对弈模拟后续棋局的发展，直到终局决出胜负。最后，将胜负结果逐层回传，把胜负分值累加到路径的所有节点上。这一过程反复进行，最终确定胜率最高的走法作为当前的最佳选择。图展示了 MCTS 算法的基本过程：
蒙特卡洛树搜索（MCTS）算法
- 路径选择：以当前棋局作为根节点，自上而下依次选择节点，直到遇到第一个未扩展的子节点 A。在做路径选择时，一方面选择胜率较高的节点，同时兼顾访问较少的节点。
- 叶节点扩展：初始化子节点 A，设置其初始胜率和访问次数。
- 模拟走棋：从节点A 开始进行随机模拟走棋，直到终局决出胜负。该胜负值作为A 节点此次模拟获得的收益。
- 反馈走棋结果：将 A 节点的模拟结果逐层回传，更新路径上所有节点的胜率和访问次数。
重复上述过程后，树中每个节点累积的收益将代表该节点的己方胜率。当模拟完成后，根节点中收益最高的子节点所对应的走棋方式即为当前的最优落子选择。
MCTS 本质上是一种对走棋路径的随机采样方法，关键在于保留一棵可扩展的搜索树，并在随机采样时以这棵树为基础进行有序扩展，从而提高模拟走棋的效率。