Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj	(revision 12923)
@@ -155,6 +155,6 @@
   <ItemGroup>
     <Compile Include="Interfaces\IStateFunction.cs" />
-    <Compile Include="Interfaces\IQualityFunction.cs" />
-    <Compile Include="Interfaces\ITabularQualityFunction.cs" />
+    <Compile Include="Interfaces\IStateValueFunction.cs" />
+    <Compile Include="Interfaces\ITabularStateValueFunction.cs" />
     <Compile Include="Interfaces\ISymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="IteratedSymbolicExpressionConstruction.cs" />
@@ -169,7 +169,7 @@
     </Compile>
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="QualityFunctions\TabularQualityFunctionBase.cs" />
-    <Compile Include="QualityFunctions\TabularAvgQualityFunction.cs" />
-    <Compile Include="QualityFunctions\TabularMaxQualityFunction.cs" />
+    <Compile Include="QualityFunctions\TabularStateValueFunctionBase.cs" />
+    <Compile Include="QualityFunctions\TabularAvgStateValueFunction.cs" />
+    <Compile Include="QualityFunctions\TabularMaxStateValueFunction.cs" />
     <Compile Include="SearchTree.cs" />
     <Compile Include="StateFunctions\ParentChildStateFunction.cs" />
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IQualityFunction.cs	(revision 12922)
+++ 	(revision )
@@ -1,15 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Core;
-
-namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
-  // maps a state action pair to a quality
-  public interface IQualityFunction : IStatefulItem {
-    double Q(object state, int action);
-    void Update(object state, int action, double observedQuality);
-    IStateFunction StateFunction { get; }
-  }
-}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateFunction.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateFunction.cs	(revision 12923)
@@ -10,5 +10,5 @@
   // creates a state from the information available at sequential derivation steps of symbolic expression trees
   public interface IStateFunction : IItem {
-    object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parentNode, int childIdx);
+    object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parentNode, int childIdx);
   }
 }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateValueFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateValueFunction.cs	(revision 12923)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/IStateValueFunction.cs	(revision 12923)
@@ -0,0 +1,15 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Core;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  // represents the state value function (V(s))
+  public interface IStateValueFunction : IStatefulItem {
+    double Value(object state);
+    void Update(object state, double observedQuality);
+    IStateFunction StateFunction { get; }
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ISymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ISymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ISymbolicExpressionConstructionPolicy.cs	(revision 12923)
@@ -9,6 +9,6 @@
   public interface ISymbolicExpressionConstructionPolicy : IItem {
     void Initialize(SymbolicExpressionTreeProblem problem, IRandom random);
-    ISymbolicExpressionTree Sample(out IEnumerable<Tuple<object, int>> stateActionSequence);
-    void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality);
+    ISymbolicExpressionTree Sample(out IEnumerable<object> stateSequence);
+    void Update(IEnumerable<object> stateSequence, double quality);
   }
 }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularQualityFunction.cs	(revision 12922)
