TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

将棋AIの実験ノート:初期局面集の優先順位付きサンプリング

深層強化学習の手法に、Prioritized experience replay (PER)(優先順位付き経験再生)という方法がある。
リプレイバッファに蓄積した経験データに優先順位を付けて、優先順位が高いほどより多くサンプリングする手法だ。

優先順位の尺度には、TD誤差が用いられる。
現在のネットワークの予測と、nステップ後の\max _{a} Q\left(s^{\prime}, a\right)の差が大きいほど優先的にサンプリングする。
サンプリングしたデータの優先度は、その時点の推論結果によって更新される。

将棋AIへの応用

この考えを、dlshogiの学習に採用したいと思っているが、将棋AIでは、勝敗と探索後のルートノードQ値を学習しているため、一度付けた優先度を推論結果だけでは更新することができない。
そこで、優先順位を付けるのを初期局面のサンプリングに置き換えることで、似たような効果を得たいと考えている。
つまり、判断の難しい局面(=優先度が高い局面)を多く初期局面として対局することで、学習効果の高い棋譜を生成したい。

以前に、自己対局で優勢と判断した局面から負けた局面を抽出して、初期局面集に加えるということを行ったが、考え方は近い。
しかし、もう少し統計的に処理したい。

実現方式案

初期局面集に登録する局面には、勝敗結果とその時の探索結果のQ値を記録しておく。

初期局面集をロードする際に、|勝敗結果-Q値|を使用してsum-treeを構築する。
sum-treeはセグメント木の一種で、一度構築すると、優先度によるサンプリングがO(log(N))の計算量で行える。

優先度には、|勝敗結果-Q値|以外にも、序盤や入玉勝ちを重点的に学習したい場合にバイアスを掛けたりできる。
そのため初期局面集には、勝敗の理由(千日手入玉勝ち)や、手数も同時に記録しておくと良いだろう。

こうしておけば、過去の自己対局で生成した局面や、floodgateの棋譜などから適当にサンプリングして登録した初期局面集でも、適切な優先度に応じて初期局面として使用されるため、初期局面の作成に悩まずに済む。
とにかく数多く登録しておけばよい。

まとめ

まだ試しても実装もしていないが、とりあえず案だけ書いてみた。
教師局面のフォーマットを見直そうと考えているので、後で必要になりそうな情報も出力しておきたいため、とりあえず案だけ整理してみた形である。

MineRLをWindowsで動かす

MinecraftのOpenAI Gym環境 MineRLWindowsで動かすための環境構築方法について。
ほぼ個人用メモ。

インストール方法は、公式ドキュメントを元にしている。

OpenJDKインストール

Chocolateyを使用してインストールする。
PowerShellを管理者権限で起動し、

choco install openjdk8

Python環境構築

Anaconda3の仮想環境に構築する。
Pythonのバージョンは、3.8だとコンフリクトが起きるため、3.7を使用する。
依存パッケージは、condaでインストールしておく。

conda create -n minerl python=3.7 matplotlib=3.0.3 pillow=7.2.0 jupyter coloredlogs numpy scipy scikit-learn pandas tqdm joblib requests lxml psutil dill future cloudpickle typing
conda activate minerl
conda install pytorch torchvision torchaudio cudatoolkit=11.0 -c pytorch

matplotlibはバージョン指定(3.0.3)になっているので注意。
minerl/requirements.txt at 5a9c06a7e727ae20cf123e5161b5cfa6ba69793b · minerllabs/minerl · GitHub
異なるバージョンだと、ソースからビルドされて、Windows環境だとビルドエラーになる。

MineRLインストール

pip install minerl==0.3.6

バージョンは現時点の最新。

起動テストとgradle修正

iPythonやJupyter QtConsoleなどから、以下のスクリプトを実行する。

import minerl
import gym
env = gym.make('MineRLNavigateDense-v0')

数分待つと、以下のようなビルドエラーが発生する。

