NegaScout

Negamax探索はMinmax探索の実装を簡素化したものであり、NegaAlphaBetaも同様にAlphaBeta探索の実装を簡素化したものである。これらは、minノードにおけるスコアの符号が反転する点を除いては同じである。

しかし、紛らわしいことに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

Scout

αβ探索はmove orderingが最適のとき探索に必要なノード数が最も少なくなるという意味で最適な探索である。そこで、Killer heuristicおよびHistory heuristicはmove orderingを改善することで探索ノード数を最小にしようとした。

それに対して、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

Benchmark of the FFO test suite

これまでbenchmarkは、random playerを相手に、先手で100戦、後手で100戦を行い、各plyごとに平均をとってきた。回数が多いのは分散が小さくないため、安定した結果を得るには、ある程度の数が必要であるからである。しかし、この方法ではreversiがほとんどの場合で1試合に32 plyかかることから、6400 ply程度の実行が必要となる。1 plyを平均5秒で実行したとしても結果を得るのに1時間程度の時間がかかる。また、実際の大会などでは1 plyに1分程度の時間が与えられており、探索の深さももっと深く設定することが普通である。しかし、それでは結果を得るのに丸1日かかってしまう。また、random playerを相手にしているため、試合の終盤では圧勝の状況になっていることが多く、実践的なデータがとれているとはいえない。

そこで、Zebraの作者であるGunnarさんのホームページで紹介されている、The FFO endgame test suiteを用いてbenchmarkを行うことにする。

終盤だけしかないという欠点はあるが、まだ序盤や終盤で変化するようなプログラムは作成していないので現在のところ問題ない。

ここまでの手法のbenchmarkをとってみると次のようになる。

まず、negamaxにくらべてnegaalphaが、ずっと効率が良いことが確認できる。
negaalphaでは、odd depthよりも、その次のeven depthの方がノード数が少ないときがある。internal node数や実行時間ではそのような逆転は起きていない。実行時間はマシン環境によって変化するが、最も重要な指標である。leaf node数よりも、internal node数で比較した方がよいという意見もある[?]。

> xtabs(node ~ name + test, data=data)
                  test
name               end40.pos end41.pos end42.pos end43.pos end44.pos
  negamax2                30       126        68        84       106
  negamax3               305      1193       586       578      1061
  negamax4              1325     13165      4517      7297     10652
  negamax5             12843    122563     37324     55434    103153
  negamax6             63589   1211104    282095    625740    987883
  negaalpha2              13        30        30        49        37
  negaalpha3             117       289       223        77       208
  negaalpha4             139       525       338       673       575
  negaalpha5             866      4332      3747      1388      4023
  negaalpha6            1278      6865      4063     10677      6969
                  test
name               end45.pos end46.pos end47.pos end48.pos end49.pos
  negamax2                88       111        86        98       116
  negamax3              1112      1143       736      1127      1092
  negamax4              7913     11557      8327      8756     13930
  negamax5             92259    107326     70239     92677    142210
  negamax6            707766   1093863    791984    727446   1635128
  negaalpha2              34        25        47        29        34
  negaalpha3             370       335        77       313       273
  negaalpha4             329       594       788       470       494
  negaalpha5            5777     10135       843      6681      2408
  negaalpha6            2723     11688     14354      9337      6707
                  test
name               end50.pos end51.pos end52.pos end53.pos end54.pos
  negamax2               131        94       111       143        63
  negamax3              1942       959      1089      1573       707
  negamax4             18665      9470     10863     20035      4796
  negamax5            260643     96971    104217    219668     54825
  negamax6           2491678    962986    978789   2691658    415888
  negaalpha2              33        59        63        43        23
  negaalpha3             452       183       204       350       239
  negaalpha4             626      1160       992      1214       586
  negaalpha5           15963      2032      1946     11389      2323
  negaalpha6           10816     31843      6498     29471     14222
                  test
