4x4x4 FMC (computer and human) round 2

[qq280833822]

My algorithm was nothing more than a fancy line-crawl @ fixed depth, solving subsets of the scramble, and rearranging the solution at the end. It reduced the solution length from 52 moves in my program's metric to 36 moves, a savings of 16 moves. The very first line of the rules forbids this very thing. I never read it. I just processed the scrambles.

For example, if the scramble is "A B C", then you try to find a move sequence "B*" which is equivalent to B but shorter than B, and the sequence "C^-1 B*^-1 A^-1" is a valid solution of course. And for a given scramble, you tried different split of A B C, find optimal B*, and the solution is shortened to only 36 moves?

If the algorithm is like that, then I have a question. When finding B*, you should check the equivalence between B* and B on a 4x4x4 super cube. Otherwise, although B* is equivalent to B on a solved 4x4x4 cube, A B C might not be equivalent to A B* C. Hence, have you checked the correctness of your solutions?

If your solution is absolutely correct, do not worry about the regulation as finding a valid 4x4x4 solution is extremely easy (for example, human solution). Then you can modify your algorithm as:
1. find a valid solution (although the solution is very long, e.g. 100 moves)
2. use your algorithm to reduce the length of solution to ~36 moves.

 

[unsolved]

For example, if the scramble is "A B C", then you try to find a move sequence "B*" which is equivalent to B but shorter than B, and the sequence "C^-1 B*^-1 A^-1" is a valid solution of course. And for a given scramble, you tried different split of A B C, find optimal B*, and the solution is shortened to only 36 moves?

If the algorithm is like that, then I have a question. When finding B*, you should check the equivalence between B* and B on a 4x4x4 super cube. Otherwise, although B* is equivalent to B on a solved 4x4x4 cube, A B C might not be equivalent to A B* C. Hence, have you checked the correctness of your solutions?

It is much less complicated than that. And, once you see how simple it is, you will laugh.

Here is the starting position:

Spoiler: Image

Nothing fancy. The program is just making its way to a fixed depth of 13 plies. Notice only 24 nodes were explored through depth 12, and only 352 shown so far @ depth 13. When it doesn't find a solution, it chops one move off from the beginning, not the end. This way, I don't have to worry about doing too much work to splice together a working solution at the end.

Spoiler: Image

The above image should make this more clear. I just crawl down the line until I encounter the deepest position that can be solved in 13 moves. At that point, I can stop, and only search the rest of the unsolved space, from move 1-N where N might be 19 moves out. So a 19-move solution was found in 13 moves (for example, call that solution A) and you just sliced 6 moves off of the solve length. This process is repeated:

Moves 1-43, 2-43, 3-43, 4-43.... until another solution is found, call that solution B.

That way, I have moves 1-x still unsolved, then solution B, then solution A.

Now I work on moves 1-x, 2-x, 3-x, 4-x, etc. finding solution C.

I keep going until my last solution reaches back to depth 1.

If I find no solution A after going all the way down the tree, then another set of code kicks in.

 

[bobthegiraffemonkey]

I have to disqualify my 36-move result after chatting with one of the other participants. I have an algorithm that makes use of subsets of the scramble. I started working on it long before the contest when I was making my own stage solver, and I discovered an interesting way to find near-optimal or optimal solutions to just about any scramble. It's very CPU-intensive and massively parallel. So, until I come up with a new stage solving algorithm, I must remove myself.

I skimmed over your posts since this one. Unless I'm misunderstanding (I might be), the issue is with applying the technique to the scramble which is provided. Then, isn't it possible to fix the problem by first generating a different scramble for the same position to start with, then applying the technique to that?

 

[qq280833822]

The above image should make this more clear. I just crawl down the line until I encounter the deepest position that can be solved in 13 moves. At that point, I can stop, and only search the rest of the unsolved space, from move 1-N where N might be 19 moves out. So a 19-move solution was found in 13 moves (for example, call that solution A) and you just sliced 6 moves off of the solve length. This process is repeated:

