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

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

ShogiGUIのバグ？

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

<< info depth 58
<< info depth 59
<< info depth 60
>> stop
<< info depth 61
<< info depth 62
<< info depth 63

<< info depth 58

<< info depth 59

<< info depth 60

>> stop

<< info depth 61

<< info depth 62

<< info depth 63

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

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を作ります。

  // 1クラスターにおけるTTEntryの数
  static const int ClusterSize = 3;

  struct Cluster {
    TTEntry entry[ClusterSize];
    int8_t padding[2]; // 全体を32byteぴったりにするためのpadding
  };

// 1クラスターにおけるTTEntryの数

static const int ClusterSize = 3;

struct Cluster {

TTEntry entry[ClusterSize];

int8_t padding[2]; // 全体を32byteぴったりにするためのpadding

};

置換表の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に格納されているのと等価な動作だと言えるでしょう。

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

namespace CooperativeMate
{
  struct TranspositionTable;

  struct alignas(8) TTEntry {

    // この深さにおいて詰まない
    uint16_t depth() const { return key_depth & 0xffff; }

    // 置換表のエントリーに対して与えられたデータを保存する。上書き動作
    void save(Key128 key_, uint16_t depth) { key_depth = depth | (key_.p(1) & ~UINT64_C(0xffff)); }

    // 与えられたkey_がこのTTEntryに格納されているかを判定する。
    bool found(Key128 key_) const { return ((key_depth ^ key_.p(1)) & ~UINT64_C(0xffff)) == 0; /* 上位48bitが一致するかどうか*/ }

  private:
    friend struct TranspositionTable;

    uint64_t key_depth; // depth 2byte(uint16_t) + key48bit
  };

  struct TranspositionTable {

    // 置換表のなかから与えられたkeyに対応するentryを探す。
    // 見つかったならfound == trueにしてそのTT_ENTRY*を返す。
    // 見つからなかったらfound == falseで、このとき置換表に書き戻すときに使うと良いTT_ENTRY*を返す。
    TTEntry* probe(const Key128 key, bool& found) const
    {
      TTEntry* const tte = &table[(size_t)key.p(0) & (entryCount - 1)];
      return found = tte->found(key), tte;
    }

    // 置換表のサイズを変更する。mbSize == 確保するメモリサイズ。MB単位。
    void resize(size_t mbSize) {
      free(table);
      entryCount = UINT64_C(1) << msb(mbSize * 1024 * 1024 / sizeof(TTEntry) );
      table = (TTEntry*)calloc(entryCount * sizeof(TTEntry), 1);

      if (!table)
      {
        std::cout << "failed to calloc\n";
        exit(EXIT_FAILURE);
      }
    }

    // 置換表のエントリーの全クリア
    void clear() { memset(table, 0, entryCount * sizeof(TTEntry)); }

    TranspositionTable() { table = nullptr; resize(16); }
    ~TranspositionTable() { free(table); }

    // 確保されているTTEntryの先頭
    TTEntry* table;

    size_t entryCount;
  };

  extern TranspositionTable TT;

} // end of namespace

namespace CooperativeMate

{

struct TranspositionTable;

struct alignas(8) TTEntry {

// この深さにおいて詰まない

uint16_t depth() const { return key_depth & 0xffff; }

// 置換表のエントリーに対して与えられたデータを保存する。上書き動作

void save(Key128 key_, uint16_t depth) { key_depth = depth | (key_.p(1) & ~UINT64_C(0xffff)); }

// 与えられたkey_がこのTTEntryに格納されているかを判定する。

bool found(Key128 key_) const { return ((key_depth ^ key_.p(1)) & ~UINT64_C(0xffff)) == 0; /* 上位48bitが一致するかどうか*/ }

private:

friend struct TranspositionTable;

uint64_t key_depth; // depth 2byte(uint16_t) + key48bit

};

struct TranspositionTable {

// 置換表のなかから与えられたkeyに対応するentryを探す。

// 見つかったならfound == trueにしてそのTT_ENTRY*を返す。

// 見つからなかったらfound == falseで、このとき置換表に書き戻すときに使うと良いTT_ENTRY*を返す。

TTEntry* probe(const Key128 key, bool& found) const

{

TTEntry* const tte = &table[(size_t)key.p(0) & (entryCount - 1)];

return found = tte->found(key), tte;

}

// 置換表のサイズを変更する。mbSize == 確保するメモリサイズ。MB単位。

void resize(size_t mbSize) {

free(table);

entryCount = UINT64_C(1) << msb(mbSize * 1024 * 1024 / sizeof(TTEntry) );

table = (TTEntry*)calloc(entryCount * sizeof(TTEntry), 1);

if (!table)

{

std::cout << "failed to calloc\n";

exit(EXIT_FAILURE);

}

// 置換表のエントリーの全クリア

void clear() { memset(table, 0, entryCount * sizeof(TTEntry)); }

TranspositionTable() { table = nullptr; resize(16); }

~TranspositionTable() { free(table); }

// 確保されているTTEntryの先頭

TTEntry* table;

size_t entryCount;

};

extern TranspositionTable TT;

} // end of namespace

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

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

X = 1 << msb(X);

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

探索部本体の修正

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

  {
    bool found;
    Key128 key = pos.state()->long_key();
    auto tte = TT.probe(key , found); // 置換表がヒットするか
    if (found && tte->depth() >= depth)
      return;
      // このnodeに関しては現在の残り探索深さ以上の深さにおいて
      //不詰めが証明されているのでもう帰ってよい。(枝刈り)

	(中略)

    // このnodeに関して残り探索深さdepthについては詰みを調べきったので不詰めとして扱い、置換表に記録しておく。
    tte->save(key, depth);
  }

{

bool found;

Key128 key = pos.state()->long_key();

auto tte = TT.probe(key , found); // 置換表がヒットするか

if (found && tte->depth() >= depth)

return;

// このnodeに関しては現在の残り探索深さ以上の深さにおいて

//不詰めが証明されているのでもう帰ってよい。(枝刈り)

(中略)

// このnodeに関して残り探索深さdepthについては詰みを調べきったので不詰めとして扱い、置換表に記録しておく。

tte->save(key, depth);

}

ここまでのまとめ

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

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

次回に続きます。