* What went wrong:
Could not resolve all dependencies for configuration ':compileClasspath'.
> Could not resolve org.spongepowered:mixin:0.7.5-SNAPSHOT.
  Required by:
      com.microsoft.MalmoMod:Minecraft:0.37.0
   > Could not resolve org.spongepowered:mixin:0.7.5-SNAPSHOT.
      > Unable to load Maven meta-data from http://repo.spongepowered.org/maven/org/spongepowered/mixin/0.7.5-SNAPSHOT/maven-metadata.xml.
         > Could not GET 'http://repo.spongepowered.org/maven/org/spongepowered/mixin/0.7.5-SNAPSHOT/maven-metadata.xml'. Received status code 520 from server: Origin Error

gradleの定義が古く、URLが間違っているため、以下のファイルをテキストエディタで開き、手動で編集する。
C:\Users\<username>\anaconda3\envs\minerl\Lib\site-packages\minerl\env\Malmo\Minecraft\build.gradle

(変更前)

url = "http://repo.spongepowered.org/maven/"
(変更後)
url = "https://repo.spongepowered.org/maven/"

参考:assanuma Profile - githubmemory

起動テスト

以下のスクリプトを実行する。

import minerl
import gym
env = gym.make('MineRLNavigateDense-v0')

MineCraftが起動する。
f:id:TadaoYamaoka:20210223091003p:plain

obs = env.reset()

を実行すると、ゲームが開始し、小さいウィンドウになる。
f:id:TadaoYamaoka:20210223091056p:plain

f:id:TadaoYamaoka:20210223091231p:plain

env.render()

を実行すると、別ウィンドウで、拡大画面と現在の状態が表示される。
f:id:TadaoYamaoka:20210223091328p:plain

サンプル実行

ランダムに行動するサンプルプログラムを実行する。

import minerl
import gym
env = gym.make('MineRLNavigateDense-v0')

obs = env.reset()

done = False
while not done:
    action = env.action_space.sample()
    obs, reward, done, info = env.step(action)

ランダムにアクションをサンプリングし、アクションがなくなるまで実行される。
カメラ操作もランダムなので、スムーズな表示ではない。

カメラをゆっくり操作して、大きい画面でウェイトを入れて表示してみる。

import minerl
import gym
from time import sleep
env = gym.make('MineRLNavigateDense-v0')

obs = env.reset()

done = False
while not done:
    action = env.action_space.sample()
    action['camera'] = [0, min(5, max(-5, action['camera'][1]))]
    obs, reward, done, info = env.step(action)
    env.render()
    sleep(0.01)
終了方法
env.close()

で、終了する。

将棋AIの実験ノート:Normalizer-Free Networks

ちょうどFixup Initializationを試したタイミングで、DeepMindからBatch Normalizerを削除してSOTAを達成したという論文が発表された。

さっそく試してみようとしたが、ソースコードJaxで実装されているため、PyTorchで実装し直す必要がある。
deepmind-research/nfnets at master · deepmind/deepmind-research · GitHub

はじめ自力で実装していたが、途中で非公式のPyTorchの実装が公開されたたため、そちらを大いに参考にさせてもらった。
pytorch-image-models/nfnet.py at master · rwightman/pytorch-image-models · GitHub

ひとまず実装できたので、現在のdlshogiのResNet(Batch Normalizerあり)と、Normalizer-Free ResNetsで比較してみた。

論文の要旨

Batch Normalizerの効果
  • 損失を滑らかにし、より大きな学習率とより大きなバッチサイズで安定した訓練を可能とする。
  • 正則化の効果もある。
Batch Normalizerの欠点
  • 驚くほど高価な計算プリミティブであり、メモリオーバーヘッドが発生し、一部のネットワークで勾配を評価するために必要な時間が大幅に増加する。
  • 訓練中と推論時のモデルの動作の間に不一致が生じ、調整が必要な隠れたハイパーパラメーターが導入される。
  • ミニバッチの訓練サンプル間の独立性を壊す。
提案手法
  • ネットワーク構成は、Normalizer-Free ResNets(NF-ResNets)をベースにする。残差ブロックの分散の増加に合わせてダウンスケールする。

