Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/BoltzmanExplorationPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/BoltzmanExplorationPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/BoltzmanExplorationPolicy.cs	(revision 11770)
@@ -0,0 +1,57 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Configuration;
+using System.Linq;
+using System.Security.Policy;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class BoltzmannExplorationPolicy : GrammarPolicy {
+
+    private readonly HashSet<string> done;
+    private readonly double beta;
+
+    public BoltzmannExplorationPolicy(IProblem problem, bool useCanonicalRepresentation = false, int beta = 100)
+      : base(problem, useCanonicalRepresentation) {
+      this.beta = beta;
+      this.done = new HashSet<string>();
+    }
+
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // only select states that are not yet done
+      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
+      if (!afterStates.Any()) {
+        // fail because all follow states have already been visited => also disable the current state
+        done.Add(CanonicalState(curState.ToString()));
+        selectedState = null;
+        return false;
+      }
+      // try each state at least once
+      if (afterStates.Any(s => GetTries(s) == 0)) {
+        selectedState = afterStates.First(s => GetTries(s) == 0);
+        return true;
+      }
+
+      var w = from state in afterStates
+              select Math.Exp(beta * AvgReward(state));
+
+      selectedState = afterStates.SampleProportional(random, w).First();
+      return true;
+    }
+
+    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      base.UpdateReward(stateTrajectory, reward);
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
+    }
+
+    public void Reset() {
+      base.Reset();
+      done.Clear();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/EpsGreedyPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/EpsGreedyPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/EpsGreedyPolicy.cs	(revision 11770)
@@ -0,0 +1,66 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Configuration;
+using System.Linq;
+using System.Security.Policy;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class EpsGreedyPolicy : GrammarPolicy {
+
+    private readonly HashSet<string> done;
+    private readonly double eps;
+    private readonly IGrammarPolicy greedyPolicy;
+    private readonly IGrammarPolicy randomPolicy;
+
+    public EpsGreedyPolicy(IProblem problem, bool useCanonicalRepresentation = false, double eps = 0.1)
+      : base(problem, useCanonicalRepresentation) {
+      this.eps = eps;
+      this.done = new HashSet<string>();
+      this.greedyPolicy = new GreedyPolicy(problem, useCanonicalRepresentation);
+      this.randomPolicy = new RandomPolicy(problem, useCanonicalRepresentation);
+    }
+
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // only select states that are not yet done
+      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
+      if (!afterStates.Any()) {
+        // fail because all follow states have already been visited => also disable the current state
+        done.Add(CanonicalState(curState.ToString()));
+        selectedState = null;
+        return false;
+      }
+
+      if (random.NextDouble() > eps) {
+        return greedyPolicy.TrySelect(random, curState, afterStates, out selectedState);
+      } else {
+        return randomPolicy.TrySelect(random, curState, afterStates, out selectedState);
+      }
+    }
+
+    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      base.UpdateReward(stateTrajectory, reward);
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
+
+      // forward
+      greedyPolicy.UpdateReward(stateTrajectory, reward);
+      randomPolicy.UpdateReward(stateTrajectory, reward); // is ignored but for completeness
+    }
+
+    public override void Reset() {
+      base.Reset();
+      done.Clear();
+      greedyPolicy.Reset();
+      randomPolicy.Reset();
+    }
+
+    public double GetValue(ReadonlySequence state) {
+      return greedyPolicy.GetValue(state);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs	(revision 11770)
@@ -0,0 +1,88 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+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;
+    private readonly IProblem problem;
+    private readonly IBanditPolicy banditPolicy;
+    private readonly HashSet<string> done;
+
+    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
+      this.useCanonicalState = useCanonicalState;
+      this.problem = problem;
+      this.banditPolicy = banditPolicy;
+      this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
+      this.done = new HashSet<string>();
+    }
+
+    public bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates,
+      out ReadonlySequence selectedState) {
+      // only select states that are not yet done
+      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
+      if (!afterStates.Any()) {
+        // 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)
+        throw new NotImplementedException();
+        //var curStateCanonical = CanonicalState(curState.ToString());
+        //if (curState.ToString().Length == curStateCanonical.Length)
+          done.Add(CanonicalState(curState.ToString()));
+        selectedState = null;
+        return false;
+      }
+
+
+      var selectedIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
+      selectedState = afterStates.ElementAt(selectedIdx);
+      return true;
+    }
+
+    private IBanditPolicyActionInfo GetStateInfo(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      IBanditPolicyActionInfo info;
+      if (!stateInfo.TryGetValue(s, out info)) {
+        info = banditPolicy.CreateActionInfo();
+        stateInfo[s] = info;
+      }
+      return info;
+    }
+
+    public virtual void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
+
+      foreach (var state in stateTrajectory) {
+        GetStateInfo(state).UpdateReward(reward);
+      }
+    }
+
+    public virtual void Reset() {
+      stateInfo.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
+      else return 0;
+    }
+
+    public double GetValue(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      else return 0.0; // TODO: check alternatives
+    }
+
+    protected string CanonicalState(string state) {
+      if (useCanonicalState) return problem.CanonicalRepresentation(state);
+      else return state;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GrammarPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GrammarPolicy.cs	(revision 11770)
@@ -0,0 +1,76 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  // stores: tries, avg reward and max reward for each state
+  public abstract class GrammarPolicy : IGrammarPolicy {
+    protected Dictionary<string, double> avgReward;
+    protected Dictionary<string, int> tries;
+    protected Dictionary<string, double> maxReward;
+    private readonly bool useCanonicalState;
+    private readonly IProblem problem;
+
+    public GrammarPolicy(IProblem problem, bool useCanonicalState = false) {
+      this.useCanonicalState = useCanonicalState;
+      this.problem = problem;
+      this.tries = new Dictionary<string, int>();
+      this.avgReward = new Dictionary<string, double>();
+      this.maxReward = new Dictionary<string, double>();
+    }
+
+    public abstract bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState);
+
+    public virtual void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      foreach (var state in stateTrajectory) {
+        var s = CanonicalState(state.ToString());
+
+        if (!tries.ContainsKey(s)) tries.Add(s, 0);
+        if (!avgReward.ContainsKey(s)) avgReward.Add(s, 0);
+        if (!maxReward.ContainsKey(s)) maxReward.Add(s, 0);
+
+        tries[s]++;
+        double alpha = 1.0 / tries[s];
+        avgReward[s] += alpha * (reward - avgReward[s]);
+        maxReward[s] = Math.Max(maxReward[s], reward);
+      }
+    }
+
+    public virtual void Reset() {
+      avgReward.Clear();
+      maxReward.Clear();
+      tries.Clear();
+    }
+
+    public double AvgReward(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      if (avgReward.ContainsKey(s)) return avgReward[s];
+      else return 0.0;
+    }
+
+    public double MaxReward(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      if (maxReward.ContainsKey(s)) return maxReward[s];
+      else return 0.0;
+    }
+
+    public virtual int GetTries(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      if (tries.ContainsKey(s)) return tries[s];
+      else return 0;
+    }
+
+    public virtual double GetValue(ReadonlySequence state) {
+      return AvgReward(state);
+    }
+
+    protected string CanonicalState(string state) {
+      if (useCanonicalState) return problem.CanonicalRepresentation(state);
+      else return state;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GreedyPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GreedyPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GreedyPolicy.cs	(revision 11770)
@@ -0,0 +1,44 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Eventing.Reader;
+using System.Linq;
+using System.Runtime.InteropServices;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class GreedyPolicy : GrammarPolicy {
+    private readonly IProblem problem;
+
+    public GreedyPolicy(IProblem problem, bool useCanonicalRepresentation)
+      : base(problem, useCanonicalRepresentation) {
+    }
+
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // always returns the afterstate with the highest value
+      double maxV = V(afterStates.First());
+      var bestStates = new List<ReadonlySequence>();
+      bestStates.Add(afterStates.First());
+      foreach (var state in afterStates.Skip(1)) {
+        if (maxV < V(state)) {
+          maxV = V(state);
+          bestStates.Clear();
+          bestStates.Add(state);
+        } else if (maxV == V(state)) {
+          bestStates.Add(state);
+        }
+      }
+      // break ties randomly
+      // selectedState = bestStates.SelectRandom(random);
+      // break ties using first
+      selectedState = bestStates.First();
+      return true;
+    }
+
+    private double V(ReadonlySequence state) {
+      return base.AvgReward(state);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/IGrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/IGrammarPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/IGrammarPolicy.cs	(revision 11770)
@@ -0,0 +1,12 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public interface IGrammarPolicy : IPolicy<ReadonlySequence> {
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomNoResamplingPolicy.cs	(revision 11770)
@@ -1,43 +1,47 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Configuration;
 using System.Linq;
+using System.Security.Policy;
 using System.Text;
-using System.Threading.Tasks;
 using HeuristicLab.Common;
 using HeuristicLab.Problems.GrammaticalOptimization;
 
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class RandomNoResamplingPolicy : IGrammarPolicy {
+  public class RandomNoResamplingPolicy : GrammarPolicy {
 
-    private readonly Dictionary<ReadonlySequence, bool> done;
-    private readonly Dictionary<Tuple<ReadonlySequence, ReadonlySequence>, ReadonlySequence> nextState;
+    private readonly HashSet<string> done;
 
-
-    public RandomNoResamplingPolicy() {
-      this.done = new Dictionary<ReadonlySequence, bool>();
+    public RandomNoResamplingPolicy(IProblem problem, bool useCanonicalRepresentation)
+      : base(problem, useCanonicalRepresentation) {
+      this.done = new HashSet<string>();
     }
 
-    public ReadonlySequence SelectAction(Random random, ReadonlySequence state, IEnumerable<ReadonlySequence> actions) {
-      var allDone = true;
-      foreach (var a in actions) {
-        var p = Tuple.Create(state, a);
-        allDone &= nextState.ContainsKey(p) && Done(nextState[p]);
-        if (!allDone) break;
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // only select states that are not yet done
+      afterStates = afterStates.Where(a => !done.Contains(a.ToString())).ToArray();
+      if (!afterStates.Any()) {
+        // fail because all follow states have already been visited => also disable the current state
+        done.Add(CanonicalState(curState.ToString()));
+        selectedState = null;
+        return false;
       }
-      if(allDone)
-      return actions
-        .Where(a => !nextState.ContainsKey(Tuple.Create(state, a)) || Done(nextState[Tuple.Create(state, a)]))
-        .SelectRandom(random);
+
+      selectedState = afterStates.SelectRandom(random);
+      return true;
     }
 
-    public void UpdateReward(ReadonlySequence state, ReadonlySequence action, double reward, ReadonlySequence newState) {
-      var key = Tuple.Create(state, action);
-      nextState[key] = newState;
-      if (newState.IsTerminal) done[newState] = true;
-      if 
+    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      base.UpdateReward(stateTrajectory, reward);
+      // ignore rewards but update the set of visited terminal states
+
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
     }
 
-    public bool Done(ReadonlySequence state) {
-      return done.ContainsKey(state);
+    public override void Reset() {
+      base.Reset();
+      done.Clear();
     }
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/RandomPolicy.cs	(revision 11770)
@@ -8,15 +8,13 @@
 
 namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
-  public class RandomPolicy : IGrammarPolicy {
-    public ReadonlySequence SelectAction(Random random, ReadonlySequence state, IEnumerable<ReadonlySequence> actions) {
-      return actions.SelectRandom(random);
+  public class RandomPolicy : GrammarPolicy {
+    public RandomPolicy(IProblem problem, bool useCanonicalRepresentation)
+      : base(problem, useCanonicalRepresentation) {
     }
 
-    public void UpdateReward(ReadonlySequence state, ReadonlySequence action, double reward, ReadonlySequence newState) {
-      // ignore
-    }
-
-    public bool Done(ReadonlySequence state) {
-      return false;
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // never fail => allows re-visits of terminal states
+      selectedState = afterStates.SelectRandom(random);
+      return true;
     }
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs	(revision 11770)
@@ -0,0 +1,92 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Configuration;
+using System.Linq;
+using System.Security.Policy;
+using System.Text;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class TDPolicy : GrammarPolicy {
+
+    private readonly HashSet<string> done;
+    private readonly Dictionary<string, double> v;
+    private EpsGreedyPolicy epsGreedy;
+
+    public TDPolicy(IProblem problem, bool useCanonicalRepresentation = false)
+      : base(problem, useCanonicalRepresentation) {
+      this.done = new HashSet<string>();
+      this.v = new Dictionary<string, double>();
+      this.epsGreedy = new EpsGreedyPolicy(problem, useCanonicalRepresentation, 0.1);
+    }
+
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // only select states that are not yet done
+      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
+      if (!afterStates.Any()) {
+        // fail because all follow states have already been visited => also disable the current state
+        done.Add(CanonicalState(curState.ToString()));
+        selectedState = null;
+        return false;
+      }
+
+      //return epsGreedy.TrySelect(random, curState, afterStates, out selectedState);
+
+      var bestQ = double.NegativeInfinity;
+      selectedState = null;
+      foreach (var state in afterStates) {
+        // try each state at least once
+        if (GetTries(state) == 0) {
+          selectedState = state;
+          return true;
+        }
+        var q = V(state);
+        if (q > bestQ) {
+          bestQ = q;
+          selectedState = state;
+        }
+      }
+
+      return true;
+    }
+
+    private double V(ReadonlySequence state) {
+      var s = CanonicalState(state.ToString());
+      if (v.ContainsKey(s)) return v[s];
+      else return 0.0;
+    }
+
+    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      base.UpdateReward(stateTrajectory, reward);
+      epsGreedy.UpdateReward(stateTrajectory, reward);
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
+
+      v[CanonicalState(lastState.ToString())] = V(lastState) + 1.0 / GetTries(lastState) * (reward - V(lastState));
+
+      foreach (var p in stateTrajectory.Zip(stateTrajectory.Skip(1), Tuple.Create).Reverse()) {
+        var cur = p.Item1;
+        var next = p.Item2;
+
+        v[CanonicalState(cur.ToString())] = V(cur) + 1.0 / GetTries(cur) * (V(next) - V(cur));
+        //v[CanonicalState(cur.ToString())] = V(cur) + 0.1 * (V(next) - V(cur));
+      }
+
+    }
+
+    public override double GetValue(ReadonlySequence state) {
+      return V(state);
+    }
+
+    public void Reset() {
+      base.Reset();
+      epsGreedy.Reset();
+      v.Clear();
+      done.Clear();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/UCTPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/UCTPolicy.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/UCTPolicy.cs	(revision 11770)
@@ -0,0 +1,64 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Configuration;
+using System.Linq;
+using System.Security.Policy;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public class UCTPolicy : GrammarPolicy {
+
+    private readonly HashSet<string> done;
+    private readonly double c;
+
+    public UCTPolicy(IProblem problem, bool useCanonicalRepresentation = false, double c = 1.0)
+      : base(problem, useCanonicalRepresentation) {
+      this.c = c;
+      this.done = new HashSet<string>();
+    }
+
+    public override bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates, out ReadonlySequence selectedState) {
+      // only select states that are not yet done
+      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
+      if (!afterStates.Any()) {
+        // fail because all follow states have already been visited => also disable the current state
+        done.Add(CanonicalState(curState.ToString()));
+        selectedState = null;
+        return false;
+      }
+
+      var totalTries = afterStates.Select(GetTries).Sum();
+      var bestQ = double.NegativeInfinity;
+      selectedState = null;
+      foreach (var state in afterStates) {
+        // try each state at least once
+        if (GetTries(state) == 0) {
+          selectedState = state;
+          return true;
+        }
+        var q = AvgReward(state) + 2.0 * c * Math.Sqrt(Math.Log(totalTries) / GetTries(state));
+        if (q > bestQ) {
+          bestQ = q;
+          selectedState = state;
+        }
+      }
+
+      return true;
+    }
+
+    public override void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
+      base.UpdateReward(stateTrajectory, reward);
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));
+    }
+
+    public void Reset() {
+      base.Reset();
+      done.Clear();
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11770)
@@ -66,4 +66,15 @@
     <Compile Include="Bandits\IBandit.cs" />
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
+    <Compile Include="GrammarPolicies\BoltzmanExplorationPolicy.cs" />
+    <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="GrammarPolicies\TDPolicy.cs" />
+    <Compile Include="GrammarPolicies\UCTPolicy.cs" />
+    <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
+    <Compile Include="GrammarPolicies\EpsGreedyPolicy.cs" />
+    <Compile Include="GrammarPolicies\GreedyPolicy.cs" />
+    <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />
+    <Compile Include="GrammarPolicies\RandomNoResamplingPolicy.cs" />
     <Compile Include="GrammarPolicies\RandomPolicy.cs" />
     <Compile Include="IPolicy.cs" />
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IBanditPolicyActionInfo.cs	(revision 11770)
@@ -1,9 +1,3 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.Bandits {
+﻿namespace HeuristicLab.Algorithms.Bandits {
   public interface IBanditPolicyActionInfo {
     bool Disabled { get; }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11770)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Dynamic;
 using System.Linq;
 using System.Text;
@@ -7,13 +8,18 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
-  // this interface represents a policy for reinforcement learning
-  public interface IPolicy<in TState, TAction> {
-    TAction SelectAction(Random random, TState state, IEnumerable<TAction> actions);
-    void UpdateReward(TState state, TAction action, double reward, TState newState); // reward received when after taking action in state and new state
-    bool Done(TState state); // for deterministic MDP with deterministic rewards and goal to find a state with max reward
-  }
+  // this interface represents a policy for episodic reinforcement learning (with afterstates)
+  // here we assume that a reward is only recieved at the end of the episode and the update is done only after an episode is complete
+  // we also assume that the policy can fail to select one of the followStates
+  public interface IPolicy<TState> {
+    bool TrySelect(Random random, TState curState, IEnumerable<TState> afterStates, out TState selectedState); // selectedState \in afterStates
 
-  public interface IGrammarPolicy : IPolicy<ReadonlySequence, ReadonlySequence> {
+    // state-trajectory are the states of the episode, at the end we recieved the reward (only for the terminal state)
+    void UpdateReward(IEnumerable<TState> stateTrajectory, double reward);
 
+    void Reset(); // clears all internal state
+
+    // for introspection
+    double GetValue(TState state); 
+    int GetTries(TState state); 
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11770)
@@ -45,4 +45,5 @@
     <Compile Include="AlternativesSampler.cs" />
     <Compile Include="AlternativesContextSampler.cs" />
+    <Compile Include="SequentialSearch.cs" />
     <Compile Include="TemporalDifferenceTreeSearchSampler.cs" />
     <Compile Include="ExhaustiveRandomFirstSearch.cs" />
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs	(revision 11770)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs	(revision 11770)
@@ -0,0 +1,231 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Resources;
+using System.Runtime.InteropServices;
+using System.Text;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  // a search procedure that uses a policy to generate sentences and updates the policy (online RL)
+  // 1) Start with phrase = sentence symbol of grammar
+  // 2) Repeat
+  //    a) generate derived phrases using left-canonical derivation and grammar rules
+  //    b) keep only the phrases which are allowed (sentence length limit)
+  //    c) if the set of phrases is empty restart with 1)
+  //    d) otherwise use policy to select one of the possible derived phrases as active phrase
+  //       the policy has the option to fail (for instance if all derived phrases are terminal and should not be visited again), in this case we restart at 1
+  //    ... until phrase is terminal
+  // 3) Collect reward and update policy (feedback: state of visited rewards from step 2)
+  public class SequentialSearch {
+
+    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 IGrammarPolicy behaviourPolicy;
+    private readonly IGrammarPolicy greedyPolicy;
+    private int maxSearchDepth;
+
+    private double bestQuality;
+    private string bestPhrase;
+    private int tries;
+    private readonly List<ReadonlySequence> stateChain;
+
+    public SequentialSearch(IProblem problem, int maxLen, Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = random;
+      this.randomTries = randomTries;
+      this.behaviourPolicy = behaviourPolicy;
+      this.greedyPolicy = new GreedyPolicy(problem, false);
+      this.stateChain = new List<ReadonlySequence>();
+      this.cache = new Dictionary<ReadonlySequence, ReadonlySequence[]>();
+    }
+
+    public void Run(int maxIterations) {
+      bestQuality = double.MinValue;
+      //InitPolicies(problem.Grammar);
+      Reset();
+
+      for (int i = 0; !Done() && i < maxIterations; i++) {
+        var phrase = SampleSentence(problem.Grammar);
+        // can fail on the last sentence
+        if (phrase.IsTerminal) {
+          var sentence = phrase.ToString();
+          tries++;
+          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;
+            bestPhrase = sentence;
+            RaiseFoundNewBestSolution(sentence, quality);
+          }
+        }
+      }
+
+      // clean up
+      // Reset(); GC.Collect();
+    }
+
+
+    private ReadonlySequence SampleSentence(IGrammar grammar) {
+      ReadonlySequence phrase;
+      do {
+        stateChain.Clear();
+        phrase = new ReadonlySequence(grammar.SentenceSymbol);
+        //var startPhrase = new Sequence("a*b+c*d+e*f+E");
+      } while (!Done() && !TryCompleteSentence(grammar, ref phrase));
+      return phrase;
+    }
+
+    private bool TryCompleteSentence(IGrammar g, ref ReadonlySequence phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      var curDepth = 0;
+
+      stateChain.Add(phrase);
+      while (!phrase.IsTerminal) {
+
+        //if (n.randomTries < randomTries) {
+        //  n.randomTries++;
+        //  treeDepth = Math.Max(treeDepth, curDepth);
+        //  lastNode = n;
+        //  return g.CompleteSentenceRandomly(random, phrase, maxLen);
+        //} else {
+
+        var newPhrases = GenerateFollowStates(g, phrase);
+
+        // => select using bandit policy
+        // failure means we simply restart
+        if (!behaviourPolicy.TrySelect(random, phrase, newPhrases, out phrase)) {
+          return false;
+        }
+        stateChain.Add(phrase);
+        curDepth++;
+      } // while
+
+      maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
+      return true;
+    }
+
+
+    private readonly Dictionary<ReadonlySequence, ReadonlySequence[]> cache;
+    private IEnumerable<ReadonlySequence> GenerateFollowStates(IGrammar g, ReadonlySequence phrase) {
+      ReadonlySequence[] follow;
+      if (!cache.TryGetValue(phrase, out follow)) {
+        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);
+
+        follow = new ReadonlySequence[alts.Count()];
+        int idx = 0;
+        foreach (var alt in alts) {
+          var newPhrase = new Sequence(phrase); // clone
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+          follow[idx++] = new ReadonlySequence(newPhrase);
+        }
+        cache[phrase] = follow;
+      }
+      return follow;
+    }
+
+    private void DistributeReward(double reward) {
+      behaviourPolicy.UpdateReward(stateChain, reward);
+      greedyPolicy.UpdateReward(stateChain, reward);
+    }
+
+
+    private void Reset() {
+      behaviourPolicy.Reset();
+      greedyPolicy.Reset();
+      maxSearchDepth = 0;
+      bestQuality = 0.0;
+      tries = 0;
+      cache.Clear();
+    }
+
+    public bool Done() {
+      var g = problem.Grammar;
+      var startState = new ReadonlySequence(g.SentenceSymbol);
+      var follow = GenerateFollowStates(g, startState);
+      ReadonlySequence selectedState;
+      return !behaviourPolicy.TrySelect(random, startState, follow, out selectedState);
+    }
+
+    #region introspection
+    public void PrintStats() {
+      Console.WriteLine("depth: {0,5} tries: {1,5} best phrase {2,50} bestQ {3:F3}", maxSearchDepth, tries, bestPhrase, bestQuality);
+
+      // use greedy strategy to generate the currently prefered sentence
+      var phrase = new ReadonlySequence(problem.Grammar.SentenceSymbol);
+      var policy = behaviourPolicy;
+      while (!phrase.IsTerminal) {
+        Console.ForegroundColor = ConsoleColor.White;
+        Console.WriteLine("{0,-30}", phrase);
+        var newPhrases = GenerateFollowStates(problem.Grammar, phrase);
+        if (!newPhrases.Any()) break;
+        var values = newPhrases.Select(p => policy.GetValue(p));
+        var maxValue = values.Max();
+        if (maxValue == 0) maxValue = 1.0;
+
+        // write phrases
+        foreach (var p in newPhrases) {
+          SetColorForValue(policy.GetValue(p) / maxValue);
+          Console.Write(" {0,-4}", p.Subsequence(Math.Max(0, p.Length - 3), Math.Min(3, p.Length)));
+        }
+        Console.WriteLine();
+
+        // write values
+        foreach (var p in newPhrases) {
+          SetColorForValue(policy.GetValue(p) / maxValue);
+          Console.Write(" {0:F2}", policy.GetValue(p) * 10.0);
+        }
+        Console.WriteLine();
+
+        // write tries
+        foreach (var p in newPhrases) {
+          SetColorForValue(policy.GetValue(p) / maxValue);
+          Console.Write(" {0,4}", policy.GetTries(p));
+        }
+        Console.WriteLine();
+        if (!policy.TrySelect(random, phrase, newPhrases, out phrase)) {
+          break;
+        }
+      }
+
+      Console.ForegroundColor = ConsoleColor.White;
+      Console.WriteLine("-------------------");
+    }
+
+    private void SetColorForValue(double v) {
+      Console.ForegroundColor = ConsoleEx.ColorForValue(v);
+    }
+    #endregion
+
+    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 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ConsoleEx.cs	(revision 11770)
@@ -108,5 +108,6 @@
 
     public static ConsoleColor ColorForValue(double d) {
-      Debug.Assert(d >= 0 && d <= 1.0);
+      //Debug.Assert(d >= 0 && d <= 1.0);
+      d = Math.Min(1.0, Math.Max(0.0, d));
       var cIdx = Math.Max(0, (int)Math.Floor(d * 15) - 1);
       return colors[cIdx];
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11770)
@@ -13,6 +13,5 @@
     private const string grammarString = @"
 G(S):
-S -> N | N*S | N+S | !S | (S)
-N -> a | b | c | d
+S -> a | b | c | d | a*S | b*S | c*S | d*S | a+S | b+S | c+S | d+S | !S | (S)
 ";
 
@@ -20,5 +19,5 @@
     private readonly ExpressionInterpreter interpreter = new ExpressionInterpreter();
     public EvenParityProblem() {
-      this.grammar = new Grammar (grammarString);
+      this.grammar = new Grammar(grammarString);
     }
 
@@ -52,4 +51,5 @@
 
     public string CanonicalRepresentation(string terminalPhrase) {
+      throw new NotImplementedException();
       return terminalPhrase;
     }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs	(revision 11770)
@@ -143,4 +143,8 @@
         if (!phrases.Contains(phrase)) phrases.Add(phrase);
       }
+      var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+      remainder = CanonicalPhrase(remainder);
+      if (!phrases.Contains(remainder)) phrases.Add(remainder);
+
       return string.Join("", phrases);
     }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs	(revision 11770)
@@ -26,7 +26,5 @@
     private readonly double correctReward;
     private readonly double incorrectReward;
-    private readonly int _numCorrectPhrases;
     private readonly int sequenceLen;
-    private readonly int alphabetSize;
     private readonly int phraseLen;
     private readonly bool phrasesAsSets;
@@ -40,8 +38,6 @@
       if (correctReward <= incorrectReward) throw new ArgumentException();
 
-      this.alphabetSize = alphabetSize;
       this.sequenceLen = sequenceLen;
       this.phraseLen = phraseLen;
-      this._numCorrectPhrases = numCorrectPhrases;
       this.correctReward = correctReward;
       this.incorrectReward = incorrectReward;
@@ -127,4 +123,8 @@
         }
 
+        var remainder = terminalPhrase.Substring(numPhrases * phraseLen, terminalPhrase.Length - (numPhrases * phraseLen));
+        remainder = CanonicalPhrase(remainder);
+        phrases.Add(remainder);
+
         return string.Join("", phrases);
       } else
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11770)
@@ -11,4 +11,6 @@
 A -> l | r | m | ?(A)(A) | lA | rA | mA 
 ";
+
+
     // original koza grammar
     // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
@@ -103,5 +105,5 @@
       do {
         oldPhrase = terminalPhrase;
-        terminalPhrase.Replace("ll", "rr").Replace("rl", "lr");
+        terminalPhrase = terminalPhrase.Replace("ll", "rr").Replace("rl", "lr").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l");
       } while (terminalPhrase != oldPhrase);
       return terminalPhrase;
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11770)
@@ -2,4 +2,5 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Net;
 using System.Security;
 using System.Security.AccessControl;
@@ -72,14 +73,20 @@
 
     // right now only + and * is supported
+    private Dictionary<string, string> cache = new Dictionary<string, string>();
     public string CanonicalRepresentation(string phrase) {
-      var terms = phrase.Split('+').Select(t => t.Replace("*", ""));
-      var terminalTerms = terms.Where(t => t.All(ch => grammar.IsTerminal(ch)));
-      var nonTerminalTerms = terms.Where(t => t.Any(ch => grammar.IsNonTerminal(ch)));
+      string res;
+      if (!cache.TryGetValue(phrase, out res)) {
+        var terms = phrase.Split('+').Select(t => t.Replace("*", ""));
+        var terminalTerms = terms.Where(t => t.All(ch => grammar.IsTerminal(ch)));
+        var nonTerminalTerms = terms.Where(t => t.Any(ch => grammar.IsNonTerminal(ch)));
 
-      return string.Join("+", terminalTerms.Select(term => CanonicalTerm(term)).OrderBy(term => term).Concat(nonTerminalTerms.Select(term => CanonicalTerm(term))));
+        res = string.Join("+", terminalTerms.Select(term => CanonicalTerm(term)).OrderBy(term => term).Concat(nonTerminalTerms.Select(term => CanonicalTerm(term))));
+        cache[phrase] = res;
+      }
+      return res;
     }
 
     private string CanonicalTerm(string term) {
-      return string.Join("", term.OrderByDescending(ch => (byte)ch));
+      return string.Join("", term.OrderByDescending(ch => (byte)ch)); // we want to have the up-case characters last
     }
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11769)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11770)
@@ -137,4 +137,7 @@
 
     private static void RunDemo() {
+      // TODO: move problem instances into a separate folder
+      // TODO: improve performance of SequentialSearch (memory allocations related to sequences)
+      // TODO: implement bridge to HL-GP 
       // TODO: unify MCTS, TD and ContextMCTS Solvers (stateInfos)
       // TODO: test with eps-greedy using max instead of average as value (seems to work well for symb-reg! explore further!)
@@ -161,6 +164,5 @@
       int iterations = 0;
       var sw = new Stopwatch();
-      double bestQuality = 0;
-      string bestSentence = "";
+
       var globalStatistics = new SentenceSetStatistics();
       var random = new Random();
@@ -168,15 +170,18 @@
       //var phraseLen = 3;
       //var numPhrases = 5;
-      //var problem = new RoyalPhraseSequenceProblem(random, 10, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: true);
-
-      //var phraseLen = 4;
-      //var numPhrases = 5;
-      //var problem = new FindPhrasesProblem(random, 15, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 500, correctReward: 1.0, decoyReward: 0.2, phrasesAsSets: true);
-
-      var problem = new SymbolicRegressionPoly10Problem();   // good results e.g. 10 randomtries and EpsGreedyPolicy(0.2, (aInfo)=>aInfo.MaxReward)
+      //var problem = new RoyalPhraseSequenceProblem(random, 15, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: true);
+
+      // var phraseLen = 2;
+      // var numPhrases = 5;
+      // var problem = new FindPhrasesProblem(random, 15, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 0, correctReward: 1.0, decoyReward: 0.0, phrasesAsSets: true);
+
+      //var problem = new SymbolicRegressionPoly10Problem();   // good results e.g. 10 randomtries and EpsGreedyPolicy(0.2, (aInfo)=>aInfo.MaxReward)
       // Ant
       // good results e.g. with       var alg = new MctsSampler(problem, 17, random, 1, (rand, numActions) => new ThresholdAscentPolicy(numActions, 500, 0.01));
       // GaussianModelWithUnknownVariance (and Q= 0.99-quantil) also works well for Ant
-      //var problem = new SantaFeAntProblem();
+      // very good results with:       var alg = new SequentialSearch(problem, 17, random, 0, 
+      // new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new UCB1TunedPolicy(), true));
+
+      var problem = new SantaFeAntProblem();
       //var problem = new SymbolicRegressionProblem("Tower"); 
       //var problem = new PalindromeProblem();
@@ -186,5 +191,7 @@
       // symbreg length = 11 q = 0.824522210419616
       //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 MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
+      var alg = new SequentialSearch(problem, 10, random, 0, 
+        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new GaussianThompsonSamplingPolicy(true), true));
       //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
       //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
@@ -199,6 +206,4 @@
 
       alg.FoundNewBestSolution += (sentence, quality) => {
-        bestQuality = quality;
-        bestSentence = sentence;
         //Console.WriteLine("{0,4} {1,7} {2}", alg.treeDepth, alg.treeSize, globalStatistics);
         //Console.ReadLine();
@@ -208,5 +213,5 @@
         globalStatistics.AddSentence(sentence, quality);
         if (iterations % 100 == 0) {
-          //if (iterations % 1000 == 0) Console.Clear();
+          if (iterations % 1000 == 0) Console.Clear();
           Console.SetCursorPosition(0, 0);
           alg.PrintStats();
@@ -226,5 +231,7 @@
       sw.Stop();
 
-      Console.WriteLine("{0,10} Best soultion: {1,10:F5} {2}", iterations, bestQuality, bestSentence);
+      Console.Clear();
+      alg.PrintStats();
+      Console.WriteLine(globalStatistics);
       Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
         sw.Elapsed.TotalSeconds,
