【決定版】コンピュータ将棋のHASHの概念について詳しく

投稿日時: 2018年11月18日投稿者: やねうらお

いまどきの将棋ソフトを使っていると、「HASH 50%」などと表示されている。これはHASH利用率と呼ばれる。この数字が大きくなってくると探索の効率が悪くなる。要するに潤沢にメモリがある場合に比べると弱くなる。これは、どれくらいの値までであるなら適切なのか？HASH利用率が99%にならない限りHASHには余裕があるものなのか？HASHはどういう仕組みになっているのか？HASH利用率が50%の状況で、ハッシュ衝突はしているのか？など、わりとソフトを長年使っていても知らない人が多いのでここに原理から詳しく説明した決定版的な記事を書く。

ShogiGUIや将棋神やねうら王に表示されている「HASH」とは何ですか？

一度探索した局面を保存しておく表です。

この表に登録するときにハッシュ(hash)という値を使って登録するため、ハッシュテーブル(hash table)と呼ばれます。これを略して(値としてのhashと紛らわしくない文脈においては)「ハッシュ」と呼んでいます。

この「ハッシュテーブル」は、正式には「置換表」(transposition table)と呼ばれます。

以下の文章では、「HASH」をこの置換表のことを指すものとします。

HASHはどんなデータ構造になっていますか？

表になっています。プログラマーにわかる言葉で言うと配列です。高校数学の言葉で言うとベクトルです。どちらもわからない人にわかる言葉で言うとデータを格納する箱が複数並んでいるということです。

いま、データを格納する1000個の箱があるとしましょう。
それぞれa[0],a[1],…,a[999]のように添え字をつけて表記します。

この箱に一度調べた局面の情報を格納したいわけです。

hash keyとは何ですか？

局面の情報(盤上の駒の配置や手駒など)を丸ごとこの箱に登録すると箱がもったいないので(箱の大きさはなるべく小さく設計したいので)、まず、局面に対応する値を計算することにします。この値は、hash keyと呼ばれます。hash keyは、64bitの符号なし整数(0 から 18446744073709551615までの値)です。

1) 同じ局面であれば同じhash key(になるようにうまく作られている)
2) 異なる局面でも偶然同じhash keyになることはある。(これをhash keyの衝突と呼ぶ)

1)のアルゴリズムにはZobrist hashingという仕組みが使われています。極めて小さな計算量でこのhash keyを求めることができます。

2)のhash keyの衝突が生じると異なる局面の情報を間違えて使ってしまうので、当然のことながら棋力は弱くなります。なるべくならば起きないほうが嬉しいです。

ところが、実際は、hash keyの衝突よりも格納する領域がなくて格納できないという問題のほうがダメージが大きいです。これについてはこのあと説明します。

局面の情報はHASHのどこに格納されますか？

HASHとして、a[0],a[1],…,a[999]の1000個の領域があるとして、一番単純な実装としては、このa[0]から使っていく方法が考えられます。a[0]が使用中であればa[1]を使う。a[1]も使用中であればa[2]を使う。という方法です。

しかし、これだとHASH利用率50%という状況において、先頭から順番にデータが全体の50%のところまで使用中であるので、データを一つ格納するためにa[0]からa[500]まで順番に使用中であるかを調べないといけないことになります。

実際のケースでは、箱は1000個ではなく1億個とかあるので、データひとつ格納するために箱を5千万個とか調べないといけないことになります。これだけで1秒以上かかることになるでしょう。1つの局面のデータを1個格納するのに1秒以上ですよ？ありえないでしょう。

つまり、この理由から、このように先頭から使っていくというような方法はまったく現実的ではないのです。

では、どこから使っていくのが良いのでしょうか？

せっかくhash keyという局面と対応する値が求まっているので、この値から箱を一つ選べぶ方法があると嬉しいです。

hash keyは局面ごとにばらばらの値になることが保証されていると仮定できるなら、1000個の箱のどれにするかをhash keyの値を1000で割った余りとするとどうでしょう？x を yで割った余りを「x % y」のように書くとしたら、これは、

a[hash_key % 1000]

ということです。

これなら先頭から順番に見ていくよりはるかに効率が良いですね。

ハッシュ値

このとき、keyを以下のように計算してハッシュテーブルを参照する(look upする)と解釈できます。

key = hash_key % 1000;

このkeyは1/1000の確率で衝突(同じ値になる)します。

hash keyの衝突と、このkeyの衝突とは明らかに異なる概念です。衝突する確率も前者と後者とでは全く異なりますしね。