[2101.08692] Characterizing signal propagation to close the performance gap in unnormalized ResNets

  • 残差ブロックの最後に、学習可能なスカラー(SkipInit)を含める。
  • 畳み込み層の重みの平均と分散により、再パラメータ化する「Scaled Weight Standardization」を導入する。
  • 従来の勾配クリッピングは、閾値の選択に敏感であるため、重みのノルムによる比を用いた「Adaptive Gradient Clipping (AGC) 」を導入する。

\displaystyle
\begin{equation}
G^{\ell}_i \rightarrow
    \begin{cases}
    
    \lambda \frac{\|W^{\ell}_i\|^\star_F}{\|G^{\ell}_i\|_F}G^{\ell}_i& \text{if $\frac{\|G^{\ell}_i\|_F}{\|W^{\ell}_i\|^\star_F} > \lambda$}, \\
    G^{\ell}_i & \text{otherwise.}
    \end{cases}
\end{equation}

実験方法

dlshogiの強化学習で生成した31,564,618局面で訓練し、floodgateからサンプリングした856,923局面で評価する。
MomentumSGD(lr=0.1)で学習する。
SWAはオフにする。
重み減衰は有効(rate=0.0001)にする。
論文の残差ブロックの畳み込み層は3層だが、dlshogiは2層なので2層に合わせる。
活性化関数は論文ではgeluだが、dlshogiに合わせてsiluを使用する。
論文では、AGCは、最終層には適用しないとあるので、policyヘッドと、valueヘッドの全結合層は除外する。

測定結果

f:id:TadaoYamaoka:20210220155549p:plainf:id:TadaoYamaoka:20210220155552p:plainf:id:TadaoYamaoka:20210220155555p:plainf:id:TadaoYamaoka:20210220155559p:plain

考察

Batch Normalizerを用いたResNetの方が、速く訓練損失が低下しており、テスト損失も低い。
NFNetsには、いくつかパラメータがあるため、いくつか変更して試してみたが、ほとんど結果は変わらなかった。

まとめ

Normalizer-Free Networksを、dlshogiの学習で試してみた。
論文ではImageNetの学習で、SOTAを達成したと報告されているが、将棋の学習では効果を確認できなかった。

画像のデータセットで実装したコードを使用してそもそも再現できるのかや、論文と残差ブロックの畳み込み層の数が異なるなど条件が異なる部分もあるため、そろえた場合にどうなるかは別途確認したい。

学習時間

学習時間は以下の通りであった。
PyTorchでAMPを使用している。

訓練時間
ResNet(Batch Normalizerあり) 1:16:34 100%
NFNets 1:09:05 90.2%

将棋AIの実験ノート:Fixup Initialization

深いResNetの訓練では、勾配爆発が起きる。そのため、Batch Normalizationを使用するのが一般的である。

Leela Chess Zeroでは、Batch Normalizationの統計情報に関連する問題が報告されている。
Pawn promotion issues in T40 · Issue #784 · LeelaChessZero/lc0 · GitHub

具体的には、訓練時の正規化はバッチ単位で行われるのに対して、推論時は訓練時の移動平均が使用されるため、頻度の少ない局面では、推論時にチャネルの出力が0になるケースがあるという問題である。
将棋でもそれに該当する具体的な局面があるかは調べられていない。

Leela Chess Zeroでは、Batch Renormalizationを採用することで、対処を行っている。
Test40 update - Leela Chess Zero


一方、KataGoでは、Batch Normalizationを使用するのをやめて、Fixup Initializationを採用している。
KataGo/KataGoMethods.md at master · lightvector/KataGo · GitHub

Fixup Initializationは、適切な初期値を設定することで、Batch Normalizationがなくても勾配爆発を解消するという手法である。
詳しい理論は、論文を参照いただくとして、以下の通りResNetを変更して、初期値を設定を行う。

  1. 分類レイヤーと各残差ブランチの最後のレイヤーを0に初期化する。
  2. 標準的な方法(He et al.(2015)など)を使用して1つおきのレイヤーを初期化し、残りのブランチ内のウェイトレイヤーのみをL^{-\frac{1}{2m-2}}でスケーリングする。
  3. すべてのブランチにスカラー乗数(1で初期化)とスカラーバイアス(0で初期化)を、各畳み込み、線形、および要素ごとのアクティブ化レイヤーの前に追加する。

