Computer solving: a new two-phase algorithm?

[Herbert Kociemba]

I think you are talking about two-way search in a narrow sense. According to nxopt's point of view ( https://github.com/rokicki/cube20src/blob/master/nxopt.md ) and my understanding, IDA* can be regarded as a refinement of two-way search in a broad sense.

Ok, if you regard a pruning table as a manifestation/result of some search from the solved state and the actual search process as a search from the target state I think we both mean the same.

 

[bcube]

qq280833822, I am wondering:

1) at https://github.com/cs0x7f/cube_solver_test/wiki#solvers, in the Variations column, 3Color835M is not an optimal solver as far as I know. Only Quad-Core (1.8 GB dist4) and Solver 2 (1.8 GB or above dist4) are, or rather can be used as optimal solvers.

2) there are parts of code in assembly at https://github.com/hkociemba/CubeExplorer/blob/master/CordCube.pas. Can you tell how much search code for CE is assembly code? If it is a big portion of the search code, shouldn't be changed pascal to assembly?

3) what is the reason behind choosing 15-17f instead of 17-19f in your tables? From distribution point of view, 17-19f interval makes a better sense to me.

Considering point no. 3 above, I understand qq280833822´s reasoning for point no. 1 now.

Aside from random-state scrambles (including expected 17-19f* scramble distributions), I have another feature request: aside from optimal (one-phase) Kociemba's algorithm solvers and optimal (two-phase) Feather's algorithm solver, could you please also add any Korf's algorithm solver to your analysis page? I don't know what solving algorithm is being used by the stickersolve and cubeopt solvers, I am assuming some modification of optimal Kociemba's algorithm.

Is there any chance you could include the following test to your analysis page?

Just for fun (results can not be mutually compared objectively), could you reproduce the test above (search time for optimal solutions for 1 000 random-state cubes, preferably with the same scrambles as being used in the test for Solver 2) to the solvers in your analysis page?

Last but not least, it is not clear to me what exactly do you mean by "3Color835M" - Single Core, Quad-Core or Solver 2? Same for "3ColorOpt" - Quad-Core or Solver 2? If Solver 2, what Dist4 file size? Could you please specify?

 

[bcube]

Would it be possible to modify/extend/make a new version of min2phase.js so that it would be able to find optimal solutions?

It turned out min2phase.js can find optimal solution by default.

To address requests like this one, I made a simple PWA (progressive web app). My testing conditions were: cell phone, PWA in offline mode featuring both min2phase.js and Solver 2 solvers, free RAM of 1 GB, free disk space of 2 GB - by today´s standards, I consider this phone setup as rather a low-end device.

If it wasn´t obvious from previous debate in this thread what you can expect from both solvers on my specific device, here is one example (note that I am talking only about the search time below, not the solvers´s initialization time):



Finding a 13-move solution took: 0.02 s for min2phase.js, 0.03 s for Solver 2 (7+6 and 12+1 solutions can be seen on the above simulator).
Proving a 13-move solution to be optimal took: 620.47 s for min2phase.js, 0.19 s for Solver 2.

One difference I noticed when playing with both 2-phase solvers and random-state scrambles: while an intermediate state (solved 3-color cube) can be always directly seen in Solver 2 solution, an intermediate state (a DR state) can not be always directly seen in min2phase.js solution (as opposed to e.g. a solution in Cube Explorer) due to optimizations known from human fewest moves solving such as NISS or pre-moves.

My conclusion: if a user wants to launch an app and start using the solver on his offline mobile device as quickly as possible, min2phase.js solver is the way to go. If a user wants to search for optimal solution on his offline mobile device, Solver 2 is the way to go. If solver´s initialization time, memory and space requirements are not an issue for a user, any of these 2 solvers is the way to go.
Batch solving is not considered here because min2phase.js, by its current design, doesn´t have a function/parameter to stop/cancel the search, meaning it could be running literally forever in some max length < 20 test settings.

Fun challenge between Solver 2 and min2phase.js could be to test the search time needed for finding 20-move solutions for 1 000 20f* scrambles (i.e. finding optimal 20-move solutions but not necessarily proving them to be optimal).

