OK, now let''s get down to business.

What would ba a good heuristic to start from?
We''ve talked about the Manhatten Distance divided by 4. That''s nice, but that brings out a question: What happens when there are less than 4 numbers out of place? It means that it would take MORE than 1 move to get to the solution, and the result comes out as less than 1.
Is there a way to deal with that, or do we have to tolerate that it will choose the wrong path once in a while (note that it''s quite a common situation)?
Should we round it to 1 if the result comes out as less than 1, or should we use real numbers? Or maybe do something special if the result comes out as less than 1?
And the ultimate question: If we do find a heuristic that never overestimates, wouldn''t it be equally bad if it underestimates constantly?

I thought this had been made pretty clear. It doesn''t matter if the heuristic is occasionally wrong. It''s just there to try and direct the search more effectively. Even if the heuristic for A* is abysmal, the worse-case complexity is still no worse than BFS or DFS since you will still just end up searching every possible state and finding the result in the end, if there is a result. Any heuristic which is not blatantly wrong is likely to be beneficial providing it''s not too expensive to compute.

I think that Manhattan difference divided by 4 sounds reasonable. But just to complicate matters, if you''re worried about the relative weighting of the cost so far compared to the heuristic, (ie. the heuristic is too small or too large to be effective) then you could discover the optimal combination through genetic algorithms. The values you''d be evolving would be the 2 weightings of the cost so far and the estimate, between 0.0 and 1.0, and the fitness of a given solution would be how few moves it took to find the solution for a random board position (so 1/num_moves sounds reasonable to me).

Actually, I expect that using GAs to find good weightings for multiple heuristics is perhaps a good compromise method, if you know that there are situations when each heuristic can be inaccurate. Just throwing an idea out though.

Finally, did anyone point out this link yet, to a similar problem: http://www.geocities.com/csmba/?

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

I''m glad you said what you said, since I have thought about using GA to evolve a good heuristic.
The problem is, I don''t really understand how to do it.
OK, the fitness is obvious, but how do I actually evole heuristics? How to apply changes?

"What else would an A* heuristic estimate other then how close (or far away) you are from the goal. If you''ve read something that says otherwise i''d be interested to know. Remember that in A* it is not just the heuristic that you use to order the nodes (for order of expansion) it is the heuristic estimate + the actual path cost to that node."

Artificial Intelligence A Modern Approach by err hmm gaaa he''s famous. forgot the author. Bennen. think thats it.

Anyway there in that book an A* example conversation uses the standard tile shifting game. you have a 4 by 4 tiles one gap shift them into order. the heuristic: better is the one that minimize the least squares distance. ( as i outlined early in this thread... and people thought i pulled that out my butt i bet. in the book bennen describes it as the best heuristic known for that game.)

you asked for an example =) there ya go. Estimating which path cost is greater is all you need from an A* heuristic. you dont need the actual path cost estimate.

How those types of heuristic relate to admissable is of interest.

to this:
"I thought this had been made pretty clear. It doesn''t matter if the heuristic is occasionally wrong. "

ya i was the one that said it. ok get back to the geometric interpretation of A* as a path over an obstacle course. using an over estimating heuristic in that setting has your resultant path wandering sometimes away from the goal. it would get to the goal but it might not be the fastest way to the goal.

the question when ever you design a search is how can i make this search come up with the best answer... or better answers. in this example game the fastest solution in terms of number of steps. sometimes it possible sometimes its not.


someone noted however that if your heuristic always underestimates how long it will take to get to the goal

Firstly, i don''t see how least means squares is not an estimate of the distance to the goal. As far as i can tell it is exactly that. If you can explain how it''s not, please do

"How those types of heuristic relate to admissable is of interest."
You can test this, just solve the puzzle from every possible start state (and keep track of states as you will come across them in later states) and check wether the heuristic ever overestimates the actual cost to the goal from that state.

"the question when ever you design a search is how can i make this search come up with the best answer... or better answers. in this example game the fastest solution in terms of number of steps. sometimes it possible sometimes its not."
A* will always find the shortest path if the heuristic is admissible. (Is that what you were talking about?)

