Long Effect Library 完全解説 その3

前回の続き。

長い利きの発生と遮断は相殺する

長い利きに関して発生と遮断は相殺します。

例えば、35の升に味方の飛車がいて、別の飛車を52から55の升に移動させたとします。(盤上に他の駒はないものとします)

このとき、55の升では遮断処理が行われますが、左方向には(元からあった飛車の長い利きがすでにあるので)更新しなくても良いことがわかります。

つまり、この相殺されるのをうまく表現しようと思うと、^(xor)となります。この例で言うと、

更新する方角 = toの地点(55の升)で元の長い利き ^ toの地点(55)に置いた駒(飛車)の長い利き

こうなります。

方角は先後合わせて16bitで管理することは前回説明しました。

ということは、「toの地点(55)に置いた駒(飛車)の長い利き」というのは、駒の種類が与えられて、(この方角だけがわかればいいので)16bitの値が返る関数があれば十分なのです。とても簡単な利きの関数だと思いませんか?
やねうら王miniの場合、long_effect16_of()という関数があり、上の処理は次のようになります。

directions = long_effect.long_effect[to] ^ long_effect16_of(Piece);

この方角から1ビットずつ取り出して、その方向に長い利きを更新していきますが、先後同時に扱えるので実際のコードは次のようになります。

Squareの表現には先日記事を書いた壁付きSquareを用いているものとします。

(ここまでは)わりと綺麗に書けている気がします。

泥臭いテクニックが何故必要なのか?

ここからいくつかの泥臭いテクニックを用いて、さらに高速化します。

上のようにやっても更新処理自体はさほど重くないのですが、実際は利きの更新処理のときに評価関数の差分更新も伴うので、なるべく更新対象の升は少ないほうが嬉しいというのがあります。

fromの反対側の長い利きは変化しない

角や飛車をfromからtoに移動させるとして、fromにとってtoと反対側の長い利きは変化しません。toに移動したあとも長い利きはそこにその方向で利き続けるからです。そこで、移動させる方向と逆の方角については利きを更新しなくても良いということになります。

※ ただし、桂の移動の場合は、反対側の方角というのがないので要注意。この処理は桂の場合だけ除外する必要があります。

no_captureの場合、toの反対側の長い利きは変化しない

角や飛車をfromからtoに移動させるとして、no_captureの場合、toの地点にはもともと駒はなかったので、toにとってfromと反対側の升の長い利きは変化しません。fromに移動させた駒があったときから、そこには長い利きがあったはずで、また、fromからtoに移動できているということはこの間の升には駒がないことは保証され、fromの地点に駒があったということは、fromの升で(fromのtoの反対側からの利きは)遮断されていたということになるので、結局、fromに移動させる駒があったときの状態と変化しないからです。

駒別の長い利きの更新

角と飛車に関してはfromからtoへ移動させたとき、fromの地点からtoの地点までの長い利きを消滅させながら、toの地点からfromの地点に向かって長い利きが発生します。(角と飛車は成っても、その持つ、長い利きの特性は変わらないことに注意。)

この長い利きの更新処理は、xorを使って一本化できるのですが、レアケースのわりには、コードが複雑になるのでやねうら王ではいまのところやっていません。

このように、動かす駒別の場合分けは行なうと色々高速化できるケースはあるのですが、コードがとても複雑になります。

つづく


Long Effect Library 完全解説 その3” への2件のコメント

  1. なかなか将棋をソフト化するのは大変な事なのだ・・・ということが分かる記事であります。
    そしてこれがなかなかの事を言っているのでしょうが、あまり考えた事がない内容なので頭がピンボケ状態です。
    まあそれはさておき、いつもの、、、。

    >さらに高速化します。・・・上野ようにやっても・・・
    野ー>の・・・でしょうね。

コメントを残す

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