Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ActiveLearningPolicy.cs	(revision 11806)
@@ -11,7 +11,7 @@
     public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       const double delta = 0.1;
-      int k = myActionInfos.Where(a => !a.Disabled).Count();
+      int k = myActionInfos.Count();
       var bestActions = new List<int>();
       var us = new List<double>();
@@ -20,5 +20,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         double u;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs	(revision 11806)
@@ -37,7 +37,5 @@
 
       var w = from aInfo in myActionInfos
-              select aInfo.Disabled
-                ? 0.0
-                : Math.Exp(beta * valueFunction(aInfo));
+              select Math.Exp(beta * valueFunction(aInfo));
 
       var bestAction = Enumerable.Range(0, myActionInfos.Count()).SampleProportional(random, w);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ChernoffIntervalEstimationPolicy.cs	(revision 11806)
@@ -21,6 +21,6 @@
       // select best
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
-      int k = myActionInfos.Count(a => !a.Disabled);
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      int totalTries = myActionInfos.Sum(a => a.Tries);
       double bestQ = double.NegativeInfinity;
       var bestActions = new List<int>();
@@ -28,5 +28,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -46,5 +45,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/DefaultPolicyActionInfo.cs	(revision 11806)
@@ -9,6 +9,4 @@
   // stores information that is relevant for most of the policies
   public class DefaultPolicyActionInfo : IBanditPolicyActionInfo {
-    private double knownValue;
-    public bool Disabled { get { return Tries == -1; } }
     public double SumReward { get; private set; }
     public int Tries { get; private set; }
@@ -16,6 +14,4 @@
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
           return Tries > 0 ? SumReward / Tries : 0.0;
       }
@@ -26,23 +22,13 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
-
       Tries++;
       SumReward += reward;
       MaxReward = Math.Max(MaxReward, reward);
     }
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.SumReward = 0.0;
-      this.knownValue = reward;
-    }
+
     public void Reset() {
       SumReward = 0.0;
       Tries = 0;
       MaxReward = 0.0;
-      knownValue = 0.0;
-    }
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", SumReward / Tries, Disabled);
     }
 
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/EpsGreedyPolicy.cs	(revision 11806)
@@ -35,5 +35,4 @@
         foreach (var aInfo in myActionInfos) {
           aIdx++;
-          if (aInfo.Disabled) continue;
 
           var q = valueFunction(aInfo);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs	(revision 11806)
@@ -22,6 +22,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
-        //if (aInfo.Tries == 0) return aIdx;
         var q = aInfo.SampleExpectedReward(random);
         if (q > bestQ) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/MeanAndVariancePolicyActionInfo.cs	(revision 11806)
@@ -39,8 +39,4 @@
       estimator.Reset();
     }
-
-    public void PrintStats() {
-      Console.WriteLine("avg reward {0,5:F2} disabled {1}", AvgReward, Disabled);
-    }
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModelPolicyActionInfo.cs	(revision 11806)
@@ -10,11 +10,7 @@
   public class ModelPolicyActionInfo : IBanditPolicyActionInfo {
     private readonly IModel model;
-    private double knownValue;
-    public bool Disabled { get { return Tries == -1; } }
     public double Value {
       get {
-        if (Disabled) return knownValue;
-        else
-          return model.SampleExpectedReward(new Random());
+        return model.SampleExpectedReward(new Random());
       }
     }
@@ -26,5 +22,4 @@
 
     public void UpdateReward(double reward) {
-      Debug.Assert(!Disabled);
       Tries++;
       model.Update(reward);
@@ -35,21 +30,11 @@
     }
 
-    public void Disable(double reward) {
-      this.Tries = -1;
-      this.knownValue = reward;
-    }
-
     public void Reset() {
       Tries = 0;
-      knownValue = 0.0;
       model.Reset();
     }
 
-    public void PrintStats() {
-      model.PrintStats();
-    }
-
     public override string ToString() {
-      return string.Format("disabled {0} model {1}", Disabled, model);
+      return string.Format("model {1}", model);
     }
   }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ModifiedUCTPolicy.cs	(revision 11806)
