Long Effect Library 完全解説 その4

前回の続き。

利きの数の更新

長い利きの更新をざっと説明しました。

また、長い利きの更新のときに盤上の利きの数の更新をします。動かした駒に関する利きの数だけならば、他にもやりようがあるのですが、利きの遮断処理や開放処理を伴うと、長い利きの更新のときに同時に盤上の利きの数の更新もやってしまうのが合理的です。

そこで、短い利きを更新する必要が出てきます。今回はこれをどうするか説明します。

短い利きの特徴

短い利きの特徴として利きは遮断されないということです。利きが遮断されないので、移動させた駒に関するfromの地点とtoの地点での(他の短い利きの)開放処理と遮断処理はありません。

移動させる駒がfromの地点でからなくなるのでfromの地点での短い利きの分だけ利きの数を各升から減らす処理と、toの地点で短い利きの分だけ利きの数を増やす処理は必要となります。

利き = 短い利き + 長い利き

そう考えると短い利きだけを取得する関数が必要になることがわかります。

短い利きは盤上の状態を考慮する必要がないため、普通の利きの関数を流用すると比較的簡単に書けます。例えば、以下のようになります。馬の短い利きが上下左右1升であるだとか、龍の短い利きが斜め1升であるだとかは、パッと出てこないかも知れませんが、ここまでの説明を読んだ人ならわかるでしょう。

もちろん、ひたすら場合分けするほうが速いとは思います。歩の移動の指し手とか、上のコードだとずいぶん無駄が出ますし…。

Long Effect Libraryの使い方

ざっと仕組みの解説が終わったところで、あなたの将棋ソフトにこのLong Effect Libraryを組み込む方法を説明します。

やねうら王miniのソースコードの
extra/long_effect.h
に、以下の3つの関数があります。

普通、局面クラス(Position)を指し手で1手進める(do_move() )とき、drop(駒打ち),non_capture(敵の駒を取らない駒移動),capture(敵の駒を取る駒移動)の3種に指し手を分類して局面の更新処理を行なうと思いますが、そのときに上記の関数を呼び出すだけです。これであなたのPositionクラスが利き(+長い利き)に対応します。素晴らしいですね!(無論、関数名などは調整する必要がありますが…。)

まとめ

Long Effect Libraryの仕組みとその使い方について一通り説明しました。
次回からは、このLong Effect Libraryを用いた超高速1手詰め判定について書いていきます。

Long Effect Library 完全解説 その4」への7件のフィードバック

  1. do_move()に対応するのがupdate_by_*()として、undo_move()に対応するのは何???と思ったら、同じくlong_effect.hにあるrewind_by_*()がundo_move()に対応しているってことですね?

    • はい、undo_move()のときに更新したい場合はそうですね。do_move()のときに親nodeでの利きをmemcpyなどして、それを更新して、undo_move()のときには破棄するような実装もありえるので、rewind_by_*()が必要とは限りません。

  2. 連載楽しく読ませて頂いております。
    超高速1手詰め判定ライブラリ(mate1ply.cpp)で気になる箇所がありましたので、報告させて頂きます。
    もし見当外れでしたら無視してください。
    (手元のVC++で動かしてみたのはENGINE_VERSION “1.16”のソースですが、おそらく最新版でも変わらないかと思います)

    (1)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.

    (2)駒の移動による詰み判定の中で
    「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二玉)

    .+.
    **.

  3. 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%ほど詰み発見率が上がりました。

コメントを残す

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