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).