Check-in [1c7a01b7f4]
Not logged in
Overview
SHA1 Hash:1c7a01b7f47ac7a810b832a1bd7b9b04b8a5aa7a
Date: 2012-07-16 09:54:11
User: kinaba
Comment:clear improvement.
Timelines: family | ancestors | descendants | both | trunk
Diffs: redesign
Downloads: Tarball | ZIP archive
Other Links: files | file ages | manifest
Tags And Properties
Changes

Modified src/solver.d from [5e89251084030d6c] to [434706ae08dfc66e].

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