# 5x5x5 Brute Force Solving Program



## unsolved (Mar 17, 2015)

*Thread closed*:
This thread has been closed as requested by unsolved
---

I guess the only question is, what notation system should this use?








*Latest version is always here:* lightningcloudcomputing.com/cubes/OO_5x5x5.zip


----------



## Chrizz (Mar 17, 2015)

unsolved said:


> I guess the only question is, what notation system should this use?



Just 1 question? I have more.

Is this program finished yet?
How long does it take approximately to solve a cube?
Is this available for download?
Does it always solve it in the least number of moves?
What does the name of the program mean?


----------



## Lucas Garron (Mar 17, 2015)

unsolved said:


> I guess the only question is, what notation system should this use?



Awesome, because your only question has a good answer!

Is this available yet?


----------



## unsolved (Mar 18, 2015)

Chrizz said:


> Is this program finished yet?



It is functional and it works. "Finished" can mean a few things. Will it solve a 5x5x5 cube in a reasonable amount of time: yes. "Finished" as in am I done making changes to it; no. I never really finish a program, I constantly tweak, improve, and add features to just about everything I have ever written.



Chrizz said:


> How long does it take approximately to solve a cube?



I have two modes: *Brute Force* and *Stage Solving*. Brute Force finds the shortest path to a solution, but if you don't have at least 6 processors, be prepared to wait a long time for > 7 moves. By a long time I mean 24 hours. Stage Solving is still in its infancy since I am learning better ways to code it. Stage Solving can complete a cube solve in roughly 10% fewer moves than some of the move counts I have seen on here, but sometimes it will hit 150 moves or more when it struggles. Right now a stage solve takes 24-36 hours. But, remember, I have not optimized this code yet.



Chrizz said:


> Is this available for download?



You won't understand the notation. I use things like *T+* to mean *U* and *r-* to mean a single slice move of the right slice counterclockwise. I use *z+* to mean your *E'* and *Z+* is for rotating the cube "in your hands" about the equator. I can't make sense of *M*, *E*, and *S* slice turn designations. It's mostly foreign to me. Why use capitals for outer face turns and the middle slices? The middle slices should be lower case in my opinion. So that is why I was asking for "what notation system" you guys want to use. I will have to convert my output to that format.

I have the 4x4x4 version available for download here and I'll build a page for the 5x5x5 when I get a sense of which notation system to support.* I only want to do the move notation conversion once, so I will need some convincing.*



Chrizz said:


> Does it always solve it in the least number of moves?



In *Brute Force* mode, yes.



Chrizz said:


> What does the name of the program mean?



*Omnia Obtorquebantur* is Latin for "All will be turned" literally, or in the case of this cube, "everything will be tried."





Lucas Garron said:


> Awesome, because your only question has a good answer!
> 
> Is this available yet?



Once I convert the notation output, it will be.

I would like to request that some 5x5x5 SiGN algos with scrambles and full solutions to your awesome web page be listed here so I can get a sense of the notation. Include algs with every move you want supported, e.g. *2L'* and *M* (ugh!) and what not. I want to make sure I "get it right" because the conversion will be painful to me


----------



## Lucas Garron (Mar 18, 2015)

unsolved said:


> You won't understand the notation. I use things like *T+* to mean *U* and *r-* to mean a single slice move of the right slice counterclockwise. I use *z+* to mean your *E'* and *Z+* is for rotating the cube "in your hands" about the equator. I can't make sense of *M*, *E*, and *S* slice turn designations. It's mostly foreign. Why use capitals for outer face turns and the middle slices? The middle slices should be lower case in my opinion. So that is why I was asking for "what notation system" you guys want to use. I will have to convert my output to that format.



You don't really need M/E/S. SiGN is pretty simple if you know Singmaster (U/F/R/B/L/D for face turns, along with ' for inverses and 2 for double turns).

All you *really* need is lowercase block turns like "3-5r". That means "take slices #3 through #5 from the right, and turn them like R". Similar for the other 5 sides.



Spoiler



And there are a few convenient simplifications:

