Heuristic search and the 8 puzzle
pe...@icce.rug.nl
I'm currently implementing some search algorithms in C++. For testing
purposes I use the 8 puzzle. The problem is what heuristic to
use for best search. The standard heuristic used in the 8 puzzle problem
as described in e.g. 'Nilsson, Problem-solving methods in artificial
intelligence' is the following:
h(n) = P(n) + 3S(n)
Where P(n) is the sum of distances that each tile is from "home" and
S(n) is a 'sequence score': every noncentral tile gets 2 points when it's
not followed by its proper successor and 0 if it is, a piece in the centre
scores 1. So far so good. When I implemented this I got far different results
than Nilsson writes. Next I checked Bratko, who also uses the same heuristic,
but again I didn't get the same result. The problem is not just that nodes
get different values, but (as a consequence of that) a different path is
followed (in one case according to Nilsson and Bratko a solution is found
in 18 steps while my program needs 22). I think the problem is in S(n),
what exactly does it mean that a tile is followed by another tile, does
this also apply to edges? and what about the last tile? (Bratko solves this
apparently by pretending that the last tile is 'followed' by the first, but
even when I followed his scheme I didn't get the same result).
So...my question is, has anyone worked on this before, if so, how did
you compute the sequence score? Or if you never of a better heuristic (this
one isn't admissible) let me know!
Thanks in advance!
Peter Bouthoorn
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| Steal a little and they throw you in jail | Peter Bouthoorn |
| Steal a lot and they make you king | pe...@icce.rug.nl |
| Bob Dylan | Linux addict |
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
--
The ICCE usenet account
providing access to usenet news
for the ICCE Experience
_WERKEN_AAN_DE_GRENZEN_VAN_HET_KUNNEN_
Marco Valtorta
>Hi,
>I'm currently implementing some search algorithms in C++. For testing
>purposes I use the 8 puzzle. The problem is what heuristic to
>use for best search. The standard heuristic used in the 8 puzzle problem
> Or if you never of a better heuristic (this
>one isn't admissible) let me know!
>Thanks in advance!
>Peter Bouthoorn
Two very good admissible heuristics are the Linear Conflict heuristic of
O.~Hansson, A.~Mayer, and M.~Yung.
\newblock Relaxed Models Yield Powerful Admissible Heuristics.
\newblock {\it Information Sciences}, to appear.
[This has appeared, but I do not have the exact reference
handy--apologies!]
and the X-Y heuristic described in
A.~Prieditis.
\newblock {\it Machine Discovery of Effective Admissible Heuristics}.
\newblock In {\it Proceedings of the Twelfth International Joint Conference
on
Artificial Intelligence}, Sidney, 1991, 720--725.
I hope this helps. Good luck!
Marco Valtorta, Assistant Professor and Undergraduate Director
Department of Computer Science internet: m...@usceast.cs.scarolina.edu
University of South Carolina tel.: (1)(803)777-4641
Columbia, SC 29208, U.S.A. fax: 777-3767 tlx: 805038 USC
Scott Schmidler
Marco Valtorta <m...@cs.scarolina.edu> wrote:
>Two very good admissible heuristics are the Linear Conflict heuristic of
>O.~Hansson, A.~Mayer, and M.~Yung.
>\newblock Relaxed Models Yield Powerful Admissible Heuristics.
>\newblock {\it Information Sciences}, to appear.
>[This has appeared, but I do not have the exact reference
>handy--apologies!]
The reference for this is:
O. Hansson, A.Mayer, and M. M. Yung. Criticizing Solutions to
Relaxed Models Yields Powerful Admissible Heuristics.
Information Sciences, 63:3, 1992
scott.