学習とかそこらへんの話
死活の概念や勝負勘といったものの自動獲得を考えてみる。
必要性?
コンピュータ将棋について見聞きする限り、現状強い思考ルーチンほど微に入り細に渡るチューニングが必要なようだ。単純に末端評価関数の値を信用して探索したのでは、末端評価関数の精度の限界から重要な手、特に、一見評価上の得点は高いのだが自己が必死だったりする手筋を見逃してしまう(らしい)。
そこでどうしているかと言うと、現状は人間がそれらの概念(死活の概念や勝負勘といったもの)をプログラムしている。
これは煩雑極まりない作業だが、作業としては避けられないと思う。われわれは面白いゲームで勝ちたいのだし、そうしたゲームは共通して変化に富むという特徴を有する。すなわち1手の違いが形勢の重大な差異を生み、末端評価関数の誤差もまた拡大されて勝敗に直結してしまうから、「誰かが」「何らかの手段で」妥当な補正をしてやらねばならない。
また、強敵を相手に「死ににくい」だけでは勝利は覚束ない。有限の手番で終わるゲームである以上、敵より早く必勝手を打たねば負ける(か良くて引き分けになる)ことに変わりはない。
末端評価関数の精度がさほど期待できない場合、これらの問題は水平線問題という形で現れる(が探索をどこで打ち切るかも現状人間が大枠をプログラムしている)。
現状の手段
現状、上記補正の「手段」としてはつぎの2つの流れがあるっぽい。
- (賢い選択探索等で中盤を乗り切るとして)詰めエンジンで終盤を仕上げる方式
- 末端評価関数の高精度化(を行った上で全幅探索)する方式。
現状、トップクラスレベル同士の強さの比較においては両者伯仲のようだが、これを「意図せず死んでしまう」ことの起こりにくさも同等と解釈していいのかどうかはワカラソ。また、伯仲なら伯仲で、ベストな解はどっか中間あたりにあるのではないか、とつい勘繰ってしまう。人が任意に与えたゲームのルールにそうそう整った解法が内包されるとは考えにくい。
玉虫色の解決
下記のことを学習により完全解決に向かって全自動で漸進的に近づけていく。
- 末端評価関数の高精度化
- 選択探索の高度化
つまり負けたら末端評価関数と探索の選択則を変更するが、ただし過去に勝ったときの指し筋は保持させる。
末端評価関数は局面の特徴量ベクトルを入力とするパーセプトロンとして、教授信号は自己対戦で生成する。ただし、学習には幅広い入力が要る(不必要に偏った学習にしないために)から、教授役となる側の手には乱数を加える。
この乱数の与え方は後回しにするとして、どのように学習させるか?
- 対戦させる
- 勝負がつく
- 勝った場合:
- 必勝が決まった最初の手番まで局面を巻き戻す
- 負けた場合:
- 必死が回避される最後の手番まで局面を巻き戻す
- 勝った場合:
- 巻き戻した局面を記憶
- 記憶した局面で判断を誤らないようにパーセプトロンの結合加重を変更する。
(巻き戻しはいずれも詰めエンジンで判定しつつ行う。)
過学習の兆候が見えたら中間層を増やしてやり直す。ただし一旦記憶した局面は何度でも学習に使う(詰めエンジンによる確定結果なので学習の進度とは無関係に使える)。以上で末端評価関数の全自動強化サイクルが多分実現される。
次に選択探索の高度化だが…
上記手段で十分強化された末端評価関数は、読みきり探索の代用品として十分な精度を持つに到る…と仮定したいところだが、あまり過大な期待を掛けると裏切られる。(入力パターン数よりあまりに多いケースを判断させようとすると過学習めいた兆候が現れる。)
そこで評価の安定度に注目する。ノードを3段読んで評価値が同等なら、読み切り探索の代用を十分果たしたとしてそこで探索を打ち切る。不安定なら、その部分木について末端評価関数は信用せず、次のどちらかの手段をとる。
- 静止探索に切り替えてあくまで有効手(と期待される手)を捜す
- 無視
どちらをとるかは勝負勘に属する判断事項である。この基準をどう与えるべきかは後で書く。