人間の対戦相手としての ゲームアルゴリズム， 話題提供

Presentation on theme: "人間の対戦相手としての ゲームアルゴリズム， 話題提供"— Presentation transcript:

1 人間の対戦相手としての ゲームアルゴリズム， 話題提供
　3/3 組合せゲーム・パズル　ミニ研究集会 池田 心 （京都大学）

2 自己紹介 学部は数学科 大学院は知能システム科学専攻 現在は京大学術情報メディアセンター助教
昔からゲーム好き，パズル好き，プログラム好き．囲碁五段．　 　　→当然，最強の囲碁プログラムを目指すことに．

3 研究テーマ：エージェントと最適化 エージェント ： 知的処理・制御・意志決定を行う主体
エージェントの，（遺伝アルゴリズムの技術に基づく） 構成・最適化・シミュレーション

4 何がしたいのか 賢い/速い/強いエージェントを作る ← 昔はこれが優先された 制御可能な強さのエージェントを作る
賢い/速い/強いエージェントを作る　←　昔はこれが優先された 制御可能な強さのエージェントを作る ミクロにリアルなエージェントを作る マクロにリアルなエージェント（群）を作る 人間ぽくない（リアルでない），多様なエージェントを作る 教師ができるエージェントを作る 【なぜ作りたいのか】 創造者的な気分？ そこに山があるから？ そういうエージェントが作れれば，システムを理解したと思えるから？羽生に勝てれば羽生より偉いから？ 役に立つから？

5 賢い/速い/強いエージェント 比較的定量化しやすい指標（複数でも）について，それが優れていれば良い
目的１ 賢い/速い/強いエージェント 比較的定量化しやすい指標（複数でも）について，それが優れていれば良い 勝負としてのゲーム，インフラ制御，投資など 多くの場合これが主流だった

6 制御可能な強さのエージェント 人間の相手をするAIプレイヤは，強ければ強いほどいいわけではない
目的２ 制御可能な強さのエージェント 人間の相手をするAIプレイヤは，強ければ強いほどいいわけではない 遊びとしてのゲーム（特に対等なもの），職業訓練など 定説 「ゲームのＡＩはアホである」 麻雀 ドラクエＩＶ （同期型コマンド選択戦闘ゲーム） ぷよぷよ （落ちものパズルゲーム） カルドセプト （カード・すごろくゲーム） Age of Empire （エージェントベースド戦争ゲーム） 強さは一軸ではない（例えば将棋ＡＩは序盤と終盤が強い） 「このAIはあまりにもアホである」「このAIはズルをしてる」「このAIは手抜きをしている」「でもいい勝負」ではダメ

7 ミクロにリアルなエージェント 模擬したい対象（人間など）と，なんらかの意味で挙動が似ていること シミュレーション実験，ゲーム，ペット
目的３ ミクロにリアルなエージェント 模擬したい対象（人間など）と，なんらかの意味で挙動が似ていること シミュレーション実験，ゲーム，ペット たいていは，挙動が似ているほうが親しめる 高いリアルさを持つパラメータの最適化だけでなく，直接目標とする行動を入れ込める仕組みも必要 リアルさのためなら，バレなければズルしてもよいかも

8 マクロにリアルなエージェント 人工市場，交通規範，社会調査など
目的４ マクロにリアルなエージェント 人工市場，交通規範，社会調査など 着眼点： ミクロにリアルであることと，マクロにリアルであることはお互いに必要条件でも十分条件でない つまり，マクロにリアルなら，目的によってはミクロにリアルでなくてもよい 出展： n_vervoer/bereikbaarheid/knelpunten_in

9 人間ぽくないエージェント 「能力が近く（良く），挙動も似ている」 ではなく， 「能力は近い（良い）が，挙動は似てない」 を作る
目的５ 人間ぽくないエージェント 「能力が近く（良く），挙動も似ている」 ではなく， 「能力は近い（良い）が，挙動は似てない」 を作る 戦法発見，ニッチ開拓，攻撃への予防，ロバスト性 崩珠の例（後述）

