含Pass操作的Alpha Beta剪枝算法实现方案问询

问题背景 #

当玩家无合法移动时必须Pass回合给对手；若双方均无合法移动，则游戏结束并返回当前局面的收益值。需要基于基础Alpha Beta剪枝算法实现这一规则。

基础Alpha Beta剪枝算法代码 #

function alphabeta(node, depth, α, β, Player)         
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Beta cut-off
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Alpha cut-off
        return β

// Initial call
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

核心疑问 #

不清楚当玩家因无合法移动需Pass时，递归应保持当前玩家还是切换玩家，以及对应的max/min逻辑如何选择。以下是猜测的实现代码：

function alphabeta(node, depth, α, β, Player)         
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if Player = MaxPlayer
        for each child of node
            α := max(α, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Beta cut-off
        if no children // a pass, player plays again.
            α := max(α, alphabeta(node, depth-1, α, β, Player))     
            if β ≤ α
                return α

        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Alpha cut-off
        if no children // a pass, player plays again.
            α := min(α, alphabeta(node, depth-1, α, β, Player))     
            if β ≤ α
                return β // Beta cut-off

        return β

// Initial call
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

正确实现思路与代码 #

首先明确规则对应的逻辑：

1. 若当前玩家有合法移动：正常遍历所有子节点，递归时切换玩家，保持原max/min逻辑
2. 若当前玩家无合法移动：
   • 先检查对手是否也无合法移动：若是，当前节点为终端节点，返回局面估值
   • 若对手有合法移动：当前玩家Pass，递归进入同一局面，但切换到对手回合，使用对手对应的max/min逻辑

修正后的代码如下：

function alphabeta(node, depth, α, β, Player)         
    // 终止条件：搜索深度耗尽，或双方均无合法移动（终端节点）
    if depth = 0 or (no valid moves for Player AND no valid moves for not(Player))
        return the heuristic value of node
    
    if Player = MaxPlayer
        // 先尝试所有合法移动
        has_valid_moves := false
        for each child of node
            has_valid_moves := true
            α := max(α, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Beta cut-off
        
        // 无合法移动，Pass给对手
        if not has_valid_moves
            // 递归切换到对手回合，使用MinPlayer的逻辑
            α := max(α, alphabeta(node, depth-1, α, β, not(Player)))
        
        return α
    else // MinPlayer
        has_valid_moves := false
        for each child of node
            has_valid_moves := true
            β := min(β, alphabeta(child, depth-1, α, β, not(Player)))     
            if β ≤ α
                break // Alpha cut-off
        
        // 无合法移动，Pass给对手
        if not has_valid_moves
            // 递归切换到对手回合，使用MaxPlayer的逻辑
            β := min(β, alphabeta(node, depth-1, α, β, not(Player)))
        
        return β

// Initial call
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

关键说明 #

• 终止条件需修改为双方均无合法移动才判定为终端节点，避免单玩家无移动时提前终止
• 当当前玩家无合法移动时，必须切换到对手回合递归，而非保持当前玩家（这是原猜测代码的核心问题）
• Pass操作不改变当前局面，仅切换玩家，因此递归时传入的node仍是当前节点，但Player参数切换为对手
• 保持原max/min逻辑：MaxPlayer始终取最大值，MinPlayer始终取最小值，即使是Pass后的递归调用

内容的提问来源于stack exchange，提问作者Carlos Briceño