Tag Archives: AI

Building Tic-Tac-Toe in Rust: rustic_tac_toe

When learning a new language, it’s always great to make fun little games. Not only are they rewarding, but they also allow you to quickly learn paradigms of that language. I decided to build Tic-Tac-Toe. Luckily, Rust combines nicely with the name of this game. Rustic-Tac-Toe.

The first thing we want to do is think about the design of our game. I decided to go with a simple 9-slot array that would keep track of the 9 spots of the Tic-Tac-Toe board. This array would be filled with characters to keep track of the symbols entered. At first, however, it could be filled with numbers representing each slot in order to allow the user to pick their slots. Something like this:

fn main() {
    let zero_ascii = 48;
    let default_char = '-';

    // Step one, create board:
    let mut board = [default_char; 9];
    for i in 0..9 {
        board[i] = (i + zero_ascii) as u8 as char;
    }
}

The two most challenging parts about this particular block of code happen to be dealing with integer to char conversions. First of all, Rust didn’t seem to like doing something like
i + '0' , so I went ahead and looked up the ASCII value for the 0 character and manually added that in. If there is an easier way to do this, I would appreciate the commentary!

Also, casting from a for loop’s usize variable into a char is a little tricky, as in order to call as char , you need to have a u8 . So first, we cast the usize to a u8 and then to a char. All of that mumbo-jumbo allows us to fill the board with numbers corresponding to the slots. So far, nothing too challenging.

Next up, we want to give the user some way to interact with the board. We want to display the board to the user and have them pick a number. In order to do this, we make a nice print_board function, as such:

fn print_board(board: [char; 9]) {
    for i in 0..9 {
        print!("{} ", board[i]);
        if i > 0 && (i+1) % 3 == 0 {
            println!("");
        }
    }
}

Nothing too complicated about this at all. We essentially print the elements of the board separated by spaces, and make a new line after every third entry, signalling the end of a row. This is done with mod math and a greater-than-0 check, since 0 % 3 == 0 will return true.

Another intermediate step we need to do is make some function to determine whether or not our game of Rustic-tac-toe is over. This will allow the user to repeatedly fill the board without having to restart the program every time. I’m sure there’s a much better way to do this, but here’s what I came up with:

fn someone_has_won(board: [char;9]) -> (bool, char) {
    if board[0] == board[1] && board[1] == board[2] {
        return (true, board[0]);
    } else if board[3] == board[4] && board[4] == board[5] {
        return (true, board[3]);
    } else if board[6] == board[7] && board[7] == board[8] {
        return (true, board[6]);
    } else if board[0] == board[3] && board[3] == board[6] {
        return (true, board[0]);
    } else if board[1] == board[4] && board[4] == board[7] {
        return (true, board[1]);
    } else if board[2] == board[5] && board[5] == board[8] {
        return (true, board[2]);
    } else if board[0] == board[4] && board[4] == board[8] {
        return (true, board[0]);
    } else if board[2] == board[4] && board[4] == board[6] {
        return (true, board[2]);
    } else {
        return (false, '-');
    }
}

This function basically checks to see if a column or row contains all three of the same characters. It also checks the diagonal options. When it finds a win condition, it returns a tuple containing whether or not someone has won and who won. This allows for some flexibility. If no one has won yet, we just return a tuple with false and some character we don’t care about.

The final step to pull this game together is to implement a loop where the user can input a number and have the updated board printed to them! Basically, the loop displays the board, gets the results, asks the user for his input, makes sure the input is valid, and then displays the new board. The basic structure of the loop, then, will look like this:

print_board(board);
let mut results = someone_has_won(board);
while !results.0 {
    // do stuff
}

Pretty simple. We print the board, set a mutable variable to keep track of whether or not someone has won, and then start the while loop. The loop will keep on going until someone has won.  But what if no one wins? What if it is a tie? (So called, ‘Cats game’). This will occur when we are still in the loop (So no one has won yet), but all the spots are filled with symbols (No spots are their default values). Thus, we can check that using a method similar to when we created the board. We create a new function as such:

fn cats_game(board: [char;9] ) -> bool {
    for i in 0..board.len() {
        if board[i] == (i +  48) as u8 as char {
            return false;
        }
    }
    return true;
}

I notice that most of my functions have explicit return calls, which I read somewhere in the documentation is bad style. I’m going to keep it, though, since I don’t really understand how the alternative works quite yet. Now we just need to add this “Cats Game” check into our main loop:

  while !results.0 {
        if cats_game(board) {
            println!("Cats game. Nobody wins!");
            break;
        }
}

