[phpBB Debug] PHP Warning: in file [ROOT]/phpbb/session.php on line 571: sizeof(): Parameter must be an array or an object that implements Countable
[phpBB Debug] PHP Warning: in file [ROOT]/phpbb/session.php on line 627: sizeof(): Parameter must be an array or an object that implements Countable
forum.starcraftai.com • Unit composition algorithm
Page 1 of 1

Unit composition algorithm

Posted: Sat Dec 17, 2016 9:43 pm
by AIL
Hello there!

I don't have an own bot and also am not so sure whether I want to invest much time in starting from scratch, so I'd like to share an algorithm I came up with for other bot-makers to use if they are interested.

My background is: I started AI-developing around 2013 for 4x-games. One is Pandora: First Contact and the other one is Dominus Galaxia, which is my current project and is not out yet and will also keep me busy for some more time.

I just very recently stumbled over the Broodwar-AI-scene and have binge-watched the "[SSCAIT] StarCraft Artificial Intelligence Tournament" youtube-channel.

Of course this doesn't happen without making my own thoughts and I think I have a really good idea for a generalistic unit-composition algorithm which also should affect build-orders and upgrades.

Pandora: First Contact also uses algorithms to determine unit-composition based on that of the enemy and affected by own units. In Brood War, there's another very important factor, which is the investment to make the unit producible.

First each unit needs a base score.
how it is determined is not so important. Could be something simple like DPS*Hitpoints*(1+range/10)/cost and for spellcasters/workers the DPS-value is abstracted (if workers are to be included in the algorithm afterall, but it should be able to handle them just fine)

The evaluation of cost shall be modified by the current income of gas and minerals in order to value units higher that require less waiting-time for their resource to be available. Maybe multiply it by time required to mine the required resources.

the other thing each units needs is a number of tags
The tags are split up in two categories:
counterable: ground, air, stealth, small, normal, large, caster, splashweakness
countering: anti-ground, anti-air, concussive, explosive, anti-caster, siege, detection, splash
some example tags:
Marine: small, ground, normal, splashweakness, anti-air, anti-ground
Carrier: large, air, normal, anti-air, anti-ground, siege
Scourge: small, air, anti-large, anti-air

these tags act as modifiers for the value of a unit based on the modifiers of scouted enemy units and existing own units and here's how:

the supply-modified-percentage of enemy units in the known enemy-unit compositon having a counter-tag devalue all units that have the corresponding counterable tag by that percentage multiplied with 1/tag-count

the countering-value by default is 0 and each known enemy unit increases the value of the countering-tag-bearers by 1/tag-count times the supply-modified-percentage of the units coutnerable with that tag

a lot of this will just cancel each other out. For example almost all ground-units are anti-ground at the same time.

thus far it is similar to how it works in pandora and now comes the BW-specific part.

the cost-part of the score gets to include the cost of the required tech-path aswell as a percentage of the cost of the units of this type that already exist

So units that are available earlier will be preferred even if their score is bad but the more units of that type are already built, the more attractive teching for another one becomes.
If a unit wins by score that cannot be produced yet, it's tech-path should be determined and teching into their direction shall be triggered. But if tech-path is already on their way and resources are available the 2nd-place should be build instead, of course, so there's no disruption in unit-production.
Also note that if, let's say the battle-cruiser wins by score and one is already in prodction, the cost of adding another starport is to be added so that probably a goliath wins and gets prioritized over adding another starport in order to build more cruisers.

Tweaking the percentage by how much of the cost of existing units impact their own score will determine whether the AI is more about rushing with early-game-units or more about teching up. But it will all develop naturally and not by fixed build-orders. I would even imagine that this algorithm will "find out" new working build-orders. The percentage could be randomized within acceptable parameters at the start of the game and thus create a different style everytime you play against them and make them very hard to predict.

Furthermore the adapting to enemy-unit-composition could be initialized with very good default-assumptions and based on existing scouted buildings.

The algorithsm has lot's of tweaking potential. I think it can be a lot better than hard-coded unit-compositions as it is way more adaptive to mixed compositions of the enemy where other approaches don't give such good results.

Let me know if someone wants to experiment with this in their bot. If you write skeleton-methods for that I can also do the coding myself. I'm undecided whether I really want to dive into making bw-ai-bots. Unlikely I'd want to do it from scratch. But if someone who already has a working bot would offer me to continue working on it, I'd likely agree.