游戏树搜索与优化策略：Alpha-Beta剪枝及其实例分析

1.Alpha-Beta搜索

Alpha-Beta 搜索是一种用于对抗性游戏（比如象棋、围棋）的智能算法，目的是帮助计算机快速找到“最优走法”，同时避免不必要的计算。它的核心思想是：通过剪掉明显糟糕的分支，大幅减少需要计算的步数。

通俗理解：

假设你和朋友下棋，你在思考下一步时，会脑补各种可能的走法：

1. 如果你走A，朋友可能会走A1、A2、A3...，然后你又要回应，最终可能赢或输。

2. 如果你走B，朋友可能会走B1、B2...，依此类推。

Alpha-Beta 的作用就是帮你快速排除明显不靠谱的选项。比如：

• 当你分析走A时，发现朋友只要走A1就能轻松击败你，那么A这条路直接放弃，不用再分析A2、A3了。

• 接着分析走B，如果发现无论朋友怎么应对，你都能赢，那么直接选B，不用再分析剩下的选项了。

这就是“剪枝”——砍掉无用的分支，节省时间。

---

核心规则：

1. 两个角色：

   • 你（最大化玩家）：想选对自己最有利的走法（比如最高分数）。

   • 对手（最小化玩家）：会选对你最不利的走法（比如最低分数）。

2. 两个关键值：

   • Alpha：当前你能保证的“最差下限”。比如你已经找到一条路至少能得5分，那么Alpha=5。

   • Beta：当前对手能允许的“最差上限”。比如对手已经找到一条路最多让你得3分，那么Beta=3。

3. 剪枝条件：

   • 如果在分析某一步时，发现它的结果比对手能接受的最差值还差（比如你算出这一步最多得2分，但对手已经有办法限制你到3分），那么直接放弃这条路，不用再往下算了！

---

举个栗子🌰：

假设你在下棋，有3种走法（A、B、C）：

1. 分析A：对手回应后，你最多得3分。

2. 分析B：对手回应后，你至少能得5分。这时更新Alpha=5。

3. 分析C：如果发现对手某一步能让你得分≤4分（而你的Alpha已经是5），那么直接放弃C的分支，因为对手绝不会让你得5分以上。

最终，你会选择B，因为它保证了至少5分，而其他分支要么分更低，要么被剪掉了。

---

总结：

• Alpha-Beta 是“聪明穷举”：不盲目计算所有可能，而是边算边排除垃圾选项。

• 核心是剪枝：通过Alpha和Beta的边界值，提前终止无用的计算。

• 效果：让AI在复杂游戏中也能快速找到最优解！

就像考试时做选择题：先排除明显错误的选项，再仔细分析剩下的，省时又高效！

先给大家po一道例题

 我们为了辨识，将树结构变成下述标记：

         MAX（根节点）  
      /                           \  
   MIN₁（左）               MIN₂（右）  
  /           \               /          |        \          \  
MAX₁   MAX₂     MAX₃  MAX₄  MAX₅  MAX₆  
0  4        5 1         2 5      1 3       4 6      7 3  

遍历顺序与剪枝分析（假设从左到右遍历）：

1. 根节点（MAX）

   • α = -∞, β = +∞

   • 先处理左子节点 MIN₁

2. MIN₁（左）

   • 继承父节点的α = -∞, β = +∞

   • 处理第一个子节点 MAX₁（叶子值0和4）：

     • MAX₁返回最大值4

     • MIN₁当前β = min(+∞, 4) = 4

   • 处理第二个子节点 MAX₂（叶子值5和1）：

     • MAX₂返回最大值5

     • MIN₁最终值 = min(4, 5) = 4

   • 根节点更新α = max(-∞, 4) = 4

3. 根节点（MAX）继续处理右子节点 MIN₂（右）

   • 当前α = 4, β = +∞

   • MIN₂的α = 4, β = +∞

   • 处理第一个子节点 MAX₃（叶子值2和5）：

     • MAX₃返回5

     • MIN₂当前β = min(+∞, 5) = 5

   • 处理第二个子节点 MAX₄（叶子值1和3）：

     • MAX₄返回3

     • MIN₂更新β = min(5, 3) = 3

     • 此时父节点的α=4 ≥ β=3，触发剪枝！

     • 后续子节点（MAX₅、MAX₆）无需评估

