簡単に実行できた! "強化学習 DQN vs ゲーム 2048"

#0. まえおき
強化学習をやってみたいと思うものの、なかなか難しくて手が出ないということがあると思います。その理由は：

• 理論が難しい、故にコードを書くのも難しい
• ディープニューラルネットワークも必要
• 環境構築が大変

の三重苦じゃないかなと。
今回は最新版のMATLAB R2020bを使ったら、案外簡単にゲーム x 強化学習が実装できたのでシェアします。ゲームの状態と報酬を得られる状態にあれば、今回ご紹介する枠組みでゲームに強化学習を適用することができます。

##0.1 強化学習とは
強化学習における役者は以下の2つです:

• エージェント - 行動する主体 (方策と強化学習アルゴリズムを持つ)
• 環境 - 行動が加えられる客体。それに伴って状態を(確率的に)遷移させる

重要なポイントは

• 状態は観測可能でなければならない
• 報酬は環境の遷移により決まり、行動の良さの評価
• エージェントは状態を見て、方策に従って次の行動を(確率的に)決定する

です。詳しいことは [強化学習入門 複雑な強化学習をMATLAB x Simulinkで簡単に!] (https://www.mathworks.com/videos/introduction-to-reinforcement-learning-matlab-and-simulink-makes-complex-rl-simpler--1603913259072.html?s_tid=srchtitle) などを見ると良いと思います。

##0.2 ゲーム 2048 について

###0.2.1 ゲームのルール

• ブロック全体を上下左右に動かします、同時にランダムに2 or 4の数値のブロックが生成されます
• 同じ数を重ねることができ、重ねるとブロックが1つに集約されて数値が2倍になります
• ブロックが集約されるたびに得点が入ります
• ブロックが埋まってきて、身動きが取れなくなったらゲームオーバー

有名なゲームのようで、無料でオンラインでプレイできるものが沢山あります。今回は強化学習の環境としてこのゲームを使います。つまり、強化学習を適用し、このゲームを攻略して人間以上のスコアを出せるようにする のが目標です。

ゲームのイメージをご覧になりたい方は下の方にGifで動画を入れていますので、そちらをご覧ください。

##0.3 利用ツール

強化学習の要素	設定	ツール
環境	2048 MATLAB Edition (4x4 ボードゲーム)	File Exchangeから入手
アルゴリズム	DQN	MATLAB R2020b, Reinforcement Learning Toolbox
ニューラルネットワーク	デフォルト	MATLAB R2020b, Reinforcement Learning Toolbox
報酬	ゲーム得点 + 移動 +消したブロック - 移動無し	試行錯誤により決定

ニューラルネットワークの設定がデフォルトで準備されていたので、非常に楽ができました。

#1. 強化学習の学習準備 with MATLAB
MATLABで強化学習を学習させるには以下のコマンドを実行します:

train(agent,env,opt)

コマンド中、agentはエージェントのオブジェクト、envは環境のオブジェクト、optは学習のオプション設定です。従って、前者2つを準備することが本質です。

次の流れに沿って準備をしていきます。

1. 準備 - ゲーム2048から状態量 (ブロックの位置と数、得点) を取り出す
2. 環境の設定 (env) - 観測される状態量と加えられる行動の設定、状態遷移と状態リセットの指定
3. エージェントの設定 (agent) - 学習方策の指定、Critic (Q関数を近似するネットワーク) の作成・指定、Criticの学習方法の設定

##1.1 ゲーム 2048 からの状態量取り出し
全ボードの状態とスコアは2048のゲームオブジェクトのメンバとなっているので簡単に取り出せます:

% ゲームのオブジェクトを作成
gameObj = Game2048();

% ボードの状態を取得, ただし NaNは0で置き換え
state = gameObj.Game.Board;
state(isnan(state)) = 0;

% 報酬
reward = gameObj.Game.Score;

ただし、gameObj.GameはメンバにScoreを元々は持っていません。その代りgameObj.Game.Scoresという得点履歴を持っています。1つの行動に対しての得点を獲得したいので、得点履歴の差分からScoreというメンバをゲーム側のクラスに加えました。また、カプセル化されたクラスのアクセス権も変更して、上記の情報を取り出しています。

このあたりは、他のゲームにも強化学習を応用できることをご紹介するのが本質だと思うので、step by stepで言及しません。

##1.2 環境の設定
今回の 環境 自体はゲーム側で提供されるので、環境構築は省略できます。そのため残りの作業は4つ:

• 状態観測のインターフェースを作成する
• 行動のインターフェースを作成する
• 行動を取った後に、その状態遷移から報酬を定義する ステップ関数 を作成する
• エピソードを終了させて、環境をリセットする リセット関数 を作成する

###1.2.1 状態と行動のインターフェース作成
環境のインタフェース (状態と行動の) を作成して、強化学習アルゴリズムに接続できるようにします。
状態と行動のインタフェースを作成する関数は2種類あります。離散値か連続値かで関数が変わります。
今回は観測される状態は、状態数が多いので連続値として扱うことにしました（数え上げるのが大変なので）。また、行動に関しては上下左右の4通りなので離散です。

• 離散: rlFiniteSetSpec
• 連続: rlNumericSpec

% 状態観測 - 数え上げられない
ObservationInfo = rlNumericSpec([16 1],'LowerLimit',zeros(16,1),'UpperLimit',2048*ones(16,1));
ObservationInfo.Name = 'Board State';
ObservationInfo.Description = 'grid of (4 x 4)';

% 行動 - 数え上げます
ActionInfo = rlFiniteSetSpec([1 2 3 4]);
ActionInfo.Name = 'Board move';
ActionInfo.Description = 'up, down, right, left';

スクリプト内の*.Nameや*.Descriptionは無くても良いです。可読性を上げるために付け加えました。状態観測は4x4のボードなので、[16 1]のベクトルとしました。

###1.2.2 ステップ関数とリセット関数の作成
今回はこのあたりを読みながら、これらの関数を定義しました。
リセット関数のフォーマットは以下です:

[InitialObservation,LoggedSignals] = myResetFunction()

• InitialObservation: 初期の環境の状態
• LoggedSignals.State: 環境の状態遷移履歴を保存する。初期の状態も登録して返す。

ステップ関数のフォーマットは以下です:

[Observation,Reward,IsDone,LoggedSignals] = myStepFunction(Action,LoggedSignals)

• Observation: 状態遷移後の状態。2048ゲームならボードの数値と位置。
• Reward: 状態遷移によって得られた即時報酬。
• IsDone: エピソード終了フラグ。2048ゲームならゲームオーバーなど。
• LoggedSignals.State: 環境の状態遷移履歴を保存する。

なお、リセット関数やステップ関数に、フォーマットには無い引数を与えることも可能です。その場合は関数を関数ハンドルにします。たとえば

[InitialObservation,LoggedSignals] = myResetFunction(arg1,arg2)
[Observation,Reward,IsDone,LoggedSignals] = myStepFunction(Action,LoggedSignals,arg1,arg2)

だった場合は、

ResetHandle = @()myResetFunction(arg1,arg2);
StepHandle = @(Action,LoggedSignals) myStepFunction(Action,LoggedSignals,arg1,arg2);

としてあげれば、見かけ上の引数は元の関数のモノと同じになります。
参考までに私が作成した2048ゲーム用の関数を以下に貼り付けます：

2048用のリセット関数の設定

function [InitialObservation, LoggedSignal] = myResetFunction(gameObj)
    
    if (gameObj.Game.isGameOver() || gameObj.Game.isGameWon())
        gameObj.newGame(); % reset the state
    end

    state = reshape(gameObj.Game.Board,16,1); % Get Board status
    state(isnan(state)) = 0; % replace NaN with zero
    LoggedSignal.State = state;
    InitialObservation = LoggedSignal.State;
end

2048用のステップ関数の設定

function [NextObs,Reward,IsDone,LoggedSignals] = myStepFunction(Action, LoggedSignals,gameObj)
    % Action
    % 1-up, 2-down, 3-right, 4-left
    
    % Check if the given action is valid.
    if ~ismember(Action,[1 2 3 4 ])
        error("Action must be [1,2,3,4] corresponding to [u,d,r,l]");
    end    
    
    switch Action
        case 1
            movement = 'up';
        case 2
            movement = 'down';
        case 3
            movement = 'right';
        case 4
            movement = 'left';
    end
    
    % State before move
    statePre = reshape(gameObj.Game.Board,16,1);
    statePre(isnan(statePre)) = 0; % replace NaN with zero
    
    % Move
    gameObj.Game.move(movement);
    
    % State update
    state = reshape(gameObj.Game.Board,16,1);
    state(isnan(state)) = 0; % replace NaN with zero
    
    % Check if it has moved
    if LoggedSignals.State == state
        noMove = true;
        noMovePenalty = -36;
    else
        noMove = false;
        noMovePenalty = 4;
    end
    
    LoggedSignals.State = state;
    
    % Next Observation
    NextObs = LoggedSignals.State;
    
    % Check terminal condition
    IsDone = gameObj.Game.isGameOver() || gameObj.Game.isGameWon() || noMove;
        
    % Zero bonus
    zeroDiff =  sum(state==0) - sum(statePre==0);
    if zeroDiff >=0 && ~noMove
        zeroBonus = (zeroDiff + 1) * 4;
    else
        zeroBonus = 0;
    end
    
    % Reward shaping
    Reward = gameObj.Game.Score + noMovePenalty + zeroBonus;    

さて、ステップが4つ終わりましたので、環境を強化学習用に設定します。

env = rlFunctionEnv(ObservationInfo, ActionInfo, StepHandle,ResetHandle);

これで環境envが出来上がりました。

##1.3 エージェントの設定
嬉しいことに、agentの作成は非常に簡単です。1.2.1で作成した、状態と行動のインタフェースをエージェントオブジェクト作成関数に与えてあげれば終わりです:

agent = rlDQNAgent(ObservationInfo,ActionInfo);

今回は状態や行動の離散・連続を考慮して、DQNをアルゴリズムとして採用しました。選択方法の基準はこちらに書いてあったので、参考にできます。

さて、ここで色々と疑問がわいてくるかと思います

• エージェントの設定簡単すぎないか？
• ディープニューラルネットワークの設定していないぞ!?
• ネットワークの学習のオプションは?!

その通りです。この辺は全てすっ飛ばしましたが、デフォルトで既に準備ができています。もちろん、ご自身のアプリケーションに応じてカスタマイズできるということですが、とりあえずこれだけで使えるようになるってのが 楽だな と思いました。MATLAB R2020bからの機能だと思います。
以下で、詳細を調整する部分をご紹介します。

###1.3.1 Critic (Q関数を近似するニューラルネットワーク) の設定
先ほど書いたように、agentにQ関数を近似するためのCritic、つまりディープニューラルネットワークが既に設定されています。取り出して確認します。

% agentからcriticを得る
critic = getCritic(agent);

% ネットワーク部を確認
criticNet = getModel(critic);
plot(criticNet);

このネットワークが気に入らなければ、他のものを設計して、次のようにagentに設定することができます：

setCritic(agent,critic)

このCriticですが、いわゆるディープニューラルネットワークですので、学習時のオプションの設定もあります。デフォルトで数値が入っていますが、カスタムしたい場合は

critic.Options.LearnRate = 0.00025; % 学習率
critic.Options.GradientThreshold = 1; % 勾配クリップ
critic.Options.L2RegularizationFactor = 0.00005; % L2ノルムでの正則化の係数

のように設定が可能です。

###1.3.2 エージェントの詳細設定
上記で生成したagentオブジェクトですが、学習時の方策の設定なども重要なポイントだと思います。
例えばε-greedy方策の設定は

agent.AgentOptions.EpsilonGreedyExploration.Epsilon = 0.95;
agent.AgentOptions.EpsilonGreedyExploration.EpsilonDecay = 0.0001;
agent.AgentOptions.EpsilonGreedyExploration.EpsilonMin = 0.1;

のように設定ができます。これは$i$ エピソード目の状態$s$における、最適行動以外の行動$a$をとる確率を次のように規定します。学習初期は探索に比重を置くので、この値は大きい方が良いです:

\pi(a|s) = \epsilon(1-decay)^i \quad \text{,where}\quad \forall a \ne \max_{a} Q^{(i)}(a,s).

この他にも、報酬の割引率は

agent.AgentOptions.DiscountFactor = 1;

と設定できます。詳細は、DQNエージェントの設定を行う関数をご参照ください。今回はDQNを使っていますが、用いるエージェント（アルゴリズム) によっても設定項目は異なりますので、ある程度の理論部分の理解は必要だと思われます。

