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

Question

我目前正在尝试写一个能玩象棋游戏的人工智能。为此，我使用了minimax算法的一种变体，该算法迭代每一个可能的移动，然后假设深度为N时，对手（和他们）将以最佳方式进行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;

    }

当调用“移动”时，它会检测是否拍摄了一幅作品，然后为该作品生成一个分数，该分数被保存到变量“温度”中。对于深度为2的情况，我简单地调用另一个Depth1方法，但改变颜色。对于深度为3的情况，我再次调用这个方法，以进行人工智能将做出的下一个理论移动。这工作得很好，但在深度为4的情况下，它不再以逻辑方式运行。

这是因为算法假设“最佳”移动是贪婪的（即，最佳移动是获取价值最高的棋子，这不一定是游戏本身的最佳移动，因为你可能会立即被收回，并在过程中失去一个更有价值的棋子）。为了解决这个问题，我尝试在Depth3或Depth4方法中调用我的Depth2方法，但它产生的结果同样不合逻辑，在游戏中也很糟糕。我不知道为什么会出现这种情况，但如果不是这样的话，把它留在Depth3会产生最强大的人工智能。

我是否未能理解类似极大极小算法的本质？如何改进算法，使N值越高，游戏效果越好？

Answer 1

MiniMax很适合递归实现。你可以在这段精彩的视频中找到一个例子。迭代地实现Minimax，并为depth n编写n次depth 1函数，该函数不遵循不重复自己（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_根算法。注意：你可以使用比Minimax更短的NegaMax算法（但需要从玩家的角度来评估位置，而不是像Minimax那样从white的角度）。