using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using HeuristicLab.Algorithms.Bandits; using HeuristicLab.Problems.GrammaticalOptimization; namespace HeuristicLab.Algorithms.GrammaticalOptimization { public class MctsSampler { private class TreeNode { public string ident; public int randomTries; public IBanditPolicyActionInfo actionInfo; public TreeNode[] children; public bool done = false; public TreeNode(string id) { this.ident = id; } public override string ToString() { return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, actionInfo.Tries, done, actionInfo); } } public event Action FoundNewBestSolution; public event Action SolutionEvaluated; private readonly int maxLen; private readonly IProblem problem; private readonly Random random; private readonly int randomTries; private readonly IBanditPolicy policy; private List updateChain; private TreeNode rootNode; public int treeDepth; public int treeSize; // public MctsSampler(IProblem problem, int maxLen, Random random) : // this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) { // // } public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, IBanditPolicy policy) { this.maxLen = maxLen; this.problem = problem; this.random = random; this.randomTries = randomTries; this.policy = policy; } public void Run(int maxIterations) { double bestQuality = double.MinValue; InitPolicies(problem.Grammar); for (int i = 0; !rootNode.done && i < maxIterations; i++) { var sentence = SampleSentence(problem.Grammar).ToString(); var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen); Debug.Assert(quality >= 0 && quality <= 1.0); DistributeReward(quality); RaiseSolutionEvaluated(sentence, quality); if (quality > bestQuality) { bestQuality = quality; RaiseFoundNewBestSolution(sentence, quality); } } // clean up InitPolicies(problem.Grammar); GC.Collect(); } public void PrintStats() { var n = rootNode; Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, n.actionInfo.Tries); while (n.children != 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: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())))); //n.policy.PrintStats(); n = n.children.Where(ch => !ch.done).OrderByDescending(c => c.actionInfo.Value).First(); } Console.ReadLine(); } private void InitPolicies(IGrammar grammar) { this.updateChain = new List(); rootNode = new TreeNode(grammar.SentenceSymbol.ToString()); rootNode.actionInfo = policy.CreateActionInfo(); treeDepth = 0; treeSize = 0; } 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; var curDepth = 0; while (!phrase.IsTerminal) { updateChain.Add(n); if (n.randomTries < randomTries) { n.randomTries++; treeDepth = Math.Max(treeDepth, curDepth); return g.CompleteSentenceRandomly(random, phrase, maxLen); } else { 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 Debug.Assert(maxLenOfReplacement > 0); var alts = g.GetAlternatives(nt).Where(alt => g.MinPhraseLength(alt) <= maxLenOfReplacement); if (n.randomTries == randomTries && n.children == null) { n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative foreach (var ch in n.children) ch.actionInfo = policy.CreateActionInfo(); treeSize += n.children.Length; } // => select using bandit policy int selectedAltIdx = policy.SelectAction(random, n.children.Select(c => c.actionInfo)); Sequence selectedAlt = alts.ElementAt(selectedAltIdx); // replace nt with alt phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt); curDepth++; // prepare for next iteration n = n.children[selectedAltIdx]; } } // while updateChain.Add(n); // the last node is a leaf node (sentence is done), so we never need to visit this node again n.done = true; treeDepth = Math.Max(treeDepth, curDepth); return phrase; } 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(); if (node.children != null && node.children.All(c => c.done)) { node.done = true; node.actionInfo.Disable(); } if (!node.done) { node.actionInfo.UpdateReward(reward); } } } private void RaiseSolutionEvaluated(string sentence, double quality) { var handler = SolutionEvaluated; if (handler != null) handler(sentence, quality); } private void RaiseFoundNewBestSolution(string sentence, double quality) { var handler = FoundNewBestSolution; if (handler != null) handler(sentence, quality); } } }