Could potentially speed it up by

1. Preferentially exploring branches that are closer to the target. A reasonable distance metric would be min number of steps needed to get from “here” to goal.

2. Explore forwards and backwards.