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