Starcraft – mathematical way to discover the fastest build order required for certain unit(s)

modsstarcraft

So I started programming a simple Zerg AI in Starcraft. I wanted to start with zergling rush strategy. It turns out that there's many different guides for fastest zergling rush, as well as other fastest builds, such as lurker rush.

I was thinking about this and basically a build order is a little comlicated state space diagram, if you treat time as just another "requirement" for units. So probably that must be a math-based way to prove that one solution is the best.

Best Answer

For a zergling rush specifically:

  • Resources to consider:
    • Minerals
    • Larva
    • Supply
    • Time
  • Influencing factors:
    • Queen (larva inject)
    • Drones (mineral gathering rate)
    • Overlords (add supply cap)
    • Extractor trick (temporarily 'adds' supply cap and lowers mineral rate)

For just a zergling rush, you can limit yourself to considering one of the following choices at each stage:

  • Build a drone
  • Build a spawning pool
  • Build an overlord
  • Build a queen
  • Build a zergling
  • Perform an extractor trick, and build a drone, queen, or zergling
  • Wait until when you are able to perform an above action which you are currently unable to

Obviously you would need to check if you have the prerequisites (other buildings and/or resources) before doing any of the above.

You could certainly brute force it if you so desired. This program doesn't prove or guarantee optimal times, but if you want to see SC2 build order optimization at work, check out these:

If you are looking for a generic way of "proving" a certain build order is best, I think you will find accounting for the diminishing returns of workers, resource exhaustion, expansion, travel times, and other factors will make it a rather herculean task unless you make so many simplifications that "best" becomes largely meaningless.

Related Topic