重要なのは、2.で、1.、3.は訓練のパフォーマンスを向上する。

論文では、CIFER-10とImageNet、翻訳タスクでの実験結果が報告されており、CIFER-10とImageNetでは、Batch Normalizationより若干精度が下回っているが、KataGoでは、Batch Normalizationと同等のパフォーマンスを再現できたそうだ。


Batch Normalizationがなくなると訓練速度を大幅に向上できるため、dlshogiでもFixup Initializationの効果があるか試してみた。

実装

論文著者によるPyTorchの実装を参考にした。
GitHub - hongyi-zhang/Fixup: A Re-implementation of Fixed-update Initialization

始めswishのモデルに適用したら、まったく学習できなかった。
活性化関数は、ReLUである必要があるようだ。

論文は出力層の全結合の重みとバイアスを0で初期化するとあるが、policyとvaueの出力層にも畳み込みがあるため、それらを0で初期化したところ、valueが全く学習できなかった。
そこで、出力層はvalueの最終層の全結合のみ0で初期化した。

測定方法

dlshogiの強化学習で生成した60,911,062局面で訓練し、floodagteからサンプリングした856,923局面でテストした。

MomentumSGD、学習率0.01、WeightDecay0.0001でResNet10ブロックのネットワークを訓練した。

結果

訓練損失
訓練平均方策損失 訓練平均価値損失
Batch Normalization 0.68084329 0.38440849
Fixup Initialization 0.70152103 0.39291802
テスト損失
テスト方策損失 テスト価値損失
Batch Normalization 0.97448369 0.54640203
Fixup Initialization 0.97963965 0.54785213
テスト正解率
テスト方策正解率 テスト価値正解率
Batch Normalization 0.42880582 0.70676383
Fixup Initialization 0.42871940 0.70434300
考察

Fixup Initializationでも、安定して学習できることが確認できた。
Batch Normalizationと比較すると、精度は落ちている。

収束するまで学習した場合に、どうなるかまでは確認できていない。

まとめ

Batch Normalizationをなくすと訓練速度を大幅に短縮できるというメリットがあるため、dlshogiの学習でFixup Initializationの効果があるか試してみた。
結果、Fixup Initializationで安定して学習できることが確認できた。
しかし、Batch Normalizationと比べると少し精度が落ちることがわかった。

収束するまで学習した場合や、対局しての強さについては別途確認したい。

将棋AIの実験ノート:最大手数で引き分けの局面を除外

dlshogiの強化学習では、最大手数(320手)に達した局面の価値を0.5として学習対象としている。

補助タスクの学習の際に、教師データを調べていた際に、あと数手で詰みの局面で引き分けになっている局面が含まれていることに気付いた(これまであまりチェックしていなかった)。

ほぼ勝ち(or負け)の局面を引き分けで学習すると、価値の精度に悪影響がありそうなので、除外した方がよさそうなので、引き分けも学習した場合と除外した場合の精度を比較してみた。
結論から言うと、ほとんど変わらなかったが、記録として残しておく。

除外方法

強化学習で教師データを作り直すのは時間がかかるので、生成済みの教師データから最大手数に達した引き分けの局面を除外した。
なお、dlshogiで使用しているhcpeフォーマットは、局面を対局と紐づけずに記録しており、候補が1手のみの局面やリーグ戦の対局では局面が数手飛びになっている。
局面の差分が小さいかで対局か判定して、最後のevalが0の場合は千日手として残して、それ以外を除外するようにした。
除外用コード(千日手入玉を補助ターゲットとする処理も含む):
ElmoTeacherDecoder/hcpe_to_hcpe2.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

比較方法