@@ -0,0 +1,55 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits.BanditPolicies {
+  /* modified UCT: see Coquelin & Munos, Bandit Algorithms for Tree Search, UAI 2007 */
+  public class ModifiedUCTPolicy : IBanditPolicy {
+    private readonly double c;
+
+    public ModifiedUCTPolicy(double c = 1.0) {
+      this.c = c;
+    }
+
+
+    public int SelectAction(Random random, IEnumerable<IBanditPolicyActionInfo> actionInfos) {
+      var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
+      double bestQ = double.NegativeInfinity;
+      int totalTries = myActionInfos.Sum(a => a.Tries);
+
+      int aIdx = -1;
+      var bestActions = new List<int>();
+      foreach (var aInfo in myActionInfos) {
+        aIdx++;
+        double q;
+        if (aInfo.Tries == 0) {
+          q = double.PositiveInfinity;
+        } else {
+          q = aInfo.SumReward / aInfo.Tries + c * Math.Sqrt(Math.Sqrt(totalTries) / aInfo.Tries); // modification in comparison to original UCT
+        }
+        if (q > bestQ) {
+          bestActions.Clear();
+          bestQ = q;
+          bestActions.Add(aIdx);
+        } else if (q.IsAlmost(bestQ)) {
+          bestActions.Add(aIdx);
+        }
+
+      }
+      Debug.Assert(bestActions.Any());
+      return bestActions.SelectRandom(random);
+    }
+
+    public IBanditPolicyActionInfo CreateActionInfo() {
+      return new DefaultPolicyActionInfo();
+    }
+
+    public override string ToString() {
+      return string.Format("ModifiedUCTPolicy({0:F2})", c);
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/RandomPolicy.cs	(revision 11806)
@@ -17,5 +17,4 @@
       return actionInfos
         .Select((aInfo, idx) => Tuple.Create(aInfo, idx))
-        .Where(p => !p.Item1.Disabled)
         .SelectRandom(random).Item2;
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/ThresholdAscentPolicy.cs	(revision 11806)
@@ -28,15 +28,11 @@
       public int Tries { get; private set; }
       public int thresholdBin = 1;
-      private double knownValue;
 
       public double Value {
         get {
-          if (Disabled) return knownValue;
           if (Tries == 0.0) return 0.0;
           return rewardHistogram[thresholdBin] / (double)Tries;
         }
       }
-
-      public bool Disabled { get { return Tries == -1; } }
 
       public void UpdateReward(double reward) {
@@ -46,22 +42,8 @@
       }
 
-      public void Disable(double reward) {
-        this.knownValue = reward;
-        Tries = -1;
-      }
-
       public void Reset() {
         Tries = 0;
         thresholdBin = 1;
-        this.knownValue = 0.0;
         Array.Clear(rewardHistogram, 0, rewardHistogram.Length);
-      }
-
-      public void PrintStats() {
-        if (Tries >= 0) {
-          Console.Write("{0,6}", Tries);
-        } else {
-          Console.Write("{0,6}", "");
-        }
       }
 
@@ -101,10 +83,9 @@
       var bestActions = new List<int>();
       double bestQ = double.NegativeInfinity;
-      int k = myActionInfos.Count(a => !a.Disabled);
-      var totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int k = myActionInfos.Count();
+      var totalTries = myActionInfos.Sum(a => a.Tries);
       int aIdx = -1;
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -118,5 +99,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1Policy.cs	(revision 11806)
@@ -13,5 +13,5 @@
       var myActionInfos = actionInfos.OfType<DefaultPolicyActionInfo>();
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       var bestActions = new List<int>();
@@ -19,5 +19,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -31,5 +30,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCB1TunedPolicy.cs	(revision 11806)
@@ -37,5 +37,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCBNormalPolicy.cs	(revision 11806)
@@ -33,5 +33,5 @@
           bestActions.Clear();
           bestActions.Add(aIdx);
-        } else if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/UCTPolicy.cs	(revision 11806)
@@ -21,5 +21,5 @@
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      int totalTries = myActionInfos.Where(a => !a.Disabled).Sum(a => a.Tries);
+      int totalTries = myActionInfos.Sum(a => a.Tries);
 
       int aIdx = -1;
@@ -27,5 +27,4 @@
       foreach (var aInfo in myActionInfos) {
         aIdx++;
-        if (aInfo.Disabled) continue;
         double q;
         if (aInfo.Tries == 0) {
@@ -38,6 +37,5 @@
           bestQ = q;
           bestActions.Add(aIdx);
-        }
-        if (q == bestQ) {
+        } else if (q.IsAlmost(bestQ)) {
           bestActions.Add(aIdx);
         }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11806)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -9,31 +10,55 @@
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
   // this represents grammar policies that use one of the available bandit policies for state selection
-  public class GenericGrammarPolicy : IGrammarPolicy {
-    protected Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state 
-    private readonly bool useCanonicalState;
+  // any bandit policy can be used to select actions for states
+  // a separate datastructure is used to store visited states and to prevent revisiting of states
+  public sealed class GenericGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
 
-    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
-      this.useCanonicalState = useCanonicalState;
+    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
       this.problem = problem;
       this.banditPolicy = banditPolicy;
       this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
     }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
 
     public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
       // fail if all states are done (corresponding state infos are disabled)
-      if (afterStates.All(s => GetStateInfo(s).Disabled)) {
+      if (afterStates.All(s => Done(s))) {
         // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
+        MarkAsDone(curState);
 
-        GetStateInfo(curState).Disable(afterStates.Select(afterState => GetStateInfo(afterState).Value).Max());
         selectedStateIdx = -1;
         return false;
       }
 
-      selectedStateIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
 
       return true;
     }
+
+
 
     private IBanditPolicyActionInfo GetStateInfo(string state) {
@@ -47,5 +72,5 @@
     }
 
-    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
       foreach (var state in stateTrajectory) {
         GetStateInfo(state).UpdateReward(reward);
@@ -53,11 +78,13 @@
         // only the last state can be terminal
         if (problem.Grammar.IsTerminal(state)) {
-          GetStateInfo(state).Disable(reward);
+          MarkAsDone(state);
         }
       }
     }
 
-    public virtual void Reset() {
+
+    public void Reset() {
       stateInfo.Clear();
+      done.Clear();
     }
 
@@ -74,6 +101,42 @@
     }
 
-    protected string CanonicalState(string state) {
-      if (useCanonicalState) {
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
         return problem.CanonicalRepresentation(state);
       } else
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs	(revision 11806)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericTDPolicy.cs	(revision 11806)
@@ -0,0 +1,153 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public sealed class GenericTDPolicy : IGrammarPolicy {
+    private Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
+    private readonly IProblem problem;
+    private readonly IBanditPolicy banditPolicy;
+
+    public GenericTDPolicy(IProblem problem, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
+      this.problem = problem;
+      this.banditPolicy = new EpsGreedyPolicy(0.1);
+      this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
+    }
+
+    private IBanditPolicyActionInfo[] activeAfterStates; // don't allocate each time
+    private int[] actionIndexMap; // don't allocate each time
+
+    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      // fail if all states are done (corresponding state infos are disabled)
+      if (afterStates.All(s => Done(s))) {
+        // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
+        MarkAsDone(curState);
+
+        selectedStateIdx = -1;
+        return false;
+      }
+
+      // determine active actions (not done yet) and create an array to map the selected index back to original actions
+      if (activeAfterStates == null || activeAfterStates.Length < afterStates.Count()) {
+        activeAfterStates = new IBanditPolicyActionInfo[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var idx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[idx] = GetStateInfo(afterState);
+          actionIndexMap[idx] = originalIdx;
+          idx++;
+        }
+        originalIdx++;
+      }
+
+      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+      
+      
+      GetStateInfo(curState).UpdateReward(afterStates.Select(s=>GetStateInfo(s).Value).Max());
+
+      return true;
+    }
+
+
+
+    private IBanditPolicyActionInfo GetStateInfo(string state) {
+      var s = CanonicalState(state);
+      IBanditPolicyActionInfo info;
+      if (!stateInfo.TryGetValue(s, out info)) {
+        info = banditPolicy.CreateActionInfo();
+        stateInfo[s] = info;
+      }
+      return info;
+    }
+
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+
+      foreach (var state in stateTrajectory.Zip(stateTrajectory.Skip(1), Tuple.Create)) {
+        var parent = state.Item1;
+        var child = state.Item2;
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(child)) {
+          MarkAsDone(child);
+        }
+        // GetStateInfo(parent).UpdateReward(GetValue(child));
+
+      }
+
+      GetStateInfo(stateTrajectory.Last()).UpdateReward(reward);
+    }
+
+
+    public void Reset() {
+      stateInfo.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(string state) {
+      var s = CanonicalState(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
+      else return 0;
+    }
+
+    public double GetValue(string state) {
+      var s = CanonicalState(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      else return 0.0; // TODO: check alternatives
+    }
+
+    // the canonical states for the value function (banditInfos) and the done set must be distinguished
+    // sequences of different length could have the same canonical representation and can have the same value (banditInfo)
+    // however, if the canonical representation of a state is shorter than we must not mark the canonical state as done when all possible derivations from the initial state have been explored
+    // eg. in the ant problem the canonical representation for ...lllA is ...rA
+    // even though all possible derivations (of limited length) of lllA have been visited we must not mark the state rA as done
+    private void MarkAsDone(string state) {
+      var s = CanonicalState(state);
+      // when the lengths of the canonical string and the original string are the same we also disable the actions
+      // always disable terminals
+      Debug.Assert(s.Length <= state.Length);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        Debug.Assert(!done.Contains(s));
+        done.Add(s);
+      } else {
+        // for non-terminals where the canonical string is shorter than the original string we can only disable the canonical representation for all states in the same level
+        Debug.Assert(!done.Contains(s + state.Length));
+        done.Add(s + state.Length); // encode the original length of the state, states in the same level of the tree are treated as equivalent
+      }
+    }
+
+    // symmetric to MarkDone
+    private bool Done(string state) {
+      var s = CanonicalState(state);
+      if (s.Length == state.Length || problem.Grammar.IsTerminal(state)) {
+        return done.Contains(s);
+      } else {
+        // it is not necessary to visit states if the canonical representation has already been fully explored
+        if (done.Contains(s)) return true;
+        if (done.Contains(s + state.Length)) return true;
+        for (int i = 1; i < state.Length; i++) {
+          if (done.Contains(s + i)) return true;
+        }
+        return false;
+      }
+    }
+
+    private string CanonicalState(string state) {
+      if (useCanonicalPhrases) {
+        return problem.CanonicalRepresentation(state);
+      } else
+        return state;
+    }
+  }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11806)
@@ -49,4 +49,5 @@
     <Compile Include="BanditPolicies\ChernoffIntervalEstimationPolicy.cs" />
     <Compile Include="BanditPolicies\ActiveLearningPolicy.cs" />
