Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11850)
@@ -21,4 +21,6 @@
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.Bandits", "HeuristicLab.Problems.Bandits\HeuristicLab.Problems.Bandits.csproj", "{E8138227-0C64-4E85-B676-21D3B97F254F}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Test", "Test\Test.csproj", "{8B4C199E-C08B-479E-9B82-6AE5B113459E}"
 EndProject
 Global
@@ -68,4 +70,8 @@
 		{E8138227-0C64-4E85-B676-21D3B97F254F}.Release|Any CPU.ActiveCfg = Release|Any CPU
 		{E8138227-0C64-4E85-B676-21D3B97F254F}.Release|Any CPU.Build.0 = Release|Any CPU
+		{8B4C199E-C08B-479E-9B82-6AE5B113459E}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{8B4C199E-C08B-479E-9B82-6AE5B113459E}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{8B4C199E-C08B-479E-9B82-6AE5B113459E}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{8B4C199E-C08B-479E-9B82-6AE5B113459E}.Release|Any CPU.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11850)
@@ -42,16 +42,4 @@
     <Compile Include="ActionInfos\MeanAndVariancePolicyActionInfo.cs" />
     <Compile Include="ActionInfos\ModelPolicyActionInfo.cs" />
-    <Compile Include="GrammarPolicies\GenericFunctionApproximationGrammarPolicy.cs" />
-    <Compile Include="GrammarPolicies\GenericContextualGrammarPolicy.cs" />
-    <Compile Include="GrammarPolicies\GenericTDPolicy.cs" />
-    <Compile Include="GrammarPolicies\GenericGrammarPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="GrammarPolicies\RandomPolicy.cs">
-      <SubType>Code</SubType>
-    </Compile>
-    <Compile Include="GrammarPolicies\GrammarPolicy.cs" />
-    <Compile Include="GrammarPolicies\IGrammarPolicy.cs" />
-    <Compile Include="IPolicy.cs" />
     <Compile Include="IBanditPolicy.cs" />
     <Compile Include="IBanditPolicyActionInfo.cs" />
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11849)
+++ 	(revision )
@@ -1,25 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Dynamic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.Bandits {
-  // 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<in TState> {
-    bool TrySelect(Random random, TState curState, IEnumerable<TState> afterStates, out int selectedStateIdx); // selectedState \in afterStates
-
-    // 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: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11849)
+++ 	(revision )
@@ -1,118 +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 AlternativesContextSampler {
-    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 contextLen;
-    private readonly IBanditPolicy policy;
-
-    public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, IBanditPolicy policy) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = random;
-      this.contextLen = contextLen;
-      this.policy = policy;
-    }
-
-    public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
-      InitPolicies(problem.Grammar);
-      for (int i = 0; i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        DistributeReward(quality);
-
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-    }
-
-
-    private Dictionary<string, IBanditPolicyActionInfo[]> contextActionInfos;
-    private List<Tuple<string, int>> updateChain;
-
-    private void InitPolicies(IGrammar grammar) {
-      this.contextActionInfos = new Dictionary<string, IBanditPolicyActionInfo[]>();
-      this.updateChain = new List<Tuple<string, int>>();
-    }
-
-    private Sequence SampleSentence(IGrammar grammar) {
-      updateChain.Clear();
-      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
-    }
-
-    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
-      if (phrase.Length > maxLen) throw new ArgumentException();
-      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.IsTerminal; // terminal phrase means we are done
-      while (!done) {
-        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);
-        Sequence selectedAlt;
-        // if the choice is restricted then one of the allowed alternatives is selected randomly
-        if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
-          var allowedAlts = alts.Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-          Debug.Assert(allowedAlts.Any());
-          // replace nt with random alternative
-          selectedAlt = allowedAlts.SelectRandom(random);
-        } else {
-          // all alts are allowed => select using bandit policy
-          var ntIdx = phrase.FirstNonTerminalIndex;
-          var startIdx = Math.Max(0, ntIdx - contextLen);
-          var endIdx = Math.Min(startIdx + contextLen, ntIdx);
-          var lft = phrase.Subsequence(startIdx, endIdx - startIdx + 1).ToString();
-          lft = problem.CanonicalRepresentation(lft);
-          if (!contextActionInfos.ContainsKey(lft)) {
-            contextActionInfos.Add(lft, g.GetAlternatives(nt).Select(_ => policy.CreateActionInfo()).ToArray());
-          }
-          var selectedAltIdx = policy.SelectAction(random, contextActionInfos[lft]);
-          selectedAlt = alts.ElementAt(selectedAltIdx);
-          updateChain.Add(Tuple.Create(lft, selectedAltIdx));
-        }
-
-        // replace nt with alt
-        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-        done = phrase.IsTerminal; // terminal phrase means we are done
-      }
-      return phrase;
-    }
-
-    private void DistributeReward(double reward) {
-      foreach (var e in updateChain) {
-        var lft = e.Item1;
-        var action = e.Item2;
-        contextActionInfos[lft][action].UpdateReward(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: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11849)
+++ 	(revision )
@@ -1,112 +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 AlternativesSampler {
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly Random random;
-    private readonly IProblem problem;
-    private readonly IBanditPolicy policy;
-
-    public AlternativesSampler(IProblem problem, IBanditPolicy policy, int maxLen) {
-      this.problem = problem;
-      this.maxLen = maxLen;
-      this.random = new Random();
-      this.policy = policy;
-    }
-
-    public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
-      InitPolicies(problem.Grammar);
-      for (int i = 0; i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        DistributeReward(quality);
-
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-    }
-
-
-    private Dictionary<char, IBanditPolicyActionInfo[]> ntActionInfos;
-    private List<Tuple<char, int>> updateChain;
-
-    private void InitPolicies(IGrammar grammar) {
-      this.ntActionInfos = new Dictionary<char, IBanditPolicyActionInfo[]>();
-      this.updateChain = new List<Tuple<char, int>>();
-      foreach (var nt in grammar.NonTerminalSymbols) {
-        ntActionInfos.Add(nt, grammar.GetAlternatives(nt).Select(_ => policy.CreateActionInfo()).ToArray());
-      }
-    }
-
-    private Sequence SampleSentence(IGrammar grammar) {
-      updateChain.Clear();
-      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
-    }
-
-    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
-      if (phrase.Length > maxLen) throw new ArgumentException();
-      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.IsTerminal; // terminal phrase means we are done
-      while (!done) {
-        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);
-        Sequence selectedAlt;
-        // if the choice is restricted then one of the allowed alternatives is selected randomly
-        if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
-          var allowedAlts = alts.Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
-          Debug.Assert(allowedAlts.Any());
-          // replace nt with random alternative
-          selectedAlt = allowedAlts.SelectRandom(random);
-        } else {
-          // all alts are allowed => select using bandit policy
-          var selectedAltIdx = policy.SelectAction(random, ntActionInfos[nt]);
-          selectedAlt = alts.ElementAt(selectedAltIdx);
-          updateChain.Add(Tuple.Create(nt, selectedAltIdx));
-        }
-
-        // replace nt with alt
-        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
-
-        done = phrase.IsTerminal; // terminal phrase means we are done
-      }
-      return phrase;
-    }
-
-
-    private void DistributeReward(double reward) {
-      foreach (var e in updateChain) {
-        var nt = e.Item1;
-        var action = e.Item2;
-        ntActionInfos[nt][action].UpdateReward(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: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11849)
+++ 	(revision )
@@ -1,68 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class ExhaustiveBreadthFirstSearch {
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly Queue<Sequence> bfsQueue = new Queue<Sequence>();
-    private readonly IProblem problem;
-
-    public ExhaustiveBreadthFirstSearch(IProblem problem, int maxLen) {
-      this.problem = problem;
-      this.maxLen = maxLen;
-    }
-
-    public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
-      bfsQueue.Enqueue(new Sequence(problem.Grammar.SentenceSymbol));
-      var sentences = GenerateLanguage(problem.Grammar);
-      var sentenceEnumerator = sentences.GetEnumerator();
-      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current.ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-    }
-
-    // create sentences lazily
-    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
-      while (bfsQueue.Any()) {
-        var phrase = bfsQueue.Dequeue();
-
-        char nt = phrase.FirstNonTerminal;
-
-        var alts = grammar.GetAlternatives(nt);
-        foreach (var alt in alts) {
-          var newPhrase = new Sequence(phrase);
-          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
-          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
-            yield return newPhrase;
-          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
-            bfsQueue.Enqueue(newPhrase);
-          }
-        }
-      }
-    }
-
-
-    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: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11849)
+++ 	(revision )
@@ -1,68 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class ExhaustiveDepthFirstSearch {
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly Stack<Sequence> stack = new Stack<Sequence>();
-    private readonly IProblem problem;
-
-    public ExhaustiveDepthFirstSearch(IProblem problem, int maxLen) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-    }
-
-    public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
-      stack.Push(new Sequence(problem.Grammar.SentenceSymbol));
-      var sentences = GenerateLanguage(problem.Grammar);
-      var sentenceEnumerator = sentences.GetEnumerator();
-      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current.ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-    }
-
-    // create sentences lazily
-    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
-      while (stack.Any()) {
-        var phrase = stack.Pop();
-
-        char nt = phrase.FirstNonTerminal;
-        var alts = grammar.GetAlternatives(nt);
-        foreach (var alt in alts) {
-          var newPhrase = new Sequence(phrase);
-          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
-
-          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
-            yield return newPhrase;
-          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
-            stack.Push(newPhrase);
-          }
-        }
-      }
-    }
-
-
-    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: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveRandomFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveRandomFirstSearch.cs	(revision 11849)
+++ 	(revision )
@@ -1,74 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class ExhaustiveRandomFirstSearch {
-    public event Action<string, double> FoundNewBestSolution;
-    public event Action<string, double> SolutionEvaluated;
-
-    private readonly int maxLen;
-    private readonly System.Collections.Generic.SortedList<double, Sequence> sortedList = new SortedList<double, Sequence>();
-    private readonly IProblem problem;
-    private readonly Random random;
-
-    public ExhaustiveRandomFirstSearch(IProblem problem, Random random, int maxLen) {
-      this.maxLen = maxLen;
-      this.problem = problem;
-      this.random = new Random();
-    }
-
-    public void Run(int maxIterations) {
-      double bestQuality = double.MinValue;
-      sortedList.Add(0, new Sequence(problem.Grammar.SentenceSymbol));
-      var sentences = GenerateLanguage(problem.Grammar);
-      var sentenceEnumerator = sentences.GetEnumerator();
-      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
-        var sentence = sentenceEnumerator.Current.ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        RaiseSolutionEvaluated(sentence, quality);
-
-        if (quality > bestQuality) {
-          bestQuality = quality;
-          RaiseFoundNewBestSolution(sentence, quality);
-        }
-      }
-    }
-
-    // create sentences lazily
-    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
-      while (sortedList.Any()) {
-        var phrase = sortedList.First().Value;
-        sortedList.RemoveAt(0);
-
-        char nt = phrase.FirstNonTerminal;
-        var alts = grammar.GetAlternatives(nt);
-        foreach (var alt in alts) {
-          var newPhrase = new Sequence(phrase);
-          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
-
-          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
-            yield return newPhrase;
-          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
-            var r = random.NextDouble();
-            Sequence t;
-            while (sortedList.TryGetValue(r, out t)) { r = random.NextDouble(); }
-            sortedList.Add(r, newPhrase);
-          }
-        }
-      }
-    }
-
-
-    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 11849)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11850)
@@ -38,14 +38,23 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="AlternativesSampler.cs" />
-    <Compile Include="AlternativesContextSampler.cs" />
+    <Compile Include="ISequentialDecisionPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\GenericContextualGrammarPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\GenericFunctionApproximationGrammarPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\GenericGrammarPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\GenericTDPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\GrammarPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\IGrammarPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\RandomPolicy.cs" />
+    <Compile Include="SequentialDecisionPolicies\TDPolicy.cs" />
     <Compile Include="SolverBase.cs" />
     <Compile Include="ISolver.cs" />
