• branch=trunk inherited from [16f0b5784f]
• sym-trunk inherited from [16f0b5784f]

Modified score_memo.txt from [0e695941ab7be6d2] to [574f95bdd01111dd].

    15     15   flood5       561?
    16     16   trampoline1  291    // むずかしい岩崩し
    17     17   trampoline2 1728?
    18     18   trampoline3  698    // "上に岩" ワープゾーン版
    19     19   beard1       856?
    20     20   beard2      2792    // 崩すの怖がりすぎて間に合わなくなって溺死
    21     21   beard3       811    // 無理ゲー：速攻で髭刈らないといけない
    22         -beard4       677    // 岩が落ちてきてデッドエンド
           22  +beard4      1950    // 髭を解放しないように動くゲー
    23     23   beard5       665    // これクリアできるの
    24     24   horock1      333
    25     25   horock2      235
    26     26   horock3     1542

Modified src/solver.d from [3fbaa7115d831a14] to [fc45f9bc575c213e].

   313    313     }
   314    314     return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
   315    315    }
   316    316   }
   317    317   
   318    318   class Solver_2(SubSolver) : Solver
   319    319   {
   320         - static const PredictFuture = 10;
          320  + // Parameters.
          321  + static const   PredictFuture = 10;
          322  + const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps
          323  + const          ReplanLength  = 400; // O(PF*RCP*RL*SubSolver.single_step)
   321    324   
   322    325    Game      current_game;
   323    326    SubSolver sub_solver;
   324    327   
   325    328    enum {Tentative, Tentative_Stuck, Fixed};
   326    329    string plan;
   327    330    int    plan_state;
          331  + int    replan_limit;
   328    332   
   329    333    this(in Game g)
   330    334    {
   331    335     current_game = g.clone();
   332    336     plan         = "";
   333    337     plan_state   = Tentative;
          338  +  replan_limit = PredictFuture;
          339  +  if(g.map.W*g.map.H <= 400)
          340  +   RandomChoicePattern = ["UU","UD","UL","UR",
          341  +                          "DU","DD","DL","DR",
          342  +                          "LU","LD","LL","LR",
          343  +                          "RU","RD","RL","RR","UUU","UUUU","UUUUU"];
          344  +  else if(g.map.W*g.map.H <= 4096)
          345  +   RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"];
          346  +  else
          347  +   RandomChoicePattern = ["U","D","L","R"];
   334    348    }
   335    349   
   336    350    char single_step()
   337    351    {
   338    352     if(current_game.dead || current_game.cleared)
   339    353      return 'A';
   340    354   
   341    355     // Make enough prediction.
   342         -  while( plan_state==Tentative && plan.length<PredictFuture )
          356  +  while( plan_state==Tentative && plan.length<replan_limit )
   343    357      single_step_predict();
   344    358   
   345    359     // If the future is bad, correct.
   346         -  if( plan_state==Tentative_Stuck && plan.length<PredictFuture )
          360  +  if( plan_state==Tentative_Stuck && plan.length<replan_limit )
   347    361      replan();
   348    362   
   349    363     // Follow the predicted plan.
   350    364     if( plan.empty )
   351    365      return 'A';
   352    366   stderr.writeln(plan, " ", plan_state);
   353    367     char c = plan[0];
................................................................................

   391    405    }
   392    406   
   393    407    void replan()
   394    408    {
   395    409   stderr.writeln("replan!");
   396    410     // Try to replace every step of the plan by another move.
   397    411     Game g = current_game.clone();
   398         -  Tuple!(long, SubSolver, string, int) cand =
   399         -   tuple(sub_solver.g.score, sub_solver, plan, Tentative_Stuck);
          412  +  Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck);
          413  +  bool tiebreak_by_turn = false;
   400    414     for(int i=0; i<plan.length; ++i) {
   401         -   foreach(string prefix; ["U","D","L","R","UD","DU","LR","RL"])
          415  +   foreach(string prefix; RandomChoicePattern)
   402    416       if(prefix[0] != plan[i]) {
   403         -     Tuple!(long, SubSolver, string, int) r = try_plan(g, prefix);
   404         -     if(cand[0] < r[0]) {
   405         -      r[2] = plan[0..i] ~ prefix ~ r[2];
   406         -      cand = r;
          417  +     Tuple!(SubSolver, string, int) r = try_plan(g, prefix);
          418  +     r[1] = plan[0..i] ~ prefix ~ r[1];
          419  +     bool better = false, tbt=false;
          420  +     if(!cand[0].g.cleared && r[0].g.cleared)
          421  +      better = true;
          422  +     else if(cand[0].g.cleared && r[0].g.cleared) {
          423  +      better = cand[0].g.score < r[0].g.score;
          424  +     }
          425  +     else if(!cand[0].g.cleared && !r[0].g.cleared) {
          426  +      if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda)
          427  +       better = true;
          428  +      else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) {
          429  +       if(cand[0].g.dead && !r[0].g.dead)
          430  +        better = true;
          431  +       else if(cand[0].g.dead == r[0].g.dead) {
          432  +        better = (cand[1].length < r[1].length);
          433  +        tbt = true;
          434  +       }
          435  +      }
   407    436        }
          437  +     if(better) {
          438  +      cand = r;
          439  +      tiebreak_by_turn = true;
          440  +writeln(cand);
          441  +}
   408    442       }
   409    443      g.command(plan[i]);
   410    444     }
   411    445   
   412         -  sub_solver = cand[1];
   413         -  plan       = cand[2];
   414         -  plan_state = (plan.length < PredictFuture ? Fixed : cand[3]);
          446  +  sub_solver   = cand[0];
          447  +  plan         = cand[1];
          448  +  plan_state   = (plan.length < PredictFuture ? Fixed : cand[2]);
          449  +  replan_limit = tiebreak_by_turn ? min(PredictFuture, plan.length/2) : PredictFuture;
   415    450    }
   416    451   
   417         - Tuple!(long, SubSolver, string, int) try_plan(in Game g, string prefix)
          452  + Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix)
   418    453    {
   419    454     SubSolver s = new SubSolver(g);
   420    455     foreach(char c; prefix)
   421    456      s.force(c);
   422    457     string log;
   423    458     int state = Tentative;
   424         -  while(!s.g.cleared && !s.g.dead && log.length<=g.map.H*g.map.W) {
          459  +  while(!s.g.cleared && !s.g.dead && log.length<=ReplanLength && log.length<=g.map.W*g.map.H) {
   425    460      char c = s.single_step();
   426    461      if( c == 'A' ) {
   427    462       state = Tentative_Stuck;
   428    463       break;
   429    464      }
   430    465      log ~= c;
   431    466     }
   432    467     if(s.g.cleared) state = Fixed;
   433    468     else if(s.g.dead) state = Tentative_Stuck;
   434         -  return tuple(s.g.score, s, log, state);
          469  +  return tuple(s, log, state);
   435    470    }
   436    471   }
   437         -/*
   438         -class MasterSolver : Solver
   439         -{
   440         - this(in Game g)
   441         - {
   442         -  int SIZE = g.map.H * g.map.W;
   443         -  if( SIZE <= 32*32 )
   444         -   sub = new Solver_2!(Solver_1)(g);
   445         -  else if( SIZE <= 100*100 )
   446         -   sub = new Solver_1(g);
   447         -  else
   448         -   sub = new Solver_1(g);
   449         - }
   450    472   
   451         - private Solver sub;
   452         - char single_step() { return sub.single_step(); }
   453         - void force(char c) { sub.force(c); }
   454         -}
   455         -
   456         -alias MasterSolver MainSolver;
   457         -*/
   458    473   alias Solver_2!(Solver_1) MainSolver;
   459    474   //alias Solver_1 MainSolver;
   460    475   //alias Solver_0 MainSolver;