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.