So I was trying to implement BFS on a Sliding Blocks puzzle (number type). Now the main thing I noticed that is if you have a 4*4 board the number of states can be as large as 16! so I cannot enumerate all states beforehand.

So my question is how do I keep track of already visited states? (I am using a class board each class instance contains an unique board pattern and is created by enumerating all possible steps from the current step).

I searched on the net and apparently they do not go back to the just completed previous step, BUT we can go back to the previous step by another route too and then again re-enumerate all steps which has been previously visited. So how to keep track of visited states when all the states have not been enumerated already? (comparing already present states to the present step will be costly).

  • 1
    Side Note: I could not think of a more appropriate Stack to post this question. I am aware implementation details are generally not welcome in this Stack. – DuttaA Aug 14 at 13:04
  • 2
    imo this is a great question for SE:AI because it's not just about implementation, but the concept itself. Not to mention, the question attracted 4 legit answers in a matter of hours. (Took the liberty of editing the title for search, and creating a BFS tag) – DukeZhou Aug 14 at 19:14
up vote 8 down vote accepted

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are:

  • inserting elements
  • testing if elements are already in there

Pretty much every programming language should already have support for a data structure that can perform both of these operations in constant ($O(1)$) time. For example:

  • set in Python
  • HashSet in Java

At first glance, it may seem like adding all the states you ever see to a set like this will be expensive memory-wise, but it is not too bad in comparison to the memory you already need for your frontier; if your branching factor is $b$, your frontier will grow by $b - 1$ elements per node that you visit (remove $1$ node from frontier to "visit" it, add $b$ new successors/children), whereas your set will only grow by $1$ extra node per visited node.

