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

Modified src/solver.d from [707b7344a0841f62] to [4176698dd9ba368b].

   142    142       }
   143    143     }
   144    144   
   145    145     if(c == 'W')
   146    146      wait_count++;
   147    147     else
   148    148      wait_count = 0;
          149  +  if(wait_count==2)
          150  +   c = 'A';
   149    151     if(choke_count >= g.map.H)
   150    152      c = 'A';
   151    153   
   152    154     bool[char] choice;
   153    155     foreach(t; cand)
   154    156      choice[t[0]] = true;
   155    157     log ~= tuple(ro.clone(), cast(int)choice.length);
................................................................................

   311    313     }
   312    314     return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
   313    315    }
   314    316   }
   315    317   
   316    318   class Solver_2(SubSolver) : Solver
   317    319   {
          320  + static const PredictFuture = 10;
          321  +
          322  + Game      current_game;
          323  + SubSolver sub_solver;
          324  +
          325  + enum {Tentative, Tentative_Stuck, Fixed};
   318    326    string plan;
   319         - bool plan_broken = true;
          327  + int    plan_state;
   320    328   
   321         - Game g;
   322    329    this(in Game g)
   323    330    {
   324         -  this.g = g.clone();
   325         -  make_plan(g);
          331  +  current_game = g.clone();
          332  +  plan         = "";
          333  +  plan_state   = Tentative;
          334  + }
          335  +
          336  + char single_step()
          337  + {
          338  +  if(current_game.dead || current_game.cleared)
          339  +   return 'A';
          340  +
          341  +  // Make enough prediction.
          342  +  while( plan_state==Tentative && plan.length<PredictFuture )
          343  +   single_step_predict();
          344  +
          345  +  // If the future is bad, correct.
          346  +  if( plan_state==Tentative_Stuck && plan.length<PredictFuture )
          347  +   replan();
          348  +
          349  +  // Follow the predicted plan.
          350  +  if( plan.empty )
          351  +   return 'A';
          352  +writeln(plan, " ", plan_state);
          353  +  char c = plan[0];
          354  +  plan = plan[1..$];
          355  +  current_game.command(c);
          356  +  return c;
   326    357    }
   327    358   
   328         - Tuple!(SubSolver,string) run_sub_solver(in Game g)
          359  + void force(char c)
   329    360    {
   330         -  string log;
   331         -  auto s = new SubSolver(g);
   332         -  while(!g.cleared && !g.dead && plan.length<=g.map.H*g.map.W) {
   333         -   char c = s.single_step();
   334         -   if( c == 'A' )
   335         -    break;
   336         -   log ~= c;
          361  +  if(plan.length>0 && plan[0]==c)
          362  +  {
          363  +   // If matching the plan, just go forward.
          364  +   plan = plan[1..$];
          365  +  }
          366  +  else
          367  +  {
          368  +   // Discard the plan, otherwise.
          369  +   plan_state = Tentative;
          370  +   plan       = "";
          371  +   sub_solver = null;
   337    372     }
   338         -  while(log.length>0 && log[$-1]=='W')
   339         -   log.length--;
   340         -  return tuple(s, log);
          373  +  current_game.command(c);
   341    374    }
   342    375   
   343         - void make_plan(in Game g) {
   344         -  plan_broken = false;
   345         -  Tuple!(SubSolver,string) x = run_sub_solver(g);
   346         -  plan = x[1];
   347         -  if(x[0].g.cleared)
   348         -   return;
   349         -  modify_plan(g, x[0].g.score);
          376  + void single_step_predict()
          377  + {
          378  +  if(sub_solver is null) {
          379  +   sub_solver = new SubSolver(current_game);
          380  +   plan       = "";
          381  +  }
          382  +
          383  +  char c = sub_solver.single_step();
          384  +  if(c == 'A')
          385  +   plan_state = Tentative_Stuck;
          386  +  else {
          387  +   plan ~= c;
          388  +   plan_state = (sub_solver.g.dead ? Tentative_Stuck :
          389  +                 sub_solver.g.cleared ? Fixed : Tentative);
          390  +  }
   350    391    }
   351    392   
   352         - void modify_plan(in Game ini, long unmod)
          393  + void replan()
   353    394    {
   354         -  int bp = max(0, (cast(int)plan.length)-10);
   355         -  Game g = ini.clone();
   356         -  for(int i=0; i<bp; ++i) g.command(plan[i]);
   357         -
   358         -  Tuple!(string,long) cand = tuple(plan, unmod);
   359         -  for(int i=bp; i<plan.length; ++i) {
   360         -   foreach(string c; ["U","D","L","R","UD","DU","LR","RL"])
   361         -    if(c[0] != plan[i]) {
   362         -     Tuple!(string,long) zz = try_plan(c, g);
   363         -     if(cand[1]<zz[1])
   364         -      cand = tuple(plan[0..i]~c~zz[0], zz[1]);
          395  +writeln("replan!");
          396  +  // Try to replace every step of the plan by another move.
          397  +  Game g = current_game.clone();
          398  +  Tuple!(long, SubSolver, string, int) cand =
          399  +   tuple(sub_solver.g.score, sub_solver, plan, Tentative_Stuck);
          400  +  for(int i=0; i<plan.length; ++i) {
          401  +   foreach(string prefix; ["U","D","L","R","UD","DU","LR","RL"])
          402  +    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;
          407  +     }
   365    408       }
   366    409      g.command(plan[i]);
   367    410     }
   368         -  plan = cand[0];
   369         - }
   370    411   
   371         - Tuple!(string,long) try_plan(string c, in Game g)
   372         - {
   373         -  Game gg = g.clone();
   374         -  foreach(cc;c)gg.command(cc);
   375         -  Tuple!(SubSolver, string) x = run_sub_solver(gg);
   376         -  return tuple(x[1], x[0].g.score);
          412  +  sub_solver = cand[1];
          413  +  plan       = cand[2];
          414  +  plan_state = (plan.length < PredictFuture ? Fixed : cand[3]);
   377    415    }
   378    416   
   379         - char single_step() {
   380         -  if(plan_broken)
   381         -   make_plan(g);
   382         -  if(plan.empty)
   383         -   return 'A';
   384         -  char c = plan[0];
   385         -  plan = plan[1..$];
   386         -  g.command(c);
   387         -  return c;
   388         - }
   389         -
   390         - void force(char c) {
   391         -  g.command(c);
   392         -  if(plan.length==0 || plan[0]!=c) {
   393         -   plan = "";
   394         -   plan_broken = true;
          417  + Tuple!(long, SubSolver, string, int) try_plan(in Game g, string prefix)
          418  + {
          419  +  SubSolver s = new SubSolver(g);
          420  +  foreach(char c; prefix)
          421  +   s.force(c);
          422  +  string log;
          423  +  int state = Tentative;
          424  +  while(!s.g.cleared && !s.g.dead && log.length<=g.map.H*g.map.W) {
          425  +   char c = s.single_step();
          426  +   if( c == 'A' ) {
          427  +    state = Tentative_Stuck;
          428  +    break;
          429  +   }
          430  +   log ~= c;
   395    431     }
   396         -  else
   397         -   plan = plan[1..$];
          432  +  if(s.g.cleared) state = Fixed;
          433  +  else if(s.g.dead) state = Tentative_Stuck;
          434  +  return tuple(s.g.score, s, log, state);
   398    435    }
   399    436   }
   400    437   
   401    438   class MasterSolver : Solver
   402    439   {
   403    440    this(in Game g)
   404    441    {
................................................................................

   412    449    }
   413    450   
   414    451    private Solver sub;
   415    452    char single_step() { return sub.single_step(); }
   416    453    void force(char c) { sub.force(c); }
   417    454   }
   418    455   
   419         -alias MasterSolver MainSolver;
   420         -//alias Solver_2!(Solver_1) MainSolver;
          456  +//alias MasterSolver MainSolver;
          457  +alias Solver_2!(Solver_1) MainSolver;
   421    458   //alias Solver_1 MainSolver;
   422    459   //alias Solver_0 MainSolver;