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

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

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

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

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

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

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

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

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

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

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

ということで、

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

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

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

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

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

手駒の関係は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では次のように実装してあります。

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

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

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

Hand型からHandKind型へ

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

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

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

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

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

ここまでのまとめ

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

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

次回につづく


連載やねうら王miniを強くしよう!6日目” への9件のコメント

  1. >勝敗に直結する部分ではないのが残念ですが。

    そういうことを言うと、平岡さんに嫌われますよ、、、。

  2. HAND_BORROW_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_BIT_MASK + HAND_BIT_MASK) & ~HAND_BIT_MASK;

    よりも、

    (HAND_BIT_MASK << 1) & ~HAND_BIT_MASK;

    の方が、加算による overflow とか考えないのでシンプルではないですか?
    演算の優先順位的にビット論理和演算よりシフト演算の方が先に計算されるので、括弧で括る必要はないですね。

    // 余らせてあるbitの集合。
    // ※ HAND_BIT_MASKを左に1ビットシフトしてBORROW BITを1にして、
    //  元のbitをマスクしてやればBORROW BITだけの集合が得られるというhack。
    constexpr int32_t HAND_BORROW_MASK = HAND_BIT_MASK << 1 & ~HAND_BIT_MASK;

    些細なことなので、こんなのどっちでもええやん、って感じですかね。

      • 余談です。

        (2進法なので)ビットシフトと 2^n 倍が等価なのはプログラマなら常識で、これが同値変換できるのはすぐ分かりますが、

        HAND_BIT_MASK + HAND_BIT_MASK

        を見て「HAND_BIT_MASK * 2」でいいじゃん、と思ったのを(シフト演算に置き換えて)それっぽく指摘しただけでした。同時に以下のツイートを連想しました。

        https://twitter.com/yokohama_geo/status/676043972259672064
        > 小3のうちの子の算数テスト。半径4cmの円の直径を問う問題で、[式]4+4=8と答えてバツ。[式]4×2=8じゃないと不正解とのこと。先生が赤字でコメント「半径の2倍が直径です」。 …こういう馬鹿馬鹿しい教育をしてるから、理数離れが進むのではないかと思います。

        • まあ、各packed bitをoverflowさせられたら何でもいい状況なのでHAND_BIT_MASK + αなんですよね。このαとして適当なものが何か転がってないかなというのが発想の原点にあるので、「α = HAND_BIT_MASKでいいじゃん!やったー!」というのが私の思考過程で、結果として2倍してるだけなんですけど、本人は2倍とは思っていないという…。

  3. Aperyよりだいぶ前に盤面のハッシュと持ちゴマのハッシュを「うさぴょん」では持っています。
    2001年の「うさぴょん」では、盤面のハッシュだけで置換表に登録していて、劣等局面等を判定していた…けれども、今の「うさぴょん」ほど過激ではなくて、今のうさぴょんは、劣等局面の場合に-∞を返すようにしているので、タダ捨てして元の盤面に戻る時にはすぐに探索を終えるような感じになっております。

    いつからそういう過激な実装にしたのかは忘れちゃいましたが(苦笑)。

    • > 劣等局面の場合に-∞を返すようにしているので

      Aperyもそれに近い処理になってますね。私はその部分、(そんなスコア置換表に書いたら)おかしいんじゃないかと思っているんですけど、まあPV nodeは何らか読みなおしするのが普通の実装なので現実的にはそれでも大抵は困らないという…。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です