連載やねうら王miniで遊ぼう！8日目

今回は、置換表の仕組みとその実装について説明します。

perftの高速化のための置換表を実装する

まず前回の宿題。perftの高速化のための置換表を実装するところから。

// perftで用いる置換表
namespace Perft {
  struct TTEntry {
    void save(HASH_KEY key_, PerftSolverResult& result_)
    {
      key = key_;
      result = result_;
    }
    HASH_KEY key;
    PerftSolverResult result;
  };

  struct TranspositionTable {
    TranspositionTable() {
      entryCount = 256*1024*1024; // * sizeof(PerftSolverResult) == 15GBほど
      table = (TTEntry*)calloc( entryCount * sizeof(TTEntry) , 1);
    }
    ~TranspositionTable() { free(table); }

    TTEntry* probe(const HASH_KEY key_,int depth,bool& found)
    {
      auto key = key_ ^ DepthHash(depth); // depthの分だけhash keyを変更しておく。
      auto& tte = table[key /*.p(0)*/ & (entryCount - 1)];
      found = (tte.key == key_); // 変更前のhash keyが書かれているはず
      return &tte;
    }
  private:
    TTEntry* table;
    size_t entryCount; // TTEntryの数
  };
  TranspositionTable TT;
}

// perftで用いる置換表

namespace Perft {

struct TTEntry {

void save(HASH_KEY key_, PerftSolverResult& result_)

{

key = key_;

result = result_;

}

HASH_KEY key;

PerftSolverResult result;

};

struct TranspositionTable {

TranspositionTable() {

entryCount = 256*1024*1024; // * sizeof(PerftSolverResult) == 15GBほど

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

}

~TranspositionTable() { free(table); }

TTEntry* probe(const HASH_KEY key_,int depth,bool& found)

{

auto key = key_ ^ DepthHash(depth); // depthの分だけhash keyを変更しておく。

auto& tte = table[key /*.p(0)*/ & (entryCount - 1)];

found = (tte.key == key_); // 変更前のhash keyが書かれているはず

return &tte;

}

private:

TTEntry* table;

size_t entryCount; // TTEntryの数

};

TranspositionTable TT;

}

TTEntryが置換表の1エントリーで、これをentryCount個だけ確保して、hash keyの下位bitをindexとして、置換表にアクセスする。entryCountは2のべき乗にしておけば、(entryCount – 1)でマスクする(& をする)と、indexの値が求まる。

※　この意味がわからない人は、PCの電卓を起動して、プログラマー電卓モードで2進数で10000000と入力して1引いてみること。これは、01111111という答えになる。これとマスクする。

2のべき乗にしなくとも

table[key % entryCount]

としてもだいたい同じ意味ではあるが、剰余の計算やや遅いというのと、(厳密には)一様分布でないのが、少し気になる。

※　一様分布の意味がわからない人はggrks。例えば、0から(n-1)までの乱数をrand() % n とかしてしまうと一様分布にならない。

※　このへん、bit演算に慣れていない人には説明わかりにくいみたいなので、追記。ここまでの話がわかりにくい人は、10進数で考えてみるといいかも。100で割った余りは下2桁を見ればよい。同様に2進数でもこれと同じ理屈が成り立つ。100b(末尾のbは２進数表記であるの意味)で割った余りも2進数表記の下2桁を見ればよい。なので、例えば100000bで割った余りは、2進数表記での下5桁を見れば良いわけであるが、2進数表記での下5桁というのは、11111bで & したものに等しい。なので、100000bのようにどこかひとつだけ1のbitがある数字(2のべき乗)から1を引いて11111bのようになったあと、これと & を取ると元の100000bで割った余りとなるのである。

あと、置換表のエントリーをCPUのcache line(通例64bytes)の倍数か約数にして、かつ、tableのメモリアライメントを64bytes境界になるように調整したほうが速いことは言うまでもないことではあるが、この実装について興味のある人は、Stockfishのtt.h/tt.cppを見て欲しい。

それから、上のプログラム中に
DepthHash(depth)
というのが出てくるが、これはただの乱数テーブルで、depthに応じた何かしらの乱数値が返ってくる。

本当は、局面のhash値をキーとしてdepthとPerftSolverResultを格納すればいいのであるが、それだと同じ局面のdepth違いの情報が同じTTEntryに格納することになってしまう。

