I finished 7th but I am one of the creators. I will write something short as I’m sure the top players will write some nice postmortems.
Search Algo
It was pretty obvious to a lot of people that this game needs to be approached by some kind of search algorithm. For one thing the game has a lot of collisions going on that would be very hard to take into account in a heuristic bot. I had a buggy game engine ready before the contest (reimplementing helped us find referee bugs, I’m glad weren’t present in the final game). I took my time to fix the last major issue in my engine on Tuesday.
I searched with Simulated Annealing (SA). I never really used genetic algorithms (GA). I figure SA is inspired from Physics and GA is inspired from Biology, it is therefore obvious that SA is better. (@CG where is the Kappa emoji?)
Handling of skills
In my search I handled skills in the dumbest way I could think of: If SKILL is selected (10% chance) then the reaper tries to tar itself (to become really heavy+high speed and knock people away), the destroyer tries to throw a grenade on the Reaper, to push everyone away from it, and the Doof tries to throw oil on the nearest wreck (either the centre of the wreck or the closest point that allows to cover the entire wreck. I felt that partial oils that prevent looting for only 1 turn could be a massive waste of rage).
This is obviously not optimal but in many games it was enough to use up my rage. It occurs to me that I should probably have tried to grenade around the reaper to give it a speed boost.
Eval
I didn’t make much effort on my eval as I didn’t even make a local arena for the contest.
-
1 point per unit of water
-
-0.1 points per unit of enemy water
-
1e-3*MyRage
-
-1e-5*Dist(reaper,nearest_wreck) if there is a wreck
-
-1e-5*Dist(reaper,destroyer)
-
-2e-5*max(0,Dist(destroyer,nearest_tanker)-200-tanker_radius-destroyer_radius) (Get close but don’t encourage closer than 200)
-
1e-3*Number_Of_Tankers (Don’t destroy tankers)
-
1e-5*Doof_Speed
-
-1e-5*Dist(Doof,enemy_reaper)
Where enemy_reaper is the reaper of the enemy with the closest score to mine. I figure that annoying the player with the score closest to mine is most likely to affect the final outcome of the game. Extreme example: Why annoy the player who is 20 points ahead of me when I can try to keep the other player a few points below me?
I dissuade breaking tankers because I want my AI to destroy tankers as late as possible. Ideally my reaper will harvest the wreck on the same turn as the tanker is destroyed. Why destroy it early and give other players the opportunity to contest the wreck and/or oil it?
I evaluated as Eval(state after first move)+0.95*Eval(state after second move)+…
I think I have a big margin for improvement in my eval as I made very little effort to improve it.
Dummy
I had only: Reaper goes to nearest wreck (-its speed according to the popular CSB formula). Destroyer and Doof wait. For me this dummy is a very safe assumption.
I might have some room for improvement in this aspect but I suspected and found that making assumptions about enemy movement can easily be worse than assuming a WAIT.
Optimisation of Search
I found that the quality of the search affected the strength of the AI significantly. Performance is therefore probably very important but I focused only on the search itself. I wrote some code to take 20 states from real games and locally Search those states over and over to look at the average score. Using this metric I optimised my SA’s parameters. I used an exponential cooling schedule:
current_temp=Max_Temperature*exp(-Temperature_Exp_Decay*fraction_time_spent)
Max_Temperature=100
Temperature_Exp_Decay=10
fraction_time_spent=time_spent/time_limit
Every 100 iterations I reset the current solution to the best one ever seen. I also found that searching with moves described as (target,acc) was better than (angle,acc). I suspected this because if you have a sequence of N (angle,acc), when you change the first angle you end up at a very different location, so “small mutations” aren’t so small anymore which goes against the principle of SA to search in the neighbourhood of a solution.
I searched 4 turns ahead, this is probably a very important parameter but I didn’t test any other values.
Conclusion
In the end me and pb4 decided to stop improving our AIs to ensure we didn’t finish in the top3. We wanted to avoid devaluing finishing on the podium. “I am first but there are two people in front of me”.