name               end55.pos end56.pos end57.pos end58.pos end59.pos
  negamax2               143       134        85       193        66
  negamax3              1990      1319       758      2448       760
  negamax4             21662     18921      7733     35050      5828
  negamax5            283164    191384     74328    442133     65369
  negamax6           3175727   2631485    745547   6005655    562206
  negaalpha2              49        56        38        55        18
  negaalpha3             322       148       289       828       240
  negaalpha4             841      1532       458       904       210
  negaalpha5            5657      2013      5651     15508      3747
  negaalpha6           20688     26438      4485     15619      2592

> xtabs(inode ~ name + test, data=data)
                  test
name               end40.pos end41.pos end42.pos end43.pos end44.pos
  negamax2                11        11        10         7        11
  negamax3                41       137        78        91       117
  negamax4               346      1330       664       669      1178
  negamax5              1671     14495      5181      7966     11830
  negamax6             14514    137058     42505     63400    114983
  negaalpha2              11        11        10         7        11
  negaalpha3              23        71        49        36        50
  negaalpha4             132       190       189       141       252
  negaalpha5             223      1358       979       729      1181
  negaalpha6            1302      2769      2491      2416      3143
                  test
name               end45.pos end46.pos end47.pos end48.pos end49.pos
  negamax2                15        13         9        14         9
  negamax3               103       124        95       112       125
  negamax4              1215      1267       831      1239      1217
  negamax5              9128     12824      9158      9995     15147
  negamax6            101387    120150     79397    102672    157357
  negaalpha2              15        13         9        14         9
  negaalpha3              56        64        23        51        67
  negaalpha4             251       287       220       256       150
  negaalpha5            1126      2781       241      1412       752
  negaalpha6            2685      5602      4855      5112      2270
                  test
name               end50.pos end51.pos end52.pos end53.pos end54.pos
  negamax2                16        11        11        12        11
  negamax3               147       105       122       155        74
  negamax4              2089      1064      1211      1728       781
  negamax5             20754     10534     12074     21763      5577
  negamax6            281397    107505    116291    241431     60402
  negaalpha2              16        11        11        12        11
  negaalpha3              58        41        50        73        44
  negaalpha4             357       305       273       358       251
  negaalpha5            2672       607       686      2355       509
  negaalpha6            6816      8116      2085      8971      5509
                  test
name               end55.pos end56.pos end57.pos end58.pos end59.pos
  negamax2                15        10         9        14        12
  negamax3               158       144        94       207        78
  negamax4              2148      1463       852      2655       838
  negamax5             23810     20384      8585     37705      6666
  negamax6            306974    211768     82913    479838     72035
  negaalpha2              15        10         9        14        12
  negaalpha3              55        45        52       143        40
  negaalpha4             350       291       167       290       192
  negaalpha5            1157       818      1505      3752       735
  negaalpha6            8782      5578      1911      5514      2643

> xtabs(time ~ name + test, data=data)
                  test
name               end40.pos end41.pos end42.pos end43.pos end44.pos
  negamax2               162       212       183       190       221
  negamax3               386       671       520       545       625
  negamax4               794      1755      1229      1400      1773
  negamax5              2035     11600      4724      6012      8419
  negamax6              6909     79483     21643     40787     73706
  negaalpha2             148       166       166       172       187
  negaalpha3             278       446       405       326       382
  negaalpha4             467       600       569       614       689
  negaalpha5             689      1651      1463      1106      1514
  negaalpha6            1201      2089      1835      2181      2389
                  test
name               end45.pos end46.pos end47.pos end48.pos end49.pos
  negamax2               231       238       204       217       217
  negamax3               613       641       581       649       672
  negamax4              1648      1846      1521      1605      1851
  negamax5              7495      8294      6351      9081     11898
  negamax6             58783     84254     57276     56096    103962
  negaalpha2             202       200       186       188       175
  negaalpha3             437       436       261       433       442
  negaalpha4             649       741       715       662       580
  negaalpha5            1544      2261       778      1909      1202
  negaalpha6            1950      3732      3420      2964      2204
                  test
