Hi ! I just passed legend using Python 3.
I started with a determinitic approach in the first leagues. Quickly, I implemented my own Tron game to try different approaches. It helped a lot !
I found some reading around the web on Tron problem. I went for a Monte Carlo Tree Search approach (sounded sexy and cool) and I based my evaluations on Voronoi, Articulation points and Tree of chambers (found a publication taking about it, then others post-mortems).
My solution worked somewhat fine and despite several optimizations, the performance remained too high for CodinGame. However it helped a lot for having a nice evaluation approach.I tried a minimax approach with alpha beta pruning but the performance were worse. The probabilistic approach of MCTS allows to go deeper with less evaluations.
I changed my deterministic algorithm to add all the new things that I learned (voronoi, articulation points, …).
I went directly from Silver to Gold with this.
The passage to gold to legend was made possible by introducing more flexibility in my scoring function (and adding the possibility to merge chambers in the tree of chambers algorithm).
At the end the function was a ponderation of :
- maximizing my remaining space (ratio between previous and new position)
- minimizing all the adversaries space (ratio between previous and new position for each one not globally)
- minimizing the number of conflict points (voronoi diagram) (ratio between previous and new position)
- minimizing the number of articulation points (trying to have more freedom on the mid-long term)
Very interesting challenge ! Less easy that you can think ! Lot of graph theory behind the scene.
Python is maybe not the best solution to try a minimax or MCTS approach due to time constraint (nevertheless I learned a lot about these algorithms). I am glad I was able to find a deterministic algorithm. If there was a next step, it should be to take this algorithm and implement it into C++ to try again MCTS.