02-Nov-90 08:54    Jeffrey.Schlimmer            AI Seminar Next Tuesday
From: Jeffrey.Schlimmer@A.GP.CS.CMU.EDU
Carnegie Mellon                                              SCS AI Seminar

---------------------------------------------------------------------------

			       Hans Berliner
			School of Computer Science

	      SUPERPUZZ: THE IDEAL SINGLE-AGENT SEARCH DOMAIN

			 Tuesday, 6 November 1990
			    3:30-5:00 WeH 5409


				 Abstract

    We describe the  game of   SuperPuzz, which has   previously made  some
appearances around the community here.  SuperPuzz  has many properties that
make  it a more interesting   domain for single-agent  searching  than such
traditional games as  the 15-puzzle.  We will describe  the outcome of many
years of experience with  this game with programs  that solve instances  of
the    puzzle.   SuperPuzz  is the  most   difficult  puzzle  I  have  ever
encountered, comparable to chess in the intellect involved to play well.

    SuperPuzz  can be played  with a regular deck  of card  in a variety of
widths.  It is possible to  solve over 80%  of randomly generated instances
of SuperPuzz, regardless of the  puzzle  width.  However, the complexity of
the game goes up with the width.  This makes it a domain where one can vary
the  difficulty of the  problem, as   the aptitude   of the problem  solver
increases.  We began our  investigations with 4x6 SuperPuzz which typically
has solutions of length 23.  Today we are investigating 4x14 versions, with
solution lengths of 130.  That these problems can be  solved at  all is due
to ever increasing understanding of the fundamentals of how  the search can
be made effective.

    We discuss techniques  that    have   been  used  to   improve   search
performance.  The latest technique is  called "Invariances" and  allows the
search to posit theorems about what cannot be a useful attempt in lower and
sibling sub-trees.  This method allows exponential savings in search  to be
balanced off against the natural exponential growth  of the search process.
We conclude  by showing how the analysis   of  machine generated solutions,
that are barely understandable, can help improve the human's performance.

---------------------------------------------------------------------------
----------