連載やねうら王miniを強くしよう！6日目

投稿日時: 2016年1月7日投稿者: やねうらお

今回は、協力詰めの話は少しお休みして、優等局面の判定について解説します。というのも、この優等局面の判定もまた協力詰めに必要だからです。しかし、話が大変長くなるので、今回は、この話題について集中して非常に詳しく書きます。

優等局面/劣等局面とは？

優等局面というのは、盤面(手駒を含まず)と手番が同じで、手番側の手駒だけが増えている局面のことを言います。その反対に、手駒だけが減っていれば劣等局面と言います。

敵玉に歩を打って王手して、玉を交わして、そのあと歩を成り捨てて同玉と4手進むと、元の盤面と同じで、1歩損をした局面に突入します。これが劣等局面です。

協力詰めや詰将棋はもちろんのこと、実戦でも優等局面や劣等局面は出現するのでこれについてどう取り扱うかというのは重要です。

まず、この判定をどうやれば簡単に出来るかということを考えてみましょう。

盤面と手番が同一であるかの判定

「盤面と手番が同一であるか」を判定するためには、盤面 + 手番のhash keyが計算されていれば、そのhash keyが一致するかどうかだけを調べれば済みます。

置換表でよく用いられるhash keyは、盤面 + 手番 + 手駒によるhash keyとなっていますが、これとは別に盤面のhash keyも計算しておくことにします。

しかし、この２つのhash keyを個別に計算して更新するのは盤上の駒が動いたときに重複した計算が必要になって計算コストがもったいないので、実際は、「盤面 + 手番」のhash keyと、「手駒」のhash keyとの２つに分けて計算し、局面のhash keyは、前者と後者とをxor(もしくはadd)したものを返すようにします。このアイデアはAperyのものです。

ということで、

struct StateInfo {
Key key()       // 局面のhash key
Key key_board() // 盤面のhash key
Key key_hand()  // 手駒のhash key
…
};

struct StateInfo {

Key key() // 局面のhash key

Key key_board() // 盤面のhash key

Key key_hand() // 手駒のhash key

…

};

のようにそれぞれのhash keyが得られることになっています。これを使います。

手駒が優等であるかの判定

次に手駒が相手の手駒より優れているかの判定を行なう方法を考えます。

単純には、相手よりすべての種類の駒種において相手の持っている枚数より多ければ良いので、次のようなコードになります。

      bool is_equal_or_superior =
        hand_count(h1, PAWN) >= hand_count(h2, PAWN) &&
        hand_count(h1, LANCE) >= hand_count(h2, LANCE) &&
        hand_count(h1, KNIGHT) >= hand_count(h2, KNIGHT) &&
        hand_count(h1, SILVER) >= hand_count(h2, SILVER) &&
        hand_count(h1, BISHOP) >= hand_count(h2, BISHOP) &&
        hand_count(h1, ROOK) >= hand_count(h2, ROOK) &&
        hand_count(h1, GOLD) >= hand_count(h2, GOLD);

bool is_equal_or_superior =

hand_count(h1, PAWN) >= hand_count(h2, PAWN) &&

hand_count(h1, LANCE) >= hand_count(h2, LANCE) &&

hand_count(h1, KNIGHT) >= hand_count(h2, KNIGHT) &&

hand_count(h1, SILVER) >= hand_count(h2, SILVER) &&

hand_count(h1, BISHOP) >= hand_count(h2, BISHOP) &&

hand_count(h1, ROOK) >= hand_count(h2, ROOK) &&

hand_count(h1, GOLD) >= hand_count(h2, GOLD);

ダサいです。そして遅いです。こんなことは絶対にしてはなりません。

手駒の関係は4パターンある

ではどうするのか…という前に、自分の手駒(Hand構造体)と、相手の手駒(Hand構造体)とで、どういう関係があるか整理してみましょう。

パターン1. 同等(equal)

すべての駒種の枚数について、自分と相手と等しい状態。Hand構造体の値自体が等しい状態。

パターン2. 優等(superior)

すべての駒種において相手と同じか相手よりたくさん持っている状態を言います。ただし、同等のケースは除きます。これを簡単に求める方法をいま探しています。