#2. 学習
冒頭でお伝えした通り、MATLABでの強化学習の学習コマンドは

trainStats = train(agent,env,opt);

でした。このうちagent, envは上で作成済みです。では最後の、optの設定に移ります。

##2.1 学習オプション設定
　私が使ったオプションの例です:

opt = rlTrainingOptions("MaxEpisodes",15000,...
    "MaxStepsPerEpisode",550,...
    "StopTrainingCriteria","AverageReward",...
    "StopTrainingValue",50000,...
    "UseParallel", true,...
    "ScoreAveragingWindowLength",50);

強化学習の理解がある方でしたら、ほぼ何のオプションか理解ができると思いますので、詳細は避けます。
1つおススメなのは、UseParallelです。読んで字のごとく並列計算を実行してくれます。私のラップトップだと4プロセス立ち上がって計算を実行できました。強化学習は膨大なくり返し計算が必要なので、実際に学習をしてみて思ったのは 並列計算は必須 だと。
この並列計算ですが、並列処理をするというのはトリッキーな部分もあると思うので、詳細な設定が必要な場合はTrain Reinforcement Learning Agentsを読まれることをおススメします。

##2.2 学習実行
実際に学習をするとこんな感じです。(デモンストレーション用にブロックを動かすようにしていますが、実際の学習中は描画に時間がかかるので、ブロックの動きはoffにしています)

