LoginSignup
0
1

More than 3 years have passed since last update.

@bloody_snowinエムスリー株式会社

Mastering the Game of Go without Human Knowledge

Last updated at Posted at 2019-11-03
1 / 29

Mastering the Game of Go without Human Knowledge

序文

  • 人工知能の目標は挑戦する分野で白紙の状態から人間を超える能力を学ぶアルゴリズムである
  • 以前のアルファ碁は人間のプロの棋譜から学習し自己対局による強化学習を行った
  • 今回のアルファ碁ゼロは人間の対局データやドメイン知識無しで自己対局による教科学習のみ
  • アルファ碁ゼロは白紙の状態から人間を超える能力を得た

以前のアルファ碁

以下の2つのネットワークとMCTSを用いた

  • ポリシーネットワーク: 手を予測する
  • バリューネットワーク: 評価関数

今回のアルファ碁ゼロのPoint

  1. ランダムプレイから初めての自己対局による強化学習のみ
    • モンテカルロ木探索による自己対局で生成した各局面の打ち手と勝敗結果を訓練データに使用する
    • 訓練の損失関数にはValueの平均二乗誤差とPolicyの交差エントロピー損失の和を同じ重みで使う
    • L2正則化をする
  2. 入力特徴量は碁盤の黒石と白石のみ
  3. 1つのニューラルネットワークに統合された
    • PolicyとValueを1つのネットワークで出力
    • Batch Normalisationと非線形の活性化関数を使用したResidual Network(ResNet)
  4. 以前よりもシンプルな木探索アルゴリズム
    • モンテカルロ木探索はノードを1回訪問したら展開する
    • rolloutは使用しない

自己対局による強化学習

スクリーンショット 2018-03-11 11.43.36.png

ネットワーク構成

ネットワーク比較

スクリーンショット 2018-03-11 12.13.34.png

sep or dual: policyとvalueを別ネットワークに分割するか統合するか
conv or res: convolutional or residual networks

入力特徴

  1. 19×19の2値画像を17枚
  2. 8枚は現在のプレイヤーの石の座標を示す2値画像、8手分
  3. 8枚は相手のプレイヤーの石の座標を示す2値画像、8手分
  4. 1枚は現在のプレイヤーの石の色を示す全て0か1の画像
  • 履歴を必要とするのは囲碁にはコウがあるため
  • 現在のプレイヤーの石の色が必要なのは囲碁にはコミがあるため
  • 以前のAlphaGoでは入力特徴に呼吸点やシチョウなどの囲碁の知識を含む48の特徴を使用していたが石の座標情報のみになっている

ニューラルネットワーク構成

入力層

1層の畳み込み層で以下の構成

  1. 畳み込み 3×3のフィルター 256枚
  2. Batch Normalization
  3. 活性化関数(ReLU)
  • 以前のAlphaGoは5×5のフィルター192枚だったが枚数が増えている
  • Batch Normalizationも以前はなかった

中間層

19個、または39個の残差ブロック
1つの残差ブロックは以下の構成

  1. 畳み込み 3×3のフィルター、256枚
  2. Batch Normalization
  3. 活性化関数
  4. 畳み込み 3×3のフィルター、256枚
  5. Batch Normalization
  6. 残差入力の接続
  7. 活性化関数

残差ブロックの数は、はじめは19個で自己対局を行い、最終的に39個としています

出力層

ネットワークを分岐して、PolicyとValueを出力します。

Policyの出力

  1. 畳み込み 1×1のフィルター、2枚
  2. Batch Normalization
  3. 活性化関数
  4. 19×19(打ち石の座標)+1(pass)を示す362ノードの全結合層でlogit probabilitiesを出力
  5. logit probabilitiesはsoftmax関数の入力となる値で、softmax関数の出力が打ち手の確率を示します。

以前のAlphaGoでは1×1のフィルター1枚の出力をlogit probabilitiesとしていましたが、全結合層が加わっています。