+++ 	(revision )
@@ -1,14 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
-
-namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
-  // maps a state action pair to a quality
-  // represents quality functions that use a table representation for states & actions and can therefore return the number of tries for each state/action pair
-  public interface ITabularQualityFunction : IQualityFunction {
-    double QVariance(object state, int action); // estimate for the variance of observed rewards
-    int Tries(object state, int action);
-  }
-}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularStateValueFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularStateValueFunction.cs	(revision 12923)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Interfaces/ITabularStateValueFunction.cs	(revision 12923)
@@ -0,0 +1,13 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  // represents state value functions that use a table representation for states and can therefore return the number of visits to each state
+  public interface ITabularStateValueFunction : IStateValueFunction {
+    double ValueVariance(object state); // estimate for the variance of observed rewards in a state
+    int Tries(object state);
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/IteratedSymbolicExpressionConstruction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/IteratedSymbolicExpressionConstruction.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/IteratedSymbolicExpressionConstruction.cs	(revision 12923)
@@ -147,12 +147,4 @@
       random.Reset(Seed);
 
-      //var policy = new RandomSymbolicExpressionConstructionPolicy(Problem, random);
-      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy<string>(Problem, random, new TabularMaxQualityFunction<string>(new DefaultStateFunction()));
-      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy(Problem, random, new TabularAvgQualityFunction<string>(new DefaultStateFunction()));
-      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy(Problem, random, new TabularMaxQualityFunction<string>(new ParentChildStateFunction()));
-      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy(Problem, random, new TabularAvgQualityFunction<string>(new ParentChildStateFunction()));
-      //var policy = new UcbSymbolicExpressionConstructionPolicy<string>(Problem, random, new TabularMaxQualityFunction<string>(new DefaultStateFunction()));
-      //var policy = new UcbWithStateAggregationSymbolicExpressionConstructionPolicy(Problem, random, 40);
-
       var policy = PolicyParameter.Value;
       policy.Initialize(Problem, random);
@@ -186,37 +178,43 @@
       double sumQuality = 0; // for average quality calculation
       int resultUpdateInterval = ResultUpdateInterval;
-      while (evals < MaximumEvaluations) {
-        double quality = double.NaN;
-        ISymbolicExpressionTree tree = null;
-        IEnumerable<Tuple<object, int>> actionSequence;
-        tree = policy.Sample(out actionSequence);
-        quality = Problem.Evaluate(tree, random);
-        evals++;
-        sumQuality += quality;
-
-        policy.Update(actionSequence, quality);
-
-        // update statistics results in regular update intervals
-        if ((evals - 1) % resultUpdateInterval == resultUpdateInterval - 1) {
-          evaluations.Value = evals;
-          bestQualityRow.Values.Add(bestQuality.Value);
-          currentQualityRow.Values.Add(sumQuality / (double)resultUpdateInterval);
-          sumQuality = 0;
+      try {
+        while (evals < MaximumEvaluations) {
+          double quality = double.NaN;
+          ISymbolicExpressionTree tree = null;
+          IEnumerable<object> stateSequence;
+          tree = policy.Sample(out stateSequence);
+          quality = Problem.Evaluate(tree, random);
+          evals++;
+          sumQuality += quality;
+
+          policy.Update(stateSequence, quality);
+          cancellationToken.ThrowIfCancellationRequested();
+
+          // update statistics results in regular update intervals
+          if ((evals - 1) % resultUpdateInterval == resultUpdateInterval - 1) {
+            evaluations.Value = evals;
+            bestQualityRow.Values.Add(bestQuality.Value);
+            currentQualityRow.Values.Add(sumQuality / (double)resultUpdateInterval);
+            sumQuality = 0;
+          }
+
+          // update best solution results whenever a new better solution is found
+          if (Problem.IsBetter(quality, bestQuality.Value)) {
+            bestQuality.Value = quality;
+            bestFoundOnEvaluation.Value = evals;
+
+            // for problem-specific analyzer
+            solutions[0] = tree;
+            qualities[0] = quality;
+          }
+
+          // run problem-specific analyzer in each iteration
+          Problem.Analyze(solutions, qualities, Results, random);
         }
-
-        // update best solution results whenever a new better solution is found
-        if (Problem.IsBetter(quality, bestQuality.Value)) {
-          bestQuality.Value = quality;
-          bestFoundOnEvaluation.Value = evals;
-
-          // for problem-specific analyzer
-          solutions[0] = tree;
-          qualities[0] = quality;
-        }
-
-        // run problem-specific analyzer in each iteration
-        Problem.Analyze(solutions, qualities, Results, random);
-
-        cancellationToken.ThrowIfCancellationRequested();
+      } finally {
+        // update stats whenever the alg is stopped
+        evaluations.Value = evals;
+        bestQualityRow.Values.Add(bestQuality.Value);
+        currentQualityRow.Values.Add(sumQuality / (double)resultUpdateInterval);
       }
     }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs	(revision 12923)
@@ -20,9 +20,9 @@
     }
 
-    public ITabularQualityFunction QualityFunction {
+    public ITabularStateValueFunction StateValueFunction {
       get {
-        return ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value;
+        return ((IValueParameter<ITabularStateValueFunction>)Parameters["Quality function"]).Value;
       }
-      set { ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value = value; }
+      set { ((IValueParameter<ITabularStateValueFunction>)Parameters["Quality function"]).Value = value; }
     }
 
@@ -39,39 +39,36 @@
       : base() {
       Parameters.Add(new FixedValueParameter<DoubleValue>("Beta", "The weighting factor beta", new DoubleValue(1.0)));
-      Parameters.Add(new ValueParameter<ITabularQualityFunction>("Quality function", "The quality function to use", new TabularAvgQualityFunction()));
+      Parameters.Add(new ValueParameter<ITabularStateValueFunction>("Quality function", "The quality function to use", new TabularAvgStateValueFunction()));
     }
 
-    protected sealed override int Select(object state, IEnumerable<int> actions, IRandom random) {
-
+    protected sealed override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      var idxs = Enumerable.Range(0, followStates.Count);
       // find best action
-      var bestActions = new List<int>();
       var bestQuality = double.NegativeInfinity;
-      if (actions.Any(a => QualityFunction.Tries(state, a) == 0)) {
-        return actions.Where(a => QualityFunction.Tries(state, a) == 0).SampleRandom(random, 1).First();
+      if (followStates.Any(s => StateValueFunction.Tries(s) == 0)) {
+        return idxs.Where(idx => StateValueFunction.Tries(followStates[idx]) == 0).SampleRandom(random);
       }
 
       // windowing
-      var max = actions.Select(a => QualityFunction.Q(state, a)).Max();
-      var min = actions.Select(a => QualityFunction.Q(state, a)).Min();
+      var max = followStates.Select(s => StateValueFunction.Value(s)).Max();
+      var min = followStates.Select(s => StateValueFunction.Value(s)).Min();
       double range = max - min;
-      if (range.IsAlmost(0.0)) return actions.SampleRandom(random, 1).First();
+      if (range.IsAlmost(0.0)) return idxs.SampleRandom(random);
 
-      var w = from a in actions
-              select Math.Exp(Beta * (QualityFunction.Q(state, a) - min) / range);
+      var w = from s in followStates
+              select Math.Exp(Beta * (StateValueFunction.Value(s) - min) / range);
 
-      return actions.SampleProportional(random, 1, w).First();
+      return idxs.SampleProportional(random, 1, w).First();
 
     }
 
-    public sealed override void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality) {
-      foreach (var t in stateActionSequence) {
-        var state = t.Item1;
-        var action = t.Item2;
-        QualityFunction.Update(state, action, quality);
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+      foreach (var state in stateSequence) {
+        StateValueFunction.Update(state, quality);
       }
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return QualityFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/EpsGreedySymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/EpsGreedySymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/EpsGreedySymbolicExpressionConstructionPolicy.cs	(revision 12923)
@@ -20,9 +20,9 @@
     }
 
-    public IQualityFunction QualityFunction {
+    public IStateValueFunction StateValueFunction {
       get {
-        return ((IValueParameter<IQualityFunction>)Parameters["Quality function"]).Value;
+        return ((IValueParameter<IStateValueFunction>)Parameters["Quality function"]).Value;
       }
-      set { ((IValueParameter<IQualityFunction>)Parameters["Quality function"]).Value = value; }
+      set { ((IValueParameter<IStateValueFunction>)Parameters["Quality function"]).Value = value; }
     }
 
@@ -30,39 +30,38 @@
       : base() {
       Parameters.Add(new FixedValueParameter<DoubleValue>("Eps", "The fraction of random pulls", new PercentValue(0.1, true)));
-      Parameters.Add(new ValueParameter<IQualityFunction>("Quality function", "The quality function to use", new TabularAvgQualityFunction()));
+      Parameters.Add(new ValueParameter<IStateValueFunction>("Quality function", "The quality function to use", new TabularAvgStateValueFunction()));
     }
 
-    protected override int Select(object state, IEnumerable<int> actions, IRandom random) {
+    protected override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      var idxs = Enumerable.Range(0, followStates.Count);
       if (random.NextDouble() < Eps) {
-        return actions.SampleRandom(random, 1).First();
+        return idxs.SampleRandom(random);
       }
 
       // find best action
-      var bestActions = new List<int>();
+      var bestFollowStates = new List<int>();
       var bestQuality = double.NegativeInfinity;
-      foreach (var a in actions) {
-        double quality = QualityFunction.Q(state, a);
+      for (int idx = 0; idx < followStates.Count; idx++) {
+        double quality = StateValueFunction.Value(followStates[idx]);
 
         if (quality >= bestQuality) {
           if (quality > bestQuality) {
-            bestActions.Clear();
+            bestFollowStates.Clear();
             bestQuality = quality;
           }
-          bestActions.Add(a);
+          bestFollowStates.Add(idx);
         }
       }
-      return bestActions.SampleRandom(random, 1).First();
+      return bestFollowStates.SampleRandom(random);
     }
 
-    public override void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality) {
-      foreach (var t in stateActionSequence) {
-        var state = t.Item1;
-        var action = t.Item2;
-        QualityFunction.Update(state, action, quality);
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+      foreach (var state in stateSequence) {
+        StateValueFunction.Update(state, quality);
       }
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return QualityFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/RandomSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/RandomSymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/RandomSymbolicExpressionConstructionPolicy.cs	(revision 12923)
@@ -17,13 +17,15 @@
     }
 
-    protected override int Select(object state, IEnumerable<int> actions, IRandom random) {
-      return actions.SampleRandom(random, 1).First();
+    protected override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      var idxs = Enumerable.Range(0, followStates.Count);
+      return idxs.SampleRandom(random);
     }
 
-    public override void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality) {
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+
       // ignore
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
       return null; // doesn't use state information
     }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs	(revision 12923)
@@ -21,5 +21,5 @@
     [Storable]
     public IRandom Random { get; private set; }
-    private SearchTree searchTree;
+    private SearchTree<ISymbol> searchTree; // tree of replacement symbols
 
     private class Slot {
@@ -31,5 +31,5 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      searchTree = new SearchTree();
+      searchTree = new SearchTree<ISymbol>();
     }
     protected SymbolicExpressionConstructionPolicyBase(SymbolicExpressionConstructionPolicyBase original, Cloner cloner)
@@ -39,5 +39,5 @@
 
       // search tree is not cloned or stored
-      searchTree = new SearchTree();
+      searchTree = new SearchTree<ISymbol>();
     }
 
@@ -52,9 +52,9 @@
       this.Problem = problem;
       this.Random = random;
-      this.searchTree = new SearchTree(); // represents all realized actionSequences as a prefix tree 
+      this.searchTree = new SearchTree<ISymbol>(); // represents all realized actionSequences as a prefix tree 
     }
 
-    public ISymbolicExpressionTree Sample(out IEnumerable<Tuple<object, int>> stateActionSequence) {
-      var actions = new List<int>();
+    public ISymbolicExpressionTree Sample(out IEnumerable<object> stateSequence) {
+      var actions = new List<ISymbol>();
       var states = new List<object>();
 
@@ -67,5 +67,5 @@
 
       Contract.Assert(Problem.Encoding.FunctionDefinitions == 0);
-      openSlots.Push(new Slot() { parent = root, childIdx = 0, minSize = 2 }); // at least two nodes are necessary below root
+      openSlots.Push(new Slot() { parent = root, childIdx = 0, minSize = g.GetMinimumExpressionLength(root.Symbol) - 1 }); // at least two nodes are necessary below root
 
       // tree size lower bound is the current tree size + the sum of the minimal size for all open slots
@@ -79,64 +79,85 @@
         var childIdx = next.childIdx;
 
-        // states might be defined differently be different policies
-        // this allows policies to calculate the state as a function of the current tree and the position where it is changed,
-        // or as a function of the list of actions so far, 
-        // or as a function of both
-        var currentState = CreateState(root, actions, parent, childIdx);
-        states.Add(currentState);
+        if (searchTree.IsLeafNode()) {
+          var allowedChildSymbols = g.GetAllowedChildSymbols(parent.Symbol, childIdx)
+            .Where(a => a.Enabled)
+            .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen);
 
-
-        // TODO: only filter the first time later use info from search tree
-        var alts = g.GetAllowedChildSymbols(parent.Symbol, childIdx)
-          .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen)
-          .ToArray();
-
-        if (searchTree.IsLeafNode()) {
-          searchTree.ExpandCurrentNode(alts);
+          searchTree.ExpandCurrentNode(allowedChildSymbols);
         }
 
-        if (!searchTree.PossibleActions.Any()) {
+        if (!searchTree.ChildValues.Any()) {
           throw new InvalidProgramException(string.Format("Couldn't construct a valid tree of maximum length {0} or all possible trees have been visited", maxLen));
         }
 
-        // select a symbol randomly for the child 
-        // select random alternative
-        var selectedIdx = Select(currentState, searchTree.PossibleActions, Random);
-        actions.Add(selectedIdx);
+        var alternatives = searchTree.ChildValues.ToArray(); // TODO perf
 
-        // and add child node to parent
-        var childNode = alts[selectedIdx].CreateTreeNode();
-        if (childNode.HasLocalParameters) {
-          throw new NotSupportedException("Symbols with parameters are not supported by construction policies for symbolic expressions. Try to reformulate the problem so that only discrete actions are necessary");
-          // childNode.ResetLocalParameters(Random);
+        // generate follow states
+        var followStates = new object[alternatives.Length];
+        for (int i = 0; i < followStates.Length; i++) {
+          // temporarily make the replacement and create the followState object
+          var childNode = alternatives[i].CreateTreeNode();
+          if (childNode.HasLocalParameters) {
+            throw new NotSupportedException("Symbols with parameters are not supported by construction policies for symbolic expressions. " +
+                                            "Try to reformulate the problem so that only discrete actions are necessary");
+            // childNode.ResetLocalParameters(Random);
+          }
+          parent.AddSubtree(childNode);
+          actions.Add(alternatives[i]);
+
+          // states might be defined differently be different policies
+          // this allows policies to calculate the state as a function of the current tree and the position where it is changed,
+          // or as a function of the list of actions so far, 
+          // or as a function of both
+          followStates[i] = CreateState(root, actions, parent, childIdx);
+
+          // roll back the change
+          parent.RemoveSubtree(parent.SubtreeCount - 1);
+          actions.RemoveAt(actions.Count - 1);
         }
 
-        Contract.Assert(parent.SubtreeCount == childIdx);
-        parent.AddSubtree(childNode); // enforce left-canonical derivation
-        treeSize++;
+        // select one of the follow states and prepare for the next step
+        var selectedIdx = Select(followStates, Random);
+        actions.Add(alternatives[selectedIdx]);
+        states.Add(followStates[selectedIdx]);
 
-        // push new slots 
-        for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) - 1; chIdx >= 0; chIdx--) {
-          int minForChild = g.GetAllowedChildSymbols(childNode.Symbol, chIdx).Min(a => g.GetMinimumExpressionLength(a)); // min length of all possible alts for the slot
-          openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild });
+        {
+          // and add child node to parent
+          var childNode = alternatives[selectedIdx].CreateTreeNode();
+
+          Contract.Assert(parent.SubtreeCount == childIdx); // enforce left-canonical derivation
+          parent.AddSubtree(childNode);
+          treeSize++;
+
+          // push new slots 
+          for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) - 1; chIdx >= 0; chIdx--) {
+            int minForChild = g.GetAllowedChildSymbols(childNode.Symbol, chIdx)
+              .Min(a => g.GetMinimumExpressionLength(a)); // min length of all possible alts for the slot
+            openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild });
+          }
         }
 
         // if this is the last slot we never have to revisit selectedIdx
         if (!openSlots.Any()) {
-          searchTree.RemoveBranch(selectedIdx);
+          searchTree.RemoveBranch(alternatives[selectedIdx]);
         } else {
-          searchTree.Follow(selectedIdx);
+          searchTree.Follow(alternatives[selectedIdx]);
         }
       }
 
