Starcraft::overview

Last time I played SC was about one year ago. And this time I finally set out to focus on optimize AI Modules.

First, I shall list some critical problems in the battle.

1.Overview Problems

The workers have to mine the crystal minerals to developing high-tech and military forces. Then for each of the SCVs or probes or drones, they has to be assigned a job to maximize the outcome(minerals and forces).

For example:

If  the race is Protoss.

Then

a. First 4 probes have to approach the nearest mineral and start mining. At the same time, Nexus will produce new probes to join the team.

b1. Until “WHEN” one has to set out scout, because at very beginning, one’s strategy could not be figured out until his first building was done.

b2. Until “WHEN” one has to build his first pylon and first gateway to produce zealots.

Remark:

b1 is kind of easy because there are many practical experiences for us to use.

b2 is much more difficult, because it depends on may factors.

For example:

b2-i. If the rival is Zerg, then one has to defend the fast 6 zerglings to attack at about 5mins.

b2-ii. If the rival is Terrain, then one has to defend the first team of marines.

b2-iii. Also we have to care about if your rival’s scout take up your gas location.(Steal Gas, and also scout)

c. How to arrange the team:

c1. How MANY probes shall we produce? It is known that about 2*the number of minerals(8-10) and 3* number of gas location(1-2) is the best choice. Then that is about 20 more or less.

c2. How MANY zealots and dragoons should we produce? That is much harder, because we usually use zealots to complete our first attack and upgrade their speed at the first time. If zealots could not kill or destroy some critical buildings, we have to use dragoons, and this strategy will cost gas a lot.(Thus a second base is needed for now on.)

c3. How MANY gateways should we build? The answer is one or two, gateway costs 150 minerals and about 1 min to complete. We will come to this problem later.

d. What is the building order?

For protoss, this is always a hard question. Especially at the start of the game.

e. Attack strategy.

This contains some tricks in it.

Dragoons and zealots with upgraded armor and speed is a good choice.

I think this could be optimized with some AI in blocking enemies, because dragoons are moving faster at first, thus we can play some tricks here, this also works for Terrains and Zergs.

f. Components of the forces

For Protoss, the production order is normally: zealots, dragoons, observers, templars and carriers.

Also, appropriate time for producing them is a remaining problem here. And we are going to implement them later.

2. More Technical

As I can imagine, this RTS game involves serveral algorithms in it. For example:

i. Assignment Problem for workers: Use Hungarian Algorithm to solve it in Polynomial Time.

ii. Building Order Problem: Genetic Algorithm

iii. Attacking: Linear Programming and else? GENETIC ALGORITHM!!

iv. Retreating: Linear Programming(KEEP LEAST LOSS)

v. Scouting: Shortest path Problem

vi. Location choices: Trust Region

vii. Other methods: Monte Carlo, Bayesian, decision tree and so on.

I will be back for them.

About YiMin

This is just a nerd PhD student of Math@UT Austin.

5 thoughts on “Starcraft::overview

  1. zhangzi0 says:

    I think there was an app on calculating Strategies, build order and virtual-battle for SC2 on app store.

    • YiMin says:

      Yes, I heard that about one year ago, someone uses Genetic Algorithm to give out 7 roach rush’s best solution, including the building order, but that’s just for beginning, and just for Zerg.

      It is called: Evolution Chamber.

      I was thinking giving a optimized strategy on arranging the forces by utilizing genetic algorithm.

      Developing SC2 AI is also very interesting, but there is no API for it. Most of us use script AI.

  2. Jody Alston says:

    Can you tell me who did your layout? I’ve been looking for one kind of like yours. Thank you.

Comments are closed.