ゲームボーイは1989年に発売された携帯ゲーム機で、現代では非公式ながら個人でもゲームソフトを開発することができます。そこで（！？）、ゲームボーイ上で強化学習を行うソフトを試作しました。 レトロなゲーム機と言えど任意のコードが実行できる計算機ですから、強化学習を実装できないはずはありません。本連載では、初めてゲームボーイソフトの開発を行った筆者の視点で、開発に用いたツールやテクニックを解説します。 既存のゲームボーイ用ソフトを現代の強力な計算機上のエミュレータで動作させて強化学習を行う試みは存在します(例: gym-retro)が、これとは異なりゲームボーイのCPUで強化学習を行うソフトが開発された事例はおそらく存在していません。
完成形
MountainCarという、車を左右に加速して旗のところまで到達させる簡単なゲームを解きます。ソフト内にはゲームのルールと強化学習アルゴリズムが実装されており、ゲームボーイ上で試行錯誤を行うことで解き方を発見します。起動した時点ではゲームを解くことができませんが、数十分待っていると解けるようになります。
ゲームボーイ上で強化学習を実装し、MountainCarを解くことができた！MountainCarは、車を左右に加速して旗のところまで到達させるゲーム。ゲームボーイソフトに搭載したAIが、車の動かし方を自力で発見する。実機の速度では、解くのに30分程度。 #ゲームボーイ強化学習 pic.twitter.com/gcwEAP6aZO
— select766@ねね将棋 (@select766) August 27, 2023
TL;DR
ゲームボーイ特有の制約について、主な感想は3点あります。
- 浮動小数点数演算の回避は腕の見せ所。
- メモリを食うデータ構造(Qテーブル)は、事前にRAM容量(8kB)に収まるよう検討が必要。
- 性能にクリティカルな影響がない場所では、printfやmallocのような、贅沢な処理を書いても意外に大丈夫。
使用するツール
- GBDK-2020
- Emulicious
- GBTD
- ドット絵を作成し、GBDKでコンパイルできるCソースファイルに出力できます。
- スプライト（動く物体）のドット絵作成に利用しました。
- Pic2Tiles
強化学習アルゴリズム
アルゴリズムはQ学習で、Q関数にはQテーブルを用います。ニューラルネットワークは用いていません。
Q学習のフォーマルな説明はこちらの資料が参考になります。（31ページ） 強化学習の基礎と深層強化学習（東京大学 松尾研究室 深層強化学習サマースクール講義資料） | PPT
MountainCar環境の説明は公式ドキュメントをご覧ください。
Mountain Car - Gymnasium Documentation
行動は離散的で、左に力を加える、力を加えない、右に力を加えるという3通りです。 観測値は、2つの連続値があります。1つ目はx座標で、[-1.2, 0.6]の範囲です。2つ目は速度で、[-0.07, 0.07]の範囲です。 Qテーブルを構築するために離散化する必要がありますが、今回の実装では、x座標、速度をそれぞれ均等に16分割します。観測値は16×16=256通りとなり、それぞれに3通りの行動のQ値を格納するため768要素のテーブルとなります。
報酬は、1ステップごとに-1で、ゴール(x座標>=0.5)に到達したときに10を得て、エピソードが終了します。オリジナルの環境ではゴール到達時の報酬はありませんが、ゴール到達のインセンティブを高めるために調整を加えた結果となります。
実装
パソコン向けのC言語実装
GBDKではC言語での開発が可能なものの、浮動小数点数(float, double)が使えないなど制約があります。強化学習では、プログラムにバグがなくともハイパーパラメータ設定が誤っていると全く学習が進まないなどデバッグが難しい要素があります。まずは制約のないパソコン向けの環境で実装を行って学習に成功することを確認してから、GBDKでコンパイルできるコードに書き換えることとします。
MountainCar環境の実装
まずはMountainCar環境を実装します。本家のMountainCarのダイナミクスを素直に実装しています。C言語はクラスがないので、MountainCarState構造体で状態を表現し、MountainCarStep関数に状態と行動を与えて状態を進め、戻り値で報酬を得るという形式で実装しました。
mountaincar.h
#pragma once #define MAX_EPISODE_LEN 200 typedef struct { double position; double velocity; int steps; int done; } MountainCarState; typedef int MountainCarAction; // 0=left, 1=nothing, 2=right double MountainCarStep(MountainCarState *state, MountainCarAction action); void MountainCarReset(MountainCarState *state);
mountaincar.c
#include <stdlib.h> #include <math.h> #include "mountaincar.h" double MountainCarStep(MountainCarState *state, MountainCarAction action) { double position = state->position; double velocity = state->velocity; double force = action - 1; velocity += force * 0.001 + cos(3 * position) * (-0.0025); if (velocity > 0.07) { velocity = 0.07; } else if (velocity < -0.07) { velocity = -0.07; } position += velocity; if (position > 0.6) { position = 0.6; velocity = 0.0; } else if (position < -1.2) { position = -1.2; velocity = 0.0; } state->position = position; state->velocity = velocity; state->steps += 1; double reward = -1.0; if (position >= 0.5 || state->steps >= MAX_EPISODE_LEN) { reward += 10.0; state->done = 1; } return reward; } void MountainCarReset(MountainCarState *state) { // uniform random between -0.6 and -0.4 state->position = 0.2 * rand() / (double)RAND_MAX - 0.6; state->velocity = 0.0; state->steps = 0; state->done = 0; }
Q学習の実装
次に、MountainCar環境で動作するQ学習を実装します。QLearningState構造体に、Qテーブルとハイパーパラメータとなるgamma (報酬割引率)、alpha (学習率)、 epsilon (epsilon-greedy法におけるランダムな行動の発生確率)を格納します。TrainEpisode関数を呼び出すことで、1エピソード実行してQテーブルを更新します。ポイントとして、1ステップ進むたびにQテーブルの更新が実行され、行動履歴を記憶する必要がありません。必要なメモリ量はエピソードの長さに依存しませんので、ゲームボーイのようなメモリが少ない環境でも実行が可能です。
qlearning.h
#pragma once #define N_STATE_0 16 #define N_STATE_1 16 #define N_ACTIONS 3 typedef struct { double q_table[N_STATE_0 * N_STATE_1][N_ACTIONS]; double gamma, alpha, epsilon; } QLearningState; QLearningState *QLearningStateCreate(); double TestEpisode(QLearningState *q_state); double TrainEpisode(QLearningState *q_state);
qlearning.c
#include <stdlib.h> #include "mountaincar.h" #include "qlearning.h" QLearningState *QLearningStateCreate() { QLearningState *state = malloc(sizeof(QLearningState)); for (int i = 0; i < N_STATE_0 * N_STATE_1; i++) { for (int j = 0; j < N_ACTIONS; j++) { state->q_table[i][j] = 0.0; } } return state; } static int get_state_index(MountainCarState* state) { int position = (int)((state->position + 1.2) / 1.8 * N_STATE_0); int velocity = (int)((state->velocity + 0.07) / 0.14 * N_STATE_1); return position * N_STATE_1 + velocity; } double TestEpisode(QLearningState *q_state) { MountainCarState state; MountainCarReset(&state); double total_reward = 0.0; while (!state.done) { // choose action MountainCarAction action = 0; int state_index = get_state_index(&state); double max_q = q_state->q_table[state_index][0]; for (int i = 0; i < N_ACTIONS; i++) { if (q_state->q_table[state_index][i] > max_q) { max_q = q_state->q_table[state_index][i]; action = i; } } double reward = MountainCarStep(&state, action); total_reward += reward; } return total_reward; } double TrainEpisode(QLearningState *q_state) { MountainCarState state; MountainCarReset(&state); double total_reward = 0.0; while (!state.done) { // choose action MountainCarAction action = 0; int state_index = get_state_index(&state); if (rand() / (double)RAND_MAX < q_state->epsilon) { // random action MountainCarAction action = rand() % N_ACTIONS; } else { double max_q = q_state->q_table[state_index][0]; for (int i = 0; i < N_ACTIONS; i++) { if (q_state->q_table[state_index][i] > max_q) { max_q = q_state->q_table[state_index][i]; action = i; } } } double reward = MountainCarStep(&state, action); total_reward += reward; // update model int next_state_index = get_state_index(&state); double max_q_next = q_state->q_table[next_state_index][0]; for (int i = 0; i < N_ACTIONS; i++) { if (q_state->q_table[next_state_index][i] > max_q_next) { max_q_next = q_state->q_table[next_state_index][i]; } } q_state->q_table[state_index][action] += q_state->alpha * (reward + q_state->gamma * max_q_next - q_state->q_table[state_index][action]); } return total_reward; }
ハイパーパラメータ調整
main関数を実装し、上記のアルゴリズムを動作させます。プログラムの引数でハイパーパラメータを受け取って学習し、平均報酬を表示します。
main.c
#include <stdio.h> #include <stdlib.h> #include "mountaincar.h" #include "qlearning.h" int main(int argc, char** argv) { srand(1); QLearningState *q_state = QLearningStateCreate(); q_state->alpha = atof(argv[2]); q_state->epsilon = atof(argv[3]); q_state->gamma = atof(argv[4]); for (int epoch = 0; epoch < 10; epoch++) { for (int i = 0; i < 10000; i++) { TrainEpisode(q_state); } double total_reward = 0.0; for (int i = 0; i < 100; i++) { total_reward += TestEpisode(q_state); } printf("Average reward: %f\n", total_reward / 100.0); } return 0; }
optunaを用いて、適切なハイパーパラメータを探索します。
import optuna import subprocess def objective(trial: optuna.Trial): alpha = trial.suggest_float('alpha', 0.01, 0.3, log=True) epsilon = trial.suggest_float('epsilon', 0.01, 0.3, log=True) gamma = trial.suggest_float('gamma', 0.9, 0.999, log=True) x = subprocess.run(["main.exe", f"state_{trial._trial_id}.bin", str(alpha), str(epsilon), str(gamma)], capture_output=True) # 標準出力から報酬を抽出する prefix = "Average reward: " reward = None for line in reversed(x.stdout.decode("ascii").splitlines()): if line.startswith(prefix): reward = float(line[len(prefix):].strip()) break print(reward, alpha, epsilon, gamma) return -reward # minimize study = optuna.create_study() # objective関数が最小値(報酬最大)となるハイパーパラメータを探索する study.optimize(objective, n_trials=100) print(study.best_params)
ハイパーパラメータの探索は数分で完了します。
記事が長くなったので分割します。次回はQ学習のアルゴリズムをゲームボーイ用に軽量化します。
2023-11-03訂正: ソースコード上でランダムな行動を選択する箇所が誤っており、常に行動0が選ばれていました。プログラムの修正およびハイパーパラメータの探索を再実行しました。大きな変化はありませんでした。
修正前
if (rand() / (double)RAND_MAX < q_state->epsilon) {
// random action
MountainCarAction action = rand() % N_ACTIONS;
}
修正後
if (rand() / (double)RAND_MAX < q_state->epsilon) {
// random action
action = rand() % N_ACTIONS;
}
