Wednesday, November 03, 2010

Starcraft 2 build order optimizer using genetic algorithm

Over on a forum called teamliquid, a user by the name of Lomilar posted a fairly long thread about a program he had written that optimized build orders for the zerg race in starcraft. He eventually cleaned up his code and posted the code to googlecode. The program is called EvolutionChamber (a clever name, as it’s the name of one of the buildings in the game), and it uses genetic algorithms to find build orders.
A build order refers to the exact opening steps you take early in the game that best supports the strategy you are trying to conduct. These early games are all about balancing spending money on your economic foundation (making more workers), making units (rush!), or building new buildings or getting new upgrades (tech!).
Build orders generally only cover the very early game because once you’ve scouted the enemy, you have to begin to react to what he’s doing and modifying it as you go. In other words, and a perfect aphorism, no battle plan survives first contact with the enemy. In this way, build orders in real-time strategy are very much akin to openings in chess. They set up the soul of the entire game about to be played, and some players prefer to force certain types of games, depending on what kind of opening they choose to do.
One of the reasons build-order optimization is so important is that you can discover openings that “hard-counter” other openings. If I can get an army of N size into your base when you do opening X, you will always lose.
Enough with the abstract, here’s what you need to know:
  1. The program in question optimizes Zerg build orders (which is one race in starcraft), this is a rather significant choice because the mechanics of the zerg race are arguably the most difficult to manage (esp. for build order optimization).
  2. Of most interest are “rush” build orders. This means “how quickly can I get N of this type of unit?”.
  3. There are two primary resources that workers collect in starcraft: gas and minerals.
  4. Zerg also have a third de factor resource: larva. Larva are used to create ALL zerg units, including workers.  So long as you have less than three,  they regenerate at a fixed rate (note: this means any time spent at three larva delays all future larva production — very bad).
  5. Most units require some building to be constructed in order to be “unlocked” (and many of these buildings require others as prerequisites – this is the so-called tech tree)
  6. Creating a building causes you to lose the worker who creates it (so the longer you can wait, the more resources that worker can collect before building the building)
These “rules” provide for an extremely complicated search space to find optimal build orders. Essentially, you want to make the exact number of workers you need as quickly as possible (and then no more). Losing a worker when you make a building, and delaying all future larva when at three larva make the dynamics extremely complicated.

Here’s a video of someone doing the ‘all-in’ variant of this build against a real player:

Read more on lbrandy's blog

Monday, May 10, 2010

Footmen Frenzy III.scx changelog

- Archon’s 200 B spell deals less damage
- Archon’s 300 spell deals less damage
- Ghost’s 300 spell summons more ghosts; it is able to convert some of the ghosts to siege tanks
- Hydralisk’s 200 B spell does more damage
- Ultralisk’s 200 D spell holds ghost's 300 spell ghosts
- Zergling’s 200 B spell tolerates armor upgrades
- Players receive fixed +2 income; shop & upgrade costs are adjusted
- Base pyramid’s health was increased by 5,000 hp

Saturday, May 08, 2010

Footmen Frenzy map for Starcraft 2 !

As soon as Starcraft 2 beta had been released,  dokebi, had created a Footmen frenzy replica for sc2 !
Here are the original description:

Think of this game as simply Custom Hero Wars/Temple Siege/Dota + Family Guy Madness

How You Play:

- Start the game by picking a hero
- Look up its spells/special abilities at mission briefing, they can be cast by building units at your starport at middle left area of the map
- Take your hero and footmen to the center of the map, and start fighting enemy heroes and sacking the treasure box
- As you kill, the hero gains experience points (1 for footmen kill; 30 for hero kill) and money ($1 for footmen kill; $10 for hero kill)
- With enough experience pts, the hero levels up. This is indicated by a message telling you to upgrade and pings pointing to the middle left area of the map, where you have upgrade buildings. The hero receives ore in the 1000s, alternating between a x000 and x500 between each level up, and because of this you must alternate between attack upgrade and defense upgrade (and your hero’s upgrades remain even throughout the game – i.e., 1/1, 2/1, 2/2, 3/2, 3/3, 4/3, 4/4). THIS MONEY CANNOT BE USED TO UPGRADE FOOTMEN AND BUY ITEMS AT SHOP. It can only be used to upgrade your hero. (And does it make sense to upgrade footmen for $300 when you have $2000?) DO NOT TRY TO CHEAT BY UPGRADING FOR ANOTHER HERO. If you do not get your cash below $950 (do not save up more than $850), you will not be able to level up, buy items, or upgrade footmen
- If you have around $300 non-upgrade cash, you can upgrade your footmen by bringing your hero to the Upgrade Footmen beacon in your base. If you have more than $300, but you cannot upgrade your footmen, consider the following: 1) you may have maxed out the footmen level at level 6; 2) you may not have spent all of your upgrade money, in which case you must upgrade attack or armor for your hero (if your hero is a ghost, your armor is zerg carapace). 3) you do not have enough money
- The shop can be accessed at the middle left and right of the map. You can buy mana potion, health potion, and teleport home at shop, and have up to 2 of each in your inventory. You cast them by moving your infested Kerrigan to the beacon next to the shop.
- The mana fountain is at the center of the map. Once your hero’s spell level is 1 (aka 5 hero levels or 3 attack 2 armor upgrades) you start gaining mana and collecting bonus mana from the mana fountain.

You can give it a try : download