Github:
https://github.com/ResponsiveWebApps/TicTacToe
Introduction
The purpose of this project is to create a game of tic tac toe with Python. The game will allow one human player to play against an algorithm. The game takes input from the player and prints the new board with the player’s marker. The game is text-based and can be run in either Gitpod, Visual code, Command Prompt, or a Linux terminal.
I started my project backwards. First, I coded a tic tac toe game in Python and I used a function to randomly place the AI’s marker in an empty position. Then I researched various algorithms that be used to play tic tac toe. After exploring a machine earning option, I choose to go with the minimax algorithm for tic tac toe. Then I discovered that the way I had coded my game was not appropriate for the algorithm needed.
The essential lesson I learned here was that it is better to research and plan a project before creating a program. This report will describe how I created the random AI and why the minimax algorithm is better.
Random AI
In my first attempt, I created a tic tac toe game with Python that used a randomly selected number from zero to create the AI player’s marker position. I stored the positions of markers in a list. The positions start as “ “ then are replaced with integers. This list is reset back to a list of “ ” after each game.
markers = [" ", " ", " ", " ", " ", " ", " ", " ", " "]
In the form of one if statement, sixteen different win conditions were searched for in the markers list. If one of these conditions were met, either the human or AI player wins.
My function then double-checked that the position was empty. If the position was already taken, another position for the marker was randomly selected until an empty position was chosen.
aiMarker = random.randrange(0,8)
while markers[aiMarker] == "X" or markers[aiMarker] == "O":
aiMarker = random.randrange(0,8)
The result was a game of tic tac toe that was very easy to beat. Since the human can make strategies and AI does things at random, the human wins most of the time. I even found it hard to make a draw.
Minimax algorithm
The minimax algorithm works by creating a decision tree of possible moves. One player is selected to maximize their winning, in our case, the AI, and one player is chosen to minimize their ability to win, the human player. The minimax algorithm can be used for zero-sum games such as chess or go. However, the size of the decision tree for chess or go would be much larger than the options for tic tac toe.
Depending on the state of the board, the algorithm calculates the best to make to maximize chances of winning the game and minimising the chance of losing. The AI is trying to reach the score of +1 and avoid the score -1. 0 is considered a draw. As a series of moves are made, the algorithm travels down the depth of the tree until it reaches its goal. The algorithm selects positions that increase its chance of winning the game, thus scoring +1. When the depth is equal to 0, it means that the game has been won or a it is a draw. The depth value is basically the number of moves needed to win.
When I tried to implement the algorithm, I realised that I needed to change the list I used to a list that looks more like a 3x3 matrix. This meant I had to make a lot of changes. Everything from the win conditions to how the markers were positioned had to be recoded. First I tried implementing the same algorithm used in the project titled ‘’, and in the end, the majority of the code was borrowed.
I managed to keep some game features that I liked, such as the design for the board. To make the game more friendly, I give the human user a list of empty positions available for selection.
Conclusion
The end result was an unbeatable game of tic tac toe. No matter if the human starts or not, the AI will either win or most of the time gets a draw. My two attempts of creating a game of tic tac toe show that the minimax algorithm is more efficient than the AI just playing randomly.
References
Github, (2021). tictactoe_rand.py. [online]
Available at: https://github.com/ResponsiveWebApps/TicTacToe/blob/main/tictactoe_rand.py
[Accessed 4th April 2021].
Github, (2021). tictactoe.py. [online] Available at: https://github.com/ResponsiveWebApps/TicTacToe/blob/main/tictactoe.py
[Accessed 4th April 2021].
Github, (2020). tic-tac-toe-minimax. [online] Available at: https://github.com/Cledersonbc/tic-tac-toe-minimax
[Accessed 4th April 2021].
Pair with Google, (2020). Tic-Tac-Toe the Hard Way. [online] Available at: https://pair.withgoogle.com/thehardway/
[Accessed 4th April 2021].