Changeset 10427

Timestamp:

01/29/14 19:30:53 (11 years ago)

Author:

gkronber

Message:

#2026 integrated max depth into MCTS solver

Location:

branches/HeuristicLab.Problems.GPDL/CodeGenerator

Files:

• MonteCarloTreeSearchCodeGen.cs (modified) (8 diffs)
• ProblemCodeGen.cs (modified) (1 diff)
• RandomSearchCodeGen.cs (modified) (2 diffs)

branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs

@@ -34 +34 @@
     private readonly ?IDENT?Problem problem;
     private readonly Random random;
+    private readonly ?IDENT?RandomSearchSolver randomSearch;
+
     private SearchTreeNode searchTree = new SearchTreeNode();
    
@@ -44 +46 @@
     }
 
+    private  const int RANDOM_TRIES = 1;
+
     private void SampleTree(SearchTreeNode searchTree, Stack<Tuple<Tree, int, int, int>> extensionPoints) {
-      const int RANDOM_TRIES = 1000;
-      if(extensionPoints.Count == 0) {
-        searchTree.done = true;
-        return; // nothing to do
-      }
       var extensionPoint = extensionPoints.Pop();
       Tree parent = extensionPoint.Item1;
@@ -56 +55 @@
       int maxDepth = extensionPoint.Item4;
       Debug.Assert(maxDepth >= 1);
+      Debug.Assert(Grammar.minDepth[state] <= maxDepth);
       Tree t = null;
       if(searchTree.tries < RANDOM_TRIES || Grammar.subtreeCount[state] == 0) {
-        t = SampleTreeRandom(state);
+        int steps = 0; int curDepth = this.maxDepth - maxDepth; int depth = this.maxDepth - maxDepth;
+        t = randomSearch.SampleTree(state, maxDepth, ref steps, ref curDepth, ref depth);
         if(Grammar.subtreeCount[state] == 0) {
           // when we produced a terminal continue filling up all other empty points
           Debug.Assert(searchTree.children == null || searchTree.children.Length == 1);
-          if(searchTree.children == null)
-            searchTree.children = new SearchTreeNode[] { new SearchTreeNode() } ;
-          SampleTree(searchTree.children[0], extensionPoints);
-          if(searchTree.children[0].done) searchTree.done = true;
+          if(extensionPoints.Count == 0) {
+            searchTree.done = true;
+          } else {
+            if(searchTree.children == null)
+              searchTree.children = new SearchTreeNode[] { new SearchTreeNode() } ;
+            SampleTree(searchTree.children[0], extensionPoints);
+            if(searchTree.children[0].done) searchTree.done = true;
+          }
         } else {
           // fill up all remaining slots randomly
@@ -72 +77 @@
             var pState = p.Item2;
             var pIdx = p.Item3;
-            pParent.subtrees[pIdx] = SampleTreeRandom(pState);
-          }
-        }
-      } else {
-        if(Grammar.subtreeCount[state] == 1) {
-          if(searchTree.children == null) {
-            int nChildren = Grammar.transition[state].Length;
-            searchTree.children = new SearchTreeNode[nChildren];
-          }
-          Debug.Assert(searchTree.children.Length == Grammar.transition[state].Length);
-          Debug.Assert(searchTree.tries - RANDOM_TRIES == searchTree.children.Where(c=>c!=null).Sum(c=>c.tries));
-          var altIdx = SelectAlternative(searchTree);
-          t = new Tree(altIdx, new Tree[1]);
-          extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0, maxDepth - 1));
-          SampleTree(searchTree.children[altIdx], extensionPoints);
-        } else {
-          // multiple subtrees
-          var subtrees = new Tree[Grammar.subtreeCount[state]];
-          t = new Tree(-1, subtrees);
-          for(int i = subtrees.Length - 1; i >= 0; i--) {
-            extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][i], i, maxDepth - 1));
-          }
-          SampleTree(searchTree, extensionPoints);          
-        }
+            var pMaxDepth = p.Item4;
+            curDepth = this.maxDepth - pMaxDepth;
+            depth = curDepth;
+            pParent.subtrees[pIdx] = randomSearch.SampleTree(pState, pMaxDepth, ref steps, ref curDepth, ref depth);
+          }
+        }
+      } else if(Grammar.subtreeCount[state] == 1) {
+         if(searchTree.children == null) {
+           int nChildren = Grammar.transition[state].Length;
+           searchTree.children = new SearchTreeNode[nChildren];
+         }
+         Debug.Assert(searchTree.children.Length == Grammar.transition[state].Length);
+         Debug.Assert(searchTree.tries - RANDOM_TRIES == searchTree.children.Where(c=>c!=null).Sum(c=>c.tries));
+         var altIdx = SelectAlternative(searchTree, state, maxDepth);
+         t = new Tree(altIdx, new Tree[1]);
+         extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0, maxDepth - 1));
+         SampleTree(searchTree.children[altIdx], extensionPoints);
+         searchTree.done = (from idx in Enumerable.Range(0, searchTree.children.Length)
+                            where Grammar.minDepth[Grammar.transition[state][idx]] <= maxDepth - 1
+                            select searchTree.children[idx]).All(c=>c != null && c.done);
+      } else {
+        // multiple subtrees
+        var subtrees = new Tree[Grammar.subtreeCount[state]];
+        t = new Tree(-1, subtrees);
+        for(int i = subtrees.Length - 1; i >= 0; i--) {
+          extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][i], i, maxDepth - 1));
+        }
+        SampleTree(searchTree, extensionPoints);   
       }      
       Debug.Assert(parent.subtrees[subtreeIdx] == null);