普通、将棋の思考エンジンで用いる置換表では、このようにTTEntryが衝突した場合に、何かしらの方法で格納する。そういう仕組みを用意するのは面倒なので、ここでは、hash値とdepthをキーとしてPerftSolverResultを格納したかったのだ。そこでhash値をdepthも考慮した値にする必要があった。

これは前回説明したように、hash値というのは局面の駒配置などについて加算して求めているので、同じようにdepthに応じた乱数テーブルがあるなら、その値をaddするかxorするかすれば、{ 局面 , depth }という組み合わせに対応するhash値が得られるという考えである。

上のプログラムが置換表の説明および実装として、最小限のプログラムで、これを改良すればどんな置換表でも自由自在に(?)作れるようになるわけだ。

やねうら王miniは将棋思考エンジンフレームワークを標榜するわけであるが、置換表に何を格納するかというのは、どんなプログラムにしたいかで異なってくる。たとえば上のperftの例で言えば、局面とdepthをキーとして、perftの統計情報(PerftSolverResult構造体)をそのまま格納しておきたかった。

このように、将棋エンジンごとに置換表というのは異なるのが自然であるので、無理にやねうら王miniの置換表を使うことはないと思う。置換表はこのように簡単に実装できるのだから。

やねうら王miniではHash Keyを128bit/256bit化できる

「hash keyが64bitだとhash衝突するんじゃね？」という疑問に対しては、やねうら王miniにはHash Keyを128bit/256bit化できる無駄機能があるとお答えしておこう。

※　本当、無駄機能なので、こういう無駄機能を省いて、ソースコードを短くしたやねうら王nanoを別途公開しようかと考えているところである。

さきほどの置換表のソースコード上に

auto& tte = table[key /*.p(0)*/ & (entryCount – 1)];

と書いてあって、この .p(0) とはなんじゃ？と思った人もおられるだろう。これは、Hash Keyを128bitとか256bitにしたときに、下位64bitを得るための呪文である。

hash keyのサイズ自体はshogi.hの冒頭で変更できるようになっている。

// 通例hash keyは64bitだが、これを128にするとPosition::state()->long_key()から128bit hash keyが
// 得られるようになる。研究時に局面が厳密に合致しているかどうかを判定したいときなどに用いる。
// ※　やねうら王nanoではこの機能は削除する予定。
#define HASH_KEY_BITS 64
//#define HASH_KEY_BITS 128
//#define HASH_KEY_BITS 256

// 通例hash keyは64bitだが、これを128にするとPosition::state()->long_key()から128bit hash keyが

// 得られるようになる。研究時に局面が厳密に合致しているかどうかを判定したいときなどに用いる。

// ※　やねうら王nanoではこの機能は削除する予定。

#define HASH_KEY_BITS 64

//#define HASH_KEY_BITS 128

//#define HASH_KEY_BITS 256

この128bit版のHash Keyを選択しているときは以下のKey128が用いられる。SSEの命令が使ってある。256bit版はAVXの命令が使ってある。ゆえにhash値の計算では速度低下はほぼないはずだが、Hash Keyが大きくなるとそれをそのまま置換表に格納する場合、メモリ転送量が増えてメモリ帯域を圧迫するので当然ながら遅くなる。このへんに注意して使うなら、128bit Hash Keyは実用になる気がしなくもないのだが…。(128bitもあれば置換表から取ってきた指し手の合法性をチェックしなくともいいと思うのでむしろ速くなる可能性もあるわけで…)

// 64bit版
typedef uint64_t Key64;

// 128bit版
struct Key128
{
  __m128i m;

  Key128() {}
  Key128(const Key128& bb) { _mm_store_si128(&this->m, bb.m); }
  Key128& operator = (const Key128& rhs) { _mm_store_si128(&this->m, rhs.m); return *this; }

  void set(Key k0, Key k1) { m.m128i_u64[0] = k0; m.m128i_u64[1] = k1; }
  Key key64() const { return m.m128i_u64[0]; }
  uint64_t p(int i) const { return m.m128i_u64[i]; }

