Differences From Artifact [5e89251084030d6c]:
- File
src/solver.d
- 2012-07-16 00:38:53 - part of checkin [ffac82fc99] on branch trunk - Hopefully the correct way to detect deadly-round-trip. (user: kinaba) [annotate]
To Artifact [434706ae08dfc66e]:
- File
src/solver.d
- 2012-07-16 00:54:11 - part of checkin [1c7a01b7f4] on branch trunk - clear improvement. (user: kinaba) [annotate]
314 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC(); 314 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC();
315 } 315 }
316 } 316 }
317 317
318 class Solver_2(SubSolver) : Solver 318 class Solver_2(SubSolver) : Solver
319 { 319 {
320 // Parameters. 320 // Parameters.
321 static const PredictFuture = 10; | 321 int PredictFuture = 10;
322 const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL s 322 const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL s
323 const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step 323 const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step
324 324
325 Game current_game; 325 Game current_game;
326 SubSolver sub_solver; 326 SubSolver sub_solver;
327 327
328 enum {Tentative, Tentative_Stuck, Fixed}; 328 enum {Tentative, Tentative_Stuck, Fixed};
329 string plan; 329 string plan;
330 int plan_state; 330 int plan_state;
331 int replan_limit; 331 int replan_limit;
332 bool lambda_getter; 332 bool lambda_getter;
> 333 int clear_improvement = 3;
333 334
334 this(in Game g) 335 this(in Game g)
335 { 336 {
336 current_game = g.clone(); 337 current_game = g.clone();
337 plan = ""; 338 plan = "";
338 plan_state = Tentative; 339 plan_state = Tentative;
339 replan_limit = PredictFuture; 340 replan_limit = PredictFuture;
................................................................................................................................................................................
342 "DU","DD","DL","DR", 343 "DU","DD","DL","DR",
343 "LU","LD","LL","LR", 344 "LU","LD","LL","LR",
344 "RU","RD","RL","RR","UUU","UUUU", 345 "RU","RD","RL","RR","UUU","UUUU",
345 else if(g.map.W*g.map.H <= 4096) 346 else if(g.map.W*g.map.H <= 4096)
346 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU"," 347 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","
347 else 348 else
348 RandomChoicePattern = ["U","D","L","R"]; 349 RandomChoicePattern = ["U","D","L","R"];
> 350
> 351 if(g.map.W*g.map.H <= 400)
> 352 PredictFuture = 20;
> 353 else
> 354 PredictFuture = 10;
349 } 355 }
350 356
351 char single_step() 357 char single_step()
352 { 358 {
353 if(current_game.dead || current_game.cleared) 359 if(current_game.dead || current_game.cleared)
354 return 'A'; 360 return 'A';
355 361
................................................................................................................................................................................
410 416
411 void replan() 417 void replan()
412 { 418 {
413 stderr.writeln("replan!"); 419 stderr.writeln("replan!");
414 // Try to replace every step of the plan by another move. 420 // Try to replace every step of the plan by another move.
415 Game g = current_game.clone(); 421 Game g = current_game.clone();
416 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te 422 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te
> 423 int insertion_point = plan.length;
417 writeln(cand, " ", cand[0].g.map.collected_lambda); 424 writeln(cand, " ", cand[0].g.map.collected_lambda);
418 bool tiebreak_by_turn = false; 425 bool tiebreak_by_turn = false;
419 for(int i=0; i<plan.length; ++i) { 426 for(int i=0; i<plan.length; ++i) {
420 foreach(string prefix; RandomChoicePattern) 427 foreach(string prefix; RandomChoicePattern)
421 if(prefix[0] != plan[i]) { 428 if(prefix[0] != plan[i]) {
422 Tuple!(SubSolver, string, int) r = try_p 429 Tuple!(SubSolver, string, int) r = try_p
423 r[1] = plan[0..i] ~ prefix ~ r[1]; 430 r[1] = plan[0..i] ~ prefix ~ r[1];
................................................................................................................................................................................
438 tbt = true; 445 tbt = true;
439 } 446 }
440 } 447 }
441 } 448 }
442 if(better) { 449 if(better) {
443 cand = r; 450 cand = r;
444 tiebreak_by_turn = true; 451 tiebreak_by_turn = true;
> 452 insertion_point = i+prefix.lengt
445 writeln(cand, " ", cand[0].g.map.collected_lambda); 453 writeln(cand, " ", cand[0].g.map.collected_lambda);
446 } | 454 }
447 } 455 }
448 g.command(plan[i]); 456 g.command(plan[i]);
449 } 457 }
450 458
> 459 if(cand[2]==Fixed && insertion_point!=plan.length && clear_impro
451 sub_solver = cand[0]; | 460 sub_solver = cand[0];
452 plan = cand[1]; | 461 plan = cand[1];
> 462 plan_state = Tentative_Stuck;
> 463 replan_limit = (plan.length - insertion_point);
> 464 lambda_getter = current_game.map.collected_lambda < cand
> 465 } else {
> 466 sub_solver = cand[0];
> 467 plan = cand[1];
453 plan_state = (plan.length < PredictFuture ? Fixed : cand[2]); | 468 plan_state = (plan.length < PredictFuture ? Fixed : ca
454 replan_limit = tiebreak_by_turn ? min(PredictFuture, plan.length | 469 replan_limit = tiebreak_by_turn ? min(PredictFuture, pla
455 lambda_getter = current_game.map.collected_lambda < cand[0].g.ma | 470 lambda_getter = current_game.map.collected_lambda < cand
> 471 }
456 } 472 }
457 473
458 Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix) 474 Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix)
459 { 475 {
460 SubSolver s = new SubSolver(g); 476 SubSolver s = new SubSolver(g);
461 foreach(char c; prefix) 477 foreach(char c; prefix)
462 s.force(c); 478 s.force(c);