archive by month
Skip to content

AIIDE 2023 - what UAlbertaBot learned

openingtotal#1
bananab
#2
stardus
#3
purplew
#4
steamha
#5
mcrave
#6
microwa
#7
dragon
#9
infeste
total-  31%5-279  2%25-263  9%53-236  18%9-274  3%183-102  64%112-170  40%48-236  17%263-26  91%
4RaxMarines8-117 6%0-19 0%5-33 13%0-11 0%0-22 0%-3-16 16%0-16 0%-
MarineRush181-240 43%2-25 7%1-18 5%14-54 21%1-28 3%65-30 68%18-45 29%3-29 9%77-11 88%
TankPush1-89 1%0-18 0%1-16 6%0-11 0%0-21 0%-0-7 0%0-16 0%-
VultureRush1-90 1%0-18 0%0-12 0%0-11 0%0-21 0%-0-7 0%1-21 5%-
DTRush24-177 12%1-40 2%0-25 0%3-41 7%0-18 0%--20-53 27%-
DragoonRush2-119 2%0-32 0%2-39 5%0-22 0%0-18 0%--0-8 0%-
ZealotRush229-236 49%0-32 0%2-39 5%0-22 0%8-54 13%62-46 57%59-23 72%3-18 14%95-2 98%
2HatchHydra44-143 24%1-27 4%0-10 0%32-44 42%0-23 0%-2-10 17%9-29 24%-
3HatchMuta1-73 1%0-21 0%0-10 0%0-4 0%0-23 0%-0-5 0%1-10 9%-
3HatchScourge1-73 1%0-20 0%1-14 7%0-4 0%0-23 0%-0-5 0%0-7 0%-
ZerglingRush206-229 47%1-27 4%13-47 22%4-12 25%0-23 0%56-26 68%30-52 37%11-29 28%91-13 88%

UAlbertaBot’s primary builds are MarineRush, ZealotRush (9-9 gates), and ZerglingRush (5 pool). Against #5 McRave and #9 InfestedArtosis, it stuck with them. Against other opponents it experimented with alternatives to try to escape its losses. It found 4RaxMarines (barracks at 4 supply) against #2 Stardust, 2HatchHydra against #3 PurpleWave, and DTRush against #7 Dragon.

AIIDE 2021 - what UAlbertaBot learned

I haven’t found time to investigate the second instance of “we both lost”. After this post, I’m nearly done with summarizing and aligning the bot learning files. The only bot I haven’t gotten to is FreshMeat, which has a unique learning system, not similar to any other bot’s. FreshMeat’s code is remarkably low-level, and deciphering the learning algorithm and the meaning of the learning files will take time.

In any case, here is UAlbertaBot’s learned data. UAlbertaBot keeps counts of wins and losses per strategy, not full history files, so its data can be laid out in a single table.

openingtotal#1
stardus
#2
bananab
#3
dragon
#4
steamha
#5
mcrave
#6
willyt
#7
microwa
#8
daqin
#9
freshme
total-  26%2-155  1%8-147  5%27-130  17%13-139  9%98-57  63%48-105  31%67-88  43%32-124  21%68-81  46%
4RaxMarines58-93 38%0-15 0%0-11 0%3-15 17%1-17 6%40-2 95%2-9 18%0-5 0%0-10 0%12-9 57%
MarineRush18-97 16%0-15 0%1-15 6%0-6 0%0-11 0%2-3 40%0-8 0%13-25 34%0-10 0%2-4 33%
TankPush12-102 11%0-15 0%0-11 0%0-6 0%0-11 0%1-2 33%5-25 17%0-5 0%3-23 12%3-4 43%
VultureRush15-90 14%0-14 0%0-10 0%5-19 21%0-11 0%0-1 0%0-8 0%1-9 10%0-10 0%9-8 53%
DTRush41-85 33%2-18 10%0-11 0%10-26 28%0-8 0%0-2 0%0-3 0%-0-4 0%29-13 69%
DragoonRush10-62 14%0-10 0%0-11 0%0-6 0%1-12 8%0-2 0%0-3 0%-7-14 33%2-4 33%
ZealotRush104-150 41%0-10 0%4-28 12%0-6 0%10-16 38%24-24 50%19-25 43%35-15 70%12-21 36%0-5 0%
2HatchHydra6-72 8%0-15 0%0-10 0%6-20 23%0-12 0%-0-2 0%0-3 0%0-4 0%0-6 0%
3HatchMuta1-61 2%0-15 0%0-10 0%0-6 0%0-12 0%-0-2 0%0-3 0%0-4 0%1-9 10%
3HatchScourge0-56 0%0-14 0%0-9 0%0-6 0%0-12 0%-0-2 0%0-3 0%0-4 0%0-6 0%
ZerglingRush98-158 38%0-14 0%3-21 12%3-14 18%1-17 6%31-21 60%22-18 55%18-20 47%10-20 33%10-13 43%

Looking down the total column on the left, there is one big surprise. UAlbertaBot has a primary strategy for each race it may roll, and switches away only if the primary strategy turns out poorly. In past years when I analyzed UAlbertaBot’s data (2018, 2019, and 2020), UAlbertaBot’s primary strategy with every race was also its best strategy overall when it rolled that race. This year, the primary terran strategy MarineRush was no longer best; it was far exceeded by 4RaxMarines, with better results against 5 opponents and equal zero against 2 more. 4RaxMarines does not mean build four barracks to train marines, it means build a barracks at supply 4: It is a fast rush. Here is the build order from the config file.

"Terran_4RaxMarines" : { "Race" : "Terran", "OpeningBuildOrder" : ["Barracks", "SCV", "SCV", "Marine", "Supply Depot", "Marine", "SCV", "Marine", "SCV", "Marine", "SCV", "Marine", "Barracks", "Marine", "Marine", "Marine"]}

I guess opponents were less prepared for the fast marine rush. McRave in particular was unable to cope. I looked through BASIL’s build order page and did not see it; I guess no bot plays 4 rax regularly. The version of UAlbertaBot on BASIL is different from the one in the tournament. The BASIL UAlbertaBot does play the slower marine rush, so its opponents have gotten used to it.

