理解Negamax的约束

Question

代码片段的构造是为了计算tictactoe游戏中某个位置的bestMove。我得到了代码的几乎所有部分，除了for循环中的条件，即minRating != LOSING_POSITION。此代码来自给定伪码的实现。

moveT FindBestMove(stateT state, int depth, int & rating) {
for (*each possible move or until you find a forced win*) {
 *Make the move.
 Evaluate the resulting position, adding one to the depth indicator.
 Keep track of the minimum rating so far, along with the corresponding move.
 Retract the move to restore the original state.*
 }
*Store the move rating into the reference parameter.
Return the best move.*
}

我无法将for循环的第二个条件与给定的代码相匹配，该代码说，直到您找到一个强制的胜利。我找不到这个事实和minRating != LOSING_POSITION之间的相似之处。

moveT FindBestMove(stateT state, int depth, int & rating) {
Vector<moveT> moveList;
GenerateMoveList(state, moveList);
int nMoves = moveList.size();
if (nMoves == 0) Error("No moves available");
moveT bestMove;

int minRating = WINNING_POSITION + 1;

for (int i = 0; i < nMoves && minRating != LOSING_POSITION; i++) {

 moveT move = moveList[i];
 MakeMove(state, move);
 int curRating = EvaluatePosition(state, depth + 1);

 if (curRating < minRating) {
  bestMove = move;
  minRating = curRating;
  }

 RetractMove(state, move);
 }
rating = -minRating;
return bestMove;

}


int EvaluatePosition(stateT state, int depth) {
int rating;

if (GameIsOver(state) || depth >= MAX_DEPTH) {
 return EvaluateStaticPosition(state);
}

FindBestMove(state, depth, rating);
return rating;
}

Answer 1

你的程序从分配WINNING_POSITION开始(我想你的对手赢了)到minRating，然后循环通过移动，试图找到具有最大伤害的移动，最小化minRating。

当EvaluatePosition返回LOSING_POSITION，而不是意味着此移动导致您的对手在每一种情况下失败，因此，搜索可以被终止，这一移动被认为是最好的移动。

如果没有明显的LOSING_POSITIONS，那么您的算法将根据静态评估选择“最佳”移动。