• Welcome to SpeedSolving.com — the world’s largest puzzle community!

    You’re currently browsing as a guest, which means you have limited access to discussions, resources, member profiles, and community features.

    Join 50,000+ cubers and puzzle enthusiasts from around the world to ask questions, share solves, improve faster, and be part of the community.

    Registration is free, fast, and easy — create your account today.

    Already a member? Log in here to hide this message and start participating.

Announcing: New 4x4x4 Brute Force Solver

Status
Not open for further replies.
It's the latest one linked in this thread (it's got colours and tells me I have 8 TB virtual RAM)

I tested most of them, but the only one that didn't seem to work was the one with inner slice turns

Thanks. I looked at the code and saw that the position generates the same index to the solution. It was bound to happen. I only have 2 to the 64th power different indices, but those jillions of 4x4x4 positions. I will see if I can come up with a new indexing function that solves this. I thought after like 5 years maybe there would be one position like this, but not so soon! I could make the program only generate 3x3x3 moves when there are no slice turns in the scramble.
 
Thanks. I looked at the code and saw that the position generates the same index to the solution. It was bound to happen. I only have 2 to the 64th power different indices, but those jillions of 4x4x4 positions. I will see if I can come up with a new indexing function that solves this. I thought after like 5 years maybe there would be one position like this, but not so soon! I could make the program only generate 3x3x3 moves when there are no slice turns in the scramble.

Please keep the slice turns, I'm just using 3x3x3 cases because it's faster to setup and check solutions with :) (also, I would be really amazed if suddenly an optimal solution for an outer layer scramble would include inner slice turns)
 
Thanks. I looked at the code and saw that the position generates the same index to the solution. It was bound to happen. I only have 2 to the 64th power different indices, but those jillions of 4x4x4 positions. I will see if I can come up with a new indexing function that solves this. I thought after like 5 years maybe there would be one position like this, but not so soon! I could make the program only generate 3x3x3 moves when there are no slice turns in the scramble.

Based upon your earlier comments in this thread, I guess I'm not too surprised by your trying to cheat by not checking for an exact match between the reached position and the database position.

When one has access to all positions to some depth, a common approach to figure out the path to the solution is to simply do a series of depth-1 searches and checking for reaching a position one move closer to solved at each step. If you were doing that, and you reached a false match at depth 6, you would probably eventually have miss for all 36 moves at some point along the path to depth 0 (probably at depth 5). I suppose to be safe, backtrack and continue checking alternate paths until you're sure there is no valid path to solved of the expected length.
 
Hm, you're using some kind of cryptographic hash? That should more or less work for "small" tables like you're using here (whereas it definitely wouldn't work for a God's Algorithm calculation, if anyone ever did one). Of course you will get collisions... how often? Well if your table does take 12982642 KB to store, and it takes 4 bytes per position, one in every 5.5 billion buckets is full, so that's about the probability of a collision. With all the positions we check in a search it's not too crazy to find one of these. If your storage method is more efficient, that would only increase the probability of a collision (1 bit per position = one in every 170 million buckets is full).

Bruce's solution of backtracking is very clever - collisions are rare, so when you get one it doesn't hurt to make sure by actually tracing backwards through those 6 moves. I like it.
 
And that leads to your standard distances-only, direct-mapped hash table implementation,
where you use only one byte (or half byte) per position, and always search all the way to
zero on a "hit". It's guaranteed to be a lower bound on the distance so it's an admissible
heuristic.

Collision-free, dense indexing is often best, but a simple hash function and a table too
large frequently performs just as well---and sometimes a lot better.

The only difficulty is you can't do a simple breadth-first scan to build it (at least not without
additional memory). But once it is built, you can drop the extra memory.
 
@unsolved,
I didn't think of this before, but since you searched for the 2 2-cycle, R F u2 R2 u2 R2 l2 u2 l2 F' R', here is a list of the shortest solutions I could find (in single slice turn metric, at least) for the "worst" cases (all other 2 2-cycle cases have algorithms which have fewer moves than these cases, so I just picked out the longest ones for now).