  Key128& operator += (const Key128& b1) { this->m = _mm_add_epi64(m, b1.m); return *this; }
  Key128& operator -= (const Key128& b1) { this->m = _mm_sub_epi64(m, b1.m); return *this; }
  Key128& operator ^= (const Key128& b1) { this->m = _mm_xor_si128(m, b1.m); return *this; }

  Key128& operator *= (int64_t i) { m.m128i_u64[0] *= i; m.m128i_u64[1] *= i; return *this; }
  bool operator == (const Key128& rhs) const {
    return (_mm_testc_si128(_mm_cmpeq_epi8(this->m, rhs.m), _mm_set1_epi8(static_cast<char>(0xffu))) ? true : false);
  }
  bool operator != (const Key128& rhs) const { return !(*this == rhs); }

  Key128 operator * (const int64_t i) const { return Key128(*this) *= i; }
  Key128 operator ^ (const Key128& rhs) const { return Key128(*this) ^= rhs; }

};

// 64bit版

typedef uint64_t Key64;

// 128bit版

struct Key128

{

__m128i m;

Key128() {}

Key128(const Key128& bb) { _mm_store_si128(&this->m, bb.m); }

Key128& operator = (const Key128& rhs) { _mm_store_si128(&this->m, rhs.m); return *this; }

void set(Key k0, Key k1) { m.m128i_u64[0] = k0; m.m128i_u64[1] = k1; }

Key key64() const { return m.m128i_u64[0]; }

uint64_t p(int i) const { return m.m128i_u64[i]; }

Key128& operator += (const Key128& b1) { this->m = _mm_add_epi64(m, b1.m); return *this; }

Key128& operator -= (const Key128& b1) { this->m = _mm_sub_epi64(m, b1.m); return *this; }

Key128& operator ^= (const Key128& b1) { this->m = _mm_xor_si128(m, b1.m); return *this; }

Key128& operator *= (int64_t i) { m.m128i_u64[0] *= i; m.m128i_u64[1] *= i; return *this; }

bool operator == (const Key128& rhs) const {

return (_mm_testc_si128(_mm_cmpeq_epi8(this->m, rhs.m), _mm_set1_epi8(static_cast(0xffu))) ? true : false);

}

bool operator != (const Key128& rhs) const { return !(*this == rhs); }

Key128 operator * (const int64_t i) const { return Key128(*this) *= i; }

Key128 operator ^ (const Key128& rhs) const { return Key128(*this) ^= rhs; }

};

128bit/256bit hash keyは64bit hash keyの自然な拡張

もうひとつ、128bit/256bitのhash keyの実装で面白い点を挙げておく。

hash keyを用いて定跡がhitしたかしていないかを判定することがあるが、64bitのhash keyで作られた定跡DBがあるとして、これを128bit keyにしたときに、その定跡DBが使えないことになってしまう。

この問題を回避するために128/256bit hash keyの下位64bitは、64bit hash keyのときのhash値と完全に一致するように実装してある。つまり、64bit hash keyの自然な拡張というわけだ。

どのように実装してあるかと言うと、

#if HASH_KEY_BITS <= 64
#define SET_HASH(x,p0,p1,p2,p3) { x = (p0); (p1); (p2); (p3); }
#elif HASH_KEY_BITS <= 128
// 関数の引数に直接書くと(rand関数呼び出しの)評価順序が既定されていないので困る。C++11では左からのはずなのだがVC++2015ではそうなっていない。
#define SET_HASH(x,p0,p1,p2,p3) { Key _K0=(p0); Key _K1=(p1); x.set(_K0, _K1); (p2); (p3); }
#else
#define SET_HASH(x,p0,p1,p2,p3) { Key _K0=(p0); Key _K1=(p1); Key _K2=(p2); Key _K3=(p3); x.set(_K0, _K1, _K2, _K3); }
#endif

#if HASH_KEY_BITS <= 64

#define SET_HASH(x,p0,p1,p2,p3) { x = (p0); (p1); (p2); (p3); }

#elif HASH_KEY_BITS <= 128

// 関数の引数に直接書くと(rand関数呼び出しの)評価順序が既定されていないので困る。C++11では左からのはずなのだがVC++2015ではそうなっていない。

#define SET_HASH(x,p0,p1,p2,p3) { Key _K0=(p0); Key _K1=(p1); x.set(_K0, _K1); (p2); (p3); }

#else

