壁判定機能つきSquareの実装

長い利き(遠方駒による利き)の更新などで、Square(升)型に差分値を足しながら更新したいことがあります。

典型的なコードはこんな感じでしょうか。

このWALL(壁)というのは盤外を表す駒で、盤面の升を9×9ではなく、16×13ぐらい広く確保しておいて、周辺にWALLという駒を配置しておき、sqが盤外に出たかどうかを判定するのが普通です。(この技法は、うさぴょんや、BlunderなどBitboardを用いないタイプの将棋ソフトで採用されていることが多かったように思います。)

実際は、盤外のメモリに書き込んでもいいことを利用すると、上のコードのうち、WALLの判定は省略できます。(pieces_on(sq)==WALLという条件はpieces_on(sq)!=NO_PIECEに含まれるので)

しかしこのように盤面を広く確保すると、このSquare型と盤上の升との対応がややこしくなります。少なくともSquare型で盤内を表す値が離散値(飛び飛び)になるので、Bitboardから1bit取り出すときとかにテーブルを引く手間が必要になったりしてなかなか面倒なことになります。

そこでこれをどうにかして解決したいわけです。

まずWALL(壁)を用いないときの従来手法を書きます。

sq += sq_delta;

の部分でsq_deltaを加算するわけですが、sqと(sq – sq_delta)の升が1升以上離れていたら盤外に出たと判定する方法です。

具体的には、次のような距離を返す関数を用意します。ここではsq1,sq2のrank(段)の差とfile(筋)の差のうち大きいほうを返していますが、rankの差 + fileの差 のようにマンハッタン距離を返す実装も考えられます。(Aperyは後者の実装)

この関数があると

if (piece_on(sq)==WALL)
break;

の部分は

if (dist(sq,sq-sq_delta) > 1)
break

と等価となります。

AperyなどにしてもBitboardの利きテーブルの初期化時にこれに相当する処理をやっています。

しかし、こんなmax()やらabs()やらを使った関数を利きの更新のときにやっていてはとても遅くなってしまいます。

この理由から、Bitboard型で長い利きを持つ場合、利きの更新処理がストレートに書けないという問題がありました。

そこで普通にsq += sq_deltaのように加算していきながら、かつ、is_wall(sq) (sqは盤外の升かを判定する関数)、あるいはis_ok(sq) (sqは盤上の升かを判定する関数)みたいな関数が簡単に書けることが望ましいわけです。

今回、これを解決する方法を発明しました。以下にソースコードを貼り付けておきます。仕組みはご覧の通りです。これで晴れてBitboard型でも長い利きの差分更新がお手軽に出来るようになります。

やねうら王の超高速1手詰め判定関数のために新たに7つの技法を開発する必要がありました。これは、そのうちの一つです。あとの6つはまたの機会に!

2016/1/21 17:40 追記

このような意見を頂戴しました。

「提案のSquareWithWallではそれが出来ないので良くない」は、部分的に見るとそうなのです。しかし、盤面を広くとるとBitboardから1ビット取り出してSquare型の値を得たいときに毎回テーブルを引かないといけなくなって、それは指し手生成のときとか、あらゆるところで利いてきて、かなりの損をします。それに対して、長い利きの更新はごく限られた条件のときに差分更新するだけですから、do_move()ごとに平均的には数回程度。トータルで見るとここのオーバーヘッドはほぼほぼ無視できます。(かと言って、従来手法のようなabsとかmaxとかてんこ盛りのコードは避けたいという意図です。)


壁判定機能つきSquareの実装” への2件のコメント

    • > 7つの秘法のうちの一つを気前の良いことに公開

      ソースコードをGitHubから入手すると7つの秘宝が揃って、神龍が出てくるかも。

コメントを残す

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