Many thanks for the PM, Jolindien. Another question if that’s ok: If I understand correctly, the MCTS gives you a matrix of all possible move combinations, but that’s not an action. So how does one decide from this matrix which action to take?
the matrix is only for memorize which is the corresponding child (that’s why I talk about pointer -> child_node)
for exemple, you have 2 actions and the opponent 2 actions:
you need two arrays to memorize the scores :
e.g my_sum_scores = [17.58 12.2] and opp_sum_scores = [7.1 -3.57]
and two arrays for the number of visits my_nb_vists and opp_nb_vists
then you choose your action in function of my_sum_scores and my_nb_visits for you, etc.
if you choose the first action for you and the second for the opponent, the child pointer will be at childs[0][1]
This was the third contest for me. Well, second I actually had some time for… or actually: I realized this contest that 10 days just doesn’t work for me.
So I started with Legend of Code and Magic, which was 4 weeks. Because of work and a toddler at home, I could only start this LoCM after a week. Then I needed 1 week to understand the game, 1 week to develop a bot and 1 week to improve my bot. 4 weeks of work gave me 30th place in legend.
So I started XMas rush on the first day, but that was just enough to read the rules and see some games being played. Then I could not work on the bot for 3-4 days. So when I started again, I wanted to write a monte-carlo depth-limited search tree with simultaneous moves (like the Smitsimax). I spend 5 days trying to write it. I had difficulty finding a proper data structure. I worked on this for the whole Friday and the large part of the Saturday. My wife even went off to some friend with our kid give me the space and time.
After all this, 40 hours before deadline, I finally understood the game and realized my code would not work… I had to largely rewrite it in less then two days.
That’s just too short. I already felt so much stress. I gave up… I ended up never submitting my 1000-lines of (broken) code bot and finished 1212 of 1229 : 17th from the bottom.
PLEASE make competitions 4 weeks again. 10 days is just much too short for me!!!
2 Likes
Congrats for the 1st place jolindien. 1 question: during the simulation phase did you always simulate until the end of game (I’d be surprised) or did you set a depth limit?
Thanks Csipcsirip
I didn’t simulate until the end of the game.
During simulation phase (rollout) I just play one more move or not at all:
<<According to the last action played during the selection-expansion:
-for a PUSH, evaluate the current position (no additional action)
-for a MOVE, play one additional push for each player according to the following heuristics: try 5 pushes at random, keep the most promising >>
(promising = a good score with the Evaluation function for a player)
For many people, what I did was not an MCTS.
It is an UCT (Upper Confidence applies to Tree).
For me, there is enough randomness (during expansion, for additional action after a move, for new quests) to talk about MCTS (Monte Carlo TS)
A MCTS using UCB is called UCT (if i remember well).
But since you are using random to predict the future (for the next quests), it is called ISMCTS. This is what i tried (unsuccessful) in LOCAM. You just do a MCTS algorithm and you randomize what you don’t know.
Anyway, thanks you for the PM.
… and one week to rule them all !!!
I would suggest Halite III
or RAIC
http://russianaicup.ru/
Both of them will last longer than 4 weeks from now. CG has traditionally 10 day contests, which is what the community is used to the most. Personally i prefer the 10 days variant, although slightly different variant might be better suited even for this community, who knows?
Thank you for the suggestions. I know them and am already playing Halite. But these are just too long!
So for me this CG competition is like running the 500m race. Halite is more of a 42km marathon.
I would just like to run the 2km race…
Play multis, code at your own pace. There are many fun ones.
And try to ask in chat, picking the wrong strategy / data structure ends up in frustration and lot of useless code. I’m always open to discuss ideas on chat, challenges or not.
Is there a specific achievement for @RockyMullet and myself for being above beber after ~30min game 
?
More seriously, great contest once again! Congratulations to the team who developed it and to the top players of course, for making the competition really worth watching and for the PMs.
I really struggled to simulate the push efficiently, because of the module copy.deepcopy in python which is very slow, and therefore hardly reached the 28 simulations per turn (1 push, 3BFS). I was advised on the chat to try to clone the objects instead of deepcopying them, which I will try next time with more success hopefully. 
3 Likes
Why was copy.deepcopy necessary for the simulation?
You can do a full simulation without it. Just use a few for loops. Only needed one for each quest list iteration actually.
And then you can actually implement your own light-weight version which only copies the bits you need for the specific task, instead of the entire list of objects. Why did some folks use it and then complain it’s slow? I simply fail to see the benefits.
So while ignoring my horrible evaluation that clearly didn’t work, i could iterate through all push possibilities for myself and the opponent each turn.
On the move turn i could do BFS x 3 for a total of 3 quest items + another BFS for guessing the 4th item or moving towards the edge!
I used it to save my game state first, and then come back to it after simulating the push and the BFS. Yes, implementing reverse push or using bits would have been faster…but I don’t complain that deepcopy is slow, as if it did not exist, my final rank would be even worse . I blame myself for not finding a better data structure and for failing to implement some simple simulations efficiently, as the game was perfect for this!
I finished my BFS article that has some tricks for optimization. You can find it here:
There is a lot of stealable code near the top of the article, including the various BFS versions and a simple maze generator.
7 Likes
Nice article, very detailled 
If I may add another tip I use myself, regarding the visited data :
You can use an array of int, and a counter on the side :
array<int, N> visited;
for (int i = 0, i < N; ++i) visited[i] = -1;
int visitedFlag = -1;
[...]
bfs() {
visitedFlag++;
[...]
for (Cell &neighbor: current.neighbors) {
if (visited[neighbor.id] != visitedFlag) {
// add in the queue
}
}
}
You then don’t have to reset the visited array/hash/map/wathever for each BFS
6 Likes
Thanks, that is a good tip.
During tree search I ignored rule about 20 moves and used whole connectivity components (for example to process all connected items) and here is my code for connectivity component:
uint64_t spread_area(uint64_t can[4], uint64_t start_area)
{
uint64_t prev = 0;
uint64_t ret = start_area;
while (ret != prev) {
prev = ret;
ret |= (ret & can[LEFT]) >> 1;
ret |= (ret & can[UP]) >> 7;
ret |= (ret & can[RIGHT]) << 1;
ret |= (ret & can[DOWN]) << 7;
}
return ret;
}
Coordinates are numbers from 0 to 48, if you interested in particular coordinate c, you can pass 1ULL<<c to this function as start_area. In each position I store array uint64_t can[4] : for example 49 bits of can[UP] mean can I or can’t go up for each coordinate where LEFT, UP, RIGHT, DOWN are global constants 0, 1, 2, 3. If you need area of connectivity component you should use 1 bitcount instruction (or 2 since I couldn’t find 64-bit one for gcc). You may think that can[] is hard array to calculate, but I store field in the same way and for example
can[DOWN] = (field[UP]>>7) & field[DOWN];
I guess this was fast.
6 Likes
You can use __builtin_popcountll() for 64-bit
2 Likes
I tried with suffix ull but this didn’t compile. I was afraid that sign conversion would slow the program.
Try on godbolt.org to see whether the signed version creates any more instructions.
I’m pretty sure on most machines with 2’s complement representation there will be zero extra instructions.
1 Like
The gcc popcount builtins only take unsigned values (even though they don’t say ull).
2 Likes