はじめに

第5回将棋電王トーナメントに出場し、29位となったソフト「mEssiah」の内部構造を公開しようという意図で記事を書きます。
mEssiahはDeepLearningを使用した初の将棋ソフトとなるべく3年前から開発しましたが、残念ならが初にもならずそれほど強くもないということになっています。
しかし、SDT5出場ソフトの中で唯一「DeepLearningを使用しての強化学習」に成功したソフトでもあります。
DeepLearningを触ったことがない方には教師あり学習を行ったdlshogiやねね将棋と大差ないじゃんと思われると思いますが、そこには大きな難易度の差があります。
次回以降の大会のためにまだ成功した手法を公開するのはやめようかとも思いましたが、現状では独力では将棋の神に近付くのは非常に困難であるという認識となりましたので、情報公開を行い、mEssiahの技術をベースにどなたかが将棋の神を作り上げていただきたいという思いと同時に、mEssiah開発者はとても貧乏なので記事を公開したら誰かしらほしいものリストの中のものをくれるんじゃないかという甘い期待も寄せつつ記事を書くことにしました。

ほしいものリストはmEssiah 公式twitter 「messiah_ai」のプロフィールにあるのでぜひ。

mEssiah Spec

開発言語 Java8
DeepLearning部開発言語 C++11
DeepLearning フレームワーク caffe
学習アルゴリズム Triple DQN(λ)
探索 SoftMax探索 
ネットワーク構造 18層 3x3 32フィルター Convolutionネットワーク

構造概要

将棋の基礎部分、ルール等については独自実装。
盤面情報は配列で保持。ビットボードは不使用。

Triple DQN(λ)

基本はDouble DQNに1個追加したものにλを適用したもの。

学習パラメータ設定

割引率1 0.99
割引率2 0.97
割引率3 0.98
λ 0.5
学習開始メモリ 10万
学習ミニバッチ単位 32
ユニット学習イテレーション 1万
オプティマイザー AdaDelta
学習係数 0.001
モーメンタム 0.95
デルタ 1e-8
weightdecay なし
評価サーバミニバッチ数 512

DQN 基本

DQNはDeepMindが発表したDeepLearningを使ってのQ学習の一手法。
特徴としてはExperience Replayという過去の試行結果をメモリしておいて、繰り返し学習に使うという技術と、
Target Networkという、学習時に使う教師値(=試行時の評価値)を一定の学習期間固定して学習の安定性を図るという技術の2本立てです。

将棋の場合はメモリに蓄えるのは

局面A盤面情報
局面Aからの全合法手局面のうち最大の評価値
終局の場合は終局報酬

の3つです。

DQN 試行

試行方策はSoftMax方策、ε-greedyと各種設定値をいろいろためしましたが、ε=0.3で固定が一番成績がよかったです。
これは他の条件が変わると変化する可能性があるので、mEssiahの技術を発展させようとする方はいろいろ試してみてください。

試行は上記の試行方策を使用して自己対局を行いつつメモリを貯める、ということを延々と行います。
本来のDQNでは一定量メモリがたまったところで学習がはじまり、試行しながら学習を行うということをやりますが、mEssiahでは試行フェイズと学習フェイズはきっちり分かれています。それは以下の理由からです。

試行しながら学習を行うと、TargetNetWorkが更新となった場合にメモリに蓄えられている最大の評価値は過去のものとなり、新たに計算しなおさなければいけません。
従来のDQNでは最大の評価値を記録するところは、最大の行動を記録しており、学習時に改めてその評価値を算出する構造となっています。
しかしそれを将棋で行うには非常に遅くなんとかしたいといろいろ考えた結果、いわゆる雑巾絞りと同じように試行、つまり教師作成フェイズと学習フェイズを分けてしまおうという発想でした。
そうすることによって試行時と学習時に同じ評価をせずにすむのでより全体的に速くなります。
デメリットとしてはTarget Networkを更新した場合にメモリを使いまわすことができなくなるので、Experience Replayのメリットが半減することです。
これはどちらがいいのかだいぶ実験しましたが、メモリを使いまわすメリットよりもより速く自己対局→学習のフェイズを繰り返すほうが効果が高いという実験結果でした。