5R means 5-5R (or replace any other number for 5) for single slices.
R means 1R (same as 1-1r).
5r means 1-5r (or replace any other number for 5) for blocks that extend to an outer layer.
r means 2r (same as 1-2r).
And if you don't like lowercase block turns, alg.cubing.net will allow Rw instead of r'. See this for all supported notation.



Pretty much all speedcubers (and, by extension, theory folks who interact with the speedcubing community) use this now. See the link above for details.


EDIT: unsolved, I accidentally overwrote and deleted your previous post (first time I've done this after years of moderation). I'm sorry, but I don't know of a way to recover the original content.


----------



## unsolved (Mar 18, 2015)

Lucas Garron said:


> Pretty much all speedcubers (and, by extension, theory folks who interact with the speedcubing community) use this now. See the link above for details.



OK I am giving it a try, but I must be doing something wrong. I gave the program this position to process a while ago:






...and it started spitting out stuff like this:






...so I will have to investigate how I am implementing multiple block turn moves now. I use a *Compound Move Generator* to speed things up (turning two slices at a time is executed as one function call instead of calling each one at a time) and this complicates things a bit.

I would still like something a little more explicit than "see the link above," I would like to see animated examples of some of these moves. Like I said, converting from my existing notation to another one is not going to be easy because of my Compound Move Generator. If it's not clear to me 100% how to do the move notation conversation, I probably won't chunk out the time to bother with it. Show me how it's done, and I'll gladly work it out.


----------



## qqwref (Mar 18, 2015)

Go find a beginner's tutorial for 3x3x3, AKA the first video anyone learning to solve a cube will watch. That will explain the URFBLD notation. Now all you need for 5x5x5 is to understand that a number in front of a letter means to go that many slices deep. If U is the top face, then 2U is the slice under that, and 3U is the one under that. 3U and 3D' are the same exact move, so choose the one you prefer.

Stage solving takes 24-36 hours? That's a little ridiculous. What method (solving order) is it using?


----------



## unsolved (Mar 18, 2015)

qqwref said:


> Go find a beginner's tutorial for 3x3x3, AKA the first video anyone learning to solve a cube will watch. That will explain the URFBLD notation. Now all you need for 5x5x5 is to understand that a number in front of a letter means to go that many slices deep. If U is the top face, then 2U is the slice under that, and 3U is the one under that. 3U and 3D' are the same exact move, so choose the one you prefer.



I am already aware of that notation, but there seems to be no *consensus*. Ambiguity cannot be resolved by a search engine. There can be only one way to generate a resulting position, or else the amount of time spent examining duplicate positions rises sharply and the search depth stalls.

What I don't understand is what moves/groups of moves are considered "just one move." I need a list of every legal move possible from a solved cube, and how to describe it, and what layers it moves, and then I can give it to the program. Right now I have 45 possible moves.



qqwref said:


> Stage solving takes 24-36 hours? That's a little ridiculous. What method (solving order) is it using?



On middle-of-the-line hardware, with a single core, to examine the number of nodes required to complete a solve, and have a reduced move count, I assure, that is an excellent time. There's 45 moves per ply, so multiply 45 x 45 x 45 x 45 a few more times and see how large the search space becomes.

*On my 16-core machine the search speed is over 500,000,000 moves/second* but most people don't have access to this kind of hardware. So I computed how long it would take on a machine the person posing the question might have.

And, as I mentioned, there are presently NO OPTIMIZATIONS for this program. Recall my 4x4x4 program was very slow initially but now it can handle 18 move solutions in about 2 days.


----------



## unsolved (Mar 18, 2015)

qqwref said:


> Everyone agrees on it but you!



I needed to start somewhere. I chose something that made sense to me, just for my own curiosity.



qqwref said:


> If you're doing brute force this ludicrously naively, then of course it's going to take forever!



I am not, that was just an example to give you an idea as to the size of the problem. Here is the true number of 5x5x5 positions as a function of depth:

1 = 45
2 = 1,620
3 = 57,510
4 = 2,042,415
5 = 72,536,229
6 = 2,576,111,040
7 = 91,490,126,940

91 billions positions @ depth 7 is a compelling reason why a deep search to find improved play takes so long. I can write a Monte Carlo version of the move generator to find a solution that takes less than 5 seconds. It will be 300 moves or longer. To find optimal and near-optimal solutions take much longer, and that is the focus of the project.

You are not helpful and your conclusions about what I wrote are entirely incorrect. I was just asking for examples for compound moves, such as cases where 2 (or more) parallel slices are moved at once and considered one move. I have seen two and sometimes 3 slices moved at once, and just needed clarification before I evoke the move generator to do the same.

Just for future reference, I elect to ignore every post you make. I won't respond to you.


----------



## Brest (Mar 18, 2015)

unsolved said:


> I would like to see animated examples of some of these moves.



Wide and slice move examples using SiGN notation: alg.cubing.net

Also full solves here: http://www.cubesolv.es/?query=5x5


----------



## Herbert Kociemba (Mar 18, 2015)

unsolved said:


> I have two modes: *Brute Force* and *Stage Solving*. Brute Force finds the shortest path to a solution, but if you don't have at least 6 processors, be prepared to wait a long time for > 7 moves. By a long time I mean 24 hours.



Hmmm, I do not think it makes any practical difference if you have 1 processor, 6 processor or 1,000,000 processors if you use your brute force solver. Because it will not be able to solve at all any reasonable interesting position, not to mention a random position.


----------



## unsolved (Mar 18, 2015)

Herbert Kociemba said:


> Hmmm, I do not think it makes any practical difference if you have 1 processor, 6 processor or 1,000,000 processors if you use your brute force solver. Because it will not be able to solve at all any reasonable interesting position, not to mention a random position.



I was just answering the question posed by someone else.

You can test to see how long a single core takes to get to depth using this version of the program:

lightningcloudcomputing.com/cubes/OO_5x5x5.zip



Brest said:


> Wide and slice move examples using SiGN notation: alg.cubing.net
> 
> Also full solves here: http://www.cubesolv.es/?query=5x5



*PERFECT!*

Thank you, that's all I was asking for.

*Edit: And now, a question.*

In this solve...

Felix 5x5x5 solve

...I saw that Felix made moves such as *3l* and* 3r'*. These are moves that my program, at present, disallows for move generation. The reason being, *3l* is the same as *r* followed by rotating the cube in hand. Should I allow the program to make such moves when executing solves?


----------



## ch_ts (Mar 18, 2015)

I would suggest only moves that don't move the centers, so 2r or 2l instead. (Or 2R or 2L if you're using single slice moves)


