Evolution of the Overmind

[Astazha]

I'm working towards developing an AI that I'm going to call Overmind that will be a Zerg-only AI component.  The initial goals are:


- Intelligent scouting
- Moment of attack determined by decision-making rather than arbitrary times or army sizes.
- Greatest benefit economic decision-making rather than rigid build orders and stock levels.
- A strategic Overmind routine that controls the big picture.
- Adjustable personality variables for setting aggression levels, etc.
- AI doesn't cheat, including:
      *No harvest bonus.
      *No map vision
      *No use of enemy player numbers in place of "player" to access hidden information about the enemy.

I am presently building it within the latest (6.1.1) version of Starcrack as a complete replacement to the existing Zerg AI.  To the extent that it is possible, I wish to contain it within the Zerg files so that it will be easier to merge it with different AI versions.  This will be a 1v1 AI to begin with.


Milestone #1 will be to beat the Starcrack Protoss in a 1v1 without using a stock build order designed to do that.


It will be some time before this is released.  Your thoughts and code snippets are welcome.

[Astazha]

Sub Projects:


DATA COLLECTION:


The first thing any decision-making framework needs is data.

Working Functions  http://pastebin.com/2tpX4U6V


OvermindReadLarva()
  - Counts number of larva on the ground and provides an estimated rate of total larva production.
  - Does not account for Hatcheries not making larva when 3 or more are on the ground.

OvermindReadEconomy()  UPDATED 3/23/2010
  - Counts mineral and gas resources on ground at all towns. 
  - Counts # of extractors, and unused gas geysers. 
  - Depletion accounting is only per town, not at individual geyser level.
  - Adjusts for the bug in AIGetGasAmountLeft()
  - Calculates income for gas and minerals.

OvermindReadBank()
  - Current Minerals, Gas, Supply, and Projected Supply (includes overlords in progress)
   - It's questionable whether it's really necessary to put these into globals via a function.

OvermindMemory array and PeonGas functions
  - historical data storage
   - safe for use by all players
   - initially just provides  a way to set and get how many peons are harvesting gas at each town
       * Get only knows what was previously Set, it doesn't examine actual peon conditions.
       * Set is a direct replacement for AISetGasPeonCountOverride()
   - interface functions make access look like any other function and encapsulate specifics
   - can be extended to store all kinds of data.
   - OvermindMemory now includes an array slot for marking whether the initialize routines have been run for this player (separate from the standard mainstate variable.)

TODO:
  - functions to determine unit costs and build times from XML data
          *Use http://www.sc2mapster.com/api-docs/functions/catalog-field-value-get/WISHLIST:
   - whether any waves are in combat and projected change in food usage from coming losses.
   - whether a base is under attack
   - a system of relative valuation of each base, considering resources & harvest rate, resources invested in buildings.

UNIT CHOICE



PRODUCTION MANAGEMENT




ECONOMIC MANAGEMENT



TODO
  - Have the AI successfully generate and execute a starting build order.


CEREBRAL INTELLIGENCE AGENCY

Working Functions:

UPDATED 3/24/2010
  - Fixed various bugs preventing proper acquisition of enemy main.
Various Functions: http://pastebin.com/XRwTK6U7
  -  Locates all resource locations on the map for scouting/expansion purposes.
  -  Location stored is not the town hall location but the location of one of the minerals there.
  -  Will support marking the town as enemy, friendly, or neutral.  All towns start marked neutral.
  -  As any unit spots a townhall building, the location is marked as occupied by friendly or enemy.

TODO
  - Means to remove town spots when destroyed.
  - Include info on player's expansions.
  - Deal with possibility of floating command centers.
  - Various access functions for quickly returning data about known town locations
  - Store additional basic data about the town. player, starting resources, main or expansion
  - Develop system of placing scouts and quickly retrieving them for analysis.
  - Intelligently assign the right scout for the job.  Overlord, Zergling, Roach.
  - Determine travel time to and from various locations for attack coordination.
  - Refine scout behavior for optimization of information/unit conservation.
  - Particularly in protected areas, Overlords should be generating creep on potential expansions once Tier2 is reached.


