情報・システム工学概論 2015-06-01 コンピュータゲームプレイヤ 鶴岡 慶雅 工学部 電子情報工学科 工学系研究科 電気系工学専攻 概要 • コンピュータ将棋と機械学習 – ゲームと人工知能 – ミニマックス探索、αβ枝刈り – 評価関数 • 囲碁、ポーカー、麻雀、他のゲーム – モンテカルロ木探索 – 不完全情報ゲーム – ナッシュ均衡 将棋の自動解説 • 局面を自然言語で解説 次は▲３七銀として ４六銀３七桂型を目指す 矢倉模様 • 局面を解説する文章の生成モデルを作 成する 亀甲,浦,三輪, 鶴岡, 森, 近山. 将棋解説の自動生成のための局面からの特徴語生成, GPW2013, pp.36-43 3 将棋の解説 実際の解説文 ここはひとつの作戦の岐路。▲ ７八金ならよく指されている定型 だが、▲６七金と上がれば早囲 いを含みにした藤井矢倉になる 可能性もある。 今シリーズは後手番の勝利が 多く、急戦矢倉が改めて注目さ れている。先手番は淡々と進め、 後手番がなにかと工夫するのが ここしばらくの将棋界の流れだが、 そういった流れも変わってくるか もしれない。 言語のモデル化 • テキストデータ（コーパス） 「坊っちゃん」（夏目漱石） 親譲りの無鉄砲で小供の時から損ばかりしている。小学校に居る時 分学校の二階から飛び降りて一週間ほど腰を抜かした事がある。なぜ そんな無闇をしたと聞く人があるかも知れぬ。別段深い理由でもない 。新築の二階から首を出していたら、同級生の一人が冗談に、いくら 威張っても、そこから飛び降りる事は出来まい。弱虫やーい。と囃し たからである。小使に負ぶさって帰って来た時、おやじが大きな眼を して二階ぐらいから飛び降りて腰を抜かす奴があるかと云ったから、 この次は抜かさずに飛んで見せますと答えた。 ： 単語の出現頻度 • 単語に区切る 親譲りの無鉄砲で小供の時から損ばかりしている。 親譲り の 無鉄砲 で 小供 の 時 から 損 ばかり し て いる。 • 「坊っちゃん」 – 単語数： 57,886 Unigramモデル • 個々の単語の出現確率を計算すると P(親譲り) = 0.0000518 P(の) = 0.0036451 P(無鉄砲) = 0.0000691 P(で) = 0.0155824 ： • この確率分布に従って単語を選択して並べて みる Unigramモデル • 自動生成された文書 山嵐 、 やろ いや 小梅 二 も 便利 が き ん たら だ 切り下げ 船 さえ たぎり 。 なる の た 。 あいにく 。 、 。 て 追っかける を だ 山嵐 前 ある もん だ 日 見送り が 月給 だ 辺 、 勢 が ない 薬 マドンナ から 習慣 だ て に 「 床 ない から の か から た 歳 落っこちる 字 が へ 、 法 だ あなた まで の は 気に入ら 灯 ませ が 少し 女 ない すると 。 は 生意気 シャツ 人 を 掃 ない お 折合 上 ―― 加減 は 親 、 精出し こんな 膨れ もの を 布令 立たし 。 温泉 よく は 云う が あ と 出来 を に が 勘太郎 そこ に 野郎 て 。 そう について ぴたり 返り こ んな 、 ここ 、 が た 急 た 。 独り 。 赤 。 下げ し くば で だ に た 尾 なんか 婆さん とも 英語 渡し て 。 だ し から を か むずかしい おれ 来 る で 。 小日向 を 話 。 のっ で 評判 し の ざぶざぶと ら に 。 、 ま む ずかしい ない 出 使え 来 嫌い て まで まし と 顛末 はいっ 笑う 方 ん の 方 瘠せ 本当 具合 当人 酔わ ところ 騒ぎ 大勢 「 何 。 シャツ ええ し 清 た ん を 円 と 人 を し ん を ながら だ 給 が これ 得 て 答え 持っ 半ば Bigramモデル • 条件付き確率 n(w−1w) P(w w−1 ) ≈ n(w−1 ) 単語列 w-1 w の出現回数 単語 w-1 の出現回数 直前の単語が w-1 のときに単語 w が出現する確率 例） P(は|おれ) = 0.361 P(の|おれ) = 0.259 P(が|おれ) = 0.097 P(も|おれ) = 0.057 ： Bigramモデル • 自動生成された文書 「 山嵐 は 白 とか 、 森 の 方 が 出来る もの か ホホホホ と なかなか 込み入っ て しまっ て 、 山城 屋 の なる 。 とおれ と 思っ たら 、 それ は まし た んで 、 智慧 が 起き上がる や 否 や 、 おや 今晩 は 人中 じゃ が 、 なるべく 倹約 し て いる 。 次 に か ぎら れ ちゃ 、 誰 が 山嵐 と 同じ だから 清 が 豪い の 渾名 を 殺さ な くっ て さ に さえ 卸しゃ 、 お 困り じゃ ない 、 うし ろ い ます と 同 説 は 教頭 ひとり で ない って 怖く は 君子 な 顔 を 食っ た 。 「 おい て 、 狸 が 、 次第に 大きく し た か 髪結床 の 精神 的 娯楽 が 、 どん な 所 を 切っ て 一 時間 ばかり じゃ が 曲っ てる か と 云っ たら 例 の 余興 は たしかに 三 人 が 聞く から 、 すぐ 野 だ と 、 向う 合せ の お 婆さん に うずくまっ て おくれ た の 流れ は この 十 四 時間 目 に 気 が 自分 が ない 事 は こいつ あ 驚い た 奴 は 一 枚 ついてる が 芸者 は 屋 台 が 寄っ たり 、 そんなに あなた は 実に 自分 に なら なく て くれる 。 N-gramモデル • 条件付き確率の条件部を詳細にしていくと、 unigram モデル bigram モデル trigram モデル n-gram モデル P (w ) P(w w−1 ) P(w w− 2 w−1 ) ( : P w w−(n −1)...w−1 ) Trigramモデル • 自動生成された文書 山嵐 は 頑として 黙っ てる 。 こんな 所 に 我慢 が 出来る くらい な ら 、 ゆっくり 云っ て いる 。 しかし 野 だ が 、 しかし ぺらぺら 出る ぜ 。 ことに 赤 シャツ と いっしょ じゃ つまらない 。 清 は こんな 条理 に 適わ ない 議論 を 吐い て 、 急 に わっ と 云う の は 、 自分 だけ 悪 るい 事 だ 。 山嵐 は 校長 に は 下宿 とか 、 不徳 だ とか 云っ て 応じ なかっ た と 飛び上がっ た の じゃ が な もし 」 「 勝手 に お茶 を 入れ ましょ う と 発議 し た って 江戸 っ子 か 、 ッ タ を 入れ て 、 もう 大丈夫 だろ う 、 と 出来 そう だ 僕 は 実に 災難 だ と 手 を ざぶざぶと 洗っ て 、 その 地 の 淑女 に し て おい て 、 奥 から 五 円 六 十 人 の 周旋 で ある 。 それ じゃ 可哀想 で 不仕合せ な ん だ 」 と ぽかぽか なぐる 。 おれ の 懐中 を あて に なら なけれ ば な ら ない 。 こんな 土地 に 住ん でる か 分ら ない 、 餌 が なくなっ て た 懸 物 や 骨董 を 売りつけ て 、 面倒臭い から 、 下等 の 車 室 へ 乗り込 ん だ 。 おれ が 云っ たら 、 山嵐 と 名 を 使う もん だ 。 ことに よる 4-gramモデル • 自動生成された文書 親譲り 午後 は 、 先夜 おれ に対して 無礼 を 働い た 寄宿 生 の 処分 法 について の 会議 だ 。 会議 という もの は 、 あまり 岸 じゃ いけ な い です と 赤 シャツ が 忍ん で 来れ ば どうせ 夜 だ 。 しかも 宵の口 は 生徒 や その他 の 目 が ある から 、 急 に 手 が 自由 に なっ た 。 向う は 二つ ばかり 年上 で ある 。 資格 から 云う と たしかに 馬鹿 に 出来 ない 。 そのうち 評判 の 高知 の 何とか 踴 り を やる ん だ そう だ 。 傍 で 見 て いる 。 爺さん なんて 物覚え の わるい もの だ 。 これ で 海 だ と は 受け取り にくい ほど 平 だ 。 赤 シャツ が 思い出し た よう に うら なり 君 と は どう 云う 宿世 の 因縁 かしら ない が 、 人気 の ある と ない と は 様子 でも 知れる 。 長く 東 から 西 へ 貫い た 廊下 に は 鼠 一 匹 も 居 ない 事 が ある 。 それ から 優しい 事 も 赤 シャツ だ か ら 人 を 馬鹿 に し て 行く 手 を 塞い だ 。 おれ は 不意 を 打た れ て 握っ た 、 肩 を 抑え て 二 三 度 勧め た の だ が 、 思い切り は すこぶ る いい 人間 で ある 。 ところが 清 に も 別段 の 考え も なかっ た 。 将棋の自動解説 • 対数線形言語モデル 特徴量の重み exp ∑ λi f (w, w−1 , φ ) i P(w w−1 , φ ) = exp ∑ λi f (w, w−1 , φ ) ∑ w∈V i 解説したい局面 • 学習 – 局面と解説文からなるデータをもとに重みパラ メータを最適化（準ニュートン法など） 解説付き棋譜 予測モデル 先手の５筋位取り中飛車に なりそうだ。 15 解説付き棋譜 予測モデル 歩越し銀１枚だけでは攻めに ならない。急所の筋を交換し て攻め筋を広げる。 16 生成された解説文の例 矢倉模様の出だし。 亀甲博貴, 三輪誠, 鶴岡慶雅, 森信介, 近山隆. ロジスティック回帰による言語モデルを用いた将棋解説文の自動生成, 言語処理 17 学会第20回年次大会 (NLP2014), 札幌, 2014年3月 生成された解説文の例 ここから穴熊となる。 亀甲博貴, 三輪誠, 鶴岡慶雅, 森信介, 近山隆. ロジスティック回帰による言語モデルを用いた将棋解説文の自動生成, 言語処理 18 学会第20回年次大会 (NLP2014), 札幌, 2014年3月 生成された解説文の例 ▲６六銀と銀を上がってい こうということだろう 亀甲博貴, 森信介, 鶴岡慶雅. 将棋解説文のグラウンディングのための指し手表現と局面状態の対応付け, 第19回ゲームプログ 19 ラミングワークショップ, pp.202-209, 2014 生成された解説文の例 △３四歩は横歩とりになり、 横歩とりになっている 亀甲博貴, 森信介, 鶴岡慶雅. 将棋解説文のグラウンディングのための指し手表現と局面状態の対応付け, 第19回ゲームプログ 20 ラミングワークショップ, pp.202-209, 2014 コンピュータポーカー Texas Hold’em • Texas Hold’em – 最も人気のあるポーカーのひとつ ゲーム理論超入門 • 利得表・戦略・ゼロサム プレイヤBの戦略 じゃんけんゲーム プレイヤ Aの戦略 グー チョキ パー グー 0 +1 -1 チョキ -1 0 +1 パー +1 -1 0 • 純粋戦略（pure strategy） – ある戦略を確定的に選ぶ • 混合戦略（mixed strategy） – 戦略を確率的に選ぶ – 例 ［グー（0.5） チョキ（0.3） パー（0.2）］ ナッシュ均衡 じゃんけんゲーム プレイヤ Aの戦略 プレイヤBの戦略 グー チョキ パー グー 0 +1 -1 チョキ -1 0 +1 パー +1 -1 0 • ナッシュ均衡（Nash equilibrium） – どのプレイヤも自分（だけ）が戦略を変更することによって得を することがない状態 – 戦略の組が互いに最適応答になっている • じゃんけんゲーム – ナッシュ均衡は純粋戦略では存在しない – 混合戦略 ［グー（1/3） チョキ（1/3） パー（1/3）］ 問題 • グー、チョキ、パーで利得が違う場合 – グーで勝ったら３点 – チョキで勝ったら２点 – パーで勝ったら１点 • ナッシュ均衡戦略は？ ① グーの確率＞チョキの確率＞パーの確率 ② パーの確率＞チョキの確率＞グーの確率 ③ それ以外 答え ③ グー（1/3） チョキ（1/6） パー（1/2） One-card Poker • 極限まで単純化されたポーカー – １対１ – カードは１枚 – 強いカードを持っている方が勝ち • ラウンド – 最低掛け金は $1 – プレイヤ A の手番 • Bet $0 or $1 – プレイヤ B の手番 • Call, Raise or Fold – (プレイヤ B が Raise した場合のみ）プレイヤ A の手番 • Call or Fold http://www.cs.cmu.edu/~ggordon/poker/ プレイヤAのナッシュ均衡戦略 1st round 2nd round カード Bet する確率 カード Bet する確率 2 0.454 2 0.000 3 0.443 3 0.000 4 0.254 4 0.169 5 0.000 5 0.269 6 0.000 6 0.429 7 0.000 7 0.610 8 0.000 8 0.760 9 0.422 9 1.000 10 0.549 10 1.000 J 0.598 J 1.000 Q 0.615 Q 1.000 K 0.628 K 1.000 A 0.641 A 1.000 http://www.cs.cmu.edu/~ggordon/poker/ プレイヤBのナッシュ均衡戦略 Bet 0$ に対して Bet 1$ に対して カード Bet する確率 カード Bet する確率 2 1.000 2 0.000 3 1.000 3 0.000 4 0.000 4 0.000 5 0.000 5 0.251 6 0.000 6 0.408 7 0.000 7 0.583 8 0.000 8 0.759 9 1.000 9 1.000 10 1.000 10 1.000 J 1.000 J 1.000 Q 1.000 Q 1.000 K 1.000 K 1.000 A 1.000 A 1.000 http://www.cs.cmu.edu/~ggordon/poker/ ナッシュ均衡 • ポーカーの場合 – Rhode Island Hold’em • カード３枚のポーカー • 9億行 x 9億列 ⇒ 抽象化 100万行 x 100万列 – Texas Hold’em • 相当に粗い抽象化をしないと解けない 展開形による表現 • 展開形（extensive-form） A グー 情報集合 （information set） グー Bの利得 0 B チョキ パー -3 チョキ +1 パー B グー +3 B チョキ パー 0 -2 グー チョキ -1 +2 パー 0 Counterfactual Regret Minimization (CFR) • Average overall regret ( ( ) ( )) T 1 t t * − RiT = max u σ , σ u σ ∑ i i −i i T σ i*∈Σi t =1 – Regret: 結果的に見てベストであった戦略との効用の 差 – Regret が 0 に近づく ⇒ 平均戦略によるナッシュ均衡 • 情報集合（information set）と overall regret – 個々の情報集合で独立に regret を最小化 – Regret matching によって各プレイヤの戦略を更新 Regret matching 例 • 階段じゃんけん（Bからみた効用） accumulated regret A グー 1/3 期待値 -2/3 グー 1/3 B 1/3 チョキ パー 1/3 1/3 グー 1/3 0 -3 +1 2/9 -7/9 5/9 B 1/3 グー 1 チョキ 0 パー 0 グー 2/3 チョキ -1/3 パー -1/3 パー 1/3 チョキ 1/3 次回の戦略 information set B チョキ 1/3 パー 1/3 +3 0 -2 -1 +2 0 8/9 -1/9 -7/9 -4/9 5/9 -1/9 グーの確率を100%にしなかったことによる後悔 グー チョキ 1/3 1/3 パー 1/3 ｖｓ世界チャンピオン • Heads-up Limit Texas hold’em – １対１ – 掛け金は離散的に上昇 • Polaris 2.0 – University of Alberta – CFR • 2008 Gaming Life Expo – 3 wins, 2 losses, 1 tie コンピュータ囲碁 コンピュータチェス・将棋・囲碁 FPGAで将棋プログラムを作ってみるブログ http://blog.livedoor.jp/yss_fpga/archives/53897129.html MCTS • モンテカルロ木探索（Monte Carlo Tree Search, MCTS） – AI 研究に大きな影響 • 囲碁で大成功 • 他のゲーム、プランニング、制御、最適化問題などへ の応用が進む – 特長 • ドメイン知識が不要 • 他の手法がうまくいかない難しい問題で成功 • 計算パワーの向上がそのまま性能の向上につながる コンピュータ囲碁 • コンピュータ囲碁 – 初段手前でしばらく停滞 – MCTS の登場（2006年ごろ） – 現在はアマ六段（？） – 難しさ • 合法手が多い • 評価関数の設計が難しい – – – – 地が確定するのは最後 石の生死の判定 離れた場所にある石の影響 etc モンテカルロ法 • 円の面積 原始モンテカルロ法 • 各合法手からランダ ムプレイ 勝率 2/3 – 評価関数不要 3/3 1/3 • 勝率の一番高い手を 選ぶ • ダメな手に対しも多く の試行を行うので効 率が悪い 1 0 1 1 1 1 0 0 1 多腕バンディット問題 • 多腕バンディット問題（multi-armed bandits） • どのスロットマシンにお金をつぎこむべきか？ – 儲かるマシンに集中したい（exploitation） – 儲かるマシンを見つけたい（exploration） UCB • Upper Confidence Bounds (UCBs) – 多腕バンディット問題の近似解法 – Regret が O(ln n) 2 ln n UCB1 = X j + nj 腕 j の平均報酬 利用（exploitation） 総試行回数 腕 j の試行回数 探索（exploration） UCB 例 • 各イテレーションで UCB 値が最も高い手 を選ぶ UCB 1.0 1.8 2.0 1.3 1.4 ∞ ∞ 2.0 2.1 1.8 1.7 ∞ ∞ 1.0 1.1 1.2 2 ln n UCB1 = X j + nj • 有望な手に関して多 くの試行 1 0 1 1 1 0 UCT • UCB の問題 – ２手目以降のプレイアウトに無駄が多い – 相手の悪手に期待するような手を選ぶ • UCT (UCB applied to Trees) – Kocsis & Szepesvari (ECML 2006) – UCB を各ノードで適用 – 勝率等を各ノードに保存した木を成長させる – MINMAX値に収束 MCTSの基本動作 • 各イテレーション 1. 2. 3. 4. Selection Expansion Simulation Backpropagation • UCT 値が最大の子 ノードを再帰的に選 択 2 ln n UCT = X j + 2C p nj simulation (playout) MCTSの改良（主に囲碁） • Tree policy – Progressive Widening • 各ノードで考慮する合法手を徐々に増やす – All Moves As First (AMAF) • プレイアウト中の手の統計情報を木にも反映 – Rapid Action Value Estimation (RAVE) • AMAF の重みの自動調整 Playouｔ policy の改善 • 棋譜データによる教師付き学習 – Log-linear model + 局所パターン等の特徴量 • Simulation balancing – Silver and Tessauro (ICML 2009) – プレイアウトによる期待値が教師値と等しくなるよ うに policy のパラメータを調整 まとめ • ゲーム AI アルゴリズム – コンピュータ将棋 • 評価関数の自動学習 • 自動解説 – コンピュータ囲碁 • Monte-Carlo Tree Search (MCTS) – コンピュータポーカー • ナッシュ均衡解の効率的な計算 – コンピュータ麻雀 • 機械学習による「一人麻雀」＋「降り」 References • • • • • • • • • • • Tesauro, Comparison training of chess evaluation functions, Machines that learn to play games, 2001 保木, 局面評価の学習を目指した探索結果の最適制御, GPW 2006 Coulom, Efficient Selectivity and Backup Operations in Monte-Carlo Tree Search, CG 2006 Kocsis & Szepesvari, Bandit based Monte-Carlo Planning, ECML 2006 Gelly et al., Modification of UCT with patterns in Monte-Carlo Go, TechReport, 2006 Coulom, Computing Elo Ratings of Move Patterns in the Game of Go, 2007 Zinkevich et al., Regret Minimization in Games with Incomplete Information, NIPS 2007 Silver and Tessauro, Monte-Carlo Simulation Balancing, ICML 2009 Rubin & Watson, Computer poker: A review, Artificial Intelligence, 2011 Tsuruoka, Miyao & Kazama, Learning with Lookahead: Can History-Based Models Rival Globally Optimized Models?, CoNLL 2011 Browne et al., A Survey of Monte Carlo Tree Search Methods, IEEE Trans. Comput. Intell. AI Games, 2012
© Copyright 2024 ExpyDoc
