探索効率化の天王山・GHI問題対策
何を言っているのか(ry
GHI問題については下記に詳しい説明がありますん↓↓↓
ttp://www.fun.ac.jp/~kishi/pdf_file/kishimoto_gpw2004_paper.pdf
つか漏れは今のところコレしか読んでいない(何
GHI問題まとめ
深さ優先探索である手筋aが導かれる過程(深さ方向に探索が進行)で、1回見たのと同じ局面のノードが再び現れたとする。
例えば、n1->n2->n3->n4->n5->n6->n7というノード系列において、n7の局面＝n3の局面だった、等。
以下簡単のため、局面が同じとわかったノードを同じ記号で表すことも許そう*1。
すると上の例は、n1->n2->n3->n4->n5->n6->n3と書ける。
draw-first case
ある日、A君は自慢のチューニングを施した探索ルーチンでαβ探索(もしくはdf-pn探索)中にn1->n2->n3->n4->n5->n6->n3というノード系列を得た。
「あ、n3ってループじゃん調べる必要ないじゃんラッキー」
という短絡の下に、n3を子孫ノード探索済み辞書に登録してしまうところから悲劇が始まる。n3を通ったからといってループになるとは限らないのだ。
例えば、n801->n802->n3->n4->n805->...とか、n3を経由しつつループではないパスが以降の探索で現れないとなぜ断言できるのか？
draw-last case
ある日、B君は自慢のチューニングを施した探索ルーチンでαβ探索かつ反復深化中(df-pnは除外していい)にn801->n802->n3->n4->n805->n806というノード系列を一瞬得たのだが、n802ノードにおいてn3がβカットされ、n802においてαβ幅極小となる子ノードとしては直前のn33が採択された。
「あ、n3ってn802からだとβカットされるじゃんラッキー」
という短絡の下に、n3を探索不要辞書に登録してしまうことから悲劇が始まる。発見された、根ノードからn802を経由してn33に到るパスは暫定的な最適パスにすぎず、同じ反復深化サイクルの中で、n33でなくn3を経由するより優れたパスが発生しないことにはならないのだ。
例えば、まだ未探索のパスの中にn901->n902->n903->n904->n3->n4->n805というパスが本当は存在し、しかもαβ探索上n801->n802->n3'よりも良いというケースが有り得ないとなぜ断言できるのか？
なお親ノードn802と子ノードn3の組を探索不要として辞書登録することは、間違いではないものの、全く無意味だ(αβ探索の枝刈り効力と被る)。
21:30追記
よく考えたらこのB君のケースって、ノードn3について、n3のαβ値(最初の親ノードn802においてカットされる前の真の値)を辞書にでもしとけば(辞書サイズの問題はともかくとして)解決しそう。てか本を斜め読みしたら、うさぴょんは局面クラスにまさにその意味のメンバを持ってるしー。
というわけで、漏れのdraw-last caseの理解は疑った方が良い。
df-pn+は不要(!?)
実は上に上げたリンクはdf-pn+(の実験)の論文だが、その中身は読めばわかるとして(絶対間違いのない方法でおそらく効率も高い、バット、、、)、
draw-first case限定で遥かに簡単な解決方法がある。見つけたループを1個のノードに縮退させればいいのだ。
ループを適応的に発見する方法は自明。
で、ループに含まれるノード全ての子ノードの和集合(ただしループを構成する当のノード群は除く)を縮退したループの子ノードとみなすことにして、以降そのループを1個のノードとして取り扱う。これは辞書の工夫で効率的に行うことが可能だ。
縮退したループがさらに大きいループの一部であることがわかった場合でも全く同じ考えで再帰的に処理する。
一方draw-last caseについては以下略*2
