tictactoemain.java

JGAP是一种遗传算法和遗传规划的组成部分提供了一个Java框架。它提供了基本的遗传机制

/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licensing information please see the file license.txt included with JGAP
 * or have a look at the top of class org.jgap.Chromosome which representatively
 * includes the JGAP license policy applicable for any file delivered with JGAP.
 */
package examples.gp.tictactoe;

import org.jgap.*;
import org.jgap.event.*;
import org.jgap.gp.*;
import org.jgap.gp.impl.*;
import org.jgap.gp.function.*;
import org.jgap.gp.terminal.*;
import org.jgap.util.*;
import org.jgap.impl.*;

/**
 * Example demonstrating Genetic Programming (GP) capabilities of JGAP.<p>
 * Here, a strategy for playing Noughts and Crosses (Tic Tac Toe) is evolved.<p>
 * THIS PROGRAM IS STILL UNDER DEVELOPMENT AND IS NOT FINISHED YET! ANY COMMENTS
 * AND EXTENSIONS ARE VERY WELCOME!
 *
 * @author Klaus Meffert
 * @since 3.2
 */
public class TicTacToeMain
    extends GPProblem {
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.6 $";

  private static Variable vb;

  private Board m_board;

  public TicTacToeMain(GPConfiguration a_conf)
      throws InvalidConfigurationException {
    super(a_conf);
    m_board = new Board();
  }

  public Board getBoard() {
    return m_board;
  }

  /**
   * Sets up the functions to use and other parameters. Then creates the
   * initial genotype.
   *
   * @param a_conf the configuration to use
   * @param a_color the color to create a program for
   * @param a_other an optional opponent, may be null
   * @param a_otherColor color of the opponent
   *
   * @return the genotype created
   *
   * @throws InvalidConfigurationException
   *
   * @author Klaus Meffert
   * @since 3.2
   */
  public GPGenotype create(GPConfiguration a_conf, int a_color,
                           GPGenotype a_other, int a_otherColor)
      throws InvalidConfigurationException {
    Class[] types = {CommandGene.VoidClass, CommandGene.VoidClass,
        CommandGene.VoidClass,
        CommandGene.VoidClass};
    Class[][] argTypes = { {}, {}, {}, {}
    };
    int[] minDepths = new int[] {0, 2, 2, 1};
    int[] maxDepths = new int[] {0, 2, 6, 2};
//    GPConfiguration conf = getGPConfiguration();
    int color = a_color;
    ForLoop forLoop1 = new ForLoop(a_conf, SubProgram.VoidClass, 1, Board.WIDTH,
                                   1, "x", 0, 0);
    ForLoop forLoop2 = new ForLoop(a_conf, SubProgram.VoidClass, 1, Board.HEIGHT,
                                   1, "y", 0, 0);
    Variable vx = new Variable(a_conf, "move", CommandGene.IntegerClass);
    Variable vb = new Variable(a_conf, "firstmove", CommandGene.BooleanClass);
    //
    final String MATRIX1 = "MATRIX1";
    a_conf.createMatrix(MATRIX1, 3, 3);
    //
    CommandGene[][] nodeSets = { {
        // Transfer board to evolution memory.
        // -----------------------------------
        new TransferBoardToMemory(a_conf, m_board, 0, 0),
    }, {
        // Create strategy data.
        // ---------------------
        new Loop(a_conf, CommandGene.IntegerClass,
                 Board.WIDTH * Board.HEIGHT),
        new EvaluateBoard(a_conf, m_board, CommandGene.IntegerClass),
        new IncrementMemory(a_conf, CommandGene.IntegerClass, "counter", 10),
        /**@todo evaluate board to matrix*/
    }, {
        // Evaluate.
        // ---------
        vx,
        vb,
        new SubProgram(a_conf, new Class[] {CommandGene.VoidClass,
                       CommandGene.VoidClass}),
        new SubProgram(a_conf, new Class[] {CommandGene.VoidClass,
                       CommandGene.VoidClass, CommandGene.VoidClass}),
        new SubProgram(a_conf, new Class[] {TransferBoardToMemory.VoidClass,
                       CommandGene.VoidClass}),
        new SubProgram(a_conf, new Class[] {CommandGene.VoidClass,
                       CommandGene.VoidClass, CommandGene.VoidClass,
                       CommandGene.VoidClass}),
//        forLoop1,
//        forLoop2,
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 0),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 1),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 2),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 3),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 10, 22),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 11, 22),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 12, 22),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 13, 22),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 14, 23),
        new EvaluateBoard(a_conf, m_board, 14),
        new Loop(a_conf, SubProgram.class, Board.WIDTH),
        new Loop(a_conf, SubProgram.class, Board.HEIGHT),
        new Loop(a_conf, SubProgram.class, Board.WIDTH * Board.HEIGHT),
        new Constant(a_conf, CommandGene.IntegerClass, new Integer(0)),
        new Constant(a_conf, CommandGene.IntegerClass, new Integer(1)),
        new Constant(a_conf, CommandGene.IntegerClass, new Integer(2)),
        new Constant(a_conf, CommandGene.IntegerClass, new Integer(3)),
        new Terminal(a_conf, CommandGene.IntegerClass, 1.0d, Board.WIDTH, true, 4),
        new Terminal(a_conf, CommandGene.IntegerClass, 1.0d, Board.HEIGHT, true,
                     4),
        new Equals(a_conf, CommandGene.IntegerClass, 0, new int[] {22, 23}),
        new Equals(a_conf, CommandGene.IntegerClass, 0, new int[] {0, 8}),
        new IfElse(a_conf, CommandGene.BooleanClass),
        new ReadBoard(a_conf, m_board, 0, new int[] {4, 4}),
        new ReadBoard(a_conf, m_board),
        new Not(a_conf),
        new Push(a_conf, CommandGene.IntegerClass),
        new Pop(a_conf, CommandGene.IntegerClass),
        new IfIsOccupied(a_conf, m_board, CommandGene.IntegerClass, 0,
                         new int[] {4, 4, 0}),
        new IfIsFree(a_conf, m_board, CommandGene.IntegerClass, 0, new int[] {4,
                     4, 0}),
