あるルーティングゲームの 最適戦略について

Presentation on theme: "あるルーティングゲームの 最適戦略について"— Presentation transcript:

1 あるルーティングゲームの 最適戦略について
瀧本　英二　　内沢　啓 東北大学大学院情報科学研究科

2 情報処理学会東北支部 設立３０周年記念 プログラミングコンテスト みちのく 達人 秋の陣

3 りんごキャッチ競争 A B

4 ルール りんごデータ：(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,・・・ 34,s,s,s,s,s,r,r,r,r,l,l,l,s,・・・ 初期x座標 s: その場にとどまる r: 右へ移動 l: 左へ移動

5 DAGによる表現 GA=(V,EA)：プレイヤーAからみたりんごグラフ (i,j) 2 EA , りんご i を取った後りんご jを
取る可能性がある Ａの地面に落下する時刻 プレイヤーAの戦略 = GAにおけるパス X （実際にはこれの推移的閉包）

6 りんごグラフの例 GA=(V,EA) A B ※ すべてのりんごの落下開始時刻を同じと仮定

7 Ｂのりんごグラフ GB=(V,EB) A B ※ すべてのりんごの落下開始時刻を同じと仮定

8 陣地について Aのパス Bのパス A B ※ すべてのりんごの落下開始時刻を同じと仮定

9 陣地について Aのパス Aの陣地 Bの陣地 Bのパス A B ※ すべてのりんごの落下開始時刻を同じと仮定

10 零和行列ゲームによる定式化 プレイヤーA GA上のパスP <GA,GB> プレイヤーB GB上のパスQ Aからみた損失行列
M(P,Q) = Bの取ったりんごの数 – Aの取ったりんごの数 P1 Q1 P2 P3 Q2 Q3 …… ＋１ ＋２ ＋４ －２ －１ －３

11 ミニマックス戦略 Aの混合戦略 = GAのパス上の分布 W Q1 Q2 Q3 …… W1 P1 W2 P2 …… W3 P3 …… ……
＋１ ＋２ ＋４ W2 P2 ＋１ －２ －１ …… W3 P3 ＋２ ＋１ －３ …… …… …… Aの最適戦略 W*

12 Hedge Algorithm による解法[Freund,Schapire]
t = 1, 2, ..., T 仮想プレイヤーA 仮想プレイヤーB 混合戦略 Wt Qt = argmaxQ P Wt(P) M(P,Q) 戦略の更新 t 2 [0,1] 定理

13 問題点 重み Wt の更新に O(パスの個数) 時間必要 一般にパスの個数は指数的に大きい そもそも最適戦略 W* の表現の長さが指数的？

14 問題解決のアイデア P 辺上に遷移確率 vt を保持し，次の関係式によって パス上の分布 Wt を間接的に表現
0.5 1.0 0.3 P 0.5 sink 0.8 source 0.2 0.7 1.0 1.0 Wt(P) = ランダムウォークが 　　　　　　　　パスP をたどる確率

15 Wt の重み更新の模倣 条件： （更新前） （更新後） を満たすような辺上の重み更新 が求められる

16 定理[Takimoto, Warmuth] 損失行列 M が のように表せるとき，Wt の重み更新を vt を用いて
模倣できる．さらに，vt ! vt+1の更新は多項式時間 計算可能

17 りんごキャッチ競争の場合 Bの陣地 BのパスQが選んだりんご sink Aの陣地 m(Q) = の数 = 4
Aの陣地 m(Q) = の数 = 4 l(e,Q) = 0 Bの陣地の 　　　　　-2 Aの陣地の 　　　　　-1 -1 -1 -2 -1 -1 -2 source

18 Wt の重み更新の模倣 条件 より とおくと， = 任意のPに対しこれが成立するような vt+1 を求める

19 Path Kernels O(|P|) 時間？ Path Kernel 辺の重みベクトル: v = (v(e1), ..., v(em))
パスの重みベクトル: W = (W(P1), ..., W(PN)), ただし， この関係を，w = (v) と表す． 係数ベクトル : b = (b(e1), ..., b(em)) Path Kernel O(|P|) 時間？ normalization factor

20 Path Kernel の計算 sink u source

21 Path Kernel の計算 O(|E|) 時間！ u sink source

22 Weight Pushing Algorithm
目標 u sink source

23 目標を達成しているか確認 P = { (u0=source, u1) , (u1, u2) …, (uk-1, uk=sink) } に対し， OK!

24 今後の課題 何か応用は？ Adaptive な場合？