|
Request for Comment: Proposal for a BW AI Bot Ladder
Dear community
Over the last couple of weeks, I have tried to get up to date on BW bot development and AI. About two weeks ago I started development of my own bot. During this time, I have come to realize the following:
a) Brood War is generally a very motivating environment for people interested in AI because it is fun and entertaining. The approach to use a (RTS) game to teach AI is good from a motivation perspective.
b) By now some bots have become quite advanced. The better bots get, the higher the bar is set for new bots entering the scene, which can lead to frustration for new developers.
c) Most successful bots have little to no AI mechanisms implemented. The bar is therefore set by “scripted” bots, making it even harder for true AI to be successful.
d) The BW universe is far too complex to make any AI successful in a reasonable time, especially for computer science and AI students. One can easily spend months full-time only to accurately model the BW universe, without even starting to think about AI
e) The real-time nature of the game allows for only very little calculation to be done in between actions
This hinders any form of planning during the game. Still, AI mechanisms could focus on offline machine learning. This again would require a feasible way of simulating/playing many games.
To conclude: Brood War would make for a good motivator for AI students, but in its current state it actually achieves the opposite of what was intended. Due to its nature and the way developers are rewarded, developers are encouraged to spend less time on AI mechanisms and more time on “scripting” (rush bots, micro, fixed build orders, fixed scouting patterns, etc.)
I propose a solution of the above mentioned issues by introducing a unique ladder system for Brood War bots.
The goal is to encourage students and other developers to actually apply AI techniques and machine learning.
Brood War AI Bot Ladder
Design Criteria:
1. “Scripting” is discouraged (e.g. the hard-coded usage of a well-known good build order)
2. Artificial Intelligence mechanisms are encouraged (e.g. machine learning)
3. Development of more general problem solving is encouraged
4. Exploiting very specialized weaknesses is discouraged
5. The ladder gives early rewards to new developers
6. The ladder appropriately appreciates high-quality bots
Addressing the Design Criteria:
1. “Scripting” is discouraged (e.g. the hard-coded usage of a well-known good build order)
The map pool is big and varies over time. The maps in the pool are very different from each other and contain several non-standard features (e.g. there might be a map without gas or mineral patches at non-standard distances from the bases, etc.). This makes it much harder to apply human expert knowledge.
2. Artificial Intelligence mechanisms are encouraged (e.g. machine learning)
Tournament games are played on a lower speed, giving more time for complex calculations. Maps are generally more CPU friendly (smaller, with fewer neutral units). In between games, opponents have plenty time to analyze the replay and perform offline-calculations. Matches are always at least “best of 5”.
3. Development of more general problem solving is encouraged
4. Exploiting very specialized weaknesses is discouraged
The ladder is divided into leagues with different features. E.g. lower leagues have less units available. As bots progress through the leagues it is not feasible to manually adapt to specifics of any particular league every time.
5. The ladder gives early rewards to new developers
Lower leagues contain a very reduced Brood War universe. E.g. the lowest league universe consists of only SCVs, marines, command centers, supply depots, and barracks and is played on small maps. This way new developers can focus on actual AI strategies rather than having to invest heavily into dealing with all aspects of the game.
6. The ladder appropriately appreciates high-quality bots
The highest league consists of the full Brood War universe. However, bots may not skip leagues and all bots start at the lowest league every season. This is to prevent the development of a closed sub-group at the top which could slowly diverge back into “scripting”.
Implementation:
The leagues could look something like this:
League 0 (entry league):
Units: SCV, marine, command center, supply depot, barracks
Map: fixed 64x64 map with 2 spawn locations and standard main / natural setup (no geysers)
League 1:
Units: same as League 0
Maps: several sizes, several spawning locations, standard and non-standard variations
League 2:
Units: SCV, marine, medic, firebat, command center, supply depots, barracks, academy
Maps: contain gas geysers
League 3:
Units: adding vultures and factories
League 4:
Units: adding tanks, machine shop, and bunker
And so on, slowly introducing more units, and concepts like upgrades, flying units, cloaked units.
The whole league system could be developed in parallel for all three races to increase popularity. But it would probably be impossible to balance non-mirror matchups for all lower leagues.
For the actual laddering I propose reaching out to ShieldBattery. It would probably not be too difficult to mark players as bots. SB could then have a simple filter, such that bots can find and host bot games. The host determines the league level by the map he chooses.
Tournaments could be played out in headless mode on a server, casting is done via replays.
What do you think? Is this something that could spark interest?
I am interested in your comments and opinions & thanks for reading,
imp
PS: I used the term “scripting” in quotes several times. This is merely meant as a term for development where the developer hard-codes expert knowledge, as opposed to using AI mechanisms, such as machine learning. It is not meant to lessen the value of such bots in any way.
|
I think this is an interesting idea. I like the idea of having tiered levels. While the first tier in your proposal certainly seems like something that shouldn't require too much effort (relative to a full universe), how much depth is really attainable in such a scenario? I guess it depends on the terrain of the map and the use of flanking/spreading, but that seems like more of a micro conflict than a strategic one.
Also, if bots can't use builds, are you inferring that they would have to have an AI that "learns" that 9 depot 11 rax is optimal mineral spending? How would an AI learn that BBS potentially counters this on this 64×64 map? It seems impossible from an amateur perspective @_@
More general question: do any bots currently process scouting information? Like "if SCV finds hidden citadel, Terran tries to get scan ASAP?"
|
Jealous,
how much depth is really attainable in such a scenario?
From an AI and game theory perspective I think there is plenty depth. Mainly it addresses the question of economy versus army. I imagine especially on small maps the max-economy strategy is not feasible. So you would have to learn how much you necessarily need to spend on army while going macro, or the other way around how much economy to sacrifice such that you can punish a greedy opponent. You can also machine learn under what conditions fights were successful. And finally, you can use scouting to infer how economic the opponent build is (number of marines / barracks scouted at a given time) and adapt your own build accordingly.
Also, if bots can't use builds, are you inferring that they would have to have an AI that "learns" that 9 depot 11 rax is optimal mineral spending?
I am doing quite extensive calculations at the moment to define game boundaries mathematically. Check out:
http://www.teamliquid.net/blogs/513152-towards-a-good-sc-bot-p1-economy-1-2
http://www.teamliquid.net/blogs/513802-towards-a-good-sc-bot-p1-economy-2-2
Bots may use such calculations and then reason on the optimal spending depending on how the game develops. Did you know for example, that the earliest possible expansion generally is @6 supply for Terran? :p (not the optimal one, just the earliest possible one)
How would an AI learn that BBS potentially counters this on this 64×64 map?
Basically they would learn it the first time they lose to it. They are also allowed to analyze the replay with full information available after the game.
|
Just in case you weren't aware something similar to what you seem to be suggesting already was created.
(see bots-stats.krasi0.com)
It looks like the machines running games were turned off a while ago but the point is that someone has already created the infrastructure to run a ladder for BW AI.
|
On September 16 2016 11:38 Equalizer wrote:Just in case you weren't aware something similar to what you seem to be suggesting already was created. (see bots-stats.krasi0.com) It looks like the machines running games were turned off a while ago but the point is that someone has already created the infrastructure to run a ladder for BW AI.
As a matter of fact I briefly talked to krasi0 before posting. He told me that his ladder was replaced by SSCAIT.
Anyways, AFAIK it was just a normal ladder without the reduced universe leagues.
|
I like this idea, but the problem, as I see it is that we wouldn't have the required number of bots to really run the league, unless we get a massive rush of new bots being created. The reason that most bots are scripted at the moment is because its the easiest and fastest way to make a functioning system to work with. I fully encourage more learning systems, but its really hard in BW, because its such a complex game, and there are many factors which need to be tuned in order to figure out which strategys work and which don't.
Applying ML to sub tasks within the game, such as unit micro is actually an area where machine learning can be applied with reasonable effort, but building a full macro stategy using ML would probably be a task beyond most hobby programmers that we want to encourage into building bots.
Even if we take the proposed structure, with the current count of ~30 bots, we'd have 4 bots in each league, which would get really repetitive after a while.
|
Bots may use such calculations and then reason on the optimal spending depending on how the game develops. Did you know for example, that the earliest possible expansion generally is @6 supply for Terran? :p (not the optimal one, just the earliest possible one)
What do you mean earliest possible?
|
I think he means the fastest way possible to get to the minerals needed to build an expansion. So, at 6 workers, you would reach 400 minerals faster than by building an extra worker and have him mine. Similarly, you would reach 400 minerals faster by building 6 workers, rather than just having 5 and not spending the extra 50 minerals to build another worker.
|
I thought he mentioned "earliest" in the notion of supply (for some funny reason), and that`s 4 scvs, not 6. Fastest possible is a completly other thing. Thanks for you reply, it made it clear what he meant.
|
On September 16 2016 17:49 Cryptious wrote:
I like this idea, but the problem, as I see it is that we wouldn't have the required number of bots to really run the league,
[...]
Even if we take the proposed structure, with the current count of ~30 bots, we'd have 4 bots in each league, which would get really repetitive after a while.
That's a problem, yes. First of all, this speaks against further dividing the ladder into race mirrors. So new bots ideally should play Terran. Existing bots would have to live with the imbalances, for the better or worse.
Then the issue can be addressed in at least two ways:
1) let the promotion criteria be some absolute number of wins
This way, the league acts as a filter to keep out bots that cannot deal with a given league universe at all. All others will progress to higher leagues at some point during the season.
2) promote bot development for league 0 or league 1 at universities like the two SSCAIT hosts, Alberta, and many others, such that this becomes an actual practical exercise required to pass a class or at least an official competition.
When I studied CS we had a competition to program a image copy&paste function in assembly with as few CPU cycles as possible. It was not even mandatory, just the mere fact that there was an official competition made us stay up at night and spend significant parts of the Christmas holidays in the CS lab!
|
|
|
|
|
|
EPT
