情報システム工学概論コンピュータゲームプレイヤ鶴岡慶雅工学部電子情報工学科情報理工学系研究科電子情報学専攻

Size: px

Start display at page:

Download "情報システム工学概論コンピュータゲームプレイヤ鶴岡慶雅工学部電子情報工学科情報理工学系研究科電子情報学専攻"

ふみなねごろ
4 years ago
Views:

1 情報システム工学概論コンピュータゲームプレイヤ鶴岡慶雅工学部電子情報工学科情報理工学系研究科電子情報学専攻

2 DEEP Q-NETWORK (DQN)

3 Deep Q-Network (Mnih et al., 2015) Atari 2600 Games ブロック崩しスペースインベーダーピンポン etc. 同一のプログラムですべてのゲームを学習 CNN+ 強化学習 (Q-Learning) 3

4 強化学習 (Reinforcement Learning, RL) 状態 s 報酬 r 行動 a エージェント環境 4

5 MDP マルコフ決定過程 (Markov decision Process) 状態集合 S 行動集合 A 状態遷移関数 P(s s,a) 状態 s において行動 a とった場合に状態 s に遷移する確率報酬関数 R(s,a,s ) 状態 s から行動 a によって状態 s に遷移したときに得られる報酬 5

6 強化学習エージェントの目的現在から未来にわたる累積報酬を最大化 Bellman 方程式 6 ( ) ( ) ( ) ( ) ( ) a s Q s a s R a s s P a s Q a s + =, max,,,, * * γ = = = k k t k t t t t r r r r g γ γ γ 状態 s で行動 a をとりその後最善の行動をとり続けた場合に得られる報酬の期待値

7 Q 学習 Q(s, a) を学習 Q(s, a): 状態 s で行動 a をとった場合に将来得られる報酬の総和の期待値 ( の予測値 ) 行動するたびに予測値を更新 ( ) ( a) Q( s, a) + α r + maxq( s, a) Q( s, a ) Q s t, t t+ 1 γ t+ 1 a t t 一歩先で得られるより正確な予測値現在の予測値 7

8 初期状態

9 初期状態 Up Down Left Right End

10 状態 7 と状態 10 を経験

11 状態 7 と状態 10 を経験した後 Up Down Left Right End

12 状態 3 を経由して状態 7 に到達

13 状態 3 を経由して状態 7 に到達 Up Down Left Right End

14 関数近似による Q 学習テーブルによる Q 学習の問題メモリ使用量が状態空間の大きさに比例汎化能力がない関数近似による Q 学習ニューラルネットワーク等でを実現最小化 L [( ) ] 2 ( θ ) E r + γ maxq( s, a ; θ ) Q( s a) i ( ) Q s, a;θ = i 1, a 14

15 Deep Q-Network CNN 全結合 NN (Mnih et al., 2015) 15

16 Reinforcement Learning with Unsupervised Auxiliary Tasks (Jaderberg et al., 2016)

17 コンピュータポーカー

18 Texas Hold em Texas Hold em 最も人気のあるポーカーのひとつ

19 ゲーム理論超入門利得表戦略ゼロサムじゃんけんゲームプレイヤ A の戦略純粋戦略 (pure strategy) ある戦略を確定的に選ぶプレイヤ B の戦略グーチョキパーグーチョキパー混合戦略 (mixed strategy) 戦略を確率的に選ぶ例 [ グー (0.5) チョキ (0.3) パー (0.2)]

20 ナッシュ均衡じゃんけんゲームプレイヤ A の戦略プレイヤ B の戦略グーチョキパーグーチョキパーナッシュ均衡 (Nash equilibrium) どのプレイヤも自分 ( だけ ) が戦略を変更することによって得をすることがない状態戦略の組が互いに最適応答になっているじゃんけんゲームナッシュ均衡は純粋戦略では存在しない混合戦略 [ グー (1/3) チョキ (1/3) パー (1/3)]

21 問題グーチョキパーで利得が違う場合グーで勝ったら 3 点チョキで勝ったら 2 点パーで勝ったら 1 点ナッシュ均衡戦略は? 1 グーの確率 > チョキの確率 > パーの確率 2 パーの確率 > チョキの確率 > グーの確率 3 それ以外答え 3 グー (1/3) チョキ (1/6) パー (1/2)

