Open Thread: December 2009

CannibalSmith

ITT we talk about whatever.

I intend to participate in the StarCraft AI Competition. I figured there are lots of AI buffs here that could toss some pieces of wisdom at me. Shower me with links you deem relevant and recommend books to read.

Generally, what approaches should I explore and what dead ends should I avoid? Essentially, tell me how to discard large portions of porential-starcraft-AI thingspace quickly.

Specifically, the two hardest problems that I see are:

Writing an AI that can learn how to move units efficiently on its own. Either by playing against itself or just searching the game tree. And I'm not just looking for what the best StarCraft players do - I'm searching for the optimum.
The exact rules of the game are not known. By exact I mean Laplace's Demon exact. It would take me way too long to discover them through experimentation and disassembly of the StarCraft executable. So, I either have to somehow automate this discovery or base my AI on a technique that doesn't need that.

There's some discussion and early examples here: http://www.teamliquid.net/forum/viewmessage.php?topic_id=105570

You might also look at some of the custom AIs for Total Annihilation and/or Supreme Commander, which are reputed to be quite good.

Ultimately though the winner will probably come down to someone who knows Starcraft well enough to thoroughly script a bot, rather than more advanced AI techniques. It might be easier to use proper AI in the restricted tournaments, though.

10Johnicholas17y

I have some advice. 1. Pay attention to the timing of your edit/compile/test cycle time. Efforts to get this shorter pay off both in more iterations and in your personal motivation (interacting with a more-responsive system is more rewarding). Definitely try to get it under a minute. 2. A good dataset is incredibly valuable. When starting to attack a problem - both the whole thing, and subproblems that will arise - build a dataset first. This would be necessary if you are doing any machine learning, but it is still incredibly helpful even if you personally are doing the learning. 3. Succeed "instantaneously" - and don't break it. Make getting to "victory" - a complete entry - your first priority and aim to be done with it in a day or a week. Often, there's temptation to do a lot of "foundational" work before getting something complete working, or a "big refactoring" that will break lots of things for a while. Do something (continuous integration or nightly build-and-test) to make sure that you're not breaking it.

3rwallace17y

Great! That competition looks like a lot of fun, and I wish you the best of luck with it. As for advice, perhaps the best I can give you is to explain the characteristics the winning program will have. It will make no, or minimal, use of game tree search. It will make no, or minimal, use of machine learning (at best it will do something like tuning a handful of scalar parameters with a support vector machine). It will use pathfinding, but not full pathfinding; corners will be cut to save CPU time. It will not know the rules of the game. Its programmer will probably not know the exact rules either, just an approximation discovered by trial and error. In short, it will not contain very much AI. One reason for this is that it will not be running on a supercomputer, or even on serious commercial hardware; it will have to run in real time on a dinky beige box PC with no more than a handful of CPU cores and a few gigabytes of RAM. Even more importantly, only a year of calendar time is allowed. That is barely enough time for nontrivial development. It is not really enough time for nontrivial research, let alone research and development. In short, you have to decide whether your priority is Starcraft or AI. I think it should be the latter, because that's what has actual value at the end of the day, but it's a choice you have to make. You just need to understand that the reward from the latter choice will be in long-term utility, not in winning this competition.