下手の考え何とか(ry
将棋やオセロや三目並べとかの思考ルーチンの評価関数はどうあるべきか考えてみるテスト。
末端評価関数
ゲーム木を葉ノードまで読み切れるならAND/OR木として読み切った時点で勝敗(もしくは引き分け)が決定する。のだが、ノード数の爆発のためゲーム終盤を除く一般のケースでは葉ノードまでの読みを遂行できず、途中で探索を打ち切ることになる。この打ち切ったノードを点数づける関数を末端評価関数という{要出典}。
思うにこの概念のポイントは、
- 末端評価関数 ＝ 探索を打ち切ったノード以下(の部分木)を読み切った結果の代替品
であること。つまり、少なくとも、AND/OR木的に見た自己の勝敗と、末端評価関数の評価値の大小が対応していないといけない。
この基本原則を外した関数選択を行うと、一体何を探索しているのかわからなくなってしまうハズ。
以下、「評価(関数)の精度」を、探索を打ち切ったノード以下を読み切った結果との一致の良し悪しの意味で使う。
末端でない評価関数(?)
末端評価関数のスコアは捨てられるか、(親にあたる)中間ノード(ていうかそのノードを根とする部分ゲーム木)のスコアになるかの2者択一とされる。
わざわざ「末端」と頭に付くぐらいだから、末端でない(中間ノード固有の)評価関数もアリなのでは、と勘繰ってしまうがちょっと考えればわかるようにその考えはあまり意味がない。中間ノードにおいて十分精度の高い評価手段が存在するなら、そのノードで探索を打ち切ればいいからだ(結局末端評価関数になる)。
同じものを同じに見えるようにしよう
末端評価関数は、探索を行うことなく探索と同じ結果を求められる。したがって、探索して読み切った結果(勝敗確率)が同じになるものにできるだけ同じスコアがつかねばならない。もちろんその裏(違うものが違うように見えねばならない)も成り立たねばならない。
局面の特徴量
末端評価関数は、探索を行うことなく探索と同じ結果を求められるわけだが…
この「探索を行うことなく」とは、(通常は)局面一つだけ見て値を決めよ、と解釈すべきものである。
ところが局面一つに「同じものを同じものに見えるようにする」ならびに「違うものを違うものに見えるようにする」を十分実現するだけの特徴が簡単に見出せるとは限らない。
そのようなケースでは、末端評価関数を練り直すか、別手段での枝刈りによって評価自体を回避する必要があると思う。
末端評価関数と過学習
上述のように末端評価関数がクリアすべきハードルは高い。やってることはおよそ多値出力に拡張されたパーセプトロンに近く、下手をすれば過学習がおきて「同じものを同じものに見えるようにする」ならびに「違うものを違うものに見えるようにする」が満たされなくなるはずだ。
この観点に立てば
- 局面からできるだけ多くの特徴量を(大半捨てるつもりで)入力する
- 中間層にあたる論理エレメントを大量に用意する
という方針がいいはず。
してみるとBonanzaの評価項目1万個というのはそのままパーセプトロンとしての学習能力と解釈できるのかもしれない(1万個が「可能だった」のでなく、強力な学習を実現する上で「必要だった」)。
まとめ
現時点での末端評価関数案。
- 将棋の場合：駒の組み合わせ毎の距離の逆数と、駒毎の移動可能径路と他の駒との距離の逆数の線形和。
- オセロの場合：同一色の石からなる線分で両方閉じてはいないものの長さ別および閉じた側の石の交代別の数と、それに該当しない同一色の石の数の線形和。
- 三目並べの場合：(考えちう)
評価項目の種類は少なめだが、組み合わせを考えるとこれでけっこうな数になる(将棋の場合で9000個ぐらい)。
線形和の重みは、学習させねばならない。
序盤・中盤・終盤の戦術切替方式は未定(ちうか輪をかけてよく知らない)。
できれば全自動で洗練化させて正当性確認までさせたいがそれはまた今度。
