[taintegral]

This is a great idea, and the low-level optimization tips are all excellent ones I have used in the past. I want to talk a little bit more about using bidirectional A* though, because I think it's very interesting. It's a great strategy in general, but this may be a case where it doesn't do as well.

Working backwards for this particular puzzle is very difficult because on each turn an actor may or may not move. This effectively increases the branching factor from 4 (one for each direction) to 4 * 2^n (for each of four directions, each actor may or may not have moved). In practice it would be lower than that upper bound, but it could still be significantly higher than the forward branching factor. A nice visualization for this to think of your start and end states as points in space, and your A* searches as cones emitting from one point and growing toward the other. The angle of the cone would be roughly approximate of your branching factor, and when your cones meet each other or a point the search is done. If your branching factor is the same forwards and backwards, you can travel through much less space by searching forwards and backwards simultaneously. However, if your backwards branching factor is higher then the cone from the end state will be much broader. This could travel through much more space than just doing a forward search.

This kind of behavior is very evocative one-way functions, and makes me think it might be related to NP-hardness in some way. I'm really not qualified to prove these kinds of statements though. Maybe someone else can offer a more rigorous mathematical perspective?

[hairtuq]

For the quite similar puzzle Atomix, it also seems like the branching factor would be much higher for backward search because upper bounds are weaker, but you can show that on average the branching factor is actually the same [1]. I wonder if the same argument would work here.

[1] http://hueffner.de/falk/hueffner-studienarbeit-atomix.pdf Section 5.5

[mudita]

I wonder if it would make sense to do backward search, even if the forward and backward branching factors are very different. For example if the branching factor for forward search is 10 vs. 100 for backwards search, wouldn’t it make sense to do one step of backward search for every two steps of forward search? Or more generally log(b)/log(f) backward search steps for every forward search step, where the forward branching factor is f and backward branching factor is b?

This is all based on spontaneous intuitive ideas of mine and very superficial reasoning (and probably not even new).