さくさく理解する Godot 入門（ただし2Dに限る）応用編 Q学習【第1回】

はじめに

本来、Godot はゲーム開発のためのゲームエンジンなのだが、実は試行錯誤を伴う実験的なGUIプログラムも楽に作成することができる。これは Godot の柔軟性が高く、また生産性がとても高いからだ。
本連載では、近年流行りの機械学習の一種である「Q学習」を行ういくつかのプログラムを Godot を使って実装したものを解説する。

なお、Q学習の概念自体は古くから存在するが、Q学習（Q-learning）という名前で今日の手法がまとめられたのは、 1989年のクリス・ワトキンズ（Chris Watkins）の論文に端を発するらしい（wikipedia より）。

Q学習とは

この章では「Q学習」の概要を述べるが、読んでも初見では正確な理解は難しいと思われる。
全体像をなんとなく理解し、この章以降の実装解説を読み、実験してみて、もう一度この章を読めばより正確に理解できるかもしれない。では、行ってみよう！

Q学習では、行動する主体を「エージェント」と呼び、エージェントの状態ごとの可能な行動（アクション）に Q値と呼ばれる数値を割り当て、それをテーブルで管理する（これを「Q値テーブル」と呼ぶ）。例えば、次章で説明する迷路脱出であれば、エージェントが迷路のどの位置にいるかが状態となり、次にエージェントが上下左右どちらの方向に移動するかが４種類のアクションとなる。
通常、可能な状態数はかなり多く、それぞれの状態で可能な行動数は数個なので、状態数 * 行動可能数分のQ値テーブルが必要となる。例えば、迷路脱出であれば、迷路の床数の４倍の要素数の数値配列を用意する。
通常、エージェントは現在の状態の可能な行動のQ値を調べ、最大値を与える行動を選ぶ。例えば、迷路において、ある箇所で右と下に移動可能で、それぞれのQ値が 2 と 5 であれば、Q値の大きい下移動を選択する。そして、行動ごとに次の式（wikipedia より引用）に従って、そのQ値を更新していく。

ここで、Q(s, a) は状態 s で行動 a と取るときのQ値、 αは「学習率 learning rate」で範囲は (0, 1]、 γは「割引率 discount factor」で範囲は [0, 1]、r(t+1) は S(t+1) の報酬だ。

ちょっと何言ってるかわからないと思うかもしれないが、式をよくよく見ると意味がわかってくる。

「Q(s, a) ← Q(s, a) + α*[…]」の部分は代入演算子で書けば「Q(s, a) += α*[…]」ということなので、括弧内を計算し、それに学習率αを掛けたものを足し込んでいる。カッコ内は、「報酬 + γ*移動先最大Q値 – Q(s, a)」で、最初の２項は通常排他的で、Q値の目標とする値だ。それから現在の Q値を引いているので、要するに最適値からの誤差ということだ。なので「Q(s, a) += α*[…]」を延々計算していけば、いつかは Q(s, a) が正しい値（または局所最適値）に収束するということになる。
Q学習におけるQ値の更新方法を、なんとなーく理解していただけたであろうか？最初に書いたように初見で理解するのは通常は難しいので、このあとの解説を読んだり、自分で実験して理解を深めていってほしい。
なんなら、この式の意味を理解していなくても、この通りにコードを書けば、学習がうまくいく場合もある。が、実際にやってみると期待したようには学習が進まないことも多く、式の意味をちゃんと理解していないと問題の原因が特定できず、対処もできないという場合もある。なので、できたらちゃんと理解してコードを書いてほしいと考えている。

迷路脱出

■概要

まずは、最も簡単で学習していることが分かりやすい迷路脱出をやってみる。
下図に迷路のスクショを示す。

左上がスタートで右下がゴールで、スタート地点に配置されているキャラクタが迷路脱出を行うエージェント。茶色っぽいところが壁で、数字が表示されている灰色の部分が床だ。床に書いてある４つの数字は、エージェントがその場所にいる状態でのＱ値を表す。上から順に、上・左・右・下に移動する場合のＱ値だ。緑色のラベルはその中での最大値を表す。

このような単純な迷路は経路探索を行えば、最短経路はすぐに求まるので、なにもわざわざQ学習を行う必要はないのだが、 Q学習とはどんなものなのかを理解するにはよい教材だと考えている。
なお、この迷路脱出プロジェクトは github（https://github.com/vivisuke/QMaze）にあげているので、ぜひダウンロードし、実際に動かしたり、パラメータを変更したりして試してほしい。