I finished 21st.
Here is an overview of my last version:
-
Monte Carlo search over 10 moves + wait for 8 turns. I would simulate ~200k game turns per turns so around 11k “10+8” turn strategies. I think my performance wasn’t very good compared to other top AIs. But I’ve seen so many contests where performance didn’t really matter much, so I didn’t bother.
-
Evaluate game state at every turn and score a simulation as the sum of scores*pow(0.9,turn). This is the “Patience coefficient” which I learned from Xylo’s post mortem of Poker Chip Race. It avoids your AI doing nothing, always hoping for a better score one day.
-
Evaluation of game state was boxes+smaller coefficients for range, bomb carrying capacity (without encouraging more than 5 bombs), Manhattan distance to other players, manhattan distance to all boxes. And a small penalty for placed bombs to discourage placing useless bombs.
-
To avoid numerous deaths by getting trapped by other players I had the following scheme: Simulate for 5ms under the pessimistic assumption that enemies place a bomb if they can. If a solution is found where I am still alive, simulate under this pessimistic assumption for the rest of the 100ms. But if the pessimistic assumption leads only to death, simulate without the pessimistic assumption for the rest of the turn. This allows your AI to avoid traps whilst not killing itself because it thinks the enemies are going to kill it.
Some details:
Place bombs if you think your going to die
Sometimes the “pessimistic assumption” of enemies placing a bomb turned out to be optimistic. It was rare but sometimes my AI would trap and kill itself because under its “pessimistic” assumption, an enemy would have broken a box and I would have escaped my trap through there. The enemy doesn’t place the bomb and I kill myself.
~400 lines of code
Feedback:
I liked the game, it was quite bruteforcy, with the top being dominated by fast languages. But there were still people quite high that didn’t use the 100ms.
However, I feel like submits were much slower than other contests, I feel like submits were 4h long at the best of times and were 8h long at peak hours. From what I remember this was not the case in previous contests. Personally I was basically unable to test any coefficients in my Eval, and I could hardly ever be sure if my new versions were better than the previous ones. To me this was a big issue, developing without testing is a ridiculous idea.