Tron Battle (aka Line Racing) multiplayer challenge discussion

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?

We’re currently looking into it.
I’ll update this thread when solved: https://www.codingame.com/forum/t/java-random-error-occurred-during-initialization-of-vm/120354/5

1 Like

Follow-up in 2020: I scrapped the playouts in favor of a Voronoi-based heuristic, along with a few move sampling biases. Still no graph abstractions. After finally correcting a timing bug, my bot is in top 50, and I hope it will stay there. I believe a few more tricks will be needed to compete for top 10, though. Note that there is still one Python player above me on the ranking, who probably knows some tricks.

1 Like

Everyone talks about Minmax, and I understand what Minmax is, but I have zero idea how to apply it to this problem…

1 Like

pls, what is logic in the “Tron Top 5%” ? i don’t find this ^^

It was a long time ago, but I think it was this link:
https://vks.ai/2016-09-07-ai-challenge-in-78-lines

Hoooo <3 ty :wink:

Try to win this configuration as orange :smiley:

2 Likes

On Tron all games are mirrored so the goal is to not lose this kind of match up when you are red :stuck_out_tongue:
But it’s true that this might affect the true skill ranking -> if an ok bot is matched with a top bot on this setup, it’s likely that it will be 1 win and 1 loss for each…

Somewhere in the top 20 area, we have a bot, which is participating in games, but the owner it not visible in the Leaderboard. It belongs to an account, which was deleted quite a long time ago. Here is an example replay with the bot playing as red: https://www.codingame.com/replay/520462991. And this is his profile: https://www.codingame.com/profile/24c31f572d8ebfe0837f54535e51d9837432451.

I think it is a bit confusing to have a player in games, who does not participate in the (visible) Leaderboard. Is this intentional or should the bot be removed from CG or should the Leaderboard also display the deleted user?

1 Like

We recently removed from the leaderboard deleted accounts but it looks like we forgot to change the code that picks the players for the new battles. It’s a bug.

2 Likes

@TwoSteps or someone from CG! “Tron Top 5%” link on the game page contains the full copy-pastable solution, which can reach gold at least :frowning:
Is it intentional? I believe it would be better to remove either source code from write-up, or link to this write-up from the game page.

you’re right, I’ve removed the link

1 Like

The Perfect Game
(could have been)

1 Like

Hello there! Despite winning against the boss (multiple times), I am stuck in the first place of the same league (Ligue Bois 1 in french, I guess it is named Wood League in english). Any idea why I’m not promoted?

Thanks for your help!

This might be relevant to your issue: