4x4x4 FMC (computer and human) round 2

[unsolved]

Well, I gave this some thought and I've decided that unsolved may use his trimming technique if he does what bobthegiraffemonkey suggests: find a solution using some other method, invert it to use as a scramble, and use his trimming technique on that. That's definitely fair game. But not on the actual scramble itself, that just seems wrong to me.

OK, but to me, this seems like it is just a different version of the same thing the rule was designed to prevent. A subset of the original scramble is being used to generate something other than the exact scramble subset, whose use is functionally the same.

Anyway, my gut feeling is that it can only shorten sequences by some fraction, say 10% (which is a total guess not based on anything) and not to near optimal as unsolved has claimed. So a 50 move sequence might get shortened to 45, but a 100 move sequence might only get shortened to 90 moves. But it doesn't seem like that 100 move sequence could get shortened down to 40 moves. But that is just my gut feeling.

My gut feeling is almost the exact opposite. For very lengthy scrambles, anything longer than the unknown God's Number for the 4x4x4 is not adding to the length of the solve. It may be hovering at or near the same solution length, even "accidentally" getting closer to the solved state at times, but overall it increases the chance that some fixed-depth search will solve the entire portion of the scramble being examined. It's like giving more pitches to a home run hitter; you're increasing the odds of of them will be knocked out of the ballpark.

So time to shift gears and go hunt for the giraffe.

