Game of Tron - AI
Image courtesy: http://blog.expertte.com
This was my very first attempt at the participation in any sort of AI challenge. The contest was organised during the techfest of Netaji Subhas Institute of Technology in 2011. The objective being to develop the AI for the Game of Tron.
Being my very first attempt, I started using a very basic approach of using random movements avoiding obstacles, just to see how it performs. Needless to say the AI would curl and crash into itself within a few turns. But watching a code execute in real time and seeing how it performs was exhilirating in its own ways, and sort of boosted me to develop a better code.
My next approach was to figure out a way so that the AI does not take a turn to reduce the number of steps it can take in the future. For this I required an optimum algorithm to find the number of moves I can currently make. Being a fresher I was unaware of any algorithm and had to dig a lot. In the end I found the Flood-Fill algorithm generally used to fill a closed space with the given value. With this in hand I implemented the AI such that the next move it makes is the best such that the number of steps allowed to take in the next move is being maximized.
This was a good start, and felt great seeing the new and improved AI beat the previously developed random AI. My next aim was to include something that would think a few steps ahead and suggest the best possible move. To do this I used the Min-Max theorem along with the Flood Fill and Voronoi Heuristic(Again a lot of research on Game Forums and Wiki pages). I used the number of spaces left after making the current move as a reference to how good the move is. Using a breath first search until time limit exceeded, I selected the best possible move . On an average, the algorithm was able to see up to 10 moves ahead. A little slow given the number of moves in each step is only 3.
This algorithm got me the 3rd spot on the rank ladder during the contest.