The 3HatchScourge build was useless. The build was specially designed to give UAlbertaBot a chance against XIMP, and apparently has no other value. Curiously, 3HatchMuta was nearly as helpless, with only 1 win, against FreshMeat. That win was the only win as zerg against FreshMeat, though, so chalk up one advantage.

AIIDE 2020 - what UAlbertaBot learned

Though UAlbertaBot has been surpassed over the years and become a low-end bot, we can still gain insight from its experience. The table summarizes the contents of its learning files. Last year this table had the bots down the left and the strategies across the top, but this year I turned it on its side—I am looking ahead to the table for Microwave, which has many strategies.

Some of the numbers here are slightly different from those in the official crosstable, because of games where UAlbertaBot did not record a result (no doubt due to crashes).

total#1 stardust#2 purplewave#3 bananabrain#4 dragon#5 mcrave#6 microwave#7 steamhammer#8 daqin#9 zzzkbot#11 willyt#12 ecgberht#13 eggbot
4RaxMarines33-120 22%2-18 10%1-6 14%0-13 0%1-8 11%7-12 37%3-14 18%0-9 0%0-6 0%0-10 0%17-19 47%2-5 29%-
MarineRush66-140 32%0-10 0%0-5 0%1-18 5%6-16 27%8-12 40%4-12 25%4-23 15%0-5 0%0-10 0%0-5 0%6-9 40%37-15 71%
TankPush17-105 14%0-10 0%5-18 22%0-12 0%0-5 0%0-3 0%0-5 0%0-9 0%8-23 26%0-9 0%4-8 33%0-3 0%-
VultureRush17-82 17%0-10 0%0-5 0%0-12 0%0-5 0%0-3 0%0-5 0%0-9 0%0-5 0%0-9 0%0-3 0%17-16 52%-
DTRush19-119 14%1-22 4%0-13 0%1-13 7%11-26 30%0-16 0%-0-14 0%6-13 32%-0-2 0%--
DragoonRush13-117 10%0-16 0%0-13 0%0-9 0%0-12 0%2-28 7%-1-20 5%10-17 37%-0-2 0%--
ZealotRush185-170 52%0-15 0%2-24 8%4-20 17%0-12 0%0-16 0%37-13 74%1-20 5%0-5 0%48-11 81%25-18 58%28-15 65%40-1 98%
2HatchHydra9-83 10%0-12 0%2-21 9%1-6 14%6-13 32%0-11 0%0-6 0%0-8 0%0-2 0%0-1 0%0-3 0%--
3HatchMuta0-63 0%0-12 0%0-12 0%0-4 0%0-4 0%0-11 0%0-6 0%0-8 0%0-2 0%0-1 0%0-3 0%--
3HatchScourge0-59 0%0-11 0%0-11 0%0-4 0%0-4 0%0-10 0%0-6 0%0-7 0%0-2 0%0-1 0%0-3 0%--
ZerglingRush195-168 54%0-11 0%0-11 0%11-21 34%5-11 31%0-10 0%14-23 38%1-11 8%22-23 49%29-18 62%21-17 55%39-10 80%53-2 96%
total-  31%3-147  2%10-139  7%18-132  12%29-116  20%17-132  11%58-90  39%7-138  5%46-103  31%77-70  52%67-83  45%92-58  61%130-18  88%

Random UAlbertaBot starts off with its default strategies of marine rush, zealot rush, or zergling rush, and tries alternatives only if the strategy scores poorly. The table shows that the default strategies chosen years ago are still the best choices. The zealot rush even scored well against #6 Microwave. Also constant over the years is that the 3 hatch scourge build, which was designed to counter the carrier bot XIMP, has no other use; UAlbertaBot would have done better without it.

It’s curious that UAlbertaBot’s overall weakest race is terran, but that its terran scored best against many stronger opponents: Terran was UAlbertaBot’s happiest roll versus #7 Steamhammer, #5 McRave, #2 PurpleWave, and #1 Stardust. But these stronger opponents allowed few wins. #1 Stardust (2%), #7 Steamhammer (5%), and #2 PurpleWave (7%) shut down UAlbertaBot hard.

If your bot is ranked above UAlbertaBot, then pink or blue boxes suggest weaknesses that you might benefit from working on. If a weaker bot beats you this way, presumably a stronger one can too. UAlbertaBot benefits from its random race and the big differences between its strategies, so maybe something went wrong in your scouting or reactions. #6 Microwave had trouble with zealots, #5 McRave had trouble with marines, and #4 Dragon had some trouble with 4 different rushes.

AIIDE 2019 - what UAlbertaBot learned

#11 UAlbertaBot was one of the weaker participants, but no player shut it out. Even against #1 Locutus, UAlbertaBot scored 1 win and learned a little bit about its opponent. That also tells us something about each opponent.

The “total” column gives UAlbertaBot’s view of how many games it won and lost, which does not always line up with the tournament results. The results give UAlbertaBot 6 crashes, when it presumably could not record any information. Also if one side overstepped the frame time limit (UAlbertaBot never did), or if the game timed out and was decided on points (12 instances for UAlbertaBot), the player has no way to know what the tournament manager decided, and the two may disagree about who won. Something like that must explain why UAlbertaBot recorded 3 wins for itself against #2 PurpleWave when officially it won only 2 games. These issues cause difficulties for learning, but as long as most games finish normally it shouldn’t be serious.

