• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Jaap's Square-1 Solver with 'Ignore pieces' functionality

dougbenham

Member
Joined
Mar 19, 2009
Messages
152
Location
Arizona
Okay so.. I know that many people have been looking for something like this. Over the past 2 days I have spent about 8 hours reading over Jaap's square-1 solver code (C++, which i'm not even familiar with). It was pretty insane how this thing works.

Okay so I've done a few modifications:
  • Simple aesthetic changes
  • Perhaps a solution is found at a depth of 5, if you want to search further, you are now prompted to do so
  • Pieces can be ignored
  • The solver can attempt to solve using only (U and R2) or (D and R2)

Now this program is in a beta version. And I would like to first ask about the legality of distributing this program to you all.

My biggest worry is that I can't release this program because of the following line:
"by Jaap Scherphuis, [email protected], copyright 2003."
Which is located in the readme file distributed with his original work.

Am I in the legal realms if I decide to distribute this to you all?
 

jazzthief81

Premium Member
Joined
Jul 17, 2007
Messages
301
WCA
2003VAND01
YouTube
Visit Channel
Doug, I'm excited to try out your modified solver! :)

I'm very curious to know how you dealt with the pruning tables when you ignore pieces or restrict the moves.

When you restrict the moves, you can still use the same tables but they will be much less effective because the values inside it will be big underestimates.

When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all. If you use the same pruning tables as is, you will probably miss solutions because the values inside it aren't necessarily underestimates.
 
Last edited:

Johannes91

Member
Joined
Mar 28, 2006
Messages
1,341
When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all.
Or generate new tables. If many pieces are ignored they'll take much less memory.
 
Last edited:

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
Doug, I'm excited to try out your modified solver! :)

I'm very curious to know how you dealt with the pruning tables when you ignore pieces or restrict the moves.

When you restrict the moves, you can still use the same tables but they will be much less effective because the values inside it will be big underestimates.

When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all. If you use the same pruning tables as is, you will probably miss solutions because the values inside it aren't necessarily underestimates.
You are only excited because you will finally be able to solve the bandaged square-1 (U and R2 feature) ;)

Also,
Posts: 5,000
which means that I am probably going to do that 5000 cubes in a row solve next weekend!
 

jazzthief81

Premium Member
Joined
Jul 17, 2007
Messages
301
WCA
2003VAND01
YouTube
Visit Channel

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
Doug, I'm excited to try out your modified solver! :)
You are only excited because you will finally be able to solve the bandaged square-1 (U and R2 feature) ;)
Shhhhht! :)

Also,
Posts: 5,000
which means that I am probably going to do that 5000 cubes in a row solve next weekend!

Need some help?
A cube meeting might get organised that weekend. More details tonight
 

deadalnix