For a fully initialized min2phase.js and using the 835 MB Dist3 file for Solver 2 (keeping the same conditions as for the tests above), on my mobile phone using PWA in offline mode, finding a 20-move solution for the Superflip took: 70.71 s for min2phase.js, 18.69 s for Solver 2.

 

[bcube]

I haven´t seen any implementation of the following two-phase algorithm, so I was wondering if its implementation is indeed a new approach in computer solving?

It turned out Feather's algorithm can be accessed online at least since 2015. Considering he came up with his 3-color cube method for humans in 1980, there is a good chance he came up with his computer algorithm (optimal 3x3x3 solver, to be specific) much earlier, only to publish it online in 2015 at the latest.

 

[bcube]

aside from optimal (one-phase) Kociemba's algorithm solvers and optimal (two-phase) Feather's algorithm solver, could you please also add any Korf's algorithm solver to your analysis page?

For those who are interested: 1 scramble, 6 solutions.

 

[bcube]

All the optimal solvers I know use IDA* and they differ more or less only in the heuristics they use. And a heuristic often used is the true distances to some subgoal, for example the 4 equator edges in place + all orientation of corners and edges correct. You eventually can generate additional information about which moves on your way to the subgoal bring you closer to the subgoal. Often you also can exploit some of the 48 symmetries of the cubes to significantly speed up the search. And of course you can combine the heuristics for several subgoals to take the overall heuristic as the maximum of the heuristics of all subgoals. But this is essentially all what tells apart the different optimal solvers.

Optimal Feather´s algorithm has one very specific feature in comparison with optimal Kociemba´s or Korf´s algorithm. While optimal Kociemba´s or Korf´s algorithm is using a one-phase approach, optimal Feather´s algorithm is using a two-phase approach.

From wiki: "When searching for an optimal solution, Feather's algorithm is finding suboptimal solutions on the way. This is an advantage because in many cases it does not have to search the depth of the optimal solution length because it has already found a suboptimal solution at a lower depth that is equal to the optimal solution length, hence it only has to complete search depth N-1 to prove that solution length N is optimal."

From this point of view, Feather´s algorithm seems to be more two-phase algorithm than Kociemba´s algorithm because it uses a two-phase approach for both optimal and suboptimal solutions. Also from wiki: "Kociemba's two-phase algorithm is not designed to search for an optimal solution, its purpose is to quickly find a reasonably short suboptimal solution. A randomly scrambled cube would be typically solved in a fraction of a second in 20 moves or less, but without any guarantee that the solution found is optimal. While it is technically possible to search for an optimal solution using Kociemba's algorithm by reducing a two-phase solver to only a one-phase solver (only phase 1 would be used until the cube is completely solved, no phase 2 operation being done at all), more hardware utilization would be neccessary in that case because a fast optimal solver requires significantly more computing resources than a fast suboptimal solver."

 

[Herbert Kociemba]

This is an advantage because in many cases it does not have to search the depth of the optimal solution length because it has already found a suboptimal solution at a lower depth that is equal to the optimal solution length, hence it only has to complete search depth N-1 to prove that solution length N is optimal.

Maybe I miss something but I do not see that this very remarkable. You can use any suboptimal solver to find some fairly short solution of length N and then obviously any optimal solver now only has to finish depth N -1 to show length N optimality.

While it is technically possible to search for an optimal solution using Kociemba's algorithm by reducing a two-phase solver to only a one-phase solver (only phase 1 would be used until the cube is completely solved, no phase 2 operation being done at all), more hardware utilization would be neccessary in that case because a fast optimal solver requires significantly more computing resources than a fast suboptimal solver."

This description is not very accurate. When you use only phase 1 to solve a cube optimally, you can apply phase 1 with the same pruning table in parallel in three different directions (UD, RL and FB). This gives a big perfomance boost.