In pseudocode, such a set (let's name it closed_set, to be consistent with the pseudocode on wikipedia could be used in a Breadth-First Search as follows:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(some variations of this pseudocode might work too, and be more or less efficient depending on the situation; for example, you could also take the closed_set to contain all nodes of which you have already added children to the frontier, and then entirely avoid the generate_children() call if current is already in the closed_set.)


What I described above would be the standard way to handle this problem. Intuitively, I suspect a different "solution" could be to always randomize the order of a new list of successor states before adding them to the frontier. This way, you do not avoid the problem of occasionally adding states that you've already previousl expanded to the frontier, but I do think it should significantly reduce the risk of getting stuck in infinite cycles.

Be careful: I do not know of any formal analysis of this solution that proves that it always avoids infinite cycles though. If I try to "run" this through my head, intuitively, I suspect it should kind of work, and it does not require any extra memory. There may be edge cases that I'm not thinking of right now though, so it also simply might not work, the standard solution described above will be a safer bet (at the cost of more memory).

  • 1
    I will be able to do that but the comparison time will start to increase exponentially – DuttaA Aug 14 at 13:56
  • 3
    @DuttaA No the comparison time should not increase exponentially. These sets, hash sets, or whatever they happen to be called in your language of choice, should be able to test whether or not they contain any given state $S$ with constant computational complexity $O(1)$, regardless of how many elements they already contain. They're not lists, they don't test if they already contain $S$ by comparing to every currently-contained element. – Dennis Soemers Aug 14 at 13:59
  • 1
    @DuttaA I've added some pseudocode to describe exactly how the set would be used, hopefully that may clarify something. Note that we never ever loop through the entire closed_set, its size should never affect our (asymptotic) computation time. – Dennis Soemers Aug 14 at 14:15
  • 1
    Actually I was doing it using c++ I don't have any idea of hashing...Guess I'll use python now...Thanks for the answer – DuttaA Aug 14 at 16:18
  • 3
    @DuttaA In C++ you'd probably want to use an std::unordered_set – Dennis Soemers Aug 14 at 16:52

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.

However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an absurd amount of memory.

To fix this, don't use BFS. It's intractable for all but the simplest of problems, because it requires both time and memory that are exponential in the distance to the nearest goal state.

A much more memory-efficient algorithm is iterative deepening. It has all the desirable properties of BFS, but uses only O(n) memory, where n is the number of moves to reach the nearest solution. It might still take a while, but you'll hit memory limits long before CPU-related limits.

Better still, develop a domain specific heuristic, and use A* search. This should require you to examine only a very small number of nodes, and allow the search to complete in something much closer to linear time.

  • 2
    yeah this is the more practically useful answer for people who want to efficiently solve the puzzle. My answer is the one for people who insist on using BFS (because they just want to see it in action, or learn how to implement it, or whatever reason). Note that BFS hopefully will not be required to store $16!$ nodes by the way; that's only the worst case, it might be able to find a solution before that time. – Dennis Soemers Aug 14 at 15:32
  • @DennisSoemers is correct..You are also correct..I was just trying to hone my skills... I'll move to more advanced search methods later on – DuttaA Aug 14 at 16:20
  • are there cases where BFS can return acceptable local solutions? (I'm dealing with more like 81!*tbd-value and breadth-first seems optimal in that there are blocking factors that can be easy to miss without exhaustion. Right now we're not worried about truly strong play, rather "respectably weak" general performance over an array of unpredictable gameboard topologies.) – DukeZhou Aug 14 at 19:24
  • 2
    @DukeZhou BFS is usually used only when a complete solution is sought. To stop it early, you need a function that estimates the relative quality of different partial solutions, but if you have such a function, you can probably just use A* instead! – John Doucette Aug 14 at 21:13
  • Instead of saying "the number of moves in the game", I'd recommend "the minimum number of moves to get to the goal". I'd think of the number of moves in the game as every move that takes you from one of the 16! states to any other, which is a lot more memory than iterative deepening uses. – NotThatGuy Aug 14 at 22:18

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

A few key points:

  • In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM.
  • There are actually only 15!/2 states, since the state space has two mutually unreachable components.
  • This works in the sliding tile puzzle because the state spaces grows really slowly from level to level. This means that the total memory required for any level is far smaller than the full size of the state space. (This contrasts with a state space like Rubik's Cube, where the state space grows much more quickly.)
  • Because the sliding-tile puzzle is undirected, you only have to worry about duplicates in the current or previous layer. In a directed space you may generate duplicates in any previous layer of the search which makes things much more complicated.
  • In the original work by Korf (linked above) they didn't actually store the result of the search - the search just computed how many states were at each level. If you want to store the first results you need something like WMBFS (http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf)
  • There are three primary approaches to comparing states from the previous layers when states are stored on disk.
    • The first is sorting-based. If you sort two files of successors, you can scan them in linear order to find duplicates.
    • The second is hash-based. If you use a hash function to group successors into files, you can load files which are smaller than the full state space to check for duplicates. (Note that there are two hash functions here -- one to send a state to a file, and one to differentiate states within that file.)
    • The third is structured duplicate detection. This is a form of hash-based detection, but it is done in a way that duplicates can be checked immediately when they are generated instead of after they have all been generated.

There is a lot more to be said here, but the paper(s) above give a lot more details.

  • It is a great answer..but not for noobs like me :)...I am not that expert of a programmer.. – DuttaA Aug 15 at 5:50
  • How would undirected help you avoid duplicates in other layers? Surely you'd be able to get back to a node in another layer by moving 3 tiles in a circle. If anything, directed would help you avoid duplicates, because it's more restrictive. The linked paper talks about duplicate detection, but doesn't mention undirected or directed at all, nor seems to mention avoiding duplicates at different levels (but I could've missed that in my very brief scan of it). – NotThatGuy Aug 15 at 13:27
  • @NotThatGuy In an undirected graph a parent and a child are at most distance 1 apart in the depth they are found in the BFS. This is because once one is found, the undirected edge guarantees that the other will be found immediately afterwards. But, in a directed graph, a state at depth 10 can generate children at depth 2, because the child at depth 2 doesn't have to have an edge back to the other state (this would make it depth 3 instead of depth 10). – Nathan S. Aug 15 at 19:10
  • @NotThatGuy If you move 3 tiles in a circle you create a cycle, but a BFS will explore that in both directions simultaneously, so it won't actually take you back to the much shallower depth. The full 3x2 sliding tile is shown in this demo, and you can track the cycles to see how they occur: movingai.com/SAS/IDA – Nathan S. Aug 15 at 19:34
  • 1
    awesomeness. Welcome to SE:AI! – DukeZhou Aug 15 at 20:11

Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems, that it resolves this issue for you.

Consider that your BFS requires you to keep a stack of unprocessed states. As you progress into the puzzle, the states you deal with become more and more different, so you're likely to see that each ply of your BFS multiplies the number of states to look at by roughly 3.

This means that, when you're processing the last ply of your BFS, you have to have at least 16!/3 states in memory. Whatever approach you used to make sure that fit in memory will be sufficient to ensure your previously-visited list fits in memory as well.

As others have pointed out, this is not the best algorithm to use. Use an algorithm which is a better fit for the problem.

The 15-puzzle problem is played on a 4x4 board. Implementing this in sourcecode is done stepwise. At first, the game engine itself has to be programmed. This allows to play the game by a human operator. The 15-puzzle game has only one free element and on this element the actions are executed. The game engine accepts four possible commands: left, right, up and down. Other actions are not allowed, and it is possible to control the game only with these instructions.