パターン3. 劣等(inferior)

すべての駒種において相手と同じか相手より少なく持っている状態を言います。ただし、同等のケースは除きます。

パターン4. それ以外(misc)

上記の3パターンのいずれにも該当しないパターンです。自分は歩だけを持っていて、相手は香だけを持っているだとか、そういうケースにおいては上記のいずれにも該当しません。

このように考えると、実は「優等」の論理的な否定(“!”演算子をつけた場合) は、「劣等」ではなく、「優等ではない」のですから、「同等」「劣等」「それ以外」の3つのケースがあるのです。

「優等」の反対概念は「劣等」ですが、「優等」の否定は「劣等」ではないわけですね。このへん、勘違いしているとバグの原因となります。

同じく、「優等」＋「同等」(優等もしくは同等である)の否定は、「劣等」＋「それ以外」です。よく、これを間違って「劣等」かと思ってしまうので、上の4パターンであることを頭に叩き込んでおきましょう。

ビット演算で書けないか

「優等」＋「同等」を判定するコードを簡単な演算で書けないか考えてみましょう。

手駒は、bit 0..4が歩の枚数、bit5..7が香の枚数,…のようにpackされた32bitの整数として保持しています。

そこで、software packed演算の技法を用いてこれを計算できないかをまず考えます。

歩の枚数、香の枚数、桂の枚数、…、それぞれを引き算して、ボロー(借り)がでなければ優等もしくは同等であることはわかります。

飽和加算の技法を応用して、飽和減算のようなコードを書けば、その過程でボローが出るかどうかは判定できます。飽和加算については以下の記事を挙げておきます。

縦型Bitboardの唯一の弱点を克服する

確か、Bonanza6のこの部分のコード、software packed演算で済ませる方法を私が発明して、そのコードを保木さんに送った覚えがあるんですけど、わかりにくくなるので採用は見送られたような覚えが。

ボローをもっと簡単に検出する方法がないか？

あります。

bit 0..4が歩の枚数、bit5..7が香の枚数,…となっているところ、
bit 0..4が歩の枚数、bit6..8が香の枚数,…
のように1bit隙間をあけておきます。こうすれば引き算して、ボローがあれば、この隙間のbitが1になります。

こうすることで、この隙間のbitが1でなければ、(引き算の結果)ボローがでなかった＝優等もしくは同等である、と言えます。

このようなビットレイアウトにするデメリットは、このHand構造体を置換表に格納するときに隙間があって、ぎちぎちにpackして置換表に格納したいときにもったいないということです。Bonanza6ではそうでした。そこでBonanza6ではこのように隙間をあけずに、代わりにsoftware packed演算の技法が必要になったというわけです。

しかし、現代では、手駒を置換表に格納しない実装のほうが多いのでこのへんは無視できるかと思います。また格納するにしてもそこまでギリギリにpackするとpackする(bit shiftなどの)CPU時間がもったいないので、そこまでしないことが多いです。

そこで、現代においては、Hand構造体は上のようにbitに隙間を空けたレイアウトにするのが最善ということになります。これは、Aperyのアイデアです。

優等＋同等

以上を総合すると、優等＋同等の判定は次のように書けることがわかります。

inline bool hand_is_equal_or_superior(Hand h1, Hand h2) { return ((h1-h2) & HAND_BORROW_MASK) == 0; }

繰り返しになりますが、優等＋同等の否定は劣等ではありませんので、この関数の否定をとって、劣等が判定できるわけではありません。劣等を判定したければ、この関数に渡す引数を入れ替えて渡すことで、劣等＋同等であるかの判定はできます。

また、普通、局面のhash keyが一致しているときは、千日手的な循環をしていることがわかりますので、そうでないとき(局面のhash keyが一致していないとき)に、盤面のhash keyが一致しているかどうかを見て、一致していれば、さらに、上の関数で「優等＋同等」であるかを判定します。

つまり、上の関数が呼び出されるときは前提条件として、「同等」ではないわけです。
※　局面が一致していなくて、盤面が一致している＝　手駒は同等ではない

