From cube-lovers-errors@mc.lcs.mit.edu Tue Feb 15 17:39:09 2000
Return-Path:
Received: from sun28.aic.nrl.navy.mil (sun28.aic.nrl.navy.mil [132.250.84.38])
by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id RAA05665
for ; Tue, 15 Feb 2000 17:39:09 -0500 (EST)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
From: Jerry Bryan
To: Cube-Lovers
Subject: Re : Stuff...
In-Reply-To: <388AB533.798B2C6@health.on.net>
Message-Id:
Date: Thu, 27 Jan 2000 23:47:47 -0500 (Eastern Standard Time)
On Sun, 23 Jan 2000 18:30:51 +1030 Ghan wrote:
> I thought I was pretty good until I discovered that my program took
> 18 minutes to check all the 9 move algorithms! (I have a Pentium II
> 266, although not being very computer smart I'm not sure how much
> difference this makes.) I found out that more than half the
> configurations required 9 moves or more. Well, this was pretty
> embarrassing, considering that there are computer programs which can
> solve the 3x3x3 in seconds (or so I've read, I haven't tried any of
> these programs). So I'm wondering how to write a fast solver. Is my
> program slow because of my bad programming skills, or is my method
> just plain slow? I can't think of any other methods to find the
> solution.
First of all, you need to be careful what you define as a move.
Cubists seem to fall approximately equally into one of two camps --
those who count a 90 degree turn of one face as a move (a quarter
turn) and those who count either a 90 degree turn (a quarter turn) or
a 180 degree turn of one face (a half turn) as one move.
Quarter turns and half turns are collectively called face turns. You
will sometimes see a solution described as an 18q solution (18
quarter turns) or as a 16f solution (16 face turns) or something like
that. The face turn terminology distinguishes between twists of
external (faces) and internal layers (slices). A 3x3x3 can be solved
using only face moves. A 4x4x4 or 5x5x5 etc. require both face and
slice moves.
Second, you need to distinguish between programs which calculate
optimal solutions vs. those which calculate suboptimal solutions. I
am not aware of any programs which can calculate optimal solutions
for the 3x3x3 in seconds. The best programs for optimal solutions
can require an hour or two or maybe a day or two to calculate an
optimal solution, depending on the speed of the machine, the memory
size of the machine, and the difficulty of the problem at hand. This
may seem like a long time, but really it's an amazing achievement.
It is true that there are programs which can calculate *very good*
suboptimal solutions in just a few seconds. The best example is
Herbert Kociemba's Cube Explorer 1.5. It is downloadable from
Herbert's Web site (you can find it with any search engine) and from
the Cube-Lovers FTP site. If you let it run long enough it will
eventually find an optimal solution, but "long enough" may be a great
deal longer than for programs designed specifically to find optimal
solutions.
The two amazing things to me about Cube Explorer 1.5 are that it is
so extremely fast, and that its suboptimal solutions are so darn near
optimal as quickly as they are. In fact, it sometimes finds an
optimal solution in a matter of minutes, except that it is usually
not able to prove the that the solution is optimal anywhere near as
quickly as it is able to find the solution. I will include only an
extremely brief description of its algorithm, and I will defer that
description until later in my note.
The best programs for finding optimal solutions use an IDA* algorithm
invented by Richard Korf. IDA* was not invented specifically for
solving the cube, but it is well adapted to solving the cube. Cube
Explorer 1.5 uses an IDA* algorithm in part.
I will assume that you understand breadth first and depth first
searches of a search space. Your program for the 2x2x2 was
essentially doing a breadth first search -- all one move sequences,
all two move sequences, all three move sequences, etc.
Depth first searches generally require much less memory than breadth
first. Only the positions from your current state to the goal state
have to be stored. To do a depth first search of up to nine moves,
you never have to store more than nine states (well, really ten, the
original one plus nine more). However, depth first searches can kind
of run away with you and can run practically forever.
The first piece of IDA* to deal with this bad aspect of depth first
searches is called Iterative Deepening depth first (the ID of IDA*).
You do a depth first search that is first bound at one move, then
bound at two moves, then bound at three moves, etc. The procedure
can seem sort of breadth first instead of depth search, but the
underlying search really is depth first. You just bound the search
and gradually increase the bound.
Iterative Deepening depth first is still too slow for the cube. Here
is where the A* bit comes in. Suppose you were going to do an
Iterative Deepening search one move deep, then two moves, then three
moves, etc., but suppose you also knew for sure by some magic that
the solution is at least twelve moves. Then, there is no point in
doing the one move or two move or eleven move search. You might as
well start by bounding you Iterative Deepening search at twelve, then
going on to thirteen, fourteen, etc.
What is this "magic" by which you might know that the solution is at
least twelve moves? Korf calls it a pattern data base. I just call
it a table. All it amounts to is that you create a table of
positions that are a subset of the entire cube -- say the corners
only. For each one of those positions, you calculate how many moves
there are in the minimal solution. Then you take your position and
look it up in the table. For example, for the 3x3x3 you ignore the
edges and look up the corners in the table. If it will require
twelve moves to solve the corners, based on your table, then it will
require at least twelve moves to solve the whole cube. So you start
your Iterative Deepening search at twelve moves because you know that
anything less is going to fail.
But then you go one step further and look in your table after every
move. For example, you determine that your initial position is at
least twelve moves from Start, so you commence an Iterative Deepening
search which is bounded at twelve moves. You make your first move.
If the corners are now eleven moves from Start, you let the search
continue. But if the corners are now twelve or thirteen moves from
Start, it will be impossible to find a twelve move solution so you
cut off that branch of the search and backtrack (you have already
made one move, so twelve or thirteen more yield a total of thirteen
or fourteen which is greater than your bound of twelve).
The best IDA* programs run on a fast processor with lots of memory to
hold a very large table, and a table which is very cleverly
constructed.
Finishing my note by talking about Cube Explorer 1.5 again, it is a
two phase algorithm which finds one position intermediate between the
current state and the goal state. It breaks the problem down into
two substeps because it takes so long to solve the problem all in one
go. But because there is an intermediate step, the solution is not
necessarily optimal. It uses IDA* to get from the initial position
to the intermediate position. After a suboptimal solution is found,
it looks for better solutions by making the intermediate position
further from the initial step. If it is ever able to solve a
position all in the first substep, then that solution is proven
optimal.
>
> I hope some of you can help with my problems. I also realise that some
> of my questions may have been answered in past discussions, but I
> wasn't willing to read through 20 years of archives to find out! If
> you can direct me to a previous relevant discussion, that would also
> be appreciated.
>
I agree that the archives are becoming unmanageable simply because
there are so many of them. I don't know what the solution is. I
would still urge you to read as much of the archives as possible.
For this particular subject, look for Kociemba, Cube Explorer, Korf,
and IDA*. Also, look up the discussion of mike reid's optimal
solver, and the very clever table he creates.
----------------------------------------
Jerry Bryan
jbryan@pstcc.cc.tn.us