10 ネタ１ ２次元版七五三（ニム） 小～中くらいでやるゲーム 七五三 連続した横ｎ本の線を消せる．交互に消して最後の一本を消した人の勝ち
ネタ１　　２次元版七五三（ニム） 小～中くらいでやるゲーム　七五三 連続した横ｎ本の線を消せる．交互に消して最後の一本を消した人の勝ち 数理：各行の本数を２進数表記し，各桁の合計が偶数になるようにすればよい　

11 ２次元への拡張 縦・横に連続したｎ個を消せるようにする 一気に複雑になったように見える．しらみつぶしで探索するよりないか？

12 もっと簡単に考えられる 例えば曲がった３個は，まっすぐの３個と同じようなもの ０にも１にも２にもできるという特徴は同じ

13 数理： 実は整数へのマップがある 0からｎ-1まで（と等価なもの）にはできるが，ｎ（と等価なもの）にはできないものはｎと等価である
数理：　実は整数へのマップがある 0からｎ-1まで（と等価なもの）にはできるが，ｎ（と等価なもの）にはできないものはｎと等価である ｎ個の丸でできたブロックは必ず0からnまでのどれかになり，2進数桁和の法則が使える デモ．これは受けなかった．

14 ネタ２： スクラブル 配られたアルファベットを並べ替えて単語を作り，点数を競うゲーム（２～人）
ネタ２：　スクラブル 配られたアルファベットを並べ替えて単語を作り，点数を競うゲーム（２～人） 盤面にあるアルファベットにくっつけて，縦か横に置く（挟むような位置でもよい）

15 普通の人間に勝つだけなら簡単 全配置パターンについて，辞書語が作れるか検索し，最も高い点数のものを選ぶ（数秒）だけでほぼ無敵
「強さを調整する」だけなら簡単，検索を確率的にスキップしたり，辞書を間引くなど　→　つまらない

16 改善の方向 人間ぽくする 教育的にする 「母音・子音のバランスをとる」「ｓ，ｘなどを出し惜しみする」「ボーナスマスを気にする」などの戦術強化
人間が注目するような場所にしか注目しない 教育的にする プレイヤの単語レベルに合わせ，少しだけ難しい単語まで使う 戦術的に重要な単語（qi, za, joなど）を少しずつ使う プレイヤの手に文句を言う

17 ネタ３： 崩珠（ぷよぷよ改） ぷよぷよ（商標：セガ）というテレビゲームからアクション性を取り除いてパズルとして扱いやすくしたもの
ネタ３：　崩珠（ぷよぷよ改） ぷよぷよ（商標：セガ）というテレビゲームからアクション性を取り除いてパズルとして扱いやすくしたもの ルールはデモで紹介 階段連鎖（５連鎖程度）は誰でもできる 折り返し（１０連鎖程度）も慣れればできる どうすれば強いコンピュータが作れるか？ 人間の模倣でもいいが，もっと力ずくで・・・

18 発射先送りの木探索 ２手または３手先で発射する中で最も効果の高いルートを選び，「１手目だけ」従う
必要になるまで発射せず，ポテンシャルの高そうな組み方を選ぶ 　→　予想もしない連鎖に（デモ）

19 反響 「力ずくの，人間とは似ても似つかないコンピュータ」は，つまらなかったか？ → そうでもない
　→　そうでもない 結構強い（平均１０連鎖程度） 連鎖の新境地である 読みの練習になる やっぱり人間ぽい敵も欲しい もっと強い敵も欲しい Vectorに公開したり，ネット対戦版を作ったりしたが，結構好評だった

20 まとめ 人間相手を考えるなら，「強ければいい」ではない．単に「強さが調整できればいい」でもない
１０年前に比べて速度・メモリ・ＨＤＤとも飛躍的に向上しているのに，敵アルゴリズムが飛躍的に向上している気はしない 自分もゲーム好きなので，自分がやって楽しい敵を作りたい そしてそれは学問になりうると思う いつでもなんでもご連絡ください

21 現状のイメージ図