ハッシュテーブルというデータ構造の話をする文脈では、ハッシュテーブルを参照するときのキーをハッシュ値と呼び、この衝突のことを「ハッシュ衝突」と呼ぶのですが(つまり、上記のkeyの衝突をハッシュ衝突と呼ぶ)、コンピューター将棋では、このkeyの計算は明示的には出てこないため、hash keyの衝突のことを「ハッシュ衝突」と呼ぶことが多いです。この点、注意が必要です。コンピューター将棋にあまり詳しくない人に対して説明なしに「ハッシュ衝突」という言葉を使うと正しく伝わらない可能性が高いです。

以下の文章ではこのへん明確に区別して書きますので、意識しながら読んでください。

TTEntry

このa[0],a[1],…,a[999]は、置換表の値を格納しておく箱なので、TTEntryと呼ばれます。TTは、置換表(Transposition Table)の略です。

TTEntryの衝突

局面のhash keyは64bitの値なのでそんなに簡単には衝突しませんが、TTEntryは(いままでの例では)1000個しかないので、簡単に衝突しますね。

TTEntryの置き換え

TTEntryが使用中であれば今回登録する情報のほうがいま登録されているものより価値があるならば置き換えることが考えられます。

例えば、深くまで探索した結果は、浅くまで探索した結果より重要でしょう。今回登録するもののほうが、深くまで探索した結果ならば、今回の結果で置き換え(上書き)してしまうことが考えられます。

TTEntryから値の取り出し

では逆に値を取り出す時はどうでしょう？

a[hash_key % 1000]から値を取り出しました。しかし、これはhash_keyの局面に関する情報なのでしょうか？たまたまkey(hash_keyを1000で割った余り)が一致しただけの異なる局面に関する情報なのでしょうか？その区別ができないと困ります。hash_keyは64bitあるので、偶然一致する確率は、1/18446744073709551616ですが、1000で割った余りですと偶然一致する確率は1/1000だからです。後者のほうは(前者に比べると)極めて高い確率ですね。

そこで、TTEntryに書き込むときに、hash_keyの値もTTEntryに格納しておきます。TTEntryから値を取り出すときに、この値が一致することを事前に確認します。

// hash_keyが一致するか？
if (a[hash_key % 1000].hash_key == hash_key )
…

これで取り出すときに間違った局面の情報を取り出してしまう可能性は、低くなりました。(1/1000から、1/18446744073709551616に減りました)

実際は、やねうら王では、Stockfishに倣い、TTEntryのサイズをケチるために、hash keyの64bitを丸ごと格納しているわけではないのですが、まあ、それはこの記事の範囲を超えるので割愛します。

rehash

しかしTTEntryが使用中であったときにそこに書いてある情報のほうが価値があると判断される場合、新たなデータが保存できないことになります。これでは探索した情報が無駄になってしまいます。

そこで、できることならば他に空いている場所を探して格納したいです。これをrehashと言います。

rehashとして、別の箱を探したいです。

これについては、「開番地法(open addressing)」でググれば出てくるかと思いますので詳しい説明は割愛します。

単純な実装としては、a[key]が使用中ならa[key + 1]のように隣を使っていく方法が考えられます。しかしこれも上で説明したa[0]から順番に使っていく方法と同様の問題を抱えています。際限なく順番に空きを探していくのはこの意味においてとても危険です。

そこで、a[key]が使用中ならa[key + 1]とa[key + 2]を見て、それらが使用中なら諦めるという方法が考えられます。(諦めるか、もしくは、この3つのいずれか一番情報的な価値の低いところに(そこを潰して)上書きしてしまう。)

この方法はそんなに悪くはないのですが、CPUのCache Lineをまたぐ必要があり、速度的に損な実装です。(詳しくは後述します)

ガベージコレクション

本当は情報の消失を防ぐ意味では、rehashはTTEntryの空きがあるまでずっとやるべきであり、HASHの使用率が30%ぐらいになってきたときに不要な情報を削除して掃除してやる必要があります。これをガベージコレクション(garbage collection)と言います。

普通の指し将棋ではこの不要な情報を判断しにくいですし、また、空きがあるまで探すコストが大きすぎて、ガベージコレクションを採用している上位ソフトは存在しません。

しかし、詰将棋探索に限って言えば、情報が消失すると詰むはずのものが詰まなくなることがあり、また、この先は詰むとわかっている手順から先は(最善応手列以外は)結論だけあれば十分なので、削除することができます。

なので、詰将棋探索で超長手数の詰将棋を解かなければならないときは、ガベージコレクションを実装する必要があります。

※　tanuki-詰将棋エンジンは、実戦型の詰将棋を超高速に解くことに主眼をおいて開発されているので現在のところガベージコレクションは実装されていません。

Cache-Lines size

PCに搭載されているメモリを見たことはある人は多いと思いますが、小さなメモリモジュールが複数個(普通は2の累乗個)載っています。これにより、それぞれのメモリモジュールから並列的にデータを取り出すことでスループット(単位時間あたりの転送量)を稼いでいます。

