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

Timestamp:

07/14/15 20:42:55 (9 years ago)

Author:

aballeit

Message:

#2283 GUI updates, Tree-chart, MCTS Version 2 (prune leaves)

Location:

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

Files:

• Base/TreeInfos.cs (added)
• Base/TreeNode.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MonteCarloTreeSearch.csproj (modified) (3 diffs)
• MonteCarloTreeSearch.cs (modified) (8 diffs)
• Simulation/ISimulation.cs (modified) (1 diff)
• Simulation/RandomSimulation.cs (modified) (2 diffs)

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

@@ -16 +16 @@
         public List<TreeNode> children;
         public IBanditPolicyActionInfo actionInfo;
+        public int level;
 
-        public TreeNode(TreeNode parent, string phrase, IBanditPolicyActionInfo actionInfo)
+        public TreeNode(TreeNode parent, string phrase, IBanditPolicyActionInfo actionInfo, int level)
         {
             this.parent = parent;
             this.phrase = phrase;
             this.actionInfo = actionInfo;
+            this.level = level;
         }
         public bool IsLeaf()

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

@@ -33 +33 @@
     <Reference Include="System" />
     <Reference Include="System.Core" />
+    <Reference Include="System.Drawing" />
     <Reference Include="System.Xml.Linq" />
     <Reference Include="System.Data.DataSetExtensions" />
@@ -40 +41 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="Base\TreeInfos.cs" />
     <Compile Include="Simulation\ISimulation.cs" />
     <Compile Include="MonteCarloTreeSearch.cs" />
@@ -47 +49 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\GraphVizWrapper\GraphVizWrapper.csproj">
+      <Project>{cfec60dc-14e0-47e4-a60e-8919fb5fef5d}</Project>
+      <Name>GraphVizWrapper</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Algorithms.Bandits\HeuristicLab.Algorithms.Bandits.csproj">
       <Project>{24408f7d-ee0f-4886-a08b-ec324d662e47}</Project>

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

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Drawing;
 using System.Linq;
+using System.Net.Mail;
+using System.Text;
+using System.Threading;
+using GraphVizWrapper;
+using GraphVizWrapper.Commands;
+using GraphVizWrapper.Queries;
 using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Algorithms.GrammaticalOptimization;
@@ -20 +27 @@
         private readonly ISimulation simulation;
         private TreeNode rootNode;
-
-        public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy, ISimulation simulationPolicy)
+        private bool isPaused = false;
+        private object pauseLock = new object();
+
+        public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
+            ISimulation simulationPolicy)
         {
             this.problem = problem;
@@ -31 +41 @@
         }
 
-        public bool StopRequested
-        {
-            get;
-            set;
+        public bool StopRequested { get; set; }
+
+        public bool IsPaused
+        {
+            get { return this.isPaused; }
         }
 
@@ -42 +53 @@
             for (int i = 0; !StopRequested && i < maxIterations; i++)
             {
+                lock (pauseLock)
+                {
+                    if (isPaused)
+                    {
+                        Monitor.Wait(pauseLock);
+                    }
+                }
                 TreeNode currentNode = rootNode;
 
@@ -53 +71 @@
                 string phrase = currentNode.phrase;
 
-                if (!grammar.IsTerminal(phrase) && phrase.Length <= maxLen)
-                {
+                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;
+                    }
                     ExpandTreeNode(currentNode);
-
-                    currentNode =
-                        currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())];
+                    if (currentNode.children.Any())
+                    {
+                        currentNode =
+                            currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
+                                ];
+                    }
+                    else
+                    {
+                        // Version 2:
+                        // remove currentNode from tree..
+                        currentNode.parent.children.Remove(currentNode);
+                    }
                 }
                 if (currentNode.phrase.Length <= maxLen)
                 {
-                    double quality = simulation.Simulate(currentNode);
-                    OnSolutionEvaluated(phrase, quality);
+                    string simulatedPhrase;
+                    double quality = simulation.Simulate(currentNode, out simulatedPhrase);
+                    OnSolutionEvaluated(simulatedPhrase, quality);
 
                     Propagate(currentNode, quality);
-                }
-            }
+
+                }
+            }
+        }
+
+        private bool HasNonTerminal(string phrase)
+        {
+            foreach (char symbol in phrase)
+            {
+                if (grammar.IsNonTerminal(symbol))
+                {
+                    return true;
+                }
+            }
+
+            return false;
         }
 
@@ -91 +140 @@
                             if (newSequence.Length <= maxLen)
                             {
-                                TreeNode childNode = new TreeNode(treeNode, newSequence.ToString(), behaviourPolicy.CreateActionInfo());
+                                TreeNode childNode = new TreeNode(treeNode, newSequence.ToString(),
+                                    behaviourPolicy.CreateActionInfo(), treeNode.level + 1);
                                 treeNode.children.Add(childNode);
                             }
@@ -104 +154 @@
             StopRequested = false;
             bestQuality = 0.0;