#bottotalTerranTerranTerranTerranProtossProtossProtossZergZergZergZerg
4RaxMarinesMarineRushTankPushVultureRushDTRushDragoonRushZealotRush2HatchHydra3HatchMuta3HatchScourgeZerglingRush
1locutus1-99  1%0-9 0%0-8 0%0-8 0%0-8 0%0-11 0%1-15 6%0-10 0%0-8 0%0-8 0%0-7 0%0-7 0%
2purplewave3-93  3%0-8 0%0-8 0%0-8 0%0-8 0%3-18 14%0-8 0%0-7 0%0-7 0%0-7 0%0-7 0%0-7 0%
3bananabrain16-82  16%0-7 0%1-10 9%0-6 0%0-6 0%0-4 0%0-4 0%9-20 31%0-4 0%0-4 0%0-4 0%6-13 32%
4daqin21-77  21%0-10 0%0-9 0%0-9 0%0-9 0%0-3 0%3-8 27%5-8 38%0-2 0%0-2 0%0-2 0%13-15 46%
5steamhammer9-89  9%0-4 0%8-9 47%0-4 0%0-4 0%0-6 0%1-9 10%0-5 0%0-12 0%0-12 0%0-12 0%0-12 0%
6zzzkbot10-89  10%0-8 0%0-8 0%0-8 0%0-7 0%0-4 0%0-4 0%8-16 33%0-7 0%0-7 0%0-7 0%2-13 13%
7microwave18-81  18%0-7 0%2-12 14%0-7 0%0-7 0%0-3 0%0-3 0%13-11 54%1-9 10%0-5 0%1-9 10%1-8 11%
8iron9-90  9%1-9 10%1-8 11%0-5 0%0-5 0%0-8 0%0-8 0%3-18 14%0-6 0%0-6 0%0-6 0%4-11 27%
9xiaoyi26-68  28%0-4 0%0-5 0%4-13 24%0-4 0%21-5 81%0-2 0%0-5 0%0-7 0%0-7 0%0-6 0%1-10 9%
10mcrave56-44  56%-22-9 71%--0-4 0%10-19 34%0-5 0%---24-7 77%
12aitp71-23  76%-19-8 70%----24-5 83%19-2 90%7-2 78%1-2 33%1-4 20%
13bunkerboxer88-12  88%-34-4 89%----30-0 100%---24-8 75%
overall-  28%1-66 1%87-98 47%4-68 6%0-58 0%24-66 27%15-80 16%92-110 46%20-64 24%7-60 10%2-62 3%76-115 40%

UAlbertaBot was random. Its learning plan is to first play its best opening for each race (terran marine rush, protoss zealot rush, zerg zergling rush), and switch away only if it lost too often. If you are always losing, there is no harm in experimentation. Against strong opponents it tried everything, to little avail. Against weak opponents, the best opening might be reliable, so it did not try others.

UAlbertaBot’s configuration file has enemy-specific strategies defined for many historical opponents. In this tournament, 2 of them reappeared: Iron and ZZZKBot, and the declaration for ZZZKBot says “make the default choices.” I don’t see evidence in the table that UAlbertaBot paid attention to its Iron-specific strategies, so I watched replays to find out. It turned out as I expected, an enemy-specific strategy became the default strategy, the expected best opening, and if it failed severely enough (as it always did against Iron) then UAlbertaBot would try its other strategies.

The “overall” row across the bottom tells us that its best openings truly were the best. In most cases, it did no good to try alternatives. The notable exceptions are that the dark templar rush won against XiaoYi, while the 2 hatch hydra rush won against AITP (this suggests that AITP consistently followed a mech strategy). Of course, UAlbertaBot played random, which can confuse opponents that learn. It’s possible that a protoss bot that always rushed dark templar might do less well against XiaoYi, and so on.

Some openings were useless in the tournament, and UAlbertaBot would have done better without them. For example, the 3 hatchery scourge opening is designed to combat XIMP by Tomas Vajda, and scored miserably. The terran vulture rush made 58 losses and no wins at all, a weight pulling down the ranking.

There is more to learn from the table. Steamhammer had some trouble against the terran marine rush, but shut out the zealots and the zerglings. The other 2 zergs had more trouble against the hard zealot rush (which was historically difficult for zerg bots to cope with, at least zerg bots other than KillerBot by Marian Devecka). I think the difference ultimately reflects the skills of the different bots. Steamhammer has micro and defensive weaknesses against ranged units in general (the one loss against protoss was to the dragoon rush). Its opening learning is ingenious enough to cover the weakness, but only at the expense of losses against protoss and zerg. So instead Steamhammer’s learning converged on the idea of allowing the marines to win sometimes, and strictly controlling the other races. It’s counterintuitive but effective.

AIIDE 2018 - what UAlbertaBot learned

UAlbertaBot played random, and its openings are chosen, not according to the opponent’s race, but according to its own once the game starts. It has 3 protoss, 4 terran, and 4 zerg openings. Playing random gives the disadvantage of having about 1/3 as many games to figure out how to counter the opponent with each race. The countervailing advantage, of course, is that the opponent can’t predict what is coming its way.

103 rounds were played and UAlbertaBot does not deliberately drop data, so some of the totals add up to more than the 100 official rounds. UAlbertaBot also had 46 crashes, so some totals add up to less. For example, it recorded 96 games against LastOrder.

The official site doesn’t offer binaries for the bots which were carried over from last year, but this should be the 2017 version of UAlbertaBot. It has enemy-specific strategies configured for 13 opponents, of which 5 are also in this tournament: #9 Iron, #10 ZZZKBot, #16 LetaBot, #2o Ximp, and #22 Aiur. For ZZZKBot, only the protoss opening is set; for the others, all 3 races have openings set. Looking at the table, we see that UAlbertaBot did not always try all of its openings, and the blanks in the table do not always correspond to enemy-specific openings. Apparently in this UAlbertaBot version, the enemy-specific strategies act as hints rather than requirements: When available they are tried first, and when not, the default opening is tried first (ZealotRush, MarineRush, or ZerglingRush). If the first opening tried performs well enough, UAlbertaBot sticks with it.

