Bootstrapping from Game Tree Search簡単なまとめ【大幅修正版】
自分が読んだところまで、メモがてら書いていきます。
※１ 多分私の勘違い等が含まれています。
※２ ざっくり意訳していますので、細かいところは原文見て下さい。
英語がスラスラ読める人は、以下の文読んでも時間の無駄なんで つhttp://books.nips.cc/nips22.html
＃ 2010/04/11 12:21 読み直していたら訳がダラダラ長くて嫌になったので、大幅に修正しました。
1. イントロダクション
search bootstrappingは静的評価値が深い探索の結果を近似する様にパラメータを調整する為のもの。もし静的評価値が深さDの動的評価値を近似出来る様になれば、その後の（新しいパラメータでの）深さkの探索は（古いパラメータでの）深さk+Dの探索と等しくなる。
＃ この辺の発想は、柿木さんのK55の学習方式と似ているかも。
＃ あっちも深い探索を教師とした学習でしたし。
2. 背景
サミュエルのアプローチやTDLeaf(λ)*1は一つの探索木に対して一つのノード*2の価値をアップデートする。これは、大きな探索木に対しては無駄が多い。
実際の対局ではほとんど出現しない様な局面が探索中にはしばしば現れ、強くなる為にはその様な局面の評価精度が重要。上記二つの手法はその点で問題点がある。
3. ミニマックス探索ブートストラップ
最初のアルゴリズム（RootStrap(minimax)）はルートノードの静的評価値を探索の結果得られた動的評価値に近付ける。静的評価値を動的評価値に近づけ、逆向きには近付けさせない様に、動的評価値を定数として扱う。
RootStrap(αβ)とRootStrap(minimax)の違いは、探索にαβを用いることだけであり、他は同等である。
二つ目のアルゴリズム（TreeStrap(minimax)）は探索木の全内部ノードに対してもパラメータ更新を行う。
4. αβ探索ブートストラップ
ミニマックス探索ブートストラップをαβ探索に拡張する。
αβの探索木では、ほとんどのノードは正確な評価値が不明である。そこで、内部ノードの静的評価値がその内部ノードの価値の下界を超えた時だけ、静的評価値を下界に近付ける。上界に関しても同様の処理を行う。
＃ なんでこれで上手く行くのかまだ理解出来ていない。後でもう一度読み直す。
4.1 TreeStrap(αβ)でのパラメータ更新
置換表を用いて高速化するよ。
4.2 TreeStrap(αβ)のアルゴリズム
TreeStrap(αβ)はTreeStrap(minimax)に二つの単純な修正をしただけである。
- minimax関数をαβ関数に置き換える
- ΔθをDeltaFromTransTbl(s_t)関数で置き換える。
5. 学習対象のチェスプログラム
我々はMeepというプログラムに学習アルゴリズムを組み込んだ。これは、トーナメントチェスエンジンBodoの改良バージョンであり、1812個の特徴からなる線形評価関数を持つ。評価項目は以下の５つ。
- 駒割
- piece square table（絶対位置評価？）
- pawn structure
- mobility（自由度？）
- 王の安全度
評価関数のパラメータは小さな乱数で初期化した。終局時の評価値は負けを-9999.0、引き分けを0、勝ちを9999.0とした。
Meepはトーナメントモードと訓練モードを持ち、探索ルーチンの種類が異なる。探索の末端では静止探索を用いる。ここで知識ベースの枝刈りは行わない。
6. 実験結果
ここでは、学習手順の詳細を述べ、その後RootStrap(αβ),TreeStrap(minimax)とTreeStrap(αβ)の3つの性能を、大きなローカルトーナメントとオンラインプレイで測定する。
6.0.1 学習方式
各実験開始時に、全ての重みを小さな乱数で初期化する。自己対戦を用いて各プレイヤーを訓練し、訓練の多様性を維持する為に小さな定跡を用いる。一度定跡から外れたら、指し手はグリーディーに選択する。各訓練対局は"1m 1s Fischer time controls"*3で行う。これは、双方のプレイヤーは1分の持ち時間を最初から与えられ、一手ごとに1秒追加される。一局5分位で終わる。
学習率は各学習アルゴリズムごとに最適な値を選んだ。TreeStrap派生アルゴリズムは最小探索深さ1とした。これは目標値は最低1手の全幅探索と静止探索で計算される。
6.1 関連する性能調査
我々は、我々のアルゴリズムの一つを用いる、多くの異なるバージョンのMeepをトーナメントモードで比較した。乱数でパラメータを初期化しただけのプレイヤーをリファレンスとして加え、Eloレーティング250で固定した。各手法での最高レーティングを表2に示す。
また、各アルゴリズムの訓練中の強さも計測した。各訓練対局は同じ時間制限で行い、固定された計算量での性能比較になっている*4。重要なのは、学習に用いた時間も総思考時間に含まれるという事である。
この結果から、TreeStrapがTDLeaf(λ)及びRootStrap(minimax)より大幅に優れていると分かる。TreeStrap二種類はたった1000局で効果的に学習し、訓練期間を通じて最高の性能を示している。
我々の実験結果はTreeStrapベースのアルゴリズムは、乱数で初期化し、自己対戦を行っても良いパラメータを学習可能な事を示した。TreeStrapベースの手法は初期値依存性が低く、自己対戦での収束が高速だった。
