Square one can be solved in 31 moves in face turn metric

[qq280833822]

In the past week, I have calculated the god's algorithm for square one in face turn metric (ftm). According to the calculation, any twistable square-one states can be solved no more than 31 moves, where (x, 0), (0, y), / are counted as one move, (x, y) are counted as two moves.

In previous works, Mr. masonjones calculated the god's algorithm for sq1 in twist turn metric[1]. And Mike Godfrey solved all odd-permutation cube-shape positions and found that there're at least 12 positions cannot be solved in 30 moves in face turn metric[2].

Recently, I calculated the god's algorithm for sq1 in ftm. The number of different positions is 3,678 * 40,320 * 40,320 * 2 = 11,958,666,854,400, which is 3678 different shapes without considering middle layer and for each shape there are 40,320 * 40,320 combinations of permutations.
The number of positions is too large to handle, so I use symmetric reduction to reduce the search space. Firstly, all positions are split into 3678 * 2 * 2 sets according to shape, middle layer and parity, with 40320*20160 different positions per set. Then, I use symmetric to reduce the number of sets to 3816. Therefore the search space is reduced to 3816*40320*20160 = 3,101,840,179,200.
Finally, I use disk-based BFS search to calculate the god's algorithm. It spends 2 bits on each position. If the position have been visited, it stores the depth of the position modulo 3, otherwise it stores '3' to indicate the position has not been visited. So the total disk space required is 775,460,044,800 Bytes or 722.2GBytes.
After searching up to 31 moves, all positions have been accessed and therefore the god number of SQ1 is exactly 31.
Here's the depth distribution of all positions.

Spoiler

Depth          Total               #New
  0                    1                   1 
  1                   16                  15
  2                   85                  69
  3                  297                 212
  4                1,438               1,141
  5                5,371               3,933
  6               19,400              14,029
  7               63,588              44,188
  8              202,540             138,952
  9              649,260             446,720
 10            1,965,432           1,316,172
 11            6,140,878           4,175,446
 12           18,288,350          12,147,472
 13           56,172,978          37,884,628
 14          165,639,212         109,466,234
 15          498,518,504         332,879,292
 16        1,454,898,116         956,379,612
 17        4,285,819,784       2,830,921,668
 18       12,288,746,014       8,002,926,230
 19       34,951,544,310      22,662,798,296
 20       96,075,902,092      61,124,357,782
 21      257,070,679,994     160,994,777,902
 22      653,697,566,102     396,626,886,108
 23    1,581,344,013,920     927,646,447,818
 24    3,471,138,980,310   1,889,794,966,390
 25    6,600,087,749,620   3,128,948,769,310
 26    9,902,019,903,186   3,301,932,153,566
 27   11,668,654,358,130   1,766,634,454,944
 28   11,950,188,612,006     281,534,253,876
 29   11,958,657,866,914       8,469,254,908
 30   11,958,666,854,024           8,987,110
 31   11,958,666,854,400                 376

I also count the depth distribution of all 3816 unique sets. The value of cube-shaped odd-permutation sets matches the calculation of Mike Godfrey.

[1] Square One God's Algorithm Computed, http://cubezzz.dyndns.org/drupal/?q=node/view/35
[2] Odd Permutations of the Cube Shape of Square-1, http://cubezzz.dyndns.org/drupal/?q=node/view/77

 

[sp3ctum]

Great work, thank you for sharing.

If I read your shape distribution data correctly, the most difficult cases require the 31 moves to solve, and there are exactly 376 of them.

Are these states in cubeshape or randomly shaped? I would imagine odd parity square square cases take more moves to solve, but I don't trust my intuition at all.

 

[qq280833822]

Great work, thank you for sharing.

If I read your shape distribution data correctly, the most difficult cases require the 31 moves to solve, and there are exactly 376 of them.

Are these states in cubeshape or randomly shaped? I would imagine odd parity square square cases take more moves to solve, but I don't trust my intuition at all.

