Towers of Hanoi Genetic Programming Example

Towers of Hanoi

This page provides an example of using the OakGP genetic programming Java framework to evolve suitable candidates for solving the "Towers of Hanoi" puzzle.
For an overview of OakGP please read the getting started with OakGP guide.

Problem Description
Approach
Configuration
   User Defined Types
   Return Type
   Variable Set
   Constant Set
   Function Set
Java Source Code
Output

Problem Description

The Towers of Hanoi is a game played with three poles and a number of discs of different sizes which can slide onto any pole. The game starts with all the discs stacked in ascending order of size on one pole, the smallest at the top. The aim of the game is to move the entire stack to another pole, obeying the following rules:

Only one disc may be moved at a time.
Each move consists of taking the upper disc from one of the poles and sliding it onto another pole.
No disc may be placed on top of a smaller one.

Approach

The following classes were created to represent the components of a Towers of Hanoi puzzle:

Pole - an enum that has a value for each of the three poles.
Move - an enum that represents all of the possible moves. Each Move contains a reference to the Pole that it would remove a disc from and the Pole it would move a disc to.
TowersOfHanoi - objects of this class represent a particular state of a Towers of Hanoi puzzle.

The following implementations of org.oakgp.function.Function were created for inclusion in the the function set used to construct a solution to this puzzle:

IsValid - returns a Boolean indicating if a specified Move would be a valid next move for the specified TowersOfHanoi.
Next - returns an Integer indicating the upper (i.e. top) disc of the specified Pole in the specified TowersOfHanoi.

The fitness of potential solutions is determined by TowersOfHanoiFitnessFunction, which implements org.oakgp.rank.fitness.FitnessFunction.

The genetic programming run is configured in TowersOfHanoiExample using a org.oakgp.util.RunBuilder.

Configuration

User Defined Types

Type	Class
`pole`	`org.oakgp.examples.hanoi.Pole`
`move`	`org.oakgp.examples.hanoi.Move`
`gameState`	`org.oakgp.examples.hanoi.TowersOfHanoi`

Return Type

Type	Description
`move`	The next move.

Variable Set

ID	Type	Description
`v0`	`gameState`	The current state of the puzzle.
`v1`	`nullableType [move]`	The previous move. Will be `null` on first move.

Constant Set

Type	Values
`integer`	`0`
`boolean`	`Boolean.TRUE`
`pole`	`Pole.LEFT, Pole.MIDDLE, Pole.RIGHT`
`move`	`Move.LEFT_MIDDLE, Move.LEFT_RIGHT, Move.MIDDLE_LEFT, Move.MIDDLE_RIGHT, Move.RIGHT_LEFT, Move.RIGHT_MIDDLE`

Function Set

Class:	`org.oakgp.examples.hanoi.IsValid`
Symbol:	`valid?`
Return Type:	`boolean`
Arguments:	`gameState, move`

Class:	`org.oakgp.examples.hanoi.Next`
Symbol:	`next`
Return Type:	`integer`
Arguments:	`gameState, pole`

Class:	`org.oakgp.function.choice.If`
Symbol:	`if`
Return Type:	`move`
Arguments:	`boolean, move, move`

Class:	`org.oakgp.function.choice.SwitchEnum`
Symbol:	`switch`
Return Type:	`move`
Arguments:	`nullable [move], move, move, move, move, move, move, move`

Class:	`org.oakgp.function.compare.Equal`
Symbol:	`=`
Return Type:	`boolean`
Arguments:	`move, move`

Class:	`org.oakgp.function.compare.Equal`
Symbol:	`=`
Return Type:	`boolean`
Arguments:	`integer, integer`

Class:	`org.oakgp.function.compare.GreaterThan`
Symbol:	`>`
Return Type:	`boolean`
Arguments:	`integer, integer`

Class:	`org.oakgp.function.compare.LessThan`
Symbol:	`<`
Return Type:	`boolean`
Arguments:	`integer, integer`

Java Source Code

org/oakgp/examples/hanoi/Pole.java

package org.oakgp.examples.hanoi;

