Ultimate Tic Tac Toe [Puzzle discussion]


#41

By vanilla algorithm, are you refering to a basic MCTS, with complete random node selection and simulations ?
In my case, I had a hard time beating the boss with at least 30k rollouts at second turn. I used UCT to select nodes.
Anyway I agree with the need to optimize everything.

There are still two things that I don't know if I can optimize :
1) Does anyone know exactly how/when is the time measured ? Is it possible to compute things before the main loop / between each turn ?
2) Did someone achieve to use multithreading and improve the number of rollouts ? I tried and failed, since the time launching/waiting for threads is too high compared to the 100ms that we have. Did I miss something ?


#42

By vanilla I mean exactly what you mentioned. There must be some difference between us. Maybe you did something to the random number generator? Or did not set the seed? It must be something different. Or maybe the exploration coefficient? Or how do you calculate the mean value of a node. Or if you consider draws correctly. Something.


#43

About optimization:
1. Do you mean like pondering? You can have a look at the referee code but I think pondering is excluded.
2. I think other people mentioned that it is useless because we are allocated only 1 core,


#44

Yes I modified the random number generator, but it shouldn't make a huge difference. I think I have done something wrong but I don't know what. I still have many things to fix before improving the algorithm (but it works great currently and I don't know why :D).

And for optimization :
1) Yes I meant like pondering. I think it is excluded too, where could I find the referee code ?
2) Regarding cores, in the FAQ it is stated that the code runs in a multi-core environment. But this doesn't mean that we can use several cores...


#45

1.calculating the table where next player has to move, once you know the last move. There are 9 TTT tables and 9 possible moves (if you always consider the move relative to the table). So if last move was move no.7 (in what table was that it's not important) than the next move has to be made in table no. 7.

hm, didn't get what is done here... why do you need to calculate table of next player if you receive it as a part of his move after his turn?


#46

@dbf This only makes sense if you perform some type of simulation of the game. In this case you play both sides until end of the game. So after each move you have to calculate the possible moves for the other player and so on. The default implementation using (row,col) is not very fast because you have to perform some calculations to reach the table where next player is forced to move. On the other hand if instead of (row,col) pair you switch to (table,move) than finding the next table is straight forward: last move number becomes next move table and so on.

@Vingte Until gold I did not use the seed function (srand in C). After introducing this function on every turn I remember jumping about 50 places!!! Also in the legend I tried to save about 4 mil random numbers in an array on the first turn, to avoid calling the rand function during all other turns. The result was that I dropped to last places. What I figure is that I need around 3 mil random numbers per turn. Reusing those numbers will produce worst results than using 3 mil different numbers every turn. It's linked to the convergence speed of the MCTS.
Link to referee code is in the puzzle rules (just above Victory Conditions section)


#47

Hi @perseverent, when you say "calculating the table where next player has to move, once you know the last move", I don't understand what you meant. What is the advantage compared to computing the list when you need it?
BTW: thanks a lot for the figures it help to have a target.... I'm only at 3k playout and already using bitboard ...


#48

In general, multithreading will not help with speed here at codingame, because your linux user can only use a single processor, so, if you start 2 threads, both will use the same processor...
BUT, you can use multithreading to run more simulations during the opponent turn...


#49

Are you sure about this ? Has someone already implemented something like that ?

Instead of computing the list when you need it, you can precompute everything and store it in during the first turn. Then, knowing in which table you have to play (during simulations), you can just look in your array and get the precomputed move list. But I'm not sure it is exactly what perseverent meant.


#50

Thanks for the explanations. Issue is that list of possible moves depends on the moves already performed. Or your play function just return if cell is already full?


#51

Since each table can be associated to an integer (there are "only" at most 3^9 different tables), it is possible to create during the first turn an array that contains all the possible TTT representations, and then precompute all the needed information.
During simulations, there are two cases. In the easy one, you have to play in a table that is not completed. Since you know the moves already performed, you can check in your array the table which contains the information corresponding to your current state. This enables you to replace the "heavy" move list computation by an array access, which is faster.
In the other case (next player can play where he wants), you have at least to look at every playable tables to find the complete legal move list (there may be a smater way but I didn't find one).

The main problem is to create an efficient representation of the tables, that provides as much information as needed, and is not heavy in memory. Another problem is that rules for the 9 small tables do not apply for the "big table" (different win conditions, possible draws in cells).

In my implementation, there are almost no heuristics, there are only tricks to make simulations faster. I assume this is the case for most of the top players, since it is very hard to find good heuristics in this game. Is anyone using minmax instead of monte carlo simulations ?


#52

Multithreading is useless on codingame. Since we have only 1 core and our process is entirely paused when we are waiting for inputs.

But AVX is available.


#53

@jft63 You still compute the list of moves when you need them but the calculations become easier/faster!
The standard input / output is using a 9x9 array to represent the board. If last move was (6,6) how do we calculate the possible moves?

Option 1. Use some sort of lookup table for all possible moves if the table is empty and filter this table based on current board state. (@Vingte and others use it, it might be the fastest way of solving the move generation problem)

Option 2. Calculate the coordinate of the upper left point of the table where we are forced to move.
Row = 6 mod 3, Col = 6 mod 3. With this (Row,Col) use 2 for loops to check all 9 squares if empty or not.

Option 3. If we consider each 3x3 small board and we count the moves like this:
1 2 3
4 5 6
7 8 9
and we do the same for the big board where numbers represent small boards this time, than you can see that if last move was move 1 in any of the small boards this means that next move has to be made in board 1. Of course you still have to check what moves are available in board 1.

Please consider some sort of lookup table for everything: move generation, check for win, selection, random numbers, etc.


#54

Thanks a lot for advices, will try to improve, because I need to multiply my playout number by around 10 ... to go to legend.


#55

I implemented it at my TTT algo... Just try, it is easy to test...


#56

How to use AVX @Magus?


#57

SSE AVX vectorization


#58

By 25k rollouts, do you mean complete game from current state to the end (win/loose/draw) or do you cut at some point with a defined depth?


#59

The point of MC is to avoid evaluation functions (which are difficult to find for this game), so you cannot cut before the end. So the answer is : yes 25k complete games at your second turn.


#60

Has anyone been able to get pondering to work well? I'm seeing about a 1/6th drop in the number of rollouts I'm able to perform during the opponent's turn vs my turn even though I should have the same time allowance. Any clue what's going on?