So I have a tic tac toe cpp console app, and the AI (not actually AI) doesn't work as expected. It computes a very small amount of positions and chooses just the next available cell. The code I wrote is a bit similar to this one here. And I don't understand why mine isn't working since in the idea, only a few things are different. The idea in both codes is:
- iterate through the board
- if there's an empty cell, fill it with the current player
- call minimax with moves + 1 and the opposing player
- if the evaluation we got from the call is better for the current side we're playing, make the best one so far this evaluation
- undo the move/fill (backtracking)
- repeat until we iterated through all the empty cells
This is my code:
main.cpp:
#include <iostream>
//#include "Game.h"
#include "AI.h"
int main()
{
std::cout << "Do you want to play against AI? (Y for yes N for no) ";
char againstAI;
std::cin >> againstAI;
Game game = Game();
std::cout << game;
if (tolower(againstAI) == 'y')
{
std::cout << "Would you like to be X or O? ";
char choice;
std::cin >> choice;
if (choice != 'X' && choice != 'O')
{
throw("Invalid input\n");
}
bool isAiTurn = choice == 'O';
AI ai = AI(choice);
while (!game.isOver())
{
if (isAiTurn)
{
std::cout << "ai turn\n";
game.copyBoardTo(ai.boardCopy);
game.playMove(ai.decideMove());
}
else
{
game.getInput();
}
std::cout << game;
isAiTurn = !isAiTurn;
}
}
else if (tolower(againstAI) == 'n')
{
while (!game.isOver())
{
game.getInput();
std::cout << game;
}
}
else throw("Invalid input, exiting program\n");
}
AI.h:
#pragma once
#include "Game.h"
class AI
{
private:
//AI will be the maximizer and human the minimzer
const char maxChar, minChar;
const char* boardEnd;
int computations = 0;
public:
char boardCopy[Game::BOARD_SIZE][Game::BOARD_SIZE];
AI(char humanChoice);
std::pair<int, int> decideMove();
int8_t minimax(int depth, bool isMax);
};
AI.cpp:
#include "AI.h"
AI::AI(char humanChoice) : minChar(humanChoice), maxChar(humanChoice == 'X' ? 'O' : 'X'),
boardEnd(&(boardCopy[0][0]) + Game::BOARD_SIZE * Game::BOARD_SIZE)
{
}
std::pair<int, int> AI::decideMove()
{
static uint8_t movesDone = (minChar == 'X'); //if human is x s/he already made a move
computations = 0;
//because we're about to do a move
++movesDone;
int8_t eval, maxEval = -10;
std::pair<int, int> bestMove;
char* it = &(boardCopy[0][0]);
while (it != boardEnd)
{
if (*it == ' ')
{
*it = maxChar;
eval = minimax(movesDone, false);
if (eval > maxEval)
{
bestMove = { (int)(it - &(boardCopy[0][0])) / Game::BOARD_SIZE, (int)(it - &(boardCopy[0][0])) % Game::BOARD_SIZE };
if (eval == 10) break;
maxEval = eval;
}
*it = ' '; //backtracking
}
++it;
}
std::cout << "AI has computed " << computations << " positions\n";
//incrementing another time cuz human will make a move next turn
++movesDone;
return bestMove;
}
int8_t AI::minimax(int moves, bool isMax)
{
++computations;
/* can only win or draw after a player formed a line
* the line is {size} cells but both players need to take turns so size * 2
*/
if (moves >= Game::BOARD_SIZE * 2 - 1)
{
//if now it's max then before it was min who played and might have won
if (isWinning(boardCopy, isMax ? minChar : maxChar))
{
return isMax ? -10 : 10;
}
//already took up all the squares on ther board and no one won
if (moves == Game::BOARD_SIZE * Game::BOARD_SIZE) return 0;
}
char* it = &(boardCopy[0][0]);
int8_t eval;
++moves;
if (isMax)
{
int8_t maxEval = -10;
while (it != boardEnd)
{
if (*it == ' ')
{
*it = maxChar;
eval = minimax(moves, false);
if (eval > maxEval)
{
if (eval == 10) return 10;
maxEval = eval;
}
*it = ' '; //backtracking
}
++it;
}
return maxEval;
}
int8_t minEval = 10;
while (it != boardEnd)
{
if (*it == ' ')
{
*it = minChar;
eval = minimax(moves, true);
if (eval < minEval)
{
if (eval == -10) return -10;
minEval = eval;
}
*it = ' '; //backtracking
}
++it;
}
return minEval;
}
Game.h:
#pragma once
#include <iostream>
class Game
{
public:
const static int BOARD_SIZE = 3; //NOTE: if changed, change "line" at the ostream operator accordingly
private:
char board[BOARD_SIZE][BOARD_SIZE];
char currentPlayer;
int movesDone;
public:
Game();
//~Game();
//gets user input and plays the move the user inserted
void getInput();
void playMove(std::pair<int, int> coord);
void copyBoardTo(char (&board)[BOARD_SIZE][BOARD_SIZE]);
//returns true if the game is over (draw or someone won)
bool isOver();
//print the gameBoard
friend std::ostream& operator<<(std::ostream& os, const Game& game);
};
bool isWinning(const char(&board)[Game::BOARD_SIZE][Game::BOARD_SIZE], const char player);
Game.cpp:
#include "Game.h"
bool isWinning(const char(&board)[Game::BOARD_SIZE][Game::BOARD_SIZE], const char player)
{
int i, j;
//checking rows
for (i = 0; i != Game::BOARD_SIZE; ++i)
{
for (j = 0; j != Game::BOARD_SIZE && board[i][j] == player; ++j);
if (j == Game::BOARD_SIZE) return true;
}
//checking columns
for (i = 0; i != Game::BOARD_SIZE; ++i)
{
for (j = 0; j != Game::BOARD_SIZE && board[j][i] == player; ++j);
if (j == Game::BOARD_SIZE) return true;
}
//left diagonal
for (i = 0; i != Game::BOARD_SIZE && board[i][i] == player; ++i);
if (i == Game::BOARD_SIZE) return true;
//right diagonal
for (i = 0; i != Game::BOARD_SIZE && board[i][Game::BOARD_SIZE - 1 - i] == player; ++i);
if (i == Game::BOARD_SIZE) return true;
return false;
}
Game::Game() : movesDone(0), currentPlayer('X')
{
//initialing board to all empty cells
std::fill(&board[0][0], &board[0][0] + sizeof(board), ' ');
}
void Game::getInput()
{
std::cout << "Enter row and column to mark as " << currentPlayer << ": ";
int i, j;
std::cin >> i >> j;
if (--i < 0 || i >= BOARD_SIZE || --j < 0 || j >= BOARD_SIZE)
{
std::cerr << "Input is out of range [1, " << BOARD_SIZE << "].\n";
exit(1);
return;
}
if (board[i][j] != ' ')
{
std::cerr << "Cell already taken\n";
exit(1);
return;
}
playMove({ i, j });
}
void Game::playMove(std::pair<int, int> coord)
{
board[coord.first][coord.second] = currentPlayer;
currentPlayer = currentPlayer == 'X' ? 'O' : 'X';
++movesDone;
}
void Game::copyBoardTo(char (&boardStart)[BOARD_SIZE][BOARD_SIZE])
{
std::copy(&board[0][0], &board[0][0] + BOARD_SIZE * BOARD_SIZE, &boardStart[0][0]);
}
bool Game::isOver()
{
return movesDone == BOARD_SIZE * BOARD_SIZE || isWinning(board, currentPlayer);
}
void repeat(std::ostream &os, const char str[], unsigned int times)
{
while (times--)
{
os << str;
}
}
std::ostream& operator<<(std::ostream& os, const Game& game)
{
static const char minusStr[] = "+---";
unsigned int i = 1;
while (i <= Game::BOARD_SIZE)
{
os << " " << i++;
}
os << "\n ";
i = 1;
for (const auto& row : game.board)
{
repeat(os, minusStr, Game::BOARD_SIZE);
os << "+\n" << i++ << '|';
for (const auto& cell : row)
{
os << ' ' << cell << " |";
}
os << " \n ";
}
repeat(os, minusStr, Game::BOARD_SIZE);
os << "+\n";
return os;
}