Spring Challenge 2021 - Feedbacks & strategies

Contests
4

I think I will finish around the 10th legend rank after the final rerun.

My code is a sequential MCTS with the following feature:

Reuse the tree

Between two turn, I try to keep the tree of the previous turn. It only works when my opponent did only one action. If i used WAIT and my opponent did two or more actions, I just start with a new empty tree.

Save and load states

I tried many things to have the best performances. In this game, the best way I found is to save a part of the game state (tree sizes, players suns, players scores …) and when I need to, I have a load function to restore this specific part of the game. I have no bitboard and I never copy my entire Game object.

MCTS exploration

My MCTS is sequential. So in my simulations, my opponens knows my move. The exploration part of my MCTS is classic. I use UCB formula with an exploration constant of 1.0.

MCTS expand (actions computation)

When I compute possible actions for a player, I prune a lot of actions. I do like this:

  • Never try a COMPLETE before the 11th day.
  • Never try a SEED on a cell next to one of my tree.
  • Only SEED when the cost is 0
  • Never WAIT if a SEED is possible (with the previous conditions).
  • All the condition on SEED are disabled after the 21th day to let the MCTS try to win a “tree draw war”.

MCTS rollout

When I expand a node, I rollout to the end of the game. The rollout is pseudo-random. When I compute possible actions for a player during a rollout, I do like this:

  • Never try a COMPLETE before the 11th day.
  • COMPLETE is tried only when the player has at least 4 trees of size 3.
  • If we are at the 22th day or later, we can COMPLETE every tree we want.
  • Only try GROW when there is no possible COMPLETE (with the previous conditions).
  • Never try GROW if we are above the 19th day.
  • If there is no possible COMPLETE and no possible GROW, try a SEED with the same condition as the possible actions computation (not next to one of my tree and only when the seed cost is 0).

MCTS evaluation

I evaluate the game as follow:

float myScore = me.score + me.sun / 3;
float hisScore = him.score + him.sun / 3;

if (myScore > hisScore) {
    float diff = myScore - hisScore;

    if (diff > 5) {
        return 1.0 + (diff - 5) * 0.001;
    } else {
        return 0.5 + 0.5 * diff / 5;
    }
} else if (myScore < hisScore) {
    float diff = hisScore - myScore;

    if (diff > 5) {
        return -1.0 - (diff - 5) * 0.001;
    } else {
        return -0.5 - 0.5 * diff / 5;
    }
} else {
    if (me.numberOfTrees > him.numberOfTrees) {
        return 0.25 + myScore * 0.001;
    } else if (me.numberOfTrees < him.numberOfTrees) {
        return -0.25 + myScore * 0.001;
    } else {
        return myScore * 0.001;
    }
}

What didn’t work

I tried a MCTS DUCT with simultaneous move. The performances was horrible. And the loss of performance was too high and not compensated by the “intelligence gain”.

A smarter rollout : Everytime I tried to add more feature to the rollout selection, I was better in local (tested with brutaltester) but worse in the arena. Overfit nightmare.

Conclusion

The contest was nice. I’m happy to be so high with a MCTS. I hope I’m not the only MCTS in the legend top 10.

45 Likes