README FILE for optimizer 0.9

The optimizer is an addon to my Cube Explorer program. Its input is the
output of Cube Explorer and it gives the shortest maneuvers in face turn
metric equivalent to those in the the input file. 

The usage is        optimize [-n] inputFileName outputFileName

If the optional parameter -n is omitted, only one optimal maneuver is
computed for each maneuver in the input file. With n=1 all shortest maneuvers
are computed, with n=2 all shortest maneuvers plus all solutions with optimal
lenght+1 are computed....


1. System requirements

You need about 90Mb RAM and 74 MB of disk space to run the program.
The disk space is necesarry because all tables are computed only the first time
the program is run (which takes about 20 minutes on a P350). The advantage is
 that the program starts within seconds whenever it is run again.


2. Performance

On a P350 the optimizer generates about 1,110,000 nodes (or cubes) per second.
 The time critical code was improved using some inline assembly instructions
wich gave a 40% higher performance in comparison to the non-optimized code.
In a test with 10 random cube maneuvers, the time to optimize all of them took
about 35 hours (6 opimized maneuvers had lenght 18, 4 had length 17). Though it
is known that there are some maneuvers with lenght 20 (which would take a long
time to compute), in most situations you will have the solution within a few hours.


3. The algorithm

Read the Cube Explorer helpfile to get an idea of my two phase algorithm
which gives very good suboptimal solutions within a short time and with
moderate system requirements.
The complete phase 1 can be packed in one big pruning table of about 69Mb
when symmetry reductions are used. This table then can be used simultanously
in three orientations of the cube. I took this symmetry reduction idea from Mike
Reid, who already used it in 1997 in his optimal solver program. No phase 2 search
 is done at all, if the result of phase 1 is not the identity, the phase 1 solution is
discarded.
I added some idea for an improved node search algorithm, which reduces the
number of nodes to be generated by about 20%.


4. Feedback

Send any questions, suggestions and experiences with the program to
kociemba@hrz1.hrz.tu-darmstadt.de or to the the cube-lovers mailing list in the
case of general interest.

The Cube Explorer homepage with the latest version of the optimizer program is at
 
http://home.t-online.de/home/kociemba/cube.htm

May 1, 1999

Herbert Kociemba
Darmstadt, Germany
