Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Evaluation.csproj
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Evaluation.csproj	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Evaluation.csproj	(revision 12815)
@@ -56,4 +56,5 @@
     <Compile Include="FoundSolution.cs" />
     <Compile Include="Run.cs" />
+    <Compile Include="SelectionIndicator.cs" />
     <Compile Include="ViewModel\EvaluationViewModel.cs" />
     <Page Include="MainWindow.xaml">
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml	(revision 12815)
@@ -71,6 +71,6 @@
                 <TextBlock Margin="2" Grid.Column="0" Grid.Row="0" VerticalAlignment="Center">Runs:</TextBlock>
                 <TextBox Name="TextBoxRuns" Margin="2" Grid.Column="1" Grid.Row="0" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding NrRuns}"></TextBox>
-                <TextBlock Margin="2" Grid.Column="0" Grid.Row="1" VerticalAlignment="Center">MaxEvaluations:</TextBlock>
-                <TextBox Name="TextBoxMaxEvaluations" Margin="2" Grid.Column="1" Grid.Row="1" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding MaxEvaluations}"></TextBox>
+                <TextBlock Margin="2" Grid.Column="0" Grid.Row="1" VerticalAlignment="Center">MaxIterations:</TextBlock>
+                <TextBox Name="TextBoxMaxIterations" Margin="2" Grid.Column="1" Grid.Row="1" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding MaxIterations}"></TextBox>
                 <TextBlock Margin="2" Grid.Column="2" Grid.Row="0" VerticalAlignment="Center">MaxLen:</TextBlock>
                 <TextBox Name="TextBoxMaxLen" Margin="2" Grid.Column="3" Grid.Row="0" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding MaxLen}"></TextBox>
@@ -98,5 +98,5 @@
                         <ListBox Name="ListBoxRuns" Grid.Column="0" Width="100" ItemsSource="{Binding Runs}" SelectionChanged="ListBoxRuns_OnSelectionChanged"/>
                         <TabControl Grid.Column="1">
-                            <TabItem Header="Chart">
+                            <TabItem Header="Quality-Chart">
                                 <Grid>
                                     <Grid.RowDefinitions>
@@ -107,8 +107,24 @@
                                         <ColumnDefinition Width="*"></ColumnDefinition>
                                     </Grid.ColumnDefinitions>
-                                    <d3:ChartPlotter Grid.Column="1" x:Name="ChartPlotter" LegendVisible="False" EnableSmoothPanningForNumericAxes="True">
-                                        <d3:Header Content="{Binding HeaderString}"/>
-                                        <d3:VerticalAxisTitle Content="{Binding VerticalAxisString}" />
-                                        <d3:HorizontalAxisTitle Content="{Binding HorizontalAxisString}"/>
+                                    <d3:ChartPlotter Grid.Column="1" x:Name="QualityChartPlotter" LegendVisible="False" EnableSmoothPanningForNumericAxes="True">
+                                        <d3:Header Content="Quality-Chart"/>
+                                        <d3:VerticalAxisTitle Content="Quality" />
+                                        <d3:HorizontalAxisTitle Content="Evaluation"/>
+                                    </d3:ChartPlotter>
+                                </Grid>
+                            </TabItem>
+                            <TabItem Header="SelectionIndicator-Chart">
+                                <Grid>
+                                    <Grid.RowDefinitions>
+                                        <RowDefinition Height="*"></RowDefinition>
+                                    </Grid.RowDefinitions>
+                                    <Grid.ColumnDefinitions>
+                                        <ColumnDefinition Width="Auto"></ColumnDefinition>
+                                        <ColumnDefinition Width="*"></ColumnDefinition>
+                                    </Grid.ColumnDefinitions>
+                                    <d3:ChartPlotter Grid.Column="1" x:Name="SelectionChartPlotter" LegendVisible="False" EnableSmoothPanningForNumericAxes="True">
+                                        <d3:Header Content="SelectionIndicator-Chart"/>
+                                        <d3:VerticalAxisTitle Content="SelectionIndicator" />
+                                        <d3:HorizontalAxisTitle Content="SelectedNodes"/>
                                     </d3:ChartPlotter>
                                 </Grid>
@@ -204,4 +220,5 @@
                     <RowDefinition Height="Auto" />
                     <RowDefinition Height="Auto" />
+                    <RowDefinition Height="Auto" />
                 </Grid.RowDefinitions>
                 <Grid.ColumnDefinitions>
@@ -215,6 +232,6 @@
                 <TextBlock Grid.Row="2" Grid.Column="0">Evaluations:</TextBlock>
                 <TextBlock Grid.Row="2" Grid.Column="1" Text="{Binding SelectedRun.Evaluations}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
-                <TextBlock Grid.Row="3" Grid.Column="0">MaxEvaluations:</TextBlock>
-                <TextBlock Grid.Row="3" Grid.Column="1" Text="{Binding SelectedRun.MaxEvaluations}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
+                <TextBlock Grid.Row="3" Grid.Column="0">MaxIterations:</TextBlock>
+                <TextBlock Grid.Row="3" Grid.Column="1" Text="{Binding SelectedRun.MaxIterations}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
                 <TextBlock Grid.Row="4" Grid.Column="0">BestQuality:</TextBlock>
                 <TextBlock Grid.Row="4" Grid.Column="1" Text="{Binding SelectedRun.BestQuality}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
@@ -228,5 +245,7 @@
                 <TextBlock Grid.Row="8" Grid.Column="1" Text="{Binding SelectedRun.BestSolutionFoundAt}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
                 <TextBlock Grid.Row="9" Grid.Column="0">BestSolution:</TextBlock>
-                <TextBlock Grid.Row="9" Grid.Column="1" Text="{Binding SelectedRun.BestSolution}" TextWrapping="Wrap" Margin="5,0,0,0" HorizontalAlignment="Right" MaxWidth="100"/>
+                <TextBlock Grid.Row="9" Grid.Column="1" Text="{Binding SelectedRun.BestSolution}" TextWrapping="Wrap" Margin="5,0,0,0" HorizontalAlignment="Right" MaxWidth="100" MaxHeight="50"/>
+                <TextBlock Grid.Row="10" Grid.Column="0">SelectionIndicator:</TextBlock>
+                <TextBlock Grid.Row="10" Grid.Column="1" Text="{Binding SelectedRun.CurrentSelectionIndicator.Indicator}" TextWrapping="Wrap" Margin="5,0,0,0" HorizontalAlignment="Right" MaxWidth="100"/>
             </Grid>
         </Grid>
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml.cs	(revision 12815)
@@ -1,3 +1,4 @@
 ﻿using System.Collections.ObjectModel;
+using System.Security.AccessControl;
 using System.Threading;
 using System.Xml.Serialization;
@@ -32,6 +33,4 @@
         private EvaluationViewModel vm;
 
-        private DispatcherTimer updateCollectionTimer;
-
         private DrawingPage treeDrawingPage;
 
@@ -42,8 +41,6 @@
             this.DataContext = vm = new EvaluationViewModel();
             vm.MaxLen = 100;
-            vm.MaxEvaluations = 1000000;
+            vm.MaxIterations = 1000000;
             vm.NrRuns = 10;
-            vm.VerticalAxisString = "SolutionQuality";
-            vm.HorizontalAxisString = "Iteration";
         }
 
@@ -58,5 +55,5 @@
         }
 
-        private void DrawLineChart(Run run)
+        private void DrawQualityChart(Run run)
         {
             List<FoundSolution> solutions = new List<FoundSolution>(run.FoundSolutions);
@@ -76,5 +73,20 @@
 
             graph.StrokeThickness = 2;
-            graph.AddToPlotter(ChartPlotter);
+            graph.AddToPlotter(QualityChartPlotter);
+        }
+
+        private void DrawSelectionChart(Run run)
+        {
+            List<SelectionIndicator> selectionIndicators = new List<SelectionIndicator>(run.SelectionIndicators);
+
+            var ds = new EnumerableDataSource<SelectionIndicator>(selectionIndicators);
+
+            ds.SetXMapping(x => x.TotalSelections);
+            ds.SetYMapping(y => y.Indicator);
+
+            LineGraph graph = new LineGraph(ds);
+
+            graph.StrokeThickness = 2;
+            graph.AddToPlotter(SelectionChartPlotter);
         }
 
