# Copter Explorer



## cuBerBruce (Sep 3, 2012)

Copter Explorer is a program for finding optimal solutions for the Curvy Copter puzzle. Currently it is command line based program and does not support jumbling moves (only 180-degree turns). There are versions for both Windows and Mac operating systems. The program uses around 230 MB of RAM when running, and if you save the pruning tables to disk, it will use up about 230 MB of disk space. The program can be used to find optimal solutions up to around 20 moves in a somewhat reasonable amount of time.

The program is fairly simple. You simply run it in a command window, type in a scramble, and it searches for an optimal solution for that scramble. There are a few command line options.

-p causes pruning table files to be generated. This will allow subsequent runs of the program start up much faster. So unless you really don't want to use up over 200 MB of your disk space, it is recommended to use this command line option the first time you run the program. (Files are stored in the current working directory, which is always where the program expects to find them at startup.)

-e causes edge pieces to be ignored in solving. Ideally, the program should consider the puzzle to have 24 solved states, but this mode only considers 1 solved state, such that all U pieces are on the U face, all F pieces are on the F face, etc.

-f causes the program to keep searching after the first solution is found. It will not search deeper than the depth of the first solution found, though. In some cases, solutions that are essentially redundant may be included in the output.

Entering scrambles is fairly straightforward. Letter pairs are used. Either "UF" or "FU" can be used to indicate the up/front edge is to be turned, for example. Spaces can be placed between pairs, but not between the two letters making up a pair. There is currently no way to enter a position directly. You must determine a scramble to generate the position that you want solved.

when prompted to enter a scramble, you can also enter certain "commands" to change the mode of the program. Commands should not be combined on the same line with a scramble or with another command.

"+e" enables edges to be considered during solving.
"-e" disables edges from being considered during solving.
"+f" causes only the first solution found to be output.
"-f" causes the program to continue searching the current depth after a solution is found.

The ZIP file contains one Windows executable and one Mac executable. It should be obvious which is which.


----------



## StachuK1992 (Sep 5, 2012)

Very nice. Do you mind if I see the source?

I haven't used a curvy copter before, but I think I understand what's happening with it now


----------



## pjk (Sep 5, 2012)

Wow, very cool. I'll play with this shortly.


----------



## cuBerBruce (Sep 6, 2012)

StachuK1992 said:


> Very nice. Do you mind if I see the source?
> 
> I haven't used a curvy copter before, but I think I understand what's happening with it now



Copter Explorer is sort of a work in progress, so I don't think I really want to share source code at this time.

Probable features for the next version are:
- improved pruning for faster/deeper searches; for example, using current pruning table for face pieces for more than one choice of 3 orbits.
- improved "canonicalization" of move sequences to better avoid essentially redundant sequences. This will mean less time "wasted" time in searching, so it should also speed up searching. The curvy copter has 17 maximal sets of commuting moves. Regular nxnxn cubes, on the other hand, have only 3, with no moves in more than one maximal set. So canonicalization is much trickier for the curvy copter.
- 2-phase (or maybe 3-phase) sub-optimal solver to allow solving random positions. Currently looking at solving to <UF, UB, UL, UR, FR, BR> subgroup for phase 1 (essentially making a "double X-cross").

Eventual desired features:
- GUI
- support of jumbling moves
- partial solving (ignore pieces, ignore orientation or permutation of corner pieces, etc.)


----------



## StachuK1992 (Sep 6, 2012)

Why the Curvy Copter? I haven't seen an influx in interest, so I'm curious "Why this?" rather than SQ-1, skewb or anything else a bit more known.
Do you just have a personal interest?


----------



## ben1996123 (Sep 6, 2012)

What language did you make it in?


----------



## cuBerBruce (Sep 6, 2012)

StachuK1992 said:


> Why the Curvy Copter? I haven't seen an influx in interest, so I'm curious "Why this?" rather than SQ-1, skewb or anything else a bit more known.
> Do you just have a personal interest?



Well, I bought one at U.S. Nationals, so I actually have one now. And to my knowledge, algs for the Curvy Copter have pretty much been "hand-crafted" ones, until now.



