Another update from the world of academic StarCraft AI! Here is a video demonstration of the results from our paper:
"Fast Heuristic Search for RTS Game Combat Scenarios"
We use a new algorithm (ABCD - Alpha Beta Considering Durations) to plan all unit actions you see being performed. The search is allowed to run for 50ms per frame in order to simulate real-time performance. There is *NO* human input or hard-coded scripting being used. All actions are being decided intelligently in a similar manner to how chess AI systems work. The reason this problem has been so hard is two fold:
- Extremely high branching factor for search (ie: an exponential number of possible simultaneous actions) - Limited resource budget (50ms per decision, vs. many seconds or even minutes given to a game like chess)
Unit HP bars are shown above the units, as well as larger versions in the top-right corner. The red units are controlled by search, while the blue units are controlled by the default "attack closest unit" behaviour which is default to the StarCraft built-in AI. Initial starting positions for units are generated randomly, but symmetrically to guarantee fairness.
Shown is our combat simulation visualizer. Due to some issues with unknown unit behaviour in StarCraft, it is not yet possible to carry out perfect action execution in the game itself, so we showcase its performance first in simulation. Soon we'll be incorporating this into our AI bot "UAlbertaBot" which came 2nd place last year at the 2011 [AIIDE StarCraft AI Competition](http://www.starcraftaicompetition.com).
- Why is this new?
This is new because every other micro system so far (including those in BW, SC2, and the AI competition) has been performed using hard-coded human knowledge, or with incredibly long rule-based scripts. With this system, I can simply throw any units at it and it figures out the best moves on its own.
- Why does the script win sometimes?
In the examples I recorded, the blue player (script) does win sometimes. This is due to the nature of the randomly generated positions, as well as the visualization eating up some of our processing time. In our paper, our method beats the best scripts used from the 2011 StarCraft AI Competition over 80% of the time.
What does it actually evaluate? Does it try to play the battle to the end, or just find a strategy that gives a good position some time into the future? Then how does it evaluate the strength of a position? Are you using (or plan to add) heuristics? Would the winning ratio improve if the algorithm was allowed, say, 100x more computation time? How does the algorithm scale with the number of units?
I was a Flash fan before it was cool | Coiner of "jangbang"
Zhyq United Kingdom. July 05 2012 07:38. Posts 113
Is the search parallelized to run on multiple cores? If not, is it possible to do it and, if yes, would you expect significance improvements (i.e. how limiting is this 50ms limitation).
On July 05 2012 07:08 okum wrote: What does it actually evaluate? Does it try to play the battle to the end, or just find a strategy that gives a good position some time into the future?
It is trying to decide the best 'next move' that it can perform. This is, when a unit (or multiple units) finish an attack or move command, what is the next best thing they should do?
Then how does it evaluate the strength of a position? Are you using (or plan to add) heuristics?
We use two methods to evaluate a position. The first is: for each player, sum the square root of their unit hit point remaining, multiple this by their damage per frame, and then divide this by the starting total for this value. This gives us a number between 0 and 1 indicating a heuristic 'strength' of our original force.
The second is through scripted play-outs, similar to monte carlo simulations, but deterministic. We use a script to guide actions from a leaf node in the search, and then use the above formula to evaluate the end state of the scripted simulation.
Would the winning ratio improve if the algorithm was allowed, say, 100x more computation time? How does the algorithm scale with the number of units?
We do get better results if we allow for more time, but I don't have exact numbers for you. Right now we are able to do search up to 8 vs. 8 units, due to the exponential branching factor of the problem. For example, if we allow Attack, Up, Down, Left, Right movement for 8 vs 8 units, and all units are within range to attack each other, the branching factor (number of combinations of possible moves for one player) is 12^8.
On July 05 2012 07:38 Zhyq wrote: Interesting stuff. Is the paper available to read yet? If not, when is it expected?
I can't release the paper yet, since it has just been accepted to AIIDE 2012, but the camera-ready version hasn't been submitted. However, the paper improves on results from this paper, written by my supervisor:
On July 05 2012 08:17 JustPassingBy wrote: Is the search parallelized to run on multiple cores? If not, is it possible to do it and, if yes, would you expect significance improvements (i.e. how limiting is this 50ms limitation).
Any sort of parallel techniques that could be applied to alpha-beta (which are quite tricky) could be applied here, however with only 2 cores available to us during the AI competition, we may not benefit very much from it.
50ms is incredibly short amount of time, but for example we are able to look-ahead up to about 20 moves in the future in 2v2, or 5 moves in the future in 8v8 using this technique.
undyinglight United States. July 05 2012 13:48. Posts 588
As a developer, I find this really cool. Please open-source your efforts after the competition?
We are just an advanced breed of monkeys on a minor planet of a very average star. But we can understand the Universe. That makes us something very special.
Cool. I can see space for improvement though. Some dragoons die since they almost have no health. They could have been saved if they had moved further away and avoid damage.
"My sister is on vacation in Costa Rica right now. I hope she stays a while because she's a miserable cunt." -pubbanana
snakeeyez United States. July 06 2012 08:48. Posts 754
Always cool to see brood war bots get better. I wonder also about moving the weak goons to back or can it handle different combinations of units? Speed might be a problem once you get late game with huge battles those tree searches are going to get slow but again I always said you never have enough CPU in AI problems.
AcrossFiveJulys United States. July 06 2012 11:05. Posts 3593
Are you doing the search individually for each agent? It seems that considering friendly units around would be important, and its importance would scale with the number of units and unit combinations involved.
Regardless, this is cool, but I think using a search method to select individual actions is a dead end if your long term goal is to produce an intelligent sc player. There needs to be an element of learning involved combined with abstraction so that you are planning with (learned) higher level behaviors. In other words, I think your goal should be to produce a behavior/policy which is able to decide what to do in particular micro situations without needing to plan in real time.
So I would suggest forgetting about the 50ms ceiling you're imposing. You are essentially using a brute-force search method and you can't expect it to scale well. I think your method would be useful instead for producing examples of perfect micro behavior (especially if you cranked up the ceiling to minutes) which you could then feed through a learning algorithm (such as a supervised learning algorithm, or apprenticeship learning, etc) which would then be able to make decisions in real time, and can be used by a higher level AI which does more than just micro a single battle.
This should work for normal units but i can image it becoming extremely complex with units that have special effects, i.e. SC2 broodlords (broodlings), BW/SC2 carriers (interceptors), SC2 marauders (slow), BW Reavers (Scarabs) as well as active unit abilities (SC2 ghost snipe, BW marine/SC2 marauder stim, ...).
Good luck implementing that into the Starcraft AI.
Last edit: 2012-07-06 15:16:42
"Remember kids, the 3 most important things for becoming a good player: Micro, Macro and always take your Dailies!" - Rastaban
On July 06 2012 15:09 Morfildur wrote: This should work for normal units but i can image it becoming extremely complex with units that have special effects, i.e. SC2 broodlords (broodlings), BW/SC2 carriers (interceptors), SC2 marauders (slow), BW Reavers (Scarabs) as well as active unit abilities (SC2 ghost snipe, BW marine/SC2 marauder stim, ...).
Good luck implementing that into the Starcraft AI.
Well I think it would be interested to see if he just changes the AI for the units that don't have special abilities and leave the original AI for those that do. And then just try out a game or two and see how the computer plays with it's new skills.
Store
