Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11730)
@@ -17,10 +17,12 @@
     private readonly Random random;
     private readonly int contextLen;
+    private readonly Func<Random, int, IPolicy> policyFactory;
 
-    public AlternativesContextSampler(IProblem problem, int maxLen) {
+    public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, Func<Random, int, IPolicy> policyFactory) {
       this.maxLen = maxLen;
       this.problem = problem;
-      this.random = new Random(31415);
-      this.contextLen = 25;
+      this.random = random;
+      this.contextLen = contextLen;
+      this.policyFactory = policyFactory;
     }
 
@@ -29,6 +31,6 @@
       InitPolicies(problem.Grammar);
       for (int i = 0; i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         DistributeReward(quality);
 
@@ -45,4 +47,5 @@
     private Dictionary<string, IPolicy> ntPolicy;
     private List<Tuple<string, int>> updateChain;
+
     private void InitPolicies(IGrammar grammar) {
       this.ntPolicy = new Dictionary<string, IPolicy>();
@@ -50,16 +53,15 @@
     }
 
-    private string SampleSentence(IGrammar grammar) {
+    private Sequence SampleSentence(IGrammar grammar) {
       updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -67,5 +69,5 @@
 
         var alts = g.GetAlternatives(nt);
-        string selectedAlt;
+        Sequence selectedAlt;
         // if the choice is restricted then one of the allowed alternatives is selected randomly
         if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
@@ -76,10 +78,11 @@
         } else {
           // all alts are allowed => select using bandit policy
+          var ntIdx = phrase.FirstNonTerminalIndex;
           var startIdx = Math.Max(0, ntIdx - contextLen);
           var endIdx = Math.Min(startIdx + contextLen, ntIdx);
-          var lft = phrase.Substring(startIdx, endIdx - startIdx + 1);
+          var lft = phrase.Subsequence(startIdx, endIdx - startIdx + 1).ToString();
           lft = problem.Hash(lft);
           if (!ntPolicy.ContainsKey(lft)) {
-            ntPolicy.Add(lft, new UCB1TunedPolicy(g.GetAlternatives(nt).Count()));
+            ntPolicy.Add(lft, policyFactory(random, g.GetAlternatives(nt).Count()));
           }
           var selectedAltIdx = ntPolicy[lft].SelectAction();
@@ -89,8 +92,7 @@
 
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        done = phrase.IsTerminal; // terminal phrase means we are done
       }
       return phrase;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11730)
@@ -27,6 +27,6 @@
       InitPolicies(problem.Grammar);
       for (int i = 0; i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         DistributeReward(quality);
 
@@ -52,16 +52,15 @@
     }
 
-    private string SampleSentence(IGrammar grammar) {
+    private Sequence SampleSentence(IGrammar grammar) {
       updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -69,5 +68,5 @@
 
         var alts = g.GetAlternatives(nt);
-        string selectedAlt;
+        Sequence selectedAlt;
         // if the choice is restricted then one of the allowed alternatives is selected randomly
         if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
@@ -84,8 +83,7 @@
 
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        done = phrase.IsTerminal; // terminal phrase means we are done
       }
       return phrase;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11730)
@@ -11,5 +11,5 @@
 
     private readonly int maxLen;
-    private readonly Queue<string> bfsQueue = new Queue<string>();
+    private readonly Queue<Sequence> bfsQueue = new Queue<Sequence>();
     private readonly IProblem problem;
 
@@ -21,10 +21,10 @@
     public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      bfsQueue.Enqueue(problem.Grammar.SentenceSymbol.ToString());
+      bfsQueue.Enqueue(new Sequence(problem.Grammar.SentenceSymbol));
       var sentences = GenerateLanguage(problem.Grammar);
       var sentenceEnumerator = sentences.GetEnumerator();
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current;
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        var sentence = sentenceEnumerator.Current.ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -37,15 +37,16 @@
 
     // create sentences lazily
-    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
       while (bfsQueue.Any()) {
         var phrase = bfsQueue.Dequeue();
 
-        char nt;
+        char nt = phrase.FirstNonTerminal;
         int ntIdx;
-        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
+
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {
-          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
-          if (newPhrase.All(grammar.IsTerminal) && newPhrase.Length <= maxLen) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
             yield return newPhrase;
           } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11730)
@@ -11,17 +11,19 @@
 
     private readonly int maxLen;
-    private readonly Stack<string> stack = new Stack<string>();
+    private readonly Stack<Sequence> stack = new Stack<Sequence>();
+    private readonly IProblem problem;
 
-    public ExhaustiveDepthFirstSearch(int maxLen) {
+    public ExhaustiveDepthFirstSearch(IProblem problem, int maxLen) {
       this.maxLen = maxLen;
+      this.problem = problem;
     }
 
-    public void Run(IProblem problem, int maxIterations) {
+    public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      stack.Push(problem.Grammar.SentenceSymbol.ToString());
+      stack.Push(new Sequence(problem.Grammar.SentenceSymbol));
       var sentences = GenerateLanguage(problem.Grammar);
       var sentenceEnumerator = sentences.GetEnumerator();
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current;
+        var sentence = sentenceEnumerator.Current.ToString();
         var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
@@ -35,15 +37,15 @@
 
     // create sentences lazily
-    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
       while (stack.Any()) {
         var phrase = stack.Pop();
 
-        char nt;
-        int ntIdx;
-        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {
-          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
-          if (newPhrase.All(grammar.IsTerminal) && newPhrase.Length <= maxLen) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
             yield return newPhrase;
           } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11730)
@@ -10,13 +10,20 @@
   public class MctsSampler {
     private class TreeNode {
+      public string ident;
       public int randomTries;
+      public int policyTries;
       public IPolicy policy;
       public TreeNode[] children;
       public bool done = false;
 
+      public TreeNode(string id) {
+        this.ident = id;
+      }
+
       public override string ToString() {
-        return string.Format("Node(random-tries: {0}, done: {1}, policy: {2})", randomTries, done, policy);
+        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, randomTries + policyTries, done, policy);
       }
     }
+
 
     public event Action<string, double> FoundNewBestSolution;
@@ -27,15 +34,18 @@
     private readonly Random random;
     private readonly int randomTries;
-    private readonly Func<int, IPolicy> policyFactory;
+    private readonly Func<Random, int, IPolicy> policyFactory;
 
     private List<Tuple<TreeNode, int>> updateChain;
     private TreeNode rootNode;
 
+    public int treeDepth;
+    public int treeSize;
+
     public MctsSampler(IProblem problem, int maxLen, Random random) :
-      this(problem, maxLen, random, 10, (numActions) => new EpsGreedyPolicy(random, numActions, 0.1)) {
+      this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) {
 
     }
 
-    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<int, IPolicy> policyFactory) {
+    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<Random, int, IPolicy> policyFactory) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -47,7 +57,7 @@
     public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      InitPolicies();
+      InitPolicies(problem.Grammar);
       for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
+        var sentence = SampleSentence(problem.Grammar).ToString();
         var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         Debug.Assert(quality >= 0 && quality <= 1.0);
@@ -61,25 +71,45 @@
         }
       }
