Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 11727)
@@ -11,4 +11,6 @@
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.Bandits", "HeuristicLab.Algorithms.Bandits\HeuristicLab.Algorithms.Bandits.csproj", "{24408F7D-EE0F-4886-A08B-EC324D662E47}"
+EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Common", "HeuristicLab.Common\HeuristicLab.Common.csproj", "{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}"
 EndProject
 Global
@@ -38,7 +40,14 @@
 		{24408F7D-EE0F-4886-A08B-EC324D662E47}.Release|Any CPU.ActiveCfg = Release|Any CPU
 		{24408F7D-EE0F-4886-A08B-EC324D662E47}.Release|Any CPU.Build.0 = Release|Any CPU
+		{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}.Release|Any CPU.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
 		HideSolutionNode = FALSE
 	EndGlobalSection
+	GlobalSection(Performance) = preSolution
+		HasPerformanceSessions = true
+	EndGlobalSection
 EndGlobal
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/HeuristicLab.Algorithms.Bandits.csproj	(revision 11727)
@@ -43,4 +43,7 @@
     <Compile Include="Bandits\TruncatedNormalBandit.cs" />
     <Compile Include="Policies\BanditPolicy.cs" />
+    <Compile Include="Policies\BernoulliThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\GaussianThompsonSamplingPolicy.cs" />
+    <Compile Include="Policies\Exp3Policy.cs" />
     <Compile Include="Policies\EpsGreedyPolicy.cs" />
     <Compile Include="Policies\RandomPolicy.cs" />