なので、上の関数で「優等」の判定が出来るということがわかります。また引数を入れ替えて渡せば「劣等」の判定が出来ます。

HAND_BORROW_MASK

念のため、HAND_BORROW_MASKをどうやって定義するかを考えておきましょう。

ビットレイアウトは頻繁に変更する可能性があるので、こういうmagic numberを手打ちしたくないです。ビットレイアウトを変更したときに自動的に変わって欲しいです。

例えば、Aperyでは次のように実装してあります。

static const u32 BorrowMask = ((HPawnMask + (1 << HPawnShiftBits)) |
 (HLanceMask + (1 << HLanceShiftBits)) |
 (HKnightMask + (1 << HKnightShiftBits)) |
 (HSilverMask + (1 << HSilverShiftBits)) |
 (HGoldMask + (1 << HGoldShiftBits)) |
 (HBishopMask + (1 << HBishopShiftBits)) |
 (HRookMask + (1 << HRookShiftBits)));

static const u32 BorrowMask = ((HPawnMask + (1 << HPawnShiftBits)) |

(HLanceMask + (1 << HLanceShiftBits)) |

(HKnightMask + (1 << HKnightShiftBits)) |

(HSilverMask + (1 << HSilverShiftBits)) |

(HGoldMask + (1 << HGoldShiftBits)) |

(HBishopMask + (1 << HBishopShiftBits)) |

(HRookMask + (1 << HRookShiftBits)));

HPawnMaskは歩の枚数が格納されているbit位置が1であるmaskです。具体的には011111b。ここに、1を足すと桁あふれして、borrow bit(さきほど隙間をあけておいたbit)が1になるという仕組みですね。

わりと普通の実装ですが、やねうら王の場合、
HAND_BIT_MASK = HPawnMask | HLanceMask | HKnightMask | …;
というmaskがあるので、ここから次のようにしてborrow bitを算出しています。なかなかアクロバティックではないですか？

// 余らせてあるbitの集合。
// ※　HAND_BIT_MASKを2倍にすると絶対に各駒種の枚数を格納しているbitがoverflowするので、元のbitをマスクしてやれば
// 　BORROW BITの集合が得られるというhack。
constexpr int32_t HAND_BORROW_MASK = (HAND_BIT_MASK + HAND_BIT_MASK) & ~HAND_BIT_MASK;

// 余らせてあるbitの集合。

// ※　HAND_BIT_MASKを2倍にすると絶対に各駒種の枚数を格納しているbitがoverflowするので、元のbitをマスクしてやれば

// 　BORROW BITの集合が得られるというhack。

constexpr int32_t HAND_BORROW_MASK = (HAND_BIT_MASK + HAND_BIT_MASK) & ~HAND_BIT_MASK;

※ コメント欄で HAND_BORROW_MASK = HAND_BIT_MASK << 1 & ~HAND_BIT_MASK; のほうがいいのではと教えていただきました。そっちのほうがいいです、はい。

Hand型からHandKind型へ

HAND_BIT_MASKとHAND_BORROW_MASKの話が出てきたのでついでにHandKind型についても説明しておきます。

まず、HandKind型という、次のような構造体(もしくはenum)があるとします。

// 特定種の手駒を持っているかどうかをbitで表現するクラス
// bit0..歩を持っているか , bit1..香 , bit2..桂 , bit3..銀 , bit4..角 , bit5..飛 , bit6..金
enum HandKind : int32_t {};

// 特定種の手駒を持っているかどうかをbitで表現するクラス

// bit0..歩を持っているか , bit1..香 , bit2..桂 , bit3..銀 , bit4..角 , bit5..飛 , bit6..金

enum HandKind : int32_t {};

近代的な将棋ソフトにおいては、持っている手駒の種類による場合分けや、評価関数への組み込み等がしたいので、このような構造体があると便利なのです。

今回のborrow bitを余らせておくビットレイアウトと、さきほどのHAND_BIT_MASKとHAND_BORROW_MASKを用いるとこの変換子は次のように極めて簡潔に書くことが出来ます。