Moves 1-43, 2-43, 3-43, 4-43.... until another solution is found, call that solution B.

That way, I have moves 1-x still unsolved, then solution B, then solution A.

Now I work on moves 1-x, 2-x, 3-x, 4-x, etc. finding solution C.

I keep going until my last solution reaches back to depth 1.

If I find no solution A after going all the way down the tree, then another set of code kicks in.

The problem mentioned by qqwref and me is still unsolved.
For example, the scramble is X Y, where Y is a 19-move sequence. In this case, although you find a 13-move solution A such that "Y A" == solved, how can you guarantee "X Y A" == "X"?

Unless the search is on a 4x4x4 super cube.

 

[unsolved]

I skimmed over your posts since this one. Unless I'm misunderstanding (I might be), the issue is with applying the technique to the scramble which is provided. Then, isn't it possible to fix the problem by first generating a different scramble for the same position to start with, then applying the technique to that?

The rules state:

Welcome to 4x4x4 FMC round 2!

Rules:

You may not use the inverse of the scramble or the inverse of part of the scramble in your solution. You must use the scramble in its entirety; you may not break up the scramble into smaller parts to make use of "mini-scrambles".

And, you can see, I did just that.

I had been working on this technique for a while now, testing it, about 6 weeks before the rules were even posted. It was just pointed out to me that I completely violated this rule. You can see why it is a rule though. With enough time and enough computer horsepower, you can practically optimally-solve just about any scramble.

Unless the search is on a 4x4x4 super cube.

I've seen this term before but never an explanation of it. I can say this: My center pruning table treats each center as being unique, even though there are 4 that appear to be the same. And my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved. So as long as they end up where they started, the solution is applied. Otherwise, you can't join the segments together.

 

[Ranzha]

The rules state:
And, you can see, I did just that.

You misinterpreted.

bobthegiraffemonkey was suggesting you manually find a solution (call it A), invert that to get an equivalent scramble to the originally posted scramble (A'), and plug in your result (A') into your program to start solving. This would not break the rule you mentioned.

I've seen this term before but never an explanation of it. I can say this: My center pruning table treats each center as being unique, even though there are 4 that appear to be the same. And my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved. So as long as they end up where they started, the solution is applied. Otherwise, you can't join the segments together.

A 4x4 supercube looks like this. It uniquely identifies centres of the same colour, just like what your program is doing. You're good :tu

 

[unsolved]

bobthegiraffemonkey was suggesting you manually find a solution (call it A), invert that to get an equivalent scramble to the originally posted scramble (A'), and plug in your result (A') into your program to start solving. This would not break the rule you mentioned.

I think it is pretty much undermining the intent of the rule, lol. The rule makes sense though. The technique I mentioned can get you pretty close to an optimal solve almost every time. I thought this would be of interest to the group since I don't think anyone has skimmed the surface of what God's Number might be for the 4x4x4 yet (in terms of solution lengths found solely by computation). As the title of this was the "Fewest Moves Challenge" I thought any reasonable technique at solution length reduction, other than just reversing the scramble, would be permitted. But, this is really a "Shortest Stage Solve Challenge," which can only have solutions that approach the limits of known stage solving techniques, as long as the scrambles are out of range of brute force solvers.

A 4x4 supercube looks like this. It uniquely identifies centres of the same colour, just like what your program is doing.

Thanks. Yeah I figured this out a while back

 

[Ranzha]

I think it is pretty much undermining the intent of the rule, lol.

No, it doesn't. The intent of the rule is to disallow manipulation of the original scramble for obvious reasons. If you're manipulating a scramble that you generated without help from the original scramble, any solution from there is fair game.

That's how FMC works.

 

[qq280833822]

The technique I mentioned can get you pretty close to an optimal solve almost every time.

Awesome work. Have you tried longer scrambles? e.g. more than 60 or 80 moves. And see whether your solver can still return a near-36-move solution?

BTW, according to my knowledge, the algorithm you described only works if the number of canonical move sequences is much larger than the number of state at maximum search depth (e.g. 13). I'm not sure whether 4x4x4 is such puzzle in SSTM. But in OBTM, at depth 8, the number of state (44246249410) is almost equals to the number of canonical move sequences (44969120244)

 

