2009-11-29

■　まえがき

今回から何回かにわけて差分指し手生成の具体的な手法について書いていきます。

差分指し手生成をしても普通に生成するより遅くなっていては何の意味もなく、差分指し手生成によって普通に生成するより速くならなくてはなりません。

つまり、どのようなC++のコードを書けばどのようにx64のコードに変換されて、それが何サイクルで実行できるのかまでを具体的に示さなければ、出来たとは言えません。

そこで、ここではなるべく具体的に示していこうと思います。

■　その前に論文をどこかに提出すべき？

コンピュータ将棋で差分指し手生成が実際に成功した前例は無いはずで、少なくとも実際にコードを示してそれが普通の指し手生成より高速であることを証明されたというのは私は聞いたことがありません。

どこかに論文を提出することによって、広く知ってもらえるならそうしたいのですが、私はヒキコモリなので「GPWで発表しる！」とかはたぶん出来ません。何か良い方法があればコメント欄等で教えていただけると幸いです。

■　差分指し手生成の基本コンセプト

各駒の利きを持っておいて、移動させる駒のfromかtoにその利きが交差していればその駒の指し手だけ生成しなおすというのが基本的なコンセプトです。

ただ、それだけではあまり高速ではないので実装する上で他にいろいろ工夫がいります。

細切れになった指し手を回収する(シリアル化する)のに時間がかかりすぎたり、dirty flag(指し手の再生成が必要な駒に対するフラグ)のチェックが時間がかかりすぎてなかなか元がとれないのです。

これを元をとるためには、いくつものテクニックを組み合わせる必要があります。

コンピュータチェスの場合、駒が大駒ばかりなので、fromとtoに利きを持つ駒が結構あって差分指し手生成で成果を出すのは難しいでしょう。これは、(1つの駒の移動距離が全体的に小さい)コンピュータ将棋特有のものです。

■　差分指し手生成の3つの段階

差分指し手生成とは次の3つの段階にわかれます。

1) MakeMoveで利きの更新を行ない、影響を受ける駒を確定させておく。

2) gen_XXXでは、そこでdirty flag(指し手のupdateを要する駒を示すフラグ)の立っている駒だけ指し手の生成をしなおす。

3) gen_XXXでは、そのあと生成された指し手をシリアル化する。

なお、gendropや王手がかかっている局面に関しては注意が必要ですが、それらについては追々説明をしていきます。今回は、1)について解説します。

■　dirty flagとは何か？

差分描画のときに更新の必要な最小矩形のことをdirty rectと呼びますが、それと同じでdirtyというのは、「汚れた」(＝ updateの必要な)という意味でここでは使います。

移動させる駒の移動元(from)と移動先(to)のいずれかに利きが交わっている駒に関しては指し手を再度生成しなおす必要があります。すなわち、dirty flagのビットを立てる必要があります。

dirty flagは、各駒ごとに1bit消費するので40駒で40bit使います。これは64bit変数1つにぴったり(?)収まるので非常に都合が良いです。

また、利きは(Bonanzaでは)歩だけは先手と後手とですでにbitboardを持っています。ですので、それら18枚を除く40-18 = 22枚の利きを新たに用意します。

これらの利きと交差している駒に関してのみdirty bitを倒していく作業が必要になります。疑似コードで示すと次のようになります。

	bitboard mask = abb_mask[from] | abb_mask[to]; // fromとtoの地点が1であるbitboard
	u64 dirty_flag = 0;
	foreach attack in attacks[0..21]
		dirty_flag = dirty_flag*2 + (mask & attack) ? 1 : 0;

これをいかに高速化するかが、差分生成が成功するか否かの鍵になります。

■　double-sized bitboardを用いる

ここで、利きのbitboardとしてDBB(= double-sized bitboard → http://d.hatena.ne.jp/LS3600/20091123 )を用います。

DBBのp64[0]には、盤面の上64マス、p64[1]の片方には、盤面の下17マス。p64[2]には、盤面の下64マス、p64[1]のもう片方には、盤面の上17マスを格納しておきます。

要するに利きに関しては局面を冗長に持っているのですが、更新の手間は、64bit幅でアクセスして良いなら、p64[2]のためのアクセス回数が1度増えるだけなので、たかだか50%しか増えません。

利き情報は、動かした駒の利きと、その駒によって利きに影響を及ぼされたとき(香を含む大駒のみ)更新が必要になるだけですから、ここがp64[2]のためにアクセス回数が1回増えてもそれは無視できる程度の追加コストです。

こうすると何が嬉しいかというと、{ from , to }が、必ずp64[X]のどこかに収まるということです。

すなわち、
0) fromとtoが両方とも1〜7段目である → fromとtoのbitはp64[0]に存在する。
2) fromとtoが両方とも3〜9段目である → fromとtoのbitはp64[2]に存在する。
1) fromとtoの片方が1〜2段目で、もう片方が8〜9段目である。→ fromとtoのbitはp64[1]に存在する。
のです。{ from , to }の組み合わせは必ずこの3つのいずれかに分類されます。

よって、実際はbitboard全体(3×sizeof(u32))を調べる必要は無く、p64[X]をひとつ調べるだけで良いのです。

疑似コードで書くと次のようになります。

	fromとtoに関して X = 上記0)〜2)に場合わけ。

	// fromとtoの地点が1であるdouble-sized bitboardのp64[X]
	u64 mask = adbb_mask[from].p64[X] | adbb_mask[to].p64[X];

	u64 dirty_flag = 0;
	foreach attack in attacks[0..21]
		dirty_flag = dirty_flag*2 + (mask & attack.p64[X]) ? 1 : 0;

■　unrollしてみる

当然、この疑似コードのforeachの部分はunrollします。

		dirty_flag = dirty_flag*2 + (mask & attack[0].p64[X]) ? 1 : 0;
		dirty_flag = dirty_flag*2 + (mask & attack[1].p64[X]) ? 1 : 0;
		dirty_flag = dirty_flag*2 + (mask & attack[2].p64[X]) ? 1 : 0;
			…
		dirty_flag = dirty_flag*2 + (mask & attack[21].p64[X]) ? 1 : 0;

2倍して足し算をしているのが無駄に思えるかも知れませんが、これはlea XXX,[YYY + ZZZ*2]の形になるので無駄ではありません。このときシフトを使ってはいけません。シフトだと一般的に言って命令のpairingがしにくいからです。

また、3項演算子が無駄に見えるかも知れませんが、これは neg → sbbで済みます。

negは否定をとりたいのではなく、非0ならcarry flagが1になります。
sbbはsubtraction with borrowです。carry flagを含めた引き算です。sbb XXX,XXXと書くとcarry flagが1だとXXXは-1、さもなくば0になります。

すなわち、neg→sbbという2命令で、非0なら1、0なら0という変換が出来ます。結局、上のソースの1行は次のように5命令に変換されます。(このコードは32bit環境で開発しているので、32bit幅になっていますが、実際は64bit幅で計算しなくてはなりません。念のため。)

00FD1033 8B 15 88 6A FD 00 mov         edx,dword ptr [attack+8 (0FD6A88h)] 
00FD1039 23 D0            and         edx,eax 
00FD103B F7 DA            neg         edx  
00FD103D 1B D2            sbb         edx,edx 
00FD103F 8D 0C 4A         lea         ecx,[edx+ecx*2]

sbbの部分が、直前で変化したcarry flagを見る命令(いわゆる参照命令)なので、アーキテクチャによってはこの部分で1サイクルの遅延が発生するかも知れません。そこを除けば比較的良いコードで、この5命令はCore 2 Duoでは2.5サイクル弱で実行できます。

実は上のコードは、もう1命令減らして4命令にすることも出来なくはないのですが、それについては今回は割愛します。

ともかく、上のコードで、22駒に関しては2.5サイクル弱×22駒程度で完了することがわかりました。

歩はまとめて検出できるので、平均すればこの2.5サイクルよりさらに小さいサイクルで更新ができます。同じようにDBBを用いて、bsr(→ http://d.hatena.ne.jp/LS3600/20091117 )をしていくだけですね。toとfromは2つの地点しか示しませんから、更新の必要な歩の数は最大でも2つです。知れてますね。

以上のようにして、かなり多く見積もっても 40駒×2.5サイクル = 100サイクルにて「1) MakeMoveで利きの更新を行ない、影響を受ける駒を確定させておく」が出来ることがわかりました。実際は75サイクル前後で終わると思います。

また、100サイクルということは、Core 2 Duo 2.8GHzでも28M回/secは出来るということですね。

Bonanzaソース完全解析ブログ

差分指し手生成の手法その1