And indeed, if you change the goal of the phase 1 from
all orientations of edges and corners solved + equator edges in their slice, pruning table takes about 33 MB.
to the 24 times smaller subgroup
all orientations of edges and corners solved + equator edges in place, pruning table takes about 24 x 33 MB, still less than 1 GB,
you get a very fast optimal solver. I implemented this method in my optimal Python cube solver (https://github.com/hkociemba/RubiksCube-OptimalSolver) because I was curious to know if a Python optimal solver would work at all.

So though I appreciate "Feather's Algorithm" as a solid framework for optimally solving a cube I still cannot see the advantage compared to a subgroup/coset based approach which from a mathematical viewpoint at least for me has a cleaner design.

 

[bcube]

Maybe I miss something but I do not see that this very remarkable. You can use any suboptimal solver to find some fairly short solution of length N and then obviously any optimal solver now only has to finish depth N -1 to show length N optimality.

You are not missing anything. If I am not mistaken, a complete search of depth N takes about 13.3 times longer for both Kociemba´s and Feather´s algorithm than a complete search of depth N-1. In fact, I have been asking whether this speed-up is possible for optimal Kociemba´s solver too, but so far I have got no answer. I find it quite a unique feature of optimal Feather´s solver in comparison with optimal Kociemba´s and Korf´s solver (Korf´s solver, however, is not designed to search for a suboptimal solution).

This description is not very accurate.

Feel free to tell me what is wrong with it. My thought process was following: when stating that Kociemba´s algorithm can find a 20 or less move solution in a fraction of a second, and it also can find an optimal solution, some readers might get an impression that it can find an optimal solution in a fraction of a second on their typical home computer. All I tried to express was that a user could either use the same hardware and it just takes significantly longer than a fraction of a second to find an optimal solution, or a user can use significantly more hardware to find an optimal solution in a fraction of a second. By computing resource I meant both hardware and time, more precisely hardware * time.

 

[Herbert Kociemba]

Feel free to tell me what is wrong with it.

There is nothing wrong. But the three axis in parallel search is a fundamental part of the phase 1 optimal solver. Without this, the solution would take way too long.

 

[bcube]

There is nothing wrong. But the three axis in parallel search is a fundamental part of the phase 1 optimal solver. Without this, the solution would take way too long.

Got it. I edited the last part from "a fast optimal solver requires significantly more computing resources than a fast suboptimal solver" to "a fast optimal solver requires significantly more computing resources than an equally fast suboptimal solver" to be more clear.

I think you got my point from my previous post. I took one scramble & solve (#5) from your optimal Python solver examples.

DBDBUFURUBLFBRLFFLFDRRFUBLDDDRBDURUUBDLDLFULRLRLUBFBRF
depth 15 done in 0.55 s, 1335570 nodes generated, about 2441181 nodes/s
depth 16 done in 7.5 s, 18770952 nodes generated, about 2502760 nodes/s
depth 17 done in 103.77 s, 260113815 nodes generated, about 2506756 nodes/s
depth 18 done in 1055.2 s, 2624360711 nodes generated, about 2487065 nodes/s
total time: 1167.05 s, nodes generated: 2904680714
L1 D1 L2 U2 F1 U1 D2 F2 U1 R1 F1 B1 R2 U3 R1 F1 U3 F3 (18f*)

As we can see, the search time at depth 18 takes more than a 90% of a total search time in this example. If a two-phase approach is implemented in Kociemba´s optimal solver, just like in Feather´s solver which found an optimal 17+1 solution, you might not need to search at depth 18 at all.

I do not see that this very remarkable

For this particular scramble, a 90% savings of the search time looks like a very remarkable feature to me.

 

[Herbert Kociemba]

Got it. I edited the last part from "a fast optimal solver requires significantly more computing resources than a fast suboptimal solver" to "a fast optimal solver requires significantly more computing resources than an equally fast suboptimal solver" to be more clear.

It is more complicated and the above does not make it clearer. The speed of a suboptimal solver depends on the qualitiy of the solution you want to have, so the expression "fast suboptimal solver" seems problematic. If you want let's say a solution <=22 moves, it usually will be found immediately. But take your example above. The suboptimal solver has to find a 18 move solution faster than the optimal solver to be helpful. This may happen, but it is in no ways guaranteed. In your example my algorithm finds a 19 move solution almost immediately, but it does not find a 18 move solution faster than the optimal solver (I stopped after 20 min without result).
So with my algorithm this does not work.
IF you can confim that with Feather's algorithm the suboptimal solver has a better behaviour and really is a shortcut to find optimal solutions, this would indeed be a progress.

 

[bcube]

the expression "fast suboptimal solver" seems problematic

Agreed. That is why I mentioned a time span of a fraction of a second ("A randomly scrambled cube would be typically solved in a fraction of a second in 20 moves or less...") to guide a reader what is meant by a "fast suboptimal solver" in this context.

IF you can confim that with Feather's algorithm the suboptimal solver has a better behaviour and really is a shortcut to find optimal solutions, this would indeed be a progress.

As a non-programmer, I can not tell you what is in the source code. I can only tell you my observations from a user interface (go ahead and make your observations too, after all the solver is online so anyone can use it).

On my crappy computer (so never mind the search times), this is what I see when using Google Chrome, choosing Solver 2, loading the 835 MB Dist3 file, changing Search Time from 5s to 500t, entering colors and hitting the Solve button:

Searching
Current Solution: 21 Moves
Current Solution: 20 Moves
Current Solution: 19 Moves
Current Solution: 18 Moves

39.56 17+1 W2
Optimal

Then in the shortened solve log, this is what I see:

Spoiler: Solve Log

Concurrent Processes = 4
Search Array Gen Depth = 10

Worker 1:
Depth 12 completed, 133 nodes, 0 / 0 tests
Depth 13 completed, 2338 nodes, 0 / 0 tests
R D L' F2 L U B2 L B2 R L2 F B' L B2 D2 L2 B' F R2 B' F' [14+8] (22f)
Depth 14 completed, 38440 nodes, 51 / 8 tests
R U L2 D' B U2 R' F' R2 B L F2 R2 B L' R2 D2 L2 F2 D2 U2 [15+6] (21f)
Depth 15 completed, 567193 nodes, 858 / 126 tests
Depth 16 completed, 7978342 nodes, 16791 / 2168 tests
R2 L' F U2 R2 D2 R2 D R B L D' L U' R' U F B2 F2 L2 [17+3] (20f)
R2 L' F U2 R2 D2 R2 D R B L D' L U' R' U F' B2 L2 [17+2] (19f)
Depth 17 completed, 107463697 nodes, 101325 / 12838 tests
39.56 Search Time

Worker 2:
Depth 11 completed, 19 nodes, 0 / 0 tests
Depth 12 completed, 256 nodes, 15 / 2 tests
Depth 13 completed, 2305 nodes, 51 / 4 tests
Depth 14 completed, 32260 nodes, 312 / 34 tests
F2 R2 F B U L B U B U2 D R' D' R B' R2 D2 L2 B2 R2 F2 D2 F2 [15+8] (23f)
U2 L2 F' D2 B' D2 L' U L F2 B2 L' U' D2 B' F2 L2 B2 R2 D2 B2 [15+6] (21f)
Depth 15 completed, 468313 nodes, 969 / 126 tests
F' R D2 F2 L B L' U R2 D B2 R' U2 D2 L F' L2 D2 F2 R2 [16+4] (20f)
Depth 16 completed, 6623509 nodes, 9864 / 1270 tests
F2 R' U R' B2 R2 L' U2 R2 B R' F' R D' F' D L B2 L2 [17+2] (19f)
U B U' R' F2 D R2 D R' D2 F R2 U F2 R' U' F' L2 [17+1] (18f)
Depth 17 completed, 91849453 nodes, 22296 / 2816 tests
35.09 Search Time

Worker 3:
Depth 12 completed, 83 nodes, 0 / 0 tests
Depth 13 completed, 1820 nodes, 0 / 0 tests
L B2 L2 F D' B2 D B' D' R' L U R2 D F2 R2 D2 F2 L2 F2 U2 [14+7] (21f)
Depth 14 completed, 31721 nodes, 174 / 26 tests
Depth 15 completed, 476369 nodes, 729 / 98 tests
Depth 16 completed, 6912152 nodes, 11073 / 1412 tests
D2 R2 U' F2 R' D L U R2 D B R' F L F2 U' R' U2 B2 F2 [17+3] (20f)
Depth 17 completed, 98085122 nodes, 133227 / 17146 tests
37.28 Search Time

Worker 4:
Depth 11 completed, 29 nodes, 0 / 0 tests
Depth 12 completed, 248 nodes, 0 / 0 tests
Depth 13 completed, 2624 nodes, 0 / 0 tests
Depth 14 completed, 37229 nodes, 228 / 36 tests
L2 D' B D' F' R' F2 L' B2 D B D L' D' R L2 U2 R2 D2 F2 R2 B2 U2 [15+8] (23f)
L2 F D' B2 R' B2 L' B R' F2 R2 B2 R' B2 U' L2 U2 L' R' D2 L R' [15+7] (22f)
L2 F D' B2 R' B2 L' B L' U2 R2 D2 L' F2 D' B2 L R F2 L' R' [15+6] (21f)
Depth 15 completed, 532667 nodes, 1101 / 152 tests
L2 D' F B U' L' D2 L' F' L U' R' F R D L B2 L2 U2 R2 [16+4] (20f)
Depth 16 completed, 7429256 nodes, 12267 / 1628 tests
B R' F2 D R2 D R' D2 F R2 B' U F2 B R' U' F' L2 [17+1] (18f)
Depth 17 completed, 99717425 nodes, 54291 / 7022 tests
37.74 Search Time

Although I would not formulate it as that with Feather's algorithm the suboptimal solver has a better behaviour and really is a shortcut to find optimal solutions - but go ahead with that if it makes a better sense for you to formulate it that way.

Here is a description how an optimal solution was found:

• at depths 0-13 no solution was found
• at depth 14 2 solutions were found, possibly worker 3 found [14+7] (21f) quicker than worker 1 found [14+8] (22f) - 21 moves shown as current solution
• at depth 15 some solutions were found but none of them is shorter than already found 21f from depth 14
• at depth 16 2 [16+4] (20f) solutions were found - 20 moves shown as current solution
• at depth 17 some solutions were found, I can not tell whether [17+2] (19f) was found quicker by worker 1 or worker 2 - 19 moves shown as current solution
• then worker 2 found a [17+1] (18f) solution quicker than worker 4, and completed the search of depth 17 in 35.09 seconds - 18 moves shown as current solution
• to prove an 18f solution from worker 2 is optimal, all remaining workers must complete the search of depth 17 (searching for a [17+0] solution which there isn´t any), the slowest one is worker 1 in 39.56 seconds - now it is proved that a [17+1] (18f) solution from worker 2 is optimal

Edit: for a reference, I tested the same setup in Cube Explorer. It finished searching depth 17 in 241 s, and found an optimal solution in 395 s on my machine.

 

[bcube]

For those who are interested: new test results for random 10,000 cubes solved optimally have been published. Statistics (can be found at the end of this log file):

Search Time: 18575.54 => average solve: 1.85 seconds

Average Search Time:
Moves    Avg     Max
----- ------  ------
  14    0.00    0.00
  15    0.01    0.02
  16    0.05    0.47
  17    0.39    2.05
  18    2.00   14.96
  19   11.38   21.43

Frequency Distribution:
Moves  Count  Kociemba  Rokicki
-----  -----  --------  -------
 14        2       1.8     1.72
 15       15      19.7    20.63
 16      297     271.0   264.48
 17     2670    2667.3  2670.27
 18     6644    6709.9  6704.07
 19      372     330.3   338.68
https://kociemba.org/moves20.htm

Speaking of test results, I wanted to know how many 18-movers are optimal in these 100 example solves.

Kociemba's implementation (Cube Explorer) is faster

Well, my computer can not handle the huge optimal solver in CE, therefore I used the default one. My computer can not also handle the 1.8 GB dist file, therefore I used the 835 MB one. (I know you have been talking about suboptimal solving while I am testing optimal solving)

Spoiler: CE log (1630 seconds = over 27 minutes)

Number of Cubes: 7
Cubes not solved yet: 0
---------------------------------------------------------------
Cubes solved optimally: 7

17f*: 4
18f*: 3
---------------------------------------------------------------
Cubes solved with Two-Phase-Algorithm: 0

---------------------------------------------------------------
Cubes with antisymmetry: 0
---------------------------------------------------------------

Spoiler: Solver 2 log (230 seconds = under 4 minutes)

Solver 2 Log:

Params: use_dist3=2&stl=500t&snc=1&log_brief=1&batch=1

Concurrent Processes: 4

Dist Files Loaded:
Dist1_09F.dat
Dist2_09F.dat
Dist3_10FQ.dat
Dist5_11F.dat
DistP2_15F.dat

Cube File Loaded:
scrambles.txt

Init Time: 2.02
1 U' L2 F B' U2 B R' U L F2 D' B2 R B D L B D2 [17+1] (18f*) 68.36
2 U2 D' R' L F' R2 F' L2 U' R U' L U' B' U2 B L' B2 [17+1] (18f*) 59.69
3 F' D2 R' F2 U L2 F L' D F' L F R F B D' L' [17+0] (17f*) 20.20
4 U2 B L' B' L' D2 F2 U R L' B' U2 R' D B' U' F2 R2 [16+2] (18f*) 62.50
5 B D' F U' F2 D2 R2 B' U B D' R F2 L' U2 B U2 [16+1] (17f*) 5.94
6 F L F L2 F2 D B' U D R B2 L2 D2 B D L2 F2 [15+2] (17f*) 7.56
7 R' F R2 B R' U' D2 L B2 L D' F B U2 B' L2 U2 [15+2] (17f*) 5.40
Search Time: 229.65

 

[qq280833822]

I think we should first reach a consensus that the speed of the solver is closely related to the size of the pruning table (that is, the memory usage). Generally speaking, if the size of the pruning table is doubled, the search time can be halved. Therefore, it is meaningless to compare two solvers when the pruning table sizes are too different.
When huge optimal is not enabled, the pruning table used by CubeExplorer is less than 0.03GB, which is more than 20 times smaller than 800M.

On the other hand, the performance of the solver is affected by many factors, such as the algorithm, the operating environment, the programming language, etc. Usually we pay more attention to the algorithm itself, because other factors are usually easy to change.
In order to measure an algorithm, I usually pay attention to the average number of visited nodes required to solve a state, multiply it by the time taken for each node, and then the average solution time for each node can be calculated.
Back to 3ColorCube, when I used Solver2, dist4, its pruning table was about 3GB in total, and the number of nodes required to visit to solve random state was about 280M.
In comparison, the average number of nodes for CubeExplorer with 2GB of memory is 230M.
Please note that the above data are objective and can be reproduced on any platform. They have nothing to do with the operating environment, but only with the algorithm itself. In terms of the number of nodes, Solver2 uses a pruning table that is 50% larger than CubeExplorer, but the number of nodes visited is 20%+ more than CubeExplorer.
As a more advanced solver, nxopt31 uses a 2.6GB pruning table and only needs to visit 70M nodes on average to solve a state.

Let's talk about the solving time. According to the previous inference, the average solution time is equal to the number of nodes multiplied by the average access time of each node. I ran it on my laptop, and the average time taken by the above solvers on a 6-core 12-thread CPU is basically around 20ns per node. By calculation, it can be seen that the average time they take to solve a random state is:
Solver2: 5.6s
CubeExplorer: 4.6s
nxopt31: 1.4s

The 10,000 states you mentioned earlier only take an average of 1.8s. I checked the runtime environment and it used a much larger pruning table (8GB), which is not comparable.

 

[bcube]

I think we should first reach a consensus that the speed of the solver is closely related to the size of the pruning table (that is, the memory usage). Generally speaking, if the size of the pruning table is doubled, the search time can be halved. Therefore, it is meaningless to compare two solvers when the pruning table sizes are too different.
When huge optimal is not enabled, the pruning table used by CubeExplorer is less than 0.03GB, which is more than 20 times smaller than 800M.

I thought we reached that consensus in the beginning of the discussion already.

I still remember your motivation for your optimal solvers analysis.

Don't get me wrong, computer science related data are nice to have, yet for average solver user like me a more tangible quantity would be better in my opinion - the search time works well for me. You see, this performance summary is perfect for me because all relevant data are there or being linked to - I can directly see what searching time is expexted for those testing conditions. Even if similar performance summary is made by another author, the problem is with a different platform or solver settings being used, so the test results are hardly comparable. I understand that it is impossible to accurately compare the solvers according to their search time, yet I still hope for such a comparison table for your specific test conditions in your analysis page.

Otherwise there will be statements about Huge Optimal Solver in Cube Explorer solving a random cube in seconds as well as minutes (they can be both correct without knowing details).

 

[qq280833822]

Otherwise there will be statements about Huge Optimal Solver in Cube Explorer solving a random cube in seconds as well as minutes (they can be both correct without knowing details).

I see. I missed the difference between throughput and latency in the previous discussion.
Throughput refers to the overall efficiency of solving a set of cubes when I have enough cubes (for example, 1,000) to solve.
Latency refers to how long I have to wait to get a solution when I only have one cube.
Most current software does not do multi-threaded optimization for single states. Specifically, when my CPU has multiple cores, the latency of a single cube does not decrease, but it can solve multiple cubes at the same time.
Take CubeExplorer as an example. Its average latency for each cube is 1 minute, and I have a 6-core 12-thread CPU, so I can solve 12 cubes at the same time, which means that I get the optimal solutions for 12 cubes respectively in this 1 minute, which is about 5 seconds per state. But from the user's experience, it takes 1 minute to solve each state.
Solver2 can use multiple threads to solve the same state, which is reflected in the low latency, but because all threads are used to solve the same state, it cannot solve two states at the same time, so although the latency is low, the throughput is not as good as other optimal solvers.

Another question is, if users care about latency rather than throughput, does that mean Solver2 has an advantage?
I would like to point out that this is only an advantage of Solver2 as a product, not an advantage of Solver2 algorithm. Technically, any IDA*-based solver can be easily changed to use multiple threads to solve the same state, such as nissy (or h48). If we have the ability to modify the source code of CubeExplorer and compile it, it can be changed to a delay of about 5s per state. It does not do that currently because it is usually designed to solve a large number of cubes (for example, kociemba solved 100,000 before), and the same is true for other solvers.

 

[bcube]

Well, as a user I don't really care how many processors are being used for solving how many cubes at once - all I care about is the resulting search time (and before using a solver I care about its RAM size requirement (i.e. whether I can run it or not on my machine) and its initialization time).

From a statistical point of view, I would like to see test/tests for a larger amount of cubes (say, 1000 or 10000 or even 100000) rather than for a single cube anyway.

Technically, any IDA*-based solver can be easily changed to use multiple threads to solve the same state, such as nissy (or h48). If we have the ability to modify the source code of CubeExplorer and compile it, it can be changed to a delay of about 5s per state.

To me, it makes sense to use unmodified solvers for testing - just as their authors intended to be used. But go ahead and do whatever modification you like in your testing.

 

[bcube]

By the way, I just realized that aside from optimal 3-color cube solver and optimal 6-color cube solver there is also an optimal 6-color cube presolved as 3-color cube solver (optimal 3-color reduction solver if you will).

Just for the sake of completion, there is also a modified version of the solver here which has no move limitation in phase 2. Therefore its solving process is genuinely: Scrambled cube -> 3-color cube reduction -> Solved cube.

Cubers using csTimer already know how fast is min2phase.js by Shuang Chen, the solver powered by min2phase.js can be found here.

 

[bcube]

In a two phase algorithm you always cut the phase 2 length to some suitable length. If you take 7, 8 or 9 is not really relevant.

correct me if I'm wrong, but is phase 1 basically the same as half-turn reduction?

Just for the record of why at most 8 moves in phase 2 had been chosen: I have been talking to Michael Feather and he stated that his solver has always worked by reaching a 3-color cube solved state in phase 1 and the fact that he chose to limit to 8 moves in phase 2 had nothing to do with HTR, it was done because generating beyond 8 moves starts to noticeably increase initialization time and there is minimal downside to limiting because the only solutions that are eliminated are the longer ones. He said he did a lot of testing of setting the limit to various lengths above 8 and concluded that 8 was the best tradeoff in terms of initialization time vs solution length. Whether or not anyone agrees with his choice of an 8 move limit is no reflection on his solving method which is perfectly capable of working with any length for phase 2, up to and including the max length of 16 (shown in this post) which is exactly what the solver does as shown in my previous post. The fact that his choice of 8 had the incidental side-effect of providing HTR solutions is also no reflection on his or anyone else´s solving method, it is an inherent property of the cube.

 

[bcube]

From what I remember, there are no <=8 movers that can turn an HTR case into a fake HTR case (feel free to disprove that, if I remember incorrectly. In that case nvm this response).

All 117,265 configurations can be solved using only half-twists.

My answer was based on experimental outcome by checking all 117 265 configurations and seeing if they can be solved using half-turns only. However, there is a much easier proof - see the second table.

How long does it take to compute these numbers? or in other words, how long to run the code on a normal PC?

No idea because I haven´t been generating any of these numbers. All I did was gathering them from various sources and putting them into one place.