[unsolved]

Awesome work. Have you tried longer scrambles? e.g. more than 60 or 80 moves. And see whether your solver can still return a near-36-move solution?

No, this is only fully tweaked and perfected as of a few days ago. I got too distracted by messing around with my 5x5x5 program, which, oddly enough, is what led to the massive pruning discovery. I was shocked the first time I compiled the wing-edges table for the 5x5x5 and saw this:

Spoiler

I made the wing-edges table for the test position above for the (obvious) reason that corners would not be worth anything in a position like that (well, it could help the program by keeping it from "drifting" too far from a solution once the move gen length was at least one move more than half the solution length). Then I thought if I combined corners and wings, the result would probably be the same, but at least I would have corner data to use in other positions. Then I thought adding a separate "middle edge" table would be a waste of sorts, since it would require multiple probes. And I didn't finish that thought before it finally dawned on me that a ringed cube for the 5x5x5 = wings + middle edges + corners, and with one probe, you can effectively get the equivalent of three separate pruning distances.

It wasn't too much later that the thought of "ring + center" would be like bullet-proofing the forward pruning altogether, making the ultimate mechanism for the task.

BTW, according to my knowledge, the algorithm you described only works if the number of canonical move sequences is much larger than the number of state at maximum search depth (e.g. 13). I'm not sure whether 4x4x4 is such puzzle in SSTM. But in OBTM, at depth 8, the number of state (44246249410) is almost equals to the number of canonical move sequences (44969120244)

I didn't think of it in terms of that; I just let the brute force and computer science aspect do the work. Trial and error, trial and error, sometimes it takes a few failures to finally hit on the correct idea.

Here are some of my single turn counts for the 4x4x4:

Depth	Nodes	Cumulative
8	413,919,090,792	429,650,631,855
9	11,304,715,303,584	11,734,365,935,439
10	308,747,751,874,992	320,482,117,810,431
11	8,432,337,451,411,872	8,752,819,569,222,303
12	230,299,053,086,277,216	239,051,872,655,499,519
13	6,289,792,617,720,221,568	6,528,844,490,375,721,087
14	171,783,125,652,467,209,536	178,311,970,142,842,930,623
15	4,691,639,939,891,068,296,576	4,869,951,910,033,911,227,199
16	128,135,317,377,520,330,634,880	133,005,269,287,554,241,862,079

 

[Herbert Kociemba]

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 ?
Can you give the output of your program for this example? This would convince me more than the node counts for some shallow searches for depth <=16.

 

[unsolved]

You mean U R F D L B 2U 2R 2F 2D 2L 2B U R F D L B 2U 2R 2F 2D 2L 2B U R F D L B 2U 2R 2F 2D 2L 2B ... for a total of 6 times?

 

[Herbert Kociemba]

yes

 

[ch_ts]

So, the case in my mind that I had when I wrote that rule was:

Take scramble 5 as an example:
F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U Fw2 D Rw2 R Fw2 R Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2

I don't want people to do:
A = F2 L2 B' U2 D2 R2 U2 F U F2 R B R2 D2 B D L' U
B = Fw2 D Rw2 R Fw2 R Uw2 F2 R2 D Rw2 D2 U' Fw F L' Fw2 Rw' Uw F' D2 Rw' B Uw2 B L B U' F2
Solve B, solve A, and put the solutions together.

I want people to set up the cube using the scramble as I have given it in its entirety, and then solve that position not using the scramble anymore.

unsolved, if I added the rule: "Your solution may not intentionally visit any position that is visited by the scramble" how would you adapt to that? And I'm curious, what happens if you do what bobthegiraffemonkey suggested? (find your own solution, use the inverse as the scramble, apply your technique) Can you still find short solutions given a longer scramble (say 100 moves)? Have you tried?

 

[rokicki]

Awesome work. And see whether your solver can still return a near-36-move solution?

