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

今回は、局面のhash値の計算について説明します。

局面に対応するhash値の取り出し

局面に対して、StateInfo::key()からhash値が得られる。
このhash値は、局面に対応する固有の値である。

しかし通例、hash値は64bitしかないので、異なる局面であっても、たまたま同じhash値になることがある。これをhash衝突と言う。

やねうら王miniにはこのhash値を128bitにしたり256bitにしたり出来る無駄機能があるが、その話は次回にしよう。

さて、このkeyを取り出してみよう。その局面固有の内容を格納しておくのはStateInfoであった。Positionクラスのstate()を呼び出すとStateInfoの参照が得られる。StateInfoのkey()を呼び出すとこのhash値が得られる。

実際にやってみよう。

void user_test(Position& pos, istringstream& is)
{
  cout << pos;
  cout << std::hex << "HashKey = " << pos.state()->key() << endl;
}

> user
^香^桂^銀^金^玉^金^銀^桂^香
 □^飛 □ □ □ □ □^角 □
^歩^歩^歩^歩^歩^歩^歩^歩^歩
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 歩 歩 歩 歩 歩 歩 歩 歩 歩
 □ 角 □ □ □ □ □ 飛 □
 香 桂 銀 金 玉 金 銀 桂 香
先手 手駒 :  , 後手 手駒 :
手番 = 先手
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
HashKey = 75a12070b8bd438a

void user_test(Position& pos, istringstream& is)

{

cout << pos;

cout << std::hex << "HashKey = " << pos.state()->key() << endl;

}

> user

^香^桂^銀^金^玉^金^銀^桂^香

□^飛 □ □ □ □ □^角 □

^歩^歩^歩^歩^歩^歩^歩^歩^歩

□ □ □ □ □ □ □ □ □

歩歩歩歩歩歩歩歩歩

□ 角 □ □ □ □ □ 飛 □

香桂銀金玉金銀桂香

先手手駒 : , 後手手駒 :

手番 = 先手

sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1

HashKey = 75a12070b8bd438a

確かに64bitの値が得られた。局面を進めて、hash値がどうなるか調べて、ついでにundo_move()で局面を戻して、hash値がどうなるか見てみよう。

void user_test(Position& pos, istringstream& is)
{
  cout << pos;
  cout << std::hex << "HashKey = " << pos.state()->key() << endl;

  Move m = make_move(SQ_27, SQ_26);
  StateInfo si;
  pos.do_move(m, si);
  cout << pos;
  cout << std::hex << "HashKey = " << pos.state()->key() << endl;

  pos.undo_move(m);
  cout << pos;
  cout << std::hex << "HashKey = " << pos.state()->key() << endl;
}

> user
^香^桂^銀^金^玉^金^銀^桂^香
 □^飛 □ □ □ □ □^角 □
^歩^歩^歩^歩^歩^歩^歩^歩^歩
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 歩 歩 歩 歩 歩 歩 歩 歩 歩
 □ 角 □ □ □ □ □ 飛 □
 香 桂 銀 金 玉 金 銀 桂 香
先手 手駒 :  , 後手 手駒 :
手番 = 先手
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
HashKey = 75a12070b8bd438a
^香^桂^銀^金^玉^金^銀^桂^香
 □^飛 □ □ □ □ □^角 □
^歩^歩^歩^歩^歩^歩^歩^歩^歩
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ 歩 □
 歩 歩 歩 歩 歩 歩 歩 □ 歩
 □ 角 □ □ □ □ □ 飛 □
 香 桂 銀 金 玉 金 銀 桂 香
先手 手駒 :  , 後手 手駒 :
手番 = 後手
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/7P1/PPPPPPP1P/1B5R1/LNSGKGSNL w - 2
HashKey = 72528de42950f703
^香^桂^銀^金^玉^金^銀^桂^香
 □^飛 □ □ □ □ □^角 □
^歩^歩^歩^歩^歩^歩^歩^歩^歩
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 □ □ □ □ □ □ □ □ □
 歩 歩 歩 歩 歩 歩 歩 歩 歩
 □ 角 □ □ □ □ □ 飛 □
 香 桂 銀 金 玉 金 銀 桂 香
先手 手駒 :  , 後手 手駒 :
手番 = 先手
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
HashKey = 75a12070b8bd438a

void user_test(Position& pos, istringstream& is)

{

cout << pos;

cout << std::hex << "HashKey = " << pos.state()->key() << endl;

Move m = make_move(SQ_27, SQ_26);

StateInfo si;

pos.do_move(m, si);

cout << pos;

cout << std::hex << "HashKey = " << pos.state()->key() << endl;

pos.undo_move(m);

cout << pos;

cout << std::hex << "HashKey = " << pos.state()->key() << endl;

}

