KPUZZLE3





Introduction

Kpuzzle3 is a project written in C++11. This program is an optimal implementation able to solve the 15 puzzle problem.



Heuristics

In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution.

Manhattan Distance

The Manhattan Distance is the distance between two points measured along axes at right angles. The name alludes to the grid layout of the streets of Manhattan, which causes the shortest path a car could take between two points in the city.

\[ h(s)\quad=\quad \sum_{n=1}^{15} (|x_i(s) - \bar{x_i}| + |y_i(s) - \bar{y_i}|) \]

The figure shows the application of the formula for an hypothetical tile 1. The Manhattan approach evaluates the distance of the tile with the right position concerning the two x and y axis. That distance is computed for each tile and, thus, summed to any other.

That heuristic is obviously admissible because is extremely optimistic. Indeed it has been achieved relaxing an important constraint: in the real problem a tile cannot pass over another one.


Pattern Database

Since the previous heuristic is considerably optimistic, another one can be exploited. The pattern database is a clever way in order to achieve a reasonable heuristic starting from the model. This solution is based on the subdivision of the problem itself in different subproblems easier to solve.



Figure 1.
$Cost=X$

Figure 2.
$Cost=X + 0$

Figure 3
$Cost=X + 1$

If we take a subset of tiles, the new entire state space will be much smaller. If the subset is small enough, a Breadth-first search (BFS) algorithm can be performed and calculate the cost for all possible configurations.

For instance, we can take a subset of tiles composed only by the number 1,2,3,4 and the blank tile. This is the case shown in figure 1. Every other tile (which does not belong to the subset) is marked with a star. We can start from a generic state and compute all the possible configurations keeping the associated cost. It's important that the cost can increase only in the case the blank tile is swapped with one present in the partition. Indeed in the figure 2, the cost of the new state remains the same (than the previous). In the figure 3 instead the blank tile has been swapped with the tile 2 (which belongs to the partition) and the cost has been increased of one unit.

If we begin from the goal state storing each relative cost associated, we will be able to make a database of costs for each subset for each partition.

Obviously the heuristic of each partition is admissible because it represents a subsystem of the original problem. As we've already seen the cost is increased only when a move is performed involving a tile which is present in the partition, otherwise the move will have a cost step of zero.

The question at this point is if we can sum every cost for each partition in order to obtain again an acceptable heuristic.

The answer is yes (otherwise I'd have not written all this chapter) but only in a particular case: when all the partition are disjoint among them.



How it works


64 bit configuration

The idea behind the software is the optimal representation of the configuration in the data space. Indeed, the data structure used is the most simple one: a word line in a 64 bit architecture! That means every state configuration is stored in exactly 64 bits.

This simple concept allows to maximize the usage of the processor's cache. For instance an entire vector of states will be stored as a simple vector of 64 bit length blocks each. Moreover the generation of all possible performable actions on a state is very efficient in terms of CPU performance. The CPU can read the entire configuration in a single instruction, copy it on its internal register and perform the computation of the new possible state through a series of bit operations.

In this picture we can see how a configuration is stored. Each tile can contain the number from 1 to 15 and a blank one, so it needed log2(16) = 4 bit in order to store a single tile. Since we have 16 tiles in one single configuration, we need exactly 16*4 = 64 bit.

The movement of the blank tile can be performed through bitmask and bits operators. The snippet below (by the original code) shows how the movement of the blank tile toward right is done.

Database architecture

The first thing to understand is how a partition is stored in the database. This can be achieved through a simple mask which establishes the tiles that have to belong in the partition.

For example a mask is made by a one in the i-th position if we want to keep the i-th tile, otherwise there will be a zero.

The figure shows an example in which the partition has to be composed only by the tiles 15,14,13,12.


The database of the costs is very simple: a vector in which are stored all the cost for each configuration. The first idea was that to use a hash table in order to memorize the configuration as key and the cost of that configuration as data. This approach worked but it required a large memory space. The database file size reached 200MB and it could also be used until 1 GB of RAM.

Afterwards a more efficient technique has been exploited. Each configuration can also be a good index. The problem is that a configuration is made by 64 bit and it can address until 264 block, too much to be allocated! Moreover a lots of configurations share the same cost because of the partition: if the blank tile is swapped with one which does not belong to the partition itself the cost will be the same.


That's why an improvement can be done in order to solve that problem. Once we have a configuration filtered with the mask partition, we can obtain its "key" simply looking at the positions of those numbers which belong to the partition and omitting the rest.

In the figure we can see how that process works. Note that the notation used is the Little-Ended format, that means the MSB (most significant bit) is stored to right. For instance, we can begin with the higher number and look at its the position. In the figure the number 15 is stored in the 13rd position. We can write it and continue. The number 14 can be found in the 11st position, write and so on.

Once the process is completed we've obtained a proper index which can be used in order to access the vector and store the proper cost for that partition. The number of all possible indexes is so reduced, and it depends of the cardinality of the partition itself.



Download

I compiled the code for the most common current platforms. Anyway I'm aware that there could be some problem since I had to exploit some cross-compiling techniques (in particular for the MacOSX target). For this reason I think it is more reasonable and useful to compile the code on your own system following the instructions.

All binary are compiled for a 64 bit architecture. As I've explained above, the source code should be able to compile on a 32 bit architecture, but the performances will be worse.


Platform Version Bin
Linux x64 1.0 (GCC 5.3.0) Download
Windows (7, 8, 8.1, 10) x64 1.0 (Visual Studio 2015) Download
Windows XP x64 1.0 (Visual Studio 2015) Download
MacOSX x64 1.0 (CLANG 3.5.0-10 based on LLVM 3.5.0 - x86_64-apple-darwin12) Download

Note: On Linux or MacOSX system, once extract the archive, it may be need set the file 'kpuzzle3' as executable. That action can be performed through the command: chmod u+x kpuzzle3



Source

GitHub