001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licensing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package examples.gp.tictactoe;
011:
012: import org.jgap.*;
013: import org.jgap.event.*;
014: import org.jgap.gp.*;
015: import org.jgap.gp.impl.*;
016: import org.jgap.gp.function.*;
017: import org.jgap.gp.terminal.*;
018: import org.jgap.util.*;
019: import org.jgap.impl.*;
020:
021: /**
022: * Example demonstrating Genetic Programming (GP) capabilities of JGAP.<p>
023: * Here, a strategy for playing Tic Tac Toe is evolved.<p>
024: * THIS PROGRAM IS STILL UNDER DEVELOPMENT AND IS NOT FINISHED YET! ANY COMMENTS
025: * AND EXTENSIONS ARE VERY WELCOME!
026: *
027: * @author Klaus Meffert
028: * @since 3.2
029: */
030: public class TicTacToeMain extends GPProblem {
031: /** String containing the CVS revision. Read out via reflection!*/
032: private final static String CVS_REVISION = "$Revision: 1.4 $";
033:
034: private static Variable vb;
035:
036: private Board m_board;
037:
038: public TicTacToeMain(GPConfiguration a_conf)
039: throws InvalidConfigurationException {
040: super (a_conf);
041: m_board = new Board();
042: }
043:
044: public Board getBoard() {
045: return m_board;
046: }
047:
048: /**
049: * Sets up the functions to use and other parameters. Then creates the
050: * initial genotype.
051: *
052: * @param a_color the color to create a program for
053: * @return the genotype created
054: * @throws InvalidConfigurationException
055: *
056: * @author Klaus Meffert
057: * @since 3.2
058: */
059: public GPGenotype create(GPConfiguration conf, int a_color,
060: GPGenotype a_other, int a_otherColor)
061: throws InvalidConfigurationException {
062: Class[] types = { CommandGene.VoidClass, CommandGene.VoidClass,
063: CommandGene.VoidClass, CommandGene.VoidClass };
064: Class[][] argTypes = { {}, {}, {}, {} };
065: int[] minDepths = new int[] { 0, 2, 2, 1 };
066: int[] maxDepths = new int[] { 0, 2, 6, 2 };
067: // GPConfiguration conf = getGPConfiguration();
068: int color = a_color;
069: ForLoop forLoop1 = new ForLoop(conf, SubProgram.VoidClass, 1,
070: Board.WIDTH, 1, "x", 0, 0);
071: ForLoop forLoop2 = new ForLoop(conf, SubProgram.VoidClass, 1,
072: Board.HEIGHT, 1, "y", 0, 0);
073: Variable vx = new Variable(conf, "move",
074: CommandGene.IntegerClass);
075: Variable vb = new Variable(conf, "firstmove",
076: CommandGene.BooleanClass);
077: CommandGene[][] nodeSets = {
078: {
079: // Transfer board to evolution memory.
080: // -----------------------------------
081: new TransferBoardToMemory(conf, m_board, 0, 0), },
082: {
083: // Create strategy data.
084: // ---------------------
085: new Loop(conf, CommandGene.IntegerClass,
086: Board.WIDTH * Board.HEIGHT),
087: new EvaluateBoard(conf, m_board,
088: CommandGene.IntegerClass),
089: new IncrementMemory(conf,
090: CommandGene.IntegerClass, "counter", 10), },
091: {
092: // Evaluate.
093: // ---------
094: vx,
095: vb,
096: new SubProgram(conf, new Class[] {
097: CommandGene.VoidClass,
098: CommandGene.VoidClass }),
099: new SubProgram(conf, new Class[] {
100: CommandGene.VoidClass,
101: CommandGene.VoidClass,
102: CommandGene.VoidClass }),
103: new SubProgram(conf, new Class[] {
104: TransferBoardToMemory.VoidClass,
105: CommandGene.VoidClass }),
106: new SubProgram(conf, new Class[] {
107: CommandGene.VoidClass,
108: CommandGene.VoidClass,
109: CommandGene.VoidClass,
110: CommandGene.VoidClass }),
111: // forLoop1,
112: // forLoop2,
113: new ReadTerminalIndexed(conf,
114: CommandGene.IntegerClass, 0),
115: new ReadTerminalIndexed(conf,
116: CommandGene.IntegerClass, 1),
117: new ReadTerminalIndexed(conf,
118: CommandGene.IntegerClass, 2),
119: new ReadTerminalIndexed(conf,
120: CommandGene.IntegerClass, 3),
121: new ReadTerminalIndexed(conf,
122: CommandGene.IntegerClass, 10, 22),
123: new ReadTerminalIndexed(conf,
124: CommandGene.IntegerClass, 11, 22),
125: new ReadTerminalIndexed(conf,
126: CommandGene.IntegerClass, 12, 22),
127: new ReadTerminalIndexed(conf,
128: CommandGene.IntegerClass, 13, 22),
129: new ReadTerminalIndexed(conf,
130: CommandGene.IntegerClass, 14, 23),
131: new EvaluateBoard(conf, m_board, 14),
132: new Loop(conf, SubProgram.class, Board.WIDTH),
133: new Loop(conf, SubProgram.class, Board.HEIGHT),
134: new Loop(conf, SubProgram.class, Board.WIDTH
135: * Board.HEIGHT),
136: new Constant(conf, CommandGene.IntegerClass,
137: new Integer(0)),
138: new Constant(conf, CommandGene.IntegerClass,
139: new Integer(1)),
140: new Constant(conf, CommandGene.IntegerClass,
141: new Integer(2)),
142: new Constant(conf, CommandGene.IntegerClass,
143: new Integer(3)),
144: new Terminal(conf, CommandGene.IntegerClass,
145: 1.0d, Board.WIDTH, true, 4),
146: new Terminal(conf, CommandGene.IntegerClass,
147: 1.0d, Board.HEIGHT, true, 4),
148: new Equals(conf, CommandGene.IntegerClass, 0,
149: new int[] { 22, 23 }),
150: new Equals(conf, CommandGene.IntegerClass, 0,
151: new int[] { 0, 8 }),
152: new IfElse(conf, CommandGene.BooleanClass),
153: new ReadBoard(conf, m_board, 0, new int[] { 4,
154: 4 }),
155: new ReadBoard(conf, m_board),
156: new Not(conf),
157: new Push(conf, CommandGene.IntegerClass),
158: new Pop(conf, CommandGene.IntegerClass),
159: new IfIsOccupied(conf, m_board,
160: CommandGene.IntegerClass, 0, new int[] {
161: 4, 4, 0 }),
162: new IfIsFree(conf, m_board,
163: CommandGene.IntegerClass, 0, new int[] {
164: 4, 4, 0 }),
165: // new CountStones(conf, m_board, color, "count", 2),
166: new IfColor(conf, CommandGene.IntegerClass,
167: color),
168: new IsOwnColor(conf, color),
169: new Increment(conf, CommandGene.IntegerClass, 1),
170: new Increment(conf, CommandGene.IntegerClass,
171: -1),
172: new StoreTerminalIndexed(conf, 15,
173: CommandGene.IntegerClass),
174: new StoreTerminal(conf, "mem0",
175: CommandGene.IntegerClass),
176: // new StoreTerminal(conf, "mem1", CommandGene.IntegerClass),
177: new AddAndStoreTerminal(conf, "memA",
178: CommandGene.IntegerClass),
179: // new AddAndStoreTerminal(conf, "memB", CommandGene.IntegerClass),
180: new ReadTerminal(conf,
181: CommandGene.IntegerClass, "mem0"),
182: // new ReadTerminal(conf, CommandGene.IntegerClass, "mem1"),
183: new ReadTerminal(conf,
184: CommandGene.IntegerClass, "memA"),
185: // new ReadTerminal(conf, CommandGene.IntegerClass, "memB"),
186: // new ReadTerminal(conf, CommandGene.IntegerClass, "countr0", 1),
187: // new ReadTerminal(conf, CommandGene.IntegerClass, "countr1", 1),
188: // new ReadTerminal(conf, CommandGene.IntegerClass, "countc0", 8),
189: // new ReadTerminal(conf, CommandGene.IntegerClass, "countc1", 8),
190: // new ReadTerminal(conf, CommandGene.IntegerClass, "countd0"),
191: // new ReadTerminal(conf, CommandGene.IntegerClass, "countd1"),
192: // new ReadTerminal(conf, CommandGene.IntegerClass,
193: // forLoop1.getCounterMemoryName(), 5),
194: // new ReadTerminal(conf, CommandGene.IntegerClass,
195: // forLoop2.getCounterMemoryName(), 6),
196: },
197: {
198: // Make a move.
199: // ------------
200: vb,
201: // vx,
202: new Constant(conf, CommandGene.IntegerClass,
203: new Integer(1)),
204: new Constant(conf, CommandGene.IntegerClass,
205: new Integer(2)),
206: new Equals(conf, CommandGene.IntegerClass),
207: new PutStone(conf, m_board, color),
208: new PutStone1(conf, m_board, color, 0, 33),
209: new IfIsFree(conf, m_board,
210: CommandGene.IntegerClass),
211: new IfElse(conf, CommandGene.BooleanClass),
212: new Increment(conf, CommandGene.IntegerClass, 1),
213: new Increment(conf, CommandGene.IntegerClass,
214: -1),
215: new ReadTerminalIndexed(conf,
216: CommandGene.IntegerClass, 15, 33),
217: new ReadTerminal(conf,
218: CommandGene.IntegerClass, "mem0"),
219: new ReadTerminal(conf,
220: CommandGene.IntegerClass, "mem1"),
221: new ReadTerminal(conf,
222: CommandGene.IntegerClass, "memA"),
223: // new SubProgram(conf, new Class[] {CommandGene.VoidClass,
224: // CommandGene.VoidClass}),
225:
226: // new Terminal(conf, CommandGene.IntegerClass, 1.0d, Board.WIDTH, true),
227: // new Terminal(conf, CommandGene.IntegerClass, 1.0d, Board.HEIGHT, true),
228: // new IfIsOccupied(conf, m_board, CommandGene.IntegerClass),
229: } };
230: conf.setFitnessFunction(new TicTacToeMain.GameFitnessFunction(
231: getBoard(), a_color, a_other, a_otherColor));
232: // }
233: // Create genotype with initial population.
234: // ----------------------------------------
235: GPGenotype result = GPGenotype.randomInitialGenotype(conf,
236: types, argTypes, nodeSets, minDepths, maxDepths, 600,
237: new boolean[] { !true, !true, !true, !true }, true);
238: // Register variables to later have access to them.
239: // ------------------------------------------------
240: result.putVariable(vb);
241: result.putVariable(vx);
242: return result;
243: }
244:
245: public GPGenotype create() throws InvalidConfigurationException {
246: throw new InvalidConfigurationException(
247: "Please use create(Board a_board, int a_color)");
248: }
249:
250: /**
251: * Starts the example.
252: *
253: * @param args ignored
254: * @throws Exception
255: *
256: * @author Klaus Meffert
257: * @since 3.2
258: */
259: public static void main(String[] args) {
260: try {
261: System.out
262: .println("Problem: Find a strategy for playing Tic Tac Toe");
263: GPConfiguration config = new GPConfiguration();
264: config.setRandomGenerator(new GaussianRandomGenerator());
265: config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
266: int popSize;
267: popSize = 50;
268: System.out.println("Using population size of " + popSize);
269: // Setup for player 1.
270: // -------------------
271: config.setMaxInitDepth(6);
272: config.setMinInitDepth(2);
273: config.setNewChromsPercent(0.1d);
274: config.setPopulationSize(popSize);
275: config.setStrictProgramCreation(false);
276: config.setProgramCreationMaxTries(3);
277: config.setMaxCrossoverDepth(10);
278: INodeValidator validator = new GameNodeValidator();
279: config.setNodeValidator(validator);
280: final TicTacToeMain problem = new TicTacToeMain(config);
281: config.getEventManager().addEventListener(
282: GeneticEvent.GPGENOTYPE_EVOLVED_EVENT,
283: new MyGeneticEventListener());
284: // Setup for player 2.
285: // -------------------
286: GPConfiguration config2 = new GPConfiguration(config
287: .getId()
288: + "_2", config.getName() + "_2");
289: config2
290: .setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
291: config2.setMaxInitDepth(6);
292: config.setMinInitDepth(2);
293: config.setNewChromsPercent(0.1d);
294: config2.setPopulationSize(popSize);
295: config2.setStrictProgramCreation(false);
296: config2.setProgramCreationMaxTries(3);
297: config2.setMaxCrossoverDepth(7);
298: config2.setNodeValidator(validator);
299: final TicTacToeMain problem2 = new TicTacToeMain(config);
300: GPGenotype gp2 = problem2.create(config2, 2, null, 1);
301: gp2.setVerboseOutput(true);
302: config.getEventManager().addEventListener(
303: GeneticEvent.GPGENOTYPE_NEW_BEST_SOLUTION,
304: new BestGeneticEventListener(gp2));
305: // config2.getEventManager().addEventListener(GeneticEvent.
306: // GPGENOTYPE_EVOLVED_EVENT, new MyGeneticEventListener());
307: //
308: GPGenotype gp1 = problem.create(config, 1, gp2, 2);
309: ((GameFitnessFunction) gp1.getGPConfiguration()
310: .getGPFitnessFunction()).setPlayer(gp1);
311: gp1.setVerboseOutput(true);
312: //
313: config2.getEventManager().addEventListener(
314: GeneticEvent.GPGENOTYPE_NEW_BEST_SOLUTION,
315: new BestGeneticEventListener(gp1));
316: //
317: ((GameFitnessFunction) gp2.getGPConfiguration()
318: .getGPFitnessFunction()).setOpponent(gp1);
319: ((GameFitnessFunction) gp2.getGPConfiguration()
320: .getGPFitnessFunction()).setPlayer(gp2);
321: //
322: Coevolution executer = new Coevolution(config, gp1, gp2);
323: executer.start();
324: } catch (Exception ex) {
325: ex.printStackTrace();
326: System.exit(1);
327: }
328: }
329:
330: public static class GameFitnessFunction extends GPFitnessFunction {
331: private Board m_board;
332:
333: private int m_color;
334:
335: private GPGenotype m_other;
336:
337: private boolean firstTime;
338:
339: private static int maxMoves;
340:
341: private static int maxreads;
342:
343: private GPGenotype m_player;
344:
345: private int nullfound;
346:
347: static final double GAME_LOST = 5000;
348:
349: static final double MY_WORST_FITNESS_VALUE = 9999999;
350:
351: static final double READ_VALUE = 10000;
352:
353: static final double UNKNOWN_BUT_SOMETHING = MY_WORST_FITNESS_VALUE - 5000;
354:
355: static final double ONE_MOVE = MY_WORST_FITNESS_VALUE
356: / (Board.HEIGHT * Board.WIDTH);
357:
358: static final double ONE_MOVE2 = ONE_MOVE * 0.9;
359:
360: public GameFitnessFunction(Board a_board, int a_color,
361: GPGenotype a_other, int a_otherColor) {
362: m_board = a_board;
363: m_color = a_color;
364: m_other = a_other;
365: firstTime = true;
366: }
367:
368: public void setPlayer(GPGenotype a_player) {
369: m_player = a_player;
370: }
371:
372: public void setOpponent(GPGenotype a_other) {
373: m_other = a_other;
374: }
375:
376: protected double evaluate(final IGPProgram a_subject) {
377: return computeRawFitness(a_subject);
378: }
379:
380: public double computeRawFitness(final IGPProgram a_program) {
381: double error = MY_WORST_FITNESS_VALUE;
382: double errorOpponent = MY_WORST_FITNESS_VALUE;
383: Object[] noargs = new Object[0];
384: // Determine opponent's program.
385: // -----------------------------
386: IGPProgram opponent;
387: if (firstTime) {
388: // First call.
389: // -----------
390: firstTime = false;
391: opponent = m_other.getGPPopulation().getGPProgram(0);
392: if (opponent == null) {
393: System.err.println("First time: opponent is null!");
394: }
395: } else {
396: opponent = m_other.getFittestProgramComputed();
397: if (opponent == null) {
398: nullfound++;
399: if (nullfound == 100) {
400: System.err
401: .println("---------- Consecutive calls: opponent is null!");
402: }
403: opponent = m_other.getGPPopulation()
404: .getGPProgram(0);
405: }
406: }
407: // Compute fitness for each program.
408: // ---------------------------------
409: int moves = 0;
410: // Set opponent's fitness value to a value to have it set at least here.
411: // ---------------------------------------------------------------------
412: opponent.setFitnessValue(UNKNOWN_BUT_SOMETHING);
413: try {
414: while (moves < Board.WIDTH * Board.HEIGHT) {
415: m_board.startNewRound();
416: Boolean var;
417: if (moves == 0) {
418: var = new Boolean(true);
419: } else {
420: var = new Boolean(false);
421: }
422: Integer var2 = new Integer(moves);
423: Variable vb1 = m_player.getVariable("firstmove");
424: vb1.set(var);
425: Variable vb2 = m_other.getVariable("firstmove");
426: vb2.set(var);
427: Variable vx1 = m_player.getVariable("move");
428: vx1.set(var2);
429: Variable vx2 = m_other.getVariable("move");
430: vx2.set(var2);
431: // Initialize local stores.
432: // ------------------------
433: a_program.getGPConfiguration().clearStack();
434: a_program.getGPConfiguration().clearMemory();
435: try {
436: // First player.
437: // -------------
438: m_board.beginTurn();
439: for (int j = 0; j < a_program.size(); j++) {
440: if (j == a_program.size() - 1) {
441: a_program.execute_void(j, noargs);
442: } else {
443: a_program.execute_void(j, noargs);
444: }
445: }
446: // Value the number of distinct read outs of the board by the
447: // player.
448: // -----------------------------------------------------------
449: int readCount = m_board.getReadPositionCount();
450: if (readCount > maxreads) {
451: maxreads = readCount;
452: if (maxreads > 1) {
453: System.out
454: .println("**** Number of board reads reached: "
455: + maxreads);
456: }
457: }
458: error -= readCount * READ_VALUE;
459: m_board.endTurn();
460: moves++;
461: error -= ONE_MOVE2;
462: // Initialize local stores.
463: // ------------------------
464: a_program.getGPConfiguration().clearStack();
465: a_program.getGPConfiguration().clearMemory();
466: // Second player.
467: // --------------
468: m_board.beginTurn();
469: for (int j = 0; j < opponent.size(); j++) {
470: if (j == opponent.size() - 1) {
471: opponent.execute_void(j, noargs);
472: } else {
473: opponent.execute_void(j, noargs);
474: }
475: }
476: // Value the number of distincts read outs of the board by the
477: // player.
478: // -----------------------------------------------------------
479: readCount = m_board.getReadPositionCount();
480: if (readCount > maxreads) {
481: maxreads = readCount;
482: if (maxreads > 1) {
483: System.out
484: .println("**** Number of board reads reached: "
485: + maxreads);
486: }
487: }
488: errorOpponent -= readCount * READ_VALUE;
489: m_board.endTurn();
490: moves++;
491: errorOpponent -= ONE_MOVE2;
492: } catch (GameWonException gex) {
493: if (gex.getColor() == m_color) {
494: // Best case.
495: // ----------
496: error -= 0;
497: errorOpponent = GAME_LOST;
498: break;
499: } else {
500: // Worse case: Player lost, but finished game correctly!
501: // -----------------------------------------------------
502: error -= GAME_LOST;
503: errorOpponent = 0.0d;
504: break;
505: }
506: }
507: m_board.endRound();
508: }
509: System.out
510: .println("******************* SUPERB: WE MADE IT");
511: } catch (IllegalArgumentException iax) {
512: // Already cared about by not reducing error rate.
513: // -----------------------------------------------
514: ;
515: } catch (IllegalStateException iex) {
516: // Already cared about by not reducing error rate.
517: // -----------------------------------------------
518: }
519: if (maxMoves < moves) {
520: maxMoves = moves;
521: System.out
522: .println("**** Number of valid moves reached: "
523: + maxMoves);
524: }
525: if (error < 0.000001) {
526: error = 0.0d;
527: } else if (error < MY_WORST_FITNESS_VALUE * 0.8d) {
528: /**@todo add penalty for longer solutions*/
529: }
530: if (errorOpponent < 0.000001) {
531: errorOpponent = 0.0d;
532: } else if (errorOpponent < MY_WORST_FITNESS_VALUE * 0.8d) {
533: /**@todo add penalty for longer solutions*/
534:
535: }
536: opponent.setFitnessValue(errorOpponent);
537: return error;
538: }
539: }
540: }
541:
542: class BestGeneticEventListener implements GeneticEventListener {
543: private GPGenotype m_other;
544:
545: public BestGeneticEventListener(GPGenotype a_other) {
546: m_other = a_other;
547: }
548:
549: /**
550: * New best solution found.
551: *
552: * @param a_firedEvent GeneticEvent
553: */
554: public void geneticEventFired(GeneticEvent a_firedEvent) {
555: GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
556: int evno = genotype.getGPConfiguration().getGenerationNr();
557: String indexString = "" + evno;
558: while (indexString.length() < 5) {
559: indexString = "0" + indexString;
560: }
561: IGPProgram best = genotype.getAllTimeBest();
562: IGPProgram fittest = genotype.getFittestProgram();
563: if (fittest != null) {
564: // Inject fittest program into opponent's population.
565: // --------------------------------------------------
566: m_other.addFittestProgram(fittest);
567: double bestFitness = fittest.getFitnessValue();
568: if (bestFitness < 0.5) {
569: genotype.outputSolution(best);
570: System.exit(0);
571: }
572: }
573: }
574: };
575:
576: class MyGeneticEventListener implements GeneticEventListener {
577: public MyGeneticEventListener() {
578: }
579:
580: public void geneticEventFired(GeneticEvent a_firedEvent) {
581: GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
582: int evno = genotype.getGPConfiguration().getGenerationNr();
583: double freeMem = SystemKit.getFreeMemoryMB();
584: if (evno % 100 == 0) {
585: IGPProgram best = genotype.getAllTimeBest();
586: double allBestFitness = FitnessFunction.NO_FITNESS_VALUE;
587: if (best != null) {
588: allBestFitness = best.getFitnessValue();
589: }
590: System.out.println("Evolving generation " + evno
591: + ", all-time-best fitness: " + allBestFitness
592: + ", memory free: " + freeMem + " MB");
593: IGPProgram best1 = genotype.getFittestProgram();
594: System.out.println(" Best in current generation: "
595: + best1.getFitnessValue());
596: System.out.println(" " + best1.toStringNorm(0));
597: }
598: if (evno > 30000) {
599: System.exit(0);
600: } else {
601: // Collect garbage if memory low.
602: // ------------------------------
603: if (freeMem < 50) {
604: System.gc();
605: }
606: }
607: }
608: }
609:
610: class Coevolution {
611: private GPConfiguration m_conf;
612:
613: private GPGenotype m_gp1;
614:
615: private GPGenotype m_gp2;
616:
617: public Coevolution(GPConfiguration a_conf, GPGenotype a_gp1,
618: GPGenotype a_gp2) {
619: m_conf = a_conf;
620: m_gp1 = a_gp1;
621: m_gp2 = a_gp2;
622: }
623:
624: public void start() {
625: try {
626: do {
627: m_gp1.evolve();
628: Thread.currentThread().sleep(5);
629: m_gp2.evolve();
630: Thread.currentThread().sleep(5);
631: m_gp1.calcFitness();
632: Thread.currentThread().sleep(5);
633: m_gp2.calcFitness();
634: Thread.currentThread().sleep(20);
635: } while (true);
636: } catch (InterruptedException iex) {
637: ; //this is OK and means: end of evolution
638: iex.printStackTrace();
639: }
640: }
641: }
|