We are done, Greeders! Comments and random thoughts


#1

Hey all!

I just wanted to create this sort of off-topic thread, now that Greed tournament is done :slight_smile:

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!


#2

Well fought! I spent a bit of time today trying to figure out why I kept losing to you :frowning:

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.


#3

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!


#4

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?


#5

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.


#6

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!


#7

Fun to see that some of the names here can give me nightmares (Mepath, you’re one of them :wink: , 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).


#8

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.


#9

@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 :frowning:


#10

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.


#11

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.


#12

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


#13

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 4 * n operations.

  1. Figure out the direction each enemy worker is heading

  2. Grab the first coin the enemy will reach while following that path

  3. 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.

  4. 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.

  5. 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.

  6. If I couldn’t find a coin worth stealing, design a best path algorithm as follows:

  7. 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.

  8. 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.

  9. Select the overall minimum path, determined to be ( weight of anchor + weight of hamiltonian path )

  10. 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:

  1. When enemy segments the map, segment it with him.
  2. 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.
  3. 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.

#14

I had a similar coin collection strategy to Zzadded:

  • Do a quick check for any gem within 20 units, any gold-coin within 12, any other coin within 8.
  • Divide into 4 zones and assign each peon to a zone based on the total value of that zone while also deducting my distance from the center of the zone.
  • Once in the zone, look for the coin that has the most value within 15 units of it.
  • Of those nearby items, go to the nearest.
  • When I build my 5th peon (only build a 5th if the enemy has built at least 4) assign him to a quarter of the board centered at the middle. Thus I end up with 5 regions, all with an overlap.
  • At my 6th peon, repartition into 6 regions.

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.)


#15

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.


#16

I hope I get to see your code someday. Looks to be an extremely exciting read.


#17

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 :slight_smile: ).

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 :wink:

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.


#18

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.


#19

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.


#20

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.