From dik@cwi.nl Sun May 17 18:49:53 1992
Return-Path:
Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) id AA17456; Sun, 17 May 92 18:49:53 EDT
Received: from boring.cwi.nl by charon.cwi.nl with SMTP
id AA29764 (5.65b/2.10/CWI-Amsterdam); Mon, 18 May 1992 00:49:49 +0200
Received: by boring.cwi.nl
id AA22984 (5.65b/2.10/CWI-Amsterdam); Mon, 18 May 1992 00:49:48 +0200
Date: Mon, 18 May 1992 00:49:48 +0200
From: Dik.Winter@cwi.nl
Message-Id: <9205172249.AA22984.dik@boring.cwi.nl>
To: cube-lovers@life.ai.mit.edu
Subject: Kociemba's algorithm
I have made my program a bit faster. While previously the best I found for
superflip was a 21 move solution (even after 10 hours computation time,
actually the solution was found after about 30 minutes), I have now a 20
move solution, found after only 15 minutes:
Superflip:
(13+7=20): F B U^2 R F^2 R^2 B^2 U' D F U^2 R' L' U B^2 D R^2 U B^2 U
Some more information. First a short recap. Phase1 brings the cube in
the group generated by [F^2,R^2,B^2,L^2,U,D], phase2 brings him back
to start. Phase 1 searches in the space generated by the three (orthogonal)
coordinates:
Twist (2187 entries), flip (2048 entries) and slice-edge-cube placing (495
entries).
Phase 2 searches in the space generated by the three (non-orthogonal)
coordinates:
Permutations of corner cubes (40320 entries), permutations of edge cubes
not in the middle slice (40320 entries) and permutations of the middle
slice edge cubes (24 entries).
While Kociemba originally did tree pruning based on the minimal number of
moves needed along single coordinates, I now use pairs of coordinates
(except that in phase 2 the 40320*40320 pair is not used of course).
This is part of the speed-up. (Another part is that I do now disallow
successive moves of a single face, three or more consecutive moves of
opposite faces, and a move of an opposite face if the current face moved
is B, L or D.)
Program details: the program starts with phase1 allowing for succesively
1, 2 etc. until a maximal number of moves. As soon as phase1 hits a
solution phase2 is called, again with a maximum number of moves starting
at 1. This means that if the program runs long enough it will ultimately
find the shortest solutions (phase 1 might just solve it!). But that wil
take a long time (of course). For the superflip, the program has now
checked all phase1 solutions of upto 12 moves and is busy with 13. It
found 792256 solutions of 12 moves (and that in less than 10 minutes)!
Some additional data about minimal paths along coordinates:
Phase 1:
twist: 6
flip: 7
choice: 5
twist+flip: 9
twist+choice: 9
flip+choice: 9
Phase 2:
corners: 13
edges: 8
slice edges: 4
corners+slice: 14
edges+slice: 12
Based on this I expect a maximal distance in phase 1 of about 10/11, and
in phase 2 of about 16/17.
dik
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland
dik@cwi.nl