持駒の優劣関係判定 (2)

テーマ:

ハッシュキーは盤上の駒のみを基準にし、置換表レコード上に持駒データを持たせて、同一盤面の時に持駒の優劣関係から判定して詰・不詰を引用するアイデアは、恐らく古くから多くの計算機将棋開発者が持っていたのではないかと思う。コンピュータチェスの世界には前例・参考例が全くない(そもそも持駒の概念がない)ので、そのアイデアをどのように巧く実装するかが課題だったのではないかと思われる。

私が置換表の実装に踏み切れなかったのもその点の解決案がなかったからで、脊尾さんの手法を知った当時、相当真剣に優劣関係判定法について検討したものである。

脊尾さんの手法では先に書いた通り、ビットを立てていくクッション処理が入り、これが正直どうしても気に入らなかった。無論、そのやり方は論理的に正しいことが直感で判るし、2進数のままでまとめて引き算を行うやり方は「原理的に無理がある」と思い込んでしまっていたのも確かだ。例えば、


・対象局面は持駒なし: 0x00000000
・被対象局面が歩1枚:0x00000001

なら、対象から被対象を引くと、0xffffffff になり、他フィールドへドミノ倒し(将棋倒しとは書かないところがミソ)的にボロウを引き起こして全く話にならない、と感じてしまう。その演算結果を用いて「歩以外の各持駒が何枚あるか」を求めたいのであれば使えない手法であることは事実。であるが故に私自身、一時的に不可能だと勘違いしていた。

米長会長流に言えば、ここで「計算機将棋の神様の御告げ」があった。元々私は諦めが悪い方であるし、これが将棋なら「探せば手はある」筈だ[*1]。ポイントとなるのは、「各持駒の枚数を並列計算したい」のではなく、あくまで「優劣関係の判定を行いたい」だけである。つまりは{完全同一、優位、劣位、非同一}の4つの何れであるかを正しく判断できれば、どのようなやり方であっても速いなら問題ない。対象持駒をA、被対象持駒をBとした時、


・完全同一:A.歩=B.歩 ∧ A.香=B.香 ... A.角=B.角 ∧ A.飛=B.飛 
・A優位  :A.歩≧B.歩 ∧ A.香≧B.香 ... A.角≧B.角 ∧ A.飛≧B.飛 ∧ 完全同一でない
・B優位  :A.歩≦B.歩 ∧ A.香≦B.香 ... A.角≦B.角 ∧ A.飛≦B.飛 ∧ 完全同一でない
・非同一 :上記以外

これらを正確に判定できれば良いわけで、結局互い違いに算術減算を行って各フィールドのMSBを検査して全てのフィールドでボロウが起きないなら、等しいか包含関係にあることが保証されることに着目し、そのフィールド長が本来使う値の範囲より1ビットでも長いなら、2進数表現であっても優劣関係の判定は出来ることが判ったのである。

結論が最後になってしまったが、具体的なコード(マクロ)例を次に示す(引数はHand型とする)。


#define    Dominate( a , b )    ( ( ( ( a.h - b.h ) & 0x88888880 ) ? 2 : 0 ) + \
                                  ( ( ( b.h - a.h ) & 0x88888880 ) ? 1 : 0 ) )

このマクロの演算結果が示す値の意味は、次の様になる。


0:完全同一(どっちからどっちを引いても全くボロウが起きない)
1:aが優位 ( b - a の時のみボロウが起きる)
2:bが優位 ( a - b の時のみボロウが起きる)
3:非同一 (どちらでもボロウが起きる)

余談だが、このマクロには3項演算子を用いている。VisualC/C++の場合、最適化を効かせてない場合でも条件分岐命令が生成されず、それなりに高速な実行コードを吐き出してくれる。インラインアセンブラを使っている方には参考になると思うので、一度ニモニックを確認されることをお奨めする[*2]


[*1] 私の将棋の場合には、そういう事はほとんどなく、本来の将棋の神様には見放されているようである。
[*2] 個人的に最も参考になるのはWatcomCで、コレのx86コード最適化技術は気合が入っていると思う。