search

dwalton76 / rubiks-cube-NxNxN-solver

A generic rubiks cube solver
MIT License
93 stars 24 forks source link

LookupTableIDA444ULFRBDCentersStage solved state #50

Closed jgouly closed 5 years ago

jgouly commented 6 years ago

The solved state for LookupTableIDA444ULFRBDCentersStage is 'UUUULLLLFFFFLLLLFFFFUUUU' (https://github.com/dwalton76/rubiks-cube-NxNxN-solver/blob/master/rubikscubennnsolver/RubiksCube444.py#L316), I would expect it to be 'UUUULLLLFFFFUUUUFFFFLLLL' to match 'UUUURRRRFFFFDDDDBBBBLLLL'.

Can you explain why that is?

Also can you explain the difference between the 'stage' tables and the 'solve' tables? It seems like 'stage' is basically a reduction of the state to a simpler state, for example in this case it seems to reduce the centres to be opposite colours on each face only.

Sorry an issue is probably not the best place for questions..

dwalton76 commented 6 years ago

The kociemba string format that you use to input the cube state from the command line uses the order URFDBL but I always found that order really confusing so it is the only place that I use it. Everywhere else I use ULFRBD because it is easier for me to remember.

These days you can provide the input state string in whatever side order you want you just have to specify the order via the --order options

jgouly commented 6 years ago

Thanks for the reply!

I also saw this bit: https://github.com/dwalton76/rubiks-cube-NxNxN-solver/blob/master/rubikscubennnsolver/RubiksCube444.py#L719

I see that it rotates U to U and F to F. But it looks like your code solves the centres to the right positions already?

dwalton76 commented 6 years ago

I think that is to cover the scenario where the initial state of the cube has the centers staged but not solved...so you can end up solving them but the U side may not be facing up and the F side may not be facing the front.

jgouly commented 6 years ago

I'm trying to understand the difference between LookupTable and LookupTableIDA.

Does LookupTable store the move sequences for every state? Whereas LookupTableIDA stores the state up to a certain depth, and then uses IDA to search until it finds an entry in the table?

For example LookupTableIDA444ULFRBDCentersStage(LookupTableIDA), that has a max depth of 6. But the solutions can be more moves than that, so you search until you find a state you already have the sequence for?

With LookupTable444ULFRBDCentersSolve(LookupTable), you have all the sequences for solving the centres (once they only have opposite colours on each face), so you just look it up in the table and apply the moves?

dwalton76 commented 6 years ago

yep, you nailed it. There end up being two scenarios where LookupTable is used

dwalton76 commented 6 years ago

I feel like I should explain what the CostOnly tables are....because it isn't at all obvious. All of the CostOnly tables are a special type of LookupTable, they are all used as prune tables.

Lets take the scenario of "staging" the 4x4x4 centers (ie you get all UD squares on sides U or D, all LR on sides L or R, etc). This is the first phase of solving a 4x4x4, it uses IDA* with three prune tables

Originally I did not use the CostOnly approach and the UD table looked like this:

ddwalton-mbp:rubiks-cube-lookup-tables ddwalton$ tail lookup-table-4x4x4-step11-UD-centers-stage.txt
fe0080:Fw2 U' D2 L' Uw L' Fw'
fe0100:Fw2 L2 D2 R Fw'
fe0200:L Fw2 L D2 Fw'
fe0400:L2 R' Fw2 D2 L' Fw'
fe0800:L2 Fw2 D2 L' Fw'
fe1000:Rw2 Fw2 D L' Uw L' Fw'
fe2000:Fw2 D' Rw L Uw' F Rw'
fe4000:Fw2 L2 D2 Uw F Uw' Fw'
fe8000:Fw2 L2 D2 Fw' Rw U' Rw'
ff0000:Fw2 L2 D2 Fw'
ddwalton-mbp:rubiks-cube-lookup-tables ddwalton$

To find the sequence of moves for a given state I would do a binary search through the file looking for the state I wanted. This works but the disk IO is a huge bottleneck, even on solid state drive.

Each of these states is 24 bits and 2^24 is 16,777,216 so the CostOnly equivalent of this table has 16,777,216 numbers in it where the number at each position is the number of moves it would take to solve that state (for an IDA prune table we do not need to know the moves themselves, just how many it would take). So instead of doing a binary search to find the state we are looking for we can jump straight to the entry for a state. This ends up saving a ton of disk reads and makes the IDA search much faster.

jgouly commented 6 years ago

Thanks for the detailed replies!

When you say binary search, I'm a bit confused what you're actually binary searching on/for?

My current program has a prune table just for U/D staging, and I "rotate" to apply it to FB and RL. I think I saw you had tried a similar thing in one of the other git branches. I'm just IDA-ing the solutions using the prune table only.

I'm going to work on the second phase now, to actually solve them from staging.

dwalton76 commented 6 years ago

When you say binary search, I'm a bit confused what you're actually binary searching on/for?

The lookup tables are just a bunch of key/value pairs but there are too many of them for me to store in memory (one of my goals with the solver was to be able to run it on a raspberry pi3). So what I do is store a lookup table as a text file, one key/value pair per line, sort the file and make each line the same length (they are padded with trailing whitespaces to accomplish this). So if I want to find the entry for fe0800 below I do a binary search through the file for that key.

ddwalton-mbp:rubiks-cube-lookup-tables ddwalton$ tail lookup-table-4x4x4-step11-UD-centers-stage.txt
fe0080:Fw2 U' D2 L' Uw L' Fw'
fe0100:Fw2 L2 D2 R Fw'
fe0200:L Fw2 L D2 Fw'
fe0400:L2 R' Fw2 D2 L' Fw'
fe0800:L2 Fw2 D2 L' Fw'
fe1000:Rw2 Fw2 D L' Uw L' Fw'
fe2000:Fw2 D' Rw L Uw' F Rw'
fe4000:Fw2 L2 D2 Uw F Uw' Fw'
fe8000:Fw2 L2 D2 Fw' Rw U' Rw'
ff0000:Fw2 L2 D2 Fw'
ddwalton-mbp:rubiks-cube-lookup-tables ddwalton$

My current program has a prune table just for U/D staging, and I "rotate" to apply it to FB and RL. I think I saw you had tried a similar thing in one of the other git branches. I'm just IDA-ing the solutions using the prune table only.

yep I did this in the ai-playground branch, I was trying to solve 4x4x4 centers without staging them first. The prune tables are pretty big (54 million entries) so I only built it for UD and then did the rotate trick so I didn't have to build tables for LR and FB. For the normal way in master where it stages the centers first the prune tables are so small I just built all three of them to keep things simple.

I'm going to work on the second phase now, to actually solve them from staging.

Cool 👍 What language are you writing it in?

jgouly commented 6 years ago

(they are padded with trailing whitespaces to accomplish this).

Ah yes, I did notice that! I'm not so concerned about low memory systems (yet).

What language are you writing it in?

I'm doing it in rust!

Just got the second phase working. Need to actually stitch the phases together.

Do you know @iassemble? He built cubestormer etc. He has been helping me getting this up and running!

IAssemble commented 6 years ago

Yes @jgouly , I think @dwalton76 knows me lol https://www.youtube.com/user/dwalton22/videos

IAssemble commented 6 years ago

Spot the similarity? https://www.youtube.com/watch?time_continue=4&v=8xfeTQIOHGw

dwalton76 commented 6 years ago

We do need to meet in person one of these days :)

