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 15424)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis.MCTSSymbReg.csproj	(revision 15425)
@@ -98,4 +98,5 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Heuristics.cs" />
     <Compile Include="MctsSymbolicRegression\ApproximateDoubleEqualityComparer.cs" />
     <Compile Include="MctsSymbolicRegression\IConstraintHandler.cs" />
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/Heuristics.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/Heuristics.cs	(revision 15425)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/Heuristics.cs	(revision 15425)
@@ -0,0 +1,49 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Problems.DataAnalysis;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MCTSSymbReg {
+  // experimenting with heuristics
+  // 
+  // question: how can relevant interacting terms be reliably detected? 
+  //           - is this even feasible?
+  //           - even if variables are colinear?
+  //           - even for non-linear transformations
+
+  // assuming we interactions of have scaled/shifted variables (x + xo) * (y + yo) with constant xo and yo
+  // this leads to: x y + x yo + y xo + yo xo. 
+  // We only need to identify the x y as we assume that all other terms are accounted for
+  public static class Heuristics {
+    public static double CorrelationForInteraction(double[] a, double[] b, double[] z) {
+      // 
+      var am = a.Average();
+      var bm = b.Average();
+      var p1 = Enumerable.Range(0, a.Length).Where(i => a[i] < am);
+      var p2 = Enumerable.Range(0, a.Length).Where(i => a[i] > am);
+      var p3 = Enumerable.Range(0, a.Length).Where(i => b[i] < bm);
+      var p4 = Enumerable.Range(0, a.Length).Where(i => b[i] > bm);
+
+      return 1.0 / (p1.Count() + p2.Count() + p3.Count() + p4.Count()) *
+             (p1.Count() * CorrelForPartition(b, z, p1) +
+             p2.Count() * CorrelForPartition(b, z, p2) +
+             p3.Count() * CorrelForPartition(a, z, p3) +
+             p4.Count() * CorrelForPartition(a, z, p4));
+    }
+
+    public static double CorrelForPartition(double[] a, double[] z, IEnumerable<int> idx) {
+      var zp = new List<double>();
+      var ap = new List<double>();
+      foreach (var i in idx) {
+        zp.Add(z[i]);
+        ap.Add(a[i]);
+      }
+      OnlineCalculatorError error;
+      var r = SpearmansRankCorrelationCoefficientCalculator.CalculateSpearmansRank(zp, ap, out error);
+      if (error != OnlineCalculatorError.None) r = 0;
+      return r * r;
+    }
+  }
+}
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 15424)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/MctsSymbolicRegressionStatic.cs	(revision 15425)
@@ -56,7 +56,9 @@
     //    
 
-    // TODO: Taking averages of R² values is probably not ideal as an improvement of R² from 0.99 to 0.999 should 
-    //       weight more than an improvement from 0.98 to 0.99. Also, we are more interested in the best value of a 
-    //       branch and less in the expected value. (--> Review "Extreme Bandit" literature again)
+    // TODO: The samples of x1*... or x2*... do not give any information about the relevance of the interaction term x1*x2 in general!
+    //       --> E.g. if x1, x2 ~ N(0, 1) or U(-1, 1) this is trivial to show
+    //       --> Therefore, looking at rollout statistics for arm selection is useless in the general case!
+    //       --> It is necessary to rely on other features for the arm selection. 
+    //       --> TODO: Which heuristics can we apply? 
     // TODO: Solve Poly-10
     // TODO: After state unification the recursive backpropagation of results takes a lot of time. How can this be improved?
@@ -72,4 +74,5 @@
     // TODO: improve memory usage
     // TODO: support empty test partition
+    // TODO: the algorithm should be invariant to linear transformations of the space (y = f(x') = f( Ax ) ) for invertible transformations A --> unit tests
     #region static API
 
@@ -143,6 +146,12 @@
       // calculate for each level the number of alternatives the average 'inequality' of tries and 'inequality' of quality over the alternatives for each trie
       // inequality can be calculated using the Gini coefficient
