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:

Stanford AI Class

During the past few weeks I've been following the video lectures that Sebastian Thrun and Peter Norvig post every week, and that constitute their "Introduction to Artificial Intelligence" course.

I have to say that I love the course. Even if, as an AI researcher, I should know everything that they explain, it's nice to hear it again properly summarized and explained. What is more interesting about this course is that, given it's crazy amount of students (I've heard the count is about 160000!), it's generating lots of reactions among AI researchers. Some people love it, some people hate it. Here's my take on it.

I agree with many that the course is extremely biased (specially the machine learning part), and that only those techniques coming from probability and statistics are covered in the course. For example, the supervised learning module basically covers Bayesian learning, linear regression and nearest neighbor (and this last one is a nice addition!). This leaves out all the "search-based" machine learning methods (based on the idea of searching in a hypothesis space) like: version spaces or decision trees. This is an "introduction to AI" class, and I understand that they leave out the more fashionable topics like kernel methods. But I think that the search-based approach to machine learning deserves a module in this course. Whole fields (like inductive logic programming) come from this tradition of machine learning.

The same happens with the planning module of the course. Traditional introductory courses to AI use STRIPS planning to introduce the students to the idea of planning, and only tangentially touch on the problem of planning under uncertainty. However, this course does the opposite. Which is kind of weird. But here I don't have such a strong opinion as with the machine learning module.

Given the large number of students, and the strong bias of the course. Several AI researchers are actually angry at the course, since it's shaping the mind of a whole generation of potential AI researchers.

That said, I still think the course is awesome, and I follow it every week.

And I say this: all of those (and I include myself) who disagree with the way Sebastian and Peter teach their course should, instead of complain, just try to follow their lead and create an online course that represents their view of AI. Maybe we could even create a youtube channel for "missing lectures from the Stanford intro to AI course" :)

IEEE-CIG 2010

I recently attended the IEEE-CIG 2010 conference, which stands for the "Computational Intelligence in Games" conference, and I've to say, it was a very interesting experience. I've regularly attended AIIDE (the other game AI conference), but I had never been in CIG. I had the impression that the CIG environment was much more focused on games than in AI, and that made this conference really interesting from an AI researcher's point of view for the following reasons:

1) AI conferences are typically full with researchers (like me) that have a technique they believe in (case-based reasoning, support-vector machines,... you name it) and that are looking for problems they can solve with their technique. Typical "hammer looking for nail". In CIG it was the opposite. It was full of people explaining real problems they face in the creation of video games, and for which they were looking for solutions.
2) On top of that, given that a large proportion of the crowd were more game experts than AI experts, the range of AI techniques exhibited in CIG was quite narrow (as I will detail later). So, I think there are lots of opportunities for AI researchers looking for nails there.

Most of the papers presented some particular AI technique applied to some particular game. I did a rundown of all the 62 papers accepted and this is the histogram of AI techniques being used (not all papers were about AI, so the following numbers do not add up to 62):

- Machine Learning: 11 papers (3 on neural nets, 2 in reinforcement learning, rest on different techniques)
- Search: 7 papers (6 on game tree search)
- Planning: 1 paper
- Optimization: 18 papers (17 on genetic algorithms)
- Statistical: 3
- Game Theory: 2
- Logic: 2
- Scripting: 2
- Cognitive Approaches: 5 (2 on CBR/Episodic memory)
- Drama Management: 1
- Game Specific AI: 5

One quick observation is that there is a huge bias towards certain kind of approaches. For instance, there were 17 papers out of 62 talking about genetic algorithms. And out of all of the papers using some machine learning technique, the only 2 techniques to be used more than once were neural networks and reinforcement learning.

For instance, in one of the competitions held during the conference, the problem was to make an AI which would control a car, and be as fast as possible. The most successful approaches would first optimize a "race-line" using genetic algorithms, and then just have a hard-coded controller which would stick to that line when possible. The problem they faced is that driving a car is not just sticking to the race line: there are other cars in the game which have to be overtaken, etc. Thus, there are several behaviors that need to be modeled: sticking to the race line and overtaking. The AI community has solutions for these kind of problems where there are multiple competing behaviors, such as the subsumption architecture, or the more modern multi-agent bidding coordination mechanisms.

My conclusion is that we, as AI researchers, have a lot to gain by paying attention to places like CIG. On the one hand, we have the chance of contributing to the computer games community by bringing new techniques to the table, and on the other hand, the computer games community have a chance of contributing to the AI community by offering us challenging problems with which to push the limits of current AI techniques.

