Hatena::ブログ(Diary)

Bonanzaソース完全解析ブログ

2009-11-11 Bonanzaの指し手表現は何故優れていると言えるのか このエントリーを含むブックマーク このエントリーのブックマークコメント

■ Bonanzaの指し手表現は何故優れていると言えるのか


指し手生成祭り開催
http://d.hatena.ne.jp/LS3600/20091110


指し手生成に関して、「私の将棋ライブラリ」で2.15M/sec、Bonanzaが1.1M/sec、misakiが私の方法を取り入れて300K/sec→600K/secになりました。C#で書かれているBlunderはまあ仕方ないとしても、C/C++でなおかつbitboardを使っているmisakiの指し手生成自体は(私に言わせれば)遅すぎます。


それで何故遅いのかというと、ここに書かれているように、misakiはれさぴょんのコードを引きずっているからだと思います。
http://d.hatena.ne.jp/mkomiya/20091110/1257785583

typedef struct {
	uchar from;
	uchar to;
	uchar koma;	// 自駒
	uchar capture;	// 取った駒
	uchar promote;	// 成るフラグ
	short value;	// 評価値
} Te;

実はこのれさぴょんのコードは実行速度的な観点からすると、とても劣悪なコードなのですが、素人目には、これをpackして無理矢理32bitなどに収めるとそこからunpackするためのコードが必要になって速度が低下するように思えます。


実際、小宮さんは次のように書いています。

多少ロジックが発生しても、メモリを読み書きしないことが重要という観点からは
bonaのように持つべきかも知れない。

私は、これを見て、小宮さんはとても大きな勘違いをされているんだな、とわかりました。


それは、「多少ロジックが発生しても」です。


■ packされた指し手とされていない指し手はコンパイラによってどういう命令に変換されるのか


例えば、32bitにpackされた指し手から、成り/不成を判定する次のコードがあったとしましょう。

u32 IsPromote() const { return ((move) & FLAG_PROMO); }


たいていは直前で指し手関係の変数をいじっているので、このとき指し手は、レジスタに割り付けられています。そうすると、

	if (move.IsPromote())

というコードは次のように、レジスタ(ここではedi)のビットテストを行なうコードとそれを判定するコード、すなわち典型的には次の2命令にコンパイルされます。

0004588D  test        edi,4000h 
00045893  je          UnitTest+111h (458A1h) 

しかし、れさぴょん方式ですと、まだアクセスもしていないfieldがレジスタ割り付けされていることは得ないので、メモリから取り出すコードが必要になります。メモリから取り出してそれが0かどうかを判定するためには、典型的には、いったんレジスタに0を代入して、そのレジスタとメモリを比較するコードが生成され、結局、次のように3命令生成されます。


010A569E  xor         eax,eax 
010A56B6  cmp         byte ptr [esp+13h],al 
010A56BA  je          UnitTest+46h (10A56C6h) 

さて、どちらのほうが速いでしょうか?言うまでもなく前者です。仮に前者のケースでレジスタ割り付けされていなかったとしても、メモリから取り出すコードが追加されるだけですから、後者のコードと同等です。しかも前者のケースでレジスタ割り付けされていないケース自体がレアケースです。


ToやFromを取り出すときは余計なロジックが必要になるんじゃないか?と言われそうですが、ToやFromなんて使いません。Bonanzaでも探索中はほとんど使われていないので心配いりません。


BoardPosをToやFromに変換したいことはあります。そのときには、From2MoveやTo2Moveを使います。典型的には、次のコードです。これは銀のnocapの指し手の生成ルーチンの一部です。

  foreach_bitboard_lastone2_no_check(bb_piece,from,
  {
    bb_desti.p[1] = bb_p_empty.p[1] & abb_b_silver_attacks[from].p[1];
    bb_desti.p[2] = bb_p_empty.p[2] & abb_b_silver_attacks[from].p[2];

    u32 utemp =  From2Move( from ) | Piece2Move( silver );
		foreach_bitboard_lastone12_no_check(bb_desti,to,
		{
      // 自陣からなのでこの銀が成れるということはありえない。
      *pmove++ = utemp | To2Move( to );
    });
  });

