Archived

This topic is now archived and is closed to further replies.

Kalugny

How are Heuristics made?

Recommended Posts

Kalugny    122
I want to make a program that will solve the Rotation puzzle that you can find on Nokia cellphones. For those of you who do not know it, it''s a 9x9 board with numbers 1-9 and you can rotate each 2x2 square. You need to arrange the board so that the numbers are in the correct order. It seems easy enough to use A* to do it, but for that I need a heuristic. That is, I need to know how close I am to the solution. I tried many things but it''s quite diffcult finding a mathmatical way to evaluate this, since the board changes quite drastically every move. Is there a way to make a heuristic or is it all trial-and-error? Thanks, Kalugny

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
One obvious heuristic is to use the amount of pieces that are already on their correct places. At least it should be better than no heuristic at all

Share this post


Link to post
Share on other sites
Kalugny    122
Well, of course.
But that''s no good.
Look at this:

2 5 3
1 4 6
7 8 9

You can solve this in one move: rotate the top-left 2x2 square clockwise. But there are 4 numbers not in place.
Here:

1 2 3
5 4 6
7 8 9

There are only 2 out of place but you can''t solve this in a few easy steps.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
As long as a heuristic does not overestimate it is ok, however a heuristic that is closer to the actual value (number of steps etc.) will (i think it''s proved) work better.
Number of numbers out of place is not a very good (and possibly invalid) heuristic because it does not neccessarily have a direct relation to the number of ''moves'' that will be required to solve the puzzle. A better heuristic would be along the lines of number of rotations required to solve the puzzle. You coould try using the minimum number of rotations to get each number into place (vaguely similar to using manhattan distance in nxn puzzle), you would need to come up with a heuristic that could, to some extent, take into account that multiple numbers can move at once. If you wanted to try something very simple though, the simplest heuristic i can think of right now, is
for each number, the sum of the minimum number of rotations to get that number into place divided by 4.
So, for your first example, with 4 numbers out of place, each number out of place is a single roatation from it''s correct position, so the sum of rotations = 4, divided by 4 your heuristic would give the value 1. (yay)
for your second example, you would get 0.5 (round up to 1 because you have to perform a full rotation) which isn''t anywhere near as nice a value, but hey, i did say it was a simple heuristic a more complex heuristic might take into account that those two numbers would require an opposite rotation and adjust itself.
Oh, and importantly, if all the numbers are in the right place, it will require 0 rotations, and 0 / 4 is 0.
Hope that helps at least a little

Share this post


Link to post
Share on other sites
Kalugny    122
Thanks, that is something to start with, but it won''t do.
Even in the second example it ends up as a 1. One rotation to get 4 to it''s proper place and 3 to get 5 to it''s proper place (all rotations are clockwise). But why divide by 4? Let''s take the maximum number of rotations for any one piece. If we do, then the first example get''s a 1, and the second get''s a 3.

But here are a number of other interesting states to look at:

2 6 4
1 3 5 Notice that this one can be solved by 3 rotations.
7 8 9

Using this method, this get''s a score of 3 as well (due to the 4) even though it''s a lot easier than the second example posted before.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Kal,

I think he meant take all the numbers, and how many rotations it''ll take to get them in their proper place. So, in example #1 of yours, it''ss take 1 rotation to get 1 to the proper place, 1 rotation for 2, 1 rotation for 4 and 1 rotation for 5. 1+1+1+1 = 4/4 = 1

Share this post


Link to post
Share on other sites
Kalugny    122
Yeah, sure, I got that.
It''s a nice idea I haven''t thought of before, bu it doesn''t solve the problem. Besides, I don''t see the point in deviding by 4.

But I return to the question I asked before: Is it all really just trial and error? Is there no way to construct a heuristic logically?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
The point of dividing by 4 was this:
During a rotation, you move 4 numbers at a time, therefore it is possible (as noted in your first example) for 4 numbers to be out of place, and then, after a single rotation thos 4 numbers will be in the correct place. So with 4 numbers moving at a time, rather than 1, this must be taken into account in the heuristic because the heurisitic will not work as efficiently if it overestimates. It''s easy to see that in example 1 4 would be an overestimate , so it is neccessary to divide by 4 so that in no case will the heurisitic overestimate.

The fact that you can only move clockwise is an important piece of the puzzle you didn''t mention before

You can construct a heuristic logically according to "AI: A Modern Approach", it suggests using the relaxed problem approach, which means removing some of the rules governing the puzzle to make the problem easier. For instance you might remove the rule the numbers have to rotate, instead you could ''replace'' that with ''move the 4 numbers in a 2x2 square to anywhere else on the board''. Then you can just use a heuristic basically the same as the first AP, where you just use the number of pieces that are out of place (divided by 4). Without making the heurisitc a lot more complicated, i really can''t think of a way to get around using the divide by 4, because you really must make sure the heuristic doesn''t overestimate to be effective (solve the puzzle in the minimum number of steps). There is also a suggestion that you can come up with a number of equally good heuristics, and just use max(h1, h2,...hn) as the current heuristic.
It''s not trial and error coming up with a heuristic...it might be trial and error coming up with a really good, or best, heuristic. Try using the relaxed problem approach to create a few heuristics.

Share this post


Link to post
Share on other sites
Timkin    864
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.

Heuristic 1: The number of tiles NOT currently in their correct position. Since each tile not in its correct position will have to move at least 1 square then this heuristic is guaranteed never to overestimate the actual distance to be moved;

and,

Heuristic 2: The Manhattan Distance , which is the sum of horizontal and vertical movements required to move the piece from its current position to its correct position (assuming no other pieces on the board to block it). So, for example, the number 4 is in the position of number 8, so there is 1 horizontal and 1 vertical move required to move it to the number 4 position, so the heuristic cost for that node in the search tree is 4.

Cheers,

Timkin

[edited by - Timkin on May 1, 2002 11:44:42 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
It might help to read the post Timkin
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.
Now get back to work on your PhD

Share this post


Link to post
Share on other sites
Kalugny    122
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?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites
Kalugny    122
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?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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?

Share this post


Link to post
Share on other sites
MikeD    158
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

Share this post


Link to post
Share on other sites
Kylotan    10008
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 ]

Share this post


Link to post
Share on other sites
declspec    126
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]

Share this post


Link to post
Share on other sites
Psybr    122
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Kalugny    122
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...

Share this post


Link to post
Share on other sites
declspec    126
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest 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.

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites