Hi! Can I ask what other optimization contests on other platforms?
Hi sprkrd!
Here is an almost complete list of most common online coding competition:
HackerRank
Topcoder
CodeChef
Google Code Jam
LeetCode
International Collegiate Programming Contest
Google Hash Code
HackerEarth
ICFP Programming Contest
Microsoft Imagine Cup
Codewars
Project Euler
Advent of Code
Company contests
Codeforces
Coderbyte
GeeksforGeeks
Battlecode
Halite
Kaggle
I have two or three others in mind.
I guess someone will complete and will adjust this list (it will be perhaps me).
Keep practice and come back here for each spring summer fall and winter challenge.
CodeVanguard
Code Jam and Hash Code are discontinued.
Also, OP is referring to optim contests, not general CP contests
Ended up #58 Legend.
Better late than neverā¦
Iām really proud I could go so far despite my lack of experience. Iād love for this PM to inspire ppl with better coding skills to implement this approach and show me how far it can go =) Pls get in touch if you do.
Approach
I used GA. My first implementation would compute the fitness of an individual by blending together performance in the 3 minigames (I never considered skating). I realized quite quickly this approach would hit a hard limit. The game isnt about playing all minigames decently at the same time, but about choosing which fights to take and which to concede.
Enters NSGA II. The main idea is to evolve our populations without any assumptions about which game to prioritize nor how hard. Given two solutions that outperform each other on different games, we cannot say which is betterāthey are simply not comparable, neither of them ādominatesā the other. However, there are plenty of cases where a solution outperforms another in every game; this solution dominates the other one. We can then sort solutions by āPareto frontsā. Front 0 contains solutions which are dominated by none, front 1 those who are only dominated by front 0, front 2 only 0 or 1, etc.
If you want to delve more into it, I cannot recommend enough the last videos of this amazing playlist : https://youtube.com/playlist?list=PLL61h44ln0J0Pbs2EPR71wn8wvwxHI9z&si=D4pT3GBfnpDXQtiu
I simulated each player equally, as to obtain (hopefully) every locally optimal solution, by which I mean the best scoring solution for a specific tradeoff between games. I then matched my solutions against all the possible pairs of enemy locally optimal solutions, and chose the one giving me the best average āscoreā. For the first half of the games I add the medals points together so my algo doesnāt think 3 silver first turn is better than 2 golds and 1 bronze, and after a while I plug the actual multiplicative formula.
What worked

Eugenism ! It is trivial to find optimal diving strategies. It is also relatively easy to generate perfect runners en masse. There is indeed often plenty of different perfect runners (there are 15 ways to cover 7 empty squares in 3 turns!). Kickstarting my evolution process with multiple of these gave amazing improvements.

Much bigger population size than expected. I assumed 100 would be a good number and ended up with 682 (683 would make my population occupy a bigger power of two number of bytes).

Using real time instead of cpu time greatly diminished the number of random timeouts I experienced.

Going allin on not playing for skate gave much better results than one could expect. Sure all my loses could be attributed to poor skating performance. But getting better at the 3 other games meant my enemies would either get starved in medals in other games or had to deprioritize skating and play the game on my own terms.
Possible Improvements

My nondomination sort is quite crude. I was unable to understand the nlog(n) approach explained in a paper. I was concerned the nn approach that precomputes every domination relations would be too slow. I ended up on a nn worst case but often better, that may be slightly off past front 0. There might be a faster, more exact or even both implementation out there.

I did not implement crowding distance computation. That may hurt in two ways : diminishing the genetic diversity during the evolution (even though we are guaranteed some baseline level of diversity due to sorting by nondomination), but most importantly if an opponent has multiple similar solutions on front 0, I will overfit against these due to how I pick which solution of my front 0 to play.

The way I pick which of my front 0 solution to play is very flawedā¦ I suppose it worked great in Gold because ppl would pick some locally optimal solution. But assuming we did get all locally optimum solution (most of the time I had < 5, peaking to ~20 a few turns per game), this is a Nash equlibria problem. Iterated elimination of strictly dominated strategies would be a clear, improvementā¦ Then pick an āanytimeā nash equilibrium search algorithm.

My algo doesnāt even know about the existence of skating. I guess you could consider it a fourth dimension, even though it might just add to much noise in the limited computation time. I tried without success to bias my final choice depending on skating, but with mediocre heuristics. Iām pretty sure my algo would get better scores if I told it to drop everything on the last round to guarantee a gold medal in skating x)

I couldnāt set up a local testing environment, so there might be a lot of perf left in optimizing the parameters.

When a game ends my population diversity crashes, there must be a smarter way to deal with it. Making the algo understand that if a game has ended we need to keep as much options as possible in the next turns as to accommodate for the next round.
A big thank to the organizing for this thrilling competition !
Hello !
leojean890, 210/5237 (global), 15/1944 (python), 148/980 (gold)
Congratz to CG for having this interesting contest idea and organizing it, and congratz to all players !
My overall approach is a bruteforce (depth 5) applied each turn for each player.
First, I apply it on both opponents moves. I score each reached state at depth 5.
eval : I consider that each opponent will play :
 a move combination favoring several minigames at once
 minigames with the least medals (3*g+s)
 minigames where their opponents have the least medals (to deny them)
 minigames for which the issue is NOT certain (if the gap between 2 players is huge in a minigame, we may sometimes consider that the issue is fully or almost determined) => I use some ponderation about this criterion too
 I use lower coeff for skating and normalized coeffs for other minigames
 I ignore minigames that wonāt end before turn 100 and I donāt restart games finished during my depth 5 sim with random parameters.
I store/return each opponentās state maximizing this eval at depth 5 to use it in the second part.
Second, I apply this bruteforce on my own moves. I score each reached state at depth 5.
I use almost the same eval than described upper but mostly considering if Iām beating the opponents ābest reached state at depth 5ā and at which point in each minigame.
There is another criterion in the eval of my moves with bigger coeff : I add virtual medals (who is currently winning in each minigame, or won it ?)
and I calculate the real score (multiplication) of each player considering the ānewā amount of medals per minigame per player.
This criterion is strongly ponderated in the eval of my moves.
I play the move maximizing this global eval.
Hi,
Sorry for the late reply. It was mostly the ICPC challenge sponsored by huawei (codeforces). I did this 3 times. But also did atcoder once or twice and some topcoder.
There also were russian AI cups, very interesting bots programming contests (harder than CG and lasting for 1 month ; nice local visualizer/tester available). But Iām not sure what it will be then in the future