Hello, here is my postmortem (finished around #30)
The Beam Search
I implemented a beam search exactly as described by eulerscheZahl and with a similar method for filtering moves. My eval consists in :
- my sun - my opponent sun
- a pondered sum of the sun income difference between my bot and the opponent for the following days,
- the score earned,
- a malus for trees under the shadow of my own trees,
- a malus if the income is under a certain threshold, fixed for each day
The opponent is simulated in a very basic way:
- every opponent tree grows every day (except the first simulated day if it is dormant or his sun is too low),
- the opponent has a “free” complete everyday starting from day 12, reducing the amount of nutrients.
Late gold I started to manipulate the overall strategy of my bot by modifying the income threshold in the eval and the estimated nutrients for each simulated day.
I thought it would be possible to adapt this strategy depending on what my opponent plays :
my opponent completed a lot of trees early :
-> nutrients will go down more slowly as his sun income is lower, so a long term strategy involving a high sun income might be more viable
my opponent has an excessive amount of size 3 trees and did not complete much
-> nutrients will go down abruptly near the end so completing fast might be a good idea,
I’m actually not sure if this is a good idea, as I did not experiment with this much.
I went another way:
The DUCT experiment
As legend opened, I tried to implement progressively to a Decoupled UCT. The top 3 on the previous challenge did it with great success, so why not ?
But I slightly underestimated the work required to make it functional. Mixing different algorithm might be strong, but it is time consuming.
After two days of coding, my DUCT version (when activated from day 15) was performing as well as my beam search in the leaderboard, which was slightly frustrating.
So in the end, I reverted back to my beam search and fine-tuned a couple of magic numbers.
Conclusion
Pros: I learned something new
Cons: I won’t have a new T-shirt
Congrats to the winners, thanks to CG, it was fun !