Computer solving: a new two-phase algorithm?

[bcube]

Did you know that phase 4 of Kloosterman's algorithm has the same amount of configurations as unlimited phase 2 of Feather's algorithm?

In both cases, the number of configurations is ((4!)^5)/2 = 3,981,312.

Another similarities I found between Kloosterman's and Thistlethwaite's algorithms: phases 1 & 2 are identical, Kloosterman's move count 7, 10, 8, 18 = 43 is the same as Thistlethwaite's move count of 43 if all moves are allowed.

 

[bcube]

Realizing how badly I worded some parts and how poorly I made some important distinctions in this thread, causing it to be difficult for some readers to follow, I decided to try again and made this wiki article with the intention to simplify, summarize and make it more clear so that readers could digest it more easily.

While doing so, I realized this interesting fact: we know that the solution length found by Thistlethwaite´s algorithm in phase 4 ≥ the solution length found by Feather's algorithm in phase 2. It turned out that there are 6 cases which need 15 moves in Thistlethwaite´s phase 4 (15 is God´s number for this phase if using only half-turns) while they need only 8 moves in Feather's phase 2. Example of one such case:

 

[bcube]

What would be more interesting for me is how far you will have to go out in phase 1 to get an overall solution with <=20 moves. For my standard two-phase algorithm we know from the God's number proof that there exist exceptional positions which need 18 moves in phase 1 to get a 20 move solution.

As we know already, when considering no move restriction whatsoever, phase 1 of Feather´s algorithm reduces the cube more than phase 1 of Kociemba´s algorithm. Thus it is expected to be more than 18.

I checked your hard scrambles from this post and got the following frequency distribution for an overall solution with <= 20 moves using Feather´s algorithm:

[16+4] (20f)    3
[17+2] (19f)    4
[17+3] (20f)    20
[18+0] (18f)    2
[18+1] (19f)    3
[18+2] (20f)    19

A little bit surprised that no configuration needed more than 18 moves in phase 1, I next checked all 860 [16+x] solutions from this analysis and got the following frequency distribution for an overall solution with <= 20 moves using Feather´s algorithm:

[14+6] (20f)    1
[15+5] (20f)    27
[15+6] (20f)    2
[15+7] (20f)    1
[16+4] (20f)    338
[16+5] (20f)    9
[16+6] (20f)    19
[17+3] (20f)    331
[17+5] (20f)    2
[18+2] (20f)    124
[19+1] (20f)    6

So to answer your question: configurations with 19 moves in phase 1 for an overall solution with <= 20 moves using Feather´s algorithm are known. But now I am wondering whether it can be proved/disproved mathematically rather than computionally that 20 moves in phase 1 for an overall solution with <= 20 moves using Feather´s algorithm are/aren´t needed?

 

[Herbert Kociemba]

But now I am wondering whether it can be proved/disproved mathematically rather than computionally that 20 moves in phase 1 for an overall solution with <= 20 moves using Feather´s algorithm are/aren´t needed?

A proof would probably mean that you have to solve all 4.3 10^19 different configurations (reduced by 48 symmetries) within 20 moves. I do not think that this open question is important enough to justify an effort which would be presumably higher than that for the God's number proof since the size of the phase 2 subgroup (which is small) and their cosets in phase 1 (very large) are not well balanced as I already trie to point out here.

 

[bcube]

A proof would probably mean that you have to solve all 4.3 10^19 different configurations (reduced by 48 symmetries) within 20 moves. I do not think that this open question is important enough to justify an effort which would be presumably higher than that for the God's number proof since the size of the phase 2 subgroup (which is small) and their cosets in phase 1 (very large) are not well balanced as I already trie to point out here.

Let me explain how I am looking at it.

Since we know now that phase 1 needs at least 19 moves to get a 20 move solution, a computional proof would be checking all optimal 20-movers (about 4.9*10^8) instead of checking all 4.3*10^19 different configurations.

Of these 20-movers, can we mathematically prove that the solution to all of them can end by a half turn (which would automatically mean that phase 1 doesn´t need 20 moves to get a 20 move solution)?

 

[Herbert Kociemba]

Since we know now that phase 1 needs at least 19 moves to get a 20 move solution, a computional proof would be checking all optimal 20-movers (about 4.9*10^8) instead of checking all 4.3*10^19 different configurations.

Since we do not know the configurations which are at distance 20 from solved this approach does not work.

 

[bcube]

Since we do not know the configurations which are at distance 20 from solved this approach does not work.

Ok, now your previous post makes sense to me.

Out of curiosity, do you happen to know how many, on average, optimal 20 move solutions are there for a given configuration?

From this post: "For [...] distance 20 positions, the number of optimal solutions goes up tremendously."

And do you think it can be said that about 1/3 of them end with a clockwise quarter turn, about 1/3 of them end with a counter-clockwise quarter turn, and about 1/3 of them end with a half turn?

 

[Herbert Kociemba]

I cannot prove this but it is highly unlikely that a distance 20 position has a unique solution maneuver. In Tomas Rokicki's database are estimated about 20% of all 20 move positions and for almost all of them all neighbors (= one move distance, so each position has 18 neigbors) are 19 move positions. The maximum number of neighbors of a 20 move positions which also are 20 movers is 4 in his database. That means that from the 6 half turns it is very likely that at least one or two of them lead to a 19 move position when applied to a 20 move position.

