ゲーム構成要素を組み合わせた特徴の最適化 Optimizing conjunctive features of game components 電気系工学専攻近山・田浦研 37-096511 矢野友貴 2011/02/14 背景と目的  コンピュータによる識別   問題のモデル化モデルの構築には問題に対する高度な知識が必要組み合わせ特徴を用いたシンプルな識別モデル組み合わせ特徴   ○知識に依らず，設計が容易 ×冗長性，組み合わせ爆発  1 高次の組み合わせ特徴の活用が困難 2011/02/14 背景と目的  コンピュータゲームプレイヤ  組み合わせ特徴を利用される問題の一つ   識別モデル基礎要素   評価関数ゲーム構成要素 (ex. 駒) 組み合わせ特徴の意味の評価が比較的容易計算資源による制約限定的な利用 2要素の組み合わせ特徴 2 2011/02/14 背景と目的  提案：組み合わせ特徴による評価関数の新しい構成法  本研究の目的  従来よりも高次の組み合わせ特徴の利用   2つのアプローチ    ゲーム構成要素間の関連性を用いた組み合わせの絞り込みハッシュによる組み合わせ特徴の圧縮将棋を対象  要素の種類が多く，高次組み合わせ特徴の利用が難しいゲーム  3 冗長性の緩和，組み合わせ爆発の回避現状では一部の3要素間しか用いられていない 2011/02/14 本研究の貢献  組み合わせ特徴の選別を行う新しい評価関数の提案  組み合わせ特徴の冗長性の緩和の実現  組み合わせ爆発の回避の実現 4 2011/02/14 目次  関連研究  提案手法  評価設定  実験  結論 5 2011/02/14 目次  関連研究  提案手法  評価設定  実験  結論 6 2011/02/14 評価関数と組み合わせ特徴  駒の2項関係による評価関数 [ T. Kaneko, et al., 2003 ]   既存の多くの評価要素駒の2項関係として表現可能 2駒間では十分に表現できない特徴も   ex) 駒によって遮られている長距離利き将棋プログラム「ボナンザ」 [ K. Hoki, 2006 ]  玉を含む3駒間の組み合わせ特徴による評価関数   将棋における新しいパラメタ調整法を提案   7 約1億個の特徴要素大規模な組み合わせ特徴の活用の実現第16回世界コンピュータ将棋選手権で優勝 2011/02/14 ハッシュ関数と次元圧縮 Random Feature Mixing [ K. Ganchev, et al., 2008 ]  特徴要素のハッシュ値    特徴要素のインデックス特徴数をハッシュサイズに固定特徴要素のインデックス変換の効率化特徴数を1/10に圧縮しても精度を維持することに成功精度の相対値  特徴数の相対値特徴数の相対値縦軸はオリジナルとの精度の相対値，グレー部分はオリジナルの精度の標準偏差 8 2011/02/14 有効パターンの選別  多項式カーネルの近似計算 [ T. Kudo, et al., 2003 ]  PrefixSpan [ J. Pei, et al. 2001] により組み合わせを絞り込み     PrefixSpanでの頻度を特徴の重みに拡張閾値以下の組み合わせ特徴を枝刈り全体で30-300倍の高速化を実現統計情報に基づく木カーネルの枝刈り [ J. Suzuki, et al. , 2005 ]  訓練データから部分木のカイ二乗値を算出   9 部分木を展開する際にカイ二乗値を閾値として枝刈り大きな部分木でも過学習せずに安定した精度を実現 2011/02/14 目次  関連研究  提案手法  評価設定  実験  結論 10 2011/02/14 アプローチ  盤面を駒や升で構成されたグラフと考える   ノードのラベル組み合わせ特徴  要素の情報グラフ上のパスパスの総数はとても多く，すべてを展開するのは困難パスに重要度を定義して枝刈り △4二角 0.2 ▲6三金 0.1 ▲5三 0.8 0.7 歩 0.3 0.4 △5四銀 11 2011/02/14 提案手法の評価関数減衰定数により長いパス (=高次組み合わせ特徴)の影響度を調整 f (w, s)   wii (s) where i ( s)  i  | p|1 pG ( s ),1| p| d , h ( p ) i , imp ( p ) threthold 重要度の高いパスのみを展開 12 d : パスの大きさの上限 p : グラフ中のパス h(p) : pのハッシュ値 λ : 減衰定数ハッシュ関数を用いることでパスのインデックスを計算 2011/02/14 パス展開と枝刈り各要素間 (エッジ) に結合度を定義    結合度：2要素のつながりの局面評価への有効度パスの重要度 = パス上のエッジの結合度の積  重要度が閾値以下のパスを枝刈り root 選択されたパス「▲5三歩 - ▲6三金」，「▲5三歩 - ▲6三金 - △5四銀」，・・・ 1.0 △4二角 0.2 ▲5三金歩 0.7 0.3 △5四銀 13 0.8 0.1 ▲6三 0.8 展開 0.8 0.4 ▲6三歩金 △5四金銀 0.2 cut △5四 △4二銀角・・・ cut 0.3 ▲6三 0.7 0.56 ▲5三 0.3 閾値 = 0.4 最大長さ = 3 0.16 2011/02/14 ハッシュ関数によるインデックス計算  パスのハッシュ値    パスのインデックス特徴を総数をハッシュサイズに抑え込む可変長のパスのインデックス計算の効率化 2種類のハッシュ   グラフのノードに乱数 (パスの経路を考慮しない) グラフのエッジに乱数 (パスの経路を考慮する) rand(A) rand(B) rand(C) A B C rand(A-B) 14 hash(A-B-C) = rand(A) ^ rand(B) ^ rand(C) OR = rand(A-B) ^ rand(B-C) rand(B-C) 2011/02/14 目次  関連研究  提案手法  評価設定  実験  結論 15 2011/02/14 評価環境  将棋プログラム「激指」を利用   第20回世界コンピュータ将棋選手権で優勝したプログラム激指の評価関数を変更することで実験   16 探索ルーチンには激指オリジナルを使用評価関数のパラメタを学習させて評価 2011/02/14 学習方法  「激指」の学習で用いられた手法を利用    ボナンザメソッド [ K. Hoki, 2006 ] Averaged Perceptron [ M. Collins, 2002 ] プロ棋士の30,000棋譜を用いて学習  17 パラメタの更新回数は3,346,647回 2011/02/14 評価関数  ベースとして単純な駒割を利用   駒割：各駒の価値 (ex. 盤面上の歩は1枚100点) 評価関数 = 駒割 + 各種手法    駒割は固定の値として扱う組み合わせ特徴の要素として持ち駒は用いない各種手法   18 提案手法：駒グラフ (koma)，利きグラフ (kiki) 比較手法：all-two，kkp-kpp，atkk 2011/02/14 駒グラフと利きグラフ駒グラフ (koma) • 駒を全対全で結んだグラフ • ハッシュの計算ノード基準 • エッジの結合度 – 棋譜からロジスティック回帰により推定 (後述) – 閾値を設けて枝刈りパスの長さの最大値は4に制限利きグラフ (kiki) • 駒と升を利き (含む間接利き) で結んだグラフ – パスの起点は駒に限定 • ハッシュの計算エッジ基準 • エッジの結合度 – 利きがある：1.0, 利きがない：0.0 19 2011/02/14 比較手法名前  all-two 2駒の全組み合わせ kkp-kpp 玉を含む3駒の全組み合わせ atkk 2駒の全組み合わせ玉を含む3駒の全組み合わせ 3駒間の関係を用いる手法ではハッシュを利用    特徴 kkp-kppとatkk ノードに乱数を振る比較手法に対しても減衰定数λを導入  20 2駒間：λ，3駒間：λ^2 2011/02/14 評価方法基準詳細一致率 (%) 予測した手と棋譜の手が一致した割合学習で用いなかった250棋譜を用いて測定不一致度各局面で評価を誤った指し手の平均数学習で用いなかった250棋譜を用いて測定勝率 (%) 各手法同士の対戦成績初手30手を固定，250局面を先手後手で計500試合 1手あたりの探索ノード数を50万ノードに制限 ※不一致度は以下の式を用いて計算 (M:棋譜の手以外の手の集合, s’:最善応手手順後の局面)  1 N 不一致度   T wT  (sj )  wT  (s1 ) N i 1 jM i 21  1 T ( x)  1  exp 3x / 100 2011/02/14 目次  関連研究  提案手法  評価設定  実験  結論 22 2011/02/14 実験  結合度の学習と評価  ハッシュサイズと精度  枝刈り閾値と精度  既存手法との比較 23 2011/02/14 結合度の学習と評価  目的    駒グラフで利用する結合度の導出得られた結合度の評価内容   結合度の学習と利用抽出パターンの評価   24 Bonanzaのパラメタとの比較具体的なパターン 2011/02/14 結合度の学習「エッジ = 2駒間の関係」として学習    学習用の30,000棋譜から訓練データを作成学習にはLIBLINEARを利用  具体的にはL2ロジスティック回帰 srt データのラベルをチェック y = +1 (if srt == 先手), -1 (if srt == 後手) 棋譜の手 s1 s2 ・・・ sn 訓練データ (x, y) ランダムに一つ手 (sj) を選択エッジの差分を計算 x = edges(s1) – edges(sj) 25 2011/02/14 結合度の学習  エッジ e の重み w_e を結合度 con(e) に変換 1 con(ei , j )  1  exp(wei , j ) 占有率 (%) 正例:con(e) (con(e) > 0.5) 負例:1.0 - con(e) (con(e) < 0.5) con(e) pos (%) neg (%) total 0.9 – 1.0 0.01 0.01 0.02 0.8 – 0.9 0.04 0.04 0.08 0.7 – 0.8 0.15 0.15 0.30 0.6 – 0.7 1.69 1.68 3.37 0.5 – 0.6 25.55 25.65 51.20 all 27.44 27.53 54.97 ※con(e)=0.5 (i.e. w=0) は含めていない結合度 26 2011/02/14 結合度の利用  ロジスティック回帰では正例の分類確率が得られる   得られた結合度をそのまま用いるのは不適切正例・負例で別々に重要度を計算 A 正例負例 0.8 0.8 B × 0.4 0.4 C × 0.7 0.7 (1.0 - 0.8) × (1.0 - 0.4) × (1.0 - 0.7) D = 0.224 = 0.036 どちらかが閾値を超えるかチェック 27 2011/02/14 ボナンザのパラメタとの比較  ボナンザのパターンに対する抽出率を評価  玉を含む3駒間のパターン   重みの絶対値の降順にパターンをソート   28 実験では持ち駒を含むパターンは除外各パターンの重要度を計算し，閾値を超えるかチェック閾値は0.4 2011/02/14 ボナンザのパラメタとの比較抽出率が右肩下がり抽出率 (%) 重要なパターンを重点的に展開重要なパターン 29 チェックしたパターンの順位 2011/02/14 具体的なパターン重要度が最も大きいパターン • 意味があるパターンとなっていない • 2駒間では意味のありそうなパターンも評価値が最も大きいパターン • 穴熊囲いのパターン提案手法では2駒の結合度から3駒以上の重要度を近似必ずしも「重要度が大きい＝意味のあるパターン」とは限らない 30 2011/02/14 ハッシュサイズと精度  目的  衝突率と性能劣化の関係の評価   将棋の評価関数でのハッシュの有効性の評価内容  駒グラフに対して6つのハッシュサイズを適用   ハッシュサイズ以外の条件は固定  31 2^16, 2^18, 2^20, 2^22, 2^24, 2^26 枝刈り閾値は0.4，減衰定数は0.8 2011/02/14 衝突率と精度衝突率 79.379% 衝突率 (%) 不一致度ハッシュサイズ衝突率80%以下では精度をある程度維持できている 32 2011/02/14 ハッシュサイズと強さ自＼相 2^16 2^16 2^18 36.0 2^20 2^22 2^26 28.2 27.6 25.2 22.0 42.6 44.2 38.6 41.8 46.6 45.6 49.2 47.4 49.6 2^18 64.0 2^20 71.8 57.4 2^22 72.4 55.8 53.4 2^24 74.8 61.4 54.4 52.6 2^26 78.0 58.2 50.8 50.4 衝突率が80%より大きかったハッシュサイズは有意に負け越す 2^24 49.2 50.8 衝突率が80%以下のハッシュサイズではほぼ互角以降の実験ではハッシュサイズは2^24を用いた 33 2011/02/14 枝刈り閾値と精度  目的   提案手法における減衰定数の最適値の推定枝刈り閾値と精度の関係の評価   将棋における高次組み合わせ特徴の評価内容  10種類の減衰定数を用いた精度比較    0.1から1.0まで0.1刻み利きグラフについても評価学習には近似データを用いる   6種類の閾値を比較  34 近似データ：あらかじめ激指で探索を行ったデータ 0.35, 0.4, 0.45, 0.5, 0.55, 0.6 2011/02/14 減衰定数の最適値推定不一致度手法減衰定数閾値が下がる減衰定数 kiki 0.8 0.35 0.7 0.4 0.8 0.45 1.0 0.5 1.0 0.55 1.0 0.6 1.0 減衰定数も小さくなる高次組み合わせ特徴の数が増えるから (kikiも高次組み合わせ特徴が多い) 35 2011/02/14 枝刈り閾値と精度閾値  有効特徴数一致率 (%) 不一致度 0.35 13,075,101 40.6234 4.39987 0.4 6,194,174 40.8342 4.38366 0.45 3,111,783 40.2368 4.39327 0.5 1,986,039 40.3001 4.37635 0.55 415,343 39.0773 5.09832 0.6 125,478 36.7722 5.93794 閾値0.5を境に精度に差がある   0.5までは精度の向上幅が非常に大きい 0.5以下では改善がとても鈍い  36 不一致度は改善してない 2011/02/14 枝刈り閾値と平均評価特徴数平均評価特徴数手法 2駒 3駒 4駒計 kiki 112 475 1,643 2,230 0.35 519 1,193 227 1,939 0.4 519 444 53 1,016 0.45 519 175 13 707 0.5 519 59 3 581 0.55 178 20 1 199 0.6 66 8 0 74 手法  0.5以下では2要素の組み合わせ特徴をすべて展開   2要素が評価にとても重要 3要素以上の利用による有意な精度向上は見られない   37 学習時間が不足している可能性提案手法でうまく活用できていない可能性も 2011/02/14 枝刈り閾値と強さ閾値が0.5以下では有意な差がほとんどない 0.4と0.5が相対的には良い結果に自＼相 0.35 0.35 0.4 43.0 0.45 0.5 0.55 0.6 50.6 47.2 59.4 77.6 53.6 46.4 64.6 74.0 44.2 71.0 81.6 70.0 77.2 0.4 57.0 0.45 49.4 46.4 0.5 52.8 53.6 55.8 0.55 40.6 35.4 29.0 30.0 0.6 22.4 26.0 18.4 22.8 71.0 29.0 閾値が0.5より大きい場合は有意に負け越す以降の実験では枝刈り閾値は0.4を用いた 38 2011/02/14 既存手法との比較  目的  提案手法と既存手法との精度の比較   提案手法の有効性の評価内容  提案手法と比較手法を学習    39 提案手法：koma, kiki 比較手法：all-two, kkp-kpp, atkk 減衰定数は事前に推定 2011/02/14 既存手法との精度比較手法  減衰定数速度 (nps) 有効特徴数一致率 (%) 不一致度 all-two 1.0 299,871 1,569,828 40.2193 4.51190 kkp-kpp 1.0 181,851 15,607,513 39.0773 4.69772 atkk 0.8 147,143 15,642,643 40.7674 4.38599 kiki 0.8 93,685 16,777,216 40.7428 4.55356 koma 0.8 114,871 6,194,174 40.8342 4.38366 atkk (既存) とkoma (提案) が特に良い結果に  精度：atkk = koma > 他の手法   冗長性が緩和されている速度：既存 > 提案  40 利きがない関係を把握できないことが影響特徴数：atkk > koma   kikiの精度が悪いグラフ生成、特徴選択の部分が重い実装の課題 2011/02/14 既存手法との強さ比較自＼相 all-two kkp-kpp all-two  59.6 atkk kiki koma 順位 44.6 70.6 50.4 3 34.4 54.2 36.2 4 72.0 51.8 1 34.8 5 kkp-kpp 40.4 atkk 55.4 65.6 kiki 29.4 45.8 28.0 koma 49.6 63.8 48.2 65.2 2 atkkが最も強い  komaはatkkと互角  41 既存手法と同程度の強さ一方で、komaはall_twoとの直接対決では互角の結果に 2011/02/14 目次  関連研究  提案手法  評価設定  実験  結論 42 2011/02/14 まとめ  要素間の関連性に着目した評価関数の提案  組み合わせ特徴の冗長性を緩和   組み合わせ爆発の回避    精度を維持しつつ特徴数を削減最大4駒間までの組み合わせ特徴を展開将棋の評価関数へのハッシュの有効性提案手法の概念は一般的なモデルに拡張可能 43 2011/02/14 今後の課題  実行速度の向上    結合度計算の改善    重複パターンの完全回避頻出パターンの事前計算による高速化局所特徴を利用した結合度高次パターンの重要度近似の補正さらなる拡張  44 空升など要素追加による表現力の向上 2011/02/14 ご清聴ありがとうございました 45 2011/02/14 発表文献  矢野友貴, 三輪誠, 横山大作, 近山隆. ゲーム構成要素を組み合わせた特徴の最適化. 第15回ゲームプログラミングワークショップ. pp 15--22, 2010  矢野友貴, 三輪誠, 横山大作, 近山隆. 既存評価関数のパラメタを活かした適応学習. 第14回ゲームプログラミングワークショップ. pp 1--8, 2009 2011/02/14