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

Timestamp:

01/02/15 16:08:21 (10 years ago)

Author:

gkronber

Message:

#2283: several major extensions for grammatical optimization

File:

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

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

@@ -10 +10 @@
   public class MctsSampler {
     private class TreeNode {
+      public string ident;
       public int randomTries;
+      public int policyTries;
       public IPolicy policy;
       public TreeNode[] children;
       public bool done = false;
 
+      public TreeNode(string id) {
+        this.ident = id;
+      }
+
       public override string ToString() {
-        return string.Format("Node(random-tries: {0}, done: {1}, policy: {2})", randomTries, done, policy);
+        return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, randomTries + policyTries, done, policy);
       }
     }
+
 
     public event Action<string, double> FoundNewBestSolution;
@@ -27 +34 @@
     private readonly Random random;
     private readonly int randomTries;
-    private readonly Func<int, IPolicy> policyFactory;
+    private readonly Func<Random, int, IPolicy> policyFactory;
 
     private List<Tuple<TreeNode, int>> updateChain;
     private TreeNode rootNode;
 
+    public int treeDepth;
+    public int treeSize;
+
     public MctsSampler(IProblem problem, int maxLen, Random random) :
-      this(problem, maxLen, random, 10, (numActions) => new EpsGreedyPolicy(random, numActions, 0.1)) {
+      this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) {
 
     }
 
-    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<int, IPolicy> policyFactory) {
+    public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<Random, int, IPolicy> policyFactory) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -47 +57 @@
     public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
-      InitPolicies();
+      InitPolicies(problem.Grammar);
       for (int i = 0; !rootNode.done && i < maxIterations; i++) {
-        var sentence = SampleSentence(problem.Grammar);
+        var sentence = SampleSentence(problem.Grammar).ToString();
         var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         Debug.Assert(quality >= 0 && quality <= 1.0);
@@ -61 +71 @@
         }
       }
+
+      // clean up
+      InitPolicies(problem.Grammar); GC.Collect();
     }
 
-    private void InitPolicies() {
-      this.updateChain = new List<Tuple<TreeNode, int>>();
-      rootNode = new TreeNode();
+    public void PrintStats() {
+      var n = rootNode;
+      Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries);
+      while (n.policy != null) {
+        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}", ch.randomTries + ch.policyTries))));
+        //n.policy.PrintStats();
+        n = n.children.OrderByDescending(c => c.policyTries).First();
+      }
+      Console.ReadLine();
     }
 
-    private string SampleSentence(IGrammar grammar) {
-      updateChain.Clear();
-      return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());
+    private void InitPolicies(IGrammar grammar) {
+      this.updateChain = new List<Tuple<TreeNode, int>>();
+
+      rootNode = new TreeNode(grammar.SentenceSymbol.ToString());
+      treeDepth = 0;
+      treeSize = 0;
     }
 
-    public string CompleteSentence(IGrammar g, string phrase) {
+    private Sequence SampleSentence(IGrammar grammar) {
+      updateChain.Clear();
+      var startPhrase = new Sequence(grammar.SentenceSymbol);
+      return CompleteSentence(grammar, startPhrase);
+    }
+
+    private Sequence CompleteSentence(IGrammar g, Sequence phrase) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
       TreeNode n = rootNode;
-      bool done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal;
       int selectedAltIdx = -1;
+      var curDepth = 0;
       while (!done) {
-        int ntIdx; char nt;
-        Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -90 +120 @@
         if (n.randomTries < randomTries) {
           n.randomTries++;
+
+          treeDepth = Math.Max(treeDepth, curDepth);
+
           return g.CompleteSentenceRandomly(random, phrase, maxLen);
         } else if (n.randomTries == randomTries && n.policy == null) {
-          n.policy = policyFactory(alts.Count());
-          n.children = alts.Select(_ => new TreeNode()).ToArray(); // create a new node for each alternative
+          n.policy = policyFactory(random, alts.Count());
+          //n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative
+          n.children = alts.Select(alt => new TreeNode(string.Empty)).ToArray(); // create a new node for each alternative
+
+          treeSize += n.children.Length;
         }
-
+        n.policyTries++;
         // => select using bandit policy
         selectedAltIdx = n.policy.SelectAction();
-        string selectedAlt = alts.ElementAt(selectedAltIdx);
+        Sequence selectedAlt = alts.ElementAt(selectedAltIdx);
+
         // replace nt with alt
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
         updateChain.Add(Tuple.Create(n, selectedAltIdx));
 
-        done = phrase.All(g.IsTerminal); // terminal phrase means we are done
+        curDepth++;
+
+        done = phrase.IsTerminal;
         if (!done) {
           // prepare for next iteration
@@ -116 +154 @@
       n.children[selectedAltIdx].done = true;
 
+      treeDepth = Math.Max(treeDepth, curDepth);
       return phrase;
     }
@@ -127 +166 @@
         var policy = node.policy;
         var action = e.Item2;
+        //policy.UpdateReward(action, reward / updateChain.Count);
         policy.UpdateReward(action, reward);