Qhapaq Lab

Late Move Reductions

Late Move Reductions（LMR）は、手の順序の後ろに出てくる手を浅く読むことで探索量を減らす手法である。 手の並べ替えが良いほど、 後ろの手は有望でない可能性が高いので、深さを減らしても強さを保ちやすい。

概要

典型的には、

  • 最初の数手は通常深さで読む
  • それ以降の手は深さを R だけ減らして読む
  • 減らした探索で fail-high した手だけ通常深さで再探索する

という流れを取る。

この考え方は、

と並んで、現代的探索の強力な高速化技術のひとつである。

なぜ有効か

反復深化と手の並べ替えがうまく働いていれば、 有望な手はだいたい先頭付近に来る。

そのため、後ろの手は

  • たいてい悪い
  • 少し浅く読んでも cut される

ことが多い。

実装例

int searchMoves(Position pos, int depth, int alpha, int beta) {
    int moveCount = 0;

    for (Move move : generateMoves(pos)) {
        ++moveCount;
        Position next = doMove(pos, move);

        int reduction = 0;
        if (depth >= 3 && moveCount > 3 && isQuiet(move)) {
            reduction = 1;
        }

        int score = -search(next, depth - 1 - reduction, -alpha - 1, -alpha);

        if (reduction > 0 && score > alpha) {
            score = -search(next, depth - 1, -beta, -alpha);
        }

        if (score >= beta) {
            return score;
        }
        if (score > alpha) {
            alpha = score;
        }
    }

    return alpha;
}

現代エンジンでは、depth と moveCount の両方に応じて reduction 量を変えることが多い。

reduction を変える材料

  • 深いノードほど多く減らす
  • 後ろの手ほど多く減らす
  • 王手の手や捕獲手は減らしにくくする
  • history heuristicが高い手は減らしにくくする
  • cut-node 予想では多めに減らす

将棋AIでの位置づけ

将棋は分岐数が大きいため、LMR の効果が出やすい。 一方で、

  • 王手
  • 受け
  • 成り
  • 駒の取り合い

のような戦術的な手は、後ろに並んでいても重要な場合がある。 そのため、どの手を reduction の対象にするかは慎重な設計が必要である。

注意点

  • 手の並べ替えが悪いと、有望手を浅く読んでしまう危険がある
  • reduction しすぎると tactical miss が増える
  • 再探索条件をどう置くかで強さが大きく変わる

関連項目

参考にしたホームページ