• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

4x4x4 FMC (computer and human)

qq280833822

Member
Joined
May 28, 2008
Messages
206
Location
China
WCA
2008CHEN27
Oh it's a two-phase reduction solver, the only difference to the three-phase solver used in WCA scrambler is that I merged phase1 and phase2. If we treat the 3x3x3 part as a single phase, it should be a three-phase solver.
As the reduction is finished in two phases, we can try to find or estimate the near-optimal reduction solutions by trying sub-optimal phase1 solutions as kociemba did in his two-phase algorithm.
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
I just thought I would mention a kind of interesting situation on one of my "computer" solves.

It was for scramble #5.

Scramble:
F U F U F2 R2 D' R2 B2 D B2 D2 B2 R2 U' F R F' B' D' R2 D' L'
Uw2 F' Uw2 U2 Rw2 Fw2 B D F' B D' L2 B2 Rw' Fw2 R' U B U' Rw' Uw R' Fw B U L D R

Reduction:
U' L2 2F' 2U' L2 F 2L' 2F
D B Uw2 L U' Lw2 U Lw2 F2 U' Uw2 Fw2 Lw2
Fw R' F R Fw2 B' U B U' Fw y2

The reduction created a logical 3x3x3 state with a prebuilt 2x2x1 block. It also had a prebuilt C-E pair that would extend
that 2x2x1 block to a 3x2x1 block. In fact, applying:

D' L' F' L2 D2

builds a 2x2x3 block (with puzzle being viewed as a 3x3x3) with only 5 moves!

U' L2 2F' 2U' L2 F 2L' 2F
D B Uw2 L U' Lw2 U Lw2 F2 U' Uw2 Fw2 Lw2
Fw R' F R Fw2 B' U B U' Fw y2 D' L' F' L2 D2


Now, the big question is: why did that happen on a "computer" solve instead of on a "human" solve where I could actually take advantage of it? :)

EDIT: So far, I've found (without computer searching) a 29-move solution for the above reduction. While I know that F2L minus 1 slot can be achieved in 10 moves, I used 12 in this solution.

Skeleton:
2x2x3: D' L' F' L2 D2 (5)
F2L minus 1 slot: F . R2 * F' U2 R U2 R (12)
Edges: R U R' U' F' U' F U (20-1 = 19)

This left a 5-cycle of corners.

I found pairs of 3-cycle insertions that would cancel 2+2 moves or 3+1 moves. Thus, it looked to me like I would get a 19+8+8-4 = 31-move solution. However, the insertions cancelling 2 moves each were so close together, that there was a move from the 2nd insertion that cancelled out a move from the first insertion. This extra double-cancellation brought down the final move count to 29f (also 29s).

Insert at ".": D L' D' R2 D L D' R2 (27-2 = 25)
Insert at "*": D B2 D' F' D B2 D' F (33-2-2 = 29)

Final solution: D' L' F' L2 D2 F D L' D' R2 D L B2 D' F' D B2 D' U2 R U2 R2 U R' U' F' U' F U (29f/29s)
 
Last edited:

ch_ts

Member
Joined
Apr 25, 2008
Messages
251
After several hours' search, all 5 scrambles are solved no more than 40 OBTM moves. See #55.

Wow, that's great.

Does anybody know a case that might be especially difficult to reduce (based on intuition, theory, or whatever) and maybe Shuang could try his solver on it?
 

Kare

Member
Joined
Jun 12, 2006
Messages
21
Location
Sweden
WCA
2004KRIG02
Sorry about being a bit late here, I forgot about the competition and got reminded during euros.

My solver used an approach I have been thinking about for a few years and finaly got a reason to test. While it proved to be inefficient compared to the other methods used I find it a interesting and will post an outline of the algorithm. It's based on how I like to do FMC for 3x3, and only slightly adopted to a computer, so no standard reduction to 3x3. Phase 1 is solve a lot of pieces cheaply, phase 2 is commutator insertions to solve the rest. Both steps are greedy, adding a few moves at a time never branching out.

Phase 1: Solve lots cheaply.

Do a complete search of depth 5. Find the sequence Z that results in the most solved pieces. Now apply the first move of Z to the cube. Do another depth 5 search. If there is a depth 5 alg producing more solved pieces than the remainder of Z would, then swithch to the new sequence, else keep the remainder of Z. Apply another move and once again do a depth 5 search.

Once we are at a local maxima with no improvements in sight phase 1 gives up. By now most pieces are solved.

Phase 2: Insertions

Generate all possible sequences of the form (XYX') Z (XY'X') Z' or Z'(XYX')Z(XY'X') where X is orthogonal to Y and Z. Y and Z are not the same slice. This results in 2*36*24*21 = 36288 commutators. Not all commutators are 3-cycles, but I keep them all as I did not want to spend the effort to filter the list and it runs fast enough anyway.

I take the partial solution from step one and loop over all possible places to insert a commutator, loop over all commutators evaluating which insert results in the most solved pieces. From all possible insertions resulting in the best score I choose the one costing the least moves after cancelations. If no insertion results in more solved pieces the program terminates with no solution found. Rinse and repeat untill we have done enough insertions to solve the entire puzzle.

Remarks:
Phase 2 can't change parity, so the program will only find a solution if phase 1 ends with
neither corner nor edge parity. This is solved by subtracting 2 solved pieces per parity
from the score of a position. Phase 1 might still end with a parity, but it is rare.

By far the most common reason phase 2 fails is that we get into a position that is solved
except for two twisted corners. This is avoided by having permuted but twisted corner be
worth -1 point each.

