TadaoYamaokaの日記

山岡忠夫 Home で公開しているプログラムの開発ネタを中心に書いていきます。

AlphaGo Zeroの論文を読む その4(自己対局)

その3の続き

自己対局パイプライン

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

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

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

最適化

  • ミニバッチサイズ:2,048 (32バッチずつ別々のGPUで実行)
  • ミニバッチデータは直近50万の自己対局のすべての局面からランダムでサンプリング
  • モーメントありのSGDで最適化(モメンタムパラメータ=0.9)
  • 学習率は以下の通り徐々に下げる
1000ステップ 学習率
0-400 10^{-2}
400-600 10^{-3}
>600 10^{-4}

損失関数を式にすると以下の通り
l=(z-v)^2 - {\bf \pi}^T log {\bf p} + c\|\theta\|^2
zは勝敗(-1,1)、vはvalue{\bf \pi}モンテカルロ木探索で求めた局面の遷移確率、{\bf p}はpolicyの遷移確率、\|\theta\|^2はネットワークのパラメータの2乗ノルム

  • 自己対局1,000回ごとにチェックポイントを設ける
  • チェックポイントで次の自己対局で使用するか評価を行う

評価

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

自己対局

  • 評価で選択した最良のネットワークを使ってデータを生成する
  • イテレーションでは、25,000ゲーム、1手1,600シミュレーションのモンテカルロ木探索で自己対局を行う

  • 各ゲームの最初の30手は温度\tau=1に設定する(訪問回数の応じた確率で着手し、局面にバリエーションを持たせる)

  • 残りの手は、温度\tau \to 0に設定する
  • ルートノードの事前確率にディリクレノイズを加える
  • 具体的には、P(x,a)=(1-\epsilon)p_a + \epsilon \eta_a, \eta \sim Dir(0.03), \epsilon=0.25
  • このノイズは、全ての手を試すために行うが、探索することで悪手は選択されなくなる

  • 計算資源を節約するため、明らかに負けの場合投了する
  • 閾値は誤認率を5%以下に保つように自動的に決定する
  • 誤認率を測定するため10%のゲームは終局までプレイする

将棋AIに応用する際の考察

損失関数について

policyの交差エントロピーは、式では教師データの指し手ではなく、遷移確率\piを使用していますが、温度パラメータを0にして自己対局しているので、実際は打ち手のみを学習することになるので、教師データとして打ち手をone hotベクトルとしたsoftmax交差エントロピーを使っていると思われます。

valueの損失には平均二乗誤差が使われています。
出力の活性化関数がtanhの場合は、交差エントロピーは負の値に使えないので、平均二乗誤差を使用していると思われます。
報酬が(-1,1)の単位スケールなのでvalueの平均二乗誤差とpolicyの交差エントロピーと同じ重みにするのは合理的だと、書かれていましたがちょっと意味が分かりませんでした。

なお、将棋AIでは、評価関数の出力にsigmoidを使用して、損失には交差エントロピーを使うのが主流になっています。

温度パラメータについて

局面のバリエーションを増やすために、自己対局の最初30手は温度パラメータが調整されています。
将棋AIでは、初期局面集を使って局面バリエーションを増やすことが行われています。
初期局面集の質が良ければその方がバリエーションを増やすには良いと思います。
初期局面集から開始して温度パラメータ調整ありで、数手を指すのが良いかもしれません。

残りの手は、温度パラメータを0にして最大訪問回数のノードを選択しています。
それではpolicyの予測手以外を探索しなくなるので、ルート局面のみノイズが加えられています。
policyは読み抜けをなくすこと重要なので、ノイズを加えることで対策しているようです。
ルート局面以外にもノイズを加えると探索の幅が広がりすぎるので、ルート局面のみに限定しています。
ノイズを加えることで、ついでにある程度打ち手にランダム性を加えることもできます。

