博弈树搜索技术（Minimax算法，α-β算法，Monte Carlo树搜索）

1 概述

博弈树搜索技术，涉及到 2 个智能体之间的对抗或竞争博弈。此处的博弈，专指有完整信息的、确定性的、轮流行动的、双人的零和游戏，例如国际象棋、围棋等。

博弈论是经济学的一个分支。一般而言，包含多智能体的系统被称为博弈系统，其中的每个智能体都会明显地受到其它智能体的影响，不论这些智能体之间是合作关系，还是竞争关系。此外，包含非常多智能体的系统被称为经济系统，而不是博弈系统。

• 在双人游戏中，对弈的双方都力图使自身的利益最大化。每一次出招时，先全面分析对方“所有可能”的行棋，然后选择自身利益最大化的招数。为了定量地反映出这种关系，规定先出招的一方为 MAX，后出招的一方为 MIN方，并从 MAX 方的视角来定义胜负平的得分——例如，对于 MAX 方而言，胜利分值为 +1，失败分值为-1，平局分值为 0；对于 MIN 方而言，胜利分值为-1，失败分值为 1，平局分值为 0；
• S0：初始状态；
• Player(s)：在状态 s 下，返回出招者——MAX 方或 MIN 方；
• Actions(s)：在状态 s 下，返回合法的动作集合；
• Result(s, a)：在状态 s 下，执行动作 a，将使状态发生转移；
• Terminal-Test(s)：返回游戏的状态——游戏是否结束；
• Utility(s, p)：在终局状态下，返回 MAX 或 MIN 的效用值 (即胜负平的收益值)。

其中，初始状态 S0、Actions 函数、Result 函数定义了一棵博弈树 (Game Tree) 或对抗搜索树 (Adversarial Search Tree)。在博弈树中，节点是状态，边表示动作或落子。如图1-1所示，展示了一棵TicTacToe 博弈树的片段。可以看出，在初始状态下，MAX 先下，MIN 后下，双方轮流出招，直至棋局结束。在终局时，所有终局状态都被赋予了效用值——从MAX 方的视角，定义了效用值——值越高，对 MAX 方越有利。

2 Minmax 算法

在一般的搜索问题中，搜索的目标是找到一条从起始节点到目标节点的最优路径。搜索完毕，智能体只需沿着最优路径一直走下去，最终必然会到达目标节点。
对于类似 Ticktacktoe 这样的双人棋类游戏，可以执行完全的搜索。然而对于大多数棋类游戏而言，执行完全的搜索几乎是不可能的。节点搜索随着深度的搜索呈指数级增长，对于算法而言这是一个大灾难！还有一个重要的原因，即博弈树搜索不是一个单纯的目标搜索问题，必须要考虑对手的策略，因而所谓的最优解并非是最优解，而是考虑双方策略时妥协的结果。这种双方都将选择最有利己方的动作来执行所得到的最优解，又称为“对抗最优解”或“博弈最优解”。
Minimax算法的伪代码如下：

def Minimax(node,depth,player):if depth == 0 or node is terminal node:return the heuristic value of nodeif player == True: # TRUE 表示黑方现行bestvalue = -∞for each child of node：v = Minimax(child,depth-1,False)bestvalue = max(bestvalue,v)return bestvalueelse :bestValue = +∞for each child of node：v = Minimax(child,depth-1,True)bestvalue = min(bestvalue,v)return bestvalue

简单理解通过递归的方式来遍历整棵树，递归函数要注意函数出口的判断，如当深度为0或者对弈结束时(区分胜负平)返回当前节点的开发节点的启发值。由于是递归算法，实现的时候注意对上一个状态的克隆，递归时树会发生变化。

如图：

这是一棵假象的简单博弈树，在该图中，根节点 MAX 的可能落子有 3 种选择：a1、a2 和 a3。在此例中，博弈树的搜索目标是确定 1 个最优落子。它使用了简单的深度递归搜索技术来确定每个节点的值：它从根节点开始，一直前进到叶子节点，然后在递归回溯时，将叶子节点的效用值往上回传——对于 MAX 方，计算最大值，对于 MIN 方，计算最小值。在图2-2中，算法从节点 A 开始，一路深度递归到最左边的叶子节点，随后将值 3 回传给节点 B，然后又深度递归到第2 个叶子节点，值 12 被回传并与值 3 比较，不占优势，B 节点的值维持 3 不变，接着又深度递归到第 3 个叶子节点，值 8 被回传并与值 3 比较，也不占优势，B节点的值仍然维持 3 不变。对于其余节点的分析，可依此类推。

3 α-β算法

4 Monte Carlo树搜索

4.1 概述

4.2 基本思想

4.3 理论基础

4.3.1 Monte Carlo 方法

4.3.2 多臂老虎机模型

4.4 基本算法

5 算法实现

5.1 准备工作

5.2 核心代码

5.3 运行效果图

6 总结

Date

• created on Tue 2020/9/22

• last updated on