博弈树是一种用来表示博弈中所有可能状态和决策的图形结构。它由节点和边组成，节点代表博弈中的状态，而边代表玩家的行动选择。博弈树的根节点表示游戏的初始状态，随着玩家的决策，树向下分支，形成不同的游戏路径。

结构组成：

1. 根节点：表示博弈的初始状态。
2. 内部节点：表示博弈中的不同状态。
3. 边：表示从一个状态到另一个状态的可选行动。
4. 叶节点：表示博弈的最终结果或得分。

应用：

• 极大极小算法（Minimax）：用于两人零和博弈中寻找最优策略。玩家会选择使自己得分最大化并使对手得分最小化的策略。
• 剪枝技术：例如 alpha-beta 剪枝，可以减少需要评估的节点数量，提高效率。

例题

例题 1：简单的博弈树

假设有两个玩家 MAX 和 MIN两个聪明得博弈者 进行一个简单的游戏。其中数字表示MAX的得分，MAX先进行选择，MIN后选择。

博弈树示例：

                   0              MAX
                  / \
                 3   2            MIN
                / \ / \
              -3  5 2  1        
               

        首先MAX的最优解是走0->2，因为MAX选择2分，则下次MIN会选择MAX得分最少的1分，整体看来MAX总共得了3分

        而MAX选择走0->3,MIN肯定会选择MAX得分最少的-3分，那么整体下来MAX总共得了0分。

阿尔法-贝塔剪枝的工作原理

阿尔法-贝塔算法通过维护两个值（α 和 β）来限制不必要的搜索：

• α（Alpha）：当前已知的最大下限值，表示当前玩家（通常是MAX玩家）能获取的最佳得分。
• β（Beta）：当前已知的最小上限值，表示对手（通常是MIN玩家）能获取的最佳得分。

算法步骤：

1. 从根节点开始，递归地评估博弈树。
2. 对于每个节点：
   • 如果是MAX节点，更新α值，并检查是否可以剪枝（即如果当前节点的值大于或等于β值，则剪枝）。
   • 如果是MIN节点，更新β值，并检查是否可以剪枝（即如果当前节点的值小于或等于α值，则剪枝）。
3. 在遍历过程中，如果发现某个子树的值不可能影响最终决策，则直接跳过该子树的评估。

例子

考虑一个简单的博弈树，假设我们有以下节点和评分：

          A                       MAX
        /   \
       B     C                    MIX
      / \   / \
     3   5 6   9


优化得出
          A=6                       MAX（选最大）
        /     \
       B=3     C=6                  MIX（选最小）
      / \     / \
     3   5   6   9
I

• 在这个树中，A 是根节点，B 和 C 是子节点，底部的数字是叶节点的得分。
• 使用极大极小算法，MAX玩家的A 选择最大值（即选择 B 或 C 中的最大值）。
• 使用极大极小算法，MIN玩家的B、C节点选择子节点的最小值来削减MAX玩家的得分（3和5、6和9之间）
• 通过阿尔法-贝塔剪枝，我们可以在评估过程中减少不必要的节点。
• 可以得出A（α）=6中B（β）=3是小于α（最大下限）则剪掉，走C点。

优点

• 效率：通过剪枝，算法可以在较少的时间内找到最优解，尤其是在博弈树非常大的情况下。
• 减少计算量：不需要评估所有节点，节省了计算资源。