/** Represents the three poles on which discs can be placed. */
enum Pole {
    LEFT, MIDDLE, RIGHT
}

org/oakgp/examples/hanoi/Move.java

package org.oakgp.examples.hanoi;

/** Represents the possible moves that can be used to attempt to solve the puzzle. */
enum Move {
    LEFT_MIDDLE(Pole.LEFT, Pole.MIDDLE),
    LEFT_RIGHT(Pole.LEFT, Pole.RIGHT),
    MIDDLE_LEFT(Pole.MIDDLE, Pole.LEFT),
    MIDDLE_RIGHT(Pole.MIDDLE, Pole.RIGHT),
    RIGHT_LEFT(Pole.RIGHT, Pole.LEFT),
    RIGHT_MIDDLE(Pole.RIGHT, Pole.MIDDLE);

    /** The pole to remove a disc from. */
    final Pole from;
    /** The pole to add a disc to. */
    final Pole to;

    private Move(Pole from, Pole to) {
       this.from = from;
       this.to = to;
    }
}

org/oakgp/examples/hanoi/TowersOfHanoi.java

package org.oakgp.examples.hanoi;

import java.util.Arrays;

/** Represents an individual state of a Towers of Hanoi puzzle. */
class TowersOfHanoi {
    private static final int NUM_POLES = Pole.values().length;
    /**
     * IDs of the discs, suitable for bitwise operations.
     * <p>
     * 1st element represents the smallest disc, 2nd element represents the medium size disc and the 3rd element represents the large size disc.
     */
    private static final int[] DISC_IDS = { 1, 2, 4 };
    private static final int SUM_DISC_IDS = Arrays.stream(DISC_IDS).sum();

    private final int[] poles;

    TowersOfHanoi() {
       poles = new int[NUM_POLES];
       poles[0] = SUM_DISC_IDS;
    }

    private TowersOfHanoi(int[] poles) {
       this.poles = poles;
    }

    /** @return the ID of the upper (i.e. top) disc of the specified pole, or {code 0} if there are no discs on the pole */
    int upperDisc(Pole pole) {
       return Integer.lowestOneBit(poles[pole.ordinal()]);
    }

    /**
     * Returns fitness value for the state represented by this object.
     * <p>
     * The more discs that are in their required position (i.e. correctly ordered on the middle pole) the lower the fitness value - so the lower the fitness
     * value the better. A fitness value of {@code 0} means all discs are on the middle pole (i.e. the puzzle is complete).
     *
     * @return {@code 0} if the middle pole contains all the discs, or a positive number if the puzzle is not yet complete
     */
    int getFitness() {
       int poleContents = poles[Pole.MIDDLE.ordinal()];
       for (int i = DISC_IDS.length - 1; i > -1; i--) {
          if ((poleContents & DISC_IDS[i]) == 0) {
             return DISC_IDS[i];
          }
       }
       return 0;
    }

    /** @return the result of applying {@code move} to the current state, or {code null} if the move is not valid */
    TowersOfHanoi move(Move move) {
       return move(move.from, move.to);
    }

    private TowersOfHanoi move(Pole from, Pole to) {
       if (from == to) {
          // pointless move
          return null;
       }

       int fromUpperDisc = upperDisc(from);
       int toUpperDisc = upperDisc(to);

       if (fromUpperDisc == 0) {
          // invalid move - cannot move a disc from an empty pole
          return null;
       }
       if (toUpperDisc != 0 && fromUpperDisc > toUpperDisc) {
          // invalid move - no disc may be placed on top of a smaller one
          return null;
       }

       // copy current state
       int[] updatedPoles = Arrays.copyOf(poles, NUM_POLES);
       // remove disc from pole
       updatedPoles[from.ordinal()] -= fromUpperDisc;
       // add disc to pole
       updatedPoles[to.ordinal()] += fromUpperDisc;
       return new TowersOfHanoi(updatedPoles);
    }

    @Override
    public int hashCode() {
       return Arrays.hashCode(poles);
    }