+    <Compile Include="BanditPolicies\ModifiedUCTPolicy.cs" />
     <Compile Include="BanditPolicies\DefaultPolicyActionInfo.cs" />
     <Compile Include="BanditPolicies\EpsGreedyPolicy.cs" />
@@ -66,4 +67,5 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
     <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
       <SubType>Code</SubType>
@@ -72,5 +74,4 @@
       <SubType>Code</SubType>
     </Compile>
-    <Compile Include="GrammarPolicies\TDPolicy.cs" />
     <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
     <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11806)
@@ -1,12 +1,11 @@
 ﻿namespace HeuristicLab.Algorithms.Bandits {
   public interface IBanditPolicyActionInfo {
-    bool Disabled { get; }
+    //bool Disabled { get; }
     double Value { get; }
     int Tries { get; }
     void UpdateReward(double reward);
-    void Disable(double reward);
+    //void Disable(double reward);
     // reset causes the state of the action to be reinitialized (as after constructor-call)
     void Reset();
-    void PrintStats();
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ContextualMctsSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ContextualMctsSampler.cs	(revision 11805)
+++ 	(revision )
@@ -1,207 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Algorithms.Bandits;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class ContextualMctsSampler {
-    private class TreeNode {
-      public string ident;
-      public int randomTries;
-      public int policyTries;
-      public TreeNode[] children;
-      public bool done = false;
-
-      public TreeNode(string id) {
-        this.ident = id;
-      }
-
-      public override string ToString() {
-        return string.Format("Node({0} tries: {1}, done: {2})", ident, randomTries + policyTries, done);
-      }
-    }
-
-
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly IProblem problem;
-    private readonly Random random;
-    private readonly int randomTries;
-    private readonly Func<Random, int, IPolicy> policyFactory;
-    private readonly Dictionary<string, IPolicy> policyForState;
-
-    private List<Tuple<TreeNode, int, string>> updateChain;
-    private TreeNode rootNode;
-
-    public int treeDepth;
-    public int treeSize;
-
-    public ContextualMctsSampler(IProblem problem, int maxLen, Random random) :
-      this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) {
-
-    }
-
-    public ContextualMctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<Random, int, IPolicy> policyFactory) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = random;
-      this.randomTries = randomTries;
-      this.policyFactory = policyFactory;
-      this.policyForState = new Dictionary<string, IPolicy>();
-    }
-
-    public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
-      InitPolicies(problem.Grammar);
-      for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
-        Debug.Assert(quality >= 0 && quality <= 1.0);
-        DistributeReward(quality);
-
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-
-      // clean up
-      InitPolicies(problem.Grammar); GC.Collect();
-    }
-
-    public void PrintStats() {
-      var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries);
-      foreach (var p in policyForState.OrderBy(p => p.Key.Length).ThenBy(p => p.Key)) {
-        Console.Write("{0,10} {1,20}", p.Key, p.Value);
-        p.Value.PrintStats();
-      }
-      //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 void InitPolicies(IGrammar grammar) {
-      this.updateChain = new List<Tuple<TreeNode, int, string>>();
-      policyForState.Clear();
-      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
-      treeDepth = 0;
-      treeSize = 0;
-    }
-
-    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.IsTerminal;
-      int selectedAltIdx = -1;
-      var curDepth = 0;
-      while (!done) {
-        var terminalSequence = phrase.Subsequence(0, phrase.FirstNonTerminalIndex).ToString();
-
-        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
-        Debug.Assert(maxLenOfReplacement > 0);
-
-        var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-
-        if (n.randomTries < randomTries) {
-          n.randomTries++;
-
-          treeDepth = Math.Max(treeDepth, curDepth);
-
-          return g.CompleteSentenceRandomly(random, phrase, maxLen);
-        } else if (n.randomTries == randomTries && n.children == null) {
-          n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
-
-          treeSize += n.children.Length;
-        }
-
-        IPolicy policy = GetPolicyForTerminalSequence(terminalSequence, alts.Count());
-        n.policyTries++;
-        // => select using bandit policy
-        selectedAltIdx = policy.SelectAction();
-        if (selectedAltIdx == -1) {
-          // oops
-          n.done = true;
-          Console.Write("*");
-          return g.CompleteSentenceRandomly(random, phrase, maxLen);
-        }
-        Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
-        updateChain.Add(Tuple.Create(n, selectedAltIdx, terminalSequence)); // context is terminal sequence so far
-
-        // replace nt with alt
-        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-
-        curDepth++;
-
-        done = phrase.IsTerminal;
-        // prepare for next iteration
-        n = n.children[selectedAltIdx];
-        Debug.Assert(!n.done);
-      } // while
-
-      // the last node is a leaf node (sentence is done), so we never need to visit this node again
-      n.done = true;
-
-      treeDepth = Math.Max(treeDepth, curDepth);
-      return phrase;
-    }
-
-    private void DistributeReward(double reward) {
-      // iterate in reverse order (bottom up)
-      updateChain.Reverse();
-
-      foreach (var e in updateChain) {
-        var node = e.Item1;
-        var action = e.Item2;
-        var sequence = e.Item3;
-        var policy = GetPolicyForTerminalSequence(sequence, -1);
-        //policy.UpdateReward(action, reward / updateChain.Count);
-        policy.UpdateReward(action, reward);
-
-        if (node.children[action].done) policy.DisableAction(action);
-        if (node.children.All(c => c.done)) node.done = true;
-      }
-    }
-
-    private IPolicy GetPolicyForTerminalSequence(string sequence, int numAlts) {
-      IPolicy p;
-      sequence = problem.Hash(sequence);
-      if (!policyForState.TryGetValue(sequence, out p)) {
-        p = policyFactory(random, numAlts);
-        policyForState.Add(sequence, p);
-      }
-      return p;
-    }
-
-    private void RaiseSolutionEvaluated(string sentence, double quality) {
-      var handler = SolutionEvaluated;
-      if (handler != null) handler(sentence, quality);
-    }
-    private void RaiseFoundNewBestSolution(string sentence, double quality) {
-      var handler = FoundNewBestSolution;
-      if (handler != null) handler(sentence, quality);
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11806)
@@ -46,10 +46,5 @@
     <Compile Include="AlternativesContextSampler.cs" />
     <Compile Include="SequentialSearch.cs" />
-    <Compile Include="TemporalDifferenceTreeSearchSampler.cs" />
     <Compile Include="ExhaustiveRandomFirstSearch.cs" />
