Bonanzaの手駒の優劣比較にはあまり知られていない技法が使われている

■　Bonanzaの手駒の優劣比較にはあまり知られていない技法が使われている

以前、Bonanzaの手駒のbit layoutについて書いたときに、駒のbit fieldをpaddingしておけば優劣比較が引き算一発で済みますよという話を書いた。

Bonanzaの手駒のbit layoutはどうなっているか
http://d.hatena.ne.jp/LS3600/20090926

そのときに保木さんご本人から、

確かに、駒の優劣関係は padding した方が良いですね。

padding しない場合の利点は、局面表にそのまま格納できるという事でしょうか。

普通に char hand_black[7] としても実行速度はあまり変らなかったりすると思います。

というコメントをいただいた。

「局面表にそのまま格納できる」が具体的に何を指すのか、私はまだそこまでBonanzaのソースコードを読み込んでいないのでいまひとつよくわからない。

仮に持ち駒が4byteではなく3byteに格納できることに意義があるということであれば、例えば次のように部分的にpaddingしておけば、引き算 + αで手駒の優劣比較ができる。

  xxxxxxxx xxxxxxxx xxx11111  pawn    歩
  xxxxxxxx xxxxxxxx 111xxxxx  lance   香
  xxxxxxxx xxxx0111 xxxxxxxx  knight　桂
  xxxxxxxx 0111xxxx xxxxxxxx  silver　銀
  xxxx0111 xxxxxxxx xxxxxxxx  gold　　金
  xx11xxxx xxxxxxxx xxxxxxxx  bishop　角
  11xxxxxx xxxxxxxx xxxxxxxx  rook　　飛

このようなbit layoutにしておけばutility.cのis_hand_eq_supeの以下の部分は、次のように書き換えることが出来る。

  if ( IsHandKnight(u) < IsHandKnight(uref)
       || IsHandSilver(u) < IsHandSilver(uref)
       || IsHandGold(u)   < IsHandGold(uref)
       || IsHandBishop(u) < IsHandBishop(uref)
       || IsHandRook(u)   < IsHandRook(uref) ) { return 0; }
		// 手駒の数がひとつでも劣っていれば優れている局面ではないはずだから0を返す。
		// 何故ここで歩と香の数を比較しないんだろう？

↓↓↓　こう書き換える。

	// 歩と香をmaskして、かつ飛車を1ビット左シフト
	u32 u2 = (u & 0x3fff00) | ((u & 0x0c00000) << 1);
	u32 uref2 = (uref & 0x3fff00) | ((uref & 0x0c00000) << 1);

	// uの各bitfieldのMSBがどこか1になっていればそれはborrowが発生したということで、
	// そのfieldは u < urefであったことがわかる。
	if (((u2-uref2) & 0x2488800)!=0) return 0;

条件分岐が減ってはいるので多少効果はあるとは思うが、あまりすっきりしない。

Bonanzaの置換表へ登録する部分のソースを読み直してみると手駒は21bitに収まる必要があって、24bitだと駄目のようだ。

この点、お詫びして訂正したい。またお詫びがてらにBonanzaのこの部分の改良コードを以下に示す。次のBonanzaのコード

  if ( IsHandKnight(u) < IsHandKnight(uref)
       || IsHandSilver(u) < IsHandSilver(uref)
       || IsHandGold(u)   < IsHandGold(uref)
       || IsHandBishop(u) < IsHandBishop(uref)
       || IsHandRook(u)   < IsHandRook(uref) ) { return 0; }

を、ビット演算で書くには、以下のようにする。

	// 0x19c700 = 桂、金、飛だけ残すマスク
	// 0x220800 = 桂、金、飛のfieldのひとつ上のbit
	u32 uA = ((u & 0x19c700) - (uref & 0x19c700)) & 0x220800;
	// 0x063800 = 角、銀だけ残すマスク
	// 0x084000 = 角、銀のfieldのひとつ上のbit
	u32 uB = ((u & 0x063800) - (uref & 0x063800)) & 0x084000;
	
	// uA,uBの各bitfieldのMSBがどこか1になっていればそれはborrowが発生したということで、
	// そのfieldは u < urefであったことがわかる。
	if ((uA | uB)!=0) return 0;

桂、金、飛というようにfieldをひとつずつ飛ばして拾えば、paddingされているのと同じ意味になるので、引き算をすればそれらに対して優劣が求まるという原理である。速度的にはわずかに改善していると思うが、あまり変わらないかも知れない。

それはさておき、Bonanzaのソースコードで、この部分で歩と香の数を何故比較していないのかというとその直後のコードが次のようになっている。

  nsupe  = (int)IsHandRook(u) - (int)IsHandRook(uref);
  nsupe += (int)IsHandLance(u) - (int)IsHandLance(uref);
  if ( nsupe < 0 ) { return 0; }

  nsupe += (int)IsHandSilver(u) - (int)IsHandSilver(uref);
  nsupe += (int)IsHandGold(u)   - (int)IsHandGold(uref);
  nsupe += (int)IsHandPawn(u)   - (int)IsHandPawn(uref);
  if ( nsupe < 0 ) { return 0; }

  return 1;

すなわち、歩は香と銀、金、飛で完全に代用でき、かつ、香は飛で完全に代用できる。よって、盤面が同じで手駒の歩が飛に入れ替わった局面は、元の局面と完全に優越関係にある局面である。

Bonanzaのソースコードで、歩・香の枚数の比較を先延ばしにして、上のように比較しているのはそのためである。

しかし、この部分、Bonanza4.1.2のコードは実はバグっていると私は思う。

IsHandRookなどIsHand〜という関数(実際はマクロだが)は、同じ持ち駒の枚数の大小を判定するためのもので、ビットシフトは兼ねていない。よって、上のコードのように異なる種類の駒の枚数を加算したいときには問題がある。

ここを保木さんの意図通りにするには、上のnsupeに加算している部分はIsHand〜ではなく、I2Hand〜という関数を用いるべきだと思う。

■　まとめ

今回はBonanzaの手駒の優劣関係を比較するコードについて詳しく調べた。

「歩は香と銀、金、飛で完全に代用でき、かつ、香は飛で完全に代用できる」という事実を利用しているのは、目新しく、私はこのテクニックを知らなかった。

本文で書いたようにBonanzaのこのコード自体がバグっているのは少し残念だが、まあ、手駒の歩が香と入れ替わるような局面はあまり出現頻度は高くないと思うので、影響はほとんどないのかも知れない。