What happens when you challenge hundreds of elite programmers to put on their robes and wizard hats, enchant their minions to solve a constantly shifting multi-agent traveling salesman problem, use the loot to build mighty armies, and vie for eternal glory and tournament prizes?
You get a lot of clever coding, dirty tricks, attempted exploits, brilliant strategies, and an epic programming war that left millions of human and ogre widowers weeping for their fallen wives. And you get two unspeakably powerful Archmage champions.
Here are the results from our Greed multiplayer programming tournament. By the way, many of our talented players are open to job opportunities, so if you're hiring (or know someone who is), check out our employers page.
The Numbers
- 545 players submitted over 126,000 lines of solution code
- Each player spent an average of 10 hours crafting their solutions, for a total of 7.5 months of playtime
- The final ranking was performed with a 673-core computer cluster, which simulated 153,439 games in under one hour for just $5.74
- The war raged across 390 billion statements of player code executed
- Winners are taking home over $40,000 worth of prizes
The Winners
The #1 human champion is the undefeated Wizard Dude (Michael Heasell) with 363 wins, 0 losses, and 14 ties across all ogre opponents. In second is Vettax, with HighSea in third.
The #1 ogre champion is Bellardia (Ian Elliott) with 387 wins, 7 losses, and 14 ties, trailed by blinkingTore and Eye.
We’ve posted the full rankings here, with hundreds more terrifically strong players on both teams.
So is there one undisputed champion? Watch the intense head-to-head battle between human Wizard Dude and ogre Bellardia to find out if one can crush the other before the three-minute time limit! (Note: it may take several minutes to simulate on older hardware, even after the progress bar is full–tracking the bug here.)
Michael Heasell (Wizard Dude)
The top human player, Michael Heasell (Wizard Dude), is a 23-year-old software developer from the UK. He prepared years ahead for Greed, as he started programming for fun in his early teenage years by modding the RTS game Total Annihilation.
His coin collecting algorithm is very unique; he explains it in his own words.
My coin-collecting algorithm uses a novel forces-based mechanism to control movement. Each coin on the map applies an attractive force on collectors (peasants/peons) proportional to its value over distance squared. Allied collectors and the arena edges apply a repulsive force, pushing other collectors away. The sum of these forces produces a vector indicating the direction in which the collector should move this turn. The result is that:
- collectors naturally move towards clusters of coins that give the greatest overall payoff
- collectors spread out evenly to cover territory
Additionally, the value of each coin is scaled depending on its distance from the nearest enemy collector, weighting in favour of coins with an almost even distance. This encourages collectors not to chase lost coins, but to deprive the enemy of contested coins first and leave safer coins for later.
His unit production strategy is also very sophisticated. He uses an advanced AI architecture to coordinate a number of behaviors.
- Poke - Some opponents will build a large army in response to any attacker. I try to trick them into doing this by probing their base with a single soldier in the middle of the game.
- Collect - When gold is still plentiful or the enemy has more collectors than me, I build collectors, up to 6.
- Stockpile - When the enemy builds an army, I stockpile gold until I have enough to counter them.
- Defend - When the enemy arrives, I build only as many units as I need to counter the attack.
- Attack - To decide whether to attack, I use linear regression to predict an upper bound on the enemy's future gold reserves based on their collection history. I only attack in force if I am confident that, by the time my army gets to the enemy base, it will still be better than what my enemy could produce.
When we asked him how he thought of such an advanced strategy, he told us that he started with a greedy algorithm, tried to brainstorm better strategies, and:
One day a single word popped into my head: springs.
From this I quickly had a vision of spring-like forces pulling collectors around (a better analogy would be gravity/anti-gravity, but the word "springs" stuck). My initial implementation was disappointing and did not appear to be an improvement, but I wouldn't let it go, so I built my own simulation and found that, over hundreds of runs, it did just a little better on average. Things gradually got better from there.
Update: Michael has now written up his own blog post about his strategy.
Ian Elliott (Bellardia)
Ian Elliott (Bellardia), a Canadian software developer, won the top spot on the ogres leaderboard. On the forums, he explained his strategy.
My strategy dealt with mainly beating an opponent at his own pathing strategy.
Some universal truths of my workers first:
Always move at least 1.25 m per turn - provided I don't need to move the opposite direction next turn. This ensures that I maximize distance traveled over the course of a game. Never allow workers to target the same coin. Use state saving to store & precompute as much as possible. This includes vectors to each coin, armies and army values. Determine which coins were added and which were removed. Calculate a few metrics for each case. Be able to do this in After 80 seconds, I stop trying to steal coins. There's simply too few worth stealing - its more practical to simply find the highest weighted path. Continue to ignore all coins on the enemies path (I won't ignore a coin if it's directly behind an enemy but the enemy is moving away from it).4 * noperations.
- Figure out the direction each enemy worker is heading
- Grab the first coin the enemy will reach while following that path
- Determine if any of my workers can intersect that point before the enemy. Since I'm dealing with the actual directional vectors of the workers rather than coin positions, this works amazingly well. Most opponents will continue to race my workers for a lot longer than they should.
- Position my worker so that it will reach the coin first, and intersect back as close to the enemies path as possible, so I can continue to 1-up his pathing. Also continue to grab coins along the way if they still keep me in a favorable position.
- Ensure that my closest worker will steal the coin from the enemy. Make sure that several of my workers don't head towards the same coin. Enemy AI would race itself to the same coin surprisingly often late game.
- If I couldn't find a coin worth stealing, design a best path algorithm as follows:
- Grab the closest 3 coins by distance alone. These will be candidate coins for pathing, I call them "anchors". The bountyGold of anchors isn't considered when they're being chosen, just their distance from the worker.
- For each anchor, find the shortest hamiltonian path from the anchor, to "K" highest weighted coins in the area. Weight was simply ( distance / value ). Close coins could be ignored if they're low weighted.
- Select the overall minimum path, determined to be ( weight of anchor + weight of hamiltonian path )
- If a worker can't find any path at all, move him into an empty section of the map. This is a specific point determined as the centroid of all the coins that spawned in that area since game start.
After 120 seconds, I noticed a trend of people starting to segment their workers into 6 areas. There's also too few coins to provide a suitably minimal path to more than 1 or two coins, so I abandon all long term pathing. I try to remain in an advantaged position as follows:
- When enemy segments the map, segment it with him.
- Stop trying to find overall best path. Use the best path to only 2 coins. A worker will only consider coins that it's sure it can reach before an enemy and any allied worker.
- If we can't reach a coin, consider the enemy position instead of coin positions. Follow behind an enemy so that I'm in the same position, but 5m closer to the center of the segment. If the enemy moves near a corner, I'm now closer to all coins in the segment besides any coins in that corner. In this sense, even if I share a segment with an enemy, I always control more than 50% of its area, or am fetching a coin.
We asked Ian a bit about his experience playing and how he developed his solution.
I found CodeCombat on HackerNews. I've seen you on there a few times previously. I happened to be working on hacking features onto a different HTML5 RTS game when the tournament was released, and this tournament had prizes and competition!
I came up with my solution very slowly as I theory crafted various algorithms. I was focused mostly on graph and clustering algorithms. At first I was really concerned with the big O complexity, but after trying a few solutions out it was very clear that while most of these algorithms performed well for huge data sets, they were extremely poor with smaller ones due to their constant time overhead - I think that played the biggest role. Once I determined my algorithm choice, I spent a few days thinking of creative ways to reduce the amount of operations I needed to do common tasks, like tracking coins added/removed and finding nearest neighbours. My battle code is pretty embarrassing and I wrote most of it the night before the competition ended.
I loved playing! It really made me dig back into my CS routes and think creatively. Ranking my code after a big change was so nerve wracking! Battling against other top players, and trying to beat all their unique strategies with just one myself was very difficult, but very rewarding. I think this was the biggest appeal. I told myself I could win this tournament when I saw it on HN, and I had to follow through!
Some entertaining statistics
We were interested to see just how Greedy our players became during our final ranking. How much gold was collected during the final ranking? And how many units perished?
How much gold was collected?
We know that 8.2 units of currency spawn per second in a ratio of 5% gems, 10% gold, 20% copper, and 65% silver. Multiplying this by an average match length of 120 seconds a match with, say, a 90% collection rate, this gives 885.6 currency units per match. If we use the real-world value of silver to translate currency units into real-world value, we can estimate how much gold was collected in USD.
In the level editor, the size of a coin is 1 meter high by 1 meter wide. Coins are usually about 7% as deep as their diameter, so we know that a coin’s volume in game is approximately 0.07 meters cubed. 0.07 meters cubed of silver is 734kg, which at a market price of $627.07 dollars per kilogram, is worth $460,269.38, or $230,134.69 per currency unit. (Training a soldier apparently costs $2.3MM USD–about right!)
Multiplying this by the average amount of currency spawned per game, as well as the total number of games, it turns out the estimated value of coins collected is $31 trillion-perhaps three times the financial cost of WWII.
How many units died?
If we figure that 70% of gold was spent on units that were killed, that’s 620 gold spent on units per match. At an average price of 20 gold per unit, that’s 31 deaths per match. Multiplying that by 153,000 matches, over 4.6MM units perished. To put this in terms of world conflicts, about as many people died in the Napoleonic Wars as they did in Greed on Tuesday night.
As for civilian casualties (peasants and peons), this much is known:
- Many players read the targetPos of enemy peons to see if their peasants could snatch a closer coin away first.
- Some players then countered by reading the targetPos of those peasants to counter the steal.
- Player COGSMITH reported some success with detecting when an opponent would do this and intentionally setting a peasant’s targetPos off the edge of a cliff, causing the fatally clever enemy peon to fall to his death while yelling a Wilhelm scream.
So probably a few dozen civilians were lured to their doom during the tournament.