@@ -93,5 +105,5 @@
             run.StartTime = DateTime.Now;
 
-            run.Solver.Run(run.MaxEvaluations);
+            run.Solver.Run(run.MaxIterations);
 
             run.EndTime = DateTime.Now;
@@ -136,5 +148,5 @@
         {
             ButtonRun.IsEnabled = true;
-            TextBoxMaxEvaluations.IsEnabled = true;
+            TextBoxMaxIterations.IsEnabled = true;
             TextBoxMaxLen.IsEnabled = true;
             TextBoxRuns.IsEnabled = true;
@@ -162,4 +174,8 @@
                 policyInstance = new ThresholdAscentPolicy();
             }
+            else if (policy == typeof(BoltzmannExplorationPolicy))
+            {
+                policyInstance = new BoltzmannExplorationPolicy(2);
+            }
             else
             {
@@ -197,5 +213,5 @@
                 }
 
-                Run run = new Run(problem, policyInstance, solver, i + 1, vm.MaxEvaluations, vm.MaxLen);
+                Run run = new Run(problem, policyInstance, solver, i + 1, vm.MaxIterations, vm.MaxLen);
 
                 vm.Runs.Add(run);
@@ -205,7 +221,7 @@
         }
 
-        private void ClearLineChart()
-        {
-            ChartPlotter.Children.RemoveAll<LineGraph>();
+        private void ClearQualityChart()
+        {
+            QualityChartPlotter.Children.RemoveAll<LineGraph>();
         }
 
@@ -215,13 +231,19 @@
         }
 
+        private void ClearSelectionChart()
+        {
+            SelectionChartPlotter.Children.RemoveAll<LineGraph>();
+        }
+
         private void ButtonRun_OnClick(object sender, RoutedEventArgs e)
         {
-            ClearLineChart();
+            ClearQualityChart();
             ClearComparisonChart();
+            ClearSelectionChart();
 
             vm.Runs.Clear();
             vm.SelectedRun = null;
             ButtonRun.IsEnabled = false;
-            TextBoxMaxEvaluations.IsEnabled = false;
+            TextBoxMaxIterations.IsEnabled = false;
             TextBoxMaxLen.IsEnabled = false;
             TextBoxRuns.IsEnabled = false;
@@ -287,6 +309,12 @@
                 vm.SelectedRun.Solver.FoundNewBestSolution += SelectedRun_FoundNewBestSolution;
 
-                ClearLineChart();
-                DrawLineChart(vm.SelectedRun);
+                ClearQualityChart();
+                DrawQualityChart(vm.SelectedRun);
+
+                if (vm.SelectedRun.RunState == RunState.Finished)
+                {
+                    ClearSelectionChart();
+                    DrawSelectionChart(vm.SelectedRun);
+                }
                 //DrawTreeChart(vm.SelectedRun);
             }
@@ -301,6 +329,6 @@
             Dispatcher.BeginInvoke(new Action(() =>
             {
-                ClearLineChart();
-                DrawLineChart(vm.SelectedRun);
+                ClearQualityChart();
+                DrawQualityChart(vm.SelectedRun);
             }));
         }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Run.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Run.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Run.cs	(revision 12815)
@@ -1,4 +1,5 @@
 ﻿using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
+using HeuristicLab.Algorithms.MonteCarloTreeSearch;
 using HeuristicLab.Algorithms.MonteCarloTreeSearch.Base;
 using HeuristicLab.Problems.GrammaticalOptimization;
@@ -26,5 +27,5 @@
 
         public Run(ISymbolicExpressionTreeProblem problem, IBanditPolicy banditPolicy, ISolver solver, int runNumber,
-            int maxEvaluations, int maxLen)
+            int maxIterations, int maxLen)
         {
             Problem = problem;
@@ -32,11 +33,13 @@
             Solver = solver;
             RunNumber = runNumber;
-            MaxEvaluations = maxEvaluations;
+            MaxIterations = maxIterations;
             MaxLen = maxLen;
 
+            selectionIndicators = new List<SelectionIndicator>();
             Evaluations = 0;
             BestQuality = double.MinValue;
             RunState = RunState.NotStarted;
             FoundSolutions = new List<FoundSolution>();
+            CurrentSelectionIndicator = new SelectionIndicator(0, 0);
 
             BestKnownQuality = problem.BestKnownQuality(maxLen);
@@ -52,4 +55,31 @@
                 }
             };
+            if (solver is MonteCarloTreeSearch)
+            {
+                MonteCarloTreeSearch mcts = (MonteCarloTreeSearch)solver;
+                mcts.NodeSelected += mcts_NodeSelected;
+            }
+        }
+
+        private void mcts_NodeSelected(int goodSelections, int totalSelections)
+        {
+            CurrentSelectionIndicator.GoodSelections = goodSelections;
+            CurrentSelectionIndicator.TotalSelections = totalSelections;
+            this.OnPropertyChanged("CurrentSelectionIndicator");
+            //CurrentSelectionIndicator = new SelectionIndicator(goodSelections, totalSelections);
+            //selectionIndicators.Add(CurrentSelectionIndicator);
+        }
+
+        private List<SelectionIndicator> selectionIndicators;
+
+        public List<SelectionIndicator> SelectionIndicators { get { return selectionIndicators; } }
+
+
+        private SelectionIndicator currentSelectionIndicator;
+
+        public SelectionIndicator CurrentSelectionIndicator
+        {
+            get { return this.currentSelectionIndicator; }
+            set { this.currentSelectionIndicator = value; this.OnPropertyChanged("CurrentSelectionIndicator"); }
         }
 
@@ -102,13 +132,13 @@
         }
 
-        private int maxEvaluations;
-
-        public int MaxEvaluations
-        {
-            get { return this.maxEvaluations; }
-            set
-            {
-                this.maxEvaluations = value;
-                this.OnPropertyChanged("MaxEvaluations");
+        private int maxIterations;
+
+        public int MaxIterations
+        {
+            get { return this.maxIterations; }
+            set
+            {
+                this.maxIterations = value;
+                this.OnPropertyChanged("MaxIterations");
             }
         }
@@ -297,6 +327,10 @@
         protected void OnPropertyChanged(string propertyName)
         {
-            if (PropertyChanged != null)
-                this.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));
+            try
+            {
+                if (PropertyChanged != null)
+                    this.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));
+            }
+            catch (Exception) { }
         }
 
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/SelectionIndicator.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/SelectionIndicator.cs	(revision 12815)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/SelectionIndicator.cs	(revision 12815)
@@ -0,0 +1,22 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace Evaluation
+{
+    public class SelectionIndicator
+    {
+        public SelectionIndicator(int goodSelections, int totalSelections)
+        {
+            GoodSelections = goodSelections;
+            TotalSelections = totalSelections;
+        }
+
+        public int GoodSelections { get; set; }
+        public int TotalSelections { get; set; }
+
+        public double Indicator { get { return Math.Round((double)GoodSelections / TotalSelections, 5); } }
+    }
+}
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/ViewModel/EvaluationViewModel.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/ViewModel/EvaluationViewModel.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/ViewModel/EvaluationViewModel.cs	(revision 12815)
@@ -98,49 +98,13 @@
         }
 