    @Override
    public boolean equals(Object o) {
       return o instanceof TowersOfHanoi && Arrays.equals(poles, ((TowersOfHanoi) o).poles);
    }

    @Override
    public String toString() {
       return Arrays.toString(poles);
    }
}

org/oakgp/examples/hanoi/IsValid.java

package org.oakgp.examples.hanoi;

import static org.oakgp.Type.booleanType;
import static org.oakgp.examples.hanoi.TowersOfHanoiExample.MOVE_TYPE;
import static org.oakgp.examples.hanoi.TowersOfHanoiExample.STATE_TYPE;

import org.oakgp.Arguments;
import org.oakgp.Assignments;
import org.oakgp.function.Function;
import org.oakgp.function.Signature;

/** Determines if a move is a valid move for a particular game state. */
class IsValid implements Function {
    private static final Signature SIGNATURE = Signature.createSignature(booleanType(), STATE_TYPE, MOVE_TYPE);

    @Override
    public Signature getSignature() {
       return SIGNATURE;
    }

    /**
     * @param arguments
     *           the first argument is a {@code TowersOfHanoi} representing a game state and the second argument is a {@code Move}
     * @param assignments
     *           the values assigned to each of member of the variable set
     * @return {@code true} if the specified move is a valid move for the specified game state, else {@code false}
     */
    @Override
    public Object evaluate(Arguments arguments, Assignments assignments) {
       TowersOfHanoi gameState = arguments.firstArg().evaluate(assignments);
       Move move = arguments.secondArg().evaluate(assignments);
       return gameState.move(move) != null;
    }
}

org/oakgp/examples/hanoi/Next.java

package org.oakgp.examples.hanoi;

import static org.oakgp.Type.integerType;
import static org.oakgp.examples.hanoi.TowersOfHanoiExample.POLE_TYPE;
import static org.oakgp.examples.hanoi.TowersOfHanoiExample.STATE_TYPE;

import org.oakgp.Arguments;
import org.oakgp.Assignments;
import org.oakgp.function.Function;
import org.oakgp.function.Signature;

/** Returns the ID of the next disc that would be returned from a particular pole for a particular game state. */
class Next implements Function {
    private static final Signature SIGNATURE = Signature.createSignature(integerType(), STATE_TYPE, POLE_TYPE);

    @Override
    public Signature getSignature() {
       return SIGNATURE;
    }

    /**
     * @param arguments
     *           the first argument is a {@code TowersOfHanoi} representing a game state and the second argument is a {@code Pole}
     * @param assignments
     *           the values assigned to each of member of the variable set
     * @return the ID of the upper (i.e. top) disc of the specified pole, or {code 0} if there are no discs on the pole
     */
    @Override
    public Object evaluate(Arguments arguments, Assignments assignments) {
       TowersOfHanoi gameState = arguments.firstArg().evaluate(assignments);
       Pole pole = arguments.secondArg().evaluate(assignments);
       return gameState.upperDisc(pole);
    }
}

org/oakgp/examples/hanoi/TowersOfHanoiFitnessFunction.java

package org.oakgp.examples.hanoi;

import java.util.HashSet;
import java.util.Set;

import org.oakgp.Assignments;
import org.oakgp.node.Node;
import org.oakgp.rank.fitness.FitnessFunction;

/** Determines the fitness of potential solutions to the Towers of Hanoi puzzle. */
class TowersOfHanoiFitnessFunction implements FitnessFunction {
    private static final TowersOfHanoi START_STATE = new TowersOfHanoi();

    private final boolean doLog;

    TowersOfHanoiFitnessFunction(boolean doLog) {
       this.doLog = doLog;
    }

