しかし、紛らわしいことにNegaScout探索はScout探索のnega実装ではない。NegaScout探索はReinefeldによって考案された手法[1]で、名前の通りScout探索を元にしている。しかし、Scout探索がbranch and boundに似た枝刈りをするのに対して、NegaScout探索はαβ探索に基づいている。Scoutの最初のScout探索の用いるtest関数をNegaScout探索では、αβ探索のnull window searchによって実現している。
null window searchとはα+1=βとしたαβ探索である。このとき、探索によって、どのようなleaf nodeの値であろうともαカットあるいはβカットされることになる。ある枝がαカットされたとき、その枝の真のminmax値はそのαカットされたときの値と等しいかより小さい。βカットも同様である。したがって、ある枝に対してnull window searchを行うことで、その枝の真の値がある値αより大きいか、あるいは等しいまたは小さいということが判別できる。つまり、null window searchを用いることでScout関数におけるtest関数と同等のことを行うことができる。
実際のプログラムは次のようになる。
abstract class NegaScoutPlayer[N <: Node[N]](val maxDepth: Int) extends Player[N] {
override def play(ply: Int, node: N, last: Move): Move = {
val (m, s) = play(node, Int.MinValue + 1, Int.MaxValue, maxDepth)
m
}
def play(node: N, alpha: Int, beta: Int, depth: Int): (Move, Int) = {
if (depth == 0 || node.isTerminal) {
return (Move.empty, score(node))
}
val moves = node.possibleMoves()
var bestMove = Move.empty
var alpha_ = Int.MinValue + 1
var beta_ = beta
for (m <- moves) {
val n = node.play(m).get
val (_, s) = play(n, -beta_, -(alpha_ max alpha), depth - 1)
if (-s > alpha_) {
if (beta_ == beta || depth <= 2) {
alpha_ = -s
} else {
val (_, s2) = play(n, -beta, s, depth - 1)
alpha_ = -s2
}
bestMove = m
}
if (alpha_ >= beta) { // beta cut
return (m, alpha_)
}
beta_ = (alpha_ max alpha) + 1
}
(bestMove, alpha_)
}
def score(node: N): Int
}
NegaScout探索はScout探索と異なりβ値を活用するため、Scout探索よりも高速な探索となると期待できる。
ベンチマークの結果は次の通り。
, , test = end40.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 13 117 139 866 1278 7055 11826 56216 102936
scout 17 122 184 1355 1746 10638 14448 90827 159611
negascout 13 118 150 869 1426 6877 11739 50161 107685
, , test = end41.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 30 289 525 4332 6865 55580 78076 795144 637477
scout 31 147 523 1685 7813 16346 62773 259737 720301
negascout 30 277 498 3942 5522 38672 51316 637813 507317
, , test = end42.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 30 223 338 3747 4063 47325 48221 538729 579236
scout 46 208 507 1796 3929 17116 54538 242091 637888
negascout 30 177 375 2436 3176 25612 42839 248198 549411
, , test = end43.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 49 77 673 1388 10677 23115 115886 319520 1253254
scout 85 180 501 1792 5469 20568 75687 406273 1449598
negascout 49 64 455 1241 5358 13714 74902 246768 1342957
, , test = end44.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 37 208 575 4023 6969 59839 53319 834028 541004
scout 51 181 831 1754 6878 14971 45735 135692 426776
negascout 37 163 718 2376 6146 31217 41518 382253 369021
, , test = end45.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 34 370 329 5777 2723 61868 26343 817688 226751
scout 36 262 313 2588 3061 24128 27437 184520 306221
negascout 34 341 307 5106 2720 48033 26628 663943 243477
, , test = end46.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 25 335 594 10135 11688 124574 152214 1237488 1574325
scout 25 269 600 4603 12058 52798 159862 639592 1366585
negascout 25 374 485 9812 9666 120794 121581 867828 1146500
, , test = end47.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 47 77 788 843 14354 7810 191791 43789 1106182
scout 71 171 865 4122 15544 51052 170941 227355 710531
negascout 47 77 742 709 12574 6465 147226 35518 647303
, , test = end48.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 29 313 470 6681 9337 89444 145149 1129818 1887604
scout 38 235 530 3214 9771 56977 123631 620781 1160128
negascout 29 237 487 4048 8711 47471 101834 447611 1157189
, , test = end49.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 34 273 494 2408 6707 20749 125380 310137 1682987
scout 48 125 569 1718 7189 43022 168662 703102 1383906
negascout 34 278 539 1791 6544 15755 119662 171897 1286707
, , test = end50.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 33 452 626 15963 10816 534240 202532 25385511 3547451
scout 42 325 711 5129 10956 102361 213611 1484040 3335089
negascout 33 323 675 12049 10445 311521 165628 8331136 2730443
, , test = end51.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 59 183 1160 2032 31843 24937 479486 347731 11632682
scout 97 391 1425 2848 20183 58913 516050 1038602 12026764
negascout 59 202 1030 1938 19853 24097 375925 327750 8490980
, , test = end52.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 63 204 992 1946 6498 22494 94032 247170 1771168
scout 78 404 966 2461 5686 30081 106730 390460 1331091
negascout 63 180 902 1709 5654 19288 81468 195141 1277140
, , test = end53.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 43 350 1214 11389 29471 576664 332677 41483269 4314728
scout 58 239 1355 3738 26987 71788 377530 1003209 3523635
negascout 43 349 1278 10972 25288 247619 274617 10298036 3186665
, , test = end54.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 23 239 586 2323 14222 22906 211911 292473 2569049
scout 23 125 385 2688 5905 21854 100181 502976 1062680
negascout 23 216 371 2194 5870 26600 92194 287651 927408
, , test = end55.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 49 322 841 5657 20688 82789 223240 1981849 3913589
scout 70 524 1076 7771 23559 105182 225428 1312618 4845125
negascout 49 295 857 4616 20627 59091 189197 1009661 3447413
, , test = end56.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 56 148 1532 2013 26438 37070 373227 380459 7594219
scout 92 466 1758 3716 15043 58080 226731 1140123 7096800
negascout 56 120 1326 1596 14771 21502 222253 230785 6013316
, , test = end57.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 38 289 458 5651 4485 107143 44017 1887772 575659
scout 60 145 528 1040 4698 13081 39672 105975 569878
negascout 38 237 507 4475 4477 61001 30822 849439 392082
, , test = end58.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 55 828 904 15508 15619 238957 206252 3275672 2451690
scout 84 298 1401 4369 22385 72483 292685 927379 3730359
negascout 55 547 863 14095 16348 194209 211595 2727903 2286834
, , test = end59.pos
depth
name 2 3 4 5 6 7 8 9 10
negaalpha 18 240 210 3747 2592 63628 31206 690918 271286
scout 20 150 221 1922 3015 24676 33356 283456 228431
negascout 18 214 209 2844 2643 58239 30403 1008983 216835
[1] Reinefeld. An improvement of the Scout tree-search algorithm. ICCA Journal (1983) vol. 6 (4) pp. 4-14
0 件のコメント:
コメントを投稿