-        private int maxEvaluations;
-
-        public int MaxEvaluations
-        {
-            get { return this.maxEvaluations; }
-            set
-            {
-                this.maxEvaluations = value;
-                this.OnPropertyChanged("MaxEvaluations");
-            }
-        }
-
-        private string headerString;
-
-        public string HeaderString
-        {
-            get { return this.headerString; }
-            set
-            {
-                headerString = value;
-                this.OnPropertyChanged("HeaderString");
-            }
-        }
-
-        private string verticalAxisString;
-
-        public string VerticalAxisString
-        {
-            get { return this.verticalAxisString; }
-            set
-            {
-                verticalAxisString = value;
-                this.OnPropertyChanged("VerticalAxisString");
-            }
-        }
-
-        private string horizontalAxisString;
-
-        public string HorizontalAxisString
-        {
-            get { return this.horizontalAxisString; }
-            set
-            {
-                horizontalAxisString = value;
-                this.OnPropertyChanged("HorizontalAxisString");
+        private int maxIterations;
+
+        public int MaxIterations
+        {
+            get { return this.maxIterations; }
+            set
+            {
+                this.maxIterations = value;
+                this.OnPropertyChanged("MaxIterations");
             }
         }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs	(revision 12815)
@@ -31,5 +31,5 @@
       TournamentGroupSize = 4;
       MutationRate = 0.15;
-      MaxSolutionSize = 100;
+      MaxSolutionSize = 30;
       MaxSolutionDepth = 17;
       this.saveAlg = saveAlg;
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs	(revision 12815)
@@ -1,4 +1,5 @@
 ﻿using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Drawing;
 using System.Linq;
@@ -21,5 +22,5 @@
     {
         protected readonly int maxLen;
-        protected readonly IProblem problem;
+        protected readonly ISymbolicExpressionTreeProblem problem;
         protected readonly IGrammar grammar;
         protected readonly Random random;
@@ -29,6 +30,7 @@
         protected bool isPaused = false;
         protected object pauseLock = new object();
-
-        public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
+        protected int goodSelections;
+
+        public MonteCarloTreeSearch(ISymbolicExpressionTreeProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
             ISimulation simulationPolicy)
         {
@@ -39,4 +41,19 @@
             this.behaviourPolicy = behaviourPolicy;
             this.simulation = simulationPolicy;
+
+            this.problem.GenerateProblemSolutions(maxLen);
+        }
+
+        public event Action<int, int> NodeSelected;
+
+        protected virtual void OnNodeSelectedChanged(int value, int selections)
+        {
+            RaiseNodeSelectedChanged(value, selections);
+        }
+
+        private void RaiseNodeSelectedChanged(int value, int selections)
+        {
+            var handler = NodeSelected;
+            if (handler != null) handler(value, selections);
         }
 
@@ -48,7 +65,20 @@
         }
 
+        public int GoodSelections { get { return this.goodSelections; } }
+
+        protected void CheckSelection(TreeNode node, int selections)
+        {
+            if (problem.IsParentOfProblemSolution(node.phrase, maxLen))
+            {
+                goodSelections++;
+            }
+
+            OnNodeSelectedChanged(goodSelections, selections);
+        }
+
         public override void Run(int maxIterations)
         {
             Reset();
+            int selections = 0;
             for (int i = 0; !StopRequested && i < maxIterations; i++)
             {
@@ -67,4 +97,6 @@
                         currentNode.GetChildActionInfos());
                     currentNode = currentNode.children[currentActionIndex];
+                    selections++;
+                    CheckSelection(currentNode, selections);
                 }
 
@@ -77,4 +109,6 @@
                         currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
                             ];
+                    selections++;
+                    CheckSelection(currentNode, selections);
                 }
                 if (currentNode.phrase.Length <= maxLen)
@@ -122,4 +156,5 @@
         protected void Reset()
         {
+            goodSelections = 0;
             StopRequested = false;
             bestQuality = 0.0;
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch_PruneLeaves.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch_PruneLeaves.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch_PruneLeaves.cs	(revision 12815)
@@ -1,3 +1,4 @@
-﻿using HeuristicLab.Algorithms.Bandits;
+﻿using System.Diagnostics;
+using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Algorithms.MonteCarloTreeSearch.Base;
 using HeuristicLab.Algorithms.MonteCarloTreeSearch.Simulation;
@@ -11,6 +12,7 @@
     public class MonteCarloTreeSearch_PruneLeaves : MonteCarloTreeSearch
     {
-        public MonteCarloTreeSearch_PruneLeaves(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
-            ISimulation simulationPolicy):base(problem,maxLen,random,behaviourPolicy,simulationPolicy)
+        public MonteCarloTreeSearch_PruneLeaves(ISymbolicExpressionTreeProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
+            ISimulation simulationPolicy)
+            : base(problem, maxLen, random, behaviourPolicy, simulationPolicy)
         {
         }
@@ -19,4 +21,5 @@
         {
             Reset();
+            int selections = 0;
             for (int i = 0; !StopRequested && i < maxIterations; i++)
             {
@@ -35,4 +38,6 @@
                         currentNode.GetChildActionInfos());
                     currentNode = currentNode.children[currentActionIndex];
+                    selections++;
+                    CheckSelection(currentNode, selections);
                 }
 
@@ -54,4 +59,6 @@
                             currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
                                 ];
+                        selections++;
+                        CheckSelection(currentNode, selections);
                     }
                     else
@@ -69,5 +76,4 @@
 
                     Propagate(currentNode, quality);
-
                 }
             }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs	(revision 12815)
@@ -265,4 +265,15 @@
       }
     }
+
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Interfaces/ISymbolicExpressionTreeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Interfaces/ISymbolicExpressionTreeProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Interfaces/ISymbolicExpressionTreeProblem.cs	(revision 12815)
@@ -5,9 +5,13 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // represents a grammatical optimization problem that can also be used with tree-based GP in HeuristicLab
-  public interface ISymbolicExpressionTreeProblem : IProblem {
-    IGrammar TreeBasedGPGrammar { get; } // grammar for HL GP
-    string ConvertTreeToSentence(ISymbolicExpressionTree tree);
-  }
+namespace HeuristicLab.Problems.GrammaticalOptimization
+{
+    // represents a grammatical optimization problem that can also be used with tree-based GP in HeuristicLab
+    public interface ISymbolicExpressionTreeProblem : IProblem
+    {
+        IGrammar TreeBasedGPGrammar { get; } // grammar for HL GP
+        string ConvertTreeToSentence(ISymbolicExpressionTree tree);
+        void GenerateProblemSolutions(int maxLen);
+        bool IsParentOfProblemSolution(string sentence, int maxLen);
+    }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/EvenParityProblem.cs	(revision 12815)
@@ -127,4 +127,15 @@
       }
     }
+
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs	(revision 12815)
@@ -177,4 +177,15 @@
       return sb.ToString();
     }
+
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/HardPalindromeProblem.cs	(revision 12815)
@@ -65,4 +65,12 @@
       return sb.ToString();
     }
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PalindromeProblem.cs	(revision 12815)
@@ -106,4 +106,15 @@
       return sb.ToString();
     }
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PermutationProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PermutationProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/PermutationProblem.cs	(revision 12815)
@@ -56,4 +56,13 @@
       return sb.ToString();
     }
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPairProblem.cs	(revision 12815)
@@ -60,4 +60,15 @@
       return sb.ToString();
     }
+
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs	(revision 12815)
@@ -161,4 +161,15 @@
       return sb.ToString();
     }
+
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs	(revision 12815)
@@ -114,4 +114,15 @@
       return sb.ToString();
     }
+
+
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSymbolProblem.cs	(revision 12815)
@@ -3,62 +3,98 @@
 using System.Diagnostics;
 using System.Linq;
+using System.Security.Authentication.ExtendedProtection.Configuration;
 using System.Text;
 using System.Text.RegularExpressions;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  // counts the number of times a symbol occurs in a sentence
