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

    Renslay Member

    1,715
    4
    Aug 1, 2011
    Hungary
    WCA:
    2005HANT01
    YouTube:
    Renslay
    Hi! I just tried it and defined the Floppy cube. It is fun! :)

    Code:
    Name Floppy
    
    # def-file by Norbert Hantos
    
    Set CORNERS 4 2
    Set EDGES 4 2
    
    Solved
    CORNERS
    1 2 3 4
    EDGES
    1 2 3 4
    End
    
    Move R
    CORNERS
    1 3 2 4
    0 1 1 0
    EDGES
    1 2 3 4
    0 1 0 0
    End
    
    Move F
    CORNERS
    1 2 4 3
    0 0 1 1
    EDGES
    1 2 3 4
    0 0 1 0
    End
    
    Move L
    CORNERS
    4 2 3 1
    1 0 0 1
    EDGES
    1 2 3 4
    0 0 0 1
    End
    
    Move B
    CORNERS
    2 1 3 4
    1 1 0 0
    EDGES
    1 2 3 4
    1 0 0 0
    End
    Edit: Hm, I think the orientation of the corners is not necessary.
     
    Last edited: Jan 7, 2014
  2. Renslay

    Renslay Member

    1,715
    4
    Aug 1, 2011
    Hungary
    WCA:
    2005HANT01
    YouTube:
    Renslay
    I just don't understand something. I defined a puzzle:

    Code:
    Solved
    BIG 
    1 1 2 2 3
    SMALL
    1 1 1 1 1 2 2 2 2 2 3 3 3 3
    End
    And of course I defined the moves. Then I give this scramble:

    Code:
    Scramble test
    BIG
    1 1 2 2 3
    SMALL
    3 1 2 3 2 2 3 1 1 2 2 3 1 1
    End
    The program solves it in 16 moves, which is nice. However, I try to find a solution where only the permutation of the 1s are interesting for me. Therefore I try:

    Code:
    Scramble test
    BIG
    1 1 2 2 3
    SMALL
    ? 1 ? ? ? ? ? 1 1 ? ? ? 1 1
    End
    This is the same as above, just ? instead of numbers other than 1 on the small pieces. Here, the program couldn't find a solution (it goes even to depth 22 and further, but God's number for the whole puzzle is 21). However, if I give some "hint":

    Code:
    Scramble test
    BIG
    1 1 2 2 3
    SMALL
    ?3 1 ?2 ?3 ?2 ?2 ?3 1 1 ?2 ?2 ?3 1 1
    End
    It finds again the 16 moves solution. What do I do wrong, why the second example does not working?
     
  3. Carrot

    Carrot Member

    1,910
    8
    Feb 9, 2009
    WCA:
    2008ANDE02
    YouTube:
    Minxer2011
    Code:
    Solved
    BIG 
    1 1 2 2 3
    SMALL
    1 1 1 1 1 2 2 2 2 2 3 3 3 3
    End
    
    Ignore
    SMALL
    0 0 0 0 0 1 1 1 1 1 1 1 1 1
    End
    You need to put the Ignore in the Def file to activate the ?s

    Code:
    Scramble test
    BIG
    1 1 2 2 3
    SMALL
    ?3 1 ?2 ?3 ?2 ?2 ?3 1 1 ?2 ?2 ?3 1 1
    End
    it may sound silly, but you actually NEED to put a valid piece after the ?. It's silly but I hope it works. if it doesn't I swapped the 0 and 1's in the Ignore in the def. (it's binary for ignore and don't ignore)
     
  4. qqwref

    qqwref Member

    7,828
    27
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    The Mac version fix is cool, but I'm not particularly happy with you doing all this easy-but-impressive-looking stuff behind my back and attaching your username and/or website to it. You know, this kind of thing makes me a LOT less eager to work on useful tools for the cubing community in the future.

    If you aren't also putting an Ignore command in the .def file to tell ksolve you are ignoring pieces, that would be why it isn't working. Basically, if it does not know you are ignoring pieces, it uses the wrong pruning table and thinks a lot of perfectly good solutions are impossible. I'd love to only have this in the scramble file, but then it would have to compute pruning tables for each scramble as it goes, and in almost all cases that'd be way slower.

    Interesting; if I am leaking memory this way I definitely want to fix it. What data structure changes do you recommend I make (put the substate in a smart pointer? put the orientation/permutation arrays in smart pointers? switch to a pair of smart-pointered vectors?)?
     
  5. tim

    tim Member

    1,691
    1
    Nov 22, 2006
    Karlsruhe, Germany
    WCA:
    2007HABE01
    YouTube:
    cin9247
    That's totally understandable. But why do you not want to use Github (or any other comparable service)? I think this software would benefit from open sourcing it (in this case I mean: putting it somewhere to make it a) easily accessible and b) easy to contribute to). There are many capable coders in our community (and basically everyone knows C), but sending you files with fixes or improvements (like the linux port) is a pain in the ass and I personally don't want to do it.
     
  6. Jakube

    Jakube Member

    790
    4
    Feb 3, 2011
    Austria
    WCA:
    2011KOGL01
    YouTube:
    JakubeBLD
    It should only have to be in the scramble file.
    Your comment made me realize, that I had an ignore command in the definition file. It bugged me a while, that it wasn't able to find 12 move solutions in a reasonable time. After removing the command, ksolve finds 13+ solutions in a second.

    Maybe you can save multiple pruning tables and always pick the best one. And if there's a scramble with a new ignore type, the generate a save new ones. I guess, people only use a small number of different ignore definitions, so it wouldn't have to generate the pruning tables at every scramble. Only if it should ignore new pieces.

    Or just simply print a warning, if the program sees, that the current pruning tables doesn't match the scramble, like "Using different ignore setting might speed up the search" or "ksolve might not find all solutions because of wrong ignore settings".
     
  7. qqwref

    qqwref Member

    7,828
    27
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Jakube: I agree that's how it should be, but it could mean having to keep track of multiple potentially-large pruning table files, loading and unloading large amounts of data into memory between scrambles, and recalculating any or all of that pruning table data whenever the definition file is changed. Really the problem is that I don't want the software to become bloated and slow just for the sake of a single feature, and I am worried this could do just that. A chunk of extra speed or efficiency could be very valuable to people searching in particularly difficult/complex puzzles.

    I don't mind using a version control system if people want to actively contribute, and it seems like they do. I really do dislike the way git works (as a program and concept) and find most of its jargon incomprehensible, but if people are absolutely dead set on using git and github over something like SVN/Google Code I'll get down to figuring it out eventually.
     
    Last edited: Jan 8, 2014
  8. rokicki

    rokicki Member

    255
    4
    Oct 31, 2008
    Let's chat by email; mine should be pretty obvious and I'm not sure I remember what yours was.

    But for a quick fix I'd recommend (I've never used these myself but I have heard a lot of good things
    about them) the reference-counted pointers (std::shared_ptr) for your int* in substate.

    You'll probably need to give substate a default constructor, a copy constructor, a destructor, and
    an assignment operator, but these are pretty boilerplate.

    -tom
     
  9. tim

    tim Member

    1,691
    1
    Nov 22, 2006
    Karlsruhe, Germany
    WCA:
    2007HABE01
    YouTube:
    cin9247
    Yeah, git is unfortunately far from easy to understand, but IMO worth learning. I especially found learning how git works internally very rewarding [1][2]. It's surprisingly simple.
    Anyway, SVN+google code or mercurial+bitbucket would be fine as well.

    [1] http://www.youtube.com/watch?v=GYnOwPl8yCE
    [2] http://www.youtube.com/watch?v=1ffBJ4sVUb4 (funny, but not as accurate and detailed as [1])
     
    Last edited: Jan 8, 2014
  10. rokicki

    rokicki Member

    255
    4
    Oct 31, 2008
    Another fix is to replace int* with vector<int> in substate and make the relevant other
    changes throughout. This may be simpler or may be harder.

    Neither of these solutions will be particularly efficient.
     
  11. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    I do put an attribution where I can, e.g. "Versioned mirror of Kare's / qqwref's ksolve+ puzzle solver." on the top of GitHub.
    This particular time, the demo page didn't have an attribution because it is a minimal test page (i.e. based on this instead of this) but I've added them now.

    I'm glad you're open to something like GitHub for collaborative development. There are a few more easy-but-impressive-looking steps to take. ;-)
    I personally prefer the flexibility of git and the fact that GitHub focuses on the code itself (plus, most people are already there), but something else would be fine.
     
    Last edited: Jan 8, 2014
  12. cubizh

    cubizh Super Moderator Staff Member

    597
    29
    Oct 2, 2011
    Portugal
    WCA:
    2014GOME07
    YouTube:
    cubizh
    One feature I would like to see implemented is the save search upon crash or termination and resume. You can imagine how pissed off I was having ksolve running for an entire week (well, 6 days straight) searching for algs and all of a sudden losing everything due to a CPU overheat emergency shutdown.

    I have used GitHub, but am also not particularly experienced with it beyond the utmost basics, but really mostly because I have not really looked deeply into it. I will look more into it in the future.
    Thanks for the links, tim.
     
  13. Renslay

    Renslay Member

    1,715
    4
    Aug 1, 2011
    Hungary
    WCA:
    2005HANT01
    YouTube:
    Renslay
    Thanks to ksolve, I was able to construct a full solving method for a brand new puzzle!
     
  14. Ranzha

    Ranzha Friendly, Neighbourhoodly

    I made some ksolve+ definition files for Skewb in WCA-style FCN, FCeN, and Hideki Niina's notation that are similar to Thom's def file. The biggest difference is the piece labelling and the inclusion of all pieces. This may cause the solver to run less quickly, but the solver's fast and furious as it is, so no harm done? =D

    The piece labelling was meant to mirror Meep's Skewb Solver 2.2. Also, for solvers using Sarah's method (and thus Hideki Niina's notation), choose the set of moves you want to include in your def file. Turns about all eight corners are defined below.

    Fixed Corner Notation, WCA-style:
    Code:
    # Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
    #
    # Notation is Fixed Corner Notation (FCN) as defined here: 
    # https://www.worldcubeassociation.org/regulations/#12h
    #
    # Ranzha
    #
    # centres U F R D B L
    # corners UFR, UBR, UBL, UFL, DFR, DBR, DBL, DFL
    # moves U R L B
    
    Name Skewb
    Set corners 8 3
    Set centres 6 1
    Solved
    corners
    1 2 3 4 5 6 7 8
    0 0 0 0 0 0 0 0
    centres
    1 2 3 4 5 6
    End
    Move U
    corners
    1 7 3 2 5 6 4 8
    0 2 1 2 0 0 2 0
    centres
    5 2 3 4 6 1
    End
    Move R
    corners
    1 5 3 4 7 6 2 8
    0 2 0 0 2 1 2 0
    centres
    1 2 4 5 3 6
    End
    Move L
    corners
    1 2 3 7 4 6 5 8
    0 0 0 2 2 0 2 1
    centres
    1 6 3 2 5 4
    End
    Move B
    corners
    1 2 6 4 5 8 7 3
    0 0 2 0 0 2 1 2
    centres
    1 2 3 6 4 5
    End

    Fixed Centre Notation:
    Code:
    # Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
    #
    # Notation is Fixed Centre Notation (FCeN) as defined here: 
    # http://ranzha.cubing.net/skewb/notation.html
    #
    # Ranzha
    #
    # centres U F R D B L
    # corners UFR, UBR, UBL, UFL, DFR, DBR, DBL, DFL
    # moves F R L B
    
    Name Skewb
    Set corners 8 3
    Set centres 6 1
    Solved
    corners
    1 2 3 4 5 6 7 8
    0 0 0 0 0 0 0 0
    centres
    1 2 3 4 5 6
    End
    Move F
    corners
    8 2 3 4 5 1 7 6
    2 0 0 0 1 2 0 2
    centres
    1 4 2 3 5 6
    End
    Move R
    corners
    1 5 3 4 7 6 2 8
    0 2 0 0 2 1 2 0
    centres
    1 2 4 5 3 6
    End
    Move L
    corners
    1 2 3 7 4 6 5 8
    0 0 0 2 2 0 2 1
    centres
    1 6 3 2 5 4
    End
    Move B
    corners
    1 2 6 4 5 8 7 3
    0 0 2 0 0 2 1 2
    centres
    1 2 3 6 4 5
    End

    Hideki Niina's notation:
    Code:
    # Skewb ksolve+ definition file (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
    #
    # Notation is in the style of Hideki Niina as defined here: 
    # http://rubikskewb.web.fc2.com/skewb/notation.html
    #
    # Ranzha
    #
    # centres U F R D B L
    # corners UFR, UBR, UBL, UFL, DFR, DBR, DBL, DFL
    # moves F R L B f r l b
    
    Name Skewb
    Set corners 8 3
    Set centres 6 1
    Solved
    corners
    1 2 3 4 5 6 7 8
    0 0 0 0 0 0 0 0
    centres
    1 2 3 4 5 6
    End
    Move F
    corners
    1 4 3 5 2 6 7 8
    1 2 0 2 2 0 0 0
    centres
    2 3 1 4 5 6
    End
    Move R
    corners
    6 2 1 4 5 3 7 8
    2 1 2 0 0 2 0 0
    centres
    3 2 5 4 1 6
    End
    Move L
    corners
    3 2 8 4 5 6 7 1
    2 0 2 1 0 0 0 2
    centres
    6 1 3 4 5 2
    End
    Move B
    corners
    1 7 3 2 5 6 4 8
    0 2 1 2 0 0 2 0
    centres
    5 2 3 4 6 1
    End
    Move f
    corners
    8 2 3 4 5 1 7 6
    2 0 0 0 1 2 0 2
    centres
    1 4 2 3 5 6
    End
    Move r
    corners
    1 5 3 4 7 6 2 8
    0 2 0 0 2 1 2 0
    centres
    1 2 4 5 3 6
    End
    Move l
    corners
    1 2 3 7 4 6 5 8
    0 0 0 2 2 0 2 1
    centres
    1 6 3 2 5 4
    End
    Move b
    corners
    1 2 6 4 5 8 7 3
    0 0 2 0 0 2 1 2
    centres
    1 2 3 6 4 5
    End

    Rotations:
    Code:
    # Skewb ksolve+ definition file for rotations (tested on v1.3 from http://mzrg.com/rubik/ksolve+/)
    #
    # Ranzha
    #
    # moves x y z
    
    Name Skewb
    Set corners 8 3
    Set centres 6 1
    Solved
    corners
    1 2 3 4 5 6 7 8
    0 0 0 0 0 0 0 0
    centres
    1 2 3 4 5 6
    End
    Move x
    corners
    5 1 4 8 6 2 3 7
    0 0 0 0 0 0 0 0
    centres
    2 4 3 5 1 6
    End
    Move y
    corners
    2 3 4 1 6 7 8 5
    0 0 0 0 0 0 0 0
    centres
    1 3 5 4 6 2
    End
    Move z
    corners
    4 3 7 8 1 2 6 5
    0 0 0 0 0 0 0 0
    centres
    6 2 1 3 5 4
    End
    In my few days of using it, I'd like to commend all contributors to ksolve+. This solver is fast, efficient, well-documented--truly revolutionary.
     
    Last edited: Jan 9, 2014
  15. qqwref

    qqwref Member

    7,828
    27
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Honestly, because of what lgarron did, I'm really not particularly excited about putting any more time into this thing. I made a ton of huge changes since Kare's version, completely rewrote the readme, and put a lot of time in, but I'm sure soon enough anyone who googles it will just think "oh it's yet another lgarron project, he's so awesome". I'm probably going to release a last version at some point, to fix some bugs, and then that's it. For the record, ksolve was all done by Kare and everything after that and until ksolve+ v1.3 was done by me; the next version I put on my site will have contributions from others.
     
    Last edited: Jan 23, 2014
  16. joey

    joey Member

    4,406
    6
    Apr 8, 2007
    WCA:
    2007GOUL01
    YouTube:
    cardologist
    Nowhere does it say anything about Lucas? Your name is definitely on there.

    You could also ask Lucas to take it down, or make your own account on github.
     
  17. cubizh

    cubizh Super Moderator Staff Member

    597
    29
    Oct 2, 2011
    Portugal
    WCA:
    2014GOME07
    YouTube:
    cubizh
    I think everyone that matters knows and appreciates your efforts in rebooting ksolve and sharing it openly for the benefits of all, regarding general puzzle solving.
     
  18. TheNextFeliks

    TheNextFeliks Member

    2,391
    2
    Oct 27, 2012
    KCKS
    WCA:
    2013POPE01
    YouTube:
    TheNextFeliks
    How does one write a proper define file? I am just using the JavaScript one on cubing.net btw and I love it.
     
  19. Methuselah96

    Methuselah96 Member

    318
    0
    Jun 17, 2010
    WCA:
    2012BIER01
    Download the ZIP from the OP. Read the readme and look at the examples.
     
  20. TheNextFeliks

    TheNextFeliks Member

    2,391
    2
    Oct 27, 2012
    KCKS
    WCA:
    2013POPE01
    YouTube:
    TheNextFeliks
    Ok. This is great. But I can't figure out the Ignore. I am trying to do OLL so avoiding the permutation. Could someone post an example? I am trying to find algs for the I case with bars on both sides.
     

Share This Page