目次

前段

ゲームとは
ゲームプログラムの歴史

本文

ポリシーネットワークの教師あり学習
ポリシーネットワークの強化学習
バリューネットワークの強化学習
ポリシーネットワークとバリューネットワークを用いた探索
AlphaGoの棋力評価
考察

序文

囲碁は古典的なゲームの中でAIが扱うには最も難しいと見なされてきた。何故なら探索空間が巨大過ぎるのと盤面の評価が難しいからである。ボードを評価するバリューネットワークと次の手を選択するポリシーネットワークを用いたコンピュータ囲碁に対する新しいアプローチを紹介する。これらのディープニューラルネットは人間のプロ同士の棋譜による教師あり学習と自己対局による強化学習によって訓練される。先読みを一切しなくてもニューラルネットは何千もの局面を評価するモンテカルロ法の囲碁プログラムと同じレベルで動作する。モンテカルロシミュレーションとバリューネットワークとポリシーネットワークを組み合わせた新しい探索アルゴリズムも紹介する。この探索アルゴリズムを使用したAlphaGo他の囲碁プログラムに対して99.8％の勝率を達成し、ヨーロッパ囲碁チャンピオンに5-0した。これはコンピュータが19路盤でプロを初めて倒したことである。以前は10年はかかるだろうと考えられていたことである。

各ゲームの局面の数

オセロ 10^60
チェス 10^120
将棋 10^226
囲碁 10^360

AIがチェスで1997年(約20年前)に勝てた理由

盤面の評価が比較的簡単であったため。10^120の盤面を探索できていたわけではない。

盤面の評価の難易度に関してもチェス < 将棋 < 囲碁

別の言い方をするとチェスというゲームがどういうものであったかを人間は論理的に表現できたため。それに対して囲碁や将棋では「味がいい」「手厚い」「重い」「地に辛い」「模様がよい」・・・というニュアンス表現に頼っている。

ゲーム

完全情報ゲーム

すべての意思決定点において、これまでにとられた行動や実現した状態に関する情報がすべて与えられているような展開型ゲームのことをいう。

ex. オセロ, チェス, 将棋, 囲碁, etc

不完全情報ゲーム

他のプレイヤーが行動するときにそれまでに起こっている情報をすべて把握することができないゲーム

ex. 麻雀, ポーカー, 株, FX, etc

二人零和有限確定完全情報ゲーム

理論上は完全な先読みが可能であり、双方のプレーヤーが最善手を打てば、必ず先手必勝か後手必勝か引き分けかが決まるゲーム

二人

ゲームを行うプレーヤーが二人のゲーム

零和

ゲーム上、プレーしている全プレーヤーの利得の合計が常にゼロ、または個々のプレーヤーの指す手の組み合わせに対する利得の合計が全て一定の数値（零和）となるゲーム。利得とはプレーヤーがゲーム終了時（あるいはターンの終了時）に獲得する状況に対する評価である。

有限

そのゲームにおける各プレーヤーの可能な手の組み合わせの総数が有限であるゲーム

確定

プレーヤーの着手以外にゲームに影響を与える偶然の要素が入り込まないという意味

Minimax

Minimax

想定される最大の損害が最小になるように決断を行う戦略。つまり、相手が最善手を打つと仮定した場合の最善手を探す方法。

ゲーム木

ゲーム木

組合せゲーム理論において、ゲームの盤面を有向グラフのノードで、手をエッジで表したものである。

完全ゲーム木とはゲームの最初から指せる全ての手を含んだゲーム木である。

ゲーム木は人工知能で重要であり、最良の手はゲーム木を探索することで得られ、ミニマックス法などのアルゴリズムを使用する。
三目並べのゲーム木は小さいので探索も容易だが、チェスなどの完全ゲーム木は大きすぎて全体を探索することができない。
その場合は代わりに部分ゲーム木を使う。

部分ゲーム木は、一般に現在の盤面から指せる手を時間内に探索できるぶんだけ含んだものである。
2人で対戦するゲームはAND/OR木で表現することもできる。先手が勝つには、後手がどういう手を指しても先手が勝つ手が存在しなければならない。これをAND/OR木では、先手の指せる手を論理和で表し、後手のさせる手を論理積で表す。

水平線効果

水平線効果

探索アルゴリズムの深度を有限とした場合、それ以降の経路をあたかも水平線の向こうのように考慮しないため、長期的に見て問題のある選択をしてしまう人工知能における問題である。通常多くのゲームにおいて、可能な状態あるいは配置の数は莫大であり、コンピュータはそのごく一部（大抵ゲーム木の数層下）しか探索することができない。

ミニマックス法やαβ枝刈りといった技術を使用して大きなゲーム木を評価する時、探索深度は実現可能性の理由のため制限される。しかしながら、ゲーム木の部分的な評価は紛らわしい結果を与える可能性がある。探索深度の「水平線」のすぐ先に大きな変化が存在する時、計算装置は水平線効果の餌食となる。

アルファベータ法

アルファベータ法

完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。