@@ -51,5 +54,10 @@
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
-  <ItemGroup />
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Common\HeuristicLab.Common.csproj">
+      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
+  </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/IPolicy.cs	(revision 11727)
@@ -6,7 +6,17 @@
 
 namespace HeuristicLab.Algorithms.Bandits {
+  // this interface represents a policy for reinforcement learning
   public interface IPolicy {
-    int SelectAction();
-    void UpdateReward(int action, double reward);
+    IEnumerable<int> Actions { get; }
+    int SelectAction(); // action selection ...
+    void UpdateReward(int action, double reward); // ... and reward update are defined as usual
+
+    // policies must also support disabling of potential actions
+    // for instance if we know that an action in a state has a deterministic 
+    // reward we need to sample it only once
+    // it is necessary to sample an action only once
+    void DisableAction(int action);
+
+    // reset causes the policy to be reinitialized to it's initial state (as after constructor-call)
     void Reset();
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BanditPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -7,12 +8,24 @@
 namespace HeuristicLab.Algorithms.Bandits {
   public abstract class BanditPolicy : IPolicy {
-    public int NumActions { get; private set; }
-    public BanditPolicy(int numActions) {
-      this.NumActions = numActions;
+    public IEnumerable<int> Actions { get; private set; }
+    private readonly int numInitialActions;
+
+    protected BanditPolicy(int numActions) {
+      this.numInitialActions = numActions;
+      Actions = Enumerable.Range(0, numActions).ToArray();
     }
 
     public abstract int SelectAction();
     public abstract void UpdateReward(int action, double reward);
-    public abstract void Reset();
+
+    public virtual void DisableAction(int action) {
+      Debug.Assert(Actions.Contains(action));
+
+      Actions = Actions.Where(a => a != action).ToArray();
+    }
+
+    public virtual void Reset() {
+      Actions = Enumerable.Range(0, numInitialActions).ToArray();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/BernoulliThompsonSamplingPolicy.cs	(revision 11727)
@@ -0,0 +1,58 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class BernoulliThompsonSamplingPolicy : BanditPolicy {
+    private readonly Random random;
+    private readonly int[] success;
+    private readonly int[] failure;
+
+    // parameters of beta prior distribution
+    private readonly double alpha = 1.0;
+    private readonly double beta = 1.0;
+
+    public BernoulliThompsonSamplingPolicy(Random random, int numActions)
+      : base(numActions) {
+      this.random = random;
+      this.success = new int[numActions];
+      this.failure = new int[numActions];
+    }
+
+    public override int SelectAction() {
+      Debug.Assert(Actions.Any());
+      var maxTheta = double.NegativeInfinity;
+      int bestAction = -1;
+      foreach (var a in Actions) {
+        var theta = Rand.BetaRand(random, success[a] + alpha, failure[a] + beta);
+        if (theta > maxTheta) {
+          maxTheta = theta;
+          bestAction = a;
+        }
+      }
+      return bestAction;
+    }
+
+    public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+
+      if (reward > 0) success[action]++;
+      else failure[action]++;
+    }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      success[action] = -1;
+    }
+
+    public override void Reset() {
+      base.Reset();
+      Array.Clear(success, 0, success.Length);
+      Array.Clear(failure, 0, failure.Length);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/EpsGreedyPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -11,36 +12,54 @@
     private readonly int[] tries;
     private readonly double[] sumReward;
+    private readonly RandomPolicy randomPolicy;
+
     public EpsGreedyPolicy(Random random, int numActions, double eps)
       : base(numActions) {
       this.random = random;
       this.eps = eps;
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
+      this.randomPolicy = new RandomPolicy(random, numActions);
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
     }
 
     public override int SelectAction() {
+      Debug.Assert(Actions.Any());
       if (random.NextDouble() > eps) {
         // select best
         var maxReward = double.NegativeInfinity;
         int bestAction = -1;
-        for (int i = 0; i < NumActions; i++) {
-          if (tries[i] == 0) return i;
-          var avgReward = sumReward[i] / tries[i];
+        foreach (var a in Actions) {
+          if (tries[a] == 0) return a;
+          var avgReward = sumReward[a] / tries[a];
           if (maxReward < avgReward) {
             maxReward = avgReward;
-            bestAction = i;
+            bestAction = a;
           }
         }
+        Debug.Assert(bestAction >= 0);
         return bestAction;
       } else {
         // select random
-        return random.Next(NumActions);
+        return randomPolicy.SelectAction();
       }
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+
+      randomPolicy.UpdateReward(action, reward); // does nothing
       tries[action]++;
       sumReward[action] += reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      randomPolicy.DisableAction(action);
+      sumReward[action] = 0;
+      tries[action] = -1;
+    }
+
     public override void Reset() {
+      base.Reset();
+      randomPolicy.Reset();
       Array.Clear(tries, 0, tries.Length);
       Array.Clear(sumReward, 0, sumReward.Length);
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/Exp3Policy.cs	(revision 11727)
@@ -0,0 +1,55 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class Exp3Policy : BanditPolicy {
+    private readonly Random random;
+    private readonly double gamma;
+    private readonly double[] w;
+    // TODO: debug (very large weights over time)
+    public Exp3Policy(Random random, int numActions, double gamma)
+      : base(numActions) {
+      if (gamma < 0 || gamma > 1) throw new ArgumentException();
+      this.random = random;
+      this.gamma = gamma;
+      this.w = Enumerable.Repeat(1.0, numActions).ToArray();
+    }
+
+    public override int SelectAction() {
+      Debug.Assert(Actions.Any());
+      var numActions = Actions.Count();
+      var sumW = w.Sum();
+      var r = random.NextDouble();
+      var sumP = (1 - gamma) * w[0] / sumW + gamma / numActions;
+      int i = 0;
+      while (r > sumP) {
+        i++;
+        sumP += (1 - gamma) * w[i] / sumW + gamma / numActions;
+      }
+      Debug.Assert(i >= 0 && i < numActions);
+      return i;
+    }
+
+    public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+      var numActions = Actions.Count();
+      var p = (1 - gamma) * w[action] / w.Sum() + gamma / numActions;
+      var estReward = reward / p;
+      w[action] = w[action] * Math.Exp(gamma * estReward / numActions);
+    }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      w[action] = 0;
+    }
+
+    public override void Reset() {
+      base.Reset();
+      foreach (var a in Actions) w[a] = 1.0;
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/GaussianThompsonSamplingPolicy.cs	(revision 11727)
@@ -0,0 +1,60 @@
+﻿using System;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.Bandits {
+  public class GaussianThompsonSamplingPolicy : BanditPolicy {
+    private readonly Random random;
+    private readonly double[] sumRewards;
+    private readonly double[] sumSqrRewards;
+    private readonly int[] tries;
+    public GaussianThompsonSamplingPolicy(Random random, int numActions)
+      : base(numActions) {
+      this.random = random;
+      this.sumRewards = new double[numActions];
+      this.sumSqrRewards = new double[numActions];
+      this.tries = new int[numActions];
+    }
+
+
+    public override int SelectAction() {
+      Debug.Assert(Actions.Any());
+      var maxTheta = double.NegativeInfinity;
+      int bestAction = -1;
+      foreach (var a in Actions) {
+        if (tries[a] == 0) return a;
+        var mu = sumRewards[a] / tries[a];
+        var stdDev = Math.Sqrt(sumSqrRewards[a] / tries[a] - Math.Pow(mu, 2));
+        var theta = Rand.RandNormal(random) * stdDev + mu;
+        if (theta > maxTheta) {
+          maxTheta = theta;
+          bestAction = a;
+        }
+      }
+      return bestAction;
+    }
+
+    public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
+
+      sumRewards[action] += reward;
+      sumSqrRewards[action] += reward * reward;
+      tries[action]++;
+    }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      sumRewards[action] = 0;
+      sumSqrRewards[action] = 0;
+      tries[action] = -1;
+    }
+
+    public override void Reset() {
+      base.Reset();
+      Array.Clear(sumRewards, 0, sumRewards.Length);
+      Array.Clear(sumSqrRewards, 0, sumSqrRewards.Length);
+      Array.Clear(tries, 0, tries.Length);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/RandomPolicy.cs	(revision 11727)
@@ -1,11 +1,14 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Algorithms.Bandits {
   public class RandomPolicy : BanditPolicy {
     private readonly Random random;
+
     public RandomPolicy(Random random, int numActions)
       : base(numActions) {
@@ -14,12 +17,11 @@
 
     public override int SelectAction() {
-      return random.Next(NumActions);
+      Debug.Assert(Actions.Any());
+      return Actions.SelectRandom(random);
     }
     public override void UpdateReward(int action, double reward) {
       // do nothing
     }
-    public override void Reset() {
-      // do nothing
-    }
+
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1Policy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -12,6 +13,6 @@
     public UCB1Policy(int numActions)
       : base(numActions) {
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
     }
 
@@ -19,10 +20,10 @@
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      for (int i = 0; i < NumActions; i++) {
-        if (tries[i] == 0) return i;
-        var q = sumReward[i] / tries[i] + Math.Sqrt((2 * Math.Log(totalTries)) / tries[i]);
+      foreach (var a in Actions) {
+        if (tries[a] == 0) return a;
+        var q = sumReward[a] / tries[a] + Math.Sqrt((2 * Math.Log(totalTries)) / tries[a]);
         if (q > bestQ) {
           bestQ = q;
-          bestAction = i;
+          bestAction = a;
         }
       }
@@ -30,9 +31,19 @@
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
       totalTries++;
       tries[action]++;
       sumReward[action] += reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      totalTries -= tries[action];
+      tries[action] = -1;
+      sumReward[action] = 0;
+    }
+
     public override void Reset() {
+      base.Reset();
       totalTries = 0;
       Array.Clear(tries, 0, tries.Length);
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCB1TunedPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -13,7 +14,7 @@
     public UCB1TunedPolicy(int numActions)
       : base(numActions) {
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
-      this.sumSqrReward = new double[NumActions];
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
+      this.sumSqrReward = new double[numActions];
     }
 
@@ -25,12 +26,13 @@
 
     public override int SelectAction() {
+      Debug.Assert(Actions.Any());
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      for (int i = 0; i < NumActions; i++) {
-        if (tries[i] == 0) return i;
-        var q = sumReward[i] / tries[i] + Math.Sqrt((Math.Log(totalTries) / tries[i]) * Math.Min(1.0 / 4, V(i))); // 1/4 is upper bound of bernoulli distributed variable
+      foreach (var a in Actions) {
+        if (tries[a] == 0) return a;
+        var q = sumReward[a] / tries[a] + Math.Sqrt((Math.Log(totalTries) / tries[a]) * Math.Min(1.0 / 4, V(a))); // 1/4 is upper bound of bernoulli distributed variable
         if (q > bestQ) {
           bestQ = q;
-          bestAction = i;
+          bestAction = a;
         }
       }
@@ -38,4 +40,5 @@
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
       totalTries++;
       tries[action]++;
@@ -43,5 +46,15 @@
       sumSqrReward[action] += reward * reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      totalTries -= tries[action];
+      tries[action] = -1;
+      sumReward[action] = 0;
+      sumSqrReward[action] = 0;
+    }
+
     public override void Reset() {
+      base.Reset();
       totalTries = 0;
       Array.Clear(tries, 0, tries.Length);
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Policies/UCBNormalPolicy.cs	(revision 11727)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
 using System.Text;
@@ -13,26 +14,21 @@
     public UCBNormalPolicy(int numActions)
       : base(numActions) {
-      this.tries = new int[NumActions];
-      this.sumReward = new double[NumActions];
-      this.sumSqrReward = new double[NumActions];
+      this.tries = new int[numActions];
+      this.sumReward = new double[numActions];
+      this.sumSqrReward = new double[numActions];
     }
 
-    private double V(int arm) {
-      var s = tries[arm];
-      return sumSqrReward[arm] / s - Math.Pow(sumReward[arm] / s, 2) + Math.Sqrt(2 * Math.Log(totalTries) / s);
-    }
-
-
     public override int SelectAction() {
+      Debug.Assert(Actions.Any());
       int bestAction = -1;
       double bestQ = double.NegativeInfinity;
-      for (int i = 0; i < NumActions; i++) {
-        if (totalTries == 0 || tries[i] == 0 || tries[i] < Math.Ceiling(8 * Math.Log(totalTries))) return i;
-        var avgReward = sumReward[i] / tries[i];
+      foreach (var a in Actions) {
+        if (totalTries == 0 || tries[a] == 0 || tries[a] < Math.Ceiling(8 * Math.Log(totalTries))) return a;
+        var avgReward = sumReward[a] / tries[a];
         var q = avgReward
-          + Math.Sqrt(16 * ((sumSqrReward[i] - tries[i] * Math.Pow(avgReward, 2)) / (tries[i] - 1)) * (Math.Log(totalTries - 1) / tries[i]));
+          + Math.Sqrt(16 * ((sumSqrReward[a] - tries[a] * Math.Pow(avgReward, 2)) / (tries[a] - 1)) * (Math.Log(totalTries - 1) / tries[a]));
         if (q > bestQ) {
           bestQ = q;
-          bestAction = i;
+          bestAction = a;
         }
       }
@@ -40,4 +36,5 @@
     }
     public override void UpdateReward(int action, double reward) {
+      Debug.Assert(Actions.Contains(action));
       totalTries++;
       tries[action]++;
@@ -45,5 +42,15 @@
       sumSqrReward[action] += reward * reward;
     }
+
+    public override void DisableAction(int action) {
+      base.DisableAction(action);
+      totalTries -= tries[action];
+      tries[action] = -1;
+      sumReward[action] = 0;
+      sumSqrReward[action] = 0;
+    }
+
     public override void Reset() {
+      base.Reset();
       totalTries = 0;
       Array.Clear(tries, 0, tries.Length);
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs	(revision 11727)
@@ -0,0 +1,116 @@
+﻿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;
+
+    public AlternativesContextSampler(IProblem problem, int maxLen) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = new Random(31415);
+      this.contextLen = 25;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      InitPolicies(problem.Grammar);
+      for (int i = 0; i < maxIterations; i++) {
+        var sentence = SampleSentence(problem.Grammar);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        DistributeReward(quality);
+
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+
+    private Dictionary<string, IPolicy> ntPolicy;
+    private List<Tuple<string, int>> updateChain;
+    private void InitPolicies(IGrammar grammar) {
+      this.ntPolicy = new Dictionary<string, IPolicy>();
+      this.updateChain = new List<Tuple<string, int>>();
+    }
+
+    private string SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+    }
+
+    public string CompleteSentence(IGrammar g, string phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      while (!done) {
+        int ntIdx; char nt;
+        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+
+        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);
+        string 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 startIdx = Math.Max(0, ntIdx - contextLen);
+          var endIdx = Math.Min(startIdx + contextLen, ntIdx);
+          var lft = phrase.Substring(startIdx, endIdx - startIdx + 1);
+          lft = problem.Hash(lft);
+          if (!ntPolicy.ContainsKey(lft)) {
+            ntPolicy.Add(lft, new UCB1TunedPolicy(g.GetAlternatives(nt).Count()));
+          }
+          var selectedAltIdx = ntPolicy[lft].SelectAction();
+          selectedAlt = alts.ElementAt(selectedAltIdx);
+          updateChain.Add(Tuple.Create(lft, selectedAltIdx));
+        }
+
+        // replace nt with alt
+        phrase = phrase.Remove(ntIdx, 1);
+        phrase = phrase.Insert(ntIdx, selectedAlt);
+
+        done = phrase.All(g.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;
+        ntPolicy[lft].UpdateReward(action, 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/AlternativesSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs	(revision 11727)
@@ -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;
+
+    public AlternativesSampler(IProblem problem, int maxLen) {
+      this.problem = problem;
+      this.maxLen = maxLen;
+      this.random = new Random(31415);
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      InitPolicies(problem.Grammar);
+      for (int i = 0; i < maxIterations; i++) {
+        var sentence = SampleSentence(problem.Grammar);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
+        DistributeReward(quality);
+
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+
+    private Dictionary<char, IPolicy> ntPolicy;
+    private List<Tuple<char, int>> updateChain;
+
+    private void InitPolicies(IGrammar grammar) {
+      this.ntPolicy = new Dictionary<char, IPolicy>();
+      this.updateChain = new List<Tuple<char, int>>();
+      foreach (var nt in grammar.NonTerminalSymbols) {
+        ntPolicy.Add(nt, new EpsGreedyPolicy(random, grammar.GetAlternatives(nt).Count(), 0.1));
+      }
+    }
+
+    private string SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+    }
+
+    public string CompleteSentence(IGrammar g, string phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      while (!done) {
+        int ntIdx; char nt;
+        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+
+        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);
+        string 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 = ntPolicy[nt].SelectAction();
+          selectedAlt = alts.ElementAt(selectedAltIdx);
+          updateChain.Add(Tuple.Create(nt, selectedAltIdx));
+        }
+
+        // replace nt with alt
+        phrase = phrase.Remove(ntIdx, 1);
+        phrase = phrase.Insert(ntIdx, selectedAlt);
+
+        done = phrase.All(g.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;
+        ntPolicy[nt].UpdateReward(action, 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/ExhaustiveBreadthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs	(revision 11727)
@@ -12,10 +12,12 @@
     private readonly int maxLen;
     private readonly Queue<string> bfsQueue = new Queue<string>();
+    private readonly IProblem problem;
 
-    public ExhaustiveBreadthFirstSearch(int maxLen) {
+    public ExhaustiveBreadthFirstSearch(IProblem problem, int maxLen) {
+      this.problem = problem;
       this.maxLen = maxLen;
     }
 
-    public void Run(IProblem problem, int maxIterations) {
+    public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
       bfsQueue.Enqueue(problem.Grammar.SentenceSymbol.ToString());
@@ -24,5 +26,5 @@
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
         var sentence = sentenceEnumerator.Current;
-        var quality = problem.Evaluate(sentence);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -39,6 +41,7 @@
         var phrase = bfsQueue.Dequeue();
 
-        var nt = phrase.First(grammar.IsNonTerminal);
-        var ntIdx = phrase.IndexOf(nt); // TODO perf
+        char nt;
+        int ntIdx;
+        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs	(revision 11727)
@@ -24,5 +24,5 @@
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
         var sentence = sentenceEnumerator.Current;
-        var quality = problem.Evaluate(sentence);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -39,6 +39,7 @@
         var phrase = stack.Pop();
 
-        var nt = phrase.First(grammar.IsNonTerminal);
-        var ntIdx = phrase.IndexOf(nt); // TODO perf
+        char nt;
+        int ntIdx;
+        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj	(revision 11727)
@@ -43,4 +43,7 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="AlternativesSampler.cs" />
+    <Compile Include="AlternativesContextSampler.cs" />
+    <Compile Include="MctsSampler.cs" />
     <Compile Include="ExhaustiveDepthFirstSearch.cs" />
     <Compile Include="ExhaustiveBreadthFirstSearch.cs" />
@@ -49,4 +52,12 @@
   </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.Common\HeuristicLab.Common.csproj">
+      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
       <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs	(revision 11727)
@@ -0,0 +1,145 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Text;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization {
+  public class MctsSampler {
+    private class TreeNode {
+      public int randomTries;
+      public IPolicy policy;
+      public TreeNode[] children;
+      public bool done = false;
+
+      public override string ToString() {
+        return string.Format("Node(random-tries: {0}, done: {1}, policy: {2})", randomTries, done, policy);
+      }
+    }
+
+    public event Action<string, double> FoundNewBestSolution;
+    public event Action<string, double> SolutionEvaluated;
+
+    private readonly int maxLen;
+    private readonly IProblem problem;
+    private readonly Random random;
+    private readonly int randomTries;
+    private readonly Func<int, IPolicy> policyFactory;
+
+    private List<Tuple<TreeNode, int>> updateChain;
+    private TreeNode rootNode;
+
+    public MctsSampler(IProblem problem, int maxLen, Random random) :
+      this(problem, maxLen, random, 10, (numActions) => new EpsGreedyPolicy(random, numActions, 0.1)) {
+
+    }
+
+    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<int, IPolicy> policyFactory) {
+      this.maxLen = maxLen;
+      this.problem = problem;
+      this.random = random;
+      this.randomTries = randomTries;
+      this.policyFactory = policyFactory;
+    }
+
+    public void Run(int maxIterations) {
+      double bestQuality = double.MinValue;
+      InitPolicies();
+      for (int i = 0; !rootNode.done && i < maxIterations; i++) {
+        var sentence = SampleSentence(problem.Grammar);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
+        Debug.Assert(quality >= 0 && quality <= 1.0);
+        DistributeReward(quality);
+
+        RaiseSolutionEvaluated(sentence, quality);
+
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          RaiseFoundNewBestSolution(sentence, quality);
+        }
+      }
+    }
+
+    private void InitPolicies() {
+      this.updateChain = new List<Tuple<TreeNode, int>>();
+      rootNode = new TreeNode();
+    }
+
+    private string SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+    }
+
+    public string CompleteSentence(IGrammar g, string phrase) {
+      if (phrase.Length > maxLen) throw new ArgumentException();
+      if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
+      TreeNode n = rootNode;
+      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      int selectedAltIdx = -1;
+      while (!done) {
+        int ntIdx; char nt;
+        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+
+        int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
+        Debug.Assert(maxLenOfReplacement > 0);
+
+        var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement);
+
+        if (n.randomTries < randomTries) {
+          n.randomTries++;
+          return g.CompleteSentenceRandomly(random, phrase, maxLen);
+        } else if (n.randomTries == randomTries && n.policy == null) {
+          n.policy = policyFactory(alts.Count());
+          n.children = alts.Select(_ => new TreeNode()).ToArray(); // create a new node for each alternative
+        }
+
+        // => select using bandit policy
+        selectedAltIdx = n.policy.SelectAction();
+        string selectedAlt = alts.ElementAt(selectedAltIdx);
+        // replace nt with alt
+        phrase = phrase.Remove(ntIdx, 1);
+        phrase = phrase.Insert(ntIdx, selectedAlt);
+
+        updateChain.Add(Tuple.Create(n, selectedAltIdx));
+
+        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        if (!done) {
+          // prepare for next iteration
+          n = n.children[selectedAltIdx];
+          Debug.Assert(!n.done);
+        }
+      } // while
+
+      // the last node is a leaf node (sentence is done), so we never need to visit this node again
+      n.children[selectedAltIdx].done = true;
+
+      return phrase;
+    }
+
+    private void DistributeReward(double reward) {
+      // iterate in reverse order (bottom up)
+      updateChain.Reverse();
+
+      foreach (var e in updateChain) {
+        var node = e.Item1;
+        var policy = node.policy;
+        var action = e.Item2;
+        policy.UpdateReward(action, reward);
+
+        if (node.children[action].done) node.policy.DisableAction(action);
+        if (node.children.All(c => c.done)) node.done = true;
+      }
+    }
+
+    private void RaiseSolutionEvaluated(string sentence, double quality) {
+      var handler = SolutionEvaluated;
+      if (handler != null) handler(sentence, quality);
+    }
+    private void RaiseFoundNewBestSolution(string sentence, double quality) {
+      var handler = FoundNewBestSolution;
+      if (handler != null) handler(sentence, quality);
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs	(revision 11727)
@@ -0,0 +1,18 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Common {
+  public static class Extensions {
+    public static bool IsAlmost(this double x, double y) {
+      return Math.Abs(x - y) < 1.0e-6;
+    }
+
+    public static T SelectRandom<T>(this IEnumerable<T> xs, Random rand) {
+      var xsArr = xs.ToArray();
+      return xsArr[rand.Next(xsArr.Length)];
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj	(revision 11727)
@@ -0,0 +1,54 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Common</RootNamespace>
+    <AssemblyName>HeuristicLab.Common</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+  </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>
+  </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>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="Extensions.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="Rand.cs" />
+  </ItemGroup>
+  <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/HeuristicLab.Common/Properties/AssemblyInfo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Properties/AssemblyInfo.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Properties/AssemblyInfo.cs	(revision 11727)
@@ -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.Common")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("FH-Hagenberg")]
+[assembly: AssemblyProduct("HeuristicLab.Common")]
+[assembly: AssemblyCopyright("Copyright © FH-Hagenberg 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("756c28a7-4012-4f23-927b-a6baa8eefa40")]
+
+// 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/HeuristicLab.Common/Rand.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Rand.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Rand.cs	(revision 11727)
@@ -0,0 +1,69 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Common {
+  // code from Tom Minka's lightspeed toolbox (random.c)
+  // original copyright: 
+  // Written by Tom Minka
+  // (c) Microsoft Corporation. All rights reserved.
+  public static class Rand {
+
+    /* Returns a sample from Normal(0,1) */
+
+    public static double RandNormal(Random random) {
+      double x, y, radius;
+      /* Generate a random point inside the unit circle */
+      do {
+        x = 2 * random.NextDouble() - 1;
+        y = 2 * random.NextDouble() - 1;
+        radius = (x * x) + (y * y);
+      } while ((radius >= 1.0) || (radius == 0.0));
+      /* Box-Muller formula */
+      radius = Math.Sqrt(-2 * Math.Log(radius) / radius);
+      x *= radius;
+      return x;
+    }
+
+
+    /* Returns a sample from Gamma(a, 1).
+     * For Gamma(a,b), scale the result by b.
+     */
+    private static double GammaRand(Random random, double a) {
+      /* Algorithm:
+       * G. Marsaglia and W.W. Tsang, A simple method for generating gamma
+       * variables, ACM Transactions on Mathematical Software, Vol. 26, No. 3,
+       * Pages 363-372, September, 2000.
+       * http://portal.acm.org/citation.cfm?id=358414
+       */
+      double boost, d, c, v;
+      if (a < 1) {
+        /* boost using Marsaglia's (1961) method: gam(a) = gam(a+1)*U^(1/a) */
+        boost = Math.Exp(Math.Log(random.NextDouble()) / a);
+        a++;
+      } else boost = 1;
+      d = a - 1.0 / 3; c = 1.0 / Math.Sqrt(9 * d);
+      while (true) {
+        double x, u;
+        do {
+          x = RandNormal(random);
+          v = 1 + c * x;
+        } while (v <= 0);
+        v = v * v * v;
+        x = x * x;
+        u = random.NextDouble();
+        if ((u < 1 - .0331 * x * x) ||
+           (Math.Log(u) < 0.5 * x + d * (1 - v + Math.Log(v)))) break;
+      }
+      return (boost * d * v);
+    }
+
+    /* Returns a sample from Beta(a,b) */
+    public static double BetaRand(Random random, double a, double b) {
+      double g = GammaRand(random, a);
+      return g / (g + GammaRand(random, b));
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestBanditPolicies.cs	(revision 11727)
@@ -15,22 +15,28 @@
       var seedForPolicy = globalRand.Next();
       var nArms = 10;
+      //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(globalRand, nArms, new BernoulliThompsonSamplingPolicy(new Random(seedForPolicy), nArms));
       Console.WriteLine("Random");
-      TestPolicyBernoulli(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), 10));
+      TestPolicyBernoulli(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), nArms));
       Console.WriteLine("UCB1");
-      TestPolicyBernoulli(globalRand, nArms, new UCB1Policy(10));
+      TestPolicyBernoulli(globalRand, nArms, new UCB1Policy(nArms));
       Console.WriteLine("UCB1Tuned");
-      TestPolicyBernoulli(globalRand, nArms, new UCB1TunedPolicy(10));
+      TestPolicyBernoulli(globalRand, nArms, new UCB1TunedPolicy(nArms));
       Console.WriteLine("UCB1Normal");
-      TestPolicyBernoulli(globalRand, nArms, new UCBNormalPolicy(10));
+      TestPolicyBernoulli(globalRand, nArms, new UCBNormalPolicy(nArms));
       Console.WriteLine("Eps(0.01)");
-      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.01));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.01));
       Console.WriteLine("Eps(0.05)");
-      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.05));
-      Console.WriteLine("Eps(0.1)");
-      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.1));
-      Console.WriteLine("Eps(0.2)");
-      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.2));
-      Console.WriteLine("Eps(0.5)");
-      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.5));
+      TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.05));
+      //Console.WriteLine("Eps(0.1)");
+      //TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.1));
+      //Console.WriteLine("Eps(0.2)");
+      //TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.2));
+      //Console.WriteLine("Eps(0.5)");
+      //TestPolicyBernoulli(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.5));
     }
     [TestMethod]
@@ -40,22 +46,28 @@
       var seedForPolicy = globalRand.Next();
       var nArms = 10;
+      Console.WriteLine("Thompson (Gaussian)");
+      TestPolicyNormal(globalRand, nArms, new GaussianThompsonSamplingPolicy(new Random(seedForPolicy), nArms));
       Console.WriteLine("Random");
-      TestPolicyNormal(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), 10));
+      TestPolicyNormal(globalRand, nArms, new RandomPolicy(new Random(seedForPolicy), nArms));
       Console.WriteLine("UCB1");
-      TestPolicyNormal(globalRand, nArms, new UCB1Policy(10));
+      TestPolicyNormal(globalRand, nArms, new UCB1Policy(nArms));
       Console.WriteLine("UCB1Tuned");
-      TestPolicyNormal(globalRand, nArms, new UCB1TunedPolicy(10));
+      TestPolicyNormal(globalRand, nArms, new UCB1TunedPolicy(nArms));
       Console.WriteLine("UCB1Normal");
-      TestPolicyNormal(globalRand, nArms, new UCBNormalPolicy(10));
+      TestPolicyNormal(globalRand, nArms, new UCBNormalPolicy(nArms));
+      //Console.WriteLine("Exp3 (gamma=0.01)");
+      //TestPolicyNormal(globalRand, nArms, new Exp3Policy(new Random(seedForPolicy), nArms, 0.01));
+      //Console.WriteLine("Exp3 (gamma=0.05)");
+      //TestPolicyNormal(globalRand, nArms, new Exp3Policy(new Random(seedForPolicy), nArms, 0.05));
       Console.WriteLine("Eps(0.01)");
-      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.01));
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.01));
       Console.WriteLine("Eps(0.05)");
-      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.05));
-      Console.WriteLine("Eps(0.1)");
-      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.1));
-      Console.WriteLine("Eps(0.2)");
-      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.2));
-      Console.WriteLine("Eps(0.5)");
-      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), 10, 0.5));
+      TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.05));
+      //Console.WriteLine("Eps(0.1)");
+      //TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.1));
+      //Console.WriteLine("Eps(0.2)");
+      //TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.2));
+      //Console.WriteLine("Eps(0.5)");
+      //TestPolicyNormal(globalRand, nArms, new EpsGreedyPolicy(new Random(seedForPolicy), nArms, 0.5));
     }
 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSolvers.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSolvers.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/TestSolvers.cs	(revision 11727)
