Noughts and Crosses for netbyte

ai.cpp

#include "ai.h"

ai::ai(tictactoe &game, tictactoe::player_t player) : m_game(game), m_player(player) { }

void ai::move() {
    // All of these methods return true on success, thus the pile of ifs.
    if(try_win()) return;
    if(try_block()) return;
    if(try_fork()) return;
    if(try_block_fork()) return;
    if(try_centre()) return;
    if(try_opposing_corner()) return;
    if(try_empty_corner()) return;
    if(try_empty_side()) return;
    // We can't get here.
    throw "Cannot devise strategy for current board state! This is a bug.";
}

//private
tictactoe::board_t ai::us() const {
    return (m_player == tictactoe::player_crosses) ? m_game.crosses() : m_game.noughts();
}

//private
tictactoe::board_t ai::them() const {
    return (m_player == tictactoe::player_crosses) ? m_game.noughts() : m_game.crosses();
}

//private
void ai::play(short x, short y) {
    bool success;
    if(m_player == tictactoe::player_crosses) {
        success = m_game.play_cross(x, y);
    } else {
        success = m_game.play_nought(x, y);
    }
    
    if(!success) {
        throw "Play failed!";
    }
}

//private
bool ai::free(short x, short y) const {
    return m_game.at_point(x, y) == tictactoe::player_nobody;
}

// The four functions below are neatly symmetric. This is because attempting to
// "block" a move is exactly identical to us attempting to *make* the move,
// assuming that we are our opponent rather than ourself. Swapping us() and
// them() achieves this neatly.

//private
bool ai::try_win() {
    return win(us());
}

//private
bool ai::try_block() {
    return win(them());
}

//private
bool ai::try_fork() {
    return fork(us(), them());
}

//private
bool ai::try_block_fork() {
    return fork(them(), us());
}

//private
bool ai::try_centre() {
    // Variant: if it's the first move (board is clear), play a corner.
    // This is not strictly necessary, but makes it easier for the other
    // player to screw up.
    if(!m_game.is_started()) {
        play(0, 0);
    } else if(free(1, 1)) {
        play(1, 1);
    } else {
        return false;
    }
    return true;
}

//private
bool ai::try_opposing_corner() {
    if((them() & top_left_corner) && free(2, 2)) {
        play(2, 2);
        return true;
    }
    if((them() & top_right_corner) && free(0, 2)) {
        play(0, 2);
        return true;
    }
    if((them() & bottom_left_corner) && free(2, 0)) {
        play(2, 0);
        return true;
    }
    if((them() & bottom_right_corner) && free(0, 0)) {
        play(0, 0);
        return true;
    }
    return false;
}

//private
bool ai::try_empty_corner() {
    if(free(0, 0)) {
        play(0, 0);
        return true;
    }
    if(free(2, 0)) {
        play(2, 0);
        return true;
    }
    if(free(0, 2)) {
        play(0, 2);
        return true;
    }
    if(free(2, 2)) {
        play(2, 2);
        return true;
    }
    return false;
}

//private
bool ai::try_empty_side() {
    if(free(1, 0)) {
        play(1, 0);
        return true;
    }
    if(free(0, 1)) {
        play(0, 1);
        return true;
    }
    if(free(2, 1)) {
        play(2, 1);
        return true;
    }
    if(free(1, 2)) {
        play(1, 2);
        return true;
    }
    return false;
}

//private
bool ai::fork(tictactoe::board_t us, tictactoe::board_t them) {
    // To create a fork (that is, create two possible winning conditions)
    // To do this we need to find a position such that two rows, columns or
    // diagonals intersect at a single point, both of which currently have
    // exactly one piece already present.
    
    // Iterate over each board space. If it's free, check that we have at least
    // two intersecting potential wins on that piece. If we do, that should be a
    // fork, so we play there.
    for(short x = 0; x < 3; ++x) {
        for(short y = 0; y < 3; ++y) {
            if(!free(x, y)) {
                continue;
            }
            
            short count = 0;
            if(row_count(us, y) == 1 && row_count(them, y) == 0) ++count;
            if(column_count(us, x) == 1 && column_count(them, x) == 0) ++count;
            if(x == y && right_diagonal_count(us) == 1 && right_diagonal_count(them) == 0) ++count;
            if(x == 2-y && left_diagonal_count(us) == 1 && left_diagonal_count(them) == 0) ++count;
            
            if(count >= 2) {
                play(x, y);
                return true;
            }
        }
    }

    // No forks found.  
    return false;
}

//private
short ai::row_count(tictactoe::board_t board, short y) const {
    tictactoe::board_t row = (board >> (y*3)) & tictactoe::row;
    short count = 0;
    if(row & 0x01) ++count;
    if(row & 0x02) ++count;
    if(row & 0x04) ++count;
    
    return count;
}