-    <Compile Include="MctsContextualSampler.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="MctsSampler.cs" />
     <Compile Include="ExhaustiveDepthFirstSearch.cs" />
     <Compile Include="ExhaustiveBreadthFirstSearch.cs" />
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsContextualSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsContextualSampler.cs	(revision 11805)
+++ 	(revision )
@@ -1,358 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Algorithms.Bandits;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class MctsContextualSampler {
-    private class TreeNode {
-      public string ident;
-      public ReadonlySequence alt;
-      public int randomTries;
-      public int tries;
-      public List<TreeNode> parents;
-      public TreeNode[] children;
-      public bool done = false;
-
-      public TreeNode(string id, ReadonlySequence alt) {
-        this.ident = id;
-        this.alt = alt;
-        this.parents = new List<TreeNode>();
-      }
-
-      public override string ToString() {
-        return string.Format("Node({0} tries: {1}, done: {2})", ident, tries, done);
-      }
-    }
-
-    private Dictionary<string, TreeNode> treeNodes;
-    private TreeNode GetTreeNode(string id, ReadonlySequence alt) {
-      TreeNode n;
-      var canonicalId = problem.CanonicalRepresentation(id);
-      if (!treeNodes.TryGetValue(canonicalId, out n)) {
-        n = new TreeNode(canonicalId, alt);
-        tries.TryGetValue(canonicalId, out n.tries);
-        treeNodes[canonicalId] = n;
-      }
-      return n;
-    }
-
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly IProblem problem;
-    private readonly Random random;
-    private readonly int randomTries;
-
-    private List<Tuple<TreeNode, TreeNode>> updateChain;
-    private TreeNode rootNode;
-
-    public int treeDepth;
-    public int treeSize;
-    private double bestQuality;
-
-    public MctsContextualSampler(IProblem problem, int maxLen, Random random, int randomTries) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = random;
-      this.randomTries = randomTries;
-      this.v = new Dictionary<string, double>(1000000);
-      this.tries = new Dictionary<string, int>(1000000);
-      treeNodes = new Dictionary<string, TreeNode>();
-    }
-
-    public void Run(int maxIterations) {
-      bestQuality = double.MinValue;
-      InitPolicies(problem.Grammar);
-      for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        bool success;
-        var sentence = SampleSentence(problem.Grammar, out success).ToString();
-        if (success) {
-          var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-          Debug.Assert(quality >= 0 && quality <= 1.0);
-          DistributeReward(quality);
-
-          RaiseSolutionEvaluated(sentence, quality);
-
-          if (quality > bestQuality) {
-            bestQuality = quality;
-            RaiseFoundNewBestSolution(sentence, quality);
-          }
-        }
-      }
-
-      // clean up
-      InitPolicies(problem.Grammar); GC.Collect();
-    }
-
-    public void PrintStats() {
-      var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.tries, V(n), bestQuality);
-      while (n.children != null) {
-        Console.WriteLine("{0,-30}", n.ident);
-        double maxVForRow = n.children.Select(ch => Math.Min(1.0, Math.Max(0.0, V(ch)))).Max();
-        if (maxVForRow == 0) maxVForRow = 1.0;
-
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          Console.ForegroundColor = ConsoleEx.ColorForValue(Math.Min(1.0, V(ch)) / maxVForRow);
-          Console.Write("{0,5}", ch.alt);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          Console.ForegroundColor = ConsoleEx.ColorForValue(Math.Min(1.0, V(ch)) / maxVForRow);
-          Console.Write("{0,5:F2}", Math.Min(1.0, V(ch)) * 10);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          Console.ForegroundColor = ConsoleEx.ColorForValue(Math.Min(1.0, V(ch)) / maxVForRow);
-          Console.Write("{0,5}", ch.done ? "X" : ch.tries.ToString());
-        }
-        Console.ForegroundColor = ConsoleColor.White;
-        Console.WriteLine();
-        //n.policy.PrintStats();
-        n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.tries).First();
-      }
-    }
-
-
-    private void InitPolicies(IGrammar grammar) {
-      this.updateChain = new List<Tuple<TreeNode, TreeNode>>();
-      this.v.Clear();
-      this.tries.Clear();
-
-      rootNode = GetTreeNode(grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
-      treeDepth = 0;
-      treeSize = 0;
-    }
-
-    private Sequence SampleSentence(IGrammar grammar, out bool success) {
-      updateChain.Clear();
-      //var startPhrase = new Sequence("a*b+c*d+e*f+E");
-      var startPhrase = new Sequence(grammar.SentenceSymbol);
-      return CompleteSentence(grammar, startPhrase, out success);
-    }
-
-    private Sequence CompleteSentence(IGrammar g, Sequence phrase, out bool success) {
-      if (phrase.Length > maxLen) throw new ArgumentException();
-      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      TreeNode parent = null;
-      TreeNode n = rootNode;
-      var curDepth = 0;
-      while (!phrase.IsTerminal) {
-        updateChain.Add(Tuple.Create(n, parent));
-
-        if (n.randomTries < randomTries) {
-          n.randomTries++;
-          treeDepth = Math.Max(treeDepth, curDepth);
-          success = true;
-          return g.CompleteSentenceRandomly(random, phrase, maxLen);
-        } else {
-          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
-          Debug.Assert(maxLenOfReplacement > 0);
-
-          var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-
-          if (n.randomTries == randomTries && n.children == null) {
-            // create a new node for each alternative
-            n.children = new TreeNode[alts.Count()];
-            var i = 0;
-            foreach (var alt in alts) {
-              var newPhrase = new Sequence(phrase);
-              newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
-              if (!newPhrase.IsTerminal) newPhrase = newPhrase.Subsequence(0, newPhrase.FirstNonTerminalIndex + 1);
-              var treeNode = GetTreeNode(newPhrase.ToString(), new ReadonlySequence(alt));
-              treeNode.parents.Add(n);
-              n.children[i++] = treeNode;
-            }
-            treeSize += n.children.Length;
-            UpdateDone(n);
-
-            // it could happend that we already finished all variations starting from the branch
-            // stop
-            if (n.done) {
-              success = false;
-              return phrase;
-            }
-          }
-          //int selectedAltIdx = SelectRandom(random, n.children);
-
-          // => select using eps-greedy
-          int selectedAltIdx = SelectEpsGreedy(random, n.children);
-
-          //int selectedAltIdx = SelectActionUCB1(random, n.children);
-          Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
-
-          // replace nt with alt
-          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-          curDepth++;
-
-
-          // prepare for next iteration
-          parent = n;
-          n = n.children[selectedAltIdx];
-          //UpdateTD(parent, n, 0.0);
-        }
-      } // while
-
-      updateChain.Add(Tuple.Create(n, parent));
-
-      // the last node is a leaf node (sentence is done), so we never need to visit this node again
-      n.done = true;
-
-
-      treeDepth = Math.Max(treeDepth, curDepth);
-      success = true;
-      return phrase;
-    }
-
-
-    //private void UpdateTD(TreeNode parent, TreeNode child, double reward) {
-    //  double alpha = 1.0;
-    //  var vParent = V(parent);
-    //  var vChild = V(child);
-    //  if (double.IsInfinity(vParent)) vParent = 0.0;
-    //  if (double.IsInfinity(vChild)) vChild = 0.0;
-    //  UpdateV(parent, (alpha * (reward + vChild - vParent)));
-    //}
-
-    private void DistributeReward(double reward) {
-
-      // iterate in reverse order (bottom up)
-      //updateChain.Reverse();
-      UpdateDone(updateChain.Last().Item1);
-      //UpdateTD(updateChain.Last().Item2, updateChain.Last().Item1, reward);
-      //return;
-
-      BackPropReward(updateChain.Last().Item1, reward);
-      /*
-      foreach (var e in updateChain) {
-        var node = e.Item1;
-        //var parent = e.Item2;
-        node.tries++;
-        //if (node.children != null && node.children.All(c => c.done)) {
-        //  node.done = true;
-        //}
-        UpdateV(node, reward);
-
-        // the reward for the parent is either the just recieved reward or the value of the best action so far
-        //double value = 0.0;
-        //if (parent != null) {
-        //  var doneChilds = parent.children.Where(ch => ch.done);
-        //  if (doneChilds.Any()) value = doneChilds.Select(ch => V(ch)).Max();
-        //}
-        //if (value > reward) reward = value;
-      }*/
-    }
-
-    private void BackPropReward(TreeNode n, double reward) {
-      n.tries++;
-      UpdateV(n, reward);
-      foreach (var p in n.parents) BackPropReward(p, reward);
-    }
-
-    private void UpdateDone(TreeNode n) {
-      if (!n.done && n.children != null && n.children.All(c => c.done)) n.done = true;
-      if (n.done) foreach (var p in n.parents) UpdateDone(p);
-    }
-
-
-    private Dictionary<string, double> v;
-    private Dictionary<string, int> tries;
-
-    private void UpdateV(TreeNode n, double reward) {
-      var canonicalStr = problem.CanonicalRepresentation(n.ident);
-      //var canonicalStr = n.ident;
-      double stateV;
-
-      if (!v.TryGetValue(canonicalStr, out  stateV)) {
-        v.Add(canonicalStr, reward);
-        tries.Add(canonicalStr, 1);
-      } else {
-        //v[canonicalStr] = stateV + 0.005 * (reward - stateV);
-        v[canonicalStr] = stateV + (1.0 / tries[canonicalStr]) * (reward - stateV);
-        tries[canonicalStr]++;
-      }
-    }
-
-    private double V(TreeNode n) {
-      var canonicalStr = problem.CanonicalRepresentation(n.ident);
-      //var canonicalStr = n.ident;
-      double stateV;
-      if (!tries.ContainsKey(canonicalStr)) return double.PositiveInfinity;
-      if (!v.TryGetValue(canonicalStr, out  stateV)) {
-        return 0.0;
-      } else {
-        return stateV;
-      }
-    }
-
-    private int SelectRandom(Random random, TreeNode[] children) {
-      return children.Select((ch, i) => Tuple.Create(ch, i)).Where(p => !p.Item1.done).SelectRandom(random).Item2;
-    }
-
-    private int SelectEpsGreedy(Random random, TreeNode[] children) {
-      if (random.NextDouble() < 0.2) {
-        return SelectRandom(random, children);
-      } else {
-        var bestQ = double.NegativeInfinity;
-        var bestChildIdx = new List<int>();
-        for (int i = 0; i < children.Length; i++) {
-          if (children[i].done) continue;
-          // if (children[i].tries == 0) return i;
-          var q = V(children[i]);
-          if (q > bestQ) {
-            bestQ = q;
-            bestChildIdx.Clear();
-            bestChildIdx.Add(i);
-          } else if (q == bestQ) {
-            bestChildIdx.Add(i);
-          }
-        }
-        Debug.Assert(bestChildIdx.Any());
-        return bestChildIdx.SelectRandom(random);
-      }
-    }
-    private int SelectActionUCB1(Random random, TreeNode[] children) {
-      int bestAction = -1;
-      double bestQ = double.NegativeInfinity;
-      int totalTries = children.Sum(ch => ch.tries);
-
-      for (int a = 0; a < children.Length; a++) {
-        var ch = children[a];
-        if (ch.done) continue;
-        if (ch.tries == 0) return a;
-        var q = V(ch) + Math.Sqrt((2 * Math.Log(totalTries)) / ch.tries);
-        if (q > bestQ) {
-          bestQ = q;
-          bestAction = a;
-        }
-      }
-      Debug.Assert(bestAction > -1);
-      return bestAction;
-    }
-
-
-
-    private void RaiseSolutionEvaluated(string sentence, double quality) {
-      var handler = SolutionEvaluated;
-      if (handler != null) handler(sentence, quality);
-    }
-    private void RaiseFoundNewBestSolution(string sentence, double quality) {
-      var handler = FoundNewBestSolution;
-      if (handler != null) handler(sentence, quality);
-    }
-
-
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsQLearningSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsQLearningSampler.cs	(revision 11805)
+++ 	(revision )
@@ -1,243 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Algorithms.Bandits;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class MctsQLearningSampler {
-    private class TreeNode {
-      public string ident;
-      public int randomTries;
-      public int tries;
-      public double q;
-      public TreeNode parent;
-      public TreeNode[] children;
-      public bool done = false;
-
-      public TreeNode(string id, TreeNode parent) {
-        this.ident = id;
-        this.parent = parent;
-      }
-
-      public override string ToString() {
-        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident);
-      }
-    }
-
-
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly IProblem problem;
-    private readonly Random random;
-    private readonly int randomTries;
-    private readonly IBanditPolicy policy;
-
-    private TreeNode lastNode; // the bottom node in one episode
-    private TreeNode rootNode;
-
-    public int treeDepth;
-    public int treeSize;
-    private double bestQuality;
-
-    public MctsQLearningSampler(IProblem problem, int maxLen, Random random, int randomTries, IBanditPolicy policy) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = random;
-      this.randomTries = randomTries;
-      this.policy = policy;
-    }
-
-    public void Run(int maxIterations) {
-      bestQuality = double.MinValue;
-      InitPolicies(problem.Grammar);
-      for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        Debug.Assert(quality >= 0 && quality <= 1.0);
-        DistributeReward(quality);
-
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-
-      // clean up
-      InitPolicies(problem.Grammar); GC.Collect();
-    }
-
-    public void PrintStats() {
-      var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.tries, n.q, bestQuality);
-      while (n.children != null) {
-        Console.WriteLine("{0,-30}", n.ident);
-        double maxVForRow = n.children.Select(ch => ch.q).Max();
-        if (maxVForRow == 0) maxVForRow = 1.0;
-
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          SetColorForChild(ch, maxVForRow);
-          Console.Write("{0,5}", ch.ident);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          SetColorForChild(ch, maxVForRow);
-          Console.Write("{0,5:F2}", ch.q * 10);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          SetColorForChild(ch, maxVForRow);
-          Console.Write("{0,5}", ch.done ? "X" : ch.tries.ToString());
-        }
-        Console.ForegroundColor = ConsoleColor.White;
-        Console.WriteLine();
-        //n.policy.PrintStats();
-        //n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First();
-        n = n.children.OrderByDescending(c => c.tries).First();
-      }
-      Console.WriteLine("---------------------------");
-      //for (int i = 0; i < 20; i++) Console.WriteLine("{0:50}", string.Empty);
-    }
-
-    private void SetColorForChild(TreeNode ch, double maxVForRow) {
-      //if (ch.done) Console.ForegroundColor = ConsoleColor.White;
-      //else
-      Console.ForegroundColor = ConsoleEx.ColorForValue(ch.q / maxVForRow);
-    }
-
-    private void InitPolicies(IGrammar grammar) {
-
-
-      rootNode = new TreeNode(grammar.SentenceSymbol.ToString(), null);
-      treeDepth = 0;
-      treeSize = 0;
-    }
-
-    private Sequence SampleSentence(IGrammar grammar) {
-      lastNode = null;
-      var startPhrase = new Sequence(grammar.SentenceSymbol);
-      //var startPhrase = new Sequence("a*b+c*d+e*f+E");
-
-      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;
-      var curDepth = 0;
-      while (!phrase.IsTerminal) {
-
-        if (n.randomTries < randomTries) {
-          n.randomTries++;
-          treeDepth = Math.Max(treeDepth, curDepth);
-          lastNode = n;
-          return g.CompleteSentenceRandomly(random, phrase, maxLen);
-        } else {
-          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
-          Debug.Assert(maxLenOfReplacement > 0);
-
-          var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-
-          if (n.randomTries == randomTries && n.children == null) {
-            n.children = alts.Select(alt => new TreeNode(alt.ToString(), n)).ToArray(); // create a new node for each alternative
-            treeSize += n.children.Length;
-          }
-          // => select using bandit policy
-          int selectedAltIdx = SelectEpsGreedy(random, n.children);
-          Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
-
-          // replace nt with alt
-          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-          curDepth++;
-
-          n.tries++;
-          var delta = n.children.Select(ch => ch.q).Max() - n.q;
-          var alpha = 1.0 / n.tries;
-          //var alpha = 0.001;
-          n.q = n.q + alpha * delta;
-
-          // prepare for next iteration
-          n = n.children[selectedAltIdx];
-
-        }
-      } // while
-
-      lastNode = n;
-
-
-      // the last node is a leaf node (sentence is done), so we never need to visit this node again
-      n.done = true;
-
-      treeDepth = Math.Max(treeDepth, curDepth);
-      return phrase;
-    }
-
-    private int SelectEpsGreedy(Random random, TreeNode[] children) {
-      if (random.NextDouble() < 0.1) {
-        return SelectRandom(random, children);
-      } else {
-        var bestQ = double.NegativeInfinity;
-        var bestChildIdx = new List<int>();
-        for (int i = 0; i < children.Length; i++) {
-          if (children[i].done) continue;
-          // if (children[i].tries == 0) return i;
-          var q = children[i].q;
-          if (q > bestQ) {
-            bestQ = q;
-            bestChildIdx.Clear();
-            bestChildIdx.Add(i);
-          } else if (q == bestQ) {
-            bestChildIdx.Add(i);
-          }
-        }
-        Debug.Assert(bestChildIdx.Any());
-        return bestChildIdx.SelectRandom(random);
-      }
-    }
-
-    private int SelectRandom(Random random, TreeNode[] children) {
-      return children.Select((ch, i) => Tuple.Create(ch, i)).Where(p => !p.Item1.done).SelectRandom(random).Item2;
-    }
-
-    private void DistributeReward(double reward) {
-      // iterate in reverse order (bottom up)
-      var node = lastNode;
-      node.tries++;
-      // update value for last node
-      var delta = reward - node.q;
-      node.q = node.q + 1.0 / node.tries * delta;
-
-      // update done
-      while (node != null) {
-        if (node.children != null && node.children.All(c => c.done)) {
-          node.done = true;
-        }
-        node = node.parent;
-      }
-
-    }
-
-    private void RaiseSolutionEvaluated(string sentence, double quality) {
-      var handler = SolutionEvaluated;
-      if (handler != null) handler(sentence, quality);
-    }
-    private void RaiseFoundNewBestSolution(string sentence, double quality) {
-      var handler = FoundNewBestSolution;
-      if (handler != null) handler(sentence, quality);
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11805)
+++ 	(revision )
@@ -1,209 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Algorithms.Bandits;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class MctsSampler {
-    private class TreeNode {
-      public string ident;
-      public int randomTries;
-      public IBanditPolicyActionInfo actionInfo;
-      public TreeNode parent;
-      public TreeNode[] children;
-      public bool done = false;
-
-      public TreeNode(string id, TreeNode parent) {
-        this.ident = id;
-        this.parent = parent;
-      }
-
-      public override string ToString() {
-        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, actionInfo.Tries, done, actionInfo);
-      }
-    }
-
-
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly IProblem problem;
-    private readonly Random random;
-    private readonly int randomTries;
-    private readonly IBanditPolicy policy;
-
-    private TreeNode lastNode; // the bottom node in one episode
-    private TreeNode rootNode;
-
-    public int treeDepth;
-    public int treeSize;
-    private double bestQuality;
-
-    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, IBanditPolicy policy) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = random;
-      this.randomTries = randomTries;
-      this.policy = policy;
-    }
-
-    public void Run(int maxIterations) {
-      bestQuality = double.MinValue;
-      InitPolicies(problem.Grammar);
-      for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        Debug.Assert(quality >= 0 && quality <= 1.0);
-        DistributeReward(quality);
-
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-
-      // clean up
-      InitPolicies(problem.Grammar); GC.Collect();
-    }
-
-    public void PrintStats() {
-      var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.actionInfo.Tries, n.actionInfo.Value, bestQuality);
-      while (n.children != null) {
-        Console.WriteLine("{0,-30}", n.ident);
-        double maxVForRow = n.children.Select(ch => ch.actionInfo.Value).Max();
-        if (maxVForRow == 0) maxVForRow = 1.0;
-
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          SetColorForChild(ch, maxVForRow);
-          Console.Write("{0,5}", ch.ident);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          SetColorForChild(ch, maxVForRow);
-          Console.Write("{0,5:F2}", ch.actionInfo.Value * 10);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          SetColorForChild(ch, maxVForRow);
-          Console.Write("{0,5}", ch.done ? "X" : ch.actionInfo.Tries.ToString());
-        }
-        Console.ForegroundColor = ConsoleColor.White;
-        Console.WriteLine();
-        //n.policy.PrintStats();
-        //n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First();
-        n = n.children.Where(ch=>!ch.done).OrderByDescending(c => c.actionInfo.Value).First();
-      }
-      Console.WriteLine("-----------------------");
-    }
-
-    private void SetColorForChild(TreeNode ch, double maxVForRow) {
-      //if (ch.done) Console.ForegroundColor = ConsoleColor.White;
-      //else
-      Console.ForegroundColor = ConsoleEx.ColorForValue(ch.actionInfo.Value / maxVForRow);
-    }
-
-    private void InitPolicies(IGrammar grammar) {
-
-
-      rootNode = new TreeNode(grammar.SentenceSymbol.ToString(), null);
-      rootNode.actionInfo = policy.CreateActionInfo();
-      treeDepth = 0;
-      treeSize = 0;
-    }
-
-    private Sequence SampleSentence(IGrammar grammar) {
-      lastNode = null;
-      var startPhrase = new Sequence(grammar.SentenceSymbol);
-      //var startPhrase = new Sequence("a*b+c*d+e*f+E");
-
-      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;
-      var curDepth = 0;
-      while (!phrase.IsTerminal) {
-
-        if (n.randomTries < randomTries) {
-          n.randomTries++;
-          treeDepth = Math.Max(treeDepth, curDepth);
-          lastNode = n;
-          return g.CompleteSentenceRandomly(random, phrase, maxLen);
-        } else {
-          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
-          Debug.Assert(maxLenOfReplacement > 0);
-
-          var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-
-          if (n.randomTries == randomTries && n.children == null) {
-            n.children = alts.Select(alt => new TreeNode(alt.ToString(), n)).ToArray(); // create a new node for each alternative
-            foreach (var ch in n.children) ch.actionInfo = policy.CreateActionInfo();
-            treeSize += n.children.Length;
-          }
-          // => select using bandit policy
-          int selectedAltIdx = policy.SelectAction(random, n.children.Select(c => c.actionInfo));
-          Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
-
-          // replace nt with alt
-          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-          curDepth++;
-
-          // prepare for next iteration
-          n = n.children[selectedAltIdx];
-        }
-      } // while
-
-      lastNode = n;
-
-
-      // the last node is a leaf node (sentence is done), so we never need to visit this node again
-      n.done = true;
-
-      treeDepth = Math.Max(treeDepth, curDepth);
-      return phrase;
-    }
-
-    private void DistributeReward(double reward) {
-      // iterate in reverse order (bottom up)
-
-      var node = lastNode;
-      while (node != null) {
-        if (node.done) node.actionInfo.Disable(reward);
-        if (node.children != null && node.children.All(c => c.done)) {
-          node.done = true;
-          var bestActionValue = node.children.Select(c => c.actionInfo.Value).Max();
-          node.actionInfo.Disable(bestActionValue);
-        }
-        if (!node.done) {
-          node.actionInfo.UpdateReward(reward);
-        }
-        node = node.parent;
-      }
-    }
-
-    private void RaiseSolutionEvaluated(string sentence, double quality) {
-      var handler = SolutionEvaluated;
-      if (handler != null) handler(sentence, quality);
-    }
-    private void RaiseFoundNewBestSolution(string sentence, double quality) {
-      var handler = FoundNewBestSolution;
-      if (handler != null) handler(sentence, quality);
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs	(revision 11806)
@@ -77,4 +77,5 @@
           tries++;
           var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+          if (double.IsNaN(quality)) quality = 0.0;
           Debug.Assert(quality >= 0 && quality <= 1.0);
           DistributeReward(quality);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/TemporalDifferenceTreeSearchSampler.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/TemporalDifferenceTreeSearchSampler.cs	(revision 11805)
+++ 	(revision )
@@ -1,231 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Diagnostics;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Algorithms.Bandits;
-using HeuristicLab.Common;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  // SARSA (fig. 6.9 in Sutton & Barto)
-  public class TemporalDifferenceTreeSearchSampler {
-    private class TreeNode {
-      public string ident;
-      public int randomTries;
-      public double q;
-      public int tries;
-      public TreeNode[] children;
-      public bool done = false;
-
-      public TreeNode(string id) {
-        this.ident = id;
-      }
-
-      public override string ToString() {
-        return string.Format("Node({0} tries: {1}, done: {2})", ident, tries, done);
-      }
-    }
-
-
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly IProblem problem;
-    private readonly Random random;
-    private readonly int randomTries;
-
-    private List<TreeNode> updateChain;
-    private TreeNode rootNode;
-
-    public int treeDepth;
-    public int treeSize;
-    private double bestQuality;
-
-
-    public TemporalDifferenceTreeSearchSampler(IProblem problem, int maxLen, Random random, int randomTries) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = random;
-      this.randomTries = randomTries;
-    }
-
-    public void Run(int maxIterations) {
-      InitPolicies(problem.Grammar);
-      for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        Debug.Assert(quality >= 0 && quality <= 1.0);
-        DistributeReward(quality);
-
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-
-      // clean up
-      InitPolicies(problem.Grammar); GC.Collect();
-    }
-
-    public void PrintStats() {
-      var n = rootNode;
-      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.tries, n.q, bestQuality);
-      while (n.children != null) {
-        Console.WriteLine("{0,-30}", n.ident);
-        double maxVForRow = n.children.Select(ch => ch.q).Max();
-        if (maxVForRow == 0) maxVForRow = 1.0;
-
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          Console.ForegroundColor = ConsoleEx.ColorForValue(ch.q / maxVForRow);
-          Console.Write("{0,5}", ch.ident);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          Console.ForegroundColor = ConsoleEx.ColorForValue(ch.q / maxVForRow);
-          Console.Write("{0,5:F2}", ch.q * 10);
-        }
-        Console.WriteLine();
-        for (int i = 0; i < n.children.Length; i++) {
-          var ch = n.children[i];
-          Console.ForegroundColor = ConsoleEx.ColorForValue(ch.q / maxVForRow);
-          Console.Write("{0,5}", ch.done ? "X" : ch.tries.ToString());
-        }
-        Console.ForegroundColor = ConsoleColor.White;
-        Console.WriteLine();
-        //n.policy.PrintStats();
-        n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.q).First();
-      }
-    }
-
-    private void InitPolicies(IGrammar grammar) {
-      this.updateChain = new List<TreeNode>();
-
-      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
-      treeDepth = 0;
-      treeSize = 0;
-    }
-
-    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;
-      var curDepth = 0;
-      while (!phrase.IsTerminal) {
-        updateChain.Add(n);
-
-        if (n.randomTries < randomTries) {
-          n.randomTries++;
-          treeDepth = Math.Max(treeDepth, curDepth);
-          return g.CompleteSentenceRandomly(random, phrase, maxLen);
-        } else {
-          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
-          Debug.Assert(maxLenOfReplacement > 0);
-
-          var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-
-          if (n.randomTries == randomTries && n.children == null) {
-            n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
-            treeSize += n.children.Length;
-          }
-          // => select using bandit policy
-          int selectedAltIdx = SelectEpsGreedy(random, n.children);
-          Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
-
-          // replace nt with alt
-          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-          curDepth++;
-
-          // prepare for next iteration
-          n = n.children[selectedAltIdx];
-        }
-      } // while
-
-      updateChain.Add(n);
-
-
-      // the last node is a leaf node (sentence is done), so we never need to visit this node again
-      n.done = true;
-
-      treeDepth = Math.Max(treeDepth, curDepth);
-      return phrase;
-    }
-
-
-    // eps-greedy
-    private int SelectEpsGreedy(Random random, TreeNode[] children) {
-      if (random.NextDouble() < 0.1) {
-
-        return children.Select((ch, i) => Tuple.Create(ch, i)).Where(p => !p.Item1.done).SelectRandom(random).Item2;
-      } else {
-        var bestQ = double.NegativeInfinity;
-        var bestChildIdx = new List<int>();
-        for (int i = 0; i < children.Length; i++) {
-          if (children[i].done) continue;
-          // if (children[i].tries == 0) return i;
-          var q = children[i].q;
-          if (q > bestQ) {
-            bestQ = q;
-            bestChildIdx.Clear();
-            bestChildIdx.Add(i);
-          } else if (q == bestQ) {
-            bestChildIdx.Add(i);
-          }
-        }
-        Debug.Assert(bestChildIdx.Any());
-        return bestChildIdx.SelectRandom(random);
-      }
-    }
-
-    private void DistributeReward(double reward) {
-      updateChain.Reverse();
-      foreach (var node in updateChain) {
-        if (node.children != null && node.children.All(c => c.done)) {
-          node.done = true;
-        }
-      }
-      updateChain.Reverse();
-
-      //const double alpha = 0.1;
-      const double gamma = 1;
-      double alpha;
-      foreach (var p in updateChain.Zip(updateChain.Skip(1), Tuple.Create)) {
-        var parent = p.Item1;
-        var child = p.Item2;
-        parent.tries++;
-        alpha = 1.0 / parent.tries;
-        //alpha = 0.01;
-        parent.q = parent.q + alpha * (0 + gamma * child.q - parent.q);
-      }
-      // reward is recieved only for the last action
-      var n = updateChain.Last();
-      n.tries++;
-      alpha = 1.0 / n.tries;
-      //alpha = 0.1;
-      n.q = n.q + alpha * reward;
-    }
-
-    private void RaiseSolutionEvaluated(string sentence, double quality) {
-      var handler = SolutionEvaluated;
-      if (handler != null) handler(sentence, quality);
-    }
-    private void RaiseFoundNewBestSolution(string sentence, double quality) {
-      var handler = FoundNewBestSolution;
-      if (handler != null) handler(sentence, quality);
-    }
-  }
-}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ConsoleEx.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ConsoleEx.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ConsoleEx.cs	(revision 11806)
@@ -49,10 +49,10 @@
       double startGreen = -1.41;
       double endGreen = 1.41;
