Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis.MCTSSymbReg.csproj
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis.MCTSSymbReg.csproj	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis.MCTSSymbReg.csproj	(revision 15416)
@@ -20,5 +20,5 @@
     <DebugType>full</DebugType>
     <Optimize>false</Optimize>
-    <OutputPath>bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>DEBUG;TRACE</DefineConstants>
     <ErrorReport>prompt</ErrorReport>
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Automaton.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Automaton.cs	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Automaton.cs	(revision 15416)
@@ -139,5 +139,5 @@
         codeGenerator.Emit1(OpCodes.LoadConst0);
         constraintHandler.Reset();
-      }, "0, Reset");
+      }, "0");
       AddTransition(StateTermEnd, StateExprEnd, () => {
         codeGenerator.Emit1(OpCodes.Add);
@@ -155,5 +155,5 @@
           constraintHandler.StartTerm();
         },
-        "c, StartTerm");
+        "c");
       AddTransition(StateFactorEnd, StateTermEnd,
         () => {
@@ -161,5 +161,5 @@
           constraintHandler.EndTerm();
         },
-        "*, EndTerm");
+        "*");
 
       AddTransition(StateFactorEnd, StateFactorStart,
@@ -172,21 +172,21 @@
         AddTransition(StateFactorStart, StateVariableFactorStart, () => {
           constraintHandler.StartFactor(StateVariableFactorStart);
-        }, "StartFactor");
+        }, "");
       if (allowExp)
         AddTransition(StateFactorStart, StateExpFactorStart, () => {
           constraintHandler.StartFactor(StateExpFactorStart);
-        }, "StartFactor");
+        }, "");
       if (allowLog)
         AddTransition(StateFactorStart, StateLogFactorStart, () => {
           constraintHandler.StartFactor(StateLogFactorStart);
-        }, "StartFactor");
+        }, "");
       if (allowInv)
         AddTransition(StateFactorStart, StateInvFactorStart, () => {
           constraintHandler.StartFactor(StateInvFactorStart);
-        }, "StartFactor");
-      AddTransition(StateVariableFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "EndFactor");
-      AddTransition(StateExpFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "EndFactor");
-      AddTransition(StateLogFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "EndFactor");
-      AddTransition(StateInvFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "EndFactor");
+        }, "");
+      AddTransition(StateVariableFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "");
+      AddTransition(StateExpFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "");
+      AddTransition(StateLogFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "");
+      AddTransition(StateInvFactorEnd, StateFactorEnd, () => { constraintHandler.EndFactor(); }, "");
 
       // VarFact -> var_1 ... var_n
@@ -202,5 +202,5 @@
             constraintHandler.AddVarToCurrentFactor(varState);
           },
-          "var_" + varIdx + ", AddVar");
+          "var_" + varIdx + "");
         AddTransition(curDynVarState, StateVariableFactorEnd);
         curDynVarState++;
@@ -234,5 +234,5 @@
             constraintHandler.AddVarToCurrentFactor(varState);
           },
-          "var_" + varIdx + ", AddVar");
+          "var_" + varIdx + "");
         AddTransition(curDynVarState, StateExpFEnd,
           () => {
@@ -249,5 +249,5 @@
           constraintHandler.StartNewTermInPoly();
         },
-        "0, StartTermInPoly");
+        "0");
       AddTransition(StateLogTEnd, StateLogFactorEnd,
         () => {
@@ -289,5 +289,5 @@
             constraintHandler.AddVarToCurrentFactor(varState);
           },
-          "var_" + varIdx + ", AddVar");
+          "var_" + varIdx + "");
         AddTransition(curDynVarState, StateLogTFEnd);
         curDynVarState++;
@@ -300,5 +300,5 @@
           constraintHandler.StartNewTermInPoly();
         },
-        "c, StartTermInPoly");
+        "c");
       AddTransition(StateInvTEnd, StateInvFactorEnd,
         () => {
@@ -338,5 +338,5 @@
             constraintHandler.AddVarToCurrentFactor(varState);
           },
-          "var_" + varIdx + ", AddVar");
+          "var_" + varIdx + "");
         AddTransition(curDynVarState, StateInvTFEnd);
         curDynVarState++;
@@ -442,4 +442,8 @@
       codeGenerator.Reset();
       constraintHandler.Reset();
