人工知能論第１回

Size: px

Start display at page:

Download "人工知能論第１回"

ふさこみおか
8 years ago
Views:

1 知能システム総論第 14 回 : 知的エージェントの構造ゲームとAIの概説ソフトウェア情報学部講師ダビドラマムジスア (David Ramamonjisoa)

2 目次人工知能 AI とコンピュータサイエンス人工知能研究ゲームとは? ゲームと AI 問題解決エージェント問題を定式化することまとめ課題

3 人工知能研究とコンピュータサイエンス研究の違い AI 生き物が簡単に解決出来る問題を機械に解かせる顔音声文字認識会話自然言語学習思考蟻 ( アリ ) 集団の問題解決コンピュータサイエンス人間が解けない難しい問題をコンピュータで解く計算速度並列計算人工衛星制御地球シミュレーション大量データの管理 ( 銀行証券健康政府

4 人工知能研究

5 ゲーム人間の遊戯 ( ゆうぎ ) 遊び頭悩 ( ずのう ) 思考であるゲームが非生産的ということ自体がある人間にとって遊ぶということはとても大切なことである社会の仕組みをゲームと見ている立場は面白い肉体と体力反射神経を使うもの ( スポーツ )

6 ゲームの種類 (1) ゲームの人数 : 0 人 : ライフゲーム 1 人 : 考え物 (Sudoku, パズルスロット.) 2 人 : チェスオセルチェッカー囲碁将棋マージャン 3 人以上 :Monopoly, カード, UNO, マージャンゲームの完全情報がどうか完全 : 盤面を使うゲーム不完全 : 自分がもっている駒やカードが相手にみえない確定的かどうか確定的 : チェスオセル三目並べ非確定的 : サイコロを使うゲームゼロ和かどうかゼロ和 : 勝ちをプラス 1 負けをマイナス 1 引分けを 0

7 ゲームの種類 (2) シミュレーションゲーム : 人生シミュレーション :Sims クイズ(Jeopardy) 生き物のシミュレーション :Spore 乗り物 : フライトシミュレータカーシミュレータなど社会戦争街国ビジネス :SimCity, メタバース, 戦闘, RPG( ロールプレイングゲーム ): ダンジョン & ドラゴンズ Dungeons and Dragons (D&D) ビデオゲーム : ストリー有無スロットマシンカジノ大人のゲーム : セガウドライフなど, コンテンツによる男のゲーム : 戦闘アクション ; 女のゲーム : バービー人形ディジタルゲーム vs アナログゲームコンピュータゲーム vs テーブルゲーム

8 ゲームのための情報データ構造 : 局面着手アルゴリズム : 次の局面の列挙勝ち局面負け局面の決定状態 : 対象物の状況 (state, position: 局面 ) ゲームの規則の表現 : 可能な着手可能な着手 : 木の形 ( 着手 1-> 着手 2 ) 戦略 ( ゴールを早く達成するポイントを沢山取る方法敵の位置を把握するなど ) 経験 ( プレやーのレベルを認識する ) リアリズム (3D, 音声, )

9 コンピュータゲームの歴史 CRT コンソールゲームシステム NPC: 単純なパターン : レベル自動調整ダンジョンの自動生成技術 AR: Augmented Reality カセットビジョンファミリーコンピュータ (Family Computer) ウインドウズゲーム Mac ゲーム :Tetris, PacMan, Tennis, Solitary, セガ SimCity 任天堂の Wii ソニーコンピュータエンタテインメントのプレイステーション 2 およびプレイステーション 3 マイクロソフトの Xbox および Xbox マンガコンソール, ebook Ipad, Nitendo 3DS, PSVITA, ARDrone

10 ゲームと AI 人間の思考を真似るデータ構造をうまく設計するアルゴリズム ( 手続き ) を勝ち負け引き分けの探索を速く正しく短く開発する完全情報のゲームではなるべくすべての解の探索木を表現する ( 理想 ) シミュレーションゲームでは計画学習協調能力あるエージェント (NPC アバター ) を開発する

11 ゲームシステムアーキテクチャーゲームシステム人工知能 (AI) ゲーム世界 NPC プレイヤーディジタル世界 (Internal world) 相互作用 (Interaction) 外部世界 (Outside world) 11

12 NPC エージェント (agent) どのように設計する? 問題解決プロセス認識意思決定記憶事前知識内部状態行動生成? Agent センサ (Sensors) エフェクタ (Effectors) 知覚 (percepts) 環境 : ゲーム世界 (GameEnvironment) 動作 (actions) 12

13 問題解決エージェント (Problem Solving Agents (1)) 自動化するゴールを達成する反射エージェント 13

14 問題解決エージェントの内部構成知的エージェント知的反射エージェント知的エージェント学習エージェント

15 知的エージェントの例アバタキャラクタユーザとマルチモダルでコミュニケーションするニュースをユーザーの興味にあわせてまとめるユーザーの指定した主題に沿って情報を探すユーザーの個人情報を記憶しておきユーザーに代わってウェブ上のフォームに入力する監視エージェント機器を監視して報告する在庫管理プランニングスケジューリングのコスト削減を図る

16 知的なエージェント :Deep Blue ( チェスプレーヤーの世界チャンピョン ) ゲーム : チェスプレーヤーチャンピョンカスパロフ氏ディップブルー ( 機械 ) 1997 年賞金 :100 万ドル /1 億 2 千万円 1 対 2: 人間は破れた

17 ゲーム AI の歴史ボードゲーム : チェスゲームシステム NPC: 単純なパターン : レベル自動調整ダンジョンの自動生成技術 AI の構造化 :FSM A* minimax, 反復深化探索, インタフェース (3D) NPC のエージェント化リアルな CG, インタフェースの進化 : キーボードコンソールなし ( ジェスチャー認識音声認識環境認識リアルタイムモーションキャプチャと生成 ) NPC の思考の改善インタラクティブストーリゲーム :3D 強化

18 問題解決とは? 問題発見のあとに来る解決手段を探り実際に解決に至る道筋を示す行為典型的な問題はいくつかの解決手段が用意されている診断問題計画問題スケジューリング問題設計問題予測問題現実の問題は複合問題となっていることが多く問題の整理形式化が重要典型的な問題は問題解決エージェントの枠組みで整理できる

19 問題解決エージェント問題解決エージェントは, ゴールが与えられて, そのゴールに至る解を探索する. はじめに, ゴールを定式化する. ゴールは, 世界状態の集合として定義される. 行為は, 世界状態間の遷移を引き起こす. つぎに, 問題の定式化を行う. 適切な行為 ( オペレータ ) の選択が必要. つぎに, 解に至る行為の様々な可能な系列を調べて, その中で最も良いものを選ぶ ( 解の探索 ). 最後に, 解を実行する.

20 問題解決エージェントの例 ( 掃除機の世界 :vacuum world) 掃除機 ( エージェント ) の世界は 2 つの場所だけを含むようにしよう. エージェントは 1 つの場所か他の場所にいる可能性がある 8 つの可能な正解状態があるゴールの定式化 : すべての埃をきれいに掃除することであるを, ゴールとして設定すべきである. 問題の定式化 : 左へ移動 (Left) あるいは右へ移動 (Right) 吸込み (Suck) は, 行為としてある. 解の探索 : 場所間の隣接情報から, 可能な場所に行くし, 掃除する. 初期状態 : どんな状態でも OK

21 問題解決エージェントの例 2 ( 掃除機ロボットの世界 :vacuum world) 単一状態問題 (singlestate problem) 単一状態 (Single-state), 始点 #5. 解 (Solution)?

22 掃除機の世界単一状態 ( Single-state), 始点 #5. 解? [Right, Suck] センサない (Sensorless), 始点 {1,2,3,4,5,6,7,8} e.g., Right なら {2,4,6,8} 解?

23 掃除機の世界センサない (Sensorless), 始点 {1,2,3,4,5,6,7,8} e.g., Right ( 右 ) なら {2,4,6,8} 解? [Right,Suck,Left,Suck] 偶溌的問題 (Contingency) 非決定論的 (Nondeterministic): 吸い込みはきれいな部屋に埃を残す (Suck may dirty a clean carpet) 部分的観察できる (Partially observable): 場所埃の位置 (location, dirt at current location). 視覚 (Percept): [L, Clean], i.e., 始点 #5 か #7 解?

24 掃除機の世界センサない (Sensorless), 始点 {1,2,3,4,5,6,7,8} e.g., Right ( 右 ) なら {2,4,6,8} 解? [Right,Suck,Left,Suck] 偶溌的問題 (Contingency) 非決定論的 (Nondeterministic): 吸い込みはきれいな部屋に埃を残す (Suck may dirty a clean carpet) 部分的観察できる (Partially observable): 場所埃の位置 (location, dirt at current location). 視覚 (Percept): [L, Clean], 始点 #5 か #7 解? [Right, if dirt then Suck]

25 掃除機の世界 : 状態空間のグラフ (Vacuum world state space ) 状態 (states)? 行為 (actions)? ゴール検査 (goal test)? 経路コスト (path cost)?

26 掃除機の世界 : 状態空間のグラフ (Vacuum world state space ) 状態 (states)? 状態 1-8 の部分集合 (integer dirt and robot location) 行為 (actions)? L: 左に動く R: 右に動く S: 吸い込む (Left, Right, Suck) ゴール検査 (goal test)? 埃がない (no dirt at all locations) 経路コスト (path cost)? 1 各々の行為はコスト 1 を要する (1 per action)

27 掃除機の世界 : 状態空間のグラフ (Vacuum world state space )

28 例題 1. 8 パズル問題 : 滑りブロックパズルの族に属する 8 つのタイルの各々が 9 個の区画のどの位置にあるかによって決まる Start State Goal State

29 例題 1. 8 パズル状態 (states)? 行為 (actions)? ゴール検査 (goal test)? 経路コスト (path cost)?

30 例題 1. 8 パズル状態 (states)? タイルの位置 (locations of tiles) 行為 (actions)? 空白を上下左右に動かす (move blank left, right, up, down) ゴール検査 (goal test)? 状態上図のゴール配置に一致する経路コスト (path cost)? 各々の行為はコストは 1 を要する (1 per move) [ 備考 : 最適の解のクラスは NP- 完全であること (optimal solution of n- Puzzle family is NP-hard)]

31 実装 : 状態対ノード (Implementation: states vs. nodes) 状態は物理的な表現 (A state is a (representation of) a physical configuration) ノードはデータ構造であり木の一部の構成になる (A node is a data structure constituting part of a search tree includes state, parent node, action, path cost g(x), depth)

32 A* アルゴリズムの疑似コードゴールノード (G ) とスタートノード (S ) を作成するまた計算中のノードを格納しておくためのリスト (Open リスト ) と計算済みのノードを格納しておくリスト (Close リスト ) を用意するスタートノードを Open リストに追加するこのとき g * (S) = 0 であり f * (S) = h * (S) となるまた Close リストは空にする Open リストが空なら探索は失敗とする ( スタートからゴールにたどり着くような経路が存在しなかったことになる ) Open リストに格納されているノードの内最小の f * (n) を持つノード n を取り出す n = G であるなら探索を終了するそれ以外の場合は n を Close リストに移す n に隣接している全てのノード ( ここでは隣接ノードを m とおく ) に対して以下の操作を行う

33 A* アルゴリズムの疑似コード f '(m) = g * (n) + h * (m) + COST(n,m) を計算するここで COST(n,m) はノード n から m へ移動するときのコストであるまた g * (n) は g * (n) = f * (n) - h * (n) で求めることができる m の状態に応じて以下の操作を行う m が Open リストにも Close リストにも含まれていない場合 f * (m) = f '(m) とし m を Open リストに追加するこのとき m の親を n として記録する m が Open リストにある場合 f '(m) < f * (m) であるなら f * (m) = f '(m) に置き換えるこのとき記録してある m の親を n に置き換える m が Close リストにある場合 f '(m) < f * (m) であるなら f * (m) = f '(m) として m を Open リストに移動するまた記録してある m の親を n に置き換える 3 以降を繰り返す探索終了後 G から親を順次たどっていくと S から G までの最短経路が得られる

34 A* アルゴリズムの応用 : 経路探索

35 まとめゲームは人間の大切な活動である愉快教育ためのツールであるゲームは人工知能 (AI) の特級な問題である知的エージェントは学習や推論を取り入れたもの問題解決エージェントは, ゴールが与えられて, そのゴールに至る解を探索する. はじめに, ゴールを定式化し, つぎに, 問題の定式化を行う. 問題は, 初期状態, オペレータ, ゴール検査, 経路コストから成り立つ.

36 まとめ ( つづき ) ゲームは自分で競技しても楽しいものであるコンピュータに競技させるべくプログラミングゲームのも新しいジャンルの楽しみとなりつつあるコンピュータを友達として抱き込み自分の知能エージェントとして世に送り出す人間はメタの世界に入って楽しみを追求する ( セガンドライフのように ) ゲームは情報科学認知科学人工生命社会科学との関連ある

37 課題 1) この授業ではエージェントはどのように利用される問題解決エージェントが様々な種類ある順番に複雑から単純に列挙し構成を説明せよ 2) コンピュータゲーム特徴の現代を述べよ 3) 掃除機問題の状態空間のグラフの解を状態の番号で示せ

38 探索木を作成しなさい

39 深さ優先探索と幅優先探索の解を求めよ

40 XNYCiQ&NR=1 xq3ozva

人工知能論第１回

人工知能論第１回知能システム学第 3 回問題解決問題のモデル化ソフトウェア情報学部 David Ramamonjisoa 目次問題の種類問題解決プロセス? 問題解決エージェントタスク環境の設定問題を定式化すること例題まとめ問題の種類 (The Problem types) おもちゃの問題 (Toy problem) パズルルビクスキュブ数独などゲーム : チェス囲碁ポカーブリッジ N-queens

人工知能論 第１回

人工知能論第１回