Index: /branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs	(revision 10408)
+++ /branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs	(revision 10408)
@@ -0,0 +1,383 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Grammars;
+
+namespace CodeGenerator {
+  public class MonteCarloTreeSearchCodeGen {
+
+    private string solverTemplate = @"
+namespace ?PROBLEMNAME? {
+  public class SearchTreeNode {
+    public int tries;
+    public double sumQuality = 0.0;
+    public double bestQuality = double.NegativeInfinity;
+    public bool ready;
+    public SearchTreeNode[] children;
+
+    public SearchTreeNode() {
+    }
+  }
+
+  public sealed class ?IDENT?Solver {
+    // private static double baseTerminalProbability = 0.05; // 5% of all samples are only a terminal node
+    // private static double terminalProbabilityInc = 0.05; // for each level the probability to sample a terminal grows by 5%
+
+    private readonly ?IDENT?Problem problem;
+    private readonly Random random;
+    private SearchTreeNode searchTree = new SearchTreeNode();
+   
+    private Tree SampleTree() {
+      var extensionsStack = new Stack<Tuple<Tree, int, int>>(); // the unfinished tree, the state, and the index of the extension point
+      var t = new Tree(-1, new Tree[1]);
+      extensionsStack.Push(Tuple.Create(t, 0, 0));
+      SampleTree(searchTree, extensionsStack);
+      return t.subtrees[0];
+    }
+
+    private void SampleTree(SearchTreeNode searchTree, Stack<Tuple<Tree, int, int>> extensionPoints) {
+      const int RANDOM_TRIES = 100;
+      if(extensionPoints.Count == 0) return; // nothing to do
+      var extensionPoint = extensionPoints.Pop();
+      Tree parent = extensionPoint.Item1;
+      int state = extensionPoint.Item2;
+      int subtreeIdx = extensionPoint.Item3;
+      Tree t = null;
+      
+      if(searchTree.tries < RANDOM_TRIES || Grammar.subtreeCount[state] == 0) {
+        searchTree.tries++; // could be moved to UpdateTree
+        t = SampleTreeRandom(state);
+        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);
+        } else {
+          // fill up all remaining slots randomly
+          foreach(var p in extensionPoints) {
+            var pParent = p.Item1;
+            var pState = p.Item2;
+            var pIdx = p.Item3;
+            pParent.subtrees[pIdx] = SampleTreeRandom(pState);
+          }
+        }
+      } else {
+        if(Grammar.subtreeCount[state] == 1) {
+          searchTree.tries++; // could be moved to updateTree
+          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 - 1 == searchTree.children.Where(c=>c!=null).Sum(c=>c.tries));
+          // check if there is an unchecked alternative
+          var altIdx = Array.FindIndex(searchTree.children, (e) => e == null);
+          if(altIdx != -1) {
+            Debug.Assert(searchTree.children[altIdx] == null);
+            searchTree.children[altIdx] = new SearchTreeNode();
+            t = new Tree(altIdx, new Tree[1]);
+            extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
+            SampleTree(searchTree.children[altIdx], extensionPoints);
+          } else {
+            // 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].tries < minSamples) {
+            //    minSamples = searchTree.children[idx].tries;
+            //    altIdx = idx;
+            //  }
+            //}
+            // 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 (UCB(searchTree, searchTree.children[idx]) > UCB(searchTree, searchTree.children[altIdx])) {
+                altIdx = idx;
+              }
+            }
+            t = new Tree(altIdx, new Tree[1]);
+            extensionPoints.Push(Tuple.Create(t, Grammar.transition[state][altIdx], 0));
+            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));
+          }
+          SampleTree(searchTree, extensionPoints);
+        }
+      }
+      Debug.Assert(parent.subtrees[subtreeIdx] == null);
+      parent.subtrees[subtreeIdx] = t;
+    }
+
+    private double UCB(SearchTreeNode parent, SearchTreeNode n) {
+      Debug.Assert(parent.tries >= n.tries);
+      Debug.Assert(n.tries > 0);
+      return n.sumQuality / n.tries + Math.Sqrt((2 * Math.Log(parent.tries)) / n.tries ); // constant is dependent fitness function values
+    }
+
+    private void UpdateSearchTree(Tree t, double quality) {
+      var trees = new Stack<Tree>();
+      trees.Push(t);
+      UpdateSearchTree(searchTree, trees, quality);
+    }
+
+    private void UpdateSearchTree(SearchTreeNode searchTree, Stack<Tree> trees, double quality) {
+      if(trees.Count == 0 || searchTree == null) return;
+      var t = trees.Pop();
+      searchTree.sumQuality += quality;
+      if(quality > searchTree.bestQuality)
+        searchTree.bestQuality = quality;
+      if(searchTree.children == null) return;
+      if(t.subtrees == null) { 
+        Debug.Assert(searchTree.children.Length == 1);
+        UpdateSearchTree(searchTree.children[0], trees, quality);
+      } else if(t.altIdx==-1) {
+        for(int idx = t.subtrees.Length - 1 ; idx >= 0; idx--) {
+          trees.Push(t.subtrees[idx]);
+        }
+        UpdateSearchTree(searchTree, trees, quality);
+      } else {
+        Debug.Assert(t.subtrees.Length == 1);
+        trees.Push(t.subtrees[0]);
+        UpdateSearchTree(searchTree.children[t.altIdx], trees, quality);
+      }
+    }
+
+    // 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();
+      }
+    }
+
+    //private double TerminalProbForDepth(int depth) {
+    //  return baseTerminalProbability + depth * terminalProbabilityInc;
+    //}
+
+    public static void Main(string[] args) {
+      // if(args.Length >= 1) ParseArguments(args);
+
+      var problem = new ?IDENT?Problem();
+      var solver = new ?IDENT?Solver(problem);
+      solver.Start();
+    }
+    //private static void ParseArguments(string[] args) {
+    //  var baseTerminalProbabilityRegex = new Regex(@""--terminalProbBase=(?<prob>.+)"");
+    //  var terminalProbabilityIncRegex = new Regex(@""--terminalProbInc=(?<prob>.+)"");
+    //  var helpRegex = new Regex(@""--help|/\?"");
+    //  
+    //  foreach(var arg in args) {
+    //    var baseTerminalProbabilityMatch = baseTerminalProbabilityRegex.Match(arg);
+    //    var terminalProbabilityIncMatch = terminalProbabilityIncRegex.Match(arg);
+    //    var helpMatch = helpRegex.Match(arg);
+    //    if(helpMatch.Success) { PrintUsage(); Environment.Exit(0); }
+    //    else if(baseTerminalProbabilityMatch.Success) {
+    //      baseTerminalProbability = double.Parse(baseTerminalProbabilityMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
+    //      if(baseTerminalProbability < 0.0 || baseTerminalProbability > 1.0) throw new ArgumentException(""base terminal probability must lie in range [0.0 ... 1.0]"");
+    //    } else if(terminalProbabilityIncMatch.Success) {
+    //       terminalProbabilityInc = double.Parse(terminalProbabilityIncMatch.Groups[""prob""].Captures[0].Value, System.Globalization.CultureInfo.InvariantCulture);
+    //       if(terminalProbabilityInc < 0.0 || terminalProbabilityInc > 1.0) throw new ArgumentException(""terminal probability increment must lie in range [0.0 ... 1.0]"");
+    //    } else {
+    //       Console.WriteLine(""Unknown switch {0}"", arg); PrintUsage(); Environment.Exit(0); 
+    //    }
+    //  }
+    //}
+    //private static void PrintUsage() {
+    //  Console.WriteLine(""Find a solution using monte carlo tree search."");
+    //  Console.WriteLine();
+    //  Console.WriteLine(""Parameters:"");
+    //  Console.WriteLine(""\t--terminalProbBase=<prob>\tSets the probability of sampling a terminal alternative in a rule [Default: 0.05]"");
+    //  Console.WriteLine(""\t--terminalProbInc=<prob>\tSets the increment for the probability of sampling a terminal alternative for each level in the syntax tree [Default: 0.05]"");
+    //}
+
+
+    public ?IDENT?Solver(?IDENT?Problem problem) {
+      this.problem = problem;
+      this.random = new Random();
+    }
+
+    private void Start() {
+      Console.ReadLine();
+      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
+      int n = 0;
+      long sumDepth = 0;
+      long sumSize = 0;
+      var sumF = 0.0;
+      var sw = new System.Diagnostics.Stopwatch();
+      sw.Start();
+      while (true) {
+
+        int steps, depth;
+        var _t = SampleTree();
+        //  _t.PrintTree(0); Console.WriteLine();
+
+        // inefficient but don't care for now
+        steps = _t.GetSize();
+        depth = _t.GetDepth();
+        var f = problem.Evaluate(_t);
+        if(?MAXIMIZATION?)
+          UpdateSearchTree(_t, f);
+        else
+          UpdateSearchTree(_t, -f);
+        n++;    
+        sumSize += steps;
+        sumDepth += depth;
+        sumF += f;
+        if (problem.IsBetter(f, bestF)) {
+          bestF = f;
+          _t.PrintTree(0); Console.WriteLine();
+          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, steps, depth);
+        }
+        if (n % 1000 == 0) {
+          sw.Stop();
+          Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
+          sumSize = 0;
+          sumDepth = 0;
+          sumF = 0.0;
+          sw.Restart();
+        }
+      }
+    }
+  }
+}";
+
+    public void Generate(IGrammar grammar, IEnumerable<TerminalNode> terminals, bool maximization, SourceBuilder problemSourceCode) {
+      var solverSourceCode = new SourceBuilder();
+      solverSourceCode.Append(solverTemplate)
+        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
+        .Replace("?SAMPLEALTERNATIVECODE?", GenerateSampleAlternativeSource(grammar))
+        .Replace("?CREATETERMINALNODECODE?", GenerateCreateTerminalCode(grammar, terminals))
+      ;
+
+      problemSourceCode.Append(solverSourceCode.ToString());
+    }
+
+
+
+    private string GenerateSampleAlternativeSource(IGrammar grammar) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+      int stateCount = 0;
+      foreach (var s in grammar.Symbols) {
+        sb.AppendFormat("case {0}: ", stateCount++);
+        if (grammar.IsTerminal(s)) {
+          // ignore
+        } else {
+          var terminalAltIndexes = grammar.GetAlternatives(s)
+            .Select((alt, idx) => new { alt, idx })
+            .Where((p) => p.alt.All(symb => grammar.IsTerminal(symb)))
+            .Select(p => p.idx);
+          var nonTerminalAltIndexes = grammar.GetAlternatives(s)
+            .Select((alt, idx) => new { alt, idx })
+            .Where((p) => p.alt.Any(symb => grammar.IsNonTerminal(symb)))
+            .Select(p => p.idx);
+          var hasTerminalAlts = terminalAltIndexes.Any();
+          var hasNonTerminalAlts = nonTerminalAltIndexes.Any();
+          if (hasTerminalAlts && hasNonTerminalAlts) {
+            sb.Append("if(maxDepth <= 1) {").BeginBlock();
+            GenerateReturnStatement(terminalAltIndexes, sb);
+            sb.Append("} else {");
+            GenerateReturnStatement(nonTerminalAltIndexes, sb);
+            sb.Append("}").EndBlock();
+          } else {
+            GenerateReturnStatement(grammar.NumberOfAlternatives(s), sb);
+          }
+        }
+      }
+      return sb.ToString();
+    }
+    private string GenerateCreateTerminalCode(IGrammar grammar, IEnumerable<TerminalNode> terminals) {
+      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
+      var sb = new SourceBuilder();
+      var allSymbols = grammar.Symbols.ToList();
+      foreach (var s in grammar.Symbols) {
+        if (grammar.IsTerminal(s)) {
+          sb.AppendFormat("case {0}: {{", allSymbols.IndexOf(s)).BeginBlock();
+          sb.AppendFormat("var t = new {0}Tree();", s.Name).AppendLine();
+          var terminal = terminals.Single(t => t.Ident == s.Name);
+          foreach (var constr in terminal.Constraints) {
+            if (constr.Type == ConstraintNodeType.Set) {
+              sb.Append("{").BeginBlock();
+              sb.AppendFormat("var elements = problem.GetAllowed{0}_{1}().ToArray();", terminal.Ident, constr.Ident).AppendLine();
+              sb.AppendFormat("t.{0} = elements[random.Next(elements.Length)]; ", constr.Ident).EndBlock();
+              sb.AppendLine("}");
+            } else {
+              sb.Append("{").BeginBlock();
+              sb.AppendFormat(" var max = problem.GetMax{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
+              sb.AppendFormat(" var min = problem.GetMin{0}_{1}();", terminal.Ident, constr.Ident).AppendLine();
+              sb.AppendFormat("t.{0} = random.NextDouble() * (max - min) + min;", constr.Ident).EndBlock();
+              sb.AppendLine("}");
+            }
+          }
+          sb.AppendLine("return t;").EndBlock();
+          sb.Append("}");
+        }
+      }
+      return sb.ToString();
+    }
+    private void GenerateReturnStatement(IEnumerable<int> idxs, SourceBuilder sb) {
+      if (idxs.Count() == 1) {
+        sb.AppendFormat("return {0};", idxs.Single()).AppendLine();
+      } else {
+        var idxStr = idxs.Aggregate(string.Empty, (str, idx) => str + idx + ", ");
+        sb.AppendFormat("return new int[] {{ {0} }}[random.Next({1})]; ", idxStr, idxs.Count()).AppendLine();
+      }
+    }
+
+    private void GenerateReturnStatement(int nAlts, SourceBuilder sb) {
+      if (nAlts > 1) {
+        sb.AppendFormat("return random.Next({0});", nAlts).AppendLine();
+      } else if (nAlts == 1) {
+        sb.AppendLine("return 0; ");
+      } else {
+        sb.AppendLine("throw new InvalidProgramException();");
+      }
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GPDL/TestAnt.bat
===================================================================
--- /branches/HeuristicLab.Problems.GPDL/TestAnt.bat	(revision 10408)
+++ /branches/HeuristicLab.Problems.GPDL/TestAnt.bat	(revision 10408)
@@ -0,0 +1,4 @@
+GpdlCompiler\bin\Debug\GpdlCompiler.exe "Examples\Artificial Ant.txt"
+csc /optimize- /debug+ /d:DEBUG "ArtificialAnt.cs"
+"ArtificialAnt.exe"
+
