4
\$\begingroup\$

It takes my code over 700 seconds to solve simple puzzle:

2  7 11  5
13  0  9  4
14  1  8  6
10  3 12 15

My function findSolution(puzzle, minH) takes puzzle as an array and minimal h parameter which has to be found.

I'm using A* with Manhattan Distance heuristic function. G is step number and h is Manhattan Distance.

I'm searching for a node with the smallest value of f in queue, where f = g + h, and expanding it (moving tiles to empty space to get another four or less nodes). If any of expanded nodes are already in queue or visited array and its g is smaller than current node, I replace it, or else I put it in queue and I move the current node to visited array.

Every state od puzzle is two 32-bit numbers called as currentHi and currentLo and it has two numbers showing which state was previous: previousHi and previousLo, and also g and h parameters.

These numbers are calculated by hashing function.

Previously I kept states in arrays, but changing to numbers gave me more memory and speed.

I can solve puzzle from example above with minH = 4 in 0.1 s, but I see if I want to get next state with lower h, I have to expand many wrong nodes, because they have lower g + h. That's why it takes so much time.

When I'm improving simple things in my code, it doesn't seem to work faster or I get a few milliseconds extra, but it's not enought. I think the problem is with the algorithm which I'm using:

Create a node containing the goal state node_goal
Create a node containing the start state node_start
Put node_start on the open list
while the OPEN list is not empty
{
    Get the node off the open list with the lowest f and call it node_current
    if node_current is the same state as node_goal we have found the solution; break from the while loop
        Generate each state node_successor that can come after node_current
        for each node_successor of node_current
        {
            Set the cost of node_successor to be the cost of node_current plus the cost to get to node_successor from node_current
            find node_successor on the OPEN list
            if node_successor is on the OPEN list but the existing one is as good or better then discard this successor and continue
            if node_successor is on the CLOSED list but the existing one is as good or better then discard this successor and continue
            Remove occurrences of node_successor from OPEN and CLOSED
            Set the parent of node_successor to node_current
            Set h to be the estimated distance to node_goal (Using the heuristic function)
            Add node_successor to the OPEN list
        }
        Add node_current to the CLOSED list
    }

Open list is queue and closed list is visited in my code.