WISHLIST
   - Historical data including whether an enemy town was ever here, how long it's been neutral, last time attacked, time spotted, known # of workers, projected exhaustion time.
  - Track hot spots on the map where combat frequently occurs.
  - Track Pathing, particularly in high traffic areas.  Be able to locate regions that are out of the way of normal pathing.
  - Develop intel system to support coordinated attacks on multiple locations.




TACTICAL


For improving the AI of waves and individual units.

Working Functions:


SpawnLarva() http://pastebin.com/MTHgEYPV contributions by Kernel64
  - replace code in TactZergAI.galaxy
  - A Queen will spawn a larva at any hatch within range 25 of her
  - She will spawn larva until there are at least 16
  - Larva count based on count of larva units in range of the hatch so it isn't always 100% accurate but it's very close.



CHAT DEBUGGER - suggested by vjeux

This will be a library of chat commands that will cause the AI to display data.  This will be useful for debugging AI behavior during a game (while spectating, I assume it doesn't work during replays) without being continuously buried in data scroll.

TODO:
  - Income
  - KnownForces
  - KnownTowns
  - Create chat trigger options to turn on continuous debugging for a feature.  1st word will be the feature, 2nd word (if any) will be On or Off.


Example:
"Income" will display income data once.
"Income On" will make income data display continuously
"Income Off" will stop the continuous scroll of income data.

[Astazha]

Successes:


  - 3/23/2010  Overmind is capable of using the Intel functions to send an Overlord to the enemy's main to monitor production.

  - 3/18/2010 Overmind AI beat Starcrack Protoss OpenGnd1 (19 zealots) in a 1v1


Using the following stock options:
       *11-Pool build order that develops into 1 queen, 2 extractors, 30 drones
       * stock of 40 zerglings
       * default scouting
       * default expansion routine

With the following determined by AI
        *Number of banelings to send with the wave based on known # of zealots
        *Size of wave to send based on known # of zealots
        *Time of attack determined by strength of army compared to known # of zealots

Battle Length - 15:33   


Lots of room for improvement still.  Zerg has dominated Protoss OpenGnd1 before but never fast enough to prevent unscouted expansions from making victory impossible.


Note: Additional victory in 19:15.  In general however, the outcome is unpredictable.  Most games are either lost or brought to a stalemate by scouting failures.

  - 3/17/2010 Overmind AI understands when to go for the kill after wiping out most of the enemy's troops.  Current model only acknowledges Zealots, Zerglings, and Banelings.


Problems:

  - Poor scouting algorithms leave some expansions undiscovered and unattackable.
  - Baneling tactical AI wastes them on armored units if that's what is closest.
  - Army response to enemy scouts has a large and somewhat random impact on the game outcome by creating multiple unplanned skirmishes.

[Kernel64]

This is awesome!

[Astazha]

I've done some thinking about where these algorithms might be headed.  Here are some ideas for the future:


Prediction:


The ability to predict is the heart of intelligence.  As a framework is developed and as the AI becomes capable of dealing with the present, it's true brilliance will come from dealing with what it expects in the near future.


Production/Tech/Expansion


One of our difficulties is how to balance such things.  Here's one take on the matter:


We begin with some assumed capabilities:
1) The AI has an enemy unit composition that it is comparing itself to.  Intially this will be what is known, later it may include assumed production rates, etc.


2) The AI has a system of valuing a unit or mix of units against this enemy force.


3) The AI is capable of calculating it's production into the future given different scenarios.  This is something I'm actively working on.


Then we assign a window of time for when we predict combat will take place.  It might be "Somewhere between 30 seconds from now and 3 minutes from now.  Then we diminish the value of a unit over time, so that producing  100 points of units in 30 seconds is worth more than producing 200 points of units in 3 minutes.  One way to diminish this is just a linear (or other) reduction over time.  Another is to compare the units to an assumed growth rate of enemy forces.  The AI's personality variables may also impact it's perception of how time affects the value of a unit - more aggressive AI's will be more impatient.


