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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction-3.3.csproj	(revision 12955)
@@ -169,4 +169,6 @@
     <Compile Include="Plugin.cs" />
     <Compile Include="Policies\BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs" />
+    <Compile Include="Policies\DepthFirstSymbolicExpressionConstructionPolicy.cs" />
+    <Compile Include="Policies\BreathFirstSymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="Policies\UcbTunedSymbolicExpressionConstructionPolicy.cs" />
     <Compile Include="Policies\EpsGreedySymbolicExpressionConstructionPolicy.cs" />
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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BoltzmannExplorationSymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -68,6 +68,6 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BreathFirstSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BreathFirstSymbolicExpressionConstructionPolicy.cs	(revision 12955)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/BreathFirstSymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -0,0 +1,84 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  [Item("BreathFirstSymbolicExpressionConstructionPolicy", "Deterministic (almost) breath-first search")]
+  // simulates breath first search by following branches in the search tree that have been visited least often
+  public class BreathFirstSymbolicExpressionConstructionPolicy : SymbolicExpressionConstructionPolicyBase {
+
+    public BreathFirstSymbolicExpressionConstructionPolicy()
+      : base() {
+    }
+
+    private readonly Dictionary<string, int> tries = new Dictionary<string, int>();
+
+    public override void Initialize(SymbolicExpressionTreeProblem problem, IRandom random) {
+      base.Initialize(problem, random);
+      tries.Clear();
+    }
+
+    protected override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      // we want to find the action sequence that has been tried least frequently so far
+
+      Contract.Assert(followStates.Any());
+      var states = followStates.Cast<string>().ToArray();
+
+      // find action with minimum tries so far 
+      var bestIdx = 0;
+      var bestS = states.First();
+      int i = 0;
+      int minTries = int.MaxValue;
+      foreach (string s in states) {
+
+        int sTries;
+        tries.TryGetValue(s, out sTries);
+        if (sTries < minTries) {
+          bestS = s;
+          minTries = sTries;
+          bestIdx = i;
+        }
+        i++;
+      }
+
+      // increase tries of selected action
+      if (!tries.ContainsKey(bestS)) {
+        tries.Add(bestS, 1);
+      } else {
+        tries[bestS]++;
+      }
+      return bestIdx;
+
+    }
+
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+      // ignore
+    }
+
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      // TODO more compact representation than a dictionary of strings (many duplicate prefixes)
+      return string.Join(" ", actionSequence); // return the sequence of actions as string (=path in the search tree)
+    }
+
+    #region IItem
+    protected BreathFirstSymbolicExpressionConstructionPolicy(BreathFirstSymbolicExpressionConstructionPolicy original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    [StorableConstructor]
+    protected BreathFirstSymbolicExpressionConstructionPolicy(bool deserializing) : base(deserializing) { }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new BreathFirstSymbolicExpressionConstructionPolicy(this, cloner);
+    }
+
+    #endregion
+  }
+}
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/DepthFirstSymbolicExpressionConstructionPolicy.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/DepthFirstSymbolicExpressionConstructionPolicy.cs	(revision 12955)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/DepthFirstSymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -0,0 +1,52 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
+
+namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
+  [StorableClass]
+  [Item("DepthFirstSymbolicExpressionConstructionPolicy", "Deterministic depth-first search (but tries terminal states first)")]
+  public class DepthFirstSymbolicExpressionConstructionPolicy : SymbolicExpressionConstructionPolicyBase {
+
+    public DepthFirstSymbolicExpressionConstructionPolicy()
+      : base() {
+    }
+
+    protected override int Select(IReadOnlyList<object> followStates, IRandom random) {
+      Contract.Assert(followStates.Any());
+      int i = 0;
+      foreach (var followState in followStates) {
+        if ((bool)followState) return i;
+        i++;
+      }
+      return 0; // return the first non-terminal follow state
+    }
+
+    public sealed override void Update(IEnumerable<object> stateSequence, double quality) {
+      // ignore
+    }
+
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return parent.GetSubtree(childIdx).Symbol.MaximumArity == 0; // is it a terminal symbol?
+    }
+
+    #region IItem
+    protected DepthFirstSymbolicExpressionConstructionPolicy(DepthFirstSymbolicExpressionConstructionPolicy original, Cloner cloner)
+      : base(original, cloner) {
+    }
+
+    [StorableConstructor]
+    protected DepthFirstSymbolicExpressionConstructionPolicy(bool deserializing) : base(deserializing) { }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new DepthFirstSymbolicExpressionConstructionPolicy(this, cloner);
+    }
+
+    #endregion
+  }
+}
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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/EpsGreedySymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -62,6 +62,6 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, 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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/RandomSymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -26,5 +26,5 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, 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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/SymbolicExpressionConstructionPolicyBase.cs	(revision 12955)
@@ -62,5 +62,5 @@
       var g = Problem.Encoding.Grammar;
       var root = g.ProgramRootSymbol.CreateTreeNode();
