magic bitboard論争に終止符を

投稿日時: 投稿者:

今回は、前回の続きとして、遠方駒(香角飛)の利き、いわゆる飛び利きの話をざっと書いていきます。

まず、前々回、私は(0のbitをsetするのは)「orにするかxorにするかは趣味の問題と言えるでしょう」と書いたのですが、唐突にxorのほうがベターだということを思い出しました。

つまり、0だと想定しているbitをsetするのにorを使うと、これが何らかのバグで1だった場合も正しい結果になってしまうので、xorを使ってsetすべきだということですね。以前、どこかでそんな話を自分でしたと思うのですが、すっかり忘れていました。

さて、本題。

まず、magic bitboadが登場するまでのbitboardを用いた将棋ソフトでは飛び利きはどうやって計算していたのでしょうか？

例えばBonanzaです。前々回、私は「スライドテーブル」と書きました。これについて今回は詳しく書いていきます。

Bonanzaでは飛び危機の計算は、
1) 盤面を90度回転させたoccupied bitboard
2) 盤面を右に45度回転させたoccupied bitboard
3) 盤面を左に45度回転させたoccupied bitboard
の3つを持っています。

1)は意味わかりますね。90度回転させたものを持っておけば、飛車の縦方向の利きは(盤面の縦方向にbitが連続して格納されているので)ビットシフトとマスク(and)をしたあと表引きすれば済むということですね。

2),3)はちょっと意味不明かも知れません。順を追って解説します。

まず角の利きを算出するのに、盤面の辺の部分に駒があるかないかは利きには関係がありません。例えば盤面の88に角をおいた場合、97に駒があろうとなかろうと97には利きは届いています。つまり、辺にある駒はあろうがなかろうが、角の利きを遮断できないのです。

よって盤面の辺以外のエリア(7×7 = 49升)に駒があるかどうかの情報だけを調べれば良いということになります。49升(49bit)が収まるoccupied bitboardがあれば十分で、これは64bit変数ひとつに収まります。

盤面を45度回転させたoccupied bitboardがあれば、1)で飛車の縦方向の利きを調べたときのように、ビットシフトとマスクをしたあと表引きすれば斜め方向の利きが求まるということです。

斜め方向には、「右上から左下」方向(diag1)と「左上から右下」方向(diag2)とがあり、それらの利きを求めるためのoccupied bitboardが、それぞれ2)と3)ということです。

このアイデアはYSSの作者の掲示板に投稿した人がいて、それを保木さんが初代Bonanzaで採用されたのだったと思います。

さて、ここで1)は128bit、2),3)はそれぞれ64bitであることに注意しましょう。つまり2),3)をひとまとめにした場合、128bitになります。

また指し手に従って盤面を更新するとき、1),2),3)の更新が必要になりますが、このときの操作は実は同じ操作になります。

どういうことかというと、2),3)は二つまとめて1つの128bitの普通のoccupied bitboardだとみなすことが出来ます。(Bonanzaではこうなってなかったと思いますが、こういう風に実装するのが現代風だと私は思います。)

1)をfile_occ、2),3)を1つにしたものをdiag_occという名前だとすると、fromからtoの地点に駒が移動した場合、1),2),3)の更新は、
file_occ ^= file_mask[from] | file_mask[to];
diag_occ ^= diag_mask[from] | diag_mask[to];
のように、2回のorと2回のxorだけで済みます。

128bitのor/xorがSSEの命令を使って1命令で出来る世界において、この処理はさほど重くないわけです。

file_occとdiag_occとどちらに対しても同じようにorとxorをしているので、AVX256を使えば命令数はさらに半分で済みます。

上のように128bitをひとまとめにしてandとxorが出来るという状況で、本当にmagic bitboardのほうが速いのか？というのが私の長年の疑問でした。

前回書いた通り、pextによる実装とmagic bitboardとはテーブルサイズはほとんど同じで、速度的にもpextのほうがわずかに速いという程度の違いしかありません。

いまさらmagic bitboardを実装するのは嫌だけど、やねうら王をスライドテーブルを使う実装からpextを使う実装に差し替えてもいいじゃない？ということで差し替え作業をしたわけです。

結果、全体的に見て0.5～1%ほど速くなりました。つまり、
pextによる実装 ≧ magic bitboardによる実装
pextによる実装 ≧ スライドテーブルによる実装
であることには間違いありません。

Aperyの平岡さんがmagic bitboardをpextによる実装に差し替えたら3%ほど速くなったと言っていた気がするので、もしかすると
スライドテーブルによる実装 ≧ magic bitboardによる実装
かも知れませんが、このへんは計測誤差もあると思うのでよくわかりません。

ともかく、スライドテーブルは、pextを使って実装しなおすと、0.5～1%ほど速くなるということで間違いなさそうです。

逆に言うとそれだけしか速くならないということですね。どう見ても誤差です。
magic bitboardやpextによる実装に憧れるのはよしましょう。

ともかく現代ではスライドテーブルはAVX2命令で実装できるため、さほど遅くないというのが私の結論です。もともと遅くないものを高速化することは出来ません。これがpextを使ってもさほど速くならない理由だと私は思います。

時間が来たので今回はここまで。

次回はAperyの縦型Bitboard使用時におけるpextを用いた高速化について書きます。

追記2017/11/22 1:30

magic bitboard、大きなテーブルを用いるのでCPU cacheの汚染がひどいように思っています。単体スレッドでのベンチマーク値では表面化しにくいですが、マルチスレッドでのベンチマーク値に影響が出てきます。また、EvalHashのような仕組みを並行して利用しようとした場合、EvalHashのほうのパフォーマンスに影響が出かねないので、結局、このような大きなテーブルを用いる実装はトータルでは得しないというのが私の考えです。(やねうら王2017ではpext命令を使っており、magic bitboardを用いていませんし、また、pext命令のためのテーブルももったいないので非常に小さなテーブルしか用いていません。)

追記2017/11/22 3:30

かず@なのはさんによるとmagic bitboardを使って場合、オリジナル(Bonanza実装?)の速度にわずかに達しなかったという記述がPonanzaの山本君の論文にあるそうです。

「magic bitboard論争に終止符を」への8件のフィードバック

  1. >AVX256を使えば命令数はさらに半分で済みます。ただAVX256とSSE命令と混在させる場合、VZEROUPPERを呼び出してレジスタの上位128bitをクリアしないといけなかったりするので実質的にこのタイミングでは使えないのですが…。

    AVX128命令を使えばいいと思います。
    というかAVX命令を使うコンパイルオプションだと従来の
    SSE命令に変換される組み込み関数でも、SSEは使われず、AVX128が使われたはずです。

    返信 ↓

      • そーなんですね(´・ω・｀)
        話は変わりますがいつか、
        「やねうら天才になる方法」みたいな記事が読みたいです。
        普通のプログラマとやねさんの思考の違いが知りたいです。
        天才プログラマはどういう思考をしているのか。
        プログラミングの超速い人と普通の人との違いが知りたいです。
        そこに天才はできていて、普通の人が出来ていない違いがあるのか。
        ひいては、天才と普通の人との違いが見えてくると、能力開発のヒントが見えてくるかもと。
        天才になりたーいです。

        返信 ↓

        • 私が天才なのかどうかはさておき、数学の問題を解くときの思考法が他の領域でも役立つことが多々ありますね。ポリアの『いかにして問題をとくか 』(ISBN:4621045938)とか名著だと思いますけども。

          返信 ↓

          • ありがとうございます！
            購入しました！
            出来ているひとの当たり前みたいなものを学んでみます！

コメントを残す

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