Transposition Table

Revised: 2011/06/25

探索の手順が変わっても同じ盤面にたどり着くことがある。その盤面からの探索の結果は当然、同じ結果となる。そこで、探索の過程で出てくる各盤面の探索結果を記憶しておき、同じ盤面にたどり着いたときにその探索結果を利用することで、探索にかかるコストを大幅に削減することができる。

記憶する探索結果はminmax値、最善手、そのノードからの探索の深さがある。同じ盤面にたどり着いたときには、探索の深さを比較しそれが十分であれば記憶してあるminmax値と最善手を用いる。もし、探索の深さが足りないときには記憶してある最善手をmove orderingで優先的に用い、新たに得られたminmax値、最善手、探索の深さでtransposition tableを更新する。

しかし、αβ探索では、必ずしもノードの正確な値が得られているわけではない。そこで、αカット、あるいはβカットされた結果のスコアである場合はそのことも保持しておくことで、記録されているスコアが正確な値であるのか、下限値あるいは上限値であるのかが分かる。

別の見方をすると、transposition tableを用いた探索は木構造を対象としていた探索をグラフに対する探索として捉え直したものである。ゲーム木は本来グラフ構造であるといえる。

しかし、すべてのノードを記憶することは探索の最大深さが大きくなるにつれノード数が指数的に増すため難しくなる。そこで、transposition tableはサイズの上限が決められたhash tableを用いて実装される。hash tableのconflictが起こった場合、tableに格納されているノードを書き換えるかどうかでいくつかの戦略が考えられる[1]。

探索の最大の深さが6plyではノード数はそれほど多くなく、すべてのノードをメモリ内に記憶することができるため、ここでは通常のhash tableを用いて実装している。

object TranspositionTable {
  val UNKNOWN = Int.MinValue

  val EXACT = 0
  val ALPHA = -1
  val BETA = 1
}

trait TranspositionTable[N <: Node[N]] {

  var transpositionTable: mutable.Map[BigInt, (Int, Int, Int, Move)] = _

  def initTranspositionTable() {
    transpositionTable = mutable.Map.empty
  }

  def probeNode(node: N, depth: Int, alpha: Int, beta: Int)
        : (Move, Int) = {
    val key = node.toSignature
    if (transpositionTable contains key) {
      val (d, score, flag, best) = transpositionTable(key)
      if (d >= depth) { // d == depth is safer.
        if (flag == TranspositionTable.EXACT) {
          return (best, score)
        } else if (flag == TranspositionTable.ALPHA) {
          if (score <= alpha)
            return (best, alpha)
        } else if (flag == TranspositionTable.BETA) {
          if (score >= beta)
            return (best, beta)
        }
      }
      return (best, TranspositionTable.UNKNOWN)
    }
    return (Move.empty, TranspositionTable.UNKNOWN)
  }

  def recordNode(node: N, depth: Int, score: Int, flag: Int, best: Move) {
    if (best == Move.empty) return
    val key = node.toSignature
    if (transpositionTable contains key) {
      val (d, s, f, b) = transpositionTable(key)
      if (d > depth
          || (d == depth && (f == TranspositionTable.EXACT
                          || flag != TranspositionTable.EXACT)))
        return
    }
    transpositionTable(key) = (depth, score, flag, best)
  }
}

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

  override def play(ply: Int, node: N, last: Move): Move = {
    initTranspositionTable()
    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))
    }

    // check transposition table
    val (recordedMove, recordedScore) = probeNode(node, depth, alpha, beta)
    if (recordedScore != TranspositionTable.UNKNOWN)
      return (recordedMove, recordedScore)
    
    var moves = node.possibleMoves().toList

    // use the recorded move if it is available
    if (recordedMove != Move.empty && (moves contains recordedMove)) {
      moves = recordedMove :: (moves filterNot {_ == recordedMove})
    }

    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) {
        // record the node into transposition table
        recordNode(node, depth, beta, TranspositionTable.BETA, m)
        return (m, beta)
      }
      if (-s > alpha_) {
        bestMove = m
        alpha_ = -s
      }
    }

    // record the node into transposition table
    if (alpha_ > alpha)
      recordNode(node, depth, alpha_, TranspositionTable.EXACT, bestMove)
    else
      recordNode(node, depth, alpha, TranspositionTable.ALPHA, bestMove)

    (bestMove, alpha_)
  }

  def score(node: N): Int
}

transposition tableはkiller heuristicやhistory heuristicと組み合わせて用いることができる。
組み合わせることで、同じ盤面がより出やすくなるため、相乗効果が期待できる。

実験結果は、reversiのdepth=6の探索では、killer heuristicとの組み合わせで最も効果があることを示している。


[1] Breuker et al. Replacement schemes for transposition tables. ICCA Journal (1994) vol. 17 (4) pp. 183-193