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

Nega Alpha-Beta

Alpha-Beta探索もMinmax探索同様にnega-実装によってコードサイズをほぼ半分にできる。
コードサイズが半分になるとキャッシュが効いて速く・・・となるかどうかは確認していない。

abstract class NegaAlphaBetaPlayer[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_ = alpha
    for (m <- moves) {
      val n = node.play(m).get
      val (_, s) = play(n, -beta, -alpha_, depth - 1)
      if (-s >= beta) { // beta cut
        return (m, beta)
      }
      if (-s > alpha_) {
        bestMove = m
        alpha_ = -s
      }
    }
    (bestMove, alpha_)
  }

  def score(node: N): Int
}

- Int.MinValue がIntから桁あふれしてしまうことに注意。

探索木はminノードのスコアが反転する以外はalpha-betaと同じになる。

Alpha-Beta

branch-and-boundはmin{bound, max{...}, ...}という計算を考えるとmaxの中にbound以上の値が出たときには、それ以上maxの中を考える必要がないということに基づいて枝刈りを行う。max{bound, min{...}, ...}も同様である。

さらに、この考えを進めることができる。max{2, min{max{min{3, 2, ...}, max{...}, ....}, min{...}, ...}, ...}という探索木を考える。min{3, 2, となったところで、このminが2以下の値を返すことが確実になる。するとこの値を取り囲むmaxおよびminがこの値をたとえ採用したとしても、もっとも外側のmaxがこの値（関係した手）を採用することがないことが分かる。

つまり、maxの計算である時点での最大値αはそれが含むすべてのminの計算を続けるかを判断する際の下限値となる。同様に、minの計算における最小値βはmaxの計算の下限値となる。

この上限値αと下限値βを用いた探索をαβ探索と呼ぶ。プログラムは次のようになる。

abstract class AlphaBetaPlayer[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, 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_ = alpha
    for (m <- moves) {
      val n = node.play(m).get
      val s = playOpponent(n, alpha_, beta, depth - 1)
      if (s >= beta) { // beta cut
        return (m, beta)
      }
      if (s > alpha_) {
        bestMove = m
        alpha_ = s
      }
    }
    (bestMove, alpha_)
  }

  def playOpponent(node: N, alpha: Int, beta: Int, depth: Int): Int = {
    if (depth == 0 || node.isTerminal) {
      return score(node)
    }
    val moves = node.possibleMoves()
    var beta_ = beta
    for (m <- moves) {
      val n = node.play(m).get
      val s = play(n, alpha, beta_, depth - 1)._2
      if (s <= alpha) { // alpha cut
        return alpha
      }
      if (s < beta_) {
        beta_ = s
      }
    }
    beta_
  }

  def score(node: N): Int
}

探索木は次のようになる。branch-and-boundとの差は4段以上の探索で見られ、3, 2, 7となるところの7や、0, 9, 7の9, 7など、探索された端末ノードはさらに5つ減り31個になった。このようにbranch-and-boundに比べ深いノードへと影響を与えることから、このような枝刈りをdeep-cutoffという。

Branch and Bound

次の図は[Knuth75]に出てくる円周率πの少数以下80桁目までの数をノードのスコアとみなした分岐数3、深さ4ゲーム木をMinmaxによって探索した様子である。

# 解像度が...

この探索木を左下からみていく。左下は相手の番である。このとき3つの手に対する3, 1, 4というスコアに対して、相手は最も小さなスコアmin{3, 1, 4} = 1となる手を選択すると考えられる。つまり、その直上のノードである、自分の番では最初の手を一番左となる手を選ぶと1となることが分かった。そこで、このノードでの自分のスコアはmax{1, _, _}であることから、少なくとも1以上であることが保証された。では、その次の手を選んだときの相手の手を考えると、まず1となる手があることが分かる。すると、このあと2つの手を考慮することなく、min{1, _ , _} <= 1であることから、自分がこの手を選んでも1より大きなスコアとなることはないことが分かる。つまり、残り2つの手を調べる必要がないことが分かる。このように探索木の一部をスキップすることを枝刈りという。

自分の番においても同様に枝刈りを行うことができる。3141..265まで調べたところで、自分の番において、少なくとも2となる手があることが分かる。すると、その上のノードである相手の番では2より小さなスコアとなる手を探すことになる。しかし、その次の探索でmin{3, 5, 8} = 3ことから、この手を選ぶことで自分は少なくとも3以上のスコアを得ることができることが分かる。もちろん、相手はこの手を選ばないだろう。そこで、残りの979323となる探索はすべてスキップされる。

このような手法をbranch-and-bound探索と呼ぶ。プログラムにすると次のようになる。

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

  override def play(node: N, last: Move): Move = {
    val (m, s) = play(node, Int.MaxValue, maxDepth)
    m
  }

  def play(node: N, bound: Int, depth: Int): (Move, Int) = {
    if (depth == 0 || node.isTerminal) {
      return (Move.empty, score(node))
    }
    val moves = node.possibleMoves(marker)
    var nextMove = Move.empty
    var maxS = Int.MinValue
    breakable {
      for (m <- moves) {
        val n = node.play(m).get
        val s = playOpponent(n, maxS, depth - 1)
        if (s > maxS) {
          nextMove = m
          maxS = s
        }
        if (s >= bound) break
      }
    }
    (nextMove, maxS)
  }

  def playOpponent(node: N, bound: Int, depth: Int): Int = {
    if (depth == 0 || node.isTerminal) {
      return score(node)
    }
    val moves = node.possibleMoves(opponentMarker)
    var minS = Int.MaxValue
    breakable {
      for (m <- moves) {
        val n = node.play(m).get
        val s = play(n, minS, depth - 1)._2
        if (s < minS) {
          minS = s
        }
        if (s <= bound) break
      }
    }
    minS
  }

  def score(node: N): Int
}

このプログラムを用いることで得られる探索木は次のとおり。

Minmaxは探索木に対する全探索手法であり、81個の端末ノードを調べたのに対して、branch-and-boundでは36個の端末ノードしか調べていない。

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

Minmax searchの視覚化