Code is modeled after real life

When implementing a tic-tac-toe account to play against itself we need to teach the program that not all move positions are created equal. Ideally, our goal is to have an AI vs. AI game always result in a tie. The hardest part of building this AI feature is visualizing the moves available step-by-step. I found it useful to draw out the table on a piece of paper as seen here >>>

The AI Strategy

We know that the winning position combinations are as follows: WINCOMBINATIONS = [ [0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [6,4,2] ]

The goal of each player is to choose your next move where said move is included in as many win combinations as possible because this will allow us to ensure the max amount of winning moves will still be available for our next turn. Another way of thinking about this problem is to count the occurrences of each number in the win array because this count represents the probability that said move could bring the player closer to winning.

Probability of Winning: moves_by_win_frequency

moves_by_win_frequency = {4=>4, 8=>3, 6=>3, 2=>3, 0=>3, 7=>2, 5=>2, 3=>2, 1=>2}

Above we create a hash of all possible moves sorted in descending order by their number of occurrences in the winning combinations array. Based on this hash it appears that move index 4 (choose “5”) appears 4 different times in the winning combinations while no other possible move has as many occurrences. So IF this position is available it provides us with the highest chance of winning and we should always have our AI move there.

The Best First Move

moves_by_win_frequency = {4=>4, 8=>3, 6=>3, 2=>3, 0=>3, 7=>2, 5=>2, 3=>2, 1=>2}

*Remember: Key = move_index, Value = possible_wins

We can tell that choose “5” (position 4) is included in 4 different possible winning combinations.

• Horizontal Win: [3,4,5]
• Vertical Win: [1,4,7]
• Diagonal Left Win: [0,4,8]
• Diagonal Right Win: [6,4,2]

The Second Best Move(s)

moves_by_win_frequency = {4=>4, 8=>3, 6=>3, 2=>3, 0=>3, 7=>2, 5=>2, 3=>2, 1=>2}

Each of these four positions have equal probability of winning with 3 winning combinations each.

• Move 8 (choose “9”) Wins: [6,7,8], [2,5,8], [0,4,8]
• Move 6 (choose “7”) Wins:  [6,7,8], [0,3,6], [6,4,2]
• Move 2 (choose “3”) Wins: [0,1,2], [2,5,8], [6,4,2]
• Move 0 (choose “1”) Wins: [0,1,2], [0,3,6], [0,4,8]

Let’s create an array containing all of the best second moves as seen below

The Worst Move(s)

moves_by_win_frequency = {4=>4, 8=>3, 6=>3, 2=>3, 0=>3, 7=>2, 5=>2, 3=>2, 1=>2}

Each of these four positions have equal probability of winning with 2 winning combinations each. Making them the least valuable moves on the board.

• Move 7 (choose “8”) Wins: [6,7,8], [1,4,7]
• Move 5 (choose “6”) Wins: [3,4,5], [2,5,8]
• Move 3 (choose “4”) Wins: [3,4,5], [0,3,6]
• Move 1 (choose “2”) Wins:  [0,1,2], [1,4,7]

Let’s create an array containing all of these least valuable moves as seen below.

Bringing it all together

Now that we have a good understanding of probability that any given move will result in a win we can use this information to implement our AI in numerous ways following the thought process outlined below.

Recursively Choosing a Move

1. Check if first_move is available => move there if it is
2. Else check if any second_best_moves are available => pick one and move there if there is one
3. Otherwise pick an available least_valuable_moves

If you’ve implemented this AI vs AI algorithm properly your game will always result in a tie.

Cat’s Game!

via GIPHY