4

I'm trying to code a 8-puzzle game solver in C++, but I'm having a lot of problems while doing it. The program is currently working, but it takes too much steps to solve the puzzle. I mean, sometimes it can find the optimal solution, sometimes it takes as much as 400 steps to solve it. My main doubt is the following.. Imagine I have this diagram(this is just a draft):

enter image description here

I'm using Manhattan Distance as the heuristic function. After the first step we have two states where f(n)=5, so I expanded the tree. After expanding I still got two states where f(n)=2. Here is my doubt.. Do I still need to expand the tree till I got a unique lowest f(n)?

Thanks in advance!

pluralism
  • 1,487
  • 2
  • 16
  • 22
  • Are you sure you are using correct approach for this game? As far as I remember the game could be solved prettily trivially until some last steps. So generalizing - there is a straight-forward algorithm, there is no need for trees and heuristics. – Andrey Mar 26 '13 at 13:42
  • @Andrey: Usually people solve this puzzle with A* algorithm + a heuristic function as a guide. I'm trying to do it in my way, without using the algorithm, just the heuristic function. Maybe you are refering to A*/IDA* algorithm? – pluralism Mar 26 '13 at 13:44
  • I see what you mean, sorry, I didn't understood the question. – Andrey Mar 26 '13 at 13:46
  • I don't think a tree is a good algorithm for this puzzle having found an online version and solved by hand. – DiegoNolan Mar 26 '13 at 13:46
  • @DiegoNolan I mentally downvoted your comment. It is interesting CS task. – Andrey Mar 26 '13 at 13:47
  • @Andrey I never said it wasn't interesting I said I didn't think a tree was a good method because the tree could be infinite. Maybe in a lazy language but not in c++. – DiegoNolan Mar 26 '13 at 14:03
  • @DiegoNolan No, the tree wouldn't be infinite. The program would always choose the lowest f(n), so it would exist a point where the Manhattan Distance were 0. The program would then stop there. – pluralism Mar 26 '13 at 14:06
  • 1
    Instead of thinking of the problem space as a tree, think of it as a directional graph whose nodes are "game states" and whose edges are "moves" needed to get from one game state to another. There are only 362,880 possible game states for the 8 puzzle, so it's simple to do a brute-force breadth first search on the graph to get an optimal solution every time. (Don't try brute force for the 15 puzzle though, as it has 1 trillion states). – Kevin Mar 26 '13 at 14:07
  • @pluralism When you say Manhattan distance you mean the infinity norm? The sum of that for all 8 pieces. If the manhattan distance is zero when optimal I don't understand why you need to check for a unique minimum you know what the minimum should be. – DiegoNolan Mar 26 '13 at 14:23
  • @DiegoNolan Open the image I posted again.. In step 3 you see that f(n)=2, that is the lowest Manhattan Distance. How do you decide which of those two is the fasted to the goal state? You have to expand the tree till you got ONE unique f(n). That's the moment you know you're going to the fasted path. – pluralism Mar 26 '13 at 15:42
  • @pluralism How long do these 400 steps take to solve? That doesn't seem like way too much. At each there is 2-4 possible moves, correct? You are calling a step the act of creating the children of all notes in the tree? – DiegoNolan Mar 26 '13 at 15:50
  • @DiegoNolan It takes no more than 0.2s. But sometimes the program can find the optimal solution of 20 to 25 steps. The 400 steps only happen when the program finds the situation that is described on the picture. It selects a random move between the 2 lowest, and the one chosen is probably not the fastest. That's why I asked if we need to expand the tree till we find a unique f(n), or if there is another possible option. – pluralism Mar 26 '13 at 15:55
  • @pluralism Perhaps you could look at more than one node at a time. If one node is lower than another at adjacent nodes maybe create the children then check the sum. Or have some kind of tolerance. Such as you only create children of a node if it is within some tolerance of the minimum at that step. – DiegoNolan Mar 26 '13 at 16:01
  • @DiegoNolan I think I'll just use a simple BFS instead of A*. In average it generate 900,000 nodes, not to much considering that the computer is able to expand 10 million nodes/second. I'll report feedback as soon as possible :) Thank you! – pluralism Mar 26 '13 at 18:46

2 Answers2

3

Do I still need to expand the tree

You can't solve this puzzle greedily: always taking the branch with lower heuristic value will not lead you to the final solution every time. So you have to keep the other states around for backtracking. The order in which you expand them, whether simple BFS or heuristics-based A*, is up to you.

MvG
  • 57,380
  • 22
  • 148
  • 276
  • Thanks for pointing me that! My aproach actually works,but it takes too much steps. You can see in this link http://oi47.tinypic.com/2uh3jty.jpg that sometimes it takes 200+ steps and in the last one it only takes 26 steps, probably the optimal solution. – pluralism Mar 26 '13 at 21:46
  • 1
    @pluralism: neither solution is optimal. See [this implementation using A*](http://ideone.com/UZKd8b) for comparison. Instead of 259 moves, 27 are sufficient, and instead of 26 you only need 16. – MvG Mar 27 '13 at 08:49
  • 1
    Note that the implementation I mentioned in my previous comment is not really correct: when encountering an already-seen state in A*, a decrease operation might occur. This is not an issue in BFS. But [a more correct implementation](http://ideone.com/XRC69t) shows that the numbers I quoted were nonetheless correct. – MvG Mar 27 '13 at 09:01
  • Yes, you're correct, my aproach is terrible, but I just wanted to do something on my own, without using any existing algorithms :) Probably I'll have to switch to A*. – pluralism Mar 27 '13 at 11:38
  • @pluralism: there are not that many fundamentally different algorithms to solve a given problem. Nuances yes, but basically all kinds of shortest path algos for this kind of problem boil down to BFS, A* or Dijkstra, the latter two being pretty much equivalent in this case since the heuristics is monotone. Coming up with something new that actually works will be difficult. Reinventing one of these algorithms yourself, using some new terminology, is more likely. – MvG Mar 27 '13 at 11:46
1

here you can find processing applet that uses A* algorithm to find the shortest path from an initial state to the goal state. The code in the applet is available free.

rasco
  • 11
  • 1