Changeset 12781 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch

Timestamp:

07/20/15 16:45:08 (9 years ago)

Author:

aballeit

Message:

#2283 stable GUI; ThreadPool for runs; improved TreeAnalysis

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization

Files:

• . (modified) (1 prop)
• HeuristicLab.Algorithms.MonteCarloTreeSearch (modified) (2 props)
• HeuristicLab.Algorithms.MonteCarloTreeSearch/Base/TreeInfos.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.MonteCarloTreeSearch/HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj (modified) (1 diff)
• HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs (modified) (6 diffs)
• HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch_PruneLeaves.cs (added)

branches/HeuristicLab.Problems.GrammaticalOptimization

@@ -3 +3 @@
 TestResults
 _ReSharper.GrammaticalOptimization
+EvaluationResults

@@ -3 +3 @@
 TestResults
 _ReSharper.GrammaticalOptimization
+EvaluationResults

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/Base/TreeInfos.cs

@@ -13 +13 @@
             
         }
-        public TreeInfos(int totalNodes, int unexpandedNodes, int expandedNodes, int leaveNodes, int deepestLevel,
-            double averageLevel, double averageChildren)
+        public TreeInfos(int totalNodes, int unexpandedNodes, int expandedNodes, int leaveNodes, int deepestLevel)
         {
             TotalNodes = totalNodes;
@@ -21 +20 @@
             LeaveNodes = leaveNodes;
             DeepestLevel = deepestLevel;
-            AverageLevel = averageLevel;
-            AverageChildren = averageChildren;
         }
 
@@ -30 +27 @@
         public int LeaveNodes { get; set; }
         public int DeepestLevel { get; set; }
-        public double AverageLevel { get; set; }
-        public double AverageChildren { get; set; }
     }
 }

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj

@@ -42 +42 @@
   <ItemGroup>
     <Compile Include="Base\TreeInfos.cs" />
+    <Compile Include="MonteCarloTreeSearch.cs" />
     <Compile Include="Simulation\ISimulation.cs" />
-    <Compile Include="MonteCarloTreeSearch.cs" />
+    <Compile Include="MonteCarloTreeSearch_PruneLeaves.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
     <Compile Include="Base\TreeNode.cs" />

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch.cs

@@ -20 +20 @@
     public class MonteCarloTreeSearch : SolverBase
     {
-        private readonly int maxLen;
-        private readonly IProblem problem;
-        private readonly IGrammar grammar;
-        private readonly Random random;
-        private readonly IBanditPolicy behaviourPolicy;
-        private readonly ISimulation simulation;
-        private TreeNode rootNode;
-        private bool isPaused = false;
-        private object pauseLock = new object();
+        protected readonly int maxLen;
+        protected readonly IProblem problem;
+        protected readonly IGrammar grammar;
+        protected readonly Random random;
+        protected readonly IBanditPolicy behaviourPolicy;
+        protected readonly ISimulation simulation;
+        protected TreeNode rootNode;
+        protected bool isPaused = false;
+        protected object pauseLock = new object();
 
         public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
@@ -71 +71 @@
                 string phrase = currentNode.phrase;
 
-                if (phrase.Length <= maxLen)
-                {
-                    // Version 2:
-                    if (currentNode.children != null && !currentNode.children.Any())
-                    {
-                        // already removed all child nodes so remove it too..
-                        currentNode.parent.children.Remove(currentNode);
-                        continue;
-                    }
+                if (!grammar.IsTerminal(phrase) && phrase.Length <= maxLen)
+                {
                     ExpandTreeNode(currentNode);
-                    if (currentNode.children.Any())
-                    {
-                        currentNode =
-                            currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
-                                ];
-                    }
-                    else
-                    {
-                        // Version 2:
-                        // remove currentNode from tree..
-                        currentNode.parent.children.Remove(currentNode);
-                    }
+                    currentNode =
+                        currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
+                            ];
                 }
                 if (currentNode.phrase.Length <= maxLen)
@@ -101 +85 @@
 
                     Propagate(currentNode, quality);
-
-                }
-            }
-        }
-
-        private bool HasNonTerminal(string phrase)
-        {
-            foreach (char symbol in phrase)
-            {
-                if (grammar.IsNonTerminal(symbol))
-                {
-                    return true;
-                }
-            }
-
-            return false;
-        }
-
-        private void ExpandTreeNode(TreeNode treeNode)
+                }
+            }
+        }
+
+        protected void ExpandTreeNode(TreeNode treeNode)
         {
             // create children on the first visit
@@ -150 +120 @@
         }
 
-        private void Reset()
+        protected void Reset()
         {
             StopRequested = false;
@@ -157 +127 @@
         }
 
-        private void Propagate(TreeNode node, double quality)
+        protected void Propagate(TreeNode node, double quality)
         {
             var currentNode = node;
@@ -167 +137 @@
         }
 
