Case calculation

[Dennis]

Hi,
can anyone confirm the calculations I have done.

Cross:
For the cross there are 190080 cases, i.e
2^4*(12*11*10*9)

2x2x2 Block:
For the 2x2x2 block there are 253440 cases, i.e
3^1*8 * 2^3*(12*11*10)

X-Cross:
For the X-cross there are 72 990 720 cases, i.e
3^1*8 * 2^5*(12*11*10*9*8)

2x2x2 Block solved - Adding the two additional cross edges:
2^2*(9*8) = 288

Cross solved - Adding a slot, i.e a corner edge pair:
3^1*8 * 2^1*(8) = 384

 

[Johannes91]

All those seem correct to me.

 

[brunson]

Hi, Johannes, welcome back. We missed you. ;-)

 

[Dennis]

Ok, thanks. They were'nt that hard to calculate. But this may be a bit tricky;
Suppose I want to do an X-cross, but there is already a formed corner edge pair that I want to preserve. How many combinations is possible to form?

Moreover, if the corner edge pair is not formed but let's assume only one move away. How many more combinations would that yield?

 

[Johannes91]

Suppose I want to do an X-cross, but there is already a formed corner edge pair that I want to preserve. How many combinations is possible to form?

I think it's (24) * (2 ^ 5 * 11C5) * (3 ^ 1 * 7C1) = 894136320.

Moreover, if the corner edge pair is not formed but let's assume only one move away. How many more combinations would that yield?

Exactly one QTM move away: (24 * 2) * (2 ^ 5 * 11C5) * (3 ^ 1 * 7C1) = 1788272640.
Exactly one FTM move away: (24 * 3) * (2 ^ 5 * 11C5) * (3 ^ 1 * 7C1) = 2682408960.

Btw, what do you need these two number for? Doing "just" an X-cross efficiently is insanely difficult.

 

[cmhardw]

Doing "just" an X-cross efficiently is insanely difficult.

It's not too hard in practice though, to put those case counts in perspective to practice. I use dual solving, so I solve either white or yellow with equal weight, and I do Xcross that way about 30-50% of the time. Let's say 40%.

Let the probability that I solve Xcross on white only = x

My chance to solve Xcross with dual solving is roughly 1 - (1-x)^2

1 - (1-x)^2 = 0.4
x = .2254

So I would do Xcross about 1/5 the time on one color right now. That's using only the current rules roughly 12 seconds of inspection.

Not sure if that's useful, but a case count as high as X-cross translates to doing Xcross on that one color about 1/5 the time (for me).

Chris

 

[Johannes91]

My point was that finding even almost optimal X-cross solutions is so difficult that I don't see much point in thinking about preserving a ce-pair at the same time, which just adds to the complexity (and often is not such a good idea; it's a bit like heavy play in weiqi). Just as an example, the case for which you give a 10 move solution here can be done in 7 moves: R D2 B' D' L' F2 D2 (10q, 7f). (I actually sent you an email with this a while ago, as you requested on the page, but got no reply.) Anyone should have enough room for improvement in planning X-crosses that there's no need to consider more difficult first steps, IMHO.

 

[Swordsman Kirby]

it's a bit like heavy play in weiqi

I like the Chinese.

 

[Dennis]

Suppose I want to do an X-cross, but there is already a formed corner edge pair that I want to preserve. How many combinations is possible to form?

I think it's (24) * (2 ^ 5 * 11C5) * (3 ^ 1 * 7C1) = 894136320.

How can there be more combinations when a CE-pair is formed? And What do you mean with C, e.g 11C5 or 7C1?

Btw, what do you need these two number for? Doing "just" an X-cross efficiently is insanely difficult.

For now only for fun and to know how to calculate them, maybe in the future to write a solver/trainer for them. And, compare the move count btw cross/2x2x2 block and cross+1st f2l pair vs 2x2x2 block+2 edges and direct solve of the X-cross

 

[Johannes91]

How can there be more combinations when a CE-pair is formed?

The ce-pair can be in 24 different places, which makes the number bigger. Or maybe I misunderstood what you meant.

And What do you mean with C, e.g 11C5 or 7C1?

Oops, I meant to write P. For example, 11P5 = 11! / 6! = 11 * 10 * 9 * 8 * 7. Wikipedia link.

 

[rjohnson_8ball]

I think it's (24) * (2 ^ 5 * 11C5) * (3 ^ 1 * 7C1) = 894136320.

... What do you mean with C, e.g 11C5 or 7C1?

Edit: Oops, I just read he meant 11P5 not 11C5.
The total different combinations of selecting 5 items out of 11 can be described as "11 choose 5", which can be written in shorthand as "11C5". The math is "n Choose k" = n!/(k!(n-k)!). Example: if you have 10 people at a New Years Party and everyone clinks glasses with everyone else, then there would be 10 choose 2 = 45 clinks.

 

[Dennis]

Have anyone done a move count for
1: The 2x2x2 block
2: The Cross + first CE-pair in place
3. The 2x2x2 block + the two remaining F2L edges
4. Direct X-cross