@@ -57,10 +57,10 @@
 
     private void TestBFS(IProblem prob, int len, int numExpectedSols) {
-      var solver = new ExhaustiveBreadthFirstSearch(len);
+      var solver = new ExhaustiveBreadthFirstSearch(prob, len);
       int numSols = 0;
 
       solver.SolutionEvaluated += (s, d) => { numSols++; };
 
-      solver.Run(prob, int.MaxValue);
+      solver.Run(int.MaxValue);
       Assert.AreEqual(numExpectedSols, numSols);
     }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/EvenParityProblem.cs	(revision 11727)
@@ -50,4 +50,8 @@
       return nCorrect;
     }
+
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 11727)
@@ -6,4 +6,5 @@
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
Index: anches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Extensions.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Extensions.cs	(revision 11726)
+++ 	(revision )
@@ -1,18 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public static class Extensions {
-    public static bool IsAlmost(this double x, double y) {
-      return Math.Abs(x - y) < 1.0e-6;
-    }
-
-    public static T SelectRandom<T>(this IEnumerable<T> xs, Random rand) {
-      var xsArr = xs.ToArray();
-      return xsArr[rand.Next(xsArr.Length)];
-    }
-  }
-}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs	(revision 11727)
@@ -8,4 +8,5 @@
 using System.Text.RegularExpressions;
 using System.Xml.Linq;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