----------



## rokicki (Mar 18, 2015)

Howdy!

I applaud your efforts; a 5x5x5 optimal solver is a bold undertaking!

Are you using any pruning tables? Care to describe them if so?

Can you describe your staged solver? What are the intermediate goals?

I tend to start with OBTM (that is, a move is one that turns a contiguous
set of layers that includes one face). For the 5x5x5, that would cut
your naive branching factor from 45 down to 36, while still permitting
all positions to be reached. But I understand there are advantages to
the STM (single slice turn metric, which *appears* to be what you are
using), especially for some sorts of pruning tables.

You might try your solver on some last-layer positions and see if
there's anything interesting it might find that isn't already well known,
much like you (indeed, we!) did on the 4x4x4.

You might download and run the WCA scrambler and check out what's
already available. Any interoperability you can provide with that
is useful for checking/validating results.

I (with everyone else) strongly encourage you to accept SiGN. Note
that you should read *all* SiGN moves (since positions may be given
as SiGN), even if your search program uses a different metric when
solving.


----------



## unsolved (Mar 18, 2015)

rokicki said:


> Howdy!
> 
> I applaud your efforts; a 5x5x5 optimal solver is a bold undertaking!



Thanks! It's largely based on my 4x4x4 solver. I had to make the move generator
rely on two 64-bit data structures (instead of one in the 4x4x4) and that made things
a little complicated. I can generate each 5x5x5 move using 11 lines of C code or less.