@@ -101 +110 @@
     }
 
-    private int SelectAlternative(SearchTreeNode searchTree) {
+    private int SelectAlternative(SearchTreeNode searchTree, int state, int maxDepth) {
       // any alternative not yet explored?
-      var altIdx = Array.FindIndex(searchTree.children, (e) => e == null);
+      var altIndexes = searchTree.children
+                     .Select((e,i) => new {Elem = e, Idx = i})
+                     .Where(p => p.Elem == null && Grammar.minDepth[Grammar.transition[state][p.Idx]] <= maxDepth)
+                     .Select(p => p.Idx);
+      int altIdx = altIndexes.Any()?altIndexes.First() : -1;
       if(altIdx >= 0) {
         searchTree.children[altIdx] = new SearchTreeNode();
         return altIdx;
       } else {
-        altIdx = Array.FindIndex(searchTree.children, (e) => !e.done && e.tries < 1000);
+        altIndexes = searchTree.children
+                       .Select((e,i) => new {Elem = e, Idx = i})
+                       .Where(p => p.Elem != null && !p.Elem.done && p.Elem.tries < RANDOM_TRIES && Grammar.minDepth[Grammar.transition[state][p.Idx]] <= maxDepth)
+                       .Select(p => p.Idx);
+        altIdx = altIndexes.Any()?altIndexes.First() : -1;
         if(altIdx >= 0) return altIdx;
         // select the least sampled alternative
-        //altIdx = 0;
-        //int minSamples = searchTree.children[altIdx].tries;
-        //for(int idx = 1; idx < searchTree.children.Length; idx++) {
-        //  if(!searchTree.children[idx].done && searchTree.children[idx].tries < minSamples) {
+        //altIdx = -1;
+        //int minSamples = int.MaxValue;
+        //for(int idx = 0; idx < searchTree.children.Length; idx++) {
+        //  if(searchTree.children[idx] == null) continue;
+        //  if(!searchTree.children[idx].done && Grammar.minDepth[Grammar.transition[state][idx]] <= maxDepth && searchTree.children[idx].tries < minSamples) {
         //    minSamples = searchTree.children[idx].tries;
         //    altIdx = idx;
@@ -120 +138 @@
         //}
         // select the alternative with the largest average
-        altIdx = 0;
-        double bestAverage = UCB(searchTree, searchTree.children[altIdx]);
-        for(int idx = 1; idx < searchTree.children.Length; idx++) {
-          if (!searchTree.children[idx].done && UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
+        altIdx = -1;
+        double best = double.NegativeInfinity;
+        for(int idx = 0; idx < searchTree.children.Length; idx++) {
+          if(searchTree.children[idx] == null) continue;
+          if (!searchTree.children[idx].done && Grammar.minDepth[Grammar.transition[state][idx]] <= maxDepth  && UCB(searchTree, searchTree.children[idx]) > best) {
             altIdx = idx;
-          }
-        }
-
-        searchTree.done = searchTree.children.All(c=>c.done);
+            best = UCB(searchTree, searchTree.children[idx]);
+          }
+        }
+        Debug.Assert(altIdx > -1);
         return altIdx;
       }
@@ -136 +155 @@
       Debug.Assert(parent.tries >= n.tries);
       Debug.Assert(n.tries > 0);
-      return n.sumQuality / n.tries + Math.Sqrt((10 * Math.Log(parent.tries)) / n.tries ); // constant is dependent fitness function values
+      return n.sumQuality / n.tries + Math.Sqrt((40 * Math.Log(parent.tries)) / n.tries ); // constant is dependent fitness function values
     }
 
@@ -174 +193 @@
     }
 