//private
short ai::column_count(tictactoe::board_t board, short x) const {
    tictactoe::board_t column = (board >> x) & tictactoe::column;
    short count = 0;
    if(column & 0x01) ++count;
    if(column & 0x08) ++count;
    if(column & 0x40) ++count;
    
    return count;
}

//private
short ai::right_diagonal_count(tictactoe::board_t board) const {
    tictactoe::board_t diagonal = board & tictactoe::right_diagonal;
    short count = 0;
    if(diagonal & 0x01) ++count;
    if(diagonal & 0x10) ++count;
    if(diagonal & 0x100) ++count;
    return count;
}

//private
short ai::left_diagonal_count(tictactoe::board_t board) const {
    tictactoe::board_t diagonal = board & tictactoe::left_diagonal;
    short count = 0;
    if(diagonal & 0x04) ++count;
    if(diagonal & 0x10) ++count;
    if(diagonal & 0x40) ++count;
    return count;
}

//private
bool ai::win(tictactoe::board_t board) {
    short x = -1, y = -1;
    bool won = false;
    
    // First check the diagonals.
    if((board & two_right_diagonal_top) == two_right_diagonal_top && free(2, 2)) x = y = 2, won = true;
    else if((board & two_right_diagonal_bottom) == two_right_diagonal_bottom && free(0, 0)) x = y = 0, won = true;
    else if((board & two_left_diagonal_top) == two_left_diagonal_top && free(0, 2)) x = 0, y = 2, won = true;
    else if((board & two_left_diagonal_bottom) == two_left_diagonal_bottom && free(2, 0)) x = 2, y = 0, won = true;
    // TODO: Determine if we need to handle empty middle with filled corners here.
    // (I'm pretty sure we don't.)
    
    // Then the columns and rows
    else {
        for(int i = 0; i < 3; ++i) {
            // Grab a single row
            tictactoe::board_t inverted_row = ~(board >> (i*3)) & tictactoe::row;
            // This checks if there are two spaces filled, and if so,
            // gives the x coordinate of the empty space.
            switch(inverted_row) {
                case 0x01: x = 0; break; // 100
                case 0x02: x = 1; break; // 010
                case 0x04: x = 2; break; // 001
                default: x = -1;  break;
            }
            if(x != -1) {
                if(free(x, i)) {
                    y = i;
                    won = true;
                    break; // We've got it!
                } else {
                    x = -1;
                }
            }
            
            // Similar to the above, but for columns.
            tictactoe::board_t inverted_column = ~(board >> i) & tictactoe::column;
            switch(inverted_column) {
                case 0x01: y = 0; break;
                case 0x08: y = 1; break;
                case 0x40: y = 2; break;
                default: y = -1;  break;
            }
            
            if(y != -1) {
                if(free(i, y)) {
                    x = i;
                    won = true;
                    break;
                } else {
                    y = -1;
                }
            }
        }
    }
    
    // If we've found something that'll win it for us, do it.
    if(won) {
        play(x, y);
        return true;
    }
    return false;
}

ai.h

#ifndef tictactoe_ai_h
#define tictactoe_ai_h

#include "tictactoe.h"

class ai {
private:
    tictactoe& m_game;
    tictactoe::player_t m_player;
    
    // Useful constants
    
    // For the diagonals it's more effort to generate the offsets
    // programmatically than to just specify more constants here.
    static const tictactoe::board_t two_right_diagonal_top    = 0x11;
    static const tictactoe::board_t two_left_diagonal_top     = 0x14;
    static const tictactoe::board_t two_right_diagonal_bottom = 0x110;
    static const tictactoe::board_t two_left_diagonal_bottom  = 0x50;
    
    static const tictactoe::board_t top_left_corner     = 0x01;
    static const tictactoe::board_t top_right_corner    = 0x04;
    static const tictactoe::board_t bottom_left_corner  = 0x40;
    static const tictactoe::board_t bottom_right_corner = 0x100;

    // The eight-step guide to winning noughts and crosses:
    // All of these methods return true if they made a move and false if they
    // did not.
    bool try_win();             // 1) Win if we can
    bool try_block();           // 2) Block an opponent win
    bool try_fork();            // 3) Try to create two simultaneous wins
    bool try_block_fork();      // 4) Try to block the opponent's 3)
    bool try_centre();          // 5) Place a piece in the centre
    bool try_opposing_corner(); // 6) In the corner opposing the opponent
    bool try_empty_corner();    // 7) Any unused corner
    bool try_empty_side();      // 8) Anything else
    
    // Tries to win for the specified board_t (noughts or crosses)
    bool win(tictactoe::board_t board);
    // Tries to fork for the specified board_t. That is, it tries to
    // force two simultaneous winning positions, such that a win is
    // certain on the next move.
    bool fork(tictactoe::board_t forker, tictactoe::board_t forkee);
    
