Hellow, clueru warld
今日わ、「評価関数の精度」とか、そこらへんについて考えてみたい。
個人的には
- 二人零和有限確定完全情報ゲームに神の一手が存在する
という事実と
- df-pn探索
は完璧に整合する*1のに対し、min-max法(含αβ法)の立ち位置はなんか微妙─────みたいな、
確かに「常に終局まで読む」等の極限的な条件下でならmin-max法で得られる最善手と神の一手の一致を示せるが、一般的には一致するとは限らない、
ていうか実際成り立たない例があることを一昨日述べた
これについて「神の手筋に合流する手筋は神の手筋に決まっているではないか」と言う人がいるかもしれないので補足しておきたい。
いま、無限に高い精度の評価関数を用いた深さnまでの固定深さの探索によって神の一手とそうでない手が分けられたと仮定する。すると、神の一手の先のANDノードから始まる部分木(∈S1')と、そうでない手の先のANDノードから始まる部分木(∈S2')について、次の関係が成り立つ
- S1'に属する部分木を通る手筋のうちαβウィンドウを最大にする手筋は、深さnにおいて、S2'に属する部分木とノードを共有しない
(∵さもなくば「分けられた」という仮定に反する)
(仮定上、あくまでS2'に属する部分木を通る手筋が神の手筋ではありえないことに注意しつつ次へ)
だが、サイクル手順が存在するゲームにおいてS2'に属する部分木からさらに探索延長した場合、探索の先端がS1'に属する部分木に入り込み、さらにその部分木を通る手筋のうちでαβウィンドウを最大にする手筋と合流する可能性を否定できない。そうなった場合、延長された手筋においても神の手筋同然にαβウィンドウが最大になるから、その手筋が探索上神の手筋と区別できなくなってしまう。ゆえに、サイクル手順があるゲームにおいては、探索延長によって神の一手を取り違える危険が一般に存在する(少なくとも、ゲームの詳細に立ち入らねば直ちには否定できないという意味で)、と結論される。
騙されてるように感じるならそれはill-definedな要素がどこかに紛れ込んでいるせいかもしれない。その最有力候補は「評価関数の精度」という概念だと思う。こいつは実は探索の具体的前提条件と切り離しては述べられないのではないか？
この点を汲み上の例をよりwell-definedな形に言い直せば、おそらく、深さnまでの固定深さの探索において無限に高精度な評価関数は、実は探索の深さをn以外にしたとき致命的な誤りを生じ得ますよ、とかそんな感じの話、、
、、、実わ結局LS3600さんが言っていた評価関数の副作用が害を及ぼし得るという話になるのか、、orz
とにかく探索の先端でPGがやれることは組み合わせ的に星の数ほどあるはずだが、実用に供されている探索延長手法が数えるほどしかない理由はおそらくこのあたりに由来するのだろう、、
ではないだろうか、、
いや知らんけど*2、、