Fantastic. The next step is to get the user’s input. We will allow the user to always go first (There will be another player which I will introduce later. So, we ask the user for his input and then grab it from Stdin using the std::io library. Thus, we need to first use std::io; . Once that’s done, we can add the retrieval of user input into our loop.

 while !results.0 {
        if cats_game(board) {
            println!("Cats game. Nobody wins!");
            break;
        }

        // Step two, ask where the user wants to place their X.
        println!("Where would you like to place an 'X'?");
        let mut answer = String::new();
        io::stdin().read_line(&mut answer)
            .ok()
            .expect("Error reading line");

        let answer:usize = match answer.trim().parse() {
            Ok(num) => num,
            Err(_) => 10,
        };

        if answer > (board.len() - 1) {
            println!("You cannot place something there!");
            continue;
        }
}

Woah! That seems like an unnecessarily large addition of code simply to get the user’s input. However, there is also some error checking done.  The first thing this code does is display a prompt. Then, we get the answer in the form of a mutable string. After this, we convert the string an a usize integer. We have to use a usize since we later want to use this variable binding to access an array element directly, and arrays seem to be indexed by usize. [1] If the answer cannot be converted into an integer, we give it a value of 10. This will cause it to fail the next check (Since 10 > 8, which is the board’s size less 1). This next check simply makes sure to check whether the user has entered a number within the board’s bounds. Since the answer is converted into an unsigned int, it is guaranteed to be greater than or equal to 0, so we are good there and only need to check one side.

If all of these checks have completed successfully, we can go ahead and check to see if the spot is open on the board. This can be done with a match statement, as seen below:

match board {
        'X' => {
            println!("You have already placed something there!");
            continue;
        }
        'O' => {
            println!("There is already something placed there!");
            continue;
        }
         _ => {
            board = 'X';
            print_board(board);
            results = someone_has_won(board);
        }
    }

Basically, this match statement checks to see if the current position has an X or an O in it. (The player will be placing X’s and the AI player will be placing Os). If the slot that the user has requested has something in it already, we display a message and then continue at the top of the while loop, displaying a prompt and starting the whole get-input process all over again. If this isn’t the case and the spot on the board is indeed empty, we can add an X to that spot, print the new board, and then get a new “results” variable which will be used to check the while condition.

That’s it! We basically have a single-player tic-tac-toe built. This is great if you fancy playing by yourself with zero opposition. But our goal is to make something that is playable and relatively fun, so we are going to add an AI player. In our game, the player will go first and the AI will go second. Keeping this in mind, the AI needs to have a turn after each player turn. Assuming a cats game, this results in a turn pattern of Player, AI, Player, AI, Player, AI, Player, AI, Player. That is, the player goes first and last and takes exactly 5 turns. In order to prevent the AI from taking a final, extra turn, we will also implement a turn counter that prevents the AI from moving if the player just made their 5th turn. We add this to the beginning of our main:

let zero_ascii = 48;                                                        
let default_char = '-';                                                     
let last_turn = 5;

And we add a turn counter right before our while:

let mut results = someone_has_won(board);                                   
let mut turn = 1;

Now, every time the player takes a turn, we increment the turn counter and have the AI move if it is not the last turn. Thus, we alter the move line to look as such:

board = 'X';                                            
if turn < last_turn {                                           
    ai_move(&mut board);                                        
}                                                               
print_board(board);                                             
results = someone_has_won(board);                               
turn = turn + 1;

This block of code also introduces a new function, the ai_move function. Basically, we want this function to process the entirety of the AI’s move. That is, it analyzes the board, looks for a spot, and then places the O. Since it will ultimately alter the board, we need to pass a mutable reference to the function. The &amp; symbol creates a reference, and the mut keyword makes sure that the reference is mutable. Now we need to create the function:

We want to accomplish two things with our function. We want to make our AI player fairly good at playing tic-tac-toe, but we also want to give the player a chance, so we also want to make him quite terrible. Why not both? We will go ahead and randomly decide whether the AI should analyze the board and choose a spot accordingly or if the AI should just randomly choose an open spot. Since the latter is easier, we will do that first. We can go ahead and rely on Rust’s rand crate for the random number generation. In order to do so, we add the following to our Cargo.toml:

[dependencies]
rand = "*"

Now, next time we run cargo build, it will download the latest version of the rand crate and make it available for use. We also have to tell our program to utilize this crate as well, by putting

extern crate rand;
use rand::Rng;

at the top of our program. The first imports the external crate, as it would suggest. The second line allows us to easily make random number generation calls. Then, we can go ahead and make use of the rand::thread_rng::gen function that will simply generate a random boolean. This will allow us to decide (in a much unbiased fashion) whether our AI should act smart or not. Thus, the code looks like:

let mut rng = rand::thread_rng();                                           
if rng.gen() {                                                              
        // Do a good move          
else {                                                                      
        // Do a random move                                                     
        let mut num: usize = rng.gen_range(0, 9);                               
        while board[num] == 'X' || board[num] == 'O' {                          
            num = rng.gen_range(0, 9);                                          
        }                                                                       
        board[num] = 'O';                                                       
        return;                        
}

The first thing this code does is create a mutable variable binding that will allow us to generate random things. We can then use the gen function in order to generate a random boolean. If this boolean is false, we will generate a random number in the range of 0-9 until we find a random spot that is empty. Once we find a spot that’s empty, we set it to an O and then quit the function. Pretty simple!

Now comes the challenging part: designing an AI that plays the game well. Basically, the AI will perform several steps.

 

  1. If there are two X’s in a row, the player is about to win, so block the about-to-be-win.
  2. If the middle spot is not taken, take it.
  3. If there is no immediate threat, put a O next to any other O’s in order to try and win.
  4. If none of these options are available, place an O anywhere, it doesn’t really matter.

As you can see, our AI is a lot more defensive than offensive – but that’s okay. The best offense is a good defense – or so I’ve been told. So let’s design some sort of code that checks for any 2 Xs in a row. In order to give the player a chance (and make coding a bit easier), we will ignore diagonals. You can implement them on your own if you’d like, but I am going to ignore them. Thus, all we need to do is look at each row, count the number of Xs. If it is 2, place a O in the empty spot in that row. Then, do this with the columns. In order to do this, we can use an elegant double-for design, as seen below:

// First, we check to see if there are any two X's in a row so      
// that we can defend.                                              
for i in 0..3{                                                      
    let mut rowCount = 0;                                           
    for j in 0..3 {                                                 
        if board[j + 3*i] == 'X' {                                  
            rowCount = rowCount + 1;                                
        }                                                           
    }                                                               
    if rowCount == 2 {                                              
        for j in 0..3 {                                             
            if board[j + 3*i] != 'X' && board[j + 3*i] != 'O' {     
                board[j + 3*i] = 'O';                               
                return;                                             
            }                                                       
       }                                                           
   }                                                               
}

It is a little challenging to implement a nice for-loop check since our single dimensional array doesn’t really do 2D space justice. However, we deal with it by knowing that there are 3 elements in a row and each elements neighbor is one added to its own index. Thus, we scroll through each row with i and then allow j to iterate through the columns, adding 1 to the rowCount is an X exists. Then, if 2 Xs do indeed exist in that row (staying inside the i for loop since i watches the rows), we again look through the columns. If we find an empty column, we place a O there. This could have probably been compacted so that we were looking for empty spaces while counting Xs…

Now, we do the same thing for the columns:

                                                                            
// Now we check columns                                             
for i in 0..3 {                                                     
    let mut columnCount = 0;                                        
    for j in 0..3 {                                                 
        if board[i + 3*j] == 'X' {                                  
            columnCount = columnCount + 1;                          
        }                                                           
    }                                                               
    if columnCount == 2 {                                           
        for j in 0..3 {                                             
            if board[i + 3*j] != 'X' && board[i + 3*j] != 'O' {     
                board[i + 3*j] = 'O';                               
                return;                                             
            }                                                       
       }                                                           
}                                                               

The main logic of the column-checking functionality is exactly the same as the row-checking functionality. The only difference is that we use a different method to iterate through. Instead of i being the rows and j being the columns, we swap their roles. Noting that there are 3 slots in each column, we iterate through each column with i and let j iterate through the rows. We multiply j by 3 since in our single dimension array, the item in the row below another item has an index of 3 added to the index of the above item.

And with that, the first step is complete. We now block any attempts by X to win the game (except for diagonals). The next step is to take the middle spot if it is available. This is a very easy feature to implement (compared to our last chunk of code). Keep in mind that the index of the middle spot in our 1D array is 4. The code is:

if board[4] != 'X' && board[4] != 'O' {                                 
    board[4] = 'O';                                                     
    return;                                                             
}                                                                       

That’s it! How simple! We be sure to return whenever we place a O in the board in order to avoid further execution of other board-checking-and-placing code. Step 2 complete.

The next step is a long one. Basically, we look for an O already existing on the board. If there is one, we find a spot adjacent to it, check to make sure nothing is there, and then place our O. Checking for an open adjacent spot to another spot on our board is a problem all on its own since our array is misrepresentative. What if we wanted a spot adjacent to the spot with an index of 2? Easy, right? They’re the spots with indices of 3 and 1!. Wrong. Since we chose to represent our board in a 1D array, slot 3 would actually be the first entry in the next row. Thus, we need to individually consider all the spots on the board. Here’s some code to do just that:

fn get_available_adjacent(board: [char;9], spot: usize) -> usize {              
if spot == 4 {                                                              
    if board[2]  != 'X' && board[2] != 'O' {                                
        return 2;                                                           
    }                                                                       
    else if board[0] != 'X' && board[0] != 'O' {                            
        return 0;                                                           
    }                                                                       
    else if board[6] != 'X' && board[6] != 'O' {                            
        return 6;                                                           
    }                                                                       
    else if board[8] != 'X' && board[8] != 'O' {                            
        return 8;                                                           
    }                                                                       
}                                                                           
if spot + 3 < board.len() {                                                 
    if board[spot + 3] != 'X' && board[spot + 3] != 'O' {                   
        return spot + 3;                                                    
    }                                                                       
}                                                                           
else if (spot as isize - 3) >= 0 {                                          
    if board[spot - 3] != 'X' && board[spot - 3] != 'O' {                   
        return spot - 3;                                                    
    }                                                                       
}                                                                           
else if ((spot + 1) / 3) == (spot / 3) {                                    
    if spot + 1 < board.len() {                                             
        if board[spot + 1] != 'X' && board[spot + 1] != 'O' {               
            return spot + 1;                                                
        }                                                                   
    }                                                                       
}                                                                           
else if ((spot -1) / 3) == (spot / 3) {                                     
    if board[spot - 1] != 'X' && board[spot - 1] != 'O' {               
        return spot - 1;                                                
    }                                                                   
}                                                                           
for i in 0..board.len() {                                                   
    if board[i] != 'X' && board[i] != 'O' {                                 
        return i;                                                           
    }                                                                       
}                                                                           
return 10;                                                                  
}

Woah. That’s a really, really, really big chunk of code. Honestly, it could probably be much, much shorter if it was well-designed. However, what I chose to do, was look through every possible combination of spots adjacent to the provided parameter spot and return the first empty one. If there was no empty one, we return 10, which is larger than the size of the board and can be manually checked for later. If you have suggestions to improve this mess of a function, please, leave a comment! Essentially, this block solves two problems: It detects the spot that we can place an O in to complete step 3, and creates a condition for when step 4 should occur. We then call this function as such:

let mut empty_spot = -1;                                            
for i in 0..9 {                                                     
    if board[i] == 'O' {                                            
        let new_spot = get_available_adjacent(*board, i);           
            if new_spot < board.len() {                                 
                board[new_spot] = 'O';                                  
                return;                                                 
            }                                                           
     }                                                               
     else if board[i] != 'X' {                                       
         empty_spot = i;                                             
     }                                                               
}                                                                   
board[empty_spot] = 'O';                                            

We create a mutable variable-binding that allows us to keep track of what spot we should put our O in. Then, we look through every spot in the board. If the spot already has an O in it, then we know that we need to place a new O adjacent to it. We then call the new function we created to get this adjacent slot. If it returns a valid slot, we set the slot. We also keep track of the last empty spot we saw, just in case we weren’t able to find an adjacent location. Then, if we go through the entire board without finding a good spot with our get_available_adjacent function, we set the empty spot we found as a backup to be O. And with that, step 3 and 4 are complete.

And that also concludes the entirety of Rustic-Tac-Toe. Playing it results in a fun experience where the player wins most of the time; however, the difficulty can easily be increased by adding in checks for diagonal wins and by decreasing the probability of choosing a random location. The latter can be done by making two calls to the random-boolean chooser instead of just one. Something like this:

if !rng.gen() || !rng.gen() {
    // smart move
}
else {
    // random move
}

This would decrease the probability that a random move is taken and increase the difficulty of the AI.

I hope that you enjoyed this little tutorial! You can view the entire source of the project as a gist or download the entire project as a .zip here.