+    }
+
+    internal string GetActionString(int fromState, int toState) {
+      return actionStrings[fromState,toState] != null ? string.Join(" , ", actionStrings[fromState, toState]) : ""; 
     }
 
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionAlgorithm.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionAlgorithm.cs	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionAlgorithm.cs	(revision 15416)
@@ -304,4 +304,5 @@
           if (bestQ > bestQuality.Value) {
             bestSolutionIteration.Value = i;
+            if (state.BestSolutionTrainingQuality > 0.99999) break; 
           }
           bestQuality.Value = bestQ;
@@ -329,5 +330,5 @@
 
       // final results (assumes that at least one iteration was calculated)
-      if (n > 0) {
+      if (n > 0) {        
         if (bestQ > bestQuality.Value) {
           bestSolutionIteration.Value = iterations.Value + n;
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs	(revision 15416)
@@ -61,4 +61,6 @@
     // TODO: Solve Poly-10
     // TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
+    // TODO: Why is the algorithm so slow for rather greedy policies (e.g. low C value in UCB)?
+    // TODO: check if we can use a quality measure with range [-1..1] in policies
     // TODO: unit tests for benchmark problems which contain log / exp / x^-1 but without numeric constants 
     // TODO: check if transformation of y is correct and works (Obj 2)
@@ -117,6 +119,10 @@
       private readonly ExpressionEvaluator evaluator, testEvaluator;
 
+      internal readonly Dictionary<Tree, List<Tree>> children = new Dictionary<Tree, List<Tree>>();
+      internal readonly Dictionary<Tree, List<Tree>> parents = new Dictionary<Tree, List<Tree>>();
+      internal readonly Dictionary<ulong, Tree> nodes = new Dictionary<ulong, Tree>();
+
       // values for best solution
-      private double bestRSq;
+      private double bestR;
       private byte[] bestCode;
       private int bestNParams;
@@ -187,5 +193,5 @@
 
         // reset best solution
-        this.bestRSq = 0;
+        this.bestR = 0;
         // code for default solution (constant model)
         this.bestCode = new byte[] { (byte)OpCodes.LoadConst0, (byte)OpCodes.Exit };
@@ -208,5 +214,5 @@
         get {
           evaluator.Exec(bestCode, x, bestConsts, predBuf);
-          return RSq(y, predBuf);
+          return Rho(y, predBuf);
         }
       }
@@ -215,5 +221,5 @@
         get {
           testEvaluator.Exec(bestCode, testX, bestConsts, testPredBuf);
-          return RSq(testY, testPredBuf);
+          return Rho(testY, testPredBuf);
         }
       }
@@ -248,6 +254,6 @@
 
         // single objective best
-        if (q > bestRSq) {
-          bestRSq = q;
+        if (q > bestR) {
+          bestR = q;
           bestNParams = nParams;
           this.bestCode = new byte[code.Length];
@@ -266,5 +272,5 @@
       }
 
-      private void Eval(byte[] code, int nParams, out double rsq, out double[] optConsts) {
+      private void Eval(byte[] code, int nParams, out double rho, out double[] optConsts) {
         // we make a first pass to determine a valid starting configuration for all constants
         // constant c in log(c + f(x)) is adjusted to guarantee that x is positive (see expression evaluator)
@@ -280,5 +286,5 @@
           // if we don't need to optimize parameters then we are done
           // changing scale and offset does not influence r²
-          rsq = RSq(y, predBuf);
+          rho = Rho(y, predBuf);
           optConsts = constsBuf;
         } else {
@@ -289,5 +295,5 @@
           funcEvaluations++;
 
-          rsq = RSq(y, predBuf);
+          rho = Rho(y, predBuf);
           optConsts = constsBuf;
         }
@@ -297,8 +303,8 @@
 
       #region helpers
-      private static double RSq(IEnumerable<double> x, IEnumerable<double> y) {
+      private static double Rho(IEnumerable<double> x, IEnumerable<double> y) {
         OnlineCalculatorError error;
         double r = OnlinePearsonsRCalculator.Calculate(x, y, out error);
-        return error == OnlineCalculatorError.None ? r * r : 0.0;
+        return error == OnlineCalculatorError.None ? r : 0.0;
       }
 
@@ -491,24 +497,20 @@
       do {
         automaton.Reset();
-        success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, out q);
+        success = TryTreeSearchRec2(rand, tree, automaton, eval, treePolicy, mctsState, out q);
         mctsState.totalRollouts++;
       } while (!success && !tree.Done);
       mctsState.effectiveRollouts++;
 
-      if (mctsState.effectiveRollouts % 10 == 1) {
-        //Console.WriteLine(WriteTree(tree));
-        //Console.WriteLine(TraceTree(tree));
-      }
+      //if (mctsState.effectiveRollouts % 100 == 1) {
+        // Console.WriteLine(WriteTree(tree, mctsState));
+        // Console.WriteLine(TraceTree(tree, mctsState));
+      //}
       return q;
     }
-
-    private static Dictionary<Tree, List<Tree>> children = new Dictionary<Tree, List<Tree>>();
-    private static Dictionary<Tree, List<Tree>> parents = new Dictionary<Tree, List<Tree>>();
-    private static Dictionary<ulong, Tree> nodes = new Dictionary<ulong, Tree>();
-
 
 
     // search forward
     private static bool TryTreeSearchRec2(IRandom rand, Tree tree, Automaton automaton, Func<byte[], int, double> eval, IPolicy treePolicy,
+      State state,
       out double q) {
       // ROLLOUT AND EXPANSION
@@ -527,6 +529,6 @@
 
       while (!automaton.IsFinalState(automaton.CurrentState)) {
-        if (children.ContainsKey(tree)) {
-          if (children[tree].All(ch => ch.Done)) {
+        if (state.children.ContainsKey(tree)) {
+          if (state.children[tree].All(ch => ch.Done)) {
             tree.Done = true;
             break;
@@ -535,8 +537,8 @@
           // UCT selection within tree
           int selectedIdx = 0;
-          if (children[tree].Count > 1) {
-            selectedIdx = treePolicy.Select(children[tree].Select(ch => ch.actionStatistics), rand);
-          }
-          tree = children[tree][selectedIdx];
+          if (state.children[tree].Count > 1) {
+            selectedIdx = treePolicy.Select(state.children[tree].Select(ch => ch.actionStatistics), rand);
+          }
+          tree = state.children[tree][selectedIdx];
 
           // move the automaton forward until reaching the state
@@ -556,6 +558,8 @@
           int[] possibleFollowStates;
           int nFs;
+          string actionString = "";
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
           while (nFs == 1 && !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
+            actionString += " " + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[0]);
             // no alternatives -> just go to the next state
             automaton.Goto(possibleFollowStates[0]);
@@ -568,5 +572,5 @@
           }
           var newChildren = new List<Tree>(nFs);
-          children.Add(tree, newChildren);
+          state.children.Add(tree, newChildren);
           for (int i = 0; i < nFs; i++) {
             Tree child = null;
@@ -574,24 +578,24 @@
             if (automaton.IsEvalState(possibleFollowStates[i])) {
               var hc = Hashcode(automaton);
-              if (!nodes.TryGetValue(hc, out child)) {
+              if (!state.nodes.TryGetValue(hc, out child)) {
                 child = new Tree() {
                   children = null,
                   state = possibleFollowStates[i],
                   actionStatistics = treePolicy.CreateActionStatistics(),
-                  expr = string.Empty, // ExprStr(automaton),
+                  expr = actionString + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[i]),
                   level = tree.level + 1
                 };
-                nodes.Add(hc, child);
+                state.nodes.Add(hc, child);
               }
               // only allow forward edges (don't add the child if we would go back in the graph)
-              else if (child.level > tree.level) {
+              else if (child.level > tree.level)  {
                 // whenever we join paths we need to propagate back the statistics of the existing node through the newly created link
                 // to all parents 
-                BackpropagateStatistics(child.actionStatistics, tree);
+                BackpropagateStatistics(child.actionStatistics, tree, state);
               } else {
                 // prevent cycles
                 Debug.Assert(child.level <= tree.level);
                 child = null;
-              }
+              }   
             } else {
               child = new Tree() {
@@ -599,5 +603,5 @@
                 state = possibleFollowStates[i],
                 actionStatistics = treePolicy.CreateActionStatistics(),
-                expr = string.Empty, // ExprStr(automaton),
+                expr = actionString + automaton.GetActionString(automaton.CurrentState, possibleFollowStates[i]),
                 level = tree.level + 1
               };
@@ -614,13 +618,13 @@
 
           foreach (var ch in newChildren) {
-            if (!parents.ContainsKey(ch)) {
-              parents.Add(ch, new List<Tree>());
+            if (!state.parents.ContainsKey(ch)) {
+              state.parents.Add(ch, new List<Tree>());
             }
-            parents[ch].Add(tree);
-          }
-
-
-          // follow one of the children
-          tree = SelectFinalOrRandom2(automaton, tree, rand);
+            state.parents[ch].Add(tree);
+          }
+
+
+          // follow one of the children 
+          tree = SelectStateLeadingToFinal(automaton, tree, rand, state);
           automaton.Goto(tree.state);
         }
@@ -636,8 +640,10 @@
         automaton.GetCode(out code, out nParams);
         q = eval(code, nParams);
+        // Console.WriteLine("{0:N4}\t{1}", q*q, tree.expr);
         q = TransformQuality(q);
         success = true;
       } else {
         // we got stuck in roll-out (not evaluation necessary!)
+        // Console.WriteLine("\t" + ExprStr(automaton) + " STOP");
         q = 0.0;
         success = false;
@@ -647,5 +653,5 @@
       // Update statistics
       // Set branch to done if all children are done.
-      BackpropagateQuality(tree, q, treePolicy);
+      BackpropagateQuality(tree, q, treePolicy, state);
 
       return success;
@@ -655,7 +661,15 @@
     private static double TransformQuality(double q) {
       // no transformation
-      return q;
+      // return q;
 
       // EXPERIMENTAL!
+
+      // Fisher transformation
+      // (assumes q is Correl(pred, target)
+
+      q = Math.Min(q,  0.99999999);
+      q = Math.Max(q, -0.99999999);
+      return 0.5 * Math.Log((1 + q) / (1 - q));
+
       // optimal result: q = 1 -> return huge value
       // if (q >= 1.0) return 1E16;
@@ -665,9 +679,9 @@
 
     // backpropagate existing statistics to all parents
-    private static void BackpropagateStatistics(IActionStatistics stats, Tree tree) {
+    private static void BackpropagateStatistics(IActionStatistics stats, Tree tree, State state) {
       tree.actionStatistics.Add(stats);
-      if (parents.ContainsKey(tree)) {
-        foreach (var parent in parents[tree]) {
-          BackpropagateStatistics(stats, parent);
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateStatistics(stats, parent, state);
         }
       }
@@ -681,33 +695,26 @@
     }
 
-    private static void BackpropagateQuality(Tree tree, double q, IPolicy policy) {
+    private static void BackpropagateQuality(Tree tree, double q, IPolicy policy, State state) {
       if (q > 0) policy.Update(tree.actionStatistics, q);
-      if (children.ContainsKey(tree) && children[tree].All(ch => ch.Done)) {
+      if (state.children.ContainsKey(tree) && state.children[tree].All(ch => ch.Done)) {
         tree.Done = true;
         // children[tree] = null; keep all nodes
       }
 
-      if (parents.ContainsKey(tree)) {
-        foreach (var parent in parents[tree]) {
-          BackpropagateQuality(parent, q, policy);
-        }
-      }
-    }
-
-    private static Tree SelectFinalOrRandom2(Automaton automaton, Tree tree, IRandom rand) {
-      // if one of the new children leads to a final state then go there
-      // otherwise choose a random child
-      int selectedChildIdx = -1;
-      // find first final state if there is one
-      var children = MctsSymbolicRegressionStatic.children[tree];
-      for (int i = 0; i < children.Count; i++) {
-        if (automaton.IsFinalState(children[i].state)) {
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateQuality(parent, q, policy, state);
+        }
+      }
+    }
+
+    private static Tree SelectStateLeadingToFinal(Automaton automaton, Tree tree, IRandom rand, State state) {
+      // find the child with the smallest state value (smaller values are closer to the final state)
+      int selectedChildIdx = 0;
+      var children = state.children[tree];
+      Tree minChild = children.First();
+      for (int i = 1; i < children.Count; i++) {
+        if(children[i].state < minChild.state)
           selectedChildIdx = i;
-          break;
-        }
-      }
-      // no final state -> select the first child
-      if (selectedChildIdx == -1) {
-        selectedChildIdx = 0;
       }
       return children[selectedChildIdx];
@@ -865,9 +872,9 @@
     }
 
-    private static string WriteStatistics(Tree tree) {
+    private static string WriteStatistics(Tree tree, State state) {
       var sb = new System.IO.StringWriter();
       sb.WriteLine("{0} {1:N5}", tree.actionStatistics.Tries, tree.actionStatistics.AverageQuality);
-      if (children.ContainsKey(tree)) {
-        foreach (var ch in children[tree]) {
+      if (state.children.ContainsKey(tree)) {
+        foreach (var ch in state.children[tree]) {
           sb.WriteLine("{0} {1:N5}", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
         }
@@ -876,5 +883,5 @@
     }
 
-    private static string TraceTree(Tree tree) {
+    private static string TraceTree(Tree tree, State state) {
       var sb = new StringBuilder();
       sb.Append(
@@ -885,20 +892,21 @@
       int nodeId = 0;
 
-      TraceTreeRec(tree, 0, sb, ref nodeId);
+      TraceTreeRec(tree, 0, sb, ref nodeId, state);
       sb.Append("}");
       return sb.ToString();
     }
 
-    private static void TraceTreeRec(Tree tree, int parentId, StringBuilder sb, ref int nextId) {
+    private static void TraceTreeRec(Tree tree, int parentId, StringBuilder sb, ref int nextId, State state) {
       var avgNodeQ = tree.actionStatistics.AverageQuality;
       var tries = tree.actionStatistics.Tries;
       if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
       var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-
-      sb.AppendFormat("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue).AppendLine();
+      hue = 0.0;
+
+      sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue).AppendLine();
 
       var list = new List<Tuple<int, int, Tree>>();
-      if (children.ContainsKey(tree)) {
-        foreach (var ch in children[tree]) {
+      if (state.children.ContainsKey(tree)) {
+        foreach (var ch in state.children[tree]) {
           nextId++;
           avgNodeQ = ch.actionStatistics.AverageQuality;
@@ -906,15 +914,33 @@
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
           hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
-          sb.AppendFormat("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
-          sb.AppendFormat("{0} -> {1}", parentId, nextId, avgNodeQ).AppendLine();
+          hue = 0.0;
+          sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
+          sb.AppendFormat("{0} -> {1} [label=\"{3}\"]", parentId, nextId, avgNodeQ, ch.expr).AppendLine();
           list.Add(Tuple.Create(tries, nextId, ch));
         }
+
+        foreach(var tup in list) {
+          var ch = tup.Item3;
+          var chId = tup.Item2;
+          if(state.children.ContainsKey(ch) && state.children[ch].Count == 1) {
+            var chch = state.children[ch].First();
+            nextId++;
+            avgNodeQ = chch.actionStatistics.AverageQuality;
+            tries = chch.actionStatistics.Tries;
+            if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
+            hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+            hue = 0.0;
+            sb.AppendFormat("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", nextId, avgNodeQ, tries, hue).AppendLine();
+            sb.AppendFormat("{0} -> {1} [label=\"{3}\"]", chId, nextId, avgNodeQ, chch.expr).AppendLine();
+          }
+        }
+
         foreach (var tup in list.OrderByDescending(t => t.Item1).Take(1)) {
-          TraceTreeRec(tup.Item3, tup.Item2, sb, ref nextId);
-        }
-      }
-    }
-
-    private static string WriteTree(Tree tree) {
+          TraceTreeRec(tup.Item3, tup.Item2, sb, ref nextId, state);
+        }
+      }
+    }
+
+    private static string WriteTree(Tree tree, State state) {
       var sb = new System.IO.StringWriter(System.Globalization.CultureInfo.InvariantCulture);
       var nodeIds = new Dictionary<Tree, int>();
@@ -924,6 +950,6 @@
   node [style=filled];
 ");
-      int threshold = nodes.Count > 500 ? 10 : 0;
-      foreach (var kvp in children) {
+      int threshold = /* state.nodes.Count > 500 ? 10 : */ 0;
+      foreach (var kvp in state.children) {
         var parent = kvp.Key;
         int parentId;
@@ -934,6 +960,7 @@
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
           var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          hue = 0.0;
           if (parent.actionStatistics.Tries > threshold)
-            sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
+            sb.Write("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", parentId, avgNodeQ, tries, hue);
           nodeIds.Add(parent, parentId);
         }
@@ -949,6 +976,7 @@
           if (double.IsNaN(avgNodeQ)) avgNodeQ = 0.0;
           var hue = (1 - avgNodeQ) / 360.0 * 240.0; // 0 equals red, 240 equals blue
+          hue = 0.0;
           if (tries > threshold) {
-            sb.Write("{0} [label=\"{1:N3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", childId, avgNodeQ, tries, hue);
+            sb.Write("{0} [label=\"{1:E3} {2}\" color=\"{3:N3} 0.999 0.999\"]; ", childId, avgNodeQ, tries, hue);
             var edgeLabel = child.expr;
             // if (parent.expr.Length > 0) edgeLabel = edgeLabel.Replace(parent.expr, "");
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs	(revision 15416)
@@ -78,8 +78,9 @@
         else totalTries += a.Tries;
       }
-      // if there are unvisited actions select a random action
+      // if there are unvisited actions select a random unvisited action
       if (buf.Any()) {
         return buf[rand.Next(buf.Count)];
       }
+                     
       Debug.Assert(totalTries > 0);
       double logTotalTries = Math.Log(totalTries);
Index: /branches/MCTS-SymbReg-2796/Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/MctsSymbolicRegressionTest.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/MctsSymbolicRegressionTest.cs	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/MctsSymbolicRegressionTest.cs	(revision 15416)
@@ -7,4 +7,5 @@
 using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.Instances.DataAnalysis;
+using HeuristicLab.Random;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 
@@ -550,6 +551,208 @@
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(seed: 1234);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F7 ")));
-      TestMctsWithoutConstants(regProblem, nVarRefs: 10, iterations: 1000000, allowExp: false, allowLog: true, allowInv: false);
-    }
+      TestMctsWithoutConstants(regProblem, nVarRefs: 10, iterations: 100000, allowExp: false, allowLog: true, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Poly10_Part1() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X1*X2 + X3*X4 + X5*X6
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        ys[i] -= x1[i] * x7[i] * x9[i];
+        ys[i] -= x3[i] * x6[i] * x10[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+
+      var modifiedProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+
+      TestMctsWithoutConstants(modifiedProblemData, nVarRefs: 15, iterations: 100000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Poly10_Part2() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X1*X7*X9 + X3*X6*X10
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        ys[i] -= x1[i] * x2[i];
+        ys[i] -= x3[i] * x4[i];
+        ys[i] -= x5[i] * x6[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+
+      var modifiedProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+
+      TestMctsWithoutConstants(modifiedProblemData, nVarRefs: 15, iterations: 100000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Poly10_Part3() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X1*X2 + X1*X7*X9
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        ys[i] -= x3[i] * x4[i];
+        ys[i] -= x5[i] * x6[i];
+        ys[i] -= x3[i] * x6[i] * x10[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+
+      var modifiedProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+
+      TestMctsWithoutConstants(modifiedProblemData, nVarRefs: 15, iterations: 100000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Poly10_Part4() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X3*X4 + X5*X6 + X3*X6*X10
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        ys[i] -= x1[i] * x2[i];
+        ys[i] -= x1[i] * x7[i] * x9[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+      var modifiedProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+
+      TestMctsWithoutConstants(modifiedProblemData, nVarRefs: 15, iterations: 100000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Poly10_Part5() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        ys[i] -= x3[i] * x6[i] * x10[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+      var modifiedProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+
+      TestMctsWithoutConstants(modifiedProblemData, nVarRefs: 15, iterations: 100000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Poly10_Part6() {
+      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
+      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
+
+      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
+      //  Y' = X1*X2 + X3*X4 + X5*X6 + X3*X6*X10
+      // simplify problem by changing target
+      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
+      var ys = ds.GetDoubleValues("Y").ToArray();
+      var x1 = ds.GetDoubleValues("X1").ToArray();
+      var x2 = ds.GetDoubleValues("X2").ToArray();
+      var x3 = ds.GetDoubleValues("X3").ToArray();
+      var x4 = ds.GetDoubleValues("X4").ToArray();
+      var x5 = ds.GetDoubleValues("X5").ToArray();
+      var x6 = ds.GetDoubleValues("X6").ToArray();
+      var x7 = ds.GetDoubleValues("X7").ToArray();
+      var x8 = ds.GetDoubleValues("X8").ToArray();
+      var x9 = ds.GetDoubleValues("X9").ToArray();
+      var x10 = ds.GetDoubleValues("X10").ToArray();
+      for (int i = 0; i < ys.Length; i++) {
+        ys[i] -= x1[i] * x7[i] * x9[i];
+      }
+      ds.ReplaceVariable("Y", ys.ToList());
+      var modifiedProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
+
+
+      TestMctsWithoutConstants(modifiedProblemData, nVarRefs: 9, iterations: 100000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
 
     [TestMethod]
@@ -559,5 +762,52 @@
       var provider = new HeuristicLab.Problems.Instances.DataAnalysis.VariousInstanceProvider(seed: 1234);
       var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("Poly-10")));
-      TestMctsWithoutConstants(regProblem, nVarRefs: 15, iterations: 1000000, allowExp: false, allowLog: false, allowInv: false);
+      TestMctsWithoutConstants(regProblem, nVarRefs: 15, iterations: 200000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_TwoVars() {
+
+      // y = x1 + x2 + x1*x2 + x1*x2*x2 + x1*x1*x2
+      var rand = new FastRandom(1234);
+      var x1 = Enumerable.Range(0, 100).Select(_ => rand.NextDouble()).ToList();
+      var x2 = Enumerable.Range(0, 100).Select(_ => rand.NextDouble()).ToList();
+      var ys = x1.Zip(x2, (x1i, x2i) => x1i + x2i + x1i * x2i + x1i * x2i * x2i + x1i * x1i * x2i).ToList();
+
+      var ds = new Dataset(new string[] { "a", "b", "y" }, new[] { x1, x2, ys });
+
+      var problemData = new RegressionProblemData(ds, new string[] { "a", "b" }, "y");
+
+
+      TestMctsWithoutConstants(problemData, nVarRefs: 10, iterations: 10000, allowExp: false, allowLog: false, allowInv: false);
+    }
+
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void MctsSymbReg_NoConstants_Misleading() {
+
+      // y = a + baaaaa (the effect of the second term should be very small)
+      // the alg will quickly find that a has big effect and will search below a
+      // since we prevent a + a... the algorithm must find the correct expression via a + b...
+      // however b has a small effect so the branch might not be identified as relevant
+
+      var rand = new FastRandom(1234);
+      var @as = Enumerable.Range(0, 100).Select(_ => rand.NextDouble()).ToList();
+      var bs = Enumerable.Range(0, 100).Select(_ => rand.NextDouble()).ToList();
+      var cs = Enumerable.Range(0, 100).Select(_ => rand.NextDouble() *1.0e-3).ToList();
+      var ds = Enumerable.Range(0, 100).Select(_ => rand.NextDouble() ).ToList();
+      var es = Enumerable.Range(0, 100).Select(_ => rand.NextDouble() ).ToList();
+      var ys = new double[@as.Count];
+      for(int i=0;i<ys.Length;i++)
+        ys[i] = @as[i] + bs[i] + @as[i]*bs[i]*cs[i];
+
+      var dataset = new Dataset(new string[] { "a", "b", "c", "d", "e", "y" }, new[] { @as, bs, cs, ds, es, ys.ToList() });
+
+      var problemData = new RegressionProblemData(dataset, new string[] { "a", "b","c","d","e" }, "y");
+
+
+      TestMctsWithoutConstants(problemData, nVarRefs: 10, iterations: 10000, allowExp: false, allowLog: false, allowInv: false);
     }
     #endregion
@@ -822,4 +1072,15 @@
       mctsSymbReg.ConstantOptimizationIterations = -1;
 
+      // random policy
+      // var epsPolicy = new EpsilonGreedy();
+      // epsPolicy.Eps = 1.0;
+      // mctsSymbReg.Policy = epsPolicy;
+
+      // UCB tuned
+      // var ucbTuned = new UcbTuned();
+      // ucbTuned.C = 1.5; 
+      // mctsSymbReg.Policy = ucbTuned;
+
+
       #endregion
       RunAlgorithm(mctsSymbReg);
Index: /branches/MCTS-SymbReg-2796/Tests/Test.csproj
===================================================================
--- /branches/MCTS-SymbReg-2796/Tests/Test.csproj	(revision 15415)
+++ /branches/MCTS-SymbReg-2796/Tests/Test.csproj	(revision 15416)
@@ -63,4 +63,8 @@
       <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances.DataAnalysis-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
   </ItemGroup>
