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

Footmen Frenzy v7.0

7.1b Changes

1) Spasmic Heave works as intended
2) HP ups balanced a bit more
3) Grunt base HP reduced a bit
4) Duration of invuln potion decreased
5) CD of healing alcy healing spray increased - mana tweaked a bit
6) Factory and cluster rockets buffed (Tinker)
7) Scepter does 975 damage
8) Hunts slightly buffed
9) Bounties of units adjusted slightly
10) Removed hotkeys from heroes in tavern (I hate accidentally choosing a hero when I type)
11) Attack/Defense ups are available at 5 minutes
12) Choppers take less damage from wisps (it was silly that two wisps could completely counter an ult...)
13) Keldyns ult is preloaded (should eliminate lag)
14) Blades dont hit invis units anymore
15) Fixed backstab trigger
16) Firelord has increased base strength and strength gain per level. Incinerate now does full damage in an aoe and half damage in twice that aoe.
17) HCL fixed

7.1 Changes

-Berserker Aura fixed
-Several hotkey issues fixed
-Creep upgrades now go to level 4, not just level 2
-'Allied to player 16' message is gone
-Hopefully the game not ending problem is fixed, but not sure on this one. Once we find out exactly what is causing it, I can fix it for sure.
-Stasis trap should work correctly.
-HP upgrades are a bit more effective
-Attack ups do 20% and lower tiers get a little more than before.
-Berserker ult attack is now working correctly - should attack 4/5/7 units at a time now
-GW ship does not give bonus cash
-lvl 2 mana flare doesnt affect your own units
-silence is working correctly
-XP needed to level is increased and fixed
-crypt fiends health increased a bit and collision decreased a bit
-Sharon's ult fixed
-Healing ward of the gods heals itself correctly

7.0b Changes

-You can now hotkey shops
-All previous bugs should be fixed


DH - Evasion to 10/20/30/40/50/60. Slight nerf to splash damage.
Naga - nerf to tornado. slight decrease in immo, decrease in move speed reduction and leash range.
Warden - nerf to blink cd to actually give a reason to max it (higher at earlier and lower at later levels). Decrease in maximum damage of FoK at levels 5 and 6.
Panda - nerf to breath of fire, drunken haze.
Potm - lvl 6 owl scout gives 4 owls instead of 2 now =p
Holy Guardian - Holy Grace hero duration buffed
High level towers have bigger splash and very quick attack
Falcon - Fixed cripple level skip
- buffed lvl 3 Ultimate
Pally - buffed Devotion to 2/4/6/9/12/16
KotG - lvl 5 treant hp fixed
Tortured Soul - Buffed Wail of the Banshee
Frost Sphere in the first spell position
DR/Far Seer - Silence now blocks ranged at lvl 5 and melee+range at lvl 6
Digit/Pit Lord - Howl lvl 1 decreased to 25%
Roaaaarrrr - ult no longer hits ethereal
Blademaster - WW move speed increased
Countermage - Lightning Storm no longer hits Dead Units.
Firelord - Volcano no longer hits friendly units.

NEW HERO (Berserker) - Blades of Fury - The Berserker pulls out a number blades and throws them at his enemies. The blades home in on the enemy and deals damage upon collision. Number of blades and damage increases with level.
Spasmic Heave - The Berserker grabs a nearby unit or hero and flings him away. The starting distance between the hero and unit is equal to the distance the unit will be thrown. When the unit lands, it takes damage based on the distance it was thrown and also deals smash damage to units in a small area. This can be set to autocast.
Berserker Aura - Nearby units are empowered by the strength of the Berserker, allowing them a chance to critical strike nearby units. Higher levels increase the chance and multiplier.
Enraged Wyvern - The Berserker summons his fury to transform into an enraged wyvern. The Wyvern has increased hit points, faster attack, and can attack multiple targets. Raising the level raises the bonus and the duration.

Unit Changes
Removed auto tier. There is still a delay for tier1, but it isnt free. Can be bought at 5 minutes.
Went through every single unit, creep, and summon and balanced the levels and experience given. This is balanced on the strength of the unit, the spawn rate, and whether or not it is ranged. Ranged units give more XP than melee
All melee given significantly more armor and a bit more hp.
Mana removed from units
Knights spawn rate decreased to 8 seconds
Dryads spawn rate increased to 8.5 seconds

Creep Changes
Spirit Link duration decreased
All active creep abilities have 4 levels that are latently increased as the game goes on. Level is increased at 10/20/30/60 minutes

Item Changes

Item cooldown adjusted for several early game items.
Berserker mask raised to 300
Circlet to 175
Speed Scroll - 2 charges 125 gold
Healing ward of the Gods now heals itself
Roar Scroll to 450
Nikes to 550


Gold tooltip (at the top of the map) changed
Thebiggame tooltip (at the top of the map) changed
Wrath of TekPike tooltip displays damage
Added information to ankh tooltip
Socks hotkey changed to 'C'

Gameplay Changes

Attack upgrade costs are decreased significantly. % decreased slightly.
Defense upgrades % increased at earlier levels
Some balancing to racial abilities.
Switched orc tier 1 to regular peons and tier 2 to grunts and balanced accordingly. Peons just seem weaker, so I think they should be tier1.
Heroes are now autorevived according to their level - Formula is 23+(lvl * 2) that comes out to 25 seconds at lvl 1 and 59 seconds at lvl 18.
Hero gold bounty is also dependent on level now. Formula is (lvl *25)+ 125. (For BillK and Ava it is + 425)
Adjusted experience given by heroes. Higher level heroes give significantly more XP.
XP gain range increased significantly.
You can no longer see enemy items.
Your base is repeatedly pinged if an ally attacks it and their units' attack and move speed is drastically decreased.
Tier upgrades now have a hotkey.
No longer a penalty for canceling upgrades.
ghoul summons gold bounty corrected
keldyn summon bounty decreased slightly
Adjusted the gold cost of all summons (this really just matters for sharon's ult)
Increased cost of golem to 4k and slightly decreased hp regen
HCL commands are working properly
W3MMD system is in place for stats and Frenzy ladder

Thursday, February 18, 2010

Starcraft 2 Beta is out !

The big news has arrived !
StarCraft II: Wings of Liberty was released today. Even it is a closed beta it has been released to p2p: just take a look: In order to be able to play you need a SC2 beta key.

Hell, It's About Time !