4. MIN₂最终值 = 3

   • 根节点比较左分支值4和右分支值3，选择最大值4

剪枝标注：

• MIN₂的MAX₅（叶子4,6）和MAX₆（叶子7,3）被剪枝，因为父节点MIN₂的β=3已小于根节点的α=4。

最终结果

• 根节点值 = 4（来自左分支MIN₁）

• 剪枝节点：

      MAX (α=4, β=+∞)  /                 \  MIN₁(4)               MIN₂(3)  
/       \          /    |    \    \  
MAX₁(4) MAX₂(5)  MAX₃(5) MAX₄(3) [剪枝] [剪枝]
0⭕4⭕ 5⭕1⭕  2⭕5⭕ 1⭕3⭕ 4❌6❌ 7❌3❌

- **⭕**：被评估的叶子节点  
- **❌**：因剪枝未评估的节点  ---### 关键步骤说明  
1. **左分支（MIN₁）**：  - MAX₁和MAX₂均被完整遍历，MIN₁返回4。  
2. **右分支（MIN₂）**：  - 当MAX₄返回3后，MIN₂的β=3 < 根节点α=4，触发剪枝。  - 剪枝节省了对MAX₅（4,6）和MAX₆（7,3）的遍历。  
3. **剪枝条件**：  - 对于MIN节点，若子节点返回值 ≤ 父节点的α，则后续分支无需评估。  - 此处MIN₂的β=3 < α=4，直接剪枝。  **结论**：Alpha-Beta剪枝在此树中成功跳过了4个叶子节点的计算。

源码：

import numpy as np
import argparseMIN_EVAL = -1000000
MAX_EVAL =  1000000def main():parser = argparse.ArgumentParser()parser.add_argument('--g',type=str,default='ttt',help= 'ttt, con3 or con4')parser.add_argument('--h',type=str,default='1',help= 'human turn (1 or 2)')args = parser.parse_args()if args.g == 'ttt':from ttt import Gamegame = Game()elif args.g == 'con3':from con import Gamegame = Game(3)elif args.g == 'con4':from con import Gamegame = Game(4)else:print('Unknown Game:',args.g)exit(1)if args.h == '2':is_human = (False,False,True)else:is_human = (False,True,False)move = np.zeros(game.MAX_MOVE+1,dtype=np.int32)best_move = np.zeros(game.MAX_MOVE+1,dtype=np.int32)#is_human = (False,True,False)game_status = game.STILL_PLAYINGplayer = 2m = 0while m < game.MAX_MOVE and game_status == game.STILL_PLAYING:m += 1player = 3-playerif is_human[player]:game.print_board()move[m] = input('Enter move: ')while not game.is_legal_move( player, move[m] ):move[m] = input('Enter move: ')else:alphabeta(player,m,game,MIN_EVAL,MAX_EVAL,best_move,game.MAX_DEPTH)move[m] = best_move[m]game_status = game.make_move( player, move[m] )game.print_board()if game_status == game.WIN:print('Win for player',player)elif game_status == game.LOSS:print('Loss for player',player)elif game_status == game.DRAW:print('Draw')#**********************************************************
#   Negamax formulation of alpha-beta search
#
def alphabeta( player, m, game, alpha, beta, best_move, depth ):best_eval = MIN_EVALif game.game_won( 3-player ):     # lossreturn -1000 + m  # better to win faster (or lose slower)if game.game_drawn( 3-player):return 0if depth == 0:return game.board_eval( player )this_move = -1for c in game.move_range(): #range( 1, 10 ):if game.is_legal_move( player, c ):this_move = cgame.make_move( player, this_move )this_eval = -alphabeta(3-player,m+1,game,-beta,-alpha,best_move,depth-1)game.undo_move( player, this_move )if this_eval > best_eval:best_move[m] = this_movebest_eval = this_evalif best_eval > alpha:alpha = best_evalif alpha >= beta:   # cutoffreturn( alpha )if this_move < 0:   # no legal movesreturn( 0 )     # DRAWelse:return( alpha )if __name__ == '__main__':main()

2.井字棋（Tic-Tac-Toe）

 