引き分けを除外する前の局面を学習した場合と、引き分けを除外した場合を学習した場合を比較した。
引き分けを除外すると学習局面が少なくなるが、それでも精度が高くなるようであれば除外した方がよいと言える。

比較結果

約1億局面に対して、引き分けを除外すると局面数は以下の通りとなった。

引き分け 訓練局面数
あり 60911062
なし 60679983

0.379%が引き分けの対局の局面であった。

訓練損失
引き分け 訓練平均方策損失 訓練平均価値損失
あり 0.68108568 0.38443670
なし 0.68366737 0.38153932
テスト損失
引き分け テスト方策損失 テスト価値損失
あり 0.97650576 0.54598011
なし 0.97590881 0.54592327
テスト正解率
引き分け テスト方策正解率 テスト価値正解率
あり 0.42818923 0.70668091
なし 0.42822660 0.70638313

ほぼ誤差の範囲である。

初期局面集を序盤のみにして生成したデータでも比較した(上記の初期局面は終盤まで含む5億局面を使用)。

引き分け 訓練局面数
あり 5709861
なし 5699771

0.176%が引き分けの対局の局面であった。

訓練損失
引き分け 訓練平均方策損失 訓練平均価値損失
あり 0.92409930 0.50431182
なし 0.92570610 0.50405253
テスト損失
引き分け テスト方策損失 テスト価値損失
あり 1.14031462 0.62040876
なし 1.14162646 0.61995558
テスト正解率
引き分け テスト方策正解率 テスト価値正解率
あり 0.36368881 0.65681287
なし 0.36326607 0.65728349

こちらも、ほぼ誤差の範囲である。

まとめ

最大手数に達した対局を除外してもしなくても大差ないということが確認できた。
全体に対する割合は、0.4%未満であるためほとんど影響がないのだろう。

将棋AIの進捗 その55(勾配クリッピング)

dlshogiを初期値から学習を開始すると、lossがinfやnanになる場合がある。
初期値からの学習以外でも勾配爆発を防ぐために、勾配クリッピングのオプションを追加した。

KataGoでも勾配クリッピングを追加している。学習が安定してからは特に効果はないようだ。

勾配クリッピングにより同じデータを学習した場合に結果が変わるか確認した。

勾配クリッピング

PyTorchのclip_grad_norm_を使用する。
これは、勾配のノルムが閾値以下になるようにクリッピングを行う。
値でクリッピングするよりも勾配の方向が変わらないから良いのだとか、大差ないとか*1

なお、AMPを使用している場合は、クリッピングを適用する前にスケールを戻す必要があるので注意が必要である。
Automatic Mixed Precision examples — PyTorch 1.10 documentation

測定方法

dlshogiの強化学習で生成した8,939,266局面を使用して、初期値から学習する。
テストデータには、floodgateのレート3500以上の対局の棋譜からサンプリングした856,923局面を使用した。

測定結果

訓練損失
勾配クリッピング 訓練平均方策損失 訓練平均価値損失
なし 0.91759841 0.41159116
max_norm=2 0.96313657 0.41694899
max_norm=10 0.91871473 0.41199293
テスト損失
勾配クリッピング テスト方策損失 テスト価値損失
なし 1.04227679 0.58552035
max_norm=2 1.05631246 0.58615224
max_norm=10 1.04086553 0.58512790
テスト正解率
勾配クリッピング テスト方策正解率 テスト価値正解率
なし 0.38140064 0.67416036
max_norm=2 0.37752943 0.67332306
max_norm=10 0.38164004 0.67416620
考察

max_norm=2は、なしに比べて学習が遅くなっている。
max_norm=10となしはほとんど変わっていない。

まとめ

初期値からの学習を安定化させるため勾配クリッピングを試した。
小さめの値にすると学習が遅くなることがわかったため、通常の学習に影響がない適当な値(10くらい)に設定しておくことにする。
KataGoでは学習率に合わせてスケーリングしているが、そこまでの調整は必要ないだろう。

将棋AIの実験ノート:方策の分布を学習