l2 F D L F R2 D r2 D' R2 F' L' D' F' l2 (15)
r2 F D L F R2 D l2 D' R2 F' L' D' F' r2 (15)
F2 U' l' r' U F' L U' F l r F' U L' F' (15)
r2 U' B2 U' F L F' r2 F L' F' U B2 U r2 (15)
l2 U' B2 U' F L F' l2 F L' F' U B2 U l2 (15)
r2 U l r U' F R' U F' l' r' F U' R F' r2 (16)
R2 r' F' L R F r' F' R' F r2 F' L' F R2 (15)
r2 U F2 U B' R B r2 B' R' B U' F2 U' r2 (15)

They all work on the nxnxn, so I am guessing that it might be possible for shorter solutions to exist for the 4x4x4.

And... we have a winner!

Code:
Solutions To Scramble = r2 U l r U' F R' U F' l' r' F U' R F' r2 

TOP                     FRONT                   RIGHT
---------------------   ---------------------   ---------------------
|####|####|^^^^|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|####|####|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|XXXX|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|&&&&|####|####|XXXX|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------
|####|####|####|####|   |OOOO|OOOO|OOOO|OOOO|   |XXXX|XXXX|XXXX|XXXX|
---------------------   ---------------------   ---------------------


BOTTOM                  BACK                    LEFT
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|####|&&&&|&&&&|   |^^^^|^^^^|####|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------
|~~~~|~~~~|~~~~|~~~~|   |&&&&|&&&&|&&&&|&&&&|   |^^^^|^^^^|^^^^|^^^^|
---------------------   ---------------------   ---------------------



Solution [001] =  u2 f' D  B2 U' B2 r2 B2 [inside 5-TFS] ---> U  B2 D' f  u2  @ 0089361202383 nodes with 0740808355065 5-TFS probes

Hm, you're using some kind of cryptographic hash? That should more or less work for "small" tables like you're using here (whereas it definitely wouldn't work for a God's Algorithm calculation, if anyone ever did one). Of course you will get collisions... how often? Well if your table does take 12982642 KB to store, and it takes 4 bytes per position, one in every 5.5 billion buckets is full, so that's about the probability of a collision. With all the positions we check in a search it's not too crazy to find one of these. If your storage method is more efficient, that would only increase the probability of a collision (1 bit per position = one in every 170 million buckets is full).

Bruce's solution of backtracking is very clever - collisions are rare, so when you get one it doesn't hurt to make sure by actually tracing backwards through those 6 moves. I like it.

I'm doing something a little more complex. I can store 3 of the 96 pieces of facet color information in one byte, 32 bytes gives me a guaranteed unique position (note: bytes, not bits). I perform a lookup/compare of every position against every other position, and filter out the bits of each byte that are identical and keep only the bits that are unique. An ad hoc compression of only that which is germane. Beforehand I had to search for "magic numbers" to make this work, plus a fair amount of trial and error tweaking. I then re-ran up to 6-TFS one db at a time and verified uniqueness within each db.
 
Last edited by a moderator:
u2 f' D B2 U' B2 r2 B2 [inside 5-TFS] ---> U B2 D' f u2
[/code]

Interesting; it's self-inverse---by inspection!

And... we have a winner!

Code:
Solutions To Scramble = r2 U l r U' F R' U F' l' r' F U' R F' r2 


Solution [001] =  u2 f' D  B2 U' B2 r2 B2 [inside 5-TFS] ---> U  B2 D' f  u2  @ 0089361202383 nodes with 0740808355065 5-TFS probes

I don't get this. r2 U l r U' F R' U F' l' r' F U' R F' r2 followed by u2 f' D B2 U' B2 r2 B2 followed by U B2 D' f u2 leaves my 4x4x4 totally scrambled.

What am I missing?
 
Last edited by a moderator:
I don't get this. r2 U l r U' F R' U F' l' r' F U' R F' r2 followed by u2 f' D B2 U' B2 r2 B2 followed by U B2 D' f u2 leaves my 4x4x4 totally scrambled.

What am I missing?

It worked for me. Slow down, try it again.

Also a second solution now:

d2 f' D B2 U' B2 r2 B2 U B2 D' f d2
 
Last edited:
And that leads to your standard distances-only, direct-mapped hash table implementation,
where you use only one byte (or half byte) per position, and always search all the way to
zero on a "hit". It's guaranteed to be a lower bound on the distance so it's an admissible
heuristic.

