知能システム総論第 14 回 : 知的エージェントの構造ゲームとAIの概説 ソフトウェア情報学部講師 ダビド ラマムジスア (David Ramamonjisoa)
目次 人工知能 AI とコンピュータサイエンス人工知能研究ゲームとは? ゲームと AI 問題解決エージェント問題を定式化することまとめ課題
人工知能研究とコンピュータサ イエンス研究の違い AI 生き物が簡単に解決出来る問題を機械に解かせる 顔 音声 文字認識 会話 自然言語 学習 思考 蟻 ( アリ ) 集団の問題解決 コンピュータサイエンス 人間が解けない 難しい問題をコンピュータで解く 計算速度 並列計算 人工衛星制御 地球シミュレーション 大量データの管理 ( 銀行 証券 健康 政府
人工知能研究 http://www.ai-gakkai.or.jp/jsai/whatsai/airesearch.html
ゲーム 人間の遊戯 ( ゆうぎ ) 遊び 頭悩 ( ずのう ) 思考である ゲームが 非生産的 ということ自体がある 人間にとって遊ぶということはとても大切なことである 社会の仕組みをゲームと見ている立場は面白い 肉体と体力 反射神経を使うもの ( スポーツ )
ゲームの種類 (1) ゲームの人数 : 0 人 : ライフゲーム 1 人 : 考え物 (Sudoku, パズル スロット.) 2 人 : チェス オセル チェッカー 囲碁 将棋 マージャン 3 人以上 :Monopoly, カード, UNO, マージャン ゲームの完全情報がどうか 完全 : 盤面を使うゲーム 不完全 : 自分がもっている駒やカードが相手にみえない確定的かどうか 確定的 : チェス オセル 三目並べ 非確定的 : サイコロを使うゲームゼロ和かどうか ゼロ和 : 勝ちをプラス 1 負けをマイナス 1 引分けを 0
ゲームの種類 (2) シミュレーションゲーム : 人生シミュレーション :Sims クイズ(Jeopardy) 生き物のシミュレーション :Spore 乗り物 : フライトシミュレータ カーシミュレータ など 社会 戦争 街 国 ビジネス :SimCity, メタバース, 戦闘, RPG( ロールプレイングゲーム ): ダンジョン & ドラゴンズ Dungeons and Dragons (D&D) ビデオゲーム : ストリー有無スロットマシン カジノ大人のゲーム : セガウドライフなど, コンテンツによる男のゲーム : 戦闘 アクション ; 女のゲーム : バービー人形ディジタルゲーム vs アナログゲーム コンピュータゲーム vs テーブルゲーム
ゲームのための情報 データ構造 : 局面 着手 アルゴリズム : 次の局面の列挙 勝ち局面 負け局面の決定 状態 : 対象物の状況 (state, position: 局面 ) ゲームの規則の表現 : 可能な着手 可能な着手 : 木の形 ( 着手 1-> 着手 2 ) 戦略 ( ゴールを早く達成する ポイントを沢山取る方法 敵の位置を把握するなど ) 経験 ( プレやーのレベルを認識する ) リアリズム (3D, 音声, )
コンピュータゲームの歴史 1947 - CRT コンソール 1972 - ゲームシステム NPC: 単純なパターン : レベル自動調整 ダンジョンの自動生成技術 1981 1983 - AR: Augmented Reality カセットビジョンファミリーコンピュータ (Family Computer) 1986 - ウインドウズゲーム Mac ゲーム :Tetris, PacMan, Tennis, Solitary, 1990 - セガ SimCity 2007 - 任天堂の Wii ソニー コンピュータエンタテインメントのプレイステーション 2 およびプレイステーション 3 マイクロソフトの Xbox および Xbox 360 2008 - マンガコンソール, ebook 2010 - Ipad, Nitendo 3DS, PSVITA, ARDrone
ゲームと AI 人間の思考を真似る データ構造をうまく設計する アルゴリズム ( 手続き ) を勝ち 負け 引き分けの探索を速く 正しく 短く開発する 完全情報のゲームではなるべくすべての解の探索木を表現する ( 理想 ) シミュレーションゲームでは計画 学習 協調 能力あるエージェント (NPC アバター ) を開発する
ゲームシステムアーキテクチャー ゲームシステム 人工知能 (AI) ゲーム世界 NPC プレイヤー ディジタル世界 (Internal world) 相互作用 (Interaction) 外部世界 (Outside world) 11
NPC エージェント (agent) どのように設計する? 問題解決プロセス 認識 意思決定記憶 事前知識内部状態 行動生成? Agent センサ (Sensors) エフェクタ (Effectors) 知覚 (percepts) 環境 : ゲーム世界 (GameEnvironment) 動作 (actions) 12
問題解決エージェント (Problem Solving Agents (1)) 自動化するゴールを達成する 反射エージェント 13
問題解決エージェントの内部構成 知的エージェント 知的反射エージェント 知的エージェント 学習エージェント
知的エージェントの例 アバタ キャラクタ ユーザとマルチモダルでコミュニケーションする ニュースをユーザーの興味にあわせてまとめる ユーザーの指定した主題に沿って情報を探す ユーザーの個人情報を記憶しておき ユーザーに代わってウェブ上のフォームに入力する 監視エージェント 機器を監視して報告する 在庫管理 プランニング スケジューリングのコスト削減を図る
知的なエージェント :Deep Blue ( チェ スプレーヤーの世界チャンピョン ) ゲーム : チェスプレーヤーチャンピョンカスパロフ氏 ディップブルー ( 機械 ) 1997 年 賞金 :100 万ドル /1 億 2 千万円 1 対 2: 人間は破れた
ゲーム AI の歴史 1950-1997 ボードゲーム : チェス 1972 - ゲームシステム NPC: 単純なパターン : レベル自動調整 ダンジョンの自動生成技術 1994 - AI の構造化 :FSM A* minimax, 反復深化探索, インタフェース (3D) 2001 - NPC のエージェント化リアルな CG, 2009 - インタフェースの進化 : キーボード コンソールなし ( ジェスチャー認識 音声認識 環境認識 リアルタイムモーションキャプチャと生成 ) NPC の思考の改善 2011 - インタラクティブストーリゲーム :3D 強化
問題解決とは? 問題発見のあとに来る 解決手段を探り 実際に解決に至る道筋を示す行為 典型的な問題は いくつかの解決手段が用意されている 診断問題 計画問題 スケジューリング問題 設計問題 予測問題 現実の問題は 複合問題となっていることが多く 問題の整理 形式化が重要 典型的な問題は 問題解決エージェントの枠組みで整理できる
問題解決エージェント 問題解決エージェントは, ゴールが与えられて, そのゴールに至る解を探索する. はじめに, ゴールを定式化する. ゴールは, 世界状態の集合として定義される. 行為は, 世界状態間の遷移を引き起こす. つぎに, 問題の定式化を行う. 適切な行為 ( オペレータ ) の選択が必要. つぎに, 解に至る行為の様々な可能な系列を調べて, その中で最も良いものを選ぶ ( 解の探索 ). 最後に, 解を実行する.
問題解決エージェントの例 ( 掃除機 の世界 :vacuum world) 掃除機 ( エージェント ) の世界は 2 つの場所だけを含むようにしよう. エージェントは 1 つの場所か他の場所にいる可能性がある 8 つの可能な正解状態がある ゴールの定式化 : すべての埃をきれいに掃除することである を, ゴールとして設定すべきである. 問題の定式化 : 左へ移動 (Left) あるいは 右へ移動 (Right) 吸込み (Suck) は, 行為としてある. 解の探索 : 場所間の隣接情報から, 可能な場所に行くし, 掃除する. 初期状態 : どんな状態でも OK
問題解決エージェントの例 2 ( 掃除 機ロボットの世界 :vacuum world) 単一状態問題 (singlestate problem) 単一状態 (Single-state), 始点 #5. 解 (Solution)?
掃除機の世界 単一状態 ( Single-state), 始点 #5. 解? [Right, Suck] センサない (Sensorless), 始点 {1,2,3,4,5,6,7,8} e.g., Right なら {2,4,6,8} 解?
掃除機の世界 センサない (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 解?
掃除機の世界 センサない (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]
掃除機の世界 : 状態空間のグラフ (Vacuum world state space ) 状態 (states)? 行為 (actions)? ゴール検査 (goal test)? 経路コスト (path cost)?
掃除機の世界 : 状態空間のグラフ (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)
掃除機の世界 : 状態空間のグラ フ (Vacuum world state space )
例題 1. 8 パズル 問題 : 滑りブロックパズルの族に属する 8 つのタイルの各々が 9 個の区画のどの位置にあるかによって決まる. 5 4 6 1 8 7 3 2 Start State 1 2 3 8 4 7 6 5 Goal State
例題 1. 8 パズル 状態 (states)? 行為 (actions)? ゴール検査 (goal test)? 経路コスト (path cost)?
例題 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)]
実装 : 状態対ノード (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)
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 とおく ) に対して以下の操作を行う
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 までの最短経路が得られる
A* アルゴリズムの応用 : 経路探索
まとめ ゲームは人間の大切な活動である 愉快 教育ためのツールである ゲームは人工知能 (AI) の特級な問題である知的エージェントは学習や推論を取り入れたもの問題解決エージェントは, ゴールが与えられて, そのゴールに至る解を探索する. はじめに, ゴールを定式化し, つぎに, 問題の定式化を行う. 問題は, 初期状態, オペレータ, ゴール検査, 経路コストから成り立つ.
まとめ ( つづき ) ゲームは自分で競技しても楽しいものであるコンピュータに競技させるべくプログラミングゲームのも 新しいジャンルの楽しみとなりつつある コンピュータを友達として抱き込み 自分の知能エージェントとして世に送り出す 人間はメタの世界に入って楽しみを追求する ( セガンドライフのように ) ゲームは情報科学 認知科学 人工生命 社会科学との関連ある
課題 1) この授業では エージェントはどのように利用される 問題解決エージェントが様々な種類ある 順番に複雑から単純に列挙し 構成を説明せよ 2) コンピュータゲーム特徴の現代を述べよ 3) 掃除機問題の状態空間のグラフの解を状態の番号で示せ
探索木を作成しなさい
深さ優先探索と幅優先探索の解 を求めよ
http://www.youtube.com/watch?v=zb9kn XNYCiQ&NR=1 http://www.youtube.com/watch?v=syww xq3ozva