Changeset 10436

Timestamp:

02/04/14 19:12:37 (11 years ago)

Author:

gkronber

Message:

#2026 implemented softmax strategy for tree exploration

File:

• branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs (modified) (1 diff)

branches/HeuristicLab.Problems.GPDL/CodeGenerator/MonteCarloTreeSearchCodeGen.cs

@@ -138 +138 @@
         //}
         // select the alternative with the largest average
-        altIdx = -1;
-        double best = double.NegativeInfinity;
-        for(int idx = 0; idx < searchTree.children.Length; idx++) {
-          if(searchTree.children[idx] == null) continue;
-          if (!searchTree.children[idx].done && Grammar.minDepth[Grammar.transition[state][idx]] <= maxDepth  && UCB(searchTree, searchTree.children[idx]) > best) {
-            altIdx = idx;
-            best = UCB(searchTree, searchTree.children[idx]);
-          }
-        }
+        // altIdx = -1;
+        // double best = double.NegativeInfinity;
+        // for(int idx = 0; idx < searchTree.children.Length; idx++) {
+        //   if(searchTree.children[idx] == null) continue;
+        //   if (!searchTree.children[idx].done && Grammar.minDepth[Grammar.transition[state][idx]] <= maxDepth  && UCB(searchTree, searchTree.children[idx]) > best) {
+        //     altIdx = idx;
+        //     best = UCB(searchTree, searchTree.children[idx]);
+        //   }
+        // }
+        // Softmax selection
+        double temperature = 1;
+        var ms = searchTree.children.Select((c,i) => c == null || c.done || Grammar.minDepth[Grammar.transition[state][i]] > maxDepth ? 0.0 : Math.Exp((c.sumQuality / c.tries) / temperature)).ToArray();
+        var msSum = ms.Sum();
+        if(msSum == 0.0) {
+          // uniform distribution
+          ms = searchTree.children.Select((c,i) => c == null || c.done || Grammar.minDepth[Grammar.transition[state][i]] > maxDepth ? 0.0 : 1.0).ToArray();  
+          msSum = ms.Sum();
+        }
+        Debug.Assert(msSum > 0.0);
+        var r = random.NextDouble() * msSum;
+         
+        altIdx = 0;
+        var aggSum = 0.0;
+        while(altIdx < searchTree.children.Length && aggSum <= r) {
+          var c = searchTree.children[altIdx];
+          aggSum += ms[altIdx++];
+        }
+        altIdx--;
         Debug.Assert(altIdx > -1);
         return altIdx;
       }
     }
-
+ 
     public static double UCB(SearchTreeNode parent, SearchTreeNode n) {
       Debug.Assert(parent.tries >= n.tries);