原始モンテカルロ囲碁

乱数を用いて交互に合法手を終局まで打つシミュレーションを大量に行う。その結果から最も勝つ確率が高い次の一手を選択する

モンテカルロ木探索

原始モンテカルロ囲碁に対して

有利な手により多くのシミュレーションを行う
シミュレーションの回数が閾値を超えると探索木を成長させる

の変更を加えたもの。要は原始モンテカルロ囲碁のシミュレーションにおいて、次の一手の探索をMulti-Armed Bandit問題としてとらえたもの。

Multi-Armed Bandit 問題

複数のスロットマシンがあって、それらをプレイすると、当たりか外れが出る。
スロットごとに当たりが出る確率は異なっているが、その値はわからない。
このとき、決められた回数のゲームプレイで、多く当たりを引きたい。

UCB1

$\overline{X_j}$をj番目のマシンの報酬期待値, $n$をそれまでに投入したコインの数, $n_j$を$j$番目のマシンに投入したコインの数, $c$を期待値の値域によって決まる定数として、UCB1は

$$
\overline{X_j} + c \sqrt{\frac{2 \log n}{n_j}}
$$

を最大とするj番目のマシンにコインを投入する戦略。要は適度に探索はしつつも期待値の高いマシンに多くのコインを投入する戦略。

UCT(UCB applied to Trees)

UCB1を用いた木探索

Progressive Widening

囲碁の知識を用いて、良さそうな手から順に探索木に加えていく(ランダムではなく従来の知識でよさそうな手が多めに選ばれるモンテカルロシミュレーションになる)

前段

完全情報ゲームは全ての状態$s$においてゲームの結果を決定する$v^*(s)$が存在する。

これらのゲームはゲームの幅$b$(ある状態に対して打てる手の数)とゲームの深さ$d$(ゲームの手数)の局面の探索木において$v^*(s)$を再帰的に計算することで解ける。

チェス$(b \approx 35, d \approx 80)$や囲碁$(b \approx 250, d \approx 150)$などの大きいゲームでは全探索は不可能だが2つの一般原則で探索空間を削減できる。

1つ目は探索の深さは盤面評価によって減少できる。すなわち、状態$s$で探索木を切り捨て、状態$s$からの結果を予測する近似値関数$v（s） \approx v^*（s）$によって$s$以下の部分木を置き換える。このアプローチはチェス、チェッカー、オセロで圧倒的なパフォーマンスを発揮したが、ゲームの複雑さのために囲碁では扱いにくいと考えられていた。

2つ目は探索の幅は状態$s$における可能な手$a$に対する確率分布$p(a|s)$からサンプリングすることで減少できる。たとえば、モンテカルロ法は、局面$p$から双方のプレイヤーの手をサンプリングすることで、分岐を一切行わずに最大深度まで探索することができる。これらの探索結果の平均をとることで効果的な盤面評価が可能となり、バックギャモンとスクラブルで人間を超えるパフォーマンスを達成し、囲碁でもアマチュアレベルのプレイに達した。

モンテカルロ木探索（MCTS）はモンテカルロ法を用いて探索木における各盤面の値を推定する。より多くのシミュレーションを実行すればするほど、探索木が大きくなり盤面の評価値がより正確になる。探索中に手を選択するために使用されるポリシーもより高い値の子ノードを選択することによって改善される。漸近的に、この方針は最適なプレイに収束し、評価は最適値関数に収束する。現在最強な囲碁プログラムは、MCTSに基づいており、プロの動きを予測するために訓練されたポリシーによって強化されている。これらのポリシーは、探索を確率の高い手に絞り込み、実行中の手をサンプリングするために使用されます。このアプローチはアマ高段のプレイに達した。しかしながら、以前の研究では浅いポリシー、つまり、入力特徴の線形結合に基づく盤面評価関数に限定されていた。

最近、ディープCNNは、画像分類、顔認識、ゲームのプレイなど視覚領域における前例のない性能を達成している。それぞれ重なり合った畳み込み層を用いた多数のニューロンを使用して、より抽象的で局所的な画像の表現を構築する。同様のアーキテクチャを囲碁に適用した。盤面を19x19の画像として扱い、畳み込み層を用いて盤面の状態を表現する。これらのニューラルネットを用いて探索木の幅と深さを減らす。バリューネットワークを使用して状態を評価し、ポリシーネットワークを使用して手のサンプリングを行う。

ポリシーネットワークの教師あり学習

プロの棋譜から学習した盤面に対してプロがどう打つかを予測するためのニューラルネット

ポリシーネットワークの強化学習

次は旧世代のポリシーネットワークと対戦した際に最大の結果を得る手を予測するためのニューラルネット

プロの手の予測精度を最大化することが目標ではなく、ゲームに勝つという正しい目標のために学習ができる

バリューネットワーク

最後に自己対局の結果から盤面に対して期待される結果を学習した盤面評価のためのニューラルネット

1. ポリシーネットワークの教師あり学習

SLポリシーネットワーク$p_{\sigma} (a | s)$は重み$\sigma$の畳み込み層と非線形の活性化関数から構成される