function findSolution(puzzle, minH)
{
    var positionX = [3];  
    var positionY = [3]; 
    for (var i = 1; i < 16; i++)
    {
        positionX[i] = (i - 1) % 4;
        positionY[i] = parseInt((i - 1) / 4);
    }   
    var queue = [];
    var queueContent = [];
    addToQueue(
    {
        currentHi: hashHi(puzzle),
        currentLo: hashLo(puzzle),
        previousHi: 0,
        previousLo: 0,
        g: 0,
        h: calculateH(hashHi(puzzle), hashLo(puzzle))
    });
    var visited = [];
    var visitedContent = [];
    var solution = [];
    var moves = [{x: -1, y: 0}, {x: 1, y: 0}, {x: 0, y: -1}, {x: 0, y: 1}];
    var startTime = new Date().getTime();
    do
    {
        var minF = 0;
        for (var i = 1; i < queue.length; i++)
            if (queue[i].g + queue[i].h < queue[minF].g + queue[minF].h)
                minF = i;
        for (var m = 0; m < moves.length; m++)
        {
            var next = move(queue[minF], moves[m].x, moves[m].y);
            if (next)
            {
                if (queueContains(next))
                {
                    for (var j = 0; j < queue.length; j++)
                        if (queue[j].g > next.g && queue[j].currentHi === next.currentHi && queue[j].currentLo === next.currentLo)
                        {
                            queue[j].previousHi = next.previousHi;//clone(next);
                            queue[j].previousLo = next.previousLo;
                            queue[j].g = next.g;
                            break;
                        }
                }
                else if (visitedContains(next))
                {
                    for (var j = 0; j < visited.length; j++)
                        if (visited[j].g > next.g && visited[j].currentHi === next.currentHi && visited[j].currentLo === next.currentLo)
                        {
                            visited[j].previousHi = next.previousHi;
                            visited[j].previousLo = next.previousLo;
                            visited[j].g = next.g;
                            break;
                        }
                }
                else
                    addToQueue(next);
            }
        }
        addToVisited(removeFromQueue(minF));
    }
    while (visited[visited.length - 1].h > minH)
    solution.push(visited[visited.length - 1]);
    while (solution[solution.length - 1].g > 0)
    {
        for (var i = 0; i < visited.length; i++)
            if (visited[i].currentHi === solution[solution.length - 1].previousHi && 
                visited[i].currentLo === solution[solution.length - 1].previousLo)
            {
                solution.push(visited[i]);
                break;
            }
    }
    document.getElementById("result").innerHTML = "<b>Time: " + (new Date().getTime() - startTime) / 1000 + " s</b><br><br>";

    function hashHi(puzzle)
    {
        var hash = 0;
        var i = 0;
        for (var y = 0; y < 2; y++)
            for (var x = 0; x < 4; x++)
            {
                hash |= puzzle[x][y] << (4 * i);
                i++;
            }
        return hash;
    }

    function hashLo(puzzle)
    {
        var hash = 0;
        var i = 0;
        for (var y = 2; y < 4; y++)
            for (var x = 0; x < 4; x++)
            {
                hash |= puzzle[x][y] << (4 * i);
                i++;
            }
        return hash;
    }

    function calculateH(hashHi, hashLo)
    {
        var val, exp = 0, h = 0;
        for (var y = 0; y < 2; y++)
            for (var x = 0; x < 4; x++)
            {
                exp++;
                val = hashHi & 15;
                if (val != exp)
                    h += Math.abs(x - positionX[val]) + Math.abs(y - positionY[val]);
                hashHi = hashHi >>> 4;
            } 
        for (var y = 2; y < 4; y++)
            for (var x = 0; x < 4; x++)
            {
                exp++;
                if (exp === 16)
                    exp = 0;
                val = hashLo & 15;
                if (val != exp)
                    h += Math.abs(x - positionX[val]) + Math.abs(y - positionY[val]);
                hashLo = hashLo >>> 4;
            }
        return h;
    }   

    function addToQueue(state)
    {
        var x = Math.abs(state.currentHi ^ state.currentLo);
        if (!queueContent[x])
            queueContent[x] = [state.currentLo];
        else
            queueContent[x].push(state.currentLo);
        queue.push(state);
    }

    function removeFromQueue(index)
    {
        var x = Math.abs(queue[index].currentHi ^ queue[index].currentLo);
        for (var i = 0; i < queueContent[x].length; i++)
            if (queueContent[x][i] === queue[index].currentLo)
            {
                queueContent[x].splice(i, 1);
                return queue.splice(index, 1)[0];
            }
        return null;
    }

    function queueContains(state)
    {
        var x = Math.abs(state.currentHi ^ state.currentLo);
        if (queueContent[x])
            for (var i = 0; i < queueContent[x].length; i++)
                if (queueContent[x][i] === state.currentLo)             
                    return true;
        return false;
    }

    function addToVisited(state)
    {
        var x = Math.abs(state.currentHi ^ state.currentLo);
        if (!visitedContent[x])
            visitedContent[x] = [state.currentLo];
        else
            visitedContent[x].push(state.currentLo);
        visited.push(state);
    }

    function visitedContains(state)
    {
        var x = Math.abs(state.currentHi ^ state.currentLo);
        if (visitedContent[x])
            for (var i = 0; i < visitedContent[x].length; i++)
                if (visitedContent[x][i] === state.currentLo)
                    return true;
        return false;
    }   

    function findGap(state)
    {
        var currentHi = state.currentHi;
        var currentLo = state.currentLo;
        for (var y = 0; y < 2; y++)
            for (var x = 0; x < 4; x++)
            {
                if ((currentHi & 15) === 0)
                    return [x, y];
                currentHi = currentHi >> 4;
            }
        for (var y = 2; y < 4; y++)
            for (var x = 0; x < 4; x++)
            {
                if ((currentLo & 15) === 0)
                    return [x, y];
                currentLo = currentLo >> 4;
            }
    }

    function getValue(state, x, y)
    {
        var shift;
        if (y < 2)
        {
            shift = 4 * (4 * y + x);
            return ((state.currentHi >> shift) & 15);
        }
        else
        {
            shift = 4 * (4 * (y - 2) + x);
            return ((state.currentLo >> shift) & 15);
        }
    }

    function setValue(state, x, y, value)
    {
        var shift;
        if (y < 2)
        {
            shift = 4 * (4 * (y - 2) + x);
            state.currentHi = ~state.currentHi;
            state.currentHi |= (15 << shift);
            state.currentHi = ~state.currentHi;
            state.currentHi |= (value << shift);
        }
        else
        {
            shift = 4 * (4 * (y - 2) + x);
            state.currentLo = ~state.currentLo;
            state.currentLo |= (15 << shift);
            state.currentLo = ~state.currentLo;
            state.currentLo |= (value << shift);
        }
    }

    function move(state, dX, dY)
    {
        var gap = findGap(state);
        var x = gap[0];
        var y = gap[1];
        var newX = gap[0] + dX;
        var newY = gap[1] + dY;
        if (newX >= 0 && newX < 4 && newY >= 0 && newY < 4)
        {
            var nextState = 
            {
                currentHi: state.currentHi,
                currentLo: state.currentLo,
                previousHi: state.currentHi,
                previousLo: state.currentLo,
                g: state.g + 1,
                h: 0
            };
            setValue(nextState, x, y, getValue(state, newX, newY));
            setValue(nextState, newX, newY, 0);
            nextState.h = calculateH(nextState.currentHi, nextState.currentLo);
            return nextState;
        }
        return null;
    }

    return solution;
}

