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