How do you search for the bomb places? Do you consider all possible places of bombs that will affect at least a surveillant node in the next move? If you do, the number of possible moves will increase crazily fast. Try a bit greedy, and you’ll see the performance is improved.
My brain doesn’t feel the same after solving part 2…
In the first few rounds I wait and analyze node movements until all nodes’ move directions become known for sure. After this, I can simulate node movements for any rounds in the future. I run a DFS on these simulations (with a fixed depth limit that is more than the bomb timer by several rounds), thus searching for the most node kills (counted after a fixed number of simulation rounds, allowing bombs time to explode.)
In the search tree I limit the branching only to the best 3 (a fixed number) possibilities. ‘Best’ meaning how much direct kills that bomb can make (I pre-check this without doing the full simulation). So this is the ‘greedy’ part of the algorithm in place.
The problem with being such greedy is that in IDE TEST 10, my search puts happily a bomb at (4,4) and at (11,7) because of the direct 4 kills. But that means 2 bombs wasted as each neighbouring sections must use up a bomb for a single kill, so in the end 2 nodes remain. For similar reason, I also fail TEST 08 (1 node remaining alive).
If I raise the horizon by considering more than the 3 best bomb placements, or by going more rounds in the simulations, then timeout kicks in.
Wow… Your method is very similar to me.
In the last test, you should try to divide the map into smaller regions, and focus on solving the subproblems one by one, to be able to increase the number of rounds. There are probably many ways to do this, but I stick with a simple flood fill algorithm because it’s relatable to me. By doing this, I could predict ahead 8 moves.
I didn’t consider any 3 best bomb placements like you did, instead I try to find the best bomb, then search for the surrounding if there are any bomb that could affect this result. Removing duplicates or inefficient ones (bombs destroying the same 2 nodes, destroying 2 nodes but there’s a better bomb that destroy 3 nodes including the last 2,…) (trust me there are a lot) and you’ll find improvement 
Good luck.
2 Likes
Really cool game !!
It’s amazing to see how this game is easy to solve for any human, but finally so hard to solve with a coded AI. At first, I thought this puzzle would be solved in an evening… I took me 5 half days 
Thanks for this really interesting challenge 
PS : I used recursivity, simulation, brute force, and several conditions to avoid all the traps 
2 Likes
And 10 days later, the episode 2 is now solved !! I’m proud 
It was really hard, but very interesting and so fun !! Thanks for this great challenge 
I am in a hurry to see the solutions of the other players.
3 Likes
Finally managed to solve 100% (in C) using backtracking approach without any hacks for specific tests. In case anyone is interested, here’s how my algorithm works:
-
It waits first 3 moves and determines all nodes’ directions (where they are moving). I figured that first three positions unambiguously define all node movements, assuming no nodes are overlapping on the first move.
-
After it determined nodes’ directions, it starts backtracking search and outputs the sequence of moves. During next moves it doesn’t think and just outputs next move in the sequence it calculated on the 3rd move.
-
Backtracking works like this (in short): generate all possible moves (including WAIT) for the current state, try the first move, save it in the sequence, update state, repeat. If wrong state occurs (for example, there are still nodes, but no bombs left, or reaches maximum rounds), it goes back, restores previous state and tries next move.
-
The most tricky part to implement is the move order during move generation, because it has the biggest influence on the performance. If it just generates all possible moves and tries them in random order, the algorithm will timeout even on the 1st test. So, it should try “better” moves first, best case scenario: all the correct moves are first, and no backtracking occurs.
-
So, during move generation, it copies the current state, updates it three times and uses it to see which nodes will explode. For each empty cell (where no nodes, no walls, no bombs), it tries to explode the bomb there and counts how many nodes are exploded in the future. It also counts how many moving nodes are exploded. If no nodes are exploded, then this bomb placement is discarded.
-
Then it sorts bomb placements in the following order: first those which explode the most moving nodes, and if this amount is the same, it puts first those which explode the most nodes (including non-moving ones). The WAIT action is tried the last.
-
It iterates from the first action to the last (excluding WAIT) and marks the nodes which are exploded by the action. Then, when it gets to those actions which explode only one node, it discards them if previous “better” actions already explode this node (these actions are redundant).
-
The simulation was relatively easy to implement but is still tricky. The interesting part is when one bomb’s explosion causes another bomb to explode immediately. First I thought that it is very hard to implement since there can be “bomb chains” (i.e. the bomb explodes, causes another to explode, it explodes the third and so on). But, since the bomb timer is 3 moves maximum, the biggest chain would include only 3 bombs. It allows me to implement this part in very simple way: when the bomb is placed, its timer is set to 3 moves. Then all bombs in the explosion range (including the newly placed one) set their timer to the minimum timer value amongst them. So, when one bomb explodes and causes this newly placed one to explode, it should explode all bombs in its range and thus they all should explode at the same time, hence they have their timer value set to the minimum value amongst them. And during the simulation when one bomb explodes, I only need to check which nodes it explode and I don’t need to check which bombs it causes to explode.
Initially, I only sorted bomb placements only by the amount of nodes exploded (including non-moving nodes) and the last “Vandalism” test timed out. Interestingly, some test was randomly passed and timed out later without changing any code. I guess my algorithm there was on the border of 100 ms. I tried limiting the number of generated moves for each position to 5 best ones (plus WAIT action) - all tests were consistently passed, but the last still timed out.
Found here on the forum the idea that for the last test, the map should be divided into smaller regions (using flood fill) and each solved separately. Way too complicated I thought and the solution didn’t seem universal (what if the last test had random “holes” in the walls of smaller regions?). Another idea was to somehow calculate the minimum number of bombs required to explode remaining nodes, and if the number of bombs left is smaller than calculated number - then to backtrack (so it backtracks way earlier, otherwise in hopeless positions it waits, explodes remaining bombs in every possible order, backtracks, waits a turn more, explodes again in every possible order, waits two turns more and so on - so many pointless cycles). But I haven’t managed to come up with the algorithm to calculate this number.
Then I came up with the idea to sort bomb placements by amount of exploded moving nodes. In the last test the first moves was to explode those four non-moving nodes (maximum number of exploded nodes), but this is wrong. And when it prioritized exploding moving nodes, the last test was finally passed. I don’t consider this move prioritization a hack for the last test to pass, since targeting moving nodes should be a good strategy in all cases - it is easier to explode non-moving nodes in conjunction with some moving node and one should not waste the bomb only on non-moving nodes while there are still moving nodes.