-  public class RoyalSymbolProblem : ISymbolicExpressionTreeProblem {
-    private const string grammarString = @"
+namespace HeuristicLab.Problems.GrammaticalOptimization
+{
+    // counts the number of times a symbol occurs in a sentence
+    public class RoyalSymbolProblem : ISymbolicExpressionTreeProblem
+    {
+        private const string grammarString = @"
 G(S):
 S -> a | aS | b | bS
 ";
 
-    private const string hlGrammarString = @"
+        private const string hlGrammarString = @"
 G(S):
 S -> a | b | SS
 ";
 
-    // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
+        // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
 
-    private readonly IGrammar grammar;
-    public string Name { get { return "RoyalSymbol"; } }
-    public RoyalSymbolProblem() {
-      this.grammar = new Grammar(grammarString);
-      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
-      //TODO: allow configuration of the number of symbols
+        private readonly IGrammar grammar;
+        public string Name { get { return "RoyalSymbol"; } }
+        public RoyalSymbolProblem()
+        {
+            this.grammar = new Grammar(grammarString);
+            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
+            //TODO: allow configuration of the number of symbols
+        }
+
+        public double BestKnownQuality(int maxLen)
+        {
+            return maxLen;
+        }
+
+        public IGrammar Grammar
+        {
+            get { return grammar; }
+        }
+
+        private Regex regex = new Regex("a"); // count the number of "a"s
+        public double Evaluate(string sentence)
+        {
+            // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
+            Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
+            return regex.Matches(sentence).Count;
+        }
+        public string CanonicalRepresentation(string phrase)
+        {
+            return phrase;
+        }
+
+        public IEnumerable<Feature> GetFeatures(string phrase)
+        {
+            throw new NotImplementedException();
+        }
+
+        public IGrammar TreeBasedGPGrammar { get; private set; }
+        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
+        {
+            var sb = new StringBuilder();
+            foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix())
+            {
+                if (s.Symbol.Name == "S") continue;
+                sb.Append(s.Symbol.Name);
+            }
+            return sb.ToString();
+        }
+
+        private string solution = string.Empty;
+
+        public void GenerateProblemSolutions(int maxLen)
+        {
+            StringBuilder sb = new StringBuilder();
+            for (int i = 0; i < maxLen; i++)
+            {
+                sb.Append('a');
+            }
+            solution = sb.ToString();
+        }
+
+        private readonly Regex isParentSolution = new Regex("a+S");
+        public bool IsParentOfProblemSolution(string sentence, int maxLen)
+        {
+            if (sentence.Length < maxLen)
+            {
+                return isParentSolution.IsMatch(sentence);
+            }
+            else
+            {
+                return solution == sentence;
+            }
+        }
     }
-
-    public double BestKnownQuality(int maxLen) {
-      return maxLen;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    private Regex regex = new Regex("a"); // count the number of "a"s
-    public double Evaluate(string sentence) {
-      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
-      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
-      return regex.Matches(sentence).Count;
-    }
-    public string CanonicalRepresentation(string phrase) {
-      return phrase;
-    }
-
-    public IEnumerable<Feature> GetFeatures(string phrase) {
-      throw new NotImplementedException();
-    }
-
-    public IGrammar TreeBasedGPGrammar { get; private set; }
-    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
-      var sb = new StringBuilder();
-      foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
-        if (s.Symbol.Name == "S") continue;
-        sb.Append(s.Symbol.Name);
-      }
-      return sb.ToString();
-    }
-  }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs	(revision 12815)
@@ -273,4 +273,13 @@
       return sb.ToString();
     }
+    public void GenerateProblemSolutions(int maxLen)
+    {
+        throw new NotImplementedException();
+    }
+
+    public bool IsParentOfProblemSolution(string sentence, int maxLen)
+    {
+        throw new NotImplementedException();
+    }
   }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SantaFeAntProblem.cs	(revision 12815)
