My 4x4x4 optimal solver

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.

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.

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.

Click to expand...

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.

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

cmowla said:

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

Click to expand...

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.

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.

Click to expand...

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!

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!

Click to expand...

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.

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.

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.

Click to expand...

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.

unsolved said:

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.

Click to expand...

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.

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.

Click to expand...

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?

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.

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?

Click to expand...

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.

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.

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.

Click to expand...

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.

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.

FYI.

Click to expand...

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.

cuBerBruce said:

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

Click to expand...

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).

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).

Click to expand...

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.

cmowla said:

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

Click to expand...

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

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.

Click to expand...

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

Click to expand...

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!

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.

Click to expand...

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).

Click to expand...

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!

Click to expand...

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.