0

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;
}
  • What is the behaviour of your code? What do you expect it to do? – Alan Birtles Sep 04 '21 at 18:00
  • 1
    Alternative: `#include int main () { std::cout < – user4581301 Sep 04 '21 at 18:00
  • 2
    Use the debugger that came with your development tools to step through the program. Keep an eye on how the variables change and as soon as you see something you don't expect, usually the wrong value was stored or the wrong path was taken, stop. You've found a bug or your expectations are wrogn. Either one is bad and needs to be fixed. Once you've confirmed a bug, construct a small program that allows you to demonstrate the bug (a [mre]) and ask questions about it. – user4581301 Sep 04 '21 at 18:25
  • 1
    If you dump all of your code into a question, as it appears you did here, you'll probably have more than one bug in the code and the question will likely be too broad. If you provide a smaller amount of code but it can't be compiled or otherwise doesn't express the bad behaviour you want help with, we have to start guessing. Stack Overflow doesn't favour guesswork answers. But if you make a [mre], that's just right. But the really cool thing about the MRE is it almost always leads to you finding and fixing the bug. – user4581301 Sep 04 '21 at 18:25
  • Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? If you did not try this, then you probably want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) – Andreas Wenzel Sep 04 '21 at 18:26
  • Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. – Community Sep 08 '21 at 17:08

0 Answers0