1. 可能的游戏总数

井字棋的合法游戏总数约为 255,168 种。虽然理论上存在 9!=362,8809!=362,880 种落子顺序，但以下因素大幅减少了实际数量：

• 提前终止：当一方连成三子时游戏结束。

• 对称性：许多路径通过旋转或镜像视为等效。

• 无效路径：某些落子顺序因违反规则（如重复落子）被排除。

---

2. 对称性简化后的深度2游戏树

从空棋盘开始，深度2的树结构如上（合并对称情况）：

深度0（根节点）：空棋盘
深度1（MAX层）：X的三种对称等效开局：

1. 角（Corner）

2. 边（Edge）

3. 中心（Center）

深度2（MIN层）：O的回应（合并对称位置）：

• 若X在角：

  • O可选择：中心、边、对角角（对称合并后仅需计算一次）。

• 若X在边：

  • O可选择：中心、相邻角、对边。

• 若X在中心：

  • O必须选择角（对称合并后仅需计算一次）。

---

3. 评估函数与深度2节点的评估值

评估函数定义为：

其中：

• X2(s)：棋盘中有两条X且无O的行/列/对角线数量。

• X1(s)：棋盘中有一条X且无O的行/列/对角线数量。

• O2(s) 和 O1(s)) 同理计算O的威胁。

示例计算（X在角，O在中心）：

• X2=1（对角线和右侧边各有一条潜在连线，但O在中心阻断一条，实际有效为1）。

• X1=2（左侧边和上边各一条）。

• O2=0，O1=1（中心O所在行/列/对角线）。

• Eval = 3×1 + 2 − (3×0 + 1) = 4。

其他深度2节点的评估值类似计算，最终结果为：

• X在角 + O在中心 → Eval=4

• X在角 + O在边 → Eval=3

• X在中心 + O在角 → Eval=2

  ---

  4. Minimax算法与回传值

步骤：

1. 深度2（叶子节点）：直接使用评估函数计算值。

2. 深度1（MIN层）：选择子节点中的最小值。

3. 深度0（MAX层）：选择子节点中的最大值。

示例（以X在角为例）：

• O在中心 → Eval=4

• O在边 → Eval=3

• O在对角角 → Eval=5

• MIN层选择最小值3（O最优回应为边）。

• 其他开局同理，最终根节点选择最大回传值（如X在角时值为3，X在中心时值为2）。

最佳开局：选择角，因其回传值最高（3）。

---

5. Alpha-Beta剪枝

剪枝条件：

• 在MIN层，若某个子节点的值 ≤ 当前α，则剪枝后续分支。

• 在MAX层，若某个子节点的值 ≥ 当前β，则剪枝后续分支。

示例（X在角，O按最优顺序回应）：

1. MIN层首先评估O在边（Eval=3），此时父节点（MAX层）的α=3。

2. 后续评估O在对角角（Eval=5），由于5 > α=3，更新α=5。

3. 最后评估O在中心（Eval=4），无需剪枝。

4. 若子节点顺序为[中心→边→对角角]，当O在中心返回4后，后续分支可能因α=4 ≥ β=3触发剪枝。

剪枝节点：在非最优顺序下，部分分支（如O在中心后的其他对称位置）可能被跳过。

---

6. 利用对手失误的最佳开局

即使Minimax认为所有开局平局，但若对手犯错，角开局更具优势：

• 角开局的潜在威胁：X在角后，可形成两条潜在连线（如对角线和边）。

• 对手失误示例：若O未占据中心，X可通过下一步占据中心形成双威胁，迫使O无法防守。

• 其他开局（如边或中心）威胁较少，对手更易应对。

---

总结

• 最佳开局：角（对称合并后唯一最优选择）。

• 关键策略：通过评估函数量化威胁，利用Minimax和Alpha-Beta剪枝优化搜索。

• 实战意义：理解对称性与剪枝条件可大幅减少计算量，同时针对对手失误设计陷阱。

 源码：

