Tron Battle (aka Line Racing) multiplayer challenge discussion

Nice ! :smile:

Anyone have any thoughts or anecdotes about using MinMax vs MaxN (>2 player extension of MinMax)?

MinMax is cheaper to execute, but MaxN is likely to model opponents better.

Try to count the amount of squares by going one direction compared to another direction.

Do anyone have any some rules of thumb to play this game?

MinMax is not good enough, u need a good way to value the board

Minmax works quite well actually. That is what I’ve been using up until now.

Hello,
I would like to share what I have implemented to become at the top of the gold league.

  1. Save/update the map and remove opponents track when they are dead
  2. Implement the logic describe in the “Tron Top 5%” to fill the map and get a score for the 4th directions.
    2.a) Here is how I compute the score using the result of step 2) for each direction :
    10000 * nb_of_my_tiles - 10 * sum_of_opponents_tiles - nb_of_possible_moves

This means that this are my priorities:
Goal 1 : maximize my number of tiles
Goal 2 : minimize opponents number of tiles
Goal 3 : choose a move with as less as liberties as possible

The goal number 3 will only append when you are alone in a space. This will allow you to fill quite efficiently your space =).

Next goal : implement a minimax on this strategy :).

See you in master league :wink:

9 Likes

Not enough to be the best but for gold it’s a good strategy :grinning:

Minimax + Alpha + killer works well for me but what is really important in tron and take a lot of time computing i think is the evaluation function.

Good luck!

An update to my previous post.
I am currently in position 63 in master league.

To go in master league I just added:

  • being able to know if I am alone
  • in that case, compute 5 turns in advance and try to keep a path to weekest opponents
    This works pretty well for 1v1v1v1 :slight_smile: .

I have added a minimax, but as Razielwar told, it is truly hard to have a good evaluation function!
Here is an example:


At step 44, my evaluation give the same result for UP and LEFT. It would have been better to go LEFT, but I have no idea on how to “evaluate” it O_o.

See you in the next update :wink:

1 Like

Has anyone been able to get a neural net working for this challenge? I’m having a hard time further optimizing my implementation, so I’m considering trying to fiddle around with the deep mind code Google released a couple of years ago to see if I can get a better value function.

I think it’s my last update on tron :cry:.
I am currently in the top 10 :smile:

Here is what I have added:

  • Being able to manage Connection Points (see google post-mortem): this was pretty hard! When I am alone it is correctly handled, otherwise I am not sure that it’s perfectly handled…
  • Only take into account nearest(s) player(s) for minimax (in fact it is a max(n))

In order to have a feedback on my battles, I used this link:
http://cgstats.magusgeek.com/app
I didn’t checked if there is a post about it, but it is pretty useful :wink:

2 Likes

Hi, guys

Has anyone had any chance using Python3 for this problem? It takes me ~10ms to compute number of reachable cells, which limits the minmax to ~10 combinations - roughly two moves in future. Is this problem with Python3 or with my programming?

If you are doing BFS, don’t use a Python list as a queue. The method .pop(0) (and .insert(0, ...)) is very expensive on a list since it requires reindexing the whole list. Instead, use the deque object in the collections module. (A list is OK as a stack, but I think deque is still better.)

There are also other more subtle improvements you can make. Try timing parts of your code to see what is taking the longest. However, in the end, Python isn’t as fast as other languages. If I remember correctly, I can run the Voronoi heuristic about 150 times with Python 3 in the time allotted (and that is after a lot of tricks to speed up that part).

2 Likes

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.

5 Likes

Hi, I am having lots of trouble in my attempt to get legend league.

I got gold with a voronoi diagram that gave equal weightage to me and my opponents nodes.

After this, I implemented the following:

  1. Minimax with closest opponent till depth 5
  2. Voronoi diagram with all players
  3. Update voronoi by subtracting the number of possible moves I have (for filling)
  4. If isolated, depth 5 filling algorithm (basically only max)

Of course, it is highly probable that my implementation has been wrong, bit still some help on what else I can try will be appreciated.

Thanking you,
CyberLemonade

Hi,

The closest opponent may not be the most dangerous, and you can try to change your minimax by including all the players :
depth n : you
depth n-1 ; other player 1
depth n-2 ; other player 2