-    <Compile Include="SequentialSearch.cs" />
-    <Compile Include="ExhaustiveRandomFirstSearch.cs" />
-    <Compile Include="ExhaustiveDepthFirstSearch.cs" />
-    <Compile Include="ExhaustiveBreadthFirstSearch.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="RandomSearch.cs" />
+    <Compile Include="Solvers\AlternativesContextSampler.cs" />
+    <Compile Include="Solvers\AlternativesSampler.cs" />
+    <Compile Include="Solvers\ExhaustiveBreadthFirstSearch.cs" />
+    <Compile Include="Solvers\ExhaustiveDepthFirstSearch.cs" />
+    <Compile Include="Solvers\ExhaustiveRandomFirstSearch.cs" />
+    <Compile Include="Solvers\RandomSearch.cs" />
+    <Compile Include="Solvers\SequentialSearch.cs" />
   </ItemGroup>
   <ItemGroup>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ISequentialDecisionPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ISequentialDecisionPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ISequentialDecisionPolicy.cs	(revision 11850)
@@ -0,0 +1,25 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Dynamic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  // 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 ISequentialDecisionPolicy<in TState> {
+    bool TrySelect(Random random, TState curState, IEnumerable<TState> afterStates, out int selectedStateIdx); // selectedState \in afterStates
+
+    // 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: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs	(revision 11849)
+++ 	(revision )
@@ -1,29 +1,0 @@
-﻿using System;
-using HeuristicLab.Problems.GrammaticalOptimization;
-
-namespace HeuristicLab.Algorithms.GrammaticalOptimization {
-  public class RandomSearch : SolverBase {
-    private readonly int maxLen;
-    private readonly Random random;
-    private readonly IProblem problem;
-
-    public RandomSearch(IProblem problem, Random random, int maxLen) {
-      this.maxLen = maxLen;
-      this.random = random;
-      this.problem = problem;
-    }
-
-    public override void Run(int maxIterations) {
-      for (int i = 0; i < maxIterations; i++) {
-        var sentence = CreateSentence(problem.Grammar).ToString();
-        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
-        OnSolutionEvaluated(sentence, quality);
-      }
-    }
-
-    private Sequence CreateSentence(IGrammar grammar) {
-      var sentence = new Sequence(grammar.SentenceSymbol);
-      return grammar.CompleteSentenceRandomly(random, sentence, maxLen);
-    }
-  }
-}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericContextualGrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericContextualGrammarPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericContextualGrammarPolicy.cs	(revision 11850)
@@ -0,0 +1,163 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Runtime.ExceptionServices;
+using System.Text;
+using System.Text.RegularExpressions;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public sealed class GenericContextualGrammarPolicy : 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 GenericContextualGrammarPolicy(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 => 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))];
+
+      return true;
+    }
+
+
+    private IBanditPolicyActionInfo GetStateInfo(string state) {
+      var s = Context(state);
+      IBanditPolicyActionInfo info;
+      if (!stateInfo.TryGetValue(s, out info)) {
+        info = banditPolicy.CreateActionInfo();
+        stateInfo[s] = info;
+      }
+      return info;
+    }
+
+    private string Context(string state) {
+      // var cutOff = problem.Grammar.IsTerminal(state) ? 0 : 2;
+      // var contextLen = 7;
+      // var firstPos = Math.Max(0, state.Length - contextLen - cutOff);
+      // var lastPos = Math.Max(0, Math.Min(state.Length, state.Length - cutOff));
+      // var context = state.Substring(firstPos, (lastPos - firstPos));
+      var contextLen = 5;
+      var firstPos = Math.Max(0, state.Length - contextLen);
+      var lastPos = Math.Min(state.Length, firstPos + contextLen);
+      var context = state.Substring(firstPos, (lastPos - firstPos));
+      return context + Regex.Matches(state, "(?=" + Regex.Escape(context) + ")").Count;
+
+
+      //var lastPlusPos = Math.Max(0, state.LastIndexOf('+') + 1);
+      //var context = state.Substring(lastPlusPos);
+      //return context + Regex.Matches(state, "(?=" + Regex.Escape(context) + ")").Count; 
+    }
+
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      foreach (var state in stateTrajectory) {
+        GetStateInfo(state).UpdateReward(reward);
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(state)) {
+          MarkAsDone(state);
+        }
+      }
+    }
+
+
+    public void Reset() {
+      stateInfo.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(string state) {
+      var s = Context(state);
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
+      else return 0;
+    }
+
+    public double GetValue(string state) {
+      var s = Context(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.GrammaticalOptimization/SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs	(revision 11850)
@@ -0,0 +1,171 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Runtime.ExceptionServices;
+using System.Text;
+using System.Text.RegularExpressions;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
+  public sealed class GenericFunctionApproximationGrammarPolicy : IGrammarPolicy {
+    private Dictionary<string, double> featureWeigths; // stores the necessary information for bandit policies for each state (=canonical phrase)
+    private HashSet<string> done;
+    private readonly bool useCanonicalPhrases;
+    private readonly IProblem problem;
+
+
+    public GenericFunctionApproximationGrammarPolicy(IProblem problem, bool useCanonicalPhrases = false) {
+      this.useCanonicalPhrases = useCanonicalPhrases;
+      this.problem = problem;
+      this.featureWeigths = new Dictionary<string, double>();
+      this.done = new HashSet<string>();
+    }
+
+    private double[] 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 double[afterStates.Count()];
+        actionIndexMap = new int[afterStates.Count()];
+      }
+      var maxIdx = 0; int originalIdx = 0;
+      foreach (var afterState in afterStates) {
+        if (!Done(afterState)) {
+          activeAfterStates[maxIdx] = 0.0;
+          actionIndexMap[maxIdx] = originalIdx;
+
+
+          activeAfterStates[maxIdx] = GetValue(afterState);
+
+          maxIdx++;
+        }
+        originalIdx++;
+      }
+
+      if (random.NextDouble() < 0.2) {
+        selectedStateIdx = actionIndexMap[random.Next(maxIdx)];
+      } else {
+        // find max
+        var bestQ = double.NegativeInfinity;
+        var bestIdx = -1;
+        for (int i = 0; i < maxIdx; i++) {
+          if (activeAfterStates[i] > bestQ) {
+            bestQ = activeAfterStates[i];
+            bestIdx = i;
+          }
+        }
+        selectedStateIdx = actionIndexMap[bestIdx];
+      }
+
+      return true;
+    }
+
+
+    public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      foreach (var state in stateTrajectory) {
+        UpdateWeights(state, reward);
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(state)) {
+          MarkAsDone(state);
+        }
+      }
+    }
+
+
+    private IEnumerable<KeyValuePair<string, double>> Values {
+      get { return featureWeigths.OrderByDescending(p => p.Value); }
+    }
+
+    public void Reset() {
+      featureWeigths.Clear();
+      done.Clear();
+    }
+
+    public int GetTries(string state) {
+      return 1;
+    }
+
+    public double GetValue(string state) {
+      return problem.GetFeatures(state).Sum(feature => GetWeight(feature)) ;
+    }
+
+    private double GetWeight(Feature feature) {
+      double w;
+      if (featureWeigths.TryGetValue(feature.Id, out w)) return w * feature.Value;
+      else return 0.0;
+    }
+    private void UpdateWeights(string state, double reward) {
+      const double alpha = 0.01;
+      double delta = reward - GetValue(state);
+      foreach (var feature in problem.GetFeatures(state)) {
+        double w;
+        if (!featureWeigths.TryGetValue(feature.Id, out w)) {
+          featureWeigths[feature.Id] = alpha * delta;
+        } else {
+          featureWeigths[feature.Id] += alpha * delta;
+        }
+      }
+    }
+
+
+
+    // 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.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs	(revision 11850)
@@ -0,0 +1,146 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+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
+  // 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 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 => 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))];
+
+      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) {
+        GetStateInfo(state).UpdateReward(reward);
+
+        // only the last state can be terminal
+        if (problem.Grammar.IsTerminal(state)) {
+          MarkAsDone(state);
+        }
+      }
+    }
+
+
+    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.GrammaticalOptimization/SequentialDecisionPolicies/GenericTDPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericTDPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericTDPolicy.cs	(revision 11850)
@@ -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.GrammaticalOptimization/SequentialDecisionPolicies/GrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GrammarPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GrammarPolicy.cs	(revision 11850)
@@ -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 (base class for RandomPolicy and TDPolicy
+  public abstract class GrammarPolicy : IGrammarPolicy {
+    protected Dictionary<string, double> avgReward;
+    protected Dictionary<string, int> tries;
+    protected Dictionary<string, double> maxReward;
+    protected readonly bool useCanonicalState;
+    protected readonly IProblem problem;
+
+    protected 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, string curState, IEnumerable<string> afterStates, out int selectedStateIdx);
+
+    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      foreach (var state in stateTrajectory) {
+        var s = CanonicalState(state);
+
+        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(string state) {
+      var s = CanonicalState(state);
+      if (avgReward.ContainsKey(s)) return avgReward[s];
+      else return 0.0;
+    }
+
+    public double MaxReward(string state) {
+      var s = CanonicalState(state);
+      if (maxReward.ContainsKey(s)) return maxReward[s];
+      else return 0.0;
+    }
+
+    public virtual int GetTries(string state) {
+      var s = CanonicalState(state);
+      if (tries.ContainsKey(s)) return tries[s];
+      else return 0;
+    }
+
+    public virtual double GetValue(string 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.GrammaticalOptimization/SequentialDecisionPolicies/IGrammarPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/IGrammarPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/IGrammarPolicy.cs	(revision 11850)
@@ -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 : ISequentialDecisionPolicy<string> {
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/RandomPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/RandomPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/RandomPolicy.cs	(revision 11850)
@@ -0,0 +1,21 @@
+﻿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 class RandomPolicy : GrammarPolicy {
+    public RandomPolicy(IProblem problem, bool useCanonicalRepresentation)
+      : base(problem, useCanonicalRepresentation) {
+    }
+
+    public override bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      // never fail => allows re-visits of terminal states
+      selectedStateIdx = random.Next(afterStates.Count());
+      return true;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/TDPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/TDPolicy.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/TDPolicy.cs	(revision 11850)
@@ -0,0 +1,98 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Configuration;
+using System.Diagnostics;
+using System.Linq;
+using System.Security.Policy;
+using System.Text;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+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 IGrammarPolicy 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 GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.1), useCanonicalRepresentation);
+    }
+
+    public override bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      // 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));
+        selectedStateIdx = -1;
+        return false;
+      }
+      throw new NotImplementedException(); // TODO: remap indices of reduced action enumerable to indices of original enumerable (see genericgrammarpolicy)
+
+      //return epsGreedy.TrySelect(random, curState, afterStates, out selectedState);
+
+      var bestQ = double.NegativeInfinity;
+      int idx = -1;
+      selectedStateIdx = -1;
+      foreach (var state in afterStates) {
+        idx++;
+        // try each state at least once
+        if (GetTries(state) == 0) {
+          selectedStateIdx = idx;
+          return true;
+        }
+        var q = V(state);
+        if (q > bestQ) {
+          bestQ = q;
+          selectedStateIdx = idx;
+        }
+      }
+
+      Debug.Assert(selectedStateIdx > -1);
+      return true;
+    }
+
+    private double V(string state) {
+      var s = CanonicalState(state);
+      if (v.ContainsKey(s)) return v[s];
+      else return 0.0;
+    }
+
+    public override void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      base.UpdateReward(stateTrajectory, reward);
+      epsGreedy.UpdateReward(stateTrajectory, reward);
+      // the last state could be terminal
+      var lastState = stateTrajectory.Last();
+      if (problem.Grammar.IsTerminal(lastState)) done.Add(CanonicalState(lastState));
+
+      v[CanonicalState(lastState)] = 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)] = 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(string state) {
+      return V(state);
+    }
+
+    public override void Reset() {
+      base.Reset();
+      epsGreedy.Reset();
+      v.Clear();
+      done.Clear();
+    }
+  }
+}
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs	(revision 11849)
+++ 	(revision )
@@ -1,242 +1,0 @@
-﻿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 : SolverBase {
-    // only for storing states so that it is not necessary to allocate new state strings whenever we select a follow state using the policy
-    private class TreeNode {
-      public int randomTries;
-      public string phrase;
-      public Sequence alternative;
-      public TreeNode[] children;
-
-      public TreeNode(string phrase, Sequence alternative) {
-        this.alternative = alternative;
-        this.phrase = phrase;
-      }
-    }
-
-
-    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 TreeNode rootNode;
-
-    private int tries;
-    private int maxSearchDepth;
-
-    private string bestPhrase;
-    private readonly List<string> 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 GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.0), false);
-      this.stateChain = new List<string>();
-    }
-
-    public override void Run(int maxIterations) {
-      Reset();
-
-      for (int i = 0; /*!bestQuality.IsAlmost(1.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);
-          if (double.IsNaN(quality)) quality = 0.0;
-          Debug.Assert(quality >= 0 && quality <= 1.0);
-
-          if (quality > bestQuality) {
-            bestPhrase = sentence;
-          }
-
-          OnSolutionEvaluated(sentence, quality);
-          DistributeReward(quality);
-
-        }
-      }
-    }
-
-
-    private Sequence SampleSentence(IGrammar grammar) {
-      Sequence phrase;
-      do {
-        stateChain.Clear();
-        phrase = new Sequence(rootNode.phrase);
-      } while (!Done() && !TryCompleteSentence(grammar, ref phrase));
-      return phrase;
-    }
-
-    private bool TryCompleteSentence(IGrammar g, ref Sequence phrase) {
-      if (phrase.Length > maxLen) throw new ArgumentException();
-      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      var curDepth = 0;
-      var n = rootNode;
-      stateChain.Add(n.phrase);
-
-      while (!phrase.IsTerminal) {
-        if (n.randomTries < randomTries) {
-          n.randomTries++;
-          maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
-          g.CompleteSentenceRandomly(random, phrase, maxLen);
-          return true;
-        } else {
-          // => select using bandit policy
-          // failure means we simply restart
-          GenerateFollowStates(n); // creates child nodes for node n
-
-          int selectedChildIdx;
-          if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
-            return false;
-          }
-          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
-
-          // prepare for next iteration
-          n = n.children[selectedChildIdx];
-          stateChain.Add(n.phrase);
-          curDepth++;
-        }
-      } // while
-
-      maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
-      return true;
-    }
-
-
-    private IEnumerable<string> GenerateFollowStates(TreeNode n) {
-      // create children on the first visit
-      if (n.children == null) {
-        var g = problem.Grammar;
-        // tree is only used for easily retrieving the follow-states of a state
-        var phrase = new Sequence(n.phrase);
-        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);
-
-        var children = new TreeNode[alts.Count()];
-        int idx = 0;
-        foreach (var alt in alts) {
-          // var newPhrase = new Sequence(phrase); // clone
-          // newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
-          // children[idx++] = new TreeNode(newPhrase.ToString(), alt);
-
-          // since we are not using a sequence later on we might directly transform the current sequence to a string and replace there
-          var phraseStr = phrase.ToString();
-          var sb = new StringBuilder(phraseStr);
-          sb.Remove(phrase.FirstNonTerminalIndex, 1).Insert(phrase.FirstNonTerminalIndex, alt.ToString());
-          children[idx++] = new TreeNode(sb.ToString(), alt);
-        }
-        n.children = children;
-      }
-      return n.children.Select(ch => ch.phrase);
-    }
-
-    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;
-      rootNode = new TreeNode(problem.Grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
-    }
-
-    public bool Done() {
-      int selectedStateIdx;
-      return !behaviourPolicy.TrySelect(random, rootNode.phrase, GenerateFollowStates(rootNode), out selectedStateIdx);
-    }
-
-    #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 behaviour strategy to generate the currently prefered sentence
-      var policy = behaviourPolicy;
-
-      var n = rootNode;
-
-      while (n != null) {
-        var phrase = n.phrase;
-        Console.ForegroundColor = ConsoleColor.White;
-        Console.WriteLine("{0,-30}", phrase);
-        var children = n.children;
-        if (children == null || !children.Any()) break;
-        var values = children.Select(ch => policy.GetValue(ch.phrase));
-        var maxValue = values.Max();
-        if (maxValue == 0) maxValue = 1.0;
-
-        // write phrases
-        foreach (var ch in children) {
-          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-          Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
-        }
-        Console.WriteLine();
-
-        // write values
-        foreach (var ch in children) {
-          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-          Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
-        }
-        Console.WriteLine();
-
-        // write tries
-        foreach (var ch in children) {
-          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-          Console.Write(" {0,4}", policy.GetTries(ch.phrase));
-        }
-        Console.WriteLine();
-        int selectedChildIdx;
-        if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
-          break;
-        }
-        n = n.children[selectedChildIdx];
-      }
-
-      Console.ForegroundColor = ConsoleColor.White;
-      Console.WriteLine("-------------------");
-    }
-
-    private void SetColorForValue(double v) {
-      Console.ForegroundColor = ConsoleEx.ColorForValue(v);
-    }
-    #endregion
-  
-  }
-}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/AlternativesContextSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/AlternativesContextSampler.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/AlternativesContextSampler.cs	(revision 11850)
@@ -0,0 +1,118 @@
+﻿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 AlternativesContextSampler {
+    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 contextLen;
+    private readonly IBanditPolicy policy;
+
+    public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, IBanditPolicy policy) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = random;
+      this.contextLen = contextLen;
+      this.policy = policy;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      InitPolicies(problem.Grammar);
+      for (int i = 0; i < maxIterations; i++) {
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        DistributeReward(quality);
+
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+
+    private Dictionary<string, IBanditPolicyActionInfo[]> contextActionInfos;
+    private List<Tuple<string, int>> updateChain;
+
+    private void InitPolicies(IGrammar grammar) {
+      this.contextActionInfos = new Dictionary<string, IBanditPolicyActionInfo[]>();
+      this.updateChain = new List<Tuple<string, int>>();
+    }
+
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
+    }
+
+    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
+      while (!done) {
+        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);
+        Sequence selectedAlt;
+        // if the choice is restricted then one of the allowed alternatives is selected randomly
+        if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
+          var allowedAlts = alts.Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
+          Debug.Assert(allowedAlts.Any());
+          // replace nt with random alternative
+          selectedAlt = allowedAlts.SelectRandom(random);
+        } else {
+          // all alts are allowed => select using bandit policy
+          var ntIdx = phrase.FirstNonTerminalIndex;
+          var startIdx = Math.Max(0, ntIdx - contextLen);
+          var endIdx = Math.Min(startIdx + contextLen, ntIdx);
+          var lft = phrase.Subsequence(startIdx, endIdx - startIdx + 1).ToString();
+          lft = problem.CanonicalRepresentation(lft);
+          if (!contextActionInfos.ContainsKey(lft)) {
+            contextActionInfos.Add(lft, g.GetAlternatives(nt).Select(_ => policy.CreateActionInfo()).ToArray());
+          }
+          var selectedAltIdx = policy.SelectAction(random, contextActionInfos[lft]);
+          selectedAlt = alts.ElementAt(selectedAltIdx);
+          updateChain.Add(Tuple.Create(lft, selectedAltIdx));
+        }
+
+        // replace nt with alt
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
+
+        done = phrase.IsTerminal; // terminal phrase means we are done
+      }
+      return phrase;
+    }
+
+    private void DistributeReward(double reward) {
+      foreach (var e in updateChain) {
+        var lft = e.Item1;
+        var action = e.Item2;
+        contextActionInfos[lft][action].UpdateReward(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.Algorithms.GrammaticalOptimization/Solvers/AlternativesSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/AlternativesSampler.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/AlternativesSampler.cs	(revision 11850)
@@ -0,0 +1,112 @@
+﻿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 AlternativesSampler {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly Random random;
+    private readonly IProblem problem;
+    private readonly IBanditPolicy policy;
+
+    public AlternativesSampler(IProblem problem, IBanditPolicy policy, int maxLen) {
+      this.problem = problem;
+      this.maxLen = maxLen;
+      this.random = new Random();
+      this.policy = policy;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      InitPolicies(problem.Grammar);
+      for (int i = 0; i < maxIterations; i++) {
+        var sentence = SampleSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        DistributeReward(quality);
+
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+
+    private Dictionary<char, IBanditPolicyActionInfo[]> ntActionInfos;
+    private List<Tuple<char, int>> updateChain;
+
+    private void InitPolicies(IGrammar grammar) {
+      this.ntActionInfos = new Dictionary<char, IBanditPolicyActionInfo[]>();
+      this.updateChain = new List<Tuple<char, int>>();
+      foreach (var nt in grammar.NonTerminalSymbols) {
+        ntActionInfos.Add(nt, grammar.GetAlternatives(nt).Select(_ => policy.CreateActionInfo()).ToArray());
+      }
+    }
+
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol));
+    }
+
+    public Sequence CompleteSentence(IGrammar g, Sequence phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
+      while (!done) {
+        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);
+        Sequence selectedAlt;
+        // if the choice is restricted then one of the allowed alternatives is selected randomly
+        if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) {
+          var allowedAlts = alts.Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
+          Debug.Assert(allowedAlts.Any());
+          // replace nt with random alternative
+          selectedAlt = allowedAlts.SelectRandom(random);
+        } else {
+          // all alts are allowed => select using bandit policy
+          var selectedAltIdx = policy.SelectAction(random, ntActionInfos[nt]);
+          selectedAlt = alts.ElementAt(selectedAltIdx);
+          updateChain.Add(Tuple.Create(nt, selectedAltIdx));
+        }
+
+        // replace nt with alt
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
+
+        done = phrase.IsTerminal; // terminal phrase means we are done
+      }
+      return phrase;
+    }
+
+
+    private void DistributeReward(double reward) {
+      foreach (var e in updateChain) {
+        var nt = e.Item1;
+        var action = e.Item2;
+        ntActionInfos[nt][action].UpdateReward(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.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveBreadthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveBreadthFirstSearch.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveBreadthFirstSearch.cs	(revision 11850)
@@ -0,0 +1,68 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class ExhaustiveBreadthFirstSearch {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly Queue<Sequence> bfsQueue = new Queue<Sequence>();
+    private readonly IProblem problem;
+
+    public ExhaustiveBreadthFirstSearch(IProblem problem, int maxLen) {
+      this.problem = problem;
+      this.maxLen = maxLen;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      bfsQueue.Enqueue(new Sequence(problem.Grammar.SentenceSymbol));
+      var sentences = GenerateLanguage(problem.Grammar);
+      var sentenceEnumerator = sentences.GetEnumerator();
+      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
+        var sentence = sentenceEnumerator.Current.ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    // create sentences lazily
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
+      while (bfsQueue.Any()) {
+        var phrase = bfsQueue.Dequeue();
+
+        char nt = phrase.FirstNonTerminal;
+
+        var alts = grammar.GetAlternatives(nt);
+        foreach (var alt in alts) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
+            yield return newPhrase;
+          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
+            bfsQueue.Enqueue(newPhrase);
+          }
+        }
+      }
+    }
+
+
+    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/Solvers/ExhaustiveDepthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveDepthFirstSearch.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveDepthFirstSearch.cs	(revision 11850)
@@ -0,0 +1,68 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class ExhaustiveDepthFirstSearch {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly Stack<Sequence> stack = new Stack<Sequence>();
+    private readonly IProblem problem;
+
+    public ExhaustiveDepthFirstSearch(IProblem problem, int maxLen) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      stack.Push(new Sequence(problem.Grammar.SentenceSymbol));
+      var sentences = GenerateLanguage(problem.Grammar);
+      var sentenceEnumerator = sentences.GetEnumerator();
+      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
+        var sentence = sentenceEnumerator.Current.ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    // create sentences lazily
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
+      while (stack.Any()) {
+        var phrase = stack.Pop();
+
+        char nt = phrase.FirstNonTerminal;
+        var alts = grammar.GetAlternatives(nt);
+        foreach (var alt in alts) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
+            yield return newPhrase;
+          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
+            stack.Push(newPhrase);
+          }
+        }
+      }
+    }
+
+
+    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/Solvers/ExhaustiveRandomFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveRandomFirstSearch.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveRandomFirstSearch.cs	(revision 11850)
@@ -0,0 +1,74 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class ExhaustiveRandomFirstSearch {
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly System.Collections.Generic.SortedList<double, Sequence> sortedList = new SortedList<double, Sequence>();
+    private readonly IProblem problem;
+    private readonly Random random;
+
+    public ExhaustiveRandomFirstSearch(IProblem problem, Random random, int maxLen) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = new Random();
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      sortedList.Add(0, new Sequence(problem.Grammar.SentenceSymbol));
+      var sentences = GenerateLanguage(problem.Grammar);
+      var sentenceEnumerator = sentences.GetEnumerator();
+      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
+        var sentence = sentenceEnumerator.Current.ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    // create sentences lazily
+    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
+      while (sortedList.Any()) {
+        var phrase = sortedList.First().Value;
+        sortedList.RemoveAt(0);
+
+        char nt = phrase.FirstNonTerminal;
+        var alts = grammar.GetAlternatives(nt);
+        foreach (var alt in alts) {
+          var newPhrase = new Sequence(phrase);
+          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+
+          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
+            yield return newPhrase;
+          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
+            var r = random.NextDouble();
+            Sequence t;
+            while (sortedList.TryGetValue(r, out t)) { r = random.NextDouble(); }
+            sortedList.Add(r, newPhrase);
+          }
+        }
+      }
+    }
+
+
+    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/Solvers/RandomSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/RandomSearch.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/RandomSearch.cs	(revision 11850)
@@ -0,0 +1,29 @@
+﻿using System;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class RandomSearch : SolverBase {
+    private readonly int maxLen;
+    private readonly Random random;
+    private readonly IProblem problem;
+
+    public RandomSearch(IProblem problem, Random random, int maxLen) {
+      this.maxLen = maxLen;
+      this.random = random;
+      this.problem = problem;
+    }
+
+    public override void Run(int maxIterations) {
+      for (int i = 0; i < maxIterations; i++) {
+        var sentence = CreateSentence(problem.Grammar).ToString();
+        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
+        OnSolutionEvaluated(sentence, quality);
+      }
+    }
+
+    private Sequence CreateSentence(IGrammar grammar) {
+      var sentence = new Sequence(grammar.SentenceSymbol);
+      return grammar.CompleteSentenceRandomly(random, sentence, maxLen);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs	(revision 11850)
@@ -0,0 +1,242 @@
+﻿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 : SolverBase {
+    // only for storing states so that it is not necessary to allocate new state strings whenever we select a follow state using the policy
+    private class TreeNode {
+      public int randomTries;
+      public string phrase;
+      public Sequence alternative;
+      public TreeNode[] children;
+
+      public TreeNode(string phrase, Sequence alternative) {
+        this.alternative = alternative;
+        this.phrase = phrase;
+      }
+    }
+
+
+    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 TreeNode rootNode;
+
+    private int tries;
+    private int maxSearchDepth;
+
+    private string bestPhrase;
+    private readonly List<string> 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 GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.0), false);
+      this.stateChain = new List<string>();
+    }
+
+    public override void Run(int maxIterations) {
+      Reset();
+
+      for (int i = 0; /*!bestQuality.IsAlmost(1.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);
+          if (double.IsNaN(quality)) quality = 0.0;
+          Debug.Assert(quality >= 0 && quality <= 1.0);
+
+          if (quality > bestQuality) {
+            bestPhrase = sentence;
+          }
+
+          OnSolutionEvaluated(sentence, quality);
+          DistributeReward(quality);
+
+        }
+      }
+    }
+
+
+    private Sequence SampleSentence(IGrammar grammar) {
+      Sequence phrase;
+      do {
+        stateChain.Clear();
+        phrase = new Sequence(rootNode.phrase);
+      } while (!Done() && !TryCompleteSentence(grammar, ref phrase));
+      return phrase;
+    }
+
+    private bool TryCompleteSentence(IGrammar g, ref Sequence phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      var curDepth = 0;
+      var n = rootNode;
+      stateChain.Add(n.phrase);
+
+      while (!phrase.IsTerminal) {
+        if (n.randomTries < randomTries) {
+          n.randomTries++;
+          maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
+          g.CompleteSentenceRandomly(random, phrase, maxLen);
+          return true;
+        } else {
+          // => select using bandit policy
+          // failure means we simply restart
+          GenerateFollowStates(n); // creates child nodes for node n
+
+          int selectedChildIdx;
+          if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
+            return false;
+          }
+          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
+
+          // prepare for next iteration
+          n = n.children[selectedChildIdx];
+          stateChain.Add(n.phrase);
+          curDepth++;
+        }
+      } // while
+
+      maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
+      return true;
+    }
+
+
+    private IEnumerable<string> GenerateFollowStates(TreeNode n) {
+      // create children on the first visit
+      if (n.children == null) {
+        var g = problem.Grammar;
+        // tree is only used for easily retrieving the follow-states of a state
+        var phrase = new Sequence(n.phrase);
+        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);
+
+        var children = new TreeNode[alts.Count()];
+        int idx = 0;
+        foreach (var alt in alts) {
+          // var newPhrase = new Sequence(phrase); // clone
+          // newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
+          // children[idx++] = new TreeNode(newPhrase.ToString(), alt);
+
+          // since we are not using a sequence later on we might directly transform the current sequence to a string and replace there
+          var phraseStr = phrase.ToString();
+          var sb = new StringBuilder(phraseStr);
+          sb.Remove(phrase.FirstNonTerminalIndex, 1).Insert(phrase.FirstNonTerminalIndex, alt.ToString());
+          children[idx++] = new TreeNode(sb.ToString(), alt);
+        }
+        n.children = children;
+      }
+      return n.children.Select(ch => ch.phrase);
+    }
+
+    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;
+      rootNode = new TreeNode(problem.Grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
+    }
+
+    public bool Done() {
+      int selectedStateIdx;
+      return !behaviourPolicy.TrySelect(random, rootNode.phrase, GenerateFollowStates(rootNode), out selectedStateIdx);
+    }
+
+    #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 behaviour strategy to generate the currently prefered sentence
+      var policy = behaviourPolicy;
+
+      var n = rootNode;
+
+      while (n != null) {
+        var phrase = n.phrase;
+        Console.ForegroundColor = ConsoleColor.White;
+        Console.WriteLine("{0,-30}", phrase);
+        var children = n.children;
+        if (children == null || !children.Any()) break;
+        var values = children.Select(ch => policy.GetValue(ch.phrase));
+        var maxValue = values.Max();
+        if (maxValue == 0) maxValue = 1.0;
+
+        // write phrases
+        foreach (var ch in children) {
+          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
+        }
+        Console.WriteLine();
+
+        // write values
+        foreach (var ch in children) {
+          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
+        }
+        Console.WriteLine();
+
+        // write tries
+        foreach (var ch in children) {
+          SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
+          Console.Write(" {0,4}", policy.GetTries(ch.phrase));
+        }
+        Console.WriteLine();
+        int selectedChildIdx;
+        if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
+          break;
+        }
+        n = n.children[selectedChildIdx];
+      }
+
+      Console.ForegroundColor = ConsoleColor.White;
+      Console.WriteLine("-------------------");
+    }
+
+    private void SetColorForValue(double v) {
+      Console.ForegroundColor = ConsoleEx.ColorForValue(v);
+    }
+    #endregion
+  
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Properties/AssemblyInfo.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Properties/AssemblyInfo.cs	(revision 11850)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Problems.GrammaticalOptimization.Test")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("Microsoft")]
+[assembly: AssemblyProduct("HeuristicLab.Problems.GrammaticalOptimization.Test")]
+[assembly: AssemblyCopyright("Copyright © Microsoft 2014")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("1f7e7cac-1ef2-43dc-b5da-5547058c9309")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj	(revision 11850)
@@ -0,0 +1,137 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{8B4C199E-C08B-479E-9B82-6AE5B113459E}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Problems.GrammaticalOptimization.Test</RootNamespace>
+    <AssemblyName>HeuristicLab.Problems.GrammaticalOptimization.Test</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+    <ProjectTypeGuids>{3AC096D0-A1C2-E12C-1390-A8335801FDAB};{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}</ProjectTypeGuids>
+    <VisualStudioVersion Condition="'$(VisualStudioVersion)' == ''">10.0</VisualStudioVersion>
+    <VSToolsPath Condition="'$(VSToolsPath)' == ''">$(MSBuildExtensionsPath32)\Microsoft\VisualStudio\v$(VisualStudioVersion)</VSToolsPath>
+    <ReferencePath>$(ProgramFiles)\Common Files\microsoft shared\VSTT\$(VisualStudioVersion)\UITestExtensionPackages</ReferencePath>
+    <IsCodedUITest>False</IsCodedUITest>
+    <TestProjectType>UnitTest</TestProjectType>
+    <TargetFrameworkProfile />
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+    <Prefer32Bit>false</Prefer32Bit>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Core-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Core-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Problems.Instances-3.3">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Problems.Instances.DataAnalysis-3.3">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances.DataAnalysis-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="System" />
+    <Reference Include="System.Core">
+      <RequiredTargetFramework>3.5</RequiredTargetFramework>
+    </Reference>
+  </ItemGroup>
+  <Choose>
+    <When Condition="('$(VisualStudioVersion)' == '10.0' or '$(VisualStudioVersion)' == '') and '$(TargetFrameworkVersion)' == 'v3.5'">
+      <ItemGroup>
+        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework, Version=10.1.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL" />
+      </ItemGroup>
+    </When>
+    <Otherwise>
+      <ItemGroup>
+        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework" />
+      </ItemGroup>
+    </Otherwise>
+  </Choose>
+  <ItemGroup>
+    <Compile Include="TestSymbRegInstances.cs" />
+    <Compile Include="TestSequence.cs" />
+    <Compile Include="TestBanditPolicies.cs" />
+    <Compile Include="TestInstances.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="TestSolvers.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.Bandits\HeuristicLab.Algorithms.Bandits.csproj">
+      <Project>{24408f7d-ee0f-4886-a08b-ec324d662e47}</Project>
+      <Name>HeuristicLab.Algorithms.Bandits</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.GrammaticalOptimization\HeuristicLab.Algorithms.GrammaticalOptimization.csproj">
+      <Project>{eea07488-1a51-412a-a52c-53b754a628b3}</Project>
+      <Name>HeuristicLab.Algorithms.GrammaticalOptimization</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Distributions\HeuristicLab.Distributions.csproj">
+      <Project>{31171165-E16F-4A1A-A8AB-25C6AB3A71B9}</Project>
+      <Name>HeuristicLab.Distributions</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.Bandits\HeuristicLab.Problems.Bandits.csproj">
+      <Project>{E8138227-0C64-4E85-B676-21D3B97F254F}</Project>
+      <Name>HeuristicLab.Problems.Bandits</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization.SymbReg\HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj">
+      <Project>{17a7a380-86ce-482d-8d22-cbd70cc97f0d}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization.SymbReg</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
+      <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <Choose>
+    <When Condition="'$(VisualStudioVersion)' == '10.0' And '$(IsCodedUITest)' == 'True'">
+      <ItemGroup>
+        <Reference Include="Microsoft.VisualStudio.QualityTools.CodedUITestFramework, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+        <Reference Include="Microsoft.VisualStudio.TestTools.UITest.Common, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+        <Reference Include="Microsoft.VisualStudio.TestTools.UITest.Extension, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+        <Reference Include="Microsoft.VisualStudio.TestTools.UITesting, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL">
+          <Private>False</Private>
+        </Reference>
+      </ItemGroup>
+    </When>
+  </Choose>
+  <Import Project="$(VSToolsPath)\TeamTest\Microsoft.TestTools.targets" Condition="Exists('$(VSToolsPath)\TeamTest\Microsoft.TestTools.targets')" />
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestBanditPolicies.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestBanditPolicies.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestBanditPolicies.cs	(revision 11850)
@@ -0,0 +1,256 @@
+﻿using System;
+using System.Linq;
+using System.Collections.Generic;
+using System.Globalization;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Algorithms.Bandits.Models;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestBanditPolicies {
+    [TestMethod]
+    public void ComparePoliciesForGaussianUnknownVarianceBandit() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+      var nArms = 20;
+
+      // ThresholdAscent only works for rewards in [0..1] so far
+
+      Console.WriteLine("Thompson (Gaussian est variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 1, 1)));
+      Console.WriteLine("Thompson (Gaussian fixed variance)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0, 1, 0.1)));
+      Console.WriteLine("GaussianThompson (compat)"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
+      Console.WriteLine("GaussianThompson"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new GaussianThompsonSamplingPolicy());
+      Console.WriteLine("UCBNormal"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new UCBNormalPolicy());
+      Console.WriteLine("Random"); TestPolicyGaussianUnknownVariance(randSeed, nArms, new RandomPolicy());
+
+    }
+
+
+    [TestMethod]
+    public void ComparePoliciesForBernoulliBandit() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+      var nArms = 20;
+      //Console.WriteLine("Exp3 (gamma=0.01)");
+      //TestPolicyBernoulli(globalRand, nArms, new Exp3Policy(new Random(seedForPolicy), nArms, 1));
+      //Console.WriteLine("Exp3 (gamma=0.05)");
+      //estPolicyBernoulli(globalRand, nArms, new Exp3Policy(new Random(seedForPolicy), nArms, 1));
+      Console.WriteLine("Thompson (Bernoulli)"); TestPolicyBernoulli(randSeed, nArms, new BernoulliThompsonSamplingPolicy());
+      Console.WriteLine("Generic Thompson (Bernoulli)"); TestPolicyBernoulli(randSeed, nArms, new GenericThompsonSamplingPolicy(new BernoulliModel()));
+      Console.WriteLine("Random");
+      TestPolicyBernoulli(randSeed, nArms, new RandomPolicy());
+      Console.WriteLine("UCB1");
+      TestPolicyBernoulli(randSeed, nArms, new UCB1Policy());
+      Console.WriteLine("UCB1Tuned");
+      TestPolicyBernoulli(randSeed, nArms, new UCB1TunedPolicy());
+      Console.WriteLine("UCB1Normal");
+      TestPolicyBernoulli(randSeed, nArms, new UCBNormalPolicy());
+      Console.WriteLine("Eps(0.01)");
+      TestPolicyBernoulli(randSeed, nArms, new EpsGreedyPolicy(0.01));
+      Console.WriteLine("Eps(0.05)");
+      TestPolicyBernoulli(randSeed, nArms, new EpsGreedyPolicy(0.05));
+      //Console.WriteLine("Eps(0.1)");
+      //TestPolicyBernoulli(randSeed, nArms, new EpsGreedyPolicy(0.1));
+      //Console.WriteLine("Eps(0.2)");
+      //TestPolicyBernoulli(randSeed, nArms, new EpsGreedyPolicy(0.2));
+      //Console.WriteLine("Eps(0.5)");
+      //TestPolicyBernoulli(randSeed, nArms, new EpsGreedyPolicy(0.5));
+      Console.WriteLine("UCT(0.1)"); TestPolicyBernoulli(randSeed, nArms, new UCTPolicy(0.1));
+      Console.WriteLine("UCT(0.5)"); TestPolicyBernoulli(randSeed, nArms, new UCTPolicy(0.5));
+      Console.WriteLine("UCT(1)  "); TestPolicyBernoulli(randSeed, nArms, new UCTPolicy(1));
+      Console.WriteLine("UCT(2)  "); TestPolicyBernoulli(randSeed, nArms, new UCTPolicy(2));
+      Console.WriteLine("UCT(5)  "); TestPolicyBernoulli(randSeed, nArms, new UCTPolicy(5));
+      Console.WriteLine("BoltzmannExploration(0.1)"); TestPolicyBernoulli(randSeed, nArms, new BoltzmannExplorationPolicy(0.1));
+      Console.WriteLine("BoltzmannExploration(0.5)"); TestPolicyBernoulli(randSeed, nArms, new BoltzmannExplorationPolicy(0.5));
+      Console.WriteLine("BoltzmannExploration(1)  "); TestPolicyBernoulli(randSeed, nArms, new BoltzmannExplorationPolicy(1));
+      Console.WriteLine("BoltzmannExploration(10) "); TestPolicyBernoulli(randSeed, nArms, new BoltzmannExplorationPolicy(10));
+      Console.WriteLine("BoltzmannExploration(100)"); TestPolicyBernoulli(randSeed, nArms, new BoltzmannExplorationPolicy(100));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.01)"); TestPolicyBernoulli(randSeed, nArms, new ChernoffIntervalEstimationPolicy(0.01));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.05)"); TestPolicyBernoulli(randSeed, nArms, new ChernoffIntervalEstimationPolicy(0.05));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.1) "); TestPolicyBernoulli(randSeed, nArms, new ChernoffIntervalEstimationPolicy(0.1));
+
+      // not applicable to bernoulli rewards
+      //Console.WriteLine("ThresholdAscent(10, 0.01)  "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 10, 0.01));
+      //Console.WriteLine("ThresholdAscent(10, 0.05)  "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 10, 0.05));
+      //Console.WriteLine("ThresholdAscent(10, 0.1)   "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 10, 0.1));
+      //Console.WriteLine("ThresholdAscent(100, 0.01) "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 100, 0.01));
+      //Console.WriteLine("ThresholdAscent(100, 0.05) "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 100, 0.05));
+      //Console.WriteLine("ThresholdAscent(100, 0.1)  "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 100, 0.1));
+      //Console.WriteLine("ThresholdAscent(1000, 0.01)"); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.01));
+      //Console.WriteLine("ThresholdAscent(1000, 0.05)"); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.05));
+      //Console.WriteLine("ThresholdAscent(1000, 0.1) "); TestPolicyBernoulli(globalRand, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.1));
+    }
+
+    [TestMethod]
+    public void ComparePoliciesForGaussianBandit() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+
+      var randSeed = 31415;
+      var nArms = 20;
+      Console.WriteLine("Threshold Ascent (20)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(20, 0.01));
+      Console.WriteLine("Threshold Ascent (100)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(100, 0.01));
+      Console.WriteLine("Threshold Ascent (500)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(500, 0.01));
+      Console.WriteLine("Threshold Ascent (1000)"); TestPolicyGaussian(randSeed, nArms, new ThresholdAscentPolicy(1000, 0.01));
+      Console.WriteLine("Generic Thompson (Gaussian fixed var)"); TestPolicyGaussian(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1)));
+      Console.WriteLine("Generic Thompson (Gaussian unknown var)"); TestPolicyGaussian(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1, 1, 1)));
+      Console.WriteLine("Thompson (Gaussian orig)"); TestPolicyGaussian(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
+      Console.WriteLine("Thompson (Gaussian new)"); TestPolicyGaussian(randSeed, nArms, new GaussianThompsonSamplingPolicy());
+
+      /*
+      Console.WriteLine("Random"); TestPolicyNormal(randSeed, nArms, new RandomPolicy(new Random(seedForPolicy), nArms));
+      Console.WriteLine("UCB1"); TestPolicyNormal(randSeed, nArms, new UCB1Policy(nArms));
+      Console.WriteLine("UCB1Tuned"); TestPolicyNormal(randSeed, nArms, new UCB1TunedPolicy(nArms));
+      Console.WriteLine("UCB1Normal"); TestPolicyNormal(randSeed, nArms, new UCBNormalPolicy(nArms));
+      //Console.WriteLine("Exp3 (gamma=0.01)");
+      //TestPolicyNormal(randSeed, nArms, new Exp3Policy(new Random(seedForPolicy), nArms, 0.01));
+      //Console.WriteLine("Exp3 (gamma=0.05)");
+      //TestPolicyNormal(randSeed, nArms, new Exp3Policy(new Random(seedForPolicy), nArms, 0.05));
+      Console.WriteLine("Eps(0.01)"); TestPolicyNormal(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.01));
+      Console.WriteLine("Eps(0.05)"); TestPolicyNormal(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.05));
+      //Console.WriteLine("Eps(0.1)");
+      //TestPolicyNormal(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.1));
+      //Console.WriteLine("Eps(0.2)");
+      //TestPolicyNormal(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.2));
+      //Console.WriteLine("Eps(0.5)");
+      //TestPolicyNormal(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.5));
+      Console.WriteLine("UCT(0.1)"); TestPolicyNormal(randSeed, nArms, new UCTPolicy(nArms, 0.1));
+      Console.WriteLine("UCT(0.5)"); TestPolicyNormal(randSeed, nArms, new UCTPolicy(nArms, 0.5));
+      Console.WriteLine("UCT(1)  "); TestPolicyNormal(randSeed, nArms, new UCTPolicy(nArms, 1));
+      Console.WriteLine("UCT(2)  "); TestPolicyNormal(randSeed, nArms, new UCTPolicy(nArms, 2));
+      Console.WriteLine("UCT(5)  "); TestPolicyNormal(randSeed, nArms, new UCTPolicy(nArms, 5));
+      Console.WriteLine("BoltzmannExploration(0.1)"); TestPolicyNormal(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 0.1));
+      Console.WriteLine("BoltzmannExploration(0.5)"); TestPolicyNormal(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 0.5));
+      Console.WriteLine("BoltzmannExploration(1)  "); TestPolicyNormal(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 1));
+      Console.WriteLine("BoltzmannExploration(10) "); TestPolicyNormal(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 10));
+      Console.WriteLine("BoltzmannExploration(100)"); TestPolicyNormal(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 100));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.01)"); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.01));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.05)"); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.05));
+      Console.WriteLine("ChernoffIntervalEstimationPolicy(0.1) "); TestPolicyNormal(randSeed, nArms, new ChernoffIntervalEstimationPolicy(nArms, 0.1));      
+      Console.WriteLine("ThresholdAscent(10,0.01)  "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10, 0.01));
+      Console.WriteLine("ThresholdAscent(10,0.05)  "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10, 0.05));
+      Console.WriteLine("ThresholdAscent(10,0.1)   "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10, 0.1));
+      Console.WriteLine("ThresholdAscent(100,0.01) "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 100, 0.01));
+      Console.WriteLine("ThresholdAscent(100,0.05) "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 100, 0.05));
+      Console.WriteLine("ThresholdAscent(100,0.1)  "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 100, 0.1));
+      Console.WriteLine("ThresholdAscent(1000,0.01)"); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.01));
+      Console.WriteLine("ThresholdAscent(1000,0.05)"); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.05));
+      Console.WriteLine("ThresholdAscent(1000,0.1) "); TestPolicyNormal(randSeed, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.1));
+       */
+    }
+
+    [TestMethod]
+    public void ComparePoliciesForGaussianMixtureBandit() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      var randSeed = 31415;
+      var nArms = 20;
+
+      Console.WriteLine("Generic Thompson (Gaussian Mixture)"); TestPolicyGaussianMixture(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianMixtureModel()));
+      // Console.WriteLine("Threshold Ascent (20)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(20, 0.01));
+      // Console.WriteLine("Threshold Ascent (100)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(100, 0.01));
+      // Console.WriteLine("Threshold Ascent (500)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(500, 0.01));
+      // Console.WriteLine("Threshold Ascent (1000)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(1000, 0.01));
+      // Console.WriteLine("Thompson (Gaussian orig)"); TestPolicyGaussianMixture(randSeed, nArms, new GaussianThompsonSamplingPolicy(true));
+      // Console.WriteLine("Thompson (Gaussian new)"); TestPolicyGaussianMixture(randSeed, nArms, new GaussianThompsonSamplingPolicy());
+      // Console.WriteLine("Generic Thompson (Gaussian fixed variance)"); TestPolicyGaussianMixture(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1, 0.1)));
+      // Console.WriteLine("Generic Thompson (Gaussian unknown variance)"); TestPolicyGaussianMixture(randSeed, nArms, new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 1, 1, 1)));
+
+      /*
+      Console.WriteLine("Random"); TestPolicyGaussianMixture(randSeed, nArms, new RandomPolicy(new Random(seedForPolicy), nArms));
+      Console.WriteLine("UCB1"); TestPolicyGaussianMixture(randSeed, nArms, new UCB1Policy(nArms));
+      Console.WriteLine("UCB1Tuned "); TestPolicyGaussianMixture(randSeed, nArms, new UCB1TunedPolicy(nArms));
+      Console.WriteLine("UCB1Normal"); TestPolicyGaussianMixture(randSeed, nArms, new UCBNormalPolicy(nArms));
+      Console.WriteLine("Eps(0.01) "); TestPolicyGaussianMixture(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.01));
+      Console.WriteLine("Eps(0.05) "); TestPolicyGaussianMixture(randSeed, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.05));
+      Console.WriteLine("UCT(1)  "); TestPolicyGaussianMixture(randSeed, nArms, new UCTPolicy(nArms, 1));
+      Console.WriteLine("UCT(2)  "); TestPolicyGaussianMixture(randSeed, nArms, new UCTPolicy(nArms, 2));
+      Console.WriteLine("UCT(5)  "); TestPolicyGaussianMixture(randSeed, nArms, new UCTPolicy(nArms, 5));
+      Console.WriteLine("BoltzmannExploration(1)  "); TestPolicyGaussianMixture(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 1));
+      Console.WriteLine("BoltzmannExploration(10) "); TestPolicyGaussianMixture(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 10));
+      Console.WriteLine("BoltzmannExploration(100)"); TestPolicyGaussianMixture(randSeed, nArms, new BoltzmannExplorationPolicy(new Random(seedForPolicy), nArms, 100));
+
+      Console.WriteLine("ThresholdAscent(10,0.01)  "); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10, 0.01));
+      Console.WriteLine("ThresholdAscent(100,0.01) "); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(nArms, 100, 0.01));
+      Console.WriteLine("ThresholdAscent(1000,0.01)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(nArms, 1000, 0.01));
+      Console.WriteLine("ThresholdAscent(10000,0.01)"); TestPolicyGaussianMixture(randSeed, nArms, new ThresholdAscentPolicy(nArms, 10000, 0.01));
+       */
+    }
+
+
+    private void TestPolicyBernoulli(int randSeed, int nArms, IBanditPolicy policy) {
+      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new BernoulliBandit(banditRandom, nActions));
+    }
+    private void TestPolicyGaussian(int randSeed, int nArms, IBanditPolicy policy) {
+      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new TruncatedNormalBandit(banditRandom, nActions));
+    }
+    private void TestPolicyGaussianMixture(int randSeed, int nArms, IBanditPolicy policy) {
+      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianMixtureBandit(banditRandom, nActions));
+    }
+    private void TestPolicyGaussianUnknownVariance(int randSeed, int nArms, IBanditPolicy policy) {
+      TestPolicy(randSeed, nArms, policy, (banditRandom, nActions) => new GaussianBandit(banditRandom, nActions));
+    }
+
+
+    private void TestPolicy(int randSeed, int nArms, IBanditPolicy policy, Func<Random, int, IBandit> banditFactory) {
+      var maxIt = 1E5;
+      var reps = 10; // independent runs
+      var regretForIteration = new Dictionary<int, List<double>>();
+      var numberOfPullsOfSuboptimalArmsForExp = new Dictionary<int, double>();
+      var numberOfPullsOfSuboptimalArmsForMax = new Dictionary<int, double>();
+      var globalRandom = new Random(randSeed);
+      var banditRandom = new Random(globalRandom.Next()); // bandits must produce the same rewards for each test
+      var policyRandom = new Random(globalRandom.Next());
+
+      // calculate statistics
+      for (int r = 0; r < reps; r++) {
+        var nextLogStep = 1;
+        var b = banditFactory(banditRandom, nArms);
+        var totalRegret = 0.0;
+        var totalPullsOfSuboptimalArmsExp = 0.0;
+        var totalPullsOfSuboptimalArmsMax = 0.0;
+        var actionInfos = Enumerable.Range(0, nArms).Select(_ => policy.CreateActionInfo()).ToArray();
+        for (int i = 0; i <= maxIt; i++) {
+          var selectedAction = policy.SelectAction(policyRandom, actionInfos);
+          var reward = b.Pull(selectedAction);
+          actionInfos[selectedAction].UpdateReward(reward);
+
+          // collect stats
+          if (selectedAction != b.OptimalExpectedRewardArm) totalPullsOfSuboptimalArmsExp++;
+          if (selectedAction != b.OptimalMaximalRewardArm) totalPullsOfSuboptimalArmsMax++;
+          totalRegret += b.OptimalExpectedReward - reward;
+
+          if (i == nextLogStep) {
+            nextLogStep *= 2;
+            if (!regretForIteration.ContainsKey(i)) {
+              regretForIteration.Add(i, new List<double>());
+            }
+            regretForIteration[i].Add(totalRegret / i);
+
+            if (!numberOfPullsOfSuboptimalArmsForExp.ContainsKey(i)) {
+              numberOfPullsOfSuboptimalArmsForExp.Add(i, 0.0);
+            }
+            numberOfPullsOfSuboptimalArmsForExp[i] += totalPullsOfSuboptimalArmsExp;
+
+            if (!numberOfPullsOfSuboptimalArmsForMax.ContainsKey(i)) {
+              numberOfPullsOfSuboptimalArmsForMax.Add(i, 0.0);
+            }
+            numberOfPullsOfSuboptimalArmsForMax[i] += totalPullsOfSuboptimalArmsMax;
+          }
+        }
+      }
+      // print
+      foreach (var p in regretForIteration.Keys.OrderBy(k => k)) {
+        Console.WriteLine("iter {0,8} regret avg {1,7:F5} min {2,7:F5} max {3,7:F5} suboptimal pulls (exp) {4,7:F2} suboptimal pulls (max) {5,7:F2}",
+          p,
+          regretForIteration[p].Average(),
+          regretForIteration[p].Min(),
+          regretForIteration[p].Max(),
+          numberOfPullsOfSuboptimalArmsForExp[p] / (double)reps,
+          numberOfPullsOfSuboptimalArmsForMax[p] / (double)reps
+          );
+      }
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestInstances.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestInstances.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestInstances.cs	(revision 11850)
@@ -0,0 +1,264 @@
+﻿using System;
+using System.Diagnostics;
+using System.Linq;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestInstances {
+    [TestMethod]
+    public void TestGrammarFromString() {
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+  S -> aA | bB
+  A -> a | aA
+  B -> Bb | b
+");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(2, g.TerminalSymbols.Count());
+        Assert.AreEqual(3, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 'a', 'b' }.Contains(s)));
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'A', 'B' }.Contains(s)));
+
+        Assert.AreEqual(2, g.GetAlternatives('S').Count());
+        Assert.AreEqual(2, g.GetAlternatives('A').Count());
+        Assert.AreEqual(2, g.GetAlternatives('B').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "aA"));
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "bB"));
+        Assert.IsTrue(g.GetAlternatives('A').Any(s => s.ToString() == "aA"));
+        Assert.IsTrue(g.GetAlternatives('A').Any(s => s.ToString() == "a"));
+        Assert.IsTrue(g.GetAlternatives('B').Any(s => s.ToString() == "Bb"));
+        Assert.IsTrue(g.GetAlternatives('B').Any(s => s.ToString() == "b"));
+
+        Assert.AreEqual(2, g.MinPhraseLength(new Sequence("S")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
+        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("A")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("A")));
+        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("B")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("B")));
+      }
+
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+  S -> sS
+");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(1, g.TerminalSymbols.Count());
+        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
+
+        Assert.AreEqual(1, g.GetAlternatives('S').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "sS"));
+
+        Assert.AreEqual(short.MaxValue, g.MinPhraseLength(new Sequence("S")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
+      }
+
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+S->sss|sS");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(1, g.TerminalSymbols.Count());
+        Assert.AreEqual(1, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.TerminalSymbols.All(s => new char[] { 's' }.Contains(s)));
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S' }.Contains(s)));
+
+        Assert.AreEqual(2, g.GetAlternatives('S').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "sss"));
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "sS"));
+
+        Assert.AreEqual(3, g.MinPhraseLength(new Sequence("S")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
+        Assert.AreEqual(4, g.MinPhraseLength(new Sequence("sS")));
+        Assert.AreEqual(7, g.MinPhraseLength(new Sequence("sSS")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("sSS")));
+        Assert.AreEqual(3, g.MaxPhraseLength(new Sequence("sss")));
+        Assert.AreEqual(3, g.MinPhraseLength(new Sequence("sss")));
+      }
+
+      {
+        var g = Grammar.FromString(@"
+
+G(S):
+S->T|TS
+T-> a..z
+");
+        Assert.AreEqual('S', g.SentenceSymbol);
+        Assert.AreEqual(26, g.TerminalSymbols.Count());
+        Assert.AreEqual(2, g.NonTerminalSymbols.Count());
+        Assert.IsTrue(g.NonTerminalSymbols.All(s => new char[] { 'S', 'T' }.Contains(s)));
+
+        Assert.AreEqual(2, g.GetAlternatives('S').Count());
+
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "T"));
+        Assert.IsTrue(g.GetAlternatives('S').Any(s => s.ToString() == "TS"));
+
+        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("S")));
+        Assert.AreEqual(short.MaxValue, g.MaxPhraseLength(new Sequence("S")));
+        Assert.AreEqual(1, g.MinPhraseLength(new Sequence("T")));
+        Assert.AreEqual(1, g.MaxPhraseLength(new Sequence("T")));
+      }
+
+    }
+
+    [TestMethod]
+    public void TestRoyalSymbolProblem() {
+      var p = new RoyalSymbolProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1, p.Evaluate("ab"));
+      Assert.AreEqual(0, p.Evaluate("bb"));
+      Assert.AreEqual(2, p.Evaluate("aa"));
+      Assert.AreEqual(3, p.Evaluate("aaa"));
+    }
+
+
+    [TestMethod]
+    public void TestRoyalPairProblem() {
+      var p = new RoyalPairProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1, p.Evaluate("ab"));
+      Assert.AreEqual(0, p.Evaluate("bb"));
+      Assert.AreEqual(0, p.Evaluate("aa"));
+      Assert.AreEqual(0, p.Evaluate("aaa"));
+      Assert.AreEqual(2, p.Evaluate("aba"));
+      Assert.AreEqual(2, p.Evaluate("abba"));
+      Assert.AreEqual(3, p.Evaluate("abab"));
+    }
+
+    [TestMethod]
+    public void TestSantaFeAntProblem() {
+      var p = new SantaFeAntProblem();
+      Console.WriteLine(p.Grammar);
+
+      // one possible optimal solution: if-food-ahead (move) ( left left if-food-ahead (move) (right)) move right
+      Assert.AreEqual(89, p.Evaluate("?(m)(ll?(m)(r))mr"));
+    }
+    [TestMethod]
+    public void TestRoyalTreeProblem() {
+      var p = new RoyalTreeProblem();
+      Console.WriteLine(p.Grammar);
+
+    }
+    [TestMethod]
+    public void TestRoyalRoadProblem() {
+      var p = new RoyalRoadProblem();
+      Console.WriteLine(p.Grammar);
+
+    }
+    [TestMethod]
+    public void TestPalindromeProblem() {
+      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aba"));
+      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("aaba"));
+      Assert.AreEqual("aba", PalindromeProblem.LongestPalindromicSubstring("abaa"));
+      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aaaabaa"));
+      Assert.AreEqual("aabaa", PalindromeProblem.LongestPalindromicSubstring("aabaaaa"));
+      Assert.AreEqual("baaaab", PalindromeProblem.LongestPalindromicSubstring("aabaaaab"));
+
+
+      var p = new PalindromeProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1, p.Evaluate("a"));
+      Assert.AreEqual(2, p.Evaluate("aa"));
+      Assert.AreEqual(3, p.Evaluate("aaa"));
+      Assert.AreEqual(3, p.Evaluate("aba"));
+      Assert.AreEqual(3, p.Evaluate("baba"));
+      Assert.AreEqual(3, p.Evaluate("abab"));
+      Assert.AreEqual(5, p.Evaluate("babab"));
+    }
+    [TestMethod]
+    public void TestHardPalindromeProblem() {
+      var p = new HardPalindromeProblem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(1 + 1, p.Evaluate("a"));
+      Assert.AreEqual(2 + 1, p.Evaluate("aa"));
+      Assert.AreEqual(3 + 1, p.Evaluate("aaa"));
+      Assert.AreEqual(3 + 2, p.Evaluate("aba"));
+      Assert.AreEqual(3 + 2, p.Evaluate("baba"));
+      Assert.AreEqual(3 + 2, p.Evaluate("abab"));
+      Assert.AreEqual(5 + 2, p.Evaluate("babab"));
+      Assert.AreEqual(5 + 3, p.Evaluate("bacab"));
+    }
+
+    [TestMethod]
+    public void TestEvenParityProblem() {
+      var p = new EvenParityProblem();
+      Console.WriteLine(p.Grammar);
+
+      // a | b | c | d | res
+      // 0 | 0 | 0 | 0 | 1
+      // 0 | 0 | 0 | 1 | 0
+      // 0 | 0 | 1 | 0 | 0
+      // 0 | 0 | 1 | 1 | 1
+      // 0 | 1 | 0 | 0 | 0
+      // 0 | 1 | 0 | 1 | 1
+      // 0 | 1 | 1 | 0 | 1
+      // 0 | 1 | 1 | 1 | 0
+      // 1 | 0 | 0 | 0 | 0
+      // 1 | 0 | 0 | 1 | 1
+      // 1 | 0 | 1 | 0 | 1
+      // 1 | 0 | 1 | 1 | 0
+      // 1 | 1 | 0 | 0 | 1
+      // 1 | 1 | 0 | 1 | 0
+      // 1 | 1 | 1 | 0 | 0
+      // 1 | 1 | 1 | 1 | 1
+
+
+      Assert.AreEqual(8, p.Evaluate("a"));
+      Assert.AreEqual(8, p.Evaluate("b"));
+      Assert.AreEqual(8, p.Evaluate("c"));
+      Assert.AreEqual(8, p.Evaluate("d"));
+
+      Assert.AreEqual(8, p.Evaluate("a*b")); // a and b
+      Assert.AreEqual(8, p.Evaluate("a+b")); // a or b
+      Assert.AreEqual(8, p.Evaluate("!a*b+a*!b")); // a xor b
+      Assert.AreEqual(8, p.Evaluate("!(a*b)+(a*!b)")); // a xor b
+      Assert.AreEqual(16, p.Evaluate("a^b^c^d")); // a xor b
+    }
+
+    [TestMethod]
+    public void TestSymbolicRegressionPoly10Problem() {
+      var p = new SymbolicRegressionPoly10Problem();
+      Console.WriteLine(p.Grammar);
+
+      Assert.AreEqual(0.00319925877644673, p.Evaluate("a"), 1.0E-7);
+      Assert.AreEqual(0.00632775454329686, p.Evaluate("b"), 1.0E-7);
+      Assert.AreEqual(0.00569030954291292, p.Evaluate("c"), 1.0E-7);
+      Assert.AreEqual(3.32317092313123E-05, p.Evaluate("d"), 1.0E-7);
+      Assert.AreEqual(0.000562538829174826, p.Evaluate("e"), 1.0E-7);
+      Assert.AreEqual(3.29458942533772E-06, p.Evaluate("f"), 1.0E-7);
+      Assert.AreEqual(0.000193866006166768, p.Evaluate("g"), 1.0E-7);
+      Assert.AreEqual(2.83339004096246E-05, p.Evaluate("h"), 1.0E-7);
+      Assert.AreEqual(0.00291584574914239, p.Evaluate("i"), 1.0E-7);
+      Assert.AreEqual(0.00504038616701691, p.Evaluate("j"), 1.0E-7);
+
+      Assert.AreEqual(0.252718466940018, p.Evaluate("a*b"), 1.0E-7);
+      Assert.AreEqual(0.290635611728845, p.Evaluate("c*d"), 1.0E-7);
+      Assert.AreEqual(0.25737325167716, p.Evaluate("e*f"), 1.0E-7);
+
+      Assert.AreEqual(0.00173739472363473, p.Evaluate("b*c"), 1.0E-7);
+      Assert.AreEqual(3.15450564064128E-05, p.Evaluate("d*e"), 1.0E-7);
+
+      Assert.AreEqual(0.0943358163760454, p.Evaluate("a*g*i"), 1.0E-7);
+      Assert.AreEqual(0.116199534934045, p.Evaluate("c*f*j"), 1.0E-7);
+
+      Assert.AreEqual(0.824522210419616, p.Evaluate("a*b+c*d+e*f"), 1E-7);
+
+
+      Assert.AreEqual(1.0, p.Evaluate("a*b+c*d+e*f+a*g*i+c*f*j"), 1.0E-7);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSequence.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSequence.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSequence.cs	(revision 11850)
@@ -0,0 +1,325 @@
+﻿using System;
+using System.Linq;
+using System.Collections.Generic;
+using System.Globalization;
+using HeuristicLab.Algorithms.Bandits;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestSequence {
+
+    [TestMethod]
+    public void TestCtorAndProperties() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      {
+        var s = new Sequence("A");
+        Assert.AreEqual(1, s.Length);
+        Assert.AreEqual(false, s.IsTerminal);
+        Assert.AreEqual(0, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+      }
+      {
+        var s = new Sequence("AB");
+        Assert.AreEqual(2, s.Length);
+        Assert.AreEqual(false, s.IsTerminal);
+        Assert.AreEqual(0, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+      }
+      {
+        var s = new Sequence("aAB");
+        Assert.AreEqual(3, s.Length);
+        Assert.AreEqual(false, s.IsTerminal);
+        Assert.AreEqual(1, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+      }
+      {
+        var s = new Sequence("aaaaA");
+        Assert.AreEqual(5, s.Length);
+        Assert.AreEqual(false, s.IsTerminal);
+        Assert.AreEqual(4, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+      }
+      {
+        var s = new Sequence("aaaa");
+        Assert.AreEqual(4, s.Length);
+        Assert.AreEqual(true, s.IsTerminal);
+        Assert.AreEqual(-1, s.FirstNonTerminalIndex);
+        try {
+          var nt = s.FirstNonTerminal;
+          Assert.Fail();
+        } catch (IndexOutOfRangeException e) {
+        }
+      }
+      {
+        var s = new Sequence("aaaaA");
+        var t = new Sequence(s);
+        Assert.AreEqual(5, t.Length);
+        Assert.AreEqual(false, t.IsTerminal);
+        Assert.AreEqual(4, t.FirstNonTerminalIndex);
+        Assert.AreEqual('A', t.FirstNonTerminal);
+
+        t.ReplaceAt(0, 1, new Sequence("Z"));
+        Assert.AreEqual(5, t.Length);
+        Assert.AreEqual(false, t.IsTerminal);
+        Assert.AreEqual(0, t.FirstNonTerminalIndex);
+        Assert.AreEqual('Z', t.FirstNonTerminal);
+
+        // s must not be changed
+        Assert.AreEqual(5, s.Length);
+        Assert.AreEqual(false, s.IsTerminal);
+        Assert.AreEqual(4, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+      }
+    }
+
+    [TestMethod]
+    public void TestReplaceAt() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      {
+        var s = new Sequence("A");
+        var t = new Sequence("B");
+
+        s.ReplaceAt(0, 1, t);
+        Assert.AreEqual('B', s.FirstNonTerminal);
+        Assert.AreEqual(1, s.Length);
+      }
+      {
+        var s = new Sequence("A");
+        var t = new Sequence("b");
+
+        s.ReplaceAt(0, 1, t);
+        Assert.AreEqual(-1, s.FirstNonTerminalIndex);
+        Assert.AreEqual(1, s.Length);
+      }
+      {
+        var s = new Sequence("a");
+        var t = new Sequence("B");
+
+        s.ReplaceAt(0, 1, t);
+        Assert.AreEqual('B', s.FirstNonTerminal);
+        Assert.AreEqual(1, s.Length);
+      }
+      {
+        var s = new Sequence("AB");
+        var t = new Sequence("a");
+
+        s.ReplaceAt(0, 1, t);
+        Assert.AreEqual(1, s.FirstNonTerminalIndex);
+        Assert.AreEqual('B', s.FirstNonTerminal);
+        Assert.AreEqual(2, s.Length);
+      }
+      {
+        var s = new Sequence("AB");
+        var t = new Sequence("aa");
+
+        s.ReplaceAt(0, 1, t);
+        Assert.AreEqual(2, s.FirstNonTerminalIndex);
+        Assert.AreEqual('B', s.FirstNonTerminal);
+        Assert.AreEqual(3, s.Length);
+        Assert.AreEqual("aaB", s.ToString());
+      }
+      {
+        var s = new Sequence("AB");
+        var t = new Sequence("bb");
+
+        s.ReplaceAt(1, 1, t);
+        Assert.AreEqual(0, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+        Assert.AreEqual(3, s.Length);
+        Assert.AreEqual("Abb", s.ToString());
+      }
+      {
+        var s = new Sequence("AB");
+        var t = new Sequence("aA");
+
+        s.ReplaceAt(0, 1, t);
+        Assert.AreEqual(1, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+        Assert.AreEqual(3, s.Length);
+        Assert.AreEqual("aAB", s.ToString());
+      }
+      {
+        var s = new Sequence("AaaB");
+        var t = new Sequence("a");
+
+        s.ReplaceAt(0, 3, t);
+        Assert.AreEqual(1, s.FirstNonTerminalIndex);
+        Assert.AreEqual('B', s.FirstNonTerminal);
+        Assert.AreEqual(2, s.Length);
+        Assert.AreEqual("aB", s.ToString());
+      }
+      {
+        var s = new Sequence("AaaB");
+        var t = new Sequence("aAa");
+
+        s.ReplaceAt(0, 3, t);
+        Assert.AreEqual(1, s.FirstNonTerminalIndex);
+        Assert.AreEqual('A', s.FirstNonTerminal);
+        Assert.AreEqual("aAaB", s.ToString());
+      }
+      {
+        var s = new Sequence("aaaA");
+        var t = new Sequence("aaa");
+
+        s.ReplaceAt(3, 1, t);
+        Assert.AreEqual(-1, s.FirstNonTerminalIndex);
+        Assert.AreEqual("aaaaaa", s.ToString());
+      }
+      {
+        var s = new Sequence("aaaA");
+        var t = new Sequence("aaa");
+
+        s.ReplaceAt(1, 3, t);
+        Assert.AreEqual(-1, s.FirstNonTerminalIndex);
+        Assert.AreEqual("aaaa", s.ToString());
+      }
+      {
+        var s = new Sequence("aaaA");
+        var t = new Sequence("aaa");
+
+        s.ReplaceAt(0, 4, t);
+        Assert.AreEqual(-1, s.FirstNonTerminalIndex);
+        Assert.AreEqual("aaa", s.ToString());
+      }
+      {
+        var s = new Sequence("aaaA");
+        var t = new Sequence("aAaAA");
+
+        s.ReplaceAt(0, 4, t);
+        Assert.AreEqual(1, s.FirstNonTerminalIndex);
+        Assert.AreEqual("aAaAA", s.ToString());
+      }
+
+      // testing length checks
+      {
+        var s = new Sequence("aA");
+        var t = new Sequence("aA");
+
+        try {
+          s.ReplaceAt(0, 4, t);
+          Assert.Fail();
+        } catch (ArgumentException) { }
+
+        s.ReplaceAt(0, 2, t); // should work
+
+        try {
+          s.ReplaceAt(0, 3, t);
+          Assert.Fail();
+        } catch (ArgumentException) { }
+
+        try {
+          s.ReplaceAt(1, 2, t);
+          Assert.Fail();
+        } catch (ArgumentException) { }
+
+        s.ReplaceAt(1, 1, new Sequence("A")); // should work
+
+        try {
+          s.ReplaceAt(-1, 2, t);
+          Assert.Fail();
+        } catch (ArgumentException) { }
+
+      }
+    }
+
+    [TestMethod]
+    public void TestSubsequence() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      {
+        var s = new Sequence("AAaaaAA");
+        var sub = s.Subsequence(0, 7);
+
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("AAaaaAA", sub.ToString());
+      }
+      {
+        var s = new Sequence("AAaaaAA");
+        var sub = s.Subsequence(0, 3);
+
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("AAa", sub.ToString());
+      }
+      {
+        var s = new Sequence("AAaaaAA");
+        var sub = s.Subsequence(2, 3);
+
+        Assert.AreEqual(-1, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("aaa", sub.ToString());
+      }
+      {
+        var s = new Sequence("AAaaaAA");
+        var sub = s.Subsequence(2, 4);
+
+        Assert.AreEqual(3, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("aaaA", sub.ToString());
+      }
+      {
+        var s = new Sequence("AAaaaAA");
+        var sub = s.Subsequence(5, 2);
+
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("AA", sub.ToString());
+      }
+      {
+        var s = new Sequence("aaaAA");
+        var sub = s.Subsequence(2, 3);
+
+        Assert.AreEqual(1, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("aAA", sub.ToString());
+      }
+    }
+
+    [TestMethod]
+    public void TestReadonlySequence() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+      {
+        var s = new ReadonlySequence("AAaaaAA");
+        var sub = s.Subsequence(0, 7);
+
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("AAaaaAA", sub.ToString());
+      }
+      {
+        var s = new ReadonlySequence("AAaaaAA");
+        var sub = s.Subsequence(0, 3);
+
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("AAa", sub.ToString());
+
+        sub = sub.Subsequence(1, 2);
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("Aa", sub.ToString());
+      }
+      {
+        var s = new ReadonlySequence("AAaaaAA");
+        var sub = s.Subsequence(2, 3);
+
+        Assert.AreEqual(-1, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("aaa", sub.ToString());
+      }
+      {
+        var s = new ReadonlySequence("AAaaaAA");
+        var sub = s.Subsequence(2, 4);
+
+        Assert.AreEqual(3, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("aaaA", sub.ToString());
+      }
+      {
+        var s = new ReadonlySequence("AAaaaAA");
+        var sub = s.Subsequence(5, 2);
+
+        Assert.AreEqual(0, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("AA", sub.ToString());
+      }
+      {
+        var s = new ReadonlySequence("aaaAA");
+        var sub = s.Subsequence(2, 3);
+
+        Assert.AreEqual(1, sub.FirstNonTerminalIndex);
+        Assert.AreEqual("aAA", sub.ToString());
+      }
+
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSolvers.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSolvers.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSolvers.cs	(revision 11850)
@@ -0,0 +1,131 @@
+﻿using System;
+using HeuristicLab.Algorithms.GrammaticalOptimization;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestSolvers {
+    [TestMethod]
+    public void TestExhaustiveBFS() {
+      {
+        // G(A): A -> l | r | m | ?(A)(A) | lA | rA | mA 
+        var prob = new SantaFeAntProblem();
+        var comb = 3;
+        TestBFS(prob, 1, comb);
+
+        comb = comb * 3 + 3;
+        TestBFS(prob, 2, comb);
+
+        comb = comb * 3 + 3;
+        TestBFS(prob, 3, comb);
+
+        comb = comb * 3 + 3;
+        TestBFS(prob, 4, comb);
+
+        comb = comb * 3 + 3;
+        TestBFS(prob, 5, comb);
+
+        comb = comb * 3 + 3;
+        TestBFS(prob, 6, comb);
+
+        comb = comb * 3 + 3 + (3 * 3); // additionally for ?(A)(A)
+        TestBFS(prob, 7, comb);
+      }
+      {
+        // G(E):
+        // E -> V | V+E | V-E | V*E | V/E | (E)
+        // V -> a .. j 
+        /* grammar has been change ... unit test not yet adapted 
+        var prob = new SymbolicRegressionPoly10Problem();
+        var comb = 10;
+        TestDFS(prob, 1, comb);
+        TestDFS(prob, 2, comb);
+        
+        comb = comb + 10 * 4 * comb + comb;
+        TestDFS(prob, 3, comb);
+        TestDFS(prob, 4, comb);
+        
+        comb = comb + 10 * 4 * comb + 10; // ((E)) 
+        TestDFS(prob, 5, comb);
+        TestDFS(prob, 6, comb);
+        
+        comb = comb + 10 * 4 * comb + 10; // (((E)))  */
+        // takes too long
+        //TestDFS(prob, 7, comb);
+        //TestDFS(prob, 8, comb);
+      }
+    }
+
+    private void TestBFS(IProblem prob, int len, int numExpectedSols) {
+      var solver = new ExhaustiveBreadthFirstSearch(prob, len);
+      int numSols = 0;
+
+      solver.SolutionEvaluated += (s, d) => { numSols++; };
+
+      solver.Run(int.MaxValue);
+      Assert.AreEqual(numExpectedSols, numSols);
+    }
+
+    [TestMethod]
+    public void TestExhaustiveDFS() {
+      {
+        // G(A): A -> l | r | m | ?(A)(A) | lA | rA | mA 
+        var prob = new SantaFeAntProblem();
+        var comb = 3;
+        TestDFS(prob, 1, comb);
+
+        comb = comb * 3 + 3;
+        TestDFS(prob, 2, comb);
+
+        comb = comb * 3 + 3;
+        TestDFS(prob, 3, comb);
+
+        comb = comb * 3 + 3;
+        TestDFS(prob, 4, comb);
+
+        comb = comb * 3 + 3;
+        TestDFS(prob, 5, comb);
+
+        comb = comb * 3 + 3;
+        TestDFS(prob, 6, comb);
+
+        comb = comb * 3 + 3 + (3 * 3); // additionally for ?(A)(A)
+        TestDFS(prob, 7, comb);
+      }
+      {
+        // G(E):
+        // E -> V | V+E | V-E | V*E | V/E | (E)
+        // V -> a .. j 
+        /* grammar has been change ... unit test not yet adapted 
+        var prob = new SymbolicRegressionPoly10Problem();
+        var comb = 10;
+        TestDFS(prob, 1, comb);
+        TestDFS(prob, 2, comb);
+
+        comb = comb + 10 * 4 * comb + comb;
+        TestDFS(prob, 3, comb);
+        TestDFS(prob, 4, comb);
+
+        comb = comb + 10 * 4 * comb + 10; // ((E)) 
+        TestDFS(prob, 5, comb);
+        TestDFS(prob, 6, comb);
+
+        comb = comb + 10 * 4 * comb + 10; // (((E))) */
+        // takes too long
+        //TestDFS(prob, 7, comb);
+        //TestDFS(prob, 8, comb);
+      }
+    }
+
+    private void TestDFS(IProblem prob, int len, int numExpectedSols) {
+      var solver = new ExhaustiveDepthFirstSearch(prob, len);
+      int numSols = 0;
+
+      solver.SolutionEvaluated += (s, d) => { numSols++; Console.WriteLine(s); };
+
+      solver.Run(int.MaxValue);
+      Assert.AreEqual(numExpectedSols, numSols);
+    }
+
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs	(revision 11850)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs	(revision 11850)
@@ -0,0 +1,18 @@
+﻿using System;
+using System.Linq;
+using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  // tests for the brige to the HL symb-reg instances
+  [TestClass]
+  public class TestSymbRegInstances {
+    [TestMethod]
+    public void TestGetDataDescriptors() {
+
+      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
+
+    }
+  }
+}
