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);