ディリクレノイズについて、K次元のディリクリ分布は、
Dir({\bf p}|{\bf \alpha})=\frac{\Gamma(\sum_{k=1}^K \alpha_k)}{\prod_{k=1}^K \Gamma(\alpha_k)} \prod_{k=1}^K p_k^{\alpha_k-1}
で表されるので、出力ラベル数を次元としたディリクリ分布に従って生成した値をノイズに加えるということだと思います。
(合っているか自信がありません。間違っていたら教えてください。)

投了の閾値について

投了の閾値を自動で決定しているのはよく考えられていると思いました。
自分なら適当に決めていると思います。

対局数について

モンテカルロ木探索で自己対局をするには相当な時間がかかります。
個人で試そうと思ったらどこかで割り切りが必要そうです。

続く

AlphaGo Zeroの論文を読む その3(探索アルゴリズム)

その2の続き

今回は対局時の探索アルゴリズムについてです。

探索アルゴリズム

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

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

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

選択

展開済みノードの選択は、以前のAlphaGo(Fan Huiバージョン)と同じPUCTアルゴリズムを使う。

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)}
c_{puct}は定数で、具体的な値は記載されていない。
以前の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の出力値。

バックアップ

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

訪問回数N(s,a)をインクリメントする。
N(s_t,a_t)=N(s_t,a_t)+1

行動価値を更新する。
W(s_t,a_t)=W(s_t,a_t)+v
vは、末端局面の評価で出力されたvalue

行動価値の平均を更新する。
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閾値以下の場合、投了する。

以前のAlphaGoとの比較

以前のAlphaGoと比較して、rolloutを使用しないことが主要な違い。

以前のAlphaGoでは、policyの計算中に線形関数を使用した軽量のtree policyを使用し、また、valueの計算中に軽量のrollout policyを使用してrolloutを行ってvalueとrolloutの平均を報酬としていましたが、単純にニューラルネットワークの実行を待つようになっています。

将棋AIに応用する際の考察

rolloutを使用しないPUCTアルゴリズムが将棋AIでもある程度有効であることは、同様アルゴリズムを使用しているdlshogiがfloodgateでrating 2700になっていることで確かめています。
policyとvalueの精度が高くなれば、PUCTアルゴリズムを使ってまだ強くなる余地があると考えています。

評価する局面を8対称からランダムで選んでいるのは面白いと思いました。
精度をあまり落とさずにランダム性を持たせることができます。
将棋の場合は初期局面に対称性がない(飛車、角の位置が違う)ので対称な局面を考慮してもあまり意味がないと思われるので、この手法は使えなさそうです。

末端局面の初期化の際、dlshogiでは、W(s_L,a)=v, Q(s_L, a)=vとしていましたが、vを行動価値ととらえるとAlphaGo Zeroの方が正しい初期化の気がしました。

打ち手の決定は、最大の訪問回数の手を選択しないで、遷移確率に従っているのは自己対局で訓練データを生成する際はより適切と思いました。
プレイヤーとの対局時は、最大の訪問回数の手を選んでもよいと思います。

続く

コマンドプロンプトのカラースキーム変更

18日から提供開始されたWindows 10 Fall Creators Updateを適用しました。

今バージョンからコマンドプロンプトのカラースキーム変更になるということです。
今までコマンドプロンプトの青の文字が非常に読みづらく、Bash on Windowsを使うようになってから特にストレスを感じるようになりました。
なのでカラースキームの変更はうれしいですね。

適用後さっそくコマンドプロンプトで確認してみたところ、あれ?変わってない?
どうやらクリーンインストールしないと変わらないようですorz

後から変えたい場合は、ツールが提供されていました。
Creators Update適用しなくても変更できたのか。

Introducing the Windows Console Colortool – Windows Command Line Tools For Developers
こちらからツールをダウンロードできます。

コマンドプロンプトのカラースキームの変更

colortool.exe -c

で現在の色が確認できます。

colortool.exe -d <スキーマ名>

で変更できます。
反映するにはコマンドプロンプトの再起動が必要です。

各カラースキームの色

変更前

f:id:TadaoYamaoka:20171021113621p:plain

campbell

