Game Tree Search for RTS Games

Thanks to the Starcraft AI competition, and after a conversation with my PhD student (Alberto Uriarte), I recently started thinking about applying game tree search (the family of techniques used to play Chess and Go) to RTS games.

The main problem is that standard game tree search techniques, like minimax, of alphabeta search, assume turn-taking, fully-observable, deterministic games. However, RTS games are real-time, partially-observable and non-deterministic. Additionally, RTS games have a tremendous branching factor (exponential with the number of units in the game at any given time). For that reason, those techniques cannot be applied directly. I decided to go step by step, and address only one of the problems: the fact that RTS are real-time.  This problem can actually be subdivided in 3 more basic problems: actions are durative, players can execute actions simultaneously, and there is not enough time to do search (each game cycle is only a few milliseconds).

I developed a simple variation of minimax (that I called RTMM, for Real-Time Minimax) that was designed to address the first and the third of those three (durative actions and not enough time to do search), and wrote a quick paper with it for the AIIDE conference. Unfortunately, I guess I wrote it too hastily and got rejected :)  Funnily enough, there was another paper submitted to the same conference with the same idea, but the other authors had also tackled the problem of simultaneous actions, so I guess it's just fair that their got accepted instead :) However, even if that paper is now unpublishable, I still think it's an interesting read, so I uploaded it to Arxiv for the records ( http://arxiv.org/abs/1208.1940 ).

In order to test my algorithms I created a very simple RTS game, that I call microRTS, and made it open source in Google Code. microRTS is designed just to experiment with real-time game tree search, so it is still deterministic and fully-observable. Since then, I've been toying with techniques to address the extremely large branching factors that arise in these games (it's not rare for a state to have several million possible moves). I plan to write a paper soon with my findings. But meanwhile, microRTS is out there and if anyone is interested in using it for research, just send me an email, and I can provide support. In the SVN repository I included about a dozen AI techniques prebuilt with the game (most of them based on game tree search, or in Monte Carlo sampling), so you can easily test how good is your AI.

Here you can see a screenshot of microRTS in a small 8x8 map: