# My 4x4x4 optimal solver



## cuBerBruce (Apr 17, 2014)

Attached is a zip file containing my first public version of my 4x4x4 optimal solver. I'm calling it Version 0.5. It is limited in how deep it can go in a reasonable amount of time, so if you give it a "random" position, it's almost certain it won't be able to find a solution in the amount of time you are willing to wait. It is for Windows systems.

This executable supports single slice turn metric only, meaning you can move only a single layer at a time for a move to be counted as a single move. Scrambles must also be entered as single-layer moves using Singmaster convention (a lower case letter means a turn of a single inner layer). A facelet description can also be used using the same format as my five-step solver.

The first time it starts, it generates pruning tables in the working directory. (To avoid this on later starts, make sure you always invoke the program from the same working directory. These pruning tables require about 27 MB of disk space. They may take awhile to get generated.

The program uses the following heuristics for pruning.
1) a value determined from a corner database added to a number based upon the number of formed dedges.
2) a value determined from a pruning table for the U/D center pieces and the DLB corner.
3) A certain set of positions known to require at least 13 moves is also used.

If invoked with argument "-t", it will uses the "title" system command to put status information in the title bar of the command window. This assumes such a command exists on the system.

Update: I now have a version for outer block turn metric (OBTM).

Update 2: I now have a block turn metric (BTM) version. This needs 1.5GB of RAM, and pruning tables may take several hours to generate.


----------



## Jakube (Apr 17, 2014)

Nice programm. 

Haha. I tried 2 scrambles so far, a T-Perm (11 moves) and a 10 move center case. The solution for the T-perm appeared immediately, while it took quite a while, too find a solution for the "shorter" center case. I guess, center pruning is quite hard.


----------



## cuBerBruce (Apr 17, 2014)

Jakube said:


> Nice programm.
> 
> Haha. I tried 2 scrambles so far, a T-Perm (11 moves) and a 10 move center case. The solution for the T-perm appeared immediately, while it took quite a while, too find a solution for the "shorter" center case. I guess, center pruning is quite hard.



Yes, my center-based pruning is not all that good, and I don't apply it to all three opposite faces. You should at least be sure to involve as many U/D center pieces out of place as possible. T-perm on the other hand, has two swapped corners, and it takes 10 moves to swap them back (canonical A-Perm + AUF; or canonical J-perm), providing excellent pruning.


----------



## Christopher Mowla (Apr 18, 2014)

Bruce,
Does this find all optimal solutions, or does it quit after a certain amount of time?


----------



## cuBerBruce (Apr 18, 2014)

cmowla said:


> Bruce,
> Does this find all optimal solutions, or does it quit after a certain amount of time?



It searches for all optimal solutions, except it doesn't necessarily display variants of what are essentially the same solution. It saves time, for instance, by not trying both (U u) and (D d). It currently doesn't have an option to stop when the first solution is found. You can ctrl-C, of course, but it's not trapped, so you'll have to restart the program if you do. It will run as long as you let it, if no solutions have been found. Of course, this executable supports single slice turn metric, so optimality is only in terms of that metric.


----------



## Christopher Mowla (Apr 18, 2014)

cuBerBruce said:


> It searches for all optimal solutions, except it doesn't necessarily display variants of what are essentially the same solution. It saves time, for instance, by not trying both (U u) and (D d). It currently doesn't have an option to stop when the first solution is found. You can ctrl-C, of course, but it's not trapped, so you'll have to restart the program if you do. It will run as long as you let it, if no solutions have been found. Of course, this executable supports single slice turn metric, so optimality is only in terms of that metric.


Thank you Bruce for releasing this. It seems to still output variants of the same algorithm for sure (especially if the inputted algorithm had M moves or Uw2), but I have been testing it on 9-12 move sequences, and it's impressive!


----------



## cuBerBruce (Apr 18, 2014)

cmowla said:


> Thank you Bruce for releasing this. It seems to still output variants of the same algorithm for sure (especially if the inputted algorithm had M moves or Uw2), but I have been testing it on 9-12 move sequences, and it's impressive!


OK, I think I might only avoid commuting moves coming out in different order in this single-slice turn metric. I think my unreleased block turn version is a bit smarter (but still not perfect) in avoiding different ways of generating each of the possible 63 different "axis turns" on each axis.


----------



## cuBerBruce (Apr 23, 2014)

I now have a version of my optimal solver supporting outer block turn metric. The solver uses wide turn notation, as in Uw, Rw', etc. When entering a scramble, the wide turn notation is also accepted with this version.

I will keep the first post of the thread updated with the latest versions.


----------



## unsolved (Apr 23, 2014)

cuBerBruce said:


> I now have a version of my optimal solver supporting outer block turn metric. The solver uses wide turn notation, as in Uw, Rw', etc. When entering a scramble, the wide turn notation is also accepted with this version.
> 
> I will keep the first post of the thread updated with the latest versions.



Hi Bruce,

I gave them both a side-by-side test today:







I thought the program with the block turn metric would be able to solve it faster than the other program, since I entered about 5-ply worth of "block turns" on the scramble (as single turn moves).

Although it was a 14-ply scramble it should be able to be solved in 9 plies with a Block Turn Move Generator (I think).

Seems pretty fast on my machine. Nice job.


----------



## cuBerBruce (Apr 23, 2014)

unsolved said:


> Hi Bruce,
> 
> I gave them both a side-by-side test today:
> 
> ...



Your scramble is obviously solvable in 8 block turns. However, the "OBTM" program is not for (arbitrary) block turns, but *outer* block turns only. The scramble u' d requires 2 outer block turns to solve. So does the scramble u'. Thus, your scramble is not obviously solvable with less than 10 outer block turns.


----------



## unsolved (Apr 23, 2014)

cuBerBruce said:


> Your scramble is obviously solvable in 8 block turns. However, the "OBTM" program is not for (arbitrary) block turns, but *outer* block turns only. The scramble u' d requires 2 outer block turns to solve. So does the scramble u'. Thus, your scramble is not obviously solvable with less than 10 outer block turns.



Hey Bruce,

I took a closer look at your corner hash table code yesterday. I found a way to get to your exact corner position without having to probe the hash table and search while your "empty slot" condition of 99 isn't found. If you are interested, I can show you code how to access your corner permutation exactly, with 0 wasted entries, at 1 byte per entry. It's very fast.

I'll trade you that code for the code you use to parse a user's text entry for doing a scramble. I always hated parsing with scanf() and junk like that.

Deal?


----------



## cuBerBruce (Apr 26, 2014)

unsolved said:


> Hey Bruce,
> 
> I took a closer look at your corner hash table code yesterday. I found a way to get to your exact corner position without having to probe the hash table and search while your "empty slot" condition of 99 isn't found. If you are interested, I can show you code how to access your corner permutation exactly, with 0 wasted entries, at 1 byte per entry. It's very fast.
> 
> ...



OK, let's say you want to store 30,000 entries out of a possible state space of 88,179,840 states. You have some better way of doing that without allocating more than 30,000 elements for the table? I rather doubt it.

The point was to illustrate my *hashing scheme*, and I used a corners-only puzzle as just a simple example. The hashing scheme is quite fast. If you allocated enough entries in the hash table, most of the time you hit the element you're looking for on the first try, or you find an "empty" entry on the first try if you're adding a new element or looking for an element that's not in the table. Unless the hash table gets nearly full, you generally only end up checking a few entries worst case.

In any hash table where you can't guarantee a unique hash index for every possible element, you have to have some scheme of resolving hash conflicts. This is generally supported by either rehashing (what I'm using) or using "buckets."

By the way, I didn't mention that my hashing scheme does not support deleting elements (at least, as is). You can't simply replace the "deleted" element with an "empty" element, or you could end up hitting that "deleted" element when rehashing for some other element resulting in thinking that element is not in the table when it really is.

I will PM you my code for parsing scrambles or a scrambled position in a little while.


----------



## cuBerBruce (Apr 27, 2014)

I now have a version of my 4x4x4 solver for the block turn metric (version 0.52). This version uses a very large pruning table, so you basically need to have at least 1.5GB of RAM to use it. It will probably take several hours to generate the pruning table. The pruning table considers a 3x3x1 block, and the pruning table is used three ways, for DLB, URF, and FLD. It also uses two opposite center groups (with respect to a corner), and a corners pruning table. The program will also try to store 1.4GB worth of files so the pruning table data only has to be generated once.


----------



## unsolved (Apr 28, 2014)

cuBerBruce said:


