Changeset 10437 for branches

Timestamp:

02/04/14 19:28:29 (11 years ago)

Author:

gkronber

Message:

#2026 implemented epsilon-greedy search policy

File:

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

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

@@ -148 +148 @@
         // }
         // 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--;
+        // 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--;
+
+        // epsilon-greedy selection
+        double eps = 0.1;
+        if(random.NextDouble() >= eps) {
+          // select best
+          altIdx = 0; while(searchTree.children[altIdx]==null) altIdx++;
+          for(int idx=0;idx<searchTree.children.Length;idx++) {
+            var c = searchTree.children[idx];
+            if(c==null || c.done || Grammar.minDepth[Grammar.transition[state][idx]] > maxDepth) continue;
+            if(searchTree.children[idx].bestQuality > searchTree.children[altIdx].bestQuality) {
+              altIdx = idx;
+            }
+          }
+        } else {
+          // select random
+          var allowedIndexes = (searchTree.children
+                         .Select((e,i) => new {Elem = e, Idx = i})
+                         .Where(p => p.Elem != null && !p.Elem.done && Grammar.minDepth[Grammar.transition[state][p.Idx]] <= maxDepth)
+                         .Select(p => p.Idx)).ToArray();
+          altIdx = allowedIndexes[random.Next(allowedIndexes.Length)];
+        }
         Debug.Assert(altIdx > -1);
         return altIdx;