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=PLL61h44ln0J0Pbs2EPR71wn-8wvwxHI9z&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 trade-off 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 all-in 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 non-domination 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 non-domination), 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 !
6 Likes
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 mini-games at once
- mini-games with the least medals (3*g+s)
- mini-games where their opponents have the least medals (to deny them)
- mini-games for which the issue is NOT certain (if the gap between 2 players is huge in a mini-game, 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 mini-games
- I ignore mini-games 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 mini-game.
There is another criterion in the eval of my moves with bigger coeff : I add virtual medals (who is currently winning in each mini-game, or won it ?)
and I calculate the real score (multiplication) of each player considering the ānewā amount of medals per mini-game per player.
This criterion is strongly ponderated in the eval of my moves.
I play the move maximizing this global eval.
4 Likes
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
Finished 349/5237 around top 300 in the Gold League.
This is my best result in a contest, so far and it marks my 3rd contest finishing in the Gold League. I know itās hardly impressive, but it is for me, I see progress, indeed very small and rather slow, but I feel improvement in myself.
I always have very hard time managing my time for contests and I usually end up with most of the time spend on the proper simulation of the game state and I always complain that games are very hard to simulate, because we have to take into account physics, vectors, randomness and so on. But when I saw this task, I instantly realized that it would be friendly for simulation and with low branching factor, I said to myself that this is my time to shine So what I did:
I was very busy during the contest we had releases at work, I had to teach several lectures at a university course, 2 family vacations, ā¦ But I somehow managed to code for the contest at least 3 hours a day, mostly during the night, unfortunately.
Wood 2 league
I output the action, which gives the farthest position on the hurdle track, without a stun for my player.
Wood 1 league
Things started to get tricky. Tried several āif/esleā strategies, nothing worked. At the end Iāve evaluated each move and summed up the positions of my players, choosing the move with the best sum
Bronze/Silver leagues
Quickly realized that āif/esleā strategies wonāt work. Decided to make the simulation of the game state right away, as excepted this time a decent simulation was done in a couple of hours, referencing the official referee.
Afterwards Iāve tried to evaluate the moves, but didnāt like the approach. For first time Iāve decided to implement early(before the silver league was opened) a search algorithm for the game and I was pretty sure that a Genetic Algorithm would do very well. Iāve considered the task as an optimization one, try to improve my score as much as possible, thatās mainly why I chose GA. Iāve managed to implement it relatively quickly using almost the same approach and code that Iāve described in my CG blog post.
The most important thing in a Genetic Algorithm is the evaluation function. My idea was to simulate the mini games until the first Game Over and evaluate each separately:
HURDLE: closer to the finish, better
ARCHERY: closer the center, better
SKATING: more distance traveled, better
DIVING: bigger score, better
For each mini game evaluation I also include bonuses for gold and silver medals. If I do not have medals in a mini game I divide the evaluation by 2.
And this actually worked pretty well when the Silver and Gold leagues were opened I was directly promoted in them automatically. I couldnāt believe the results
Gold league
Since my GA played well so far I thought that itās the right choice and I could reached the Legend league using it. Iāve tried improving the simulation, the evaluation function, the initial population to start with the perfect moves for all mini games, tweaking the GA parametersā¦ but unfortunately nothing worked and for days I didnāt improve my rank.
Iāve consulted the discord server and saw that there were other players using GA with better ranks than me. But the main topic was that majority of players are using MCTS. I had implement MCTS on CG before but only for sequential games. In one simultaneous game Iāve managed to use MCTS. Iāve tried to port it for this game, but only a couple of days were left and I couldnāt.
Wins
Iām very happy that Iāve managed to implement a search algorithm early in the contest.
Iāve tried to improve my approach based on my remarks from the previous constest.
Mistakes
Considering the task as an optimization one was wrong. I didnāt include the opponent score in the final evaluations of the state.
Iāve ignored MCTS until the end of the contest.
Overall I liked the contest, I even gŠ¾t a little obsessed with it and afterwards I had a very big desire to reach the Legend league and Iām happy to report that Iāve managed
Reaching top 100 in a bot contest is still on the list of my dreams
1 Like
Can I ask you a question? Sorry ot bother you.
I want to know how do you choose the game to play when itās not random?
I donāt know what you mean. Youāre going to have to be more specific, referring to my post mortem.
You said 
I truncated my UCT forest after 5 moves. That meant I didnāt expand the tree beyond that and instead finished randomly. Finishing it completely is worse because your bot will think it can do a perfect diving game for example, because the other games donāt exist (in reality they do)
How do you backpropagate after 5 moves ? On which nodes ?
On the nodes of the UCT forest. You need to look into how that works before you can understand the post mortem. I have an article about it on my profile (a playground called Smitsimax)
Hi, Can I ask you a question ?
You said:
āmcts styleā rollouts: I do fully random rollouts until all minigames are ended. So the depth can vary depending on the state of the turn (if all minigames needs to be finished, the tree will be deeper). For skating, I randomize the gpu at each search iteration (that feature was a noticeable boost)
What is a roll out? How do you select a node ? you choose your node by uct and after you do a full random rollout, and backpropagate?
Thank you !!!
In a plain old MCTS, you do your selection with UCT, and when you reach a non expanded node, you expand it, pick a random child, and from there you do a simulation (which is also called a ārolloutā), by playing randomly until the end of the game (more or less).
Answers to your questions depends on the algorithm, iāll try to explain for smitsimax, as it is the one I last submitted.
With smitsimax you keep one MCTS tree per player, and play with all of them simultaneously. So basically:
- for each player, do a selection in its own tree (ie pick the action with UCT). If in a tree you reach a leaf node, expand it, and pick an action randomly (hence the ārolloutā). This gives an array of actions (one per player). Play it in order to move on to the next gamestate.
- Repeat 1 until you reach the end of the game (in this case, I stopped when all minigames were finished, as I said).
- Once done, score the gamestate for each player, and backpropagate in its own tree.
With smitsimax, a node in a tree does not relate to a specific game state, but more to an aggregation of what can happen if a player follows this line of play (as the values that will be backpropagated will correspond to many situations this line of play ended up into, while other players did what they thought to be best for themā¦which can be different across iterations, as āwhat is bestā evolves independently for each player).
As MSmits said, you have to understand the algorithm (and from my point of view, the best is to implement it to understand it )
Hi, thank to answer !!!
Can you see my implementation on Github. I want to know if itās a good Smitsimax implementation. The Smitsimax begin at line 745:
This is the link : Olymbits/olymbits_codingame.py at main Ā· regismeyssonnier/Olymbits Ā· GitHub