なんで実用に供される評価関数は多値なん? Part II.
<ここはGMA0BNの日記帳>
世の中には
- 評価関数Hと、ヒューリスティックを用いた
オーダリングや前向き枝刈りを駆使する深さdの探索(凝った探索)の組み合わせ
というものがあるわけだが、これを、思考結果を変えることなく、
- 評価関数H'と、ヒューリスティックに基づく
オーダリングや前向き枝刈りを一切含まない深さdの探索(単純な探索)との組み合わせ
に機械的に変換できないのだろうか?
それが可能なケースは絶無ではないはず。もちろん元のHの出自によってはできないかもしれないが、今はそれができるHを仮定しよう。
そのときの思考速度低下幅は、ヒューリスティックに基づくオーダリング前向き枝刈りの寄与がなくなった分、ということになるが、ひとまず思考速度の低下は気にせず、思考結果すわなち最終的に選ばれる最善手の一致のみ問題視する*1
で、また(不詰み判定に関するNB0AMG法を導いたときのような)変な論理展開になるかもしれないが、上記機械的変換手順は、上記変換が可能なHの中身を指定することなく「こうすれば良い」という方法だけは述べることができる。ここで「こうすれば良い」とは、「H(の出自)次第だが、それが上手くいけば変換が成功している」、の意味で解釈されたい
すわなち、まず、評価値の大小の向きを、当方にとって有利なほど大、と決めた上で、
- ある局面sから始まる深さdの探索木について、末端局面を列挙して返す関数手段EN(s, d)
があるとして、次のアルゴリズムに従う:
- 局面s = 根の局面s_root
- U=EN(s, d)
- Uの元をそれぞれ評価し、評価値の最大値Mを求める
- sの子局面をヒューリスティックに基づき当方にとっての有利さの昇順で列挙する。
これがs_0, s_2, s_3, ...,nだったとしよう。 - i=n,n-1,n-2,...,1について*2、下記を行う:
- T=E(s_i, d-1) (s_iから始まる探索木の末端局面(のサブセット)取得)
- T∩Uの全ての元の評価値が(M+i)となるように評価関数を調整する・・・(1)
- U=U-T
- s=s_n, d=d-1
- d>0ならステップ2.に戻る
根局面s_root 1個あたりについてはこれでおk
上記アルゴリズム自体は本日記で昔すでに述べたものではある考えを整理したもの*3
本日のエントリは、それに対し、工学的というよりはひとまず哲学的(!)意味づけを与えようとするものなので、とりあえず上記アルゴリズムの実装が複雑すぎる、とか、計算時間がかかりすぎる、とかいった工学的観点での指摘は無しにしていただきたい
で話を戻して、上記アルゴリズムを、実戦で現れ得るとか、現れた実績がある十分多数の局面について(それらをs_rootとみなして)繰り返せば、ヒューリスティックを用いた元の思考部を十分な精度で表現する評価関数が獲得されることは明らかだる…s_rootが本当に十分多種多様で、かつ調整操作(1)に既存の学習結果を壊す副作用が無ければ。
これ(十分多種多様のs_rootについて、調整操作(1)に既存の学習結果を壊す副作用が無いこと)は、評価関数の生成元汎関数Φが、ヒューリスティックを精度良く表現する評価関数H'を生成し得ることの十分条件になっている。ということで、Φの設計について形而上学的な(マテ
指針を与える
上記が必要条件かどうかは今のところわからないが、もし必要条件でもあるなら、これ(十分多種多様のs_rootについて、調整操作(1)に既存の学習結果を壊す副作用が無いこと)はs_rootの集合を固定したときの操作(1)における副作用の大小で2つの汎関数Φ_iとΦ_jの良し悪しの判断基準として使え、ここにヒューリスティックと評価関数の汎関数の関係が明らかになり、ヒューリスティックがゲームのルールの言い換えを意図している以上、ゲームのルールと評価関数(の汎関数)の関係も明らかになってくるのではないか
いやまったく知らんけど、、
追記
→次のエントリへGo!