Actually, there are 23 unique shapes with symmetry reduction or 68 shapes without considering symmetry that contains 31-depth positions.
An interesting thing is that all of these shapes have 4 corners on the top layer. Here is a list of these shapes and the number of 31-depth positions in each shape. The number before a shape is the number of different shapes that can be generated by the following shape according to symmetry (mirror and y2.)

Spoiler

      shape                 #31-depth/shape
4 *  cceecece cececece -          4
4 *  cceecece ecececec /          8
4 *  cceeceec cececece -          3
4 *  cceeceec ecececec -          2
4 *  cceeecce ececceec -          4
4 *  cececcee ecececec /          8
4 *  cececece cceecece -          4
4 *  cececece cceeceec -          3
4 *  cececece ecceecec /          4
4 *  cececece ecececce /          4
1 *  cececece ecececec -         12
2 *  cececece ecececec /         16
2 *  ceceecce ecceecec -          2
2 *  ceceecec ceceecec -         28
1 *  ceceecec ceceecec /          8
4 *  ceceecec ceeccece -          1
2 *  ceceecec ececcece -         14
4 *  ceeceecc cececece -          2
2 *  ecceceec ceececce -          4
2 *  ecceecec ceceecce -          2
4 *  ecceeecc ceeccece -          4
1 *  ececcece ececcece /          8
1 *  ecececec cececece -         12

 

[plutarch]

[Цитата= " qq280833822, сообщение: 1270354, участник: 1513"]
На самом деле, есть 23 уникальных формы с уменьшением симметрии или 68 форм без учета симметрии, которая содержит 31-позиции глубины.
Интересно то, что все эти фигуры имеют 4 угла на верхнем слое. Вот список этих фигур и количество 31-глубинных позиций в каждой фигуре. Число перед фигурой - это число различных фигур, которые могут быть созданы следующей фигурой в соответствии с симметрией (зеркало и y2.)
[Спойлер] [код] форма #31-глубина / форма
4 * cceecece cececece-4
4 * cceecece ecececec / 8
4 * cceeceec cececece-3
4 * cceeceec ecececec - 2
4 * cceeecce ececceec - 4
4 * cececcee ecececec / 8
4 * cececece cceecece - 4
4 * cececece cceeceec - 3
4 * cececece ecceecec / 4
4 * cececece ecececce / 4
1 * cececece ecececec - 12
2 * cececece ecececec / 16
2 * ceceecce ecceecec - 2
2 * ceceecec ceceecec - 28
1 * ceceecec ceceecec / 8
4 * ceceecec ceeccece-1
2 * ceceecec ececcece-14
4 * ceeceecc cececece-2
2 * ecceceecceecce - 4
2 * ecceecec ceceecce - 2
4 * ecceeecc ceeccece-4
1 * ececcece ececcece / 8
1 * ecececec cececece - 12
[/КОД] [/СПОЙЛЕР]
[/ЦИТАТА]
- Привет!
Можно ли получить скремблы из тех 376 позиций антиподов для квадрата-1, в которых решение равно 31 htm?
Они бы отлично боролись за упражнения в сборке квадрата 1 по количеству ходов.
С уважением и наилучшими пожеланиями

 

[Deleted member 36445]