This is how it works.

\$\endgroup\$
  • \$\begingroup\$ You discussed your solution too much, that you forgot to tell us what puzzle this is. What is this code doing? Also, what is G? I thought you only said the function only takes a puzzle and an h? \$\endgroup\$ – Joseph Oct 24 '15 at 9:47
  • 1
    \$\begingroup\$ @JosephtheDreamer I was expecting people who made 15 puzzles solver before to answer my question, because I didn't think someone else will be interested in reading my long code. G is a sum of nodes which was expanded to get to the current node and h is a heuristic estimate of cost to get from current node to final node. I'm using A* algorithm with Manhattan Distance heuristic function. \$\endgroup\$ – alcohol is evil Oct 24 '15 at 12:10
  • \$\begingroup\$ I'm reading that A* algorithm is not enought to solve 15 puzzles, so I will try IDA* algorithm. \$\endgroup\$ – alcohol is evil Oct 24 '15 at 16:08
  • \$\begingroup\$ You might want to add that overview in the post itself for clarity, preferably a 2-3 sentence summary on top. Not all code reviewers are puzzle solvers (though code is already a puzzle itself ;) ). \$\endgroup\$ – Joseph Oct 24 '15 at 17:50
  • 1
    \$\begingroup\$ Oh snap, I just realized that it's one of those kids puzzles. Except it's not pictures, but numbers. >.< Didn't realize it had a name. :D \$\endgroup\$ – Joseph Oct 24 '15 at 17:54
8
\$\begingroup\$

Non-optimal solutions

If you just need to compute a relatively fast solution quickly but it doesn't have to be the guaranteed fastest solution, then you can just greedily look for the fastest way to get the fringe row and column (the row and column furthest from the non-tile goal) right, and then solve the remaining 8 puzzle. Related paper. Plain A* or IDA* should be enough for each subtask.

There seem to be no algorithms that make use of known upper bounds.

Basic algorithm choice

From what I have read, a more space efficient algorithm such as IDA* is needed to make sure you can't get unlucky and run out of memory. It makes the algorithm significantly slower, though. A better heuristic function is needed to make the algorithm faster.

Improved Manhattan distance

A relatively simple tweak is to take the Manhattan distance heuristic function + the linear conflict correction. For the latter you look at every line of the puzzle. If you find two tiles there which are supposed to end up in this line, but which are currently in the wrong order, then you know that the Manhattan distance is too optimistic and you actually need at least 2 more moves to get the two tiles past each other. One can prove that the heuristic function remains admissible (in fact monotone) even if you add 2 for every pair with this problem in any row and also for every pair with the analogous problem in any column.

This paper describes an additional corner-tiles heuristic, but unfortunately it cannot tell us whether the additional moves required are horizontal or vertical. Therefore, for some of the arguments below (the tweak that consists of combining several lower bounds more efficiently by taking separate horizontal and vertical maxima) it can't be included in the improved Manhattan distance, or only with extra care to distinguish various special cases.

Inversion distance

A similarly good heuristic function that can also be computed on the fly is inversion distance. For horizontal inversion distance, we linearise the square (conceptually) by concatenating the rows and looking at the number of inversions, i.e. pairs of tiles that are out of order. (We do not count inversions with the empty place.) Horizontal moves cannot affect horizontal inversions. A vertical move means that from the point of view of our linearised problem, one tile jumps over three other tiles. This changes the number of inversions by ±1 or ±3. Therefore a lower bound for the number of vertical moves in a solution is given by ⌈n/3⌉, where n is the number of inversions in our long row.

Obviously there is a similar lower bound for the number of horizontal moves which we get by considering the vertical inversions. For its computation we have to renumber the tiles in a way that corresponds to a matrix transposition. The total inversion distance is the sum of the two lower bounds we get in this way. Clearly it is admissible.