If you're going for optimal, you might have to rethink this. Take the following scramble:
(R U R' U)5

Your program should be able to recognize that the cube is in a solved state even though 4 of the centers are not where they started. Otherwise it will miss the optimal solution (which in this case is 0 moves).

This is almost too ridiculous to even offer a comment. The first thing I generate is every non-supercube arrangement through 5 turns. Before starting any search, I probe the hashtable to see if a search is even necessary.

I can see how it is tempting to try and offer "improvements" to something you know nothing about, as you like to say so often about me before moderators delete your comments.

 

[adimare]

This is almost too ridiculous to even offer a comment. The first thing I generate is every non-supercube arrangement through 5 turns. Before starting any search, I probe the hashtable to see if a search is even necessary.

I can see how it is tempting to try and offer "improvements" to something you know nothing about, as you like to say so often about me before moderators delete your comments.

You're right in stating that I know little about your program. Why would I? Why would I assume you look into non supercube arrangements if the information I have is you literally saying "my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved"?

 

[qqwref]

OK, but to me, this seems like it is just a different version of the same thing the rule was designed to prevent. A subset of the original scramble is being used to generate something other than the exact scramble subset, whose use is functionally the same.

Just to clarify, since this is a pretty subtle distinction: the difference is in the knowledge you(r solver) are allowed to have. The goal is to be handled a scrambled state and solve it, without knowing the moves that got the cube to that state. When you improve the scrambling algorithm to get a solution, you are making use of knowledge of the scrambling algorithm, which is knowledge you are not supposed to have. However, when you generate a new solution and then improve it, you are not making use of knowledge of anything other than the scrambled cube you were given, so that is OK. The problem with your approach is not your method of improving a solution (which is fine), but with using the scrambling algorithm (which you should not know) as a starting point.

 

[unsolved]

Well, I gave this some thought and I've decided that unsolved may use his trimming technique if he does what bobthegiraffemonkey suggests: find a solution using some other method, invert it to use as a scramble, and use his trimming technique on that. That's definitely fair game. But not on the actual scramble itself, that just seems wrong to me.

Maybe for future computer contests we should be required to "parse the stickers" by either face colors or face names.

U=BRFB/BRFF/BLRR/RFDL would be the top side for the first scramble where B = Back, R = Right, F = Front, etc. I know we chatted about something like this before, but I forget where we left off.

 

[ch_ts]

That's a possibility... but that would only be useful for the computer fmc, and not human fmc where a scramble is easier to apply to a cube.

 

[unsolved]

That's a possibility... but that would only be useful for the computer fmc, and not human fmc where a scramble is easier to apply to a cube.

Yep, that's what I implied. I wouldn't know how to even attempt such a thing as a human

How many moves has your optimal or near to optimal solution for (U R F D L B 2U 2R 2F 2D 2L 2B)^6 ?

So is there any supercube software out there that might be able to help me track down my supercube bug? It looks like one of the solution segments to the 36-mover from the first scramble does not recombine from the start to solve the whole cube. It is an insidious bug that does not always recreate itself after seemingly undertaking deterministic quality controls.

This is what my supercube looks like at the start:

Spoiler

...and this is what it looks like after Herbert's 72-move scramble test.

Spoiler

If this is confirmed to be a correct representation, I can go about making sure the other 23 rotated states of the supercube code are working correctly, then relaunch the line-crawl algorithm and see what happens. Although this test took a lot of time, it will be worth it if it tracks down this bug, and the technique turns out to be useful.

EDIT: I think I have the quintessential supercube test position:


2R2 F2 U2 2R2 U2 F2 U2 2R U2 2R2 U2 2R2 U2 2R U2 2R2 U2

This is not supercube solved, but it is non-supercube solved.

There are 16 supercube solutions, one of which is:

L' F2 D2 B2 R' L U2 B2 D2 R

If this is correct, I think it is safe to say I can resume the hunt.

 

[Herbert Kociemba]

...and this is what it looks like after Herbert's 72-move scramble test.

Spoiler

http://s28.postimg.org/mln0ngejh/4x4x4_supercube_test_02.png

If this is confirmed to be a correct representation, I can go about making sure the other 23 rotated states of the supercube code are working correctly, then relaunch the line-crawl algorithm and see what happens. Although this test took a lot of time, it will be worth it if it tracks down this bug, and the technique turns out to be useful.

Yes it is ok as it can be seen easyly here
https://alg.cubing.net/?alg=_(U_R_F_D_L_B_2U_2R_2F_2D_2L_2B)6 &puzzle=4x4x4
Then let's see what happens.

 

[unsolved]

Yes it is ok as it can be seen easyly here
https://alg.cubing.net/?alg=_(U_R_F_D_L_B_2U_2R_2F_2D_2L_2B)6 &puzzle=4x4x4
Then let's see what happens.

Yes but that does not show the supercube centers. I'm pretty sure I have the supercube stuff working right now, but I await independent confirmation.

 

[Herbert Kociemba]

I can confirm that your supercube centers are in the right positions for this scramble.

 

[unsolved]

Search for "Analysis of 3x3x3 corners only" to find that the number you are seeking is 14 (11 is when we ignore all of the puzzle except for corners, meaning that we are able to destroy other piece types in order to solve the corners themselves optimally).

Oh, right. The corners-only pruning table has no concern for other piece types.

Since you not only have to solve the corners but also have to keep the edges, the shortest solution is longer. The shortes solution using only outer face turns is 18 moves: U (B' U2 D' F2)^4 U' (18f*).

Thanks.

=============================================================

In other news, now that the 3-stage approach I have seems to be working, I have a few questions.

1. Is there a "God's Number" that is known once "the cage" has been solved? (all corners + all edges correct).
2. Is the estimate for the number of moves required to solve all centers first smaller than the number to solve all of the centers last?
3. I am hunting for the most difficult cube position where 4 sides are solved in entirety plus the cage is solved. One such case is shown below:

https://alg.cubing.net/?puzzle=4x4x...=U-_2R_2D2_U_2L-_U2_2L_2D2_U_2R-_U-_2L-_U2_2L

So far, I have 13 moves as being the greatest number of moves required to solve centers exchanged between two adjacent faces. Are there any known positions with longer solutions?

 

[Herbert Kociemba]

In general I would say that it is not optimal to define intermediate states of a multi-stage solver which fix certain pieces in their final position. This is more or less a "human" approach. Superior to this seems an approach where the intermediate states are defined by reducing the allowed moves from step to step, for example use only outer face turns in the last step.
Concenrning the centers I have the result that in worst case it will take 11 moves (SSTM) to restore the centers in such a way that the centers of opposite faces are at least on the same axis again (but still the two colors can be mixed on the two opposite faces).
But this is with totally ignoring the edges and corners. If your want to keep the corners and edges of your cage and also want to completely fix the centers it will take considerably more moves.

 

[unsolved]

In general I would say that it is not optimal to define intermediate states of a multi-stage solver which fix certain pieces in their final position. This is more or less a "human" approach. Superior to this seems an approach where the intermediate states are defined by reducing the allowed moves from step to step, for example use only outer face turns in the last step.

I am taking the human approach because I simply don't know how to do it any other way

I am doing something a little different in my 3 stages.

Stage 1 = all 24 edges (very, very long time to resolve).
Stage 2 = complete "cage" or "ringed cube" (only requires face turns after stage 1, so this is usually the fastest stage).
Stage 3 = solve the cube (does not require calling the move generator at all and is very quick)

During stage 3, I convert the ringed cube hash table into a linear array of "solving algs." I have every move sequence that will create a caged cube in 4- through 10-turns. The program simply goes through this list (at a rate of about 27,000,000 algs/second) and applies the moves. It tests to see if the cube is solved. If the cage is not 10 turns (or less) from the solved state, the cube won't be solved. If this is the case, the program applies the 4- and 7-turn solutions in cascade, making an ad hoc 11-turn alg out of the combined two. Since all caged cube algorithms do not disturb the cage (the set is "closed") I can apply them blindly and just test for a final result.

I apply all of the solutions in pairs. (4x7) and (7x4), (5x6) and (6x5) give me all of the ad hoc 11-turn solutions.
(4x8),(8x4),(5x7),(7x5), and (6x6) give me all of the ad hoc 12-turn solutions.
I repeat this process and also sample the solved cubie population along the way. If I don't solve the cube after running through the entire list up to (10x10), I apply the solution that gives me the highest solved cubie population (usually 92+ out of a possible 96 at this point) and then just brute force solve the rest.

Stage 2 is in the neighborhood of 9- and 10-turns on average (from the test positions I have given the program).
Stage 3 is sometimes 18-20 moves because this approach is clearly not optimal (but it is fast given the depth).

But there's no getting around the fact that stage one can take up to 2 weeks until I figure out a better way.

But this is with totally ignoring the edges and corners. If your want to keep the corners and edges of your cage and also want to completely fix the centers it will take considerably more moves.

I am still trying to discover this upper bound.

 

[rokicki]

Will there be intermediate results posted at any time? It might be interesting to see how people are doing.

Unless of course no one has submitted solutions yet.

 

[unsolved]

Will there be intermediate results posted at any time? It might be interesting to see how people are doing.

Unless of course no one has submitted solutions yet.

I can demonstrate something that is humorous and interesting, without spoiling the contest. Recall Herbert asked for a solution to his 72-move scramble while my program was still using a (flawed) supercube approach before I switched on-the-fly to a 3-stage solver where all of the edges were solved first. Well I noticed the alg was doing fine, conquering most of the edges after 18 plies of search.

https://alg.cubing.net/?alg=F2_2R2_...4x4x4&setup=_(U_R_F_D_L_B_2U_2R_2F_2D_2L_2B)6

But, you will notice, with a few edges remaining to be solved, the colors are incorrect for the bottom and left faces

So my "wonderful" fastest-edge-solving portion of the stage solver went awry somewhere.

 

[ch_ts]

Yes, I can post some intermediate results when I get more entries. So far, only computer entries from you and qq280833822. No human entries yet.

 

[ch_ts]

Not many people have entered, but the solutions received were very good solutions indeed!

Computer Leaderboard: (as of June 13)
1. rokicki
2. qq280833822

rokicki has a slight lead. No human entries.

 

[cuBerBruce]

I am off to a slow start. I have worked out "human" solutions for 2 of the 5 so far, but even these I would like to improve on. I should at least get a set of human solutions submitted by the end of the month.

 

[unsolved]

Not many people have entered, but the solutions received were very good solutions indeed!

I was banking heavily on the "line crawl" technique, which was functionally illegal if not completely illegal, and it did not pan out as expected. Still, some good came out of it. I have a 4x4x4 supercube solving mode now that I can eventually integrate into the interface.

That left me in the awkward position of re-investigating stage solving code I had written before (which was time consuming and not really worth mentioning the long solves it produced) or coming up with a new one altogether. It is strange how sometimes it is better to start from scratch rather than build on code that is even slightly unfamiliar. So that's what I did.

My stage solver hunts for all edges to be in their correct location as expediently as possible, with some "time cutoff" parameters that will "settle" for correct facelet colors if the edge can't be "totally correct." Next it solves the corners, and finally the centers.

I now have a new edge pruning mechanism that requires 0 RAM and no pre-loading of table data. It needs to be refined, and I spent too much time making sure this was "admissible" as a legitimate implementation. I have decided it might be worth trying to perfect this at the expense of not finishing on time. I might have some interesting solutions to these after the contest is over.

I was surprised to see that corners take so long to solve after the edges are in place. I incorrectly assumed 11 turns was the max distance based on the corner pruning data. More than one corner solution required over 15 moves for stage 2 alone.

Stage 3 is always fun to watch, even though it is not optimal. The program flies through its list of cage-solving algs, and you can see the line of play extend from 10-11-12-13-14-15-16 moves rather quickly.

I am loading up the machine before I take a short vacation. In case I don't get back in time and you might be curious about the edge solving solution, here is one of them.

Spoiler

https://alg.cubing.net/?puzzle=4x4x...R2_2U_2B-_D2_R_2U-_2B-_R2_B_D2_F_2L2_F-_D2_B-

 

[Herbert Kociemba]

Stage 3 is always fun to watch, even though it is not optimal. The program flies through its list of cage-solving algs, and you can see the line of play extend from 10-11-12-13-14-15-16 moves rather quickly.

How many moves does it take on average to solve stage 3 if the centers are randomly scrambled?

The discussions in this thread motivated me to give a three stage solver a try too. It will be based on the concept of restricting the allowed moves from stage to stage. In the moment I am working on stage 1 and definitely it will take several more weeks before I hope to be able to have some results. Definitely not before the end of the contest.

 

[unsolved]

How many moves does it take on average to solve stage 3 if the centers are randomly scrambled?

For functionally random center scrambles, my data sample is small: 4.

It took 14, 17, 20, and 21 moves.

The 21-move solution was composed of 9-7-5 turn "algs" applied in cascade.