//        new CountStones(conf, m_board, color, "count", 2),
        new IfColor(a_conf, CommandGene.IntegerClass, color),
        new IsOwnColor(a_conf, color),
        new Increment(a_conf, CommandGene.IntegerClass, 1),
        new Increment(a_conf, CommandGene.IntegerClass, -1),
        new StoreTerminalIndexed(a_conf, 0, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 1, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 2, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 3, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 10, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 11, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 12, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 13, CommandGene.IntegerClass),
        new StoreTerminalIndexed(a_conf, 14, CommandGene.IntegerClass),
        new StoreTerminal(a_conf, "mem0", CommandGene.IntegerClass),
//        new StoreTerminal(conf, "mem1", CommandGene.IntegerClass),
        new AddAndStoreTerminal(a_conf, "memA", CommandGene.IntegerClass),
//        new AddAndStoreTerminal(conf, "memB", CommandGene.IntegerClass),
        new ReadTerminal(a_conf, CommandGene.IntegerClass, "mem0"),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "mem1"),
        new ReadTerminal(a_conf, CommandGene.IntegerClass, "memA"),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "memB"),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "countr0", 1),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "countr1", 1),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "countc0", 8),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "countc1", 8),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "countd0"),
//        new ReadTerminal(conf, CommandGene.IntegerClass, "countd1"),
//        new ReadTerminal(conf, CommandGene.IntegerClass,
//                         forLoop1.getCounterMemoryName(), 5),
//        new ReadTerminal(conf, CommandGene.IntegerClass,
//                         forLoop2.getCounterMemoryName(), 6),
        new ReadFromMatrix(a_conf, MATRIX1),
        new WriteToMatrix(a_conf, MATRIX1),
        new ResetMatrix(a_conf, MATRIX1, ' '),
        new CountMatrix(a_conf, MATRIX1, CountMatrix.CountType.COLUMN,
                        CountMatrix.CountMode.EMPTY, ' ', ' '),
        new ReplaceInMatrix(a_conf, MATRIX1,
                            ReplaceInMatrix.ReplacementMode.COLUMN, "ABC",
                            'R'),
    }, {
        // Make a move.
        // ------------
        vb,
//        vx,
        new Constant(a_conf, CommandGene.IntegerClass, new Integer(1)),
        new Constant(a_conf, CommandGene.IntegerClass, new Integer(2)),
        new Equals(a_conf, CommandGene.IntegerClass),
        new PutStone(a_conf, m_board, color),
        new PutStone1(a_conf, m_board, color, 0, 33),
        new IfIsFree(a_conf, m_board, CommandGene.IntegerClass),
        new IfElse(a_conf, CommandGene.BooleanClass),
        new Increment(a_conf, CommandGene.IntegerClass, 1),
        new Increment(a_conf, CommandGene.IntegerClass, -1),
        new ReadTerminalIndexed(a_conf, CommandGene.IntegerClass, 15, 33),
        new ReadTerminal(a_conf, CommandGene.IntegerClass, "mem0"),
        new ReadTerminal(a_conf, CommandGene.IntegerClass, "mem1"),
        new ReadTerminal(a_conf, CommandGene.IntegerClass, "memA"),
//        new SubProgram(conf, new Class[] {CommandGene.VoidClass,
//                       CommandGene.VoidClass}),

        //        new Terminal(conf, CommandGene.IntegerClass, 1.0d, Board.WIDTH, true),
//        new Terminal(conf, CommandGene.IntegerClass, 1.0d, Board.HEIGHT, true),
//        new IfIsOccupied(conf, m_board, CommandGene.IntegerClass),
    }
    };
    a_conf.setFitnessFunction(new TicTacToeMain.
                            GameFitnessFunction(getBoard(), a_color, a_other,
        a_otherColor));