    /**
     * @param n
     *           a potential solution to the Towers of Hanoi puzzle
     * @return the fitness of {@code n}
     */
    @Override
    public double evaluate(Node n) {
       TowersOfHanoi towersOfHanoi = START_STATE;
       Set<TowersOfHanoi> previousStates = new HashSet<>();
       previousStates.add(towersOfHanoi);

       Move previousMove = null;
       int previousFitness = Integer.MAX_VALUE;
       while (true) {
          // update the puzzle with the next move returned from the potential solution
          Assignments assignments = Assignments.createAssignments(towersOfHanoi, previousMove);
          previousMove = n.evaluate(assignments);
          towersOfHanoi = towersOfHanoi.move(previousMove);
          if (doLog) {
             System.out.println(previousMove + " " + towersOfHanoi);
          }

          if (towersOfHanoi == null) {
             // the last move was invalid - stop evaluating
             return previousFitness;
          }
          if (!previousStates.add(towersOfHanoi)) {
             // the last move has returned the puzzle to a state it has already been in - exit now to avoid getting stuck in a loop
             return previousFitness;
          }
          previousFitness = Math.min(previousFitness, towersOfHanoi.getFitness());
          if (previousFitness == 0) {
             // the puzzle has been solved - no need to keep evaluating
             return previousFitness;
          }
       }
    }
}

org/oakgp/examples/hanoi/TowersOfHanoiExample.java

package org.oakgp.examples.hanoi;

import static java.util.Collections.addAll;
import static org.oakgp.Type.integerType;
import static org.oakgp.Type.nullableType;
import static org.oakgp.Type.type;
import static org.oakgp.util.Utils.createEnumConstants;

import java.util.ArrayList;
import java.util.List;

import org.oakgp.Type;
import org.oakgp.function.Function;
import org.oakgp.function.choice.If;
import org.oakgp.function.choice.SwitchEnum;
import org.oakgp.function.compare.Equal;
import org.oakgp.function.compare.GreaterThan;
import org.oakgp.function.compare.LessThan;
import org.oakgp.function.math.IntegerUtils;
import org.oakgp.node.ConstantNode;
import org.oakgp.node.Node;
import org.oakgp.rank.RankedCandidates;
import org.oakgp.rank.fitness.FitnessFunction;
import org.oakgp.util.RunBuilder;
import org.oakgp.util.Utils;

public class TowersOfHanoiExample {
    static final Type STATE_TYPE = type("gameState");
    static final Type MOVE_TYPE = type("move");
    static final Type POLE_TYPE = type("pole");

    private static final int TARGET_FITNESS = 0;
    private static final int NUM_GENERATIONS = 1000;
    private static final int INITIAL_POPULATION_SIZE = 100;
    private static final int INITIAL_POPULATION_MAX_DEPTH = 4;

    public static void main(String[] args) {
       Function[] functions = { new If(MOVE_TYPE), new Equal(MOVE_TYPE), new IsValid(), new SwitchEnum(Move.class, nullableType(MOVE_TYPE), MOVE_TYPE),
             new GreaterThan(integerType()), LessThan.create(integerType()), new Equal(integerType()), new Next() };
       List<ConstantNode> constants = createConstants();
       Type[] variables = { STATE_TYPE, nullableType(MOVE_TYPE) };
       FitnessFunction fitnessFunction = new TowersOfHanoiFitnessFunction(false);

       RankedCandidates output = new RunBuilder().setReturnType(MOVE_TYPE).setConstants(constants).setVariables(variables).setFunctions(functions)
             .setFitnessFunction(fitnessFunction).setInitialPopulationSize(INITIAL_POPULATION_SIZE).setTreeDepth(INITIAL_POPULATION_MAX_DEPTH)
             .setTargetFitness(TARGET_FITNESS).setMaxGenerations(NUM_GENERATIONS).process();
       Node best = output.best().getNode();
       System.out.println(best);
       new TowersOfHanoiFitnessFunction(true).evaluate(best);
    }

    private static List<ConstantNode> createConstants() {
       List<ConstantNode> constants = new ArrayList<>();
       constants.add(IntegerUtils.INTEGER_UTILS.zero());
       constants.add(Utils.TRUE_NODE);
       addAll(constants, createEnumConstants(Move.class, MOVE_TYPE));
       addAll(constants, createEnumConstants(Pole.class, POLE_TYPE));
       return constants;
    }
}

Output

Below are some examples of solutions generated by TowersOfHanoiExample.

