にわか微分幾何学乙 - 思うだけで学ばない日記 2.0

それはそうとして。
前回のエントリのアルゴリズムは間違いで、隣接行列の行を接続数降順で並べるんじゃなくて、まず列をノードの大小昇順で並べた後、上三角行列(左下に0が集中する)にしないと再帰にならんかったorz
えらくノイズの多いblogだが、見方によってはblog主の迷走っぷりが客観的解釈可能な形で報じられているという意味でこれはいい記事性が高いblogですね

局面の差分計算

ちょっと前のエントリで、ndがゲーム木のノードだとして、ndの子ノード列挙を

Node& nxnd = nd.NewChildNode();
{
  <子ノードnxndを参照する処理>
}

という構文を使って記述しようと図ったが、このセマンティクスを自然に解釈すると、1行目で親ノードndとは別に子ノードnxndを新規生成することになってしまう。これは空間・時間効率ともに悪いので却下*1。
ここはむしろ次のロジックが効率的。

Te te = nd.NextTe();        // (子ノードでなく)手を列挙
nd.ChangeWith(te);          // ndに手teを適用する(オブジェクトndは子ノードに変更される)
{
  <子ノードを参照する処理>  // このブロック内では、nd == 子ノード
}
nd.RestoreFrom(te);         // ndを元に戻す

ここで、Teクラスは、駒の種類、駒の移動前座標、駒の移動後座標の組を含むクラスであり、手を表現する。具体的局面に手を適用したときの局面の変化は動いた駒の移動前座標と移動後座標に極限されるから、その影響さえ計算すれば次の局面が得られる。つまり差分計算というやつ。これはれさぴょん本で知った。
逆演算(元の局面に戻す)も同様にして実現でき、いずれにせよ1局面まるごと新たに生成するより少ないメモリコピー量で行える(ことが十分期待される)。つまり早い(と考えても罰は当たらない)。

draw-first caseのGHI対策

簡単だと言った手前回答を示しとこうっと
まず、新規ループを見出して登録する方法は自明だ*2。
また、任意のノードnが既知のループLxの一部かどうかは、nの局面のハッシュをキーとする辞書を別途用意して高速に判定することが可能だる。これをループ所属辞書と仮に呼ぶ。
1つのループは、ループを構成する具体的局面(先頭局面と呼ぶ)と、それに引き続く手のリスト1周分で記述で完全に記述できる。この<ループ>表現を採用しよう。

ノードnがループLxの一部だとして、ではLxを構成するどのノードなのか？これは、上記<ループ>表現において、先頭局面から順に局面のハッシュを差分計算し、Lxのハッシュと一致するポイントを探せばわかる(とりあえず線形探索)。
上記探索でnがLxを構成するどのノードか特定できれば、nから出発してLxを一周し、再びnに戻る手筋を得たことになる*3から、それらを辿りつつ子ノードを列挙することは差分計算のみで容易に行える。ただし、子ノードを順次列挙するうちに、Lxに舞い戻ってくるケースは注意が必要だ。出発ノードをn1、舞い戻ってきたポイントをノードn2としよう。n2より先の列挙は、Lxの子ノード列挙と完全に被るから、探索効率上避けねばならない。そこで次のように処置する。

次の新規ループLyを生成し、以後Lyを構成するノード(の局面のハッシュ)から引けるように辞書登録する。
- 先頭局面: n1
- 手のリスト: n1→n2に至った手筋(履歴から取得)と、n2→n1に至る手筋(Lxの<ループ>表現から取得)を接合したもの
列挙は、n2から単に親ノードに戻り、他の子ノードの列挙に移る(親ノードから見てn2が最初から存在しなかったかの如く振る舞う)

ここまでの処置を行った結果、探索で出くわす任意のノードは次のどちらかである。

既知のループの一部ではない
既知のループの一部である(2つ以上のループに同時に所属するかもしれない)

1.の場合、その子ノードの中に未列挙のノードがある可能性があり、かつその時点で列挙せねば後で列挙される保証はないから、(完全探索のためには)無条件で子ノード列挙を試みねばならない*4。なお、子ノードより下のノードの列挙の重複は局面表*5により発生しない(ことが気体される)。
2.の場合への対処としては、2通り考えられる。

ノード列挙時に、ノードが所属する全ループを1回以上通過する経路を辿る。
ループLx新規登録時に、所属する予定のノードnzがすでに他のループLzに所属しているかチェックし、所属していたらそのループを展開した結果(手のリスト)を登録しようとするループに組み込む*6

1.だとノードが複数のループに所属できるようにループ所属辞書を工夫せねばならない*7。
2.はループ所属辞書が簡単で良い。Lz所属のまま変更されないノードが残ってしまうが、同一ノードの多重探索にはつながらないから問題ではない。

雑感

しかっし、評価関数をこの世で最も多く計算する人たちが評価関数の正体について定見を見いださないというのは不思議な現象だる
駒の交換値とか、より上位の概念で統一的に説明されるべきものの粗雑な近似物に思えてならない

*1:ndとnxtが同時に空間を使用するから空間効率が悪く、さらに新規生成には親局面1局面分をまるごとメモリコピーせざるを得ないから時間効率も悪い。

*2:局面表(れさぴょん本参照)と手の履歴のスタックを用意し、1回の深さ方向探索で通過した局面に出くわしたら手の履歴を(逆差分計算で)辿ればループを構成する全ノードを得る。なお局面表は探索の反復毎にクリアする。当然、登録要素数は高々最大探索深度である。

*3:Lxの<ループ>表現の手のリストを追うことで一周できる。

*4:列挙を試みねばならないが、必ずしも列挙しきらねばならないわけではない。αβなど、適当な手段による枝刈りは当然行う。

*5:れさぴょん本参照。この仕組みはループ検出のためどのみち必須。

*6:nzの所属は変更Lxに変更してもしなくてもどっちでもいい(たいして差はない)。

*7:ノードが所属する全ループを列挙できる必要がある。