Overview
| SHA1 Hash: | ff8066db429a4b5d400101bad5c08865d5195c71 |
|---|---|
| Date: | 2012-07-16 10:23:58 |
| User: | kinaba |
| Comment: | Replanning. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Diffs: | redesign |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [16f0b5784f]
- sym-trunk inherited from [16f0b5784f]
Changes
Modified score_memo.txt from [574f95bdd01111dd] to [80c37c10a3b0a423].
1 contest1 212! 1 contest1 212! 2 contest2 280? | 2 contest2 281! 3 contest3 275! 3 contest3 275! 4 contest4 561? 4 contest4 561? 5 contest5 1281? 5 contest5 1281? 6 contest6 737 // 一度通り過ぎるとふさがってしまう曲がり道 6 contest6 737 // 一度通り過ぎるとふさがってしまう曲がり道 7 contest7 867? 7 contest7 867? 8 contest8 1245 // 無理ゲー 8 contest8 1245 // 無理ゲー 9 contest9 3042? 9 contest9 3042? 10 contest10 2076 // "λの上に岩" トラップが複数 10 contest10 2076 // "λの上に岩" トラップが複数 11 flood1 569 // 崩すの怖がりすぎ ＆ 一直線に並んでるのに真ん中から取るのはどうなの 11 flood1 569 // 崩すの怖がりすぎ ＆ 一直線に並んでるのに真ん中から取るのはどうなの 12 flood2 280? | 12 flood2 281! 13 flood3 802 // 溺死 13 flood3 802 // 溺死 14 flood4 970 // むずかしい岩崩し 14 flood4 970 // むずかしい岩崩し 15 flood5 561? 15 flood5 561? 16 trampoline1 291 // むずかしい岩崩し 16 trampoline1 291 // むずかしい岩崩し 17 trampoline2 1728? | 17 trampoline2 1732? 18 trampoline3 698 // "上に岩" ワープゾーン版 18 trampoline3 698 // "上に岩" ワープゾーン版 19 beard1 856? 19 beard1 856? 20 beard2 2792 // 崩すの怖がりすぎて間に合わなくなって溺死 20 beard2 2792 // 崩すの怖がりすぎて間に合わなくなって溺死 21 beard3 811 // 無理ゲー：速攻で髭刈らないといけない 21 beard3 811 // 無理ゲー：速攻で髭刈らないといけない 22 beard4 1950 // 髭を解放しないように動くゲー 22 beard4 1950 // 髭を解放しないように動くゲー 23 beard5 665 // これクリアできるの 23 beard5 665 // これクリアできるの 24 horock1 333 24 horock1 333 25 horock2 235 25 horock2 235 26 horock3 1542 26 horock3 1542
Modified src/solver.d from [434706ae08dfc66e] to [15905b6766caaf1d].
333 int clear_improvement = 3; 333 int clear_improvement = 3; 334 334 335 this(in Game g) 335 this(in Game g) 336 { 336 { 337 current_game = g.clone(); 337 current_game = g.clone(); 338 plan = ""; 338 plan = ""; 339 plan_state = Tentative; 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 RandomChoicePattern = ["UU","UD","UL","UR", 341 RandomChoicePattern = ["UU","UD","UL","UR", 343 "DU","DD","DL","DR", 342 "DU","DD","DL","DR", 344 "LU","LD","LL","LR", 343 "LU","LD","LL","LR", 345 "RU","RD","RL","RR","UUU","UUUU", 344 "RU","RD","RL","RR","UUU","UUUU", > 345 PredictFuture = 20; > 346 clear_improvement = 3; > 347 } 346 else if(g.map.W*g.map.H <= 4096) | 348 else if(g.map.W*g.map.H <= 4096) { 347 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU"," 349 RandomChoicePattern = ["UUU","U","D","L","R","UD","DU"," > 350 PredictFuture = 10; > 351 clear_improvement = 0; > 352 } 348 else | 353 else { 349 RandomChoicePattern = ["U","D","L","R"]; 354 RandomChoicePattern = ["U","D","L","R"]; 350 < 351 if(g.map.W*g.map.H <= 400) < 352 PredictFuture = 20; < 353 else < 354 PredictFuture = 10; 355 PredictFuture = 10; > 356 clear_improvement = 0; > 357 } > 358 > 359 replan_limit = PredictFuture; 355 } 360 } 356 361 357 char single_step() 362 char single_step() 358 { 363 { 359 if(current_game.dead || current_game.cleared) 364 if(current_game.dead || current_game.cleared) 360 return 'A'; 365 return 'A'; 361 366 ................................................................................................................................................................................ 405 } 410 } 406 411 407 char c = sub_solver.single_step(); 412 char c = sub_solver.single_step(); 408 if(c == 'A') 413 if(c == 'A') 409 plan_state = Tentative_Stuck; 414 plan_state = Tentative_Stuck; 410 else { 415 else { 411 plan ~= c; 416 plan ~= c; > 417 if(sub_solver.g.cleared) { > 418 if(clear_improvement-->0) { > 419 plan_state = Tentative_Stuck; > 420 replan_limit = min(plan.length-plan.leng > 421 } else { > 422 plan_state = Fixed; > 423 } > 424 } else { 412 plan_state = (sub_solver.g.dead ? Tentative_Stuck : | 425 plan_state = (sub_solver.g.dead ? Tentative_Stuc 413 sub_solver.g.cleared ? Fixed : Tentative); < > 426 } 414 } 427 } 415 } 428 } 416 429 417 void replan() 430 void replan() 418 { 431 { 419 stderr.writeln("replan!"); 432 stderr.writeln("replan!"); 420 // Try to replace every step of the plan by another move. 433 // Try to replace every step of the plan by another move. 421 Game g = current_game.clone(); 434 Game g = current_game.clone(); 422 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te 435 Tuple!(SubSolver, string, int) cand = tuple(sub_solver, plan, Te 423 int insertion_point = plan.length; 436 int insertion_point = plan.length; 424 writeln(cand, " ", cand[0].g.map.collected_lambda); 437 writeln(cand, " ", cand[0].g.map.collected_lambda); 425 bool tiebreak_by_turn = false; 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, can > 441 426 for(int i=0; i<plan.length; ++i) { 442 for(int i=0; i<plan.length; ++i) { 427 foreach(string prefix; RandomChoicePattern) 443 foreach(string prefix; RandomChoicePattern) 428 if(prefix[0] != plan[i]) { 444 if(prefix[0] != plan[i]) { 429 Tuple!(SubSolver, string, int) r = try_p | 445 Tuple!(SubSolver, string, int) r = try_p 430 r[1] = plan[0..i] ~ prefix ~ r[1]; 446 r[1] = plan[0..i] ~ prefix ~ r[1]; 431 bool better = false, tbt=false; 447 bool better = false, tbt=false; 432 if(!cand[0].g.cleared && r[0].g.cleared) 448 if(!cand[0].g.cleared && r[0].g.cleared) 433 better = true; 449 better = true; 434 else if(cand[0].g.cleared && r[0].g.clea 450 else if(cand[0].g.cleared && r[0].g.clea 435 better = cand[0].g.score < r[0]. 451 better = cand[0].g.score < r[0]. 436 } 452 } ................................................................................................................................................................................ 446 } 462 } 447 } 463 } 448 } 464 } 449 if(better) { 465 if(better) { 450 cand = r; 466 cand = r; 451 tiebreak_by_turn = true; 467 tiebreak_by_turn = true; 452 insertion_point = i+prefix.lengt 468 insertion_point = i+prefix.lengt > 469 if(r[0].g.cleared) consider_leng 453 writeln(cand, " ", cand[0].g.map.collected_lambda); 470 writeln(cand, " ", cand[0].g.map.collected_lambda); 454 } 471 } 455 } 472 } 456 g.command(plan[i]); 473 g.command(plan[i]); 457 } 474 } 458 475 459 if(cand[2]==Fixed && insertion_point!=plan.length && clear_impro 476 if(cand[2]==Fixed && insertion_point!=plan.length && clear_impro 460 sub_solver = cand[0]; 477 sub_solver = cand[0]; 461 plan = cand[1]; 478 plan = cand[1]; 462 plan_state = Tentative_Stuck; 479 plan_state = Tentative_Stuck; 463 replan_limit = (plan.length - insertion_point); | 480 replan_limit = min(plan.length - insertion_point, Predic 464 lambda_getter = current_game.map.collected_lambda < cand 481 lambda_getter = current_game.map.collected_lambda < cand 465 } else { 482 } else { 466 sub_solver = cand[0]; 483 sub_solver = cand[0]; 467 plan = cand[1]; 484 plan = cand[1]; 468 plan_state = (plan.length < PredictFuture ? Fixed : ca 485 plan_state = (plan.length < PredictFuture ? Fixed : ca 469 replan_limit = tiebreak_by_turn ? min(PredictFuture, pla | 486 replan_limit = tiebreak_by_turn ? min(PredictFuture, (pl 470 lambda_getter = current_game.map.collected_lambda < cand 487 lambda_getter = current_game.map.collected_lambda < cand 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 co 475 { 492 { > 493 if(consider_length<=0) consider_length = 2; > 494 476 SubSolver s = new SubSolver(g); 495 SubSolver s = new SubSolver(g); 477 foreach(char c; prefix) 496 foreach(char c; prefix) 478 s.force(c); 497 s.force(c); 479 string log; 498 string log; 480 int state = Tentative; 499 int state = Tentative; 481 while(!s.g.cleared && !s.g.dead && log.length<=ReplanLength && l | 500 while(!s.g.cleared && !s.g.dead && log.length<=consider_length) 482 char c = s.single_step(); 501 char c = s.single_step(); 483 if( c == 'A' ) { 502 if( c == 'A' ) { 484 state = Tentative_Stuck; 503 state = Tentative_Stuck; 485 break; 504 break; 486 } 505 } 487 log ~= c; 506 log ~= c; 488 } 507 }