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

発表資料