超訳！Tree Strap Search

現実逃避したくなることがいっぱいだから現実逃避してみた。
ここの超訳。
無許可でしかも途中までで訳したより先は全く読んでないというおまけつき。

ゲーム木探索結果による探索ブートストラップ手法
Joel Veness, David Silver, Wiliam Uther, Alan Blair
(超訳：GMA0BN)

【要旨】
本論文ではそれはαβ探索から計算される結果を用いて評価関数を更新する新しいアルゴリズムを提案する。提案する手法は既存の探索からの学習ベースアルゴリズム（サミュエルのチェッカープログラムの手法やTD-Leafアルゴリズム）とは2つの点で異なる。一つは、単一ノード評価値だけでなく全ノードの評価値について評価関数を更新すること、もう一つは連続する2手番の探索結果でなく単一手番内での深さ探索の結果を学習の教師信号とすることである。我々は新しい手法をチェスプログラムMeepに実装した。評価関数は線形荷重和のものを用いた。荷重ベクトルを小さな乱数値で初期化後、Meepは自己対戦だけで高品位な荷重を学習し、人間と対戦してもマスターレベルな戦いを見せ、戦績において他の自己対戦による強化ベースなチェスプログラムを圧倒した。

【概要】
本手法は深さ方向探索の値に向かって評価関数のパラメータを調整するというものである。本手法の正当性は木構造探索が持つ再帰性に由来する。すなわち、パラメータを深さDの探索において最適値に調整できたなら、深さkまでの探索をもって深さk+Dの探索と等価とみなせる。（訳注：これはDが少なくともゲームの真の最善手のある連鎖の長さ以上でないと厳密には成立しないから現実に可能な探索の限界深さと現実的なゲームの複雑さを前提として厳密に正当性を問うなら誤りのはず。）

チェスみたく確定2人ゲームが本手法の理想的な実験場となる。このような大量の局面を探索せねば有効な手を決められないゲームにおいて、非探索ベースの学習手法は効果を上げてこなかった。探索ベースの学習について、多数の第一級の仕事がチェスかそれに類する2人対戦ゲームで成され、従来手法との違いは明かである。

探索ブートストラッピングという独創的なアイデアはサミュエル(1959)がチェッカープログラムにおいて最初に発表した。サミュエルの手法では、評価関数の更新は黒と白が交互に動いた後で、それぞれのmin-max探索結果（評価値）で行われる。この手法は後にBaxtcr他(1998)によって改良され、チェスプログラムKnightcapに組み込まれた。その改良版アルゴリズムTD-Leafでは、評価関数は、あるαβ探索で得られた主経路の評価値が、次に行われるαβ探索で得られる主計路の評価値に近づくように調整される。（訳注：固定深さの探索だとすると、αβ探索間で主計路は（評価関数の更新をこの間行わないと言っているから）概ね変化しない。末端ノード位置が1段深くなるだけのハズ。）

サミュエルの手法とTD-Leafは3つの難点を抱えている。一つ、自己手番から次の自己手番が来るまでに1ノードしか更新しておらず、探索木に含まれる貴重な情報を見逃していること。二つ、ゲームに実際に現れた手のみに基づいて更新すること。これは自己対戦においては偽りの最善手である疑いがある。それは十分に評価されるべき多くの手を反映しおらず、複雑な局面で要求される精妙な手とは隔たりがある。（訳注：調整中の評価関数は真の最適戦略とは別の戦略を記述している。）