-      
+
       double startBlue = -3;
       double endBlue = 1;
-      
+
       double startAlpha = 0;
-      double endAlpha =0;
+      double endAlpha = 0;
 
       // fire
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 11806)
@@ -15,5 +15,5 @@
     private const string grammarString = @"
         G(E):
-        E -> V | V+E | V-E | V*E | (E)
+        E -> V | V+E | V-E | V*E | V/E | (E)
         V -> <variables>
         ";
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11806)
@@ -9,5 +9,5 @@
     IGrammar Grammar { get; }
     double Evaluate(string sentence);
-    string CanonicalRepresentation(string terminalPhrase);
+    string CanonicalRepresentation(string terminalPhrase); // canonical state must use correct syntax (must be a valid input for evaluate)
   }
 }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 11806)
@@ -115,5 +115,5 @@
     public string CanonicalRepresentation(string terminalPhrase) {
       if (phrasesAsSets) {
-        var phrases = new List<string>();
+        var sb = new StringBuilder();
         var numPhrases = terminalPhrase.Length / phraseLen;
         for (int phraseIdx = 0; phraseIdx < numPhrases; phraseIdx++) {
@@ -121,12 +121,12 @@
           var phrase = terminalPhrase.Substring(sentenceIdx, phraseLen);
           phrase = CanonicalPhrase(phrase);
-          phrases.Add(phrase);
+          sb.Append(phrase);
         }
 
         var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
         remainder = CanonicalPhrase(remainder);
-        phrases.Add(remainder);
+        sb.Append(remainder);
 
-        return string.Join("", phrases);
+        return sb.ToString();
       } else
         return terminalPhrase;
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 11806)
@@ -32,5 +32,5 @@
       // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
       Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      return regex.Matches(sentence.ToString()).Count;