また、試行は32並列で行い、DeepLeaning評価サーバを別スレッドで動かして評価時は評価サーバにキューを投げる、という形で実装を行いました。
32並列というのは、評価サーバのミニバッチ数512をぎりぎり満たすようなスレッド数に調整されています。評価が1回走る間に512局面の評価要求が貯められる、みたいな感じですね。
GPUをもっと早いものを使うのであれば、もう少したくさん並列にしたほうがいいかもしれません。
GPU待ちの間はCPUは何もやっていないのでCPUのコア数よりもだいぶ多いスレッド数を使用しても特に問題はありませんでした。

DQN学習

メモリが10万局面分たまった時点で試行を止めて、学習スレッドが動き出します。
メモリからランダムにデータを取り出して32個づつごく普通に学習するだけです。
1サンプルあたりどのくらい学習を回すか、つまり何epoch回すかはいろいろ試したのですが、
10万サンプルで32ミニバッチを1万回、つまり3.2epochほどがもっとも時間効率がよく過学習もしないことがわかりました。
これを100epochほどやると過学習傾向になり、ミニバッチ数を512とかに増やして学習率をあげるということもやりましたが、32 1万を上回る学習効率は得られませんでした。

TripleDQN

DeepMindが発表したDouble DQNというDQNの発展形があるのですが、効果としては値のスパイク耐性のためとか過学習防止のためとか世間ではいろいろいわれていてほんとのところは何がいいのかさっぱりわかってません。
しかし、DQNよりも性能がよくなることだけは確実なのでmEssiahにも採用することにしました。

Double DQNとはざっくりいうとネットワークが2つあって、Q学習でMaxをとるときにお互いのMaxをとるということをやります。

ネットワーク A
ネットワーク B

があって、現局面がS、Sからの全合法手局面のうちネットワークAが一番いいといってる局面をS'MaxA、ネットワークBが一番いいといってる局面をS'MaxBとします。
そうしたときに以下のように学習します

