連載やねうら王miniを強くしよう!3日目

今回は、Clusterを用いた置換表について説明します。

ShogiGUIのバグ?

ShogiGUI上で協力詰めを解かせているときに別の作業をしていると何故か探索深さが深くならないのでログをチェックしたら”stop”が送られてきていました。原因はよくわかりません。

※ 誰か原因がわかる人はコメント欄にコメントお願いします。

ShogiGUIにフォーカスがあるときに「Ctrl + V」が押されると”quit”が送られてきたりするようです。上の”stop”が送られてくる現象とは違うようですけども、こういう変なキーボードショートカット、わりと困ります。

協力詰めは簡単?

普通の探索や詰将棋ですと手数が伸びるとそこそこ組み合わせ爆発を起こすのですが、協力詰めの場合、そこまで組み合わせ爆発を起こさないようです。(王手にも限度がありますし、ちょっと攻め駒を渡すとすぐに詰みますし…)

しかし前回の67手詰めには数時間を要するようでした。
そこで置換表を用いて詰まないnodeについて何らかの情報を記録していきます。

TTEntryに何を保存したいか?

置換表は以前にも実装しました。

置換表を作るときは、TTEntry(置換表の1エントリー)に何を保存したいのかを考えます。
今回は、「そのnodeからN手で詰まない」ときにそのことを保存しておくとします。

こうしておけば、同じnodeに到達したときにN以下しか残り探索depthがなければ詰まないことは証明されていますから、それ以上このnodeについて調べる必要がありません。

しかし置換表には膨大なメモリを必要とするので、なるべくなら一つのエントリー(TTEntry)は小さめにしたいです。

昔は、メモリアライメントの問題や扱いやすさから、TTEntryは4や8の倍数にするのが流行りました。最近はそうでもないです。このことは次で書きます。

TTEntryによるCluster(クラスター)実装

最近の流行りとしては、TTEntryによるClusterを使う実装があります。

順を追って説明します。

TTEntryを格納する場所は、hash keyの下位bitから求めるというのは以前やりました。

TTEntry* const tte = &table[(size_t)key & (entryCount – 1)];

格納する場所が衝突したときの代替処理(rehash)が必要な場合があります。せっかく探索した結果を格納してあるのにそこを潰すのはもったいないので格納する場所が衝突した場合は、別のところに格納したいことがあります。

これをrehashと呼び、従来は、hash keyに一定の値を足すなどして、再度、上のようにしてTTEntry* を求めて、そこを代替の場所として使う実装が多かったように思います。

しかし、このようなrehashは、そのコストが馬鹿になりませんしプログラムが複雑化します。

そこで、最近では、TTEntryを数個を組にしてClusterを作る方法が主流です。

例えば、sizeof(TTEntry)が10だとしましょう。このときTTEntryを3つ組にして2バイトpaddingして32byteのClusterを作ります。

置換表のprobe() (hash keyに対応するTTEntry*を返す関数)のときに、

1. このClusterのentry[0],[1],[2]のいずれかに値が格納されているかを調べて、値が格納されていれば値が見つかったことにして(found を trueにして)、そのTTEntry*を返します。

2. いずれにも値が格納されていなければ、値は見つからなかったことにして(found を falseにして)、この3つのentryのなかで情報的な価値が一番低そうなものをsave() (TTEntryに値を保存する関数)するためのTTEntry* として返します。

つまり、rehashは(メモリ上に連続した)お隣のentryを見ていくだけで済むので非常に簡単に実装できます。(hashの値は変更していないのでrehashというのも少し変ですが、適切な用語がないのでここではそう呼んでおきます。)

さらに素晴らしいことに、CPUのcache lineは通例、64byteで、(64byteにalignmentされた)先頭の1バイト目をアクセスしたときに、この64byteのブロックの残りがCPU cacheに読み込まれます。

すなわち、置換表のTTEntryを数個集めて64の約数か倍数になるClusterを作ってしまえば、rehashのときにそれらはすでにCPU cacheに格納されているので素早く値を取り出すことが出来ます。

今回のTTEntry

今回はClusterまでは実装しませんが(近いうちにやります)、まずはTTEntryを8の倍数にはしておきます。

depth(2バイト)を格納しないといけませんから、hash keyを6バイト(48bit)格納することにしましょう。hashのEntryの格納場所としてhash keyの下位の数十bitを用いますから、結局、これでも64bit程度のhash keyが格納されているのと同じ意味があります。

具体的に計算して確認しておきましょう。仮に置換表に16GBを割り当てるとしたら、TTEntryが8byteなら、TTEntryの数は16GB/8 = 2G個。格納場所が2G個あり、hash keyの下位21bit(2^21 = 2G)で格納場所を決める実装だとすれば、TTEntryに格納されている48bit + TTEntryの格納場所の21bit = 69bitあります。

この場合、64bitを超えているので、TTEntryに6バイトしかhash keyを格納していなくともこれで十分であることがわかります。

なお、やねうら王miniではHash Keyを128bit化することが出来るので、このHash Keyの下位21bitでTTEntryの格納場所を決めて、上位48bitをTTEntryに格納するという実装にすれば、実際に69bitのhash keyがTTEntryに格納されているのと等価な動作だと言えるでしょう。

今回の置換表の実装コード

ここまでの説明が理解できていれば、depthが2バイトで足りないときに3バイトにして、hash keyを6バイトではなく5バイトにするだとかいう変更も簡単でしょう。

上のソースコード中のresize()に出てくるmsb()というのは、最上位bitのbit位置を返す関数です。2のべき乗の個数だけTTEntryを確保したいので、

X = 1 << msb(X);

のようにすれば、Xの最上位bit以外のbitを0とみなした値が得られるという理屈です。

探索部本体の修正

探索部本体の修正として、この置換表のprobe()とTTEntryへのsave()のコードを追加するだけです。

ここまでのまとめ

置換表に何を格納したいか考える→置換表を実装する→置換表を使ってみる
という流れにもいい加減慣れてきたかと思います。

さて、置換表を実装した驚異の結果は..?

次回に続きます。

連載やねうら王miniを強くしよう!3日目」への5件のフィードバック

  1. >ShogiGUIのバグ?

    今年もよろしくお願いします
    将棋所で試してみてはどうでしょうか
    私はkif for windowsのツールメニューというのは使ったことがないのでよく分かりませんが、いつもkif for windowsで局面コピーして将棋所に貼りつけています。

    • はい、将棋所では問題なさそうです。このへん、長年使われているだけあって、動作的には将棋所のほうがいくぶん安定はしているように思います。

  2. >1. このClusterのentry[0],[1],[2]のいずれかに値が格納されているかを調べて、値が格納されていれば値が見つかったことにして(found を trueにして)、そのTTEntry*を返します。

    >2. いずれにも値が格納されていなければ、値は見つからなかったことにして(found を falseにして)、この3つのentryのなかで情報的な価値が一番低そうなものをsave() (TTEntryに値を保存する関数)するためのTTEntry* として返します。

    やっぱりよくわかりません。

    1、は3つある場所のどこかにすでに値が格納されている、、、のですよね。
    だから、その場所をさけて次の場所に格納する。

    2、は3つある場所がすべて空。
    だから、どこに格納しても良い?
    そうすると
    >この3つのentryのなかで情報的な価値が一番低そうなもの・・・
    これはいったい何でしょう?

    すみません、よろしくお願いします。

野菜凝縮 へ返信する コメントをキャンセル

メールアドレスが公開されることはありません。 が付いている欄は必須項目です