Magic BitboardはPEXT Bitboardのエミュレートである

もちろん時系列的にはMagic Bitboardのほうが先に現れているので現実に存在するPEXT BitboardをMagic Bitboardがエミュレートしたわけではない。しかしながらMagic Bitboardは、ばらばらに散らばっている走り駒*1の利きに関するビットを下位ビットに集めて表引きで利きを求める手法であり、利きに関するビットを下位ビットに集めるという操作はPEXT命令の操作そのものである。よってMagic Bitboardとは当時は存在しなかった(仮想の)PEXT Bitboardをエミュレートした存在であると言える。

  なぜ掛け算(とビットごとの論理和とシフト)でPEXTをエミュレートできるか

 この事を理解するためにはまず(2進数の)掛け算がどういうビット操作になるかを考えないといけない。

2進数の掛け算とはどういう操作か?

まずある非負の整数aに0をかけてみよう。当然0である。

次にaに1をかけてみよう。aのままである。

次にaに2のn乗*2をかけてみよう(nは非負の整数とする)。aをnビット左シフトした値になる。ここまではよく知られていると思う。

次にxに十進表示での3、つまり二進表示での11をかけてみよう。3aになるわけだが注意して考えればこれは2a+1aとなることがすぐに分かる。 これはつまりaを1ビット左シフトした値と0ビット左シフトした値を足し合わせた値である。

 次にaに二進表示で1100110でもかけてみよう。これも3をかけたときと同じ考え方を使えばよい。1100110を複数の2のn乗に分けてそれぞれを左シフトして足し合わせればよい。そして2進数表示だと何ビット左シフトしたものを足し合わせればよいか見極めるのは簡単である。右端の位を0桁目として1が立っている桁を見て行けばよい。1100110の場合1,2,5,6である。

以上より定数をかけるという操作は左シフトと足し算の組み合わせになっていることが分かると思う。

 

次に足し算について考えてみる。

まずは1bitの足し算から考える。これは4通りしか無い。0+0=0,1+0=1,0+1=1,1+1=10である。

これをよくみれば最下位桁はXORとなり、繰り上がりがANDになっていることが分かると思う。

次に桁あがりがある場合にそなえて3つの1bitの数の和について考えてみる。

0+0+0=0,0+0+1=1,0+1+0=1,1+0+0=1,0+1+1=10,1+0+1=10,1+1+0=10,1+1+1=11となる。

これをよくみれば最下位桁はaXORbXORcの形となり、繰り上がりが3項中2項以上1なら1になっていることが分かると思う。

次に複数bitの足し算a+bのあるbitを考えてみる。(a,bのnbit目をan,bnとし下の桁ほどnが小さいとする。またmajor(a,b,c)はa,b,c3項中0が2項以上であれば0、そうでなければ1となる関数とする)

繰り上がりが無ければanXORbnとなるが桁上がりがあるためanXORbnXOR(major(an-1,bn-1,major(an-2,bn-2,major(・・・))))となることは分かると思う。*3

煩雑になるので書かないが複数項の足し算の結果の各ビットも論理演算でうまく書けそうであることは想像できるだろう

しかもMagic BitboardではまずANDでマスクをかけるために0となっていることが確定しているビットが多く、定数(マジックナンバー)をうまく選んでやればビットの重なりを元のビットがどうだったか検出出来るくらいにはうまく避けられそうである*4

Magic Bitboardの操作を追いかけてみる

まずは利きに関係しうるビットだけを残すためにANDでマスクをかけてある。ここまではビット演算の基礎なので大丈夫だろう。

次に定数をかけてあるわけだがここまでの内容を思い出して欲しい。これは左シフトしてその結果を足し算でまとめているにすぎない

もっとも単純な形で見たい各マスの駒の有無がそのまま入っている形であり、複雑でもみたい各マスの駒の有無を見極めるのに十分な内容が連続する十数ビットに入るのである。

もちろんそのためには定数を注意深く選ぶ必要があり、Bitboardではその定数を探すのは人間業では無いため、乱数を発生させて条件を満たす定数が探された。

後はこの連続する十数ビットを一番下まで持ってくるために、論理右シフトするだけである。上位側に出てくるであろうごみデータは定数を工夫してオーバフローであらかじめ消しておけばよい。

後はMagic Bitboard、PEXT Bitboard共通の作業で利きを表引きしてやればよい。*5

*1:チェスではQueen,Rook,Bishop将棋では飛角香

*2:2進表示だと1の後にn個0が続く数になる

*3:分からなかったら全加算器あたりでググって。ここより詳しく解説していると思う

*4:避けられることは自明ではないと思うが、現実にはうまく避ける事が出来た

*5:MagicとPEXTで操作された結果下位bitにまとめられたマスごとの駒の有無のbit位置等は異なるので引くテーブルは違うものになる