    // Returns the number of pieces of the given type in `row`
    short row_count(tictactoe::board_t board, short row) const;
    // Returns the number of pieces of the given type in `column`
    short column_count(tictactoe::board_t board, short column) const;
    // Returns the number of pieces of the given type in the
    // top-left to bottom-right diagonal
    short right_diagonal_count(tictactoe::board_t board) const;
    // Returns the number of pieces of the given type in the
    // top-right to bottom-left diagonal
    short left_diagonal_count(tictactoe::board_t board) const;
    
    // Handy convenience functions
    tictactoe::board_t us() const; // Returns the board_t containing our pieces
    tictactoe::board_t them() const; // Returns the board_t containing the opponent's pieces
    void play(short x, short y); // Plays a piece for us at (x, y).
    bool free(short x, short y) const; // Returns true if a move would be legal, otherwise false.
    
public:
    ai(tictactoe &game, tictactoe::player_t player);
    void move(); // Perform one move. Throws if unsuccessful (shouldn't ever happen).
};

#endif

game.cpp

#include <iostream>
#include <limits>
#include <cstdlib>
#include "game.h"

game_controller::game_controller(tictactoe::player_t first) : 
    m_board((first == tictactoe::player_nobody) ? tictactoe::player_noughts : first), // Noughts first if not otherwise specified
    m_computer(m_board, tictactoe::player_crosses) // Computer always plays crosses
{ }

void game_controller::run() {
    std::cout << "Computer is playing X." << std::endl;
    std::cout << "Game start." << std::endl;
    while(!m_board.is_finished() && m_board.winner() == tictactoe::player_nobody) {
        std::cout << "Current board:" << std::endl;
        print_board();
        if(m_board.current_turn() == tictactoe::player_crosses) {
            std::cout << "Computer's turn. Computer places X." << std::endl;
            m_computer.move();
        } else {
            // Loop until we have a valid, legal move from the player.
            short x = -1, y = -1;
            while(x < 0 || x > 2 || y < 0 || y > 2 || !m_board.play_nought(x, y)) {
                std::cout << "Player's turn. Enter a move (x y): ";
                x = read_short();
                y = read_short();
            }
        }
    }

    std::cout << "Game over. Final board:" << std::endl;
    print_board();
    std::cout << std::endl;

    tictactoe::player_t winner = m_board.winner();
    if(winner == tictactoe::player_crosses) {
        std::cout << "The computer wins!" << std::endl;
    } else if(winner == tictactoe::player_noughts) {
        std::cout << "You win!" << std::endl;
    } else {
        std::cout << "Tied game." << std::endl;
    }
}

//private
void game_controller::print_board() const {
    std::cout << "  0 1 2" << std::endl;
    std::cout << " +-+-+-+" << std::endl;
    for(short y = 0; y < 3; ++y) {
        std::cout << y << "|";
        for(short x = 0; x < 3; ++x) {
            switch(m_board.at_point(x, y)) {
                case tictactoe::player_crosses:
                    std::cout << "X";
                    break;
                case tictactoe::player_noughts:
                    std::cout << "O";
                    break;
                case tictactoe::player_nobody:
                    std::cout << " ";
                    break;
            }
            std::cout << "|";
        }
        std::cout << std::endl << " +-+-+-+" << std::endl;
    }
}

//private
short game_controller::read_short() const {
    short in;
    while (!(std::cin >> in)) {
        // Exit unsuccessfully if we reach EOF.
        if(std::cin.eof())
            std::exit(EXIT_FAILURE);
        // Clear errors and discard the entered text so we can prompt again.
        std::cin.clear();
        std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    }
    return in;
}

game.h

#ifndef tictactoe_game_h
#define tictactoe_game_h

#include "ai.h"
#include "tictactoe.h"

class game_controller {
public:
    game_controller(tictactoe::player_t first = tictactoe::player_nobody);

    // Plays one game; does not return until that game is completed.
    void run();

    // Returns a reference to the tictactoe object running the game.
    const tictactoe& board() const { return m_board; }

private:
    tictactoe m_board; //< The game itself
    ai m_computer;     //< The AI
    
    void print_board() const; //< Prints the board to stdout
    short read_short() const; //< Reads a short from stdin
};

#endif

main.cpp

#include <iostream>
#include <string>
#include "game.h"

int main(int argc, const char * argv[])
{
    int wins = 0, losses = 0, draws = 0;
    tictactoe::player_t plays_first = tictactoe::player_nobody;
    while(true) {
        game_controller game(plays_first);
        game.run();
        plays_first = game.board().winner();
        switch(plays_first) {
            case tictactoe::player_crosses:
                ++losses;
                break;
            case tictactoe::player_noughts:
                ++wins;
                break;
            case tictactoe::player_nobody:
                ++draws;
                break;
        }
        
        std::string again;
        std::cout << "Play again? ";
        std::cin >> again;
        if(::tolower(again.at(0)) != 'y') {
            break;
        }
    }
    
    std::cout << std::endl;
    std::cout << "Total wins: " << wins << std::endl;
    std::cout << "Total draws: " << draws << std::endl;
    std::cout << "Total losses: " << losses << std::endl;
    
    if(wins > 0) {
        std::cout << "(You have found a bug - you should never win!)" << std::endl;
    }
}

