Changeset 12893 for branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization

Timestamp:

08/24/15 13:56:27 (9 years ago)

Author:

gkronber

Message:

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization

Files:

• HeuristicLab.Algorithms.GrammaticalOptimization.csproj (modified) (2 diffs)
• ISequentialDecisionPolicy.cs (modified) (1 diff)
• SentenceBandit.cs (added)
• SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs (modified) (5 diffs)
• SequentialDecisionPolicies/GenericGrammarPolicy.cs (modified) (7 diffs)
• SequentialDecisionPolicies/GenericPolicy.cs (modified) (5 diffs)
• SequentialDecisionPolicies/GrammarPolicy.cs (modified) (1 diff)
• SequentialDecisionPolicies/RandomPolicy.cs (modified) (1 diff)
• Solvers/ExhaustiveRandomFirstSearch.cs (modified) (1 diff)
• Solvers/RandomSearch.cs (modified) (1 diff)
• Solvers/SequentialSearch.cs (modified) (9 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj

@@ -32 +32 @@
     <WarningLevel>4</WarningLevel>
     <Prefer32Bit>false</Prefer32Bit>
+    <UseVSHostingProcess>true</UseVSHostingProcess>
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="HeuristicLab.Algorithms.DataAnalysis-3.4">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Algorithms.DataAnalysis-3.4.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Core-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Core-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Data-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Data-3.3.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4">
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis-3.4.dll</HintPath>
+    </Reference>
+    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="SentenceBandit.cs" />
     <Compile Include="ISequentialDecisionPolicy.cs" />
     <Compile Include="SequentialDecisionPolicies\GenericPolicy.cs" />
@@ -60 +84 @@
     </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Common\HeuristicLab.Common.csproj">
-      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Project>{3a2fbbcb-f9df-4970-87f3-f13337d941ad}</Project>
       <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Problems.Bandits\HeuristicLab.Problems.Bandits.csproj">
+      <Project>{E8138227-0C64-4E85-B676-21D3B97F254F}</Project>
+      <Name>HeuristicLab.Problems.Bandits</Name>
     </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/ISequentialDecisionPolicy.cs

@@ -12 +12 @@
   // we also assume that the policy can fail to select one of the followStates
   public interface ISequentialDecisionPolicy<in TState> {
-    bool TrySelect(Random random, TState curState, IEnumerable<TState> afterStates, out int selectedStateIdx); // selectedState \in afterStates
+    bool TrySelect(System.Random random, TState curState, IEnumerable<TState> afterStates, out int selectedStateIdx); // selectedState \in afterStates
 
     // state-trajectory are the states of the episode, at the end we recieved the reward (only for the terminal state)

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericFunctionApproximationGrammarPolicy.cs

@@ -32 +32 @@
     private int[] actionIndexMap; // don't allocate each time
 
-    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+    public bool TrySelect(System.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 => Done(s))) {
@@ -60 +60 @@
         originalIdx++;
       }
-      
-      
+
+
       // TODO: policy should be a parameter of the function approximation policy
       if (random.NextDouble() < 0.2) {
@@ -74 +74 @@
             bestIdxs.Add(i);
             bestQ = activeAfterStates[i];
-          } else if (activeAfterStates[i].IsAlmost(bestQ)) {
+          } else if (HeuristicLab.Common.Extensions.IsAlmost(activeAfterStates[i], bestQ)) {
             bestIdxs.Add(i);
           }
@@ -80 +80 @@
         selectedStateIdx = actionIndexMap[bestIdxs[random.Next(bestIdxs.Count)]];
       }
-      
+
       return true;
     }
@@ -133 +133 @@
         //double alpha = 1.0 / GetFeatureTries(feature.Id);
         //alpha = Math.Max(alpha, 0.001);
-        
+
         // simple setting of constant alpha = 0.01 works very well for poly-10 (100% success rate for 20 runs within 40000 evaluations))
         var alpha = 0.01;

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericGrammarPolicy.cs

@@ -4 +4 @@
 using System.Linq;
 using System.Text;
+using System.Text.RegularExpressions;
 using System.Threading.Tasks;
