These planning algorithms are pretty cool, and they got me thinking about AIs in RTS tournaments. RTS games seem like a perfect fit for human/computer pairs. Automation would completely change micro. The computer reacts instantly, has perfect accuracy, and never gets tired or distracted. It would enable tactics that no human could perform unaided. The human would have fewer distractions while making strategic decisions that current RTS AIs are terrible at: Where to build, where to mass units, defense placement, etc.
I looked around a little, but didn't find any StarCraft-equivalent to Advanced Chess[1]. If such a thing doesn't exist, it's a shame. The combination of better strategy and ludicrous APM would completely change gameplay.
Well, there was no GUI involved, but such man machine hybrid wars did often occur in MUDs, particularly ones with player killing and guilds. You would often have a set of alts controlled by scripts doing automated tasks like crafting iron from ingredients and selling it in town whereas meanwhile in combat you would have the mud client automatically drink health potions when low on health, auto attack when an enemy player walked in, etc..
I think World of Warcraft had a similar bot getting popular before it was banned.
The Iron Realms MUDs have a combat system that's so complex and demanding on reaction time that you can buy (with real world money, from other players) full curing systems that track how fast you can cure things, how close you are to inflicting limb breaks on your opponent and all sorts of other stuff.
The problem with this type of planning is that it is not nearly powerful enough to address real problems in Starcraft (except for the given examples) because:
-discreteness: Well, I think it's safe to assume that every starcraft state is discrete (for sure it's binary representation is) but in general you cannot assume it.
- imperfect information: For planning, it's necessary to know or meaningfully guess the state of the enemy and that is not possible due to fog of war. Therefore, everything involving enemy interaction cannot be planned.
- dimensionality: There are so many actions available at each state that you shouldn't even be able to reach a depth of 3 of the planning tree in a reasonable amount of time. For instance, if you have 50 units, you can send each subset of them to attack or move to say 128x128 points on the map, you end up having 2^50 x 16k x 2 possible moves.
And that doesn't include build units, build buildings + some more exotic stuff like patrol, set rally points, ...
You can prune some stuff (e.g., never attack with peons after minute 10, never move to or attack your own buildings) but the order of magnitude should stay the same.
So planning is nice but not for continuous problem spaces (real world), problems with imperfect information (every good card game) or problems with a high number of actions (something as "easy and simple" as Go), rendering it IMO not so useful after all.
Planning is only one of the solutions you need for an RTS AI. Exploring a tech tree and having a ordered list of actions + cost is quite useful. Also, a fast planner can run every turn or more often with updated information and may e.g. output an attack plan with the units needed to eliminate a given enemy structure.
Processing 2^55 moves is not really needed to win a game. At least I believe a human brain uses a different approach. And an AI which wins on average only every second game is just right. Who - honestly - has fun with an unbeatable AI?
Well, it would have to beat a human's micro first.
Remember, it's not just doing predictable actions every time. A lot of it is dancing back and forth and trying to bait your opponent.
So an AI might say "focus firing a stalker is the most efficient" and the human player blinks it away. Then it chooses the next target and the human player blinks that away as well. And so forth until the human player runs out of healthy stalkers and simply walks away with hurt stalkers having done enough damage.
The "correct" solution might have been actually to run past your opponent's army and to surround it spreading the damage. Even when you blink out you're still close to the enemy army because of blink's range.
There could be a mathematical model that predicts whether to run past or to attack or to stutter-step, but humans do this based on experience. AIs are not close to this level of sophistication.
I think this is exactly the kind of situation that GP had in mind. A computer would be undoubtedly faster and more accurate concentrating fire on the weakest stalker, but a human is better at deciding whether to attack now or move into position.
So instead of 'attack this unit,' the player could command his units to 'attack the weakest stalker in range.' Or even, 'stutter step along this path, concentrating fire on the weakest anti-air unit.'
yeah, for kiting/splitting a bot can just do this easily
now think what the bot would have to do if it's controlling the banelings KNOWING that the other person is going to control the marines away and it's not as simple
Don't forget that the AI already does things like shoot and pursue. Your AI could do other things, but it is not clear exactly what. Starcraft 1 has a lot of micromanagement tricks, for example shooting while moving, that appear to be deficiencies of the game engine. I think there is motivation to view such tedious tasks as limitations or the game engine rather than the AI, unless off course you like that sort of thing!
Don't get me wrong, I find it very cool that people try to popularize STRIPS planning among programmers and that automated planning gets more known. However, please don't say that you can "solve" Starcraft this way.
To get a decent starcraft AI you will need more than the ability to make plans to build battlecruisers: you will need the ability to choose the best plan for the recognized situation, to take decisions under uncertainty and to make compromises between objectives.
For chess to be called "solved" you would need to have a winning strategy for every winnable position. The same is true for Starcraft.
What this person provides is a (very non-optimal) algorithm to build anything within the tech tree of starcraft, but building is just one part of the game, and the only easily pannifiable one.
Interesting. Although going over an abstract representation harms the performance in a RTS game. I finally chose Nau's HTN planner to plan entire villages in a few milliseconds. The core in JavaScript fits on one screen page:
I'm very happy that another guy got interested in AI and is backing it up with some code. Keep up the good work! But maybe join a free web AI course if you are really interested in this topic. A* on a decision graph is really an old thing for AI. Sorry to disappoint. It's one of the things you do for homework if you visit an AI course.
A few people have made genetic algorithm programs to calculate optimal (in terms of speed) build orders given certain conditions. Here's one I have used: https://code.google.com/p/evolutionchamber/
A genetic algorithm, of course, is much different than using AI to solve the problem, but I think it's an interesting project nonetheless.
I suspect it has to do with the definition of "Optimal" in this case. It has likely been defined as "least number of steps". It would be cool to see how it would play if the goal was changed to "shortest amount of time".
I looked around a little, but didn't find any StarCraft-equivalent to Advanced Chess[1]. If such a thing doesn't exist, it's a shame. The combination of better strategy and ludicrous APM would completely change gameplay.
1. http://en.wikipedia.org/wiki/Advanced_Chess