Are you really sure you are computing during opponent’s turn and not yours, between writing/reading in/outputs ? It seems that BrunoFelthes made it, but I didn’t try yet.
Same here. I’d say I don’t even get 1/10th the number of rollouts when I calculate stuff during the opponent’s turn.
Yes, I’m quite sure that I am computing during my opponents turn.
Same here… I have no clue why it happens… But it still worth…
I think that you’re not really using opponents turn, but the time between your output and the next referee input. Normally, your application should be paused during the opponents turn, not only your main thread. Thus, you should not be able to compute anything during the opponent’s turn. But since there is a little time before the referee pauses your process, you still have time to make some computation.
I tried to make it work with my code, using a second thread that starts when my turn ends. It computes stuff during about 10ms, then stops during about 110ms, and restarts and directly stops since I told him to stop after 100ms. That’s why I also have only about 10% of additional rollouts. If you want to be sure that you are really making computations during the opponents turn, you should print regularly your timer value (for instance each 500 rollouts) and check if you really have computations all the time. I obtained exactly the same results when I made computations in the main thread instead of launching a second one.
Finally, you can only make about 10% more computations using this method (depending of the time needed by the referee to stop the process), and most of the rollouts will be useless since the opponent will play only one of the possible moves that you are simulating. In most cases, you will in average only get a benefit of about a few percents of the total number of rollouts. This may be a lot in some cases, but you also have to consider the memory cost of the growing tree, and the risk of unpredictable timeouts.
1 Like
Does anyone know if something changed on this multi?
My last commit 3 months ago was working fine and right now, the same code is getting a lot of timeout.
I’m wondering if something changed with C++?
Hello, i am starting get sometimes strange error, any ideas? @_CG_Maxime
/proc/self/maps:
00400000-0084f000 r-xp 00000000 00:33 332 /usr/bin/mono-sgen
00a4e000-00a56000 r--p 0044e000 00:33 332 /usr/bin/mono-sgen
00a56000-00a5b000 rw-p 00456000 00:33 332 /usr/bin/mono-sgen
00a5b000-00a72000 rw-p 00000000 00:00 0
02a01000-02b45000 rw-p 00000000 00:00 0 [heap]
40a3c000-40a4c000 rwxp 00000000 00:00 0
41263000-41273000 rwxp 00000000 00:00 0
7f112a9f1000-7f114c000000 rw-p 00000000 00:00 0
7f114c000000-7f114c021000 rw-p 00000000 00:00 0
7f114c021000-7f1150000000 ---p 00000000 00:00 0
7f11536ce000-7f1153942000 r--p 00000000 00:33 367 /usr/lib/mono/gac/System/4.0.0.0__b77a5c561934e089/System.dll
7f1153942000-7f1153943000 r--p 00000000 00:33 357 /usr/lib/mono/aot-cache/amd64/mscorlib.dll.so
7f1153943000-7f1153e25000 r-xp 00001000 00:33 357 /usr/lib/mono/aot-cache/amd64/mscorlib.dll.so
7f1153e25000-7f1153f7d000 r--p 004e3000 00:33 357 /usr/lib/mono/aot-cache/amd64/mscorlib.dll.so
7f1153f7d000-7f1153f7e000 r--p 0063a000 00:33 357 /usr/lib/mono/aot-cache/amd64/mscorlib.dll.so
7f1153f7e000-7f1153f7f000 rw-p 0063b000 00:33 357 /usr/lib/mono/aot-cache/amd64/mscorlib.dll.so
7f1153f7f000-7f1153fa8000 rw-p 00000000 00:00 0
7f1153fa8000-7f11543ff000 r--p 00000000 00:33 348 /usr/lib/mono/4.5/mscorlib.dll
7f11543ff000-7f11553ff000 rw-p 00000000 00:00 0
7f11553ff000-7f1155400000 ---p 00000000 00:00 0
7f1155400000-7f1156000000 rw-p 00000000 00:00 0
7f115606d000-7f115606f000 rw-p 00000000 00:00 0
7f115606f000-7f1156070000 ---p 00000000 00:00 0
7f1156070000-7f1156071000 rw-p 00000000 00:00 0
7f1156071000-7f1156079000 ---p 00000000 00:00 0 ```Not sure what I’m doing wrong. I’m using lookup tables for available moves and checking win states, yet I still can’t consistently get more than 6,000 rollouts. Also using the pragma trick. I’m out of ideas.
Disappointing because my MCTS is so slow that it performs worse than my minimax bot.
Probably because the structures you use to store the game is too big and slow.
My game state is saved as 21 integers. 9 integers representing each of the miniature boards for each player, and then 2 integers representing the larger board for each player. Also one integer tracking player turn. I know it’s probably not ideal, but does that seem too big to get to 25k?
You can use something smaller than an int. Or you can use a single int to store a 3x3 grid for both players.
And you should precompute the list of possibles moves for each grids.
So I made some changes and am now storing my game state with 2 regular ints and 2 128bit ints. I am getting about 16-17k rollouts per turn. However, randomly my rollouts will drop to around 10-11k, and not just for the first turn but even for the next several turns. Yet my win percentage during these games is the same as the games when I am getting 16-17k rollouts. Is it possible that codingame is just running slower during these games (since then my opponent would be getting less rollouts and that would explain the unchanged win percentage)?
1 Like
Hello everyone, I would like to learn more about MCTS so I’ve started writing my bot. Initially I’ve wrote it in python - which ended up with only about 300 rollouts per turn. Then I’ve decided to rewrite it in C#, I have about 1.1k rollouts per turn. I’ve cached all possible TTT states and I’m not computing moves on the small boards - they all were calculated during first turn. By far the slowest part of my implementation are three parts - “IsTerminalState”, “Winner” and “AvailableMoves” for UTTT - I have to calculate them once for each new node. If there’s anyone who would like to chat a bit more about it I would love to hear some feedback, can share code in PM - don’t want to spoil the fun for other people learning. I’m currently top 70 gold with only 1.1k rollouts - the difference is really that major towards the top? That’s quite amazing!
Quite a bit, the top of legend goes more towards 100k+. You will need C++ to reach those speeds though.
1 Like
That’s very informative. Thank you 
If i remember well, i reached legend league with 25k rollouts (measured during turn 2). And my current code can reach 300k rollouts but my MCTS is tuned with some heuristics so it’s not “complete rollouts”.
Iam 25th gold in C#, i have about 6k sim on second turn, but i am stuck hard here. If u want u can PM me.
Anyone from tops using full rollout? Or the way to succes is evaluated function?
First, switch to C++ or any other compiled language. Do not forget optimization #pragma for GCC. You will get more rollouts.
I use full rollouts that try to play smart moves. Use full random first. That will be enough to get Legend
Any tops using neural networks for rollout/expansion policy?