TicTacToeMain


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