Negamax

Minmaxの実装をみると、playとplayOpponentが最大の評価値となる手を探すか、最小の評価値となる手を探すかを除いて、同じであることが分かる。max{x} = -min{-x} であることに注目すると、これらを一つの関数にまとめることができる。これは実装上のテクニックであって、探索手法としては同じであるが、このテクニックを用いて書いたMinmaxアルゴリズムをNegamaxとよぶことがある。

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

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

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

もちろん、強さはMinmaxと同じ。

negamax2 D: 48, minmax2 L: 49, -: 3
minmax2 D: 52, negamax2 L: 45, -: 3