source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs @ 11770

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using HeuristicLab.Common;
using HeuristicLab.Problems.GrammaticalOptimization;

namespace HeuristicLab.Algorithms.Bandits.GrammarPolicies {
  // this represents grammar policies that use one of the available bandit policies for state selection
  public class GenericGrammarPolicy : IGrammarPolicy {
    protected Dictionary<string, IBanditPolicyActionInfo> stateInfo; // stores the necessary information for bandit policies for each state 
    private readonly bool useCanonicalState;
    private readonly IProblem problem;
    private readonly IBanditPolicy banditPolicy;
    private readonly HashSet<string> done;

    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
      this.useCanonicalState = useCanonicalState;
      this.problem = problem;
      this.banditPolicy = banditPolicy;
      this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
      this.done = new HashSet<string>();
    }

    public bool TrySelect(Random random, ReadonlySequence curState, IEnumerable<ReadonlySequence> afterStates,
      out ReadonlySequence selectedState) {
      // only select states that are not yet done
      afterStates = afterStates.Where(a => !done.Contains(CanonicalState(a.ToString()))).ToArray();
      if (!afterStates.Any()) {
        // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
        throw new NotImplementedException();
        //var curStateCanonical = CanonicalState(curState.ToString());
        //if (curState.ToString().Length == curStateCanonical.Length)
          done.Add(CanonicalState(curState.ToString()));
        selectedState = null;
        return false;
      }


      var selectedIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));
      selectedState = afterStates.ElementAt(selectedIdx);
      return true;
    }

    private IBanditPolicyActionInfo GetStateInfo(ReadonlySequence state) {
      var s = CanonicalState(state.ToString());
      IBanditPolicyActionInfo info;
      if (!stateInfo.TryGetValue(s, out info)) {
        info = banditPolicy.CreateActionInfo();
        stateInfo[s] = info;
      }
      return info;
    }

    public virtual void UpdateReward(IEnumerable<ReadonlySequence> stateTrajectory, double reward) {
      // the last state could be terminal
      var lastState = stateTrajectory.Last();
      if (lastState.IsTerminal) done.Add(CanonicalState(lastState.ToString()));

      foreach (var state in stateTrajectory) {
        GetStateInfo(state).UpdateReward(reward);
      }
    }

    public virtual void Reset() {
      stateInfo.Clear();
      done.Clear();
    }

    public int GetTries(ReadonlySequence state) {
      var s = CanonicalState(state.ToString());
      if (stateInfo.ContainsKey(s)) return stateInfo[s].Tries;
      else return 0;
    }

    public double GetValue(ReadonlySequence state) {
      var s = CanonicalState(state.ToString());
      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
      else return 0.0; // TODO: check alternatives
    }

    protected string CanonicalState(string state) {
      if (useCanonicalState) return problem.CanonicalRepresentation(state);
      else return state;
    }
  }
}