-    // same as in random search solver (could reuse random search)
-    private Tree SampleTreeRandom(int state) {
-      return SampleTreeRandom(state, 5);
-    }
-    private Tree SampleTreeRandom(int state, int maxDepth) {
-      Tree t = null;
-
-      // terminals
-      if(Grammar.subtreeCount[state] == 0) {
-        t = CreateTerminalNode(state, random, problem);
-      } else {
-        // if the symbol has alternatives then we must choose one randomly (only one sub-tree in this case)
-        if(Grammar.subtreeCount[state] == 1) {
-          var targetStates = Grammar.transition[state];
-          var altIdx = SampleAlternative(random, state, maxDepth);
-          var alternative = SampleTreeRandom(targetStates[altIdx], maxDepth - 1);
-          t = new Tree(altIdx, new Tree[] { alternative });
-        } else {
-          // if the symbol contains only one sequence we must use create sub-trees for each symbol in the sequence
-          Tree[] subtrees = new Tree[Grammar.subtreeCount[state]];
-          for(int i = 0; i < Grammar.subtreeCount[state]; i++) {
-            subtrees[i] = SampleTreeRandom(Grammar.transition[state][i], maxDepth - 1);
-          }
-          t = new Tree(-1, subtrees); // alternative index is ignored
-        }
-      }
-      return t;
-    }
-
-    private static Tree CreateTerminalNode(int state, Random random, ?IDENT?Problem problem) {
-      switch(state) {
-        ?CREATETERMINALNODECODE?
-        default: { throw new ArgumentException(""Unknown state index"" + state); }
-      }
-    }
-
-    private int SampleAlternative(Random random, int state, int maxDepth) {
-      switch(state) {
-
-?SAMPLEALTERNATIVECODE?
-
-        default: throw new InvalidOperationException();
-      }
-    }
-
     public ?IDENT?MonteCarloTreeSearchSolver(?IDENT?Problem problem, string[] args) {
-      if(args.Length > 0 ) throw new ArgumentException(""Arguments ""+args.Aggregate("""", (str, s) => str+ "" "" + s)+"" are not supported "");
+      this.randomSearch = new ?IDENT?RandomSearchSolver(problem, args);
+      if(args.Length > 0 ) ParseArguments(args);
       this.problem = problem;
       this.random = new Random();
     }
+    private void ParseArguments(string[] args) {
+      var maxDepthRegex = new Regex(@""--maxDepth=(?<d>.+)"");
+
+      var helpRegex = new Regex(@""--help|/\?"");
+      
+      foreach(var arg in args) {
+        var maxDepthMatch = maxDepthRegex.Match(arg);
+        var helpMatch = helpRegex.Match(arg);
+        if(helpMatch.Success) { 
+          PrintUsage(); Environment.Exit(0); 
+        } else if(maxDepthMatch.Success) {
+           maxDepth = int.Parse(maxDepthMatch.Groups[""d""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
+           if(maxDepth < 1 || maxDepth > 100) throw new ArgumentException(""max depth must lie in range [1 ... 100]"");
+        } else {
+           Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0); 
+        }
+      }
+    }
+    private void PrintUsage() {
+      Console.WriteLine(""Find a solution using Monte-Carlo tree search."");
+      Console.WriteLine();
+      Console.WriteLine(""Parameters:"");
+      Console.WriteLine(""\t--maxDepth=<depth>\tSets the maximal depth of sampled trees [Default: 20]"");
+    }
+
+
 
     public void Start() {

branches/HeuristicLab.Problems.GPDL/CodeGenerator/ProblemCodeGen.cs

@@ -27 +27 @@
     public static void Main(string[] args) {
       var problem = new ?IDENT?Problem();
-      var solver = new ?IDENT?RandomSearchSolver(problem, args);
+      var solver = new ?IDENT?MonteCarloTreeSearchSolver(problem, args);
       solver.Start();
     }

branches/HeuristicLab.Problems.GPDL/CodeGenerator/RandomSearchCodeGen.cs

@@ -19 +19 @@
     private readonly Random random;
 
-    private Tree SampleTree(int maxDepth, out int steps, out int depth) {
+    public Tree SampleTree(int maxDepth, out int steps, out int depth) {
       steps = 0;
       depth = 0;
@@ -26 +26 @@
     }
 
-    private Tree SampleTree(int state, int maxDepth, ref int steps, ref int curDepth, ref int depth) {
+    public Tree SampleTree(int state, int maxDepth, ref int steps, ref int curDepth, ref int depth) {
       curDepth += 1;
       Debug.Assert(maxDepth > 0);