go - 国际象棋:静止搜索主导运行时

Question

我已经为我的国际象棋引擎实现了带有静态搜索的 alpha-beta 搜索。然而，在大多数情况下，静态搜索占用了总执行时间的 80-90%，正如我的分析器所显示的那样。我的修剪有问题吗？

我已经包含了 alpha-beta 例程和静止例程。

我的静态搜索直接基于this pseudocode .

// Perform the alpha-beta search.
func ab(b *dragontoothmg.Board, alpha int16, beta int16, depth int8, halt chan bool, stop *bool) (int16, dragontoothmg.Move) {
    nodeCount++

    if *stop {
        return alpha, 0
    }

    found, tableMove, tableEval, tableDepth, tableNodeType := transtable.Get(b)
    if found && tableDepth >= depth {
        if tableNodeType == transtable.Exact {
            return tableEval, tableMove
        } else if tableNodeType == transtable.LowerBound {
            alpha = max(alpha, tableEval)
        } else { // upperbound
            beta = min(beta, tableEval)
        }
        if alpha >= beta {
            return tableEval, tableMove
        }
    }
    if depth == 0 {
        //return eval.Evaluate(b), 0
        return quiesce(b, alpha, beta, stop), 0
    }

    alpha0 := alpha
    bestVal := int16(negInf) 
    moves := b.GenerateLegalMoves()
    var bestMove dragontoothmg.Move
    if len(moves) > 0 {
        bestMove = moves[0] // randomly pick some move
    }
    for _, move := range moves {
        unapply := b.Apply(move)
        var score int16
        score, _ = ab(b, -beta, -alpha, depth-1, halt, stop)
        score = -score
        unapply()
        if score > bestVal {
            bestMove = move
            bestVal = score
        }
        alpha = max(alpha, score)
        if alpha >= beta {
            break
        }
    }

    if *stop {
        return bestVal, bestMove
    }

    var nodeType uint8
    if bestVal <= alpha0 {
        nodeType = transtable.UpperBound
    } else if bestVal >= beta {
        nodeType = transtable.LowerBound
    } else {
        nodeType = transtable.Exact
    }
    transtable.Put(b, bestMove, bestVal, depth, nodeType)
    return bestVal, bestMove
}

func quiesce(b *dragontoothmg.Board, alpha int16, beta int16, stop *bool) int16 {
    nodeCount++
    if *stop {
        return alpha
    }
    var standPat int16
    found, _, evalresult, _, ntype := transtable.Get(b)
    if found && ntype == transtable.Exact {
        standPat = evalresult
    } else {
        standPat = eval.Evaluate(b)
        transtable.Put(b, 0, standPat, 0, transtable.Exact)
    }
    if standPat >= beta {
        return beta
    }
    if alpha < standPat {
        alpha = standPat
    }
    moves := b.GenerateLegalMoves()
    if len(moves) == 0 { // TODO(dylhunn): What about stalemate?
        return negInf
    }
    for _, move := range moves {
        if !isCapture(move, b) {
            continue
        }
        unapply := b.Apply(move)
        score := -quiesce(b, -beta, -alpha, stop)
        unapply()
        if score >= beta {
            return beta
        }
        if score > alpha {
            alpha = score
        }
    }
    return alpha
}

func isCapture(m dragontoothmg.Move, b *dragontoothmg.Board) bool {
    toBitboard := (uint64(1) << m.To())
    return (toBitboard&b.White.All != 0) || (toBitboard&b.Black.All != 0)
}

Answer 1

如果我正确阅读了您的代码，则您正在搜索所有捕获。为了节省工作，您可以做的是修剪无望的捕获 Action 。事实证明， Action 非常糟糕以至于可以安全跳过它们是很常见的，因此该技术非常安全。

例如，看看这个位置:

FEN:rnbqkbnr/pppppppp/8/8/8/8/1PP1PPP1/RNBQKBNR w KQkq - 0 1

一共有三个捕获:

• Rxa7
• Qxd7+
• Rxh7

让我们假设引擎首先尝试对女王进行捕获 Action 。黑方有四种回吃的方法，但这些棋步中的任何一种都可能导致截断。

例如，黑色下 Bxd7。现在白方在结果位置有两个捕获，Rxa7 或 Rxh7。

在这里，大多数引擎会认识到白色已经在 Material 上有所下降(与 beta 相比)，即使捕获一个 pawn 也无济于事。因此，这两个新车捕获不太可能导致截止。

在这里，您当前的搜索仍会继续搜索这些着法。检测此类情况并跳过这些 Action 将节省大量工作。

还有进一步的优化。例如，带有 static exchange evaluation 的强大引擎会立即看到 Qxd7 将赢得一兵，但会失去皇后。由于这是一个糟糕的交易，引擎可以立即跳过此移动。其他两个新车捕获也是如此。

不过，与往常一样，需要权衡取舍。如果你过于激进地修剪，你最终也会修剪好的 Action 。一般来说，我会建议花更多的时间在正常搜索上，而不是在静止搜索上，所以激进的剪枝应该没问题。