cant form a distance if the tiles dont have dimension. never meant it to be a formalism but its going that way *grin*

cant square and sum the distances of displacements then square root them if the tiles dont have dimension. the square length was a poor use of words. but it refers to the tiles physical dimensions. the algo of summing distance of displacement implies were seeing the board as a physical thing.

but anyway once you do the squareroot (sigma (square(displacement))) you get a number with distance as the dimension. for this admissable argument to have meaning you need to convert "distance" to "tile shifts"

im assuming. remember this got started by "whats it mean to overestimate" it was said your function estimates the number of tile shifts (in this context) if that estimate is more then the actual tile shifts it overestimated.

right?

ok one thing im confused about is this:
doesnt that mean a heuristic that always estimates 1 tile shift to goal state is always admisable? since clearly it cant overestimate. but thats not true because a heurstic that always says 1 tile shift to goal will provide you with a less then optimal path as branches are effectively explored randomly.

this whole idea must have something in the proof not stated but otherwise important to understanding the entire interaction.

ya im a rigorous bastard *grin*

In this puzzle (and most sliding tile class puzzles) a heuristic that always returns 1 (except when it''s in the goal state of course) is admissible, yes (because it never overestimates).
However it is not a very GOOD heuristic, as it will simply be performing a greedy search (using only the path cost so far to determine which node to expand next) and because the path cost between all child-parent nodes is 1 in this type of puzzle, it will basically be performing Breadth First Search.
Just because a heuristic is admissible, doesn''t mean it''s good
It won''t search very effectively, HOWEVER it will still find the optimal path! Because it still uses the path cost (so far) to order it''s nodes for expansion, it is impossible for it to expand a goal node on a non-optimal path before expanding a goal node on the optimal path.
Try this... (goal nodes represented with G with path cost to goal node listed beneath, normal nodes are N, path cost from all parent to child nodes = 1)

        root      1 /   \ 1       /     \       N1    N2    1 /\      /\ 1     /  \    /  \    N3   N4  G1  N5 1 / \   /\  (2)  /   \ G2   N6(3) 

Due to the path cost ordering, the nodes would be expanded in the following order (arbitrarily breaking ties)
N1, N2, N3, N4, G1, N5, G2, N6
So G1 (optimal) would be expanded before G2. However, the search has only run as well as BFS.
You may use a random element to break ties (when multiple nodes have the same path cost so far). But it will always expand all nodes of total path cost 2 before it expands any of total path cost 3, so it is impossible for it to not return the/an optimal path.

So, Let''s sum things up-
A heuristic is admissable only (that is, worth using?) if it never overestimates.
And, A heuristic is good if it gives a good guess as to how many moves are left.
But, only if it doesn''t take too much time to calculate.
Is that so?

And, if we now know that, how do we use Genetic Programming to evolve one such heuristic?

quote:Original post by Kalugny
So, Let''s sum things up-
A heuristic is admissable only (that is, worth using?) if it never overestimates.

No no! ''Admissible'' is a formal term that, basically speaking, means it never overestimates. There are plenty of inadmissible heuristics which are worth using, and plenty of admissible heuristics that are not much help.

quote:And, A heuristic is good if it gives a good guess as to how many moves are left.
But, only if it doesn''t take too much time to calculate.
Is that so?

Yes, this is the true measure of the quality of a heuristic unless finding the best path is more important than finding any path quickly. In most practical applications you don''t care if the path is not perfect, so long as you don''t have to spend forever searching for it.

quote:And, if we now know that, how do we use Genetic Programming to evolve one such heuristic?

You will really have to look into genetic algorithms to be able to do that, as a full explanation is too long for this thread. And when you understand that, it would be pretty obvious. You''d be encoding the weightings of each heuristic and testing their fitness on a random map. In this case though, it would probably be easier for you to just run a few tests with different weightings to find out for yourself, rather than set up GAs to do it for you.