negamax算法..怎么了？

Question

我正在尝试编写一个国际象棋游戏，并且已经花了几天的时间来尝试修复代码。我甚至尝试过min max，但最终还是得到了相同的结果。AI总是从角落开始，并移动一个兵离开道路，然后车只是在每一次转弯时来回移动。如果它被吃掉了，AI会把每一块都从一边移动到另一边，直到所有的东西都被吃掉。你知道下面的代码会出什么问题吗？

public Move MakeMove(int depth)
{
    bestmove.reset();
    bestscore = 0;
    score = 0;
    int maxDepth = depth;
    negaMax(depth, maxDepth);
    return bestmove;
}


public int EvalGame() //calculates the score from all the pieces on the board
{
    int score = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if (AIboard[i, j].getPiece() != GRID.BLANK)
            {
                score += EvalPiece(AIboard[i, j].getPiece());
            }
        }
    }

    return score;
}

private int negaMax(int depth, int maxDepth)
{
    if (depth <= 0)
    {
        return EvalGame();
    }

    int max = -200000000;

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            for (int k = 0; k < 8; k++)
            {
                for (int l = 0; l < 8; l++)
                {
                    if(GenerateMove(i, j, k, l)) //generates all possible moves
                    {
                        //code to move the piece on the board
                        board.makemove(nextmove);
                        score = -negaMax(depth - 1, maxDepth);

                        if( score > max )
                        {
                            max = score;

                            if (depth == maxDepth)
                            {
                                bestmove = nextmove;
                            }
                        }

                        //code to undo the move
                        board.undomove;
                    }
                }
            }
        }
    }

    return max;
}

public bool GenerateMove(int i, int j, int k, int l)
{
    Move move;
    move.moveFrom.X = i;
    move.moveFrom.Y = j;
    move.moveTo.X = k;
    move.moveTo.Y = l;

    if (checkLegalMoves(move.moveTo, move.moveFrom)) //if a legal move
    {
        nextMove = move;
        return true;
    }

    return false;
}

Answer 1

这段代码：

public Move MakeMove(int depth)
{
    bestscore = 0;
    score = 0;
    int maxDepth = depth;
    negaMax(depth, maxDepth);
    return bestmove;
}

请注意，最佳走法永远不会被设定！将negaMax的返回分数与move备选方案进行比较。你甚至没有在可能的动作上进行循环。

此外，当您提交的代码不完全一致时，查找错误真的很难。negaMax方法在代码中的一个位置接受两个参数，然后在递归调用中接受四个参数？

我还建议在您的代码中进行更好的抽象。分离电路板表示法、移动表示法、移动生成和搜索算法。那会对你有很大帮助的。举个例子:为什么在移动生成中需要深度计数器？

-Øystein

Answer 2

您可能会遇到两个问题：

1. 它有点模棱两可，因为你没有向我们展示你的变量声明，但我认为你使用了太多的全局变量。Negamax通过计算每个节点的最佳移动来工作，因此在搜索值和移动时应该是局部的。在任何情况下，保持变量的作用域尽可能紧密都是一种好的做法。当遍历博弈树改变了这么多变量时，很难对代码进行推理。但是，您的搜索看起来应该返回正确的值。
2. 你的评估似乎并不能区分哪一方在比赛。我不知道EvalPiece是否会处理这个问题，但无论如何，评估应该从当前有权移动的哪一方的角度进行。

您还有其他与您的问题没有直接关系的问题：

1. 你的移动一代是可怕的。你成对地遍历棋盘上每一对可能的from/to方块。这是非常低效的，我甚至不明白这样的方法是如何工作的。你只需要遍历棋盘上的所有棋子，或者对于较慢的方法，遍历棋盘上的每个方块(而不是4096个方块)。
2. MakeMove看起来可能是根节点的位置。现在，您的方案起作用了，因为搜索退出的最后一个节点将是root。但是，在根部使用特殊例程是很常见的，例如迭代加深，因此在根部有一个单独的循环可能是很好的。