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

[bcube]

Hi,

I have been revisiting the idea from this post, more precisely option 3 from this post. While it is working perfectly fine for a single attempt format, there is a slight problem for a mean of 3 format. Let me explain what I mean by that.

In a speed-solving competition, there was already a scramble with 12 optimal moves. It is only a matter of time when it happens in the 3x3x3 fewest moves event too. When it happens (assuming using the system linked above), how would you quickly generate another 2 states with 12 optimal moves for the next 2 attempts in a round?

All 0f* - 15f* states have been solved according to cube20.org. Are there any public pools of states with a fixed optimal solution length available? So that one could simply use a pool of all 12f* states and pick 2 more states from it. What about 16f* and 19f* states, any public pool for them? The issue is not solving these states quickly, the issue is how to generate them quickly? For 17f* and especially 18f* one could simply generate them using let´s say 10 random states (we need to get only 2 more 17f* or 18f*) - and even if some 19f* state would be included in that batch of 10 random states, solutions should be generated rather quickly these days on a decent machine. As for 20f* states, considering one can expect 1 such a scramble in almost 90 billion scrambles, I guess it is fine to simply use the pool of current 1,130,184 scrambles for all 102,764,490 known distance-20 positions from cube20.org in a case it will ever happen.

So the questions are:

1. is there a pool of all 12f* states (or, rather, pools for 0f* - 15f* states sorted by optimal solution length) from cube20.org available?
2. is there a pool of, let´s say, 1,000,000 19f* states (and 1,000,000 16f* states) available?
3. do you know any other way how to quickly generate at least 2 random-state scrambles with a fixed optimal solution length (say, 17f*)?

 

[Herbert Kociemba]

Take the more than 1,000,000 representants for 20-move positions from cube20.org, conjugate the maneuvers by all 96 cube symmetries and inversions (delete duplicates - which can happen if you the representant has symmetry or antisymmetry) to get the more than 100,000,000 20 move positions. Then delete the first move, the first two moves, the first three moves... or the last move, the last two moves, the last 3 moves... to get a list with more than 200,000,000 19 move, 18 move, 17 move... maneuvers.
Example:
L2 D2 U2 R' F2 D2 L F' U F2 U' B' R' U L B' R B2 U' R' is a 20 move position
B2 L2 R2 F' U2 L2 B U' R U2 R' D' F' R B D' F D2 R' F' is for example result for the rotation by 120° at the URF axis, U->R->F->U and L->B->D->L
R U B2 R' B L' U' R B U F2 U' F L' D2 F2 R U2 D2 L2 is just the inversion of the first generator
L' U' B2 L B' R U L' B' U' F2 U F' R D2 F2 L' U2 D2 R2 is the result for the reflection of the last one at the RL plane,
R<->L', R'<->L, U<->U', D<->D', F<->F', B<->B'
In this way you can in principle generate up to 96 different positions from one of the representants.
If you cut off the first move you get 19 move positions
D2 U2 R' F2 D2 L F' U F2 U' B' R' U L B' R B2 U' R' , L2 R2 F' U2 L2 B U' R U2 R' D' F' R B D' F D2 R' F' etc.
also when cutting off the last move
L2 D2 U2 R' F2 D2 L F' U F2 U' B' R' U L B' R B2 U', B2 L2 R2 F' U2 L2 B U' R U2 R' D' F' R B D' F D2 R' etc

In this way you get about 200,000,000 million different 19 move positions, You can derive 300,000,000 18 move positions by cutting off 2 moves from left or 2 moves from right or one move from left and one move from right etc...

This should be enough for all practical purposes.

 

[bcube]

In this way you get about 200,000,000 million different 19 move positions,

Thank you for the approach you mentioned (I have been thinking about this one). Do I understand it correctly that even if we knew all optimal 20-movers (about 490,000,000) it would still not be possible to generate all optimal 19-movers (about 1,500,000,000,000,000,000) in your approach?

Also, do you think we can´t get any advantage of the fact that all optimal 0-15-movers have been solved at all? I would imagine that we could use a truly random states for all optimal 0-15-movers as opposed to the pools/lists of optimal 16-20-movers with unknown amount of states.

 

[Deleted member 36445]

1. do you know any other way how to quickly generate at least 2 random-state scrambles with a fixed optimal solution length (say, 17f*)?

STEP 1: check for past FMC events where people solved with few moves
STEP 2: do it again

 

[Herbert Kociemba]

Do I understand it correctly that even if we knew all optimal 20-movers (about 490,000,000) it would still not be possible to generate all optimal 19-movers (about 1,500,000,000,000,000,000) in your approach?

Yes. With my approach only those 19 move position can be reached which are neigbours of a 20 move position. But most 19 move position do not have such neighbours but are local maxima.