@@ -157,5 +158,5 @@
       while (!done) {
         int ntIdx; char nt;
-        FindFirstNonTerminal(phrase, out nt, out ntIdx);
+        FindFirstNonTerminal(this, phrase, out nt, out ntIdx);
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -175,7 +176,7 @@
     }
 
-    private void FindFirstNonTerminal(string phrase, out char nt, out int ntIdx) {
+    public static void FindFirstNonTerminal(IGrammar g, string phrase, out char nt, out int ntIdx) {
       ntIdx = 0;
-      while (ntIdx < phrase.Length && IsTerminal(phrase[ntIdx])) ntIdx++;
+      while (ntIdx < phrase.Length && g.IsTerminal(phrase[ntIdx])) ntIdx++;
       if (ntIdx >= phrase.Length) {
         ntIdx = -1;
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HardPalindromeProblem.cs	(revision 11727)
@@ -39,4 +39,7 @@
     }
 
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj	(revision 11727)
@@ -44,7 +44,7 @@
   <ItemGroup>
     <Compile Include="ExpressionInterpreter.cs" />
-    <Compile Include="Extensions.cs" />
     <Compile Include="Grammar.cs" />
     <Compile Include="EvenParityProblem.cs" />
+    <Compile Include="SentenceSetStatistics.cs" />
     <Compile Include="SymbolicRegressionPoly10Problem.cs" />
     <Compile Include="SantaFeAntProblem.cs" />
@@ -59,4 +59,10 @@
     <Compile Include="RoyalTreeProblem.cs" />
   </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Common\HeuristicLab.Common.csproj">
+      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
+  </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs	(revision 11727)
@@ -9,4 +9,5 @@
     IGrammar Grammar { get; }
     double Evaluate(string sentence);
+    string Hash(string terminalPhrase);
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/PalindromeProblem.cs	(revision 11727)
@@ -79,4 +79,8 @@
       return result.ToString();
     }
+
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPairProblem.cs	(revision 11727)
@@ -33,4 +33,8 @@
       return regex.Matches(sentence).Count;
     }