+      return regex.Matches(sentence).Count;
     }
     public string CanonicalRepresentation(string terminalPhrase) {
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 11806)
@@ -111,5 +111,4 @@
         canonicalPhrase = sb.ToString();
       } while (canonicalPhrase != oldPhrase);
-      sb.Append(terminalPhrase.Length - canonicalPhrase.Length);
       return sb.ToString();
     }
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 11806)
@@ -92,5 +92,4 @@
 
         sb.Append(CanonicalTerm(terms[terms.Length - 1]));
-        sb.Append(phrase.Length - sb.Length);
         canonicalPhrase = sb.ToString();
         canonicalPhraseCache.Add(phrase, canonicalPhrase);
@@ -109,7 +108,11 @@
         var sb = new StringBuilder(chars.Length);
         // we want to have the up-case characters last
-        for (int i = chars.Length - 1; i >= 0; i--) {
-          if (chars[i] != '*') sb.Append(chars[i]);
+        for (int i = chars.Length - 1; i > 0; i--) {
+          if (chars[i] != '*') {
+            sb.Append(chars[i]);
+            if (chars[i - 1] != '*') sb.Append('*');
+          }
         }
+        if (chars[0] != '*') sb.Append(chars[0]); // last term
         canonicalTerm = sb.ToString();
         canonicalTermDictionary.Add(term, canonicalTerm);
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11805)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11806)
@@ -24,6 +24,6 @@
       CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
 