#bottotalProtossTerranZerg
DTRushDragoonRushZealotRush4RaxMarinesMarineRushTankPushVultureRush2HatchHydra3HatchMuta3HatchScourgeZerglingRush
#1saida13-88  13%12-7 63%0-2 0%0-5 0%0-9 0%0-9 0%1-13 7%0-9 0%0-9 0%0-9 0%0-8 0%0-8 0%
#2cherrypi1-99  1%0-8 0%0-7 0%0-7 0%0-8 0%1-11 8%0-8 0%0-8 0%0-11 0%0-11 0%0-10 0%0-10 0%
#3cse2-99  2%0-7 0%2-14 12%0-7 0%0-11 0%0-10 0%0-10 0%0-10 0%0-8 0%0-8 0%0-7 0%0-7 0%
#4bluebluesky11-92  11%0-4 0%3-10 23%4-11 27%0-5 0%0-5 0%2-11 15%0-5 0%0-9 0%0-8 0%0-8 0%2-16 11%
#5locutus6-97  6%0-7 0%4-17 19%0-7 0%0-8 0%0-8 0%1-11 8%0-8 0%1-10 9%0-7 0%0-7 0%0-7 0%
#6isamind5-96  5%0-7 0%4-17 19%0-7 0%0-9 0%0-8 0%0-8 0%0-8 0%0-7 0%0-7 0%0-7 0%1-11 8%
#7daqin12-90  12%4-12 25%0-4 0%2-9 18%0-6 0%0-6 0%1-6 14%0-5 0%2-13 13%0-7 0%0-7 0%3-15 17%
#8mcrave29-71  29%5-12 29%1-6 14%0-5 0%0-3 0%10-13 43%1-5 17%0-3 0%2-6 25%0-3 0%0-3 0%10-12 45%
#9iron9-94  9%0-10 0%1-14 7%0-9 0%0-8 0%0-8 0%0-8 0%1-12 8%1-6 14%1-6 14%0-4 0%5-9 36%
#10zzzkbot13-87  13%0-3 0%0-3 0%13-20 39%0-9 0%0-9 0%0-9 0%0-9 0%0-7 0%0-6 0%0-6 0%0-6 0%
#11steamhammer11-92  11%0-5 0%0-5 0%8-19 30%1-10 9%0-6 0%0-6 0%0-6 0%0-7 0%0-7 0%0-7 0%2-14 12%
#12microwave20-81  20%--18-7 72%0-7 0%2-14 12%0-7 0%0-7 0%0-10 0%0-10 0%0-10 0%0-9 0%
#13lastorder4-92  4%0-6 0%0-6 0%2-12 14%2-10 17%0-5 0%0-5 0%0-5 0%0-11 0%0-11 0%0-11 0%0-10 0%
#14tyr36-61  37%5-12 29%0-4 0%0-5 0%0-2 0%3-4 43%13-7 65%1-2 33%13-15 46%0-3 0%0-3 0%1-4 20%
#15metabot35-56  38%4-5 44%6-5 55%2-4 33%1-6 14%3-9 25%1-6 14%0-3 0%0-2 0%6-3 67%3-3 50%9-10 47%
#16letabot48-44  52%11-14 44%0-3 0%2-6 25%0-2 0%1-4 20%0-2 0%4-7 36%30-6 83%---
#17arrakhammer56-41  58%--23-6 79%0-6 0%0-6 0%0-6 0%0-6 0%---33-11 75%
#18ecgberht40-56  42%9-7 56%9-8 53%1-4 20%0-2 0%0-5 0%0-2 0%6-7 46%0-3 0%0-3 0%0-3 0%15-12 56%
#20ximp38-56  40%0-2 0%7-7 50%4-5 44%0-4 0%0-4 0%9-19 32%1-6 14%--17-9 65%-
#21cdbot44-54  45%--23-4 85%0-2 0%19-15 56%0-2 0%0-2 0%0-6 0%1-9 10%0-5 0%1-9 10%
#22aiur57-45  56%35-1 97%--0-2 0%0-2 0%0-2 0%11-10 52%1-5 17%9-15 38%0-3 0%1-5 17%
#23killall73-27  73%--30-8 79%0-2 0%12-6 67%0-2 0%0-2 0%---31-7 82%
#24willyt36-55  40%3-12 20%1-8 11%0-5 0%0-4 0%0-5 0%0-4 0%10-11 48%---22-6 79%
#25ailien71-30  70%--18-11 62%16-10 62%2-4 33%0-2 0%0-2 0%---35-1 97%
#26cunybot75-15  83%--23-1 96%-30-7 81%-----22-7 76%
#27hellbot100-2  98%--33-0 100%-41-2 95%-----26-0 100%
overall-  33%88-141 38%38-140 21%206-184 53%20-145 12%124-185 40%29-161 15%34-153 18%50-151 25%17-133 11%20-121 14%219-206 52%

The DT rush caused surprising problems for SAIDA, but terran and zerg had nothing. Did playing random contribute? Does the updated current SAIDA, flame-hardened on SSCAIT, react better? The hand-chosen 2 hatch hydra also did strikingly well against LetaBot, not an obvious choice. Every opening had a plus score against some opponent, though VultureRush barely made it over. Looking across the bottom row, the default openings had the best overall results for each race—they were chosen correctly. Also, we can see that protoss was UAlbertaBot’s best race, and terran the worst; we already knew that, but here we see it in the numbers.

new base placement code

Today I tested Steamhammer’s new base placement code, a major step in getting rid of BWTA2. There are still a couple of big bugs, but it works well most of the time. It’s getting close to ready.

As I mentioned when I first wrote about map analysis plans last June, Dave Churchill removed BWTA as a dependency from UAlbertaBot after Steamhammer forked from it. Newer UAlbertaBot versions do the necessary map analysis themselves, and when it comes to unnecessary map analysis, they simply delete some less important features that BWTA used to provide. I won’t delete features that add strength, but for the necessary features my plan has always been to borrow from UAlbertaBot.

Here’s how placing bases works in general. A base consists of a location for the resource depot, plus a set of minerals and vespene geysers belonging to the base (plus any other info you find useful). For starting positions that a player may begin the game in, the map specifies where the resource depot goes. BWAPI passes the information through. You still have to figure out which resources belong to the base. I had Steamhammer assign all the resources within a fixed distance to each starting base, and it works fine.

