Понимание ограничений Negamax

Фрагмент кода создан для расчета наилучшего хода позиции в тиктактой игре. Я получил почти каждую часть кода, кроме условия в цикле 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;
}

0

Решение

Ваша программа начинается с назначения WINNING_POSITION (победа для вашего оппонента, я полагаю) minRating а затем перебирая ходы, пытаясь найти ход с максимальным уроном, минимизируя minRating,

когда EvaluatePosition возвращается LOSING_POSITION Это означает, что этот ход приводит к тому, что ваш оппонент проигрывает в любом случае, поэтому поиск можно прекратить, и этот ход считается лучшим.

Если нет очевидного LOSING_POSITIONSЗатем ваш алгоритм выбирает «лучший» ход в соответствии со статической оценкой.

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector