GPU computingによるbitboard実装の実験

clz(count leading zero, x86ではlzcnt)を利用できるとき、bitboardの着手(move generator)は、右向きにはclz、左向きにはキャリー伝播(T.Ishiiさんの解説)を用いて、分岐なしで書くことができます。 OpenCL風に書くと、
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桁遅い結果になりました。
これでもうまくCPUと並列に使えば1割程度高速化できる可能性は残りますが、GPUの構成上ある程度のブロックをまとめて渡さなければピーク性能は得られず、実装は容易ではありません。

というわけで実用性に欠けるコードになりましたが、同じことを考えている方のために、参考までに公開します。(GPL3)
warp内のsyncthreadsを省略できるのと(ifの中なので特に重要)、voteやshuffleが使えると性能上有利なので、CUDAにより実装しています。


参考文献

Parallel Minimax Tree Searching on GPU, Kamil Rocki, Reiji Suda (2010)
ReversiのmidgameのMinimaxをGPUに実装する実験。 divergence(ここでは着手可能数の変動)が少ないとき、GPUの効果があるということですが、α-βでないMinimax同士の比較です。
Parallel Alpha-Beta Algorithm on the GPU,Damjan Strnad, Nikola Guid (2011)
Reversiのmidgameのα-βをGPUに実装する実験。やはり8*8ではCPUより遅いようです。
GPU AI for Board Games, Avi Bleiweiss, NVidia (2010)
プレゼンテーションスライドによれば、 Reversiでは同時試合数16384のときGPUがCPUの5.88倍とのこと(一試合ではCPUが速い)。 私のPCではなぜかサンプルがインストールできません。

奥原 俊彦

Booby Reversi Home