History Heuristic

History Heuristicではsufficient moveを記録する。sufficient moveとは、cutoffとなった手あるいは、cutoffがなかった場合のbest minmax scoreとなった手のことである。

各moveごとにスコアを保持し、sufficient moveとなるごとにスコアを増やしていく。
各ノードにおいて、move orderingを考える際に、sufficient moveのスコアを用いることで「有望そうな」手を先に調べるというheuristicである。

また、killer heuristicと異なり、同じdepthのmoveだけではなく、すべてのdepthのmoveを考慮する。

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

  val MIN_DEPTH_FOR_HISTORY = 2

  val numHistories: Int

  var historyMoves: mutable.Map[Move, Int] = _

  def initHistory() {
    historyMoves = mutable.Map.empty
  }

  def reorderByHistory(moves: List[Move]): List[Move] = {
    val histList = historyMoves.toList.sortBy(- _._2) map (_._1)
    var is = histList intersect moves
    if (!is.isEmpty)
      is ++ (moves diff is)
    else
      moves
  }

  def recordHistory(best: Move, depth: Int) {
    // depth > 1: Schaeffer, History Heuristic and
    // Alpha-Beta Search Enhancements (1989).
    if (depth >= MIN_DEPTH_FOR_HISTORY) {
      if (historyMoves contains best) {
        historyMoves(best) = historyMoves(best) + (1 << (depth - MIN_DEPTH_FOR_HISTORY))
      } else {
        historyMoves(best) = 1 << (depth - MIN_DEPTH_FOR_HISTORY)
      }
    }
  }

}


abstract class HistoryPlayer[N <: Node[N]](val maxDepth: Int, override val numHistories: Int) extends Player[N] {

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

    var moves = node.possibleMoves().toList
    var bestMove = Move.empty
    var alpha_ = alpha

    // use history
    moves = reorderByHistory(moves)

    for (m <- moves) {
      val n = node.play(m).get
      val (_, s) = play(n, -beta, -alpha_, depth - 1)
      if (-s >= beta) { // beta cut
        // record the move into history
        recordHistory(m, depth)
        return (m, beta)
      }
      if (-s > alpha_) {
        bestMove = m
        alpha_ = -s
      }
    }

    // record the best move into history
    if (alpha_ > alpha)
      recordHistory(bestMove, depth)

    (bestMove, alpha_)
  }

  def score(node: N): Int
}

スコアには2^{(leafまでのdepth)}を用い、また、leafのそばのnodeではsufficient moveという扱いにはしていない[1]。

実際にreversiでrandom playerを相手にした結果は、killer moveの方がむしろいいという結果に。
reversiだと手が進むと盤面のmarkerの数は増えていくので、ply違いで共通の盤面というのは基本的になく、何手か進んだ後の盤面で共通のいい手というのは盤面の右のほうと左のほうで別々に展開するという状況しかない。

[1] Schaeffer. The history heuristic and alpha-beta search enhancements in practice. Pattern Analysis and Machine Intelligence, IEEE Transactions on (1989) vol. 11 (11) pp. 1203-1212