ChainerでDQN。強化学習を三目並べでいろいろ試してみた。contentChainerでDQN。強化学習を三目並べでいろいろ試してみた。update.初めてのQiita投稿です。Ridge-iという会社で機械学習を中心としたコンサル~開発をしてます。実装して教材を作りました。ちなみに強いプレーヤー同士ならば、ドローだけが繰り返されるはずです。(WarGameの有名なやつですね。更新式の設計に気を遣う。色々な落とし穴が多数。最適なトポロジーがわからん。Reluにするまで最弱。教え方ミスると何も学習しない。Q-Learningまでの実装は1-2時間位しかかからなかったのに、DQNがきちんと学習するようにするだけで6時間くらいかかりました。(泣)学習の効率化という面ではきちんと盤面の反転と回転をするとよいのですが、今回は分かりやすさ重視で抜きました。あと、きちんとインターフェース設計と変数の隠匿化をしなかったので時々違反してます。そのあたりは無視してください。Githubはこちら。https://github.com/narisan25/TTT-RL理論的な詳細を知りたい場合は別途連絡ください。指摘・改良・アドバイス、大Welcomeです。三目並べの設計これはざざっとやります。盤面0-9の配列にXなら1、ブランクなら0、○なら-1を入れます。self.player_turn=self.player_xゲームの進行役Observer+Mediatorモデルにします。これでPlayerが直接盤面をいじらないようにしつつ、ターン・勝敗・表示の管理などを行います。置けるところに置くだけのシンプルなやつです。lost...")まずは人間とランダムで戦わせてみます。RandomHuman:0,Random:1,DRAW:0なんと、ログに残っていたのは気を抜いて負けた例でした。Random)さすがにただのランダムだとつまらないので、次の手で勝てるところがあればきちんと指すようにします。acts[i]モンテカルロさて、ここからが強化学習領域に入ってきます。モンテカルロでは、あるポリシーに沿って一定回数をゲーム終了まで試し、その勝率を見ることでいい手を探索します。モンテカルロの重要な点は、「一定回数」の数と、「あるポリシー」によって強さが左右されること。「あるポリシー」には、先ほどの改良ランダム君を使いました。「一定回数」は試したところ100回を超えれば、まず間違った手は打たないようです。50回くらいだと、乱数次第で時々負けたりします。ここから実績を動的計画法に持ってったり、モンテカルト木探索(MCTS)に派生して強いポリシーと弱いポリシーを組み合わせる方法もありますが、今回は言及しません。GameM1:0,M2:2,DRAW:8大体ドローですね。気が向いたら試行回数を100回にして試してみてください。全部ドローになると思います。Q-Learningさて、強化学習といえば、Q-Learning。勝ったら+1、負けたら-1、引き分けは0です。それをベースにQ(s,a)のDictionaryを以下の更新式で更新していきます。重要なのはε-greedyというコンセプトでランダムの打ち手を推奨すること。optimumに陥ります。最初のQの値も重要です。ないと、すぐ探す気をなくしちゃいます。ゲーム終了でのmax(Q)をどうしようとか、ゲーム途中の更新を忘れたりと、意外とはまりました。pQ=PlayerQL(PLAYER_O,"QL1")p2=PlayerQL(PLAYER_X,"QL2")game=TTT_GameOrganizer(pQ,p2,100000,False,False,10000)game.progress()QL1:4371,QL2:4436,DRAW:1193QL1:8328,QL2:8456,DRAW:3216QL1:11903,QL2:11952,DRAW:6145QL1:14268,QL2:14221,DRAW:11511QL1:15221,QL2:15099,DRAW:19680QL1:15730,QL2:15667,DRAW:28603QL1:16136,QL2:16090,DRAW:37774QL1:16489,QL2:16439,DRAW:47072QL1:16832,QL2:16791,DRAW:56377QL1:17128,QL2:17121,DRAW:65751大体ドローに収束していますね。εで勝敗が分かれているのがわかります。モンテカルロ君と戦わせるεをゼロにして、ランダム要素をなくして最良の打ち手で攻めてみますpQ.e=0p2=PlayerMC(PLAYER_X,"M1")game=TTT_GameOrganizer(pQ,p2,100,False,False,10)game.progress()QL1:1,M1:0,DRAW:9QL1:1,M1:0,DRAW:19QL1:2,M1:0,DRAW:28QL1:2,M1:0,DRAW:38QL1:3,M1:0,DRAW:47QL1:4,M1:0,DRAW:56QL1:5,M1:0,DRAW:65QL1:5,M1:0,DRAW:75QL1:6,M1:0,DRAW:84QL1:6,M1:0,DRAW:94モンテカルロ君も時々負けてしまいました。モンテカルロ君は乱数の気まぐれから逃れられません。ちなみにこの状態のQ-Learning君と戦うと、かなり痛い目にあいます。Network)さて今回の本題。Q-LearningのネックはQ(s,a)のテーブルが膨大になること。三目並べならいいけど、碁ではSもaも莫大なメモリとなってしまいます。Q-NetworkではQ(s)により各aの期待報酬を出して、argmaxを取ることになります。「勝手に勝つ特徴をみつけちゃうんじゃない!?」、1000回位の対戦でいいんじゃない?とたかをくくってました。・・・・が、ドはまりしました。Parameterが多すぎる。Searchがほしかったです。教師がないのでロスの測定もできないんですよね。精度は、相手と戦わせて初めてわかる。Linkが切れて全然学習しなかったり。GPUのないマシンでいろいろやってたので遅い。GPUないと学習に5-10分くらいかかったりします。#print(self.q)ソース長いですねぇ。試行錯誤の形跡が残っている気がしますが、きれいにしていません。改良ランダムと対戦これでまずはざっくり打ち方と勝ち方を覚えさせます。pDQ=DQNPlayer(PLAYER_X)p2=PlayerAlphaRandom(PLAYER_O)game=TTT_GameOrganizer(pDQ,p2,20000,False,False,1000)game.progress()DQN:206,AlphaRandom:727,DRAW:67DQN:468,AlphaRandom:1406,DRAW:126DQN:861,AlphaRandom:1959,DRAW:180DQN:1458,AlphaRandom:2315,DRAW:227DQN:2185,AlphaRandom:2560,DRAW:255DQN:3022,AlphaRandom:2704,DRAW:274DQN:3832,AlphaRandom:2856,DRAW:312DQN:4632,AlphaRandom:3023,DRAW:345DQN:5481,AlphaRandom:3153,DRAW:366DQN:6326,AlphaRandom:3280,DRAW:394DQN:7181,AlphaRandom:3400,DRAW:419DQN:8032,AlphaRandom:3522,DRAW:446DQN:8902,AlphaRandom:3618,DRAW:480DQN:9791,AlphaRandom:3705,DRAW:504DQN:10673,AlphaRandom:3793,DRAW:534DQN:11545,AlphaRandom:3893,DRAW:562DQN:12420,AlphaRandom:3986,DRAW:594DQN:13300,AlphaRandom:4074,DRAW:626DQN:14183,AlphaRandom:4158,DRAW:659DQN:15058,AlphaRandom:4246,DRAW:696だいぶ強くなりましたね。改良ランダム君には勝てるようで。Q-Learningと対決pDQ.e=1game=TTT_GameOrganizer(pDQ,pQ,30000,False,False,1000)game.progress()DQN:4,QL1:436,DRAW:560DQN:6,QL1:790,DRAW:1204DQN:6,QL1:1135,DRAW:1859DQN:6,QL1:1472,DRAW:2522DQN:6,QL1:1801,DRAW:3193DQN:6,QL1:2123,DRAW:3871DQN:6,QL1:2439,DRAW:4555DQN:6,QL1:2777,DRAW:5217DQN:7,QL1:3128,DRAW:5865DQN:9,QL1:3648,DRAW:6343DQN:13,QL1:4132,DRAW:6855DQN:13,QL1:4606,DRAW:7381DQN:13,QL1:5087,DRAW:7900DQN:14,QL1:5536,DRAW:8450DQN:14,QL1:6011,DRAW:8975DQN:14,QL1:6496,DRAW:9490DQN:14,QL1:7394,DRAW:9592DQN:14,QL1:7925,DRAW:10061DQN:16,QL1:8357,DRAW:10627DQN:16,QL1:8777,DRAW:11207ようやく強くなったのかな。なんだか微妙な強さですが。このログではまだ負けが多いですが、10万回対戦位すると大体ドローに落ち着きました。GameDQN:1,Human:0,DRAW:1まぁそれらしい打ち手にはなっていました。Networkでは試行錯誤しないと決められないことが非常に多かったです。Reluにしてよくなりました。盤面に-1が入るのでReluではうまく表現できなかったのかな。あと、なぜかAdamではだめでSGDではうまくいきました。Adam最強と勝手に思っていました。AlphaRandomと対戦させないで、最初からQ-Learning(強いやつ)と戦わさせると、すぐにやる気をなくして、負けっぱなしになったりします。最初は弱いやつと戦わせて、やる気を出させる必要があるようです。何より苦労したのがどうやって、DQNに打ってはいけない手を教えるかという点です。今回は既にコマのあるところに打ったら、強制的にマイナス報酬を与えて10回学習という、アプローチをいれてうまくいきました。打ってよい場所を入力に入れればいいのかな?疑問や改善したいところがたくさんあるのでもしわかる人いたら教えてください。アドバイスや指摘、どんどんウェルカムです。それにしても、三目並べなら2-3時間くらいあればできるだろう、とたかをくくっていたのに、思いのほか時間がかかりました。ないギャップがあることを痛感。皆さんも今回のソースはあまり見ずに、ご自身で実装されることをお勧めします。時間のあるときにオセロバージョンを作るかなぁ。それかきちんとAlphaGoの3NN構成を試してみようか、次の課題に悩み中です。尚史@narisan25機械学習全般のコンサルとソリューション提供している会社Ridge-iを運営しています。10年くらい金融畑でアルゴリズム取引やHFT(高頻度取引)、リスク分析システムの開発をしてました。