Eight Puzzle solution in scala February 22, 2013
This post is about solving an interesting game as a search problem in Scala and seeing how different heuristics can help find optimal solutions much faster than than regular breath first algorithm. Similar game search problems for example the water pouring problem and the Bloxorz were part of Martin's lectures and homework in the Streams (lazy evaluated lists) part of the course. The problem came from the coursera course in Artificial Intelligence Planning.
The problem is the Eight Puzzle Problem described more precisely here.
The problem theory says there are 2 disjoint sets of states for the game, and that any problem starting from an initial state in either set, can only reach other states in the same set using valid game moves. The problem is not solvable in case you are trying to reach a state in the other set. There are also some rules to check whether a solution is possible between 2 states(you can read more here), but since we want to burn some CPU muscle, we will ignore it for now.
The worst case scenario would be to cover all 9!/2 exactly 181440, possible states starting from any initial position, either to find it in the lowest possible level with a maximum move depth of 31 or to show that a solution cannot be found. This of course without repeating already visited states and going into loops.
I tried the solution using a regular BFS using Streams in the same way it was done for the afore mentioned problems in the Scala course, but after a certain depth it seemed to hang and also used too much memory, I guess it has to do with all the closures that needs to stay in memory until they need to be evaluated. I am still looking into that but I am not sure why there is such a difference, I will update this part when I know more.
Then I tried the same problem using lists instead of streams, also used @tailrec to make sure the compiler would optimize my function to work as a loop. The program run in ~50 seconds to calculate all possible solutions to the problem and the heart of it looks like this:
The method is final and saves the result in the acc List so that the recursive call is the last operation and the method can be optimized with @tailrec.
The third solution involves the A* algorithm to make a better selection of the next node to work on. Simply put A* uses a priority queue where the nodes are ordered using an evaluation function f(n) which is the sum of the distance of the node from the initial state g(n) and a heuristic function h(n) which following some properties guaranties we get the optimal solution to our problem.
The code looks like this:
Again its optimized to do @tailrec same as before. Difference is that I am only looking for the answer to the specific case so i will not create all possible states, but work only according to the highest priority f(n) and so the "best" route to my solution.
First i tried it using h(n) to be the number of misplaced tiles and the solution to the deepest possible state from my initial state (debth 31) took ~4 seconds, thats a great improvement, already given that to find this solution using regular BFS I would actually have to go through all possible states since its at the deepest level, so it's a performance improvement of a magnitude of 10.
Then i tried using a Manhattan block distance as my h(n). This is a better heuristic since it has more information as to how far I am from the solution. This time the solution came in just ~0.5 seconds, about 100 times faster than my initial solution.
Switching heuristic functions is actually trivial, and its easy to create your own and run the solution again to see if you can come up with a better one than the Manhattan block distance.
Bellow is the full code for the problem solution: