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 лучших ходов, то случайный из них выбирается как ход компьютера.
В 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).