name               end50.pos end51.pos end52.pos end53.pos end54.pos
  negamax2               237       226       222       252       201
  negamax3               771       641       668       741       538
  negamax4              2292      1779      1805      2269      1359
  negamax5             18820      7853     10665     16513      5537
  negamax6            157724     75202     66660    171968     37524
  negaalpha2             197       208       200       208       177
  negaalpha3             469       356       404       485       388
  negaalpha4             762       858       751       862       704
  negaalpha5            2648      1105      1207      2321      1065
  negaalpha6            3720      5664      1937      5738      3626
                  test
name               end55.pos end56.pos end57.pos end58.pos end59.pos
  negamax2               266       229       200       285       205
  negamax3               807       697       570       896       616
  negamax4              2642      2161      1473      3234      1425
  negamax5             19360     16159      7499     32512      6098
  negamax6            227045    167510     48530    366104     46530
  negaalpha2             225       203       187       239       174
  negaalpha3             434       370       428       669       379
  negaalpha4             837       857       592       811       602
  negaalpha5            1641      1281      1814      3272      1327
  negaalpha6            5587      4255      1793      4273      2051

nagealphaとkiller heuristic, history heuristic, transposition tableの比較は次の通り。
多くの盤面でkiller heuristicとtransposition tableの組み合わせが最もよい成績を収めている。

> xtabs(node ~ name + test, data=data)
                  test
name               end40.pos end41.pos end42.pos end43.pos end44.pos
  negaalpha6            1278      6865      4063     10677      6969
  killer6_32            1259      4463      2894      3733      4865
  history6              1445      6983      3980      3720      7391
  transposition6        1205      5159      3818      9939      6347
  transposition_k6      1220      3338      2695      3327      4397
  transposition_h6      1329      5744      3669      3511      6947
                  test
name               end45.pos end46.pos end47.pos end48.pos end49.pos
  negaalpha6            2723     11688     14354      9337      6707
  killer6_32            2491      6313      8238      6105      6608
  history6              2902      6068     16889      6299      9535
  transposition6        2120     10377     12686      8672      5633
  transposition_k6      2035      5122      7778      5599      5928
  transposition_h6      2179      5533     14725      6113      8294
                  test
name               end50.pos end51.pos end52.pos end53.pos end54.pos
  negaalpha6           10816     31843      6498     29471     14222
  killer6_32            8119     11697      3956     13370      4067
  history6              6781     19981      8367     13158      4789
  transposition6        9222     29411      5734     25134     12567
  transposition_k6      6826     11206      3598     11054      3530
  transposition_h6      5375     20090      8070     11771      4416
                  test
name               end55.pos end56.pos end57.pos end58.pos end59.pos
  negaalpha6           20688     26438      4485     15619      2592
  killer6_32           13649      6337      4357     12740      2370
  history6             30422      7353      5982     12378      2264
  transposition6       19080     22952      4152     14000      2248
  transposition_k6     12423      5298      4193     10983      2127
  transposition_h6     27967      6018      5387     10597      2062

> xtabs(inode ~ name + test, data=data)
                  test
name               end40.pos end41.pos end42.pos end43.pos end44.pos
  negaalpha6            1302      2769      2491      2416      3143
  killer6_32            1277      2255      2170      1186      2595
  history6              1459      2849      2504      1151      3245
  transposition6        1302      2338      2446      2306      3017
  transposition_k6      1277      1988      2151      1118      2429
  transposition_h6      1430      2592      2439      1124      3287
                  test
name               end45.pos end46.pos end47.pos end48.pos end49.pos
  negaalpha6            2685      5602      4855      5112      2270
  killer6_32            2683      3511      2781      4105      1901
  history6              2927      3243      4742      3879      2924
  transposition6        2581      5307      4504      5037      2040
  transposition_k6      2578      3368      2682      4026      1765
  transposition_h6      2461      3127      4395      3947      2646
                  test
name               end50.pos end51.pos end52.pos end53.pos end54.pos
  negaalpha6            6816      8116      2085      8971      5509
  history6              4578      5938      2701      4077      3167
  killer6_32            6011      4977      2069      4757      3260
  transposition6        6376      7878      1990      8316      5345
  transposition_k6      5750      4947      1940      4282      3038
  transposition_h6      4142      6099      2649      3764      3046
                  test
