Teaching a computer to play Tic-Tac-Toe

One downside of spending all your free time on fun development side projects is a lack of time to develop and sustain friendships with real people. But who needs real friends when we can write our own! AI friends are great because big hard drives are way cheaper than bigger couches. So let’s go make some friends! If you want to look ahead or check out the complete code, I’ve made the repo public at https://gitlab.aderholdt.net/jason/ai_tic_tac_toe.

Before we get too far into the AI, we need to pick a game for it to play. I choose tic-tac-toe because it’s trivial to implement and I suspect that it will be relatively simple to make an AI play it. Just in case you don’t know tic-tac-toe, two players (one represented by X and the other by O) take turns placing thier symbol on a 3x3 board trying to get three in of their symbol in a row. Typing that out actually makes it sound way more complicated than it actually is.

tic-tac-toe example In real life, it’s always a draw…

Creating the game

Technology

We’ll use Rust to implement both the game and AI due to its speed and ease of multi-threading. Since essentially all AI techniques require mutliple iterations over the same task or data to refine itself, the faster we can do this the better. If we can scale this out over each processing core, all the better. In the past I’ve used C++ with OpenMP to maximize core usage and performance, but since I don’t use C++ on a regular basis it always feels like I’m wasting time tracking down weird memory issues (especially once threading is added) or spending too much time ensuring my Makefile works and all environments have identical dependency resolution. Rust solves a lot of these problems by having a very strict compiler that calls out invalid memory access along with a package manager and build tool, cargo, that makes dependencies a breeze.

Design

To represent the game board, we’ll use a simple 9 element array of signed integers where each element will represent one square of the board. Rust, like most languages, uses zero indexed arrays, so the first position is 0 while the last will be 8. Empty spots will contain the value 0, while player 1’s positions will contain a 1, and player 2’s positions will contain a -1. You can probably identify some potential problems with this design already, what if someone tries to take the square at position 15 (outside of the bounds of our array) or if a square contained a 7 instead of -1, 0, or 1. Both of these problems could be made impossible by using enums or Options for the pieces and board, making any invalid situations impossible, but there are some special advantages to this design that I think make it worth handling these pitfalls another way.

 0 | 1 | 2 
-----------
 3 | 4 | 5
-----------
 6 | 7 | 8 

The array index mapping for the board

Data Structures

pub struct Game {
    pub board: [i8; 9],
    pub current_player: i8,
    pub status: GameStatus
}

pub enum GameStatus {
    InProgress,
    Winner,
    Draw
}

Additionally we need to keep track of whose turn it is, which if we re-use the 1 and -1 from the board mapping, means we can just put the player’s value in the board array and no other transformation needs to be done. Then to set the current player to the next person, we can simply multiply by -1. Our 1, 0, -1 plan also makes checking for a winner relatively simple, if the absolute value of any row, column, or diagonal is 3, then it has to be a win, and if there are no zeroes and no winner, then we have a draw. To keep track of if we need to take another turn, we’ll use a status enum to indicate if the game is over or if it is still in progress.

fn check_for_winner(game: &Game) -> GameStatus {
    let mut winner = false;
    let mut draw = false;
    for i in 0..3 {
        if (game.board[i*3+0] + game.board[i*3+1] + game.board[i*3+2]).abs() == 3  ||
            (game.board[i] + game.board[i+3] + game.board[i+6]).abs() == 3 ||
            (game.board[i] + game.board[4] + game.board[8-i]).abs() == 3 {
                winner = true;
                break;
            }
    }
    if ! game.board.iter().any(|x| *x==0i8) {
        draw = true;
    } 

    if winner {
        GameStatus::Winner
    } else if draw {
        GameStatus::Draw
    } else {
        GameStatus::InProgress
    }
}

We run the win check at the end of each turn to know if the game is complete or not. Next up, playing a single turn. A turn should take a position on the board and will return a Result of either Ok or Err to indicate if the position selected was valid. If the position was valid, we check if there was a winner and if not, we change to the next player. If there was a winner, we update the game status to indicate this.

    pub fn play_turn(&mut self, position: u8) -> Result<bool, &str> {
        if position > 8 || self.board[position as usize] != 0 {
            Err("Invalid position")
        } else {

            self.board[position as usize] = self.current_player;
            match check_for_winner(self) {
                GameStatus::InProgress => self.current_player = self.current_player * -1,
                GameStatus::Winner => {
                    self.status = GameStatus::Winner;
                },
                GameStatus::Draw => {
                    self.status = GameStatus::Draw;
                }
            }
            Ok(true)
        }
    }

The last part of the game is putting these pieces together, but before we do that, we need to define what a player is. A player needs to cover both AI as well as human players. This ends up being pretty straight foward if we create a Player trait for different types of players to impliment. A player really only needs to be able to take a turn, but we’ll give them a name too so that we can tell them apart.

pub trait Player {
    fn take_turn(&self, board: &[i8; 9]) -> u8;
    fn player_name(&self) -> &str;
}

Given that we can call the take_turn method on anything that impliments the Player trait and have it return a board position, we should be able to wrap this game up. To start a game, we’ll take two players and loop through the play_turn method on each player until we have a winner.

    pub fn play_game(&mut self, player1: &impl Player, player2: &impl Player) -> (GameResult, [i8; 9]) {
        loop {
            match
                match self.current_player {
                1 => self.play_turn(player1.take_turn(&self.board)),
                -1 => self.play_turn(player2.take_turn(&self.board)),
                _ => Err("Unknown Player.  This shouldn't happen.")
                } {
                    Err(_) => {},
                    Ok(_) => {
                        match self.status {
                            GameStatus::Winner => {
                                if self.current_player == 1 {
                                    let result = GameResult { player1: WinStatus::Winner, player2: WinStatus::Loser };
                                    break { (result, self.board) };
                                } else {
                                    let result = GameResult { player1: WinStatus::Loser, player2: WinStatus::Winner };
                                    break { (result, self.board) };
                                }
                            },
                            GameStatus::Draw => {
                                let result = GameResult { player1: WinStatus::Draw, player2: WinStatus::Draw };
                                break { (result, self.board) };
                            }
                            _ => {}
                        }
                    }
                }
        }
    }

We have a second check for winner call that we should be able to refactor out later, but for now it’s fine and gets the job done. Once the game is complete, we return a GameResult that contains info on who won and the final board. We can use this later for showing our human players how they did as well and for training our AI.

pub struct GameResult {
    pub player1: WinStatus,
    pub player2: WinStatus
}

In the next post, we’ll look into building the Players and the Neural Network for the AI.