-            rootNode = new TreeNode(null, grammar.SentenceSymbol.ToString(), behaviourPolicy.CreateActionInfo());
+            rootNode = new TreeNode(null, grammar.SentenceSymbol.ToString(), behaviourPolicy.CreateActionInfo(), 0);
         }
 
@@ -117 +167 @@
         }
 
-        public void PrintStats()
-        {
-            //Console.WriteLine("depth: {0,5} tries: {1,5} best phrase {2,50} bestQ {3:F3}", maxSearchDepth, tries, bestPhrase, bestQuality);
-
-            //// use behaviour strategy to generate the currently prefered sentence
-            //var policy = behaviourPolicy;
-
-            //var n = rootNode;
-
-            //while (n != null)
-            //{
-            //    var phrase = n.phrase;
-            //    Console.ForegroundColor = ConsoleColor.White;
-            //    Console.WriteLine("{0,-30}", phrase);
-            //    var children = n.children;
-            //    if (children == null || !children.Any()) break;
-            //    var values = children.Select(ch => policy.GetValue(ch.phrase));
-            //    var maxValue = values.Max();
-            //    if (maxValue == 0) maxValue = 1.0;
-
-            //    // write phrases
-            //    foreach (var ch in children)
-            //    {
-            //        SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-            //        Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
-            //    }
-            //    Console.WriteLine();
-
-            //    // write values
-            //    foreach (var ch in children)
-            //    {
-            //        SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-            //        Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
-            //    }
-            //    Console.WriteLine();
-
-            //    // write tries
-            //    foreach (var ch in children)
-            //    {
-            //        SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
-            //        Console.Write(" {0,4}", policy.GetTries(ch.phrase));
-            //    }
-            //    Console.WriteLine();
-            //    int selectedChildIdx;
-            //    if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx))
-            //    {
-            //        break;
-            //    }
-            //    n = n.children[selectedChildIdx];
-            //}
-
-            //Console.ForegroundColor = ConsoleColor.White;
-            //Console.WriteLine("-------------------");
-        }
-
-        private void SetColorForValue(double v)
-        {
-            Console.ForegroundColor = ConsoleEx.ColorForValue(v);
+        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>();
+            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++;
+                }
+                else
+                {
+                    if (!HasNonTerminal(currentNode.phrase))
+                    {
+                        leaveNodes++;
+                    }
+                    else
+                    {
+                        unexpandedNodes++;
+                    }
+                }
+            }
+            return new TreeInfos(totalNodes, unexpandedNodes, expandedNodes, leaveNodes, deepestLevel,
+                totalLevel / totalNodes, totalChildren / expandedNodes);
+        }
+
+        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)
+        {
+            return "#" + c.R.ToString("X2") + c.G.ToString("X2") + c.B.ToString("X2");
+        }
+
+        private String GetHexNodeColor(Color weakColor, Color strongColor, double quality)
+        {
+            // convert quality to value between 0 and 1
+            double bestKnownQuality = problem.BestKnownQuality(this.maxLen);
+            double q = quality / bestKnownQuality;
+
+            // calculate difference between colors
+            byte rDiff = (byte)Math.Abs(weakColor.R - strongColor.R);
+            byte bDiff = (byte)Math.Abs(weakColor.B - strongColor.B);
+            byte gDiff = (byte)Math.Abs(weakColor.G - strongColor.G);
+
+            byte newR = weakColor.R > strongColor.R
+                ? Convert.ToByte(weakColor.R - Math.Round(rDiff * q))
+                : Convert.ToByte(weakColor.R + Math.Round(rDiff * q));
+
+            byte newB = weakColor.B > strongColor.B
+                ? Convert.ToByte(weakColor.B - Math.Round(bDiff * q))
+                : Convert.ToByte(weakColor.B + Math.Round(bDiff * q));
+
+            byte newG = weakColor.G > strongColor.G
+                ? Convert.ToByte(weakColor.G - Math.Round(gDiff * q))
+                : Convert.ToByte(weakColor.G + Math.Round(gDiff * q));
+
+            return HexConverter(Color.FromArgb(newR, newG, newB));
+        }
+
+        public void PauseContinue()
+        {
+            lock (pauseLock)
+            {
+                if (isPaused)
+                {
+                    isPaused = false;
+                    Monitor.Pulse(pauseLock);
+                }
+                else
+                {
+                    isPaused = true;
+                }
+            }
         }
     }

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

@@ -10 +10 @@
     public interface ISimulation
     {
-        double Simulate(TreeNode node);
+        double Simulate(TreeNode node, out string simulatedPhrase);
     }
 }

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

@@ -22 +22 @@
         }
 
-        public double Simulate(TreeNode node)
+        public double Simulate(TreeNode node, out string simulatedPhrase)
         {
             Sequence sequence = new Sequence(node.phrase);
@@ -48 +48 @@
                 }
             }
+            simulatedPhrase = sequence.ToString();
             return problem.Evaluate(sequence.ToString());
         }