name               end55.pos end56.pos end57.pos end58.pos end59.pos
  negaalpha6            8782      5578      1911      5514      2643
  killer6_32            6394      2333      1810      3845      2562
  history6             11729      2467      2252      3589      2374
  transposition6        8537      5139      1839      5233      2529
  transposition_k6      6183      2109      1759      3691      2485
  transposition_h6     11182      2267      2100      3325      2300

> xtabs(time ~ name + test, data=data)
                  test
name               end40.pos end41.pos end42.pos end43.pos end44.pos
  negaalpha6            1201      2089      1835      2181      2389
  killer6_32            1236      1871      1672      1489      2107
  history6              1272      2244      1812      1382      2538
  transposition6        1227      1951      1890      2198      2426
  transposition_k6      1308      1740      1822      1470      2123
  transposition_h6      1387      2220      2041      1514      2712
                  test
name               end45.pos end46.pos end47.pos end48.pos end49.pos
  negamax6             58783     84254     57276     56096    103962
  killer6_32            1971      2809      2460      2640      2095
  history6              2091      2592      3613      2470      2483
  transposition6        1859      3714      3293      3026      2061
  transposition_k6      1939      2698      2497      2691      2005
  transposition_h6      2026      2714      3627      2730      2532
                  test
name               end50.pos end51.pos end52.pos end53.pos end54.pos
  negaalpha6            3720      5664      1937      5738      3626
  killer6_32            3410      3707      1849      3680      2527
  history6              2797      4391      2313      3294      2521
  transposition6        3542      5527      1928      5426      3566
  transposition_k6      3335      3733      1824      3418      2431
  transposition_h6      2708      4745      2521      3297      2670
                  test
name               end55.pos end56.pos end57.pos end58.pos end59.pos
  negaalpha6            5587      4255      1793      4273      2051
  killer6_32            4559      2274      1807      3399      1981
  history6              7623      2309      1972      3188      1853
  transposition6        5498      4029      1893      4106      1991
  transposition_k6      4437      2232      1820      3298      2069
  transposition_h6      7493      2321      2116      3143      1963

Transposition Table

Revised: 2011/06/25

探索の手順が変わっても同じ盤面にたどり着くことがある。その盤面からの探索の結果は当然、同じ結果となる。そこで、探索の過程で出てくる各盤面の探索結果を記憶しておき、同じ盤面にたどり着いたときにその探索結果を利用することで、探索にかかるコストを大幅に削減することができる。

記憶する探索結果はminmax値、最善手、そのノードからの探索の深さがある。同じ盤面にたどり着いたときには、探索の深さを比較しそれが十分であれば記憶してあるminmax値と最善手を用いる。もし、探索の深さが足りないときには記憶してある最善手をmove orderingで優先的に用い、新たに得られたminmax値、最善手、探索の深さでtransposition tableを更新する。

しかし、αβ探索では、必ずしもノードの正確な値が得られているわけではない。そこで、αカット、あるいはβカットされた結果のスコアである場合はそのことも保持しておくことで、記録されているスコアが正確な値であるのか、下限値あるいは上限値であるのかが分かる。

別の見方をすると、transposition tableを用いた探索は木構造を対象としていた探索をグラフに対する探索として捉え直したものである。ゲーム木は本来グラフ構造であるといえる。

しかし、すべてのノードを記憶することは探索の最大深さが大きくなるにつれノード数が指数的に増すため難しくなる。そこで、transposition tableはサイズの上限が決められたhash tableを用いて実装される。hash tableのconflictが起こった場合、tableに格納されているノードを書き換えるかどうかでいくつかの戦略が考えられる[1]。

探索の最大の深さが6plyではノード数はそれほど多くなく、すべてのノードをメモリ内に記憶することができるため、ここでは通常のhash tableを用いて実装している。

object TranspositionTable {
  val UNKNOWN = Int.MinValue

  val EXACT = 0
  val ALPHA = -1
  val BETA = 1
}

trait TranspositionTable[N <: Node[N]] {

  var transpositionTable: mutable.Map[BigInt, (Int, Int, Int, Move)] = _

  def initTranspositionTable() {
    transpositionTable = mutable.Map.empty
  }