-      internal readonly double[] giniCoeffs = new double[100];
-      
+      internal readonly double[] pathGiniCoeffs = new double[100];
+      internal readonly double[] pathQs = new double[100];
+      internal readonly double[] levelBestQ = new double[100];
+      // internal readonly double[] levelMaxTries = new double[100];
+      internal readonly double[] pathBestQ = new double[100]; // as long as pathBestQs = levelBestQs we are following the correct path
+      internal readonly string[] levelBestAction = new string[100];
+      internal readonly string[] curAction = new string[100];
+      internal readonly double[] pathSelectedQ = new double[100];
 
       public State(IRegressionProblemData problemData, uint randSeed, int maxVariables, bool scaleVariables,
@@ -448,9 +457,63 @@
 #if DEBUG
       internal void ClearStats() {
-        for (int i = 0; i < giniCoeffs.Length; i++) giniCoeffs[i] = -1;
-      }
-      internal void WriteStats() {
-        Console.WriteLine(string.Join("\t", giniCoeffs.TakeWhile(x => x >= 0).Select(x => string.Format("{0:N3}", x))));
-      }
+        for (int i = 0; i < pathGiniCoeffs.Length; i++) pathGiniCoeffs[i] = -1;
+        for (int i = 0; i < pathQs.Length; i++) pathGiniCoeffs[i] = -99;
+        for (int i = 0; i < pathBestQ.Length; i++) pathBestQ[i] = -99;
+        for (int i = 0; i < pathSelectedQ.Length; i++) pathSelectedQ[i] = -99;
+      }
+      internal void WriteGiniStats() {
+        Console.WriteLine(string.Join("\t", pathGiniCoeffs.TakeWhile(x => x >= 0).Select(x => string.Format("{0:N3}", x))));
+      }
+      internal void WriteQs() {
+        // Console.WriteLine(string.Join("\t", pathQs.TakeWhile(x => x >= -100).Select(x => string.Format("{0:N3}", x))));
+        var sb = new StringBuilder();
+        // length
+        int i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99 && pathBestQ[i] == levelBestQ[i]) {
+          i++;
+        }
+        sb.AppendFormat("{0,-3}",i);
+
+        i = 0;
+        // sb.AppendFormat("{0:N3}", levelBestQ[0]);
+        while (i < pathSelectedQ.Length && pathSelectedQ[i] > -99) {
+          sb.AppendFormat("\t{0:N3}", pathSelectedQ[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        sb.Clear();
+        i = 0;
+        // sb.AppendFormat("{0:N3}", levelBestQ[0]);
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0:N3}", pathBestQ[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        sb.Clear();
+        i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0:N3}", levelBestQ[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        
+        sb.Clear();
+        i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0,-5}", (curAction[i] != null && curAction[i].Length > 5) ? curAction[i].Substring(0, 5) : curAction[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        sb.Clear();
+        i = 0;
+        while (i < pathBestQ.Length && pathBestQ[i] > -99) {
+          sb.AppendFormat("\t{0,-5}", (levelBestAction[i] != null && levelBestAction[i].Length > 5) ? levelBestAction[i].Substring(0, 5) : levelBestAction[i]);
+          i++;
+        }
+        Console.WriteLine(sb.ToString());
+        
+        Console.WriteLine();
+      }
+
 
 #endif
@@ -525,5 +588,9 @@
 
 #if DEBUG
-      mctsState.WriteStats();
+      // mctsState.WriteGiniStats();
+      Console.WriteLine(ExprStr(automaton));
+      mctsState.WriteQs();
+      // Console.WriteLine(WriteStatistics(tree, mctsState));
+
 #endif
       //if (mctsState.effectiveRollouts % 100 == 1) {
@@ -564,7 +631,8 @@
             selectedIdx = treePolicy.Select(state.children[tree].Select(ch => ch.actionStatistics), rand);
           }
-
+          
           // STATS
