はじめに
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つ目の手としか重複チェックをしない（キュー構造になっている）ことには合理的な理由があったのです。