// Hand型からHandKind型への変換子
// 例えば歩の枚数であれば5bitで表現できるが、011111bを加算すると1枚でもあれば桁あふれしてbit5が1になる。
// これをPEXT32で回収するという戦略。
inline HandKind toHandKind(Hand h) {return (HandKind)PEXT32(h + HAND_BIT_MASK, HAND_BORROW_MASK);}

// Hand型からHandKind型への変換子

// 例えば歩の枚数であれば5bitで表現できるが、011111bを加算すると1枚でもあれば桁あふれしてbit5が1になる。

// これをPEXT32で回収するという戦略。

inline HandKind toHandKind(Hand h) {return (HandKind)PEXT32(h + HAND_BIT_MASK, HAND_BORROW_MASK);}

borrow bitを余らせていない実装だと次のようにsoftware packed演算の秘術を使う必要があります。これはこれで参考になると思うので紹介しておきます。

// Hand型からHandKind型への変換子
// →　packed bitとみなして飽和加算みたいなことをしてpacked bitのMSBをpextを回収すればいい。
//   たとえば、歩の枚数をandしたところに0x0fを足すと、1枚以上あればMSB(bit4)が1になる。
//   ただし歩の枚数が16枚を超えているとオーバーフローしてしまうので、あらかじめbit4は別のところに移動させておかないといけない。
inline HandKind toHandKind(Hand h) {
  constexpr uint32_t MSB = 0x12A490; // Hand型から取り出したいbit位置( = packed bitのMSB = bit4,bit7,bit10,bit13,bit15,bit17,bit20 = 100101010010010010000b )
  constexpr uint32_t LSB = 0x054921; // packed bitのLSB( = bit0,bit5,bit8,bit11,bit14,bit16,bit18 = 1010100100100100001b )
  // このとき加算しなければならない定数は(MSB-LSB)
  // →　たとえば0から31までの5bitの数字があったとして、このMSBはbit4で、LSBはbit0で、2^4 - 2^0 = 15。これを加算するとbit0..3の情報(そこが0であるか否か)を
  // MSB(bit4)に移動できる。

  h = (Hand)(((h & ~MSB) + (MSB-LSB) ) | (h & MSB));

  return (HandKind)PEXT32(h, MSB);
}

// Hand型からHandKind型への変換子

// →　packed bitとみなして飽和加算みたいなことをしてpacked bitのMSBをpextを回収すればいい。

// たとえば、歩の枚数をandしたところに0x0fを足すと、1枚以上あればMSB(bit4)が1になる。

// ただし歩の枚数が16枚を超えているとオーバーフローしてしまうので、あらかじめbit4は別のところに移動させておかないといけない。

inline HandKind toHandKind(Hand h) {

constexpr uint32_t MSB = 0x12A490; // Hand型から取り出したいbit位置( = packed bitのMSB = bit4,bit7,bit10,bit13,bit15,bit17,bit20 = 100101010010010010000b )

constexpr uint32_t LSB = 0x054921; // packed bitのLSB( = bit0,bit5,bit8,bit11,bit14,bit16,bit18 = 1010100100100100001b )

// このとき加算しなければならない定数は(MSB-LSB)

// →　たとえば0から31までの5bitの数字があったとして、このMSBはbit4で、LSBはbit0で、2^4 - 2^0 = 15。これを加算するとbit0..3の情報(そこが0であるか否か)を

// MSB(bit4)に移動できる。

h = (Hand)(((h & ~MSB) + (MSB-LSB) ) | (h & MSB));

return (HandKind)PEXT32(h, MSB);

}

ここまでのまとめ

以上をもって、優等局面の判定については理解が出来たかと思います。
優等局面の判定についてここまで詳しい資料は他に類を見ないでしょう。(また自画自賛か！)

そしてAperyがいかに細かいところに気をつけて設計されているかがわかるでしょう。本当、こういうところにおいてAperyに勝つのは容易ではないです。「この処理、Aperyではどうやってるんだろう？」と思ってAperyのソースコードを見ると自分より優れた実装になっていることも多々あります。勝敗に直結する部分ではないのが残念ですが。

次回につづく