[Цитата= " qq280833822, сообщение: 1270354, участник: 1513"]
На самом деле, есть 23 уникальных формы с уменьшением симметрии или 68 форм без учета симметрии, которая содержит 31-позиции глубины.
Интересно то, что все эти фигуры имеют 4 угла на верхнем слое. Вот список этих фигур и количество 31-глубинных позиций в каждой фигуре. Число перед фигурой - это число различных фигур, которые могут быть созданы следующей фигурой в соответствии с симметрией (зеркало и y2.)
[Спойлер] [код] форма #31-глубина / форма
4 * cceecece cececece-4
4 * cceecece ecececec / 8
4 * cceeceec cececece-3
4 * cceeceec ecececec - 2
4 * cceeecce ececceec - 4
4 * cececcee ecececec / 8
4 * cececece cceecece - 4
4 * cececece cceeceec - 3
4 * cececece ecceecec / 4
4 * cececece ecececce / 4
1 * cececece ecececec - 12
2 * cececece ecececec / 16
2 * ceceecce ecceecec - 2
2 * ceceecec ceceecec - 28
1 * ceceecec ceceecec / 8
4 * ceceecec ceeccece-1
2 * ceceecec ececcece-14
4 * ceeceecc cececece-2
2 * ecceceecceecce - 4
2 * ecceecec ceceecce - 2
4 * ecceeecc ceeccece-4
1 * ececcece ececcece / 8
1 * ecececec cececece - 12
[/КОД] [/СПОЙЛЕР]
[/ЦИТАТА]
- Привет!
Можно ли получить скремблы из тех 376 позиций антиподов для квадрата-1, в которых решение равно 31 htm?
Они бы отлично боролись за упражнения в сборке квадрата 1 по количеству ходов.
С уважением и наилучшими пожеланиями

English:

In fact, there are 23 unique shapes with reduced symmetry or 68 shapes without symmetry, which contains 31-position depths. Interestingly, all these shapes have 4 corners on the top layer. Here is a list of these figures and the number of 31 deepest positions in each figure. The number in front of the figure is the number of different figures that can be created by the next figure in accordance with the symmetry (mirror and y2.)

Spoiler

4 * cceecece cececece-4
4 * cceecece ecececec / 8
4 * cceeceec cececece-3
4 * cceeceec ecececec - 2
4 * cceeecce ececceec - 4
4 * cececcee ecececec / 8
4 * cececece cceecece - 4
4 * cececece cceeceec - 3
4 * cececece ecceecec / 4
4 * cececece ecececce / 4
1 * cececece ecececec - 12
2 * cececece ecececec / 16
2 * ceceecce ecceecec - 2
2 * ceceecec ceceecec - 28
1 * ceceecec ceceecec / 8
4 * ceceecec ceeccece-1
2 * ceceecec ececcece-14
4 * ceeceecc cececece-2
2 * ecceceecceecce - 4
2 * ecceecec ceceecce - 2
4 * ecceeecc ceeccece-4
1 * ececcece ececcece / 8
1 * ecececec cececece - 12

Is it possible to get scrambles from those 376 antipode positions for square-1 in which the solution is 31 htm?
They would have fought well for the exercises in building square 1 in the number of moves.
best regards

 

[plutarch]

Judging by the lack of an answer, I conclude that no studies have been conducted and all the hackneyed nonsense.

 

[MaximalMegaminx]

In the past week, I have calculated the god's algorithm for square one in face turn metric (ftm). According to the calculation, any twistable square-one states can be solved no more than 31 moves, where (x, 0), (0, y), / are counted as one move, (x, y) are counted as two moves.

In previous works, Mr. masonjones calculated the god's algorithm for sq1 in twist turn metric[1]. And Mike Godfrey solved all odd-permutation cube-shape positions and found that there're at least 12 positions cannot be solved in 30 moves in face turn metric[2].

Funnily enough, neither the metric used by masonjones nor by you is the one actually used to count moves on the Square-1 by the WCA as defined in 12c4* for the purposes of rule 4b3d**. Would it be possible to say what the God's number is using WCA's knock-off Axis Turn Metric? Using the result of 13 by masonjones you can conclude it's between 25 and 27, and frankly it's probably 27 but I don't know how to prove it. One would need to show that there's a 13-twist state that requires horizontal moves at the start and the end of the solution. Probably relatively trivial for someone who's not me.

By the way, would it be possible for you to give an example of one of those 31-move combinations in FTM? That'd be nice to have.

*12c4) Metric for Square-1: (X, Y) counts as one move, "/" counts as one move.
**4b3d) Square-1: The (random) state must require at least 11 moves to solve.

