Another interesting thing to note about this puzzle, is that the last state before the goal state will ALWAYS have exactly 4 numbers out of place, as the final rotation to reach the goal state must rotate 4 numbers into the correct position.

I finally figuered out what it is I mean to do, thanks to you.

The A* algorithm is just a way to get the most out of a big search, such as BFS.
So it doesn''t really matter all that much if the heuristic causes a bad decision once in a while...

exactly.

the answer is coming from the search not from the heuristic. there is also an issue of speed in the heuristic. if your heuristic takes forever to computer then it eats into how deep you can search. sometimes a "better" heuristic isnt "better" comes up all the time in chess etc.


someone pointed out that with heuristic like these that your not guarenteed to have the best solution just "a" solution. thats very true. but its also very true that there arnt many things that i can think of off the top of my head where there search algo is the guarentee that this solution is the best. its pretty rare.

Not sure i understand exactly what you''re saying at the end there, but A* is guaranteed to find the shortest path from initial state to goal state if such a path exists AND if the heuristic is admissible.

quote: Original post by Anonymous Poster
Not sure i understand exactly what you''re saying at the end there, but A* is guaranteed to find the shortest path from initial state to goal state if such a path exists AND if the heuristic is admissible.

... and it guarantees to search less nodes in the search tree than any other algorithm (BFS,DFS, etc).

declspec''s point is a good one though. If the computational cost of the heuristic is excessive, then you might be better off performing a brute force search on this problem, since the search space is tiny.

Cheers,

Timkin

Hello,

After seeing ur rather interesting problem, i decided to give it a go!

I used an OCT tree which calculated every possible combination on rotates from the given puzzel. It will only make a node if the node does not exist elsewhere on the tree, I had to do this as the number of nodes just EXPLODES after about 3 levels.

If you wanna take a look @ my code, just ask!



bangz.

Sure, I''d love to look at the code.
My e-mail is at the top of everyone of my messages, I think.

A. Poster, how do you know that a heuristic is admissable?
Is it that it doesn''t overestimates?

Another thing. If A* is guranteed to give the shortest path, and all I want is an answer in the shortest _time_ will it no be better to change the algorithm?

Yes, a heuristic is admissible if it NEVER over-estimates.

If you are going to attempt to find the answer via a search tecnique, you will be best off using A*, TimKin notes that it guarantees to expand fewer nodes than any other search, and although i would have to re-read some stuff to look that up, i would trust that he is correct. It is easy to see just by the nature of the A* algorithm that this would be the case (at least in a puzzle such as this) since the pathcost between each node is 1 (1 rotation) the A* algorithm can''t possibly search to a depth below that of the shortest goal node (so it will generally beat Depth first) and it won''t expand nodes with high pathcost+heuristic if there is a lower cost node to expand, so in this way it will beat breadth first.

Also, bangz, it is common to save searched states, if a state already exists in your saved states, then it''s likely that the search has already found a shorter path to that state and so it can kill the node where it has found a duplicated state.

Bangz,

Why did you code this with an octree? The way I see it you only have 4(!) choices with the puzzle. As you said you sometimes calculate some options twice, so you don''t recurse with this node. When you only calculate using say left-turnes, you don''t have his problem, making the tree a lot simpler with the same (or less?) number of calculations.

Know what I mean?

Edo

to prove that a heuristic can over estimate all we have to do is find a _specific_ case where it said result a is closer then result b? correct? im asking.

if so then a heuristic that wont rate that position where just two are switched above that position where four are switched but only one rotation from being done is going to be hard to find.

and if it does do that then it over estimates... hmm got to get down to what it means to overestimate in a tile game. tad confused better look at some code.

humph. what does "never over estimate" actually mean in this context? there i''ll just ask the question.

typically heuristics just order the results from good to bad. but "never over estimates" implies that with A* heuristics need to estimate how close you are to the end? asking again. AI suffers from vocabulary.