また、1バイトのデータをくれとメモリにお願いしてメモリからデータが返ってくるのに(CPUの内部で処理するのと比べると)極めて長い時間がかかります。

なのでプログラムから1バイトの読み込みを要求されたからと言って1バイトのデータだけを取り出すようなことはしません。プログラムからはそのアドレスに隣接するデータも使うことが普通なので、プログラムから1バイトだけ読み込みを要求されたとしても、もうちょっとまとまった単位でデータをCPU(CPUのL1 cache)に取り込むようになっています。

このサイズはCache-Lines sizeと呼ばれ、典型的には64バイト(CPUによっては32バイト)になっています。

TTCluster

そこで、TTEntryをいくつか束にして、32バイトになるようにしておけば、Cache-Lines sizeに収まるので、rehashのときにCPU内にすでに転送されたあとのメモリを見るだけで済むので極めて速くなります。

やねうら王では、Stockfishの実装に倣い、TTEntryは10バイトなのでこれを3つ束にして30バイト。2バイトpadding(使わずに空けておくこと)して、合計32バイト。これをTTClusterと呼びます。

例えば、TTClusterを1000個確保したなら、

tt[hash_key % 1000]

のようにして使うTTClusterを確定させます。そのなかの1つ目のTTEntryは、

tt[hash_key % 1000].entry[0]

となります。

データを書き込みたいとき、1つ目のTTEntryが使用中であれば、2つ目のTTEntryにrehashします。

tt[hash_key % 1000].entry[1]

2つ目も使用中であれば、3つ目にrehashします。

tt[hash_key % 1000].entry[2]

すべてが使用中であれば、そのなかで一番価値の低いTTEntryに上書きします。

TTClusterを使う利点

TTCluster 1個が丸ごとCache-Lines sizeに収まるのでrehashしたときのTTEntryもCPU内のメモリ(CPUのL1 cache)にすでに取り込まれていることが期待できるので、極めて高速です。

HASH使用率とは？

やねうら王では、Stockfishに倣い、HASH使用率はTTClusterの先頭から1000個のTTEntryに関して使用中のものを数えてその数をGUI側に送信しています。つまりこれは千分率で使用率を表現していることになります。他の将棋ソフトも(Stockfishに倣っているものは)だいたいこうなっているはずです。

まとめ

以上がコンピューター将棋におけるHASHのすべてです。

今回の内容を踏まえてQA方式で答えていきます。

Q) HASH使用率50%の状況でハッシュは衝突してるの？
A) hash keyは衝突していないですが、TTEntry自体は足りていないのではないでしょうか。HASH使用率50%であれば、TTClusterのなかのTTEntryが3つとも使用中でそのためどれか1つを潰して上書きしなければ値を格納できないということが頻繁に発生しうるのではないでしょうか。

Q) HASH使用率10%の状況でもハッシュ衝突はしてるの？
A) 確率の計算なので割愛しますが、上のような原理になっているので、TTEntry自体はどこか潰して上書きされていてもおかしくはないですね。

Q) TTEntryが破壊されると棋力は弱くなるの？
A) 局面を調べた情報を損失しているわけで、メモリが潤沢にある状況に比べるとその分だけ弱くなります。

Q) TTEntryが破壊されるとどれくらい棋力が弱くなるの？
A) 定量的な値を出すのは難しいですが、HASH使用率90%以上だとメモリが潤沢にある状況に比べると20%～70%ぐらいの性能ダウンにはなるのではないでしょうか。

Q) 同じサイズのHASHを確保している状態で、HASH使用率99%(最終的な値)の状態で1時間探索を続けた場合と、HASH使用率99%(最終的な値)の状態で30分思考させた状態とを比較して、前者が後者より弱くなるということは起こりえますか？
A) よほど極端な条件でない限り、前者が後者より弱くなることはないと思います。一度訪問したノード(局面)に再度訪問するとは限らないので現実的には二度と使わない情報も多々ありますし、TTEntryが破壊されて情報が失われていても、その局面を再度探索するときに、その子ノード(1手進めた局面)の情報は残っているかも知れませんので、丸ごと探索しなおしには普通ならないからです。

Q) HASH使用率は99%までなら効率は落ちていないということですか？
A) TTEntryを潰して上書きされることになるのでHASH使用率10%であろうと効率の低下は始まっています。(この記事で書いたように先頭から空いているところを探して使うのではないので、使用率が99%ではないからまだいける、ということではないです。)

Q) HASH 1024でHASH使用率99%の状態で1時間思考させた場合と、HASHをその100倍確保して、HASH使用率50%(最終的な値)の状態で10分思考させた場合とを比較すると、前者は後者より強いですか？
A) そうとは言い切れないです。(定量的な実験データは出せないですが…)