@@ -9,13 +9,15 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class SantaFeAntProblem : ISymbolicExpressionTreeProblem {
-    private const string grammarString = @"
+namespace HeuristicLab.Problems.GrammaticalOptimization
+{
+    public class SantaFeAntProblem : ISymbolicExpressionTreeProblem
+    {
+        private const string grammarString = @"
 G(A):
-A -> l | r | m | ?(A)(A) | lA | rA | mA 
+A -> l | r | m | ?(A)(A) | ?(A)(A)A | lA | rA | mA
 ";
-    // for tree-based GP in HL we need a different grammar for the same language
-    // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
-    private const string hlGrammarString = @"
+        // for tree-based GP in HL we need a different grammar for the same language
+        // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
+        private const string hlGrammarString = @"
     G(A):
     A -> l | r | m | P | I
@@ -25,290 +27,478 @@
 
 
-    // original koza grammar
-    // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
-    // 
-    // here we use a modified grammar which has only one syntax tree for each sentence
-
-
-    private readonly IGrammar grammar;
-    public string Name { get { return "SantaFeAnt"; } }
-
-    public SantaFeAntProblem() {
-      this.grammar = new Grammar(grammarString);
-      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
+        // original koza grammar
+        // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
+        // 
+        // here we use a modified grammar which has only one syntax tree for each sentence
+
+
+        private readonly IGrammar grammar;
+        public string Name { get { return "SantaFeAnt"; } }
+
+        public SantaFeAntProblem()
+        {
+            this.grammar = new Grammar(grammarString);
+            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
+        }
+
+        public double BestKnownQuality(int maxLen)
+        {
+            // for now only an upper bound is returned, ideally all food pellets are discovered
+            return 89;
+        }
+
+        public IGrammar Grammar
+        {
+            get { return grammar; }
+        }
+
+        public double Evaluate(string sentence)
+        {
+            var ant = new Ant();
+            int p = 0;
+            Run(ant, sentence, ref p);
+            return ant.FoodEaten;
+        }
+
+        private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false)
+        {
+            while (!ant.Done())
+            {
+                if (p >= sentence.Length)
+                {
+                    if (stopAfterFirst) return;
+                    p = 0; // restart
+                }
+                switch (sentence[p])
+                {
+                    case 'r':
+                        {
+                            ant.TurnRight();
+                            p++;
+                            break;
+                        }
+                    case 'l':
+                        {
+                            ant.TurnLeft();
+                            p++;
+                            break;
+                        }
+                    case 'm':
+                        {
+                            ant.Move();
+                            p++;
+                            break;
+                        }
+                    case '?':
+                        {
+                            p++; // skip p
+                            if (ant.IsFoodAhead())
+                            {
+                                if (sentence[p] != '(') throw new ArgumentException();
+                                p++;
+                                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
+                                if (ant.Done()) return;
+                                if (sentence[p] != '(') throw new ArgumentException();
+                                p++;
+                                Skip(sentence, ref p);
+                            }
+                            else
+                            {
+                                if (sentence[p] != '(') throw new ArgumentException();
+                                p++;
+                                Skip(sentence, ref p);
+                                if (sentence[p] != '(') throw new ArgumentException();
+                                p++;
+                                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
+                            }
+                            break;
+                        }
+                    case '.':
+                        {
+                            // nop
+                            p++;
+                            ant.Nop();
+                            break;
+                        }
+                    case ')':
+                        {
+                            p++; // skip
+                            return;     // caller must continue processing
+                        }
+                    default:
+                        {
+                            throw new ArgumentException();
+                        }
+                }
+            }
+        }
+
+        private static void Skip(string sentence, ref int p)
+        {
+            int openCount = 1;
+            while (openCount > 0)
+            {
+                if (sentence[p] == '(') openCount++;
+                else if (sentence[p] == ')') openCount--;
+                p++;
+            }
+        }
+
+        public string CanonicalRepresentation(string phrase)
+        {
+            //phrase = phrase.Replace("A", ".");
+            var sb = new StringBuilder(phrase);
+            string canonicalPhrase = phrase;
+            string oldPhrase;
+            do
+            {
+                oldPhrase = canonicalPhrase;
+                sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
+                //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
+                canonicalPhrase = sb.ToString();
+            } while (canonicalPhrase != oldPhrase);
+            return canonicalPhrase;
+        }
+
+        public IEnumerable<Feature> GetFeatures(string phrase)
+        {
+            phrase = CanonicalRepresentation(phrase);
+            var isTerminal = grammar.IsTerminal(phrase);
+
+            yield return new Feature(isTerminal + ToString(), 1.0);
+
+            yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
+            if (!isTerminal)
+            {
+                for (int i = 4; i < phrase.Length; i++)
+                {
+                    if (!grammar.IsTerminal(phrase[i]))
+                    {
+                        yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
+                        break;
+                    }
+                }
+            }
+
+            yield return new Feature(phrase, 1.0);
+        }
+
+        public IGrammar TreeBasedGPGrammar { get; private set; }
+        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
+        {
+            var sb = new StringBuilder();
+            ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
+            return sb.ToString();
+        }
+        private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb)
+        {
+            if (node.SubtreeCount == 0)
+            {
+                // terminal
+                sb.Append(node.Symbol.Name);
+            }
+            else if (node.Symbol.Name == "I")
+            {
+                Debug.Assert(node.SubtreeCount == 2);
+                sb.Append("?(");
+                ConvertTreeToSentence(node.GetSubtree(0), sb);
+                sb.Append(")(");
+                ConvertTreeToSentence(node.GetSubtree(1), sb);
+                sb.Append(")");
+            }
+            else
+            {
+                foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
+            }
+        }
+
+        private string[] solutions;
+
+        public void GenerateProblemSolutions(int maxLen)
+        {
+            if (maxLen > 17)
+            {
+                throw new NotImplementedException();
+            }
+            solutions = new string[12];
+            solutions[0] = "?(m)(ll?(m)(r))mr";
+            solutions[1] = "?(m)(rr?(m)(l))ml";
+            solutions[2] = "r?(m)(ll?(m)(r))m";
+            solutions[3] = "l?(m)(rr?(m)(l))m";
+            solutions[4] = "mr?(m)(ll?(m)(r))";
+            solutions[5] = "ml?(m)(rr?(m)(l))";
+            solutions[6] = "?(m)(ll?(m)(l))ml";
+            solutions[7] = "?(m)(rr?(m)(r))mr";
+            solutions[8] = "l?(m)(ll?(m)(l))m";
+            solutions[9] = "r?(m)(rr?(m)(r))m";
+            solutions[10] = "ml?(m)(ll?(m)(l))";
+            solutions[11] = "mr?(m)(rr?(m)(r))";
+
+            // A
+            // rA
+            // lA
+            // mA
+            // mlA
+            // mrA
+            // ?(A)(A)A
+            // mr?(m)(ll?(A)(A))
+            // ?(A)(A)?(A)(A)
+        }
+
+        private readonly List<string> validStarts3 = new List<string> { "A", "rA", "lA", "mA", "mlA", "mrA" };
+
+
+        public bool IsParentOfProblemSolution(string sentence, int maxLen)
+        {
+            //INFO: only works with maxlen 17!!
+
+            // eliminate wrong parents..
+            if (sentence.Length < 17 && !sentence.Contains('A'))
+            {
+                return false;
+            }
+            if (sentence.Length > 3 && !sentence.Contains('?'))
+            {
+                return false;
+            }
+            if (sentence.Length <= 3)
+            {
+                return validStarts3.Contains(sentence);
+            }
+            if (sentence.Contains("m?"))
+            {
+                return false;
+            }
+
+            if (sentence.Length <= 17 && sentence.Contains('A'))
+            {
+                // check front part of solutions..
+                // contains A, contains ?(x)(x), length > 3
+                int index = sentence.IndexOf('?');
+                if (index > 2) return false;
+
+                int firstCloseBracket = sentence.IndexOf(')');
+                // only one item in bracket
+                if ((firstCloseBracket - index) != 3) return false;
+                // must be m or A
+                if (sentence[firstCloseBracket - 1] != 'm' && sentence[firstCloseBracket - 1] != 'A') return false;
+
+                // check back and front part of solutions..
+                int lastCloseBracket = sentence.LastIndexOf(')');
+                // before first ? and after last ) either 1 left one right, or only two left (also A), or only two right (also A)
+                int diff;
+                if (index == 0)
+                {
+                    // must end with mr, ml, mA, A
+                    diff = sentence.Length - 1 - lastCloseBracket;
+                    if (diff == 0 || diff > 2) return false;
+                    if (diff == 1 && sentence[sentence.Length - 1] != 'A') return false;
+                    if (diff == 2 && (sentence[sentence.Length - 2] != 'm' || sentence[sentence.Length - 1] == 'm'))
+                        return false;
+                }
+                else if (index == 1 && (sentence[0] == 'm' || (sentence[sentence.Length - 1] != 'm' && sentence[sentence.Length - 1] != 'A'))) return false;
+                else if (index == 2)
+                {
+                    // must start with ml, mr, mA
+                    // must end with )
+                    if (sentence[sentence.Length - 1] != ')') return false;
+                    if (sentence[0] != 'm' || sentence[1] == 'm') return false;
+                }
+
+                // check middle part of solutions ..(ll?(m)(l))..
+                int index2 = sentence.IndexOf('?', index + 1);
+                if (index2 == -1)
+                {
+                    // no second ? so far..
+                    // allowed within second (..): A, lA, llA, rA, rrA
+                    int lastOpenBracket = sentence.LastIndexOf('(', lastCloseBracket);
+                    diff = lastCloseBracket - lastOpenBracket;
+                    if (diff > 4) return false;
+                    // last item must be A
+                    if (sentence[lastCloseBracket - 1] != 'A') return false;
+                    // first item must not be m
+                    if (sentence[lastOpenBracket + 1] == 'm') return false;
+                    // ll or rr
+                    if (diff == 4 && sentence[lastOpenBracket + 1] != sentence[lastOpenBracket + 2]) return false;
+                }
+                else
+                {
+                    // second ? there..
+                    // ?(x)(..?(x)(x))
+                    int secondLastCloseBracket = sentence.LastIndexOf(')', lastCloseBracket - 1);
+                    // has to end with '))'
+                    if (lastCloseBracket - secondLastCloseBracket != 1) return false;
+                    // only one item within second brackets
+                    if (sentence[secondLastCloseBracket - 2] != '(') return false;
+                    // the one item can be A, l or r
+                    if (sentence[secondLastCloseBracket - 1] == 'm') return false;
+                    // only one item in first brackets
+                    if (sentence[index2 + 3] != ')') return false;
+                    // only m or A allowed
+                    if (sentence[index2 + 2] == 'l' || sentence[index2 + 2] == 'r') return false;
+                    // ll or rr before second ? must already be there..
+                    if (sentence[index2 - 1] != 'l' && sentence[index2 - 1] != 'r') return false;
+                    if (sentence[index2 - 1] != sentence[index2 - 2]) return false;
+                }
+            }
+            else
+            {
+                // has to be solution or false..
+                return solutions.Any(solution => solution == sentence);
+            }
+
+            return true;
+        }
     }
 
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally all food pellets are discovered
-      return 89;
+    public class Ant
+    {
+        private int maxSteps = 600;
+        public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
+        public enum HeadingEnum { North, East, South, West };
+        public int FoodEaten { get; private set; }
+        private readonly char[][] world = new char[32][];
+        private int posX;
+        private int posY;
+        private int steps;
+        private HeadingEnum heading;
+        public int PosX { get { return posX; } }
+        public int PosY { get { return posY; } }
+        public HeadingEnum Heading { get { return heading; } }
+        private bool recordTrail = false;
+        private StringBuilder trailBuilder;
+
+        public string Trail
+        {
+            get
+            {
+                if (!recordTrail) throw new NotSupportedException();
+                else return trailBuilder.ToString() + heading; // add final heading as state
+            }
+        }
+
+        public Ant(bool recordTrail = false)
+        {
+            world[00] = " ###                            ".ToCharArray();
+            world[01] = "   #                            ".ToCharArray();
+            world[02] = "   #                    .###..  ".ToCharArray();
+            world[03] = "   #                    #    #  ".ToCharArray();
+            world[04] = "   #                    #    #  ".ToCharArray();
+            world[05] = "   ####.#####       .##..    .  ".ToCharArray();
+            world[06] = "            #       .        #  ".ToCharArray();
+            world[07] = "            #       #        .  ".ToCharArray();
+            world[08] = "            #       #        .  ".ToCharArray();
+            world[09] = "            #       #        #  ".ToCharArray();
+            world[10] = "            .       #        .  ".ToCharArray();
+            world[11] = "            #       .        .  ".ToCharArray();
+            world[12] = "            #       .        #  ".ToCharArray();
+            world[13] = "            #       #        .  ".ToCharArray();
+            world[14] = "            #       #  ...###.  ".ToCharArray();
+            world[15] = "            .   .#...  #        ".ToCharArray();
+            world[16] = "            .   .      .        ".ToCharArray();
+            world[17] = "            #   .      .        ".ToCharArray();
+            world[18] = "            #   #      .#...    ".ToCharArray();
+            world[19] = "            #   #          #    ".ToCharArray();
+            world[20] = "            #   #          .    ".ToCharArray();
+            world[21] = "            #   #          .    ".ToCharArray();
+            world[22] = "            #   .      ...#.    ".ToCharArray();
+            world[23] = "            #   .      #        ".ToCharArray();
+            world[24] = " ..##..#####.   #               ".ToCharArray();
+            world[25] = " #              #               ".ToCharArray();
+            world[26] = " #              #               ".ToCharArray();
+            world[27] = " #     .#######..               ".ToCharArray();
+            world[28] = " #     #                        ".ToCharArray();
+            world[29] = " .     #                        ".ToCharArray();
+            world[30] = " .####..                        ".ToCharArray();
+            world[31] = "                                ".ToCharArray();
+
+            posX = 0;
+            posY = 0;
+            heading = HeadingEnum.East;
+            FoodEaten = 0;
+            steps = 0;
+
+            this.recordTrail = recordTrail;
+            if (this.recordTrail) trailBuilder = new StringBuilder();
+        }
+
+        public bool Done()
+        {
+            return steps > maxSteps;
+        }
+
+        public void TurnRight()
+        {
+            if (steps <= maxSteps)
+            {
+                steps++;
+                if (heading == HeadingEnum.West) heading = HeadingEnum.North;
+                else heading++;
+            }
+        }
+
+        public void TurnLeft()
+        {
+            if (steps <= maxSteps)
+            {
+                steps++;
+                if (heading == HeadingEnum.North) heading = HeadingEnum.West;
+                else heading--;
+            }
+        }
+
+        public void Move()
+        {
+            if (steps <= maxSteps)
+            {
+                steps++;
+                MoveInternal(ref posX, ref posY);
+                if (world[posY][posX] == '#')
+                {
+                    FoodEaten++;
+                    world[posY][posX] = '.';
+                }
+                if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
+            }
+        }
+
+        public void Nop()
+        {
+            // wait one time step
+            if (steps <= maxSteps)
+            {
+                steps++;
+            }
+        }
+
+        private void MoveInternal(ref int posX, ref int posY)
+        {
+            switch (heading)
+            {
+                case HeadingEnum.North:
+                    posY = (posY + 31) % 32;
+                    break;
+                case HeadingEnum.East:
+                    posX = (posX + 1) % 32;
+                    break;
+                case HeadingEnum.South:
+                    posY = (posY + 1) % 32;
+                    break;
+                case HeadingEnum.West:
+                    posX = (posX + 31) % 32;
+                    break;
+            }
+        }
+
+        public bool IsFoodAhead()
+        {
+            int nextPosX = posX;
+            int nextPosY = posY;
+            MoveInternal(ref nextPosX, ref nextPosY);
+
+            if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
+
+            return world[nextPosY][nextPosX] == '#';
+        }
     }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      var ant = new Ant();
-      int p = 0;
-      Run(ant, sentence, ref p);
-      return ant.FoodEaten;
-    }
-
-    private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false) {
-      while (!ant.Done()) {
-        if (p >= sentence.Length) {
-          if (stopAfterFirst) return;
-          p = 0; // restart
-        }
-        switch (sentence[p]) {
-          case 'r': {
-              ant.TurnRight();
-              p++;
-              break;
-            }
-          case 'l': {
-              ant.TurnLeft();
-              p++;
-              break;
-            }
-          case 'm': {
-              ant.Move();
-              p++;
-              break;
-            }
-          case '?': {
-              p++; // skip p
-              if (ant.IsFoodAhead()) {
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
-                if (ant.Done()) return;
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Skip(sentence, ref p);
-              } else {
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Skip(sentence, ref p);
-                if (sentence[p] != '(') throw new ArgumentException();
-                p++;
-                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
-              }
-              break;
-            }
-          case '.': {
-              // nop
-              p++;
-              ant.Nop();
-              break;
-            }
-          case ')': {
-              p++; // skip
-              return;     // caller must continue processing
-            }
-          default: {
-              throw new ArgumentException();
-            }
-        }
-      }
-    }
-
-    private static void Skip(string sentence, ref int p) {
-      int openCount = 1;
-      while (openCount > 0) {
-        if (sentence[p] == '(') openCount++;
-        else if (sentence[p] == ')') openCount--;
-        p++;
-      }
-    }
-
-    public string CanonicalRepresentation(string phrase) {
-      //phrase = phrase.Replace("A", ".");
-      var sb = new StringBuilder(phrase);
-      string canonicalPhrase = phrase;
-      string oldPhrase;
-      do {
-        oldPhrase = canonicalPhrase;
-        sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
-        //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
-        canonicalPhrase = sb.ToString();
-      } while (canonicalPhrase != oldPhrase);
-      return canonicalPhrase;
-    }
-
-    public IEnumerable<Feature> GetFeatures(string phrase) {
-      phrase = CanonicalRepresentation(phrase);
-      var isTerminal = grammar.IsTerminal(phrase);
-
-      yield return new Feature(isTerminal + ToString(), 1.0);
-     
-      yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
-      if (!isTerminal) {
-        for (int i = 4; i < phrase.Length; i++) {
-          if (!grammar.IsTerminal(phrase[i])) {
-            yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
-            break;
-          }
-        }
-      }
-    
-      yield return new Feature(phrase, 1.0);
-    }
-
-    public IGrammar TreeBasedGPGrammar { get; private set; }
-    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
-      var sb = new StringBuilder();
-      ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
-      return sb.ToString();
-    }
-    private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb) {
-      if (node.SubtreeCount == 0) {
-        // terminal
-        sb.Append(node.Symbol.Name);
-      } else if (node.Symbol.Name == "I") {
-        Debug.Assert(node.SubtreeCount == 2);
-        sb.Append("?(");
-        ConvertTreeToSentence(node.GetSubtree(0), sb);
-        sb.Append(")(");
-        ConvertTreeToSentence(node.GetSubtree(1), sb);
-        sb.Append(")");
-      } else {
-        foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
-      }
-    }
-  }
-
-  public class Ant {
-    private int maxSteps = 600;
-    public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
-    public enum HeadingEnum { North, East, South, West };
-    public int FoodEaten { get; private set; }
-    private readonly char[][] world = new char[32][];
-    private int posX;
-    private int posY;
-    private int steps;
-    private HeadingEnum heading;
-    public int PosX { get { return posX; } }
-    public int PosY { get { return posY; } }
-    public HeadingEnum Heading { get { return heading; } }
-    private bool recordTrail = false;
-    private StringBuilder trailBuilder;
-
-    public string Trail {
-      get {
-        if (!recordTrail) throw new NotSupportedException();
-        else return trailBuilder.ToString() + heading; // add final heading as state
-      }
-    }
-
-    public Ant(bool recordTrail = false) {
-      world[00] = " ###                            ".ToCharArray();
-      world[01] = "   #                            ".ToCharArray();
-      world[02] = "   #                    .###..  ".ToCharArray();
-      world[03] = "   #                    #    #  ".ToCharArray();
-      world[04] = "   #                    #    #  ".ToCharArray();
-      world[05] = "   ####.#####       .##..    .  ".ToCharArray();
-      world[06] = "            #       .        #  ".ToCharArray();
-      world[07] = "            #       #        .  ".ToCharArray();
-      world[08] = "            #       #        .  ".ToCharArray();
-      world[09] = "            #       #        #  ".ToCharArray();
-      world[10] = "            .       #        .  ".ToCharArray();
-      world[11] = "            #       .        .  ".ToCharArray();
-      world[12] = "            #       .        #  ".ToCharArray();
-      world[13] = "            #       #        .  ".ToCharArray();
-      world[14] = "            #       #  ...###.  ".ToCharArray();
-      world[15] = "            .   .#...  #        ".ToCharArray();
-      world[16] = "            .   .      .        ".ToCharArray();
-      world[17] = "            #   .      .        ".ToCharArray();
-      world[18] = "            #   #      .#...    ".ToCharArray();
-      world[19] = "            #   #          #    ".ToCharArray();
-      world[20] = "            #   #          .    ".ToCharArray();
-      world[21] = "            #   #          .    ".ToCharArray();
-      world[22] = "            #   .      ...#.    ".ToCharArray();
-      world[23] = "            #   .      #        ".ToCharArray();
-      world[24] = " ..##..#####.   #               ".ToCharArray();
-      world[25] = " #              #               ".ToCharArray();
-      world[26] = " #              #               ".ToCharArray();
-      world[27] = " #     .#######..               ".ToCharArray();
-      world[28] = " #     #                        ".ToCharArray();
-      world[29] = " .     #                        ".ToCharArray();
-      world[30] = " .####..                        ".ToCharArray();
-      world[31] = "                                ".ToCharArray();
-
-      posX = 0;
-      posY = 0;
-      heading = HeadingEnum.East;
-      FoodEaten = 0;
-      steps = 0;
-
-      this.recordTrail = recordTrail;
-      if (this.recordTrail) trailBuilder = new StringBuilder();
-    }
-
-    public bool Done() {
-      return steps > maxSteps;
-    }
-
-    public void TurnRight() {
-      if (steps <= maxSteps) {
-        steps++;
-        if (heading == HeadingEnum.West) heading = HeadingEnum.North;
-        else heading++;
-      }
-    }
-
-    public void TurnLeft() {
-      if (steps <= maxSteps) {
-        steps++;
-        if (heading == HeadingEnum.North) heading = HeadingEnum.West;
-        else heading--;
-      }
-    }
-
-    public void Move() {
-      if (steps <= maxSteps) {
-        steps++;
-        MoveInternal(ref posX, ref posY);
-        if (world[posY][posX] == '#') {
-          FoodEaten++;
-          world[posY][posX] = '.';
-        }
-        if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
-      }
-    }
-
-    public void Nop() {
-      // wait one time step
-      if (steps <= maxSteps) {
-        steps++;
-      }
-    }
-
-    private void MoveInternal(ref int posX, ref int posY) {
-      switch (heading) {
-        case HeadingEnum.North:
-          posY = (posY + 31) % 32;
-          break;
-        case HeadingEnum.East:
-          posX = (posX + 1) % 32;
-          break;
-        case HeadingEnum.South:
-          posY = (posY + 1) % 32;
-          break;
-        case HeadingEnum.West:
-          posX = (posX + 31) % 32;
-          break;
-      }
-    }
-
-    public bool IsFoodAhead() {
-      int nextPosX = posX;
-      int nextPosY = posY;
-      MoveInternal(ref nextPosX, ref nextPosY);
-
-      if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
-
-      return world[nextPosY][nextPosX] == '#';
-    }
-  }
 }
