Square one - what to index to compute ?

[deadalnix]

Here is the question.

To be really effiscient in puzzle computing, it's useful to generate an index and build a transition table from an index to another for each moves.

For exemple, on a 2x2x2, we generate a transition table for both permutation and orientation of the corener. When performing a move, we just have to look into the transition table for the new permutation and the new orientation.

This is working pretty well because set number of permutation and orientation isn't really big. The fact is also that when you have a given permutation fo corners, if you perform a given move, you get always the same new permutation, whatever is the orientation. Orientation and permutation can be independant.

For the square-one, the problem is more complex. It's impossible to do a simple thing like corner permutation and edge permutation. These permutation are making the shape of the puzzle, and so, a given move is affecting the corner permutation in a way that depends on edges orientation.

A 2 phase alg is possible making BTC+parity at phase 1 and permute everything keeping square shape at phase 2.

But I'm not satisfied with that and I'm pretty sure a smarter way to compute this puzzle is possible.

Another thing, Jaap explain on his webpage that the gos alg is calculated for the square one. Considering that the calculation involved more than 400 billions of positions, and that at least 2bits are needed for god alg, more than 100Gb of memory is needed. And computing on hard drive is just really slow (and even slower than that). How this god alg is calculated ?

 

[Stefan]

Here's some explanation of how God's algorithm was computed:
http://cubezzz.homelinux.org/drupal/?q=node/view/35

For the square-one, the problem is more complex. It's impossible to do a simple thing like corner permutation and edge permutation. These permutation are making the shape of the puzzle, and so, a given move is affecting the corner permutation in a way that depends on edges orientation.

You could use absolute positions (well, relative to let's say the left middle layer half), i.e., use the 2*12 places a piece can be at. For example a piece at 5am (think of a clock) will move to 9am by turning (4,0) no matter where the other pieces are. And move from 5am to 5pm by turning "/" no matter where the other pieces are.

What is your goal? Do you want to compute that whole God's table as well or do you want to write a solver for single cases or ...?

 

[rokicki]

God's algorithm

To calculate God's algorithm for a puzzle, if the puzzle doesn't fit in memory by a long margin, some standard tricks apply.

First, the positions should be reduced by symmetry as much as possible (and anti-symmetry too). For the normal Rubik's cube, this gives a 96-way reduction in state space.

You only need 1.6 bits per position, not 2; store five states (0,1,2) in a byte.

If you are almost there, using one bit per position and storing each level on disk can work just fine; you write and read each level exactly once, sequentially.

If these tricks do not suffice, using a coset approach can work well.

Break up the state space into some number of cosets, where the cosets do fit in memory. Solve each coset independently, and add the numbers. This is how I calculated God's algorithm out to 13f* and 15q* for the normal 3x3, but it also works for other puzzles.

Selecting the correct group to use is important, or you will find yourself solving the same positions over and over again in your coset exploration.

I'd be happy to expand on any of these tricks if you are interested.

 

[cuBerBruce]

Break up the state space into some number of cosets, where the cosets do fit in memory. Solve each coset independently, and add the numbers.

What I've sometimes done is calculate each coset for each level and write a disk file to save the result for each coset. To calculate a coset you need to read the file for the previous level for each neighboring coset.

Back to the original question:

As far as an "index" values (or what Kociemba refers to as "coordinates") for Square-1, I would think dividing the pieces into 4 subsets would work well: edges belonging in the top layer, edges belonging in the bottom layer, corners belonging in the top layer, and corners belonging in the bottom layer. Each set of pieces can be located in 24*23*22*21 = 255024 different ways. (Corners, of course, have further restrictions, but for purposes of using a single table for calculating moves, you might want to calculate the coordinates in the same way as edges.) Note that in this scheme you're keeping track of where each piece is located, as opposed to keeping track of what piece is located in each position. Of course, you need an extra bit to keep track of the state of the middle layer. This scheme needs a total of at least 73 bits to represent a position, which is not minimal, of course.

If you need to store information for each possible position, you would probably have to consider handling each possible shape separately, and how pieces are arranged within the current shape.

 

[Lucas Garron]

In my Mathematica code, I ignored the middle layer (it's not that useful for theory, although it may be useful to handle it for finding algs) and used the fact that every state is slicable to store edge and corner positions
Therefore, the Square-1 looks like this in cube shape:
{{2, 1, 2, 1, 2, 1, 2, 1}, {1, 2, 1, 2, 1, 2, 1, 2}}

The sum of each is 12, and each one can be split into halves of sum 6. Any legal move preserves that. If I wanted to distinguish moves, I would call them each a name/number, and have some way of inferring which the 1's (edges{ and 2's (corners) are. Another option then would be to list the corners double, and make sure each double corner appears together.

It sounds a little naive to do this way, but I'd probably end up doing something similar in C. The whole thing is just a bandaged pure permutation puzzle, anyhow.

 

[deadalnix]

I did excpected so much answers

I need some time to think about everything, but quickly :

StefanPochmann > I'm interested in computing alg for square-one. the question about god alg are more for my personnal culture.

rokicki > Packing 5 positions in 1 byte is pretty smart. But still, the memory needed is huge.

The 1 bit per position solution is using a big file for each deepth is a good one, but How do you prevent regressions ?

cuBerBruce > Nice idea. A bif bit field with possible move or not depending on corner permutation is managable. The thing is a bit redundant, but it remains tiny enought to fit in modern computer memory.

Lucas Garron > You idea obviously work. But does fit very well with the transition table idea.

 

[rokicki]

Coordinates

Split the coordinates into two sets: ones that are funky/hard and ones that are easy.

The funky/hard ones are the shape ones. The easy ones are the permutation of the three categories of pieces (and maybe the flip of the middle if you want), given the shape.

Use a hashtable for the shape; I don't think there are too many possibilities. Use that hashtable to find a bitmap, and that bitmap includes the permutations of the small/large pieces. So the bitmap is 40K by 40K (divided by any permutation requirements); that's 1.6B and requires 400MB at 2 bits per.

Then, for every shape, consider all possible moves (within the shape), calculate the permutation on the small/big pieces individually, and then rip through that bitmap at a huge speed updating things as you go.

Since this doesn't fit in memory, do it by cosets, where each coset is the set of positions that has a fixed shape, and use the 200MB bitmap to handle the permutations (one bit per; you only need to know if you've seen this one before or not). Your search just fixes the shape, and you enumerate all ways to "solve" the shape until you've hit all possible permutations; then you're done with that coset, and you move on to the next.

Reduce the shapes by symmetry up front, so you don't do any symmetry work in your coset explorations.

Managing the permutations given any given move is easy, because they fit into a simple pattern; you're always swapping pairs of subsequences. A lookup table will handle this pretty easily, I suspect.

Sum the results from all cosets and you're done.

This should be hugely fast, probably do the whole computation in less than a day and take a few hundred megabytes of RAM.

For real speed, make the shape distance table include information on which moves take you closer to solved, and which moves leave you the same distance from solved, and then you'll avoid all the "unnecessary" lookups.