Haswell以降専用だと何が嬉しいのですか？

投稿日時: 投稿者:

Haswell以降、BMI2やAVX256が使えます。
これらを使うとコンピューター将棋において何が嬉しいのでしょうか？

まず今回はpextの周辺についていままで誰も書いていないあたりをだらだらと書いていきます。今回の文脈ならbitwise(ビット単位)であることは書かなくともわかると思うので、以下、単にor/and/xorと書きます。

BMI使ってますか？
http://d.hatena.ne.jp/LS3600/20141011

ここまでは他の開発者の皆さんもよくご存知のことでしょう。

まず、magic bitboardをHaswellのpextを用いて代替したいわけです。

何のために代替したいかというと、magic bitboardは準備が結構たいへんだからです。magic bitboardで使うmagic number(掛け算の定数)がなかなか見つからなかったりします。Aperyのソースコードにはその苦心の跡が見られますね。

それとは別にmagic bitboardへの批判として将棋に使うにはテーブルが大きすぎるというのが挙げられます。

飛車の利きを確定させるためには、盤面の辺以外においた飛車の場合、縦横6升ずつ(=12升)を調べる必要があります。角に置いた場合は縦横7升ずつ(=14升)について調べる必要があります。

つまり愚直に実装した場合、14bitの組み合わせ(2^14)×81升×128bit ≒ 21MBのテーブルが必要になります。局所的にしかアクセスしないので、このへんはCPU cacheに載るのではないかと言われています。

まあ、CPUのメモリ帯域的な問題は、新しいCPUやマザーボードが出るごとにそのへんの事情は変わってきますので、いまは考えないようにします。

実際このへんをmagic bitboardと普通のBonanza型のスライドテーブルとで速度比較した人はいません。この速度比較はとても手間がかかるからです。

何故なら、まずmagic bitboardを使うに当って、盤面をBonanza型Bitboardから、Apery型(後述)Bitboardにする必要があります。そうするとSquare型(盤上の81升の位置を示す型)の意味するところが変わってきます。Zobrist Hashの値も変わってきますし、評価関数も大幅にコードの書き直しが必要になります。公平な比較をしようと思うと以前の評価関数テーブルを新しい評価関数テーブルに変換するコードが必要になりますし、また、Bitboardのレイアウトが変わるので、指し手生成で生成される指し手の順番が変わってきます。指し手生成の順番が変わるということは、以前と同じ局面を探索させても探索結果が変わってくるということであり、以前のベンチマークと同じ探索ノード数にはならなくなってきます。

このように、magic bitboardを導入する前/導入した後とで厳密な速度比較を行なうというのは至難の業です。なので、コンピューター将棋界で誰もこの比較を真面目にやった人はいません。

「pextを使うのだから、magic bitboardの話は関係ないんじゃないの？」

と聞こえてきそうです。しかし、そうではありません。

magic bitboardのときに掛け算を使って(飛車の利きが関与する)14bitのbitをかき集めていた部分にpextが使えるというだけで、結局、そのあと、上で書いた21MBのテーブルは必要になるわけです。
※　magic bitboard、将棋の実装だとmagic number(掛け算に使う定数)が見つからない箇所があって、その部分、ちょっとしたhackが必要になり、テーブルサイズはpextを使うときより微妙に大きいのですが、これについてはAperyのソースコードを読んでください。

つまり、テーブルサイズが大きすぎるのではないかという批判はpextを用いた実装にもそれがそのまま当てはまります。なので、pextを用いる場合、magic bitboardで実装した場合と速度的にはほぼ変わらないのです。

そして、Haswellのpextを使うためにBitboardのレイアウトを何らか変更した人からは悲鳴が聞こえてきています。

上のツイートはSunfishの作者のものです。Sunfishの作者は「先にxorした時に衝突させないために)7筋、2筋に変えた」とあります。

これはApery型とは少し違うのですが、着眼点は同じです。