Also, do you think we can´t get any advantage of the fact that all optimal 0-15-movers have been solved at all?

A database which stores all 15 move positions would be too big, even if we would store only the representants mod symmetry and antisymmetry. So I do not think it exists. But generating such positions should not be very difficult though. Generate canonical sequences of length 15 and solve them optimally. This should go in fractions of a second. Then discard solutions which are shorter than 15 moves. There are 103,697,388,221,736,960 canonical sequences of length 15 and 91,365,146,187,124,313 belong to a position with length 15. So the chance is about 90%.

 

[bcube]

STEP 1: check for past FMC events where people solved with few moves
STEP 2: do it again

Perhaps you missed the point. The wanted use case is following: a round consists of 3 attemps. For attempt 1, a random-state scramble is used. For attempts 2 and 3, random-state scrambles with the same optimal move count as having the attempt 1 are used.

In a perfect world, there are generally 2 ways how to get a random-state scramble:

1. use a pool of all 43 252 003 274 489 856 000 states (attempt 1 is generated this way), or
2. use a pool of 243 states for all 2-movers, a pool of 3,240 states for all 3-movers, etc.

In both approaches, all states to be generated have probability greater than 0, whereas in your approach there would be states with a probability of being generated equal to 0.

In reality however, there are 2 issues regarding the frequency distribution of states:

1. if you keep generating random-state scrambles in the pool with 43*10^18 states, you can expect approximately 1 optimal 12-mover in every million of scrambles => it is very time consuming to generate 2 more 12-movers after getting a 12-mover in attempt 1
2. there is an unknown amount of optimal 16-20-movers => some states are having a probability of being generetad equal to 0 unless you keep generating random-state scrambles in the pool with 43*10^18 states

Herbert provided workarounds that are applicable to practical purposes - personally, I would use them for 0-15-movers and 20-movers. For 16-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
4. 80 random-state scrambles to get 2 16-movers

 

[Herbert Kociemba]

80 random-state scrambles to get 2 16-movers

Why do you want use random scrambles? Use random canonical sequences of length 16 instead and in more than 70% the lemgth of the position will be 16. You will get 2 16 movers with lesse then 5 tries usually.

 

[bcube]

Why do you want use random scrambles? Use random canonical sequences of length 16 instead and in more than 70% the length of the position will be 16. You will get 2 16 movers with less than 5 tries usually.

In my case, the problem is implementation details. Even though I think I understand the process you are suggesting, and I can imagine why it should also work (so good point, thank you for mentioning it), as a non-programmer I can not really replicate it even for random canonical sequences of length 8 (I am not exactly sure how should I effectively generate and deduplicate them without storing them). In contrast, I can generate 80 random-state scrambles and look for 2 optimal 16-movers in a relatively quick time manner.

 

[bcube]

There are 103,697,388,221,736,960 canonical sequences of length 15 and 91,365,146,187,124,313 belong to a position with length 15.

On a second thought, if I sum all states of lenght 0 to length 15, I get 98,929,809,184,629,081 states. So basically it means there are duplicate states in canonical sequences.

Generate canonical sequences of length 15 and solve them optimally. This should go in fractions of a second. Then discard solutions which are shorter than 15 moves.

Now, if I delete solutions that are shorter than 15 moves, does it guarantee that all 91,365,146,187,124,313 states will be included exactly once? If not (which is what I think is correct), then that is not what is wanted - I want the same probability of all states with a fixed optimal solution length (15 in this scenario) to be generated, just like in a case with the pool with 43*10^18 states. If yes (which I think is incorrect), shouldn´t take generating canonical sequences of length 16 and solving them optimally at most several seconds? Then deleting solutions which are shorter than 16 moves would give me the amount of optimal 16-movers really quickly.

 

[Herbert Kociemba]

So basically it means there are duplicate states in canonical sequences

Of course there are duplicates. Else we would know the number of positions of any length because the number of canonical sequences can be computed by a simple formula.

Now, if I delete solutions that are shorter than 15 moves, does it guarantee that all 91,365,146,187,124,313 states will be included exactly once? If not (which is what I think is correct), then that is not what is wanted

Indeed not each position has the same probability when we generate random canonical sequences. If a position has several different generators the probability is obviously higher to get this position than for a position which which only has one generator. Each symmetrical position for example has at least so many different generators as it has symmetries.

Then deleting solutions which are shorter than 16 moves would give me the amount of optimal 16-movers really quickly.

There are way to many canonical sequences of length 16 to make this approach work. Even for the 15 movers you cannot just generate all canonical sequences of lenght 15 and solve the positions optimally and count those which really need 15 moves.

 

[bcube]

Thank you for the confirmation. Everything is clear now, except for these two statements which look like a contradiction to me:

