Microsoft PowerPoint - presentation.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - presentation.ppt"

えのたけはな
5 years ago
Views:

1 局面評価の学習を目指した探索結果の最適制御東北大学院理化学専攻保木邦仁力任せの探索は簡単高性能! Miimax 法 ( 8) Miimax 法 +beta cut ( 8 ) = ( 8.9) Miimax 法 +beta cut+ull moe pruig や hash cut Miimax 法 +beta cut+ull moe pruig や hash cut +Futility pruig 1 8 = ( ) = ( ) 1 秒に 5 万局面探索 1 秒で 18 手先まで読める実際は静止探索や moe reorderig の不備により効率が落ちる. 思考時間は序盤 3, 終盤 5 に比例する程度 1

2 Boaza 探索アルゴリズム概要 1 通常の探索基本的に全幅探索 + 静止探索. 用いる枝刈りは Beta cut Null moe pruig Futility pruig 2,8 段目の香, 飛角不成りは考えない Bitboard 反復深化 Aspiratio search. ウインドウ幅は歩の交換値 2 つぶん PV search 延長王手 (1 手 ),oe reply (.5 手 ), リキャプチャー (.5 手 ) 指し手の順序並び替え Traspositio table ( 静止探索では用いない ) 再帰的反復深化 (PV ode で hash moe が手に入らない場合 ) 一手で詰む王手 Static Exchage Ealuatio (SEE) Killer moes History heuristics 専用の詰み探索ルーチンは使わない. Boaza 探索アルゴリズム概要 2 静止探索手番を持つ側は手を指すか stad pat を返すか選択静止探索を開始してから深さ 7 段目まで SEE の下で駒損しない以下の手を探索取る手成る手王の移動一手詰みの王手 8 段目以降は歩を取る成らない手を除いた駒損しない駒を取る手を生成 SEE による指し手の順序並び替え静的評価関数駒二つの組み合わせを選び, 位置等対応する特徴ベクトル要素を足し合わせる全特徴ベクトル要素は棋譜から機械学習により求めた 1 万を超える全ベクトル要素数を探索アルゴリズムと辻褄が合うよう手動で調整し, miimax 型探索の性能を向上させるのは不可能. 機械学習による自動調整が不可欠 2

3 局面評価の学習 TD-Gammo (G. Tesauro) 思考部の学習 Temporal differece + euro etwork Logistello (M. Buro) 辺のパターンの重み学習最小二乗法 GPS 将棋 ( 金子ら ) 序盤の駒組みを棋譜から学習親子, 兄弟モデルを用いた線形回帰最適制御理論最大 ( 小 ) 化問題として力学系の制御方針を推論するラグランジュ形式の解析力学パルス整形による化学反応制御最小燃料のロケット弾道工場の消費電力池の魚に与える餌 J = T (,, ) l x u t dt t: 時間に関する数 ( 離散も可 ) x(t): 系の状態 u: 制御変数 t を手数,x(t) を miimax 探索の指し手で発展していく局面,u を特徴ベクトルとみなし, 最適制御理論に基づいた将棋プログラムの機械学習をおこなう 3

4 Miimax 探索結果の最適制御最適制御法に基づき, 棋譜の指し手と miimax 探索が良く一致する特徴ベクトルを求める指し手の一致度を測る目的関数 J を以下のように設計する N 1 1 N 1 = i= (,,,, ) (, ) J P P P l P i P i : サンプルされた棋譜中の一局面 l(p i,): 全合法手の評価値の違いの度合いを測る M m= 1 (, ) = (, ) (, ) l P T p p ξ m ξ m= p m : 局面 P を合法手 m で進めた子局面 M: 局面 P での合法手の数 m = : 棋譜中で実際に指された手 ξ(p m,): miimax 探索の評価値 T(x): 評価値の差を, 棋譜の指し手との一致度に変換する関数 T(x) の関数形と役割 1 一価の単調増加関数. x が大きい領域で傾きが小さく,x = 付近で傾きが大きくなる 1 階微分可能なもの. x =, x <, x > の意味は T(x) を階段型関数にとると, 目的関数 J はサンプルされた局面中, 棋譜で指された手よりも良く判断してしまった合法手の数となる. 強いプレイヤーと同じ手を指す miimax 関数の設計目的関数に停留値を与える特徴ベクトルの求解 1. T(x) x / 歩の交換値図 1:T(x) の関数形.( 実線 ) 階段型関数 ( 破線 ) 計算で実際に用いられたもの 4

5 T(x) の関数形と役割 2 T(x) が傾きを持つ領域の幅は, 目的関数が指し手の善悪判断を行う分解能に相当分解能が良すぎると目的関数の滑らかさが失われる. 傾きを持つ領域内にあるサンプル中の合法手が減少し, 学習データが不足. 分解能が悪すぎると目的関数の大きさと, 強い人の指し手との一致度の関係が失われる. 悪い手をさらに悪く, 良い手をさらに良く評価する方針で最適化されてしまう. このように,miimax 探索結果を変えない調整は適当ではない. Miimax 探索の深さが十分ではなく, 駒の損得詰みが全く認識できない局面も学習データとして使ってしまう. 1. T(x) x / 歩の交換値図 1:T(x) の関数形.( 実線 ) 階段型関数 ( 破線 ) 計算で実際に用いられたもの拘束条件の導入自明解 = や駒割り等が定数倍変化した別解の除去 (,, ) (,, ) λ ( ) J P = J P + M M 1 λ はラグランジュの未定乗数.M 1 () は駒割りに関する特徴ベクトル要素の大きさ等に相当し, これを定数 M に拘束する. ラクランジュ未定乗数 λ を導入する利点 p 個の変数に対する q 個の拘束条件から p q 個の独立な変数を求めることは可能だが, この作業は一般に困難 λ に適当な値を設定し, 目的関数の導関数がになる p 個の変数を求めると, 独立な変数の組を求めることなく拘束条件を課すことが可能. 5