f:id:TadaoYamaoka:20171021113743p:plain

campbell-legacy

f:id:TadaoYamaoka:20171021113928p:plain

OneHalfDark

f:id:TadaoYamaoka:20171021114021p:plain

OneHalfLight

f:id:TadaoYamaoka:20171021114102p:plain

solarized_dark

f:id:TadaoYamaoka:20171021114143p:plain

solarized_light

f:id:TadaoYamaoka:20171021114227p:plain

deuteranopia

f:id:TadaoYamaoka:20171021114438p:plain

Bash on Windowsのカラースキームの変更

これで、Bash on Windowsのlsの結果などが見やすくなると思ってBash on Windowsを起動したら、Bash on Windowsには反映されていませんでしたorz
Bash on Windowsのカラースキームを変更するには、コンソールのプロパティ→画面の色から手作業で設定する必要があります。
コマンドプロンプトのカラースキームを変更してから、コマンドプロンプトのプロパティ→画面の色と同じRGBの値に設定すればよいです。
f:id:TadaoYamaoka:20171021121033p:plain
色のパレットを選択して、赤、緑、青の数値をコマンドプロンプトと同じに設定すればよいです。
パレットの色を変更後、元のパレットの位置を選択しなおしてからOKを押しましょう(ラジオボタンで画面の背景を選んでいる場合は一番左)。

これで、青の文字が見やすくなりました。

変更前

f:id:TadaoYamaoka:20171021121204p:plain

変更後

f:id:TadaoYamaoka:20171021121323p:plain

AlphaGo Zeroの論文を読む その2(ネットワーク構成)

前回に続いてAlphaGo Zeroの論文についてです。

ネットワーク構成

入力特徴

  • 19×19の2値画像を17枚
  • 8枚は現在のプレイヤーの石の座標を示す2値画像、8手分
  • 8枚は相手のプレイヤーの石の座標を示す2値画像、8手分
  • 1枚は現在のプレイヤーの石の色を示す全て0か1の画像

履歴を必要とするのは囲碁にはコウがあるため。
石の色が必要なのは囲碁にはコミがあるため。

以前(Fan Huiバージョン)のAlphaGoでは入力特徴に、呼吸点やシチョウなどの囲碁の知識を含む48の特徴を使用していましたが、石の座標情報のみになっています。

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

入力層

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

  1. 畳み込み 3×3のフィルター、256枚
  2. Batch Normalization
  3. 活性化関数

以前のAlphaGoは5×5のフィルター192枚でしたが、より枚数が増えています。
Batch Normalizationも以前はありませんでした。
活性化関数には、具体的に何の関数を使っているか記載がありません。
以前はReLUだったので、同じと思われます。

中間層

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

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

図示すると以下のようになります。
f:id:TadaoYamaoka:20171021091056p:plain

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

出力層

ネットワークを分岐して、PolicyとValueを出力します。
Policyの出力は以下の構成

  1. 畳み込み 1×1のフィルター、2枚
  2. Batch Normalization
  3. 活性化関数
  4. 19×19(打ち石の座標)+1(pass)を示す362ノードの全結合層でlogit probabilitiesを出力

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ノードの全結合層

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

将棋AIに応用する際の考察

入力特徴について

将棋AIに応用する際には、将棋には駒の取り合いや千日手があるので、入力特徴の履歴の情報は有用と思われます。
現在のプレイヤーの石の色の情報は、将棋にはコミがないので不要かもしれません。

ニューラルネットワーク構成について

ResNetが将棋でも有用であることは、以前の実験で確かめています。
私の実験では5ブロックで192枚のフィルターでしたが、39層で256枚のフィルターはかなりの規模です。
試そうと思うと学習時間は相当かかるので覚悟が必要そうです。

PolicyとValueの同時出力について

将棋でもマルチタスク学習が有用であることも以前の実験で確かめています。

出力層の構成について