The author doesn't mention this, but there is actually a second horizontal inversion number, which we get if we renumber the tiles in such a way that it corresponds to putting the rows in the opposite order. This is likely to result in a different lower bound, and we can then take the maximum of the two. Of course we can improve the vertical horizontal inversion number in the same way.

Combined heuristic functions

If you have two (or more) admissible heuristic functions, then their maximum is again admissible. It takes longer to compute, but apart from that it is at least as good as each of the individual functions. In fact, if the functions have different strengths and weaknesses, then their maximum can be significantly better.

This is the case for the combination of Manhattan distance and inversion distance. Presumably the same still holds to some extent for improved Manhattan distance and inversion distance.

One observation that I have not seen before is that since in both Manhattan distance and inversion distance we get separate lower bounds for horizontal and vertical moves, we can also take the maximum before adding. Theoretically the result could be better in up to a quarter of cases. In practice the improvement caused by this tweak will almost certainly be less, but probably still worth it as it comes practically for free.

Pattern database

The basic idea of a pattern database is to relax the original problem in such a way that it becomes feasible to create a complete database of exact solutions, using, for example, dynamic programming. The optimal number of moves for a relaxed problem is a lower bound for the entire problem.

A very general definition of pattern that should cover most practically occurring cases is characterised by the following data:

  • A set of tiles whose horizontal moves you want to count.
  • A set of tiles whose vertical moves you want to count.
  • A partitioning of all positions that says which positions you consider equivalent.
  • A partitioning of all tiles that says which tiles you consider equivalent. Normally this is given just by considering two tiles equivalent if their goal positions are equivalent. But it can make sense to consider two tiles equivalent even if their goal positions are not.

A configuration is then given by a matrix with rows the equivalence classes of tiles and columns the equivalence classes of positions, telling you how many tiles of each type there are in positions of each type. The position up to equivalence of the empty space is implicit in this matrix. (However, sometimes it may make sense to remember it precisely and make that part of the configuration as well.)

The reason why I have made this a bit more general than usual is walking distance. It is always better than Manhattan distance, but it is not clear to me what its precise relation to improved Manhattan distance is. (My guess would be that it is often a bit better and rarely a bit worse.)

As for (improved) Manhattan distance and inversion distance, walking distance counts horizontal moves and vertical moves separately, so that we can again apply the tweak from the end of the last section when combining it with them. The database used for horizontal walking distance is relatively small and can even be used for vertical walking distance as well.

Additive pattern databases

Basically the idea was already described in full generality in the previous section. However, here the guiding idea is not to count horizontal moves of all tiles and vertical moves of all tiles, but rather to partition the tiles and count the minimal number of moves of each equivalence class of tiles separately. We can then again add the results.

