Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs	(revision 12014)
@@ -19,20 +19,17 @@
     // supports the grammar
     // G(E):
-    //     E -> V | V+E | V-E | V*E | V%E | (E) 
+    //     E -> V | V+E | V-E | V*E | V%E | V/E | (E) 
     //     V -> <variables>
     //     ";
 
-    // transformations: 
-    // - transform c*b*a to a*b*c (lexicographic ordering for factors, cached)
-    // - transfrom - to + (assumed optimized constants for terms)
-
+    // might produce expressions of the form |/x
+    // the pipe symbol | is used for the constant one (in comparison to other constants)
     private string sentence;
     private int syIdx;
 
     public string CanonicalRepresentation(string phrase) {
-      throw new NotImplementedException();
       InitLex(phrase);
       var e = CanonicalExpr();
-      return e.ToString();
+      return e.ToString(); 
     }
 
@@ -97,27 +94,23 @@
           NewSy();
           f = CanonicalFact();
-          f.Invert();
-          if (f != null) factors.Add(f);
+          // if there is only one term we can add multiple inverted simple factors instead of the whole inverted expression
+          if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) {
+            foreach (var invF in f.Expr.Terms.First().Factors) {
+              if (invF.ToString() == "|") continue;
+              invF.Invert();
+              factors.Add(invF);
+            }
+          } else {
+            f.Invert();
+            if (f != null) factors.Add(f);
+          }
         }
         curSy = CurSy();
       }
+
+      factors = CancelFactors(factors).ToList();
       return ExpandFactors(factors);
     }
 
-    /*
-    private List<Factor> CancelFactors(Term t) {
-      var nonInvF = t.Factors.Where(f => !f.IsInverse).ToArray();
-      var invF = t.Factors.Where(f => f.IsInverse).ToArray();
-
-      var result = new List<Factor>();
-      foreach (var f in nonInvF) {
-        if (!invF.Contains(f)) {
-          result.Add(f);
-        }
-      }
-      if (result.Count == 0) result.Add(new Factor('1'));
-      return result;
-    }
-    */
     // canonical fact returns a factor (either a singe variable, or a set of terms)
     private Factor CanonicalFact() {
@@ -144,5 +137,5 @@
 
     // a list of factors (symbols, or expressions, and possibly inverses are read
-    // a lis to factors symbols or expressions and possibly inverses are produced
+    // a list to factors symbols or expressions and possibly inverses are produced
     // all non-inverse expression factors are expanded
     private Expr ExpandFactors(IEnumerable<Factor> factors) {
@@ -154,5 +147,5 @@
       Expr currentFact = null;
       var firstFactor = factors.First();
-      if (firstFactor.IsSimpleFactor) currentFact = new Expr(new Term(firstFactor));
+      if (firstFactor.IsSimpleFactor || firstFactor.IsInverse) currentFact = new Expr(new Term(firstFactor));
       else currentFact = firstFactor.Expr;
 
@@ -180,17 +173,27 @@
       var results = new List<Factor>(factors);
       foreach (var f in factorsArr) {
-        if (f.ToString() == "1") results.Remove(f);
+        if (f.ToString() == "|") results.Remove(f);
+        if (f.ToString() == "|/(|)") results.Remove(f);
         if (f.IsInverse) {
           // find matching
           Factor match;
-          if (f.IsSimpleFactor) match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Symbol.Equals(other.Symbol));
-          else match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Expr.Equals(other.Expr));
+          match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Cancels(other));
           if (match != null) {
+            results.Remove(f);
+            var idx = results.IndexOf(match);
+
             results.Remove(match);
-            results.Remove(f);
+            if (!results.Any())
+              results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one
+
+            // also mark as cancelled in the factorsArr
+            idx = Array.IndexOf(factorsArr, match);
+            factorsArr[idx] = new Factor('|');
           }
         }
       }
-      if (results.Count == 0) results.Add(new Factor('1'));
+      // remove all unnecessary "1* factors"
+
+      if (results.Count == 0) results.Add(new Factor('|'));
       return results;
     }