#define SET_HASH(x,p0,p1,p2,p3) { Key _K0=(p0); Key _K1=(p1); Key _K2=(p2); Key _K3=(p3); x.set(_K0, _K1, _K2, _K3); }

#endif

こういうSET_HASHというマクロを用意して、以下のように初期化する。要するに64bit hash keyを生成するときも64bitの乱数を4つ生成して、そのうちの3つを捨てているわけだ。なかなか面白い実装だと思うが、いかがであろうか。

// ----------------------------------
//       Zorbrist keyの初期化
// ----------------------------------

void Position::init() {
  PRNG rng(20151225); // 開発開始日 == 電王トーナメント2015,最終日

  // 手番としてbit0を用いる。それ以外はbit0を使わない。これをxorではなく加算して行ってもbit0は汚されない。
  SET_HASH(Zobrist::side,1, 0, 0, 0);
  SET_HASH(Zobrist::zero,0, 0, 0, 0);

  // 64bit hash keyは256bit hash keyの下位64bitという解釈をすることで、256bitと64bitのときとでhash keyの下位64bitは合致するようにしておく。
  // これは定跡DBなどで使うときにこの性質が欲しいからである。
  for (Piece pc = PIECE_ZERO; pc < PIECE_NB; ++pc)
    for (Square sq = SQ_ZERO; sq < SQ_NB; ++sq)
      SET_HASH(Zobrist::psq[sq][pc],rng.rand<Key>() & ~1ULL, rng.rand<Key>(), rng.rand<Key>(), rng.rand<Key>());

  for (Color c = COLOR_ZERO; c < COLOR_NB; ++c)
    for (Piece pr = PIECE_ZERO ; pr < PIECE_HAND_NB;++pr)
      SET_HASH(Zobrist::hand[c][pr],rng.rand<Key>() & ~1ULL, rng.rand<Key>(), rng.rand<Key>(), rng.rand<Key>());

  for (int i = 0; i < MAX_PLY;++i)
    SET_HASH(Zobrist::depth[i], rng.rand<Key>() & ~1ULL, rng.rand<Key>(), rng.rand<Key>(), rng.rand<Key>())
}

// depthに応じたZobrist Hashを得る。depthを含めてhash keyを求めたいときに用いる。
HASH_KEY DepthHash(int depth) { return Zobrist::depth[depth]; }

// ----------------------------------

// Zorbrist keyの初期化

// ----------------------------------

void Position::init() {

PRNG rng(20151225); // 開発開始日 == 電王トーナメント2015,最終日

// 手番としてbit0を用いる。それ以外はbit0を使わない。これをxorではなく加算して行ってもbit0は汚されない。

SET_HASH(Zobrist::side,1, 0, 0, 0);

SET_HASH(Zobrist::zero,0, 0, 0, 0);

// 64bit hash keyは256bit hash keyの下位64bitという解釈をすることで、256bitと64bitのときとでhash keyの下位64bitは合致するようにしておく。

// これは定跡DBなどで使うときにこの性質が欲しいからである。

for (Piece pc = PIECE_ZERO; pc < PIECE_NB; ++pc)

for (Square sq = SQ_ZERO; sq < SQ_NB; ++sq)

SET_HASH(Zobrist::psq[sq][pc],rng.rand() & ~1ULL, rng.rand(), rng.rand(), rng.rand());

for (Color c = COLOR_ZERO; c < COLOR_NB; ++c)

for (Piece pr = PIECE_ZERO ; pr < PIECE_HAND_NB;++pr)

SET_HASH(Zobrist::hand[c][pr],rng.rand() & ~1ULL, rng.rand(), rng.rand(), rng.rand());

for (int i = 0; i < MAX_PLY;++i)

SET_HASH(Zobrist::depth[i], rng.rand() & ~1ULL, rng.rand(), rng.rand(), rng.rand())

}

// depthに応じたZobrist Hashを得る。depthを含めてhash keyを求めたいときに用いる。

HASH_KEY DepthHash(int depth) { return Zobrist::depth[depth]; }

Zorbrist Hashの実装をxorからaddに変えるときの注意点

