333 333 int clear_improvement = 3; 334 334 335 335 this(in Game g) 336 336 { 337 337 current_game = g.clone(); 338 338 plan = ""; 339 339 plan_state = Tentative; 340 - replan_limit = PredictFuture; 341 - if(g.map.W*g.map.H <= 400) 340 + if(g.map.W*g.map.H <= 400) { 342 341 RandomChoicePattern = ["UU","UD","UL","UR", 343 342 "DU","DD","DL","DR", 344 343 "LU","LD","LL","LR", 345 344 "RU","RD","RL","RR","UUU","UUUU","UUUUU"]; 346 - else if(g.map.W*g.map.H <= 4096) 345 + PredictFuture = 20; 346 + clear_improvement = 3; 347 + } 348 + else if(g.map.W*g.map.H <= 4096) { 347 349 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"]; 348 - else 350 + PredictFuture = 10; 351 + clear_improvement = 0; 352 + } 353 + else { 349 354 RandomChoicePattern = ["U","D","L","R"]; 350 - 351 - if(g.map.W*g.map.H <= 400) 352 - PredictFuture = 20; 353 - else 354 355 PredictFuture = 10; 356 + clear_improvement = 0; 357 + } 358 + 359 + replan_limit = PredictFuture; 355 360 } 356 361 357 362 char single_step() 358 363 { 359 364 if(current_game.dead || current_game.cleared) 360 365 return 'A'; 361 366 ................................................................................ 405 410 } 406 411 407 412 char c = sub_solver.single_step(); 408 413 if(c == 'A') 409 414 plan_state = Tentative_Stuck; 410 415 else { 411 416 plan ~= c; 412 - plan_state = (sub_solver.g.dead ? Tentative_Stuck : 413 - sub_solver.g.cleared ? Fixed : Tentative); 417 + if(sub_solver.g.cleared) { 418 + if(clear_improvement-->0) { 419 + plan_state = Tentative_Stuck; 420 + replan_limit = min(plan.length-plan.length/(clear_improvement+1), PredictFuture); 421 + } else { 422 + plan_state = Fixed; 423 + } 424 + } else { 425 + plan_state = (sub_solver.g.dead ? Tentative_Stuck : Tentative); 426 + } 414 427 } 415 428 } 416 429 417 430 void replan() 418 431 { 419 432 stderr.writeln("replan!"); 420 433 // Try to replace every step of the plan by another move. 421 434 Game g = current_game.clone(); 422 435 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck); 423 436 int insertion_point = plan.length; 424 437 writeln(cand, " ", cand[0].g.map.collected_lambda); 425 438 bool tiebreak_by_turn = false; 439 + int consider_length = min(ReplanLength, g.map.W*g.map.H); 440 + if(cand[0].g.cleared) consider_length = min(consider_length, cand[1].length); 441 + 426 442 for(int i=0; i<plan.length; ++i) { 427 443 foreach(string prefix; RandomChoicePattern) 428 444 if(prefix[0] != plan[i]) { 429 - Tuple!(SubSolver, string, int) r = try_plan(g, prefix); 445 + Tuple!(SubSolver, string, int) r = try_plan(g, prefix, consider_length-i-prefix.length); 430 446 r[1] = plan[0..i] ~ prefix ~ r[1]; 431 447 bool better = false, tbt=false; 432 448 if(!cand[0].g.cleared && r[0].g.cleared) 433 449 better = true; 434 450 else if(cand[0].g.cleared && r[0].g.cleared) { 435 451 better = cand[0].g.score < r[0].g.score; 436 452 } ................................................................................ 446 462 } 447 463 } 448 464 } 449 465 if(better) { 450 466 cand = r; 451 467 tiebreak_by_turn = true; 452 468 insertion_point = i+prefix.length; 469 + if(r[0].g.cleared) consider_length = min(consider_length, r[1].length); 453 470 writeln(cand, " ", cand[0].g.map.collected_lambda); 454 471 } 455 472 } 456 473 g.command(plan[i]); 457 474 } 458 475 459 476 if(cand[2]==Fixed && insertion_point!=plan.length && clear_improvement-->0) { 460 477 sub_solver = cand[0]; 461 478 plan = cand[1]; 462 479 plan_state = Tentative_Stuck; 463 - replan_limit = (plan.length - insertion_point); 480 + replan_limit = min(plan.length - insertion_point, PredictFuture); 464 481 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda; 465 482 } else { 466 483 sub_solver = cand[0]; 467 484 plan = cand[1]; 468 485 plan_state = (plan.length < PredictFuture ? Fixed : cand[2]); 469 - replan_limit = tiebreak_by_turn ? min(PredictFuture, plan.length/2) : PredictFuture; 486 + replan_limit = tiebreak_by_turn ? min(PredictFuture, (plan.length+1)/2) : PredictFuture; 470 487 lambda_getter = current_game.map.collected_lambda < cand[0].g.map.collected_lambda; 471 488 } 472 489 } 473 490 474 - Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix) 491 + Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix, int consider_length) 475 492 { 493 + if(consider_length<=0) consider_length = 2; 494 + 476 495 SubSolver s = new SubSolver(g); 477 496 foreach(char c; prefix) 478 497 s.force(c); 479 498 string log; 480 499 int state = Tentative; 481 - while(!s.g.cleared && !s.g.dead && log.length<=ReplanLength && log.length<=g.map.W*g.map.H) { 500 + while(!s.g.cleared && !s.g.dead && log.length<=consider_length) { 482 501 char c = s.single_step(); 483 502 if( c == 'A' ) { 484 503 state = Tentative_Stuck; 485 504 break; 486 505 } 487 506 log ~= c; 488 507 }