//    }
    // Create genotype with initial population.
    // ----------------------------------------
    GPGenotype result = GPGenotype.randomInitialGenotype(a_conf, types, argTypes,
        nodeSets, minDepths, maxDepths, 600, new boolean[] {!true, !true, !true, !true}, true);
    // Register variables to later have access to them.
    // ------------------------------------------------
    result.putVariable(vb);
    result.putVariable(vx);
    return result;
  }

  public GPGenotype create()
      throws InvalidConfigurationException {
    throw new InvalidConfigurationException(
        "Please use create(Board a_board, int a_color)");
  }

  /**
   * Starts the example.
   *
   * @param args ignored
   * @throws Exception
   *
   * @author Klaus Meffert
   * @since 3.2
   */
  public static void main(String[] args) {
    try {
      System.out.println("Problem: Find a strategy for playing Tic Tac Toe");
      GPConfiguration config = new GPConfiguration();
      config.setRandomGenerator(new GaussianRandomGenerator());
      config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
      int popSize;
      popSize = 50;
      System.out.println("Using population size of " + popSize);
      // Setup for player 1.
      // -------------------
      config.setMaxInitDepth(6);
      config.setMinInitDepth(2);
      config.setNewChromsPercent(0.1d);
      config.setPopulationSize(popSize);
      config.setStrictProgramCreation(false);
      config.setProgramCreationMaxTries(3);
      config.setMaxCrossoverDepth(10);
      INodeValidator validator = new GameNodeValidator();
      config.setNodeValidator(validator);
      final TicTacToeMain problem = new TicTacToeMain(config);
      config.getEventManager().addEventListener(GeneticEvent.
          GPGENOTYPE_EVOLVED_EVENT, new MyGeneticEventListener());
      // Setup for player 2.
      // -------------------
      GPConfiguration config2 = new GPConfiguration(config.getId() + "_2",
          config.getName() + "_2");
      config2.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
      config2.setMaxInitDepth(6);
      config.setMinInitDepth(2);
      config.setNewChromsPercent(0.1d);
      config2.setPopulationSize(popSize);
      config2.setStrictProgramCreation(false);
      config2.setProgramCreationMaxTries(3);
      config2.setMaxCrossoverDepth(7);
      config2.setNodeValidator(validator);
      final TicTacToeMain problem2 = new TicTacToeMain(config);
      GPGenotype gp2 = problem2.create(config2, 2, null, 1);
      gp2.setVerboseOutput(true);
      config.getEventManager().addEventListener(GeneticEvent.
          GPGENOTYPE_NEW_BEST_SOLUTION, new BestGeneticEventListener(gp2));
//      config2.getEventManager().addEventListener(GeneticEvent.
//          GPGENOTYPE_EVOLVED_EVENT, new MyGeneticEventListener());
      //
      GPGenotype gp1 = problem.create(config, 1, gp2, 2);
      ( (GameFitnessFunction) gp1.getGPConfiguration().getGPFitnessFunction()).
          setPlayer(gp1);
      gp1.setVerboseOutput(true);
      //
      config2.getEventManager().addEventListener(GeneticEvent.
          GPGENOTYPE_NEW_BEST_SOLUTION, new BestGeneticEventListener(gp1));
      //
      ( (GameFitnessFunction) gp2.getGPConfiguration().getGPFitnessFunction()).
          setOpponent(gp1);
      ( (GameFitnessFunction) gp2.getGPConfiguration().getGPFitnessFunction()).
          setPlayer(gp2);
      //
      Coevolution executer = new Coevolution(config, gp1, gp2);
      executer.start();
    } catch (Exception ex) {
      ex.printStackTrace();
      System.exit(1);
    }
  }

  public static class GameFitnessFunction
      extends GPFitnessFunction {
    private Board m_board;

    private int m_color;