rokicki said:


> Are you using any pruning tables? Care to describe them if so?



Not yet. I plan on corners-only pruning in the near future.



rokicki said:


> Can you describe your staged solver? What are the intermediate goals?



Stage 1: Face-turns only. Solve all corners. Score = 0 if unsolved.
Score = 1,000,000 if all corners are solved. This high score keeps
the program from unsolving them once they are solved.

Stage 2: Large bonuses for completing a "brick wall" from corner to corner.
Medium bonus if 2 wing edges solved correctly.
Small bonus if 1 edge solved correctly.
Bonuses for each matching center.
Fixed depth search (user configurable)
At the end, program makes the move sequence with the highest score.

Program then backs up one move, does the fixed search to the same depth.
If it finds a higher score, this is the new position to play from.
If not, retreat two moves from the previous high score, and do a search
1 move deeper than the prior fixed depth. Make the resulting move
sequence that is registered as this new high score.

Repeat this stage until reaching a "Last Layer" condition.

Stage 3: Without using any intelligence, blindly apply every pre-computed
alg in its array of algs. Score each one. Pick the alg with the greatest
change in score. Repeat until no algs are left.

Stage 4: Solve the remaining centers with brute force searches at fixed depths.




rokicki said:


> I tend to start with OBTM (that is, a move is one that turns a contiguous
> set of layers that includes one face). For the 5x5x5, that would cut
> your naive branching factor from 45 down to 36, while still permitting
> all positions to be reached.



Just to be clear, the move generator is not of this form. I used the 45^n 
example as an "order of magnitude" gauge for that other person to try and
understand why a stage solver on a slow machine with one processor might 
take 24 hours or more. On my hardware, it does not.

You can download my program here and see what the true depths are: 
lightningcloudcomputing.com/cubes/OO_5x5x5.zip

*EDIT:*

I think I successfully converted the program to *SiGN *notation. I instructed it to create a text dump of every position it would generate, up to 4 moves deep:

*Warning: 39 MB text file online. If you have a slow internet connection, this might hang your browser.*
http://lightningcloudcomputing.com/cubes/5x5x5_move_generator_output.txt

The basic move ordering is: Right to Left, Top to Bottom, Front to Back.

* R, R', R2, 2R, 2R', 2R2, 3R, 3R', 3R2, 2L', 2L, 2L2, L', L, L2 * ... and the equivalent for the *UD* and *FB* face pairs.

You might notice it starts with R and just moves one slice to the left each time. That means the L' moves get generated before the L moves, so that there is a uniform direction of movement on the cube surface.

The question is: Does the move generator properly eliminate all of the superfluous moves without pruning too many of them?

The first sequence at depth 3 = *R 2R 3R'* which effectively eliminated 3R since that would have been the 3rd consecutive move on the same axis in the same exact direction. This behavior was easy enough to code. But at depth 4, it gets a little more complicated. Now 4 moves on the same axis are permissible if only 2 of them are in different directions/distances. I'm not sure if I handled this case properly.


```
R   2R  3R' 2L  
 R   2R  3R' 2L2 
 R   2R  3R' L   
 R   2R  3R' L2  

...

 R   2R  3R2 2L  
 R   2R  3R2 2L2 
 R   2R  3R2 L   
 R   2R  3R2 L2
```

And at depth 5, the program disallows every turn on the same axis for the 5th time.


```
R   2R  3R' 2L  U   
 R   2R  3R' 2L  U'  
 R   2R  3R' 2L  U2  
 R   2R  3R' 2L  2U  
 R   2R  3R' 2L  2U' 
 R   2R  3R' 2L  2U2 
 R   2R  3R' 2L  3U  
 R   2R  3R' 2L  3U' 
 R   2R  3R' 2L  3U2 
 R   2R  3R' 2L  2D' 
 R   2R  3R' 2L  2D  
 R   2R  3R' 2L  2D2 
 R   2R  3R' 2L  D'  
 R   2R  3R' 2L  D   
 R   2R  3R' 2L  D2
```

