The goal of this repo is to make an artificial intelligent program face off against humans in a game of Tic Tac Toe.
python3 main.py
The minimax algorithm was very robust in my initial implementation, however, when trying to implement the same algorithm on a 3x3x3 board, the algorithm would hang on trying to compute all possible moves the computer and a player playing optimally could make. This is usually the case when using minimax, minimax can be applied to database systems, expert systems, robot control systems, and theorem-provers but usually has to be adapted to handle the large state space that accompanies the problem at hand. When trying to reduce the number of nodes to traverse in a tree, a common solution is to prune your tree while traversing. As anyone who knows MiniMax would suggest, the solution to this problem would be to use Alpha Beta pruning. As S. H. Fuller, J. G. Gaschnig and J. J. Gillogly state, "Alpha-beta is faster than mini-max because it does not explore some branches of the tree that will not affect the backed-up value". Alpha Beta pruning also utilizes the depth of the recursive function, allowing you to limit the amount of computation you've deemed neccessary for your AI making it perfect to adapt and test the level of diffuclty the AI can have.
I chose python because the simplicity of the syntax and the robustness of python's variable typing. Python's portability and readability makes the showcase of my code as easy as possible to demonstrate on different environments without the hassle of making sure the environment has the correct requirements beforehand. Before I could implement anything, I had to set up how the game would be playable. To begin, I had to create a board. My representation of the board is an array of 3 tic-tac-toe boards where each index represents a layer in the tic-tac-toe cube. For example, when the game starts you are shown the state of the board with the computer making the first move.
The next step to building the game was detecting if the board at hand is in a winning state. Win states include any win state for each layer, treating the layer as a traditional game of tic-tac-toe, and win states across the Z axis. To detect if the board is in a win state, I use the checkWin() function that I created. The last part of setting up the game was creating a checkScore() function that returns the 3 if the computer is in a win state, or a -3 if the opponent is in a win state. If neither player is in a win state, the function returns a 0. After all the inital setup, the MiniMax algorithm with Alpha Beta Pruning was ready to implement.
The algorithm is looking 3 moves ahead, alternating between its best possible moves and the oponents best possible moves. To make the tree prune, I use the recursive depth to penalize moves that are further ahead. For example, with the traditional minimax algorithm the computer could have a move that ensures a win thats 10 moves ahead, or a win thats only one move away and the computer could pick the move that is 10 moves ahead instead of grabbing an immediate win. To prioritize the closer moves, I ensured the score was higher if it was less deep than the other possible move. As soon as the algorithm sees a win state, I return the score and prune the other possibilities, since a win state is the most prioritized possibility. Doing this fixed my problem from the traditional game of tic-tac-toe where if the player does not play optimally, the computer would pick seemingly random moves instead of winning.