The final deadline for the Google AI Challenge has passed. The results won't be posted until Monday, as there are about 800 bots that will have to play against each other to determine a winner. One thing is for sure, I know mine won't be anywhere near the top, but it shouldn't be too close to the bottom either.
Since no more submissions can be made at this point I will release the full Java code of my bot as I promised in an earlier post about the contest:
Basically my bot operates by doing a flood fill to measure the number of free spaces in each possible direction. Then it always moves in a direction that leads it to more free tiles. If there is a choice between moves which have the same number of free tiles it tries to move toward the opponent. If it is within a few tiles of the opponent it begins following a set of complex rules to try to stay parallel to the opponent and just ahead of it, so that it can cut the opponent off and box it into a smaller room.
This bot works fairly well, but it has no foresight because it evaluates each move as it goes. I tried to implement a tree based bot which analyzes the value of different choice, but sadly I was not able to get it to perform better than my previous bot. I programmed it in C++ to take advantage of speed so that I could explore more of the game tree:
The main problem with a tree based bot is that it is only as good as the score values that can be assigned to a particular game state. Basically it is supposed to explore down the tree of possible moves, thinking several moves in advance to try to find the most optimal solution. But to do this it has to be able to assign an accurate score to a particular move, to measure whether it is a good or a bad move. In all of my test I was never able to get the weighting down right so that the bot was smarter than my previous Java bot. I'm not sure if it was a bug in my code, or just something that I was missing.
Conclusion
The Google Tron bot AI challenge has been a fun learning experience that has taught me a lot about the way AI works. Being mostly a web designer I have almost no background in AI, so it was a completely different way of thinking for me. If I am working with a database application, or a website, or some other coding problem I can easily see and plan exactly what I need to do to solve the problem. With AI this was not the case. As I was programming this bot there were times when I knew what I wanted the bot to do but I wasn't sure what code to write to get it to do what I wanted. I had to do research, study new algorithms, and think in different creative ways.
I think working on the bot was a healthy programming experience because it has definitely piqued my interest in AI. I would like to thank Google and the University of Waterloo Computer Science Club for providing this fascinating contest. I look forward to the results on Monday.
No comments:
Post a Comment