I’m not sure either. I’m in silver as well. But I’ve found that tending towards the opponent helps.
This game is more challenging than it seemed at first.
1 Like
This game was in my TODO list for a very long time (years).
After I saw the Top 5% strategy I wanted to implement MCTS using it. I started from starch reimplementing the famous strategy.
First for each empty cell I checked which player head is the closest one using Manhattan distance. I’ve simulated all valid moves and chose the move, which gives me the most closest cells, a.k.a. voronoi. Then I’ve implemented BFS coverage from my player head only in my voronoi cells. Then I’ve implemented BFS coverage for all players in turn based manner as in the image:
From this replay for turn 185
All this strategies worked pretty well but I couldn’t beat the Silver bot with them (btw the hardest Silver bot for me so far). Then I’ve decided to implement MCTS using random play out and I was placed in bottom Silver league. After fixing whatever I could I didn’t move from the bottom. I’ve tried replacing the random play outs with my previous coverage strategies and again not improvement. Another round of debugging, but I didn’t achieve any improvement until I took into account the opponents coverage, the lower the better. And finally after 2 weeks of debugging I’ve reached LEGEND.
I’ve tried to further improve my bot by running the BFS and clearing the coverage for trapped players and use the final outcome in the evaluation function but it didn’t work no matter what. So at the end I ran the BFS until all players -1 are trapped:
I’m very happy with my work. Again I’ve struggled a lot with the evaluation function. The initial placement of the players is very important, no matter how good is your bot it could start in a place from which it could not win at all. I think that I have finally understood how exactly the MCTS is working for turn based games. I still cannot imagine how I could fit all this work into a contest time frame, maybe it’s a question of further training and improving myself…
“It doesn’t matter how fast you’re going, it’s important to never give up”
2 Likes
What is your heuristics with your MCTS ?
Hi, I just compute my coverage cells count multiply it by 10 and subtract the combined coverage cells count for all opponents.
1 Like
Hi, You count only your coverage cell in your voronoi region? How do you compute voronoi region? with a naive algo or with fortune algorithm?
For Voronoi I use the “naive” algorithm, iterating all cells and for each I check which is the closest player head.
But for my final version of the bot I use BFS for the coverage, starting from my player head, as shown in my screenshots.