from,toは直前で使用していますから、まず間違いなくレジスタ割り付けされています。説明を簡略化するためにボトルネックになりそうな最内ループについてだけ見てみましょう。


00AF0C5C  mov         esi,35h									 // esi = bsrした値を35hから引いてBoardPosに変換。これでTo2Move( to )が完了
00AF0C61  sub         esi,ecx
00AF0C63  or          esi,edx                  // esi |= utemp
00AF0C65  bsf         ecx,ebp
00AF0C68  mov         dword ptr [eax-4],esi    // *pmove = esi

とまあ、結局、To2Moveは実際には省略されてコードには全く出てこないのです。何故かというと、BonanzaではTo(移動先)は、指し手の下位7bitであってTo2Moveにビットシフトは不要だからです。


強いて言えば、上のコードの or esi,edx の部分がれさぴょんで Te.To に格納するためのコードに相当するので、費やしている命令数で言うと1命令ということになります。れさぴょんと比べてコードの質として全く遜色がないことがわかります。


「To2MoveはそうだけどTo2Fromはビットシフトがいるだろ」と思われるかも知れませんが、上のループを見てもわかるように、指し手生成というのは、Fromは最内ループの外側で決定して、Toだけが最内ループで変化するというのが典型的です。Bonanzaではこのことを考慮して、FromではなくToを下位7bitに割り当ててあるわけです。


また、To2Fromも、ビットシフトが必要な代わりにTe.Fromに格納するコードが省略できるので(上のコードのように一度のメモリへの転送だけで済むので)、この時点で命令数としては相殺しています。実際はもっと他の理由もいろいろあって、さらにBonanza方式のほうが圧倒的に有利なのですが今回の主旨を大きく超えているのでこれくらいにしておきます。


以上で見てきたように、れさぴょん方式のコードが、Bonanza方式のコードに勝ることはあり得ないのです。「多少ロジックが発生しても」は大きな間違いで、ロジックが発生するどころか、ロジックはむしろ減るのです。それも必ず確実に減るのです。


あと付け加えるなら、「メモリを読み書きしないことが重要」なのではありません。どうせ生成した指し手自体はすべてL1 cacheに入るでしょうから、(もし命令数が同じなら)メモリへの書き出しで損はしません。れさぴょん方式は、上で見てきたように命令数においてすでに損をしていたのです。(実際は、れさぴょんの構造体では、初期化や読み出し/書き出し/コピーにも大幅に命令を消費しますが)


ですので、Bonanza方式のデータ構造で頑張ればれさぴょん方式のデータ構造にくらべて指し手生成が2倍や3倍速いのは当たり前なのです。逆に言えば、れさぴょん方式がBonanza方式に比べて指し手生成が2倍や3倍遅いのは当たり前なのです。


■ まとめ


Bonanzaの指し手構造体が何故高速なのかを説明した。また、れさぴょんの指し手構造体が高速化の観点からは大変まずいデータ構造であるということを説明した。


れさぴょん自体は教育的なコードを目指して書かれているので、わかりやすいコードにしようとしてそうなったのかも知れないが、真にコンピュータ将棋開発者に対して教育的な配慮をするなら、うさ親さんには是非この記事のことも広く知らしめて欲しいと願う次第である。

mkomiyamkomiya 2009/11/10 10:31 32bitへのpackの方がかなり有効のようですね。
misakiも書き換える決心がつきました。
解説ありがとうございます。

ただ、ロジックが減っているのは、レジスタを使うことでの
最適化の結果なので、
概念上はロジックが増えるのは間違ってないと思います。
(その程度の意味です)
おっしゃられていることは解ります。

以前、popCntを、表引きとシフトなどを使う方法で比較したときに、後者が速かったので、
(L1に乗ったとしても、レジスタだけで回した方が速かった)
指し手の持ち方に関しても、同じことが言えるのだろうと思いました。

LS3600LS3600 2009/11/10 11:25 ああ、意味わかりました。了解です。

usapyonusapyon 2009/11/11 21:36 TrackBackしておきますw

LS3600LS3600 2009/11/12 05:39 TrackBack感謝します。