Things don't get interesting until about ply 9, which is as far as I have looked into so far (for the obvious reason). After depth 4 I only save the first 10,000 moves at each depth. Here is how depth 9 begins...


```
R   2R  3R' 2L  U   R   2R  3R' 2L  
 R   2R  3R' 2L  U   R   2R  3R' 2L2 
 R   2R  3R' 2L  U   R   2R  3R' L   
 R   2R  3R' 2L  U   R   2R  3R' L2  
 R   2R  3R' 2L  U   R   2R  3R' U   
 R   2R  3R' 2L  U   R   2R  3R' U'  
 R   2R  3R' 2L  U   R   2R  3R' U2
```

There are no moves of L' present this early and I'm not sure if this is a mistake. The axis rotation counter resets on the occurrence of the U but I can't wrap my brain around why L' was filtered. I have been staring at this too long!

If the cases above are allowed, I think I have it implemented properly. If anyone knowledgeable in SiGN has some insight as the correctness/incorrectness, please let me know.

*EDIT #2:*

And now, 24 hours later, it is only finishing depth 9 and starting depth 10, using all 16 cores on my machine. So it looks like depth 10 might be the limit of reasonable brute force searching unless a remarkable pruning approach thins the search space.

The search begins with ...


```
R   2R  3R' 2L  U   R   2R  3R' 2L  U   
 R   2R  3R' 2L  U   R   2R  3R' 2L  U'  
 R   2R  3R' 2L  U   R   2R  3R' 2L  U2  
 R   2R  3R' 2L  U   R   2R  3R' 2L  2U  
 R   2R  3R' 2L  U   R   2R  3R' 2L  2U' 
 R   2R  3R' 2L  U   R   2R  3R' 2L  2U2 
 R   2R  3R' 2L  U   R   2R  3R' 2L  3U  
 R   2R  3R' 2L  U   R   2R  3R' 2L  3U' 
 R   2R  3R' 2L  U   R   2R  3R' 2L  3U2
```

... but I was curious to see how far down the first reappearance of the move *R* was...


```
R   2R  3R' 2L  U   R   2R  3R' U   R   
 R   2R  3R' 2L  U   R   2R  3R' U   R'  
 R   2R  3R' 2L  U   R   2R  3R' U   R2  
 R   2R  3R' 2L  U   R   2R  3R' U   2R  
 R   2R  3R' 2L  U   R   2R  3R' U   2R' 
 R   2R  3R' 2L  U   R   2R  3R' U   2R2 
 R   2R  3R' 2L  U   R   2R  3R' U   3R  
 R   2R  3R' 2L  U   R   2R  3R' U   3R' 
 R   2R  3R' 2L  U   R   2R  3R' U   3R2
```

Not too far as it turns out.

I will be building some new hardware in April with a Quad Socket motherboard and 15-core Intel CPUs. We'll see how the program does running on 60 very fast cores.

*Edit #3: Screen shot requested.*






*Edit #4: Good news, bad news.*






The program now completes an 8-ply search in 17 seconds. But something crazy is going on in depths 1-7. Hmmmmm.


----------



## unsolved (Mar 28, 2015)

*Edit #5: Everything fixed and running pretty fast now*






I'd like to know if any of the above algs are improvements to known 5x5x5 algs.


----------



## Christopher Mowla (Mar 28, 2015)

unsolved said:


> I'd like to know if any of the above algs are improvements to known 5x5x5 algs.


This is such a well-known position that I'm sure all of these 10 ply algorithms have been found several years ago. (All, of them can be found by single piece isolating commutators and shifting and/or conjugating them.)

It might be of your interest to go visit http://www.mementoslangues.fr/->"Cube Design"->"Cube Algorithms". For 3-cycles of wing edges, see "stats_threecycles_edges.txt". The move sequences are in superset notation: you can view the algorithms in CubeTwister.

I doubt any last layer algorithms < 13 ply have not been found already been found by someone or a solver, so I think it might be best for you to look for positions which require 13 or more ply to perchance find new move sequences.


----------



## unsolved (Apr 1, 2015)

