それに対して、Judea Pearlによって考案されたScout探索[1]は、最悪の場合、αβ探索よりも遅くなることもあるが、多くの場合はαβ探索よりも速くなる手法である。
Scout探索はevalとtestの二種類の関数からなる。eval(node)はnodeのminmax値を求める関数で、まず一番左の子ノードのminmax値sを再帰的にevalを呼び出すことで求める。次に、maxノードの場合、左から２つ目以降の子ノードが先のminmax値sを超えているかどうかをtest関数を用いて求める。もし、超えていれば再帰的にeval関数を用いることでminmax値を求めsを更新する。minノードの場合も同様である。
αβ探索との違いはtest関数である。この関数はeval関数とは異なり値を超えているか、あるいは超えていないかだけを調べるため、子ノードを順に見ていく際に一つでも値が超えていた場合、そこでtrueを返すことができる。そうすることによって、通常のαβ探索以上に高速な探索が可能になる。
プログラムは次の通り。
abstract class ScoutPlayer[N <: Node[N]](val maxDepth: Int) extends Player[N] {
override def play(ply: Int, node: N, last: Move): Move = {
val (m, s) = evalMax(node, maxDepth)
m
}
def evalMax(node: N, depth: Int): (Move, Int) = {
if (depth == 0 || node.isTerminal) {
return (Move.empty, score(node))
}
var bestMove = Move.empty
var s = Int.MinValue
val moves = node.possibleMoves()
bestMove = moves.head
val n1 = node.play(bestMove).get
s = evalMin(n1, depth - 1)._2
for (m <- moves.tail) {
val n = node.play(m).get
if (testGTMin(n, s, depth - 1)) {
bestMove = m
s = evalMin(n, depth - 1)._2
}
}
(bestMove, s)
}
def testGTMin(node: N, s: Int, depth: Int): Boolean = {
if (depth == 0 || node.isTerminal) {
return (score(node) > s)
}
val moves = node.possibleMoves()
for (m <- moves) {
val n = node.play(m).get
if (!testGTMax(n, s, depth - 1)) {
return false
}
}
true
}
def testGTMax(node: N, s: Int, depth: Int): Boolean = {
if (depth == 0 || node.isTerminal) {
return (score(node) > s)
}
val moves = node.possibleMoves()
for (m <- moves) {
val n = node.play(m).get
if (testGTMin(n, s, depth - 1)) {
return true
}
}
false
}
def evalMin(node: N, depth: Int): (Move, Int) = {
if (depth == 0 || node.isTerminal) {
return (Move.empty, score(node))
}
var bestMove = Move.empty
var s = Int.MaxValue
val moves = node.possibleMoves()
bestMove = moves.head
val n1 = node.play(bestMove).get
s = evalMax(n1, depth - 1)._2
for (m <- moves.tail) {
val n = node.play(m).get
if (testLTMax(n, s, depth - 1)) {
bestMove = m
s = evalMax(n, depth - 1)._2
}
}
(bestMove, s)
}
def testLTMax(node: N, s: Int, depth: Int): Boolean = {
if (depth == 0 || node.isTerminal) {
return (score(node) < s)
}
val moves = node.possibleMoves()
for (m <- moves) {
val n = node.play(m).get
if (!testLTMin(n, s, depth - 1)) {
return false
}
}
true
}
def testLTMin(node: N, s: Int, depth: Int): Boolean = {
if (depth == 0 || node.isTerminal) {
return (score(node) < s)
}
val moves = node.possibleMoves()
for (m <- moves) {
val n = node.play(m).get
if (testLTMax(n, s, depth - 1)) {
return true
}
}
false
}
def score(node: N): Int
}
実際にベンチマークをとってみると次のようになる。
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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
, , 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
実験結果から、速くなることもあれば、遅くなることもあることがわかる。
[1] Pearl. SCOUT: A Simple Game-Searching Algorithm with Proven Optimal Properties. AAAI (1980) pp. 143-145
0 件のコメント:
コメントを投稿