从 alphabeta 框架中收集和检索主要变体

Question

我正在尝试在 python 中编写一个国际象棋引擎，我可以找到给定位置的最佳着法，但我正在努力收集该位置的主要变化，以下是我尝试过的到目前为止：

def alphabeta(board, alpha, beta, depth, pvtable):

    if depth == 0:
        return evaluate.eval(board)

    for move in board.legal_moves:
        board.push(move)
        score = -alphabeta(board, -beta, -alpha, depth - 1, pvtable)
        board.pop()
        if score >= beta:
            return beta
        if score > alpha:
            alpha = score
            pvtable[depth-1] = str(move)
    return alpha

我正在使用 pvtable[depth - 1] = str(move) 来追加移动，但最后我发现 pvtable 包含随机的不一致移动，例如 ['g1h3', 'g8h6', 'h3g5', 'd8g5'] 作为起始位置。

我知道有人问过类似的问题，但我仍然不知道如何解决这个问题。

Answer 1

我认为当搜索再次达到相同深度时（在游戏树的不同分支中），您的动作会被覆盖。

这个网站很好地解释了如何检索主要变化：https://web.archive.org/web/20071031100114/http://www.brucemo.com:80/compchess/programming/pv.htm

应用到你的代码示例中，应该是这样的（我没测试）：

def alphabeta(board, alpha, beta, depth, pline):

    line = []
    if depth == 0:
        return evaluate.eval(board)

    for move in board.legal_moves:
        board.push(move)
        score = -alphabeta(board, -beta, -alpha, depth - 1, line)
        board.pop()
        if score >= beta:
            return beta
        if score > alpha:
            alpha = score
        pline[:] = [str(move)] + line

    return alpha

从 alphabeta 框架中收集和检索主要变体

Collecting and retrieving the principal variation from an alphabeta framework

python

chess

artificial-intelligence

minimax

alpha-beta-pruning