For other bases, software is on its own. First, group the resources on the map into clusters, expecting that each cluster will become a base location. You probably want to skip over blocking minerals and any clusters that don’t provide enough resources to be worth placing a base at, or at least handle them differently. Then, for each cluster, figure out the best place to put the resource depot so that mining will be efficient. Details matter, but it’s not complicated, at least if you ignore weird maps like Crystallis.

I wrote my own clustering, which is simpler than UAlbertaBot’s (though I wonder if I made it too simple and crude). For placing the resource depot, I followed UAlbertaBot’s way. UAlbertaBot provides 2 methods, one of which is commented out. The commented out method finds the center of the resources by averaging their locations. (Technically, it’s the centroid.) It then uses UAlbertaBot’s building placement code to find the nearest location to the center at which it is legal to build a resource depot—you have to be at a minimum distance from any minerals and gas. The building placement code calculates a spiral of tiles centered at the desired location and tries each one until it finds one that works.

The active method in UAlbertaBot, which I took for Steamhammer, is to find the center of the bounding box of the resources. That’s the desired location, and UAlbertaBot proceeds as above.

In practice, Steamhammer’s new code usually finds exactly the same base locations as BWTA. There are some exceptions. It finds 2 bases in the center base of Fighting Spirit (as some other bots do), which I think is due to a bug that assigns the same mineral patch to more than one base. I don’t expect it to be hard to fix.

Good progress so far.

Dave Churchill has updated SparCraft

The SparCraft combat simulator is an important feature of UAlbertaBot. Dave Churchill has updated SparCraft to a new “semistable” version, on a branch at the UAlbertaBot repository: sparcraft update branch.

I haven’t looked closely at the new SparCraft yet, but I have glanced through. I thought the headline features were:

  • More and better control over the details of the simulation. Part of it is a fancier configuration file. You can tweak details of the simulation to more closely match your bot’s actual micro (matching the enemy is not as easy).
  • Flying units are “supported correctly”.
  • No limit on the number of units in the simulation.

There are new data structures that use less memory and the simulation is more faithful in some respects, so we can hope that results are more accurate. I see changes to the implementation of healing, so maybe medics will be better simulated.

Time will tell, but on the face of it this is an important update. I’ll be trying it out as soon as I get through immediate priorities.

a new UAlbertaBot bug fix

The bot bftjoe by Joseph Huang fixes a bug in UAlbertaBot that I did not catch.

bool UnitUtil::CanAttack(BWAPI::Unit attacker, BWAPI::Unit target)
{
    return GetWeapon(attacker, target) != BWAPI::UnitTypes::None;
}

Easy to type, easy to read past... and totally wrong. Unit type None is 228, which does not match the value of any weapon type, so it will always return true. “All ints are the same type, right?” Bjarne Stroustrup: “Uh, sure.”

bool UnitUtil::CanAttack(BWAPI::Unit attacker, BWAPI::Unit target)
{
    return GetWeapon(attacker, target) != BWAPI::WeaponTypes::None;
}

In UAlbertaBot, CanAttack() is used only in the tank manager, so the damage, er, fallout, er... severity is limited. Steamhammer additionally uses the function in controlling lurkers, which it does not build by default because its control is so poor. So the next Steamhammer version should be a little less clumsy with tanks and lurkers. Still pretty clumsy, though; the clumsiness runs deep.

Tomorrow: The newly uploaded Krasi0 seems to be playing new builds.

the big BOSS bug with zerg

UAlbertaBot includes BOSS, the Build Order Search System, which accepts goals like “I want 12 zerglings and the speed upgrade” and calculates how to achieve them as quickly as possible, including creating the spawning pool and extractor if necessary, adding supply, building the ideal number of workers, and the exact spending sequence for everything. It does make approximations, but the build orders it produces should be close to optimal for the goal you give. UAlbertaBot by default uses BOSS to oversee its production as soon as it gets out of its opening build order.

Unfortunately BOSS also has limitations and bugs. If you give it a complex goal, it can’t run in real time (though you can still use it to create opening builds offline). And for zerg, BOSS has the bug that it will sometimes throw in an extra building that is not implied by your goal, usually an extractor, hydralisk den, or lair. I only wanted zerglings, why are you giving me a hydra den?

Blog reader Micky Holdorf looked into that bug and found the cause. Thanks for the report!

BOSS wants to search efficiently, so given your goal, it calculates the prerequisites so that it doesn’t waste time searching actions that don’t contribute to the goal. It calls this the goalMax, the most of each thing that you might want in order to achieve the goal. For terran and protoss, BOSS recursively calculates all the prerequisites and carefully counts each. Here is the code for zerg, from DFBB_BuildOrderSmartSearch::setPrerequisiteGoalMax():

    else if (getRace() == Races::Zerg)
    {
        _goal.setGoalMax(ActionTypes::GetActionType("Zerg_Spawning_Pool"), 1);
        _goal.setGoalMax(ActionTypes::GetActionType("Zerg_Extractor"), 1);
        _goal.setGoalMax(ActionTypes::GetActionType("Zerg_Lair"), 1);
        _goal.setGoalMax(ActionTypes::GetActionType("Zerg_Spire"), 1);
        _goal.setGoalMax(ActionTypes::GetActionType("Zerg_Hydralisk_Den"), 1);
    }

That’s not a calculation, that’s a stand-in! This part of the code was never written in the first place. I wonder if there was a bug in the recursive calculation for zerg, and Dave Churchill put in a stub until it could be dealt with?

Anyway, the correct fix is to write that code. One workaround is to delete the setGoalMax calls for zerg and always pass in goals that include their own prerequisites; you have to remember that you might need a spawning pool, or notice that you’ve lost yours and explicitly put it in. Micky Holdorf found another workaround with the same effect, which tells BOSS not to worry about prerequisites at all. In DFBB_BuildOrderStackSearch::generateLegalActions() change the line

            if (!goal.getGoal(actionType) && !goal.getGoalMax(actionType))