Index: /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs
===================================================================
--- /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 12814)
+++ /branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs	(revision 12815)
@@ -12,19 +12,21 @@
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
-namespace HeuristicLab.Problems.GrammaticalOptimization {
-  public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem {
-    //    private const string grammarString = @"
-    //    G(E):
-    //    E -> V | V+E | V-E | V*E | (E)
-    //    V -> a .. j 
-    //    ";
-    private const string grammarString = @"
+namespace HeuristicLab.Problems.GrammaticalOptimization
+{
+    public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem
+    {
+        //    private const string grammarString = @"
+        //    G(E):
+        //    E -> V | V+E | V-E | V*E | (E)
+        //    V -> a .. j 
+        //    ";
+        private const string grammarString = @"
     G(E):
     E -> a | b | c | d | e | f | g | h | i | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | i+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | i*E | j*E 
     ";
 
-    // for tree-based GP in HL we need a different grammar for the same language
-    // E = expr, S = sum, P = product
-    private const string hlGrammarString = @"
+        // for tree-based GP in HL we need a different grammar for the same language
+        // E = expr, S = sum, P = product
+        private const string hlGrammarString = @"
     G(E):
     E -> S | P | a | b | c | d | e | f | g | h | i | j
@@ -32,162 +34,302 @@
     P -> EE | EEE
     ";
-    // mininmal tree for the optimal expr (40 nodes)
-    // E S
-    //     E S
-    //         E P 
-    //           E a E b
-    //         E P 
-    //           E c E d
-    //         E P 
-    //           E e E f
-    //     E S
-    //         E P 
-    //           E a E g E i
-    //         E P 
-    //           E c E f E j
-
-    public IGrammar TreeBasedGPGrammar { get; private set; }
-
-    private readonly IGrammar grammar;
-
-    private readonly int N;
-    private readonly double[][] x;
-    private readonly double[] y;
-    public string Name { get { return "SymbolicRegressionPoly10"; } }
-
-    public SymbolicRegressionPoly10Problem() {
-      this.grammar = new Grammar(grammarString);
-      this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
-
-      this.N = 500;
-      this.x = new double[N][];
-      this.y = new double[N];
-
-      GenerateData();
+        // mininmal tree for the optimal expr (40 nodes)
+        // E S
+        //     E S
+        //         E P 
+        //           E a E b
+        //         E P 
+        //           E c E d
+        //         E P 
+        //           E e E f
+        //     E S
+        //         E P 
+        //           E a E g E i
+        //         E P 
+        //           E c E f E j
+
+        public IGrammar TreeBasedGPGrammar { get; private set; }
+
+        private readonly IGrammar grammar;
+
+        private readonly int N;
+        private readonly double[][] x;
+        private readonly double[] y;
+        public string Name { get { return "SymbolicRegressionPoly10"; } }
+
+        public SymbolicRegressionPoly10Problem()
+        {
+            this.grammar = new Grammar(grammarString);
+            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
+
+            this.N = 500;
+            this.x = new double[N][];
+            this.y = new double[N];
+
+            GenerateData();
+        }
+
+        private void GenerateData()
+        {
+            // generate data with fixed seed to make sure that data is always the same
+            var rand = new Random(31415);
+            for (int i = 0; i < N; i++)
+            {
+                x[i] = new double[10];
+                for (int j = 0; j < 10; j++)
+                {
+                    x[i][j] = rand.NextDouble() * 2 - 1;
+                }
+                // poly-10 no noise
+                /* a*b + c*d + e*f + a*g*i + c*f*j */
+                y[i] = x[i][0] * x[i][1] +
+                       x[i][2] * x[i][3] +
+                       x[i][4] * x[i][5] +
+                       x[i][0] * x[i][6] * x[i][8] +
+                       x[i][2] * x[i][5] * x[i][9];
+            }
+        }
+
+        public double BestKnownQuality(int maxLen)
+        {
+            // for now only an upper bound is returned, ideally we have an R² of 1.0
+            // the optimal R² can only be reached for sentences of at least 23 symbols
+            return 1.0;
+        }
+
+        public IGrammar Grammar
+        {
+            get { return grammar; }
+        }
+
+        public double Evaluate(string sentence)
+        {
+            var interpreter = new ExpressionInterpreter();
+            return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
+        }
+
+
+        // most-recently-used caching (with limited capacity) for canonical representations
+        MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
+        // right now only + and * is supported
+        public string CanonicalRepresentation(string phrase)
+        {
+            string canonicalPhrase;
+            if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase))
+            {
+                var terms = phrase.Split('+');
+                var canonicalTerms = new SortedSet<string>();
+                // only the last term might contain a NT-symbol. make sure this term is added at the end
+                for (int i = 0; i < terms.Length - 1; i++)
+                {
+                    canonicalTerms.Add(CanonicalTerm(terms[i]));
+                }
+
+                var sb = new StringBuilder(phrase.Length);
+                foreach (var t in canonicalTerms)
+                    sb.Append(t).Append('+');
+
+                sb.Append(CanonicalTerm(terms[terms.Length - 1]));
+                canonicalPhrase = sb.ToString();
+                canonicalPhraseCache.Add(phrase, canonicalPhrase);
+            }
+            return canonicalPhrase;
+        }
+
+        // cache the canonical form of terms for performance reasons
+        private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
+        private string CanonicalTerm(string term)
+        {
+            string canonicalTerm;
+            if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm))
+            {
+                // add
+                var chars = term.ToCharArray();
+                Array.Sort(chars);
+                var sb = new StringBuilder(chars.Length);
+                // we want to have the up-case characters last
+                for (int i = chars.Length - 1; i > 0; i--)
+                {
+                    if (chars[i] != '*')
+                    {
+                        sb.Append(chars[i]);
+                        if (chars[i - 1] != '*') sb.Append('*');
+                    }
+                }
+                if (chars[0] != '*') sb.Append(chars[0]); // last term
+                canonicalTerm = sb.ToString();
+                canonicalTermDictionary.Add(term, canonicalTerm);
+            }
+            return canonicalTerm;
+        }
+
+        // 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));
+            }
+            return canonicalTerms.Select(entry => new Feature(entry, 1.0))
+              .Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
+        }
+
+        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
+        {
+            var sb = new StringBuilder();
+
+            TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
+
+            return sb.ToString();
+        }
+
+        private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb)
+        {
+            if (treeNode.SubtreeCount == 0)
+            {
+                // terminal
+                sb.Append(treeNode.Symbol.Name);
+            }
+            else
+            {
+                string op = string.Empty;
+                switch (treeNode.Symbol.Name)
+                {
+                    case "S": op = "+"; break;
+                    case "P": op = "*"; break;
+                    default:
+                        {
+                            Debug.Assert(treeNode.SubtreeCount == 1);
+                            break;
+                        }
+                }
+                // nonterminal
+                if (op == "+") sb.Append("(");
+                TreeToSentence(treeNode.Subtrees.First(), sb);
+                foreach (var subTree in treeNode.Subtrees.Skip(1))
+                {
+                    sb.Append(op);
+                    TreeToSentence(subTree, sb);
+                }
+                if (op == "+") sb.Append(")");
+            }
+        }
+
+        public void GenerateProblemSolutions(int maxLen)
+        {
+        }
+
+        private readonly List<string> canonicaSolutionTerms3 = new List<string> { "b*a", "d*c", "f*e" };
+        private readonly List<string> canonicaSolutionTerms5 = new List<string> { "i*g*a", "j*f*c" };
+
+        public bool IsParentOfProblemSolution(string sentence, int maxLen)
+        {
+            /* a*b + c*d + e*f + a*g*i + c*f*j */
+
+            bool containsE = sentence.EndsWith("E");
+
+            if (!containsE && sentence.Length != 23 || sentence.Length > 23)
+            {
+                return false;
+            }
+
+            // now: contains E or has solution length..
+            string[] terms = sentence.Split('+');
+
+            bool[] terms3 = new bool[3];
+            bool[] terms5 = new bool[2];
+
+            // run through addends without E
+            for (int i = 0; i < terms.Length - 1; i++)
+            {
+                string term = terms[i];
+                if (term.Length == 3)
+                {
+                    string canonicalTerm = CanonicalTerm(term);
+                    int index = canonicaSolutionTerms3.IndexOf(canonicalTerm);
+                    if (index < 0 || terms3[index])
+                    {
+                        // term is not part of solution or twice in solution
+                        return false;
+                    }
+                    terms3[index] = true;
+                }
+                else if (term.Length == 5)
+                {
+                    string canonicalTerm = CanonicalTerm(term);
+                    int index = canonicaSolutionTerms5.IndexOf(canonicalTerm);
+                    if (index < 0 || terms5[index])
+                    {
+                        // term is not part of solution or twice in solution
+                        return false;
+                    }
+                    terms5[index] = true;
+                }
+                else
+                {
+                    return false;
+                }
+            }
+
+            string lastTerm = terms[terms.Length - 1];
+            if (containsE)
+            {
+                if (lastTerm.Length == 1)
+                {
+                    // is E
+                    return true;
+                }
+                string withoutE = lastTerm.Substring(0, lastTerm.Length - 2);
+                if (lastTerm.Length == 3)
+                {
+                    for (int i = 0; i < 3; i++)
+                    {
+                        if (!terms3[i] && canonicaSolutionTerms3[i].Contains(withoutE))
+                        {
+                            return true;
+                        }
+                    }
+
+                }
+                else if (lastTerm.Length == 5)
+                {
+                    for (int i = 0; i < 2; i++)
+                    {
+                        if (!terms5[i] && canonicaSolutionTerms5[i].Contains(withoutE))
+                        {
+                            return true;
+                        }
+                    }
+                }
+            }
+            else
+            {
+                // check if it is already correct solution
+                if (lastTerm.Length == 3)
+                {
+                    for (int i = 0; i < 3; i++)
+                    {
+                        if (!terms3[i] && canonicaSolutionTerms3[i] == lastTerm)
+                        {
+                            return true;
+                        }
+                    }
+
+                }
+                else if (lastTerm.Length == 5)
+                {
+                    for (int i = 0; i < 2; i++)
+                    {
+                        if (!terms5[i] && canonicaSolutionTerms5[i] == lastTerm)
+                        {
+                            return true;
+                        }
+                    }
+                }
+            }
+
+            return false;
+        }
     }