+
+      // clean up
+      InitPolicies(problem.Grammar); GC.Collect();
     }
 
-    private void InitPolicies() {
-      this.updateChain = new List<Tuple<TreeNode, int>>();
-      rootNode = new TreeNode();
+    public void PrintStats() {
+      var n = rootNode;
+      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries);
+      while (n.policy != null) {
+        Console.WriteLine();
+        Console.WriteLine("{0,5}->{1,-50}", n.ident, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.ident))));
+        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.randomTries + ch.policyTries))));
+        //n.policy.PrintStats();
+        n = n.children.OrderByDescending(c => c.policyTries).First();
+      }
+      Console.ReadLine();
     }
 
-    private string SampleSentence(IGrammar grammar) {
-      updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+    private void InitPolicies(IGrammar grammar) {
+      this.updateChain = new List<Tuple<TreeNode, int>>();
+
+      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
+      treeDepth = 0;
+      treeSize = 0;
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      var startPhrase = new Sequence(grammar.SentenceSymbol);
+      return CompleteSentence(grammar, startPhrase);
+    }
+
+    private Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
       TreeNode n = rootNode;
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal;
       int selectedAltIdx = -1;
+      var curDepth = 0;
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -90,20 +120,28 @@
         if (n.randomTries < randomTries) {
           n.randomTries++;
+
+          treeDepth = Math.Max(treeDepth, curDepth);
+
           return g.CompleteSentenceRandomly(random, phrase, maxLen);
         } else if (n.randomTries == randomTries && n.policy == null) {
-          n.policy = policyFactory(alts.Count());
-          n.children = alts.Select(_ => new TreeNode()).ToArray(); // create a new node for each alternative
+          n.policy = policyFactory(random, alts.Count());
+          //n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
+          n.children = alts.Select(alt => new TreeNode(string.Empty)).ToArray(); // create a new node for each alternative
+
+          treeSize += n.children.Length;
         }
-
+        n.policyTries++;
         // => select using bandit policy
         selectedAltIdx = n.policy.SelectAction();
-        string selectedAlt = alts.ElementAt(selectedAltIdx);
+        Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
+
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
         updateChain.Add(Tuple.Create(n, selectedAltIdx));
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        curDepth++;
+
+        done = phrase.IsTerminal;
         if (!done) {
           // prepare for next iteration
@@ -116,4 +154,5 @@
       n.children[selectedAltIdx].done = true;
 
+      treeDepth = Math.Max(treeDepth, curDepth);
       return phrase;
     }
@@ -127,4 +166,5 @@
         var policy = node.policy;
         var action = e.Item2;
+        //policy.UpdateReward(action, reward / updateChain.Count);
         policy.UpdateReward(action, reward);
 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11727)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11730)
@@ -13,15 +13,17 @@
     private readonly int maxLen;
     private readonly Random random;
+    private readonly IProblem problem;
 
-    public RandomSearch(int maxLen) {
+    public RandomSearch(IProblem problem, Random random, int maxLen) {
       this.maxLen = maxLen;
-      this.random = new Random(31415);
+      this.random = random;
+      this.problem = problem;
     }
 
-    public void Run(IProblem problem, int maxIterations) {
+    public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
       for (int i = 0; i < maxIterations; i++) {
-        var sentence = CreateSentence(problem.Grammar);
-        var quality = problem.Evaluate(sentence);
+        var sentence = CreateSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -33,6 +35,6 @@
     }
 
-    private string CreateSentence(IGrammar grammar) {
-      var sentence = grammar.SentenceSymbol.ToString();
+    private Sequence CreateSentence(IGrammar grammar) {
+      var sentence = new Sequence(grammar.SentenceSymbol);
       return grammar.CompleteSentenceRandomly(random, sentence, maxLen);
     }
