Date: Mon, 04 May 92 03:43:47 +0200
From: Dik T. Winter <Dik.Winter@cwi.nl >
~~~ Subject: Are we approaching God's algorithm?

Because it might interest the readers and to be ahead of Peter Beck:
Saturday I received CFF (Cubism For Fun) # 28.
It has an interesting article by Herbert Kociemba from Darmstadt, who
describes his program to solve Rubik's Cube. He states that he has not
yet encountered a configuration that required more than 21 moves. A short
description follows:

Basicly the program consists of two stages, based on the groups:
G0: [U,D,R,L,F,B]
G1: [U,D,R^2,L^2,F^2,B^2]
G2: I
The stages are from G0 to G1 and next from G1 to G2. Note that the first
stage is the combination of the first two stages of Thistlethwaite, and
the last stages combine his last two stages.

His first stage can loosely be described as working in a three dimensional
coordinate system where the coordinates are resp. twist, flip and permutation.
He searches his way until the coordinate [0,0,0] is reached. Most important
here is that he is able to find multiple ways. The second stage is similar,
although he is not very clear here.

He uses lookup tables, but does not tell us how large his lookup tables
are. But his program runs on 1 MByte Atari ST. The heart is coded in
a few lines of 68k assembly, the remainder in GFA Basic. As far as I
know GFA Basic it can be interpreted, but also compiled. He does also
use tree pruning.

What he does is find successive solutions in stage 1 and fit solutions
from stage 2. Letting the system run longer generally finds shorter
solutions.

His claims are on average less than 14 turns in stage 1, on average less
than 10 turns in stage 2. But according to his article this is not completely
deterministic, so there is no proven upperbound. Perhaps a proof can be
found; I do not know. In practice he finds an upperbound of 21 moves, which
is indeed far better than other algorithms do obtain.

To take this in perspective here Thistlethwaites results from Singmaster's book:
Stage 1 2 3 4
Proven 7 13 15 17
Anticipated 7 12 14? 17
Best Possible 7 10? 13? 15?
(Are there configurations that require the maxima proven for Thistlethwaites
algorithm?)

Apparently the combination of stages largely reduces the number of turns
required.

In CFF 25 there was an article by Hans Kloosterman which did already improve
on the number of moves. His stages 1 and 2 are identical to Thistlethwaites,
he has a third stage that combines the 3rd and 4th stages of Thistlethwaite.
He reports a proven maximum for his three stages of 7, 10 and 25 moves, so
slightly better than Thistlethwaites conjectured best figures.

Kociemba's algorithm appears however to be a big leap forward, although there
are no proofs yet. One example:

In 1981 Christoph Bandelow wrote a book where he offered a prize for the
shortest sequence of moves that would flip every edge cuby and twists
every corner cuby. The deadline was September 1, 1982; at that time the
prize was offered for a 23 move manoeuvre. As Christoph writes:
All solutions presented after the main deadline and shorter than
all solutions submitted before were also proised a prize. Using
his very ingeneous new search program Herbert Kociemba, Darmstadt,
Germany now found:
DF^2U'(B^2R^2)^2LB'D'FD^2FB^2UF'LRU^2F'
for 20 moves.
Our first solution had 12 moves in stage 1 and 14 moves in stage 2.
In progress solutions 12+13, 12+12 and 12+11 were found. However,
as soon as we introduced manoeuvres of 13 moves in stage 1, we found
successively 9, 8 and at last 7 moves for stage 2. The program was
stopped after treating about 3000 solutions.
He further states that the first solution in general takes 95 seconds, but
successive solutions take much shorter, and in general he finds one of less
than 22 moves in a few hours on his 8 MHz Atari.

What is clear is that one does not need the minimal solution in one stage
to get the minimal overall total.

dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland
dik@cwi.nl