Member
Joined
Apr 6, 2007
Messages
560
WCA
2008SECH01
Come to nantes open and do this there ! (and bring me with you in you, I'm in Amsterdam :D).

More seriously, if the solution is underestimate in the prunning table, we will only loose time, but not miss solution. I don't understand what you mean lars . . .
 

Johannes91

Member
Joined
Mar 28, 2006
Messages
1,341
More seriously, if the solution is underestimate in the prunning table, we will only loose time, but not miss solution.
The depths in the pruning table are lower bounds. If these are actually not lower-bounds and there could be shorter solutions, the search will back-track and miss them.

For example, the pruning table could give depth 5 for some position, but if some pieces are ignored, there might be a 4-move solution. If the search has exactly 4 moves left, it will back-track and miss the solution, because the pruning table said that the position can't be solved in less than 5 moves.
 
Last edited:

jazzthief81

Premium Member
Joined
Jul 17, 2007
Messages
301
WCA
2003VAND01
YouTube
Visit Channel
More seriously, if the solution is underestimate in the prunning table, we will only loose time, but not miss solution.

Yes, that's exactly what I meant when I talked about restricting moves, because restricting moves will only make the solutions longer:
When you restrict the moves, you can still use the same tables but they will be much less effective because the values inside it will be big underestimates.

But when you ignore pieces, solutions will get shorter and the pruning values are not necessarily underestimates anymore and hence the conclusion:
If you use the same pruning tables as is, you will probably miss solutions because the values inside it aren't necessarily underestimates.
I don't know how Doug implemented the 'ignore pieces' functionality, but I'm guessing he still fills up those positions on the puzzle with actual pieces and simply doesn't check those pieces to determine whether a position is solved.
 

masterofthebass

Premium Member
Joined
May 13, 2007
Messages
3,923
Location
Denver, CO
WCA
2007COHE01
YouTube
Visit Channel
as for the copyright issue:

I would assume that the open source nature of the program could maybe allow the copyright to fall under one of the many open source licenses that exist. Jaap doesn't explicitly mention how his work is copyrighted, and with the vagueness that he uses, the copyright could technically only apply to the contents of the readme ;)
 

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
Come to nantes open and do this there ! (and bring me with you in you, I'm in Amsterdam :D).
I actually considered that, but 5000 (+ some) solves will really take me the entire weekend. Driving and a competition would really distract me.

masterofthebass: please don't confuse open source and licensing!
 

Johannes91

Member
Joined
Mar 28, 2006
Messages
1,341
I would assume that the open source nature of the program could maybe allow the copyright to fall under one of the many open source licenses that exist.
When someone releases code under a license, he still keeps the copyright, but gives other people permission to use the code under some conditions. This surely needs to be explicit. Assuming that you can use some work under the conditions of <insert your favourite license here> without asking the author isn't ok.

Jaap doesn't explicitly mention how his work is copyrighted, and with the vagueness that he uses, the copyright could technically only apply to the contents of the readme ;)
There's actually no need to mention it at all under the Berne Convention. If you can show that you're the author, you have the copyright even if you haven't said it anywhere.
 
Last edited:

deadalnix

Member
Joined
Apr 6, 2007
Messages
560
WCA
2008SECH01
Ha yes, that's obvious :D

I was thinking about limitations moves (that can only incrase the solution size) but you are right, the pruning table computation have to be remade for ignored pieces.
 

Mike Hughey

Administrator
Staff member
Joined
Jun 7, 2007
Messages
11,303
Location
Indianapolis
WCA
2007HUGH01
SS Competition Results
YouTube
Visit Channel
Also,
Posts: 5,000
which means that I am probably going to do that 5000 cubes in a row solve next weekend!
Ugh. I've been enjoying the fact that I've occasionally beaten you on 3x3x3 speedsolving in the weekly competitions the past few weeks. I suspect that after you do this, I'll once again be as far behind you on 3x3x3 speedsolving as I was a year or two ago.

:)

Looking forward to seeing Arnaud averaging sub-20!
 

AvGalen

Premium Member
Joined
Jul 6, 2006
Messages
6,857
Location
Rotterdam (actually Capelle aan den IJssel), the N
WCA
2006GALE01
YouTube
Visit Channel
Also,
Posts: 5,000
which means that I am probably going to do that 5000 cubes in a row solve next weekend!
Ugh. I've been enjoying the fact that I've occasionally beaten you on 3x3x3 speedsolving in the weekly competitions the past few weeks. I suspect that after you do this, I'll once again be as far behind you on 3x3x3 speedsolving as I was a year or two ago.

:)

Looking forward to seeing Arnaud averaging sub-20!
I have done all monthly competitions twice (keyhole, then F2L) in one sitting yesterday. That were 24 * 6 * 2 = 288 solves in a row. It took about 4 hours, including scrambling, inspection, writing down times, etc. I will post those results tonight and will try to see if there is an upward or downward trend in these results.

I am expecting you to easily beat me on 3x3x3 next week because my hands will probably hurt quite a lot. ;)

If you want to keep up with me, can I suggest you doing a 2500++ round? You actually have kids that can scramble for you, so you should be able to do that in about 20 hours
 

dougbenham

Member
Joined
Mar 19, 2009
Messages
152
Location
Arizona
okay so I just got home from school. now it seems that you are all quite familiar with the problems that are faced with implementing this new functionality. now first things first, i emailed jaap and he said
"Yes, go right ahead.My only condition is something you would have done anyway, and that is that you include something like 'Based on code written by Jaap Scherphuis' and the url to my site."
So I made a change to the program, at the start of the program it displays, "Jaap's Square-1 Optimizer v2.0 BETA http://www.jaapsch.net/ (modified by Doug Benham, [email protected])".

now before i give you the link to the BETA version of the modified solver, there are some things i must address.

"Perhaps a solution is found at a depth of 5, if you want to search further, you are now prompted to do so"
Quite simple feature, if a certain depth returns solution(s), the program displays the following line, "Continue searching? (type 'n' then press enter to stop, otherwise just press enter)", and proceeds accordingly. Quite a straight-forward change, the reason I did this was to give the option to find less than optimal solutions.

"Pieces can be ignored"
There is now another argument that you can supply to the solver. In the following format: "sq1optim A2B3C1D45E6F7G8H -t ----------------".
Now in place of each '-' you can place a certain character to specify the target piece.
  • - = Exact match
  • X = Any edge (top/bottom)
  • Y = Any corner (top/bottom)
  • K = Top layer edge
  • L = Bottom layer edge
  • M = Top layer corner
  • N = Bottom layer corner

"The solver can attempt to solve using only (U and R2) or (D and R2)"
There are 2 more new arguments that can optionally be supplied to the solver. '-onlytop' and '-onlybottom'. Quite simple to get the functionality working.. However, the pruning tables will not treat this well.

