あるルーティングゲームの最適戦略について瀧本英二内沢啓東北大学大学院情報科学研究科情報処理学会東北支部設立３０周年記念プログラミングコンテストりんごキャッチ競争 A B ルールりんごデータ：(x1,y1,t1), ..., (xn,yn,tn) (xi,yi) = i番目のりんごの座標 ti = i番目のりんごの落下開始時刻プレイヤーＢプレイヤーＡ 7,s,s,s,r,r,r,s,s,s,l,l,l,s,s,・・・初期x座標 34,s,s,s,s,s,r,r,r,r,l,l,l,s,・・・ s: その場にとどまる r: 右へ移動 l: 左へ移動 DAGによる表現 GA=(V,EA)：プレイヤーAからみたりんごグラフ (i,j) 2 EA , りんご i を取った後りんご jを取る可能性があるＡの地面に落下する時刻プレイヤーAの戦略 = GAにおけるパス X （実際にはこれの推移的閉包）りんごグラフの例 GA=(V,EA) A B ※ すべてのりんごの落下開始時刻を同じと仮定Ｂのりんごグラフ GB=(V,EB) A B ※ すべてのりんごの落下開始時刻を同じと仮定陣地について Aのパス Bのパス A B ※ すべてのりんごの落下開始時刻を同じと仮定陣地について Aの陣地 Bの陣地 Aのパス Bのパス A B ※ すべてのりんごの落下開始時刻を同じと仮定零和行列ゲームによる定式化 <GA,GB> プレイヤーA GA上のパスP プレイヤーB GB上のパスQ Aからみた損失行列 M(P,Q) = Bの取ったりんごの数 – Aの取ったりんごの数 Q1 Q2 Q3 P1 P2 ＋１＋２＋４＋１－２－１ P3 ＋２＋１－３ …… …… …… ミニマックス戦略 Aの混合戦略 = GAのパス上の分布 W Q1 Q2 Q3 W1 P1 W2 P2 ＋１＋２＋４＋１－２－１ W3 P3 ＋２＋１－３ …… Aの最適戦略 W* …… …… Hedge Algorithm による解法 [Freund,Schapire] t = 1, 2, ..., T 仮想プレイヤーA 混合戦略 Wt 仮想プレイヤーB Qt = argmaxQ P Wt(P) M(P,Q) 戦略の更新定理 t 2 [0,1] 問題点  重み Wt の更新に O(パスの個数) 時間必要  一般にパスの個数は指数的に大きい  そもそも最適戦略 W* の表現の長さが指数的？問題解決のアイデア辺上に遷移確率 vt を保持し，次の関係式によってパス上の分布 Wt を間接的に表現 0.5 1.0 0.3 0.5 source 0.2 0.7 sink 0.8 P 1.0 1.0 Wt(P) = ランダムウォークがパスP をたどる確率 Wt の重み更新の模倣条件：（更新前）（更新後）を満たすような辺上の重み更新が求められる定理[Takimoto, Warmuth] 損失行列 M がのように表せるとき，Wt の重み更新を vt を用いて模倣できる．さらに，vt ! vt+1の更新は多項式時間計算可能りんごキャッチ競争の場合 Bの陣地 BのパスQが選んだりんご sink 0 0 Aの陣地 -1 0 m(Q) = l(e,Q) = 0 Bの陣地の -2 Aの陣地の -1 0 0 -1 -2 -1 0 -1 source -2 の数 = 4 Wt の重み更新の模倣より条件 = とおくと，任意のPに対しこれが成立するような vt+1 を求める Path Kernels 辺の重みベクトル: v = (v(e1), ..., v(em)) パスの重みベクトル: W = (W(P1), ..., W(PN)), ただし，この関係を，w = (v) と表す．係数ベクトル : b = (b(e1), ..., b(em)) Path Kernel O(|P|) 時間？ normalization factor Path Kernel の計算 sink source u Path Kernel の計算 O(|E|) 時間！ u sink source Weight Pushing Algorithm 目標 u sink source 目標を達成しているか確認 P = { (u0=source, u1) , (u1, u2) …, (uk-1, uk=sink) } に対し， OK! 今後の課題 • 何か応用は？ • Adaptive な場合？