目次はこちら
##今回のテーマ
藤井聡太七段(2020年6月執筆時現在)の快進撃が続いています。
彼の活躍を語るときに必ず入るのがコンピューター将棋での研究です。
たまにコンピューター将棋についての記事を見ますが、「自己対局することで強くなる」くらいの解説で終わっていることが多いのではないでしょうか(当然ですが)。
そこで今回は、強化学習(Reinforcement Learning)という将棋AIに使われている手法を解説していきます。この強化学習は最初に紹介したフレームワークではPrescriptive Analysis、つまり「どう行動すればよいか」を教えてくれるタイプの機械学習になります。最近のネット将棋中継を見たことのある方は「次の一手」が画面に表示されていますよね。

将棋というのは運の要素が入り込むことのない勝負ですが、強化学習は運の介在する余地があっても適用することができます。有名な例はカジノのブラックジャックです(ご存じない方はルールをググってみてください)。
ブラックジャックにおいてプレイヤーが認識できる状況(「環境」といいます)は、自分の手札とディーラーの手札です。そこで新しいカードを引くか、もう止めるかを決めるわけですが、同じ行動をしたからと言って毎回同じ結果が得られるわけではないことは明らかでしょう。しかし、ある手札が見えているとき、引くのとやめるのとでどちらが期待値が高いのか、は比べることができます。このときどちらの方が期待値が高いのか、を教えてくれるのが強化学習です、

##動的計画法
強化学習の話をする前に、最も素朴なアイデアである動的計画法(Dynamic Planning; DP)の話をします。動的計画法というのは、とても単純に言うと、ある状況からの分岐をすべて追っていく総当たりの方法です。

最初に数式で説明します。ある状況$s$の価値$V(s)$というのは、

V(s) = \max_a \left[\sum_{s^{\prime}} V(s^{\prime})\varphi(s \rightarrow s^{\prime}, a)\right]

で表されます。数式を見ただけでは意味不明なので、説明します。

まず、$a$が「方策」と呼ばれるもので、これは普通の言葉でいうと行動です。例えば、ブラックジャックの引く/止めるや将棋の手に対応します。
$\varphi(s \rightarrow s^{\prime}, a)$というのは、行動$a$をとった後に状況が$s$から$s^{\prime}$に変化する確率です。例えばブラックジャックで自分の手の合計が15であったときに、もう一枚引いて20になる確率は1/13です。

すると、上の数式は以下のように解釈されます。
ある局面の価値を計算するには、すべてのあり得る行動について、行動した結果の期待値を計算します($\sum_{s^{\prime}} V(s^{\prime})\varphi(s \rightarrow s^{\prime}, a)$)。そのためには、ある行動について、その結果として起こりえるすべての局面の価値と、その局面になる確率をかけて足し合わせます。
そして、期待値が最大になるような行動($\max_a$)の期待値が現在の局面の価値(評価値)です。逆に言うと、現在取るべき行動は、結果の期待が最大になるような行動です。

いまいちピンとこない方のために、具体的な例を考えましょう。将棋やブラックジャックは複雑すぎるので、以下のような局面を考えます。

あなたはクイズ$ミリオネアの14問目に挑戦しています。残っているライフラインは50:50のみです。
あなたは4択クイズに2問連続正解すれば1000万円を手に入れることができますが、間違ってしまうとここまで13問正解してきたにも関わらず、100万円しか手に入りません。
ただしあなたには「ドロップアウト」(=リタイア)の権利があり、14問目でドロップアウトすると500万円、15問目でドロップアウトすると750万円が手に入ります。
また、「50:50」を一度だけ使うことができ、この場合4択問題が2択問題となります。
クイズの難易度が高く、もうあなたはランダムに回答することしかできません。

さて、現在の局面における最適行動を動的計画法で探してみましょう。

まず、ここでドロップアウトした場合、期待値は明らかに$V(14問目, ドロップアウト)=500万円$です。
次に、ここで50:50を使わずに回答した場合、期待値は

\begin{align}
V(14問目, 回答)&=正解する確率 \times V(15問目に50:50あり) + (1-正解する確率) \times 100万円 \\
&= 0.25 \times V(15問目に50:50あり) + 0.75 \times 100万円
\end{align}

です。
最後に、14問目を50:50を使って回答した場合、

\begin{align}
V(14問目, 50:50で回答)&=正解する確率 \times V(15問目に50:50なし) + (1-正解する確率) \times 100万円 \\
&= 0.5 \times V(15問目に50:50なし) + 0.5 \times 100万円
\end{align}

となります。

では次に$V(15問目に50:50あり)$と$V(15問目に50:50なし)$を計算しましょう。
前者は、「50:50を使って回答」「50:50を使わずに回答」「ドロップアウト」の3種類の方策があります。しかし、50:50を使わずに回答するより使って回答したほうが明らかに期待値は高いので、使わないという方策の期待値を計算する必要はありません。50:50を使って回答すると、

\begin{align}
V(15問目に50:50あり, 50:50を使って回答)&= 0.5 \times 1000万円 + 0.5 \times 100万円 \\
&= 550万円
\end{align}

である一方、$V(15問目に50:50あり, ドロップアウト)=750万円>550万円$です。ですので、この場合の15問目にはドロップアウトするのが最善で、$V(15問目に50:50あり)=750万円$とわかりました。
同様に、50:50を14問目に使って15問目にたどり着いた場合もドロップアウトするのが最善で、$V(15問目に50:50なし)=750万円$となります。

この結果を使って$V(14問目, 回答)$と$V(14問目, 50:50で回答)$を計算すると、