そもそもApery型Bitboardとは何なのか？その利点とは何なのか？
「先にxorした時に衝突させないために」とは何か？

今回は後者について説明します。

pextは特定のbitを一箇所にかき集めてくる命令です。遠方駒(香・飛車・角)の利きを確定させるために必要な升に駒があるかどうかの情報をかき集めてきます。

駒があるかどうかはoccupied bitboardというbitboardに格納してあるものとします。occupied bitboardは将棋盤面を収めるために128bitとなっています。

しかしpextでかき集めてこれる対象(の変数)は64bitです。つまりoccupied bitboardのbitをかき集めてこようと思った場合、2回pextを呼び出す必要が出てきます。ビットシフトも必要になります。

これは、たまらん！ということですね。

そこで、bitboardのレイアウトをうまく調整して、この飛車の利きを求めるのに必要な14bitの位置がbitboardのp[0](上位64bit)とp[1](下位64bit)とで被らないようにしようと思うわけです。

これは比較的簡単で、例えば、64bit変数のp[0]に将棋盤面の1～7段目(7×9 = 63bit)、p[1]に8～9段目(2×9 = 18bit)を格納するという方法を取ります。これがSunfishの作者が採った方法です。
こうすれば、51に置いた飛車の利きを求めるのに必要な升(横81,71,61,41,31,21と、52,53,54,55,56,57,58)があり、このときの58がp[0]とp[1]でorを取ったときに51の地点(元もと飛車がいた位置)とorされ、この部分はp[0]のほうでは使っていないのでセフセフというわけです。

飛車が辺以外にいる場合は、辺の情報は利きには関与しませんので、1段目と9段目は無視して考えることが出来るため、p[0]とp[1]でorをとったときに8段目と1段目がor、9段目と1段目がorされ、ちょうど使わないところ同士がorされるので、これもセフセフです。

また角の場合も、p[0]とp[1]とでは(p[0]に格納されている升が奇数なので)偶奇性(?)が違うので盤上のある地点sqにおいた角の利きがp[0]とp[1]とのorを取ったときに被ることはないです。

まあ、厳密な証明は読者諸氏にお任せします。

つまり、p[0]とp[1]のorを返すmerge()という関数があるとして、
index = pext((occupied & mask).merge() , mask.merge());
のようにすればテーブルのindexが求まるという仕組みです。

Sunfishの作者のツイートでは「xor」とありますが、両方のbitが1であるケースはそもそも想定していないので、この「xor」は「or」と等価な動作です。orにするかxorにするかは趣味の問題と言えるでしょう。

以上でSunfishの作者のツイートの意味は(将棋ソフト開発者の)皆さんにわかっていただけたかと思います。

しかし、このためだけにbitboardのレイアウトを変更すると大改造になります。嫌ですね。

例えば、盤面の上64升をp[0]に割り当てていて、残り17升をp[1]に割り当てているような実装をしている人がこのためだけにbitboardのメモリレイアウトを変更するのは感心しません。

そういう人は、次のようなhackを使うといいでしょう。
occupied.p[1] <<= 1;
index = pext((occupied & mask).merge() , mask.merge());
※　maskの値は上で書いたmaskの値と同じものとします。
このようにすることで、bitboardの大幅なレイアウト変更は避けられます。

Sunfishのようにp[0]が1～5段、p[1]が6～9段というレイアウトであれば、
occ = occupied & mask;
index = pext(occ.p[0] | (occ.p[1] << 5*9 ) | (occ.p[1] >> 2*9) , mask2);
※　mask2 = mask.p[0] | (mask.p[1]<<5*9) | (mask.p[1]>>2*9)
とやれば同じことです。まあ、このシフトが嫌だったのだとは思いますが、ほとんど誤差です。全体の実行速度は0.5%すら変わらないと思います。

だらだら書いていたらApery型のBitboardについて書く時間がなくなってしまいました。これについてはまた次回に書きます。

コメントを残す

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