-      //RunDemo();
-      RunGridTest();
+      RunDemo();
+      //RunGridTest();
     }
 
@@ -61,4 +61,12 @@
          () => new UCTPolicy( 5),
          () => new UCTPolicy( 10),
+         () => new ModifiedUCTPolicy(0.01),
+         () => new ModifiedUCTPolicy(0.05),
+         () => new ModifiedUCTPolicy(0.1),
+         () => new ModifiedUCTPolicy(0.5),
+         () => new ModifiedUCTPolicy(1),
+         () => new ModifiedUCTPolicy(2),
+         () => new ModifiedUCTPolicy( 5),
+         () => new ModifiedUCTPolicy( 10),
          () => new UCB1Policy(), 
          () => new UCB1TunedPolicy(), 
@@ -161,5 +169,4 @@
 
     private static void RunDemo() {
-      // TODO: move problem instances into a separate folder
       // TODO: implement bridge to HL-GP 
       // TODO: unify MCTS, TD and ContextMCTS Solvers (stateInfos)
@@ -170,5 +177,4 @@
       // TODO: warum funktioniert die alte Implementierung von GaussianThompson besser fÃŒr SantaFe als neue? Siehe Vergleich: alte vs. neue implementierung GaussianThompsonSampling
       // TODO: why does GaussianThompsonSampling work so well with MCTS for the artificial ant problem?
-      // TODO: wie kann ich sampler noch vergleichen bzw. was kann man messen um die qualitÃ€t des samplers abzuschÃ€tzen (bis auf qualitÃ€t und iterationen bis zur besten lÃ¶sung) => ziel schnellere iterationen zu gutem ergebnis
       // TODO: research thompson sampling for max bandit?
       // TODO: ausfÃŒhrlicher test von strategien fÃŒr numCorrectPhrases-armed max bandit
@@ -192,5 +198,5 @@
 
 
-      var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
+      //var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
       //var phraseLen = 3;
       //var numPhrases = 5;
@@ -218,5 +224,5 @@
       //var problem = new SymbolicRegressionPoly10Problem();
 
-      //var problem = new SantaFeAntProblem();
+      var problem = new SantaFeAntProblem();
       //var problem = new SymbolicRegressionProblem("Tower"); 
       //var problem = new PalindromeProblem();
@@ -227,6 +233,8 @@
       //var alg = new MctsSampler(problem, 23, random, 0, new BoltzmannExplorationPolicy(100));
       //var alg = new MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
-      var alg = new SequentialSearch(problem, 30, random, 0,
-        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.1), true));
+      //var alg = new SequentialSearch(problem, 23, random, 0,
+      //  new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new ModifiedUCTPolicy(0.1), true));
+      var alg = new SequentialSearch(problem, 17, random, 0,
+        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericTDPolicy(problem, true));
       //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
       //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
@@ -248,5 +256,5 @@
         globalStatistics.AddSentence(sentence, quality);
         if (iterations % 1000 == 0) {
-          if (iterations % 1000 == 0) Console.Clear();
+          if (iterations % 10000 == 0) Console.Clear();
           Console.SetCursorPosition(0, 0);
           alg.PrintStats();
