これだけ読めば分かる（かもしれない）強化学習＠コンピュータ将棋界
はじめに
「強化学習 将棋」でググッてこのブログに来て貰う人が時々いますが、そう言えばちゃんとした概要を書いていなかったので、自分の復習がてら書いてみます。
んで、まず検索すると出てくる二大キーワード。
- マルコフ決定過程（MDP:Markov Decision Process）
- ベルマン方程式（Bellmann Equation）
これは当面忘れてもらってOKです。つか、これらのせいで強化学習の本質が見えづらい入門記事が散見されます。
概要
さて、じゃぁ「強化学習とはなんぞや」って話ですが、これは機械学習の一分野です。
機械学習は大別して「教師あり学習」「強化学習」「教師なし学習」の3種類があります*1。
「教師あり学習」は文字通り「教師」のいる学習方式です。コンピュータ将棋で言えば、Bonanza Methodがこれにあたります。教師がいるので、比較的効率が良く学習可能です。
「教師なし学習」は反対に「教師」のいない学習方式です。無理やりコンピュータ将棋に応用するなら、クラスタリングとかが出来そうです。「これとこれとこれは似た局面（例えば相矢倉）」「これとこれは別の似た局面（例えば居飛車振り飛車対抗型）」って感じで、似た者同士を分ける感じですね*2。
んで、本命の「強化学習」は、「教師」はいませんが「褒めたり叱ったりする人」のいる学習方式だと思って下さい。
この「褒める・叱る」というのが、強化学習の文脈で言う「報酬」にあたります。
「教師」と「報酬」の違いは、「教師」は全ての入力（局面等）に対して正解（指し手や評価値）を与えてくれるのに対して、「報酬」は時間的な遅延やノイズがある事です。
コンピュータ将棋で素直に「報酬」の与え方を実装すると、「勝ったら+1、負けたら-1、引き分けなら0」になります。（一般的に、強化学習では目的を達成したらプラスの報酬を、出来なければマイナスの報酬を与えます。）
つまり、「序盤で良い手を指した」直後にプラスの報酬が貰えるとは限りません。また、「終盤まで有利に進めていたのに、頓死して負けた」場合はマイナスの報酬が与えられます。
強化学習の主体となるモジュールの事を「エージェント」と呼びますが、エージェントの目的は「報酬を最大化する為にはどうすれば良いか、試行錯誤して学習する」事です。
言い方を変えると、「教師あり学習」では「手段」を「教師信号」として与え、それを模倣するのが学習の目的あるのに対し、「強化学習」では「目的」を「報酬」として与え、「手段」はエージェント自身が考えて決定します。
もうちょっと詳しく（TD法）
強化学習を将棋に応用する場合ですと、自己対局や他のプレイヤー*3との対局を通じて、「こういう局面でこう指せば勝率が高くなるな」というのを自律的に学習してくれます。
まずは、「局面の良し悪し」を判断する「価値関数」というものを導入します。コンピュータ将棋に詳しい方は「評価関数」と同等のもの、と考えて下さい。
これを使って、「この局面は何点位有利（不利）なのかな?」と判断します。（これは、一般的には「関数近似を用いた強化学習」になります。）
次に、点数計算の取っ掛かりとして、さっき出てきた報酬を使います。つまり、「報酬の期待値」を「局面の価値」と見なします。
例えば「自分が居飛車穴熊で、相手は棒銀に失敗して居玉のまま」だと「（自分から見て）+0.4点位かな*4」とか、そんな感じです。
じゃぁ、どうやって期待値の計算をするか、ですがこれは実際の対局中の局面の価値と、最終的に得られた報酬から計算します。
数式を書くと小難しく見えるので、不正確を承知で日本語で書くと「ある局面の価値は、それ以降の局面の価値・報酬に近いはずだ」という推測を元に計算します。
例えば「終盤で飛車を切って金を取った」とします。で、その次の自分の手番で「頭金で詰んだ」場合を考えます。
まず、「頭金で詰んだ」局面の価値は、その直後に貰えた報酬と等しいと考えて「+1」に近付けます（近付く様に価値関数のパラメータを修正します）。
次に、「飛車を切った」局面の価値は、「頭金で詰んだ」局面の価値に近いと考えて、その時の価値に近付けます（同じく、価値関数のパラメータを修正）。
これを、終局から初手まで遡って計算していくのが、「TD法」と呼ばれる手法です*5。
もちろん、一局だけだと正確に学習出来ませんので、沢山対局して何度もパラメータを修正していけば、どんどん正確な価値関数が出来上がります。
（ちなみに、コンピュータチェスで提唱されたTDLeaf(λ)は、TD法とαβ探索を組み合わせた手法になっています。）
別の手法（方策勾配法）
前項のTD法は、「正確な価値関数を作る」→「価値関数が正確なので強くなる」という2段構えの手法です。
これに対して、一発で「強い価値関数を作る」手法が有り、これが「方策勾配法」と呼ばれるものです。（芝浦将棋Jr.チームの五十嵐治一先生と私が共同で提案したPGLeafも、方策勾配法の一種です。）
こっちは数式を書くと無茶苦茶ややこしく見えるので、将棋の場合に限定して（若干不正確な面もありますが）書いてみます。
まず、指し手の選択の際に「良さそうな手（≒価値の高い手）ほど高確率で選ぶ」とします。強化学習ではSoftmax戦略（方策）と呼ばれるやり方です。
次に、対局後に「今回は勝った（プラスの報酬が貰えた）から、本譜の手は良かったんだろう」「今回は負けた（マイナスの報酬を与えられた）から、本譜の手は悪かったんだろう」と推測します。
そこで、勝った場合は「本譜の手の価値を上げ、それ以外の手の価値を下げる方向」に価値関数のパラメータを修正します。負けた場合は逆に「本譜の手を下げ、それ以外の手を上げる方向」に修正します。
これも、TD法と同様に、何度も対局してその都度学習して行けば、どんどん「強い価値関数」が出来上がります。
最後に
え〜、長々と書きましたが、一部（大部分?）不正確な記述が有ります。
厳密な数式やら証明やらは、専門書にあたるのが手っ取り早いと思いますので、日本語の良書（だと思ってる）を2つ載せておきます。
- 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
- 出版社/メーカー: 森北出版
- 発売日: 2000/12/01
- メディア: 単行本（ソフトカバー）
- 購入: 5人 クリック: 76回
- この商品を含むブログ (29件) を見る
強くなるロボティック・ゲームプレイヤーの作り方 プレミアムブックス版 ~実践で学ぶ強化学習~
- 作者: 八谷大岳,杉山将
- 出版社/メーカー: マイナビ出版
- 発売日: 2016/06/30
- メディア: 単行本
- この商品を含むブログ (2件) を見る
前者はTD法まで、後者は方策勾配法も記載があります。強化学習にどっぷり浸かるつもりなら、両方買っておくのが良いと思います。
それから、不明瞭な点や分かりづらい部分など有りましたら、コメント頂けると有り難いです。可能な限り追記・修正していくつもりです。