The program solves each side to the position it had when scrambled. So if we scramble with
WCA orientation the soulution should end up with WCA orientation. Because of this we can
solve each scramble 24 times with all the different puzzle rotations inserted before the
solution and then choose the shortest.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
It seems that you have found shorter solutions for this contest?

Playing around with new technology, trying to interleave the new access code in properly. In certain positions I can chop 7-ply from the trunk of the tree.

centers_frustrating.jpg


You can see the obvious bug here, of course. It's a little tricky, but once I get this worked out, this thing will be cruising :)
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
You've made good progress, but I don't think you're even a factor of a million off from solving arbitrary random scrambles. Not the right thread :p

Well, considering there is no stage solving in this version....

fastest_snake_solve_ever.jpg


...but that is not my lofty goal for now. One pruning algo at a time. And I think I have the centers code ironed out. I copied/pasted the wrong variable name into a parameter I was passing to a search function prep call. D'oh!

center_probe_success.jpg
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Maybe we can do another FMC in June 2015? I'm working on a 5x5x5 program now while waiting for some 4x4x4 database generation to finish. I will have a new experimental version of my 4x4x4 program by mid-April, so if anyone else wants to start tuning up their software, this might be enough notice for the proposed June timeframe.
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Maybe we can do another FMC in June 2015? I'm working on a 5x5x5 program now while waiting for some 4x4x4 database generation to finish. I will have a new experimental version of my 4x4x4 program by mid-April, so if anyone else wants to start tuning up their software, this might be enough notice for the proposed June timeframe.

I wouldn't mind *entering* such a 4x4x4 FMC. (If I *run* it, I feel a bit odd about *entering* it.)

If someone else wants to run it, that would be great.

I don't feel I need to wait until June, either. :)

-tom
 

rokicki

Member
Joined
Oct 31, 2008
Messages
301
I could run it... but with no prize or small prize like $10

That would be very nice! I am not sure how much prizes motivate folks to enter; I think
people willing to spend the time to try it, pretty much just want to see how they do.

This probably goes double for the computer part of it (the part I care most about).
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
I really don't see why unsolved is interested in 4x4x4 FMC because his solver is in a completely different metric. In addition, seeing the last competition, where the best computer results came from tweaking ch_ts' solver's solutions a bit, I doubt anything has changed since the last competition. Perhaps a human competition could spark new ideas to be implemented for the next competition, however.
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
I don't feel I need to wait until June, either. :)

-tom

Well my new 4x4x4 version will be available then. I'm using pre-computed databases that will be loaded into large RAM buffers to aid in the search. I am also building a new 60-core computer in April. Combining the two should result in something interesting. My program handles the solve from start to finish, and does not rely on any outside software. I give it the scramble, and it does all the rest, without assistance or intervention.

You guys can start whenever you want to, of course. It's just my software/hardware won't be ready for a while.

I really don't see why unsolved is interested in 4x4x4 FMC because his solver is in a completely different metric.

My single slice half turn solutions to random scrambles are in the neighborhood of 65 turns presently. I don't know how that translates to the metric that the contest uses. But apply whatever move counts that you like to the solutions. It is my hope to get the move counts down to 45 with the new hardware and software.
 
Last edited:

ch_ts

Member
Joined
Apr 25, 2008
Messages
251
Great to see people are still interested!

So, the preliminary rules:

Two categories: computer and human
$10 top prize in each category
Single slice turn metric - something different from last year, may encourage different approaches
Will start late spring, run for 1 month - i'm interested in seeing what unsolved has/will have
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Great to see people are still interested!

So, the preliminary rules:

Two categories: computer and human
$10 top prize in each category
Single slice turn metric - something different from last year, may encourage different approaches
Will start late spring, run for 1 month - i'm interested in seeing what unsolved has/will have

Well I am pulling what's left of my hair out now with my 5x5x5 solver over stuff like this:

5x5x5_depth_08_12_seconds.png


Two nights ago a 7-ply search on the 5x5x5 took 90 minutes and 8-ply was over a day and a half.

Tonight 8-ply was down to 17 seconds with pre-computed databases loaded into RAM, but it throws the parallel search code into a tizzy.

Grrrrrrrrr.

Edit: Finally nailed it!

5x5x5_TFS_03_center_solve.png


I'll take 21 seconds for 8-ply in a 5x5x5 solve without corner pruning :) It's a shame about the hash collisions though. For a 6 GB buffer and only 3 Turns-From-Solved loaded into RAM, I would not expect 138 hash collisions. I guess with two 64-bit variables x 6 = 96 bytes/cube, transforming that much data into a mere 64-bit hash is bound to produce duplicate hash numbers. I'll have to work on a more random hash function. The 4x4x4 collision rate is only 3 or 4 for the entire 5-turns-from-solved database.
 
Last edited:

ch_ts

Member
Joined
Apr 25, 2008
Messages
251
Without looking at all the details of your solver, I think that you could get better performance with a more careful selection of stages and tables than trying to max it out on the hardware side. Nevertheless, I am trying to make this fmc as favorable as possible for you :tu
 

unsolved

Member
Joined
Mar 2, 2014
Messages
566
Location
Doylestown, PA
Without looking at all the details of your solver, I think that you could get better performance with a more careful selection of stages and tables than trying to max it out on the hardware side. Nevertheless, I am trying to make this fmc as favorable as possible for you :tu

I appreciate the sentiment, but I suffer from no delusions regarding the prospects of winning :) I've always had an interest in brute force searching, and I've solved endgame positions for checkers requiring 253 plies and chess endings of 535 plies. All for fun, although I did have 3-4 papers published on the results back in 2003 and 2004.

I have 12 different stage solving procedures ready to fire up and test on the new hardware. Whichever shows the most promise from random scrambles fed to it in April and May I will use for the contest.
 
Top