Va(S) ← Va(S'MaxB)
Vb(S) ← Vb(S'MaxA)

という感じで、お互いのいいといってる局面を交換して、その評価値に近づけるように学習させます。
これをさらに効率化し、マルチタスク学習の発想を使うとひとつのネットワークに2つの出力Va,Vbを用意してやればいいということになります。

で、私がやったのはTripleなので

Va(S) ← Va(S'MaxC)
Vb(S) ← Vb(S'MaxA)
Vc(S) ← Vc(S'MaxB)

となってるだけの話です。
何故3つにしてみたかというと3つだとMAGIだー!って言えるからというしょーもない理由です。
2つを3つにしたからといって精度が上がったかというとそうでもないです。
だた、ひとつだけ工夫した点があって、3つのネットワークを学習する際に割引率を変えています。
割引率が高ければ高いほど終盤の報酬が序盤に伝播しやすくなるけども学習の収束は遅くなり、終盤の評価値の解像度は落ちる。割引率が小さいとその逆になるわけですが両方あればいいとこどりできるのではないか?との発想で割引率を3種類用意しています。
効果があったかというと、結構微妙です。同じ割引率でもよかったんじゃないかと思っています。

DQN(λ)

世界コンピュータ将棋選手権でelmoが行ったelmo絞りの発想を活かせないかと考え、elmo絞りって要するにTreeStrap(λ)でしょ?ということでそれならQ学習にもQ(λ)というものがあるのでやってみようという発想でした。
懸念点としては同じ局面のメモリでもその後の進行によって記憶してる評価値(λ適用後)が違うものができてしまう可能性があるのと、λを適用すると学習が学習方策に依存してしまいQ学習の方策オフ型(学習方策はどんなものであっても最終的には神になれる)というよさが失われてしまうことでした。

TripleDQNにλを追加する実装自体は非常に容易で、元々オンライン学習ではないのでλ収益を前方参照型で計算する必要性がなく、シンプルな後方参照型で計算できるというのが大きかったです。

具体的には1局の試行が終わったあとに1局分のメモリを使って局面Aからの全合法手局面のうち最大の評価値をλ収益に変えてやるという感じです。

DQN(λ)にする際には学習方策はε=0.3ではいまいちで、ここではSoftMax方策、温度0.1を使用しました。
SoftMax方策は全合法手の評価値をボルツマン分布に突っ込む形で確率に変換するのですが、割引率がかかってる関係で序盤と終盤の評価値の絶対値が違い、同じ温度では指し手選択確率のばらけ方が変わってしまうという問題がありました。そこで、一旦評価値を平均0分散1に正規化してからボルツマン分布に放り込んでやることによって、評価値の絶対値がだいたい同じくらいになり、序盤終盤かかわらず意図したくらいの指し手の選択確率のばらけ方になるようになりました。

DQN(λ)は学習序盤は非常に賢くなるのが速いのを確認しましたが、難点であったそこそこ賢くなってからの伸びは期待したほどではありませんでした。

ネットワーク構造

入力特徴

駒種類28x81 = 2268

(効き12方向+飛び効き8方向)x81x先後2 = 3240

持ち駒 76種類 (手番ごとに持ち駒になる可能性のある駒38枚づつ)

手番 1

現局面が王手をかけている局面であるか? 1

駒種類ごとの枚数 盤上 28 (枚数/種類ごとの最大枚数が1次元)

駒種類ごとの枚数 持ち駒 14 (枚数/種類ごとの最大枚数が1次元)

手数32,64,100,150,200に達しているかどうかのフラグ 5

Convolution入力のための余白 37

計5760次元

このうち必ず必要なのは盤面、持ち駒、手番の2345次元のみ。
効きに関しては私が行った実験ではあったほうが精度があがるという結果となった。
それ以外に関してはおそらくあってもなくてもいい。明確な精度の向上は認められなかった。

ここで重要なのは持ち駒情報等2次元情報でないものを一般的なDeepLearningネットワークのように1個づつ全面1とかにしていないところ。
これは私の持論で、Convolutionの有効性はデータの2次元構造を学習することにあるのではなく、単にFull Connectよりも高速にパラメータを増やせることにある、ということに基づいている。
この説の元はmEssiahを開発してるときにcaffeの仕様をよくわかっておらず、本来なら28x9x9という並びで1次元配列にして入力しなければいけないところ、9x9x28と入力してしまっていたのだが、これでも何の問題もなく学習ができていた。
何の問題もなかったので気づくのがだいぶ遅れたのだが、この並び順が逆というのはConvolutionが2次元構造を学習するというのであれば致命的なはずで、もしそうであれば学習がうまくいくはずがない。しかし、学習はうまくいっていたのでこの2次元うんぬんの話は嘘ではないか?という結論に至った。
実際今回のmEssiahは上記特徴入力になっているのにもかかわらず、持ち駒の変化を正しく学習できており、何の問題も出ていない。

学習する上での小細工

強化学習というものは学習最序盤はまったく間違ってる教師データをもとにひたすら学習するのとほぼ変わらないので、はじめからくそ重い学習を回すのはとても非効率です。
ZeroじゃないAlphaGoは人間の棋譜をもとに学習することによって、その非効率なところをショートカットしています。
私も棋譜を使ってショートカットすることも考えましたが学習がうまくいかず(ボナンザメソッドの実装がうまくできなかった)別の方法を模索していました。
そこで考えたのが、はじめは小さいネットワークで学習しはじめて、徐々に層を増やしていく方法です。
転移学習の考え方を流用すればたぶんできるだろうと思ってまず6層ネットワークでLesserKaiに勝てるようになるまで学習させ(約100万局かかる)その後3層追加し、1~6層をロックして学習をさせるということを行いました。
これで再びLesserKaiに勝てるようになるまで約10万局かかりました。そこで1~6層のロックを外して再び学習する、といったやり方です。
なお、100万局学習時の強さは、6層ネットワークでも12層ネットワークでもたいして変わらないという実験結果でした。
ですが12層ネットワークは6層ネットワークで学習するよりだいたい1.5倍~2倍程度の時間を要します。
ですのではじめは少ない層で学習を行って徐々に増やしていく手法は時間的に有効であるという実験結果でした。
ちなみにSDT5 verのmEssiahははじめは6層で3日(100万局)ほど、それから12層でさくら高火力で2週間(1000万局)、その後18層で自宅で2週間(150万局)ほど学習しています。
さくらインターネットさまさまですね。

その他試したこと

方策勾配法による学習

AlphaGoが採用してたり、私の強化学習の師匠であるGA将の森岡さんも使用している方策勾配法も試しました。
しかし、caffeに搭載されているloss layerでは方策勾配法を行うことが困難で、かつ方策勾配法をよく理解できなかったので自作でのloss layerの作成も失敗し、断念するということになりました。その点Chainerだと方策勾配法のサンプルがあったり(DeepLearning強化学習の師匠のmooopanさんが作ってる)するので、容易にできるかもしれません。ですが、私がmEssiahの開発をはじめたころはまだChainerがなかったw 今からはじめるなら私もChainerを選ぶんですけどねぇ。

サイズの大きいネットワーク

128フィルター、256フィルター等の横幅のでかいネットワークも試しました。
GPUをたくさん使うようになり効率UPのような気もしたんですが、驚異的に遅くなる上、上記に書いたとおりネットワークサイズによって学習の進みが速くなったりすることはどうやらないらしいということがわかったので断念しました。
ネットワークサイズのでかさは賢さの上限を上げることには寄与するけども、学習の進行を速めたりはしてくれないというのが重要な発見でした。

教師あり学習

ボナンザメソッドでの学習は上記のように実装に失敗し、断念しました。
そこで次に考えたのがShogi Net方式ですが、これはそこそこ成功しLesserKaiに勝てるようになりました。
しかしそれ以上の伸びはなく、当然のことですが教師あり学習は教師の強さに依存するので公開されている棋譜では限界であると感じました。
同様の方法で学習したと思われるnnやShogi Netが私が実験したものよりも強かったのは単に教師の質が私が使ったものよりよかったのだと思います。
ちなみに、この方式を考えたのは私ですからねw
nnでもShogi Netでもないですよ!w

SoftMax探索

WCSC27で芝浦将棋SoftMaxチームが発表した新しい探索方法ですが、これを見たときにこれしかないとびびっときました。
DeepLearning評価関数を使う際に問題となるのは「重すぎて探索がほぼ不可能なこと」なんですが、それをさくっと解決してくれそうな気がしたので早速実装しました。
詳しい理屈は芝浦将棋SoftMaxチームのアピール文書を見てもらえばいいと思いますが、私がこう理解したということを書いておきます。

通常のαβ探索
探索の1セットは設定された深さを全探索したら終わる。
効率的な枝狩りを行うため、評価関数呼び出しは1局面づつ行えることが望ましい。

SoftMax探索
探索の1セットは新規ノードに当たったところで終わる。1セットが非常に短くてシンプル。
新規ノードに当たったときに全合法手の評価値が一度に必要となるため、たくさんの局面を一気に評価できるほうが有利

SoftMax探索の利点
バッチで評価することにより1局面当たりの評価時間をものすごく短くできるため、一気にたくさんの局面評価値を必要とするSoftMax探索とは非常に相性がいい。
1サイクルが完全に独立して動作できるので並列化が容易

SoftMax探索の弱点
本来探索は評価関数の誤りを補正する役割をするが、その評価関数の精度に探索の効率が依存してしまう。
SoftMax探索と相性のいい枝狩り手法が現在のところまだ開発されていないのでSoftMax方策のみの枝狩りとなるが、温度調整が難しい。

これからの可能性としては、SoftMax探索内部でSoftMax方策以外での枝狩りを行ってより探索効率をあげられる可能性があることがある。
並列化の容易さではLazy SMPをはるかに上回り、モンテカルロ木探索と同等程度なのでこれからCPUのコア数がどんどん増えていく傾向になればSoftMax探索の優位性はどんどん増えていくだろう。
しかし、現状ではSoftMax方策の調整がとても難しいために読み抜けが頻繁に発生するといった問題もある。
Stock Fish型探索のようにヒューリスティックな何かや統計的な何かを追加してやらないことには完成形にはならないと思われる。

まぁ、私は基本的には評価関数のみで神を目指したいので探索はおまけに過ぎないと考えている。なので、SoftMax探索を重点的に研究するといったことはしばらくはないだろう。

以上、mEssiahの内部構造でした。
なお、他にここが知りたいということがあれば、コメントいただければ記事に追記していこうと思います。

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.