Herbert Kociemba said:


> Hmmm, I do not think it makes any practical difference if you have 1 processor, 6 processor or 1,000,000 processors if you use your brute force solver. Because it will not be able to solve at all any reasonable interesting position, not to mention a random position.



Well almost 2 weeks ago I gave the source code to a parallelization subject matter expert who works for a well known company in the supercomputer sector (a competitor, in fact, but we are friends). He asked me to explain a few things in the memory management code where the Turns-From-Solved databases were being built. I re-wrote a calling function to take a big chunk of RAM and build the largest database that could fit into RAM without too many collisions in the hash table. So he calls me back and said "It's trying to solve the 10-TFS database for the 5x5x5 cube, what is taking so long?" and I tried not to laugh. Their hardware cluster of 2,048 processors had something like 64 Terabytes of RAM so the program basically took over most of the cluster. I had given him fair warning though! 

All this time I thought he just killed the process and stopped running the program, but no! It was still trying to solve a 26-turn scramble! Apparently his firm was impressed with the way his implementation split out and managed all of the sub processes, so they went full tilt and let it run on even more CPUs. As of tonight, it found a solution at depth 15 that hit the 10-TFS database for a 25-turn solution (and therefore an improvement!) on the scramble.

The 26 move scramble and 25-turn solution:

https://alg.cubing.net/?puzzle=5x5x5&alg=R2_U_2F2_U_2F-_3F_U_3F_R2_U2_3F-_U_3F-_2F_U_R2_2B_U2_2F_U2_2B-_U2_2F2_U-_R2&setup=R2_U_2F2_U2_2B_U2_2F-_U2_2B-_R2_U-_2F-_3R2_U2_3R_U-_R2_U_3R-_U2_3R2_2F_U-_2F2_U-_R2


----------



## rokicki (Apr 9, 2015)

On the 5x5x5 you might consider using additive pruning tables.

Especially in the single-slice-turn metric.

This should give you a several-ply advantage.

As an example, use the simpler 3x3x3 pruning table for slice-turn
metric for the eight corners, six centers, and 12 middle edges.
These are only affected by face turns and central slice turns.
This will probably give you a depth-10 or so table.

Add to this a simple matchup count on the diagonal middle pieces.
These are only affected by non-central slice turns and do not
affect the corners, centers, or middle edges; this should give you
typically an additional three moves.

These are additive, so you end up with a typically-depth-13
table.

Combine this with an overall-matchup-count or your 6-TFS
to take care of positions that are okay in each individual
additive component but not when taken together.

You're still a long way from solving random positions, this way,
but you'll end up with a more effective solver for the positions
you can solve.

This is only one example of additive pruning tables; I'm sure
you can think of other ones, and perhaps significantly more
effective ones.


----------



## unsolved (Apr 9, 2015)

rokicki said:


> On the 5x5x5 you might consider using additive pruning tables.
> 
> Especially in the single-slice-turn metric.
> 
> ...



I've been toying with the idea of independent corners/edges/centers. I've already seen how a "reverse centers" database makes the final cage-solving stage instantaneous because the completely caged cube is a closed set. I have all solutions for 8-turns where only the centers are unsolved, but I can cascade them and get wicked-fast solves without calling the move generator. I probe the databases linearly from index 0 to the last entry, blindly apply the solution at rates of 50,000,000 per second, and just test to see if the cube gets solved. I chain together the move sequences: *centers_04* + *centers_05* solves every cube 9 turns from being solved once the cage is built; *_04* + *_06* && *_05* +* _05* == every 10-turns from solved state, etc. I can chain all the way up to 16-turns from solved by applying every *_08* + * _08* solution in tandem.

I've also been playing around generating some 5x5x5 centers algs that might not be known.

Examples:
















You can see I am completing depth 11 in seconds and finding depth 12 solutions in under 2 minutes now. I am kind of pleased with these single-core, no corner pruning at all results 

Makes me wonder how the performance will jump with the pruning tables added.


----------



## Carrot (May 3, 2015)

This thread has been closed with respect to unsolved's wish.


----------

