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

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, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
      // fail if all states are done (corresponding state infos are disabled)
      if (afterStates.All(s => GetStateInfo(s).Disabled)) {
        // 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)

        GetStateInfo(curState).Disable(0.0); // should the value be max of afterstate values instead of 0.0?
        selectedStateIdx = -1;
        return false;
      }

      selectedStateIdx = banditPolicy.SelectAction(random, afterStates.Select(s => GetStateInfo(s)));

      return true;
    }

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

    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
      // the last state could be terminal
      var lastState = stateTrajectory.Last();
      if (problem.Grammar.IsTerminal(lastState)) {
        GetStateInfo(lastState).Disable(reward);
      }

      // update remaining states
      foreach (var state in stateTrajectory.Reverse().Skip(1)) {
        GetStateInfo(state).UpdateReward(reward);
      }
    }

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

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

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

    protected string CanonicalState(string state) {
      if (useCanonicalState) {
        if (problem.Grammar.IsTerminal(state))
          return problem.CanonicalRepresentation(state);
        else {
          // for non-terminal phrases make sure we don't disable canonical states that have not yet been fully explored
          // e.g. if for the ant problem we have the phrase lllS (and we are limited to 4 symbols) and lllr as well as llll are explored
          // then we are not allowed to disable rS (canonical of lllS) because rS might not have been fully explored
          // solution: we disable the state rS4 
          return problem.CanonicalRepresentation(state) + state.Length;
        }
      } else
        return state;
    }
  }
}