> user

^香^桂^銀^金^玉^金^銀^桂^香

□^飛 □ □ □ □ □^角 □

^歩^歩^歩^歩^歩^歩^歩^歩^歩

□ □ □ □ □ □ □ □ □

歩歩歩歩歩歩歩歩歩

□ 角 □ □ □ □ □ 飛 □

香桂銀金玉金銀桂香

先手手駒 : , 後手手駒 :

手番 = 先手

sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1

HashKey = 75a12070b8bd438a

^香^桂^銀^金^玉^金^銀^桂^香

□^飛 □ □ □ □ □^角 □

^歩^歩^歩^歩^歩^歩^歩^歩^歩

□ □ □ □ □ □ □ □ □

□ □ □ □ □ □ □ 歩 □

歩歩歩歩歩歩歩 □ 歩

□ 角 □ □ □ □ □ 飛 □

香桂銀金玉金銀桂香

先手手駒 : , 後手手駒 :

手番 = 後手

sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/7P1/PPPPPPP1P/1B5R1/LNSGKGSNL w - 2

HashKey = 72528de42950f703

^香^桂^銀^金^玉^金^銀^桂^香

□^飛 □ □ □ □ □^角 □

^歩^歩^歩^歩^歩^歩^歩^歩^歩

□ □ □ □ □ □ □ □ □

歩歩歩歩歩歩歩歩歩

□ 角 □ □ □ □ □ 飛 □

香桂銀金玉金銀桂香

先手手駒 : , 後手手駒 :

手番 = 先手

sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1

HashKey = 75a12070b8bd438a

do_move()で局面を進めると、75a12070b8bd438aから72528de42950f703になったようである。これをundo_move()で戻すと75a12070b8bd438aに戻った。

・同じ局面に対しては同じ値を取る
・異なる局面に対しては異なる値を取る(が、64bitしかないので、ごくまれに同じ値になってしまう)

という性質があることがわかった。

hash値の使いみち

局面に対する何らかの情報を連想配列などに保存したいときに、このhash値がキーとして使える。

この連想配列のことを将棋ソフトの世界では「置換表」と呼んでいる。名前の由来については以下の記事を参考にされたし。

置換表は何故置換表と言うのか？

前回の記事でperftという、将棋の初期局面からN手で到達できる局面の数を数えるプログラムを書いた。

そのあと、チェスのperftに倣って、captures(駒を捕獲する指し手の数)や、mates(詰みの局面の数)も表示されるようにした。

将棋でPerftしてみたまとめのまとめ

これを高速化して、将棋の世界のperftの世界記録を更新した。

将棋におけるperftの世界記録を更新中

まあ、世界記録って言っても誰も本気で取り組んですらいないのだが…。

置換表を用いたperftの高速化

話を戻して、perftを高速化することを考えよう。

ある局面での残り探索深さと、そのときの探索結果を置換表に保存しておけば、同じ局面に遭遇したときに計算が省ける。

まず、統計情報の構造体を用意する。

struct PerftSolverResult {
  uint64_t nodes, captures, promotions, checks, mates;
  void operator+=(const PerftSolverResult& other) {
    nodes += other.nodes;
    captures += other.captures;
    promotions += other.promotions;
    checks += other.checks;
    mates += other.mates;
  }
};

struct PerftSolverResult {

uint64_t nodes, captures, promotions, checks, mates;

void operator+=(const PerftSolverResult& other) {

nodes += other.nodes;

captures += other.captures;

promotions += other.promotions;

checks += other.checks;

mates += other.mates;

}

};

ある局面のhash値とそのときの探索深さをキーとして、このPerftSolverResultを格納しておける連想記憶があればよろしい。

それさえあれば、perftのプログラムは次のように書ける。

