長い利き(遠方駒による利き)の更新などで、Square(升)型に差分値を足しながら更新したいことがあります。
典型的なコードはこんな感じでしょうか。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
while (true) { effect[sq]++; // 駒があればここでこのrayの利きは終了。 if (pieces_on(sq)!=NO_PIECE) break; sq += sq_delta; if (piece_on(sq)==WALL) break; } |
このWALL(壁)というのは盤外を表す駒で、盤面の升を9×9ではなく、16×13ぐらい広く確保しておいて、周辺にWALLという駒を配置しておき、sqが盤外に出たかどうかを判定するのが普通です。(この技法は、うさぴょんや、BlunderなどBitboardを用いないタイプの将棋ソフトで採用されていることが多かったように思います。)
実際は、盤外のメモリに書き込んでもいいことを利用すると、上のコードのうち、WALLの判定は省略できます。(pieces_on(sq)==WALLという条件はpieces_on(sq)!=NO_PIECEに含まれるので)
しかしこのように盤面を広く確保すると、このSquare型と盤上の升との対応がややこしくなります。少なくともSquare型で盤内を表す値が離散値(飛び飛び)になるので、Bitboardから1bit取り出すときとかにテーブルを引く手間が必要になったりしてなかなか面倒なことになります。
そこでこれをどうにかして解決したいわけです。
将棋で盤上の遠方駒の利きの更新するときに、うさぴょんやBlunderみたく盤面を16*13升ぐらい確保して壁の升を用意しておくのが常道なんだけど、それだと升の表現が不連続になっていまどきのソフトとは相性が悪い。壁の升を用意せずに壁の判定を簡単に行なう画期的な方法を発明したのだが、
— やねうら王 (@yaneuraou) January 19, 2016
まずWALL(壁)を用いないときの従来手法を書きます。
sq += sq_delta;
の部分でsq_deltaを加算するわけですが、sqと(sq – sq_delta)の升が1升以上離れていたら盤外に出たと判定する方法です。
具体的には、次のような距離を返す関数を用意します。ここではsq1,sq2のrank(段)の差とfile(筋)の差のうち大きいほうを返していますが、rankの差 + fileの差 のようにマンハッタン距離を返す実装も考えられます。(Aperyは後者の実装)
|
1 2 3 4 5 |
// ２つの升のfileの差、rankの差のうち大きいほうの距離を返す。sq1,sq2のどちらかが盤外ならINT_MAXが返る。 inline int dist(Square sq1, Square sq2) { return (!is_ok(sq1) || !is_ok(sq2)) ? INT_MAX : std::max(abs(file_of(sq1)-file_of(sq2)) , abs(rank_of(sq1) - rank_of(sq2))); } |
この関数があると
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
// -------------------- // 壁つきの升表現 // -------------------- // 長い利きを更新するときにある升からある方向に駒にぶつかるまでずっと利きを更新していきたいことがあるが、 // sqの升が盤外であるかどうかを判定する簡単な方法がない。そこで、Squareの表現を拡張して盤外であることを検出 // できるようにする。 // bit 0..7 : Squareと同じ意味 // bit 8 : Squareからのborrow用に1にしておく // bit 9..13 : いまの升から盤外まで何升右に升があるか(ここがマイナスになるとborrowでbit13が1になる) // bit 14..18 : いまの升から盤外まで何升上に(略 // bit 19..23 : いまの升から盤外まで何升下に(略 // bit 24..28 : いまの升から盤外まで何升左に(略 enum SquareWithWall : int32_t { // 相対移動するときの差分値 SQWW_RIGHT = SQ_RIGHT - (1 << 9) + (1 << 24) , SQWW_UP = SQ_UP - (1 << 14) + (1 << 19) , SQWW_DOWN = -SQWW_UP, SQWW_LEFT = -SQWW_RIGHT, SQWW_RU = SQWW_RIGHT + SQWW_UP , SQWW_RD = SQWW_RIGHT + SQWW_DOWN , SQWW_LU = SQWW_LEFT+ SQWW_UP , SQWW_LD = SQWW_LEFT + SQWW_DOWN , // SQ_11の地点に対応する値(他の升はこれ相対で事前に求めテーブルに格納) SQWW_11 = SQ_11 | (1 << 8) /* bit8 is 1 */ | (0 << 9) /*右に0升*/| (0 << 14) /*上に0升*/ | (8 << 19) /*下に8升*/| (8 << 24) /*左に8升*/, // SQWW_RIGHTなどを足して行ったときに盤外に行ったときのborrow bitの集合 SQWW_BORROW_MASK = (1 << 13) | (1 << 18) | (1 << 23) | (1 << 28) , }; // 型変換。下位8bit == Square inline Square to_sq(SquareWithWall sqww) { return Square(sqww & 0xff); } extern SquareWithWall sqww_table[SQ_NB]; // 型変換。Square型から。 inline SquareWithWall to_sqww(Square sq) { return sqww_table[sq]; } // 盤内か。壁(盤外)だとfalseになる。 inline bool is_ok(SquareWithWall sqww) { return (sqww & SQWW_BORROW_MASK) == 0; } void init() { // SquareWithWallテーブルの初期化処理(例) for (auto sq : SQ) sqww_table[sq] = SquareWithWall(SQWW_11 + (int32_t)file_of(sq) * SQWW_LEFT + (int32_t)rank_of(sq) * SQWW_DOWN); } |
やねうら王の超高速1手詰め判定関数のために新たに7つの技法を開発する必要がありました。これは、そのうちの一つです。あとの6つはまたの機会に！
2016/1/21 17:40 追記
このような意見を頂戴しました。
@dasapon17 @yaneuraou このように,盤外のマスに効きを書き込んでも構わない構造なら上記のコードでうまくいきますが,提案のSquareWithWallではそれが出来ないので良くないように思うのですがどうでしょうか?
— dasapon (@dasapon17) January 21, 2016
「提案のSquareWithWallではそれが出来ないので良くない」は、部分的に見るとそうなのです。しかし、盤面を広くとるとBitboardから1ビット取り出してSquare型の値を得たいときに毎回テーブルを引かないといけなくなって、それは指し手生成のときとか、あらゆるところで利いてきて、かなりの損をします。それに対して、長い利きの更新はごく限られた条件のときに差分更新するだけですから、do_move()ごとに平均的には数回程度。トータルで見るとここのオーバーヘッドはほぼほぼ無視できます。(かと言って、従来手法のようなabsとかmaxとかてんこ盛りのコードは避けたいという意図です。)
＞よく来たな勇者よ！
＞ここは「こんな数学の問題ぐらい(東大の数学科の院生なら)誰でも解けるだろ」
・・・
そういう訳で、今回新たに開発した７つの秘法のうちの一つを気前の良いことに公開された・・・と。
いや、魔王さまは本当にお優しい方でありますなあ。
https://twitter.com/yaneuraoh/status/689343169515786244?ref_src=twsrc%5Etfw
> ７つの秘法のうちの一つを気前の良いことに公開
ソースコードをGitHubから入手すると7つの秘宝が揃って、神龍が出てくるかも。