Spring Challenge 2021 - Feedbacks & strategies

Contests
2

Finished 12th

Search

I’m using beam search. It’s a bit off-standard because of the game logic that works in days. So I do a beam search for the current day and make sure all states end with a WAIT action, all while pruning states after each step. Then I prune the final states again and start the next day. Some simplified code:

List<Board> currentBoards = new List<Board> { this };
for (int day = Day; day < 24 && timeRemaining; day++)
{
    HashSet<Board> endOfDay = new HashSet<Board>();
    for (int depth = 1; ; depth++)
    {
        HashSet<Board> next = new HashSet<Board>();
        foreach (Board c in currentBoards)
        {
            foreach (Board n in c.Expand())
            {
                if (n.Day > day) endOfDay.Add(n);
                else next.Add(n);
            }
        }
        if (next.Count == 0) break;
        currentBoards = FilterBoards(next); // only keep those boards with the highest score
    }
    currentBoards = FilterBoards(endOfDay);
}
Board best = currentBoards.First();

My beam width is between 150 and 200. What is I take the best 150 child states at first. But I also try to get at least 50 states that had a GROW action on the current day and keep some more states even with a worse score.

Move generation

To cut down the number of possible states, it can help to not generate all of them.
Regarding suns, it’s always the cheapest to COMPLETE first, then GROW starting from the largest sizes and SEED at the end. So I only generate actions in this order (if a SEED is for free, I can later print it first to claim the cell for myself). Furthermore I disallow seeding from size 1 and have at most 1 seed on the map.

Scoring

That was the hardest part for me. It’s hard to analyze the replays as a human and see what’s working, so I ended up testing against my own bot with brutaltester.

I ended up with:

  • Points + (0.33+0.01*remainingDay) * Suns, taking mine and subtracting the opponent score
  • Simulating the whole game until the end with both players waiting to count the suns at the end of the game. Taking factor * (mySunsPerDay - opponentSunsPerDay) with a factor starting at 0.7 and getting multiplied by 0.98 to further decrease over time.
  • -1 for each pair of my own trees that can possibly give shadow to each other when reaching size 3
  • A bonus for having trees of a certain size. Size 1 is worth 1/11, size 2 4/11 and size 3 is 11/11. These are equal to the costs of growing a tree from size 0 to size 3 without any other trees. I multiply these by (Nutrient - 0.5) * Min(1, remainingDays * 0.09) as the motivation to keep a tree will drop over time. And a multiplier on top, that penalizes having too many trees of the same size.

I made my simulation incorrect by not decreasing the nutrient on each cut tree. Instead I decrease it by 1 on each WAIT action.

Opponent prediction

I consider two opponents. One that is always waiting and another one that grows whatever is theoretically possible (even if the combination of all the grow actions exceeds the available suns).
To predict my suns for the next turn, I then take 2/3 * the suns for a waiting opponent + 1/3 * the suns for a growing opponent.

I tried to use my own search to predict the opponent but the results were on par at best.

67 Likes