#3. 強化学習を用いたゲーム2048のパフォーマンス
1-2週間かけてこれに取り組んだのですが、なかなか良い方策を得ることができていません。人間様に勝てるどころか、3歳児にも勝てるか怪しいレベルまでにしか持ち込めていません (3歳児にランダムにやらせると1000-1500点)。ちなみに、四則演算ができる小学1年生は5000点以上獲得していました。

##3.1 学習済み方策を使ったシミュレーション結果
シミュレーションの実行は次のように行います:

simOpts = rlSimulationOptions('MaxSteps',200,"NumSimulations",1);
experience = sim(env,agent,simOpts);

スクリプト内のexperienceはシミュレーションの経緯の情報が入っています。今回はMaxStepsにしていますが、実際には$80$程度で止まっています：

この理由は、80ステップの時点で次の行動としてボードが動かないような選択をエージェントがしており、MaxSteps数に達するまで、ひたすらその行動を取り続けて終わっているということです。
実は、この点が今回の一番の課題でした。つまり、ある時点で 最適な行動として動かない ものが選択され続けると、そのまま何も起こらないということです。

報酬をかなり色々と工夫しましたが、この点が上手く回避できる学習をすることができませんでした。ひょっとしたらネットワークのユニット数を増やしたりすれば、もう少しQ関数の近似の精度が上がって、良いものができたのでは？とも思います。

##3.2 今後の課題
設定した報酬を紹介します。この設定によって、得られる方策や学習の収束具合がかなり変わってくることが分かりました。

• ゲームから返ってくる直接的な得点
• 動く事で消すことができたブロック数 $\times 4$
• 動くという行動 $+4$
• 動かない場合　$-36$

この辺のチューニングでパフォーマンスが変わるかどうか？は詰め切れていません。ただ、当初からするとかなり報酬の設定も変わりました。報酬shapingは非常に重要で、試行錯誤が必要 だと身をもって経験できました。

また、今回はDQNというアルゴリズムを使ったため、経験リプレイという仕組みでCriticネットワークをアップデートしていました。その際に使うデータの数を増やすとアップデートが安定するということが分かりました。ただ、計算負荷がかかるのでラップトップでやるには厳しさを感じ、aws上での計算に現在取り組んでいます。