+
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalRoadProblem.cs	(revision 11727)
@@ -29,4 +29,7 @@
       throw new NotImplementedException();
     }
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
 
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSymbolProblem.cs	(revision 11727)
@@ -33,4 +33,8 @@
       return regex.Matches(sentence).Count;
     }
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
+
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalTreeProblem.cs	(revision 11727)
@@ -29,4 +29,7 @@
       throw new NotImplementedException();
     }
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase;
+    }
 
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs	(revision 11727)
@@ -96,4 +96,8 @@
         p++;
       }
+    }
+
+    public string Hash(string terminalPhrase) {
+      return terminalPhrase.Replace("rl", "").Replace("lr", "");
     }
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs	(revision 11727)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs	(revision 11727)
@@ -0,0 +1,48 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization {
+  public class SentenceSetStatistics {
+    public int NumberOfSentences { get; private set; }
+    public string BestSentence { get; private set; }
+    public string FirstSentence { get; private set; }
+    public string LastSentence { get; private set; }
+    public double BestSentenceQuality { get; private set; }
+    public double FirstSentenceQuality { get; private set; }
+    public double LastSentenceQuality { get; private set; }
+    public double AverageQuality { get { return sumQualities / NumberOfSentences; } }
+    // public double MedianQuality { get; private set; }
+    private double sumQualities;
+
+    public void AddSentence(string sentence, double quality) {
+      if (NumberOfSentences == 0) {
+        FirstSentence = sentence;
+        FirstSentenceQuality = quality;
+      }
+
+      if (quality > BestSentenceQuality) {
+        BestSentence = sentence;
+        BestSentenceQuality = quality;
+      }
+
+      sumQualities += quality;
+      NumberOfSentences++;
+
+      LastSentence = sentence;
+      LastSentenceQuality = quality;
+    }
+
+    public override string ToString() {
+      return
+        string.Format("Sentences: {0,10} avg.-quality {1,7:F5} best {2,7:F5} {3} first {4,7:F5} {5} last {6,7:F5} {7}",
+      NumberOfSentences, AverageQuality,
+      BestSentenceQuality, BestSentence,
+      FirstSentenceQuality, FirstSentence,
+      LastSentenceQuality, LastSentence
+     );
+    }
+  }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs	(revision 11727)
@@ -5,12 +5,17 @@
 using System.Security.AccessControl;
 using System.Text;
+using HeuristicLab.Common;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization {
   public class SymbolicRegressionPoly10Problem : IProblem {
+    //    private const string grammarString = @"
+    //    G(E):
+    //    E -> V | V+E | V-E | V*E | (E)
+    //    V -> a .. j 
+    //    ";
     private const string grammarString = @"
-G(E):
-E -> V | V+E | V-E | V*E | V/E | (E)
-V -> a .. j 
-";
+    G(E):
+    E -> a | b | c | d | e | f | g | h | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | j*E 
+    ";
 
 
@@ -82,4 +87,12 @@
       return s * s / (ssX * ssY);
     }
+
+
+    // right now only + and * is supported
+    public string Hash(string terminalPhrase) {
+      var terms = terminalPhrase.Split('+');
+      return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))
+        .OrderBy(term => term));
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj	(revision 11727)
@@ -49,4 +49,8 @@
   </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>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11726)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 11727)