> I now have a version of my 4x4x4 solver for the block turn metric (version 0.52). This version uses a very large pruning table, so you basically need to have at least 1.5GB of RAM to use it. It will probably take several hours to generate the pruning table. The pruning table considers a 3x3x1 block, and the pruning table is used three ways, for DLB, URF, and FLD. It also uses two opposite center groups (with respect to a corner), and a corners pruning table. The program will also try to store 1.4GB worth of files so the pruning table data only has to be generated once.



Hi Bruce,

I downloaded it, let it run for a while and do its builds. Once I saw the prompt, I entered the 15-ply single dedge flip you showed me. It wrote out the time, then no other output.






FYI.


----------



## cuBerBruce (Apr 28, 2014)

unsolved said:


> Hi Bruce,
> 
> I downloaded it, let it run for a while and do its builds. Once I saw the prompt, I entered the 15-ply single dedge flip you showed me. It wrote out the time, then no other output.
> 
> ...



My program displays progress status through the system "title" command. You have to use -t command line option because I don't think one can necessarily count on the Command Prompt window recognizing the "title" command on all Windows systems, and you'll tend to get a lot of annoying error messages if it's not.

Even so, the dedge flip will start at a depth 13 search, and that's so deep you will probably see "depth 13 move 0" and never see it update to "depth 13 move 1" because that is pretty deep for my program, especially the BTM version. And my pruning function don't provide really great pruning for that starting position. I note that the BTM version considers 54 different moves, not a mere 36, so the time increases much quicker with depth than the single slice turn metric version.


----------



## Christopher Mowla (Apr 29, 2014)

cuBerBruce said:


> I now have a version of my 4x4x4 solver for the block turn metric (version 0.52).


Thanks Bruce! I will have to try this out soon. Is it, by any chance, possible to make a BQTM solver with the same (or less, now that you have already programed a BHTM solver) effort? If so, then maybe unsolved could run it on his powerful machine to find the set of optimal solutions for the single dedge flip case (I found 7 distinct 19q algs for the 4x4x4, so if an 18q or 17q exists, there won't be many solutions)! I bet many people, not just me, would be interested to see proof that my algs are optimal for this position! (Just kidding, I hope there is an 18q or even a 17q to prove me wrong, although right now, I just can't see that happening).


----------



## cuBerBruce (Apr 29, 2014)

cmowla said:


> Thanks Bruce! I will have to try this out soon. Is it, by any chance, possible to make a BQTM solver with the same (or less, now that you have already programed a BHTM solver) effort? If so, then maybe unsolved could run it on his powerful machine to find the set of optimal solutions for the single dedge flip case (I found 7 distinct 19q algs for the 4x4x4, so if an 18q or 17q exists, there won't be many solutions)! I bet many people, not just me, would be interested to see proof that my algs are optimal for this position! (Just kidding, I hope there is an 18q or even a 17q to prove me wrong, although right now, I just can't see that happening).



I'll try to look into this. I think the main effort would be in developing the pruning scheme based on move history. Still, 17q might likely be out of reach for my present level of performance that I'm achieving.


----------



## unsolved (Apr 29, 2014)

cmowla said:


> I bet many people, not just me, would be interested to see proof that my algs are optimal for this position!



My favorite is still this one:

http://alg.garron.us/?cube=4x4x4&no...Lw+Uw'+Lw2'+Bw'+r'+Bw+Rw'+R'+u+y'+M'+Uw+x2+z'

I don't care if I find a 13-ply shortcut, I'll still execute the algo above


----------



## Christopher Mowla (Apr 29, 2014)

cuBerBruce said:


> I'll try to look into this. I think the main effort would be in developing the pruning scheme based on move history. Still, 17q might likely be out of reach for my present level of performance that I'm achieving.


Thanks Bruce. I know we are all busy, so please don't let this distract you from what you're currently trying to accomplish, but if you ever get time to do it, that would be great. If 17q or 18q depth searches are too complex at the moment, I completely understand. I just thought I would ask.



unsolved said:


> My favorite is still this one:
> 
> http://alg.garron.us/?cube=4x4x4&no...Lw+Uw'+Lw2'+Bw'+r'+Bw+Rw'+R'+u+y'+M'+Uw+x2+z'
> 
> I don't care if I find a 13-ply shortcut, I'll still execute the algo above