-      stateActionSequence = states.Zip(actions, Tuple.Create);
+      stateSequence = states;
       return new SymbolicExpressionTree(root);
     }
 
+    /// <summary>
+    /// Choose one of the follow states
+    /// </summary>
+    /// <param name="followStates"></param>
+    /// <param name="random"></param>
+    /// <returns>The index of the selected follow state</returns>
+    protected abstract int Select(IReadOnlyList<object> followStates, IRandom random);
+    public abstract void Update(IEnumerable<object> stateSequence, double quality);
 
-    protected abstract int Select(object state, IEnumerable<int> possibleActions, IRandom random);
-    public abstract void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality);
-
-    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx);
+    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx);
   }
 }
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbSymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbSymbolicExpressionConstructionPolicy.cs	(revision 12923)
@@ -20,9 +20,9 @@
     }
 
-    public ITabularQualityFunction QualityFunction {
+    public ITabularStateValueFunction StateValueFunction {
       get {
-        return ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value;
+        return ((IValueParameter<ITabularStateValueFunction>)Parameters["Quality function"]).Value;
       }
-      set { ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value = value; }
+      set { ((IValueParameter<ITabularStateValueFunction>)Parameters["Quality function"]).Value = value; }
     }
 
@@ -39,41 +39,38 @@
       : base() {
       Parameters.Add(new FixedValueParameter<DoubleValue>("R", "The weighting factor for the confidence bound (should be scaled based on the range or the fitness values)", new DoubleValue(1.0)));
-      Parameters.Add(new ValueParameter<ITabularQualityFunction>("Quality function", "The quality function to use", new TabularAvgQualityFunction()));
+      Parameters.Add(new ValueParameter<ITabularStateValueFunction>("Quality function", "The quality function to use", new TabularAvgStateValueFunction()));
     }
 
-    protected sealed override int Select(object state, IEnumerable<int> actions, IRandom random) {
-
-      // find best action
-      var bestActions = new List<int>();
+    protected sealed override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      var bestFollowStates = new List<int>();
       var bestQuality = double.NegativeInfinity;
-      int totalTries = actions.Sum(a => QualityFunction.Tries(state, a));
-      foreach (var a in actions) {
+      int totalTries = followStates.Sum(s => StateValueFunction.Tries(s));
+      for (int idx = 0; idx < followStates.Count; idx++) {
         double quality;
-        if (QualityFunction.Tries(state, a) == 0) {
+        var s = followStates[idx];
+        if (StateValueFunction.Tries(s) == 0) {
           quality = double.PositiveInfinity;
         } else {
-          quality = QualityFunction.Q(state, a) + R * Math.Sqrt((2 * Math.Log(totalTries)) / QualityFunction.Tries(state, a));
+          quality = StateValueFunction.Value(s) + R * Math.Sqrt((2 * Math.Log(totalTries)) / StateValueFunction.Tries(s));
         }
         if (quality >= bestQuality) {
           if (quality > bestQuality) {
-            bestActions.Clear();
+            bestFollowStates.Clear();
             bestQuality = quality;
           }
-          bestActions.Add(a);
+          bestFollowStates.Add(idx);
         }
       }
-      return bestActions.SampleRandom(random, 1).First();
+      return bestFollowStates.SampleRandom(random);
     }
 
-    public sealed override void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality) {
-      foreach (var t in stateActionSequence) {
-        var state = t.Item1;
-        var action = t.Item2;
-        QualityFunction.Update(state, action, quality);
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+      foreach (var state in stateSequence) {
+        StateValueFunction.Update(state, quality);
       }
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return QualityFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs	(revision 12923)
@@ -20,9 +20,9 @@
     }
 
-    public ITabularQualityFunction QualityFunction {
+    public ITabularStateValueFunction StateValueFunction {
       get {
-        return ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value;
+        return ((IValueParameter<ITabularStateValueFunction>)Parameters["Quality function"]).Value;
       }
-      set { ((IValueParameter<ITabularQualityFunction>)Parameters["Quality function"]).Value = value; }
+      set { ((IValueParameter<ITabularStateValueFunction>)Parameters["Quality function"]).Value = value; }
     }
 
@@ -39,42 +39,39 @@
       : base() {
       Parameters.Add(new FixedValueParameter<DoubleValue>("R", "The weighting factor for the confidence bound (should be scaled based on the range or the fitness values)", new DoubleValue(1.0)));
-      Parameters.Add(new ValueParameter<ITabularQualityFunction>("Quality function", "The quality function to use", new TabularAvgQualityFunction()));
+      Parameters.Add(new ValueParameter<ITabularStateValueFunction>("Quality function", "The quality function to use", new TabularAvgStateValueFunction()));
     }
 
-    protected sealed override int Select(object state, IEnumerable<int> actions, IRandom random) {
-
-      // find best action
-      var bestActions = new List<int>();
+    protected sealed override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      var bestFollowStates = new List<int>();
       var bestQuality = double.NegativeInfinity;
-      int totalTries = actions.Sum(a => QualityFunction.Tries(state, a));
-      foreach (var a in actions) {
+      int totalTries = followStates.Sum(s => StateValueFunction.Tries(s));
+      for (int idx = 0; idx < followStates.Count; idx++) {
+        var s = followStates[idx];
         double quality;
-        if (QualityFunction.Tries(state, a) == 0) {
+        if (StateValueFunction.Tries(s) == 0) {
           quality = double.PositiveInfinity;
         } else {
-          double v = QualityFunction.QVariance(state, a) + Math.Sqrt(2 * Math.Log(totalTries) / QualityFunction.Tries(state, a));
-          quality = QualityFunction.Q(state, a) + R * Math.Sqrt(Math.Log(totalTries) / QualityFunction.Tries(state, a) * v);
+          double v = StateValueFunction.ValueVariance(s) + Math.Sqrt(2 * Math.Log(totalTries) / StateValueFunction.Tries(s));
+          quality = StateValueFunction.Value(s) + R * Math.Sqrt(Math.Log(totalTries) / StateValueFunction.Tries(s) * v);
         }
         if (quality >= bestQuality) {
           if (quality > bestQuality) {
-            bestActions.Clear();
+            bestFollowStates.Clear();
             bestQuality = quality;
           }
-          bestActions.Add(a);
+          bestFollowStates.Add(idx);
         }
       }
-      return bestActions.SampleRandom(random, 1).First();
+      return bestFollowStates.SampleRandom(random);
     }
 
-    public sealed override void Update(IEnumerable<Tuple<object, int>> stateActionSequence, double quality) {
-      foreach (var t in stateActionSequence) {
-        var state = t.Item1;
-        var action = t.Item2;
-        QualityFunction.Update(state, action, quality);
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+      foreach (var state in stateSequence) {
+        StateValueFunction.Update(state, quality);
       }
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return QualityFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgQualityFunction.cs	(revision 12922)
+++ 	(revision )
@@ -1,33 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using HeuristicLab.Common;
-using HeuristicLab.Core;
-using HeuristicLab.Parameters;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-
-namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
-  [StorableClass]
-  [Item("TabularAvgQualityFunction", "")]
-  internal class TabularAvgQualityFunction : TabularQualityFunctionBase {
-
-    public TabularAvgQualityFunction()
-      : base() {
-    }
-
-    #region item
-    [StorableConstructor]
-    protected TabularAvgQualityFunction(bool deserializing) : base(deserializing) { }
-    protected TabularAvgQualityFunction(TabularAvgQualityFunction original, Cloner cloner)
-      : base(original, cloner) {
-    }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new TabularAvgQualityFunction(this, cloner);
-    }
-    #endregion
-
-    protected override double CalculateNewQ(object state, int action, double observedQuality) {
-      var delta = observedQuality - Q(state, action);
-      return Q(state, action) + (1.0 / Tries(state, action)) * delta; // iterative calculation of mean
-    }
-  }
-}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgStateValueFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgStateValueFunction.cs	(revision 12923)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularAvgStateValueFunction.cs	(revision 12923)
@@ -0,0 +1,33 @@
+﻿using System;
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  [Item("TabularAvgQualityFunction", "")]
+  internal class TabularAvgStateValueFunction : TabularStateValueFunctionBase {
+
+    public TabularAvgStateValueFunction()
+      : base() {
+    }
+
+    #region item
+    [StorableConstructor]
+    protected TabularAvgStateValueFunction(bool deserializing) : base(deserializing) { }
+    protected TabularAvgStateValueFunction(TabularAvgStateValueFunction original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TabularAvgStateValueFunction(this, cloner);
+    }
+    #endregion
+
+    protected override double CalculateNewQ(object state, double observedQuality) {
+      var delta = observedQuality - Value(state);
+      return Value(state) + (1.0 / Tries(state)) * delta; // iterative calculation of mean
+    }
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxQualityFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxQualityFunction.cs	(revision 12922)
+++ 	(revision )
@@ -1,32 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using HeuristicLab.Common;
-using HeuristicLab.Core;
-using HeuristicLab.Parameters;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-
-namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
-  [StorableClass]
-  [Item("TabularMaxQualityFunction", "")]
-  internal class TabularMaxQualityFunction : TabularQualityFunctionBase {
-
-    public TabularMaxQualityFunction()
-      : base() {
-    }
-
-    #region item
-    [StorableConstructor]
-    protected TabularMaxQualityFunction(bool deserializing) : base(deserializing) { }
-    protected TabularMaxQualityFunction(TabularMaxQualityFunction original, Cloner cloner)
-      : base(original, cloner) {
-    }
-    public override IDeepCloneable Clone(Cloner cloner) {
-      return new TabularMaxQualityFunction(this, cloner);
-    }
-    #endregion
-
-    protected override double CalculateNewQ(object state, int action, double observedQuality) {
-      return Math.Max(Q(state, action), observedQuality);
-    }
-  }
-}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxStateValueFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxStateValueFunction.cs	(revision 12923)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularMaxStateValueFunction.cs	(revision 12923)
@@ -0,0 +1,32 @@
+﻿using System;
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  [Item("TabularMaxStateValueFunction", "")]
+  internal class TabularMaxStateValueFunction : TabularStateValueFunctionBase {
+
+    public TabularMaxStateValueFunction()
+      : base() {
+    }
+
+    #region item
+    [StorableConstructor]
+    protected TabularMaxStateValueFunction(bool deserializing) : base(deserializing) { }
+    protected TabularMaxStateValueFunction(TabularMaxStateValueFunction original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new TabularMaxStateValueFunction(this, cloner);
+    }
+    #endregion
+
+    protected override double CalculateNewQ(object state, double observedQuality) {
+      return Math.Max(Value(state), observedQuality);
+    }
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularQualityFunctionBase.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularQualityFunctionBase.cs	(revision 12922)
+++ 	(revision )
@@ -1,111 +1,0 @@
-﻿using System;
-using System.Collections.Generic;
-using HeuristicLab.Common;
-using HeuristicLab.Core;
-using HeuristicLab.Parameters;
-using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-
-namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
-  [StorableClass]
-  internal abstract class TabularQualityFunctionBase : ParameterizedNamedItem, ITabularQualityFunction {
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, double>> q = new Dictionary<object, Dictionary<int, double>>();
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, double>> qVariance = new Dictionary<object, Dictionary<int, double>>();
-    [Storable]
-    private readonly Dictionary<object, Dictionary<int, int>> tries = new Dictionary<object, Dictionary<int, int>>();
-
-    public IStateFunction StateFunction {
-      get {
-        return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
-      }
-      set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
-    }
-
-    protected TabularQualityFunctionBase()
-      : base() {
-      Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
-    }
-
-    public int Tries(object state, int action) {
-      Dictionary<int, int> stateTries;
-      if (!tries.TryGetValue(state, out stateTries)) return 0;
-      int stateActionTries;
-      if (!stateTries.TryGetValue(action, out stateActionTries)) return 0;
-      return stateActionTries;
-    }
-
-    public double Q(object state, int action) {
-      // an action that has never been tried has q == infinity
-      Dictionary<int, double> stateActionQualities;
-      if (!q.TryGetValue(state, out stateActionQualities)) return double.PositiveInfinity;
-      double quality;
-      if (!stateActionQualities.TryGetValue(action, out quality)) return double.PositiveInfinity;
-      return quality;
-    }
-
-    public double QVariance(object state, int action) {
-      // an action that has never been tried has qVariance == infinity
-      Dictionary<int, double> stateActionVariances;
-      if (!qVariance.TryGetValue(state, out stateActionVariances)) return double.PositiveInfinity;
-      double var;
-      if (!stateActionVariances.TryGetValue(action, out var)) return double.PositiveInfinity;
-      return var / Tries(state, action);
-    }
-
-    public virtual void Update(object state, int action, double observedQuality) {
-      Dictionary<int, int> stateActionTries;
-      if (!tries.TryGetValue(state, out stateActionTries)) {
-        stateActionTries = new Dictionary<int, int>();
-        tries.Add(state, stateActionTries);
-      }
-      Dictionary<int, double> stateActionQualities = null;
-      if (!q.TryGetValue(state, out stateActionQualities)) {
-        stateActionQualities = new Dictionary<int, double>();
-        q.Add(state, stateActionQualities);
-      }
-      Dictionary<int, double> stateActionVariances = null;
-      if (!qVariance.TryGetValue(state, out stateActionVariances)) {
-        stateActionVariances = new Dictionary<int, double>();
-        qVariance.Add(state, stateActionVariances);
-      }
-      int t;
-      if (!stateActionTries.TryGetValue(action, out t)) {
-        t = 0;
-        stateActionTries.Add(action, t + 1);
-        stateActionQualities.Add(action, observedQuality);
-        stateActionVariances.Add(action, 0); // naive initialization
-      } else {
-        stateActionTries[action] = t + 1;
-        var delta = observedQuality - stateActionQualities[action];
-        var curMean = CalculateNewQ(state, action, observedQuality);
-        stateActionQualities[action] = curMean;
-        stateActionVariances[action] = stateActionVariances[action] + delta * (observedQuality - curMean); // iterative calculation of mean
-      }
-    }
-
-    protected abstract double CalculateNewQ(object state, int action, double observedQuality);
-
-
-    #region item
-    [StorableConstructor]
-    protected TabularQualityFunctionBase(bool deserializing) : base(deserializing) { }
-    protected TabularQualityFunctionBase(TabularQualityFunctionBase original, Cloner cloner)
-      : base(original, cloner) {
-      this.q = new Dictionary<object, Dictionary<int, double>>(original.q);
-      this.qVariance = new Dictionary<object, Dictionary<int, double>>(original.qVariance);
-      this.tries = new Dictionary<object, Dictionary<int, int>>(original.tries);
-    }
-    #endregion
-
-    public void InitializeState() {
-      ClearState();
-    }
-
-    public void ClearState() {
-      q.Clear();
-      tries.Clear();
-      qVariance.Clear();
-    }
-  }
-}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularStateValueFunctionBase.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularStateValueFunctionBase.cs	(revision 12923)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularStateValueFunctionBase.cs	(revision 12923)
@@ -0,0 +1,90 @@
+﻿using System;
+using System.Collections.Generic;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  internal abstract class TabularStateValueFunctionBase : ParameterizedNamedItem, ITabularStateValueFunction {
+    [Storable]
+    private readonly Dictionary<object, double> q = new Dictionary<object, double>();
+    [Storable]
+    private readonly Dictionary<object, double> qVariance = new Dictionary<object, double>();
+    [Storable]
+    private readonly Dictionary<object, int> tries = new Dictionary<object, int>();
+
+    public IStateFunction StateFunction {
+      get {
+        return ((IValueParameter<IStateFunction>)Parameters["State function"]).Value;
+      }
+      set { ((IValueParameter<IStateFunction>)Parameters["State function"]).Value = value; }
+    }
+
+    protected TabularStateValueFunctionBase()
+      : base() {
+      Parameters.Add(new ValueParameter<IStateFunction>("State function", "The function that is used to map partial trees to states", new DefaultStateFunction()));
+    }
+
+    public int Tries(object state) {
+      var t = 0;
+      if (!tries.TryGetValue(state, out t)) return 0;
+      return t;
+    }
+
+    public double Value(object state) {
+      // an action that has never been tried has q == infinity
+      double quality;
+      if (!q.TryGetValue(state, out quality)) return double.PositiveInfinity;
+      return quality;
+    }
+
+    public double ValueVariance(object state) {
+      // an action that has never been tried has qVariance == infinity
+      double var;
+      if (!qVariance.TryGetValue(state, out var)) return double.PositiveInfinity;
+      return var / Tries(state);
+    }
+
+    public virtual void Update(object state, double observedQuality) {
+      int t;
+      if (!tries.TryGetValue(state, out t)) {
+        t = 0;
+        tries.Add(state, t + 1);
+        q.Add(state, observedQuality);
+        qVariance.Add(state, 0); // naive initialization
+      } else {
+        tries[state] = t + 1;
+        var delta = observedQuality - q[state];
+        var curMean = CalculateNewQ(state, observedQuality);
+        q[state] = curMean;
+        qVariance[state] = qVariance[state] + delta * (observedQuality - curMean); // iterative calculation of mean
+      }
+    }
+
+    protected abstract double CalculateNewQ(object state, double observedQuality);
+
+
+    #region item
+    [StorableConstructor]
+    protected TabularStateValueFunctionBase(bool deserializing) : base(deserializing) { }
+    protected TabularStateValueFunctionBase(TabularStateValueFunctionBase original, Cloner cloner)
+      : base(original, cloner) {
+      this.q = new Dictionary<object, double>(original.q);
+      this.tries = new Dictionary<object, int>(original.tries);
+      this.qVariance = new Dictionary<object, double>(original.qVariance);
+    }
+    #endregion
+
+    public void InitializeState() {
+      ClearState();
+    }
+
+    public void ClearState() {
+      q.Clear();
+      tries.Clear();
+      qVariance.Clear();
+    }
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/SearchTree.cs	(revision 12923)
@@ -7,8 +7,9 @@
 
 namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
-  internal class SearchTree {
-    private class Node {
-      internal Node parent;
-      internal Node[] children;
+  internal class SearchTree<TValue> {
+    private class Node<TValue> {
+      internal TValue value;
+      internal Node<TValue> parent;
+      internal Node<TValue>[] children;
       // children == null -> never visited
       // children[i] != null -> visited at least once, still allowed
@@ -16,11 +17,11 @@
     }
 
-    private Node root;
+    private Node<TValue> root;
 
     // for iteration
-    private Node currentNode;
+    private Node<TValue> currentNode;
 
     public SearchTree() {
-      root = new Node();
+      root = new Node<TValue>();
       currentNode = root;
     }
@@ -34,32 +35,41 @@
     }
 
-    public void ExpandCurrentNode<T>(IEnumerable<T> actions) {
-      Contract.Assert(actions.Any());
+    public void ExpandCurrentNode(IEnumerable<TValue> values) {
+      Contract.Assert(values.Any());
       Contract.Assert(currentNode.children == null);
-      currentNode.children = actions.Select(_ => new Node() { parent = currentNode }).ToArray();
+      currentNode.children = values.Select(val => new Node<TValue>() { value = val, parent = currentNode }).ToArray();
     }
 
-    public void Follow(int action) {
-      Contract.Assert(currentNode.children != null);
-      Contract.Assert(currentNode.children[action] != null);
-      currentNode = currentNode.children[action];
+    public void Follow(TValue value) {
+      // TODO: perf
+      int i = 0;
+      while (i < currentNode.children.Length && (
+        currentNode.children[i] == null || !currentNode.children[i].value.Equals(value))) i++;
+
+      if (i >= currentNode.children.Length) throw new InvalidProgramException();
+      currentNode = currentNode.children[i];
     }
 
-    public IEnumerable<int> PossibleActions {
+    public IEnumerable<TValue> ChildValues {
       get {
-        return Enumerable.Range(0, currentNode.children.Length)
-                         .Where(i => currentNode.children[i] != null);
+        return from ch in currentNode.children
+               where ch != null
+               select ch.value;
       }
     }
 
-    public void RemoveBranch(int action) {
-      Contract.Assert(currentNode.children != null);
-      Contract.Assert(currentNode.children[action] != null);
-      currentNode.children[action] = null;
+    public void RemoveBranch(TValue value) {
+      // TODO: perf
+      int i = 0;
+      while (i < currentNode.children.Length && (
+        currentNode.children[i] == null || !currentNode.children[i].value.Equals(value))) i++;
+
+      if (i >= currentNode.children.Length) throw new InvalidProgramException();
+      currentNode.children[i] = null;
 
       RemoveRecursively(currentNode);
     }
 
-    private void RemoveRecursively(Node node) {
+    private void RemoveRecursively(Node<TValue> node) {
       // when the last child has been removed we must remove the current node from it's parent
       while (node.parent != null && node.children.All(ch => ch == null)) {
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/DefaultStateFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/DefaultStateFunction.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/DefaultStateFunction.cs	(revision 12923)
@@ -18,6 +18,6 @@
     }
 
-    public object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parentNode, int childIdx) {
-      return string.Join(",", actions);
+    public object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parentNode, int childIdx) {
+      return string.Join(",", actions.Select(a => a.Name));
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/ParentChildStateFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/ParentChildStateFunction.cs	(revision 12922)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/StateFunctions/ParentChildStateFunction.cs	(revision 12923)
@@ -19,5 +19,5 @@
     }
 
-    public object CreateState(ISymbolicExpressionTreeNode root, List<int> actions, ISymbolicExpressionTreeNode parentNode, int childIdx) {
+    public object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parentNode, int childIdx) {
       return (parentNode == null ? "" : parentNode.Symbol.Name) + childIdx;
     }