Currently the fastest option, but requiring a lot of space, comes from dividing the puzzle into two halves (top and bottom or sometimes fringe and non-fringe - I don't know which is better). We distinguish all positions, but we consider all tiles with goal positions in one half to be equivalent. We only count the minimal number of moves of the other (individual) tiles, not distinguishing between horizontal and vertical moves.

The patterns for each of the two choices taken together are additive in the sense that (as in the case of counting horizontal and vertical moves separately) we can add them and still have a lower bound on the total number of moves.

Since the empty place causes an asymmetry, we need separate (large!) databases for top and bottom half. But on the plus side, we can reuse them for dual lower bounds on left and right half. We can then take the maximum of the following:

  • sum of lower bounds for top and bottom
  • sum of lower bounds for left and right
  • sum of lower bounds for horizontal and vertical moves, where each of these is the maximum over the (horizontal or vertical) improved Manhattan distance, inversion distance and walking distance

Varying the goal state

There are only two possible last moves. Unless the puzzle is already almost finished (don't forget to treat this case somehow if you decide to implement this idea!), the minimal number of moves for a full solution is therefore 1 plus the minimum of the minimum numbers of moves to reach either of the two penultimate configurations. Some of the heuristic functions have simple and straightforward adaptations to a general goal state and are sufficiently sensitive to this different point of view that this will occasionally result in a better bound.

Similarly, there are only four possible configurations two steps before the goal configuration is reached. The general idea is from this paper.

Pruning the search tree

IDA* revisits nodes. A small but potentially still significant part of this costly redundancy can be removed by detecting and pruning periodic moves. This paper describes the basic idea of how this can be done with the help of a large finite state machine that is built automatically as another precomputation.

Implementation tweaks

This paper says they got differences up to a running time factor of 28 between straightforward implementations and various low-level tweaks such as computing Manhattan distance incrementally, inlining functions, tweaking order of arithmetic operators etc.

Two optimisations they did not mention, but which are probably worth trying:

  1. When taking the maximum of a lower bound that is cheap to compute and one that is expensive, compute only the cheap one first. When taking the cheapest node from the priority queue, compute the expensive lower bound as well and adjust the overall result if necessary. If the overall change is substantial, place the now more expensive node back in the priority queue and consider the next cheapest node.
  2. To save space on databases, use the idea of Bloom filters to store them in such a way that false positives correspond to making the lower bound smaller. This has the potential of reducing the space needed greatly while preserving optimality and making the resulting heuristic function only slightly worse. Illustrative example that is probably not going to be sufficiently efficient: Use five hash functions and a byte array of length N initialised with 255 everywhere. To store f(x) for a configuration x, compute the five positions in the array and by making some of the bytes smaller ensure (if possible) that the sum of the bytes there is at most f(x).
\$\endgroup\$
  • \$\begingroup\$ Linear conflict function is great idea, I didn't think about it before :) I'll try and let you know about the result. \$\endgroup\$ – alcohol is evil Oct 25 '15 at 10:37
  • \$\begingroup\$ It still takes about 120 seconds to solve it with IDA* algorithm and linear conflict function. And with A* and linear conflict it takes 70 seconds, so A* is faster and memory consumption is not that bad, because the process takes about 50 MB. It's strange, because 15-puzzle solver windows application, which I downloaded, takes a few milliseconds to solve it with Manhattan Distance (without linear conflict). Maybe with IDA* I shouldn't use recursive function? And also javascript is slower than C++, which could be used to write windows application. But still too big difference... \$\endgroup\$ – alcohol is evil Oct 25 '15 at 18:55
  • \$\begingroup\$ Then I think the next step should be to add inversion distance (see PS), or if even that doesn't help, use pattern databases. I think it's normal to use two additive ones - either fringe + non-fringe or top half + bottom half. Additive means that you store the optimal number of moves of the labeled tiles (not the number of moves of the labeled tiles in an optimal solution). Maybe you can find out first which option is faster. \$\endgroup\$ – Hans Adler Oct 25 '15 at 23:29
  • \$\begingroup\$ Thank You ;) I forgot about loops, but have read one of your links again and it remainded me about them. When I disabled moves which are the same as previous moves, it takes 100 ms to solve my example puzzle ;) So it's over 1000 times faster. I think I can't get more in javascript with IDA* and Manhattan Distance with licean conflict, but I will try all other options as well. \$\endgroup\$ – alcohol is evil Oct 26 '15 at 20:36
  • \$\begingroup\$ Wow. I think that's already a really good running time for JavaScript. But I think there is a risk that a non-negligible percentage of problems are much harder than most. \$\endgroup\$ – Hans Adler Oct 26 '15 at 21:27
1
\$\begingroup\$

I'm not a javascript person, so it's possible I'm reading it wrong. However, it appears that your data structures are inefficient, and the algorithm seems to be doing more work than necessary.

People tend to throw around rather over-complicated pseudo-code for A*, which can often be misleading. This website provides a very clear and useful introduction to A* (and other graph search algorithms): http://www.redblobgames.com/pathfinding/a-star/introduction.html

The simplest way to implement A* involves a search frontier (the "open list") and a data structure to contain visited nodes (technically the union of the "open" and "closed" lists).

The search frontier stores a node and it's f-cost, and is commonly implemented as a priority queue. This is usually implemented as a heap, with logarithmic time insertion and removal. You appear to be using a flat array instead, and searching through the entire structure to find the best element (lowest f-cost). You also appear to be (linearly) checking the search frontier for the next element as well, which is unnecessary.

The visited data structure can be implemented as a map, with the "next" node as the key, and storing the g cost and the current (parent) node. Using a map provides logarithmic lookup (assuming a binary tree structure, or constant time if you use a hash map).

\$\endgroup\$
  • \$\begingroup\$ Thanks. I will write again my code with A* and with your tips to solve 8-puzzle. Why shouldn't I search frontier for next element? I'm looking for element with smallest f. When I was taking first element from the list and expanding it, it was taking more time to solve the puzzle. \$\endgroup\$ – alcohol is evil Oct 26 '15 at 21:04
  • \$\begingroup\$ With the frontier as a dynamic array, you have to iterate through every single element to find the lowest f-cost. This can be slow. Taking the first element won't give you the minimum value unless you keep the list sorted. Keeping the list in a particular order is basically what a priority queue does, which makes the time to find the minimum element constant. I'm not experienced with Javascript, so I don't know exactly what data structures Javascript provides, or whether you'd have to implement one yourself, sorry. \$\endgroup\$ – user673679 Oct 26 '15 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.