PYTHON Tic Tac Toe PART 3: The Visualizer

Link to GitHub

Update on CPU: Mega Difficult

First and foremost, I need to explain the update on CPU: Mega Difficult mode. After two days of being stumped on why my minimax algorithm was not behaving optimally, I realized my base case was what was screwing up the recursion. I was only accounting for terminal states where the grid was full. This was my previous code for my base case within the minimax function:

if len(board.get_empty_squares()) == 0:
            winner = board.check_winner()
            if winner == player_MAX:
                return (1, None)
            elif winner == player_MIN:
                return (-1, None)
            else:
                return (0, None)

This was incorrect for the purposes of TicTacToe as this conditional is only checking for when the game board is full. However, I should have been checking for whenever there is a end game state, such as situations where the game is over but there are still empty squares. I overlooked this small detail causing much confusion as to why my algorithm was not working as expected. In order to fix it, I had to switch the conditional to the following:

if len(board.get_empty_squares()) == 0 or board.check_winner():

This checked if the number of available squares was 0 OR if there was a winner returned from the check_winner method of the board class.

Additionally, I added alpha beta pruning to speed up the algorithm exponentially! This was done by passing in an alpha representing a maximum and a beta representing a minimum. This enabled branches of the game state that were insignificant to be pruned, resulting in less recursive calls to minimax. I decided to leave CPU: Difficult as the old algorithm to let the user play against a CPU with some minimal strategy. However, I made CPU: Mega Difficult the new, correct algorithm and it cannot be beat, only tied an infinite number of times at best.

The Visualizer

I created a ‘visualizer’ in order to simulate multiple games and demonstrate the consistency of a Random CPU and a Smart CPU. I reimplemented my TicTacToe functionality in a python script without pygame in order to quickly simulate games and collect the results of those games. I built this script using classes called Board, Player, RandomCPU(Player), and SmartCPU(Player). These classes coupled with the fact that I am not using the pygame GUI has helped make everything much more modular and easy to work with. I can simulated thousands of RandomCPU vs RandomCPU games in seconds. I can simulate hundreds of Smart CPU games in seconds as well. It usually takes somewhere between 4-7 seconds to simulate 200 Smart CPU games.

TicTacToe Main Menu

Here are some actual visualizations of the data generated from the visualizer code using matplotlib.pyplot.

TicTacToe Main Menu
TicTacToe Main Menu
TicTacToe Main Menu
TicTacToe Main Menu

Hiccup in the Code

Weirdly enough, the Smart CPU vs Smart CPU produces interesting results. At first it seems normal because the games are split nearly even with Smart CPU Anastasia winning 101 games, Smart CPU Francesca winning 99 games, and no CATs. But when the parameters are reversed the results are staggeringly different: 200 CATs and no wins for either Smart CPU.

It gets worse.

When I run the Smart CPU vs Random CPU instead of Random CPU vs the Smart CPU (i.e. I reverse the parameters to the simulation function), the following are the results:

TicTacToe Main Menu

Clearly, the minimax algorithm is beatable given those results. Or is it? I really dont think it is beatable but clearly something is wrong with my visualizer code. I am not quite sure what it is but I have a feeling it has to do with the way I am simulating the games rather than the minimax algorithm behaving incorrectly. While it is time for me to move on to another project, I hope to one day revisit this issue and learn why reversing the parameters causes such a fuss…

Conclusion

This was a fun experience getting my hands on pygame after not playing with it for several years. I also gained some practice implementing a real machine learning algorithm into a real GUI application. I was humbled by the importance of the small details in programming and I gained a higher appreciation for the game most commonly played on restaurant napkins, the game of TicTacToe.

Remember to check out my code if you find this project interesting and want a closer look.

Link to GitHub