313 } 313 } 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 static const PredictFuture = 10; | 321 static const PredictFuture = 10; > 322 const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL s > 323 const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step 321 324 322 Game current_game; 325 Game current_game; 323 SubSolver sub_solver; 326 SubSolver sub_solver; 324 327 325 enum {Tentative, Tentative_Stuck, Fixed}; 328 enum {Tentative, Tentative_Stuck, Fixed}; 326 string plan; 329 string plan; 327 int plan_state; 330 int plan_state; > 331 int replan_limit; 328 332 329 this(in Game g) 333 this(in Game g) 330 { 334 { 331 current_game = g.clone(); 335 current_game = g.clone(); 332 plan = ""; 336 plan = ""; 333 plan_state = Tentative; 337 plan_state = Tentative; > 338 replan_limit = PredictFuture; > 339 if(g.map.W*g.map.H <= 400) > 340 RandomChoicePattern = ["UU","UD","UL","UR", > 341 "DU","DD","DL","DR", > 342 "LU","LD","LL","LR", > 343 "RU","RD","RL","RR","UUU","UUUU", > 344 else if(g.map.W*g.map.H <= 4096) > 345 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU"," > 346 else > 347 RandomChoicePattern = ["U","D","L","R"]; 334 } 348 } 335 349 336 char single_step() 350 char single_step() 337 { 351 { 338 if(current_game.dead || current_game.cleared) 352 if(current_game.dead || current_game.cleared) 339 return 'A'; 353 return 'A'; 340 354 341 // Make enough prediction. 355 // Make enough prediction. 342 while( plan_state==Tentative && plan.length<PredictFuture ) | 356 while( plan_state==Tentative && plan.length<replan_limit ) 343 single_step_predict(); 357 single_step_predict(); 344 358 345 // If the future is bad, correct. 359 // If the future is bad, correct. 346 if( plan_state==Tentative_Stuck && plan.length<PredictFuture ) | 360 if( plan_state==Tentative_Stuck && plan.length<replan_limit ) 347 replan(); 361 replan(); 348 362 349 // Follow the predicted plan. 363 // Follow the predicted plan. 350 if( plan.empty ) 364 if( plan.empty ) 351 return 'A'; 365 return 'A'; 352 stderr.writeln(plan, " ", plan_state); 366 stderr.writeln(plan, " ", plan_state); 353 char c = plan[0]; 367 char c = plan[0]; ................................................................................................................................................................................ 391 } 405 } 392 406 393 void replan() 407 void replan() 394 { 408 { 395 stderr.writeln("replan!"); 409 stderr.writeln("replan!"); 396 // Try to replace every step of the plan by another move. 410 // Try to replace every step of the plan by another move. 397 Game g = current_game.clone(); 411 Game g = current_game.clone(); 398 Tuple!(long, SubSolver, string, int) cand = | 412 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te 399 tuple(sub_solver.g.score, sub_solver, plan, Tentative_St | 413 bool tiebreak_by_turn = false; 400 for(int i=0; i<plan.length; ++i) { 414 for(int i=0; i<plan.length; ++i) { 401 foreach(string prefix; ["U","D","L","R","UD","DU","LR"," | 415 foreach(string prefix; RandomChoicePattern) 402 if(prefix[0] != plan[i]) { 416 if(prefix[0] != plan[i]) { 403 Tuple!(long, SubSolver, string, int) r = | 417 Tuple!(SubSolver, string, int) r = try_p 404 if(cand[0] < r[0]) { < 405 r[2] = plan[0..i] ~ prefix ~ r[2 | 418 r[1] = plan[0..i] ~ prefix ~ r[1]; > 419 bool better = false, tbt=false; 406 cand = r; | 420 if(!cand[0].g.cleared && r[0].g.cleared) > 421 better = true; > 422 else if(cand[0].g.cleared && r[0].g.clea > 423 better = cand[0].g.score < r[0]. > 424 } > 425 else if(!cand[0].g.cleared && !r[0].g.cl > 426 if(cand[0].g.map.collected_lambd > 427 better = true; > 428 else if(cand[0].g.map.collected_ > 429 if(cand[0].g.dead && !r[ > 430 better = true; > 431 else if(cand[0].g.dead = > 432 better = (cand[1 > 433 tbt = true; > 434 } > 435 } 407 } 436 } > 437 if(better) { > 438 cand = r; > 439 tiebreak_by_turn = true; > 440 writeln(cand); > 441 } 408 } 442 } 409 g.command(plan[i]); 443 g.command(plan[i]); 410 } 444 } 411 445 412 sub_solver = cand[1]; | 446 sub_solver = cand[0]; 413 plan = cand[2]; | 447 plan = cand[1]; 414 plan_state = (plan.length < PredictFuture ? Fixed : cand[3]); | 448 plan_state = (plan.length < PredictFuture ? Fixed : cand[2]); > 449 replan_limit = tiebreak_by_turn ? min(PredictFuture, plan.length 415 } 450 } 416 451 417 Tuple!(long, SubSolver, string, int) try_plan(in Game g, string prefix) | 452 Tuple!(SubSolver, string, int) try_plan(in Game g, string prefix) 418 { 453 { 419 SubSolver s = new SubSolver(g); 454 SubSolver s = new SubSolver(g); 420 foreach(char c; prefix) 455 foreach(char c; prefix) 421 s.force(c); 456 s.force(c); 422 string log; 457 string log; 423 int state = Tentative; 458 int state = Tentative; 424 while(!s.g.cleared && !s.g.dead && log.length<=g.map.H*g.map.W) | 459 while(!s.g.cleared && !s.g.dead && log.length<=ReplanLength && l 425 char c = s.single_step(); 460 char c = s.single_step(); 426 if( c == 'A' ) { 461 if( c == 'A' ) { 427 state = Tentative_Stuck; 462 state = Tentative_Stuck; 428 break; 463 break; 429 } 464 } 430 log ~= c; 465 log ~= c; 431 } 466 } 432 if(s.g.cleared) state = Fixed; 467 if(s.g.cleared) state = Fixed; 433 else if(s.g.dead) state = Tentative_Stuck; 468 else if(s.g.dead) state = Tentative_Stuck; 434 return tuple(s.g.score, s, log, state); | 469 return tuple(s, log, state); 435 } 470 } 436 } 471 } 437 /* < 438 class MasterSolver : Solver < 439 { < 440 this(in Game g) < 441 { < 442 int SIZE = g.map.H * g.map.W; < 443 if( SIZE <= 32*32 ) < 444 sub = new Solver_2!(Solver_1)(g); < 445 else if( SIZE <= 100*100 ) < 446 sub = new Solver_1(g); < 447 else < 448 sub = new Solver_1(g); < 449 } < 450 472 451 private Solver sub; < 452 char single_step() { return sub.single_step(); } < 453 void force(char c) { sub.force(c); } < 454 } < 455 < 456 alias MasterSolver MainSolver; < 457 */ < 458 alias Solver_2!(Solver_1) MainSolver; 473 alias Solver_2!(Solver_1) MainSolver; 459 //alias Solver_1 MainSolver; 474 //alias Solver_1 MainSolver; 460 //alias Solver_0 MainSolver; 475 //alias Solver_0 MainSolver;