人工知能概論 第4回 探索(3) ゲームの理論.

Slides:



Advertisements
Similar presentations
最上 亮.  近年標的型と呼ばれるサイバー攻撃が増え、大 企業や、政府機関が情報窃取型の標的型メール 攻撃の被害を受けている。  標的型メール攻撃による個人情報漏えいは、企 業に莫大な損失を与えるとともに、信頼を失う。  現在サイバー攻撃における攻撃者、防御者の戦 略をゲーム理論的にモデル化する研究がおこな.
Advertisements

Voronoi Game on Graph and its Complexity 寺本 幸生 上原 隆平 (JAIST)
Information このスライドは「イラ ストで学ぶ人工知能概 論」を講義で活用した り,勉強会で利用した りするために提供され ているスライドです.イラ ストで学ぶ人工知能概 論.
あみだくじ AMIDA-KUJI 井上 康博 Statistical analysis on Amida-kuji, Physica A 369(2006)
Information このスライドは「イラ ストで学ぶ人工知能概 論」を講義で活用した り,勉強会で利用した りするために提供され ているスライドです.イラ ストで学ぶ人工知能概 論.
ゲーム理論の誕生と発展 von Neumann & Morgenstern The Theory of Games and Economic Behavior.
 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
新ゲーム理論 第Ⅰ部 非協力ゲームの理論 第2章 戦略形ゲームのナッシュ均衡
2行+αチョンプに関する考察 京都大学 ○後藤順一 伊藤大雄.
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
ゲーム理論・ゲーム理論Ⅰ(第2回) 第2章 戦略形ゲームの基礎
人工知能概論 第4回 探索(3) ゲームの理論.
内容 部分ゲーム完全均衡点 -部分ゲーム -部分ゲーム完全均衡点 -2段階完全情報ゲーム シュタッケルベルク均衡点
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
ゲーム理論・ゲーム理論Ⅰ (第4回) 第3章 完全情報の展開形ゲーム
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
シミュレーション論Ⅰ 第13回 意思決定とシミュレーション.
ゲーム理論・ゲーム理論Ⅰ (第8回) 第5章 不完全競争市場の応用
© Yukiko Abe 2014 All rights reserved
上級価格理論II 第3回 2011年後期 中村さやか.
ゲーム理論・ゲーム理論Ⅰ (第6回) 第4章 戦略形ゲームの応用
新ゲーム理論ゼミ 第5章 「繰り返しゲーム」 M1 松村 草也.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
人 工 知 能 第3回 探索法 (教科書21ページ~30ページ)
アルゴリズムとデータ構造 2012年7月23日
初級ミクロ経済学 -ゲーム理論入門- 2014年12月19日 古川徹也 2014/12/19.
法と経済学(file 6) ゲーム理論2 今日の講義の目的 (1)展開型ゲームという考え方を理解する (2)後方帰納法の考え方を理解する
10.Private Strategies in Games with Imperfect Public Monitoring
政策決定のプロセス 政策過程論 公共選択 ゲームの理論.
ゲームプレイング (Game Playing)
ゲームプレイング (Game Playing)
ゲームプレイング (Game Playing)
初級ミクロ経済学 -ゲーム理論入門- 2014年12月15日 古川徹也 2014年12月15日 初級ミクロ経済学.
ゲーム理論・ゲーム理論Ⅰ(第3回) 第2章 戦略形ゲームの基礎
人工知能概論 第6章 確率とベイズ理論の基礎.
データ構造と アルゴリズム 知能情報学部 新田直也.
アルゴリズムとデータ構造 2011年7月14日
単位 おねだり ☆オセロ おねだり隊☆D班.
特殊講義(経済理論)B/初級ミクロ経済学
計算量理論輪講 岩間研究室 照山順一.
JAVAでつくるオセロ 伊東飛鳥、宮島雄一 長畑弘樹、ソギ原直人.
慶應義塾大学経済学部 グレーヴァ香子 Takako Fujiwara-Greve
新ゲーム理論 第Ⅰ部 非協力ゲームの理論 第1章 非協力ゲームの戦略形
シミュレーション論Ⅰ 第11回 意思決定とシミュレーション.
パソコンでゲームの理論 第1,2章 ゼロ和2人ゲーム ゼミ合宿 東京理科大学理学部第2部数学科・統計学ゼミ
第Ⅱ部 協力ゲームの理論 第9章 シャープレイ値.
シミュレーション論 Ⅱ 第14回 まとめ.
シミュレーション論 Ⅱ 第15回 まとめ.
データ解析 静岡大学工学部 安藤和敏
経済学とは 経済学は、経済活動を研究対象とする学問。 経済活動とは? 生産・取引・消費 等 なぜ、経済活動を行うのか?
人工知能概論 第2回 探索(1) 状態空間モデル,基本的な探索
第Ⅱ部 協力ゲームの理論 第10章 コア 2008/07/01(火) ゲーム理論合宿.
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
G班メンバー リーダー 橋本望 SE 北本理紗と服部友哉 PPT作成 橋本望と山田侑加
京都大学大学院情報学研究科 宮川博光 伊藤大雄
様々な情報源(4章).
モンテカルロ法を用いた 立体四目並べの対戦プログラム
Problem L: シャノワール 問題作成: 高橋 解法作成: 安達・高橋・前原 解説: 安達.
第Ⅱ部 協力ゲームの理論 第7章 提携形ゲームと配分 2008/07/01(火) ゲーム理論合宿 M1 藤井敬士.
近畿大学 理工学部 情報学科 情報論理工学部研究室 潘小月
第Ⅱ部 協力ゲームの理論 第14章 交渉集合.
数値解析Ⅱ ~五目並べのプログラミング~ C班.
or-8. ゲーム理論 (オペレーションズリサーチを Excel で実習するシリーズ)
囚人のジレンマ ―― 裏切りのインセンティブ ――
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
第Ⅰ部 非協力ゲームの理論 第6章 情報の価値 2008/07/01(火) ゲーム理論合宿 M2 渡辺美穂.
Othello G班         山崎 木下 山本 上手      .
情報論理工学 研究室 第8回: ミニマックス法.
情報数理Ⅱ 第10章 オートマトン 平成28年12月21日.
京都大学 情報学研究科 通信情報システム専攻 高田智史 joint work with 伊藤大雄 中村義作
Presentation transcript:

人工知能概論 第4回 探索(3) ゲームの理論

Information このスライドは「イラストで学ぶ人工知能概論」を講義で活用したり,勉強会で利用したりするために提供されているスライドです.

STORY 探索(3) ホイールダック2号は一つ誤解をしていた.迷路の中ではとにかくまっすぐゴールに向かえばよいわけではない.迷路にはホイールダック2号を邪魔しようとする敵がいる.これとぶつかると何かと面倒である.敵がどのように行動するのかを先読みしながら迷路を抜けなければならない.

仮定 探索(3) ホイールダック2号は自分と敵の行動に対する利得を知っている. 仮定 探索(3) ホイールダック2号は自分と敵の行動に対する利得を知っている. ホイールダック2号は自らの行動に対する結果を確実に予測できるものとする. 敵は合理的(rational, p.46)に行動する. ホイールダック2号も敵も物理的につながっている場所・状態には意図すれば確定的に移動することができるものとする.

Contents 4.1 利得と回避行動 4.2 標準型ゲーム 4.3 展開型ゲーム

4.1.1 はじめに ホイールダック2号はどうすべきか?

利得行列 プレイヤーが二人の場合には,各プレイヤーの行動を行列の行と列に書き,それぞれの交わるセルに,それぞれのプレイヤーが得る利得を書いたものを利得行列と呼ぶ. 一般の行列とは異なり,双行列(bimatrix)と呼ばれる. プレイヤー2 の行動 プレイヤー1 の行動 左がプレイヤー1,右がプレイヤー2の利得

4.1.2 ケース1: 敵はホイールダック2 号を捕まえたい ホイールダック2 号にとっては上に移動すると敵にぶつかってしまうが,まだ利得が−5 で済むため,上への移動を選ぶのが最適な選択となる. CW = −5, CE = 3,DW = DE = −2

4.1.3 ケース2: 少しだけ敵のモチベーションが下がったら? 敵は左へ行くことが最適 したがって、ホイールダック2 号は右に行く、つまり×印で−3 のダメージを受けるだけで,ゴールにたどり着ける. 少しの利得の違いでとるべき行動が変化する. CW = −5, CE = 3-1,DW = DE = −2-1 主体の意思決定が混ざり合って状況が決定する系をゲームと呼ぶ

Contents 4.1 利得と回避行動 4.2 標準型ゲーム 4.3 展開型ゲーム

4.2.1 はじめに/ 標準型ゲーム ゲーム理論 複数のプレイヤの意志決定を扱う理論 1944年ジョン・フォン・ノイマン,オスカー・モルゲンシュテルン 「ゲームの理論と経済行動」 基本的な用語の定義 プレイヤ 意志決定を行なう個々の主体.複数存在する. 行動 プレイヤの選択.戦略と呼ぶこともある.探索の作用素に相当. 利得 プレイヤの行動の組み合わせに対して定義される数値.結果に対する各プレイヤの効用を示す.大きいほうがより嬉しいとする. 合理的 各プレイヤは自分の利益を最大化しようと最大限の努力をする.利己的(selfish) と呼ぶこともあるが,ニュアンス的に誤解がある.英語ではrational. 均衡 合理的な意思決定の結果として,自ずと決まる全プレイヤーの行動の落ち着く先.