+using HeuristicLab.Algorithms.Bandits.BanditPolicies;
+using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Common;
+using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Problems.GrammaticalOptimization;
 
@@ -18 +22 @@
     private readonly IProblem problem;
     private readonly IBanditPolicy banditPolicy;
+    public double[] OptimalPulls { get; private set; }
 
     public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalPhrases = false) {
@@ -30 +35 @@
     private int[] actionIndexMap; // don't allocate each time
 
-    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+    public bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+      //// only for debugging
+      //if (done.Count == 30000) {
+      //  foreach (var pair in stateInfo) {
+      //    var state = pair.Key;
+      //    var info = (DefaultPolicyActionInfo)pair.Value;
+      //    if (info.Tries > 0) {
+      //      Console.WriteLine("{0};{1};{2};{3};{4};{5}", state, info.Tries, info.Value, info.MaxReward,
+      //        optimalSolutions.Contains(problem.CanonicalRepresentation(state)) ? 1 : 0,
+      //        string.Join(";", GenerateFeaturesPoly10(state)));
+      //    }
+      //  }
+      //  System.Environment.Exit(1);
+      //}
+
       // fail if all states are done (corresponding state infos are disabled)
       if (afterStates.All(s => Done(s))) {
@@ -55 +74 @@
       }
 
-      selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
-
+      //// select terminals first
+      //var terminalAfterstates = afterStates.Select((s, i) => new { s, i }).FirstOrDefault(t => !Done(t.s) && problem.Grammar.IsTerminal(t.s));
+      //if (terminalAfterstates != null) {
+      //  selectedStateIdx = terminalAfterstates.i;
+      //  return true;
+      //}
+
+      if (valueApproximation == null) {
+        // no approximation yet? --> use bandit
+        selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+      } else if (afterStates.Any(s => problem.Grammar.IsTerminal(s) && !Done(s))) {
+        selectedStateIdx = SelectionMaxValueTerminalAction(random, afterStates);
+      } else {
+        // only internal states? --> use bandit
+        selectedStateIdx = actionIndexMap[banditPolicy.SelectAction(random, activeAfterStates.Take(idx))];
+      }
       return true;
     }
 
+    private int SelectionMaxValueTerminalAction(System.Random random, IEnumerable<string> afterStates) {
+      int idx = 0;
+      var terminalStates = new List<string>();
+      var originalIdx = new List<int>();
+      foreach (var state in afterStates) {
+        if (problem.Grammar.IsTerminal(state) && !Done(state)) {
+          terminalStates.Add(state);
+          originalIdx.Add(idx);
+        }
+        idx++;
+      }
+
+      return originalIdx[SelectionMaxValueAction(random, terminalStates)];
+    }
+
+    private IRegressionSolution valueApproximation;
+    private int SelectionMaxValueAction(System.Random random, IEnumerable<string> afterStates) {
+
+      // eps greedy
+      //if (random.NextDouble() < 0.1) return Enumerable.Range(0, afterStates.Count()).SelectRandom(random);
+
+      Dataset ds;
+      string[] variablesNames;
+      CreateDataset(afterStates, afterStates.Select<string, IBanditPolicyActionInfo>(_ => null), out ds, out variablesNames);
+
+      var v = valueApproximation.Model.GetEstimatedValues(ds, Enumerable.Range(0, ds.Rows)).ToArray();
+
+      //boltzmann exploration
+      //double beta = 100;
+      //var w = v.Select(vi => Math.Exp(beta * vi));
+      //
+      //return Enumerable.Range(0, v.Length).SampleProportional(random, w);
+
+      return Enumerable.Range(0, v.Length).MaxItems(i => v[i]).SelectRandom(random);
+    }
+
+    private void UpdateValueApproximation() {
+      Dataset ds;
+      string[] variableNames;
+      CreateDataset(stateInfo.Keys, stateInfo.Values, out ds, out variableNames);
+      var problemData = new RegressionProblemData(ds, variableNames.Skip(1), variableNames.First());
+      //problemData.TestPartition.Start = problemData.TestPartition.End; // all data are training data
+      valueApproximation = GradientBoostedTreesAlgorithmStatic.TrainGbm(problemData, new SquaredErrorLoss(), 50, 0.1,
+        0.5, 0.5, 100);
+      Console.WriteLine(valueApproximation.TrainingRSquared);
+      Console.WriteLine(valueApproximation.TestRSquared);
+    }
+
+    private void CreateDataset(IEnumerable<string> states, IEnumerable<IBanditPolicyActionInfo> infos, out Dataset ds, out string[] variableNames) {
+      variableNames = new string[] { "maxValue" }.Concat(GenerateFeaturesPoly10("E").Select((_, i) => "f" + i)).ToArray();
+
+      int rows = infos.Zip(states, (info, state) => new { info, state }).Count(i => i.info == null || (i.info.Tries == 1 && Done(i.state)));
+      int cols = variableNames.Count();
+
+      var variableValues = new double[rows, cols];
+      int n = 0;
+      foreach (var pair in states.Zip(infos, Tuple.Create)) {
+        var state = pair.Item1;
+        var info = (DefaultPolicyActionInfo)pair.Item2;
+        if (info == null || (info.Tries == 1 && Done(state))) {
+          if (info != null) {
+            variableValues[n, 0] = info.MaxReward;
+          }
+          int col = 1;
+          foreach (var f in GenerateFeaturesPoly10(state)) {
+            variableValues[n, col++] = f;
+          }
+          n++;
+        }
+      }
+
+      ds = new Dataset(variableNames, variableValues);
+    }
 
 
@@ -72 +178 @@
     }
 