jgouly commented 6 years ago

Luckily me and @IAssemble work at the same place, so meeting up is easy!

jgouly commented 6 years ago

I'm a bit confused by LookupTable444Edges / lookup-table-4x4x4-step110-edges.txt.

It looks like that table is generated by this: https://github.com/dwalton76/rubiks-cube-lookup-tables/blob/master/builder.py#L390. That states some illegal moves, but I downloaded the file and it contains those moves.

I also saw this line https://github.com/dwalton76/rubiks-cube-lookup-tables/blob/master/builder.py#L314 which states those tables are used when generating 4x4x4 edge tables, but I don't see how they're used.

I also noticed that your edge algorithms don't "keep" the orientation of the centres, that's pretty cool. (That is the the cube might end up rotated from the original position)

dwalton76 commented 6 years ago

I've been experimenting with 4x4x4 edges so what is in lookup-table-4x4x4-step110-edges.txt wasn't built from the latest code that is checked in. When I built the step110 table I did not list any moves as illegal.

The lookup-table-4x4x4-step30-ULFRBD-centers-solve-with-edges-oriented.txt table is used here https://github.com/dwalton76/rubiks-cube-lookup-tables/blob/master/repopulate-workq.py#L75

The logic for building the 4x4x4 edges table is pretty different from the other tables. The way it works is we start traversing sequences of moves but in the end we only want to keep the sequences where the centers are still solved. The number of branches gets out of control pretty quickly. To keep things within reason say we are building the edges table 10 moves deep, if we have done 7 moves and we look at the centers and see that they will take 4 moves to solve (per the step30 table above) we prune the branch.

jgouly commented 6 years ago

Do you understand what this means for Tsai: 'Orient edges (separate low and high edges)'? Having a hard time understand it.

I also don't understand where/if TRP does this. All I can find in phase2 to do with edges, is if it has parity or not.

dwalton76 commented 6 years ago

yeah...but it would be easier to explain via a quick video call. What timezone are you in?