Labyrinth: Adversarial search for BFS

Previous:

1. random-labyrinths
2. labyrinth-complexity
3. breadth-first-search
4. monte-carlo-simulations

Now that the of infrastructure for generating, visualizing, analyzing, and searching labyrinths has come into place, we are ready for the big payoff: actually searching for hard labyrinths. It turns out to that one can get very good results with a simple algorithm:

The only thing that is being done here is to remove some random subset of 4 nodes, and then connect the labyrinth again. If the cost is higher, we keep the changes. If the cost is lower, we revert back. If the cost is equal to the best cost, we accept it, in order to get out of plateaus.

For N=100 nodes, the optimal hardness is found in less than 5000 iterations:

Optimally hard labyrinth for BFS. All nodes are expanded, and the solving path is as short as possible.

I cannot say definitely if this is the optimal hardness. However, 180 is not possible for parity reasons. 

For N=900 nodes we still get close to optimum, but struggle in the final points. I guess we have to be a little smarter next time!

Optimum is 1739.

Optimum is about 1739.