How to quickly generate states with a fixed optimal solution length?

[Herbert Kociemba]

There are K=1,384,201,395,738,071,424 canonical sequences for N=16. How do you want to do this sampling practically? A one to one mapping of each canonical sequence to some index 0<=x<K which can be calculated in both directions is the only way I see to solve this problem. It may be possible but it doesn’t seem trivial.

 

[qq280833822]

There are K=1,384,201,395,738,071,424 canonical sequences for N=16. How do you want to do this sampling practically? A one to one mapping of each canonical sequence to some index 0<=x<K which can be calculated in both directions is the only way I see to solve this problem. It may be possible but it doesn’t seem trivial.

What I mean is to calculate the probability of each move at each sampling step, which includes the following steps.

1. First, calculate the number of canonical sequences of length N start with specific face, which are divided into U/R/F and D/L/B according to symmetry. For U/R/F, this sequence should be C_urf = [9, 135, 1782, 23814, ...], and for D/L/B, this sequence is C_dlb = [9, 108, 1458, 19440, ...], and the calculation formula is
C_urf[ i ] = C_urf[i - 1] * 6 + C_dlb[i - 1] * 9;
C_dlb[ i ] = C_urf[i - 1] * 6 + C_dlb[i - 1] * 6;

2. Now start sampling, for example, we want to sample a 15-step canonical sequence. Then for the first move, according to the above calculation, we know that the probability of its face being U/R/F is P(U/R/F) = C_urf[15]/(C_urf[15] + C_dlb[15]). Then we randomly sample a random real number between [0, 1). If it is less than P(U/R/F), we randomly select an face between U/R/F with equal probability, otherwise we randomly select an face between D/L/B with equal probability (of course, we also need to add the random of 90/180/270 degrees).

3. After sampling the kth step, we can continue to calculate the probability of each face appearing in the next move. For example, when the previous face is D, the number of canonical sequences start with specific face that appear in the next move is Count_U=Count_D=0 (since D D, D U is forbidden), Count_R=Count_F=C_urf[N-k], Count_L=Count_B=C_dlb[N-k]. Using the sampling strategy in 2, we can continue to randomly sample the current move.

4. Recursively execute the above steps, and finally the canonical sequence with length N can be sampled with equal probability.

 

[Herbert Kociemba]

Then for the first move, according to the above calculation, we know that the probability of its face being U/R/F is P(U/R/F) = C_urf[15]/(C_urf[15] + C_dlb[15])

I don’t understand the idea behind what you are trying to explain. Let‘s start with this statement. As I understand it, your formula describes the probability of the last move to be U/R/F. The probability of the first move is 1/2.

 

[qq280833822]

I don’t understand the idea behind what you are trying to explain. Let‘s start with this statement. As I understand it, your formula describes the probability of the last move to be U/R/F. The probability of the first move is 1/2.

Here, it refers to the probability of all canonical sequences in the sense of equal probability. Taking the number of moves = 2 as an example, among all 243 canonical sequences, 135 start with URF (because we stipulate that D U is not allowed to appear).
Randomly sampling in this probability space, the probability of the first face being U/R/F is 135/243.
Similarly, when the number of moves = 3, the first face being U/R/F is 1782/3240 if all 3-move canonical sequences are sampled in equal probability.

 

[Herbert Kociemba]

For example, when the previous face is D, the number of canonical sequences start with specific face that appear in the next move is Count_U=Count_D=0 (since D D, D U is forbidden), Count_R=Count_F=C_urf[N-k], Count_L=Count_B=C_dlb[N-k].

Ok, I now understood the first step how to generate the first move according to the probabilities. So if the first move is for example D, we now must look at the distribution of the moves of the N-move sequences at the second position provided the first move is D. But should not be
Count_R=Count_F=C_urf[N-1]/3 ?

 

[qq280833822]

Ok, I now understood the first step how to generate the first move according to the probabilities. So if the first move is for example D, we now must look at the distribution of the moves of the N-move sequences at the second position provided the first move is D. But should not be
Count_R=Count_F=C_urf[N-1]/3 ?

Yes, it was my typo.

 

[Herbert Kociemba]

I think I have understood now. Nice method!
In the moment, I only have access to my smart phone, but when I’m back in a few weeks, I will give it a try.

 

[bcube]

Out of curiosity, when using the same procedure for optimal 17-19 solution lengths, do you know what is the average number of generated states needed? I am wondering if we can further reduce the following numbers and the time associated with finding optimal solutions for random-state scrambles:

For 17-19 movers, I would still use the pool with 43*10^18 states, meaning that I would need to solve optimally an expected value of approximately:

1. 3 random-state scrambles to get 2 18-movers
2. 8 random-state scrambles to get 2 17-movers
3. 60 random-state scrambles to get 2 19-movers

Based on the following currently known numbers:

depth   # of positions   # of canonical move sequences
-----   --------------   -----------------------------
 17     about 12*10^18   18,476,969,736,848,122,368
 18     about 29*10^18   246,639,261,965,462,754,048
 19     about 15*10^17   3,292,256,598,848,819,251,200