  def probeNode(node: N, depth: Int, alpha: Int, beta: Int)
        : (Move, Int) = {
    val key = node.toSignature
    if (transpositionTable contains key) {
      val (d, score, flag, best) = transpositionTable(key)
      if (d >= depth) { // d == depth is safer.
        if (flag == TranspositionTable.EXACT) {
          return (best, score)
        } else if (flag == TranspositionTable.ALPHA) {
          if (score <= alpha)
            return (best, alpha)
        } else if (flag == TranspositionTable.BETA) {
          if (score >= beta)
            return (best, beta)
        }
      }
      return (best, TranspositionTable.UNKNOWN)
    }
    return (Move.empty, TranspositionTable.UNKNOWN)
  }

  def recordNode(node: N, depth: Int, score: Int, flag: Int, best: Move) {
    if (best == Move.empty) return
    val key = node.toSignature
    if (transpositionTable contains key) {
      val (d, s, f, b) = transpositionTable(key)
      if (d > depth
          || (d == depth && (f == TranspositionTable.EXACT
                          || flag != TranspositionTable.EXACT)))
        return
    }
    transpositionTable(key) = (depth, score, flag, best)
  }
}

abstract class TranspositionTablePlayer[N <: Node[N]](val maxDepth: Int) extends Player[N] with TranspositionTable[N] {

  override def play(ply: Int, node: N, last: Move): Move = {
    initTranspositionTable()
    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))
    }

    // check transposition table
    val (recordedMove, recordedScore) = probeNode(node, depth, alpha, beta)
    if (recordedScore != TranspositionTable.UNKNOWN)
      return (recordedMove, recordedScore)
    
    var moves = node.possibleMoves().toList

    // use the recorded move if it is available
    if (recordedMove != Move.empty && (moves contains recordedMove)) {
      moves = recordedMove :: (moves filterNot {_ == recordedMove})
    }

    var bestMove = Move.empty
    var alpha_ = alpha
    for (m <- moves) {
      val n = node.play(m).get
      val (_, s) = play(n, -beta, -alpha_, depth - 1)
      if (-s >= beta) {
        // record the node into transposition table
        recordNode(node, depth, beta, TranspositionTable.BETA, m)
        return (m, beta)
      }
      if (-s > alpha_) {
        bestMove = m
        alpha_ = -s
      }
    }

    // record the node into transposition table
    if (alpha_ > alpha)
      recordNode(node, depth, alpha_, TranspositionTable.EXACT, bestMove)
    else
      recordNode(node, depth, alpha, TranspositionTable.ALPHA, bestMove)

    (bestMove, alpha_)
  }

  def score(node: N): Int
}

transposition tableはkiller heuristicやhistory heuristicと組み合わせて用いることができる。
組み合わせることで、同じ盤面がより出やすくなるため、相乗効果が期待できる。

実験結果は、reversiのdepth=6の探索では、killer heuristicとの組み合わせで最も効果があることを示している。


[1] Breuker et al. Replacement schemes for transposition tables. ICCA Journal (1994) vol. 17 (4) pp. 183-193

History Heuristic

History Heuristicではsufficient moveを記録する。sufficient moveとは、cutoffとなった手あるいは、cutoffがなかった場合のbest minmax scoreとなった手のことである。

各moveごとにスコアを保持し、sufficient moveとなるごとにスコアを増やしていく。
各ノードにおいて、move orderingを考える際に、sufficient moveのスコアを用いることで「有望そうな」手を先に調べるというheuristicである。

また、killer heuristicと異なり、同じdepthのmoveだけではなく、すべてのdepthのmoveを考慮する。

trait HistoryHeuristic[N <: Node[N]] {

  val MIN_DEPTH_FOR_HISTORY = 2

  val numHistories: Int

  var historyMoves: mutable.Map[Move, Int] = _

  def initHistory() {
    historyMoves = mutable.Map.empty
  }

  def reorderByHistory(moves: List[Move]): List[Move] = {
    val histList = historyMoves.toList.sortBy(- _._2) map (_._1)
    var is = histList intersect moves
    if (!is.isEmpty)
      is ++ (moves diff is)
    else
      moves
  }

