Search Problems: A*

2019-01-24 Nick Larsen

Today we continued out trek on search problems. We implemented breadth first search and A* using Hamming distance as the heuristic which we applied to the 8 puzzle problem. We verified the correctness of finding the optimal solution by solving problems with only a few moves to reach the goal. Once that was done, we ramped up to the hardest problem for the 8 problem and saw that even my beefy ass computer with 128 GB of ram was still easily resource exhausted using both of these techniques.

For reference, the harest 8 puzzle problem is (0 is the blank) (source):

8 6 7
2 5 4
3 0 1

Try to solve that in 31 moves by hand!

The last 5 minutes really sums up how incredible of a challenge it is going to be to find the optimal way to solve matrix multiplication using search techniques. This game only has 9! solvable states (362,880 / 2) and somehow we managed to use a technique which explores 10<sup>12</sup> states. That's 7 order of magnitude too many! Finding good heuristics is going to be key if we're going to have any chance of completing our goal of finding a new state of the art way to do dense matrix multiplication.

The todo list for tomorrow is:

  • redfine the goal state to match what's common in the literature
  • add some performance tooling, counters for explored nodes and a regular pulsing of performance info
  • improve the nodes explored per sec by orders of magnitude
  • implement the manhattan distance metric
  • actually find the optimal solution to the hardest 8 puzzle problem!