前回の続き。
利きの数の更新
長い利きの更新をざっと説明しました。
また、長い利きの更新のときに盤上の利きの数の更新をします。動かした駒に関する利きの数だけならば、他にもやりようがあるのですが、利きの遮断処理や開放処理を伴うと、長い利きの更新のときに同時に盤上の利きの数の更新もやってしまうのが合理的です。
そこで、短い利きを更新する必要が出てきます。今回はこれをどうするか説明します。
短い利きの特徴
短い利きの特徴として利きは遮断されないということです。利きが遮断されないので、移動させた駒に関するfromの地点とtoの地点での(他の短い利きの)開放処理と遮断処理はありません。
移動させる駒がfromの地点でからなくなるのでfromの地点での短い利きの分だけ利きの数を各升から減らす処理と、toの地点で短い利きの分だけ利きの数を増やす処理は必要となります。
利き = 短い利き + 長い利き
そう考えると短い利きだけを取得する関数が必要になることがわかります。
短い利きは盤上の状態を考慮する必要がないため、普通の利きの関数を流用すると比較的簡単に書けます。例えば、以下のようになります。馬の短い利きが上下左右1升であるだとか、龍の短い利きが斜め1升であるだとかは、パッと出てこないかも知れませんが、ここまでの説明を読んだ人ならわかるでしょう。
|
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 |
// 駒pcをsqの地点においたときの短い利きを取得する(長い利きは含まれない) inline Bitboard short_effects_from(Piece pc,Square sq) { switch (pc) { case B_PAWN: return pawnEffect(BLACK, sq); case W_PAWN: return pawnEffect(WHITE, sq); case B_KNIGHT: return knightEffect(BLACK, sq); case W_KNIGHT: return knightEffect(WHITE, sq); case B_SILVER: return silverEffect(BLACK, sq); case W_SILVER: return silverEffect(WHITE, sq); // 金相当の駒 case B_GOLD: case B_PRO_PAWN: case B_PRO_LANCE: case B_PRO_KNIGHT: case B_PRO_SILVER: return goldEffect(BLACK, sq); case W_GOLD: case W_PRO_PAWN: case W_PRO_LANCE: case W_PRO_KNIGHT: case W_PRO_SILVER: return goldEffect(WHITE, sq); // 馬の短い利きは上下左右 case B_HORSE : case W_HORSE: return cross00StepEffect(sq); // 龍の短い利きは斜め長さ1 case B_DRAGON : case W_DRAGON: return cross45StepEffect(sq); case B_KING : case W_KING: return kingEffect(sq); // 短いを持っていないもの case B_LANCE: case B_BISHOP: case B_ROOK: case W_LANCE: case W_BISHOP: case W_ROOK: return ZERO_BB; default: UNREACHABLE; return ZERO_BB; } } |
もちろん、ひたすら場合分けするほうが速いとは思います。歩の移動の指し手とか、上のコードだとずいぶん無駄が出ますし…。
Long Effect Libraryの使い方
ざっと仕組みの解説が終わったところで、あなたの将棋ソフトにこのLong Effect Libraryを組み込む方法を説明します。
やねうら王miniのソースコードの
extra/long_effect.h
に、以下の3つの関数があります。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// ---------------------- // do_move()での利きの更新用 // ---------------------- // Usの手番で駒pcをtoに配置したときの盤面の利きの更新 template // Usの手番で駒pcをtoに移動させ、成りがある場合、moved_after_pcになっており、捕獲された駒captured_pcがあるときの盤面の利きの更新 template // Usの手番で駒pcをtoに移動させ、成りがある場合、moved_after_pcになっている(捕獲された駒はない)ときの盤面の利きの更新 template |
普通、局面クラス(Position)を指し手で1手進める(do_move() )とき、drop(駒打ち),non_capture(敵の駒を取らない駒移動),capture(敵の駒を取る駒移動)の3種に指し手を分類して局面の更新処理を行なうと思いますが、そのときに上記の関数を呼び出すだけです。これであなたのPositionクラスが利き(+長い利き)に対応します。素晴らしいですね！(無論、関数名などは調整する必要がありますが…。)
まとめ
Long Effect Libraryの仕組みとその使い方について一通り説明しました。
次回からは、このLong Effect Libraryを用いた超高速1手詰め判定について書いていきます。
do_move()に対応するのがupdate_by_*()として、undo_move()に対応するのは何？？？と思ったら、同じくlong_effect.hにあるrewind_by_*()がundo_move()に対応しているってことですね？
はい、undo_move()のときに更新したい場合はそうですね。do_move()のときに親nodeでの利きをmemcpyなどして、それを更新して、undo_move()のときには破棄するような実装もありえるので、rewind_by_*()が必要とは限りません。
連載楽しく読ませて頂いております。
超高速1手詰め判定ライブラリ（mate1ply.cpp）で気になる箇所がありましたので、報告させて頂きます。
もし見当外れでしたら無視してください。
（手元のVC++で動かしてみたのはENGINE_VERSION “1.16”のソースですが、おそらく最新版でも変わらないかと思います）
（１）mate1ply.cpp内の「#define CHECK_PIECE(DROP_PIECE)」で「Next ## DROP_PIECE:;」の位置を間違われておりませんでしょうか？
while (directions) の中にwhile (cut_dirs_from_king) がありますが、
内側のwhile内で詰まないことが分かると、外側のwhileまで抜けてしまっています。
例えば下記局面は7二金打の一手詰めですが、
directionsとして｛6二金打、7二金打｝に相当する方角が入り、
6二金打で詰まないことが分かると、7二金打を判定することなく「金打ちでは詰みなし」として、次の銀打ちの判定に移ってしまい、
結果的に1手詰を逃してしまっているように思いますが、いかがでしょうか？
□^桂^玉 □ □ □ 金 □ □
^香 □ □ □ □ 龍 金^角 □
^銀 □^歩 □ □ □ □ □^香
^桂 □ □^歩 □ □ □^歩^歩
□^歩 □ 歩 歩 □ □ □ □
□ □ □ □ 玉 歩 歩 歩 □
桂 歩 歩 □ 銀 □ □ □ 歩
香 飛 □ □ □^歩^歩 金 香
角 □ □^と^圭 □ 銀 □ □
先手 手駒 : 歩2 銀 金 , 後手 手駒 :
手番 = 先手
sfen 1nk3G2/l4+RGb1/s1p5l/n2p3pp/1p1PP4/4KPPP1/NPP1S3P/LR3ppGL/B2+p+n1S2 b 2PSG 123
mated = G*7b, but mate1ply() = MOVE_NONE.
（２）駒の移動による詰み判定の中で
「auto cut_dirs = cutoff_directions(to_direct, long_effect.directions_of(Us, to));」のあたりで
駒の移動による長い利きの遮断を考慮されていると思いますが、
場合によっては、元々長い利きがなかった升まで利きが減ったものとみなしてしまっているように思います。
例えば下記局面は5三龍の一手詰めですが、
下図のようにcut_dirsとして｛7三、6三｝に相当する方角が入り、
7三への先手の利きが減ったため詰まないと判定されてしまっているように思いますが、いかがでしょうか？
と □ 杏^金 □ 銀 と □^角
と □ □^玉 □ □ □ □^歩
□ 桂 □^香 □ 龍 □ □^桂
□ 香 金 □ 金^歩 □ □ 香
銀 □ □ □ □ □^歩 □ □
□ 歩 歩 歩 □^金 □^歩 □
角 □ □ □ 飛 □ □ □^桂
^歩^歩 □ □^圭 □ 玉^銀 歩
□ 銀 □ □ □ □ 歩 □ □
先手 手駒 : 歩2 , 後手 手駒 : 歩2
手番 = 先手
sfen +P1+Lg1S+P1b/+P2k4p/1N1l1+R2n/1LG1Gp2L/S5p2/1PPP1g1p1/B3R3n/pp2+n1KsP/1S4P2 b 2P2p 203
mated = 4c5c, but mate1ply() = MOVE_NONE.
■cut_dirs（+は6二玉）
…
.+.
**.
うおー！めっちゃ助かります。ありがとうございます。(｀･ω･´)ゞ
以上、２つのケース、詰むように修正してGitHubのほうにコミットしておきました。(｀･ω･´)ゞ
Ver1.48の超高速1手詰め判定ライブラリ（mate1ply.cpp）で
もう一つ漏れているケースを見つけましたので、報告させて頂きます。
「#define CHECK_PIECE(DROP_PIECE)」で駒打ちによる長い利きの遮断を考慮している箇所で、「& a8_them_movable」を追加
■修正前
Directions cut_dirs_from_king = cutoff_directions(to_direct, long_effect.directions_of(Us, to)) \
& effect_not & a8_board_mask; \
■修正後
Directions cut_dirs_from_king = cutoff_directions(to_direct, long_effect.directions_of(Us, to)) \
& effect_not & a8_board_mask & a8_them_movable; \
例えば下記局面は後手の5四金打で一手詰めですが、
修正前のソースでは、6四の飛車の3四への利きが遮断されるため詰まないと判定されてしまいます。
そもそも3四には先手の成り香がいるため先手玉は移動できないので、cut_dirs_from_kingから除外することを意図しています。
<< ^歩 □ □^金 □ □ □^桂 □
<< □ □^金^桂 □ □ □ □^金
<< と □^銀 □^玉 □ □ □^銀
<< □^歩^歩^飛 □ □ 杏^角^歩
<< □ 歩 □^歩 □ 玉 □ □^角
<< □ □ □ □ 歩 □ 歩^歩^香
<< □ □ □^圭 □ 歩 □ 飛 歩
<< 香 銀 □ □ □^歩 □ 歩 香
<< □ □ □ 歩^と □ □ 桂 銀
<< 先手 手駒 : 歩 , 後手 手駒 : 歩 金
<< 手番 = 後手
<< sfen p2g3n1/2gn4g/+P1s1k3s/1ppr2+Lbp/1P1p1K2b/4P1Ppl/3+n1P1RP/LS3p1PL/3P+p2NS w Ppg 160
<< mated = G*5d, but mate1ply() = MOVE_NONE.
test rpで試してみましたところ、0.2%ほど詰み発見率が上がりました。
うおー！それはありがたい！修正してGitHubに反映させておきました(｀･ω･´)ゞ