(notably this isn't the metric used when dealing out the misalignment penalties, where regular FTM is used, with the caveat that it's 45 degree horizontal face rotations that are the limit, not 15 degrees as would be intuitive for Square-1)

Edit: duh, it can't be 25 because all I need to do is make a U or D face turn that blocks a slice move with a corner, so it's either 26 or 27
Edit: not if we don't allow those positions though, which under your count and by WCA scrambling practices... would be the case, so still between 25 and 27 then

 

[UMichSpeedCubist]

In the past week, I have calculated the god's algorithm for square one in face turn metric (ftm). According to the calculation, any twistable square-one states can be solved no more than 31 moves, where (x, 0), (0, y), / are counted as one move, (x, y) are counted as two moves.

In previous works, Mr. masonjones calculated the god's algorithm for sq1 in twist turn metric[1]. And Mike Godfrey solved all odd-permutation cube-shape positions and found that there're at least 12 positions cannot be solved in 30 moves in face turn metric[2].

Recently, I calculated the god's algorithm for sq1 in ftm. The number of different positions is 3,678 * 40,320 * 40,320 * 2 = 11,958,666,854,400, which is 3678 different shapes without considering middle layer and for each shape there are 40,320 * 40,320 combinations of permutations.
The number of positions is too large to handle, so I use symmetric reduction to reduce the search space. Firstly, all positions are split into 3678 * 2 * 2 sets according to shape, middle layer and parity, with 40320*20160 different positions per set. Then, I use symmetric to reduce the number of sets to 3816. Therefore the search space is reduced to 3816*40320*20160 = 3,101,840,179,200.
Finally, I use disk-based BFS search to calculate the god's algorithm. It spends 2 bits on each position. If the position have been visited, it stores the depth of the position modulo 3, otherwise it stores '3' to indicate the position has not been visited. So the total disk space required is 775,460,044,800 Bytes or 722.2GBytes.
After searching up to 31 moves, all positions have been accessed and therefore the god number of SQ1 is exactly 31.
Here's the depth distribution of all positions.

Spoiler

Depth          Total               #New
  0                    1                   1
  1                   16                  15
  2                   85                  69
  3                  297                 212
  4                1,438               1,141
  5                5,371               3,933
  6               19,400              14,029
  7               63,588              44,188
  8              202,540             138,952
  9              649,260             446,720
 10            1,965,432           1,316,172
 11            6,140,878           4,175,446
 12           18,288,350          12,147,472
 13           56,172,978          37,884,628
 14          165,639,212         109,466,234
 15          498,518,504         332,879,292
 16        1,454,898,116         956,379,612
 17        4,285,819,784       2,830,921,668
 18       12,288,746,014       8,002,926,230
 19       34,951,544,310      22,662,798,296
 20       96,075,902,092      61,124,357,782
 21      257,070,679,994     160,994,777,902
 22      653,697,566,102     396,626,886,108
 23    1,581,344,013,920     927,646,447,818
 24    3,471,138,980,310   1,889,794,966,390
 25    6,600,087,749,620   3,128,948,769,310
 26    9,902,019,903,186   3,301,932,153,566
 27   11,668,654,358,130   1,766,634,454,944
 28   11,950,188,612,006     281,534,253,876
 29   11,958,657,866,914       8,469,254,908
 30   11,958,666,854,024           8,987,110
 31   11,958,666,854,400                 376

I also count the depth distribution of all 3816 unique sets. The value of cube-shaped odd-permutation sets matches the calculation of Mike Godfrey.

[1] Square One God's Algorithm Computed, http://cubezzz.dyndns.org/drupal/?q=node/view/35
[2] Odd Permutations of the Cube Shape of Square-1, http://cubezzz.dyndns.org/drupal/?q=node/view/77

I just did a bit of work on this and got a table that perfectly matches yours for depth 0 thru 15. After that depth, mine runs out of memory. I ran my code and then found this post from 8 years ago, so it's an independent verification.