誰も教えてくれないKiller Moveが2個な理由

  • 7
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

はじめに

3年くらい前にはてなダイアリーに書いたものですが、個人的にお気に入りな記事だったのでサルベージして加筆修正してみました。

強いコンピュータチェスやコンピュータ将棋のプログラムには、思わぬ細かいところに重要な工夫があったりします。
この記事は、その重要な工夫の一つである、Killer Moveの実装方法の話です。

Killer Moveとは

皆様ご存じのとおり、βカットした手を覚えておいて兄弟局面でもオーダリングの上位で試してみる、という手法です。

最近誰も彼もが読んでいる(?)Stockfishの実装でも、βカットした取る手以外の指し手を以下のような形で記録します。

    if (ss->killers[0] != move)
    {
        ss->killers[1] = ss->killers[0];
        ss->killers[0] = move;
    }

この実装には以下の2つのポイントがあります。

  • Killer Moveを保持する数は、1個でも3個以上でもなく2個。
  • 保存する条件は、ss->killers[1] != move は無しで ss->killers[0] != move だけ。

これらについての考察を自分は見たことが無いのですが、実はどちらにもちゃんと理由があります。

解説

まず、Killer Moveのリストに入る可能性のある手を、以下の2つに分類してみましょう。

  • 入っているとうれしい指し手(良いKiller Move)
  • 入っていてもうれしくない手(悪いKiller Move)

良いKiller Moveとなるのは、以下の条件を満たす手です。

  • 多くの兄弟局面で合法手、かつ、多くの兄弟局面でβカットを発生させる程度に良い手

悪いKiller Moveとなるのは、以下の条件のうちのいずれかを満たす手になります。

  • 多くの兄弟局面でβカットを発生させない手(特定の状況下でのみ良い手)
  • 多くの兄弟局面で非合法手

これを元にKiller Moveのリストで保持すべき手の数を考えてみましょう。

まず、Killer Moveを1手しか保持しない場合。
これの弊害は簡単で、良いKiller Moveを保持していてもたまたまβカットしなかった局面があったときに、悪いKiller Moveで置き換えられてしまい、その後の探索でまた良いKiller Moveが出現するまで「あまりKiller Moveの効果が発揮されない」という状態が発生します。

次に、2手保持した場合。
上記の現象が起こった場合、Killer Moveのリストは↓こうなります。

  • ss->killers[0] ← 悪いKiller Move
  • ss->killers[1] ← 良いKiller Move

この状態で次の兄弟ノードの探索に入ると、まず悪いKiller Moveが先に探索されます。
ただし、悪いKiller Moveは、その定義通り、βカットが発生する可能性や、そもそも合法手である可能性が低いです。
また、仮にβカットされた場合も、ss->killers[0] != moveの条件によりKiller Moveのリストは更新されません。

βカットが発生しなかったとすると、次に、良いKiller Moveが探索されます。
この手でβカットが発生する確率はそれなりに高い[要出典]です。
そして、βカットが発生すると、Killer Moveのリストが更新されて↓こうなります。

  • ss->killers[0] ← 良いKiller Move
  • ss->killers[1] ← 悪いKiller Move

これでまた「良いKiller Moveでβカットせず、他の手でβカットした局面」が出現するまでは、良いKiller Moveの地位は安泰です。
この動作になるために、ss->killers[1] != moveという条件は入れてはならないのです。

更に、良いKiller Moveでもβカットしなかった場合、その局面はそもそもβカットしない可能性がかなり高い[要出典]です。
その場合、Killer Moveのリストは更新されないため、良いKiller Moveは保持され続けます。

つまり、2手保持する実装で、一度発見した良いKiller Moveが失われるには、以下のような手順が必要になるのです。

  • 良いKiller Moveでβカットが発生せず、かつ他の指し手でβカットが発生。
  • その後更に、まだ残っている良いKiller Moveでβカットが発生する前に、Killer Moveでβカットせず、他の指し手でβカットが発生。

この手順の発生する確率がとても小さい[要出典]為に、3個以上保持するメリットが薄いのです。
また、3つもKiller Moveで上位に持ってくる事になると、その分他の指し手が後回しになるというデメリットも発生します。

そんなわけで、Killer Moveが2個であることや、1つ目の手としか重複チェックをしない(キュー構造になっている)ことには合理的な理由があったのです。