  def recordHistory(best: Move, depth: Int) {
    // depth > 1: Schaeffer, History Heuristic and
    // Alpha-Beta Search Enhancements (1989).
    if (depth >= MIN_DEPTH_FOR_HISTORY) {
      if (historyMoves contains best) {
        historyMoves(best) = historyMoves(best) + (1 << (depth - MIN_DEPTH_FOR_HISTORY))
      } else {
        historyMoves(best) = 1 << (depth - MIN_DEPTH_FOR_HISTORY)
      }
    }
  }

}


abstract class HistoryPlayer[N <: Node[N]](val maxDepth: Int, override val numHistories: Int) extends Player[N] {

  override def play(ply: Int, node: N, last: Move): Move = {
    initHistory()
    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))
    }

    var moves = node.possibleMoves().toList
    var bestMove = Move.empty
    var alpha_ = alpha

    // use history
    moves = reorderByHistory(moves)

    for (m <- moves) {
      val n = node.play(m).get
      val (_, s) = play(n, -beta, -alpha_, depth - 1)
      if (-s >= beta) { // beta cut
        // record the move into history
        recordHistory(m, depth)
        return (m, beta)
      }
      if (-s > alpha_) {
        bestMove = m
        alpha_ = -s
      }
    }

    // record the best move into history
    if (alpha_ > alpha)
      recordHistory(bestMove, depth)

    (bestMove, alpha_)
  }

  def score(node: N): Int
}

スコアには2^{(leafまでのdepth)}を用い、また、leafのそばのnodeではsufficient moveという扱いにはしていない[1]。

実際にreversiでrandom playerを相手にした結果は、killer moveの方がむしろいいという結果に。
reversiだと手が進むと盤面のmarkerの数は増えていくので、ply違いで共通の盤面というのは基本的になく、何手か進んだ後の盤面で共通のいい手というのは盤面の右のほうと左のほうで別々に展開するという状況しかない。

[1] Schaeffer. The history heuristic and alpha-beta search enhancements in practice. Pattern Analysis and Machine Intelligence, IEEE Transactions on (1989) vol. 11 (11) pp. 1203-1212

Killer Moves

αβ探索で最も効率良く枝刈りが行われるのは、一番、最初に選択される探索パスが常に最善のものであるときである。

探索木がuniformであるとは、すべての中間ノードの分岐数が一定の数wであり、すべての端末ノードが同じ高さdにあることという。探索木がuniformであるとすると、MinMax探索はすべてのパスを探索することから調べる端末ノードの数はw^d個だけあるのに対して、αβ探索では最善の場合、w^floor(d/2)+w^ceil(d/2)-1個となる[1]。

つまり、αβ探索を効率良く実行するためには、どの手から探索をするかが重要となり、これをmove orderingとよぶ。

move orderingを改善するための一つの手法としてkiller heuristicという手法がある。これは、探索木のある場所で枝刈りが行われたときに、枝刈りをおこした"killing" moveを、次に同じ深さのノードに到達した際に、その手が可能であれば先に調べるというものである。

NegaAlphaを元にした、プログラムは次のとおり、

trait KillerHeuristic[N <: Node[N]] {

  val numKillerMoves: Int

  var killerMoves: Array[List[Move]] = _

  def initKillerMoves(maxDepth: Int) {
    killerMoves = Array.fill(maxDepth) { List.empty }
  }

  def reorderByKillerMoves(i: Int, moves: List[Move]): List[Move] = {
    val km = killerMoves(i)
    var is = km intersect moves
    if (!is.isEmpty)
      is ++ (moves diff is)
    else
      moves
  }

  def recordKillerMove(i: Int, move: Move) {
    val km = killerMoves(i)
    if (km contains move) {
      killerMoves(i) = move :: (km filterNot (_ == move))
    } else {
      killerMoves(i) = (move :: km) take numKillerMoves
    }
  }

}


abstract class KillerHeuristicPlayer[N <: Node[N]](val maxDepth: Int, override val numKillerMoves: Int) extends Player[N] with KillerHeuristic[N] {