Valueの出力

  1. 畳み込み 1×1のフィルター、1枚
  2. Batch Normalization
  3. 活性化関数
  4. 256ノードの全結合層
  5. 活性化関数
  6. tanh関数で勝率を示すスカラー値を出力する1ノードの全結合層(not sigmoid)

Batch Normalization以外は、以前のAlphaGoと同じ構成です。

探索アルゴリズム

対局時はpolicyとvalueを使ったモンテカルロ木探索(APV-MCTS)を使用する。
探索は複数スレッドで並列に行う。

スクリーンショット 2018-03-11 11.58.52.png

データ

探索木の各ノードsは以下の情報を持つ。

表記 意味
N(s,a) 行動aの訪問回数
W(s,a) 行動aの行動価値の合計
Q(s,a) 行動aの行動価値の平均
P(s,a) 行動aの事前確率

選択

PUCTアルゴリズム(前回と同じ)

UCTアルゴリズムをpolicyを使って拡張したアルゴリズム。UCB1に代わって

Q(s_t, a) + U(s_t, a)

を最大化する行動aを選択する。

$Q(s,a)$はvalueから算出される(後述)。
$U(s,a)$はpolicyの遷移確率$P(s,a)$を事前確率として使用した以下の式で計算される。

U(s, a) = c_{puct} P(s, a) \frac{ \sqrt{ \sum_b N(s, b) } }{ 1+N(s, a) }

cpuctcpuctは定数で、具体的な値は記載されていない。以前のAlphaGoでは5が使われていた。

展開と評価

末端ノードLに到達したら、局面評価用キューに追加する。
キューに追加する際、8つの対称(反転、回転)な局面から1つランダムに選ぶ。

キューが8たまるとミニバッチを実行する。評価が完了するまで探索スレッドはロックする。
評価が完了すると、ノードを展開し、以下の値で初期化する。

N(s_L, a) = 0, W(s_L, a) = 0, Q(s_L, a) = 0, P(s_L, a) = p_a

$p_a$はpolicyの出力値。

バックアップ

末端ノードからルートノードまで、訪問した順を逆にたどって、以下の通り各ノードを更新する。

  1. 訪問回数$N(s, a)$をインクリメントする。

    N(s_t, a_t) = N(s_t, a_t) + 1

  2. 行動価値を更新する。

    W(s_t, a_ t) = W(s_t, a_t) + v

    vは、末端局面の評価で出力されたvalue。

  3. 行動価値の平均を更新する。

    Q(s_t, a_t) = \frac{ W(s_t, a_t) }{ N(s_t, a_t) }

    なお、訪問回数は、複数スレッドで同一局面を探索しないように、バーチャルロス(訪問回数を先にインクリメントしておく)を使用する。

打ち手決定

探索終了後、ルートノードの訪問回数から遷移確率を計算する。

\pi (a | s_0) = \frac{ N(s_0, a)^{ 1 / \tau }}{\sum_b N(s_0, b)^{ 1 / \tau }}

$\tau$は温度パラメータ。温度が低いと差が開き、温度が高いと均一になる。0の場合は常に最大の手を選択する。

選択したノードの子ノードは次のステップで再利用する。
それ以外のノードとその子ノードは破棄する。

ルートノードのvalueと最善手を選んだ後の局面のvalueが閾値以下の場合、投了する。

自己対局

自己対局パイプラインは、3つの主要な部分から構成される。

  1. 最適化
  2. 評価
  3. 自己対局

これらは並行で実行される。

トレーニング

  1. ランダム着手から3日で人間に勝った
  2. 1手0.4秒で1600のMCTSのシミュレーション、490万局
  3. バッチサイズ2,048で700,000回パラメータ更新

スクリーンショット 2018-03-11 12.10.15.png

