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と同じになる。