To compare two scenarios - let's say either build more zerglings or tech to roaches - the ai will calculate the point value of each over the time window and determine at what point within the window, if any, it becomes more valuable to produce roaches.


Things worth looking at will be:
1) What will the difference in capacity be for the two scenarios?  This is the real goal of teching - to increase the # of points/minute that you can produce against your opponent's army.  What this increased capacity must be weighed against is "Is it safe to tech?"


2) How long till the low tech scenario counters the enemy forces?  How long till the high tech scenario counters them?  What's the difference - how big and how bad is the window of vulnerability?


3) Can short term weakness be held off with defensive structures?  A gas heavy tech like mutas might be a devastating move to make, and building a pile of spine crawlers in the short term might provide the security to do it without having much impact on our capacity once the tech is reached (if we're gas limited)


4) What are the other values of a unit - and this one will be hard to quantify, but roaches are:
     * more re-usable
     * excellent scouts
     * good for worker raids
None of these is really accounted for in the calculation of "how many roaches does it take to defeat X Zealots and Y Stalkers?"


I don't have this fully thought out, but this is the direction I'm headed with it, and it seems like the kind of thing that would balance tech and production.  I often find when I start heading in a direction that things become clearer as I approach the goal.


It could also generate the initial build order - the computer could be operating with a threat of 1 zealot and a time window of 3 minutes (or whatever it is) and be left to calculate a build based on it's personality.  More aggressive build will go 10-pool or something, and more patient ones would go for a fast expo.  (And maybe patient/impatient should be different from aggressive/defensive)


Unit Valuation


I want to try a weighted average against the assumed enemy force composition and see how that goes.  It will be overly simple, but that's appropriate to start with.  Things can always be more sophisticated later; right now they need to be achievable.


Posture

Separate from the personality constants, I'm imagining a posture variable that the AI itself would set.  After losing most of it's forces and having a large enemy army remaining it might "turtle" for a short time.  This kind of thing would affect it's tendency to go for mobile units where it can assert map control or for defensive structues that provide more economical defense at the cost of mobility.


Levels might be things like:
Turtle - seriously not poking our heads out and preparing for the worst.  Consider building crawlers for defense and do something to recover control - tech, rebuilding drones, hidden expansion, whatever.


Cautious - it's time to venture out a little more, but the enemy has a strong presence.  We should not be doing things like transporting drones from one expansion to another or making other unnecessary troop movements. We're less interested in where the enemy is than where they're not because right now we want to be where they're not.


Neutral - starting stance, no particular bias


Aggressive - we have map dominance.  Expanding etc. should be done without concern or escort.  The cost of missing opportunities is higher right now than the cost of losing some units.  We are very interested in knowing where the enemy is so that they can be contained.  This is not a reckless posture, however.


Seek and Destroy - the enemy is full on the run, and what matters most is getting the scouting done to make sure they aren't recovering at a hidden expansion somewhere.  Some recklessness is appropriate - Waves shouldn't even bother to regroup at this stage because no real resistance is expected and time is of the essence.


Something like that. 

[Astazha]

OvermindReadEconomy() will give you your income now.  It's pretty accurate.  The changes happen faster than what shows up in Blizzard's monitor box, but that's because Blizz is showing a running average.


Correct assessment of drone assignment to gas depends on using the OvermindSetPeonGasCount() function to assign them.

[Astazha]

The new Intel functions track where the expansion locations are, and which ones have been used by enemy or friendly players. 


Preliminary test code has successfully used the data provided by the Intel functions to send an Overlord to the enemy's main (once the initial Drone scout finds it) to monitor production.  This results in a more accurate unit count and better decisions about what to build,  how many to build, and when to attack.


Future development will improve upon these successes to include:
  - moving the Overlord when he is in danger, and early enough to get clear.
  - placing scouts at nearby locations to monitor expansion activity.

[Bloodyaugust]

I would like to help with this AI. I can see you're extremely serious about this, and I have been looking for an AI/Map-Making partner. PM me for my email account.

[Astazha]

Bloodyaugust:  I... think I sent you a PM.  DarkBlizz's message system seems a little wonky.