【技術Tips】elmo, root learning, descent 3種類の強化学習手法の有効性 を○×ゲームを用いて比較してみた

はじめに

強化学習とは強化学習は、AIが処理した結果に対して「報酬(スコア)」を与え、報酬が最大になる処理方法を学習させる手法です。 引用元:強化学習とは?機械学習との違いなどの用語解説や活用事例などをご紹介

強化学習のゲームでの成功例としてDeepMindによって開発されたAlphaZeroがあげられます。AlphaZeroは人間の事前知識を必要とせず、自分自身と対局する自己対局のみで強くなりチェス、将棋、囲碁でそれぞれの世界チャンピオンプログラムに互角以上のレベルに達しました。AlphaZeroの学習方法は異なるゲームでも同じ学習方法を用いて強くなることができたという点が画期的でした。

今回はAlphaZeroの手法以外の強化学習法である

  • elmo式学習
  • root learning
  • descent

の3つで実験し、どの程度正解の手を選べるのか調べてみました。

elmo式学習

elmo式学習は瀧澤 誠氏により提案された強化学習の手法です。人間の知識を必要としない学習手法でelmoは第27回世界コンピュータ将棋選手権で優勝しました。 ほかの将棋AIソフトも同じ学習手法を用いることで強いプログラムが作成できることが確認できたことから有用性が証明されました。 詳しい手法はこちら:elmoがもたらしたオーパーツについてのブログを参照ください。

root learningとdescent

descentはQuentin Cohen-Solalにより提案された強化学習の手法です。descentもAlphaZeroの学習手法と同様に、人間の知識を必要とせず、特定のゲームに依らない学習手法です。詳しい手法は こちらの論文を参照ください。こちらの論文では

  • tree learning
  • root learning
  • desent

について実験しています。

elmo式学習はroot learningと似た手法です。elmo式学習とroot learningの違いは、学習時の目的関数に深い探索結果だけでなく、自己対局の結果も考慮する点にあります。elmo式学習のほうが性能が良いことが将棋では示されています。 またこの論文では9つのゲームに対してそれぞれの学習手法で学習した結果を比較し、descentが最も強いモデルができることを確認しました。

実験

3種類の学習手法の有効性を試すため○×ゲームで実験を行いました。このゲームを選んだ理由はゲームの状態数が少なく、各局面での勝ち、負け、引き分けが容易に分かるためです。

実験に使用したソースはこちらで共有しています。

○×ゲーム

○×ゲームとは3x3のマスを用意して、順番に○、×を書き込んでいくゲームです。○×のどちらかが縦横斜めのいずれかに3つ並べることができるか、またはすべてのマスに○×を書き込んでしまったらゲーム終了となります。縦横斜めのいずれかに○×を並べることができたら並んだ方の勝ちで、どちらも並べることができず、マスが埋まってしまった場合引き分けとなります。このゲームは双方が最善を尽くすと引き分けになることが知られています。 ゲームの詳細はこちらを参照ください。

○×ゲームの状態数は5478通りあることが確認されています。(参考) 今回作成したプログラムでも同様の検証を行い、結果が一致したので正しいそうだと考えられます。

図1:初期局面

図2:お互いに1回ずつ○×を書き込んだ後

図3:終了局面

モデルの性能評価方法

学習によってどの程度モデルの性能が上がっているのかを調べるため、モデルの更新が終わった各タイミングでテストデータによる評価を行いました。 テストデータはゲームで存在しうる全局面(5478局面)に対してモデルの評価を行い、その値に対して次に説明するルールにしたがいラベルに変換しました。テストデータのラベルとモデルが出力した結果を変換したラベルが一致しているかどうかの正解率にて評価を行いました。

モデルの出力をラベルに変換するルール

  • [ -1.0, -0.2 ):負け
  • [ -0.2, 0.2 ]:引き分け
  • ( 0.2, 1.0 ]:勝ち

実験時の条件

学習時の条件は下記表のとおりです。

各学習手法で共通条件

  • 最適化手法:AdamW
  • 学習率:1e-4
  • エポック:30
  • ミニバッチサイズ:128
  • 自己対局の際の着手の選択方法:ε-greedy法(ε=0.2)
  • 自己対局→モデル更新の回数:32回
  • 自己対局時の1着手を選択するためのシミュレーションの回数:25

root learning

  • 自己対局の回数:1000

elmo式学習

  • 自己対局の回数:1000
  • lambda:0.7

descent

  • 自己対局の回数:10

実験結果

モデルの性能をプロットした結果は下記のとおりです。いずれの学習手法も○×ゲームは難易度が低くすぎたようで、1回目の学習が終わった時点で正解率が80%を超えており、その後学習を継続しても正解率はあまり変化しませんでした。

elmo式学習とroot learningはほぼ同じ正解率でしたが、若干elmo式学習のほうが正解率が高いことが確認できました。

descentは正解率が最大で98%となり他の学習手法と比較すると性能が良いことがわかりました。

図4:学習結果

考察

root learningとelmo式学習の正解率が80%前後にとどまり、descentのように90%以上の正解率に達しなかった原因について考察しました。

elmo式学習で判断を間違えてしまった局面の一例を確認してみます。

図5:間違いの例1

図6:間違いの例2

model_outputがモデルが出力したスコアでlabelが前述の条件に従ってラベル化した値、正解の値がanswerとなります。 いずれの例も勝ちまたは負けが簡単にわかる局面で引き分けと判定してしまっています。

原因として、自己対局時の棋譜に偏りが生じてしまったのが原因だと考えられます。自己対局は学習中のモデルを用いて棋譜を生成していきます。なので学習中のモデルは学習が進むに連れ、勝ち負けがはっきりわかった局面(=難易度低の局面)は学習が進むに連れ選ばれないようになっていきます。図7で示したとおり学習1回目では様々な難易度の局面が現れますが、学習2回目、3回目と進むごとに自己対局の棋譜の内容が難易度が高い局面が増えていくことが予想されます。

図7:自己対局時の棋譜の推移

一方モデルの更新は自己対局の棋譜を元に行われるため、モデルの更新に使用する局面が難易度高、中に偏っていくことになります。図7で示したように学習1回目では様々な難易度の局面を学習対象としていましたが、学習2、3回目と学習が進むにしたがって難易度高、中に偏っていくことが予想されます。そのためモデル更新を実施していく中で難易度低の局面の結果が変わってしまったことが原因だと考えられます。

まとめ

今回は以下の3種類の強化学習を実装し、○×ゲームで学習させ、どの学習手法が最も性能の良いモデルを作成できるか検証しました。 検証した結果、descentが○×ゲームの全局面に対する98%の局面で正解することができました。 またroot learning、elmo式学習がdescentよりも性能が悪かった原因について考察し、自己対局時の局面の偏りが原因ではないかと考察しました。 次回はどうぶつしょうぎや6x6のオセロなどもう少し難しいゲームで実験してどのような結果になるか試してみたいと思います。

記事執筆者

*

宇賀神 拓也

パーソルキャリア株式会社
テクノロジー本部 デジタルテクノロジー統括部 デジタルソリューション部 フロントアプリエンジニアグループ

前職ではベンチャー企業で音声を使ったAIのサービス開発を担当し、フロントエンド、バックエンドを広く浅く経験。パーソルキャリア入社後はデータエンジニアとして、AIを用いたアプリケーション開発に携わっている。