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という。