Index: branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 12049)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln	(revision 12050)
@@ -1,5 +1,7 @@
 ﻿
 Microsoft Visual Studio Solution File, Format Version 12.00
-# Visual Studio 2012
+# Visual Studio 2013
+VisualStudioVersion = 12.0.31101.0
+MinimumVisualStudioVersion = 10.0.40219.1
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GrammaticalOptimization", "HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj", "{CB9DCCF6-667E-4A13-B82D-DBD6B45A045E}"
 EndProject
@@ -59,4 +61,6 @@
 	EndProjectSection
 EndProject
+Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.MonteCarloTreeSearch", "HeuristicLab.Algorithms.MonteCarloTreeSearch\HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj", "{2C115235-8FA9-4F7F-B3A0-A0144F8A35CA}"
+EndProject
 Global
 	GlobalSection(SolutionConfigurationPlatforms) = preSolution
@@ -105,4 +109,8 @@
 		{8B4C199E-C08B-479E-9B82-6AE5B113459E}.Release|Any CPU.ActiveCfg = Release|Any CPU
 		{8B4C199E-C08B-479E-9B82-6AE5B113459E}.Release|Any CPU.Build.0 = Release|Any CPU
+		{2C115235-8FA9-4F7F-B3A0-A0144F8A35CA}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+		{2C115235-8FA9-4F7F-B3A0-A0144F8A35CA}.Debug|Any CPU.Build.0 = Debug|Any CPU
+		{2C115235-8FA9-4F7F-B3A0-A0144F8A35CA}.Release|Any CPU.ActiveCfg = Release|Any CPU
+		{2C115235-8FA9-4F7F-B3A0-A0144F8A35CA}.Release|Any CPU.Build.0 = Release|Any CPU
 	EndGlobalSection
 	GlobalSection(SolutionProperties) = preSolution
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Base/TreeNode.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Base/TreeNode.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Base/TreeNode.cs	(revision 12050)
@@ -0,0 +1,27 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.MonteCarloTreeSearch
+{
+    public class TreeNode
+    {
+        public string phrase;
+        public TreeNode parent;
+        public List<TreeNode> children;
+        public IBanditPolicyActionInfo actionInfo;
+        public bool expandable;
+        public List<int> unvisitedNonTerminals;
+
+        public TreeNode(TreeNode parent, string phrase, bool expandable, List<int> unvisitedNonTerminals)
+        {
+            this.phrase = phrase;
+            this.expandable = expandable;
+            this.unvisitedNonTerminals = unvisitedNonTerminals;
+        }
+    }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Expansion/IExpansionPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Expansion/IExpansionPolicy.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Expansion/IExpansionPolicy.cs	(revision 12050)
@@ -0,0 +1,13 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.MonteCarloTreeSearch.Expansion
+{
+    public interface IExpansionPolicy
+    {
+        TreeNode ExpandTreeNode(TreeNode node);
+    }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Expansion/RandomExpansionPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Expansion/RandomExpansionPolicy.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Expansion/RandomExpansionPolicy.cs	(revision 12050)
@@ -0,0 +1,16 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.MonteCarloTreeSearch.Expansion
+{
+    public class RandomExpansionPolicy : IExpansionPolicy
+    {
+        public TreeNode ExpandTreeNode(TreeNode node)
+        {
+            throw new NotImplementedException();
+        }
+    }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj	(revision 12050)
@@ -0,0 +1,68 @@
+﻿<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="12.0" DefaultTargets="Build" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props" Condition="Exists('$(MSBuildExtensionsPath)\$(MSBuildToolsVersion)\Microsoft.Common.props')" />
+  <PropertyGroup>
+    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
+    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
+    <ProjectGuid>{2C115235-8FA9-4F7F-B3A0-A0144F8A35CA}</ProjectGuid>
+    <OutputType>Library</OutputType>
+    <AppDesignerFolder>Properties</AppDesignerFolder>
+    <RootNamespace>HeuristicLab.Algorithms.MonteCarloTreeSearch</RootNamespace>
+    <AssemblyName>HeuristicLab.Algorithms.MonteCarloTreeSearch</AssemblyName>
+    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
+    <FileAlignment>512</FileAlignment>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
+    <DebugSymbols>true</DebugSymbols>
+    <DebugType>full</DebugType>
+    <Optimize>false</Optimize>
+    <OutputPath>bin\Debug\</OutputPath>
+    <DefineConstants>DEBUG;TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
+    <DebugType>pdbonly</DebugType>
+    <Optimize>true</Optimize>
+    <OutputPath>bin\Release\</OutputPath>
+    <DefineConstants>TRACE</DefineConstants>
+    <ErrorReport>prompt</ErrorReport>
+    <WarningLevel>4</WarningLevel>
+  </PropertyGroup>
+  <ItemGroup>
+    <Reference Include="System" />
+    <Reference Include="System.Core" />
+    <Reference Include="System.Xml.Linq" />
+    <Reference Include="System.Data.DataSetExtensions" />
+    <Reference Include="Microsoft.CSharp" />
+    <Reference Include="System.Data" />
+    <Reference Include="System.Xml" />
+  </ItemGroup>
+  <ItemGroup>
+    <Compile Include="MonteCarloTreeSearch.cs" />
+    <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="TreeNode.cs" />
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.Bandits\HeuristicLab.Algorithms.Bandits.csproj">
+      <Project>{24408f7d-ee0f-4886-a08b-ec324d662e47}</Project>
+      <Name>HeuristicLab.Algorithms.Bandits</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.GrammaticalOptimization\HeuristicLab.Algorithms.GrammaticalOptimization.csproj">
+      <Project>{eea07488-1a51-412a-a52c-53b754a628b3}</Project>
+      <Name>HeuristicLab.Algorithms.GrammaticalOptimization</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
+      <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>
+      <Name>HeuristicLab.Problems.GrammaticalOptimization</Name>
+    </ProjectReference>
+  </ItemGroup>
+  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
+  <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 
+       Other similar extension points exist, see Microsoft.Common.targets.
+  <Target Name="BeforeBuild">
+  </Target>
+  <Target Name="AfterBuild">
+  </Target>
+  -->
+</Project>
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs	(revision 12050)
@@ -0,0 +1,93 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Resources;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
+using HeuristicLab.Algorithms.MonteCarloTreeSearch;
+using HeuristicLab.Algorithms.MonteCarloTreeSearch.Expansion;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.GrammaticalOptimization.Solvers
+{
+    public class MonteCarloTreeSearch : SolverBase
+    {
+        private readonly int maxLen;
+        private readonly IProblem problem;
+        private readonly Random random;
+        private readonly IBanditPolicy behaviourPolicy;
+        private readonly IExpansionPolicy expansionPolicy;
+        private readonly ISimulationPolicy simulationPolicy;
+        private TreeNode rootNode;
+        private List<IBanditPolicyActionInfo> actions;
+        private List<TreeNode> nodes;
+
+        public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
+            IExpansionPolicy expansionPolicy, ISimulationPolicy simulationPolicy)
+        {
+            this.problem = problem;
+            this.maxLen = maxLen;
+            this.random = random;
+            this.behaviourPolicy = behaviourPolicy;
+            this.expansionPolicy = expansionPolicy;
+            this.simulationPolicy = simulationPolicy;
+        }
+
+        public bool StopRequested
+        {
+            get;
+            set;
+        }
+
+        public override void Run(int maxIterations)
+        {
+            Reset();
+            for (int i = 0; !StopRequested && !Done() && i < maxIterations; i++)
+            {
+                // select by behaviour policy
+                TreeNode currentNode;
+                do
+                {
+                    int currentActionIndex = behaviourPolicy.SelectAction(random, actions);
+                    currentNode = nodes[currentActionIndex];
+                } while (!Expandable(currentNode));
+
+                // expand tree
+                currentNode = expansionPolicy.ExpandTreeNode(currentNode);
+                // simulate
+                double reward = simulationPolicy.Simulate(currentNode);
+                // propagate/reward
+                Propagate(currentNode, reward);
+            }
+        }
+
+        private void Reset()
+        {
+            StopRequested = false;
+            bestQuality = 0.0;
+            rootNode = new TreeNode(null, problem.Grammar.SentenceSymbol.ToString(), true, new List<int>() { 0 });
+        }
+
+        private bool Done()
+        {
+            return !rootNode.expandable;
+        }
+
+        private bool Expandable(TreeNode node)
+        {
+            return !problem.Grammar.IsTerminal(node.phrase);
+        }
+
+        private void Propagate(TreeNode node, double reward)
+        {
+            var currentNode = node;
+            do
+            {
+                currentNode.actionInfo.UpdateReward(reward);
+                currentNode = node.parent;
+            } while (currentNode != null);
+        }
+    }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Properties/AssemblyInfo.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Properties/AssemblyInfo.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Properties/AssemblyInfo.cs	(revision 12050)
@@ -0,0 +1,36 @@
+﻿using System.Reflection;
+using System.Runtime.CompilerServices;
+using System.Runtime.InteropServices;
+
+// General Information about an assembly is controlled through the following 
+// set of attributes. Change these attribute values to modify the information
+// associated with an assembly.
+[assembly: AssemblyTitle("HeuristicLab.Algorithms.MonteCarloTreeSearch")]
+[assembly: AssemblyDescription("")]
+[assembly: AssemblyConfiguration("")]
+[assembly: AssemblyCompany("")]
+[assembly: AssemblyProduct("HeuristicLab.Algorithms.MonteCarloTreeSearch")]
+[assembly: AssemblyCopyright("Copyright ©  2015")]
+[assembly: AssemblyTrademark("")]
+[assembly: AssemblyCulture("")]
+
+// Setting ComVisible to false makes the types in this assembly not visible 
+// to COM components.  If you need to access a type in this assembly from 
+// COM, set the ComVisible attribute to true on that type.
+[assembly: ComVisible(false)]
+
+// The following GUID is for the ID of the typelib if this project is exposed to COM
+[assembly: Guid("3482040b-e928-4464-8b3c-460a5886a18d")]
+
+// Version information for an assembly consists of the following four values:
+//
+//      Major Version
+//      Minor Version 
+//      Build Number
+//      Revision
+//
+// You can specify all the values or you can default the Build and Revision Numbers 
+// by using the '*' as shown below:
+// [assembly: AssemblyVersion("1.0.*")]
+[assembly: AssemblyVersion("1.0.0.0")]
+[assembly: AssemblyFileVersion("1.0.0.0")]
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Simulation/ISimulationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Simulation/ISimulationPolicy.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Simulation/ISimulationPolicy.cs	(revision 12050)
@@ -0,0 +1,13 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace HeuristicLab.Algorithms.MonteCarloTreeSearch
+{
+    public interface ISimulationPolicy
+    {
+        double Simulate(TreeNode node);
+    }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Simulation/RandomSimulationPolicy.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Simulation/RandomSimulationPolicy.cs	(revision 12050)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Simulation/RandomSimulationPolicy.cs	(revision 12050)
@@ -0,0 +1,25 @@
+﻿using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
+using HeuristicLab.Problems.GrammaticalOptimization;
+
+namespace HeuristicLab.Algorithms.MonteCarloTreeSearch.Simulation
+{
+    public class RandomSimulationPolicy : ISimulationPolicy
+    {
+        private ISymbolicExpressionTreeProblem problem;
+        public RandomSimulationPolicy(ISymbolicExpressionTreeProblem problem)
+        {
+            this.problem = problem;
+        }
+
+        public double Simulate(TreeNode node)
+        {
+
+            return 0.0;
+        }
+    }
+}
Index: branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs
===================================================================
--- branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 12049)
+++ branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs	(revision 12050)
@@ -36,7 +36,7 @@
       var random = new Random();
 
-      var problem = new SymbolicRegressionPoly10Problem();
+      //var problem = new SymbolicRegressionPoly10Problem();
       //var problem = new SantaFeAntProblem();              
-      //var problem = new RoyalPairProblem();
+      var problem = new RoyalPairProblem();
       //var problem = new EvenParityProblem();
       var alg = new SequentialSearch(problem, 23, random, 0,
