ulong flip(int pos, ulong P, ulong O)
{
ulong4 flipped, OM, outflank, mask;
OM.x = O;
OM.yzw = O & 0x7e7e7e7e7e7e7e7eUL;
mask = (ulong4) (0x0080808080808080UL, 0x7f00000000000000UL, 0x0102040810204000UL, 0x0040201008040201UL) >> (63 - pos);
outflank = (0x8000000000000000UL >> clz(~OM & mask)) & P;
flipped = (-outflank * 2) & mask;
mask = (ulong4) (0x0101010101010100UL, 0x00000000000000feUL, 0x0002040810204080UL, 0x8040201008040200UL) << pos;
outflank = mask & ((OM | ~mask) + 1) & P;
flipped |= (outflank - (outflank != 0)) & mask;
return flipped.x | flipped.y | flipped.z | flipped.w;
}
これを試しにGPGPUに実装してみました。
GPUでは同期して動作するある程度のスレッド数(CUDAでは32)が必要なので、5カ所空きの完全読みを並列処理するようにしました(5! = 120通りのBrute force)。
SIMTが有効に使えるとき、GPUはCPU以上の演算能力がありますが、Brute forceのために打てない空きや、α-βでは枝刈りされるノードにまで演算ユニットを割り当てることになり、（CPUとGPUの性能にもよりますが）残念ながらピーク性能としてもCPUのα-βより1桁遅い結果になりました。
これでもうまく使えば高速化できる可能性は残りますが、GPUの構成上ある程度のブロックをまとめて渡さなければピーク性能は得られず、実装は容易ではありません。
というわけで実用性に欠けるコードになりましたが、同じことを考えている方のために、参考までに公開します。(GPL3)
warp内のsyncthreadsを省略できるのと(ifの中なので特に重要)、voteやshuffleが使えると性能上有利なので、CUDAにより実装しています。