最適化

  1. ミニバッチサイズ: 2,048 (32バッチずつ別々のGPUで実行)
  2. ミニバッチデータは直近50万の自己対局のすべての局面からランダムでサンプリング
  3. モーメントありのSGDで最適化(モメンタムパラメータ=0.9)

  4. 学習率は以下の通り徐々に下げる

    1000ステップ 学習率
    0-400 10−210−2
    400-600 10−310−3
    600- 10−410−4

  5. 損失関数には、policyの交差エントロピーとvalueの平均二乗誤差の和を使用

  6. policyの交差エントロピーとvalueの平均二乗誤差は等しく重み付けする

  7. L2正則化を行う($c=10^{−4}$)

  8. 自己対局1,000回ごとにチェックポイントを設ける

  9. チェックポイントで次の自己対局で使用するか評価を行う

損失関数

l = (z − v)^2 − \pi^T \log{p} + c||\theta||^2

zは勝敗(-1,1)、vはvalue、$\pi$はモンテカルロ木探索で求めた局面の遷移確率、pはpolicyの遷移確率、$||\theta||^2$はネットワークのパラメータの2乗ノルム

評価

  1. チェックポイントで現在の最良のネットワークと比較して評価する
  2. モンテカルロ木探索アルゴリズムで最良のネットワークと400回対局を行う
  3. 1手1,600シミュレーション
  4. 温度パラメータは$\tau \to 0$とする(最大の訪問回数のノードを選択)
  5. 最良のネットワークに55%以上勝利した場合、それを最良のネットワークとし、その後の自己対局で使用する

自己対局

  1. 評価で選択した最良のネットワークを使ってデータを生成する
  2. 各イテレーションでは、25,000ゲーム、1手1,600シミュレーションのモンテカルロ木探索で自己対局を行う
  3. 各ゲームの最初の30手は温度$\tau = 1$に設定する(訪問回数の応じた確率で着手し、局面にバリエーションを持たせる)
  4. 残りの手は、温度$\tau \to 0$に設定する
  5. ルートノードの事前確率にディリクレノイズを加える

  6. 具体的には

    P(x, a) = (1 − \epsilon) p_a + \epsilon \eta_a \\
\eta \sim Dir(0.03) \\
\epsilon = 0.25

  7. このノイズは、全ての手を試すために行うが、探索することで悪手は選択されなくなる

  8. 計算資源を節約するため、明らかに負けの場合投了する

  9. 閾値は誤認率を5%以下に保つように自動的に決定する

  10. 誤認率を測定するため10%のゲームは終局までプレイする

学習結果の他プログラムとの比較

スクリーンショット 2018-03-11 12.17.09.png

ドメイン知識

"Our primary contribution is to demonstrate that superhuman performance can be achieved without human domain knowledge."

人間の知識を用いないということが、この技術が囲碁に特化しない汎用的な技術であることを示している。
それを明確にするために、使用したドメイン知識を列挙している。

使用したドメイン知識

  1. 囲碁のルール
    1. シミュレーションの終端状態でのスコア付け
    2. ゲームの終了条件
    3. 各局面での合法手
  2. MCTSシミュレーション中にTromp-Taylorスコアリング(曖昧さの無いルール)を使用
  3. 19×19のボードであること
  4. 回転と反転しても囲碁のルールが不変であること

以上の点を超えるドメイン知識は使用していない。
以前のAlphaGoでは、rollout policyやtree policyにドメイン知識やヒューリスティックを利用していたが、rollout policyやtree policyは使用していない。

合法手は一切除外していない。
従来のプログラムでは合法手でも駄目を詰めるといった無駄な手を除外していたが、そのようなことはしていない。
ニューラルネットワークアーキテクチャは、画像認識の最新技術に基づいており、それに応じて訓練用ハイパーパラメータを選択した。
MCTS探索パラメータは、予備実験で訓練されたニューラルネットワークを使って自己対局を行い、ガウス過程により最適化した。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1