The next layer for playing the game is a GUI. This is very important, because it allows to test the game engine and try to solve the game by hand. Also, a GUI is important because we need to figure out potential heuristics. And now we can talk about the AI itself. The AI has to send commands to the game engine (left, right, up and down). A naive approach for a solver would be a brute force search algorithm, which means, that the AI is sending random commands until the goal state is reached. A more advanced idea is to implement some kind of pattern database which reduces the state space. Breadth first search isn't directly a heuristics, but it is a beginning. It is equal to create a graph for testing out possible movements in a chronological way.

Tracking existing states can be done with a graph. Each state is a node, has an id and a parent id. The AI can add and delete nodes in the graph, and the planner can solve the graph for finding a path to the goal. From a programming perspective a game-engine of the 15 puzzle is the object and the list of many objects is a arraylist. They are stored in a graph class. Realizing this in source code is a bit tricky, usually the first trial will fail and the project will produce lots of errors. To manage the complexity, such a project is usually done in an academic project, that means, it is a topic for writing a paper about it which can have 100 pages and more.

Approaches to the Game

It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and endless looping when searching a graph that may contain graph cycles.

However, those trivial facts are not pertinent if the goal is to complete the puzzle in the fewest computing cycles. Breadth first search isn't a practical way to complete an orthogonal move puzzle. The very high cost of a breadth first search would only be necessary if number of moves is of paramount importance for some reason.

Sub-sequence Descent

Most of the vertices representing states will never be visited, and each state that is visited can have between two and four outgoing edges. Each block has an initial position and a final position and the board is symmetric. The greatest freedom of choice exists when the open space is one of the four middle positions. The least is when the open space is one of the four corner positions.

A reasonable disparity (error) function is simply the sum of all x disparities plus the sum of all y disparities and a number heuristically representing which of the three levels of freedom of movement exists because of the resulting placement of the open space (middle, edge, corner).

Although blocks may temporarily move away from their destinations to support a strategy toward completion requiring a sequence of moves, there is rarely a case where such a strategy exceeds eight moves, generating, on the average, 5,184 permutations for which the final states can be compared using the disparity function above.

If the empty space and positions of block 1 through 15 are encoded as an array of nibbles, only addition, subtraction, and bit-wise operations are needed, making the algorithm fast. Repeating the eight move brute force strategies can be repeated until disparity falls to zero.

Summary

This algorithm cannot cycle because there is always at least one of the permutations of eight moves that decreases disparity, regardless of the initial state, with the exception of a starting state that is already complete.

We can start with just the starting state in your queue and keep a track of the depth, and return the depth as answer once we arrive at the state with all lights switched off or return −1once there are no more nodes left unvisited. To keep track of visited nodes, we can define a function which maps each state to an integer or string and use a map/dictionary/set to store visited states.

Following is a sample python code:

start = [[0,1,0],[1,0,0],[1,1,0]] q = [start,[]]

def getStateVal(state): val = 0 base = 1 for i in range(len(state)): for j in range(len(state[0])): val += base * state[i][j] base = base * 2 return val

def toggle_bit(bit): return 1 if bit == 0 else 0

def toggle(state, i, j): new_state = [] for r in state: new_state.append([c for c in r])

new_state[i][j] = toggle_bit(new_state[i][j])
if i+1 < len(state):
    new_state[i+1][j] = toggle_bit(new_state[i+1][j])
if i-1 >= 0:
    new_state[i-1][j] = toggle_bit(new_state[i-1][j])
if j+1 < len(state[0]):
    new_state[i][j+1] = toggle_bit(new_state[i][j+1])
if j-1 >= 0:
    new_state[i][j-1] = toggle_bit(new_state[i][j-1])

return new_state

d = {} depth = 0 while len(q) > 0: state = q[0] q.pop(0) if len(state) == 0: depth += 1 q.append(state) else: val = getStateVal(state) if val == 0: print depth break if val not in d: d[val] = True for i in range(len(state)): for j in range(len(state)): new_state = toggle(state, i, j) q.append(new_state)

start represents the starting state of the board. A value of 1 represents that the light in that position is on and 0 represents otherwise. The empty list represents end of a level, it is used to keep track of the depth (no. of moves made to reach that position) d is the dictionary which keeps track of visited nodes getStateVal function maps a state to an integer, here each state is interpreted as a binary string and corresponding decimal value is treated as the integer mapped value.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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