Tron Battle multiplayer challenge discussion


#21

Nice ! :smile:


#22

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.


#23

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


#24

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


#25

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


#26

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


#27

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:


#28

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!


#29

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:


#30

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.


#31

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:


#32

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?


#33

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).


#34

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.


#35

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


#36

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.


#37

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


#38

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.