-          state.giniCoeffs[tree.level] = InequalityCoefficient(state.children[tree].Select(ch => (double)ch.actionStatistics.AverageQuality));
+          state.pathGiniCoeffs[tree.level] = InequalityCoefficient(state.children[tree].Select(ch => (double)ch.actionStatistics.AverageQuality));
+          state.pathQs[tree.level] = tree.actionStatistics.AverageQuality;
 
           tree = state.children[tree][selectedIdx];
@@ -576,9 +644,10 @@
           int nFs;
           automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          while (automaton.CurrentState != tree.state && nFs == 1 && 
-            !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
-            automaton.Goto(possibleFollowStates[0]);
-            automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          }
+          // TODO!
+          // while (possibleFollowStates[0] != tree.state && nFs == 1 && 
+          //   !automaton.IsEvalState(possibleFollowStates[0]) && !automaton.IsFinalState(possibleFollowStates[0])) {
+          //   automaton.Goto(possibleFollowStates[0]);
+          //   automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          // }
           Debug.Assert(possibleFollowStates.Contains(tree.state));
           automaton.Goto(tree.state);
@@ -589,10 +658,11 @@
           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]);
-            automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
-          }
+          // TODO
+          // 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]);
+          //   automaton.FollowStates(automaton.CurrentState, out possibleFollowStates, out nFs);
+          // }
           if (nFs == 0) {
             // stuck in a dead end (no final state and no allowed follow states)
@@ -672,4 +742,5 @@
         q = TransformQuality(q);
         success = true;
+        BackpropagateQuality(tree, q, treePolicy, state);        
       } else {
         // we got stuck in roll-out (not evaluation necessary!)
@@ -682,5 +753,7 @@
       // Update statistics
       // Set branch to done if all children are done.
-      BackpropagateQuality(tree, q, treePolicy, state);
+      BackpropagateDone(tree, state);
+      BackpropagateDebugStats(tree, q, state);
+
 
       return success;
@@ -703,5 +776,5 @@
     private static double TransformQuality(double q) {
       // no transformation
-      // return q;
+      return q;
 
       // EXPERIMENTAL!
@@ -738,5 +811,14 @@
 
     private static void BackpropagateQuality(Tree tree, double q, IPolicy policy, State state) {
-      if (q > 0) policy.Update(tree.actionStatistics, q);
+      policy.Update(tree.actionStatistics, q);
+
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateQuality(parent, q, policy, state);
+        }
+      }
+    }
+
+    private static void BackpropagateDone(Tree tree, State state) {
       if (state.children.ContainsKey(tree) && state.children[tree].All(ch => ch.Done)) {
         tree.Done = true;
@@ -746,6 +828,22 @@
       if (state.parents.ContainsKey(tree)) {
         foreach (var parent in state.parents[tree]) {
-          BackpropagateQuality(parent, q, policy, state);
-        }
+          BackpropagateDone(parent, state);
+        }
+      }
+    }
+
+    private static void BackpropagateDebugStats(Tree tree, double q, State state) {
+      if (state.parents.ContainsKey(tree)) {
+        foreach (var parent in state.parents[tree]) {
+          BackpropagateDebugStats(parent, q, state);
+        }
+      }
+
+      state.pathSelectedQ[tree.level] = tree.actionStatistics.AverageQuality;
+      state.pathBestQ[tree.level] = tree.actionStatistics.BestQuality;
+      state.curAction[tree.level] = tree.expr;
+      if (state.levelBestQ[tree.level] < tree.actionStatistics.BestQuality) {
+        state.levelBestQ[tree.level] = tree.actionStatistics.BestQuality;
+        state.levelBestAction[tree.level] = tree.expr;
       }
     }
@@ -917,10 +1015,11 @@
     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);
+      sb.Write("{0}\t{1:N5}\t", tree.actionStatistics.Tries, tree.actionStatistics.AverageQuality);
       if (state.children.ContainsKey(tree)) {
         foreach (var ch in state.children[tree]) {
-          sb.WriteLine("{0} {1:N5}", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
-        }
-      }
+          sb.Write("{0}\t{1:N5}\t", ch.actionStatistics.Tries, ch.actionStatistics.AverageQuality);
+        }
+      }
+      sb.WriteLine();
       return sb.ToString();
     }
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/EpsGreedy.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/EpsGreedy.cs	(revision 15424)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/EpsGreedy.cs	(revision 15425)
@@ -18,4 +18,5 @@
       public double SumQuality { get; set; }
       public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
       public int Tries { get; set; }
       public bool Done { get; set; }