to this, which tells it that only goals and not prerequisites are legal actions:

            if (!goal.getGoal(actionType))

I don’t have any plans to write a fix for Steamhammer. If somebody sends me one I’ll certainly consider it! But Steamhammer is moving away from BOSS, because BOSS answers the opening question “how do I get this stuff as fast as possible?” and not the middlegame question “how do I spend my resources efficiently?”

UAlbertaBot fixes #9 and #10

And these are the last of the batch.

#9 tracking mineral patches—or not

WorkerData has two maps of worker unit -> mineral patch.

  std::map<BWAPI::Unit, enum WorkerJob>         workerJobMap;
  std::map<BWAPI::Unit, BWAPI::Unit>  workerMineralMap;
  std::map<BWAPI::Unit, BWAPI::Unit>  workerDepotMap;
  std::map<BWAPI::Unit, BWAPI::Unit>  workerRefineryMap;
  std::map<BWAPI::Unit, BWAPI::Unit>  workerRepairMap;
  std::map<BWAPI::Unit, WorkerMoveData>         workerMoveMap;
  std::map<BWAPI::Unit, BWAPI::UnitType>        workerBuildingTypeMap;

  std::map<BWAPI::Unit, int>                    depotWorkerCount;
  std::map<BWAPI::Unit, int>                    refineryWorkerCount;

  std::map<BWAPI::Unit, int>                    workersOnMineralPatch;
  std::map<BWAPI::Unit, BWAPI::Unit>  workerMineralAssignment;

They are workerMineralMap and workerMineralAssignment. workerMineralAssignment is the “real” one that is updated. workerMineralMap is not updated and is referred to only in WorkerData::getWorkerResource(), which in UAlbertaBot happens to be called only to get the refinery and never the mineral patch.

I deleted workerMineralMap and replaced its 2 occurrences with workerMineralAssignment. The bug has no practical effect without other code changes, but it was lying in wait.

#10 no overlords in combat

This one is not mine--AIL reported it in a blog comment. If a zerg bot includes overlords in a combat squad as detectors (which you have to write code to do), then the bot does not pass the overlords in to SparCraft and ends up fleeing from dark templar without trying to fight because there is “no detection”.

I rewrote InformationManager::isCombatUnit() like this. The original has a redundant check to exclude lurkers and doesn’t include overlords.

bool InformationManager::isCombatUnit(BWAPI::UnitType type) const
{
	return
		type.canAttack() ||
		type == BWAPI::UnitTypes::Terran_Medic ||
		type == BWAPI::UnitTypes::Terran_Bunker ||
		type == BWAPI::UnitTypes::Protoss_Observer ||
		type == BWAPI::UnitTypes::Zerg_Overlord;
}

Thanks, AIL!

UAlbertaBot fixes #6 through #8

Thanks to AIL I have a 10th fix, so I decided to cover 3 today.

#6 a morphing hive is not a resource depot

WorkerManager::getClosestDepot() figures out what command center/nexus/hatchery to send a worker to.

  if (unit->getType().isResourceDepot() &&
    (unit->isCompleted() || unit->getType() == BWAPI::UnitTypes::Zerg_Lair) &&
    !workerData.depotIsFull(unit))

The unit->isCompleted() part handles a corner case. If a command center, nexus, or hatchery is uncompleted, it can’t accept resources. If a lair or a hive is still morphing, it can. The bug is that the check omits hive.

  if (unit->getType().isResourceDepot() &&
    (unit->isCompleted() || unit->getType() == BWAPI::UnitTypes::Zerg_Lair || unit->getType() == BWAPI::UnitTypes::Zerg_Hive) &&
    !workerData.depotIsFull(unit))

#7 my base is your base

This is the one I wrote up as Steamhammer’s funniest bug. InformationManager::updateBaseLocationInfo() implements (among other things) a heuristic to guess where the enemy base is: If an enemy building is seen in the same region as a starting location, it assumes that the enemy base is at that starting location. Obviously it can be fooled if the enemy builds in another main base.

  if (isEnemyBuildingInRegion(BWTA::getRegion(startLocation->getTilePosition())))
  {
    if (Config::Debug::DrawScoutInfo)
    {
      BWAPI::Broodwar->printf("Enemy base found by seeing it");
    }

    baseFound = true;
    _mainBaseLocations[_enemy] = startLocation;
    updateOccupiedRegions(BWTA::getRegion(startLocation->getTilePosition()), BWAPI::Broodwar->enemy());
  }
...

For example, if the enemy proxies in your base, UAlbertaBot believes that your base is the enemy base, with hilarious results. I fixed it by checking against our own base location. That removes this way for the heuristic to fail, but it adds another one—if you ever play on a map in which your base and the enemy base are in the same region, the bot cannot find the enemy base this way. That’s life when you accept heuristics.

  if (isEnemyBuildingInRegion(BWTA::getRegion(startLocation->getTilePosition()))) 
  {
    updateOccupiedRegions(BWTA::getRegion(startLocation->getTilePosition()), BWAPI::Broodwar->enemy());

    // On a competition map, our base and the enemy base will never be in the same region.
    // If we find an enemy building in our region, it's a proxy.
    if (startLocation != _mainBaseLocations[_self]))
    {
      if (Config::Debug::DrawScoutInfo)
      {
        BWAPI::Broodwar->printf("Enemy base found by seeing it");
      }

      baseFound = true;
      _mainBaseLocations[_enemy] = startLocation;
    }
...

#8 assigning workers to buildings