-
-    private void GenerateData() {
-      // generate data with fixed seed to make sure that data is always the same
-      var rand = new Random(31415);
-      for (int i = 0; i < N; i++) {
-        x[i] = new double[10];
-        for (int j = 0; j < 10; j++) {
-          x[i][j] = rand.NextDouble() * 2 - 1;
-        }
-        // poly-10 no noise
-        /* a*b + c*d + e*f + a*g*i + c*f*j */
-        y[i] = x[i][0] * x[i][1] +
-               x[i][2] * x[i][3] +
-               x[i][4] * x[i][5] +
-               x[i][0] * x[i][6] * x[i][8] +
-               x[i][2] * x[i][5] * x[i][9];
-      }
-    }
-
-    public double BestKnownQuality(int maxLen) {
-      // for now only an upper bound is returned, ideally we have an R² of 1.0
-      // the optimal R² can only be reached for sentences of at least 23 symbols
-      return 1.0;
-    }
-
-    public IGrammar Grammar {
-      get { return grammar; }
-    }
-
-    public double Evaluate(string sentence) {
-      var interpreter = new ExpressionInterpreter();
-      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
-    }
-
-
-    // most-recently-used caching (with limited capacity) for canonical representations
-    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
-    // right now only + and * is supported
-    public string CanonicalRepresentation(string phrase) {
-      string canonicalPhrase;
-      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
-        var terms = phrase.Split('+');
-        var canonicalTerms = new SortedSet<string>();
-        // only the last term might contain a NT-symbol. make sure this term is added at the end
-        for (int i = 0; i < terms.Length - 1; i++) {
-          canonicalTerms.Add(CanonicalTerm(terms[i]));
-        }
-
-        var sb = new StringBuilder(phrase.Length);
-        foreach (var t in canonicalTerms)
-          sb.Append(t).Append('+');
-
-        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
-        canonicalPhrase = sb.ToString();
-        canonicalPhraseCache.Add(phrase, canonicalPhrase);
-      }
-      return canonicalPhrase;
-    }
-
-    // cache the canonical form of terms for performance reasons
-    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
-    private string CanonicalTerm(string term) {
-      string canonicalTerm;
-      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
-        // add
-        var chars = term.ToCharArray();
-        Array.Sort(chars);
-        var sb = new StringBuilder(chars.Length);
-        // we want to have the up-case characters last
-        for (int i = chars.Length - 1; i > 0; i--) {
-          if (chars[i] != '*') {
-            sb.Append(chars[i]);
-            if (chars[i - 1] != '*') sb.Append('*');
-          }
-        }
-        if (chars[0] != '*') sb.Append(chars[0]); // last term
-        canonicalTerm = sb.ToString();
-        canonicalTermDictionary.Add(term, canonicalTerm);
-      }
-      return canonicalTerm;
-    }
-
-    // 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));
-      }
-      return canonicalTerms.Select(entry => new Feature(entry, 1.0))
-        .Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
-    }
-
-    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
-      var sb = new StringBuilder();
-
-      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
-
-      return sb.ToString();
-    }
-
-    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
-      if (treeNode.SubtreeCount == 0) {
-        // terminal
-        sb.Append(treeNode.Symbol.Name);
-      } else {
-        string op = string.Empty;
-        switch (treeNode.Symbol.Name) {
-          case "S": op = "+"; break;
-          case "P": op = "*"; break;
-          default: {
-              Debug.Assert(treeNode.SubtreeCount == 1);
-              break;
-            }
-        }
-        // nonterminal
-        if (op == "+") sb.Append("(");
-        TreeToSentence(treeNode.Subtrees.First(), sb);
-        foreach (var subTree in treeNode.Subtrees.Skip(1)) {
-          sb.Append(op);
-          TreeToSentence(subTree, sb);
-        }
-        if (op == "+") sb.Append(")");
-      }
-    }
-  }
 }
