From cube-lovers-errors@mc.lcs.mit.edu Mon Sep 29 13:08:14 1997
Return-Path:
Received: from sun30.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.1/mc) with SMTP
id NAA14569; Mon, 29 Sep 1997 13:08:14 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From reid@math.brown.edu Sun Sep 28 14:45:54 1997
Message-Id: <199709281845.OAA08068@life.ai.mit.edu>
Date: Sun, 28 Sep 1997 14:46:39 -0400
From: michael reid
To: cube-lovers@ai.mit.edu
Subject: idea for smaller optimal solver
a number of people have told me that they don't have 80Mb of RAM on their
computers, so that my optimal solver won't work on their machine. here's
an idea for an optimal solver that uses much less memory; it should fit
within 16Mb, or 20Mb at the most. of course, it's a space/time tradeoff,
but perhaps will still be fairly good.
in my current program, i use distances to the subgroup
H = __
as my "heuristic" function. there is another subgroup, H' , which
contains H as a subgroup of index 8. H' is the subgroup of all
elements of H composed with all (valid) flips of U-D slice edges.
another way to describe H' is the subgroup of all elements where
the U face has only the colors U and D, and the same for the D face.
from this latter description, we see that if H1' , H2' and H3'
are the three orientations of this subgroup, then their intersection
is the subgroup of elements that "look like" they're in the square
group. this is the same target subgroup that my current program has.
the subgroup H' also has 16 symmetries. using this to reduce the
size of the pattern database, and storing each entry with 4 bits,
it should take about 8.5Mb. my current program also has about 8.5Mb
of transformation tables (but 3Mb of these are not used while searching).
the transformation tables will probably be slightly smaller (certainly
no larger), so it seems plausible that this could run with 16Mb of RAM.
what about running time? in his paper, rich korf hypothesizes that
the number of nodes generated should be roughly proportional to the
inverse of the size of the pattern databases. this suggests that
using the smaller tables above would result in about 8 times as many
nodes as my current program. this isn't bad, especially given that
the branching factor (6 + 3 * sqrt(6) = 13.348469 for face turns,
9.3736596 for quarter turns) is larger than this. so this approach
would be within 1 turn of my current program.
i don't foresee having enough spare time anytime soon to program this,
so i'll just post it here and maybe someone who is interested will
program this.
mike
__