Collision-free, dense indexing is often best, but a simple hash function and a table too
large frequently performs just as well---and sometimes a lot better.

The only difficulty is you can't do a simple breadth-first scan to build it (at least not without
additional memory). But once it is built, you can drop the extra memory.

Actually, that's not exactly how hashing works. A hash modulo some number is never a final index. What you do is visit the index, and see what is there. If the slot is empty, you write your very long full hash number, without the modulo divide result, into that slot, along with your other data. If the slot is taken, compare very long hash numbers. If they are different, both hash numbers merely have the same remainder, so you find a new home for the next number. There are many ways to go about this, the simplest being a linear scan for the next free spot. Once you find it, write the full hash number plus it's data at that location.


update: two more solutions, from a different scramble

Scramble: r2 U' B2 U' F L F' r2 F L' F' U B2 U r2

Solves:

u2 b' U' b' l D2 f2 D2 l' b U b u2
u2 b' U' b' l' D2 f2 D2 l b U b u2
 
Last edited:
A hash modulo some number is never a final index.

Never is a strong word.


Ahh, thanks for the alg link; that's what I needed. But wait, d is not d? Apparently the solve given
by the program uses "d" to mean, a single slice turn, but (for instance) alg.cubing.net uses "d" to
mean, an outer block turn of depth two. What good is a notation that's ambiguous?
 
Last edited by a moderator:
Ahh, thanks for the alg link; that's what I needed. But wait, d is not d? Apparently the solve given
by the program uses "d" to mean, a single slice turn, but (for instance) alg.cubing.net uses "d" to
mean, an outer block turn of depth two. What good is a notation that's ambiguous?

Singmaster used the convention that d represent an inner layer turn. Initially, the WCA used d to represent a double-layer turn for scrambles. Also d had been widely used on 3x3x3 to represent wide turns. In Asia, a "w" after a letter was used to represent a double-layer turn. The WCA started using that to avoid possible confusion on what a lower case letter meant. Then there's also SiGN notation where a lower case letter means the outer two layers, but can be prefixed to represent arbitrary mult-layer turns. So basically, you should say what convention you're using.
 
Last edited:
Never is a strong word.

Well, the point being, if some number x modulo n = i, and i is always unique, then x is always some integer multiple of n, plus i, and there will never be more than n - 1 unique values. Since n is usually much smaller than x, your effective table size is diminished.

What you really want is some magic function, h(x), which really does the opposite. For any domain of x as input, you want voluminous, almost chaotically, seemingly random output that spans a huge range.
 
Ahh, thanks for the alg link; that's what I needed. But wait, d is not d? Apparently the solve given
by the program uses "d" to mean, a single slice turn, but (for instance) alg.cubing.net uses "d" to
mean, an outer block turn of depth two. What good is a notation that's ambiguous?

SiGN is defined here: http://www.mzrg.com/rubik/nota.shtml
Short version: Use SiGN, and the world will live as one.


Story time:

Back in the day (mid-'00s), r had two meanings: turn the two outermost slices together, or turn the second-outermost slice.
The Japanese also had Rw for "wide" outer turns. But the rest of the world didn't use it, except Macky. For 3x3x3, the "Western" world basically used r to represent wide turns.

For big cubes, people sometimes used r to mean one thing, sometimes the other thing, and sometimes switched depending on whether their alg had more slice turns or more block turns. Of course, people didn't really specify which notation they were using, so this was all not very good. There is no reason that every time someone writes a 4x4 alg it should be ambiguous.

A few of us on IRC, including me, qqwref, and probably Kirjava, took some of the common conventions and formulated a simple notation we called SiGN.
It was simple because an uppercase letter meant a single slice and a lowercase letter meant multiple slices; adding a number like 3R or 3r would specify which slice/how deep to go. In addition, R simply meant the outer slice, and r was the simplest multi-slice outer block turn (two slices) -- which was consistent with one common conventions.
Apart from allowing 3-5r for non-outer block turns, that's just about it: If you see an R it means a single slice, if you see an r it means multiple slices.

Everything was great because we now had a simple standard that we were going to start using, and encouraging everyone to use. It was easy to learn, consistent, and at least *something* we would hopefully all agree on. Some day, people would forget r had ever had another meaning. (Slight dramatization, but that's basically how I felt.)

Unfortunately, this was exactly the time when the WCA saw a need for an official notation. It was introduced in 2008. Ron probably saw the notations that were in use and thought that it would be clearest to use Rw for wide turns.
But for some reason still unknown to me, the Regulations also defined r turns... as inner slice turns slice. I don't know the reason for this, because the links to the official scramble pages never used these turns, and 3x3x3 FMC didn't really need them.

This kind of threw a wrench in the whole thing, because the WCA notation was the closest the community had to a standard. SiGN was fairly common, but (partially because of the WCA notation, I assume) people still used r to mean a single slice when it was convenient -- after all, now everyone was comfortable with the meaning of Rw if you needed some wide turns to go with that.
In the end, I don't *really* care which meaning r takes on, but I was annoyed because this directly contradicted the most important detail of our effort to get everyone speaking the same notation -- all due to a Regulation that defined a turn the WCA didn't even use or need.

When I was writing alg.garron.us, I begrudgingly used Randelshofer's tools to generate a secondary WCA notation specification, but I set SiGN.

I was going to start a small "unofficial" cubing standards body and start getting the community to agree on RFCs for things like this, but the Regulations sort of fell into disrepair and Tyson brought me on to start the WRC instead. There were a lot of things to do, but I took out those "Inner Slice Moves" before we even reached the first draft].
I still want to get to the standards body thing some day (the Regulations aren't the place for all these things, and in fact it might actually be better to use an external definition for the notation), but I've been busy with the WRC.

Anyhow, the 2012 Regs finally meant that WCA notation and SiGN don't contradict each other, and we can have a universal notation. That's why alg.cubing.net simply uses SiGN with the addition that Rw is an alias for r (this will be permanent).

But the damage has been done. While most people use SiGN, some people like cmowla will still use old WCA notation. I'm not blaming them, but it makes me sad that as a community we still haven't fully settled on a single notation.

Of course, I can't control what notation people use. But we should have a standard, and SiGN is as good as any. It's simple, and I believe it makes the most sense: r can only stand for one of 2R or Rw, and if we're going to have a standard we need to pick on. I believe the latter is better because I find the following reasons for r = Rw more important than the arguments for r = 2R:

  • It makes "lower case = multiple slices, uppercase = single slice" very simple to understand for cubes of all sizes.
  • Humans can execute wide turns more easily. I think it's better to use the shorter "r" turn notation for the reconstructions and algs people actually use in practice.

In any case, alg.garron.us will start redirecting to alg.cubing.net in a few months (whenever I take a breath from working on the WRC and fix a few alg.cubing.net details first), and all "old WCA" algs will be translated to SiGN. That is, r will be redirected to 2R.
 
Well, the point being, if some number x modulo n = i, and i is always unique, then x is always some integer multiple of n, plus i, and there will never be more than n - 1 unique values. Since n is usually much smaller than x, your effective table size is diminished.

What you really want is some magic function, h(x), which really does the opposite. For any domain of x as input, you want voluminous, almost chaotically, seemingly random output that spans a huge range.

I'm just sharing ideas that have been used to great effect in the past.

You are welcome to dismiss them, of course; the ideas stand on their
own, with no need for me to defend them.
 
I'm just sharing ideas that have been used to great effect in the past.

You are welcome to dismiss them, of course; the ideas stand on their
own, with no need for me to defend them.

Your statement about a hash function @ 1-byte per entry is what I was referring to as not being correct. A hash number is usually 32- or 64-bits (4 or 8 bytes in size) and you store the hash number + other information with every entry.

What you don't is precisely what you mentioned: execute hash_number modulo some_number = index, then visit database[index] and get your info. At database[index] you have multiple pieces of info, one of which is the FULL 32- bit or 64-bit number. So there is no 1-byte/entry version of a hash table.

There are 1-byte/entry implementations that use indexing functions. An indexing function magically knows exactly where everything is, and there is no need to store anything else at the slot. When I solved the 19 billion endgames for the game of checkers with wins up to 253 plies in length, that is exactly what I did: 1 byte per position, and no need of storing a position with the win/loss lengths.
 
Status
Not open for further replies.
Back
Top