General Algorithms on Starcraft 2

As I am learning data warehousing and mining strategies, I came across one of the technique by using General Algorithms. General Algorithms is a search heuristic that mimics the process of natural evolution for optimization solution and search problems. Its is also sometimes referred as evolutionary algorithms (EA), which uses techniques inspired by natural evolution, such as inheritance, mutation, selection, and crossover. While learning the concepts, I came across one interesting application of GA, build up optimization for Starcraft 2!!

For those whom is not familiar with Starcraft. Starcraft is a real-time strategy game that begin the game with a simple base, some workers, and some resources, and player strategies how to put those workers to work collecting resources and build things, and eventually building up an army and killing the opponents. A build order refers to the exact opening sequences and steps player take at early of the game that best supports the strategy. The early efficient strategy allow balancing spending money or making army to rush, or building advanced buildings. Some gamers adopt early rush offense strategy, by building substantial sum of army in shortest time before the opponent manage to build up their army or defense. 

This blog from Louis Brandy shows how the General Algorithm was implemented to optimize this strategy and conclude with its sequential build orders for one of the Starcraft race, Zerg. 

The result is 7-Roach Rush! This is the orders constructed by the program,

10 extractor-trick to 11

11 overlord

11 spawning pool

15 extractor

16 queen (stop drones here)

18 overlord

18 roach warren

17 overlord (yes, two)

spawn-larva on queen when she pops

roach x7

This strategy has been proven incredibly strong from Starcraft perspective. In terms of artificial intelligence perspective, I would like to point out some of the counter-intuitive order of this strategy, that violates several popular heuristics used by a lot of Starcraft players. The use of 'Extractor trick' and 'Double Overlord at 18/17'. More detail could be found in Louis Brandy explanation here.

Here is the video of how the 7-Roach Rush work in action!