negamax算法..有什么不对？
我试图编写一个国际象棋游戏，并花了数天时间来修复代码。 我甚至尝试了最小值，但以相同的结果结束。 人工智能总是从角落开始，并将一个棋子移开，然后每次转动时，这只车就会前后移动。 如果它被吃掉，那么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;
}
此代码：
public Move MakeMove(int depth)
{
bestscore = 0;
score = 0;
int maxDepth = depth;
negaMax(depth, maxDepth);
return bestmove;
}
请注意，最好的举措从未设置！ 比较negaMax的回报分数以移动替代品。 你甚至没有循环可能的举动。
此外，当您提交的代码不完全一致时，很难查找错误。 negaMax方法在代码negaMax两个参数放在一个地方，然后在递归调用中需要四个参数？
我也建议在你的代码中抽象得更好。 单独的棋盘表示，移动表示，移动生成和搜索算法。 这会帮助你很多。 举一个例子：为什么你需要移动代中的深度计数器？
-Øystein
你有两个可能的问题：
由于你没有向我们展示你的变量声明，所以有点含糊不清，但我认为你使用了太多的全局变量。 Negamax通过计算每个节点的最佳移动来进行工作，因此在搜索值和移动时应该是局部的。 无论如何，最好尽量保持变量的范围。 遍历游戏树时，更难以推断代码的变化如此之多。 但是，您的搜索看起来应该返回正确的值。
您的评估似乎没有区分哪一方在玩。 我不知道EvalPiece处理这个问题，但无论如何，评估应该从任何一方目前有权移动的角度进行。
您还有其他问题不直接影响您的问题：
你的举动是可怕的。 你成对地遍历棋盘上每一对可能的方块。 这是非常低效的，我不明白这种方法甚至会如何工作。 您只需循环通过电路板上的所有部件，或者使用较慢的方法，电路板上的每个方块（而不是4096个方块）。
MakeMove好像可能是根节点的地方。 现在，您的方案起作用，因为搜索结果的最后一个节点将是root。 但是，在根中使用特殊的例程（如迭代加深）是很常见的，所以在根目录下有一个单独的循环可能会很好。