From cube-lovers-errors@oolong.camellia.org Wed Jun 11 00:38:42 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 AAA12658; Wed, 11 Jun 1997 00:38:41 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@oolong.camellia.org
From: SCHMIDTG@iccgcc.cle.ab.com
Date: Wed, 11 Jun 1997 0:35:55 -0400 (EDT)
To: cube-lovers@ai.mit.edu
Message-Id: <970611003555.21417ec3@iccgcc.cle.ab.com>
Subject: Re: Detailed explanation of two phase algorithm
Herbert Kociemba wrote:
>SCHMIDTG@iccgcc.cle.ab.com wrote:
>>
>> And if we want to show that all depth one nodes will be pruned when
>> we are at some search depth d where 1 < d < h[0] we would need to show
>> that:
>>
>> 1.9 1 + h[1] > h[0]
>>
>
>Why do you say 1 < d < h[0] and not d = 1?
Oops, I think that should have been 'D' and not 'd'.
>[...slightly different restatement of earlier proof omitted...]
After examining this once again, I have now satisfied myself
that it is correct. It's just that for some reason, I seem to
find the result rather counter-intuitive. But that makes the
result all the more interesting.
So I think this may yet me another case where the phase1 algorithm
differs slightly from IDA*, but the difference is not significant
since, in this case, one is able to prove a special property of the
heuristic that demonstrates that the number of nodes explored by the
two algorithms is comparable. At this point, I think we can wind down
this thread, (I do hope others on this list have found it interesting)
and I will still continue to think of possible ideas for improving
the algorithm.
I do have one last question regarding the pruning tables. While
the three tables used in phase1 are clear, I do not recall reading
a description of the tables that are used in phase2.
I examined Dik Winter's program and he seems to have a few more
"maximum move" (i.e. "mm" tables) than I expected, namely:
phase1
------
mm_twists[]
mm_flips[]
mm_choices[]
/* and the following "mixed" tables */
mm_tf[][] /* twist & flip */
mm_tc[][] /* twist & choice */
mm_fc[][] /* flip & choice */
phase2
------
mm_eperms[] /* edge perms */
mm_cperms[] /* corner perms */
mm_sperms[] /* slice orderliness */
/* "mixed" tables follow */
mm_cs[][] /* corner perms & slice orderliness */
mm_es[][] /* edge perms and slice orderliness */
Are you using the same tables? Or are the "mixed" tables ones that Dik
added to the algorithm? It appears that Dik was able to use them because
he had a machine with more memory at his disposal than your 1MB Atari ST.
His program can be built with or without the "mixed" tables and is 11MB
with them. He also mentions that the small program finds a reasonable
solution in 30 minutes whereas the large program finds it in only a
few seconds.
I have also been studying his code to try to understand how he generates
these tables. He does not seem to be using breadth-first-search to
fill in these tables as Korf does.
I will be interested in looking at your new program when it becomes
available.
Thanks again for your patience.
Best regards,
-- Greg