最後のソフトマックス層の出力は可能な全ての手$a$の確率

入力$s$は盤面の表現

盤面$s$に対する人間の手$a$の確率を最大化するように確率的勾配上昇を用い、無作為に抽出された$(s, a)$を学習していく

$$
\Delta \sigma \propto \frac{\partial \log{p_{\sigma}(a | s)}}{\partial \sigma}
$$

KGSの3000万の局面から13層のネットワークを学習した

ネットワークはプロの手を57%の精度での予測を達成した。少しの精度向上でも勝率は大きく向上する。ただ、大きなネットワークであればあるほど精度は向上したが、計算速度が遅くなった。そのため精度は低いが高速なネットワーク$p_{\pi} (a | s)$も実装した。

2. ポリシーネットワークの強化学習

RLポリシーネットワーク$p_{\rho}$はSLポリシーネットワークと同一の構造で重みはSLポリシーネットワークの値で初期化する。最新のポリシーネットワーク$p_{\rho}$と過学習を防ぐために無作為に選ばれた以前のネットワークとを対戦させる。

報酬関数

r(s) =\left\{ \begin{array}{ll}
0 & (途中の局面) \\
+1 & (勝利) \\
-1 & (敗北) \\
\end{array} \right.

を最大化するように確率的勾配上昇によって重みは更新される

$$
\Delta \rho \propto \frac{\partial \log{p_{\rho}(a_t | s_t)}}{\partial \rho} z_t
$$

RLポリシーネットワークはSLポリシーネットワークに対して80%以上も勝つようになった

3. バリューネットワークの強化学習

盤面$s$からポリシー$p$でプレイした場合の結果を予想する評価関数

$$
v^p (s) = E [ z_t | s_t = s, a_{t...T} \sim p ]
$$

理想としては完璧なプレイ$v^* (s)$の評価関数が知りたい。実際には$v^{p_{\rho}}$を推定する。

$v_{\theta}(s) \approx v^{p_{\rho}}(s) \approx v^*(s)$となるような重み$\theta$のネットワーク$v_{\theta}$を構築する。ポリシーネットワークと同様な構造をしているが、出力は1つ(勝ちそうか負けそうか)だけ。

状態と結果のペア$(s, z)$の二乗誤差を最小化するように確率的勾配降下法を用いて学習させる。

$$
\Delta \theta \propto \frac{\partial v_{\theta}(s)}{\partial \theta} (z - v_{\theta}(s))
$$

4. ポリシーネットワークとバリューネットワークを用いた探索

AlphaGoはMCTSにポリシーネットワークとバリューネットワークを組み合わせたもの。探索木の各エッジ$(s, a)$は手の価値$Q(s, a)$と訪問回数$N(s, a)$と事前確率$P(s, a)$を記憶する。

1 状態$s_t$で選択される手$a_t$は

a_t = {argmax}_a (Q(s_t, a) + u(s_t, a))

と、手の価値とボーナス$u(s, a) \propto \frac{P(s, a)}{1 + N(s, a)}$の合計を最大化するように選択する

2 Lステップで葉ノード$S_L$に到達すると葉ノードは拡張される

3 葉ノード$S_L$はSLポリシーネットワーク$p_{\sigma}$によって一回だけ探索する

4 探索結果は$P(s, a) = p_{\sigma}(a|s)$として保存する

5 葉ノードは2つの異なる方法で評価する

バリューネットワーク$v_{\theta}(S_L)$によって
ポリシーネットワーク$p_{\pi}$によってプレイされた結果$z_L$によって
この2つの評価から最終的な葉ノード$S_L$の評価

$$
V(S_L) = (1 - \lambda) v_{\theta} (S_L) + \lambda z_L
$$

を生成する

6 $s^i_L$は$i$回目のシミュレーションの葉ノード、$1(s, a, i)$は$i$回目のシミュレーションでエッジ(s, a)を使われたかどうかを示す関数とし、

$$
N(s, a) = \sum_{i = 1}^{n} 1(s, a, i)
$$
$$
Q(s, a) = \frac{1}{N(s, a)} \sum_{i = 1}^{n} 1(s, a, i) V(s^i_L)
$$

とシミュレーションが終わった時に更新する

7 探索が完了すると最もよく使った手を選択する

5. AlphaGoの棋力評価

6. 考察

実装

top
1. ai -> 貪欲法によるポリシー選択、確率によるポリシー選択、モンテカルロ囲碁
2. go -> 囲碁の状態、手
3. mcts -> モンテカルロ木探索
4. util ->
models
1. nn_util
2. policy -> CNNのポリシーネットワーク
3. value ->
preprocessing
1. game_converter -> 棋譜の変換(SGF -> HDF5)
2. preprocessing ->
training
1. reinforcement_policy_trainer -> ポリシーネットワークの強化学習
2. reinforcement_value_trainer -> バリューネットワークの教科学習
3. supervised_policy_trainer -> ポリシーネットワークの教師あり学習