python - 主要变化返回。

Question

嗨!我正在制作一个国际象棋引擎，因为我想实现迭代深化，我需要找到主要变化(引擎认为最佳的移动顺序)。但是，我没有在网上找到任何 python 伪代码示例，而且由于我的 alphabeta 函数是递归的，所以我真的很难理解它。

能否请您给我一些提示或伪代码示例如何做到这一点？非常感谢。

这是我的 alpha beta 函数，它只返回移动的估值，而不是移动本身:

def alphaBeta(self, board, rules, alpha, beta, ply, player):
    """ Implements a minimax algorithm with alpha-beta pruning. """
    if not ply:
        return self.positionEvaluation(board, rules, player)

    move_list = board.generateMoves(rules, player)

    if not len(move_list):
        return self.mateCheck(rules, board, player, ply)

    for move in move_list:
        board.makeMove(move, player)
        current_eval = -self.alphaBeta(board, rules, -beta, -alpha, ply - 1, board.getOtherPlayer(player))
        board.unmakeMove(move, player)

        if current_eval >= beta:
            return beta

        elif current_eval > alpha:
            alpha = current_eval

    return alpha

Answer 1

使用 NegaMax 搜索。下面是一个例子:

 function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            val := -negamax(child, depth-1, -β, -α, -color)
            {the following if statement constitutes alpha-beta pruning}
            if val≥β
                return val
            if val≥α
                α:=val
        return α

调用时，参数 α 和 β 应设置为任何节点可能的最低值和最高值，颜色应设置为 1。

(* Initial call *)
negamax(origin, depth, -inf, +inf, 1)

您始终可以使用 negamax 进行 alpha beta 剪枝

P.S:我已经实现了一个在线国际象棋平台。如果您想引用:check Chesshunt

您始终可以看到客户端代码，但实际的走法和国际象棋游戏逻辑是在服务器端实现的。