@@ -26,4 +27,5 @@
         this.Tries += o.Tries;
         this.SumQuality += o.SumQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
       }
     }
@@ -60,4 +62,5 @@
       var a = action as ActionStatistics;
       a.SumQuality += q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
       a.Tries++;
     }
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/GreedyUcbTuned.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/GreedyUcbTuned.cs	(revision 15425)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/GreedyUcbTuned.cs	(revision 15425)
@@ -0,0 +1,127 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Diagnostics.Contracts;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies {
+  [StorableClass]
+  [Item("GreedyUcbTuned Policy", "UcbTuned is similar to Ucb but tracks empirical variance. Use parameter c to balance between exploitation and exploration")]
+  public class GreedyUcbTuned : PolicyBase {
+    private class ActionStatistics : IActionStatistics {
+      public double SumQuality { get; set; }
+      public double SumSqrQuality { get; set; }
+      public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
+      public double QualityVariance { get { return SumSqrQuality / Tries - AverageQuality * AverageQuality; } }
+      public int Tries { get; set; }
+      public bool Done { get; set; }
+
+      public void Add(IActionStatistics other) {
+        var o = other as ActionStatistics;
+        if (o == null) throw new ArgumentException();
+        this.Tries += o.Tries;
+        this.SumQuality += o.SumQuality;
+        this.SumSqrQuality += o.SumSqrQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
+      }
+    }
+    private List<int> buf = new List<int>();
+
+    public IFixedValueParameter<DoubleValue> CParameter {
+      get { return (IFixedValueParameter<DoubleValue>)Parameters["C"]; }
+    }
+
+    public double C {
+      get { return CParameter.Value.Value; }
+      set { CParameter.Value.Value = value; }
+    }
+
+    [StorableConstructor]
+    protected GreedyUcbTuned(bool deserializing) : base(deserializing) { }
+    protected GreedyUcbTuned(GreedyUcbTuned original, Cloner cloner)
+      : base(original, cloner) {
+    }
+    public GreedyUcbTuned()
+      : base() {
+      Parameters.Add(new FixedValueParameter<DoubleValue>("C", "Parameter to balance between exploration and exploitation 0 <= c < 100", new DoubleValue(Math.Sqrt(2))));
+    }
+
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new GreedyUcbTuned(this, cloner);
+    }
+
+    public override int Select(IEnumerable<IActionStatistics> actions, IRandom random) {
+      return Select(actions, random, C, buf);
+    }
+
+    public override void Update(IActionStatistics action, double q) {
+      var a = action as ActionStatistics;
+      a.SumQuality += q;
+      a.SumSqrQuality += q * q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
+      a.Tries++;
+    }
+
+    public override IActionStatistics CreateActionStatistics() {
+      return new ActionStatistics();
+    }
+
+    private static int Select(IEnumerable<IActionStatistics> actions, IRandom rand, double c, IList<int> buf) {
+      // select action with best quality in 90% of the cases
+      var bestBestQ = double.NegativeInfinity;
+      var idxOfBest = -1;
+      int aIdx = -1;
+      foreach (var a in actions.Cast<ActionStatistics>()) {
+        ++aIdx;
+        if (a.BestQuality > bestBestQ) {
+          bestBestQ = a.BestQuality;
+          idxOfBest = aIdx;
+        }
+      }
+      if (rand.NextDouble() < 0.1) return idxOfBest;
+
+      // determine total tries of still active actions
+      int totalTries = 0;
+      buf.Clear();
+      aIdx = -1;
+      foreach (var a in actions) {
+        ++aIdx;
+        if (a.Done) continue;
+        if (a.Tries == 0) buf.Add(aIdx);
+        else totalTries += a.Tries;
+      }
+      // if there are unvisited actions select a random action
+      if (buf.Any()) {
+        return buf[rand.Next(buf.Count)];
+      }
+      Contract.Assert(totalTries > 0);
+
+
+      double logTotalTries = Math.Log(totalTries);
+      var bestQ = double.NegativeInfinity;
+      aIdx = -1;
+      foreach (var a in actions.Cast<ActionStatistics>()) {
+        ++aIdx;
+        if (a.Done) continue;
+        var varianceBound = a.QualityVariance + Math.Sqrt(2.0 * logTotalTries / a.Tries);
+        if (varianceBound > 0.25) varianceBound = 0.25;
+        var actionQ = a.AverageQuality + c * Math.Sqrt(logTotalTries / a.Tries * varianceBound);
+        if (actionQ > bestQ) {
+          buf.Clear();
+          buf.Add(aIdx);
+          bestQ = actionQ;
+        } else if (actionQ >= bestQ) {
+          buf.Add(aIdx);
+        }
+      }
+      return buf[rand.Next(buf.Count)];
+    }
+  }
+}
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IActionStatistics.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IActionStatistics.cs	(revision 15424)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/IActionStatistics.cs	(revision 15425)
@@ -8,4 +8,5 @@
   public interface IActionStatistics {
     double AverageQuality { get; }
+    double BestQuality { get; }
     int Tries { get; }
     bool Done { get; set; }
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 15424)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/Ucb.cs	(revision 15425)
@@ -19,4 +19,5 @@
       public double SumQuality { get; set; }
       public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
       public int Tries { get; set; }
       public bool Done { get; set; }
