游戏树搜索与优化策略：Alpha-Beta剪枝及其实例分析
1.Alpha-Beta搜索
Alpha-Beta 搜索是一种用于对抗性游戏（比如象棋、围棋）的智能算法，目的是帮助计算机快速找到“最优走法”，同时避免不必要的计算。它的核心思想是：通过剪掉明显糟糕的分支，大幅减少需要计算的步数。
通俗理解：
假设你和朋友下棋，你在思考下一步时，会脑补各种可能的走法：
如果你走A，朋友可能会走A1、A2、A3...，然后你又要回应，最终可能赢或输。
如果你走B，朋友可能会走B1、B2...，依此类推。
Alpha-Beta 的作用就是帮你快速排除明显不靠谱的选项。比如：
当你分析走A时，发现朋友只要走A1就能轻松击败你，那么A这条路直接放弃，不用再分析A2、A3了。
接着分析走B，如果发现无论朋友怎么应对，你都能赢，那么直接选B，不用再分析剩下的选项了。
这就是“剪枝”——砍掉无用的分支，节省时间。
核心规则：
两个角色：
你（最大化玩家）：想选对自己最有利的走法（比如最高分数）。
对手（最小化玩家）：会选对你最不利的走法（比如最低分数）。
两个关键值：
Alpha：当前你能保证的“最差下限”。比如你已经找到一条路至少能得5分，那么Alpha=5。
Beta：当前对手能允许的“最差上限”。比如对手已经找到一条路最多让你得3分，那么Beta=3。
剪枝条件：
如果在分析某一步时，发现它的结果比对手能接受的最差值还差（比如你算出这一步最多得2分，但对手已经有办法限制你到3分），那么直接放弃这条路，不用再往下算了！
举个栗子🌰：
假设你在下棋，有3种走法（A、B、C）：
分析A：对手回应后，你最多得3分。
分析B：对手回应后，你至少能得5分。这时更新Alpha=5。
分析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遍历顺序与剪枝分析（假设从左到右遍历）：
根节点（MAX）
α = -∞, β = +∞
先处理左子节点 MIN₁
MIN₁（左）
继承父节点的α = -∞, β = +∞
处理第一个子节点 MAX₁（叶子值0和4）：
MAX₁返回最大值4
MIN₁当前β = min(+∞, 4) = 4
处理第二个子节点 MAX₂（叶子值5和1）：
MAX₂返回最大值5
MIN₁最终值 = min(4, 5) = 4
根节点更新α = max(-∞, 4) = 4
根节点（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₆）无需评估
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 argparse
MIN_EVAL = -1000000
MAX_EVAL = 1000000
def 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 Game
game = Game()
elif args.g == 'con3':
from con import Game
game = Game(3)
elif args.g == 'con4':
from con import Game
game = 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_PLAYING
player = 2
m = 0
while m < game.MAX_MOVE and game_status == game.STILL_PLAYING:
m += 1
player = 3-player
if 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_EVAL
if game.game_won( 3-player ): # loss
return -1000 + m # better to win faster (or lose slower)
if game.game_drawn( 3-player):
return 0
if depth == 0:
return game.board_eval( player )
this_move = -1
for c in game.move_range(): #range( 1, 10 ):
if game.is_legal_move( player, c ):
this_move = c
game.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_move
best_eval = this_eval
if best_eval > alpha:
alpha = best_eval
if alpha >= beta: # cutoff
return( alpha )
if this_move < 0: # no legal moves
return( 0 ) # DRAW
else:
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的三种对称等效开局：
角（Corner）
边（Edge）
中心（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算法与回传值
步骤：
深度2（叶子节点）：直接使用评估函数计算值。
深度1（MIN层）：选择子节点中的最小值。
深度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按最优顺序回应）：
MIN层首先评估O在边（Eval=3），此时父节点（MAX层）的α=3。
后续评估O在对角角（Eval=5），由于5 > α=3，更新α=5。
最后评估O在中心（Eval=4），无需剪枝。
若子节点顺序为[中心→边→对角角]，当O在中心返回4后，后续分支可能因α=4 ≥ β=3触发剪枝。
剪枝节点：在非最优顺序下，部分分支（如O在中心后的其他对称位置）可能被跳过。
6. 利用对手失误的最佳开局
即使Minimax认为所有开局平局，但若对手犯错，角开局更具优势：
角开局的潜在威胁：X在角后，可形成两条潜在连线（如对角线和边）。
对手失误示例：若O未占据中心，X可通过下一步占据中心形成双威胁，迫使O无法防守。
其他开局（如边或中心）威胁较少，对手更易应对。
总结
最佳开局：角（对称合并后唯一最优选择）。
关键策略：通过评估函数量化威胁，利用Minimax和Alpha-Beta剪枝优化搜索。
实战意义：理解对称性与剪枝条件可大幅减少计算量，同时针对对手失误设计陷阱。
源码：
import numpy as np
class Game:
def __init__(self):
self.ILLEGAL_MOVE = 0
self.INITIAL_STATE = 1
self.STILL_PLAYING = 2
self.WIN = 3
self.LOSS = 4
self.DRAW = 5
self.EMPTY = 0
self.ILLEGAL_MOVE = 0
self.STILL_PLAYING = 1
self.WIN = 2
self.LOSS = 3
self.DRAW = 4
self.MAX_MOVE = 9
self.MAX_DEPTH = 9
self.board = self.EMPTY*np.ones(10,dtype=np.int32)
# Print the board
def print_board( self ):
sb = '.XO'
bd = self.board
print(' +-------+')
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 full
def full_board( self ):
b = 1
while b <= 9 and self.board[b] != self.EMPTY:
b += 1
return( b == 10 )
# Return range of feasible moves
def move_range( self ):
return range(1,10)
# Return True if the specified move is legal
def 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 status
def make_move( self, player, this_move ):
if self.board[this_move] != self.EMPTY:
print('Illegal Move')
return self.ILLEGAL_MOVE
else:
self.board[this_move] = player
if self.game_won( player ):
return self.WIN
elif self.full_board():
return self.DRAW
else:
return self.STILL_PLAYING
# Undo the specified move
def 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.board
return( ( 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一道题
完整计算过程（无剪枝）
MIN节点的值：
MIN1: min(2, 2) = 2
MIN2: min(1, 2) = 1
MIN3: min(0, 2) = 0
MIN4: min(-1, 0) = -1
CHANCE节点的期望值：
期望值=0.25×2+0.25×1+0.25×0+0.25×(−1)=0.5根节点（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