+        private void GetTreeInfosRek(TreeInfos treeInfos, List<TreeNode> children)
+        {
+            treeInfos.TotalNodes += children.Count;
+            foreach (TreeNode child in children)
+            {
+                if (child.children != null)
+                {
+                    treeInfos.ExpandedNodes++;
+                    if (treeInfos.DeepestLevel <= child.level)
+                    {
+                        treeInfos.DeepestLevel = child.level + 1;
+                    }
+                    GetTreeInfosRek(treeInfos, child.children);
+                }
+                else
+                {
+                    if (grammar.IsTerminal(child.phrase))
+                    {
+                        treeInfos.LeaveNodes++;
+                    }
+                    else
+                    {
+                        treeInfos.UnexpandedNodes++;
+                    }
+                }
+            }
+        }
+
         public TreeInfos GetTreeInfos()
         {
-            int totalNodes = 0;
-            int unexpandedNodes = 0;
-            int expandedNodes = 0;
-            int leaveNodes = 0;
-            int deepestLevel = 0;
-            int totalLevel = 0;
-            int totalChildren = 0;
-
-            List<TreeNode> toDoNodes = new List<TreeNode>();
+            TreeInfos treeInfos = new TreeInfos();
+
             if (rootNode != null)
             {
-                toDoNodes.Add(rootNode);
-            }
-            while (toDoNodes.Any())
-            {
-                TreeNode currentNode = toDoNodes[0];
-                toDoNodes.RemoveAt(0);
-                totalNodes++;
-                if (currentNode.level > deepestLevel)
-                {
-                    deepestLevel = currentNode.level;
-                }
-                totalLevel += currentNode.level;
-
-                if (currentNode.children != null)
-                {
-                    totalChildren += currentNode.children.Count;
-                    toDoNodes.AddRange(currentNode.children);
-                    expandedNodes++;
+                treeInfos.TotalNodes++;
+                if (rootNode.children != null)
+                {
+                    treeInfos.ExpandedNodes++;
+                    treeInfos.DeepestLevel = rootNode.level + 1;
+                    GetTreeInfosRek(treeInfos, rootNode.children);
                 }
                 else
                 {
-                    if (!HasNonTerminal(currentNode.phrase))
-                    {
-                        leaveNodes++;
+                    treeInfos.DeepestLevel = rootNode.level;
+                    if (grammar.IsTerminal(rootNode.phrase))
+                    {
+                        treeInfos.LeaveNodes++;
                     }
                     else
                     {
-                        unexpandedNodes++;
-                    }
-                }
-            }
-            return new TreeInfos(totalNodes, unexpandedNodes, expandedNodes, leaveNodes, deepestLevel,
-                totalLevel / totalNodes, totalChildren / expandedNodes);
+                        treeInfos.UnexpandedNodes++;
+                    }
+                }
+            }
+            return treeInfos;
         }
 
         public byte[] GenerateSvg()
         {
-            IGetStartProcessQuery getStartProcessQuery = new GetStartProcessQuery();
-            IGetProcessStartInfoQuery getProcessStartInfoQuery = new GetProcessStartInfoQuery();
-            IRegisterLayoutPluginCommand registerLayoutPluginCommand =
-                new RegisterLayoutPluginCommand(getProcessStartInfoQuery, getStartProcessQuery);
-
-            GraphGeneration wrapper = new GraphGeneration(getStartProcessQuery,
-                getProcessStartInfoQuery,
-                registerLayoutPluginCommand);
-            wrapper.GraphvizPath = @"../../../Graphviz2.38/bin";
-            StringBuilder dotFile = new StringBuilder("digraph {");
-            dotFile.AppendLine();
-            dotFile.AppendLine("splines=ortho;");
-            dotFile.AppendLine("concentrate=true;");
-            dotFile.AppendLine("ranksep=1.2;");
-
-            List<TreeNode> toDoNodes = new List<TreeNode>();
-            if (rootNode != null)
-            {
-                toDoNodes.Add(rootNode);
-                // declare node
-                string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, rootNode.actionInfo.Value);
-
-                dotFile.AppendLine(string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
-                    rootNode.GetHashCode(),
-                    rootNode.phrase, rootNode.actionInfo.Value, rootNode.actionInfo.Tries, hexColor));
-            }
-
-            // to put nodes on the same level in graph
-            Dictionary<int, List<TreeNode>> levelMap = new Dictionary<int, List<TreeNode>>();
-
-            List<TreeNode> sameLevelNodes;
-
-            while (toDoNodes.Any())
-            {
-                TreeNode currentNode = toDoNodes[0];
-                toDoNodes.RemoveAt(0);
-                // put currentNode into levelMap
-                if (levelMap.TryGetValue(currentNode.level, out sameLevelNodes))
-                {
-                    sameLevelNodes.Add(currentNode);
-                }
-                else
-                {
-                    sameLevelNodes = new List<TreeNode>();
-                    sameLevelNodes.Add(currentNode);
-                    levelMap.Add(currentNode.level, sameLevelNodes);
-                }
-
-                // draw line from current node to all its children
-                if (currentNode.children != null)
-                {
-                    foreach (TreeNode childNode in currentNode.children)
-                    {
-                        toDoNodes.Add(childNode);
-                        // declare node
-
-                        string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, childNode.actionInfo.Value);
-                        dotFile.AppendLine(
-                            string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
-                                childNode.GetHashCode(),
-                                childNode.phrase, childNode.actionInfo.Value, childNode.actionInfo.Tries, hexColor));
-                        // add edge
-                        dotFile.AppendLine(string.Format("{0} -> {1}", currentNode.GetHashCode(),
-                            childNode.GetHashCode()));
-                    }
-                }
-            }
-
-            // set same level ranks..
-            foreach (KeyValuePair<int, List<TreeNode>> entry in levelMap)
-            {
-                dotFile.Append("{rank = same;");
-                foreach (TreeNode node in entry.Value)
-                {
-                    dotFile.Append(string.Format(" {0};", node.GetHashCode()));
-                }
-                dotFile.AppendLine("}");
-            }
-
-            dotFile.Append(" }");
-            byte[] output = wrapper.GenerateGraph(dotFile.ToString(), Enums.GraphReturnType.Svg);
-            return output;
-        }
-
-        private String HexConverter(Color c)
+            if (GetTreeInfos().TotalNodes < 1000)
+            {
+                IGetStartProcessQuery getStartProcessQuery = new GetStartProcessQuery();
+                IGetProcessStartInfoQuery getProcessStartInfoQuery = new GetProcessStartInfoQuery();
+                IRegisterLayoutPluginCommand registerLayoutPluginCommand =
+                    new RegisterLayoutPluginCommand(getProcessStartInfoQuery, getStartProcessQuery);
+
+                GraphGeneration wrapper = new GraphGeneration(getStartProcessQuery,
+                    getProcessStartInfoQuery,
+                    registerLayoutPluginCommand);
+                wrapper.GraphvizPath = @"../../../Graphviz2.38/bin";
+                StringBuilder dotFile = new StringBuilder("digraph {");
+                dotFile.AppendLine();
+                dotFile.AppendLine("splines=ortho;");
+                dotFile.AppendLine("concentrate=true;");
+                dotFile.AppendLine("ranksep=1.2;");
+
+                List<TreeNode> toDoNodes = new List<TreeNode>();
+                if (rootNode != null)
+                {
+                    toDoNodes.Add(rootNode);
+                    // declare node
+                    string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, rootNode.actionInfo.Value);
+
+                    dotFile.AppendLine(
+                        string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
+                            rootNode.GetHashCode(),
+                            rootNode.phrase, rootNode.actionInfo.Value, rootNode.actionInfo.Tries, hexColor));
+                }
+
+                // to put nodes on the same level in graph
+                Dictionary<int, List<TreeNode>> levelMap = new Dictionary<int, List<TreeNode>>();
+
+                List<TreeNode> sameLevelNodes;
+
+                while (toDoNodes.Any())
+                {
+                    TreeNode currentNode = toDoNodes[0];
+                    toDoNodes.RemoveAt(0);
+                    // put currentNode into levelMap
+                    if (levelMap.TryGetValue(currentNode.level, out sameLevelNodes))
+                    {
+                        sameLevelNodes.Add(currentNode);
+                    }
+                    else
+                    {
+                        sameLevelNodes = new List<TreeNode>();
+                        sameLevelNodes.Add(currentNode);
+                        levelMap.Add(currentNode.level, sameLevelNodes);
+                    }
+
+                    // draw line from current node to all its children
+                    if (currentNode.children != null)
+                    {
+                        foreach (TreeNode childNode in currentNode.children)
+                        {
+                            toDoNodes.Add(childNode);
+                            // declare node
+
+                            string hexColor = GetHexNodeColor(Color.White, Color.OrangeRed, childNode.actionInfo.Value);
+                            dotFile.AppendLine(
+                                string.Format("{0} [label=\"{1}\\n{2:0.00}/{3}\", style=filled, fillcolor=\"{4}\"]",
+                                    childNode.GetHashCode(),
+                                    childNode.phrase, childNode.actionInfo.Value, childNode.actionInfo.Tries, hexColor));
+                            // add edge
+                            dotFile.AppendLine(string.Format("{0} -> {1}", currentNode.GetHashCode(),
+                                childNode.GetHashCode()));
+                        }
+                    }
+                }
+
+                // set same level ranks..
+                foreach (KeyValuePair<int, List<TreeNode>> entry in levelMap)
+                {
+                    dotFile.Append("{rank = same;");
+                    foreach (TreeNode node in entry.Value)
+                    {
+                        dotFile.Append(string.Format(" {0};", node.GetHashCode()));
+                    }
+                    dotFile.AppendLine("}");
+                }
+
+                dotFile.Append(" }");
+                byte[] output = wrapper.GenerateGraph(dotFile.ToString(), Enums.GraphReturnType.Svg);
+                return output;
+            }
+            return null;
+        }
+
+        protected String HexConverter(Color c)
         {
             return "#" + c.R.ToString("X2") + c.G.ToString("X2") + c.B.ToString("X2");
         }
 
-        private String GetHexNodeColor(Color weakColor, Color strongColor, double quality)
+        protected String GetHexNodeColor(Color weakColor, Color strongColor, double quality)
         {
             // convert quality to value between 0 and 1

@@ -3 +3 @@
 TestResults
 _ReSharper.GrammaticalOptimization
+EvaluationResults