Home »

2 questions

Submitted by mdlazreg on Thu, 02/21/2008 - 02:02.
Hi,

I am asking for help to understand the second phase of the 2-phases algorithm. I do understand the first phase.

My question is once we bring the scrambled cube to a position in the G1 = subgroup, how is this position taken to the Identity?

Kociemba says the following in his website:

In phase 2 the algorithm restores the cube in the subgroup G1, using only moves of this subgroup. It restores the permutation of the 8 corners, the permutation of the 8 edges of the U-face and D-face and the permutation of the 4 UD-slice edges. The heuristic function h2(a,b,c) only estimates the number of moves that are necessary to reach the goal state, because there are too many different elements in G1.

Unfortunately I am not able to understand what he means and what is really being done in the second phase. Can someone please try to explain to me how the optimal number of moves that takes the position in G1 to Identity is found?

The second question is regarding Tom's optimal solver, I could not figure out how to run it... What input does it expect? Can someone please give an example of a full command line?

Many thanks
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

some tips on using this forum

Submitted by Bruce Norskog on Fri, 02/22/2008 - 00:21.

Be aware that the input text on this forum is treated as HTML, not regular text. Your use of <U ... gets interpreted as an HTML tag to underline text instead of the text itself. Netscape 7 underlines the entire rest of the page, not just your own message. The correct way to insert a less-than symbol is to use: &lt;. Use the preview feature before submitting. Unlike some other forums, the preview feature on this forum is actually useful.

Another thing I've seen recently is people writing internet urls, but not using <a ...> HTML syntax so that an actual hyperlink is created. This forum does not try to automatically generate hyperlinks - you have to explicitly use the <a ...> HTML tag to create a hyperlink.

» login or register to post comments

In answer to your first quest

Submitted by rokicki on Thu, 02/21/2008 - 15:12.
In answer to your first question: the heuristic function h2(a,b,c) gives an lower bound on the number of moves required. Normally phase 2 simply does a normal recursive search based on the number of moves we want to allow at this point and this function: 
findsol(int movesleft, coords pos) {
   if (pos == identity)
      return solved ;
   if (movesleft < h2(pos))
      return no_solution_this_branch ;
   for (move m in moves) {
      int test = findsol(movesleft-1, pos.move(m)) ;
      if (test == solved)
         return solved ;
   }
   return no_solution_this_branch ;
}
Does that make sense? To run my optimal solver, the input is a move sequence (generator) to be optimized. You can give the move sequence on the command line, or you can just give "-" on the command line which means read move sequences from stdin, one per line: 
rubsolv164 U1R2F3U1
or 
rubsolv164 -
U2R3F1
F1U3D1
...
Let me know if that's not clear.
» login or register to post comments

Thanks Tom. I do understa

Submitted by mdlazreg on Fri, 03/07/2008 - 20:04.
Thanks Tom.

I do understand now phase 2. I wonder why phase 2 is not applied to the whole group? it will take too much time?
» login or register to post comments

one phase vs. two phase

Submitted by Bruce Norskog on Fri, 03/07/2008 - 23:54.
You guessed it. Optimal solvers generally do this same type of algorithm as a single phase. You probably are aware how slow they are compared to the two-phase solver, even though they may use an even higher quality pruning table. The execution time increases more or less exponentially with search depth. So two searches of about half the depth per search is a lot faster than than one search of the full depth.
» login or register to post comments