5x5x5, 6x6x6, 7x7x7 or NxNxN solvers

Discussion in 'Software Area' started by dwalton76, Jan 16, 2017.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    I've move the solver to its own repo here:
    https://github.com/dwalton76/rubiks-cube-NxNxN-solver

    The lookup tables for 2x2x2 and 4x4x4 are small enough that gzipped them and checked them into the repo. The lookup tables for 5x5x5 and 6x6x6 are several gigs so I cannot put them in the repo but I have them in a dropbox folder that I can share...ping me if you want access.

    I've been working on 6x6x6 centers, I can stage them now
    [​IMG]
    The algorithm for staging 6x6x6 centers is
    • stage the UD inner x-centers
    • pair the UD oblique edges (the edges in the centers, between the outer x-centers)....kudos to xyzzy for this idea
    • at this point the UD centers have been reduced to 5x5x5 centers so use the 5x5x5 solver to stage the UD outer x-centers
    • stage the LR inner x-centers and LR oblique edges
    • at this point the LR centers have been reduced to 5x5x5 centers so use the 5x5x5 solver to stage the LR outer x-centers
     
    shadowslice e likes this.
  2. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    Nice, I will have a look at it soon! Meanwhile my 3x3x3 Python solver is almost finished and the code just needs a bit to be polished up and documented. I consists of a server you can run on any machine and which takes the cube definition string from the client and returns the solving maneuver to the client. You can connect to the server with telnet for example or easier with a simple GUI-interface I also provide. The performance is better than I expected with the combination Python/Raspberry PI3. Running the server on the RaspberryPi3 with a time limit of 3 seconds per solve I got the following results for 100 random cubes:
    18: 4, 19: 31, 20: 48 and 21:17. So the average solving length is less than 20 moves on the Raspi if 3 secons of "thinking" is allowed.

    I also will upload it to Github soon and I think it is better to open a new thread for discussions concerning the solver since it seems a bit misplaces in this thread which deals with 5x5x5 and higher.
     
  3. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    Sounds cool, I'm looking forward to trying it out :)
     
  4. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    [​IMG]
    Can now solve 6x6x6 centers...next step is to reduce the edges to a 4x4x4
     
  5. qqwref

    qqwref Member

    7,828
    27
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Cool to see the development of more good NxNxN solvers! Many of the ones in the past have been private or never got released, so there are actually very few out there.

    Sounds pretty good for reduction! I think in the 4x4x4 FMC challenge some people had solvers that could reduce the 4x4x4 in not much move than 25 moves, but that probably requires a lot of searching.

    You definitely want to fix parity while solving centers here. In fact, that's a good idea for all big cubes; 4x4/5x5 have one parity type, 6x6/7x7 have two, and so on. You can generally do this by adding an extra slice move somewhere in the centers stage. Then the final two wings can only have some very simple "slice, flip edge, slice back" solutions, or you could just solve everything at the same time.
     
  6. abunickabhi

    abunickabhi Member

    158
    21
    Jan 9, 2014
    Yo
    WCA:
    2013GHOD01
    YouTube:
    abunickabhi
    good to hear that a feasible solver for 5x5 can be constructed.
     
  7. xyzzy

    xyzzy Member

    777
    337
    Dec 24, 2015
    Yeah, that's something I brought up too, but honestly I'm not sure if solving slice parity is that useful with redux. (Compared to "subgroup descent" methods, as in solvers that go from the full group into smaller subgroups defined by a restricted move set, e.g. mine. You can sort of see what it's doing in the video dwalton76 posted on the first page of the thread.)

    On the 555, there's the 9-move parity fix (r U2)5 which can solve 3 wings at once if you spend a bunch of moves to set up the pieces appropriately. It's worse than using 3-cycles (5 moves to solve 2 wings), but not that much worse. Solving parity at the start would probably save only about 2 moves on average. For the last two edges, the parity cases are also only about 3-4 moves longer on average (iirc). (Compare this (non-parity; 10 moves optimal) with this (parity; 12 moves).)

    Also, doing L2E/L4E on 555 the same way we do it for speedsolving is actually pretty bad in terms of move count, because slice-flip-unslice costs 7 moves, or 8 if you need to set it up. In contrast, most wing 3-cycles are either 5 or 6 moves, so if you let the unpaired wings be anywhere on the cube instead of just the 2U/2D layers, the move count just magically drops. On the flip side, solving the wings with 3-cycles is not compatible with freeslice, and almost everyone seems to think that freeslice is the best way to do edge pairing on 666 and up. I don't have data on this (yet).
     
  8. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    I uploaded my 3x3x3 Python solver to https://github.com/hkociemba/RubiksCube-TwophaseSolver now.
    For me it was the fun way to learn Python but I would appreciate if anybody with more experience with Python would have a look at the code and give me some suggestions for improvements. Maybe dwalton76 has use of it for the last phase of his NxNxN solver or some other persons who want to build a cube solving robot.
    client.jpg
     
  9. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    I tried it out, this is pretty cool. I haven't had a chance to look at the code yet but just some quick feedback:
    • Have you thought about including the tables in the repo so the user doesn't have to build them? If you 'gzip --best' they are only about 40M, thats plenty small enough to check into github.
    Code:
    [email protected] ~/l/RubiksCube-TwophaseSolver> ls -lh *.gz
    -rw-rw-r-- 1 dwalton dwalton  54K Apr 29 11:00 co_classidx.gz
    -rw-rw-r-- 1 dwalton dwalton  37K Apr 29 10:59 conj_twist.gz
    -rw-rw-r-- 1 dwalton dwalton 1.2M Apr 29 11:00 conj_ud_edges.gz
    -rw-rw-r-- 1 dwalton dwalton 2.2K Apr 29 10:58 coord.py.gz
    -rw-rw-r-- 1 dwalton dwalton 5.0K Apr 29 11:00 co_rep.gz
    -rw-rw-r-- 1 dwalton dwalton  12K Apr 29 11:00 co_sym.gz
    -rw-rw-r-- 1 dwalton dwalton 1.7M Apr 29 11:00 fs_classidx.gz
    -rw-rw-r-- 1 dwalton dwalton  96K Apr 29 11:00 fs_rep.gz
    -rw-rw-r-- 1 dwalton dwalton  14K Apr 29 11:00 fs_sym.gz
    -rw-rw-r-- 1 dwalton dwalton 1.3M Apr 29 11:01 move_corners.gz
    -rw-rw-r-- 1 dwalton dwalton 308K Apr 29 11:01 move_d_edges.gz
    -rw-rw-r-- 1 dwalton dwalton  45K Apr 29 11:00 move_flip.gz
    -rw-rw-r-- 1 dwalton dwalton 311K Apr 29 11:01 move_slice_sorted.gz
    -rw-rw-r-- 1 dwalton dwalton 1.5K Apr 29 10:58 moves.py.gz
    -rw-rw-r-- 1 dwalton dwalton  53K Apr 29 11:00 move_twist.gz
    -rw-rw-r-- 1 dwalton dwalton 838K Apr 29 11:01 move_ud_edges.gz
    -rw-rw-r-- 1 dwalton dwalton 308K Apr 29 11:01 move_u_edges.gz
    -rw-rw-r-- 1 dwalton dwalton  29M Apr 29 11:25 phase1_prun.gz
    [email protected] ~/l/RubiksCube-TwophaseSolver>
    
    • For the gui, is there a way to specify the default center colors?
    • start_server.py reports 'Error while receiving data. Connection closed' but I do get the correct response
    Code:
    [email protected][RubiksCube-TwophaseSolver]# curl 'http://localhost:8080/?DUUBULDBFRBFRRULLLBRDFFFBLURDBFDFDRFRULBLUFDURRBLBDUDL'
    <html><head><title>Answer from Cubesolver</title></head><body>
    D2 L3 D3 L2 U1 R2 F1 B1 L1 B1 D3 B2 R2 U3 R2 U3 F2 R2 U3 L2 (20f)
    </body></html>
    [email protected][RubiksCube-TwophaseSolver]#
    
     
  10. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    I am not sure if this is works The problem is that the endianess might be different in different operating systems and this could break the program since some tables store information on the bit level. So it is saver to build the tables on the system where the server is running.
    No, the gui is intented only as a very simple demonstration how to interact with the server.
    You savely can comment out the corresponding print-line in the try-except block in sockets.py if this is irritating.
     
    Last edited: Apr 29, 2017
  11. xyzzy

    xyzzy Member

    777
    337
    Dec 24, 2015
    Is there a reason you're using a `signed long` array instead of, say, an `unsigned long` or `unsigned char` array? Using an unsigned type would get rid of some of the weird checks you have for ix%16 == 15, and using `char` would get rid of endianness concerns.
     
  12. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    I suppose you address issues in the module pruning.py .
    Indeed both issues you address were also part of my considerations and what you propose was exactly what I tried in my original coding attempts.
    1. Using char instead for the arrays flipslice_twist_depth3 and corners_ud_edges_depth3: Yes this would be possible. But the generation of the two pruning tables (which take the most time to generate) really was much faster using "long" instead, mainly because it is much faster for the lower depths where the tables are sparsely populated (if not backsearch and idx % 16 == 0 and corners_ud_edges_depth3[idx // 16] == -1...).

    2. I know the lines in set_flipslice_twist_depth3 and in set_corners_ud_edges_depth3 look weird but using unsigned long which I tried first simply did not work. If I remember correctly I could not get around problems similar to what happens here:

    import array
    test = array.array('L', [0] *5)
    test[0] = ~(3 << 30)

    If you run this code you get an OverflowError: can't convert negative value to unsigned int.
    But thanks, I will give the unsigned approach another try, I think this will simplify the code because I now have the extra handling for << 30 also in the signed version!
     
    Last edited: Apr 30, 2017
  13. xyzzy

    xyzzy Member

    777
    337
    Dec 24, 2015
    Hm, I knew there had to be a catch somewhere. Would it be better to generate the tables as long (or even long long) and then convert them to char when saving them to disk?

    I haven't looked at the code very closely, but I'm assuming you use the `corners_ud_edges_depth3[idx // 16] == -1` test to simultaneously check 16 entries at once? That's pretty cool.
    Python 3's ~ operator works almost as though we're in the 2-adics. The ~ of any positive number will have "infinitely many" 1s to the left of it, so it'd be treated as a negative number, which Python refuses to implicitly convert to an unsigned int; you need to mask it with 0xFFFFFFFF to get it to be a 32-bit unsigned int.
     
  14. mark49152

    mark49152 Super Moderator Staff Member

    4,097
    2,208
    Oct 29, 2012
    UK
    WCA:
    2015RIVE05
    YouTube:
    mark49152
    Or you could solve inner edges like a 4x4 then outers like 5x5.
     
  15. Gold Cuber

    Gold Cuber Member

    119
    21
    Apr 13, 2017
    In a house
    WCA:
    2017SIMC01
    YouTube:
    Gold Cuber
    that would probably be an easier stratagie but i don't know how to make a cube robot so...
     
  16. Herbert Kociemba

    Herbert Kociemba Member

    168
    40
    Nov 29, 2008
    That's indeed the reason. I changed to unsigned long again and committed and pushed the changes. Really looks much nicer now. In the moment I do not do the mask you proposed but just make an extra handling for <<30 . But I also will try your approach today. With unsigned long long I am not sure how this performs on 32 bit systems because it extends the native int size. So maybe I better leave it as it is now.

    Edit: Used the mask operation you proposed now. Even seems to be a tiny bit faster.
     
    Last edited: Apr 30, 2017
  17. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    @Herbert Kociemba want to announce your 3x3x3 python solver in another thread so we don't end up with two conversations in this one?
     
  18. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    yep, I ended up doing that for 6x6x6. This also made me realize that I could simplify my 5x5x5 edge pairing code a good deal by using my 4x4x4 edge pairing code to pair all of the outer wings. That eliminates quite a few scenarios for pairing the last two edges 5x5x5, you only have to take care of 1, 5, 6, 7, and 8 from here:
    [​IMG]
     
  19. dwalton76

    dwalton76 Member

    34
    18
    Jan 2, 2017
    VICTORY!! Or something like that :)

    [​IMG]
     
  20. mark49152

    mark49152 Super Moderator Staff Member

    4,097
    2,208
    Oct 29, 2012
    UK
    WCA:
    2015RIVE05
    YouTube:
    mark49152
    I guess it depends whether there's any advantage to you in reducing slices or phases. If you look at each wing and pair it up with its midge you have a single phase to reduce to the last 2-3 tredges using outer block moves only. (Search AvG edge pairing.)
     

Share This Page