Changeset 11747 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs

Timestamp:

01/12/15 21:23:01 (10 years ago)

Author:

gkronber

Message:

#2283: implemented test problems for MCTS

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs (modified) (9 diffs)

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

@@ -5 +5 @@
 using System.Text;
 using HeuristicLab.Algorithms.Bandits;
+using HeuristicLab.Common;
 using HeuristicLab.Problems.GrammaticalOptimization;
 
@@ -13 +14 @@
       public int randomTries;
       public IBanditPolicyActionInfo actionInfo;
+      public TreeNode parent;
       public TreeNode[] children;
       public bool done = false;
 
-      public TreeNode(string id) {
+      public TreeNode(string id, TreeNode parent) {
         this.ident = id;
+        this.parent = parent;
       }
 
@@ -35 +38 @@
     private readonly IBanditPolicy policy;
 
-    private List<TreeNode> updateChain;
+    private TreeNode lastNode; // the bottom node in one episode
     private TreeNode rootNode;
 
@@ -75 +78 @@
       Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}, rootQ {3:F3}, bestQ {4:F3}", treeDepth, treeSize, n.actionInfo.Tries, n.actionInfo.Value, bestQuality);
       while (n.children != null) {
+        Console.WriteLine("{0,-30}", n.ident);
+        double maxVForRow = n.children.Select(ch => ch.actionInfo.Value).Max();
+        if (maxVForRow == 0) maxVForRow = 1.0;
+
+        for (int i = 0; i < n.children.Length; i++) {
+          var ch = n.children[i];
+          SetColorForChild(ch, maxVForRow);
+          Console.Write("{0,5}", ch.ident);
+        }
         Console.WriteLine();
-        Console.WriteLine("{0,5}->{1,-50}", n.ident, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.ident))));
-        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4:F2}", ch.actionInfo.Value * 10))));
-        Console.WriteLine("{0,5}  {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.done ? "X" : ch.actionInfo.Tries.ToString()))));
+        for (int i = 0; i < n.children.Length; i++) {
+          var ch = n.children[i];
+          SetColorForChild(ch, maxVForRow);
+          Console.Write("{0,5:F2}", ch.actionInfo.Value * 10);
+        }
+        Console.WriteLine();
+        for (int i = 0; i < n.children.Length; i++) {
+          var ch = n.children[i];
+          SetColorForChild(ch, maxVForRow);
+          Console.Write("{0,5}", ch.done ? "X" : ch.actionInfo.Tries.ToString());
+        }
+        Console.ForegroundColor = ConsoleColor.White;
+        Console.WriteLine();
         //n.policy.PrintStats();
-        n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First();
-      }
+        //n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First();
+        n = n.children.Where(ch=>!ch.done).OrderByDescending(c => c.actionInfo.Value).First();
+      }
+      Console.WriteLine("-----------------------");
+    }
+
+    private void SetColorForChild(TreeNode ch, double maxVForRow) {
+      //if (ch.done) Console.ForegroundColor = ConsoleColor.White;
+      //else
+      Console.ForegroundColor = ConsoleEx.ColorForValue(ch.actionInfo.Value / maxVForRow);
     }
 
     private void InitPolicies(IGrammar grammar) {
-      this.updateChain = new List<TreeNode>();
-
-      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
+
+
+      rootNode = new TreeNode(grammar.SentenceSymbol.ToString(), null);
       rootNode.actionInfo = policy.CreateActionInfo();
       treeDepth = 0;
@@ -94 +124 @@
 
     private Sequence SampleSentence(IGrammar grammar) {
-      updateChain.Clear();
+      lastNode = null;
       var startPhrase = new Sequence(grammar.SentenceSymbol);
+      //var startPhrase = new Sequence("a*b+c*d+e*f+E");
+
       return CompleteSentence(grammar, startPhrase);
     }
@@ -105 +137 @@
       var curDepth = 0;
       while (!phrase.IsTerminal) {
-        updateChain.Add(n);
 
         if (n.randomTries < randomTries) {
           n.randomTries++;
           treeDepth = Math.Max(treeDepth, curDepth);
+          lastNode = n;
           return g.CompleteSentenceRandomly(random, phrase, maxLen);
         } else {
@@ -120 +152 @@
 
           if (n.randomTries == randomTries && n.children == null) {
-            n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
+            n.children = alts.Select(alt => new TreeNode(alt.ToString(), n)).ToArray(); // create a new node for each alternative
             foreach (var ch in n.children) ch.actionInfo = policy.CreateActionInfo();
             treeSize += n.children.Length;
@@ -138 +170 @@
       } // while
 
-      updateChain.Add(n);
+      lastNode = n;
 
 
@@ -150 +182 @@
     private void DistributeReward(double reward) {
       // iterate in reverse order (bottom up)
-      updateChain.Reverse();
-
-      foreach (var e in updateChain) {
-        var node = e;
-        if (node.done) node.actionInfo.Disable();
+
+      var node = lastNode;
+      while (node != null) {
+        if (node.done) node.actionInfo.Disable(reward);
         if (node.children != null && node.children.All(c => c.done)) {
           node.done = true;
-          node.actionInfo.Disable();
+          var bestActionValue = node.children.Select(c => c.actionInfo.Value).Max();
+          node.actionInfo.Disable(bestActionValue);
         }
         if (!node.done) {
           node.actionInfo.UpdateReward(reward);
         }
+        node = node.parent;
       }
     }