【決定論的】評価関数の確率収束でないブートストラップ方法【多分確実】
昨日の混乱は2つの探索S0とSの使い分けにあったとも言える。そもそも探索S0(ゲーム木全体を根から葉まで読み切るmin-max探索；いわば神の目)の評価関数が所与とする想定は現実的でないから、Sに統一しよう。すると話がうんと単純化して、概略として次の学習アルゴリズムが考えられる。
- 評価関数H(n) (n:探索の末端ノード)を使った探索Sを採択する。H(n)の初期値は適当に与えておく。
- 探索Sを使って対戦する。
このときプレイヤーA,Bは自己対戦でもいいし、片方（Bとしよう）は他のプログラムか人間であってもいい。 - 勝負がついたら、勝った方の初手から終局までの手筋がハイウェイになるように（他のゲーム木の葉ノード（＝ゲームの終端ノード）発のハイウェイに妨害されないように）H(n)を調整する。
- 調整後のH(n)を評価関数とする新たな探索S'を改めてSとして採択し、ステップ2.に戻る。
ステップ3.はブートストラップ型の自己学習を目指すコンピュータ将棋開発者がだれしも目標とするであろう動作をハイウェイと言う言葉をつかって言い直しただけに聞こえるが、orz
ハイウェイの性質については昨日のエントリからいくつかの役立ちそうな事実が言える。曰く、
- ハイウェイの終端ノード評価値（H(n)に他ならない）を、min｛ハイウェイ建設予定経路に含まれるANDノードのmin{D}｝まで引き上げてもハイウェイ建設の困難さは増さない（妨害する他のハイウェイが減ることはあっても増えることはない）。
- 性質1.の範囲でハイウェイ建設が済めばそれでよい。さもなくば、
max｛ハイウェイ建設予定経路に含まれるORノードのmax{D}｝＜min｛ハイウェイ建設予定経路に含まれるANDノードのmin{D}｝
が満たされるまで、ハイウェイ建設予定経路のORノードから分岐している他のハイウェイの評価値を引き下げる（次の性質3., 4.を使う）。 - ハイウェイの始点ノード評価値を引き下げる際、max{ハイウェイに含まれるORノードのmax{D}}までは無条件に引き下げられる（そうしてもハイウェイであり続ける）
その際、評価値を引き下げるノードはハイウェイの終端ノードただ1つで良い。 - 項番2.において評価値引き下げの障害となるmin{D}を発見したなら、問題となるノードを始点とするハイウェイに項番2.の原理を再帰的に適用して引き下げれば良い。
この際、引き下げ対象となるハイウェイの集合に次善のハイウェイが存在するのは確実なので、順序を破壊しないように引き下げ量を引き下げられるハイウェイの集合全体で画一とする。（これをまじめにやると単純に再帰1回では済まないがorz
性質3., 4.により、ハイウェイ建設予定経路を妨害する他のハイウェイを確実に抑制できる。以上のことから人類は確率収束しか保証されないなどという気むずかしいアルゴリズム（？）を用いた学習部を学習率αの与え方でなだめすかせつつ強化学習をかろうじて達成するような苦労からは永久に解放される。特に上記引き下げられるハイウェイの順序性保護（引き下げ量の画一化）を確実に行うなら、一旦建設されたハイウェイの知識は全く無駄にならない。
あとは、H(n)をいかにうまくパラメータ化するか、すなわちH(n)で最強の指し筋（これの存在は二人零和有限確定完全情報ゲームの理論が示している、つか当blogでも何通りかのやり方で述べている）を表現するために必要十分な評価因子の集合を確定することのみに集中すれば良い。それが完成したとき、もはや中途半端な強さで学習が頭打ちになる問題からも人類は永遠に開放され、ハンドコーディングによるプログラムの強化プロセスは確実に終焉を迎える、
