brute force — минимаксная реализация c ++ для Tic Tac Toe

void generate_moves(int gameBoard[9], list<int> &moves)
{
for (int i = 0; i < 9; i++)
{
if (gameBoard[i] == 0){
moves.push_back(i);
}
}
}int evaluate_position(int gameBoard[9], int playerTurn)
{
state currentGameState = checkWin(gameBoard);

if (currentGameState != PLAYING)
{
if ((playerTurn == 1 && currentGameState == XWIN) || (playerTurn == -1 && currentGameState == OWIN))
return +infinity;
else if ((playerTurn == -1 && currentGameState == XWIN) || (playerTurn == 1 && currentGameState == OWIN))
return -infinity;
else if (currentGameState == DRAW)
return 0;
}

return -1;
}int MinMove(int gameBoard[9], int playerTurn)
{
//if (checkWin(gameBoard) != PLAYING) { return evaluate_board(gameBoard); };
int pos_val = evaluate_position(gameBoard, playerTurn);
if (pos_val != -1) return pos_val;

int bestScore = +infinity;
list<int> movesList;
generate_moves(gameBoard, movesList);

while (!movesList.empty())
{
gameBoard[movesList.front()] = playerTurn;
int score = MaxMove(gameBoard, playerTurn*-1);
if (score < bestScore)
{
bestScore = score;
}
gameBoard[movesList.front()] = 0;
movesList.pop_front();
}

return bestScore;
}int MaxMove(int gameBoard[9], int playerTurn)
{
//if (checkWin(gameBoard) != PLAYING) { return evaluate_board(gameBoard); };
int pos_val = evaluate_position(gameBoard, playerTurn);
if (pos_val != -1) return pos_val;

int bestScore = -infinity;
list<int> movesList;
generate_moves(gameBoard, movesList);

while (!movesList.empty())
{
gameBoard[movesList.front()] = playerTurn;
int score = MinMove(gameBoard, playerTurn*-1);
if (score > bestScore)
{
bestScore = score;
}
gameBoard[movesList.front()] = 0;
movesList.pop_front();
}

return bestScore;
}int MiniMax(int gameBoard[9], int playerTurn)
{
int bestScore = -infinity;
int index = 0;
list<int> movesList;
vector<int> bestMoves;
generate_moves(gameBoard, movesList);

while (!movesList.empty())
{
gameBoard[movesList.front()] = playerTurn;
int score = MinMove(gameBoard, playerTurn);
if (score > bestScore)
{
bestScore = score;
bestMoves.clear();
bestMoves.push_back(movesList.front());
}
else if (score == bestScore)
{
bestMoves.push_back(movesList.front());
}
gameBoard[movesList.front()] = 0;
movesList.pop_front();
}

index = bestMoves.size();
if (index > 0) {
time_t secs;
time(&secs);
srand((uint32_t)secs);
index = rand() % index;
}

return bestMoves[index];
}

Я создал программу Tic Tac Toe на C ++ и попытался реализовать алгоритм MiniMax с исчерпывающим деревом поиска.
Это функции, которые я написал с помощью вики и с помощью некоторых веб-сайтов. Но ИИ просто не работает правильно, а иногда и вовсе не играет своей очереди.

Может кто-то взглянуть и, пожалуйста, указать, если что-то не так с логикой?

Вот как я думаю, что это работает:

Minimax : Эта функция начинается с очень большого -ve числа, так как лучший результат и цель — максимизировать это число. Это вызывает minMove функция. Если новый результат> лучший результат, то лучший результат = новый результат …

MinMove : Эта функция оценивает игровое поле. Если игра окончена, то возвращается -infinity или + infinity в зависимости от того, кто выиграл. Если игра продолжается, эта функция начинается с максимального значения + бесконечность, как лучший результат, и цель состоит в том, чтобы свести его к минимуму насколько это возможно. Это вызывает MaxMove с ходом игрока противника. (так как игроки чередуются ходы).
Если оценка < лучший результат, то лучший результат = оценка. …

MaxMove : Эта функция оценивает игровое поле. Если игра окончена, то возвращается -infinity или + infinity в зависимости от того, кто выиграл. Если игра продолжается, эта функция начинается с наименьшего значения бесконечности, так как лучший результат и цель состоит в том, чтобы максимально увеличить его. Это вызывает MinMove с ходом игрока противника. (так как игроки чередуются ходы).
Если оценка> лучшая оценка, тогда лучшая оценка = оценка. …

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

Если есть более 1 лучших ходов, то случайный из них выбирается как ход компьютера.

0

Решение

В MiniMax, MinMove(gameBoard, playerTurn) должно быть MinMove(gameBoard, -playerTurn) как вы делаете в MaxMove,

Как вы используете MinMove а также MaxMoveВаша оценочная функция должна быть абсолютной. Я имею в виду +infinity за XWIN
а также -infinity за OWIN, Так что MinMove можно использовать только тогда, когда player == -1 и MaxMove, когда player == 1Таким образом, параметр становится бесполезным. Так что MiniMax может использоваться только player == 1,

Я сделал некоторые изменения в вашем коде, и это работает (https://ideone.com/Ihy1SR).

0

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


По вопросам рекламы [email protected]