If anyone is interested, here's a quick list of the competitions that called my attention in CIG:

- Simulated Car Racing Championship: make an AI which races a car through a track with opponents as fast as possible. The problems involve both optimizing the trajectory, real-time control and handling unpredictable events (opponents). URL: http://cig.dei.polimi.it/

- Ms. Pac-Man Competition: create an AI agent which can play Ms. Pac-Man, problems: real-time decision making, non-determinism. URL: http://dces.essex.ac.uk/staff/sml/pacman/PacManContest.html

- Mario AI Championship: create an AI that can play Mario. In addition to the reactive control needed in Ms. Pac-Man, here you need high level planning, since there are levels which require some amount of puzzle-solving ability (e.g. you can only pass by first breaking some stones, and then jumping to a particular position, etc.). URL: http://www.marioai.org/

- The 2K BotPrize: a Turing test for first-person shooter bots, and with a cash prize! URL: http://botprize.org/

- StarCraft RTS AI Competition: if you think Chess is hard. Starcraft has a way bigger action and state space, it is real-time, and there is imperfect information. Good luck trying to create an AI for this! :) URL: http://ls11-www.cs.tu-dortmund.de/rts-competition/starcraft-cig2010

So, what's what I'd like to see next year at CIG? a more varied histogram of AI techniques, and a more varied set of entries to the competitions. I think this would provide a more interesting discussion and also help better understand which techniques are more suitable for which kind of game problems.

Chinese Room

Today I was reading once again about the Chinese Room argument by Searle (check out the wikipedia article which is pretty good). I always thought that the argument made no sense because Searle always argues that "it is obvious that the guy inside of the room does not understand Chinese", when for me it was "obvious" that it was the complete room and not any of its parts (like the human inside) who understood Chinese. Reading about it today, I discovered that my argument had actually been made before, and it's called the "systems reply". Searle had a very good response to the reply (in my opinion) consisting on imagining a new Chinese room, where the guy inside just memorizes all the rules in his head, so that there is nothing else but the guy. He claims it is obvious he still does not understand Chinese, and I have to admit that I'm having a hard time belying Searle here.

But far from admitting my defeat, I kept reading just to discover a new version of Searle's argument that he published in 1990, in which he "tries" to be more formal. His argument is constructed by three premises (that should be taken "obviously true"), and a direct conclusion from them:

(A1) Programs are formal (i.e. syntactic)

(A2) Minds have mental contents (i.e. they are semantic)

(A3) Syntax by itself is neither constitutive nor sufficient for semantics

Therefore:

(C1) Programs are neither constitutive nor sufficient for minds.

Well, I've to admit that if we assume A1, A2, and A3, then C1 follows quite nicely. However, let's look a bit at A1, A2 and A3. If you look at it with detail, A3 is the Chinese Room argument, and in most texts I've been reading refer to it as the only controversial one. However, looking at them with detail, I came to think that actually the one that is hard to admit for me is A2. What does it mean that minds use semantics while programs use only syntactics?

It seems to me that the big hole in both the Chinese Room argument and in Searle's new formulation is his assumption, without any more explanation, that "minds" are semantic. It seems to me that if we explain what do we mean by "minds are semantic", then we would be able to encode that in the form of a program. Thus, the key here is define semantics. If we take the logics definition of semantic as "mapping between two symbol systems", then minds are semantic because we have a "symbol system" in our minds, and we know the mapping between that symbol system and another symbol system, the real world. Thus, we "know" what the symbols in our mind mean. However, if we go that route, then a program running in a robot with sensors can do exactly the same, since its sensors can provide the bridge between his internal symbol system and the real world.

Digging more into articles in the internet, I discovered that my previous argument has also been made before and it's called the "robot reply", to which Searle replies that a robot would only convert the inputs to its sensors into symbols and then just use syntactics with them. Thus, not achieving semantics. Well, I would reply two things: first, humans do the same (we map our senses to neuronal impulses and then operate with those); and second, and most important, Searle is only trying to defend A3, while I'm actually attacking A2.

Conclusion: after trying to find why Searle's Chinese room argument was wrong, I realized, that the Chinese room might be wrong or right, it does not matter, since the key question here is whether minds are semantic or also syntactic like computer programs. Until someone proves me wrong, from today I'm convinced the human mind is also purely syntactic. Thus, I don't think semantics is required for intelligence (if we assume that humans are intelligent, of course :)).