\begin{align}
V(14問目, 回答)&= 0.25 \times V(15問目に50:50あり) + 0.75 \times 100万円 \\
&= 0.25 \times 750万円 + 0.75 \times 100万円 \\
&=262.5万円 \\
\\
V(14問目, 50:50で回答)&= 0.5 \times V(15問目に50:50なし) + 0.5 \times 100万円 \\
&= 0.5 \times 750万円 + 0.5 \times 100万円 \\
&=425万円
\end{align}

となりました。結局これらの期待値は14問目でドロップアウトした場合の$V(14問目, ドロップアウト)=500万円$を超えられません。
ですので、現在の局面では__ドロップアウトして500万円を確保するのが最善である__という結論が出ました。

以上の計算を追っていただければ、動的計画法が総当たりであるという意味が理解できると思います。

##強化学習
###モンテカルロ法
しかし、以上の動的計画法にはいくつかの実用上の問題があります。
まず、遷移確率$\varphi(s \rightarrow s^{\prime}, a)$がいつもわかっているとは限りません。ブラックジャックやミリオネアではこの確率は比較的容易に計算できますが、例えば麻雀で、ある牌を切って誰かの当たり牌である確率、というのを計算するのは容易ではないでしょう。
もう一つは、総当たりするというのは実質的に不可能であることがあることが多いです。例えば将棋の合法手は数十あり得るので、それをすべて辿っていくことは現実的に不可能です。チェスは一度取られた駒が再使用できないというルールと、駒損による悪影響が非常に大きいという特性のため、総当たりによるコンピューター探索が比較的容易で、古くから人間より強いコンピューターが出現しました。しかし、将棋は持ち駒というルールのため、全探索が不可能とされています。

この問題点に対処できる手法が__モンテカルロ法__による強化学習です。モンテカルロ法というのは、「何度も何度も実験して期待値を求める」という意味です。
ちなみにモンテカルロというのはカジノで有名なモナコの地名らしいです。

###ブラックジャックによる例
ブラックジャックの例で強化学習を説明しましょう。
ブラックジャックのある局面$s$における行動$a$の価値を推定するために、以下のようなプロセスを繰り返します。

全局面の各行動について、評価値を0に初期化
局面$s$において行動$a$をする
新しい局面$s^{\prime}$を観測し、$s^{\prime}$におけるありえる全行動の評価値を確認
$s^{\prime}$における最善の行動$a^{\prime}$の評価値$V(s^{\prime}, a^{\prime})$と$s$における行動$a$の評価値$V(s, a)$に差がある場合、差が縮まるよう$V(s, a)$を調整
2-4を何度、何ゲームも繰り返す

何をしているか例で説明します。
ある局面$s$で、カードを引くことの評価値が+10、もう引かない評価値が-10だったとします。今回は(いいと思っているので)カードをもう一枚引くことにしました。
すると、新しいカードが配られて、局面が変化します。
この新しい局面$s^{\prime}$で、可能な行動とその評価値をすべて確認します。
しかし、新しい局面において、カードを引くことの評価値は+5、やめることの評価値は-5でした。この局面でベストな行動をしても評価値は+5にすぎません。なので、先ほどカードを引くことの評価値を+10と思っていたのは過大評価だったと考え、局面$s$でカードを引くという行動への評価値を+9にマイナス補正します。

これを何万回、何億回、何兆回と繰り返せば各局面の各行動の評価値が、真の期待値に近づいていくはず、というのが強化学習です。

行動の決め方

以上が基本的な強化学習の考え方ですが、局面$s$における行動$a$の決め方はまだ説明していませんでした。基本的には毎回ベストだと思っている行動をとり続けることになります。なぜかというと、ある局面のある行動の評価値というのは、その後でもベストの行動をとり続けることを仮定しているからです(先ほどの動的計画法の例を思い出してください)。しかし、これをすると毎回同じような行動ばかりをすることになってしまい、本当はベストかもしれない他の局面にたどり着くことができません。
そこで広く使われているのが$\epsilon$-グリーディーと呼ばれる方法です。グリーディー(貪欲)というのは、その場で最もよいと思っている行動をすることを指しています。そこで、この$\epsilon$-グリーディー法は以下のように行動を決めます。
確率$1-\epsilon$でベストと思っている行動をする
確率$\epsilon$でランダムに他の行動する
例えば$\epsilon=5%$なら、95%の確率で現在ベストと思っている行動をして、5%の確率でランダムに他の行動をします。
こうしてランダムに行動する余地を残すことで、広い可能性を探索できるようにします。

##まとめと補遺
動的計画法は強力なPrescriptive Analysisでしたが、全探索での期待値が難しいという問題がありました。そこで、実験的に期待値を求める強化学習を導入しました。

今回のブラックジャックの例ではプレイヤーは一人だけでしたが、将棋では局面は確率的に変化するのではなく、相手の着手に応じて変化します。そこで、一人二役で同じ評価関数を使って、自分の番は自分が最善と思う手を、相手の番では相手にとって最善と思う手を指して評価関数をアップデートし続けることで、将棋AIは評価関数をアップデートしていきます。本物の将棋ソフトは全探索アルゴリズムとこの強化学習による評価値を併用して、何十手も先までの起こりえる評価値が最善となる手を選びます(と理解しています)。

今回は各局面の各行動に評価値が紐づいていると仮定しましたが、将棋では可能な局面も可能な行動も星の数ほどあるため、これは現実的に困難です。そこで、この評価値を何らかの関数の形で近似しなければいけません。そこで使われるのがニューラルネットワークです。
ニューラルネットについては次回お話しする予定です。