今月がタイムリミットなのは万人にとっての普遍的真理

機械学習とチューニングに要する時間を逆算すると年内にせめて学習部ぐらいは形にしないといけない(もちろん実戦を積ませようとするならもっと急ぐ)。

ここでGMA0BNの迷走ぶりを報道するという当blogの使命を思い出したので、機械学習についてGMA0BNの過去の考えを批判などしつつ現時点で彼が思っているに違いないところを述べる。

その前に、GMA0BNがれさぴょん本p.60の上段に書いてあることを知っていることをお断りしておく。以下の記事の中で言ってることが完全ルックアップテーブル方式と完全読み尽くし探索方式の間を漂い続けるのはその両極端を知らないからではなく、一重に問題が超複雑でそんなことをすれば時間か空間を使い果たすからだ。できるなら誰もがとっくにどちらかの方法で解いているだろう、、

GHI対策に関する迷走の件について

GHIは最良優先探索において考慮すべき問題だが、完全探索と同値なαβ探索には基本的に無縁といえる。αβ探索でGHIの実例(draw-first caseとdraw-last case)を説明しようとしてできなかったのは当然だ。
また、GHI対策に言及するときループ(サイクル手順)に含まれるノードを単一ノードに縮退させるアイデアを述べたこともあったが愚策の極みなので撤回。

上記を明らかにするには正しい置換表の実装について述べねばならない。

あるゲーム局面xの置換表が正常に機能するためには、深さdのノードnで作成されたxの置換表が、後に深さd'≧dのノードnでxが現れたとき参照される形である必要がある。d'とdの大小関係が重要だ。
いま、根ノードから深さd_maxまでを深さ優先探索で読むものとすると、ノードnにおいて作られた置換表は、nからさらにd_max-d段先まで読んだ結果生じるものであるから(トラバースの順序を考えればわかる)、それを深さd'のノードn'において参照することは、根ノードからの深さで言うとd'+(d_max-d) = (d'-d) +d_max段先まで読むことと等価。ゆえにd'-d＜0だと深さd_maxまで読んだことにならないから最初の意図とは違う(深さd_maxまで読んだわけではない)探索結果になる。
すなわち、同一深さのノード列挙順依存で、結果が意図した深さd_maxまでの完全探索に対して劣化し得る。
だからd'-d＜0なケースが生じるような置換表の実装はバグ。そうでないなら、αβ探索において置換表は基本的にGHIを生じない。

「基本的に」とことわりがつくのは、深さd_maxまで読むつもりが部分的にd_max + αまで読んだのと等価になってしまうと、評価関数によっては局面評価に問題を生じることがあるからだ。とある人がとあるページでそういう傾向にある評価関数の実例を示しており、当blogの過去記事からも参照してたと思う*1。するとトラバースの順序によって局面評価の大小順が異なるから、GHIが起きたと言える。(αβウィンドウ幅を弄ったαβ探索の場合はどうかというと以下略)

これがdf-pn探索だとシビアで、置換表を上記の形で正しく実装しても、根ノードからの経路の記憶を持たずに最良優先探索する限りGHIから逃れられない。
いやより正確に言うと、置換表の概念が成立しない。
なぜなら最良優先探索は反復深化込みの探索手法であり、一度訪れたノードの探索結果をd_maxの増加を挟んで持ち越すことが前提だからだ。
上述の置換表の説明文になぞらえて説明すると、d_max=Nのときノードnで作成された局面表のエントリeが、次以降の反復すなわちd_max=N+m (m>0)のとき深さd'のノードn'で参照されるということが普通に起きる。
するとd'-d≧0であっても、d_max=N+mである探索においてノードn'でeを参照することが、深さN+m以上読んだことと等価にならない(深さN以上のどこかまで読んだのと等価とは言えるが、その「どこか」が深さN+mに達している保証がない)。
なお、置換表になっていないものを置換表と呼ぶのはおかしいからdf-pn探索については局面表と言い換えた。以後この規則に従う。

まとめ

何にが言いたかったのか忘れたが、とにかくループ(サイクル手順)に含まれるノードを単一ノードに縮退させるアイデアは、ループを縮退させる過程で必要無いかも知れないノードを無駄にトラバースした挙げ句、さらに子ノードを異様にたくさん持つ単一ノードを現出せしめる結果、以後の反復において最良優先探索してるのか水平探索(!)してるのか分からない状態にしてしまって探索効率を極度に低下させる上に、メモリ消費もループを見つける度に青天井であってキャッシュ利用効率上も最悪の結果を招く。

今にして思えば「GHI対策は簡単だ」の後にはこう続けるべきであった。「水平探索すればGHIは全く発生しない」

*1:つか統計的手段で求めた評価関数はだいたい評価値のmin-max結果に探索深度依存性があると思われる