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の指し手構造体が何故高速なのかを説明した。また、れさぴょんの指し手構造体が高速化の観点からは大変まずいデータ構造であるということを説明した。
れさぴょん自体は教育的なコードを目指して書かれているので、わかりやすいコードにしようとしてそうなったのかも知れないが、真にコンピュータ将棋開発者に対して教育的な配慮をするなら、うさ親さんには是非この記事のことも広く知らしめて欲しいと願う次第である。
