ぼくのかんがえたさいきょうのマリオAI

ぼくのかんがえたさいきょうのマリオ AI 艮鮟鱇 @ushitora anqou 1

とりあえずデモ https://twitter.com/ ushitora_anqou/status/ 1061234857181765633 2

とりあえずデモ https://goo.gl/VJhD8Q Google URL Shortener は 2019 年 3 月で
サービス終了 3

すごくない？？ 4

すごい！ 5

いろんなやりかた 6

いろんなやりかた • ルールベース • すたっとさんとか • つらそう 6

いろんなやりかた • ルールベース • すたっとさんとか • つらそう • 遺伝的アルゴリズム •
VT-b とか • つらそう 6

いろんなやりかた • ルールベース • すたっとさんとか • つらそう • 遺伝的アルゴリズム •
VT-b とか • つらそう • ﾁﾞｰﾌﾟﾗﾆｰﾝｸﾞ（DQN） • 梅さんとか • つらそう 6

設定 • エージェント（AI）がマリオをする。 • 環境情報を受け取り、ボタンの押し方を返す。画像引用：http://ur0.biz/Ok3H 7

想定解入力：マリオの状態や周りの情報 ⬇ エージェント f (x) ⬇ 出力：ボタンの押し方 8

ところで • マリオ AI のステージは固定 • ランダム要素はない。 • エージェント出力の種類は有限 •
6 個のボタンの ON/OFF なので 26 = 64 ⬇ 出力を全て決めればその評価は一定 9

どゆこと？事前にエージェントの出力を決める。 1. 右移動＋ダッシュ 2. 右移動＋ジャンプ 3. ジャンプ . .
. これを出力した後の状態を評価すると、その出力の「よさ」が分かる ➡ 探索可能 10

想定解（再掲）入力：マリオの状態や周りの情報 ⬇ エージェント f (x) ⬇ 出力：ボタンの押し方 11

鮟鱇解あからじめ出力が決められたエージェント f () ⬇ 出力：ボタンの押し方 12

全幅探索計算量：O(64n) 13

おねえさーぁぁん！画像引用：https://youtu.be/Q4gTV4r0zRs 14

すくなく計算する 64 通りも要らない。 • 左移動と右移動を同時に入力することはない。 • 上移動は使わない。 • 四六時中ダッシュすればいい。
15

すくなく計算する 4 通りに減らせる。 • ダッシュ＋左移動 • ダッシュ＋右移動 • ダッシュ＋左移動＋ジャンプ •
ダッシュ＋右移動＋ジャンプ 16

続‧すくなく計算する人間がマリオを遊ぶ。 • 人間の反応時間は 0.2s。 • 片や PC の画面更新は 30fps
→ 0.033s ➡ 人間のほとんどの反応は前と同じ同様にエージェントの出力をダブらせる。 17

計算量：O ( 4n k ) 18

指数時間はいやだ！多項式時間で計算したい。 • 貪欲法 • 一番良さそうな手を選択することを繰り返す。 • 捨てる手が多い。 •
計算量は O(4n) • ビームサーチ • 貪欲法の拡張。 • 今回はこれを選択。 19

ビームサーチ • 良さそうな手を m 個持っておき、その手から伸びる手を探索する。 • 探索した手のうち、上位 m 個を次の探
索で使う。 • 計算量は O(4mn) • わりとうまくいく。 20

ところで 21

ところで「良さそうな手」ってなに？ 21

評価関数をつくる ϕ : 手 −→ 評価値ある手がどのくらい「良い」のかを表す関数をつくる。 22

評価関数をつくる ϕ : 手 −→ 評価値ある手がどのくらい「良い」のかを表す関数をつくる。めっちゃ難しい。 22

続‧評価関数をつくる • マリオの x 座標を使う？ • 無謀にジャンプして距離を稼ぎ死ぬ。 • 袋小路に入って死ぬ。 •
マリオの y 座標を使う？ • ジャンプし続けて死ぬ。 • その他の指標？ • わからん！ｗ 23

どうしたか「接地していたマリオの x 座標の最大値」 24

どうしたか「接地していたマリオの x 座標の最大値」 • 接地していないと評価にならない。 • 無謀なジャンプを低評価に。 • 最大値をとることで袋小路にスタック
することを防ぐ。 • 全ての行動が等価になるので、乱択で行動が決まる。 24

評価関数図解 1 25

まとめ • マリオ AI は意外と難しかった。 • 正直喋れてないことはたくさんある。 • どうでもいいけどステージ 4–1
はクソ。 • そのうちｺｿｯとコードは公開します。 28

ご清聴ありがとうございました 29

More Decks by Ushitora Anqou