Thanks,
But I still don''t get why you have to devide by 4.
The point is to tell which state is closer to the goal state.
If I devide by 4 anyway, what different does it make if I copare 4 with 6 or 1 with 1.5? (Bsides making it less accurate...)
Or do you mean that I should devide by 4 only if I have a certain situation, like when all the numbers in a certain 2x2 squre are 1 step away from their place?

For the simple heuristic i suggested you MUST divide by 4 for the heuristic to be valid (admissible) because there does exist a case where you can move 4 numbers into the correct position with a single rotation. However, if you make a more complex heuristic that does some sort of check on how many numbers will move into place with a rotation you may be able to forgo the divide by 4.
I can guarantee that my simple heuristic is admissible, i''m not sure to what extreme you would have to go to with check how many numbers rotations move into place to make such a heuristic admissible. And remember, it''s pointless having a heuristic that takes longer to calculate than the search would take to find the answer

quote: Original post by Anonymous Poster
It might help to read the post Timkin

I did read the post... and as I said...

quote: Original post by Timkin
I have not seen the particular puzzle you are talking about as I do not own a Nokia phone... however, it basically sounds like the 8-puzzle... assuming that it IS the 8-puzzle, there are two widely accepted and well known heuristics for this problem.

...meaning that if my assumption wasn''t valid, then ignore my post.

However, going by...

quote: Original post by Anonymous Poster
The puzzle as stated above is to get all the numbers into the right place by a series of clockwise rotations of 4 numbers (in a 2x2 square) at a time.

then it is clear that this IS a sliding tile class of puzzle (which the 8-puzzle is also a member) and hence the above heuristics I mentioned are still applicable.... particularly the Manhattan distance... have a think about it and you''ll see why.

Cheers,

Timkin

There is one point I''m not sure about. Does the heuristic need to tell how many steps are until we reach the goal state?
I thought that it was enough to have a heuristic that will compare two states and tell us which is closer to the goal state. That way we can choose it and not the other in our A*.
If that is so, what does it matter if we devide by 4?
If we have to choose between the first state (1 strp from goal) and another state than the first state will gove us a 4, and the other state will give us more.
But anyway, why are we arguing about this? It''s not effective counting the anount of numbers that are out of place, because there can be a state that there are only 2 numbers out of place and we''re miles away from the goal state.
What does it say in that book about AI you mentioned before?

Ok, at each node of the A* search you apply the function f(n) = g(n) + h(n) where n is the current node, g(n) is the cost from the root to the current node, and h(n) is the heuristic that estimates the cost to the goal. So, the next node you should expand is the node with the lowest f(n) that hasn''t been expanded yet.
To give an example, imagine that you have 2 nodes, n1 has a current cost (g(n1)) of 7, and n2 has a g(n2) of 4. Now we apply the heuristics (without dividing by 4). If n1 has 4 numbers out of place, and n2 has 8 numbers out of place, then f(n1) = 7 + 4 = 11 and f(n2) = 4 + 8 = 12. This means that n1 would be expanded before n2. However, if we use an admissable heuristic (one that never overestimates), and so we divide by 4, then we get f(n1) = 7 + 1 = 8 and f(n2) = 4 + 2 = 6, so n2 would be expanded before n1 in this case. That is why the divide 4 is neccessary (due to the ratio of g(n) to h(n)).

As timkin mentioned, you could use manhattan distance (divided by 4), which will be more effective than just numbers out of place, but (as far as i can think about it atm) this is not a simple problem, and A* is going to have to do a lot of searching.
If you would prefer to think about it a different way than just divide by 4, try thinking about the relaxed problem approach where you would come up with, instead of "rotate a 2x2 square clockwise" you would come up with "move any 4 numbers 1 position, horizontal or vertical" which would be the equivalent to the manhattan distance.
The AI book i mentioned says a lot of things, anythign specific you were after?

Have you ever considered using an approximate (read *wrong*) heuristic to get the program started and building up the value of h(n) as the system progresses from state n to the goal state. So for each state in the search tree (factorial 9 of them, i.e. 362,880 not a big number) you estimate the value of h(n) when you come across it for the first time. Then, when you actually proceed from any given state to the goal state, you apply the actual cost and store it with that node in the search space. That way the only thing underestimating the value of h(n) does is encourage the system to try out new paths through the search space it hasn''t yet tried.
Of course the first time through you may well take a longer route from state n to the goal state than necessary, but this again will only encourage the system to try new paths.

Of course this doesn''t answer your question of "what''s a good heuristic for this problem" but perhaps you could come up with the answer as you go along, by analysing the state of a node whilst knowing the actual value of h(n) for that node you could find a method of deriving h(n) by some learning method. Evolving an analytical neural net for instance (or a set of neural nets with different masks looking for different properties, not necessarily over the entire board) could give an approximation to h(n) for any position. You could then use those nets if you where trying to build an AI for a larger board of the same basic problem.

Mike

quote: Original post by Kalugny
There is one point I''m not sure about. Does the heuristic need to tell how many steps are until we reach the goal state?
I thought that it was enough to have a heuristic that will compare two states and tell us which is closer to the goal state. That way we can choose it and not the other in our A*.
If that is so, what does it matter if we devide by 4?
If we have to choose between the first state (1 strp from goal) and another state than the first state will gove us a 4, and the other state will give us more.
But anyway, why are we arguing about this? It''s not effective counting the anount of numbers that are out of place, because there can be a state that there are only 2 numbers out of place and we''re miles away from the goal state.

The heuristic is just an estimate, based on current knowledge. It doesn''t have to be ''correct''. If it was always going to be correct, it wouldn''t even be a heuristic, it would be the solution. So the ''number of numbers out of place'' heuristic is not too bad... certainly better than nothing.

So it doesn''t matter that it might occasionally be wrong, just as long as it''s generally right. If 9 numbers are out of place then that''s definitely worse than if 4 are out of place. And 4 out of place is worse than 0 out of place. It''s a generalisation, but that doesn''t matter.

And no, you don''t use heuristics to directly compare 2 states in A*. The heuristic contributes to an overall score which is stored with the state, and generally the ''best'' state is the one which is evaluated next. And you don''t discard the other states, you just postpone looking at them until there is no better alternative. I suggest you study the algorithm a little more.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions ]

least squares distance is generally the best heuristic in tile shifting games.

that is to say you have a concept of displacement of a tile. express that as a number. as a distance. now square all the distances your tiles are from their home. now square root that. thats your heuristic value. thats your concept of "better" its not perfect but in any sort of aggressive best first branch searching it will produce ok results _usually_

oh you asked for a system for detirming heuristics. there are proprietary programs out there that are designed to help users come to heuristics for a problem. sort of just test stuff though.

as for a science of heuristic. there isnt one really. sort of art. like noting that tile games in the past have done ok with least squares distance. and thinking this is a tile game therefor...

the math question might become why is least squares better then counting number of tiles in correct positions or why is this number algo better then that. and does that help us evaluate other non tile specific topics. but it breaks down to quickly if you go that route.





[edited by - declspec on May 5, 2002 1:19:08 PM]

I think a better value to divide the heuristic by 2, since not every rotation puts 4 pieces into their correct places, and some rotations actually move pieces AWAY from their correct spots, so something less than 4 seems better.

But if you want the heuristic to be admissible that won''t work. You can still do it with an inadmissible heuristic but you aren''t guaranteed to find the shortest path.