Вернуть bestMove в минимаксном алгоритме для tictactoe

В простейшей версии минимакса первый игрок хочет максимизировать свой счет, а второй игрок хочет минимизировать счет первого игрока.
Поскольку как первый, так и второй игрок заботятся только о счете первого игрока, EvaluateStaticPosition должен вернуть значение, указывающее, насколько хорошим является состояние доски для первого игрока. Чья это очередь не имеет значения.

int EvaluateStaticPosition(stateT state)
{
if(CheckForWin(state, FIRST_PLAYER))
{
return WINNING_POSITION;
}
if(CheckForWin(state, Opponent(FIRST_PLAYER)))
{
return LOSING_POSITION;
}
return NEUTRAL_POSITION;
}

Теперь, когда вы хотите ход, который лучше всего подходит для первого игрока, вызывайте MaxMove. Если вы хотите ход, который лучше для второго игрока, позвоните в MinMove.

moveT MiniMax(stateT state)
{
moveT bestMove;
int i = 0;
if (state.whoseTurn == FIRST_PLAYER){
i = MaxMove(state, bestMove);
}
else{
i = MinMove(state,bestMove);
}
cout<<"i is "<<i<<endl;
return bestMove;
}

Наконец, у вас есть некоторые проблемы внутри MinMove а также MaxMove, когда вы назначаете curRating ни в одном из них вы не должны проходить bestMove в качестве второго аргумента MaxMove или же MinMove, Затем он положит противника лучший шаг в bestMove, который не имеет смысла. Вместо этого объявите opponentsBestMove возразить и передать это в качестве второго аргумента. (На самом деле вы не будете использовать объект или даже смотреть на его значение, но это нормально). С этим изменением вы никогда ничего не назначаете bestMove в MinMoveтак что вы должны сделать это внутри if(curRating < v) блок.

int MaxMove(stateT state, moveT &bestMove)
{
if(GameIsOver(state))
{
return EvaluateStaticPosition(state);
}
vector<moveT> moveList;
GenerateMoveList(state, moveList);
int nMoves = moveList.size();
int v = -1000;
for(int i = 0 ;i<nMoves; i++)
{
moveT move = moveList[i];
MakeMove(state, move);
moveT opponentsBestMove;
int curRating = MinMove(state, opponentsBestMove);
if (curRating > v)
{
v = curRating;
bestMove = move;
}
RetractMove(state, move);
}
return v;

}
int MinMove(stateT state,  moveT &bestMove)
{
if(GameIsOver(state))
{
return EvaluateStaticPosition(state);
}
vector<moveT>moveList;
GenerateMoveList(state, moveList);
int nMoves = moveList.size();
int v = 1000;
for(int i = 0 ; i<nMoves; i++)
{
moveT move = moveList[i];
MakeMove(state , move);
moveT opponentsBestMove;
int curRating = MaxMove(state,opponentsBestMove);
if(curRating < v)
{
v = curRating;
bestMove = move;
}
RetractMove(state, move);
}
return v;
}

На данный момент у вас должен быть непобедимый AI!

The final position looks like this:

O | O | X
---+---+---
X | X | O
---+---+---
O | X | X

Cat's game.

Альтернативный метод использует тот факт, что крестики-нолики — игра с нулевой суммой. Другими словами, в конце игры сумма очков игроков будет равна нулю. Для игры с двумя игроками это означает, что оценка одного игрока всегда будет отрицательной оценкой другого игрока. Это удобно для нас, поскольку минимизация счета другого игрока идентична максимизации собственного счета. Таким образом, вместо одного игрока, максимизирующего свой счет, и одного игрока, минимизирующего счет другого игрока, мы можем просто заставить обоих игроков попытаться максимизировать свой собственный счет.

+ Изменить EvaluateStaticPosition вернуться к своей первоначальной форме, так что он дает оценку, основанную на том, насколько хорошо состояние доски для текущего игрока.

int EvaluateStaticPosition(stateT state)
{
if(CheckForWin(state, state.whoseTurn))
{
return WINNING_POSITION;
}
if(CheckForWin(state, Opponent(state.whoseTurn)))
{
return LOSING_POSITION;
}
return NEUTRAL_POSITION;
}

удалять MinMove, так как мы заботимся только о максимизации.
перезапись MaxMove так что он выбирает ход, который дает противнику наихудший возможный счет. Счет за лучший ход является отрицательным результатом худшего результата другого игрока.

int MaxMove(stateT state, moveT &bestMove)
{
if(GameIsOver(state))
{
return EvaluateStaticPosition(state);
}
vector<moveT> moveList;
GenerateMoveList(state, moveList);
int nMoves = moveList.size();
int v = -1000;
for(int i = 0 ;i<nMoves; i++)
{
moveT move = moveList[i];
MakeMove(state, move);
moveT opponentsBestMove;
int curRating = -MaxMove(state, opponentsBestMove);
if (curRating > v)
{
v = curRating;
bestMove = move;
}
RetractMove(state, move);
}
return v;

}

поскольку MaxMove используется для обоих игроков, нам больше не нужно различать игроков в MiniMax функция.

moveT MiniMax(stateT state)
{
moveT bestMove;
int i = 0;
i = MaxMove(state, bestMove);
cout<<"i is "<<i<<endl;
return bestMove;
}