Long Effect Library 完全解説 その2

前回の続き。

長い利きの更新処理

指し手を次の3つに分類します。

1. drop(駒打ち)
2. no_capture(移動による指し手)
3. capture(移動による駒を捕獲する指し手)

長い利きを更新する上でこの分類が一番合理的です。
この理由はあとあとわかります。

まず上記の3つの指し手に対して長い利きの更新処理がどうなるか考えていきましょう。

dropによる長い利きの更新

駒打ちはまず打った駒の長い利きが発生します。長い利きは、特定の駒にしか発生しません。駒打ちによって長い利きが発生するのは、香、角、飛車の3種類です。

また、to(=駒を打つ升)で長い利きを遮断することがありますから、この遮断した利きをこの利きの方向に延長していき更新する必要があります。

こういう観点で見ると、ある升での長い利きの「遮断」によって発生する更新処理があるというのがわかります。これを(長い利きの)「遮断処理」と呼ぶことにします。

またtoの地点でtoに置いた駒による長い利きの発生があります。この処理のことを「発生処理」と呼ぶことにします。

no_captureによる長い利きの更新

no_captureである場合、from(=移動元の升)からはここで遮断されていた長い利きは開放されます。遮断していた利きの方角に利きを延長していき更新する処理が必要となります。これを長い利きの「開放処理」と呼ぶことにします。

また、to(=移動先)の升は、もともとそこには駒がなかった升ですから、ここで「遮断処理」が必要となります。

fromの地点からは移動させた駒の長い利きがなくなるので「除去処理」も必要でtoの地点での「発生処理」も必要です。

captureによる長い利きの更新

captureの場合もfromでは「開放処理」が必要となりますが、toの升での「遮断処理」は必要ありません。なぜなら、そこにはもともと駒が存在していたわけですから、遮断はされないのです。もちろん、もともと存在していた駒による長い利きを取り除く処理は必要です。これを「除去処理」と呼ぶことにします。

その他はno_captureと同様です。

長い利きの更新処理の分類

drop : toの地点での(打った駒による長い利きの)発生処理 + toの地点での遮断処理
no_capture : fromの地点での(移動させた駒の長い利きの)除去処理 + 開放処理 + toの地点での(移動させた駒の長い利きの)発生処理 + 遮断処理
capture : fromの地点での(移動させた駒の長い利きの)除去処理 + 開放処理 + toの地点での(移動させた駒の長い利きの)発生処理 + (元あった駒の長い利きの)除去処理

このように分類されます。面白いことに、dropはtoの地点で2つの処理(発生+遮断)、no_captureはfromの地点で2つの処理(除去+開放) + toの地点で2つの処理(発生+遮断)、captureはfromの地点で2つの処理(除去+開放) + toの地点で2つの処理(発生+除去)というように、すべて2つの処理で成り立っていることがわかります。

3つの処理がfromかtoに集中することがないという特徴があります。

遮断・開放処理の特徴

遮断するのは敵の利きとは限りません。味方の利きも別け隔てなく遮断してしまいます。開放も同様です。敵の利きも味方の利きも別け隔てなくなく開放してしまいます。

つまり、この観点から見ると、長い利きに関して敵と味方と同時に同じ効果が及びます。別の言い方をすると、同じ方向に更新していくとき、敵の分も味方の分も同時に更新していけます。

このことについてさらに突っ込んで考えていきましょう。

遮断・開放処理の一本化

遮断と開放と区別したくないので、長い利きの更新にはxorを用います。
こうすることで遮断するコードと開放するコードとが一本化できます。

例えば、開放処理と遮断処理において、ある方向の長い利きを復元していく(擬似)コードは次のように書けます。

long_effect.dir[sq]はsqの升の長い利きを表現する16bitの値で、すなわちこれはWordBoardです。

このようになっていることで、例えば、先手の左方向への長い利きを増やしながら、後手の左方向の長い利きを減らすというようなことが同時に行えます。

具体例としては、先手が飛車を55の升に動かして、35にあった敵の飛車の利きを遮断したとします。このとき55の升の左方向には敵の飛車の長い利きが伸びていたはずですが、この遮断処理と、発生処理が同時に行なえます。

先手の左方向への長い利きは
value = 1 << DIRECT_LEFT;
のように表現できるとします。このとき後手の左方向の長い利きは、これをさらに8回シフトした
value = 1 << (DIRECT_LEFT + 8);
となります。なので、

value = (1 << DIRECT_LEFT) | (1 << (DIRECT_LEFT + 8));

と設定して、上の更新処理のコードによって先後の長い利きを同時に更新できることになります。

WordBoardにする必然性

これでだいたい長い利きをWordBoardにする必然性が見えてきたかと思います。

指し手を3つに分類したときに、fromとtoの地点でそれぞれ2つの処理が発生して、その2つをひとまとめにして処理することが出来るので、ひとまとめにしたときに、同じ方向の利きは先後同時に更新したくて、そのためには、長い利きは各升、先後が一つの16bitの値として扱えたほうが更新処理が捗るのです。

『技巧』が用いたWordBoard

電王トーナメント(2015)での『技巧』のPR文書を見ると、利きをByteBoard/WordBoardで持っているという一文があったと思いますが、すなわち長い利きをWordBoardで持っていて、それを用いて利きの数(こちらはByteBoardで持っている)を差分更新しているのだと推測できます。

今回の記事の内容まで理解していれば、PR文書にWordBoardと書かれた時点で、「ああ、長い利きを持っていて利きの差分更新してるのね。」ということがわかります。(たぶん)

つづく

(Visited 1,467 time, 1 visit today)

コメントを残す

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