depth 0 ; eval your voronoi
It is somehow pessimistic, because it considers that everyone is fighting against you, and it will reduce your horizon. But it seemed to improve my results and get me to legend.

There is also a trick you can do in your evaluation, see part “evaluation heuristic tweaking” in https://www.a1k0n.net/2010/03/04/google-ai-postmortem.html. It helps you follow the borders.

1 Like

Thank you so much. I will definitely try it out :slight_smile:

Anyone have examples of how to do something like minimax or alpha-beta pruning with more than two players? The pseudo-code I used is very specific to two players and I am having some trouble adapting it to 3 or 4.

I am all about pure MCTS for this, because that is most (ehm!) relevant to my academic studies. Spending a lot of time on crafting an evaluation function may be less valuable.

At first I thought that moves were simultaneous, so I made an incredibly slow plain MCTS solution in Python, where each step involved generating up to 256 complete (!) immutable successor states indexed by immutable tuples of moves, filtering out the ones that would never be chosen by a player because the move that player made would be a suicide regardless of the moves of other players, then trying to optimize the move selection probabilities of each player in light of the possible immediate outcomes, before sampling one successor for the playout. Then repeat. This approach allowed only three playouts within 100 ms, so I made sure that all were for different moves, and selected at random one of the moves with best playout outcome…

I kind of got tired of using Python, and realized that I could speed up and improve the thing a lot, not only by switching to C, but by considering one player turn at a time, checking whether a move is suicidal before testing it, and doing playouts in-place (with a single copy to begin with). This allowed somewhere near 14000 root-level playouts within 100 ms, and got me to top 160 or so in Silver. (I have discovered a bug in my timetaking calculation since. If the fix were implemented in this plain MCTS version, the number of playouts could easily reach 20000-40000, I think.)

The plain MCTS agent has very interesting behavior. It is the greatest coward of all time. Not only does it flee from its opponents, but it also avoids spaces where it “thinks” it can easily trap itself (based on playouts). To improve on this and be able to compete with minimax approaches, I am currently going for MCTS with UCT selection, which involves building a tree of promising options, and sampling playouts from leaf nodes of that tree. Up to four players are handled by backpropagating evaluation for all players, consisting only of the average end result over all playouts from a node.

The behavior now is much more directed, looks smarter. But it is still some of a coward. It will trap opponents in obvious cases, but often wastes time going back and forth while its opponents are winning ground. I have reached top 75 on Silver league (OK, more like top 85 now), but notice some weird (buggy) moves and occasional timeouts and being denied the amount of memory that I try to reserve. If I fix these errors, I believe I can reach Gold. Then I can put to test my hypothesis that I will do better (relatively) with four players on the board than with three, because my approach naturally handles multiple players equally well, whereas some other approaches rely on simplifications. The dream scenario is jumping straight to Legend League, but I guess that is too much to hope for.

During my experiments, I have implemented my own console-based visualization of the board, and also a procedure that optimizes the UCT’s exploration parameter by offline self-play. :slight_smile:

BTW, this is my favorite on CodinGame so far. The rules are so clean and simple, allowing simulation without an enormous effort. Without simulation, one is stuck in heuristics hell. :-/

4 Likes

Hello
I often get this error

usr/local/lib/nodejs/bin/node[1]:
…/src/node_platform.cc:58:std::unique_ptr node::BackgroundTaskRunner::DelayedTaskScheduler::Start(): Assertion `(0) == (uv_thread_create(t.get(), start_thread, this))’ failed.
1: 0x8dc510 node::Abort() [/usr/local/lib/nodejs/bin/node]
2: 0x8dc5e5 [/usr/local/lib/nodejs/bin/node]
3: 0x965cba node::BackgroundTaskRunner::BackgroundTaskRunner(int) [/usr/local/lib/nodejs/bin/node]
4: 0x965d6b node::NodePlatform::NodePlatform(int, node::tracing::TracingController*) [/usr/local/lib/nodejs/bin/node]
5: 0x8e507b node::Start(int, char**) [/usr/local/lib/nodejs/bin/node]
6: 0x7f412c4e009b __libc_start_main [/lib/x86_64-linux-gnu/libc.so.6]
7: 0x89ed85 [/usr/local/lib/nodejs/bin/node]

How can it be fixed?