6
\$\begingroup\$

Posted my first attempt at Tic-Tac-Toe a second ago here. Got a lot of great and helpful responses. The main things I took away from these responses was to use spell check, and to keep things simple. Wanted to give it a second go before moving on to something a bit bigger.

Learned about the Minimax algorithm from this article. It doesn't work exactly like I'd hope but I can't tell if it's just the pitfalls of the algorithm or my code.

I'm grateful for any critique or pointers.

tictactoe.h

#ifndef TICTACTOE
#define TICTACTOE
#include <bitset>
#include <iostream>
#include <vector>

enum class BoardValue{ none, o, x};

class Board
{
public:
    Board() = default;
    Board(const Board& board): o_bits(board.o_bits), x_bits(board.x_bits) {};
    BoardValue at(int index) const;
    bool check_tie() const;
    bool check_win(bool) const;
    bool place(int, bool);
    std::vector<int> possible_moves() const;
private:
    std::bitset<9> o_bits{};
    std::bitset<9> x_bits{};
    std::bitset<9> filled_bits() const{ return o_bits | x_bits; }
};

class AI
{
public:
    AI(bool o) : is_o(o) {};
    int best_move(const Board&);
private:
    int minimax(const Board&, int, bool);

    int choice{};
    bool is_o; //is the ai playing as 'O'
};
#endif

tictactoe.cpp

#include "tictactoe.h"
#include <bitset>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>

BoardValue Board::at(int index) const{
    if(index < 0 || 8 < index) throw std::out_of_range{ "Index out of Board range" };
    if(filled_bits().test(index) == true)
    {
        return (o_bits.test(index) ? BoardValue::o : BoardValue::x);
    }
    else return BoardValue::none;
}

bool Board::check_tie() const
{
    std::bitset<9> full_board{ "111111111" };
    if( full_board == (filled_bits() & full_board) ) return true;
    return false;
}

bool Board::check_win(bool o) const
{
    const std::bitset<9>& bits = o ? o_bits : x_bits; //bits to be checked

    //diagonals
    if(bits.test(4) != false) //if middle is not taken no diagonals will pass
    {
        std::bitset<9> forward_diagonal{ "100010001" }; //bits of '\'
        std::bitset<9> backward_diagonal{ "001010100" }; //bits of '/'
        if(forward_diagonal == (bits & forward_diagonal)) return true;
        if(backward_diagonal == (bits & backward_diagonal)) return true;
    }

    //columns and rows
    std::bitset<9> col_check{ "001001001" }; //bits of the first column/row
    std::bitset<9> row_check{ "000000111" };
    for(int i = 0; i < 3; ++i) // loop for all 3 columns and rows
    {
        if(col_check == (bits & col_check)) return true;
        if(row_check == (bits & row_check)) return true;
        col_check = col_check << 1; //move over a column/row over
        row_check = row_check << 3;
    }

    return false;
}

//returns false if index is occupied
bool Board::place(int index, bool o)
{
    if(at(index) != BoardValue::none) return false;

    std::bitset<9>& bits = o ? o_bits : x_bits; //bits to be changed
    bits.set(index);
    return true;
}

//returns indexes of free spaces
//all returned indexes will return true when used in place(int,bool)
std::vector<int> Board::possible_moves() const
{
    const std::bitset<9> bits = filled_bits();
    std::vector<int> moves{};
    //loop through each bit and add the index of the ones that are 0 to possible_moves
    for(int i = 0; i < 9; ++i)
    {
        if( bits.test(i) == false)
        {
            moves.push_back(i);
        }
    }
    return moves;
}

int AI::best_move(const Board& board)
{
    minimax(board, 0, true);
    return choice;
}

int AI::minimax(const Board& position, int depth, bool maxPlayer)
{
    //check position game state and return score if game is lost, won, or tied
    if(position.check_win(!is_o)) //AI loses
    {
        return depth - 10;
    }
    else if(position.check_win(is_o)) //AI wins
    {
        return 10 - depth;
    }
    else if(position.check_tie())
    {
        return 0;
    }

    //do minimax calculation
    if(maxPlayer)
    {
        int max_move{};
        int max_move_score{ std::numeric_limits<int>::min()};
        for(int move : position.possible_moves())
        {
            Board possible_position{ position };
            possible_position.place(move, is_o);
            int score = minimax(possible_position, ++depth, false);
            if ( score > max_move_score )
            {
                max_move = move;
                max_move_score = score;
            }
        }

        choice = max_move;//last call to this will be at first call to minimax() from best_move()
        return max_move_score; //return max score
    }
    else
    {
        int min_move{};
        int min_move_score{ std::numeric_limits<int>::max()};
        for(int move : position.possible_moves())
        {
            Board possible_position{ position };
            possible_position.place(move, !is_o);
            int score = minimax(possible_position, ++depth, true);
            if ( score < min_move_score )
            {
                min_move = move;
                min_move_score = score;
            }
        }

        return min_move_score; //return max score
    }
}