Generate canonical sequences of length 15 and solve them optimally. This should go in fractions of a second. Then discard solutions which are shorter than 15 moves.

Even for the 15 movers you cannot just generate all canonical sequences of lenght 15 and solve the positions optimally and count those which really need 15 moves.

Oh, perhaps the first statement applies to the amount of states greater than 91,365,146,187,124,313 while the second statement applies to the amount of states equal to 91,365,146,187,124,313.

 

[Herbert Kociemba]

The first statement means samples, not all 15 movers.

 

[bcube]

Oh, I see now. Thank you for the clarification. Not exactly what I wanted, but I can see the reasoning behind your question now:

Why do you want use random scrambles? Use random canonical sequences of length 16 instead and in more than 70% the lemgth of the position will be 16. You will get 2 16 movers with lesse then 5 tries usually.

I thought you meant all canonical sequences of length 16, not just samples. So there seems to be no solution to what I want - the same probability greater than 0 for all states with a fixed optimal solution length to be generated quickly, but there are compromises / workarounds for practical use.

 

[bcube]

So there seems to be no solution to what I want - the same probability greater than 0 for all states with a fixed optimal solution length to be generated quickly

On a second thought, this is not an issue at all. When related to the 3x3x3 fewest moves competition, and assuming 16-19 (or 17-19) movers will be generetad as random-state scrambles (which should be doable very quickly by the WCA hardware/software), then 2-15 movers and 20-movers:

1. will affect only a minority of competitors
2. will guarantee fair and equal conditions for everyone, as opposed to the current system in which the WCA regards a 10-mover from a competitor A the same way as a 19-mover from a competitor B from another competition

Why is point 2 true? Here is an example for a 12-mover generated in attempt 1: the WCA could generate 15 random canonical move sequences of length 12, make sure there is no duplicate sequence in them, solve them optimally, delete solutions which are shorter than 12 moves, so the result is let´s say 10 states/scrambles. Then randomly choose 2 out of these 10 states/scrambles. Choosing 2 out of 10 generated states/scrambles can be applied to all 2-15 movers generated in attempt 1. Optionally, the WCA doesn´t have to generete 10 states/scrambles because 2 of them are enough.

That is what Herbert was saying from the beginnig, sorry for realizing it took me so long

 

[qq280833822]

I think a random-state sampling of a state with specific optimal-solution length (<=16) can be achieved in the following way.

1. Randomly generate a canonical sequence of length N and get a state.
2. Use a solver to calculate **all** canonical sequence solutions. If the optimal solution length <N is found, repeat 1.
3. If the number of solutions is 1, return the sampled state.
4. Otherwise, if the number of solutions is N>1, further randomly sample an integer between [0, N).
5. If the sampled integer is 0 (whose probability is 1/N), return the sample state, otherwise repeat the above steps starting from 1.

It is not difficult to prove that the above process can sample states with equal probability, and in fact it converges quickly, and the average number of generated states is usually less than 1.5.

 

[Herbert Kociemba]

1. Randomly generate a canonical sequence of length N and get a state.
4. Otherwise, if the number of solutions is N>1, further randomly sample an integer between [0, N).

I agree with your method, I just would not use N for two different things to increase readability.

 

[bcube]

I think a random-state sampling of a state with specific optimal-solution length (<=16) can be achieved in the following way.

Nice procedure, thank you for mentioning it.

the average number of generated states is usually less than 1.5.

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

 

[Herbert Kociemba]

1. Randomly generate a canonical sequence of length N and get a state.

How do we make this random process that all canonical sequences have the same probability to be picked? Generating all of them, indexing them and then selecting one index by random is only an option for small N but definitely not for N=15 or bigger. And the algorithm: For N=1 take any of the 18 possible moves with equal probability, and to extend the random canonical sequence r(N) from length N to length N+1 append with equal probability any of the moves which are allowed to be appended to r(N) doesn’t work since for different r(N) the number of moves which are allowed to be appended to r(N) differ.

 

[Herbert Kociemba]

For example for canonical sequences we allow moves of the D face after moves of the U face, but not the other way round, since the moves commute. So the canonical sequence U R would have probability 1/18*1/15, but D R would have 1/18*1/12.

 

[qq280833822]

For example for canonical sequences we allow moves of the D face after moves of the U face, but not the other way round, since the moves commute. So the canonical sequence U R would have probability 1/18*1/15, but D R would have 1/18*1/12.

First of all, as with your premise, we can agree that U must precede D in a canonical sequence.
In this way, for any given prefix sequence and total length N, the number of canonical sequences can be accurately calculated in O(N) time using recursive algorithms (or dynamic programming).
Then for each step, we can do sampling according to this amount (instead of equal probability), which ensures that each sequence is occurring with equal probability.