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

    qqwref Member

    7,833
    25
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    ksolve+ is a C++ program that can find algorithms for many different puzzles - any simple permutation puzzle you can think of, and some not-so-simple ones too. This includes 2x2x2, 3x3x3, Megaminx, Square-1, and so on. You write a definition file defining the puzzle, and a scramble file listing the scrambles, and then ksolve+ will find optimal (or near-optimal, if you want) solutions for your scrambles.

    The original ksolve was written by Kare Krig, but it hasn't been updated in a few years and I figured it could use some improvement. Apart from some major code rewriting, there are many improvements and new features. Changes include generating/solving random scrambles, ignoring pieces in the scramble file, reading in move sequences as scrambles, computing God's Algorithm tables, optionally using QTM, limiting the allowed number of each type of move, and looking for suboptimal algs. I also made it about 25% faster.

    Download link (v1.3):
    http://mzrg.com/rubik/ksolve+/ksolve_v1.3.rar
    Apart from ksolve+ itself, I have included a readme, a bunch of sample definition and scramble files, and the source code.

    Please let me know if you have any problems or if you find any bugs :)
     
    Last edited: Nov 19, 2013
  2. Tim Major

    Tim Major Platinum Member

    5,376
    11
    Aug 26, 2009
    Melbourne, Australia
    WCA:
    2010MAJO01
    Last edited: Oct 17, 2013
  3. qqwref

    qqwref Member

    7,833
    25
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Gotcha. Should be fixed now, give it a try.
     
  4. BurntTheCube

    BurntTheCube Member

    27
    0
    Aug 24, 2013
    Tx, USA
    Can't really get it to open but thats probably because I'm not tech savvy. But it closed like 22 tabs (MY COOKIE CLICKER!!) and downloaded some crappy homepage. 0/10
     
  5. qqwref

    qqwref Member

    7,833
    25
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    I put it up on my website instead; the download should be more foolproof now.
     
  6. Ranzha

    Ranzha Friendly, Neighbourhoodly Staff Member

    Cookie Clicker autosaves every minute.
     
  7. Tim Major

    Tim Major Platinum Member

    5,376
    11
    Aug 26, 2009
    Melbourne, Australia
    WCA:
    2010MAJO01
    I extracted, double clicked on ksolve.exe, it opens a small black window (like cmd) and instantly closes with no error message or anything. I can fraps if you want.
     
  8. oranjules

    oranjules Member

    90
    12
    Oct 29, 2010
    WCA:
    2010DESJ01
    you have to launch it from cmd
     
  9. Tim Major

    Tim Major Platinum Member

    5,376
    11
    Aug 26, 2009
    Melbourne, Australia
    WCA:
    2010MAJO01
    Yeah I read the readme, I think I understand how to use it now. Thanks. I probably won't actually use this software. I basically understand how to use it, but it's too difficult to use.
     
    Last edited: Oct 17, 2013
  10. Renslay

    Renslay Member

    1,715
    4
    Aug 1, 2011
    Hungary
    WCA:
    2005HANT01
    YouTube:
    Renslay
    If I'm guessing right, one can define a Square-1 by a puzzle with 24 pieces, (12 top, 12 bottom), 8 pairs of them are bandanged, and there are two center pieces (middle layer), where the orientation (permutation?) counts; and define U30, D30 and R180 moves with only permutations.

    Edit: well, actually only the orientation of the right "center" counts.
     
    Last edited: Oct 17, 2013
  11. Kirjava

    Kirjava Colourful

    6,123
    23
    Mar 26, 2006
    WCA:
    2006BARL01
    YouTube:
    snkenjoi
    I'm really glad you improved this, will save me a lot of time hacking together quick solvers.

    Code:
    Name 3 Colour Cube
    
    # Kirjava
    # CORNERS URF, ULF, ULB, URB, DRF, DLF, DLB, DRB
    # EDGES UF UL UB UR FR FL BL BR DF DL DB DR
    
    Set CORNERS 8 3
    Set EDGES 12 2
    
    Solved
    CORNERS
    1 2 1 2 2 1 2 1
    0 0 0 0 0 0 0 0
    EDGES
    1 2 1 2 3 3 3 3 1 2 1 2
    0 0 0 0 0 0 0 0 0 0 0 0
    End
    
    Move U
    CORNERS
    4 1 2 3 5 6 7 8
    0 0 0 0 0 0 0 0
    EDGES
    4 1 2 3 5 6 7 8 9 10 11 12
    0 0 0 0 0 0 0 0 0 0 0 0
    End
    
    Move R
    CORNERS
    5 2 3 1 8 6 7 4
    1 0 0 2 2 0 0 1
    EDGES
    1 2 3 5 12 6 7 4 9 10 11 8
    0 0 0 1 1 0 0 1 0 0 0 1
    End
    
    Move F
    CORNERS
    2 6 3 4 1 5 7 8
    2 1 0 0 1 2 0 0
    EDGES
    6 2 3 4 1 9 7 8 5 10 11 12
    0 0 0 0 0 0 0 0 0 0 0 0
    End
    
    Move D
    CORNERS
    1 2 3 4 6 7 8 5
    0 0 0 0 0 0 0 0
    EDGES
    1 2 3 4 5 6 7 8 10 11 12 9
    0 0 0 0 0 0 0 0 0 0 0 0
    End
    
    Move L
    CORNERS
    1 3 7 4 5 2 6 8
    0 2 1 0 0 1 2 0
    EDGES
    1 7 3 4 5 2 10 8 9 6 11 12
    0 1 0 0 0 1 1 0 0 1 0 0
    End
    
    Move B
    CORNERS
    1 2 4 8 5 6 3 7
    0 0 2 1 0 0 1 2
    EDGES
    1 2 8 4 5 6 3 11 9 10 7 12
    0 0 0 0 0 0 0 0 0 0 0 0
    End
    Gonna have some fun with this, I always knew there would be a short way to J perm but never thought it'd be like 6 moves.
     
  12. JustinJ

    JustinJ Premium Member

    This is super awesome! I've been thinking about how something like this would be useful recently, and it would be really nice to have this as a library of some kind so people could make GUI solvers easily (I don't mind CLI, but I think a lot of people who want to find algs do). Do you think it might even be possible to compile it to JavaScript with https://github.com/kripken/emscripten/wiki, and then use it to make in-browser solvers easily?
     
  13. Kare

    Kare Member

    21
    0
    Jun 12, 2006
    Sweden
    WCA:
    2004KRIG02
    This is great to see. I have been avoiding any development as I felt a major rewrite was needed to clean up the mess and thanks to the magic of open source I won't have too do that :)

    Something I have been experimenting with but never released is making the computations on multiple cores. A solver is very well suited to parallelization. With OpenMP it's fairly easy to add to a working single threaded program and I know gcc can get it working on both Windows and Linux. If you want any help with OpenMP I would be happy to lend a hand.
     
  14. qqwref

    qqwref Member

    7,833
    25
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Glad this is useful to you guys. I was also thinking of putting up a page of prewritten def files on my site, so if you write up a def file for anything unusual, if you post it or send it over I could put it up.

    If you do want to use ksolve+ as a sort of library you definitely could (it's open source and I don't personally mind if you use it in another project). It should be possible to compile to JS too, although I have a feeling the speed would be a problem (a solver specifically written for your puzzle of choice would probably be faster). You're thinking of a solver for a specific puzzle that comes with a prewritten def file, right?

    Glad I could help :)

    Sure, some help with that would be very useful. Would it slow down the program much on a machine with only one or two cores?
     
  15. JustinJ

    JustinJ Premium Member

    Yeah, pretty much, and that could translate input on a graphical puzzle into something ksolve could solve. Maybe I will look into it when I have a chance.
     
  16. qqwref

    qqwref Member

    7,833
    25
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    I put up a page on my website with a ksolve+ download and a bunch of .def files: http://mzrg.com/rubik/ksolve+/

    I had some new ideas for things to add, so version 1.1 should be coming soon...
     
  17. This thread is proof that only a few people in the world are creators and all others are users.
    It also felt like I was back in 2000 with seeing C++, commandline, missing references, bad downloadlinks.....and then someone asked "can it be used with javascript" :)

    Great work Michael. I will have a look at it this week and see if I can make a def file for one or more puzzles
    BOOKMARKED
     
  18. Gunnar

    Gunnar Member

    231
    0
    May 7, 2006
    Norrköping, Sweden
    WCA:
    2004KRIG01
    YouTube:
    GunnarKrig
    Using openMP

    Kåre is in Manilla for a month so I'm not sure if he will respond here, but I can just tell how I've used openMP to parallelize my own little cube solver.

    My basic searchFunction looks like this. The pragma call will split the for-loop to be run on as many threads as there are cores. You'd have to import the library <omp.h> and I had to link "\MinGW\bin\pthreadGC2.dll" and set the compiler flag -fopenMP. I think you may find more info on openmp.org, since I'm not very good at explaining this. :p

    bool SearchParallel(Cube scramble, int indexEO, int indexCO, int indexCP, int depth)
    {
    if(depth == 0)
    {
    if(scramble.isSolved(indexEO, indexCO, indexCP))
    {
    cout << endl << "Cube is already solved!" << endl;
    return true;
    }
    }

    #pragma omp parallel for
    for(int i = 0; i < nrOfAllowedMoves; i++)
    {
    int move = allowedMoves;
    int newIndexEO = transition.transitionTable_EO[PruningTable::SIZE_PRUNE_EO*i + indexEO];
    int newIndexCO = transition.transitionTable_CO[PruningTable::SIZE_PRUNE_CO*i + indexCO];
    int newIndexCP = transition.transitionTable_CP[PruningTable::SIZE_PRUNE_CP*i + indexCP];
    if(Search(scramble.applyMove(move), newIndexEO, newIndexCO, newIndexCP, depth-1, move, -1, moves[move]))
    found = true;
    }

    return false;
    }


    I also run the creation of the pruning tables in parallel in a manner like this. If the functions execute very quickly the overhead will make it run slower in parallel, but it's great for generating several big pruning tables.

    #pragma omp parallel sections
    {
    #pragma omp section
    {
    generatePruningTableEO(allowedMoves, nrOfAllowedMoves);
    }
    #pragma omp section
    {
    generatePruningTableEP(allowedMoves, nrOfAllowedMoves);
    }
    #pragma omp section
    {
    generatePruningTableCO(allowedMoves, nrOfAllowedMoves);
    }
    }
     
  19. cuBerBruce

    cuBerBruce Member

    912
    4
    Oct 8, 2006
    Malden, MA, USA
    WCA:
    2006NORS01
    YouTube:
    cuBerBruce
    It appears to me that if I specify "ForbiddenPairs" explicitly, the program still forbids certain pairs of its own. For example, if I add:
    Code:
    ForbiddenPairs
    UF UB
    FL UB
    FR UB
    UL UR
    End
    
    to the Helicopter_Cube_6gen.def file, and give it the scramble "UF UB FL", it fails to find any 3-move solutions, even though "UB FL UF" doesn't violate any of the given move restrictions. It finds 11-move solutions. In fact, simply including "FL UB" as a forbidden pair is sufficient to make it fail to find any 3-move solutions.

    One other thing, if I forget to enter a name for a scramble, the program crashes.

    Generally, though, thanks for implementing these improvements.
     
  20. qqwref

    qqwref Member

    7,833
    25
    Dec 18, 2007
    a <script> tag near you
    WCA:
    2006GOTT01
    YouTube:
    qqwref2
    Yes, the program forbids quite a few pairs of its own. The reason for the problem you encountered is that ksolve+ has apparently already forbidden UB FL due to the two moves being parallel (it always forbids one of the two possibilities when it notices this). When you manually forbid the other possibility (FL UB), it cannot generate UB and FL next to each other in either order. Your move sequence is also equivalent to FL UF UB, which I think is also forbidden by the parallel move code. Thus the 3-move solution is blocked. I think this is more of an unintended effect of your command than an actual bug, since it seems like ksolve+ is working properly given its internal list of forbidden move pairs. I'll add some code to deal with this case, but you should never need to use ForbiddenPairs in the way you did.

    I'll look into the nameless scramble thing as well, thanks.
     

Share This Page