src/genetic/ParallelChessGeneticProcess.java

   1 /*
   2  Copyright 2007 Scott Gasch
   3
   4  Licensed under the Apache License, Version 2.0 (the "License"); you
   5  may not use this file except in compliance with the License. You may
   6  obtain a copy of the License at
   7
   8      http://www.apache.org/licenses/LICENSE-2.0
   9
  10  Unless required by applicable law or agreed to in writing, software
  11  distributed under the License is distributed on an "AS IS" BASIS,
  12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
  13  implied. See the License for the specific language governing
  14  permissions and limitations under the License.
  15 */
  16
  17 package org.guru.wannabe.genetic;
  18
  19 import java.io.*;
  20 import java.util.regex.*;
  21
  22 import java.util.Map;
  23 import java.util.TreeMap;
  24 import java.util.List;
  25 import java.util.ArrayList;
  26 import java.util.Arrays;
  27
  28 public class ParallelChessGeneticProcess implements GeneticProcess {
  29     private static final int numProcessors = 4;
  30     private static final String baselineDna = "./baseline.dna";
  31     private static final String baselineLog = "./baseline.log";
  32     private static final String scriptName = "./trial.ep_";
  33
  34     private int numGenerations;
  35     private int numPerGeneration;
  36     private int numSeeds;
  37
  38     // Helper function to emulate system(3).
  39     private static void system(String cmd[]) {
  40         Runtime runtime = Runtime.getRuntime();
  41         try {
  42             Process ps = runtime.exec(cmd);
  43             InputStream stdin = ps.getInputStream();
  44             InputStreamReader isr = new InputStreamReader(stdin);
  45             BufferedReader br = new BufferedReader(isr);
  46             String line = null;
  47             while((line = br.readLine()) != null) ;
  48             ps.waitFor();
  49         } catch(Exception e) {
  50             throw new AssertionError(e);
  51         }
  52     }
  53
  54     // Private helpers to build filenames
  55     private static String seedFilename(int generation, int which) {
  56         return "./gen" + generation + "_seed" + which + ".dna";
  57     }
  58
  59     private static String logFilename(int generation, int which) {
  60         return "./gen" + generation + "_" + which + ".log";
  61     }
  62
  63     private static String dnaFilename(int generation, int which) {
  64         return "./gen" + generation + "_" + which + ".dna";
  65     }
  66
  67     // Uses mutate.pl to cause dna mutations
  68     private static void mutate(String from, String to) {
  69         String cmd[] = new String[] { "./mutate.pl", from, to };
  70         system(cmd);
  71         try {
  72             BufferedWriter out =
  73                 new BufferedWriter(new FileWriter(to, true));
  74             out.write("# mutate " + from + " -> " + to + "\n");
  75             out.close();
  76         } catch(IOException e) {
  77             throw new AssertionError(e);
  78         }
  79     }
  80
  81     // Runs a chess trial event
  82     private static void chessTrial(String dnaFile, String logFile) {
  83         String cmd[] = new String[] { "./typhoon",
  84                              "--cpus", "1",
  85                              "--hash", "128m",
  86                              "--batch",
  87                              "--logfile", logFile,
  88                              "--dnafile", dnaFile,
  89                              "--command", "script ./trial.ep_" };
  90         system(cmd);
  91     }
  92
  93     // The mainInitialize method produces the 0th generation DNA from
  94     // a seed file called "baseline.dna" using a helper script called
  95     // mutate.pl (the generic DNA mutation routine).
  96     public boolean mainInitialize(int numGenerations,
  97                                   int numPerGeneration) {
  98
  99         System.out.println("Performing pre-generation setup tasks.");
 100         this.numGenerations = numGenerations;
 101         this.numPerGeneration = numPerGeneration;
 102         this.numSeeds = numPerGeneration / 5;
 103         if ((numGenerations <= 0) ||
 104             (numPerGeneration <= 0) ||
 105             (numSeeds <= 0)) {
 106             throw new IllegalArgumentException("Bad value");
 107         }
 108
 109         // Create generation zero seeds based on mutations of baseline.dna
 110         for (int x = 0; x < numSeeds; x++) {
 111             String seedFile = seedFilename(0, x);
 112             if (!new File(seedFile).exists()) {
 113                 mutate(baselineDna, seedFile);
 114             } else {
 115                 System.out.println("Using existing " + seedFile);
 116             }
 117         }
 118
 119         // Run baseline.dna trial to get a starting point.
 120         if (!new File(baselineLog).exists()) {
 121             chessTrial(baselineDna, baselineLog);
 122         } else {
 123             System.out.println("Using existing " + baselineLog);
 124         }
 125         return true;
 126     }
 127
 128     public boolean generationInitialize(int generationNumber) {
 129
 130         // Using the seed dna of the previous generation, build the
 131         // genes for the current generation.
 132         System.out.println("Initializing generation " + generationNumber);
 133         for (int x = 0; x < numPerGeneration; x++) {
 134             String dnaFile = dnaFilename(generationNumber, x);
 135             String seedFile = seedFilename(generationNumber, x % numSeeds);
 136             mutate(seedFile, dnaFile);
 137         }
 138         return true;
 139     }
 140
 141     public boolean generationEvaluation(int generationNumber) {
 142         class ChessGame implements Runnable {
 143             public String dnaFile;
 144             public String logFile;
 145             public ChessGame(String dnaFile, String logFile) {
 146                 this.dnaFile = dnaFile; this.logFile = logFile;
 147             }
 148             public void run() {
 149                 if (!new File(logFile).exists()) {
 150                     System.out.println("Creating " + logFile);
 151                     chessTrial(dnaFile, logFile);
 152                 } else {
 153                     System.out.println("Using existing " + logFile);
 154                 }
 155             }
 156         }
 157
 158         // Populate work queue
 159         System.out.println("Evaluating generation " + generationNumber);
 160         List<ChessGame> workQueue = new ArrayList<ChessGame>();
 161         for (int x = 0; x < numPerGeneration; x++) {
 162             String dnaFile = dnaFilename(generationNumber, x);
 163             String logFile = logFilename(generationNumber, x);
 164             workQueue.add(new ChessGame(dnaFile, logFile));
 165         }
 166
 167         // Depopulate the work queue in parallel
 168         Thread threadPool[] = new Thread[numProcessors];
 169         while(!workQueue.isEmpty()) {
 170             ChessGame next = workQueue.remove(0);
 171             int x = 0;
 172             do {
 173                 if ((threadPool[x] == null) ||
 174                     (!threadPool[x].isAlive())) {
 175                     threadPool[x] = new Thread(next);
 176                     threadPool[x].setPriority(Thread.MAX_PRIORITY);
 177                     threadPool[x].start();
 178                     break;
 179                 }
 180                 x++;
 181                 if (x >= numProcessors) {
 182                     x = 0;
 183                     try {
 184                         Thread.sleep(2000);
 185                     } catch(Exception e) {
 186                         ;
 187                     }
 188                 }
 189             }
 190             while(true);
 191         }
 192
 193         // Wait for all threads to become idle again
 194         int x = 0;
 195         do {
 196             if (threadPool[x] != null && threadPool[x].isAlive()) {
 197                 x = 0;
 198             }
 199             x++;
 200             try {
 201                 Thread.sleep(2000);
 202             } catch(Exception e) {
 203                 ;
 204             }
 205         } while(x < numProcessors);
 206         return true;
 207     }
 208
 209     public boolean generationReproduction(int generationNumber) {
 210
 211         // Helper data class
 212         class FileAndScore implements Comparable<FileAndScore> {
 213             public final String file;
 214             public final int score;
 215             public final int number;
 216             public FileAndScore(String file, int score, int number) {
 217                 this.file = file; this.score = score; this.number = number;
 218             }
 219             public int compareTo(FileAndScore other) {
 220                 return other.score - score;
 221             }
 222         }
 223
 224         System.out.println("Seeding subsequent generation.");
 225         List<FileAndScore> scores = new ArrayList<FileAndScore>();
 226         for (int x = 0; x < numPerGeneration; x++) {
 227             String logFile = logFilename(generationNumber, x);
 228             try {
 229                 BufferedReader log = new BufferedReader(
 230                                          new FileReader(logFile));
 231                 String line = null;
 232                 Pattern p =
 233                     Pattern.compile("\\s+correct solutions\\s+:\\s+(\\d+)");
 234                 while ((line = log.readLine()) != null) {
 235                     Matcher m = p.matcher(line);
 236                     if (m.matches()) {
 237                         int score = Integer.parseInt(m.group(1));
 238                         FileAndScore fas =
 239                             new FileAndScore(logFile, score, x);
 240                         scores.add(fas);
 241                         break;
 242                     }
 243                 }
 244                 log.close();
 245             }
 246             catch (Exception e) {
 247                 throw new AssertionError(e);
 248             }
 249         }
 250         java.util.Collections.sort(scores);
 251         for (int x = 0; x < numSeeds; x++) {
 252             FileAndScore breeder = scores.get(0);
 253             scores.remove(0);
 254             String dnaFile = dnaFilename(generationNumber, breeder.number);
 255             String seedFile = seedFilename(generationNumber + 1, x);
 256             if (!new File(seedFile).exists()) {
 257                 System.out.println("Number " + breeder.number + " got score " +
 258                                    breeder.score + " and will propagate.");
 259                 String cmd[] = new String[] { "/bin/cp", "-f", dnaFile, seedFile };
 260                 system(cmd);
 261             } else {
 262                 System.out.println("Using existing " + seedFile);
 263             }
 264         }
 265         return true;
 266     }
 267 }