一般的な方策勾配法では、選択した行動aに対して、損失を計算するが、
\displaystyle
l_{policy} = - \log p(a)
AlphaZeroでは、方策の損失は、探索から求めた方策の確率分布\pmb{\pi}を使用している。
\displaystyle
l_{policy} = - \pmb{\pi}^\top \log \mathbf{p}

dlshogiでは、前者をベースにしたActor-Criticで更新を行っている。
後者の確率分布を学習する場合と、どちらが良いのか比較してみた。

実装

損失関数

選択した行動を学習する場合は、方策がソフトマックス関数で、出力がロジットの場合は、PytorchのCrossEntropyLossを使用して損失が計算できる。

確率分布を学習する場合は、組み込みの損失関数がないため、以下のように損失関数を定義した。

def cross_entropy_loss_with_soft_target(pred, soft_targets):
    return torch.sum(-soft_targets * F.log_softmax(pred, dim=1), 1)
教師データ

方策の確率分布が教師データに必要になるため、dlshogiで使用しているhcpeフォーマットでは対応できない。
また、合法手ごとの訪問回数を記録するため、局面により合法手の数が異なるため可変長フォーマットになる。
hcpeを拡張して、以下のようなフォーマットにした。

HuffmanCodedPosAndEval3 = np.dtype([
    ('hcp', dtypeHcp),
    ('eval', dtypeEval),
    ('bestMove16', dtypeMove16),
    ('result', np.uint8),
    ('seq', np.uint8), # 開始局面からの手数/2(今のところ使わない)
    ('candidateNum', np.uint16),
    ])
MoveVisits = np.dtype([
    ('move16', dtypeMove16),
    ('visits', np.uint16),
    ])

MoveVisitsはcandidateNumの数だけ繰り返す。
可変長フォーマットの場合は、今までの固定長のようにディスク上のデータすべてをメモリにそのまま読み込んで使用することができないので、シーケンシャルに読み込む処理が必要になる。
その場合は、開始局面のhcpと指し手のみ記録した方がデータサイズを節約できる。
また、resultを全局面に記録する必要もなくなるので、フォーマットはもう少しスリムにできる。
とりあえず実験したかったので、上記のような冗長なフォーマットになっている。

測定方法

強化学習で新たに教師データを生成するには時間がかかるため、方策の分布が記録されているAobaZeroの棋譜を使用した。
棋譜はarch000015000000からarch000015190000を使用し、合計19,695,636局面を学習した。

テストデータには、floodgateのレート3500以上の対局の棋譜からサンプリングした856,923局面を使用した。

比較対象のActor-Criticは、dlshogiで使用している式を使用した。
これはエントロピー正則化も含んでいる。

分布を学習する場合は、エントロピー正則化は行わない。

比較結果

訓練損失
訓練平均方策損失 訓練平均価値損失
Actor-Critic 0.90724320 0.58483684
分布を学習 1.97043909 0.58462431
テスト損失
テスト方策損失 テスト価値損失
Actor-Critic 0.98559491 0.57659638
分布を学習 0.93136043 0.56870430
テスト正解率
テスト方策正解率 テスト価値正解率
Actor-Critic 0.40432432 0.68084011
分布を学習 0.41709992 0.68707843
テストエントロピー
テスト方策エントロピー テスト価値エントロピー
Actor-Critic 1.67369065 0.60195279
分布を学習 1.82972054 0.59813645
考察

方策の訓練損失は式が異なるため直接は比較できない。
テスト損失は、dlshogiの損失計算に合わせている。
テスト損失、テスト正解率どちらも、分布を学習した方が、方策、価値どちらも良い値になっている。
ただし、価値については初期値の影響による誤差の範囲かもしれない。

また、方策のエントロピーが分布を学習した方が高く、より偏りの少ない方策になっていることがわかる。

まとめ

方策をActor-Criticで学習する場合と、探索後のルートノードの訪問数を使用した確率分布を学習する場合の比較を行った。
実験結果から、方策は分布を学習した方がよさそうということがわかった。

結果を受けて、dlshogiの強化学習でも分布を学習可能にする予定である。
教師データのフォーマットの見直しから行うことにする。