投入計算量の有限性に基づくUCT探索の枝刈り新領域創成科学研究科基盤情報学専攻近山研究室 47-076308 北川竜平はじめに • 時間が限られている状態で最大の成果を得たい時には – 現時点で良さそうなことを重点的に考える – 考えても無駄そうなことは早めに打ち切る • 例：数学の問題集 – 家で解くときは時間がたくさんあるので全ての問題を解いてみる – 試験等で時間が限られている時は解けそうな問題から解く – 解くのが難しそうなら後回し x 2  3x  2  0 d 2 y dy   y  ex dx2 dx • この考え方でアルゴリズムの性能強化を行う 2 本研究の目的 • 対象 – 非常に難しい問題を解くアルゴリズム – 処理性能の低いCPU（組み込み用等）上で実行されるアルゴリズム • 実用的な時間内で精度の高い解が得られるとは限らない • 投入できる計算量は有限 – 使用可能な残りの計算量を意識させることでアルゴリズムの性能強化を行う • ゲーム木探索を例として、この考え方の有効性を実証 – 解くのが非常に難しい問題 – 処理性能の低いCPU上での実行も想定可能 (携帯ゲーム機等) – 評価が簡単 3 本研究の手法 • 残り探索時間を考慮することによる探索の放棄 – いくつかの選択肢の中から最善のものを選ぶ問題 • 評価値が一番高いものが最善 – 探索できる時間が t1までなら選択肢Bが選択肢Aを超えることはない • 選択肢Bの探索を放棄してもよい – 探索できる時間がt 2までなら選択肢Bが選択肢Aを超える可能性はある • 選択肢Bの探索を放棄してはいけない評価値それまでの評価値評価値の推定値の上限下限選択肢A 選択肢B t0 t1 t2 時間 4 本研究の位置づけ • 投入計算量の有限性を意識することによるアルゴリズムの性能強化手法の提案 • ゲーム木探索の性能強化手法の提案 – ゲームの知識を用いない – ゲームの性質に依存しない 5 発表の流れ 1. 2. 3. 4. 5. 6. はじめに背景関連研究提案手法実験と評価結論 6 背景 • ゲームにおける“解” – 与えられた局面において必勝の合法手を見つけること • ゲームを解くには、ゲーム木探索を使用 – ルートノード:現在局面・枝:合法手･子ノード:移行局面初期局面においては解かれた探索時間は数年単位ゲームチェッカーオセロ囲碁探索空間の大きさ 1030 1060 10360 ゲーム木探索は、非常に難しい問題を解くアルゴリズムに相当 7 ゲーム木探索 • 探索時間に上限が無ければ解くことは可能 – • 全ての局面を探索実際には有限時間で探索を打ち切って近似解を使用 – – モンテカルロ木探索 [Brugmann. 1996] UCT探索 [Kocsis et al. 2006] • • • 各合法手の評価値にはゲームのプレイアウトを繰り返した時の勝率を用いる評価値の精度はプレイアウトの回数に依存評価関数を使用しないので知識表現の難しいゲームや新しいゲームで効果的プレイアウト 30 100 … 60 勝ち数プレイアウト回数 100 … … プレイアウト何らかの方法により合法手を選ばせ、現在局面から終局までのゲームを行うこと 55 100 8 プレイアウト • モンテカルロ木探索 – 全てランダムで選択 • UCT探索 – 未探索ノード:ランダム選択 – 探索されたことのあるノード:UCB値が一番高いノードを選択勝率 UCB  X  正の定数 c log n s 親ノードのプレイアウト回数そのノードのプレイアウト回数 勝率の高いノード・探索された回数の少ないノード程探索されやすくなる 9 UCTの利点と欠点 • 利点 – 結果的に勝率が高くなりそうなノードを多く探索 • ゲーム木探索では選ばれそうな手の評価値の精度が高いことが重要 • 選ばれなさそうな手の評価値はデタラメで良い • 欠点 – 探索時間に上限が無ければ必ず最適な解が得られる • 実際は探索に使える時間は有限 • 探索時間の後半で、選ばれそうにない手に関しても探索してしまう 10 関連研究 • 選ばれそうな手のプレイアウトの回数を増やす – UCB1-Tuned [Gelly et al. 2006] • 多腕バンディット問題の手法 – Progressive Pruning [Bouzy. 2006] • モンテカルロ木探索の手法 11 UCB1-Tuned [Gelly et al. 2006] • UCB値を以下のように求める勝率 UCB  X  c log n s 親ノードのプレイアウト回数そのノードのプレイアウト回数 c を動的に求める 1 c  min( , V ) 4 V  2  報酬の分散 2 log n s • プレイアウトが多くなると、極端に勝率の低い枝が探索される可能性が低下 12 Progressive Pruning [Bouzy. 2006] • 勝率は正規分布に従うと仮定 • 区間推定で勝率の区間[ X L , X R ] を推定勝率報酬の標準偏差  XL  X r 信頼係数 XR  X  r s  プレイアウト回数 s • 手AのX Rより手BのX L の方が大きければ、手Aが選択される可能性は低い  手Aを枝刈り（＝探索の放棄）手A 手B XL X XR X XL 手C XL X XR XR 13 勝率問題点 • 現時点までの探索の結果のみを用いて、選ばれそうな枝とそうでない枝とを判別している – 評価値は現時点までの結果と将来の結果に影響される • 将来の結果を推定することで、より少ないプレイアウト回数で枝刈りを進めることが可能 14 提案手法 • ゲーム木探索を行うのに使える時間は有限 – 今後プレイアウトが行える回数が有限 • 残りプレイアウト回数から、それぞれの手が到達する勝率の区間を推定 – 現在非常に勝率の低い枝は、今後のプレイアウトでたくさん勝ったとしても高い勝率にはならない • その区間から選択される可能性の低い手を判断 15 提案手法概要残り10回しかプレイアウトができない絶対に選択されないので枝刈り … … … プレイアウト勝ち数プレイアウト数 60 90 30 90 55 90 勝ち数プレイアウト数 70 100 40 100 65 100 結果が最善だった場合勝ち数プレイアウト数 60 100 30 100 55 100 結果が最悪だった場合 16 到達勝率の推定 • 合法手 i が探索の終了時に到達する勝率 Pi 現在の勝ち数 X i  eiYi Pi  si  ei 現在のプレイアウト回数探索終了時の推定プレイアウト回数今後のプレイアウトによっ今後のプレイアウト探索終了時の推定勝ち数て得られる報酬の平均による勝ち数推定残りプレイアウト回数 • 将来の報酬の平均Yiと推定残りプレイアウト回数 ei が必要 17 将来報酬推定 • 今後のプレイアウトによって得られる報酬の平均の区間 [YL , YR ]を推定 – 報酬の平均は[0,1]のため最大値と最小値を設定勝率 YLi  max(0, X i  r 信頼係数 YRi  min(1, X i  r i si i si 報酬の標準偏差 ) プレイアウト回数 ) 18 残りプレイアウト回数推定 (1) • 安全な枝刈りにはプレイアウト回数の推定の上限が必要 • 区間推定によって合法手 i でプレイアウトが行われる確率q i の上限を推定 • 親ノードの残りプレイアウト回数 n と q iに従う二項分布 B(n, qi ) から、合法手 i の残りプレイアウト回数の上限 ei を推定 – 親ノードの残りプレイアウト回数n が必要 si qi  r sj jB i s jB プレイアウト回数の標準偏差 j 今回のプレイアウトで枝刈りされない手の集合 ei  qi n   qi (1  qi )n 19 残りプレイアウト回数推定 (2) • 1段目の残りプレイアウト回数 N は探索打ち切り条件から推定 – 例：プレイアウトの回数、経過時間 • 2段目以降の残りプレイアウト回数は本提案手法による推定値を用いる N nN e1 e 2 e3 n  e1 e11 e12 e13 20 到達勝率区間推定 • 探索終了時に合法手が到達する勝率の区間 [ PLi , PRi ]を将来報酬の平均の区間 [YLi , YRi ] と推定残りプレイアウト回数 ei から推定 X i  eiYLi PLi  si  ei X i  eiYRi PRi  si  ei • 手AのPRより手BのPLの方が大きければ、手Aが選択される可能性は低い 手Aを枝刈り（＝探索の放棄）手A 手B PL X PR X PL 手C PL X PR PR 21 勝率枝刈り条件 PRi  max(PL1 , PL 2 ,, PLk ) を満たす枝 i を枝刈り – PL は最大のものが正確であることが重要 – PR は全て正確である必要がある • 各種推定はプレイアウト回数が十分大きいときの近似 • – 最低枝刈りプレイアウト回数 s min を超えた枝でなければ枝刈りを行わない 22 利点 • 探索した回数が多くなると枝刈りが進む • 残り計算量が少なくなると枝刈りが進む • 勝率の低い手のプレイアウト回数が少ないUCT探索でも効果が期待できる 23 実験 • 対象ゲーム – 囲碁9路盤コミ5目半 • 実験環境 – CPU Opteron 2.1GHz QuadCore – メモリ3GB • 実験のパラメータ r  1.96   3.0 smin  16 • UCTとUCTにUCB1-Tunedを利用した探索(UCTTuned)に提案手法を実装 24 実験概要 • 推定実験 – 将来報酬推定、残りプレイアウト回数推定、到達勝率推定 • 枝刈り実験 – 枝刈りされた枝の割合、プレイアウト回数の割合、最善手を選ぶ可能性の変化 • 対戦実験 – 提案手法適用前と後との対戦結果、同一の相手に対する対戦結果 25 推定実験 • 全プレイアウト回数が10,000回の時点で推定 • その後10,000回プレイアウトを行い、実際の結果と推定を比較 • 初期局面に対して100回行い，推定失敗率の平均を求める • 1段目の手の推定について提示 – 将来報酬推定 – 残りプレイアウト回数推定 – 到達勝率推定 26 残りプレイアウト回数推定実験 700 350 result mean prediction result mean prediction 600 each move's playout of last 10,000 playouts each move's playout of last 10,000 playouts 300 250 200 150 100 500 400 300 200 100 50 0 0 40 60 80 100 120 140 160 180 200 220 240 0 50 each move's playout of first 10,000 playouts 100 150 200 250 300 350 each move's playout of first 10,000 playouts UCT-Tuned UCT アルゴリズム推定失敗率 UCT 11.7% UCT-Tuned 18.7% 青よりも上になっている点が推定を失敗したノード 27 将来報酬推定実験 0.7 0.6 result mean upper lower 0.5 mean of rewards of last 10,000 playouts mean of rewards of last 10,000 playouts 0.6 result mean upper lower 0.5 0.4 0.3 0.2 0.4 0.3 0.2 0.1 0.1 0 0 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.1 mean of rewards of first 10,000 playouts 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 mean of rewards of first 10,000 playouts UCT UCT-Tuned アルゴリズム上限より上下限より下合計推定失敗率 UCT 1.7% 21.6% 23.3% UCT-Tuned 2.6% 29.4% 32.0% 青：推定の上限紫：推定の下限下限より下になる割合が高い 28 到達勝率推定実験 0.6 0.6 result mean upper lower result mean upper lower 0.55 0.5 evaluated value of next 10,000 playouts evaluated value of next 10,000 playouts 0.5 0.45 0.4 0.35 0.3 0.25 0.4 0.3 0.2 0.1 0.2 0.15 0 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0 0.1 evaluated value of 10,000 playouts 0.2 0.3 0.4 0.5 0.6 evaluated value of 10,000 playouts UCT-Tuned UCT アルゴリズム上限より上下限より下推定失敗率 UCT 1.6% 6.7% 8.4% UCT-Tuned 3.5% 2.7% 6.2% 青：推定の上限紫：推定の下限上限より上になる割合が少ない方が枝刈りを失敗する可能性は低い 29 推定の失敗率 • 用いたパラメータによる失敗率が期待しているものより高い • 探索の前半と後半で得られる結果の質が変化することが原因 – 各ノードは前半はランダム、後半では勝ちそうな手を選びやすい 30 枝刈り実験 • 枝刈りに関する実験 – 枝刈りされた枝の割合 – プレイアウト回数の割合 • 枝刈りの影響に関する実験 – 真の最善手の評価順位の変化 • ランダムに作成した5手目の100局面 • 真の最善手は100,000回のプレイアウトを行うFuego を用いて判断 • 1段目の手に関して提示 31 1 1 0.9 0.9 0.8 0.8 0.7 0.7 0.6 0.6 pruning rate pruning rate 枝刈りされた枝の割合 0.5 0.5 0.4 0.4 0.3 0.3 0.2 0.2 0.1 0.1 0 0 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 0 2000 4000 6000 number of playouts UCT 8000 10000 12000 14000 16000 18000 20000 number of playouts UCT-Tuned •枝刈りされた枝の割合が下がることがあるのは、枝刈り条件の緩和による枝の復活のため •残りプレイアウト回数が減ると、枝刈りされた枝が増加 32 プレイアウト回数の割合 0.18 UCT UCT-Tuned UCT+proposal UCT-Tuned+proposal 0.16 アルゴリズム選択された手のプレイアウト回数の割合 UCT 4.5% UCT+提案手法 10.9% UCT-Tuned 11.6% UCT-Tuned+提案手法 17.7% 0.14 playout rate 0.12 0.1 0.08 0.06 0.04 0.02 0 0 10 20 30 40 50 60 70 80 rank •提案手法を組み込むことで、選択された手のプレイアウト回数は増加 •評価順位が上位のプレイアウト回数も増加 •強い手に対する枝刈りが発生していなければ、性能向上が期待できる 33 最善手の評価順位 1 UCT UCT-Tuned UCT+proposal UCT-Tuned+proposal 0.9 アルゴリズム平均順位一致率 0.8 rate 0.7 0.6 0.5 0.4 0.3 UCT 6.13 25% UCT+提案手法 9.64 37% UCT-Tuned 10.06 33% UCT-Tuned+提案手法 14.99 39% 0.2 0 10 20 30 40 50 60 70 80 rank •最善手に対する枝刈りは発生している •最善手を選択する割合は上昇 34 枝刈りによる影響 • 枝刈りによって最善手を非常に悪い手と判断してしまうこともある – 行ってはいけない枝刈りの発生 • 最善手を選択する割合は増加 • 枝刈りによって、選択された手や評価順位が上位の手に関しての枝刈り回数は増加 – 最善手を枝刈りされたとしても、枝刈りされていない手の中から、最も良い手を選択する可能性は向上 35 対戦実験 • 提案手法適用前と後との対戦結果 – プレイアウト回数固定 – 探索時間固定 • 同一の相手に対する対戦結果 • 黒白50戦ずつの計100戦 – 有意水準5%の二項検定で有意に勝ち越したと判断された合計の勝ち数には*マーク 36 プレイアウト回数固定での対戦結果先手 45 後手 5 39 * 計 84 0% 20% 勝ち 11 40% 負け 16 60% 80% 提案手法適用後の適用前に対する勝ち数 100% UCT 1手20,000プレイアウト先手 35 後手 15 33 * 計 68 0% 20% 勝ち 17 負け 32 40% 60% 80% 100% UCT-Tuned UCT,UCT-Tuned共に有意に勝ち越した 37 探索時間固定での対戦結果先手 44 後手 6 39 勝ち 11 負け計 83 0% 20% * 40% 17 60% 80% 提案手法適用後の適用前に対する勝ち数 100% UCT 1手2秒先手 34 後手 16 27 計 61 0% 20% 勝ち 23 * 負け 39 40% 60% 80% 100% UCT-Tuned UCT,UCT-Tuned共に有意に勝ち越した 38 同一相手に対する対戦結果 UCT 84* 16 UCT+提案手法 45 55 勝ち UCT-Tuned 56 0% 20% 負け 44 61* UCT-Tuned+提案手法 GnuGo level10に対する各種アルゴリズムの勝ち数 39 40% 60% 80% 100% 1手20,000プレイアウト提案手法を用いることで勝率は上昇 UCT :有意に負け→有意な差無し UCT-Tuned：有意な差無し→有意に勝ち 39 まとめ • UCTを投入計算量の有限性から枝刈り – 残りプレイアウト回数から探索終了時の状態を推定 – ゲームの知識や性質に依存しない • 最善手に対して枝刈りを行う可能性はあるが、結果的には最善手を選択する可能性は上昇 – 推定の失敗は探索の前半と後半で得られる結果の質に違いがあるのが原因 • 提案手法を組み込むことでゲーム木探索の性能強化に成功 – UCTでは勝率8割以上、UCT-Tunedでは勝率6割以上 • 投入できる計算量を意識することでアルゴリズムの性能強化は可能であることを示すことができた 40 今後の課題 • 推定の改善 – 推定失敗率が期待されるものよりも高い • 探索の前半と後半で得られる報酬の質が違うため – 近いプレイアウトによるものを重視させる推定手法 • ゲーム木探索以外への応用 – 残り計算量を意識したアルゴリズム改善手法はゲーム木探索に限ったものではない 41 発表文献 • 査読付会議論文 – 北川竜平，三輪誠，近山隆．麻雀の牌譜からの打ち手評価関数の学習. 第12回ゲームプログラミングワークショップ2007. pp.76--83,2007 – 北川竜平，栗田哲平，近山隆．投入計算量の有限性に基づくUCT探索の枝刈り. 第13回ゲームプログラミングワークショップ2008. pp.46--53,2008 • 研究奨励賞受賞 42