A Survey of RTS Game AI Research and Competition in StarCraft (2013) [pdf]
webdocs.cs.ualberta.caGlad to see the scene is still alive and well. Back when it was picking up I made a Ruby client to one of the server based BWAPI clients, I built a really neat Ruby API to it too. Unfortunately I invested so much time at that point the actual 'AI' I made just 6-pooled the opponent, in just 44 lines though[1]!
Lately the release of mruby made me think maybe I should try again :) (mruby seriously reduces the amount of effort required in getting Ruby to talk to BWAPI.)
1] https://github.com/d-snp/RProxyBot/blob/master/basic_ai.rb
I used the python BWAPI client. I recently tried to get back into it but it seemed a lot more buggy and BWAPI wouldn't run on my newer Windows PC. :/
It was a lot of fun. Figuring out a base layout was the most difficult part for me. I ended up using the random function and placing buildings around my main base at random offsets. Didn't get too far with that, haha.
Yeah, silly problems like that really made being competitive with established AI's or even players hard. Just an AI that sets up a base properly and manages to build a proper army at the right timings but without any strategic insight into the opponent or even micro-decision making (which unit targets which opponent) will still do very decently, just because all the boiler plate is so much work not many AI's get to the actually being 'intelligent' part.
I played the sh*t out of Broodwar (and nowadays, SC2 HOTS) but i never heard about this Bot league. Thank you, this was a very interesting read.
Is there a human vs bot comparison?
Yes. Here's a video[0] of the winner in 2014 StarCraft AI Competition against one of the better human player.
More can be found at their official website[1] under Media/Files tab.
Seems the TvZ part of the bot could be improved by getting up turrets in time. Maybe they could get the bot to do a statistical analysis of builds they are likely to face in each match-up and use a build order that counters it.
Well, if you build enough to be safe against just about everything, your build will lose against any build which is properly executed. If you play the numbers and just have set builds which counter the most popular builds you might face, the human will pretty quickly figure out what the AI is doing and adapt their own build.
One of the most common and basic techniques in Starcraft is to bait another player into thinking you are doing a certain popular build, and then do something theoretically inferior but which requires a wildly different response.
Know your opponent is going to have turrets up at 5:30 on the clock? New build! Hits at 5:25! Have the AI use builds which have their turrets at (x-2) minutes just in case? Well, that's going to be an awful build against almost everything.
As shown in one example in the paper, even when the AI was extremely lucky and hard-countered the human's build, the human was able to adapt, respond, and win handily.
Since even the top humans are able to trick each other in these manners, you'd basically need general/strong AI to be able to compete.
> Well, if you build enough to be safe against just about everything, your build will lose against any build which is properly executed.
No one mentioned being safe against just about everything, just the important timing attacks (such as 3-hatch muta), which are known to be a big part about Starcraft. If you're going a build order that gets you straight-up killed by one of the most popular build orders, something is going wrong. Even if the enemy timing hits 5s before you get turrets up, your build should have a fallback e.g. marines in the base to hold off mutas until turrets complete, which is what a lot of progamers do off a 4-rax opening. Your (x-2) minutes statement seems to assume that AI builds can't cut corners and are forced to play the safest build possible every game.
> Since even the top humans are able to trick each other in these manners, you'd basically need general/strong AI to be able to compete.
This flies in the face of game theory, which is focused on solving exactly the problem you deem impossible to solve without strong AI. In 2008, poker bots (researched by the same university, the University of Alberta) have been able to defeat human experts in limit heads-up poker [1].
Perhaps the problem statement the researchers are working with is different from the one I'm envisioning. Maybe they are training their bots with only replays from other bots, rather than with replays from the top players in the world which constitute what we currently regard to be optimal play. I am thinking that the researchers may overlap with the poker research group, which suggests that the entire project is more focused on using superior game theory as the winning condition rather than exploiting areas where the computer is already known to be better than the human e.g. micro (giving hundreds of units unique instructions) and macro (sending build commands to buildings on the clock). The former is shown in the wraith vs. hydralisk video [2]. This may not work as well as in poker and may not yield as impressive games in the short-term as focusing on micro and macro, but the research is definitely fascinating!
They haven't even come close to a build which is safe against popular build orders or adapts. Judging by the difficulty they're having making the AI do what they want, this might be a bit harder than poker.
http://webdocs.cs.ualberta.ca/~cdavid/pdf/starcraft_survey.p...
Top play uses huge tradeoffs depending on what the progamer thinks they are facing; that would require an AI which can dynamically scout and effectively adjust its build based on what it sees. That isn't even taking tricks into account.
Basically, everything that you are saying is so far beyond what they're doing to program the AI that it's completely irrelevant. Critical things are hard-coded instead of adaptive, so that would all have to be written from scratch.
(None of this proves that it's not possible to program an AI which can beat humans without general AI, of course. I suppose that if you had enough scenarios with adaptive logic built in, the AI's ability to perfectly split marines or zerglings could be used to design a timing attack impossible for humans to stop.)
edit: I did not see your edit of the two sentences of your post when I wrote mine, or I wouldn't have covered the same concept.
> Top play uses huge tradeoffs depending on what the progamer thinks they are facing; that would require an AI which can dynamically scout and effectively adjust its build based on what it sees. That isn't even taking tricks into account.
I was thinking about that. Like what if they hired Flash to tell them everything he looks for when he scouts/scans at some time interval and then they factor them in as adjustments to build order or play using if-else statements. The possibilities are endless, but it must be a pain to test.
I never got into competitive Starcraft, because spending hours to acquire the mechanical ability in doing repetitive tasks seemed a waste of time to me. Perhaps they could build a rudimentary hard-coded bot that will aid the human player in all the boring tasks in executing a build order (base maintenance, unit building) and the human player scouts/combat micros against real players. Then later on, the replay gets analyzed and is used to train the bot in the next level of adaptive play. And the process is repeated, say the human player only does combat micro now. In each level the human requirement is reduced as the AI takes over increasing responsibility.
Flash doesn't just have a set list, he uses his general intelligence exhaustively during games - and he still loses a lot from being too predictable, too routine, producing the same responses to the same stimuli - even though his macro mechanics and builds are utterly top-notch.
Players triple and quadruple guess each other as they decide what build to use, where to place a proxy, how to scout, whether to scout, how to fake a proxy or allin, how to pretend like you're faking a proxy or allin but actually do the allin or a different proxy or allin or just do two half baked allins in a row to fake out your opponent into your real timing attack which might actually be a double fast expand while they're confused.
When you scan a player and see a tech lab on a starport, are they building banshees? Are they faking you out? Even if you've run stats on them, maybe they have a history of never building banshees, and they're using it in a key game because they know you won't expect it.
So any single action in the game has to be placed into a context. Depending on that context, a tiny factor which is irrelevant in one game can be key in another.
For me, the mechanical things are a zen thing. It's almost like a sort of meditation; your mind falls into these practiced routines, but you have to juggle all of them at the same time, choose which ones you can afford to let fall (since you can't do everything at once,) and then have your higher order tactical and strategical decisions on top of it. I haven't ever done anything else which engages my mind in the same way, and it certainly wouldn't do so without the mechanical demand you can never truly fulfill.
> Flash doesn't just have a set list, he uses his general intelligence exhaustively during games
I am not so familiar with SC2, but I know a bit about BW. I think you are mystifying Flash a bit here. I went through a BW phase (because my friends were all interested in it). I was trying to learn a build, so I watched Youtube videos of Flash games where he goes siege expand vs. Protoss. When the camera shows Flash's scout exploring the enemy base, you can see what information Flash gains, which is a (possibly incomplete) count on a number of units and buildings. Then by Flash's actions and deviations from his usual build order, one can construct an if-else statement of his reaction (defined as deviation from his standard build).
For example, one detail I noted was that he usually builds an Engineering Bay on 33 supply, but one game he starts it immediately at 21 supply after his scouting SCV was blocked by zealots from entering the Protoss base and seeing no Nexus up at the natural. The reason he did this was because he was afraid of 1-base DT rush. This gives us one thing that Flash looks for when he scouts in one particular build vs. Protoss. Since Flash is but human, I believe his thought process can be reduced to a checklist. It's not a very romantic notion of the best BW player of all time, but given enough data I believe it can be done. Perhaps by a bot that collects all the data from Youtube videos of pro BW games. I was thinking of writing a bot that does that, but what with the declining interest in BW and having to learn new tools never got around to it. Or even better, a former pro player could be asked.
There are fakes in BW too where a player begins construction of a building while the scout is there, but cancels as soon as the scout is out of sight. This would be included as part of the data, which a clever enough parser would be able to make sense of.
> and he still loses a lot from being too predictable, too routine, producing the same responses to the same stimuli - even though his macro mechanics and builds are utterly top-notch.
I think at least part of this may be attributed to the difference in mechanical floor needed to play the game at the top level. In BW, the number of players who could keep up with Flash's late-game macro were a mere handful. He had a reputation that even if you knew what he was going to do, you still couldn't beat him. In SC2 however, the reward of predictable play going to late-game may be less apparent.
> For me, the mechanical things are a zen thing. It's almost like a sort of meditation; your mind falls into these practiced routines, but you have to juggle all of them at the same time, choose which ones you can afford to let fall (since you can't do everything at once,) and then have your higher order tactical and strategical decisions on top of it. I haven't ever done anything else which engages my mind in the same way, and it certainly wouldn't do so without the mechanical demand you can never truly fulfill.
This part is quite fascinating to me, because I recently had a similar experience playing Osu!, which is like fast-paced DDR but with mouse and keyboard. At first I was just clicking slowly, but after several hours, I felt my body taking over and almost playing the game by instinct beating maps that were way too fast for me to beat a few days before. Before such an experience, I'd dismissed people who play Osu! as wasting their time doing something pointless and the music as a great destroyer of conscious thought. Yet after getting into a relaxing "Zen" state similar to the one you mentioned, I felt I could still think very clearly about my day, which came as a pleasant surprise.
I'm not exactly fanboying him here; every player uses their general intelligence. In Starcraft 2, Flash is actually famous for trying to use the same builds and responses too often, and he loses a lot of games because of it. For example, he lost one game because he uses the same reaper scout pattern and someone predicted how to dodge it. He lost another because his timing for stim finishing is predictable.
I think you might be right about Broodwar, and my experience with the games is the opposite of yours, so I had forgotten that such builds could work in that game.
I am glad that you have had that experience you mention, because it's not one everyone has had and I think it's quite valuable. I can definitely understand why so many martial arts have practiced sets of movements; when you repeat the same sets, the body records them into muscle memory and you can initiate the series of movements without having to incur any further conscious thought. The feeling of peace you can obtain from doing so is quite astonishing.
It's also good to note that in any tournament setup, the players would be in a best of 3 or best of 5. That means there's some meta-gaming going on as well. (Will the player go Muta 2 times in a row? or won't they? What did they do in the past?)
AI tries to defend with siege tanks against airborne mutalisks??
Building these AI's is actually a lot of work. They're usually built by a single or a few persons, in their spare time or perhaps as a college course. Most time is spent making sure your bot actually plays the game. Very little if any at all time is spent making the bot smart enough to deal with situations like this. In this case, obviously there's a bug where the bot is not dealing property with aerial attacks. A human player would have given up or made a suicide attack the second those mutas landed as he realized he missed a turret at his main.
Very well said. I've started a few month ago on an AI/Bot for 0AD an open source game. Scripting language is JavaScript running on SpiderMonkey. So far I've accumulated thousands of locs, learned a lot about writing fast code against a specific engine and have barely more than a framework. But I still remember the moment the bot did it's first baby steps and actually build a structure to train some scouts and started exploring the map.
Also it became a decent exercise in dealing with abstraction. The code base just explodes if you do not follow DRY - strictly.
Yes that was dumb. Should have basetraded (attacked with the tanks to force retreat (buy time and build towers) or destroy zerg base or 2 if the zerg keeps attacking).
I guess it was caught off guard and started panicking. Typical for human players as well.
I don't know any games besides chess and tic tac toe where a bot have been able to beat a good player ...
Your research is out of date, then. :) Even the game of Go, thought to be the hardest for computers, now has bots at the 6-dan (stronger than >99% of humans will ever be) level.
What about any FPS? Instant headshots would be hard to deal with.
TicTacToe can be easily played to a draw, unconditionally. Optimal play is simple, even for humans and optimal play leads to a draw.
Poker bots made by the same university have been able to defeat human experts in heads-up limit play [1].
Checkers is solved too (AI will always draw or win).