313 313 } 314 314 return (danger_ok ? [] : tryA()) ~ tryB() ~ tryC(); 315 315 } 316 316 } 317 317 318 318 class Solver_2(SubSolver) : Solver 319 319 { 320 - static const PredictFuture = 10; 320 + // Parameters. 321 + static const PredictFuture = 10; 322 + const string[] RandomChoicePattern; // PF*RCP exhaustive search for RL steps 323 + const ReplanLength = 400; // O(PF*RCP*RL*SubSolver.single_step) 321 324 322 325 Game current_game; 323 326 SubSolver sub_solver; 324 327 325 328 enum {Tentative, Tentative_Stuck, Fixed}; 326 329 string plan; 327 330 int plan_state; 331 + int replan_limit; 328 332 329 333 this(in Game g) 330 334 { 331 335 current_game = g.clone(); 332 336 plan = ""; 333 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","UUUUU"]; 344 + else if(g.map.W*g.map.H <= 4096) 345 + RandomChoicePattern = ["UUU","U","D","L","R","UD","DU","LR","RL"]; 346 + else 347 + RandomChoicePattern = ["U","D","L","R"]; 334 348 } 335 349 336 350 char single_step() 337 351 { 338 352 if(current_game.dead || current_game.cleared) 339 353 return 'A'; 340 354 341 355 // Make enough prediction. 342 - while( plan_state==Tentative && plan.length<PredictFuture ) 356 + while( plan_state==Tentative && plan.length<replan_limit ) 343 357 single_step_predict(); 344 358 345 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 361 replan(); 348 362 349 363 // Follow the predicted plan. 350 364 if( plan.empty ) 351 365 return 'A'; 352 366 stderr.writeln(plan, " ", plan_state); 353 367 char c = plan[0]; ................................................................................ 391 405 } 392 406 393 407 void replan() 394 408 { 395 409 stderr.writeln("replan!"); 396 410 // Try to replace every step of the plan by another move. 397 411 Game g = current_game.clone(); 398 - Tuple!(long, SubSolver, string, int) cand = 399 - tuple(sub_solver.g.score, sub_solver, plan, Tentative_Stuck); 412 + Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Tentative_Stuck); 413 + bool tiebreak_by_turn = false; 400 414 for(int i=0; i<plan.length; ++i) { 401 - foreach(string prefix; ["U","D","L","R","UD","DU","LR","RL"]) 415 + foreach(string prefix; RandomChoicePattern) 402 416 if(prefix[0] != plan[i]) { 403 - Tuple!(long, SubSolver, string, int) r = try_plan(g, prefix); 404 - if(cand[0] < r[0]) { 405 - r[2] = plan[0..i] ~ prefix ~ r[2]; 406 - cand = r; 417 + Tuple!(SubSolver, string, int) r = try_plan(g, prefix); 418 + r[1] = plan[0..i] ~ prefix ~ r[1]; 419 + bool better = false, tbt=false; 420 + if(!cand[0].g.cleared && r[0].g.cleared) 421 + better = true; 422 + else if(cand[0].g.cleared && r[0].g.cleared) { 423 + better = cand[0].g.score < r[0].g.score; 424 + } 425 + else if(!cand[0].g.cleared && !r[0].g.cleared) { 426 + if(cand[0].g.map.collected_lambda < r[0].g.map.collected_lambda) 427 + better = true; 428 + else if(cand[0].g.map.collected_lambda == r[0].g.map.collected_lambda) { 429 + if(cand[0].g.dead && !r[0].g.dead) 430 + better = true; 431 + else if(cand[0].g.dead == r[0].g.dead) { 432 + better = (cand[1].length < r[1].length); 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 443 g.command(plan[i]); 410 444 } 411 445 412 - sub_solver = cand[1]; 413 - plan = cand[2]; 414 - plan_state = (plan.length < PredictFuture ? Fixed : cand[3]); 446 + sub_solver = cand[0]; 447 + plan = cand[1]; 448 + plan_state = (plan.length < PredictFuture ? Fixed : cand[2]); 449 + replan_limit = tiebreak_by_turn ? min(PredictFuture, plan.length/2) : PredictFuture; 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 454 SubSolver s = new SubSolver(g); 420 455 foreach(char c; prefix) 421 456 s.force(c); 422 457 string log; 423 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 && log.length<=g.map.W*g.map.H) { 425 460 char c = s.single_step(); 426 461 if( c == 'A' ) { 427 462 state = Tentative_Stuck; 428 463 break; 429 464 } 430 465 log ~= c; 431 466 } 432 467 if(s.g.cleared) state = Fixed; 433 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 473 alias Solver_2!(Solver_1) MainSolver; 459 474 //alias Solver_1 MainSolver; 460 475 //alias Solver_0 MainSolver;