I appreciate that a lot! It took me 9 months of off and on research (from knowing nothing about how parity algs work) to finding it (and its translation to all big cube sizes) . So if it takes a solver 9 months to find it (maybe we would have to run the code on Google's computers, LOL), it would be fair I suppose, but to find its translation that works on all orbits of the 6x6x6 and larger cubes with a solver, well that might not be achievable in our life time!


----------



## unsolved (Apr 29, 2014)

cmowla said:


> Thanks Bruce. I know we are all busy, so please don't let this distract you from what you're currently trying to accomplish, but if you ever get time to do it, that would be great. If 17q or 18q depth searches are too complex at the moment, I completely understand. I just thought I would ask.



The idea is to bring the unreachable to the ordinary. Look at chess software by comparison. For over a decade the "Levy Wager" that he could defeat any chess machine produced in the next 10 years looked like it was a safe bet. Then Deep Thought and Hi Tech had people saying, "I don't know..." and then the subsequent revolution of the software programs changed things forever. Incredibly deep searches have allowed chess programs to be able to boast (legitimately) of being able to beat any World Champion using only 1 second per move of search time. Nobody ever thought this would ever be the case.

We just have to do the functional equivalent here. Bruce has got a handle on leaf node pruning. I have a handle on terminal node pruning. Now what we need is effective "middlegame" pruning.



cmowla said:


> I appreciate that a lot! It took me 9 months of off and on research (from knowing nothing about how parity algs work) to finding it (and its translation to all big cube sizes).



To me, that algo is like a thing of beauty. Almost like everything comes together magically at the end. My hat is off to you, sir!



cmowla said:


> So if it takes a solver 9 months to find it (maybe we would have to run the code on Google's computers, LOL), it would be fair I suppose, but to find its translation that works on all orbits of the 6x6x6 and larger cubes with a solver, well that might not be achievable in our life time!



They have a lot of computers, but our company makes the fastest hardware in the world (per core). If my code makes the transition to "embarrassing parallel" bitboards, I could leverage up to 160 cores @ 5.40 GHz each. That's a lot of horsepower. It won't be code you can run on your machine at home, but I might be able to design a "login interface" for a select few that I could assign access to. 

My goal is iron out the bumps with my array-based move generator, figure out that dang corner-pruning thing once and for all, convert everything to bitboards, make the parallel searching bitboard version, generate the 7-TFS and 8-TFS databases (already have the RAM on one Behemoth at the office), then let that puppy rip!

We're talking a year from now, if I am lucky... but we'll get there.

I am coding with higher cube dimension in mind, so the move generator/TFS database code could be written for 5x5x5 or 6x6x6 in short order once the "killer version" of 4x4x4 has no room left for improvement.


----------



## cuBerBruce (Apr 30, 2014)

I've built some pruning tables for BQTM, assuming I didn't make any programming errors.


```
U & D centers with respect to DLB corner:
dist  0: count =          1 total          1
dist  1: count =         12 total         13
dist  2: count =        217 total        230
dist  3: count =       4260 total       4490
dist  4: count =      64118 total      68608
dist  5: count =     779840 total     848448
dist  6: count =    6713546 total    7561994
dist  7: count =   26142524 total   33704518
dist  8: count =   17537779 total   51242297
dist  9: count =     240673 total   51482970

3x3x1 block:
dist  0: count =          1 total          1
dist  1: count =         12 total         13
dist  2: count =        234 total        247
dist  3: count =       4330 total       4577
dist  4: count =      76535 total      81112
dist  5: count =    1285915 total    1367027
dist  6: count =   18429091 total   19796118
dist  7: count =  191970261 total  211766379
dist  8: count = 1040548531 total 1252314910
dist  9: count = 1355916695 total 2608231605
dist 10: count =  101642625 total 2709874230
dist 11: count =      10794 total 2709885024
```



unsolved said:


> My favorite is still this one:
> 
> http://alg.garron.us/?cube=4x4x4¬at...Lw+Uw'+Lw2'+Bw'+r'+Bw+Rw'+R'+u+y'+M'+Uw+x2+z'
> 
> I don't care if I find a 13-ply shortcut, I'll still execute the algo above



Rest assured, there is no 13-move shortcut for the single dedge flip, not even in block turn metric. I think I had determined there is no 13-move reduction-state OLL parity fix that doesn't change the position of at least 4 dedges (not to mention corner effects). I think Clément has claimed 15 turns is the minimal dedge flip, but I'm not sure offhand if that has been proved and for what metrics.


----------