The chance of getting a depth 17 position from a length 17 canonical move sequence is about 65%.
There are about 1.5 optimal solutions per depth 17 position.
Putting it all together it means that on average, 5 generated states will lead to 2 17-movers using the procedure by qq280833822.

There are about 8 optimal solutions per depth 18 position. It alone implies that generating 3 random-states scrambles to get 2 18-movers on average is less computionally expensive.

The chance of getting a depth 19 position from a length 19 canonical move sequence is about 0.05%. It alone implies that generating 60 random-states scrambles to get 2 19-movers on average is less computionally expensive.

The procedure by qq280833822 is less computionally expensive for depths 1-17, random-state generated scrambles are less computionally expensive for depths 18 and 19.

 

[bcube]

1. First, calculate the number of canonical sequences of length N start with specific face, which are divided into U/R/F and D/L/B according to symmetry. For U/R/F, this sequence should be C_urf = [9, 135, 1782, 23814, ...], and for D/L/B, this sequence is C_dlb = [9, 108, 1458, 19440, ...], and the calculation formula is
C_urf[ i ] = C_urf[i - 1] * 6 + C_dlb[i - 1] * 9;
C_dlb[ i ] = C_urf[i - 1] * 6 + C_dlb[i - 1] * 6;

As I understand it, this procedure is the equivalent of modifying a sequence generator so that instead of generating all possible moves at each depth it just randomly picks one possible move at each depth (possible = canonical).

I see the reason to look at probabilities in the procedure described for generating random canonical sequences, for the first move at least. I currently don't see the reason for looking at probabilities for subsequent moves. The reason for doing it on the first move is that you don't get the proper distribution for the first move (after running it 1000 times or whatever) which for a two move sequence shoud be a ratio of 135 for URF to 108 for DLB as you explained which is exactly what my normal sequence generator does (the one that gen's all sequences, i.e. all 243 configs for depth 2). Canonical is being used to mean two different things: 1) eliminate duplicate moves and 2) give proper proportion of URF & DLB moves at each step (there's 20% less DLB moves because of elimination of redundant D U, B F & L R sequential moves). The sequence generator is already removing those duplicates (and also eliminating two subsequent moves to same face) hence the reason I don't see why probabilities are needed for subsequent moves (beyond first one).

I did 3 tests of the random generator with 2000 generates each (for length 2 sequences) and found the results to be as expected as shown below. Prior to the 3 tests I show the results from the normal sequence generator for (length 2) which shows that totals for UFR & DBL are switched between moves 1 & 2. The random tests show similar results so I think this method does not require looking at probabilities for any moves other than the first but feel free to prove me wrong.

-----------------------------------
Normal sequence generator (depth 2)
-----------------------------------
Move 1:
     45 F
     45 R
     45 U
    135 Total

     36 B
     36 D
     36 L
    108 Total

Move 2:
     36 F
     36 R
     36 U
    108 Total

     45 B
     45 D
     45 L
    135 Total

-----------------------------
Random Generator - Test 1
-----------------------------
Move 1:
    384 F
    395 R
    352 U
   1131 Total

    275 B
    274 D
    320 L
    869 Total

Move 2:
    298 F
    287 R
    269 U
    854 Total

    383 B
    386 D
    377 L
   1146 Total

-----------------------------
Random Generator - Test 2
-----------------------------
Move 1:
    387 F
    410 R
    355 U
   1152 Total

    275 B
    247 D
    326 L
    848 Total

Move 2:
    283 F
    272 R
    277 U
    832 Total

    400 B
    377 D
    391 L
   1168 Total

-----------------------------
Random Generator - Test 3
-----------------------------
Move 1:
    403 F
    385 R
    353 U
   1141 Total

    274 B
    258 D
    327 L
    859 Total

Move 2:
    296 F
    277 R
    280 U
    853 Total

    373 B
    406 D
    368 L
   1147 Total

 

[bcube]

Analysis of sequences up to length 10.

The following table shows the % of UFR for each move for each sequence length. Results are actual numbers from generating all the sequences and counting the moves.

Len  Move1  Move2  Move3 ...

 1  0.5000

 2  0.5556 0.4444

 3  0.5500 0.5000 0.4500

 4  0.5506 0.4944 0.5056 0.4494

 5  0.5505 0.4949 0.5000 0.5051 0.4495

 6  0.5505 0.4949 0.5006 0.4994 0.5051 0.4495

 7  0.5505 0.4949 0.5005 0.5000 0.4995 0.5051 0.4495

 8  0.5505 0.4949 0.5005 0.4999 0.5001 0.4995 0.5051 0.4495

 9  0.5505 0.4949 0.5005 0.4999 0.5000 0.5001 0.4995 0.5051 0.4495

10  0.5505 0.4949 0.5005 0.4999 0.5000 0.5000 0.5001 0.4995 0.5051 0.4495

For lengths > 1, using 55% on first move, 45% on last move and 50% for all other moves is probably close enough given the amount of a larger variance associated with random sampling.