Candidate	Result
`(switch v1 (if (< 0 (next v0 RIGHT)) RIGHT_LEFT LEFT_RIGHT) MIDDLE_RIGHT MIDDLE_LEFT LEFT_MIDDLE RIGHT_MIDDLE LEFT_MIDDLE LEFT_MIDDLE)`	LEFT_MIDDLE [6, 1, 0] LEFT_RIGHT [4, 1, 2] MIDDLE_RIGHT [4, 0, 3] LEFT_MIDDLE [0, 4, 3] RIGHT_LEFT [1, 4, 2] RIGHT_MIDDLE [1, 6, 0] LEFT_MIDDLE [0, 7, 0]
(if (< 0 (next v0 LEFT)) (switch v1 LEFT_RIGHT MIDDLE_RIGHT RIGHT_MIDDLE LEFT_MIDDLE MIDDLE_RIGHT (if (< (next v0 RIGHT) (next v0 LEFT)) LEFT_MIDDLE MIDDLE_RIGHT) LEFT_MIDDLE) (switch v1 RIGHT_MIDDLE RIGHT_LEFT MIDDLE_LEFT LEFT_RIGHT RIGHT_MIDDLE MIDDLE_LEFT RIGHT_MIDDLE))	LEFT_MIDDLE [6, 1, 0] LEFT_RIGHT [4, 1, 2] MIDDLE_RIGHT [4, 0, 3] LEFT_MIDDLE [0, 4, 3] RIGHT_MIDDLE [0, 5, 2] MIDDLE_LEFT [1, 4, 2] RIGHT_MIDDLE [1, 6, 0] LEFT_MIDDLE [0, 7, 0]
`(switch v1 (if (valid? v0 RIGHT_LEFT) RIGHT_LEFT LEFT_RIGHT) MIDDLE_RIGHT LEFT_RIGHT LEFT_MIDDLE RIGHT_MIDDLE LEFT_MIDDLE LEFT_MIDDLE)`	LEFT_MIDDLE [6, 1, 0] LEFT_RIGHT [4, 1, 2] MIDDLE_RIGHT [4, 0, 3] LEFT_MIDDLE [0, 4, 3] RIGHT_LEFT [1, 4, 2] RIGHT_MIDDLE [1, 6, 0] LEFT_MIDDLE [0, 7, 0]
`(if (valid? v0 MIDDLE_LEFT) (switch v1 (if (valid? v0 LEFT_RIGHT) LEFT_RIGHT RIGHT_LEFT) MIDDLE_RIGHT LEFT_MIDDLE LEFT_RIGHT MIDDLE_RIGHT MIDDLE_RIGHT RIGHT_MIDDLE) LEFT_MIDDLE)`	LEFT_MIDDLE [6, 1, 0] LEFT_RIGHT [4, 1, 2] MIDDLE_RIGHT [4, 0, 3] LEFT_MIDDLE [0, 4, 3] RIGHT_LEFT [1, 4, 2] LEFT_MIDDLE [0, 5, 2] RIGHT_LEFT [2, 5, 0] MIDDLE_RIGHT [2, 4, 1] LEFT_MIDDLE [0, 6, 1] RIGHT_LEFT [1, 6, 0] LEFT_MIDDLE [0, 7, 0]
`(switch v1 RIGHT_LEFT LEFT_MIDDLE RIGHT_MIDDLE LEFT_RIGHT (if (valid? v0 MIDDLE_RIGHT) MIDDLE_RIGHT RIGHT_MIDDLE) LEFT_MIDDLE LEFT_RIGHT)`	LEFT_RIGHT [6, 0, 1] LEFT_MIDDLE [4, 2, 1] RIGHT_LEFT [5, 2, 0] MIDDLE_RIGHT [5, 0, 2] LEFT_RIGHT [4, 0, 3] LEFT_MIDDLE [0, 4, 3] RIGHT_LEFT [1, 4, 2] RIGHT_MIDDLE [1, 6, 0] LEFT_MIDDLE [0, 7, 0]