@@ -26,4 +27,5 @@
         this.Tries += o.Tries;
         this.SumQuality += o.SumQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
       }
     }
@@ -60,4 +62,5 @@
       var a = action as ActionStatistics;
       a.SumQuality += q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
       a.Tries++;
     }
@@ -82,4 +85,6 @@
         return buf[rand.Next(buf.Count)];
       }
+
+      Debug.Assert(actions.All(a => a.Done || a.Tries > 0));
                      
       Debug.Assert(totalTries > 0);
Index: /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/UcbTuned.cs
===================================================================
--- /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/UcbTuned.cs	(revision 15424)
+++ /branches/MCTS-SymbReg-2796/HeuristicLab.Algorithms.DataAnalysis/3.4/MctsSymbolicRegression/Policies/UcbTuned.cs	(revision 15425)
@@ -19,4 +19,5 @@
       public double SumSqrQuality { get; set; }
       public double AverageQuality { get { return SumQuality / Tries; } }
+      public double BestQuality { get; internal set; }
       public double QualityVariance { get { return SumSqrQuality / Tries - AverageQuality * AverageQuality; } }
       public int Tries { get; set; }
@@ -29,4 +30,5 @@
         this.SumQuality += o.SumQuality;
         this.SumSqrQuality += o.SumSqrQuality;
+        this.BestQuality = Math.Max(this.BestQuality, other.BestQuality);
       }
     }
@@ -64,4 +66,5 @@
       a.SumQuality += q;
       a.SumSqrQuality += q * q;
+      a.BestQuality = Math.Max(a.BestQuality, q);
       a.Tries++;
     }
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 15424)
+++ /branches/MCTS-SymbReg-2796/Tests/HeuristicLab.Algorithms.DataAnalysis-3.4/MctsSymbolicRegressionTest.cs	(revision 15425)
@@ -4,4 +4,5 @@
 using System.Threading;
 using HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression.Policies;
+using HeuristicLab.Algorithms.DataAnalysis.MCTSSymbReg;
 using HeuristicLab.Data;
 using HeuristicLab.Optimization;
