Hey all!
I just wanted to create this sort of off-topic thread, now that Greed tournament is done 
It was super fun to play against you guys!
Special mention to WizardDude, who seems is going to win xD
And as well to Ravenclaw, because of its interesting eco strategy, I still do not see the pattern!
Iām Urdaris ingame!
Well fought! I spent a bit of time today trying to figure out why I kept losing to you 
The distribution between the two races is definitely interesting. Iām currently sitting in 1st for ogres but the same code only places me 7th for humans. I assume most players have done similarly, making it seem like strategies definitely favor a specific race. Hard to say how much of this is due to chance alone.
I was really pleased with how massively you all crushed all my playtesting strategies. Out of the six strategies I developed while designing the level (which defeated all the playtesters), the best one only got up to around #150 on ogres by the end. Nice stomping, amigos.
Feel free to share any favorite tricks youāve been using!
I think it would be pretty fun in the near future to run through some of the winning strategies. @nick is this a good idea in your mind?
This has been a very educational experience. The 4000 execution constraint really put a limit on how I ended up tackling the code changes. I think itāll be cool to disclose the code of the top winners.
Hi all! Wizard Dude checking in. Itās been a blast competing against everyone for the past couple of weeks and Iām really eager to see the results. Competition for first place has been very fierce!
Iām very curious to learn what approaches other high ranking players took to solve the challenge and would love to read a post that went through some of the best ones. I plan to blog about my own strategy and its evolution once results have been posted, assuming this is okay with the CodeCombat team.
Best of luck to all competitors and many thanks to CodeCombat for hosting such an awesome competition!
Fun to see that some of the names here can give me nightmares (Mepath, youāre one of them 
, WizardDudeā¦cry )
You looked at the battle, and say : how possible, how he does that, ho my gā¦
So yes, if the top players are agree to share their code, it could be very very interesting. Maybe after a little rewrite to add comments and make the code more understandable by others (I know how a code can be a big mess after multiple optimisations).
Yeah, it was very fun. Each time I climbed to the top, Iād get overtaken, and then Iād have to figure out how to overtake that person, once I do, the cycle repeats itself.
I commented to a co-worker that itās going to be extremely fascinating how this āpure soldier rushā code which is doing ridiculously well, will have to evolve over the course of the next 3 weeks.
Let me know when you guys blog about it, itāll be a great read. At some point, I was investigating pathing algorithms, and vector based mathematics, and a lot of stuff, but I think the 4000 command limit restricted my approaches a lot. I have a theory that in the end, we all ultimately did a lot of the same thing, although clearly, others did it better.
Canāt wait for the reveal! GG everyone, I had a great time. See you guys at the next one, and I hope the next round would be as fun. Iāll probably organize my code better from the get-go. I honestly didnāt expect myself to be THIS involved, but Iām glad I did. Had a great time, learned a lot, and enjoyed a lot of the āattackingā, on ādefense messagesā, like ā¦ āI spit at thee from the depths of hell.ā That one cracked me up.
@Bellardia Ogres and humans start at different locations, so if your economic strategy is putting the workers in certain positions, it might be that the start position of the 4th worker is set good for humans but while playing ogres it has to cross the entire map. This a weakness of mine, I did not have time to fix this!
Agreed with the 4000 execution contraint. Same as mepath, I designed in paper an algorithm to figure out the best coins to pick up, but it was too resource consuming
Just wanted to say that it was a pleasure competing against you all.
And thanks to Codecombat for hosting this great game.
@WizardDude
Iām looking forward to your blogpost.
Iām also very keen on learning what the top ranked players used as their strategy
I plan to do a blogpost as well
Although it isnāt that much of a strategy on my partā¦
From the beginning my basic idea was:
Copy your enemy as much as possible, do things a little bit better than him, crush him near the end with overwhelming force.
Very good game guys!
Being a business logic developer, it was a blast to dive into creating game strategies. Though it did remind me of how much I forgot about geometry!
Thank you all for a wonderful diversion.
Nice to see so many posts.
It was a great experience and I had a lot of fun. I would love to read the top players strategies.
At least mine was:
Grab coins based on distance vs bounty
Split the maps in 6 zones, give priority to areas with more coins even if it was a coin closer (this way I avoid being stuck in an area with few coins spawning right next to me).
With more than one peon, I gave each of them a zone with the items in that zone, so O(n^2) operations would be less because n is a subset of the total items (To keep inside the 4000 execution constraint).
I obtained the two best items a peon could get. Then, when going to grab the first coin the peon is already moving towards the second one using the 5m radius for collection.
I think those where all the mainly features of my code. Another thing would be to discuss war strategies, but that would be too long xD
My strategy dealt with mainly beating an opponent at his own pathing strategy.
Some universal truths of my workers first:
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 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).
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:
I had a similar coin collection strategy to Zzadded:
It wasnāt until the last few hours that I realized I could look at what enemy peons were targeting, so I tried to avoid coins that we were both targeting and that they were closer to. I donāt think my implementation was very good though as this didnāt keep me from looking at the coin just beyond it that they would still beat me to. I thought about trying to see where they were going and beat them to it, but didnāt get around to that code.
Love your strategy and explanation Bellardia, would love to see the code that made this work. I tried doing a saved state of what coins were on the board and want disappeared and was added each time, but my implementation didnāt seem to help things.
Overall, a fun way to start learning javascript! (This was my first real experience doing anything big with it.)
Heh. I went through so many different calculations on money gathering it wasnāt funny.
I tried partitioning the map into equal sizes based on my number of peasants
I tried dividing the map into 35 sections and comparing (section value/2) / distance vs bountyĀ²/distance
I tried just bountyĀ²/distance (I found the bountyĀ² helped to weight the importance of gems and gold better without making it too strong).
I tried both with and without caring about the enemy peonās target and locations (a few times it seemed giving up on a coin because the enemy was closer ended up being bad luck due to the random distribution.)
The 4 sections had almost no calculations beyond that point and I threw it back up because it seemed every time I changed anything, my code performed worse. Iām not sure why, but that sectioning still performs the best out of those that I tried. :\
I was overall happy with the money collection of each of those. Often times if I lost, it was due to army composition, not the gold.
I canāt wait for more of these multiplayer challenge levels.
I hope I get to see your code someday. Looks to be an extremely exciting read.
Good idea to start the discussion with gold collection.
I started also with 4 areas. Easiest way to assign the items to peons.
Great for 4 peons, or 2.
For 5 and 6, I also put them in the middle, overlapping the first areas. Not the best, but efficient the first week.
And for 3 peons, not good at all. And it was not possible to overlap the regions.
So I changed the strategy using a big table : For each peons.length = n, I define the n centers, correctly placed on the grid, and a radius for the region. So Iām able to spread region as I want based on n.
And in a loop for each peon, I assign him a region center, and I loop through all the items to measure the distance from the item to his center.
If the distance is too high (>radius), abandon the item for this peon, out of zone.
So I have round shape areas for each of them, with little overlapping on the edge.
For each Item in the circle, I calculate a value based on : Distance to peon, Distance to center, gold value, andā¦ the age of the item.
For the last point, I remark that new items are added at the beginning of the table. The idea is that : if an item is old, maybe itās in an area not visited for long, so maybe there is a lot of other item around not visited, so maybe itās a good idea to go there. Itās interesting at the begining of the battle, when there is not a lot of peons, and a lot of items.
These 4 parameters are mixed with constant to equilibrate the finale value, to find the best target in the area.
Theses constants could be different based on the number of peon at a given time. It ends up in a formula very difficult to fine tune, depending of the enemy, and of the seed. And you have to test and try a lot to get the idea of the best overall config (maybe not the most interesting part of the job).
I did not take advantage of the 5 meters circle to take item. My understanding is that : as soon as the peon enter the circle, It will take the item, so itās not in the list anymore, so the peon will go to another destination. He donāt have to really go to the center. Ok, If you know the 2 most interesting items, maybe you can optimize a little bit (but itās too complex for me ).
I tryed multiple very good ideas that all ends up in lower ranking.
Last optimization : avoid two peons to target the same item. Itās possible in my code because of the region overlap. And this management is critical when you have 6 peons, because you have only 3 or 4 items on the whole grid. Not so simple, it reach me very close to 4000 statements with 3 peons and 40 or 50 items, and it adds a lot of code not very efficient.
Also, when no target, the peon return to the center of itās area (like a spider
I think thatās all for the most important part of the game. Compared to it, building troops was just fun.
Iām curious if someone have a complete different approach, without areas for each peon. With just an algorithm to avoid them to go all in the same corner.
The other approach for assigning peons/items is to find the best item for each collector, avoiding items that are likely to be collected by the enemy and that were already assigned to the other collector, and then solve the assignment problem, fixing the suboptimality caused by the initial assignment order. This is good for early stages of the game, when you can quickly collect rich clusters with all the collectors while the enemy is using only the zoned one. It is not so good at the later stages when you have to wait for items to appear.
My implementation did not take into account various details, like 5m radius or allowing more then one preferable coins for a collector. Iām so lazy sometimesā¦especially when each change can impose hidden bugs that does not cause any runtime errors but create a lot of useless āundefinedā values.
Another trick is to make your tagetPos different from the coin.pos you want to collect, so that enemy code canāt detect what you want to collect easily. Calculating the enemy direction is much more complicated. But when you code skip some steps, your collectors can fall of the cliff and dieā¦ I was so surprised when I noticed only three collectors at the end of the simulation.
The idea for the combat is to build the units simultaneously. Other ideas like delaying the building until you have significantly more gold than enemy does or balancing the wizards with warriors or disabling captains and flying guys because they are nearly useless are less important. Ideally we should find something like āzerg crush protoss, protoss crush humans, humans crush zergsā for different unit types, but i didnāt notice any complicated balance of such type.
Wait! Am I to understand that you only had to be 5m from the item in order to collect it!?!?
Once again things that could have been brought to my attention YESTERDAY!
Ha, that lack of knowledge probably saved me another 2 hours or so of extra work, so all is well. Hahaha.
My coin collection strategy is a bit different. I used the Newtonās law of universal gravitation.
If you change the divisor, from Math.pow(distance,2) to Math.pow(distance,Lim -> infinite), the resultant vector will point to the nearest coin.
I tried with different values searching for balance between heading towards the nearest coin and regions with many coins.
With more than three workers I divide the map in zones and search the nearest coin.