TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

リバーシ(オセロ)で深層強化学習 その3(DQN)

前回DQNのネットワークを教師ありでQ学習で学習した。
今回は、DQN強化学習で学習する。

実装するアルゴリズムは、Nature に掲載された論文「Human-level control through deep reinforcement learning」に基づく。
DeepMindによる公式の実装は、TensorFlowもPyTorchもない時期なので、LuaJITとTorch 7.0で実装されている。

今ではTensorFlowかPyTorchで実装する方がよいので、分かりやすいチュートリアルが提供されているPyTorchの実装を参考にすることにした。

OpenAI Gymについて

PyTorchのチュートリアルは、OpenAI GymのCartPoleをDQNで学習するサンプルになっている。
強化学習は、環境とエージェントの相互作用で学習を行うが、環境とエージェントのインターフェースを統一することで、それぞれ差し替えて実験するのが容易になる。
そのために、OpenAIがインターフェースを定義して、CartPoleやその他の強化学習の研究で使用される代表的な環境を提供している。

リバーシのOpenAI Gymインターフェース

残念ながら、OpenAIではリバーシの環境は提供されていない。
そこで、リバーシのOpenAI Gymインターフェースを、creversiに実装した。

リバーシに合わせた変更

PyTorchのチュートリアルは、OpenAI GymのCartPole向けになっているので、リバーシに合わせて変更が必要になる。

エピソード完了後に学習

CartPoleでは、ステップごとに報酬が得られるが、リバーシではゲームの終了まで報酬が得られない。
リバーシでもステップごとに学習を行うことも可能だが、効率が悪いためエピソード終了の区切りで学習を行うことにする。
1回ごとに学習するよりも、数エピソードごとに学習した方が学習が安定するため、16エピソードごとに学習することした。

DQNでは、方策に使用するネットワーク(policy_net)と、価値を推定する際の使用するネットワーク(target_net)が分かれている。
policy_netは毎回学習し、target_netは一定間隔ごとにpolicy_netからパラメータがコピーされる。

CartPoleのサンプルでは、10ステップごとにコピーを行っているが、64エピソードごととした。

学習間隔とpolicy_netからtarget_netへのコピーの間隔は、チューニングが必要なハイパーパラメータになるが、今回は適当に決めている。

ミニマックスを考慮した行動価値

DQNで使用されるQ学習は、1ステップ後の行動価値の最大値を使用するが、リバーシでは1ステップ後は相手の手番のため、行動価値の符号を反転する必要がある。

割引率

DQNでは、1ステップ後の行動価値に対して割引を使用するが、ボードゲームでは割引を使用しないで学習することが多い。
AlphaZeroでも、終端の報酬を割引なしで学習している。
そのため、割引率は高めの0.99とした。

εグリーディー

DQNの方策には、εグリーディー戦略が用いられる。
基本は、policy_netで行動価値が最大となる行動が選択されるが、一定の割合εでランダムに行動が選択される。
強化学習では、すでに価値が高いとわかった行動を優先して探索するが、まだ探索していない行動の方がより価値の高い可能性があるため、未知の行動の探索も必要である。
εグリーディー戦略では、一定の割合εでランダムな行動を選択すること、探索と活用のバランスをとる。

εは、はじめに高めで、徐々に小さくしていくと良いことが知られている。
チュートリアルでは、
\displaystyle
\varepsilon_{end} + (\varepsilon_{start} - \varepsilon_{end}) \cdot \exp(-\text{steps_done} / \varepsilon_{decay})
という式が使用されている。
ここで、\varepsilon_{start}\varepsilon_{end}\varepsilon_{decay}は定数で、それぞれ

\varepsilon_{start} = 0.9 \\
\varepsilon_{end} = 0.05 \\
\varepsilon_{decay} = 200
という値が使用されている。

グラフにすると、

のようになり、\varepsilon_{start}から徐々に小さくなり、\varepsilon_{end}で一定になる。
\varepsilon_{decay}は、小さくする速度を制御している。

リバーシでは、ステップ数をエピソード数に置き換えて、\varepsilon_{start}\varepsilon_{end}は、同じ値を使用し、\varepsilon_{decay}は2000とした。

学習結果

教師ありのQ学習では、1万ステップ学習してもランダムよりも強くならなかった。
そのため、最低でも1万ステップ以上は学習する必要があると思われる。
そこで、一旦1万ステップ(16万エピソード)の学習を試すことにした。

損失

損失のグラフは以下のようになった。

はじめ順調に下がった後、上昇してまた下がっている。
まったく学習できていないわけでもなさそうである。

強さ

ランダムと1000局対局して強さを測定した。
597勝368敗35分という結果になった。
信頼区間95%の勝率は、64.9~58.8%で、ランダムより有意に強くなっている。

学習時間

16万エピソードの学習にはGeForce 2080Tiを使用して、約14時間かかった。

まとめ

リバーシで、DQNを用いて強化学習することで、ランダムより強くできることが確認できた。

リバーシは、ルールがシンプルで60手で必ず勝負がつくので強化学習の勉強題材としては良いのではないかと思う。
将棋ではDQNがまった学習できなかったので、とりあえずランダムより強くなるという結果がでて良かった。

シングルスレッドでシングルゲームを繰り返しているので、ゲームを並列実行することで学習時間は短くできるはずである。
他のアルゴリズムを試す前に、並列実行を実装したい。

その後、DDQNなど他のアルゴリズムも試したい。
あと、GUIソフトと連携させて人間とも対局できるように、プロトコルも実装するつもりである。

ソース

実装したDQNのソースは、こちら。
creversi_gym/dqn.py at master · TadaoYamaoka/creversi_gym · GitHub