PerftSolverResult Perft(Position& pos, int depth) {

bool found;
auto tt = Perft::TT.probe(pos.state()->key(), depth, found); // 置換表に登録されているか。
if (found)
  return tt->result;

＿人人人人人人人人人＿
＞　元のプログラム　＜  // ここに元のプログラムを書く
￣Y^Y^Y^Y^Y^Y^Y^Y￣

tt->save(key, result); // 登録されていなかったので置換表に保存する

return result;

PerftSolverResult Perft(Position& pos, int depth) {

bool found;

auto tt = Perft::TT.probe(pos.state()->key(), depth, found); // 置換表に登録されているか。

if (found)

return tt->result;

＿人人人人人人人人人＿

＞　元のプログラム　＜ // ここに元のプログラムを書く

￣Y^Y^Y^Y^Y^Y^Y^Y￣

tt->save(key, result); // 登録されていなかったので置換表に保存する

return result;

元のプログラムにわずか5行追加するだけである。あとはこのような置換表を実装すればいいのだ。まあ、プログラミングコンテストでこの手のプログラムを書き慣れた人なら10分もあれば書けるだろう。(私は30分ぐらいかかったが…)

これは次回までの読者への宿題として、このhash値をどうやって計算しているのかについて詳しく書いておこう。

Zobrist Hash

この手のhash値はZobrist Hashと相場が決まっている。詳しくはggrksである。

早い話、駒pcと升sqに対して乱数表psq[pc][sq]のようなものを持っているのである。
盤上の先手の歩が27から26に移動したとしたら

key ^= psq[B_PAWN][SQ_27];
key ^= psq[B_PAWN][SQ_26];

のようにして更新完了である。簡単でしょ？

ggrksと言っておきながらZobrist Hashのことについてすべて解説してしまった。この連載、親切すぎる。

また、手番も同じく64bitの乱数値である。

// 手番を相手番にする処理
key ^= side; // sideは、手番を示す乱数値

do_mode()では、相手番になるので、毎回、この処理が入る。

上の例ではpsq配列とxorをしている。このようにZobrist Hashではxorを用いるのが普通である。最初にこれを発明した Albert Lindsey Zobristさんがそうやっていたから、みんなこれを真似しているわけである。

xorにしておけば2回同じ値でxorすれば元の値に戻ることが保証されるので、上の更新処理の逆手順(26の歩が27に移動)をしたときに元の値に戻ることが保証されるわけだ。

key ^= psq[B_PAWN][SQ_26];
key ^= psq[B_PAWN][SQ_27];

つまり、hash値は同一の局面では同じ値を取るということが担保されるわけだな。

Zobrist Hashの元のままだと将棋では困る

ところが、将棋のプログラムではこの処理、xorではやや困ったことが起きるのだ。

具体的には、将棋には手駒がある。手駒としてZobrist Hashを用意する。先手の1枚目の歩ならば、次のような値となるとしよう。

hand[BLACK][PIECE][1]

だとすると、先手の歩が1枚から2枚になる場合、

key ^= hand[BLACK][PIECE][1]; // 1枚目の歩が消失して
key ^= hand[BLACK][PIECE][2]; // 2枚目の歩が出現

こういうコードになる。

ちょっとダサい。手駒は1枚ずつしか増えたり減ったりしないのに何故2回もテーブルを引かなければならないのか。そこで歩が1枚から2枚になるときは

key ^= hand[BLACK][PIECE][2];

こうして、2枚から1枚になるときは、この逆変換(元の値に戻す)であればいいのだから、

key ^= hand[BLACK][PIECE][2];

とすれば元の値に戻るではないかと。

確かに正しい。当然、このように書くべきである。

ところが、よく見るとこの配列は3次元配列で、歩は18枚もあるので、歩以外の駒でも18まで要素が確保されている。これはもったいない。

Zobrist Hashの改良(GPS将棋の方法)

そこでもっと賢い方法が考案された。最初にやったのはGPS将棋だ。GPS将棋が採った戦略は、Zobrist Hashの計算をxorではなくadd(足し算)にしてしまうということだった。

つまり、26の歩が27に進むのであれば、

key -= psq[B_PAWN][SQ_26];
key += psq[B_PAWN][SQ_27];

のようにする。戻すときは足すと引くを入れ替えて

key += psq[B_PAWN][SQ_26];
key -= psq[B_PAWN][SQ_27];

のようにすれば元の値に戻せるはずだ。結局、同じ局面で元の値に戻りさえすればいいのだ。xorでやるよりは乱数によってはhash値に偏りが発生する可能性もあるが、実用上無視できる範囲であろう。

このとき、手駒の処理がとても簡単になる。先手の歩が1枚増えるときはこうだ。

key += hand[BLACK][PAWN];

なんと、何枚目の歩であろうとこの処理で済むのだ。足し算、最高！！
言うまでもなく1枚減るときは、こうだ。

key -= hand[BLACK][PAWN];

素晴らしい。「3次元配列なんていらんかったんや～」である。

GPS将棋、賢すぎる。

実は、私も自力でこれと同じことを発明していた。平岡さんに「これ、xorでなくaddでやったら2次元配列で済むよね」と言ったら、「それGPS将棋で(とっくに)やってますよ…Aperyもそうやってますし」と当然のことのように言われたのだ。2年前に。

さて、コンピューター将棋では、Zobrist Hashをaddで済ませるというところまで話が進んだ。

ただaddで済ませるときに一つだけ気をつけないことがある。これについては次回説明する。

次回につづく。