4.2.4 支配戦略均衡 相手の行動が何であろうが,その行動をとった方が高い利得を得られる行動を支配戦略 という. 支配戦略が存在すればゲームの状態は支配戦略均衡に至る(前提:合理性) エネルギー供給装置

4.2.5 ナッシュ均衡 ナッシュ均衡:行動の組(ホイールダック2 号の行動, 敵の行動) が互いに相手の行動に対する最適 どのプレイヤも自分だけ行動を変えても利得が増えない状況

「白状したらおまえだけは助けてやるぞ!」 4.2.6 囚人のジレンマ ナッシュ均衡は必ずしも全体として良い状態に至るわけではない. ・・・・・ ・・・・・ 「白状したらおまえだけは助けてやるぞ!」

4.2.7 ゼロサム・ゲーム ゼロサム・ゲームはプレイヤーの利得の総和が0 になるゲームであり,特にプレイヤーが2 名の場合はプレイヤー1 の利得をr とすると,プレイヤー2 の利得は-r となることになる. 双行列で書く必要がない

4.2.8 ミニマックス戦略 相手プレイヤーの利得を最小化(minimize)し,自らの利得を最大化(maximize)する戦略 ナッシュ均衡を実現する.

Contents 4.1 利得と回避行動 4.2 標準型ゲーム 4.3 展開型ゲーム

4.3.1 展開型ゲーム 実際のゲームは一度きりの意思決定ではなく,多段階の意思決定を含む.このようなゲームを展開型ゲームという. オセロやチェスなど多くのゲームは展開型ゲームでモデル化できる. ゲーム木で表現できる. 先手の手番 後手の手番 最終的に先手が得る利得

演習問題4-1 交互ジャンケン 順番にジャンケンを出すゲームをする.相手に勝つ手を出すと,自分にその指の本数分だけ得点になる.(負けた場合と引き分けの場合、得点は変化しない.) 自分がパーを出した状態を初期状態としてスタート。初期状態→相手→自分 の一往復で終了する際のゲーム木は以下のようになる. ゲーム木の葉ノードに評価値を記入せよ.ただし評価値は 評価値 = 自分の得点 – 相手の得点 とする.

4.3.3 ミニマックス法 「先手が最も低い利得になる」手を後手がとることを前提として,先手は自分にとり高い利得が得られる行動を選択する.

演習問題4-2 交互ジャンケン min-max法 このゲームに先手は勝つことができるか? このゲームにおける最後の先手の最良の手を述べよ. もし,最初の一手を先手が選ぶことが出来れば先手は勝つことが出来るか?

アルファ・ベータ法 pruning = 枝刈り ミニマックス法では盤面の局面を先読みすればするほど,良い手を選択し,ゲームを有利に進めていける. しかし,探索しすぎるとゲーム木の探索空間が膨大になる. ミニマックス法の性質を生かして,不必要な探索を避ける(サボる)ことができる. アルファ・ベータ法(αβ pruning) βカット(β pruning) 評価値最小化局面の枝刈り 後手がわざわざ評価値の大きな手を打たないことを利用して,先手の行動(作用)をカット αカット(α pruning) 評価値最大化局面の枝刈り 先手がわざわざ評価値の小さな手を打たないことを利用して,後手の行動(作用)をカット pruning = 枝刈り

βカット (β pruning)

αカット (α pruning)

演習問題4-3 交互ジャンケン αβカット 4-2 で考えた,交互ジャンケンについてαカット,もしくはβカットをする所はあるか?あるとすれば何処で生じるか?答えよ.

演習4-4 現実のゲーム オセロはゲーム木で表現される種類のゲームである. オセロのゲーム木を表現し,勝利のための必勝法を計算したい. 初手黒が置き,その後,交互に置いていく事を考えると,オセロの状態空間の大きさ(葉ノードの数)はどれくらいになるか?概算を求めよ. 盤面は 8×8 である. 近似として一回に置ける手は平均して5箇所程度であるとしてよい.

第4章のまとめ プレイヤー,利得行列や合理的な行動といったゲーム理論における基本用語を学び,ゲーム理論の対象となるゲームとは何かを知った. 支配戦略均衡やナッシュ均衡といった標準型ゲームにおける均衡概念の基礎について学んだ. 展開型ゲームとそのゲーム木による表現について学んだ. 展開型ゲームがゼロサム・ゲームであった場合について効率的に解を求めるミニマックス法を学んだ. ミニマックス法において解の探索を効率化するα カットとβ カットについて学んだ.

宿題 章末問題の1を答えよ(演習4-1~4-3を含んでいる)。 予習問題:第5章は「動的計画法」が重要なポイント 答えは教科書の巻末に与えられているので、宿題としては特に(5)が答えのようになることの「理由説明」を中心とする 予習問題:第5章は「動的計画法」が重要なポイント 図5.5の初期値からアルゴリズム5.1によって、どのように図5.10という結果が得られるか、考えてみよ(次回講義の一つのポイント)