Index: /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs	(revision 12297)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs	(revision 12298)
@@ -48,8 +48,5 @@
       foreach (var afterState in afterStates) {
         if (!Done(afterState)) {
-          if (GetTries(afterState) == 0) 
-            activeAfterStates[idx] = double.PositiveInfinity;
-          else
-            activeAfterStates[idx] = GetValue(afterState);
+          activeAfterStates[idx] = CalculateValue(afterState);
           actionIndexMap[idx] = originalIdx;
           idx++;
@@ -58,11 +55,49 @@
       }
 
+
       //var eps = Math.Max(500.0 / (GetTries(curState) + 1), 0.01);
       //var eps = 10.0 / Math.Sqrt(GetTries(curState) + 1);
-      var eps = 0.2;
+      var eps = 0.01;
       selectedStateIdx = actionIndexMap[SelectEpsGreedy(random, activeAfterStates.Take(idx), eps)];
 
+      UpdateValue(curState, afterStates);
+
       return true;
     }
+
+    private double CalculateValue(string chain) {
+      var features = problem.GetFeatures(chain);
+      var sum = 0.0;
+      foreach (var f in features) {
+        // if (GetTries(f.Id) == 0)
+        //   sum = 0.0;
+        // else
+        sum += GetValue(f.Id) * f.Value;
+      }
+      return sum;
+    }
+
+    private void UpdateValue(string curChain, IEnumerable<string> alternatives) {
+      const double gamma = 1;
+      const double alpha = 0.01;
+      var maxNextQ = alternatives
+          .Select(CalculateValue).Max();
+
+      var delta = gamma * maxNextQ - CalculateValue(curChain);
+
+      foreach (var f in problem.GetFeatures(curChain)) {
+
+        Q[f.Id] = GetValue(f.Id) + alpha * delta * f.Value;
+      }
+    }
+
+    private void UpdateLastValue(string terminalChain, double reward) {
+      const double alpha = 0.01;
+      var delta = reward - CalculateValue(terminalChain);
+      foreach (var f in problem.GetFeatures(terminalChain)) {
+        Q[f.Id] = GetValue(f.Id) + alpha * delta * f.Value;
+      }
+    }
+
 
     private int SelectBoltzmann(Random random, IEnumerable<double> qs, double beta = 10) {
@@ -121,29 +156,27 @@
 
     public void UpdateReward(IEnumerable<string> chainTrajectory, double reward) {
-      const double gamma = 0.95;
-      const double minAlpha = 0.01;
-      var reverseChains = chainTrajectory.Reverse();
-      var terminalChain = reverseChains.First();
-
-      var terminalState = CalcState(terminalChain);
-      T[terminalState] = GetTries(terminalChain) + 1;
-      double alpha = Math.Max(1.0 / GetTries(terminalChain), minAlpha);
-      Q[terminalState] = (1 - alpha) * GetValue(terminalChain) + alpha * reward;
-
-      foreach (var chain in reverseChains.Skip(1)) {
-
-        var maxNextQ = followStates[chain]
-          //.Where(s=>!Done(s))
-          .Select(GetValue).Max();
-        T[CalcState(chain)] = GetTries(chain) + 1;
-
-        alpha = Math.Max(1.0 / GetTries(chain), minAlpha);
-        Q[CalcState(chain)] = (1 - alpha) * GetValue(chain) + gamma * alpha * maxNextQ; // direct contribution is zero
-      }
+      // // only updates the last chain because we already update values after each step
+      // var reverseChains = chainTrajectory.Reverse();
+      // var terminalChain = reverseChains.First();
+      // 
+      // UpdateValue(terminalChain, reward);
+      // 
+      // foreach (var chain in reverseChains.Skip(1)) {
+      // 
+      //   var maxNextQ = followStates[chain]
+      //     //.Where(s=>!Done(s))
+      //     .Select(GetValue).Max();
+      // 
+      //   UpdateValue(chain, maxNextQ);
+      // }
+      var terminalChain = chainTrajectory.Last();
+      UpdateLastValue(terminalChain, reward);
       if (problem.Grammar.IsTerminal(terminalChain)) MarkAsDone(terminalChain);
     }
+
 
     public void Reset() {
       Q.Clear();
+      T.Clear();
       done.Clear();
       followStates.Clear();
@@ -160,33 +193,49 @@
 
 
-    public int GetTries(string state) {
-      var s = CalcState(state);
-      if (T.ContainsKey(s)) return T[s];
+    public int GetTries(string fId) {
+      if (T.ContainsKey(fId)) return T[fId];
       else return 0;
     }
 
-    public double GetValue(string chain) {
-      var s = CalcState(chain);
-      if (Q.ContainsKey(s)) return Q[s];
+    public double GetValue(string fId) {
+      // var s = CalcState(chain);
+      if (Q.ContainsKey(fId)) return Q[fId];
       else return 0.0; // TODO: check alternatives
     }
 
-    private string CalcState(string chain) {
-      var f = problem.GetFeatures(chain);
-      // this policy only works for problems that return exactly one feature (the 'state')
-      if (f.Skip(1).Any()) throw new ArgumentException();
-      return f.First().Id;
-    }
+    // private string CalcState(string chain) {
+    //   var f = problem.GetFeatures(chain);
+    //   // this policy only works for problems that return exactly one feature (the 'state')
+    //   if (f.Skip(1).Any()) throw new ArgumentException();
+    //   return f.First().Id;
+    // }
 
     public void PrintStats() {
       Console.WriteLine(Q.Values.Max());
-      var topTries = Q.Keys.OrderByDescending(key => T[key]).Take(50);
-      var topQs = Q.Keys.Where(key => key.Contains(",")).OrderByDescending(key => Q[key]).Take(50);
-      foreach (var t in topTries.Zip(topQs, Tuple.Create)) {
-        var id1 = t.Item1;
-        var id2 = t.Item2;
-        Console.WriteLine("{0,30} {1,6} {2:N4} {3,30} {4,6} {5:N4}", id1, T[id1], Q[id1], id2, T[id2], Q[id2]);
-      }
-
+      // var topTries = Q.Keys.OrderByDescending(key => T[key]).Take(50);
+      // var topQs = Q.Keys/*.Where(key => key.Contains("E"))*/.OrderByDescending(key => Q[key]).Take(50);
+      // foreach (var t in topTries.Zip(topQs, Tuple.Create)) {
+      //   var id1 = t.Item1;
+      //   var id2 = t.Item2;
+      //   Console.WriteLine("{0,30} {1,6} {2:N4} {3,30} {4,6} {5:N4}", id1, T[id1], Q[id1], id2, T[id2], Q[id2]);
+      // }
+
+      foreach (var option in new String[]
+      {
+        "a*b", "c*d", "a*b+c*d", "e*f", "a*b+c*d+e*f",
+        "a*b+a*b", "c*d+c*d",
+        "a*a", "a*b","a*c","a*d","a*e","a*f","a*g","a*h","a*i","a*j",
+        "a*b","c*d","e*f","a*c","a*f","a*i","a*i*g","c*f","c*f*j",
+        "b+c","a+c","b+d","a+d",
+        "a*b+c*d+e*f", "a*b+c*d+e*f+a", "a*b+c*d+e*f+b", "a*b+c*d+e*f+c", "a*b+c*d+e*f+d","a*b+c*d+e*f+e",  "a*b+c*d+e*f+f", "a*b+c*d+e*f+g", "a*b+c*d+e*f+h", "a*b+c*d+e*f+i", "a*b+c*d+e*f+j", 
+        "a*b+c*d+e*f+a*g*i+c*j*f"
+      }) {
+        Console.WriteLine("{0,-10} {1:N5}", option, CalculateValue(option));
+      }
+
+      // var topQs = Q.Keys/*.Where(key => key.Contains("E"))*/.OrderByDescending(key => Math.Abs(Q[key])).Take(10);
+      // foreach (var t in topQs) {
+      //   Console.WriteLine("{0,30} {1:N4}", t, Q[t]);
+      // }
     }
   }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/PartialExpressionInterpreter.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/PartialExpressionInterpreter.cs	(revision 12297)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/PartialExpressionInterpreter.cs	(revision 12298)
@@ -2,4 +2,5 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Security.Policy;
 using HeuristicLab.Common;
 
@@ -9,6 +10,6 @@
     private string sentence;
     private int syIdx;
+    private HashSet<double> intermediateValues = new HashSet<double>();
     private Stack<double> stack = new Stack<double>();
-    private Stack<char> opStack = new Stack<char>();
     // interprets sentences from L(G(Expr)):
     // Expr -> Term { ('+' | '-' | '^' ) Term } 
@@ -22,13 +23,14 @@
     // The constant symbols '0' .. '9' are treated as ERC indices
 
-    public Stack<double> Interpret(string sentence, double[] vars) {
+    public IEnumerable<double> Interpret(string sentence, double[] vars) {
       return Interpret(sentence, vars, emptyErc);
     }
 
-    public Stack<double> Interpret(string sentence, double[] vars, double[] erc) {
+    public IEnumerable<double> Interpret(string sentence, double[] vars, double[] erc) {
       InitLex(sentence);
-      stack.Clear(); opStack.Clear();
+      intermediateValues.Clear();
+      stack.Clear();
       Expr(vars, erc);
-      return new Stack<double>(stack);
+      return intermediateValues;
     }
 
@@ -58,16 +60,19 @@
         if (curSy == '+') {
           NewSy();
-          if (!Term(d, erc)) { stack.Push(-1.0); return false; }
+          if (!Term(d, erc)) { return false; }
           stack.Push(stack.Pop() + stack.Pop());
+          intermediateValues.Add(stack.Peek());
         } else if (curSy == '-') {
           NewSy();
-          if (!Term(d, erc)) { stack.Push(-2.0); return false; return false; }
+          if (!Term(d, erc)) {  return false; }
           stack.Push(-stack.Pop() + stack.Pop());
+          intermediateValues.Add(stack.Peek());
         } else {
           NewSy();
-          if (!Term(d, erc)) { stack.Push(-3.0); return false; }
+          if (!Term(d, erc)) { return false; }
           var e = stack.Pop();
           var r = stack.Pop();
           stack.Push(Not(r) * e + r * Not(e)); // xor = (!x AND y) OR (x AND !y)
+          intermediateValues.Add(stack.Peek());
         }
         curSy = CurSy();
@@ -82,13 +87,15 @@
         if (curSy == '*') {
           NewSy();
-          if (!Fact(d, erc)) { stack.Push(-4.0); return false; }
+          if (!Fact(d, erc)) { return false; }
           stack.Push(stack.Pop() * stack.Pop());
+          intermediateValues.Add(stack.Peek());
         } else {
           NewSy();
-          if (!Fact(d, erc)) { stack.Push(-5.0); return false; }
+          if (!Fact(d, erc)) { return false; }
           var nom = stack.Pop();
           var r = stack.Pop();
           if (HeuristicLab.Common.Extensions.IsAlmost(nom, 0.0)) nom = 1.0;
           stack.Push(r / nom);
+          intermediateValues.Add(stack.Peek());
         }
         curSy = CurSy();
@@ -100,12 +107,12 @@
       var curSy = CurSy();
       if (curSy == '!') {
-        NewSy();
-        if (!Expr(d, erc)) { stack.Push(-7.0); return false; }
-        stack.Push(Not(stack.Pop()));
+        //NewSy();
+        //if (!Expr(d, erc)) { stack.Push(-7.0); return false; }
+        //stack.Push(Not(stack.Pop()));
       } else if (curSy == '(') {
-        NewSy();
-        if (!Expr(d, erc)) { stack.Push(-8.0); return false; }
-        if (CurSy() != ')') throw new ArgumentException();
-        NewSy();
+        //NewSy();
+        //if (!Expr(d, erc)) { stack.Push(-8.0); return false; }
+        //if (CurSy() != ')') throw new ArgumentException();
+        //NewSy();
       } else if (curSy >= 'a' && curSy <= 'z') {
         int o = (byte)curSy - (byte)'a';
@@ -113,11 +120,12 @@
         if (o < 0 || o >= d.Length) throw new ArgumentException();
         stack.Push(d[o]);
+        intermediateValues.Add(stack.Peek());
         NewSy();
       } else if (curSy == '/') {
         // /-symbol is used in the expressionextender to represent inverse (1/x). 
         // this is necessary because we also use symbols 0..9 as indices for ERCs
-        NewSy();
-        if (!Fact(d, erc)) { stack.Push(-9.0); return false; }
-        stack.Push(1.0 / stack.Pop());
+        //NewSy();
+        //if (!Fact(d, erc)) { stack.Push(-9.0); return false; }
+        //stack.Push(1.0 / stack.Pop());
       } else if (curSy >= '0' && curSy <= '9') {
         int o = (byte)curSy - (byte)'0';
@@ -125,4 +133,5 @@
         if (o < 0 || o >= 10) throw new ArgumentException();
         stack.Push(erc[o]);
+        intermediateValues.Add(stack.Peek());
         NewSy();
       } else {
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 12297)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 12298)
@@ -156,21 +156,63 @@
     // splits the phrase into terms and creates (sparse) term-occurrance features
     public IEnumerable<Feature> GetFeatures(string phrase) {
-      // var canonicalTerms = new HashSet<string>();
-      // foreach (string t in phrase.Split('+')) {
-      //   canonicalTerms.Add(CanonicalTerm(t));
+      //if (phrase.EndsWith("E")) phrase = phrase.TrimEnd('*', '+', 'E');
+      //yield return new Feature("$$$", 1.0); // const
+      //var canonicalTerms = new HashSet<string>();
+      //foreach (string t in phrase.Split('+')) {
+      //  canonicalTerms.Add(CanonicalTerm(t));
+      //}
+      //return canonicalTerms.Select(entry => new Feature(entry, 1.0));
+      //.Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
+
+
+      if (phrase.EndsWith("E")) phrase = phrase.TrimEnd('*', '+', 'E');
+      //var len = 5;
+      //var start = Math.Max(0, phrase.Length - len);
+      //var end = Math.Min(phrase.Length, start + len);
+      //string f = phrase.Substring(start, end - start);
+      //yield return new Feature(f, 1.0);
+      //
+
+      var terms = phrase.Split('+');
+      foreach (var t in terms.Distinct()) yield return new Feature(t, 1.0);
+
+      for (int i = 0; i < terms.Length; i++) {
+        for (int j = i + 1; j < terms.Length; j++) {
+          yield return new Feature(terms[i] + " " + terms[j], 1.0);
+        }
+      }
+
+      // var substrings = new HashSet<string>();
+      // for (int start = 0; start <= phrase.Length - 2; start += 2) {
+      //   var s = phrase.Substring(start, 3);
+      //   substrings.Add(s);
       // }
-      // return canonicalTerms.Select(entry => new Feature(entry, 1.0))
-      //   .Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
-
-      return new Feature[] { new Feature(phrase, 1.0), };
-
-      // var partialInterpreter = new PartialExpressionInterpreter();
-      // var vars = new double[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, };
-      // var s = partialInterpreter.Interpret(phrase, vars);
-      // //if (s.Any())
-      // //  return new Feature[] { new Feature(s.Pop().ToString(), 1.0), };
-      // //else
-      // //  return new Feature[] { new Feature("$", 1.0), };
-      // return new Feature[] { new Feature(string.Join(",", s), 1.0) };
+      // 
+      // var list = new List<string>(substrings);
+      // 
+      // for (int i = 0; i < list.Count; i++) {
+      //   yield return new Feature(list[i], 1.0);
+      //   //for (int j = i+1; j < list.Count; j++) {
+      //   //  yield return new Feature(list[i] + " " + list[j], 1.0);
+      //   //}
+      // }
+
+      //
+      // for (int len = 1; len <= phrase.Length; len += 2) {
+      //   var start = Math.Max(0, phrase.Length - len);
+      //   var end = Math.Min(phrase.Length, start + len);
+      //   string f = phrase.Substring(start, end - start);
+      //   yield return new Feature(f, 1.0);
+      // 
+      // }
+
+      //var partialInterpreter = new PartialExpressionInterpreter();
+      //var vars = new double[] { 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, };
+      //var s = partialInterpreter.Interpret(phrase, vars);
+      ////if (s.Any())
+      ////  return new Feature[] { new Feature(s.Pop().ToString(), 1.0), };
+      ////else
+      ////  return new Feature[] { new Feature("$", 1.0), };
+      //return s.Select(f => new Feature(f.ToString(), 1.0));
     }
 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs	(revision 12297)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs	(revision 12298)
@@ -50,10 +50,10 @@
     public override string ToString() {
       return
-        string.Format("Sentences: {0,10} avg.-quality {1,7:F5} best {2,7:F5} {3,2} {4,10} {5,30} first {6,7:F5} {7,20} last {8,7:F5} {9,20}",
+        string.Format("Sentences: {0,10} avg.-quality {1,7:F5} best {2,7:F5} {3,2} {4,10} {5,30} last {6,7:F5} {7,20}",
       NumberOfSentences, AverageQuality,
       BestSentenceQuality, DoubleExtensions.IsAlmost(BestSentenceQuality, bestKnownQuality) ? 1.0 : 0.0,
       BestSentenceIndex, TrimToSize(BestSentence, 30),
-      FirstSentenceQuality, TrimToSize(FirstSentence, 20),
       LastSentenceQuality, TrimToSize(LastSentence, 20)
+      //LastSentenceQuality, TrimToSize(LastSentence, 20)
      );
     }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs	(revision 12297)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Main/Program.cs	(revision 12298)
@@ -1,5 +1,8 @@
 using System;
+using System.Collections.Generic;
 using System.Diagnostics;
 using System.Globalization;
+using System.Linq;
+using System.Text.RegularExpressions;
 using HeuristicLab.Algorithms.Bandits.BanditPolicies;
 using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
@@ -38,4 +41,5 @@
 
         var globalStatistics = new SentenceSetStatistics();
+        ResetAlleleStatistics();
         var random = new Random();
 
@@ -66,13 +70,21 @@
           iterations++;
           globalStatistics.AddSentence(sentence, quality);
-
+          UpdateAlleleStatistics(sentence);
           // comment this if you don't want to see solver statistics
           if (iterations % 100 == 0) {
-            if (iterations % 1000 == 0) Console.Clear();
+            if (iterations % 1000 == 0) {
+              Console.Clear();
+            }
             Console.SetCursorPosition(0, 0);
-             alg.PrintStats();
-            //policy.PrintStats();
+            Console.WriteLine(iterations);
+            WriteAlleleStatistics();
+            Console.WriteLine(globalStatistics.BestSentenceQuality);
+            Console.WriteLine(globalStatistics.BestSentence);
+            Console.WriteLine(globalStatistics);
+            //alg.PrintStats();
+            policy.PrintStats();
+            //ResetAlleleStatistics();
           }
-
+          
           // uncomment this if you want to collect statistics of the generated sentences
           //if (iterations % 100 == 0) {
@@ -94,4 +106,64 @@
       }
     }
+
+    private static void UpdateAlleleStatistics(string sentence) {
+      for (int i = 0; i < sentence.Length; i++) {
+        var allele = sentence.Substring(i, 1);
+        if (alleleStatistics.ContainsKey(allele)) alleleStatistics[allele]++;
+      }
+      for (int i = 0; i < sentence.Length - 2; i+=2) {
+        var allele = sentence.Substring(i, 3);
+        if (alleleStatistics.ContainsKey(allele)) alleleStatistics[allele]++;
+      }
+      for (int i = 0; i < sentence.Length - 4; i+=2) {
+        var allele = sentence.Substring(i, 5);
+        if (alleleStatistics.ContainsKey(allele)) alleleStatistics[allele]++;
+      }
+    }
+
+
+    private static Dictionary<string, int> alleleStatistics;
+
+    private static void ResetAlleleStatistics() {
+      alleleStatistics = new Dictionary<string, int>()
+      {
+        {"a", 0},
+        {"b", 0},
+        {"c", 0},
+        {"d", 0},
+        {"e", 0},
+        {"f", 0},
+        {"g", 0},
+        {"h", 0},
+        {"i", 0},
+        {"j", 0},
+        {"a*b", 0},
+        {"b*a", 0},
+        {"c*d", 0},
+        {"d*c", 0},
+        {"e*f", 0},
+        {"f*e", 0},
+        {"a*g*i", 0},
+        {"a*i*g", 0},
+        {"g*a*i", 0},
+        {"g*i*a", 0},
+        {"i*g*a", 0},
+        {"i*a*g", 0},
+        {"j*c*f", 0},
+        {"j*f*c", 0},
+        {"c*j*f", 0},
+        {"c*f*j", 0},
+        {"f*c*j", 0},
+        {"f*j*c", 0}
+      };
+    }
+
+
+    private static void WriteAlleleStatistics() {
+      double count = alleleStatistics.Sum(e => e.Value);
+      foreach (var entry in alleleStatistics.OrderByDescending(e=>e.Value)) {
+        Console.WriteLine("{0,-10} {1,-10}", entry.Key, entry.Value);
+      }
+    }
   }
 }