tictactoe.cpp

#include "tictactoe.h"

tictactoe::tictactoe(player_t first) : 
    m_noughts(0),
    m_crosses(0),
    m_current_move(first) 
{ }

bool tictactoe::play_cross(short x, short y) {
    if(m_current_move != player_crosses) return false;
    
    return play_piece(to_pos(x, y), m_crosses);
}

bool tictactoe::play_nought(short x, short y) {
    if(m_current_move != player_noughts) return false;
    
    return play_piece(to_pos(x, y), m_noughts);
}

tictactoe::player_t tictactoe::at_point(short x, short y) const {
    board_t bit = 1 << to_pos(x, y);
    if(m_crosses & bit) {
        return player_crosses;
    } else if(m_noughts & bit) {
        return player_noughts;
    } else {
        return player_nobody;
    }
}

bool tictactoe::is_finished() const {
    return ((m_noughts | m_crosses) & full) == full;
}

bool tictactoe::is_started() const {
    return (m_noughts | m_crosses) != 0;
}

tictactoe::player_t tictactoe::winner() const {
    if(has_won(m_crosses)) return player_crosses;
    if(has_won(m_noughts)) return player_noughts;
    return player_nobody;
}

//private
bool tictactoe::play_piece(short pos, board_t &board) {
    board_t bit_pos = 1 << pos;
    if((m_noughts | m_crosses) & bit_pos) {
        return false;
    }
    board |= bit_pos;
    
    m_current_move = (m_current_move == player_noughts) ? player_crosses : player_noughts;
    
    return true;
}

//private
bool tictactoe::has_won(board_t board) const {
    if((board & right_diagonal) == right_diagonal) return true;
    if((board & left_diagonal) == left_diagonal) return true;
    
    for(int i = 0; i < 3; ++i) {
        if((board & (column << i)) == (column << i)) return true;
        if((board & (row << (3*i))) == (row << (3*i))) return true;
    }
    
    return false;
}

tictactoe.h

#ifndef tictactoe_tictactoe_h
#define tictactoe_tictactoe_h

class tictactoe {
public:
    enum player_t { player_nobody, player_noughts, player_crosses };
    typedef unsigned short board_t;

private:
    // The game state is stored in two integers; one for noughts and one
    // for crosses. Each position is stored in a bit like so:
    // 012
    // 345
    // 678
    // When checks against the entire board are required, the two are overlaid.
    board_t m_noughts, m_crosses;
    player_t m_current_move; //< The current player's turn
    
    // Places a piece at `pos` in the specified `board`. Since each board_t can
    // only hold one type of piece, the type of piece placed is determined by the
    // board_t passed in.
    // Returns true if the move is legal (and was made) and false if not (and
    // wasn't made).
    bool play_piece(short pos, board_t &board);
    
    // Returns true if there is a winning streak on the specified board_t.
    bool has_won(board_t board) const;
    
    // Converts(x, y) coordinates from (0, 0) to (2, 2) to a board position.
    short to_pos(short x, short y) const { return x + 3 * y; }
    
public: 
    tictactoe(player_t first = player_crosses);
    
    // Returns the player who should be moving next.
    player_t current_turn() const { return m_current_move; }
    
    // Plays a nought or a cross at the given position, between (0, 0) and
    // (2, 2). Returns true if the move was made or false if it would be
    // illegal.
    bool play_cross(short x, short y);
    bool play_nought(short x, short y);

    // Returns the player at the given position; one of player_noughts,
    // player_crosses or player_nobody.
    player_t at_point(short x, short y) const;
    
    bool is_finished() const; //< True if the board is full, otherwise false.
    bool is_started() const; //< True if the board isn't empty, otherwise false.
    tictactoe::player_t winner() const; //< Returns the winner, if any.
    
    // These methods are probably only useful if the code needs to do significant
    // analysis of the board state.
    board_t crosses() const { return m_crosses; } //< Returns the crosses bitfield
    board_t noughts() const { return m_noughts; } //< Returns the noughts bitfield
    
    // Useful constants
    static const board_t column = 0x49;  //< The left-most column
    static const board_t row    = 0x07;  //< The top-most row
    static const board_t full   = 0x1FF; //< The entire board
    static const board_t right_diagonal = 0x111; //< The diagonal from top-left to bottom-right
    static const board_t left_diagonal  = 0x54;  //< The diagonal from top-right to bottom-left
};

#endif