"someone noted however that if your heuristic always underestimates how long it will take to get to the goal"
I think what you are saying here is that if the heuristic always underestimates this is very bad (??). It is true that, the further the heuristic estimate is fromt he true cost, the longer the search will take (more nodes expanded) however, it will still find the shortest path, and will still perform better than BFS (and better than DFS by virtue of DFS not being complete). Even if you use a heuristic that returns 1 unless it is in the goal state (1 being the smallest move possible)...eg.
if ( !goalState() ) return 1;
It will only perform as badly as a greedy search.

"Estimating which path cost is greater is all you need from an A* heuristic. you dont need the actual path cost estimate."
You need the path cost to expand the right nodes.

quote: Original post by Anonymous Poster
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.

Okay, here is an excerpt from a post I made in this thread...

quote: Original post Timkin
A* guarantees to expand all nodes within a given contour of the cost space BEFORE considering any nodes in the next highest contour.

Remember that we require an admissable heuristic for A*. We require that the heuristic underestimate the actual cost to get from a node to the goal. We ALSO require that the cost function be monotonically increasing. Taken together, these two constraints mean that as we expand nodes out from the start node, then 1) the cost of each node increases (or at least doesnt decrease) with distance from the start; and, 2) that the estimate of that cost will never be greater than the actual cost of a path through that node to the goal. Since we choose to expand the lowest estimated cost path first, then every iteration, the level of cost considered increases. The algorithm therefore MUST - if it finds a path to the goal - have found the lowest cost path, {edit}since it expanded the node with the lowest estimated cost{edit}. This can be proven mathematically, but I'll spare you the grim details!

As Kylotan suggested... it doesn't matter too much if the A* heuristic overestimates the cost some of the time. Certainly, you will violate the minimal cost path guarantee of A*. However, there is a nice theory that suggests that the proportion of searches that dont return the lowest cost path is about the same proprotion of heuristic estimates that are over-estimates.

... and a heuristic is better than no heuristic! So, pick one and implement it and see what happens! Play with it, tune it and see what happens. This is one good way to learn about the nuts and bolts of A*'s mathematical guarantees.

Cheers,

Timkin

[edited by - Timkin on May 8, 2002 10:23:54 PM]

"Firstly, i don''t see how least means squares is not an estimate of the distance to the goal. As far as i can tell it is exactly that. If you can explain how it''s not, please do."

Is the least means squares a statement of path distance in a tile shifting game?
No. distance being defined as the number of shifts it takes to get to the goal. this heuristic doesnt say a darn thing bout number of shifts.

for that you need to convert some float to an int of shifts. you could just floor(f(board)) calling that int the number of shifts noting its not hard to generate a board where thats an overestimate. See what im saying? the least squares distances doesnt have units of shifts. another function is implied that would convert a unit of abstract distance (sense our board has no dimensions) to shifts.

side note:
if you think the one i gave is implied then
1_2_3
4_6_9
7_5_8

overestimates. floor(f(board)/square_size) generates a 2. where as the actual shift count is one. (i use square_size of 1). proving that heuristic while good is not admissable.

Perhaps you should use square_size = 4.

that comes out out to the same result square_size is inside f(board) as sqrt(4*4+4*4 + 4*4 +4*4).
f(board) is summing the squared displacements then square rooting it.

that gets you to 8 divided by 4 is 2 again. square size is really irrelevant but since it was implied inside the function it had to be mentioned outside the function in number of shifts = f(board)/square_size

What does square_size actually refer to? I''m assuming board is the "least squares distance" function (also known as euclidean distance i think?).
As for some other things, number of numbers out of place also doesn''t say anything explicit about the distance to the goal. It''s also interesting to note that you called the function "least squares distance" in an earlier post, eluding to the fact that it may indeed be related to distance.
I''ll maintain my stance that it would be difficult to have a heuristic that doesn''t estimate distance to the goal using A*, as an estimate of distance to the goal is how A* decides which node to expand next (combined with path cost so far).
It''s interesting that you note that the "least means squared" or "least squares distance" (whatever it''s called) is not admissible (in this rotating puzzle problem), however i have an inkling of a feeling that it may in fact be admissible in the standard sliding tile nxn puzzle that it was most likely designed for. I may write a small program to check this, if i do i''ll post the results