ben1996123 said:


> What language did you make it in?



C++


----------



## pjk (Sep 21, 2012)

What version of Mac OS is this written for? I am using Mac OSX 10.5.8 (older, I know), and when I open it in Terminal I get:


> /Users/patkelly/Desktop/CopterExplorer/CopterExplorerMac ; exit;
> Patrick-Kellys-Computer-2:~ patkelly$ /Users/patkelly/Desktop/CopterExplorer/CopterExplorerMac ; exit;
> -bash: /Users/patkelly/Desktop/CopterExplorer/CopterExplorerMac: Bad CPU type in executable
> logout
> ...


----------



## cuBerBruce (Sep 22, 2012)

pjk said:


> What version of Mac OS is this written for? I am using Mac OSX 10.5.8 (older, I know)



I compiled it on a MacBook Pro running Lion 10.7.4. Perhaps your Mac has a PowerPC instead of an Intel processor. I'm not sure if I can can build a PowerPC version.

I'm probably near having version 2. Simple 2-phase solver trying 24 cube orientations, and faster optimal solver.


----------



## pjk (Sep 22, 2012)

cuBerBruce said:


> I compiled it on a MacBook Pro running Lion 10.7.4. Perhaps your Mac has a PowerPC instead of an Intel processor. I'm not sure if I can can build a PowerPC version.
> 
> I'm probably near having version 2. Simple 2-phase solver trying 24 cube orientations, and faster optimal solver.


Weird. I'm using an Intel. If you could run it on 10.7, I'd think 10.8 would work.

To anyone reading this: anyone else with a Mac try this? If so, what OS version?


----------



## cuBerBruce (Sep 22, 2012)

pjk said:


> Weird. I'm using an Intel. If you could run it on 10.7, I'd think 10.8 would work.
> 
> To anyone reading this: anyone else with a Mac try this? If so, what OS version?



Ok, I've compiled it now for "i386" architecture. I hope this will work for you.


----------



## pjk (Sep 22, 2012)

cuBerBruce said:


> Ok, I've compiled it now for "i386" architecture. I hope this will work for you.


I have Intel Core Duo. It is 32 bit. Ran that one and get:


> /Users/patkelly/Desktop/CopterExplorerMac32 ; exit;
> Patrick-Kellys-Computer-2:~ patkelly$ /Users/patkelly/Desktop/CopterExplorerMac32 ; exit;
> dyld: unknown required load command 0x80000022
> Trace/BPT trap
> ...


----------



## cuBerBruce (Sep 26, 2012)

OK, I've built another Copter Explorer binary for the Mac. I built this one from XCode rather than straight from gcc. It's actually supposed to be a fat binary supporting both 32-bit and 64-bit (Intel-based) Macs. My version of XCode seems to say it's only compatible back to 10.6, so it might not be compatible with 10.5.x. Since it's just basically platform-independent C++ source code, hopefully it will work on 10.5.x anyway.


----------



## pjk (Sep 26, 2012)

cuBerBruce said:


> OK, I've built another Copter Explorer binary for the Mac. I built this one from XCode rather than straight from gcc. It's actually supposed to be a fat binary supporting both 32-bit and 64-bit (Intel-based) Macs. My version of XCode seems to say it's only compatible back to 10.6, so it might not be compatible with 10.5.x. Since it's just basically platform-independent C++ source code, hopefully it will work on 10.5.x anyway.


I appreciate you working with me on this. It would be nice if someone else with a Mac was testing this so we know it isn't just me experiencing these issues. I just loaded up that one in Terminal and get the same error I got last time:


> /Users/patkelly/Desktop/CopterExplorerMac ; exit;
> dyld: unknown required load command 0x80000022
> Trace/BPT trap
> logout
> ...


----------



## cuBerBruce (Sep 27, 2012)

pjk said:


> I appreciate you working with me on this. It would be nice if someone else with a Mac was testing this so we know it isn't just me experiencing these issues. I just loaded up that one in Terminal and get the same error I got last time:


OK, I researched the error message that pjk was getting and think I've built a version that will fix that problem. This binary has only a 32-bit (Intel) executable, but it seems to still run on a 64-bit Lion machine. I still don't know if there may be other compatibility issues with a Leopard-based machine. (And I've gone back to building via command line rather than XCode.)


----------



## pjk (Sep 27, 2012)

cuBerBruce said:


> OK, I researched the error message that pjk was getting and think I've built a version that will fix that problem. This binary has only a 32-bit (Intel) executable, but it seems to still run on a 64-bit Lion machine. I still don't know if there may be other compatibility issues with a Leopard-based machine. (And I've gone back to building via command line rather than XCode.)


Bingo, that worked well, thanks. Took about 4 minutes to build the pruning tables, and then worked excellent.



> You must determine a scramble to generate the position that you want solved.



It would be awesome to have a scramble generator for a specific state that is entered in, so the optimal solution to any scramble can be found.


----------



## cuBerBruce (Sep 27, 2012)

pjk said:


> Bingo, that worked well, thanks. Took about 4 minutes to build the pruning tables, and then worked excellent.



Great! In 10.6, Apple added a new format in executable binaries that prior OS versions don't understand. I had to change an environment variable so the linker would use the format that 10.5 understands.



pjk said:


> It would be awesome to have a scramble generator for a specific state that is entered in, so the optimal solution to any scramble can be found.



Accepting scrambles was a simple and easy way to guarantee it only tries to solve a legal puzzle position, and converting to the internal puzzle representation was easy too. I think I can figure out if a position is solvable by quickly solving EO and CP, and then check the parities of the face piece orbits. Any suggestion on an input format?

Also, the optimal solver isn't good enough to find solutions for random positions in reasonable time. The next version will have significantly better performance, but it still may have trouble solving typical random positions in a reasonable amount of time. Its 2-phase solver should be able to solve random positions in reasonable time, but the solutions won't generally be optimal.


----------



## qqwref (Sep 27, 2012)

cuBerBruce said:


> Any suggestion on an input format?


I think this demands a graphical interface because in a given random scramble on a non-pillowed copter it can be very tough to tell which face goes where (and it does matter). If you must use text, you could ask for corner placements like ACube and then do centers by asking the user to list the four sticker colors on each face (e.g. UUUL FRDB ....) in a Speffz-like order. It'll be ugly though.


----------



## pjk (Sep 27, 2012)

cuBerBruce said:


> Accepting scrambles was a simple and easy way to guarantee it only tries to solve a legal puzzle position, and converting to the internal puzzle representation was easy too. I think I can figure out if a position is solvable by quickly solving EO and CP, and then check the parities of the face piece orbits. Any suggestion on an input format?


Although a GUI would be nice, I can think of a couple ways that would be doable w/o it. First one would be to use letters A-L on each side of the puzzle to define a position. In some order such as: Top Front Right Back Left Bottom. A-D would label corners, E-H would label centers, I-L would label edges. Each position color could be defined by 1 of 6 letters to define a color. Such as this image:






The other option would be similar, but instead, just use A-L left to right on each face going down in 3 rows, as shown in this image:





So basically an input for 1 face would like like: RGBYGWYORBGY, and there would be 6 12-letter groups to define the puzzle.


----------



## cuBerBruce (Sep 27, 2012)

qqwref said:


> I think this demands a graphical interface because in a given random scramble on a non-pillowed copter it can be very tough to tell which face goes where (and it does matter). If you must use text, you could ask for corner placements like ACube and then do centers by asking the user to list the four sticker colors on each face (e.g. UUUL FRDB ....) in a Speffz-like order. It'll be ugly though.





pjk said:


> Although a GUI would be nice, I can think of a couple ways that would be doable w/o it. First one would be to use letters A-L on each side of the puzzle to define a position. In some order such as: Top Front Right Back Left Bottom. A-D would label corners, E-H would label centers, I-L would label edges. Each position color could be defined by 1 of 6 letters to define a color. ... (image omitted)
> 
> The other option would be similar, but instead, just use A-L left to right on each face going down in 3 rows, ... (image omitted)
> 
> So basically an input for 1 face would like like: RGBYGWYORBGY, and there would be 6 12-letter groups to define the puzzle.



PJK's scheme, especially the 2nd version, is much like what I implemented for my 4x4x4 solver. One thing I like about his first scheme is that the edges are all last (per face) - and you can just leave that part off for the edgeless copter. (And yes, I should really support the edgeless copter properly.)

Face order and orientation also needs specifying. For face order and orientation, I used this model of flattening the cube (in my 4x4x4 solver):


```
U
L F R B
  D
```

An ACube-like scheme like qqwref mentioned may make more sense than pjk'scheme if I get around to supporting ACube-like features. (It's also a reasonable scheme even if I don't support ACube-like features.)

I am not sure if I'll get around to supporting jumbling. These schemes will work if only cubeshape states are allowed as input, but should non-cubeshape states be allowed as input (if jumbling is ever supported)? I don't think we need to worry about this now, but one might think about how a scheme could be extended for jumbled states.

I'm kind of thinking of having the GUI be a separate front end program written a GUI-friendly language, possibly platform-specific (as in C# or Objective C with Cocoa).


----------



## cuBerBruce (Oct 7, 2012)

Copter Explorer Ver 2.0 is now available.

There are several new features in version 2.0.

The main enhancements are improved performance in the optimal solver and a simple two-phase suboptimal solver that can solve most positions in a reasonable time frame. To support these features, the amount of memory used by the program has increased to around 400 MB, and even more during the creation of the pruning tables. It is probably desirable to have at least 1 GB of RAM on the computer.

Optimal Solver Enhancements

The face pieces pruning table has been changed to allow deeper pruning without using more memory. It is also used for two different sets of 18 face pieces instead of one set of 18 face pieces.

A pruning table for corner permutation and edge orientation has been added instead of a pruning function based upon edge orientation only.

The "search space" of maneuvers is further restricted through better taking into account of commuting moves. (I have not proven that this new "smart" logic could result in the solver missing the optimal solution for maneuvers longer than 8 moves. However, I think the performance boost is generally worth it. The "-s" optional allows disabling this "smart" logic.

Two-Phase Solver

The two-phase solver solves a "double-X-Cross" (adjacent slots) for the first phase. It does an iterative deepening across 24 possible cube orientations for defining the double X-Cross. Those cube orientations producing the lowest number of 1st phase moves are then used for phase 2. Phase 2 solves are aborted whenever the move count exceeds the best move count achieved so far. So you might get multiple two-phase solutions. Phase 2 uses only 6 of the 12 moves - only the moves that are generally necessary to use after the double-X-Cross is made.

Other Changes

Some minor changes have been implemented in the user interface. Input text is no longer case sensitive. There is better handling of bad input. The optimal solver prints the time at the start and end of the search. There are other minor changes users of version 1.0 will probably notice.

Mode change commands now include:
-e ignore the edge pieces (as in the plain helicopter puzzle)
+e include edge pieces

Note: When edge pieces are ignored, the cube is still not considered solved unless the U face has the U colored stickers, the F face has the F colored stickers, etc. It really should allow the cube to be in any orientation, but that's not supported yet.

-f keeps searching the current depth after a solution is found in the optimal solver
+f makes search stop when the first solution is found in the optimal solver

-o use two-phase solver
+o use optimal solver

-s use old maneuver search space logic
+s use "smart" maneuver search space logic

The "e" and "s" options affect both the optimal solver and the two-phase solver.

The "-" options can also be specified on the command line (must be separate command arguments) to override the default mode.

The file CopterExplorerV2.zip file contains a Windows 32-bit executable, and a Mac 64-bit executable for OSX 10.7 ("Lion") and later. It also contains a text file with a brief description of the changes in Version 2.0. The fiole CopterExplorerV2Mac105.zip) contains an executable for OSX 10.5 ("Leopard"). The executable only supports Intel-based Macs, but both 32- and 64-bit are supported. For OSX 10.6 ("Snow Leopard"), the "Lion" executable may work for a 64-bit computer - otherwise I think the "Leopard" one should work. Let me know of any problems.

(Sorry, I couldn't upload as a single .zip because of size restrictions.)


----------

