ksolve+ v1.0 - general-purpose algorithm finder

Discussion in 'Software Area' started by qqwref, Oct 17, 2013.

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

    cuBerBruce Member

    911
    1
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    So basically, while the original ksolve gives the user full control over defining canonical sequences, with the new version the user don't have any control over that whatsoever. I think it's great that the program can handle canonicalization automatically, but I don't think I particularly like its choice being forced upon me. And it seems to me the ForbiddenPairs feature has been made pretty much obsolete unless you want to prohibit certain non-commuting 2-move sequences for some reason.
     
  2. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Well, for ksolve+ v1.1 I've made a change that if you explicitly forbid one of the two parallel possibilities (e.g. FL UB) it will not automatically forbid the other one. The Helicopter Cube example you gave will generate the 3-move sequence now. So you can have control over which of the two canonical sequences it chooses, although if you are looking for the choice of generating both FL UB and UB FL, that is not currently an option.

    And yes, ForbiddenPairs/ForbiddenGroups should be pretty much obsolete, although if someone does want to use them (for generating algs without particularly un-ergonomic move sequences, perhaps?) they are still available.
     
  3. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Version 1.1 is out: http://mzrg.com/rubik/ksolve+/ksolve_v1.1.rar

    - I fixed the two problems Bruce mentioned.
    - Orientation is now optional (you can leave it out anywhere and ksolve+ will just use all 0's). This should save time writing definition files, especially for puzzles with no orientation.
    - MoveLimits is now in the scramble file instead of the definition file. You can put a limit on single moves (F2 2) or one move and all its powers (F* 2). I also added some optimizations to make move-limited alg searches run a bit faster.
     
  4. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    This runs great for me in OSX using wine, but I'd prefer a native build for OSX/Linux.
    How hard would it be to remove Windows-specific code?

    Also, I'd be interested in tracking the revision history. Would you consider posting a versioned repository somewhere? (I'm always a fan of things on GitHub!)
     
  5. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    I could be wrong, but I think the only Windows-specific code is the stuff in pruning.h that checks which of two files is newer. You're welcome to try to rewrite those small parts (probably shouldn't need much changed) and recompile it.

    And no, I really dislike using stuff like GitHub for personal development. There's too much overhead for me (sometimes I can spend more time trying to figure out how to send in the updated code than I actually spent writing it :|). I've just been keeping sub-versions in folders, which I guess I could zip up and send to you if you really want.
     
  6. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Version 1.2: http://mzrg.com/rubik/ksolve+/ksolve_v1.2.rar

    - Everything runs way faster (roughly 2-3 times for my test cases). This is partly due to turning on gcc's maximum optimization (sorry I didn't think of this sooner :p) and partly due to code optimizations which have the biggest effect on bandaged puzzles (such as the Bicube) and on puzzles with permutation-only pieces (such as 2gen Megaminx).
    - Various other code improvements
     
  7. qqwref

    qqwref Member

    7,832
    17
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Version 1.3: http://mzrg.com/rubik/ksolve+/ksolve_v1.3.rar

    - Optimized indexing code for non-unique permutations (so puzzles with indistinguishable pieces will run faster)
    - Changed data structure for moves, everything runs faster
    - God's Alg tables can be generated for puzzles with > 2^63 positions, although it's slower
    - God's Alg command prints algs for antipode positions
    - Comments no longer require a space after the #, and they work in scramble files too
    - In .def file, can omit parts of a move/solved state
     
  8. MarcoRossi

    MarcoRossi Member

    4
    0
    Jan 2, 2011
    Italy
    Can anyone explain me how the orientations are defined? I don't understand even the 2x2x2 def files.
    For example move R is:

    CORNERS
    1 3 6 4 2 5 7
    0 2 1 0 1 2 0

    Why the orientation of the piece "3" is 2 and of piece "6" is 1?
     
    Last edited: Nov 24, 2013
  9. Kare

    Kare Member

    21
    0
    Jun 12, 2006
    Sweden
    WCA:
    2004KRIG02
    View attachment ksolveParallel.zip

    Sorry it took so long to get started with the threading, work came in the way.

    I have changed the search to consider each initial move a different task. Eg "find a 12 move solution starting with R" is one task, "find a 12 move solution starting with U2" is another. Each core on the computer will be assigned one task, and when one task is finished the core will get a new one if any remains. Output algs will no longer be sorted.

    The only change is in treeSolve(...).

    Program needs to be built with openmp. I think most compilers support that, but it might be an optional item you need to install. I used mingw-gcc on windows and had to install openmp as an optional package.

    With gcc you need to build and link with -fopenmp

    With mingw-gcc on windows the exe will be dependant on libgomp-1.dll and pthreadGC2.dll, both was included when I got the openmp package. For linux it seems to just work.

    Performance is decent, but I was expecting better scaling than this. On my machine (4 cores, no hyper threading) I get the following for your 3x3x3_RFU computations.

    Your binary: 658s
    Your source, built by me: 654s
    Threaded program, one thread: 653s
    Threaded program, two threads: 432s
    Threaded program, four threads: 342s


    My change looks horrendous with all the code duplication, but when I tried to fix that by breaking it out to a function (ie, treeSearch calling foo() which in turn calls the next treeSearch level) I took a big performance hit.

    It would be quite easy to also parallelize the table generation. Each table (edges permutation, corners orientation etc) can be considered one task and easily distributed, but with tables saved on disk it's not that much of an advantage.
     
  10. Kirjava

    Kirjava Colourful

    6,123
    17
    Mar 26, 2006
    WCA:
    2006BARL01
    YouTube:
    snkenjoi
    Aww yea, I knew this would come in handy

    Code:
    # Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
    #
    # Notation is FCN as defined here; 
    # http://meep.cubing.net/skewb-fcn.html
    #
    # Kirjava is cool
    #
    # CORNERS UFL, UBL, UBR, DFR, DFL, DBL, DBR
    # CENTRES U F L B R D
    # MOVES U D L R
    
    Name Skewb
    Set CORNERS 7 3
    Set CENTRES 6 1
    Solved
    CORNERS
    1 2 3 4 5 6 7
    CENTRES
    1 2 3 4 5 6
    End
    Move R
    CORNERS
    1 2 4 6 5 3 7
    0 0 2 2 0 2 1
    CENTRES
    1 2 3 5 6 4
    End
    Move L
    CORNERS
    6 2 3 1 5 4 7
    2 0 0 2 1 2 0
    CENTRES
    1 3 6 4 5 2
    End
    Move U
    CORNERS
    3 2 6 4 5 1 7
    2 1 2 0 0 2 0
    CENTRES
    4 2 1 3 5 6
    End
    Move D
    CORNERS
    1 7 3 4 2 6 5
    0 2 0 0 2 1 2
    CENTRES
    1 2 4 6 5 3
    End
    rob helped fix a mistake
     
  11. Robert-Y

    Robert-Y Super Moderator Staff Member

    3,271
    60
    Jan 21, 2009
    England
    WCA:
    2009YAUR01
    YouTube:
    Robert271291
    Hi. I've created a definition file for 3x3x3 <R,r,U,F>, but whenever I run it, my laptop seems to freeze.
    Can someone please tell me how to run this successfully and if I've made an error in the code? Thanks...

    Code:
    Name 3x3x3 <R,r,U,F>
    
    # def-file by Robert Yau
    # Edges: UF UL UB UR FL BR FR DF DB DR
    # Corners: UFL UBL UBR UFR DFL DBR DFR
    # Centres: U F D B
    
    Set EDGES 10 2
    Set CORNERS 7 3
    Set CENTRES 4 1
    
    Solved 
    EDGES 
    1 2 3 4 5 6 7 8 9 10
    0 0 0 0 0 0 0 0 0 0
    CORNERS
    1 2 3 4 5 6 7
    0 0 0 0 0 0 0
    CENTRES
    1 2 3 4
    End
    
    Move R
    EDGES
    1 2 3 7 5 4 10 8 9 6
    0 0 0 0 0 0 0 0 0 0
    CORNERS
    1 2 4 7 5 3 6
    0 0 1 2 0 2 1
    CENTRES
    1 2 3 4
    0 0 0 0
    End
    
    Move r
    EDGES
    8 2 1 7 5 4 10 9 3 6
    1 0 1 0 0 0 0 1 1 0
    CORNERS
    1 2 4 7 5 3 6
    0 0 1 2 0 2 1
    CENTRES
    2 3 4 1
    0 0 0 0
    End
    
    Move U
    EDGES
    4 1 2 3 5 6 7 8 9 10
    0 0 0 0 0 0 0 0 0 0
    CORNERS
    4 1 2 3 5 6 7
    0 0 0 0 0 0 0
    CENTRES
    1 2 3 4
    0 0 0 0
    End
    
    Move F
    EDGES
    5 2 3 4 8 6 1 7 9 10
    1 0 0 0 1 0 1 1 0 0
    CORNERS
    5 2 3 1 7 6 4
    2 0 0 1 1 0 2
    CENTRES
    1 2 3 4
    0 0 0 0
    End
    EDIT: I figured it out. I defined two moves R and r but ksolve isn't case sensitive so I had to call r something else like Rw.
     
    Last edited: Jan 7, 2014
  12. Robert-Y

    Robert-Y Super Moderator Staff Member

    3,271
    60
    Jan 21, 2009
    England
    WCA:
    2009YAUR01
    YouTube:
    Robert271291
    Here's a fun 3x3x3 one :p

    (Just T perm and rotations!)

    Code:
    Name Tperm
    
    # Robert Yau made this...
    # CORNERS URF, ULF, ULB, URB, DRF, DLF, DLB, DRB
    # EDGES UF UL UB UR FR FL BL BR DF DL DB DR
    # CENTRES U F L B R D
    
    Set CORNERS 8 3
    Set EDGES 12 2
    Set CENTRES 6 1
    
    Solved
    CORNERS
    1 2 3 4 5 6 7 8
    EDGES
    1 2 3 4 5 6 7 8 9 10 11 12
    CENTRES
    1 2 3 4 5 6
    End
    
    Move T
    CORNERS
    4 2 3 1 5 6 7 8
    EDGES
    1 4 3 2 5 6 7 8 9 10 11 12
    CENTRES
    1 2 3 4 5 6
    End
    
    Move x
    CORNERS
    5 6 2 1 8 7 3 4
    1 2 1 2 2 1 2 1
    EDGES
    9 6 1 5 10 2 4 12 11 7 3 8
    1 0 1 0 0 0 0 0 1 0 1 0
    CENTRES
    2 6 3 1 5 4
    End
    
    Move y
    CORNERS
    4 1 2 3 8 5 6 7
    EDGES
    4 1 2 3 8 5 6 7 12 9 10 11
    0 0 0 0 1 1 1 1 0 0 0 0
    CENTRES
    1 5 2 3 4 6
    End
    
    Move z
    CORNERS
    2 6 7 3 1 5 8 4
    2 1 2 1 1 2 1 2
    EDGES
    6 10 7 2 1 9 11 3 5 12 8 4
    1 1 1 1 1 1 1 1 1 1 1 1 
    CENTRES
    3 2 6 4 1 5
    End
     
  13. DrKorbin

    DrKorbin Member

    707
    3
    Aug 10, 2011
    Russia, Moscow
    WCA:
    2011GRIT01
    YouTube:
    Korbinification
    If def-file or file with scrambles has an empty line at the end, the program crashes.
    Code:
    ...
    Pruning tables found on file.
    Pruning tables loaded.
    terminate called after throwing an instance of 'std::out_of_range'
      what():  basic_string::at
    
    This application has requested the Runtime to terminate it in an unusual way.
    Please contact the application's support team for more information.
    
     
  14. cubizh

    cubizh Super Moderator Staff Member

    596
    25
    Oct 2, 2011
    Portugal
    WCA:
    2014GOME07
    YouTube:
    cubizh
    This specific bug can be easily fixed by editing readdef.h and readscramble.h and locate the following code (around line 40), and add the check for size == 0 like the following, for both files:
    Code:
                    ......
                    while(!fin.eof()){
                            string command;
                            fin >> command;
                            // Break if nothing is found on file
                            if (command.size() == 0) {
                                    break;
                            }
              
                            if (command == " .......
    
    
    Hope this helps you.

    Also, I asked a friend to help me port it to Linux and so I'd like to share a working Ksolve for Linux version, and I would like to ask the developers to see if they can find a way to integrate the changes into the main code so that a system-independent version can be achieved (which I can't do/test).
     
  15. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    qqwref doesn't like using GitHub for this, but I track his changes on my repo. I've also added your changes on a branch: https://github.com/lgarron/ksolve-plus/tree/unix
     
  16. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    Merging the parallel code from Kåre worked: https://github.com/lgarron/ksolve-plus/tree/unix

    I've got a parallel native binary on OSX now (using GCC 4.2, because apparently clang doesn't support OpenMP).

    Inline functions?
     
    Last edited: Jan 5, 2014
  17. cubizh

    cubizh Super Moderator Staff Member

    596
    25
    Oct 2, 2011
    Portugal
    WCA:
    2014GOME07
    YouTube:
    cubizh
    I'm having problems compiling (actually linking) with gcc 4.7.3, it doesn't seem to recognize OpenMP for some reason.

    EDIT: Fixed.
     
    Last edited: Jan 5, 2014
  18. TheNextFeliks

    TheNextFeliks Member

    2,412
    0
    Oct 27, 2012
    KCKS
    WCA:
    2013POPE01
    YouTube:
    TheNextFeliks
    Wow. How do you do something like this? I'm a new programmer but I mostly do web dev like JavaScript. That is pretty cool. I might try to work on a JavaScript one.
     
  19. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    So, compiling to JS was easy: http://www.cubing.net/ksolve.js/

    Unfortunately, memory usage blows up in the browser (I quickly hit 600MB on the 3x3x3 RFU example).
     
    Last edited: Jan 6, 2014
  20. rokicki

    rokicki Member

    253
    1
    Oct 31, 2008
    The substate structure uses unmanaged pointers for its int arrays. Either smart pointers should
    be used, or explicit resource management should be done.

    (I don't know that this is the only memory leak, but it's the main one I see.)
     

Share This Page