ksolve+ v1.0 - general-purpose algorithm finder

[cuBerBruce]

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.

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.

 

[qqwref]

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.

 

[qqwref]

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.

 

[Lucas Garron]

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!)

 

[qqwref]

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.

 

[qqwref]

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 ) 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

 

[qqwref]

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

 

[MarcoRossi]

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?

 

[Kare]

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.

 

[Kirjava]

Aww yea, I knew this would come in handy

# 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

 

[Robert-Y]

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

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.

 

[Robert-Y]

Here's a fun 3x3x3 one

(Just T perm and rotations!)

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

 

[DrKorbin]

If def-file or file with scrambles has an empty line at the end, the program crashes.

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

 

[cubizh]

If def-file or file with scrambles has an empty line at the end, the program crashes.

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:

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

 

[Lucas Garron]

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

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

 

[Lucas Garron]

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

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.

Inline functions?

 

[cubizh]

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

I'm having problems compiling (actually linking) with gcc 4.7.3, it doesn't seem to recognize OpenMP for some reason.

EDIT: Fixed.

 

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

 

[Lucas Garron]

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

 

[rokicki]

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

Unfortunately, memory usage blows up in the browser (I quickly hit 600MB on the 3x3x3 RFU example).

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