Last and most important issue
The pruning tables.. I have not done anything to them. Now of course you are asking, "Won't this result in unoptimized solutions?!". The answer is yes. For the moment I have only implemented the functionality of these features. Now there is a little quick and dirty fix that can help those pruning tables out. In the search() function there are a few lines of code:
Code:
if( pr1.table[shp ][e0][c0]>l+1 ) return(0);
if( pr2.table[shp ][e1][c1]>l+1 ) return(0);
if( pr2.table[shp2][e2][c2]>l+1 ) return(0);

which I changed to:
Code:
if( pr1.table[shp ][e0][c0]>l+[B]pruneamount[/B] ) return(0);
if( pr2.table[shp ][e1][c1]>l+[B]pruneamount[/B] ) return(0);
if( pr2.table[shp2][e2][c2]>l+[B]pruneamount[/B] ) return(0);

The prune amount is another optional argument that can be supplied to the solver. '-p x', x is the prune amount. By default it is 2. I would recommend a low # such as 1, 2, 3, 4, or 5. The higher the number, the less solutions the pruning will throw out, thus the more computing time necessary to find a solution. However, the lower the number, the more likely that the solver will throw out a more optimal solution.

Hopefully this little feature will result in less of the solutions being thrown out as they are deemed suboptimal. However, this is a temporary solution and is not a good solution. I know.. you all saw the topic's title and had your hopes up high. But this project will continue and I will soon have the program functioning with correct pruning tables.

Now as for the download.. https://u.pcloud.link/publink/show?code=XZtaB97Z1Pk778JswCYfxwpKb3CoIhStK12y. It includes the newly compiled exe and the modified c++ source code file.


When you ignore pieces you can generate all equivalent cases and look them up in the table and take the minimum value, or you can decide not to use the pruning tables at all.
Or generate new tables. If many pieces are ignored they'll take much less memory.

Could you perhaps help me out in doing this? I'm not sure how to go about this. I've looked at JACube's source code a bit and I'm not sure how the 'ignored pieces' functionality is being put into the pruning tables.
 
Last edited:

dougbenham

Member
Joined
Mar 19, 2009
Messages
152
Location
Arizona
Here's an example for this case:
edgestop12.png
edgesbottom12.png
(Source: http://www.cubezone.be/square1step3.html)

Position denotes a 3 cycle of edges, including the DF, UB, and UL edges. The target state says that the only thing that matters is the orientation (all pieces must be in their correct layers, not correct position). -a states that all solutions must be found. -m states that the middle layer doesn't matter. The -w states that the solution should be optimal in the twist metric. The -p 5 helps ensure that no optimal solutions are missed. -onlytop states that only the U and R2 moves can be made (no D moves).

"sq1optim A2B5C3D41E6F7G8H -t MKMKMKMKLNLNLNLN -a -m -w -p 5 -onlytop"

Here is the output:
"Jaap's Square-1 Optimizer v2.0 BETA http://www.jaapsch.net/ (modified by Doug Benham, [email protected])

Initializing...
5. Shape transition table
4. Colouring 1 transition table
3. Colouring 2 transition table
2. Colouring 1 pruning table
1. Colouring 2 pruning table
0. Finished.

Flags: Twist Metric, Find All Solutions
Position to solve: A2B5C3D41E6F7G8H
Searching depth 0..
Searching depth 1..
Searching depth 2..
Searching depth 3..
Searching depth 4..
Searching depth 5..
Searching depth 6..
Searching depth 7..
Searching depth 8..
Searching depth 9..
Searching depth 10..
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/2,0 [10|21]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/5,0 [10|21]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/8,0 [10|21]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/10,0/11,0 [10|21]
Continue searching? (type 'n' then press enter to stop, otherwise just press enter)

Searching depth 11..
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/2,0 [11|23]
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/5,0 [11|23]
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/8,0 [11|23]
4,0/3,0/2,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/10,0/11,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/2,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/5,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/8,0 [11|23]
4,0/5,0/3,0/1,0/2,0/2,0/1,0/3,0/3,0/1,0/9,0/11,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/2,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/5,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/8,0 [11|23]
4,0/5,0/3,0/3,0/2,0/1,0/1,0/2,0/3,0/4,0/6,0/11,0 [11|23]
Continue searching? (type 'n' then press enter to stop, otherwise just press enter)"

So at depth 10, I decided to continue searching for more solutions, resulting in the depth 11 solutions being found.

If you have any questions, suggestions, or if you have a way to fix the pruning table problem, let me know!
 

deadalnix

Member
Joined
Apr 6, 2007
Messages
560
WCA
2008SECH01
To fix the prunning table issue, I simply suggest to compute table with the following flag :

1/ ignoring edge
2/ edge corect orientation
3/ edge corect permutation

1/ ignoring corners
2/ corners corect orientation
3/ corners corect permutation

The number of table to précompute isn't so important. I you have 2 "don't care permutation" edges, then use the 2 and if you have 2 "don't care orientation" edges, then use the 1 . The pruning table can be sub-optimal in these case, but allox an optimal solution to be found.

To allow automated computations, you should add a paramter xxx move more than optimal and xxx move max instead of press n or enter.
 
Top