BuildingManager::assignWorkersToUnassignedBuildings() is responsible for choosing what worker builds each building. It calls on WorkerManager to find a worker which is close to the building’s final position, which is stored in b.finalPosition. I read this code quite a few times before the bug hit me.

  // grab a worker unit from WorkerManager which is closest to this final position                                         
  BWAPI::Unit workerToAssign = WorkerManager::Instance().getBuilder(b);

  if (workerToAssign)
  {
    //BWAPI::Broodwar->printf("VALID WORKER BEING ASSIGNED: %d", workerToAssign->getID());                               

    // TODO: special case of terran building whose worker died mid construction                                          
    //       send the right click command to the buildingUnit to resume construction                                     
    //           skip the buildingsAssigned step and push it back into buildingsUnderConstruction                        

    b.builderUnit = workerToAssign;

    BWAPI::TilePosition testLocation = getBuildingLocation(b);
    if (!testLocation.isValid())
    {
      continue;
    }

    b.finalPosition = testLocation;

    // reserve this building's space                                                                                     
    BuildingPlacer::Instance().reserveTiles(b.finalPosition,b.type.tileWidth(),b.type.tileHeight());

    b.status = BuildingStatus::Assigned;
  }

It is assigning “the closest worker” before the position it is to be close to has been computed. In practice, I found it was assigning the free worker closest to (0,0). If the bot has several bases, it may send a distant worker on a long trek. Since UAlbertaBot normally plays rushes, the buggy behavior is not easy to notice in its play, but Steamhammer likes to take the map.

  BWAPI::TilePosition testLocation = getBuildingLocation(b);
  if (!testLocation.isValid())
  {
    continue;
  }

  b.finalPosition = testLocation;

  // grab the worker unit from WorkerManager which is closest to this final position
  b.builderUnit = WorkerManager::Instance().getBuilder(b);
  if (!b.builderUnit)
  {
    continue;
  }

  // reserve this building's space
  BuildingPlacer::Instance().reserveTiles(b.finalPosition,b.type.tileWidth(),b.type.tileHeight());

  b.status = BuildingStatus::Assigned;

UAlbertaBot fixes #4 and #5

#4 where are you? where are you?

CombatCommander::getMainAttackLocation() figures out where the “main attack” squad should aim to attack. It thinks the enemy main base is the top possibility. Here enemyBaseLocation is the location of the enemy main base (the comment is a little off), null if the enemy base location is not known.

    // First choice: Attack an enemy region if we can see units inside it                                                        
    if (enemyBaseLocation)
    {
        BWAPI::Position enemyBasePosition = enemyBaseLocation->getPosition();

        // get all known enemy units in the area                                                                                 
        BWAPI::Unitset enemyUnitsInArea;
        MapGrid::Instance().GetUnits(enemyUnitsInArea, enemyBasePosition, 800, false, true);

        bool onlyOverlords = true;
	for (auto & unit : enemyUnitsInArea)
        {
            if (unit->getType() != BWAPI::UnitTypes::Zerg_Overlord)
            {
                onlyOverlords = false;
            }
        }

        if (!BWAPI::Broodwar->isExplored(BWAPI::TilePosition(enemyBasePosition)) || !enemyUnitsInArea.empty())
        {
            if (!onlyOverlords)
            {
                return enemyBaseLocation->getPosition();
            }
        }
    }

The isExplored() check is supposed to account for the case where the location of the enemy base has been inferred although the base has not been seen. (UAlbertaBot infers the location of the enemy base when it has seen all but 1 starting location and they’re all bare.) But the check is not correct, because of how onlyOverlords and isExplored() are combined.

The effect is that, if the enemy base location has been inferred, the first combat units do not go toward it but believe that the enemy base is empty. If no other enemy buildings have been seen, the squad ends up exploring the map trying to find the enemy whose location is already known. This happened in one game of Steamhammer 0.2 versus PeregrineBot, and it was the main reason that PeregrineBot won. I’ve seen it in other games too.

The exploration check can be made correct by separating it from the onlyOverlords check.

	if (enemyBaseLocation)
	{
		BWAPI::Position enemyBasePosition = enemyBaseLocation->getPosition();

		// If the enemy base hasn't been seen yet, go there.
		if (!BWAPI::Broodwar->isExplored(BWAPI::TilePosition(enemyBasePosition)))
		{
			return enemyBasePosition;
		}

		// get all known enemy units in the area
		BWAPI::Unitset enemyUnitsInArea;
		MapGrid::Instance().GetUnits(enemyUnitsInArea, enemyBasePosition, 800, false, true);

		for (auto & unit : enemyUnitsInArea)
		{
			if (unit->getType() != BWAPI::UnitTypes::Zerg_Overlord)
			{
				// Enemy base is not empty: It's not only overlords in the enemy base area.
				return enemyBasePosition;
			}
		}
	}

#5 there is always a building rush

Here is how UAlbertaBot checks whether it is getting proxied.

bool CombatCommander::beingBuildingRushed()
{
    int concernRadius = 1200;
    BWAPI::Position ourBasePosition = BWAPI::Position(BWAPI::Broodwar->self()->getStartLocation());

    // check to see if the enemy has zerglings as the only attackers in our base                                                 
    for (auto & unit : BWAPI::Broodwar->enemy()->getUnits())
    {
        if (unit->getType().isBuilding())
	{
            return true;
        }
    }

    return false;
}

Well, there is an incorrect comment, but that’s not a bug. The routine omits one little condition.

        if (unit->getType().isBuilding() && unit->getDistance(myBasePosition) < 1200)

UAlbertaBot thinks it is being proxied whenever it knows the location of any enemy building anywhere on the map. The bug causes workers to be pulled for emergency defense more often than originally intended. See CombatCommander::findClosestDefender. Here’s the rather confusing line you may want to rewrite to change when workers are pulled for defense:

        if (!Config::Micro::WorkersDefendRush || (unit->getType().isWorker() && !zerglingRush && !beingBuildingRushed()))

UAlbertaBot fix #3 - the double overlord bug

ProductionManager::detectBuildOrderDeadlock() figures out when the bot is supply blocked so that it can order up supply if needed—for zerg, it orders an overlord. To tell whether the supply block is real, it needs to know not only current supply but pending supply—if supply is already being built, you’re not blocked. Here’s the critical code in UAlbertaBot:

  // are any supply providers being built currently                                                                        
  bool supplyInProgress = BuildingManager::Instance().isBeingBuilt(BWAPI::Broodwar->self()->getRace().getSupplyProvider());

  for (auto & unit : BWAPI::Broodwar->self()->getUnits())
  {
    if (unit->getType() == BWAPI::UnitTypes::Zerg_Egg)
    {
      if (unit->getBuildType() == BWAPI::UnitTypes::Zerg_Overlord)
      {
        supplyInProgress = true;
        break;
      }
    }
  }