For the cross I many people have done it. Johannes have you done it for the 2x2x2 block and the others perhaps. Reason is that I started experimenting with case no3 and it feels kind of good (although I can't do it fast enough yet)

 

[Johannes91]

Have anyone done a move count for
1: The 2x2x2 block

Here's one link: http://cubezzz.homelinux.org/drupal/?q=node/view/116.

2: The Cross + first CE-pair in place
3. The 2x2x2 block + the two remaining F2L edges
4. Direct X-cross

I have #4 running at the moment, and if that finishes without problems, it's trivial to get the other two, too.

 

[cuBerBruce]

Have anyone done a move count for
1: The 2x2x2 block

Here's one link: http://cubezzz.homelinux.org/drupal/?q=node/view/116.

That's a link to one of my posts.
I note that Morley Davidson & Joe Miller had earlier posted the 2x2x2 block analysis for FTM in the Yahoo Petrusmethod group (registering is required to read the archives). Actually it was from Johannes that I found out about the post by Davidson & Miller.

2x2x2 Block solved - Adding the two additional cross edges:
2^2*(9*8) = 288

Cross solved - Adding a slot, i.e a corner edge pair:
3^1*8 * 2^1*(8) = 384

I note that while these are a small number of cases, computing optimal solutions for these cases involves considering positions where the already solved pieces are moved out of place temporarily. So the "search space" is much larger. Probably one would use the same "search space" as for the direct X-cross (72990720 positions).

In his "Hume" thesis, Stefan Pochmann got a statistical estimate of 6.09 average number of moves for solving a fixed CE pair after the cross, or 5.03 for solving the best CE pair after the cross.

 

[Johannes91]

Creating pruning table: XCross
Depth: 0, Positions found: 1
Depth: 1, Positions found: 16
Depth: 2, Positions found: 188
Depth: 3, Positions found: 2138
Depth: 4, Positions found: 23673
Depth: 5, Positions found: 244041
Depth: 6, Positions found: 2233632
Depth: 7, Positions found: 15665622
Depth: 8, Positions found: 56629514
Depth: 9, Positions found: 72954698
Depth: 10, Positions found: 72990720
Done.

2x2x2 Block solved - Adding the two additional cross edges:
2^2*(9*8) = 288

Cross solved - Adding a slot, i.e a corner edge pair:
3^1*8 * 2^1*(8) = 384

I note that while these are a small number of cases, computing optimal solutions for these cases involves considering positions where the already solved pieces are moved out of place temporarily. So the "search space" is much larger. Probably one would use the same "search space" as for the direct X-cross (72990720 positions).

It would also be possible, and perhaps more efficient, to just solve the cases one by one with an optimal solver (ACube, for example). But since I have the table for direct X-cross now I'll just loop through it and post the numbers later today, unless someone beats me to it.

 

[Dennis]

Creating pruning table: XCross
Depth: 0, Positions found: 1
Depth: 1, Positions found: 16
Depth: 2, Positions found: 188
Depth: 3, Positions found: 2138
Depth: 4, Positions found: 23673
Depth: 5, Positions found: 244041
Depth: 6, Positions found: 2233632
Depth: 7, Positions found: 15665622
Depth: 8, Positions found: 56629514
Depth: 9, Positions found: 72954698
Depth: 10, Positions found: 72990720
Done.

Wow, thats great. Only 8-9 moves for the X-cross that was a little less than expected. Don't worry about me beating you for the other numbers, I have'nt even started any programming yet.

This might seem a little bit silly but, would one gain in switching the order of 2x2x2 block+last 2 cross edges to the opposite, more or less positions? Or Cross+first CE-pair to first CE-pair then cross?

 

[Johannes91]

The lists are pairs of ([i]n[/i], positions at depth [i]n[/i]).

XCross (avg 7.9757): [(0,1),(1,15),(2,172),(3,1950),(4,21535),(5,220368),(6,1989591),(7,13431990),(8,40963892),(9,16325184),(10,36022)]
XCross with 2x2x2 done (avg 4.0104): [(0,1),(1,6),(2,20),(3,60),(4,101),(5,76),(6,23),(7,1)]
XCross with cross done (avg 6.0833): [(0,1),(3,6),(4,15),(5,69),(6,162),(7,107),(8,24)]

6.08 ≈ 6.09

This might seem a little bit silly but, would one gain in switching the order of 2x2x2 block+last 2 cross edges to the opposite, more or less positions? Or Cross+first CE-pair to first CE-pair then cross?

As Bruce pointed out, the search space for the second step of both of these variations is just as big as for direct X-cross, so even if there are less cases, I don't think it would save any memory. And I can't think of anything else this switch could possibly gain.

 

[Dennis]

Wow, that confirms my theory.
Do you state FTM or QTM?

Direct X-cross:
average: 8 moves
worst: 10 moves
Best but 'insanely hard' to do

Cross+First CE-pair:
average:. 5.81+6.08 = 11.89 ~ 12 moves
worst: 8+8 = 16 moves

2x2x2 block+Last 2 cross edges
average: 6.03+4.01 =10.04 ~ 10 moves
worst: 8+7 = 15 moves
Best for speedcubing the X-cross

Data taken from:
http://cubezzz.homelinux.org/drupal/?q=node/view/116
http://www.cubezone.be/crossstudy.html

 

[Johannes91]

Do you state FTM or QTM?

FTM.