@@ -273,4 +276,11 @@
         this.inv = !inv;
       }
+      public bool Cancels(Factor other) {
+        if (this.inv == other.inv) return false;
+        if (this.Expr != null && other.Expr == null) return false;
+        if (this.Expr == null && other.Expr != null) return false;
+        if (Expr == null) return this.Symbol.Equals(other.symbol);
+        else return this.Expr.CompareTo(other.Expr) == 0;
+      }
 
       public int CompareTo(Factor other) {
@@ -294,5 +304,5 @@
         var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
         if (IsInverse) {
-          return "1/" + s;
+          return "|/" + s;
         } else return s;
       }
@@ -356,8 +366,8 @@
         var other = obj as Expr;
         if (other == null) return false;
-        //if (this.Inverse != other.Inverse) return false;
         if (this.Terms.Count() != other.Terms.Count()) return false;
         return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
       }
+
       public override int GetHashCode() {
         var h = 31415;
@@ -388,21 +398,4 @@
       return ContainsNonTerminal(term.Factors);
     }
-
-
-    /*
-
-    internal class FactorComparer : IComparer<char> {
-      public int Compare(char x, char y) {
-        if (IsNonTerminal(x) && !IsNonTerminal(y)) {
-          return 1;
-        } else if (!IsNonTerminal(x) && IsNonTerminal(y)) {
-          return -1;
-        } else if (IsNonTerminal(x) && IsNonTerminal(y)) {
-          return x.CompareTo(y);
-        } else {
-          return x.CompareTo(y);
-        }
-      }
-    }*/
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs	(revision 12014)
@@ -17,8 +17,9 @@
     // does not compile to IL it is only necessary to calculate gradients for parameter optimization
     // Expr -> Term { ('+' | '-' | '^' ) Term } 
-    // Term -> Fact { ('*' | '%') Fact }
-    // Fact -> '!' Expr | '(' Expr ')' | Var | const
+    // Term -> Fact { ('*' | '%' | '/') Fact }
+    // Fact -> '!' Expr | '(' Expr ')' | Var | const | one
     // Var -> 'a'..'z'
     // const -> '0' .. '9'
+    // one -> |    // pipe symbol for constant one instead of ERC 1
 
     // constants are completely ignored, instead we introduce a multiplicative constant factor for each term and an additive constant term for each expression
@@ -94,5 +95,5 @@
       if (f != null) factors.Add(f);
       var curSy = CurSy();