Oh, but there is a tricky case for zerg. When an overlord is just hatched from its egg, it has unit type overlord but does not provide supply for a short time. The pending supply is unnoticed in the above code, the routine detects a supply block when there is none, and the bot orders 2 overlords in a row. The first overlord spawned turns into 2 overlords in around half of games. That is why Steamhammer 0.2 often finds itself with 3 overlords (providing 25 supply total, including the hatchery) when it is using 10 supply. The wasted minerals and larva ruin any opening that depends on precise timing, which is most zerg openings.

I solved it by counting supply by hand, including pending supply. Remember that BWAPI counts supply in units double what the game reports in the user interface.

	// If supply is being built now, there's no block. Return right away.
	// Terran and protoss calculation:
	if (BuildingManager::Instance().isBeingBuilt(BWAPI::Broodwar->self()->getRace().getSupplyProvider()))
	{
		return false;
	}

	// Terran and protoss calculation:
	int supplyAvailable = BWAPI::Broodwar->self()->supplyTotal() - BWAPI::Broodwar->self()->supplyUsed();

	// Zerg calculation:
	// Zerg can create an overlord that doesn't count toward supply until the next check.
	// To work around it, add up the supply by hand, including hatcheries.
	if (BWAPI::Broodwar->self()->getRace() == BWAPI::Races::Zerg) {
		supplyAvailable = -BWAPI::Broodwar->self()->supplyUsed();
		for (auto & unit : BWAPI::Broodwar->self()->getUnits())
		{
			if (unit->getType() == BWAPI::UnitTypes::Zerg_Overlord)
			{
				supplyAvailable += 16;
			}
			else if (unit->getType() == BWAPI::UnitTypes::Zerg_Egg &&
					 unit->getBuildType() == BWAPI::UnitTypes::Zerg_Overlord)
			{
				return false;    // supply is building, return immediately
				// supplyAvailable += 16;
			}
			else if ((unit->getType() == BWAPI::UnitTypes::Zerg_Hatchery && unit->isCompleted()) ||
					 unit->getType() == BWAPI::UnitTypes::Zerg_Lair || 
					 unit->getType() == BWAPI::UnitTypes::Zerg_Hive)
			{
				supplyAvailable += 2;
			}
		}
	}

I haven’t tried it to make sure, but I think another way to fix it would be to look for overlords for which unit->getOrder() returns BWAPI::Orders::ZergBirth and count them as pending supply.

I sent Dave Churchill 9 fixes (so far!). I’m planning to blog the rest 2 at a time, so I should be able to write up the remaining 6 over the next 3 days. Tomorrow: #4 has to do with squad orders and #5 with detecting building rushes.

UAlbertaBot fixes #1 and #2

I heard news from Dave Churchill about UAlbertaBot.

1. He has been working on SparCraft. He has changes that are not yet pushed to github.

2. He is willing to take my bug fixes and may merge them into UAlbertaBot as he has time (which I take to mean don’t hold your breath, he’s busy). He prefers bug writeups to pull requests, so I guess the code changes to UAlbertaBot are extensive.

I’ve already written up 2 bug fixes and sent them off. I’ll also post them here, because if you’re actively working on a UAlbertaBot fork then you don’t want to wait.

If you have your own bug fixes to UAlbertaBot, one way to get them into the pipeline is to send them to me. If you want to do it that way, post a comment here or e-mail me, and be sure to include enough details. I will post them for the community and send them on to Dave Churchill as appropriate, with credit to you, of course.

#1 null pointer bug

From CombatCommander::updateScoutDefenseSquad():

  // get the region that our base is located in                                                                                
  BWTA::Region * myRegion = BWTA::getRegion(BWAPI::Broodwar->self()->getStartLocation());
  if (!myRegion && myRegion->getCenter().isValid())
  {
    return;
  }

Oops, if the pointer is null it goes down on its face. It’s a simple slip. I haven’t found a map that tickles this bug, and as far as I know the pointer might never be null (if so, the whole check can be dropped). But in the spirit of defensive programming I changed the if condition:

  if (!myRegion || !myRegion->getCenter().isValid())

#2 building zerg static defense

From ProductionManager::create(BWAPI::Unit producer, BuildOrderItem & item):

  if (t.isUnit() && t.getUnitType().isBuilding()
    && t.getUnitType() != BWAPI::UnitTypes::Zerg_Lair
    && t.getUnitType() != BWAPI::UnitTypes::Zerg_Hive
    && t.getUnitType() != BWAPI::UnitTypes::Zerg_Greater_Spire
    && !t.getUnitType().isAddon())
  {
...

This omits 2 morphed unit types. The error prevents a zerg bot from morphing any static defense.

        && t.getUnitType() != BWAPI::UnitTypes::Zerg_Sunken_Colony
        && t.getUnitType() != BWAPI::UnitTypes::Zerg_Spore_Colony

By the way, there is a similar omission in BOSS. From ActionTypeData::ActionTypeData(BWAPI::UnitType t, const ActionID id):

   if (t == BWAPI::UnitTypes::Zerg_Lair ||
    t == BWAPI::UnitTypes::Zerg_Hive ||
    t == BWAPI::UnitTypes::Zerg_Greater_Spire ||
    t == BWAPI::UnitTypes::Zerg_Lurker ||
    t == BWAPI::UnitTypes::Zerg_Guardian ||
    t == BWAPI::UnitTypes::Zerg_Sunken_Colony ||
    t == BWAPI::UnitTypes::Zerg_Spore_Colony)
  {
    morphed = true;
  }

It omits Zerg_Devourer. I haven’t tried to make a devourer via a BOSS production plan, so I don’t know what effects it has to leave them out. But it sure looks like a bug.

Tomorrow: The double overlord bug.