Parabon Sponsored GECCO Competition 2009

Contest Rules

  Interactive CubeTwister applet by Werner Randelshofer. Used with permission.

Competition: Evolve a Rubik's Cube Solver ($2,000 prize)

Goal: Evolve a program that can solve an arbitrarily-scrambled cube in the fewest number of moves (as measured by the face-turn metric).

Background: In conjunction with Dr. Sean Luke of George Mason University and under a research grant from NASA, Parabon has developed the Origin Evolutionary SDK, an extension of Dr. Luke's ECJ framework that runs on the Frontier Grid Platform. This GECCO 2009 competition is intended to exercise and demonstrate the capabilities of performing large-scale evolutionary computation with Frontier and Origin.

Required Tools: Contestants are required to use Parabon's Frontier Grid Service and may optionally use Origin. Free access to the service, at up to 100 C of capacity for a total of 5 kCh, will be granted to contestants to perform evoutionary jobs for the competition through 22 June 2009 (the submission deadline for the competition).  The Frontier SDK comes with a grid simulator that can be used locally for program development and testing, so that time on the grid service can be used to best effect.

To Get Started: 

  1. Sign up for a Frontier account.
  2. Download and install the Frontier SDK. (You will be asked to provide a Username and Password.) 
  3. Email GECCO_2009@parabon.com to let us know you are participating in the competition so we can set your account parameters accordingly.  Please include your Frontier account Username.
  4. Optionally download and install the Origin Evolutionary SDK.  

Documentation for Parabon's Frontier technologies can be found under the Dev Center tab.

Instructions: Contestants are required to evolve a Java™ class using the Frontier Grid Service. The resultant Java™ class must support the following Solver interface:

 /*
* Solver.java
*/

package com.parabon.rubik;
import java.util.List;

/**
* An interface for a class that can solve any arbitrarily scrambled
* Rubik's Cube with the goal of doing so in the minimal number of moves.
*/

public interface Solver {

/**
* Returns a minimal length list of moves that will solve the
* specified cube.
* @param cube an arbitrarily scrambled Rubik's Cube.
* @return a minimal length list of moves that will solve the
* specified cube.
*/

List<Move> solve(Cube cube);
}

Contestants are required to produce:

  1. A jar file containing a Java class that implements the Solver interface, along with any other support classes or data required for its execution — the total size of which is no larger than 1 MB.
  2. A report (5-page limit) that provides details on how the solver was evolved.
  3. All source code used to evolve the solver (to be used only for judging purposes).

Entries will be judged by executing the supplied solver in a judging application that will test it against a set of 1,000 randomly scrambled cubes that will not be made available to contestants in advance. Entries will be assigned one point for each move required to solve each cube; a penalty of 200 points will be added for each cube not solved in less than 200 moves or in less than 10 seconds. Any entry that causes a program exception during its execution will be disqualified.

Final judging decisions will not be based solely on lowest score, but also on the scientific quality and originality of the evolutionary approach by which the class was generated.

Possible quality factors will be:

  • Autonomy (to what extent the program can be considered a human-competitive machine-generated solution; use of published or otherwise human-derived heuristics for solving the cube is strongly discouraged)
  • Simplicity (solutions that do NOT rely on group theoretic decompositions of the cube's permutation space will be favored over those that do)
  • Originality of the evolutionary approach
  • Parsimony (small, elegant solutions are preferred)
  • Quality of the documentation

All entries for the competition should be emailed, as a tar-gzipped or zipped attachment to GECCO_2009@parabon.com by 22 June 2009. Any inquiry regarding the competition should also be emailed to the same address.  To be eligible for the prize, contestants must be willing to give media interviews at the conference.

With permission, Parabon is using the open source Rubiks Cube model created by Werner Randelshofer as the basis for the class FrontierCube. The classes RubiksCube.java and RubiksCubeCore.java form part of Randelshofer's CubeTwister application, which is a prerequisite for compiling the test harness, which will be published soon. The initial state of each test cube can be discovered via the API exposed by these two classes.

Note: The referenced version of CubeTwister is not compatible with Java 1.5 or greater, however, simply changing all variables named enum to enumm will bring the code into 1.5 compliance.
 /*
* FrontierCube.java
*/

package com.parabon.rubik;
import java.util.List;

import ch.randelshofer.rubik.RubiksCube;

public class FrontierCube extends RubiksCube {

void apply(Move move) {
switch (move) {
case F: twistSide(0, false); break;
case F_: twistSide(0, true); break;
case F2: twistSide(0, true);
twistSide(0, true); break;

case R: twistSide(1, false); break;
case R_: twistSide(1, true); break;
case R2: twistSide(1, true);
twistSide(1, true); break;

case D: twistSide(2, false); break;
case D_: twistSide(2, true); break;
case D2: twistSide(2, true);
twistSide(2, true); break;

case B: twistSide(3, false); break;
case B_: twistSide(3, true); break;
case B2: twistSide(3, true);
twistSide(3, true); break;

case L: twistSide(4, false); break;
case L_: twistSide(4, true); break;
case L2: twistSide(4, true);
twistSide(4, true); break;

case U: twistSide(5, false); break;
case U_: twistSide(5, true); break;
case U2: twistSide(5, true);
twistSide(5, true); break;
}
}

void apply(List<Move> moves) {
for (Move m : moves) apply(m);
}

}
 /*
* Move.java
*/

package com.parabon.rubik;

public enum Move {

F("F"), F_("F'"), F2("F2"),
B("B"), B_("B'"), B2("B2"),
U("U"), U_("U'"), U2("U2"),
D("D"), D_("D'"), D2("D2"),
L("L"), L_("L'"), L2("L2"),
R("R"), R_("R'"), R2("R2");

private final String label;
Move(String name) { this.label = name; }
public String toString() { return label; }
}