Policyの出力に全結合層が加わっています。
この構成にした理由は書かれていませんが、この方が精度が上がるということでしょうか。
将棋でも有用か試してみようと思います。
1×1のフィルターを出力としていると、移動できない座標もラベルとする必要がありましたが、全結合を使うなら、出力ラベル数は減らせるのでその効果もでるかもしれません。

Valueには以前のAlphaGoと同様にtanh関数が使われていますが、コンピュータ将棋では評価関数の出力にsigmoidを使う方が主流ですね。
sigmoidでも大差はないと思っていますが、tanh関数を使った方がよい理由とかあるのでしょうか。
分かる人がいらっしゃたら教えてもらえると助かります。

続く

AlphaGo Zeroの論文を読む

今日のAlphaGo Zeroのニュースは衝撃でした。

将棋AIで方策勾配で強化学習を行ったときは、発散してうまくいかなかったので
教師データで最初に訓練が必要と思っていました。
それが、自己対局のみで強くできるとは驚きです。

論文が公開されたので、使われたテクニックを調べていきたいと思います。

http://www.nature.com/nature/journal/v550/n7676/full/nature24270.html

まだ全部読んでいませんが、ざっくり初めの方を読んで以下の特徴があるようです。

  1. PolicyとValueを1つのネットワークで出力する
  2. Batch Normalisationと非線形の活性化関数を使用したResidual Network(ResNet)
  3. モンテカルロ木探索による自己対局で生成した各局面の打ち手と、勝敗結果を訓練データに使用する
  4. モンテカルロ木探索はノードを1回訪問したら展開する
  5. rolloutは使用しない
  6. 訓練の損失関数にはValueの平均二乗誤差とPolicyの交差エントロピー損失の和を同じ重みで使う
  7. L2正則化をする


Methodに自己対局と訓練方法について、かなり詳細に書かれていますので、
理解した内容を少しずつ書いていこうと思います。


おそらくこの方法は将棋AIにも応用可能と思われます。

PolicyとValueを1つのネットワークで出力すのは、
自分の将棋AIでも行っていて効果を確かめていましたが、
別々のネットワークの方が実は良いのではと思っていましたので、
自信が得られました。

モンテカルロ木探索の部分はrolloutを使わず1回で展開するのは、
自分の将棋AIと基本は同じ方法ですが、
ボルツマン分布の温度パラメータを動的に変えているようです。
将棋でも効果があるか実験したいところです。

続く。。。

AlphaGo Zeroの論文を読む その2(ネットワーク構成) - TadaoYamaokaの日記
AlphaGo Zeroの論文を読む その3(探索アルゴリズム) - TadaoYamaokaの日記

将棋AIの進捗 その8(ponder対応)

電王トーナメントの出場ソフトが公開されました。
私のソフトは「dlshogi」です。
denou.jp

ディープラーニングを使ったソフトがいくつか出場するようです。
対局できるのが楽しみです。


電王トーナメントに向けて、時間制御まわりを改善しています。
ひとまずponderに対応させました。

USIのponderの仕様は、ponderhitの際、続けて思考するための残り時間情報が渡されないので、通常のgoの処理と分けないといけないのが面倒ですね。
バグがないか確認のためにfloodgateに放流しています。

USIの仕様では、予測手1手のみを先読みする想定のようですが、それだけでも効果があるそうです。
文献によると、相手の局面と同じ局面を思考してハッシュを埋める場合と大差ないそうです。
違いがどれくらいあるかは実験してみたいところです。

後は、モンテカルロ囲碁で行われている時間延長を実装する予定です。

技術書典3の告知

10/22(日)に秋葉原で開催される技術書典3にサークル参加します。
サークル名は「dlshogi」、配置は「か19」です。
頒布するのは、「ディープラーニングを使った将棋AIの作り方」です。

f:id:TadaoYamaoka:20171001233240p:plain:w250f:id:TadaoYamaoka:20171002212032p:plain:w250
Policy Networkの作り方についての解説本になります。

あと、お隣のサークルの「Andirogue」にはDevBooksでの既刊ですがAlphaGoについての記事を寄稿しています。

どうぞよろしくお願いいたします。