-      while (curSy == '*' || curSy == '%') {
+      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
         if (curSy == '*') {
           NewSy();
@@ -134,4 +135,9 @@
         r = variables[varIdx];
         NewSy();
+      } else if (curSy == '|') {
+        // pipe symbol is used in the expressionextender to represent constant one (|/x). 
+        // this is necessary because we also use symbols 0..9 as indices for ERCs
+        r = 1.0;
+        NewSy();
       } else if (curSy >= '0' && curSy <= '9') {
         int o = (byte)curSy - (byte)'0';
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 12014)
@@ -9,4 +9,5 @@
 using System.Text;
 using AutoDiff;
+using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Common;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -128,4 +129,7 @@
         return OptimizeConstantsAndEvaluate(sentence);
       else {
+        var extender = new ExpressionExtender();
+
+        Debug.Assert(SimpleEvaluate(sentence) == SimpleEvaluate(extender.CanonicalRepresentation(sentence)));
         return SimpleEvaluate(sentence);
       }
@@ -143,12 +147,10 @@
 
     public string CanonicalRepresentation(string phrase) {
-      return phrase;
+      var extender = new ExpressionExtender();
+      return extender.CanonicalRepresentation(phrase);
     }
 
     public IEnumerable<Feature> GetFeatures(string phrase) {
-      // first generate canonical expression (which must not contain ())
-      // recursively split into expressions
-      // for each expression split into terms
-      // for each term order factors to canonical // ../E = * 1/E
+      phrase = CanonicalRepresentation(phrase);
       return new Feature[] { new Feature(phrase, 1.0) };
     }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs	(revision 12014)
@@ -92,5 +92,5 @@
       r = Fact(d, erc);
       var curSy = CurSy();
-      while (curSy == '*' || curSy == '%') {
+      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
         if (curSy == '*') {
           NewSy();
@@ -124,4 +124,9 @@
         r = d[o];
         NewSy();
+      } else if (curSy == '|') {
+        // pipe symbol is used in the expressionextender to represent constant one (|/x). 
+        // this is necessary because we also use symbols 0..9 as indices for ERCs
+        r = 1.0;
+        NewSy();
       } else /* if (curSy >= '0' && curSy <= '9') */ {
         int o = (byte)curSy - (byte)'0';
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs	(revision 12014)
@@ -184,5 +184,5 @@
         Debug.Assert(maxLenOfReplacement > 0);
 
-        var alts = GetTerminalAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
+        var alts = GetAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
         Debug.Assert(alts.Any());
 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/RunDemo.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/RunDemo.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/RunDemo.cs	(revision 12014)
@@ -7,10 +7,15 @@
 using HeuristicLab.Algorithms.Bandits.BanditPolicies;
 using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
+using HeuristicLab.Algorithms.Bandits.Models;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
 
 namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
-  class RunDemo {
-    private static void RunGridTest() {
-      int maxIterations = 200000; // for poly-10 with 50000 evaluations no successful try with hl yet
+  [TestClass]
+  public class RunDemo {
+    [TestMethod]
+    public void RunGridTest() {
+      int maxIterations = 20000; // for poly-10 with 50000 evaluations no successful try with hl yet
       //var globalRandom = new Random(31415);
       var localRandSeed = new Random().Next();
@@ -19,72 +24,72 @@
       var policyFactories = new Func<IBanditPolicy>[]
         {
-         //() => new RandomPolicy(), 
-         // () => new ActiveLearningPolicy(),  
-         //() => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"), 
-         //() => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"), 
-         //() => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"), 
-         //() => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"), 
-         ////() => new GaussianThompsonSamplingPolicy(), 
-         //() => new GaussianThompsonSamplingPolicy(true), 
-         //() => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)), 
-         //() => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), 
-         ////() => new BernoulliThompsonSamplingPolicy(),
-         //() => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)), 
-         //() => new EpsGreedyPolicy(0.01), 
-         //() => new EpsGreedyPolicy(0.05), 
-         //() => new EpsGreedyPolicy(0.1), 
-         //() => new EpsGreedyPolicy(0.2), 
-         //() => new EpsGreedyPolicy(0.5), 
-         //() => new UCTPolicy(0.01),
-         //() => new UCTPolicy(0.05),
-         //() => new UCTPolicy(0.1),
-         //() => new UCTPolicy(0.5),
-         //() => new UCTPolicy(1),
-         //() => new UCTPolicy(2),
-         //() => new UCTPolicy( 5),
-         //() => new UCTPolicy( 10),
-         //() => new ModifiedUCTPolicy(0.01),
-         //() => new ModifiedUCTPolicy(0.05),
-         //() => new ModifiedUCTPolicy(0.1),
-         //() => new ModifiedUCTPolicy(0.5),
-         //() => new ModifiedUCTPolicy(1),
-         //() => new ModifiedUCTPolicy(2),
-         //() => new ModifiedUCTPolicy( 5),
-         //() => new ModifiedUCTPolicy( 10),
-         //() => new UCB1Policy(), 
-         //() => new UCB1TunedPolicy(), 
-         //() => new UCBNormalPolicy(), 
-         //() => new BoltzmannExplorationPolicy(1),
-         //() => new BoltzmannExplorationPolicy(10),
-         //() => new BoltzmannExplorationPolicy(20),
-         //() => new BoltzmannExplorationPolicy(100),
-         //() => new BoltzmannExplorationPolicy(200),
-         //() => new BoltzmannExplorationPolicy(500),
-         // () => new ChernoffIntervalEstimationPolicy( 0.01), 
-         // () => new ChernoffIntervalEstimationPolicy( 0.05),
-         // () => new ChernoffIntervalEstimationPolicy( 0.1),
-         // () => new ChernoffIntervalEstimationPolicy( 0.2),
-         //() => new ThresholdAscentPolicy(5, 0.01), 
-         //() => new ThresholdAscentPolicy(5, 0.05),
-         //() => new ThresholdAscentPolicy(5, 0.1),
-         //() => new ThresholdAscentPolicy(5, 0.2),
-         //() => new ThresholdAscentPolicy(10, 0.01), 
-         //() => new ThresholdAscentPolicy(10, 0.05),
-         //() => new ThresholdAscentPolicy(10, 0.1),
-         //() => new ThresholdAscentPolicy(10, 0.2),
-         //() => new ThresholdAscentPolicy(50, 0.01), 
-         //() => new ThresholdAscentPolicy(50, 0.05),
-         //() => new ThresholdAscentPolicy(50, 0.1),
-         //() => new ThresholdAscentPolicy(50, 0.2),
-         //() => new ThresholdAscentPolicy(100, 0.01), 
+         () => new RandomPolicy(), 
+          () => new ActiveLearningPolicy(),  
+         () => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"), 
+         //() => new GaussianThompsonSamplingPolicy(), 
+         () => new GaussianThompsonSamplingPolicy(true), 
+         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)), 
+         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), 
+         //() => new BernoulliThompsonSamplingPolicy(),
+         () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)), 
+         () => new EpsGreedyPolicy(0.01), 
+         () => new EpsGreedyPolicy(0.05), 
+         () => new EpsGreedyPolicy(0.1), 
+         () => new EpsGreedyPolicy(0.2), 
+         () => new EpsGreedyPolicy(0.5), 
+         () => new UCTPolicy(0.01),
+         () => new UCTPolicy(0.05),
+         () => new UCTPolicy(0.1),
+         () => new UCTPolicy(0.5),
+         () => new UCTPolicy(1),
+         () => new UCTPolicy(2),
+         () => new UCTPolicy( 5),
+         () => new UCTPolicy( 10),
+         () => new ModifiedUCTPolicy(0.01),
+         () => new ModifiedUCTPolicy(0.05),
+         () => new ModifiedUCTPolicy(0.1),
+         () => new ModifiedUCTPolicy(0.5),
+         () => new ModifiedUCTPolicy(1),
+         () => new ModifiedUCTPolicy(2),
+         () => new ModifiedUCTPolicy( 5),
+         () => new ModifiedUCTPolicy( 10),
+         () => new UCB1Policy(), 
+         () => new UCB1TunedPolicy(), 
+         () => new UCBNormalPolicy(), 
+         () => new BoltzmannExplorationPolicy(1),
+         () => new BoltzmannExplorationPolicy(10),
+         () => new BoltzmannExplorationPolicy(20),
+         () => new BoltzmannExplorationPolicy(100),
+         () => new BoltzmannExplorationPolicy(200),
+         () => new BoltzmannExplorationPolicy(500),
+          () => new ChernoffIntervalEstimationPolicy( 0.01), 
+          () => new ChernoffIntervalEstimationPolicy( 0.05),
+          () => new ChernoffIntervalEstimationPolicy( 0.1),
+          () => new ChernoffIntervalEstimationPolicy( 0.2),
+         () => new ThresholdAscentPolicy(5, 0.01), 
+         () => new ThresholdAscentPolicy(5, 0.05),
+         () => new ThresholdAscentPolicy(5, 0.1),
+         () => new ThresholdAscentPolicy(5, 0.2),
+         () => new ThresholdAscentPolicy(10, 0.01), 
+         () => new ThresholdAscentPolicy(10, 0.05),
+         () => new ThresholdAscentPolicy(10, 0.1),
+         () => new ThresholdAscentPolicy(10, 0.2),
+         () => new ThresholdAscentPolicy(50, 0.01), 
+         () => new ThresholdAscentPolicy(50, 0.05),
+         () => new ThresholdAscentPolicy(50, 0.1),
+         () => new ThresholdAscentPolicy(50, 0.2),
+         () => new ThresholdAscentPolicy(100, 0.01), 
          () => new ThresholdAscentPolicy(100, 0.05),
-         //() => new ThresholdAscentPolicy(100, 0.1),
-         //() => new ThresholdAscentPolicy(100, 0.2),
-         //() => new ThresholdAscentPolicy(500, 0.01), 
-         //() => new ThresholdAscentPolicy(500, 0.05),
-         //() => new ThresholdAscentPolicy(500, 0.1),
-         //() => new ThresholdAscentPolicy(500, 0.2),
-         //() => new ThresholdAscentPolicy(5000, 0.01), 
-         //() => new ThresholdAscentPolicy(10000, 0.01), 
+         () => new ThresholdAscentPolicy(100, 0.1),
+         () => new ThresholdAscentPolicy(100, 0.2),
+         () => new ThresholdAscentPolicy(500, 0.01), 
+         () => new ThresholdAscentPolicy(500, 0.05),
+         () => new ThresholdAscentPolicy(500, 0.1),
+         () => new ThresholdAscentPolicy(500, 0.2),
+         () => new ThresholdAscentPolicy(5000, 0.01), 
+         () => new ThresholdAscentPolicy(10000, 0.01), 
         };
 
@@ -96,10 +101,11 @@
         //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
         //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
-        (rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
+        //(rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
+        (rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17)
       };
 
       foreach (var instanceFactory in instanceFactories) {
         foreach (var useCanonical in new bool[] { true /*, false */ }) {
-          foreach (var randomTries in new int[] { 1 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
+          foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
             foreach (var policyFactory in policyFactories) {
               var myRandomTries = randomTries;
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj	(revision 12014)
@@ -8,5 +8,5 @@
     <AppDesignerFolder>Properties</AppDesignerFolder>
     <RootNamespace>HeuristicLab.Problems.GrammaticalOptimization.Test</RootNamespace>
-    <AssemblyName>HeuristicLab.Problems.GrammaticalOptimization.Test</AssemblyName>
+    <AssemblyName>Test</AssemblyName>
     <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
     <FileAlignment>512</FileAlignment>
@@ -68,4 +68,5 @@
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="TestSolvers.cs" />
+    <Compile Include="TestTunedSettings.cs" />
   </ItemGroup>
   <ItemGroup>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs	(revision 12014)
@@ -5,4 +5,7 @@
 using System.Threading.Tasks;
 using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
+using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
 
@@ -64,15 +67,16 @@
       Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
       Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
+      Assert.AreEqual("|/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
     }
     [TestMethod]
     public void TestDivisionExpansion() {
       var extender = new ExpressionExtender();
-      Assert.AreEqual("a*1/c+b*1/c", extender.CanonicalRepresentation("(b+a)%c"));
-      Assert.AreEqual("a*1/c*1/d+b*1/c*1/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
-      Assert.AreEqual("a*1/(c+d)+b*1/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
-      Assert.AreEqual("a*b*1/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
+      Assert.AreEqual("a*|/c+b*|/c", extender.CanonicalRepresentation("(b+a)%c"));
+      Assert.AreEqual("a*|/c*|/d+b*|/c*|/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
+      Assert.AreEqual("a*|/(c+d)+b*|/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
+      Assert.AreEqual("a*b*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
 
-      Assert.AreEqual("a*b*1/(a+b)*1/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
-      Assert.AreEqual("a*b*1/(a*1/e+b*1/e)*1/(c+d)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
+      Assert.AreEqual("a*b*|/(a+b)*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
+      Assert.AreEqual("a*b*|/(c+d)*|/(a*|/e+b*|/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
       // a*b*e%(c+d)%(a+b)
     }
@@ -80,12 +84,35 @@
     public void TestDivisionCancellation() {
       var extender = new ExpressionExtender();
-      Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
+      Assert.AreEqual("|", extender.CanonicalRepresentation("a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
-      Assert.AreEqual("1/a", extender.CanonicalRepresentation("(a%a)%a"));
-      Assert.AreEqual("1/a", extender.CanonicalRepresentation("a%a%a"));
+      Assert.AreEqual("|/a", extender.CanonicalRepresentation("(a%a)%a"));
+      Assert.AreEqual("|/a", extender.CanonicalRepresentation("a%a%a"));
       Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
-      Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
-      Assert.AreEqual("1/a+1/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
-      Assert.AreEqual("a*1/(a*c*1/b+e*1/d*1/f)+b*1/(a*c*1/b+e*1/d*1/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
+      Assert.AreEqual("|", extender.CanonicalRepresentation("(a+b)%(b+a)"));
+      Assert.AreEqual("|/a+|/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
+      Assert.AreEqual("a*|/(a*c*|/b+e*|/d*|/f)+b*|/(a*c*|/b+e*|/d*|/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
+      Assert.AreEqual("|", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
+      Assert.AreEqual("|", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
+    }
+
+    [TestMethod]
+    public void TestRandomExpressions() {
+      // samples sentences for the Tower dataset with the random MCTS policy 
+      // and evaluates the original and the extended expression
+      // the results must be the same
+
+      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
+      var random = new Random(31415);
+      var solver = new SequentialSearch(problem, 30, random, 0, new RandomPolicy(problem, true));
+
+      var extender = new ExpressionExtender();
+
+      solver.SolutionEvaluated += (sentence, quality) => {
+        var canonicalSentence = extender.CanonicalRepresentation(sentence);
+
+        Assert.AreEqual(problem.SimpleEvaluate(sentence), problem.SimpleEvaluate(canonicalSentence), 1E-4, string.Format("{0} <> {1}", sentence, canonicalSentence));
+      };
+
+      solver.Run(10000);
     }
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs	(revision 12013)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs	(revision 12014)
@@ -1,4 +1,6 @@
 ﻿using System;
 using System.Linq;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
 using HeuristicLab.Algorithms.GeneticProgramming;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
@@ -12,7 +14,12 @@
     [TestMethod]
     public void TestGetDataDescriptors() {
+      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
+      Assert.IsNotNull(problem);
+    }
 
+    [TestMethod]
+    public void TestConstantOptimization() {
+      double r2;
       var problem = new SymbolicRegressionProblem(new Random(), "Tower");
-      double r2;
       Assert.AreEqual(problem.Evaluate("a*b"), problem.OptimizeConstantsAndEvaluate("a*b"));
       Assert.AreEqual(problem.OptimizeConstantsAndEvaluate("a*b"), problem.Evaluate("a*b"));
@@ -23,4 +30,16 @@
       Assert.IsTrue(problem.OptimizeConstantsAndEvaluate("0*a+1*b") >= problem.Evaluate("a+b"));
     }
+
+    [TestMethod]
+    public void TestSequentialSolverForTower() {
+      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
+      var random = new Random(31415);
+      var solver = new SequentialSearch(problem, 30, random, 0, new GenericGrammarPolicy(problem, new UCB1TunedPolicy(), true));
+      solver.FoundNewBestSolution += (s, d) => {
+        Console.WriteLine("{0:F3} {1}", d, s);
+      };
+      solver.Run(100);
+    }
+
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestTunedSettings.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestTunedSettings.cs	(revision 12014)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestTunedSettings.cs	(revision 12014)
@@ -0,0 +1,192 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Globalization;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
+using HeuristicLab.Algorithms.Bandits.Models;
+using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Common;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
+
+namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
+  [TestClass]
+  public class TestTunedSettings {
+    private const int randSeed = 31415;
+    internal class Configuration {
+      public IProblem Problem;
+      public int MaxSize;
+      public int RandSeed;
+
+      public override string ToString() {
+        return string.Format("{0} {1} {2}", RandSeed, Problem, MaxSize);
+      }
+    }
+    [TestMethod]
+    // this configuration worked especially well in the experiments
+    public void TestThresholdAscentArtificialAnt() {
+      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
+
+      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
+      {
+        (randSeed) => (ISymbolicExpressionTreeProblem)new SantaFeAntProblem(), 
+      };
+
+      var policyFactories = new Func<IBanditPolicy>[]
+        {
+         () => new RandomPolicy(), 
+          () => new ActiveLearningPolicy(),  
+         () => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"), 
+         () => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"), 
+         //() => new GaussianThompsonSamplingPolicy(), 
+         () => new GaussianThompsonSamplingPolicy(true), 
+         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)), 
+         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), 
+         //() => new BernoulliThompsonSamplingPolicy(),
+         () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)), 
+         () => new EpsGreedyPolicy(0.01), 
+         () => new EpsGreedyPolicy(0.05), 
+         () => new EpsGreedyPolicy(0.1), 
+         () => new EpsGreedyPolicy(0.2), 
+         () => new EpsGreedyPolicy(0.5), 
+         () => new UCTPolicy(0.01),
+         () => new UCTPolicy(0.05),
+         () => new UCTPolicy(0.1),
+         () => new UCTPolicy(0.5),
+         () => new UCTPolicy(1),
+         () => new UCTPolicy(2),
+         () => new UCTPolicy( 5),
+         () => new UCTPolicy( 10),
+         () => new ModifiedUCTPolicy(0.01),
+         () => new ModifiedUCTPolicy(0.05),
+         () => new ModifiedUCTPolicy(0.1),
+         () => new ModifiedUCTPolicy(0.5),
+         () => new ModifiedUCTPolicy(1),
+         () => new ModifiedUCTPolicy(2),
+         () => new ModifiedUCTPolicy( 5),
+         () => new ModifiedUCTPolicy( 10),
+         () => new UCB1Policy(), 
+         () => new UCB1TunedPolicy(), 
+         () => new UCBNormalPolicy(), 
+         () => new BoltzmannExplorationPolicy(1),
+         () => new BoltzmannExplorationPolicy(10),
+         () => new BoltzmannExplorationPolicy(20),
+         () => new BoltzmannExplorationPolicy(100),
+         () => new BoltzmannExplorationPolicy(200),
+         () => new BoltzmannExplorationPolicy(500),
+          () => new ChernoffIntervalEstimationPolicy( 0.01), 
+          () => new ChernoffIntervalEstimationPolicy( 0.05),
+          () => new ChernoffIntervalEstimationPolicy( 0.1),
+          () => new ChernoffIntervalEstimationPolicy( 0.2),
+         () => new ThresholdAscentPolicy(5, 0.01), 
+         () => new ThresholdAscentPolicy(5, 0.05),
+         () => new ThresholdAscentPolicy(5, 0.1),
+         () => new ThresholdAscentPolicy(5, 0.2),
+         () => new ThresholdAscentPolicy(10, 0.01), 
+         () => new ThresholdAscentPolicy(10, 0.05),
+         () => new ThresholdAscentPolicy(10, 0.1),
+         () => new ThresholdAscentPolicy(10, 0.2),
+         () => new ThresholdAscentPolicy(50, 0.01), 
+         () => new ThresholdAscentPolicy(50, 0.05),
+         () => new ThresholdAscentPolicy(50, 0.1),
+         () => new ThresholdAscentPolicy(50, 0.2),
+         () => new ThresholdAscentPolicy(100, 0.01), 
+         () => new ThresholdAscentPolicy(100, 0.05),
+         () => new ThresholdAscentPolicy(100, 0.1),
+         () => new ThresholdAscentPolicy(100, 0.2),
+         () => new ThresholdAscentPolicy(500, 0.01), 
+         () => new ThresholdAscentPolicy(500, 0.05),
+         () => new ThresholdAscentPolicy(500, 0.1),
+         () => new ThresholdAscentPolicy(500, 0.2),
+         () => new ThresholdAscentPolicy(5000, 0.01), 
+         () => new ThresholdAscentPolicy(10000, 0.01), 
+        };
+      var maxSizes = new int[] { 17 };  // necessary size for ant programm
+      int nReps = 20;
+      int maxIterations = 20000;
+      foreach (var instanceFactory in instanceFactories) {
+        var sumBestQ = 0.0;
+        var sumItersToBest = 0;
+        double fractionSolved = 0.0;
+        foreach (var conf in GenerateConfigurations(instanceFactory, nReps, maxSizes)) {
+          foreach (var policy in policyFactories) {
+            var prob = conf.Problem;
+            var maxLen = conf.MaxSize;
+            var rand = new Random(conf.RandSeed);
+
+            var solver = new SequentialSearch(prob, maxLen, rand, 0, new GenericGrammarPolicy(prob, policy(), true));
+            var problemName = prob.GetType().Name;
+            var policyName = policy().ToString();
+            double bestQ; int itersToBest;
+            RunSolver(solver, problemName, policyName, 1.0, maxIterations, maxLen, out bestQ, out itersToBest);
+            sumBestQ += bestQ;
+            sumItersToBest += itersToBest;
+            if (bestQ.IsAlmost(1.0)) fractionSolved += 1.0 / nReps;
+          }
+        }
+        // Assert.AreEqual(0.85, fractionSolved, 1E-6);
+        // Assert.AreEqual(0.99438202247191, sumBestQ / nReps, 1E-6);
+        // Assert.AreEqual(5461.7, sumItersToBest / (double)nReps, 1E-6);
+      }
+
+    }
+
+    private IEnumerable<Configuration> GenerateConfigurations(Func<int, ISymbolicExpressionTreeProblem> problemFactory,
+     int nReps,
+     IEnumerable<int> maxSizes
+     ) {
+      var seedRand = new Random(randSeed);
+      // the problem seed is the same for all configuratons 
+      // this guarantees that we solve the _same_ problem each time
+      // with different solvers and multiple repetitions
+      var problemSeed = randSeed;
+      for (int i = 0; i < nReps; i++) {
+        // in each repetition use the same random seed for all solver configuratons
+        // do nReps with different seeds for each configuration
+        var solverSeed = seedRand.Next();
+        foreach (var maxSize in maxSizes) {
+          yield return new Configuration {
+            MaxSize = maxSize,
+            Problem = problemFactory(problemSeed),
+            RandSeed = solverSeed
+          };
+        }
+      }
+    }
+
+
+
+
+    private static void RunSolver(ISolver solver, string problemName, string policyName, double bestKnownQuality, int maxIters, int maxSize,
+      out double bestQ, out int itersToBest) {
+      int iterations = 0;
+      var globalStatistics = new SentenceSetStatistics(bestKnownQuality);
+      var solverName = solver.GetType().Name;
+      double bestQuality = double.NegativeInfinity;
+      int iterationsToBest = -1;
+      solver.SolutionEvaluated += (sentence, quality) => {
+        iterations++;
+        globalStatistics.AddSentence(sentence, quality);
+        if (quality > bestQuality) {
+          bestQuality = quality;
+          iterationsToBest = iterations;
+        }
+        if (iterations % 1000 == 0) {
+          Console.WriteLine("\"{0,25}\" \"{1,25}\" {2} \"{3,25}\" {4}", solverName, policyName, maxSize, problemName, globalStatistics);
+        }
+      };
+
+
+      solver.Run(maxIters);
+
+      bestQ = bestQuality;
+      itersToBest = iterationsToBest;
+    }
+  }
+}
