Royale, 4th
My basic strategy was: do not die and try to maximize my score.
##Getting to Wood 1
At each turn, I tried to put a bomb on each cell and simulate the explosion to see how many crates were destroyed.
Then, I BOMB to these coordinates (until the crates exploded). The automatic pathfinding by CodinGame was doing the work for me.
##Getting to Silver
I skipped the rule where only opponents’ bombs hurt and considered all the bombs could kill me (bronze rule).
In order to destroy crates and avoid the bombs, I used a DFS algorihtm that would:
- update the bombs timers
- simulate the bombs explosions and chain explosions
- for leaf nodes make all the bombs explode whatever the timer was
- for each crate that is destroyed by my bombs increment my score
- if I am hit by a bomb return with -INFINITE score
- recursively consider all my valid actions (MOVE 5 directions + BOMB 5 directions) and keep the best one
Note that I ignore the opponents possible actions.
At first, my DFS was looking at a fixed depth of 6.
As I added more features (pick up bonuses, leaf nodes heuristic) I switched to an iterative deepening DFS that tried to go as deep as possible without the risk of timeout.
##Local simulator
From my experience during previous contests, the arena is crowed near the end of the competition so it can be long to have a new evaluation of your AI and consider if it is better than the previous one or not.
So I started my own local simulator (most of the rules were already implemented in the DFS) in order to quickly run many simulations on my computer.
I tried to mimic the maps provided by CodinGame (same walls, same number of crates/bonuses).
By comparing the game results for the same map between my local simulator and CodinGame, I found many bugs in my simulations (bombs did not explode/block/chain or bonuses did not appear/disappear as expected).
I also used a smaller timeout value to run the simulations faster and emphasize the importance of the heuristic.
##Getting to Legend
After trying Monte-Carlo without much success, I kept the DFS algorithm until the end of the contest, tuning it for performance (changing my data structures several times).
My score evaluation was basically:
- bonuses I pick up depending on my current range and number of bombs.
- number of crates I destroyed
- big malus if I die
- for leaf nodes: Manhattan distance to remaining crates, number of escapes I have
##“Fake” bombs
At this point, looking at the replay I was sometimes dying stupidly because of a bomb placed by an opponent that would trap me in a dead end or link a chain of bombs that I did not consider.
On the other hand I did not want to simulate the opponent moves because I thought this would cost too much time.
So I just considered each opponent that had a bomb left could put it on his current position during the first turn of the simulation.
Then during the DFS, if such a “fake” bomb exploded and killed me, it would lower my score (but not as much as a real death).
Also, my character was allowed to move through the “fake” bombs with another score malus.
This allowed my AI to avoid dangerous situations, but still escape if the opponent did not really attack me.
Finally, I would like to thank CodinGame and the staff for this contest, as usual it was really fun!