@@ -14,4 +15,110 @@
   [TestClass()]
   public class MctsSymbolicRegressionTest {
+    #region heuristics
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void TestHeuristics() {
+      {
+        // a, b ~ U(0, 1) should be trivial
+        var nRand = new MersenneTwister(1234);
+
+        int n = 10000; // large sample so that we can use the thresholds below
+        var a = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var b = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var x = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var y = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+
+        var z = a.Zip(b, (ai, bi) => ai * bi).ToArray();
+
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, b, z) > 0.05); // should be detected as relevant
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, x, z) > 0.05); // a and b > 0 so these should be detected as well
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, y, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, x, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, y, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(x, y, z) < 0.05);
+      }
+      {
+        // a, b ~ U(1000, 2000) also trivial
+        var nRand = new UniformDistributedRandom(new MersenneTwister(1234), 1000, 2000);
+
+        int n = 10000; // large sample so that we can use the thresholds below
+        var a = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var b = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var x = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var y = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+
+        var z = a.Zip(b, (ai, bi) => ai * bi).ToArray();
+
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, b, z) > 0.05); // should be detected as relevant
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, x, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, y, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, x, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, y, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(x, y, z) < 0.05);
+      }
+      {
+        // a, b ~ U(-1, 1) 
+        var nRand = new UniformDistributedRandom(new MersenneTwister(1234), -1, 1);
+
+        int n = 10000; // large sample so that we can use the thresholds below
+        var a = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var b = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var x = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var y = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+
+        var z = a.Zip(b, (ai, bi) => ai * bi).ToArray();
+
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, b, z) > 0.05); // should be detected as relevant
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, x, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, y, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, x, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, y, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(x, y, z) < 0.05);
+      }
+      {
+        // a, b ~ N(0, 1)
+        var nRand = new NormalDistributedRandom(new MersenneTwister(1234), 0, 1);
+
+        int n = 10000; // large sample so that we can use the thresholds below
+        var a = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var b = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var x = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var y = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+
+        var z = a.Zip(b, (ai, bi) => ai * bi).ToArray();
+
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, b, z) > 0.05); // should be detected as relevant
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, x, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, y, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, x, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, y, z) < 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(x, y, z) < 0.05);
+      }
+      {
+        // a ~ N(100, 1), b ~ N(-100, 1)
+        var nRand = new NormalDistributedRandom(new MersenneTwister(1234), 0, 1);
+        var aRand = new NormalDistributedRandom(new MersenneTwister(1234), 100, 1);
+        var bRand = new NormalDistributedRandom(new MersenneTwister(1234), -100, 1);
+
+        int n = 10000; // large sample so that we can use the thresholds below
+        var a = Enumerable.Range(0, n).Select(_ => aRand.NextDouble()).ToArray();
+        var b = Enumerable.Range(0, n).Select(_ => bRand.NextDouble()).ToArray();
+        var x = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+        var y = Enumerable.Range(0, n).Select(_ => nRand.NextDouble()).ToArray();
+
+        var z = a.Zip(b, (ai, bi) => ai * bi).ToArray();
+
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, b, z) > 0.05); // should be detected as relevant
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, x, z) > 0.05); // a > 0
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(a, y, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, x, z) > 0.05); // b < 0
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(b, y, z) > 0.05);
+        Assert.IsTrue(Heuristics.CorrelationForInteraction(x, y, z) < 0.05);
+      }
+    }
+    #endregion
+
+
     #region expression hashing
     [TestMethod]
@@ -790,9 +897,9 @@
       }
 
-      var ds = new Dataset(new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "y" }, 
+      var ds = new Dataset(new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "y" },
         new[] { x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, ys });
 
 
-      var problemData = new RegressionProblemData(ds, new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j"}, "y");
+      var problemData = new RegressionProblemData(ds, new string[] { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j" }, "y");
 
       problemData.TrainingPartition.Start = 0;
@@ -1118,7 +1225,7 @@
 
       // UCB tuned
-      // var ucbTuned = new UcbTuned();
-      // ucbTuned.C = 1.5; 
-      // mctsSymbReg.Policy = ucbTuned;
+      var ucbTuned = new UcbTuned();
+      ucbTuned.C = 1;
+      mctsSymbReg.Policy = ucbTuned;
 
 