+    private int rewardUpdatesSinceLastTraining = 0;
+    private HashSet<string> statesWritten = new HashSet<string>();
     public void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
+      rewardUpdatesSinceLastTraining++;
+      if (rewardUpdatesSinceLastTraining == 5000) {
+        rewardUpdatesSinceLastTraining = 0;
+        //// write
+        //foreach (var pair in stateInfo) {
+        //  var state = pair.Key;
+        //  var info = (DefaultPolicyActionInfo)pair.Value;
+        //  if (!statesWritten.Contains(state) && info.Tries > 0) {
+        //    Console.WriteLine("{0};{1};{2};{3};{4}", state, info.Tries, info.Value, info.MaxReward, string.Join(";", GenerateFeaturesPoly10(state)));
+        //    statesWritten.Add(state);
+        //  }
+        //}
+        //
+        //Console.WriteLine();
+        //UpdateValueApproximation();
+      }
+
+      int lvl = 0;
       foreach (var state in stateTrajectory) {
+        double alpha = 0.99;
+        OptimalPulls[lvl] = alpha * OptimalPulls[lvl] + (1 - alpha) * (problem.IsOptimalPhrase(state) ? 1.0 : 0.0);
+        lvl++;
+
         GetStateInfo(state).UpdateReward(reward);
-
+        //reward *= 0.95;
         // only the last state can be terminal
         if (problem.Grammar.IsTerminal(state)) {
@@ -83 +213 @@
     }
 
+    private IEnumerable<double> GenerateFeaturesPoly10(string state) {
+      // yield return problem.IsOptimalPhrase(state) ? 1 : 0;
+      foreach (var f in problem.GetFeatures(state)) yield return f.Value;
+
+      //if (!state.EndsWith("E")) state = state + "+E";
+      //int len = state.Length;
+      //Debug.Assert(state[len - 1] == 'E');
+      //foreach (var sy0 in new char[] { '+', '*' }) {
+      //  foreach (var sy1 in problem.Grammar.TerminalSymbols) {
+      //    foreach (var sy2 in new char[] { '+', '*' }) {
+      //      yield return state.Length > 3 && state[len - 4] == sy0 && state[len - 3] == sy1 && state[len - 2] == sy2 ? 1 : 0;
+      //    }
+      //  }
+      //}
+
+      //yield return state.Length;
+      //foreach (var terminalSy in problem.Grammar.TerminalSymbols) {
+      //  yield return state.Length > 2 && state[0] == terminalSy && state[1] == '+' ? 1 : 0;
+      //  yield return state.Length > 2 && state[0] == terminalSy && state[1] == '*' ? 1 : 0;
+      //}
+      // yield return optimalSolutions.Contains(problem.CanonicalRepresentation(state)) ? 1 : 0;
+      //foreach (var term in optimalTerms) yield return Regex.Matches(problem.CanonicalRepresentation(state), term).Count == 1 ? 1 : 0;
+      //var len = state.Length;
+      //yield return len;
+      //foreach (var t in problem.Grammar.TerminalSymbols) {
+      //  yield return state.Count(ch => ch == t);
+      //}
+      //// pairs
+      //foreach (var u in problem.Grammar.TerminalSymbols) {
+      //  foreach (var v in problem.Grammar.TerminalSymbols) {
+      //    int n = 0;
+      //    for (int i = 0; i < state.Length - 1; i++) {
+      //      if (state[i] == u && state[i + 1] == v) n++;
+      //    }
+      //    yield return n;
+      //  }
+      //}
+    }
+
 
     public void Reset() {
       stateInfo.Clear();
       done.Clear();
+      OptimalPulls = new double[300]; // max sentence length is limited anyway
     }
 
@@ -97 +267 @@
     public double GetValue(string state) {
       var s = CanonicalState(state);
-      if (stateInfo.ContainsKey(s)) return stateInfo[s].Value;
+      if (stateInfo.ContainsKey(s)) return stateInfo[s].MaxReward;
       else return 0.0; // TODO: check alternatives
     }

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GenericPolicy.cs

@@ -28 +28 @@
     private int[] actionIndexMap; // don't allocate each time
 
-    public bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+    public bool TrySelect(System.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 => Done(s))) {
@@ -101 +101 @@
 
 
-    private int SelectBoltzmann(Random random, IEnumerable<double> qs, double beta = 10) {
+    private int SelectBoltzmann(System.Random random, IEnumerable<double> qs, double beta = 10) {
       // select best
 
@@ -122 +122 @@
     }
 
-    private int SelectEpsGreedy(Random random, IEnumerable<double> qs, double eps = 0.2) {
+    private int SelectEpsGreedy(System.Random random, IEnumerable<double> qs, double eps = 0.2) {
       if (random.NextDouble() >= eps) { // eps == 0 should be equivalent to pure exploitation, eps == 1 is pure exploration
         // select best
@@ -136 +136 @@
             bestActions.Add(aIdx);
             bestQ = q;
-          } else if (q.IsAlmost(bestQ)) {
+          } else if (HeuristicLab.Common.Extensions.IsAlmost(q,bestQ)) {
             bestActions.Add(aIdx);
           }
@@ -148 +148 @@
     }
 
-    private int SelectRandom(Random random, IEnumerable<double> qs) {
+    private int SelectRandom(System.Random random, IEnumerable<double> qs) {
       return qs
          .Select((aInfo, idx) => Tuple.Create(aInfo, idx))

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/GrammarPolicy.cs

@@ -24 +24 @@
     }
 
-    public abstract bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx);
+    public abstract bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx);
 
     public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialDecisionPolicies/RandomPolicy.cs

@@ -13 +13 @@
     }
 
-    public override bool TrySelect(Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
+    public override bool TrySelect(System.Random random, string curState, IEnumerable<string> afterStates, out int selectedStateIdx) {
       // never fail => allows re-visits of terminal states
       selectedStateIdx = random.Next(afterStates.Count());

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveRandomFirstSearch.cs

@@ -13 +13 @@
     private readonly System.Collections.Generic.SortedList<double, Sequence> sortedList = new SortedList<double, Sequence>();
     private readonly IProblem problem;
-    private readonly Random random;
+    private readonly System.Random random;
 
-    public ExhaustiveRandomFirstSearch(IProblem problem, Random random, int maxLen) {
+    public ExhaustiveRandomFirstSearch(IProblem problem, System.Random random, int maxLen) {
       this.maxLen = maxLen;
       this.problem = problem;
-      this.random = new Random();
+      this.random = new System.Random();
     }
 

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/RandomSearch.cs

@@ -5 +5 @@
   public class RandomSearch : SolverBase {
     private readonly int maxLen;
-    private readonly Random random;
+    private readonly System.Random random;
     private readonly IProblem problem;
 
-    public RandomSearch(IProblem problem, Random random, int maxLen) {
+    public RandomSearch(IProblem problem, System.Random random, int maxLen) {
       this.maxLen = maxLen;
       this.random = random;

branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/SequentialSearch.cs

@@ -6 +6 @@
 using System.Runtime.InteropServices;
 using System.Text;
+using System.Windows.Markup;
 using HeuristicLab.Algorithms.Bandits;
 using HeuristicLab.Algorithms.Bandits.BanditPolicies;
@@ -40 +41 @@
     private readonly int maxLen;
     private readonly IProblem problem;
-    private readonly Random random;
+    private readonly System.Random random;
     private readonly int randomTries;
     private readonly IGrammarPolicy behaviourPolicy;
@@ -51 +52 @@
     private readonly List<string> stateChain;
 
-    public SequentialSearch(IProblem problem, int maxLen, Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
+    public SequentialSearch(IProblem problem, int maxLen, System.Random random, int randomTries, IGrammarPolicy behaviourPolicy) {
       this.maxLen = maxLen;
       this.problem = problem;
@@ -117 +118 @@
           GenerateFollowStates(n); // creates child nodes for node n
 
+
           int selectedChildIdx;
           if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
             return false;
           }
+
           phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
 
@@ -167 +170 @@
     }
 
+
+
     private void DistributeReward(double reward) {
       behaviourPolicy.UpdateReward(stateChain, reward);
     }
+
 
 
@@ -178 +184 @@
       bestQuality = 0.0;
       tries = 0;
+      //rootNode = new TreeNode("a*b+c*d+e*f+E", new ReadonlySequence("$"));
       rootNode = new TreeNode(problem.Grammar.SentenceSymbol.ToString(), new ReadonlySequence("$"));
     }
@@ -194 +201 @@
 
       var n = rootNode;
-
+      int lvl = 0;
       while (n != null) {
         var phrase = n.phrase;
         Console.ForegroundColor = ConsoleColor.White;
+        
+        if (lvl++ > 10) return;
+
         Console.WriteLine("{0,-30}", phrase);
         var children = n.children;
         if (children == null || !children.Any()) break;
-        var triesEnumerable = children.Select(ch => policy.GetTries(ch.phrase));
-        double maxTries = triesEnumerable.Where(v => !double.IsInfinity(v)).DefaultIfEmpty(1).Max();
-        maxTries = Math.Max(maxTries, 1.0);
+        var valuesEnumerable = children.Select(ch => policy.GetValue(ch.phrase));
+        double maxValue = valuesEnumerable.Where(v => !double.IsInfinity(v)).DefaultIfEmpty(0).Max();
+        maxValue = Math.Max(maxValue, 1.0);
         // write phrases
         foreach (var ch in children) {
-          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          //SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
           Console.Write(" {0,-4}", ch.phrase.Substring(Math.Max(0, ch.phrase.Length - 3), Math.Min(3, ch.phrase.Length)));
         }
@@ -213 +223 @@
         // write values
         foreach (var ch in children) {
-          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          //SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
           if (!double.IsInfinity(policy.GetValue(ch.phrase)))
             Console.Write(" {0:F2}", policy.GetValue(ch.phrase) * 10.0);
@@ -223 +233 @@
         // write tries
         foreach (var ch in children) {
-          SetColorForValue(policy.GetTries(ch.phrase) / maxTries);
+          //SetColorForValue(policy.GetValue(ch.phrase) / maxValue);
           Console.Write(" {0,4}", policy.GetTries(ch.phrase));
         }
         Console.WriteLine();
-        int selectedChildIdx;
-        if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
-          break;
-        }
+        var triesArr = valuesEnumerable.ToArray();
+        //var selectedChildIdx = Array.IndexOf(triesArr, triesArr.Max());
+        var valuesArr = children.Select(ch => policy.GetValue(ch.phrase)).ToArray();
+        int selectedChildIdx = Enumerable.Range(0, children.Length).OrderByDescending(i => valuesArr[i]).ThenByDescending(i => triesArr[i]).First();
+
+        //int selectedChildIdx;
+        //if (!policy.TrySelect(random, phrase, children.Select(ch => ch.phrase), out selectedChildIdx)) {
+        //  break;
+        //}
         n = n.children[selectedChildIdx];
       }