さて、前回、Zobrist Hashを将棋ではxorではなくaddで行なうというところまで話をしたが、注意しなければならないことの説明がまだ終わってなかった。
置換表に登録した指し手を取り出してくるわけだが、いくつか困ったことになる。まず、hashが衝突したりして別の局面の情報が登録されていることがある。また、SMPによる影響、すなわち、置換表のエントリーから値を取り出しているときに、別のスレッドによって置換表のエントリーの書き換えが起きることもある。

※ SMPは、Symmetric Multiprocessingの略のようで、「他のスレッドが壊すねん！」という文脈でよくStockfishのソースコードに書いてあるので覚えておくといいと思う。

置換表に登録している情報のうち最も重要な情報は指し手である。その局面でベストだと思われる指し手を登録しておくのに使う。これが他の局面の指し手を間違って取り出してしまった場合、どうだろうか。

その局面では非合法手となってしまう。その結果、3枚目の角を打ってしまうかも知れない。(笑)

そこで置換表から取り出してきた指し手に関しては、合法手かどうかを判定しないといけない。

ところが、先手は1段目に歩を打てない。51歩打みたいな手は先手の手としては非合法手である。後手の51歩打は非合法ではない。正確に言うと、51の升に駒があると打てないから非合法手だし、二歩であるとか打ち歩詰めであるとか、etc…のケースにおいて非合法手であるが、51歩打だから非合法手とは言えない。後手の51歩打は非合法手とは限らない。

よって、置換表から取り出してきた指し手の合法性についてチェックするときに、これが後手の局面用の指し手だとわかっていれば51歩打という指し手があっても、打てないはずの升への打ち歩でないことは確かなので、この合法性のチェックの処理が一部省略できるのである。

なので、置換表は、先手の局面と後手の局面とは登録する場所が分かれていて欲しい。置換表はそのような性質を持っているのが望ましい。

これを実現するにはどうすればいいだろうか？

置換表のエントリーをhash keyの下位から何bitかを使う。さきほどの置換表の実装を思い出して欲しい。

auto& tte = table[key /*.p(0)*/ & (entryCount – 1)];

と書いてあった。

HashEntryが先手と後手とで異なる場所であることを担保するには、先手と後手とで、hashのどこかのbitが異なる値になっていれば良いが、上のようにエントリーのアドレスを求めるとしたら、そのために使えるbitはbit0しかない。ここ以外のbitはアドレスの計算に必ず使うとは言いがたいからである。

そこで先手ならbit0を0、後手ならbit0を1とするような実装にする。

そうするとさきほどのpsq,handの乱数テーブルなどもbit0は手番情報として使うので0にしておかなければならない。bit0が0である数字をいくら足そうが引こうがbit0は0のままであるので、bit0に影響を及ぼさない。

こうしておいて、手番としてhash keyのbit0を用いる。さきほどの乱数テーブルの初期化するソースコードで言うところのZobrist::sideがこのための定数である。

つまり、do_move()で相手番にするには、

if (us == BLACK)
key += Zobrist::side; // 次は後手番なのでZobrist::sideを加算
else
key -= Zobrist::side; // 次は先手番なのでZobrist::sideを減算

となるわけであるが、do_move()では相手番になれば良いのでこんな判定処理は不要で、単に次のようにすれば相手番となる。

key ^= Zobrist::side;

つまり、add型のZobrist Hashにおいても、手番の更新だけはxorで済ませるというテクニックが誕生した。

Zobrist Hashingのオリジナルのコードでのsideの扱い

一般的に知られてるZobrist Hashing(xorを用いるオリジナルのほう)では、sideも単なる乱数値で上のように1という定数ではない。

これはZobrist Hashingはコンピューターチェスの開発過程で発祥したものであり、チェスには将棋の先手51歩打のような先手だけが非合法手となるような性質の指し手は存在しないので、仮にhashが衝突して置換表から先手用の局面の指し手として後手の指し手が得られたとしても、上に書いたような合法性のチェック上の問題は発生しないので、問題とならなかったのだろう。

そんなわけで将棋でxorでZobrist Hashingを実装する場合でもやはり、将棋の場合はbit 0はside(手番)を表すbitとして確保しておくような実装が好ましいのである。これは将棋特有の問題であるということになる。

ここまでのまとめ

読者は、局面のhash keyの実装の完全な理解が得られ、そして、置換表の自前実装が出来るようになった。(と思いたい)

次回に続く。