-      int maxDepth = Problem.Encoding.TreeDepthParameter.Value.Value;
+      int maxDepth = Problem.Encoding.TreeDepthParameter.Value.Value; // ignored
       int maxLen = Problem.Encoding.TreeLengthParameter.Value.Value;
 
@@ -75,5 +75,6 @@
 
       while (openSlots.Any()) {
-        var next = openSlots.Pop();
+        var next = openSlots.First();
+        openSlots.Pop();
         var parent = next.parent;
         var childIdx = next.childIdx;
@@ -82,5 +83,6 @@
           var allowedChildSymbols = g.GetAllowedChildSymbols(parent.Symbol, childIdx)
             .Where(a => a.Enabled)
-            .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen);
+            .Where(a => treeSize + g.GetMinimumExpressionLength(a) + openSlots.Select(e => e.minSize).Sum() <= maxLen)
+            .OrderBy(a => a.MaximumArity); // terminals should be tried first
 
           searchTree.ExpandCurrentNode(allowedChildSymbols);
@@ -131,8 +133,8 @@
 
           // push new slots 
-          for (int chIdx = g.GetMinimumSubtreeCount(childNode.Symbol) - 1; chIdx >= 0; chIdx--) {
+          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 });
+            openSlots.Push(new Slot() { parent = childNode, childIdx = chIdx, minSize = minForChild }); 
           }
         }
@@ -159,5 +161,5 @@
     public abstract void Update(IEnumerable<object> stateSequence, double quality);
 
-    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx);
+    protected abstract object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, 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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbSymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -71,6 +71,6 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, 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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/Policies/UcbTunedSymbolicExpressionConstructionPolicy.cs	(revision 12955)
@@ -72,6 +72,6 @@
     }
 
-    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actions, ISymbolicExpressionTreeNode parent, int childIdx) {
-      return StateValueFunction.StateFunction.CreateState(root, actions, parent, childIdx);
+    protected override object CreateState(ISymbolicExpressionTreeNode root, List<ISymbol> actionSequence, ISymbolicExpressionTreeNode parent, int childIdx) {
+      return StateValueFunction.StateFunction.CreateState(root, actionSequence, parent, childIdx);
     }
 
Index: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/GbtApproximateStateValueFunction.cs
===================================================================
--- branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/GbtApproximateStateValueFunction.cs	(revision 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/GbtApproximateStateValueFunction.cs	(revision 12955)
@@ -1,7 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
-using System.Collections.Specialized;
 using System.Linq;
-using System.Runtime.InteropServices.WindowsRuntime;
 using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Common;
@@ -167,9 +165,5 @@
 
     public void ClearState() {
-
     }
-
   }
-
-
 }
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 12924)
+++ branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/QualityFunctions/TabularStateValueFunctionBase.cs	(revision 12955)
@@ -72,4 +72,6 @@
     protected TabularStateValueFunctionBase(TabularStateValueFunctionBase original, Cloner cloner)
       : base(original, cloner) {
+      // TODO: these become really large when using this class only from BasicAlgorithms it would not be necessary to clone and reset everything, (pause is not allowed)
+
       this.q = new Dictionary<object, double>(original.q);
       this.tries = new Dictionary<object, int>(original.tries);