22 One-card Poker 極限まで単純化されたポーカー 1 対 1 カードは 1 枚強いカードを持っている方が勝ちラウンド最低掛け金は $1 プレイヤ A の手番 Bet $0 or $1 プレイヤ B の手番 Call, Raise or Fold ( プレイヤ B が Raise した場合のみ ) プレイヤ A の手番 Call or Fold

23 プレイヤ A のナッシュ均衡戦略 1 st round 2 nd round カード Bet する確率 J Q K A カード Bet する確率 J Q K A

24 プレイヤ B のナッシュ均衡戦略 Bet 0$ に対してカード Bet する確率 J Q K A Bet 1$ に対してカード Bet する確率 J Q K A

25 ナッシュ均衡ポーカーの場合 Rhode Island Hold em カード3 枚のポーカー 9 億行 x 9 億列抽象化 100 万行 x 100 万列 Texas Hold em 相当に粗い抽象化をしないと解けない

26 展開形による表現展開形 (extensive-form) A グーチョキパー情報集合 (information set) B B B グーチョキパーグーチョキパーグーチョキパー B の利得

27 Counterfactual Regret Minimization (CFR) Average overall regret T T 1 ( ( t ) ( t R ) i = max ui σ * i, σ i ui σ * T σ i Σ i t= 1 Regret: 結果的に見てベストであった戦略との効用の差 Regret が 0 に近づく平均戦略によるナッシュ均衡情報集合 (information set) と overall regret 個々の情報集合で独立に regret を最小化 Regret matching によって各プレイヤの戦略を更新

28 Regret matching 例階段じゃんけん (B からみた効用 ) グー 1/3 A チョキ 1/3 accumulated regret パー 1/3 グー 2/3 チョキ -1/3 パー -1/3 information set 次回の戦略グー 1 チョキ 0 パー 0 期待値 -2/3 B 1/3 B 1/3 B グー 1/3 チョキ 1/3 パー 1/3 グー 1/3 チョキ 1/3 パー 1/3 グー 1/3 チョキ 1/3 パー 1/ /9-7/9 5/9 8/9-1/9-7/9-4/9 5/9-1/9 グーの確率を 100% にしなかったことによる後悔

29 vs 世界チャンピオン Heads-up Limit Texas hold em 1 対 1 掛け金は離散的に上昇 Polaris 2.0 University of Alberta CFR 2008 Gaming Life Expo 3 wins, 2 losses, 1 tie

30 コンピュータ将棋

31 将棋 Japanese chess 持ち駒のルール ( 取った駒が再利用できる ) 将棋人口 (1 年に 1 回以上指した 15 歳以上の人の数 ):700 万人

32 コンピュータチェス将棋囲碁 FPGAで将棋プログラムを作ってみるブログ

33 コンピュータの思考法の原理現在の局面 2 1 手先の局面手先の局面評価関数によって末端局面の有利不利の度合いを数値化お互いが自分にとって最も都合の良い手を選ぶと仮定して逆算 ( ミニマックス探索 )

34 深さ優先探索現在の局面 2 1 手先の局面手先の局面関数の再帰呼び出しで簡単に実装できる省メモリ

35 枝刈り現在の局面 2 1 手先の局面手先の局面枝刈り! 枝刈り! 探索ノード数を大幅に減らせる現在局面で選択する手と評価値は変わらない

36 反復深化最大深さ1で探索最大深さ2で探索最大深さ3で探索最大深さ4で探索探索の最大深さを徐々に深くしていく時間がなるまで繰り返す

37 評価関数局面の有利 / 不利を数値化互角ならゼロ先手が有利ならプラス後手が有利ならマイナス重要な要素駒の損得駒の働き玉の危険度序盤の駒組み +320 点

戦略的行動と経済取引（ゲーム理論入門）

戦略的行動と経済取引（ゲーム理論入門）展開形表現戦略的行動と経済取引 ( ゲーム理論入門 ) 3. 展開形ゲームとサブゲーム完全均衡戦略形ゲーム : プレイヤー戦略利得から構成されるゲーム展開形ゲーム (extensive form game): 各プレイヤーの意思決定を時間の流れとともにゲームの木を用いて表現 1 2 展開形ゲームの構成要素プレイヤー (player) の集合ゲームの木 (tree) 枝 ( 選択肢

情報 システム工学概論 コンピュータゲームプレイヤ 鶴岡慶雅 工学部電子情報工学科 情報理工学系研究科電子情報学専攻

情報システム工学概論コンピュータゲームプレイヤ鶴岡慶雅工学部電子情報工学科情報理工学系研究科電子情報学専攻