目標
自分の勝てないレベルを目指す(私自身はオセロが強いわけではない)
Alpha Zeroとは
2017年にGoogleが人間の知識を全く使わずに、囲碁の世界チャンピオンよりも強い囲碁のプログラムを発表した(AlphaGo Zero)。その1年後、ほぼ同じアーキテクチャーでチェスや将棋においてもたった1日の学習で世界最強レベルのコンピュータ(もちろん、人間より強い)を超えることができると発表し、大きな話題となった(Alpha Zero)。
なぜオセロ?
まず、囲碁や将棋、チェスだと単なるトレースなんで面白くない。また、これらは複雑すぎるのでgoogleほどの計算資源がないと現実的な計算時間で強くするのは難しい(私のPCのスペックで真似すると1年かかっても終わらない)。その点、オセロならみんな知ってるし、適当な複雑さのゲームなので選んだ。
Alpha Zeroの概要
Alpha Zeroは自己対局を通じて強くなっていく強化学習プログラムである。Alpha Zeroは自己対局→学習→自己対局→学習を繰り返すことで強くなっていく。学習するものは自己対局で実際に現れた、各場面における手の選択(の確率密度分布)とその後の結果である。自己対局の結果を学習するため、自己対局はある程度読んで行わないと意味がない。その「読み」にはMonte Calro Tree Search(MCTS)という手法が使われている。MCTSは学習した手の選択と選択後の状態の手の価値に基づいて読みを行う。また、探索が狭くならないように、訪れていない状態が読まれやすいようにしている。
環境
最初はGoogle colabolatoryでやってたが、CPUの並列性能がほしかったので、パソコンを買った。スペックは以下のとおりである。
GPU:GeForce1080X
CPU:Ryzen 7 2700X(8コア16スレッド)
実装
ここに書くには長すぎるでコードは割愛する(詳細は私のgithub参照)。今回の実装はDeep reinforcement learning Hands-Onを参考にpythonで行った。ちなみにこの本は深層強化学習全般の実装が解説されており、英語に抵抗がないなら一読の価値はあると思う。この本では、connect-4(4目並べ)をAlphaGo Zeroで実装しているため、それをオセロ用、並列化用に書き換えて学習を行った。なお、この本での実装では
- L2正則化を行っていない
- 選択していない手のMCTSのsub treeを残している
の二点がAlphaGo Zeroの原論文と異なるため、原論文に合わせた修正を行っている。また、AlphaGo Zeroでは学習後、今までの最新モデルと自己対局を行い、一定以上の勝率をあげないとモデルの更新を行わない。しかし、Alpha Zeroでは毎回モデルの更新を行うと書いてあるため、本実装では学習のたびにモデルを更新している。また、Alpha Zeroは将棋やチェスに対応するため、碁にある対称性を利用していないが、オセロは碁と同じように対称性があるため、回転と反転に関しても同様の結果になるとして自己対局の結果に加えている(生成する自己対局数が単純に8倍になる)。では、主な設定を挙げていく。
- 用いるニューラルネットはAlpha Zeroと同じ構造
- 各手のMCTSは800回(Alpha Zeroの論文と同等)
- 自己対局で生成するゲーム数は300ゲーム(15CPU並列で20ゲームずつ、対称性考慮で2400ゲーム、Alpha Zeroでは25000)
- 保存する手の数は150万(1対局約60手として25000ゲーム、Alpha Zeroでは50万ゲーム)
- 1回のトレーニングは64バッチ×32回を1セットとしてそれを500回繰り返す(Alpha Zeroでは1000回繰り返し)
- 学習率は0.01(Alpha Zeroでは0.2から始めて一定回数に達すると1/10にしている)
- 自己対局の始めの20手はランダム性を加える(Alpha Zeroでは30手、オセロが囲碁や将棋、チェスに比べ短手数なため)
また、これに加え、自己対局結果保存の際に割引率0.95を設定している。これは、私自身が対局した時に、初期に意味もなく高い評価値になっている場合があったためである。おそらく十分な自己対局数があれば偏らないと思われるが、Googleのように5000TPUを持っているわけではないので、自己対局数を増やすのは現実的でない。そのため、初期の評価値が偏りすぎないように、割引率を設定した。
学習結果
下のグラフにlossを示す。10kあたりからあまり強くなっていないため、ここらへんで学習率を下げるなど、まだまだ改善の余地がありそう。
1日くらい学習したあと(対局→学習を20回程度繰り返したあと、下のグラフの10kあたり)に対戦したら全く歯が立たなかった。MCTSの探索数を少なく(320MCTS)して対戦すると1手先で負けているパターンを読めずに勝てることがあったが、基本は勝てる気がしない。また、探索数を1600MCTSにしてスマホアプリのリバーシLv99とやるとLv32までは勝てた(そのあとはまだ対戦していない)。後手の方が強い気がする。githubにGUIも公開しているので試してみた感想をいただけると嬉しい。なお、GUIはバグが取り切れていないため、たまに止まったりするがご容赦いただきたい。
参考
あまり調べてないですが、Alpha Go Zeroでの実装は既出のようです。