After watching the AlphaGo documentary, I was determined to set foot in the world of gaming AI.
I created a simple program with if-else statements for a Tic-Tac-Toe game. Knowing that such an algorithm wasn't foolproof, I began to do more research on an undefeatable sound program. With further research, I learned about the importance of having a model for your game, which led me to build a game tree for my scenario. Using OOP, I created a model class for my gameplay, allowing whatever algorithm I deploy on top of it to have a well-managed space complexity. With this, I could apply Breadth First Search to traverse through the tree to find the most efficient way for AI to win. Knowing there are even more ways to improve run time, I explored fast searching algorithms, like MiniMax and A*. I chose to go with A* and Minimax, as they had the smallest space complexity and allowed the computer only to keep track of things that matter.
Now that I have developed my ultimate algorithm, I understand how to set up an efficient AI. It was time to apply this knowledge to games other than Tic-Tac-Toe. Here is an application of my work in a 8-sliding puzzle