@@ -1,7 +1,10 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Data;
 using System.Diagnostics;
 using System.Linq;
 using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
 using HeuristicLab.Problems.GrammaticalOptimization;
@@ -10,4 +13,69 @@
   class Program {
     static void Main(string[] args) {
+      // RunDemo();
+      RunGridTest();
+    }
+
+    private static void RunGridTest() {
+      int maxIterations = 150000;
+      var globalRandom = new Random(31415);
+      var reps = 10;
+      Parallel.ForEach(new int[] { 1, 5, 10, 100, 500, 1000 }, (randomTries) => {
+        Random localRand;
+        lock (globalRandom) {
+          localRand = new Random(globalRandom.Next());
+        }
+        var policyFactories = new Func<int, IPolicy>[]
+        {
+          (numActions) => new RandomPolicy(localRand, numActions), 
+          (numActions) => new UCB1Policy(numActions), 
+          (numActions) => new UCB1TunedPolicy(numActions), 
+          (numActions) => new UCBNormalPolicy(numActions), 
+          (numActions) => new EpsGreedyPolicy(localRand, numActions, 0.01), 
+          (numActions) => new EpsGreedyPolicy(localRand, numActions, 0.05), 
+          (numActions) => new EpsGreedyPolicy(localRand, numActions, 0.1), 
+          (numActions) => new EpsGreedyPolicy(localRand, numActions, 0.2), 
+          (numActions) => new EpsGreedyPolicy(localRand, numActions, 0.5), 
+          (numActions) => new GaussianThompsonSamplingPolicy(localRand, numActions), 
+          (numActions) => new BernoulliThompsonSamplingPolicy(localRand, numActions)
+        };
+
+        foreach (var policyFactory in policyFactories)
+          for (int i = 0; i < reps; i++) {
+            int iterations = 0;
+            var sw = new Stopwatch();
+            var globalStatistics = new SentenceSetStatistics();
+
+            // var problem = new SymbolicRegressionPoly10Problem();
+            var problem = new SantaFeAntProblem();
+            //var problem = new PalindromeProblem();
+            //var problem = new HardPalindromeProblem();
+            //var problem = new RoyalPairProblem();
+            //var problem = new EvenParityProblem();
+            var alg = new MctsSampler(problem, 17, localRand, randomTries, policyFactory);
+            //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
+            //var alg = new AlternativesContextSampler(problem, 25);
+
+            alg.SolutionEvaluated += (sentence, quality) => {
+              iterations++;
+              globalStatistics.AddSentence(sentence, quality);
+              if (iterations % 10000 == 0) {
+                Console.WriteLine("{0} {1} {2}", randomTries, policyFactory(1), globalStatistics);
+              }
+            };
+
+            sw.Start();
+
+            alg.Run(maxIterations);
+
+            sw.Stop();
+          }
+      });
+    }
+
+    private static void RunDemo() {
+      // TODO: implement threshold ascent
+      // TODO: implement inspection for MCTS
+
       int maxIterations = 10000000;
       int iterations = 0;
@@ -15,16 +83,28 @@
       double bestQuality = 0;
       string bestSentence = "";
+      var globalStatistics = new SentenceSetStatistics();
+      var random = new Random(31415);
 
-      var rs = new ExhaustiveDepthFirstSearch(17);
+      // var problem = new SymbolicRegressionPoly10Problem();
+      var problem = new SantaFeAntProblem();
+      //var problem = new PalindromeProblem();
+      //var problem = new HardPalindromeProblem();
+      //var problem = new RoyalPairProblem();
+      //var problem = new EvenParityProblem();
+      var alg = new MctsSampler(problem, 17, random);
+      //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
+      //var alg = new AlternativesContextSampler(problem, 25);
 
-      rs.FoundNewBestSolution += (sentence, quality) => {
+      alg.FoundNewBestSolution += (sentence, quality) => {
         bestQuality = quality;
         bestSentence = sentence;
         Console.WriteLine("{0,10} {1,10:F5} {2,10:F5} {3}", iterations, bestQuality, quality, sentence);
       };
-      rs.SolutionEvaluated += (sentence, quality) => {
+      alg.SolutionEvaluated += (sentence, quality) => {
         iterations++;
+        globalStatistics.AddSentence(sentence, quality);
         if (iterations % 10000 == 0) {
-          Console.WriteLine("{0,10} {1,10:F5} {2,10:F5} {3}", iterations, bestQuality, quality, sentence);
+          //Console.WriteLine("{0,10} {1,10:F5} {2,10:F5} {3}", iterations, bestQuality, quality, sentence);
+          Console.WriteLine(globalStatistics.ToString());
         }
       };
@@ -33,5 +113,5 @@
       sw.Start();
 
-      rs.Run(new SymbolicRegressionPoly10Problem(), maxIterations);
+      alg.Run(maxIterations);
 
       sw.Stop();