import numpy as npclass Game:def __init__(self):self.ILLEGAL_MOVE  =  0self.INITIAL_STATE =  1self.STILL_PLAYING =  2self.WIN           =  3self.LOSS          =  4self.DRAW          =  5self.EMPTY         =  0self.ILLEGAL_MOVE  =  0self.STILL_PLAYING =  1self.WIN           =  2self.LOSS          =  3self.DRAW          =  4self.MAX_MOVE      =  9self.MAX_DEPTH     =  9self.board = self.EMPTY*np.ones(10,dtype=np.int32)#   Print the boarddef print_board( self ):sb = '.XO'bd = self.boardprint(' +-------+')print(' |',sb[bd[1]],sb[bd[2]],sb[bd[3]],'|')print(' |',sb[bd[4]],sb[bd[5]],sb[bd[6]],'|')print(' |',sb[bd[7]],sb[bd[8]],sb[bd[9]],'|')print(' +-------+')#   Return True if the board is fulldef full_board( self ):b = 1while b <= 9 and self.board[b] != self.EMPTY:b += 1return( b == 10 )#   Return range of feasible movesdef move_range( self ):return range(1,10)#   Return True if the specified move is legaldef is_legal_move( self, player, r ):return( r >=1 and r <= 9 and self.board[r] == self.EMPTY )#   Make specified move on the board and return game statusdef make_move( self, player, this_move ):if self.board[this_move] != self.EMPTY:print('Illegal Move')return self.ILLEGAL_MOVEelse:self.board[this_move] = playerif self.game_won( player ):return self.WINelif self.full_board():return self.DRAWelse:return self.STILL_PLAYING#   Undo the specified movedef undo_move( self, player, this_move ):self.board[this_move] = self.EMPTY#   Return True if game won by player p on board bd[]def game_won( self, p ):bd = self.boardreturn(  ( bd[1] == p and bd[2] == p and bd[3] == p )or( bd[4] == p and bd[5] == p and bd[6] == p )or( bd[7] == p and bd[8] == p and bd[9] == p )or( bd[1] == p and bd[4] == p and bd[7] == p )or( bd[2] == p and bd[5] == p and bd[8] == p )or( bd[3] == p and bd[6] == p and bd[9] == p )or( bd[1] == p and bd[5] == p and bd[9] == p )or( bd[3] == p and bd[5] == p and bd[7] == p ))def game_drawn( self, p ):return self.full_board()

3.在具有机会节点的游戏中进行修剪 （Pruning in Games with Chance Nodes）

先给大家po一道题

 

完整计算过程（无剪枝）

1. MIN节点的值：

   • MIN1: min(2, 2) = 2

   • MIN2: min(1, 2) = 1

   • MIN3: min(0, 2) = 0

   • MIN4: min(-1, 0) = -1

2. CHANCE节点的期望值：

   期望值=0.25×2+0.25×1+0.25×0+0.25×(−1)=0.5

3. 根节点（MAX）的最终值：0.5。

 前六个叶子已知（2, 2, 1, 2, 0, 2）是否需要评估第七、八叶子？

• 已知值：前三组（MIN1-MIN3）的值为2, 1, 0。

• CHANCE节点当前期望值：

  当前期望=0.25×2+0.25×1+0.25×0+0.25×x(x为MIN4的值)

• MIN4的可能值：若第七叶子为-1，第八叶子为0 → MIN4 = -1。

• 最终期望值：0.5（与是否评估第七、八叶子无关，因为MIN4的值已由-1确定）。
  结论：不需要评估第七、八叶子，因为即使不评估，MIN4的最小值已由第七叶子-1确定。

---

 前七个叶子已知（2, 2, 1, 2, 0, 2, -1）是否需要评估第八叶子？

• 已知MIN4的第七叶子为-1，无论第八叶子0是否评估，MIN4的值已确定为-1。
  结论：不需要评估第八叶子。

叶子值范围限定为[-2, 2]时的剪枝优化

• 前两个叶子值为0.5：此描述与当前树结构不符，可能用户指其他上下文。假设问题为：已知所有叶子值范围在[-2, 2]，且已评估部分叶子。

• 左CHANCE节点范围：若指MIN1-MIN4的某个子分支，需具体说明。假设评估前两个分支（MIN1和MIN2）：

  • MIN1 = 2，MIN2 = 1 → 期望值下限为 0.25×2+0.25×1+0.25×(−2)+0.25×(−2)=−0.25