/
competition_survey_AIIDE_2017_ZZZKBot.txt
127 lines (69 loc) · 26.8 KB
/
competition_survey_AIIDE_2017_ZZZKBot.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
AIIDE StarCraft AI Competition - Survey
Feel free to answer as many questions as you like, but it would be great if everyone answered everything!
Please feel free to provide external references/links as necessary
Bot Name: ZZZKBot
Bot Race: Zerg
Author Name(s): Chris Coxe
Affiliation(s): Independent
Nationality(s): Australia, Britain
Occupation(s): Software Engineer/Developer
(These will be listed on the competition website)
Bot URL: https://github.com/chriscoxe/ZZZKBot
Personal URL: if you can only put one URL here please use https://au.linkedin.com/in/chriscoxe, otherwise please use https://www.paypal.me/quatari (for donations) and https://au.linkedin.com/in/chriscoxe
Affiliation URL: N/A
Questions about your bot (please answer as many as you can, especially Q 1-3)
Q: What is the overall strategy/strategies of your bot? Why did you choose them?
Same "Wu Wei" approach as previous versions, i.e. tailor some simple rushes (all 1-base build orders) and the number of defensive sunken colonies to some opponents based on their in-game player name. The only new kind of rush compared with last year's AIIDE competition is the hydra rush. The rushes are: 4-pool, speedlings, hydras, mutas (and may decide whether to muta rush based on the enemy's race if they picked Random race), or neither. Then tech to either mutas or guardians, and all rushes eventually transition to trying guardians after enough rush units have died). After it has started teching it makes zerglings. After it eventually transitions out of guardians, it starts making other tech buildings and research/upgrades and some other unit types. However, the game has usually ended by that point, and it tends to spend all its resources on mutas and zerglings rather than other unit types like utras, because of the kludgy way that unit types are prioritized. In addition, it also uses some special logic if the enemy is expected to forge fast expand ("FFE") or is expected to worker rush, although the logic for the latter does not work very well versus very many opponents.
The reason for the simplistic overall strategy/approach is because, as I mention in extracts from the AIIDE2017_ENTRY.txt file included in the submission, it was only intended to be a throw-away proof of concept bot, but because it was good at winning games against other bots (and for fun), I have kept updating it for competitions. I.E. extracts: "A simple throw-away proof-of-concept cheesy kamikaze 4-pool bot implemented in a short amount of time to reach low-hanging fruit. Effective against many bots that do not have a solid opening economy/defence. Has some simple logic for scouting, targeting and resource-gathering. Apart from targeting its micro is very limited. Stays at 9 or 10 supply for several minutes of in-game time then techs straight to mutalisks or guardians (on only 1 base... soon runs out of gas...) in an attempt to finish off static defences of idle opponents, and mutalisks in an attempt to destroy lifted buildings. Uses speedling or muta rush or hydra rush build against some opponents. Uses file I/O to learn which types of rush are most effective against each opponent. Doesn't do much else." and "Originally implemented in a quick and dirty fashion so releases would be ready for the CIG & AIIDE 2015 Starcraft AI competitions.".
See the answer to "Q. Why did you choose the race of your bot?" further down about how I started using the 4-pool strategy. Before I started writing the bot, my original plan was to implement a range of initial build orders/strategies and experiment to see which strategies were most effective against various opponents. After I had added some logic for overlord scouting and enemy unit targeting, the 4-pool strategy seemed so effective even on 3 or 4 player maps (especially after I added logic to scout with a drone) that it seemed my time would be better spent improving the 4-pool strategy and making it more resilient than completely changing the strategy or using disk I/O for learning which strategy to use against each enemy bot. There didn't seem to be much gain in adding much logic for transitioning out of the 4-pool strategy to other units because if 4-pool fails you are probably going to lose very quickly if the opponent is any good. I decided to continue kamikaze'ing zerglings to keep up the pressure in case it slowly wears down the opponent or in case the opponent makes a bad decision to transition out of their strategy (some bots including mine use hard-coded frame numbers as thresholds). I did, however, add logic to make it transition after a frame number threshold to mutalisks then guardians in case all that is left of the enemy is static defence or lifted buildings. There is only so much you can do to improve the 4-pool strategy though, so after CIG 2015 I tried a speedling build order which I hoped might be more effective against some opponents. In this strategy, it only starts sending zerglings out when the metabolic boost research finishes, then not long afterwards it transitions to mutalisks, then transitions to guardians if any mutalisks die. In later competitions, I added a muta rush and a hydra rush. As I said, apart from targeting its micro is very limited - I still haven't worked on it. Combat units simply keep attacking something. I didn't get around to adding any logic to make them kite or retreat or regroup or avoid dangerous threats to themself like static defences.
Q: Do you incorporate learning of any form in your bot? If so, how was it accomplished?
Starting in the CIG 2017 version, ZZZKBot records game info to persistent file I/O via opponent-specific append-only binary (DAT) files in the read/write folders. However, the CIG 2017 version doesn't make use of this information. Starting in the AIIDE 2017 version, at the start of each game, ZZZKBot uses the number of wins and number of losses from the DAT files in some simple hard-coded logic to learn/experiment which strategy parameters to use for the current game. The scenario criteria that are considered which vary in this competition (apart from the opponent and whether they are Protoss/Terran/Zerg/Random race) from least specific to most specific are: the number of start positions in the map, the map hash, my start location, the enemy's start location (normally not known unless it is a 2-player map or e.g. the CompleteMapInformation flag is enabled). The strategy parameters that are decided are the type of rush to use (see the last question), the special flags for whether the enemy is expected to forge fast expand or worker rush, and the number of defensive sunken colonies to build (which may vary according to race if the enemy is Random race). If it won the last game in the most specific scenario that matches the current scenario, it will always use the same strategy parameters. Alternatively (i.e. if it is known to have lost the last game in the most specific scenario that matches the current scenario), if its win rate is >= 80% or it has lost 4 or less games total (i.e. in all scenarios vs that opponent & race) it will use the same strategy parameters as the lost game, otherwise it will either pick a different combination of strategy parameters that has won at least once in a less specific scenario that matches the current scenario (if the expected win rate is good enough of a randomly selected (but weighted by win rate) combination of strategy parameters, excluding the strategy parameters combo that we just lost for) otherwise it will pick a combination of strategy parameters at random according to some probability weightings I have pre-defined. Unfortunately there are bugs in this logic (in the AIIDE 2017 version) that cause learning to be unnecessarily slow vs Random race bots (i.e. just UAlbertaBot in the AIIDE 2017 competition), and sometimes (but thankfully quite rarely) causes it to pick a combination of parameters that were not designed to be used together which cause the bot to get stuck waiting and never building a sunken colony before doing anything such as building more drones/buildings/combat units or attacking, so it becomes extremely passive and probably loses the game.
Q: Please describe all AI techniques / algorithms used in your bot.
(For example: What parts of your bot are 'hard-coded', which use learning, search, decision trees, state machines, etc)
My original development approach was to focus on the basics and reach low-hanging fruit (i.e. a "Wu Wei" approach) before moving on to more sophisticated stuff, and as it turned out there was more than enough to work on before getting around to anything more sophisticated. The only inter-game learning is the logic to pick a combination of strategy parameters based on the outcomes (i.e. binary win vs loss) from previous games.
Idle workers (and workers that have just returned minerals/gas to the base and are now/still a mineral gatherer) are allocated to unallocated mineral patches near the starting base using a greedy search algorithm which is based on the best worker's total distance between the base and an unallocated mineral patch (most important) plus distance from the worker to that mineral patch (less important). When there are no more unallocated mineral patches available, any remaining idle workers are all simply allocated to the mineral patch that is closest to the base (which will probably make workers bounce around between mineral patches somewhat, although they may settle after a few trips).
Most of the decisions in the bot are achieved by simple hard-coded prioritization of the various considerations involved. For example, the decision for which enemy unit to target is simply distance-based spiral searches with a hard-coded maximum distance threshold specified (via calls to BWAPI's getBestUnit() and getClosestUnit() functions) using simple heuristics mainly based on an ordering of attributes, with units that are in mutual weapon range first, threatening enemy units next, and an ordering of the various enemy unit attributes such as isPowered(), unitType() (the ordering of the various unit types is hard-coded), an estimate of enemy unit life force (a kludge based on HP, shields, armor, defense matrix points if it is defense matrixed), then a bunch of other ordered enemy unit attributes such as whether it is constructing a building. Another example is the decision for which unit to build/train next - a simple ordering is used (i.e. a kludge mainly just the order the various unit command calls appear in the source code) with some heuristics based on what type of rush we are doing, what tech buildings we need, how many drones we have, how many drones have died, how many of the rush unit type have died. Tech transitions are mainly triggered based on how many of our units of a particular unit type have died, or in some cases a hard-coded frame count threshold.
Uses randomization for strategy parameters combo selection in some cases, and also for each scouting unit's target position after all possible enemy start locations have been scouted and there are no known (landed) enemy buildings (and being more likely to select a target position that is not currently visible than a position that is already visible).
For the various maps and possible start locations, I also dumped the tile positions of creep around a zerg base at the start of the game and use this data (it's now hard-coded) when scouting against a Zerg or Random race bot to help guess their start location. There may be an easy algorithm to deduce the locations of the creep, but at the time, a submission deadline was approaching and it was quicker than spending time trying to figure out Broodwar's logic.
For info about the strategy learning logic used, see the last answer.
Q: How did you become interested in Starcraft AI?
I have always loved the game of Starcraft. I have been interested in Starcraft AIs ever since I first heard they existed via posts on the slashdot forum. The main post I recall was a link to an article about how the Berkeley Overmind bot won the 2010 Starcraft AI competition - at the time of writing (29th September 2017) you can see it as a series of articles now at: https://arstechnica.com/gaming/2011/01/skynet-meets-the-swarm-how-the-berkeley-overmind-won-the-2010-starcraft-ai-competition/
Writing a Starcraft bot is a good fit for my interests in problem solving, programming, software engineering, game theory, AI/ML, strategy games (Starcraft in particular), and competition. It's a lot of fun, and often farcical.
Q: How long have you been working on your bot?
I started writing ZZZBot in mid July 2015 for CIG 2015. ZZZBot (which became ZZZKBot) was my first competitive bot, but before that I had tinkered with BWAPI (see below), which helped me to learn BWAPI and the game mechanics. I usually only work on my bot just before a competition deadline...
Q: About how many lines of code is your bot?
Currently 5382 lines total (for everything including comments and blank lines etc), i.e. 5278 lines in C++ files and 104 lines in the vcxproj file. There is also some basic documentation in TXT files. There's quite a lot of source code duplication because I wrote it in a hurry and was planning to throw away the source code when I wrote it (ZZZBot for CIG 2015 was only intended to be a simple throw-away proof of concept bot!), and I haven't got around to tidying it up much. If you want to examine/use the source code, be warned that the source code is messy, full of kludges, undocumented, has undocumented limitations/gotchas, and lacks hardly any good architecture/abstraction/encapsulation (e.g. the logic is almost all in one method (onFrame()) and uses static variables, and significant duplication of source code).
Q: Why did you choose the race of your bot?
When I started writing the bot I wrote a simple strategy that used very early aggression as all three races. I was surprised how effective the initial zerglings were, even against some existing strong bots. Since then, I've decided to stick with Zerg rather than switching to Protoss or Terran or Random. I'd like to write a Random race bot, but it would require much more development time and computational resources to properly test it. I thought my time would be better spent improving the Zerg logic.
Q: Did you use any existing code as the basis for your bot? If so, why, and what did you change?
So that I could get started quickly, as a basis I just started with the BWAPI version 4.1.2's ExampleAIModule project and modified it, then subsequently upgraded to use a later version of BWAPI. I still haven't got around to using a library such as BWTA2/BWEM for terrain info.
Q: What do you feel are the strongest and weakest parts of your bot's overall performance?
Strengths: It's a cheesy N-trick pony. All it can do is some simple 1-base rush builds, with little or no follow-up. Its only strength lies in the fact that many existing bots are vulnerable to cheesy builds like this. Now that it has a little inter-game strategy learning logic, it may be able to learn which type of rush is most effective.
Weaknesses: apart from targeting, combat micro is almost non-existent - the only logic for combat micro is whether to wait at my base after morphing (only used in some types of rush while waiting for some tech to finish), or attack (almost all other scenarios), or defend my base (very rare). Also, it never expands. It would be useless against humans - it was not intended to be tested against humans - but it is effective against various other bots.
Q: If you competed in previous tournaments, what did you change for this year's entry?
The only new kind of rush starting in the AIIDE 2017 competition is the hydra rush (the existing kinds of rush in AIIDE 2016 being 4-pool, speedlings, mutas, or straight to guardians).
Now builds defensive sunken colonies, and the number of them is treated as a strategy parameter.
Uses a faster build order when rushing straight to mutas.
Fixed a problem involving weapon cooldown that was mainly affecting the effectiveness of mutas and guardians - it was often preventing them from changing target, e.g. they would still keep targeting a building if a threatening enemy unit came into range. In a muta rush, the mutalisks now head for the enemy base rather than the nearest known enemy building, mainly because the former is typically less well defended.
Now uses persistent file I/O via binary (DAT) files in the read/write folders - the details are in an earlier answer.
Modified/added default (hard-coded) strategy parameter combo settings for some/new opponents.
Upgraded from using BWAPI 4.1.2 to using BWAPI 4.2.0. Note: this fixes some problems involving some particular research/upgrades for bots that play as Zerg, but I don't think this has any impact on this version of ZZZKBot because I don't think I've make use of these fixes.
Q: Have you tested your bot against humans? If so, how did it go?
No.
Q: Any fun or interesting stories about the development / testing of your bot?
Before I started writing a competitive bot, while I was tinkering with BWAPI for the first time, I wrote a bot just for experimentation purposes. It identifies all allowed unit commands for all my units every 3 in-game seconds and issues one out of all of those commands at random. For commands that take arguments, it picked argument value(s) from among the allowed argument values at random, e.g. it only issues a build command for buildable locations. It was able to issue every possible command in the game that was allowed at that moment, including all spells and abilities. It was useless competitively of course but it was interesting to watch it on full speed playing against itself, especially if I helped it by making a few extra workers for it at the start. It would slowly build its base up (including gathering minerals, making a refinery and gathering gas), train units, research/upgrade, and have strange skirmishes with enemy units. When playing by itself, at some point it would inevitably wipe itself out by attacking its own buildings with workers or zerglings or marines or air units or whatever. On test maps where you start with lots of late-game units it was interesting to watch it cast all kinds of spells and abilities etc on its own units and enemy units, load and unload units, lift and move and land Terran buildings, nuke/storm itself, make hallucinations, mind control critters etc.
Q: Any other projects you're working on that you'd like to advertise?
Support/donations/sponsorship or perhaps even job offers (would be my dream job!) to write or help write a "proper" Broodwar or SC2 bot that actually uses some sophisticated AI/ML techniques (perhaps alongside minimal hard-coded logic?), possibly eventually using more appropriate hardware would be helpful, i.e. via https://www.paypal.me/quatari or alternatively add me in LinkedIn but be sure to mention it's about Starcraft AI otherwise I may ignore connection requests (https://au.linkedin.com/in/chriscoxe) or contact me at chris (dot) coxe (at) gmail (dot) com.
So far, I've been working on my Starcraft bot sporadically just before competition deadlines just as a hobby, using simple techniques to reach low-hanging fruit against other bots, using my existing personal hardware, but I have been following the Broodwar and SC2 AI scene and papers closely and have a lot of ideas for more sophisticated (and resource-intensive...) AI/ML techniques I would like to experiment with in a bot and would love to work on something more serious/useful/ambitious in Broodwar/SC2 AI.
Optional Opinion Questions:
Q: What is your opinion on the current state of StarCraft AI? How long do you think before computers can beat humans in a best-of-7 match?
I have no idea whether or when they will start winning.
A lot of traditional game AIs (for simple games anyway) and machine learning problem AIs can be tested within a split second to get a decent estimate of how strong they are. Unfortunately, currently, a single bot-vs-bot game of Starcraft against most BWAPI-based bots (i.e. almost all existing AIIDE/CIG/SSCAIT bots) can typically take roughly 30 real-world seconds at full speed. To get a decent idea of how strong a bot is, you need to test it against many BWAPI-based bots, preferably on a variety of maps. Also, enemy bots can learn between games, so a strategy that was very successful in the first few games may not be very successful at all after the enemy bot has played enough games. Against opponent bots that learn slowly, it could take dozens or even hundreds of games before it starts to become clear that a strategy that was effective initially isn't going to be effective in the long-term. If both bots are able to learn between games then the results may be very chaotic initially and may take many games for the win percentage to stabilize (or it may never stabilize in the worst case depending on how they are written, although this is very unlikely) because they may each react to each other's adjustments between games. Within the last year, tscmoo has written an implementation of the Broodwar game engine in the OpenBW project (see http://www.openbw.com/ and https://github.com/openbw). This will make it a lot easier to code and run simulations of approximations of forward models without needing to run the Starcraft process, although some important game state must still be hidden from each player and it would be cheating to accurately predict Broodwar's randomization logic that it uses for RNG in some parts of its game engine. Currently, as far as I know, there is currently no quicker way to test a bot against most existing AIIDE/CIG/SSCAIT bots than to actually run the other bots by injecting them via BWAPI into a Starcraft process in Windows or WINE etc using tools like StarcraftAITournamentManager. Consequently, learning techniques that require testing vs most other AIIDE/CIG/SSCAIT bots can only learn at that pace, and similarly for the development cycle in general.
Humans are very good at identifying new kinds of weakness that have not been identified before and quickly and effectively exploiting them, whereas AIs are currently very bad at this. In Starcraft for the bots available currently, as a human it is often easy to exploit bugs in the bot that the bot has no code for learning to respond to it (e.g. gas steal against a bot that has no logic to properly predict/prevent/respond to gas steal and plays poorly or distractedly if its gas is stolen) or a simple tactic (e.g. lure) or a simple technique (e.g. walling) or a simple hard-counter strategy (e.g. a particular opening build order) to consistently beat a particular bot. Once the word gets out about a bot's weaknesses, it isn't long before humans are able to consistently/always beat it, even quite weak human players. Of course, the bot's author might later be able to make a change to remove the weakness, then humans will look for other/new weaknesses...
At present, it wouldn't surprise me if a bot might occasionally beat a strong knowledgeable Starcraft player within a few years from now if they aren't used to playing against bots, or didn't know anything about the bot beforehand and the bot is adept at some cheesy strategies that took them by surprise with a little luck as a once-off. This might tend to happen if the bot plays as Random race on large maps and the human was often unlucky when scouting. I'm sure if the human prepares by playing against the same version of the bot beforehand they will soon notice a weakness and be able to exploit it and learn how to beat the bot before they actually play in the tournament.
That said, if it does happen soon that the same version of a bot beats several strong knowledgeable human players consistently and continuously even if the humans prepare by playing against it, which I doubt, I would guess that the bot would be exploiting a human's limited multi-tasking ability and limited actions-per-minute ("APM"). It might make use of the bot's high APM, especially in cheap tactical tricks that are difficult or time consuming for a human to do but effective for a bot to do (e.g. splitting units against splash damage, unloading and loading units vs units that fire projectiles so they miss, micro when kiting using multiple units that is nearly frame-perfect). It might rely on the ability of a bot to do multi-pronged attacks and constantly harass multiple bases at once, with fast units that kite and are positioned and manouvered well to avoid taking damage. This might force the human to focus on defending and micro, leaving the human with little time to spend on attacking/macroing/scouting/expanding/improving their economy. This might enable the bot to gain map control and expand all over the map, then dominate or starve the human. As prior research has shown, a bot is also able to get a slight economic advantage by improving the control of gatherers to reassign gatherers to mineral patches that have better round trip times. This might eventually tip the balance in the bot's favor in some games, due to the snowball effect.
Q: What do you feel is the biggest hurdle (technological or otherwise) in improving your bot's AI?
When I first started tinkering with BWAPI, the main hurdle was learning what Starcraft does under the covers (e.g. what the effects are exactly when you issue the various kinds of unit commands, and pathfinding), learning what BWAPI can and can't do and how to use it, e.g. Starcraft game mechanics like how the latency frames system works, understanding the attack animation frame system, game/unit state attribute accessibility, and pitfalls such as needing to prevent spamming attack commands. Since then there have been some great tutorials/blogs made available that would have helped me then, and it is easier to write bots now.
Now, the main concern for me is being able to increase the number of games played per hour when testing with the hardware I have available so that after I make a change to my bot, I can more quickly get feedback for how the change affected its strength (and any significant effects e.g. matchups or maps it is now much stronger or much weaker for) by testing the bot against more other bots and/or on a wide range of maps and/or playing more games (and playing many more games against bots that use inter-game learning than against bots that don't). The game rate is already fast for a small network of VMs using StarcraftAITournamentManager and I doubt it can be sped up much further or made much more efficient for the hardware I have available (because Broodwar's game engine logic still needs to run for every frame). Adding more computing power by adding more machines/VMs would help a lot because the testing can be quite scalably parallelized (at least until inter-game learning effects start to become a limiting factor anyway).
Q: Which bots are the most interesting to you and why?
Any bots that use learning techniques and try to minimize hand-crafting as a design approach, because it is more interesting and inspiring to see bots learning for themselves, and they may come up with novel ways of solving problems and playing Starcraft that nobody has thought of yet (e.g. I gather that the 7 roach rush build order in Starcraft 2 was found using a genetic algorithm, although of course I can't guarantee that a human didn't think of it first).