We, as game theory enthusiasts, decided to tackle the seemingly most innocent two player game of all: Tic Tac Toe. Played billions of times by casuals and enthusiasts all over the world, each game has 255,168 unique endings. This provides for a very complex, recursive algorithm that will find the best move given any position.
Allows a user to practice their Tic Tac Toe skill by
- observing pro-level AIs play against each other
- practicing against pro and easy AIs
- practicing with other humans
Using a combination of experience, research, and logical deductions, our team designed and created an interface to allow for the interaction of neural networks and applications to assist in the training of the neural networks.
A major and the most significant challenge our team faced was in the creation of the logic of the Impossible Bot. To put it simply: we didn't know where to start. But, our team was able to put our heads together and collaborate to come up with a solution: the minimax algorithm, implemented with alpha-beta pruning to improve efficiency.
The Impossible Bot is an AI that implements the recursive minimax algorithm and alpha-beta pruning to determine the best move given any position.
Over the course of the creation of our application, our team not only learned a lot about 2 player game theory, but we also learned about the best methods of collaboration. We learned about the importance of sharing our ideas, and how to take the best of all the ideas presented.
If our team had more time, we would create another interface (i.e. web) to enhance the user experience. Also, we would create an API, so that our Impossible Bot could be shared with the world. Lastly, we would expand on the training aspect of the program, so that people could improve their game over time, and maybe one day, become as good as the Impossible Bot.