From cube-lovers-errors@oolong.camellia.org Mon Jun 2 17:32:10 1997
Return-Path: cube-lovers-errors@oolong.camellia.org
Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id RAA04147; Mon, 2 Jun 1997 17:32:10 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
Message-ID: <3393350F.6541@hrz1.hrz.th-darmstadt.de>
Date: Mon, 02 Jun 1997 23:03:11 +0200
From: Herbert Kociemba
X-Mailer: Mozilla 3.0 (Win95; I)
MIME-Version: 1.0
To: cube-lovers@ai.mit.edu
CC: Richard E Korf
Subject: Detailed explanation of two phase algorithm
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Reading the many contributions in the mailing list in the last days, I
state, that the insight im my two phase algorithm solving the cube
ranges from misunderstood to partly understood, so I will add some more
really detailed explanation here.
The memory requirements for the search algorithm are of the order
O(d*log b), where b is the branching factor and d is the solution depth,
so it definitely is not breadth-first search with O(b^d) nor is it
bidirectional search with O(b^d/2).
The "log b" is no misprint, it is due to the special situation when
dealing rotational puzzles.
The orientations of the corners, the edges and the position of the four
middleslice edges are mapped to {0,1,...,3^7-1},{0,1,...,2^11-1} and
{0,1,...,12*11*10*9/4! -1} by appropriate functions in phase1.
Every state of the cube is represented by a triple (x,y,z) in stage1,
and a face turn maps this triple to another triple (x',y',z').
Let us denote (x0,y0,z0) for the triple, when arriving in the subgroup
__. All elements of this subgroup have this same triple
(x0,y0,z0), because neither edge nor corner orientations can be changed
here and the four middleslice edges stay in their position too (only
their permutation changes, but the mapping function for z ignores the
permutation).
Before applying the search algorithm we use the inverses of the mapping
functions to create lookup-tables for each coordinate, so that a face
turn can be performed with three table lookups, which is very effective.
The three heuristic functions in phase1 also are table-based. From a
pair (x,y) we compute the index i=3^7*y + x which will be a unique
number out of {0,1,...,3^7*2^11-1}. At tableposition i we store the
minimum number of moves we need to get from (x,y) to (x0,y0), ignoring
the z coordinate. Of course this minimum number never is greater than
the number of moves to go from (x,y,z) to (x0,y0,z0), so it is accurate
for the use in an IDA* type search. The other two tables for (x,z) and
(y,z) are constructed in a corresponding way.
Because these minimum-number never exceed 9 in phase 1, 4 bits will do
per tableentry.
Now I *try* to describe the search algorithm for phase1. The
implementation in my program has slight modifications, but they would
not improve the readability of the description. For example I omit the
part how to reduce the branching factor forbidding the move sequences
RR2 or UDU etc.
During the search algorithm, we only store the current state (x,y,z).
Instead of storing the node path we store the applied move sequence,
which is equivalent but more adopted for our problem. We use 1 Byte for
every move. Let denote the list for the move sequence with A, A[i] then
is the i's element of the list. The sequence is stored in reverse order,
A[0] holds the last move of the solving sequence when a solution is
found. The iteration depth is denoted with L1.
1. On initialization set L1=1, i=0, A[0]=0.
2. Apply a face turn to (x,y,z) using the generated lookup tables, the
face turn according to the number A[i]: If A[i]==0, apply U. When we
write 0:U for that the following table shows what faceturn(s) to apply:
O:U, 1:U, 2:U, 3:UR, 4:R, 5:R, 6:RF, 7:F, 8:F, 9:FD, 10:D, 11:D, 12:DL,
13:L, 14:L, 15:LB, 16:B, 17:B, 18:B.
In the case A[i]=18 all branches had been handled and this last B move
resets the cube to the state of the node where it came from at the
current depth -1. We reset A[i] to 0, increment i and goto 3. then.
If A[i]<18 increment A[i].Then compute the indices for the heuristic
tables using the triple (x,y,z) and check, if the current depth (which
is L1-i) plus the tablevalue v (which is a heuristic for the minimum
length to solve the cube from this state) exceeds L1, which is
equivalent to v>i. If that happens for any of the three tables, we prune
that branch and goto 2., to generate the next node of the same depth.
If v<=i, we first check, if i=0. In this case the current depth is the
iteration depth L1 and we have found a solution for phase1, because v=0
only can happen for all three heuristic tables, when we are in state
(x0,y0,z0). Goto phase2 then.
But if i>0, we have to generate the node at the current length + 1. We
decrement i and goto 2.
3. If i==L1 now, we have searched the complete tree with lenght L1. In
this case we increment L1, set A[i]=0 and goto 2. to build again our
first depth-one node.
If i__