main.cpp

#include "tictactoe.h"
#include <array>
#include <ctime>
#include <iostream>
#include <random>
#include <string>

int ask_player_input()
{
    bool retry{ false };
    int index{};

    std::cout << "It's your turn. Where do you want to go(e.g. A1 B3 C2)? ";
    do{
        if(retry)
        {
            std::cout << "No, no, no! Input a letter followed by a number: ";
        }
        retry = false; //reset retry

        std::string input;
        std::cin >> input;
        if(input.size() < 2)
        {
            retry = true;
            continue;
        }

        //letter input
        int col_input{};
        switch(input.at(0))
        {
            case 'A':
            case 'a':
                col_input = 0;
                break;
            case 'B':
            case 'b':
                col_input = 1;
                break;
            case 'C':
            case 'c':
                col_input = 2;
                break;
            default:
                retry = true;
                continue;
        }

        //number input
        int row_input = input.at(1) - '0'; //converts char '2' to int 2
        if(--row_input < 0 || 3 < row_input)
        {
            retry = true;
            continue;
        }

        index = col_input * 3 + row_input;
    } while( retry );
    return index;
}

bool ask_turn() //ask who will go first if return true O goes first
{
    bool turn{};
    std::string input;
    std::cout << "Who do you want to be?(X or O)? ";
    for(bool valid_input{false}; !valid_input;)
    {
        std::cin >> input;
        switch(input.front()) //input cannot be null at this point
        {
            case 'x':
            case 'X':
                valid_input = true;
                turn = false;
                break;
            case '0':
            case 'o':
            case 'O':
                valid_input = true;
                turn = true;
                break;
            default:
                std::cout << "Invalid input! Try X or O :";
        }
    }
    return turn;
}

std::ostream& print_board(std::ostream& os,const Board& board)
{
    os << " |A|B|C\n";
    for(int row = 0; row < 3; ++row)
    {
        os << std::string( 8, '-') << '\n';
        os << row + 1 << '|';
        for(int col = 0; col < 3; ++col)
        {
            char follow_char{ col == 2 ? '\n' : '|' };
            char place_char{};

            //determine character to print for this board place on the board
            BoardValue place_value  = board.at(col * 3 + row);
            if(place_value == BoardValue::none) place_char = ' ';
            else place_char = place_value == BoardValue::o ? 'O' : 'X';

            os << place_char << follow_char;
        }
    }
    os << '\n';
    return os;
}

std::ostream& operator<<(std::ostream& os,const Board& board)
{
    return print_board(os, board);
}

int main(){
    std::default_random_engine e{ static_cast<long unsigned int>(time(NULL)) };
    bool turn{ e() % 2 };
    bool player_turn{ ask_turn() };
    Board board{};
    AI ai{ !player_turn };

    if(turn != player_turn)//player first, turns will be flipped at start of game loop
    {
        std::cout << "You go first!\n" << board;
    }
    else 
    {
        std::cout << "Computer gets to go first this time. Good luck!\n";
    }

    while(board.check_win(turn) == false && board.check_tie() == false)
    {
        turn = !turn;
        if(turn == player_turn)
        {
            bool input_valid{false};
            while(input_valid == false)
            {
                int input;
                input = ask_player_input();
                input_valid = board.place(input, turn);
                if( input_valid == false )
                    std::cout << "That place is take! Try again...\n";
            }
        }
        else //AI turn
        {
            int best_move = ai.best_move(board);
            board.place( best_move, turn);

            std::cout << board;
            //print AI turn
            std::array<char,3> col_chars = { 'A', 'B', 'C' };
            char col_input = col_chars.at( best_move % 3 );
            int row_input = ((best_move + 1) / 3) + 1;

            std::cout << "Computer picks " << col_input << row_input << '\n';
        }
    }
    std::cout << board;
    if(board.check_tie())
    {
        std::cout << "Looks like its a tie...\n";
    }
    else 
    {
        std::cout << (turn == player_turn ? "You won!" : "The computer wins..." )  << '\n';
    }
}
\$\endgroup\$
3
\$\begingroup\$

Not time to check all the program, but I still spotted something I want to share:

This:

switch (input.front()) //input cannot be null at this point
{
case 'x':
case 'X':
    valid_input = true;
    turn = false;
    break;
case '0':
case 'o':
case 'O':
    valid_input = true;
    turn = true;
    break;
default:
    std::cout << "Invalid input! Try X or O :";
}

If you turn your compiler warnings on a high level you probably get complaints that you left out some break-statements. If you use C++17 you should state your intention with [[fallthrough]]:

switch (input.front()) //input cannot be null at this point
{
case 'x':
    [[fallthrough]]
case 'X':
    valid_input = true;
    turn = false;
    break;
case '0':
    [[fallthrough]]
case 'o':
    [[fallthrough]]
case 'O':
    valid_input = true;
    turn = true;
    break;
default:
    std::cout << "Invalid input! Try X or O :";
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.