はじめに
haruka_apps です。Playload で作品を作りながらわかったことをまとめるシリーズの5本目です。
今回は、迷路の道順を自分で覚えていく AI「td maze.」を紹介します。最初は迷路をうろうろするだけの AI が、ゴールするたびに少しずつ道を覚えていき、迷路の床に「こっちへ行けばいい」という矢印が浮かび上がってきます。
- この記事の内容は Playload 0.9.5 時点 のものです。
- 調べものや検証は AI と一緒に行いました。記事の内容は、私が確認したうえで書いています。
シリーズ目次
- Playloadの画面は「文字のマス」と「動くキャラ」でできている
- 絵の描き方の基本 ― 内蔵文字で描く、自作文字は少しずつ書き換える
- 3KBで3Dを描く ― Cube Maze 3D の描き方
- 3KBの中に8ビットコンピュータを作った ― PL-8
- 迷路を自分で覚えるAI ― td maze.
- 3KBの壁を圧縮で押してみた ― 8本中7本が小さくなったけれど、すすめはしない話
td maze.
黄色の ● が AI です。左下の S から出発して、右上の ★ を目指します。迷路の床の矢印は、AI が覚えた「このマスでは、こっちへ進むといい」という向きです。
遊ぶ人は、見ているだけでなく、迷路に手を出せます。
- 十字キーでオレンジ色の ┼ を動かし、Ⓐで壁を置いたり外したりできます。覚えた道の途中に壁を置くと、AI が別の道を探し始めます。
- S のマスで Ⓐを押すと、迷路の種類が切り替わります（後で説明する STATIC・BLOCK・SHORT）。
- Ⓑで、AI の覚え方（4種類）を切り替えます。
スタートからゴールまでを1回と数えて、45回で止まります。迷路や覚え方を切り替えると、最初からやり直しになります。
AI はどうやって道を覚えるのか
この AI は、「強化学習」と呼ばれる方法で道を覚えます。ルールはとても単純です。
| できごと | 点数 |
|---|---|
| ゴールに着く | ＋240 |
| 壁にぶつかる | −32 |
| 1歩進む | −2 |
AI は、迷路のすべてのマスについて、「上・下・左・右に進んだら、この先どれくらい点数がもらえそうか」という予想の点数を持っています。最初はどれも 0 です。
1歩進むたびに、次のように予想を直します。
いま進んだ向きの点数を、「もらった点数」＋「行った先のマスでいちばん高い点数（少しだけ割り引く）」に近づける
これを繰り返すと、ゴールの近くのマスから順に「ゴールへ向かう向き」の点数が高くなっていき、その点数がスタートのほうへ伝わっていきます。床の矢印は、各マスでいちばん点数の高い向きです。点数が高いほど、矢印の色が青→緑→黄→白と明るくなります。壁にぶつかって点数がマイナスになった所には、赤い × が出ます。
AI は、ふだんはいちばん点数の高い向きに進みますが、ときどき（8%）わざとでたらめな向きに進みます。こうして、まだ知らない道も試します。
左から、出発した直後、5回目、45回目の様子です。最初は何もわからず、途中では壁にぶつかった所が × だらけになり、最後はゴールまでの矢印の道ができています。
4つの覚え方
Ⓑで切り替えられる4つの覚え方を比べました。下の画像は、どれも同じ迷路（STATIC）で、同じ5秒間だけ動かしたあとの様子です。
左から順に、次の覚え方です。
- Q(0)：1歩ごとに、いま進んだ向きの点数だけを直します。ゴールの情報は、1回ゴールするたびに1マスずつしか戻ってきません。そのため、道を覚えるのにいちばん時間がかかります。
- Q(.5)・Q(.8)：歩いた「足あと」を覚えておき、点数が変わったら、足あとに沿って前のマスにもまとめて伝えます。数字が大きいほど、遠くの足あとまで伝わります。床の • は、まだ残っている足あとです。
- DYNA-Q：歩いた経験をメモしておき、1歩進むたびに、メモの中から8つを思い出して点数を直します（頭の中で復習するイメージです）。さらに、しばらく行っていないマスに、少し行ってみたくなるようにしています。1回あたりの歩数が少なく済むので、同じ時間でいちばん先まで進んでいます。
迷路が途中で変わると
迷路の種類は3つあります。
- STATIC：迷路は変わりません。
- BLOCK：15回目のゴールのあと、覚えた近道がふさがり、別の道が開きます。
- SHORT：15回目のゴールのあと、新しい近道が開きます。
左は BLOCK で道がふさがった直後です。AI は、ふさがった道を通る矢印を覚えたままなので、壁にぶつかって × を増やしながら、別の道を探します。右は、新しい道を覚え直した後です。
それぞれの覚え方で、何回目に道を覚えたかを測りました。
| 覚え方 | 道を覚えるまで（STATIC） | ふさがった後に覚え直すまで（BLOCK） | 近道を見つけるまで（SHORT） |
|---|---|---|---|
| Q(0) | 27回 | 最初の道を覚えきれず | 20回 |
| Q(.5) | 12回 | 22回 | 10回 |
| Q(.8) | 8回 | 45回までに覚え直せず | 45回までに見つけられず |
| DYNA-Q | 10回 | 14回 | 3回 |
- 「道を覚える」は、22歩以内でゴールできた最初の回です。
- 「覚え直す」「見つける」は、迷路が変わった15回目のあと、新しい道（BLOCK は24歩以内、SHORT は近道の16歩）でゴールできるまでの回数です。
- 乱数の種を決めて1回ずつ測った結果なので、乱数が変われば多少変わります。
面白いのは、変わらない迷路ではいちばん速い Q(.8) が、迷路が変わると苦手になることです。遠くまで足あとを伝えるぶん、古い道を強く覚えすぎて、なかなか忘れられません。逆に DYNA-Q は、頭の中の復習と「しばらく行っていない所を試す」性質のおかげで、新しく開いた近道を、開いてからわずか3回で見つけました。
作っていてつまずいたこと
最初に作ったとき、BLOCK や SHORT の迷路で、AI が狭い入り口の前で止まってしまい、ずっとゴールできなくなることがありました。
原因は、足あとの扱いでした。入り口を通った先で壁にぶつかると、そのマイナスの点数が足あとに沿って入り口まで伝わり、唯一の通り道である入り口そのものが ×（行ってはいけない所）になってしまっていた のです。
そこで、壁にぶつかったときと、わざとでたらめな向きに進んだときは、足あとを消す ようにしました。こうすると、悪い結果は直前の1歩だけに伝わり、そこまでの道は悪者になりません。これは強化学習の古典的な方法（Watkins の方法）と同じ考え方です。
Playload の上限との付き合い方
-
迷路は、すべて文字のマス：床の矢印
↑↓←→、×、•、壁の█、S、★は、どれも内蔵の文字です。自作文字は使いません。 - 右のグラフだけ自作文字：「1回あたり何歩かかったか」のグラフ（STEPS/EP）は、自作文字24文字（1フレーム192バイト）で描いています。上限の256バイトに収まります。
- 動くキャラは2個だけ：AI の ● とカーソルの ┼ です。
大きさは、変数名などを短くしない読みやすいコードのままで、圧縮後およそ 2.8 KB です。
ほかにもこんな実験をしています
td maze. のほかにも、3KB の中で動く小さな AI の実験をしています。
左は、内蔵の絵文字8種類をその場で学習して、砂嵐の中から絵を浮かび上がらせる実験です。右は、ひらがなの短い文を4つ学習して、そこにない新しい文を作る実験です。
おわりに
5回にわたって、Playload で作品を作りながらわかったことを紹介してきました。
- 画面は「文字のマス」「動くキャラ」「自作文字」でできていて、上限がある
- 内蔵の文字だけで描けば上限を気にせず描け、自作文字は少しずつ使い回す
- 3D は見えない画用紙に描いてから、マスに写す
- 3KB の中に、小さなコンピュータを作ることもできる
- 3KB の中で、AI が道を覚えていく様子を見せることもできる
3KB という小さな箱の中でも、工夫しだいでいろいろなことができます。Playload で何か作ってみようと思った方の参考になればうれしいです。
Playload で作られた作品は、こちらのアーケードで遊べます。
最後まで読んでいただき、ありがとうございました。