如何在类国际象棋游戏中实现极大极小算法？

Question

我目前正在尝试编写一个能玩象棋游戏的人工智能。为此，我使用了minimax算法的一个变体，该算法遍历每一个可能的移动，然后假设对于N个移动，对手(和他们)将玩得最好。此外观的伪代码如下所示：

public string GenerateDepth1Move()
    {
       
        int max = -INFINITY;
        string bestMove;
        List<string> moves = PossibleMoves(colour);
        foreach (string s in moves)
        {
            int temp += Move(s, colour);
            if(temp > max)
            {
                max = temp;
                bestMove = s;
            }
        }

       return bestMove;

    }

当'Move‘被调用时，它会检测一块是否已经被取走，然后为该块生成一个分数，该分数被保存到变量'temp’中。对于深度为2的情况，我只需调用另一个Depth1方法，但更改了颜色。对于深度为3的情况，我再次调用它作为人工智能下一步理论上的动作。这工作得很好，但在深度为4时，它就不再以逻辑方式工作。

这是因为算法假设“最佳”走法是贪婪的(也就是说，最优走法是取走任何价值最高的棋子，这不一定是游戏本身的最佳走法，因为在这个过程中，你可能会立即被取回，并失去更有价值的棋子)。为了纠正这个问题，我尝试在Depth3或Depth4方法中调用我的Depth2方法，但它产生的结果同样不合逻辑，而且在游戏中也很糟糕。我不确定为什么会这样，但让它留在Depth3会产生最健壮的人工智能，而不应该是这样的。

我是不是没能理解类极小极大算法的本质？我如何改进我的算法，以使更高的N值导致更好的发挥？

Answer 1

MiniMax很适合递归实现。您可以在this great video中找到一个示例。迭代地实现Minimax并编写n次深度1函数，因为深度n不遵循不要重复自己(DRY)规则。Python中的实现：

def minimax(pos, depth, alpha, beta, maximizingPlayer) :
# maximizingPlayer = True if White2Play and False si Black2Play

if depth == 0 or game_is_finished(board) or can_t_move(board) :
    return evaluate(board)                                     # <- zero ground for recusivity

if maximizingPlayer :
    maxEval = -infinity
    for child in child_of_position(board) :
        evalu = minimax(child, depth - 1, alpha, beta, False)  # recursivity
        maxEval = max(maxEval, evalu)
        alpha = max(alpha, evalu)
        if beta <= alpha :
            break
    return maxEval

else :
    minEval = infinity
    for child in child_of_position(board) :
        evalu = minimax(child, depth - 1, alpha, beta, True)    # recursivity
        minEval = min(minEval, evalu)
        alpha = min(alpha, evalu)
        if beta <= alpha :
            break
    return minEval

在开始时，使用alpha = -infinity和beta = infinity调用minimax。要生成最佳移动，请使用minimax_root算法。注意:你可以使用比Minimax短的NegaMax算法(但需要从玩家的角度来评估位置，而不是像Minimax那样从白色的角度)。