So from a probabilistic point of view it is very plausible that for any 20 move position there is one solving sequence which starts with a half turn. This means that the inverse position (which also needs 20 moves) has a solution which ends in a half turn. So take an arbitrary 20 move position A and take the inverse B. B has very probably a solving sequence which starts with a half turn. Then your position A has a solving sequence which ends in a half turn.

 

[UMichSpeedCubist]

Half-turn reduction -> Solved

Depth    Configurations
0     1
1     6
2     27
3     120
4     519
5     2124
6     8188
7     27636
8     78644
9     174521
10    233504
11    116010
12    22228
13    24
Total    663,552

How confident are you with HTR-to-solved? I got these case counts and a different diameter but same total count:

 

[bcube]

How confident are you with HTR-to-solved?

Very confident (see second table and links below it). If I remember correctly, I myself checked all 144 optimal 15-movers from the <U2, D2, R2, L2, F2, B2> move set and found all 24 optimal 13-movers in them from the <U, D, R, L, F, B> move set.

But don´t worry, you are not the first one who missed this important detail.

 

[UMichSpeedCubist]

Very confident (see second table and links below it). If I remember correctly, I myself checked all 144 optimal 15-movers from the <U2, D2, R2, L2, F2, B2> move set and found all 24 optimal 13-movers in them from the <U, D, R, L, F, B> move set.

But don´t worry, you are not the first one who missed this important detail.

I'm confused still. Is the table you quoted, the version of DR-to-HTR that allows DR-breaking moves while mine stays in the DR moveset?

 

[bcube]

See example solves in this post - the first solve is from the <U2, D2, R2, L2, F2, B2> move set, the second solve is from the <U, D, R, L, F, B> move set (don't think of it as the <R, L, U2, D2, F2, B2> move set - I can give you another examples if you want in which the "DR move set" would be broken).

Is the table you quoted, the version of DR-to-HTR that allows DR-breaking moves

No. The HTO (half-turn only) column is Thistlethwaite's phase 4, the Optimal column is Thistlethwaite's phase 4 in the <U, D, R, L, F, B> move set, the DistP2 column is Feather's phase 2 with unlimited solution length.

Not important in this discussion but DistP2 column = 3-color cube reduction to Solved which can be thought of as (HTR + fake HTR) to Solved.

 

[UMichSpeedCubist]

It looks like part of my confusion is that for those 144 cases, you are switching DR-axis and in my terminology "breaking DR" still because I fixed my DR axis from the start. Correct me if I'm wrong.

 

[bcube]

It looks like part of my confusion is that for those 144 cases, you are switching DR-axis and in my terminology "breaking DR" still because I fixed my DR axis from the start. Correct me if I'm wrong.

By referring 144 cases we are talking about 144 configurations which can be optimally solved in 15 moves in HTM when your allowed moves are only half-turns.

I don't think it makes sense to talk about DR-axis at all if your move set consists of only half-turns.

 

[qq280833822]

I deployed a webassembly demo of cube48opt series on https://cstimer.net/cubeopt/

Currently, its function is to take a set of scrambles (manually input or randomly generated) as input and then find their optimal solutions respectively.

Before solving, it needs to take some time to generate a pruning table (from a few seconds to tens of minutes, depending on the solver and runtime environment). After generating, you can download the generated pruning table and upload it again the next time.

I deployed 7 solvers (cubeopt1, cubeopt2, ..., cubeopt7) here, each corresponding to a different pruning table size (from 30MB to 4GB). The larger the number, the larger the pruning table and the faster the solving speed. Generally speaking, the solution speed is proportional to the pruning table size.

Using the largest solver (cube48opt7, 4GB), on my 12-core laptop, it took an average of about 0.6 seconds to solve a random state. In comparison, due to the webassembly and browser runtime environment, its solving performance was 60% to 80% slower than a locally compiled solver.

 

[bcube]

I deployed a webassembly demo of cube48opt series on https://cstimer.net/cubeopt/

Great job. The numbers for cube48opt are looking fantastic here and here.

In 1997, Michael Reid created a solver utilizing a pruning table with 3x16 symmetry reduction with a target state of domino reduction in 3 directions, and he encouraged others to experiment with different pruning tables. I find it fascinating that it wasn´t until almost 2 decades later when Michael Feather in 2015, and later Sebastiano Tronto in 2023, had the same idea of creating a solver utilizing pruning tables with 1x48 symmetry reduction with a target state of a solved 3-color cube.

Based on the chart linked above, I got an impression that a solver utilizing pruning table with 1x48 symmetry reduction (cube48opt) is outperforming a solver utilizing pruning table with 3x16 symmetry reduction in terms of solving time vs table size. Would you say my impression is correct? My reasoning is following: guessing that both cubeopt30 and cubenp30 are using 3x16 symmetry reduction and all 3 solvers with cube48opt6 are written by the same programmer (assuming you tried the same in all 3 solvers to optimize them in terms of solving time vs table size), all 3 solvers have comparable solving time of cca. 0.7 seconds but cube48opt6 is using smaller table size. Conversely, with the same table size, cube48opt needs less time to find a solution in comparison with solvers (presumably) optimized for the best ratio of solving time vs table size and utilizing 3x16 symmetry reduction such as nxopt22 or vcube208 in the case of cca. 7.8 GB (or 1.95 GB) table size.

One more question, did Chrome let you load 15.56 GB pruning table just like that or was it due to the WebAssembly implementation?