6 ペナルティーの導入駒割りの占める割合を出来るだけ高く保つ過学習を回避目的関数の極小点を減らす最終的な目的関数の表式 N 1 i 1 2 i= (,, ) = (, ) + λ ( ) + ( ) J P l P M M wm w はペナルティーの重みを決めるパラメタ, M 2 () は特徴ベクトルの大きさを表す関数最適化の数値的手法 1 ベクトルの要素数が非常に多いため, 目的関数の勾配を求めて最適化を行う ( ) ( ) N 1 M i 1 dt x leaf leaf,, ( i, m, ) ( i, m, ) = i= m= 1 dx J P = f p f p ( ) ( ) + λ M + w M 1 2 miimax 探索の結果としての最善応手列が近傍で単一と仮定し以下の関係を用いた ξ ( p ) ( leaf i, m, = f pi, m, ) 興味深いことに,TD-leaf でも ε 6

7 最適化の数値的手法 2 目的関数が十分滑らかではないを更新すると最善応手系列が変わる T(x) の幅の中にあるサンプル数が少ないよって,2 次収束の性質をもつ手法は上手く働かない J ( P ) = h ew old,, l l sig l 初期特徴ベクトル要素と h を整数にとる h は初めは粗く, 徐々に小さく計算の詳細 1 静的評価関数で考慮する局面の特徴駒割王と他の駒 2 つの位置王と王に隣接した味方の駒とその他の味方の駒 3 つの位置隣接しあった駒 2 つの位置関係竜馬飛角桂香の利き上にいる駒の種類竜馬飛角香が動ける枡の数 pi aalysis. ピンされている駒の種類方向王との距離を考慮角と同じ色の枡にいる味方の歩の数歩桂銀が前進できるか竜飛香の前後の歩王の周囲 25 枡の利きの配置プロ棋士の棋譜 3 万局と将棋クラブ 24 の棋譜 3 万局 ( 主に入玉 ) を用いて静的評価関数のパラメタ約 1 万を調整 ξ(p, ) には一手読み + 静止探索の Boaza を使用 7

8 計算の詳細 2 拘束条件は飛角金銀桂香歩の駒割りの和ペナルティーは以下のように課す ( ) ( ) 2 M = A 2 l l l ( ) dt x A f p f p N 1 M i 1 l ( ) = i m i m i= m= 1 dx l leaf leaf (,, ) (, =, ) 出現頻度の高い特徴には強いペナルティー例 )8 八王 - 金の位置に対する得点ペナルティーなし A l なし A l あり 1 八金 -2 3 八金八金八金八金八金 -1 結果駒割 ( 交換値 ) 歩と香桂成香成桂成銀銀金角馬飛竜持ち駒の数歩 : 香 : 桂 : 銀 : 金 : 角 : 28 9 飛 : 角馬の動ける升の数角 : 馬 : 香飛竜縦方向に動ける升の数香 : x 飛 : 竜 : 飛竜横方向に動ける升の数飛 : 竜 :

9 王が 8 八にいる時の味方の金と K 王が 9 九にいる時の味方の金と K 王が 8 八にいる時の敵の金と K 王が 9 九にいる時の敵の金と K 王が 8 八にいる時の味方の歩 x x x x x x x x x K 王が 9 九にいる時の味方の歩 x x x x x x x x x K 王が 8 八にいる時の敵の歩 K x x x x x x x x x 王が 9 九にいる時の敵の歩 K x x x x x x x x 9

88 王の時の味方の駒 2 つの位置 +8-1 +1 王銀 -33 +5-14 +1 金の位置の得点 -7 +1 +1 王金 +1-2 +9-96 +1 +1-2 王銀 -16 +72 +19 +52 歩の位置の得点 +1 +1-1 王金 +2-17 -6-42 78 王の時の味方の駒 2 つの位置 +4 +6 +23 王銀 -12 +18 +4 +33 金の位置の得点 -1 +9 +18

10 88 王の時の味方の駒 2 つの位置王銀金の位置の得点王金王銀歩の位置の得点王金王の時の味方の駒 2 つの位置王銀金の位置の得点王金王銀歩の位置の得点王金問題点王が 6 一にいる時の敵の飛 -69, , ,

Microsoft PowerPoint - hoki-print.ppt

Microsoft PowerPoint - hoki-print.ppt ゲーム木探索の最適制御 : 将棋における局面評価の機械学習東北大学大学院理学研究科保木邦仁コンピュータ将棋プログラム Bonanza Bonanza 製品版を販売大和証券杯特別対局新聞一面カラー全国版テレビニュース NHK 衛星第 2 運命の一手 1 時間に及ぶドキュメンタリー角川書店新書ボナンザ VS 勝負脳一般の方々にアピール 1 何故こんな事になってしまったのだろう強い将棋プログラムを無料で公開