  override def play(ply: Int, node: N, last: Move): Move = {
    initKillerMoves(maxDepth)
    val (m, s) = play(node, Int.MinValue + 1, Int.MaxValue, maxDepth)
    Log.i("killer_moves", numKillerMoves.toString + "," + (killerMoves map { _.length }).mkString(","))
    m
  }

  def play(node: N, alpha: Int, beta: Int, depth: Int): (Move, Int) = {
    if (depth == 0 || node.isTerminal) {
      return (Move.empty, score(node))
    }

    var moves = node.possibleMoves().toList

    // reorder by killer moves
    moves = reorderByKillerMoves(depth - 1, moves)

    // nega-alpha search
    var bestMove = Move.empty
    var alpha_ = alpha
    for (m <- moves) {
      val n = node.play(m).get
      val (_, s) = play(n, -beta, -alpha_, depth - 1)
      if (-s >= beta) { // beta cut
        // record the killer move
        recordKillerMove(depth - 1, m)
        return (m, beta)
      }
      if (-s > alpha_) {
        bestMove = m
        alpha_ = -s
      }
    }
    (bestMove, alpha_)
  }

  def score(node: N): Int
}

深さ6の探索で、保持するkiller move数を変化させて実験した結果は次の通り。αβ探索の結果も比較のためにプロットしている。

killer move数は1つだけのときは、少し悪いが他はほぼ同程度である。

また、1試合あたりの総ノード数の平均を表にすると次のようになる。最も小さなkiller move数が32のときで、αβ探索に対して48.4%の改善となっている。

1        128         16          2         32          4 
 112789.62   98864.71   97492.46  108800.69   93997.23   94617.41 
        64          8 alpha beta 
  96379.85   98554.55  182336.39 

ここで、32のときに最小となっているが、depthが深くなるにつれてkiller move数は増える傾向にあり、depth==6のときに最大30~40個のkiller moveが保持されていた。

killer moveの処理の分、探索が遅くなるが、時間でみてもほぼ同じく33.4%の改善となっている。interior nodeでの重い処理以上に、枝刈りの効果のほうが大きいことが分かる。

1        128         16          2         32          4 
  16365.91   15681.85   15086.16   16000.39   15284.74   14969.75 
        64          8 alpha beta 
  15488.62   15192.91   22964.40 

[1] Knuth, D. E., and Moore, R. W., "An Analysis of Alpha-Beta Pruning". Artificial Intelligence Vol. 6, No. 4, pp. 293–326 (1975).

[2] Akl, S.G., Newborn, M.M., "The principle continuation and the killer heuristic". In Proceedings of the ACM Annual Conference, pp. 82–118 (1977).

MinmaxとAlphaBetaの探索ノード数

実際のreversiで、Minmaxに対してAlphaBetaはどの程度、調べるnode数を削減しているのかを調べた。

ルールを守る範囲で無作為に手を打つplayerを相手に、各plyごとに調べた端末node数をプロットしたものが次の図である。

縦軸はnode数で対数軸となっている。ばらつきがかなりあるが、平均をとったものが次の図となる。
＃偶数手の方が奇数手より調べるnode数が少なくなる傾向があるのはどうしてだろう？

plyごとのnode数の変化に関する傾向はMinmaxとAlphaBetaで違いがみられないので、単純に1試合あたりのnode数の平均を調べると次のようになる。

depth      MinMax   AlphaBeta
    2    1569.445     734.205
    3   13429.935    3182.210
    4  116136.220   11957.795
    5 1225244.320   42139.270
    6          NA  182336.385

大雑把にMinmax手法では探索の深さが１増すごとに9倍程度のnodeを調べていることが分かる。それに対して、AlphaBetaでは探索の深さが１増すごとにおよそ4倍程度のnode数の増加となっている。その結果、探索の深さが深くなるにつれてAlphaBetaの探索node数はMinmaxに比べると劇的に小さなものとなる。

各depthにおける探索時間(ms)は次の通り。

depth    MinMax AlphaBeta
    2   123.035    95.960
    3   910.690   311.085
    4  7931.905  1559.270
    5 73328.305  4320.155
    6        NA 22964.395