人間の対戦相手としての ゲームアルゴリズム， 話題提供 2009 3/3 組合せゲーム・パズル ミニ研究集会 池田 心 （京都大学） 1 自己紹介 • • • • 学部は数学科 大学院は知能システム科学専攻 現在は京大学術情報メディアセンター助教 昔からゲーム好き，パズル好き，プログラム好き． 囲碁五段． →当然，最強の囲碁プログラムを目指すことに． 2 研究テーマ：エージェントと最適化 • エージェント ： 知的処理・制御・意志決定を行う主体 • エージェントの，（遺伝アルゴリズムの技術に基づく） 構成・最適化・シミュレーション 3 何がしたいのか • • • • • • 賢い/速い/強いエージェントを作る ← 昔はこれが優先された 制御可能な強さのエージェントを作る ミクロにリアルなエージェントを作る マクロにリアルなエージェント（群）を作る 人間ぽくない（リアルでない），多様なエージェントを作る 教師ができるエージェントを作る 【なぜ作りたいのか】 • 創造者的な気分？ • そこに山があるから？ • そういうエージェントが作れれば，システムを理解したと思える から？羽生に勝てれば羽生より偉いから？ 4 • 役に立つから？ 目的１ 賢い/速い/強いエージェント • 比較的定量化しやすい指標（複数でも）につい て，それが優れていれば良い • 勝負としてのゲーム，インフラ制御，投資など • 多くの場合これが主流だった 5 目的２ 制御可能な強さのエージェント • 人間の相手をするAIプレイヤは，強ければ強いほどいい わけではない • 遊びとしてのゲーム（特に対等なもの），職業訓練など • 定説 「ゲームのＡＩはアホである」 – – – – – 麻雀 ドラクエＩＶ （同期型コマンド選択戦闘ゲーム） ぷよぷよ （落ちものパズルゲーム） カルドセプト （カード・すごろくゲーム） Age of Empire （エージェントベースド戦争ゲーム） • 強さは一軸ではない（例えば将棋ＡＩは序盤と終盤が強い） • 「このAIはあまりにもアホである」「このAIはズルをしてる」 「このAIは手抜きをしている」「でもいい勝負」ではダメ 6 目的３ ミクロにリアルなエージェント • 模擬したい対象（人間など）と，なんらかの意味で挙動が似て いること • シミュレーション実験，ゲーム，ペット • たいていは，挙動が似ているほうが親しめる • 高いリアルさを持つパラメータの最適化だけでなく，直接目標 とする行動を入れ込める仕組みも必要 • リアルさのためなら，バレなければズルしてもよいかも 7 目的４ マクロにリアルなエージェント • 人工市場，交通規範，社会調査など • 着眼点： ミクロにリアルであることと，マクロにリアル であることはお互いに必要条件でも十分条件でない • つまり，マクロにリアルなら，目的によってはミクロに リアルでなくてもよい 出展：http://provincie.overijssel.nl/beleid//verkeer_e n_vervoer/bereikbaarheid/knelpunten_in 8 目的５ 人間ぽくないエージェント • • • • 「能力が近く（良く），挙動も似ている」 ではなく， 「能力は近い（良い）が，挙動は似てない」 を作る 戦法発見，ニッチ開拓，攻撃への予防，ロバスト性 崩珠の例（後述） 9 ネタ１ ２次元版七五三（ニム） • 小～中くらいでやるゲーム 七五三 • 連続した横ｎ本の線を消せる．交互に消して最後の 一本を消した人の勝ち • 数理：各行の本数を２進数表記し，各桁の合計が偶 数になるようにすればよい 10 ２次元への拡張 • 縦・横に連続したｎ個を消せるようにする • 一気に複雑になったように見える．しらみつぶしで探 索するよりないか？ 11 もっと簡単に考えられる • 例えば曲がった３個は，まっすぐの３個と同じような もの • ０にも１にも２にもできるという特徴は同じ 12 数理： 実は整数へのマップがある • 0からｎ-1まで（と等価なもの）にはできるが，ｎ（と等価なもの） にはできないものはｎと等価である • ｎ個の丸でできたブロックは必ず0からnまでのどれ かになり，2進数桁和の法則が使える 13 デモ．これは受けなかった． ネタ２： スクラブル • 配られたアルファベットを並べ替えて単語を作り，点 数を競うゲーム（２～人） • 盤面にあるアルファベットにくっつけて，縦か横に置 く（挟むような位置でもよい） 14 普通の人間に勝つだけなら簡単 • 全配置パターンについて，辞書語が作れるか検索し， 最も高い点数のものを選ぶ（数秒）だけでほぼ無敵 • 「強さを調整する」だけなら簡単，検索を確率的にス キップしたり，辞書を間引くなど → つまらない 15 改善の方向 • 人間ぽくする – 「母音・子音のバランスをとる」「ｓ，ｘなどを出し惜しみす る」「ボーナスマスを気にする」などの戦術強化 – 人間が注目するような場所にしか注目しない • 教育的にする – プレイヤの単語レベルに合わせ，少しだけ難しい単語ま で使う – 戦術的に重要な単語（qi, za, joなど）を少しずつ使う – プレイヤの手に文句を言う 16 ネタ３： 崩珠（ぷよぷよ改） • ぷよぷよ（商標：セガ）というテレビゲームからアクション性 を取り除いてパズルとして扱いやすくしたもの • ルールはデモで紹介 • 階段連鎖（５連鎖程度）は誰でもできる • 折り返し（１０連鎖程度）も慣れればできる • どうすれば強いコンピュータが作れるか？ • 人間の模倣でもいいが，もっと力ずくで・・・ 17 発射先送りの木探索 • ２手または３手先で発射する中で最も効果の高いルートを選 び，「１手目だけ」従う • 必要になるまで発射せず，ポテンシャルの高そうな組み方を 選ぶ → 予想もしない連鎖に（デモ） 18 反響 • 「力ずくの，人間とは似ても似つかないコンピュータ」 は，つまらなかったか？ → そうでもない – – – – – 結構強い（平均１０連鎖程度） 連鎖の新境地である 読みの練習になる やっぱり人間ぽい敵も欲しい もっと強い敵も欲しい • Vectorに公開したり，ネット対戦版を作ったりしたが， 結構好評だった 19 まとめ • 人間相手を考えるなら，「強ければいい」ではない． 単に「強さが調整できればいい」でもない • １０年前に比べて速度・メモリ・ＨＤＤとも飛躍的に向 上しているのに，敵アルゴリズムが飛躍的に向上し ている気はしない • 自分もゲーム好きなので，自分がやって楽しい敵を 作りたい • そしてそれは学問になりうると思う • いつでもなんでもご連絡ください 20 現状のイメージ図 21
© Copyright 2024 ExpyDoc