Unsolved, if you have a 36-move solution by *any* means, that is impressive.

If you have a 36-move solution by the technique you described, that is very
surprising. Is it possible you have erred and your 36 moves do not actually
solve the position? If not, then there is something about the scramble or the
4x4x4 that I have not yet understood.

Ch_ts, are you willing to share how you generated the scrambles? Is it just
random moves, and if so, did you exclude certain adjacent move pairs or
some such?

It may be the case that for nxnxn cubes, as n increases, the state space
approaches some degree of predictability (that is, some correlation between
a structural property and the position depth) but I'm surprised if this is
happening already for the 4x4x4.

 

[qq280833822]

Ch_ts, are you willing to share how you generated the scrambles? Is it just
random moves, and if so, did you exclude certain adjacent move pairs or
some such?

I guess the first 3 scrambles are random-move scrambles, while the last 2 scrambles are generated by another solver (maybe the WCA scrambler, or a solver written by Ch_ts himself). I wonder whether the algorithm mentioned by unsolved also works well on the last 2 scrambles. If does, for a specific state, we can calculate another near-50-move generator by another solver (e.g. the WCA scrambler), and then use unsolved's algorithm to further improve the solution to near optimal.

 

[Herbert Kociemba]

Thanks, I took a look again after 8 hours you ran your program with my proposed scramble but I cannot interpret from the output if you were able to shorten it.

 

[unsolved]

Thanks, I took a look again after 8 hours you ran your program with my proposed scramble but I cannot interpret from the output if you were able to shorten it.

Two things happened last night here in the Philadelphia suburbs. We had a small lightning storm, so I took a precaution and shut down while it passed. Of course, as soon as I did the shut down, I got notice that "179 Windows Updates" were being applied, and the "Do not turn off your computer" message had me praying we would not lose power. While I waited, I recompiled the code to "automatically" enter your long scramble on startup with no human intervention. But somehow it engaged the algorithm only to depth 12, which was not deep enough to find any improvement to a scramble consisting of 12-perpendicular moves repeated over and over.

But at least you could see the automation of the algorithm and how it crawls over a line looking for the maximum possible reduction. When it finds the largest one, it resumes the search for the remainder of the scramble that is still unsolved.

The program will parse over the entire scramble, one move at a time, from both the front and back end, if it does not find any improvement. Anyone who logs on now can see that this is happening.

I also added some new text output that displays the cumulative improvements found to the line.

I'm going to relaunch in a few minutes with a deeper search mode and see what happens.

Unsolved, if you have a 36-move solution by *any* means, that is impressive.

If you have a 36-move solution by the technique you described, that is very
surprising. Is it possible you have erred and your 36 moves do not actually
solve the position?

Of course it is possible. When I misinterpreted Shuang Chen's solutions to be 27 moves in length, I stopped all copies of my program from running and starting looking over my source code for ways to improve it. What I should have done is pasted the solution into alg.cubing.net but I had not reconstructed it yet from the segmented output.

If there was an error, it would have to be in the supercube subset of the code. I have a new definition of "solved" that has 3 of the 4 centers using integers other than the one assigned to its cube face. They all have to be in their starting configuration in order for the chained solution to work.

If not, then there is something about the scramble or the
4x4x4 that I have not yet understood.

Well a picture is worth 1,000 words, as they say, so why don't you log onto my machine and take a peek at what it's doing? I'm pretty sure when you see the line crawl algorithm that it will make perfect sense.

 

[adimare]

I've seen this term before but never an explanation of it. I can say this: My center pruning table treats each center as being unique, even though there are 4 that appear to be the same. And my line crawling solver (stage solver) requires all 24 centers to be where they started in order for the cube to be solved. So as long as they end up where they started, the solution is applied. Otherwise, you can't join the segments together.

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).

 

[ch_ts]

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.

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.

Sure I can share how I generated the scrambles. The first 3 scrambles are random scrambles from cstimer, with length 45. The last 2 scrambles are from worlds 2013 (so based on reduction to 3x3x3), to which I added 5 random moves to the end.