2020-11-07

dlshogiをAWSのNVIDIA A100インスタンスで動かす

AWSのEC2に、NVIDIA A100のインスタンスが追加されたので、dlshogiでどれくらNPSが向上するか測定してみた。

個人としてはAWSを使っていなかったので、AWSのアカウントを作成して、vCPUの上限緩和申請するところから行った。
P4dインスタンスは、vCPUが96なので、上限緩和申請が必要である。
しかし、上限緩和申請をお断りされてしまった。

そこで、知り合いからアカウントをお借りして測定を行うことにした。

環境構築

AMI

AMIは、p4d.24xlargeに対応している「AWS Deep Learning Base AMI (Ubuntu 18.04) Version 31.0」を使用した。

GPUが認識されているか確認

$ nvidia-smi
Sat Nov  7 03:42:57 2020
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 450.80.02    Driver Version: 450.80.02    CUDA Version: 11.0     |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|                               |                      |               MIG M. |
|===============================+======================+======================|
|   0  A100-SXM4-40GB      On   | 00000000:10:1C.0 Off |                    0 |
| N/A   37C    P0    54W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   1  A100-SXM4-40GB      On   | 00000000:10:1D.0 Off |                    0 |
| N/A   37C    P0    51W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   2  A100-SXM4-40GB      On   | 00000000:20:1C.0 Off |                    0 |
| N/A   37C    P0    54W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   3  A100-SXM4-40GB      On   | 00000000:20:1D.0 Off |                    0 |
| N/A   35C    P0    51W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   4  A100-SXM4-40GB      On   | 00000000:90:1C.0 Off |                    0 |
| N/A   36C    P0    51W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   5  A100-SXM4-40GB      On   | 00000000:90:1D.0 Off |                    0 |
| N/A   36C    P0    54W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   6  A100-SXM4-40GB      On   | 00000000:A0:1C.0 Off |                    0 |
| N/A   38C    P0    56W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+
|   7  A100-SXM4-40GB      On   | 00000000:A0:1D.0 Off |                    0 |
| N/A   36C    P0    51W / 400W |      0MiB / 40537MiB |      0%      Default |
|                               |                      |             Disabled |
+-------------------------------+----------------------+----------------------+

+-----------------------------------------------------------------------------+
| Processes:                                                                  |
|  GPU   GI   CI        PID   Type   Process name                  GPU Memory |
|        ID   ID                                                   Usage      |
|=============================================================================|
|  No running processes found                                                 |
+-----------------------------------------------------------------------------+

CUDAバージョン変更

まず、デフォルトのCUDAバージョンが10.0になっているため、手順に従い、11.0に変更する。

$ sudo rm /usr/local/cuda
$ sudo ln -s /usr/local/cuda-11.0 /usr/local/cuda

バージョン確認

~$ nvcc --version
nvcc: NVIDIA (R) Cuda compiler driver
Copyright (c) 2005-2020 NVIDIA Corporation
Built on Wed_Jul_22_19:09:09_PDT_2020
Cuda compilation tools, release 11.0, V11.0.221
Build cuda_11.0_bu.TC445_37.28845127_0

TensorRTインストール

NVIDIAのサイトからTensorRTをダウンロードする。

Ubuntu用に、.debと.tar.gzが用意されているが、.debでインストールする場合、CUDAのパッケージも.debでインストールされていないと、最新バージョンのCUDAをインストールしようとしてインストールが失敗するため、無難に.tar.gzを使用する。

TensorRT 7.2.1 for Ubuntu 18.04 and CUDA 11.1 TAR package
をダウンロードする。

適当なディレクトリに展開する。
以下、ホームディレクトリ(/home/ubuntu/)に展開したものとする。

tar xzf TensorRT-7.2.1.6.Ubuntu-18.04.x86_64-gnu.cuda-11.0.cudnn8.0.tar.gz

環境変数LD_LIBRARY_PATHを設定する。

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/ubuntu/TensorRT-7.2.1.6/lib

dlshogiのビルド

ソースをGitHubからcloneする。

git clone https://github.com/TadaoYamaoka/DeepLearningShogi.git

Makefileを編集する。

cd cd DeepLearningShogi/usi
vi Makefile

「INCLUDE = 」で始まる行の末尾に「 -I/home/ubuntu/TensorRT-7.2.1.6/include」を追加
「LIB = 」で始まる行の「cuda-10.2」を「cuda-11.0」に変更
「LIB = 」で始まる行の末尾に「 -L/home/ubuntu/TensorRT-7.2.1.6/lib」を追加

ビルドする。

make

ライブラリが正常にロードできるか確認

cd bin
$ ldd usi
        linux-vdso.so.1 (0x00007ffe8f171000)
        libpthread.so.0 => /lib/x86_64-linux-gnu/libpthread.so.0 (0x00007f15512f4000)
        libnvinfer.so.7 => /home/ubuntu/TensorRT-7.2.1.6/lib/libnvinfer.so.7 (0x00007f153552d000)
        libnvonnxparser.so.7 => /home/ubuntu/TensorRT-7.2.1.6/lib/libnvonnxparser.so.7 (0x00007f15350b7000)
        libcudnn.so.8 => /usr/local/cuda/lib64/libcudnn.so.8 (0x00007f1534e8e000)
        libcudart.so.11.0 => /usr/local/cuda/lib64/libcudart.so.11.0 (0x00007f1534c10000)
        libcublas.so.11 => /usr/local/cuda/lib64/libcublas.so.11 (0x00007f152edc0000)
        libz.so.1 => /lib/x86_64-linux-gnu/libz.so.1 (0x00007f152eba3000)
        libstdc++.so.6 => /usr/lib/x86_64-linux-gnu/libstdc++.so.6 (0x00007f152e81a000)
        libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f152e47c000)
        libmvec.so.1 => /lib/x86_64-linux-gnu/libmvec.so.1 (0x00007f152e252000)
        libgcc_s.so.1 => /lib/x86_64-linux-gnu/libgcc_s.so.1 (0x00007f152e03a000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f152dc49000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f1552017000)
        libmyelin.so.1 => /home/ubuntu/TensorRT-7.2.1.6/lib/libmyelin.so.1 (0x00007f152d3ca000)
        libnvrtc.so.11.0 => /usr/local/cuda/lib64/libnvrtc.so.11.0 (0x00007f152bbdf000)
        librt.so.1 => /lib/x86_64-linux-gnu/librt.so.1 (0x00007f152b9d7000)
        libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f152b7d3000)
        libnvinfer_plugin.so.7 => /home/ubuntu/TensorRT-7.2.1.6/lib/libnvinfer_plugin.so.7 (0x00007f152a9d6000)
        libcublasLt.so.11 => /usr/local/cuda/lib64/libcublasLt.so.11 (0x00007f151f847000)

usiコマンド実行

適当なディレクトリにモデルファイルを用意する。
以下では、/home/ubuntu/model_rl_val_wideresnet10_selfplay_424.onnxにあるモデルファイルを使用する。

cd bin
./usi
setoption name DNN_Model value /home/ubuntu/model_rl_val_wideresnet10_selfplay_424.onnx
setoption name UCT_Threads value 3
setoption name UCT_Threads2 value 3
setoption name UCT_Threads3 value 3
setoption name UCT_Threads4 value 3
setoption name UCT_Threads5 value 3
setoption name UCT_Threads6 value 3
setoption name UCT_Threads7 value 3
setoption name UCT_Threads8 value 3
isready

TensorRTによる最適化に数分かかる。
数分後、以下のように表示される。

(略)
----------------------------------------------------------------
Input filename:   /home/ubuntu/model_rl_val_wideresnet10_selfplay_424.onnx
ONNX IR version:  0.0.6
Opset version:    9
Producer name:    pytorch
Producer version: 1.6
Domain:
Model version:    0
Doc string:
----------------------------------------------------------------
info nps 4 time 204003 nodes 900 hashfull 0 score cp 93 depth 8 pv 7g7f 3c3d 2g2f 8c8d 2f2e 4a3b 2e2d 2c2d
All Playouts       :      900
Pre Simulated      :        0
Thinking Time      :  204.003 sec
Winning Percentage :  52.5785%
Playout Speed      :        4 PO/sec
readyok

初期局面を探索する。

position startpos
go byoyomi 5000

以下のように表示される。

info nps 351568 time 4516 nodes 1587682 hashfull 158 score cp 97 depth 50 pv 7g7f 8c8d 2g2f 8d8e 8h7g 3c3d 7i6h 4c4d 2f2e 2b3c 6i7h 4a3b 3i4h 3a4b 5g5f 4b4c 6g6f 5c5d 6h6g 6a5b 4i5h 7a6b 3g3f 7c7d 2i3g 8a7c 4g4f 6c6d 4h4g 6b6c 2h2i 8b8a 9g9f 9c9d 1g1f 1c1d 7g6h 3c4b 5i6i 5a4a 3f3e 3d3e 4f4e 4d4e 6h3e 6d6e 6f6e 4c3d 3e4d 4b3c
bestmove 7g7f

初期局面で、約35万NPSがでている。
V100×8の環境では、初期局面で約25万NPSである。

NPS測定

floodgateからサンプリングした100局面で、NPSを測定した(測定用スクリプト)。
比較のためにV100×8の結果も載せている。

$ python3 benchmark.py --gpus 8 --threads 3 --engine /home/ubuntu/DeepLearningShogi/usi/bin/usi --model /home/ubuntu/model_rl_val_wideresnet10_selfplay_424.onnx

	平均	中央値	最小値	最大値
A100	272,388	267,825	158,001	369,383
V100	219,281	219,567	137,441	276,373
A100/V100	1.24	1.22	1.15	1.34

V100と比較すると、NPSが平均で1.25倍になっている。

カタログスペックでは、TensorCoreの性能は、

V100	125 TFLOPS
A100	312 TFLOPS
A100/V100	2.496

なので、もっと性能がでても良さそうである。

推論速度比較

純粋に、GPUに推論の速度を比較してみた(測定コード)。
floodgateからサンプリングした10万局面をバッチサイズ128で推論した際の時間を比較する。

$ ./test model_rl_val_wideresnet10_selfplay_424.onnx floodgate.hcpe 100000 7 128

A100	1442 ms
V100	2554 ms
A100/V100	1.77

推論速度のみであれば、1.77倍となった。
すべてのGPU演算でTensorCoreを使用しているわけではないので、これくらいで妥当なのかもしれない。

探索時のNPSの比がこれより下がっているのは、探索にボトルネックがあるので、まだ改良の余地があるかもしれない。

まとめ

AWSのA100インスタンスで、dlshogiの探索速度がどれだけ上がるか測定を行った。
結果、V100と比較してNPSが平均1.25倍になることがわかった。

再来週の電竜戦には、A100インスタンスを借りて参加するかもしれません。

2020-10-31

cshogiをPYPIに登録

cshogiは、今までPYPIに登録していなかったので、GitHubのReleaseのWheelファイルのURLを指定してインストールする必要があった。
PYPIに登録することで、以下のコマンドで簡単にインストールできるようにした。

pip install cshogi

Python用の将棋ライブラリとしては、python-shogiがあるが、cshogiはベースの部分をC++で実装しているので、10倍近く高速に動作する。

しかし、ソースからインストールする際にC++のビルド環境が必要になるため、インストールに多少ハードルがあった。
事前にビルドしたWheelをGitHubのReleaseページからURLを指定してインストールできるようにしていたが、URLをいちいち確認する必要があるため、Python公式のレポジトリであるPYPIに登録を行った。

以前にも登録しようとしたが、Linux用のWheelファイル作成にCentOS6を使用する必要があり、環境構築が煩雑なため保留したままになっていた。
今回、Linux用Wheel作成用のDockerイメージを使えば比較的簡単にできることが分かったので対応した。

以下、PYPI向けLinux用Wheelファイル作成手順を残しておく。

Dockerコンテナ実行

Ubuntuでは、PYPI向けのWheelが作成できないため、manylinuxコンテナを使用する。
x64向けのmanylinux2010_x86_64を使用した。

docker run --rm -it -v $(pwd):/workspace -w /workspace quay.io/pypa/manylinux2010_x86_64

ソースclone

git clone https://github.com/TadaoYamaoka/cshogi.git

Pythonのバージョン別Wheel作成

WheelファイルはPythonのバージョン別に作成する必要がある。
manylinuxコンテナでは、複数バージョンのPythonが用意されている。

ls /opt/python/

で、用意されているPythonのバージョンが調べられる。

以下では、Python 3.7向けを例に説明する。

ビルドに必要なパッケージインストール

/opt/python/cp37-cp37m/bin/pip install numpy
/opt/python/cp37-cp37m/bin/pip install Cython

Wheelファイル作成

cd cshogi
/opt/python/cp37-cp37m/bin/python setup.py bdist_wheel

distディレクトリにWheelファイルが作成される。
ここで作成されたWheelファイルでは、まだPYPIに登録できない。

auditwheelツールを使用して、PYPIに登録可能なWheelに変換を行う。

cd dist
auditwheel repair cshogi-0.0.6-cp37-cp37m-linux_x86_64.whl

dist/wheelhouseに、変換済みのWheelファイルが作成される。
ファイル名は、以下のようにlinuxだったところが、manylinux2010になっている。

cshogi-0.0.6-cp37-cp37m-manylinux2010_x86_64.whl

同様の手順で、複数のPythonのバージョン向けのWheelファイルが作成できる。

2020/11/1 追記

Ubuntu 18.04 LTS標準のPython3のpip3コマンドでは、インストールできないようである。
manylinux2010は、pip 19.0以上が必要だが、UbuntuのPython3は、pip 9.0.1のためである。
Ubuntu標準のPython3にインストールするには、事前にpipをアップグレードする。

python3 -m pip install --upgrade pip

その後、pip3コマンドでインストールできる。

pip3 install cshogi

なお、manylinux1コンテナを使用すれば、標準のpipのバージョンに対応したWheelを作成できるが、OSが古すぎるためnumpyのインストールから失敗するため、pipのアップグレードで対応することにした。

2020-09-21

【勉強ノート】不完全情報ゲームのアルゴリズム２

不完全情報ゲーム CFR

前回はじゃんけんを例にして後悔の最小化アルゴリズムを試した。
今回は、クーンポーカーを例にして反事実的後悔（Counterfactual Regret（CFR））最小化アルゴリズムを試す。
※Counterfactual Regretに訳語を当てている日本語の論文は見つからなかったので、Google翻訳のままの訳語を使用している。

反事実的後悔（Counterfactual Regret）最小化

前回のじゃんけんの例では、2人が同時に手を出して1回で勝負がつくため、すぐに後悔を計算することができた。

一方、展開型ゲームでは、2人が交互に手を出して、ゲームの終端に達した際にはじめて勝敗が分かる。
それぞれのノードでの後悔は、すぐには計算できず、なんらかの方法でゲーム木を展開して計算する必要がある。

反事実的後悔（Counterfactual Regret）最小化アルゴリズムは、後悔最小化アルゴリズムを確率を用いて展開型ゲームにも適用可能としたアルゴリズムである。

以下、数式での説明になるため、はじめに記号の定義を行って、利得、後悔、累積後悔、戦略、それぞれの数式とその意味について解説する（数式は一見意味が分からないが、じっくり眺めていると意味が見えてくるものである）。

その後、クーンポーカーのサンプルコードの実装を確認する。

記号の定義

A(I)：情報セットIの合法アクションのセット
t, T：タイムステップ。情報セットへの訪問ごとに加算。
履歴h：ゲームのルートから始まる一連のアクション（偶然の結果を含む）
$\pi^\sigma(h)$ ：戦略 $\sigma$ を用いたときのゲーム履歴hへの到達確率
$\pi_{-i}^\sigma(h)$ ：ゲーム状態に達するまでにプレイヤーi用いた行動の確率を1とした場合の、戦略 $\sigma$ を用いたときのゲーム履歴hへの到達確率。つまり、プレイヤーiを除いたプレイヤーの行動による履歴hへの到達確率
$\sigma_{I \to a}$ ：情報セットIでアクションaをとる確率が1であることを示す
Z：すべての端末ゲーム履歴のセット
$h \sqsubset z$ ： $z \in Z$ において、hが非終端ゲーム履歴であることを示す
$u_i(z)$ ：端末履歴zにおけるプレイヤーiの利得

反事実値(counterfactual value)

履歴hでの反事実値(counterfactual value)（※利得に相当するもの）を、以下の通り定義する。
$\displaystyle v_i(\sigma, h) = \sum_{z \in Z, h \sqsubset z} \pi_{-i}^\sigma (h) \pi^\sigma (h, z) u_i(z) \tag{1}$

終端の利得 $u_i(z)$ に、履歴hから終端zでまでの確率 $\pi^\sigma (h, z)$ を掛けることで期待値を計算し、それにi以外のプレイヤーの行動によってルートから履歴hに到達する確率 $\pi_{-i}^\sigma (h)$ で重み付けしている。

ノードに到達する確率が低い場合は、たとえ負けても後悔も小さくなるというのは、直感的にも理解できる。

反事実後悔

履歴hでアクションaを実行しなかったという反事実後悔を、以下の通り定義する。
$\displaystyle r(h, a) = v_i(\sigma_{I \to a}, h) - v_i(\sigma, h) \tag{2}$

前回の後悔最小化アルゴリズムの利得を反事実値に置き換えている。

情報セットIでアクションaを実行しなかったという反事実後悔

$\displaystyle r(I, a) = \sum_{h \in I} r(h, a) \tag{3}$

ここで、 $r_i^t(I,a)$ を、プレーヤーiに属する情報セットIで、プレイヤーが $\sigma^t$ を使用するときの、アクションaを実行しなかったときの後悔とする。

情報セットは、観察可能な状態が一致するすべての状態を含むため（観測不能な相手の手札は複数の状態をとりうる）、情報セットIに到達するすべての履歴hの反事実後悔の和になる。

累積反事実後悔

累積反事実後悔は次のように定義される。
$\displaystyle R_i^T(I,a) = \sum_{t=1}^T r_i^t(I,a) \tag{4}$

戦略

非負の反事実後悔Rを後悔最小化アルゴリズムに適用して、以下の通り、戦略を取得する。
$R_i^{T,+}(I,a) = max(R_i^T(I,a), 0)$ とし、

$\displaystyle \sigma_i^{T+1}(I,a) = \left\{ \begin{array}{ll} \frac{R_i^{T,+}(I,a)}{\sum_{a \in A(I)}R_i^{T,+}(I,a)} & \mbox{if }\sum_{a \in A(I)} R_i^{T,+}(I,a) > 0 \\ \frac{1}{|A(I)|} & \mbox{otherwise} \\ \end{array} \right. \tag{5}$

混合戦略が、正の累積反事実後悔の比率になることを示している。
すべてのアクションで累積反事実後悔0になる場合があるため、その場合は等確率となる。

前回の後悔最小化アルゴリズムと異なるのは式(1)のみであり、それ以外は考え方は同じである。

クーンポーカーの例

クーンポーカーを例にして、反事実的後悔最小化アルゴリズムを試す。

講義のページでJavaで実装したサンプルコードが、提供されているので、それの実装の確認を行う。
http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/KuhnTrainer.java

クーンポーカーについて

クーンポーカーは、ポーカーを単純化した不完全情報ゲームである。
カードは3枚のみで、2人のプレイヤーにランダムに1枚ずつ配られる（残り1枚は未使用）。
先手はパスかベットを行う。
その後、後手がパスかベットを行う。
後手がベットの場合、先手はパスかベットを行う。
勝敗は以下の通り決まる。
f:id:TadaoYamaoka:20200921125718p:plain

サンプルコードの実装

サンプルコードは、前回のじゃんけんのサンプルコードと骨格は同じである。

主に異なるのは、カードをランダムで配る部分、ノードごとに後悔累積を計算する点、アクションごとの利得を計算する部分である。
カードをランダムで配る部分は、本質ではないので省略する。

式(3)の情報セットの反事実後悔は、反復を繰り返すことで、異なる履歴hで同一のノードに到達するとこで近似的に求めている。

アクションごとの利得（反事実値(counterfactual value)）を計算する部分は、上記で解説した式(1)に該当する。
これは、再帰的に処理することで実装できる。

引数p0、p1が、履歴hへの到達確率 $\pi_{-i}^\sigma (h)$ になっており、相手プレイヤーのアクションの選択確率のみ計算されている。
また、相手の利得を自分の利得とする場合に符合を反転させている点に注意が必要である。

    private double cfr(int[] cards, String history, double p0, double p1) {
        int plays = history.length();
        int player = plays % 2;
        int opponent = 1 - player;
        if (plays > 1) {
            boolean terminalPass = history.charAt(plays - 1) == 'p';
            boolean doubleBet = history.substring(plays - 2, plays).equals("bb");
            boolean isPlayerCardHigher = cards[player] > cards[opponent];
            if (terminalPass)
                if (history.equals("pp"))
                    return isPlayerCardHigher ? 1 : -1;
                else
                    return 1;
            else if (doubleBet)
                return isPlayerCardHigher ? 2 : -2;
        }               

        String infoSet = cards[player] + history;
        Node node = nodeMap.get(infoSet);
        if (node == null) {
            node = new Node();
            node.infoSet = infoSet;
            nodeMap.put(infoSet, node);
        }

        double[] strategy = node.getStrategy(player == 0 ? p0 : p1);
        double[] util = new double[NUM_ACTIONS];
        double nodeUtil = 0;
        for (int a = 0; a < NUM_ACTIONS; a++) {
            String nextHistory = history + (a == 0 ? "p" : "b");
            util[a] = player == 0 
                ? - cfr(cards, nextHistory, p0 * strategy[a], p1)
                : - cfr(cards, nextHistory, p0, p1 * strategy[a]);
            nodeUtil += strategy[a] * util[a];
        }

        for (int a = 0; a < NUM_ACTIONS; a++) {
            double regret = util[a] - nodeUtil;
            node.regretSum[a] += (player == 0 ? p1 : p0) * regret;
        }

        return nodeUtil;
    }

実行結果

実行すると以下のように表示される。

Average game value: -0.05496601204878785
   1: [0.849753597014784, 0.15024640298521594]
  1b: [0.9999985021329627, 1.4978670373388295E-6]
  1p: [0.6644684285945989, 0.33553157140540113]
   2: [0.9999775448613657, 2.245513863439736E-5]
  2b: [0.6616830625007863, 0.3383169374992136]
  2p: [0.9999834630233202, 1.6536976679856157E-5]
 2pb: [0.5159302151546348, 0.48406978484536534]
   3: [0.5475228231479871, 0.4524771768520129]
  3b: [1.4987829882135705E-6, 0.9999985012170118]
  3p: [1.4987829882135705E-6, 0.9999985012170118]
 3pb: [1.3706996079562322E-6, 0.9999986293003921]

各履歴での、各アクション（パスとベット）それぞれの利得（反事実値(counterfactual value)）が表示されている。
ルートでの平均利得は、-0.0549となっており、お互いナッシュ均衡でプレイした場合、先手が不利になることを示している。

Wikipediaの解説によると、理論値は-1/18（=0.0555）なので、近い値になっている。

まとめ

不完全情報ゲームの代表的なアルゴリズムであるCFRについて解説を行った。
CFRは⼆⼈零和不完全情報ゲームの場合にナッシュ均衡に収束すること証明されているが、この記事では証明については触れなかった（証明に興味のある方は論文を参照してほしい）。

2020-09-19

【勉強ノート】不完全情報ゲームのアルゴリズム

不完全情報ゲームのアルゴリズムについて詳しくなりたいと思い、不完全情報ゲームの基本的なアルゴリズムであるCFRについて調べた。

不完全情報ゲームのアルゴリズムは比較的新しいということもあり、日本語の書籍はないため、こちらの大学の講義の資料を参照した。
An Introduction to Counterfactual Regret Minimization

じゃんけんにおける後悔の最小化

CFRの前に、後悔の概念をじゃんけんを例に説明する。

相手の混合戦略が、( 0.4, 0,3, 0.3 ) の場合の最適な混合戦略を、後悔を最小化することによって求める。

混合戦略 ( 0.4, 0,3, 0.3 )は、Rock(グー)、Paper(パー)、Scissors(チョキ)を、それぞれ0.4、0.3、0.3の確率で出す戦略を意味する。
この場合の最適な戦略は、何になるだろうか。

後悔の最小化アルゴリズム

自分が現在の混合戦略から選んだ手の利得(utility)と、他のある手を選んだ場合の利得の差を、後悔と呼ぶ。
後悔 = 他のある手を選んだ場合の利得 - 選んだ手の利得

これを、それぞれ手ごとに求め累積後悔に加算する。
累積後悔(ある手) += 他のある手を選んだ場合の利得 - 選んだ手の利得

累積後悔を使って、現在の混合戦略を決める。
混合戦略は、正の累積後悔の比率によって求める。
つまり、累積後悔が負の場合0として、正の場合はその値を使用して、正の後悔の合計で割った値を求める。

直感的には、選んだ手よりも良い手があれば、その手をより選びやすくしている。

以上を繰り返すことで、後悔を最小とする混合戦略が得られる。

最小の後悔戦略に収束するのは、最終的な混合戦略ではなく、すべての反復の混合戦略の平均戦略になる点に注意が必要である。

個々の反復の後悔と戦略は不安定である。一時的に後悔が負になる手は選択されず、反復中にはそのような状態が起きる。

サンプルコード

上記の講義のページに、Javaで実装されたサンプルコードが提供されている。
http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/RPSTrainer.java

これを実行してみると、

[3.418489010989012E-5, 0.9999614651098901, 4.349999999999999E-6]

という結果が得られた。

混合戦略(0.4, 0.3, 0.3)に対する最適な戦略は、(0, 1, 0)であることを示している。

検証

最適な戦略は(0.3, 0.4, 0.3)ではないか？と思うかもしれない。
混合戦略からランダムにサンプリングすることで確かめてみた。
cfr-cpp/RPS_test.cpp at master · TadaoYamaoka/cfr-cpp · GitHub

10,000,000回繰り返した利得の平均は、0.0999649になる。

混合戦略を(0, 1, 0)から、(0.3, 0.4, 0.3)に変更すると、0.0101261になる。

確かに、混合戦略(0, 1, 0)の方が、平均利得が高くなっている。

相手の混合戦略がナッシュ均衡の場合

相手の混合戦略が、じゃんけんのナッシュ均衡である(1/3, 1/3, 1/3)の場合に、最適な戦略を学習できるか試してみた。
サンプルコードの相手の戦略を以下の通り変更する。

oppStrategy = { 1.0/3, 1.0/3, 1.0/3 };

結果は、

[0.07988949151946023, 0.018809190929443522, 0.9013013175510962]

となった。
(1/3, 1/3, /3)とはかけ離れているが、本当だろうか？

サンプルコードを確認すると、getActionの実装が、累積和法になっていた。

    public int getAction(double[] strategy) {
        double r = random.nextDouble();
        int a = 0;
        double cumulativeProbability =  0;
        while (a < NUM_ACTIONS - 1) {
            cumulativeProbability += strategy[a];
            if (r < cumulativeProbability)
                break;
            a++;
        }
        return a;
    }

cumulativeProbability の加算で浮動小数の丸めが発生するため、この実装はよろしくない。
ランダムにも線形合同法が使用されている。

そこで、Walker's alias法で実装されているC++のdiscrete_distributionを使って実装し直してみた。
cfr-cpp/RPSTrainer.cpp at master · TadaoYamaoka/cfr-cpp · GitHub

これを実行すると、

[0.204437, 0.190428, 0.605135]

という結果が得られた。
やはり、じゃんけんのナッシュ均衡(1/3, 1/3, 1/3)にはなっていない。

実は相手の戦略が(1/3, 1/3, 1/3)の場合、どんな戦略であっても平均利得は同じなため、(1/3, 1/3, 1/3)には収束しない。

相手の混合戦略も学習した場合

相手の混合戦略を固定ではなく、同様に後悔の最小化アルゴリズムで混合戦略を学習させた場合、ナッシュ均衡になるか確認してみた。
cfr-cpp/RPSTrainer2.cpp at master · TadaoYamaoka/cfr-cpp · GitHub

実行結果は、

[0.339249, 0.334887, 0.325864]

となり、ナッシュ均衡(1/3, 1/3, 1/3)を学習できている。

まとめ

じゃんけんを例に、後悔の最小化アルゴリズムを実装して、最適な混合戦略を学習できるか確かめた。

次は、講義資料の3章のクーンポーカーの例で、反事実的後悔(Counterfactual Regret)の最小化を試したい。

2020-09-12

dlshogiのINT8対応

dlshogi コンピュータ将棋 TensorRT INT8

前回の記事にも書いたが、dlshogiは、V100のTensorCoreがINT8に対応していないため、INT8対応を行っていなかった。
しかし、AWSのG4インスタンスでは、NVIDIA T4 Tensor Core GPUが利用できるため、INT8に対応することにした。
また、今後クラウドでA100が提供されたときに、すぐにINT8を試せるようになる。

dlshogiをINT8に対応させる際に、Pytorchで出力した可変バッチサイズのONNXモデルを使用するとキャリブレーションがうまくできないという問題が起きたため、解決方法について残しておく。

キャリブレーションについては、前回の記事を参照。

可変バッチサイズのONNXモデルでキャリブレーションした際のエラー

PyTorchで、以下のようにdynamic_axesを付けて、ONNXを出力し、

torch.onnx.export(model, (x1, x2), args.onnx,
    verbose = True,
    do_constant_folding = True,
    input_names = ['input1', 'input2'],
    output_names = ['output_policy', 'output_value'],
    dynamic_axes={
        'input1' : {0 : 'batch_size'},
        'input2' : {0 : 'batch_size'},
        'output_policy' : {0 : 'batch_size'},
        'output_value' : {0 : 'batch_size'},
        })

TensorRTで、サンプルプログラムと同じように、キャリブレーションを行おうとすると、以下のエラーが発生する。

Calculating Maxima
C:\source\rtSafe\safeRuntime.cpp (25) - Cuda Error in nvinfer1::internal::DefaultAllocator::allocate: 2 (out of memory)
C:\source\rtSafe\safeRuntime.cpp (25) - Cuda Error in nvinfer1::internal::DefaultAllocator::allocate: 2 (out of memory)

issuesを調べたところ、同様のエラーが報告されていた。
When I use the TensorRT to infer MoblieNet in the INT8 mode,I meet the following errors.How can I solve the problems? · Issue #688 · NVIDIA/TensorRT · GitHub

しかし、再実行して解決したとしてクローズされていた。
こちらでは、何度やっても同様のエラーになる。

issuesでは、TensorRT 7.0では、dynamic shapeに対応していないため、TensorRT 7.1を使うように書き込みがあったので、TensorRT 7.1.3.4にしてみたが解決しない。

固定バッチサイズで試す

固定バッチサイズだと、うまくいくかもと思い試してみた。
PyTorchでONNX出力する際に、dynamic_axesを削除して、入力をバッチサイズ256にした。

再び、キャリブレーションを行ったが、今度は、別のエラーが発生した。

Calculating Maxima
Starting Calibration with batch size 256.
Explicit batch network detected and batch size specified, use execute without batch size instead.
C:\source\builder\cudnnCalibrator.cpp (707) - Cuda Error in nvinfer1::builder::Histogram::add: 700 (an illegal memory access was encountered)
FAILED_ALLOCATION: Unknown exception
C:\source\builder\cudnnCalibrator.cpp (703) - Cuda Error in nvinfer1::builder::Histogram::add: 700 (an illegal memory access was encountered)
FAILED_ALLOCATION: Unknown exception
C:\source\rtSafe\cuda\caskConvolutionRunner.cpp (233) - Cuda Error in nvinfer1::rt::task::CaskConvolutionRunner::allocateContextResources: 700 (an illegal memory access was encountered)
FAILED_EXECUTION: Unknown exception
  Calibrated batch 0 in 2.18174 seconds.
Cuda failure
Error: an illegal memory access was encountered
Aborting...

メモリ関連のエラーなのでバッチサイズを小さくして試したところ、エラーはでなくなったが、作成されたキャリブレーションキャッシュを使用して推論してみると、floodgateからサンプリングした局面の予測精度は、

move accuracy = 0.00741186
value accuracy = 0.4999
value mse = 0.151279

となり、精度が全くでていない。

バッチサイズ1で試す

ダメ元でONNXを固定バッチサイズ1でキャリブレーションしてみたところ、

move accuracy = 0.460036
value accuracy = 0.721254
value mse = 0.0232871

となり、今度は精度が出るようになった。
ただし、キャリブレーションに数分程度の時間がかかる。

なお、TensorRTのキャリブレーション結果は、キャッシュに保存することが可能で、バッチサイズ1でキャリブレーションした結果を、可変バッチサイズのONNXモデルで使用することができた。
キャリブレーションのキャッシュは、以下のようなテキスト形式で記述されており、バッチサイズには依存していないようである。

TRT-7000-EntropyCalibration2
input1: 7f800000
input2: 7f800000
143: 3c0779a5
144: 3b59804a
145: 3b96d0e5
146: 3c209593
147: 3c244dfc
148: 3bd96b2c
...

精度比較

なんとかキャリブレーションができるようになったので、FP16モードと精度を比較した。
キャリブレーションのデータサイズを増やした場合に、どのように精度が変わるかも比較した（キャリブレーションにはfloodgateからサンプリングした局面をキャリブレーションに使用した）。

公式ドキュメントには、ImageNet分類ネットワークのキャリブレーションには約500枚の画像で十分と書かれている。

	move accuracy	value accuracy	value mse
FP16	0.467448	0.723958	0.0229941
1024サンプル	0.460036	0.721254	0.0232871
4096サンプル	0.460437	0.721755	0.0233805
8192サンプル	0.462841	0.721855	0.0232868
16384サンプル	0.463542	0.719351	0.0231744
32768サンプル	0.460437	0.723558	0.0231636

1024サンプルでは、policyの精度が0.7%、valueの精度0.27%が落ち込んでいる。
キャリブレーションに使用するサンプル数を上げると、ある程度回復がみられるが、policyが上がるとvalueが下がったり安定していないようである。

FP32→FP16では、ほとんど精度が落ちなかったのと比較すると、ある程度精度は犠牲になるようだ。

推論速度

FP16とINT8の推論速度の比較は以下の通り。

floodagateからサンプリングした10万局面を、バッチサイズ256で推論した際の時間

モード	推論時間(ms)
FP16	277.367
INT8	185.939

推論速度は、約1.49倍になっている。

NVIDIAの資料によると、FP16→INT8で、TFLOPSは2倍になるようなので、もっと推論速度が上がってほしいが、すべてTensorCoreで計算しているわけではないので今回の結果は妥当なのかもしれない。

出典：https://www.nvidia.com/content/apac/gtc/ja/pdf/2018/2051.pdf

まとめ

dlshogiのINT8対応について、キャリブレーションをうまく行うために苦労したので、解決方法を記事にまとめた。

INT8に対応したことで、推論速度が2080 Tiで、約1.49倍になった。
予測精度が落ちているため、推論速度が上がった分とバランスして強さにどれくらい影響がでるのか別途測定したい。

2020-09-12

TensorRTでINT8を試す

TensorRT INT8

Turing世代以降のTensorCoreは、INT8に対応している。
GeForce 2080TiでもINT8が利用できるため、試してみた。

なお、V100のTensorCoreは、INT8には対応していないため、dlshogiでは、INT8対応は行っていなかったが、AWSのG4インスタンスでは、NVIDIA T4 Tensor Core GPUが利用できるため、INT8に対応することにした。

dlshogiのINT8対応は別記事で記載予定だが、この記事では、INT8のサンプルコードの動かし方について記述する。

サンプルコード

TensorRTをダウンロードして、圧縮ファイルを解凍したsampleディレクトリにあるsampleINT8に、INT8のサンプルが含まれる。

GitHubにも同様のコードがあるが、Windowsで試す場合は、ダウンロードしたzipに含まれるサンプルだとあらかじめWindowsのプロジェクトファイルになっているので試しやすい。

サンプルコードの説明は、README.mdにある。
GitHubで参照した方が見やすい。

キャリブレーションについて

INT8では、量子化を行うため、各層のダイナミックレンジの設定が必要になる。
ダイナミックレンジは、各層に個別に設定することもできるが、データを使用して計測（キャリブレーション）することもできる。
sampleINT8は、キャリブレーションを行うサンプルになっている。

キャリブレーションについては、以下のドキュメントに記載がある。
Developer Guide :: NVIDIA Deep Learning TensorRT Documentation

MNISTモデルダウンロード

このサンプルコードを動かすには、MNISTのデータセットと、CaffeでトレーニングしたMNISTのモデルが必要になる。

データセットのダウンロード

README.mdにある通り、get_mnist.shを使用して、MNISTデータセットをダウンロードする。
bashとwgetが必要なため、Windowsの場合は、MSYS2やWSLを使う。
データセットは、「data\mnist」に配置する。

Caffeのトレーニング済みモデル

Caffeをインストールして、トレーニングを動かすのは大変なので、検索して見つかった以下のレポジトリからトレーニング済みモデルをダウンロードした。
https://github.com/t-kuha/nn_models/find/master

必要なのは、

caffe/mnist_lenet/lenet.prototxt
caffe/mnist_lenet/lenet_iter_10000.caffemodel

の2つのファイルである。
ダウンロードして、「data\mnist」に配置する。
それぞれ以下の通り、リネームする。

deploy.prototxt
mnist_lenet.caffemodel

実行結果

ビルドして実行すると、FP32、FP16、INT8でのMNISTの推論時間が以下のように表示される。

&&&& RUNNING TensorRT.sample_int8 # H:\src\TensorRT-7.0.0\samples\sampleINT8\\..\..\bin\sample_int8.exe
[09/12/2020-10:49:18] [I] Building and running a GPU inference engine for INT8 sample
[09/12/2020-10:49:18] [I] FP32 run:1800 batches of size 32 starting at 16
[09/12/2020-10:49:21] [I] [TRT] Detected 1 inputs and 1 output network tensors.
[09/12/2020-10:49:21] [W] [TRT] Current optimization profile is: 0. Please ensure there are no enqueued operations pending in this context prior to switching profiles
[09/12/2020-10:49:21] [I] Processing next set of max 100 batches
(略)
[09/12/2020-10:49:22] [I] Processing next set of max 100 batches
[09/12/2020-10:49:22] [I] Top1: 0.998542, Top5: 1
[09/12/2020-10:49:22] [I] Processing 57600 images averaged 0.00654066 ms/image and 0.207457 ms/batch.
[09/12/2020-10:49:22] [I] FP16 run:1800 batches of size 32 starting at 16
[09/12/2020-10:49:30] [I] [TRT] Detected 1 inputs and 1 output network tensors.
[09/12/2020-10:49:30] [W] [TRT] Current optimization profile is: 0. Please ensure there are no enqueued operations pending in this context prior to switching profiles
[09/12/2020-10:49:30] [I] Processing next set of max 100 batches
(略)
[09/12/2020-10:49:31] [I] Processing next set of max 100 batches
[09/12/2020-10:49:31] [I] Top1: 0.998542, Top5: 1
[09/12/2020-10:49:31] [I] Processing 57600 images averaged 0.00548979 ms/image and 0.174126 ms/batch.
[09/12/2020-10:49:31] [I] INT8 run:1800 batches of size 32 starting at 16
[09/12/2020-10:49:31] [I] [TRT] Reading Calibration Cache for calibrator: EntropyCalibration2
[09/12/2020-10:49:31] [I] [TRT] Generated calibration scales using calibration cache. Make sure that calibration cache has latest scales.
[09/12/2020-10:49:31] [I] [TRT] To regenerate calibration cache, please delete the existing one. TensorRT will generate a new calibration cache.
[09/12/2020-10:49:38] [I] [TRT] Detected 1 inputs and 1 output network tensors.
[09/12/2020-10:49:38] [W] [TRT] Current optimization profile is: 0. Please ensure there are no enqueued operations pending in this context prior to switching profiles
[09/12/2020-10:49:38] [I] Processing next set of max 100 batches
(略)
[09/12/2020-10:49:38] [I] Processing next set of max 100 batches
[09/12/2020-10:49:38] [I] Top1: 0.998524, Top5: 1
[09/12/2020-10:49:38] [I] Processing 57600 images averaged 0.00454334 ms/image and 0.144106 ms/batch.
&&&& PASSED TensorRT.sample_int8 # H:\src\TensorRT-7.0.0\samples\sampleINT8\\..\..\bin\sample_int8.exe

推論時間と精度は、以下の通り。

モード	推論時間(ms/image)	推論時間(ms/batch)	精度
FP32	0.00654066	0.207457	0.998542
FP16	0.00548979	0.174126	0.998542
INT8	0.00454334	0.144106	0.998524

推論時間は、FP16→INT8で、1.2倍になっている。
精度は、INT8でわずかに低下している。

まとめ

TensorRTのINT8のサンプルコードの動かし方について説明を行った。
ネットに情報がほとんどなかったため、結構苦労した（特に、Caffeのモデルの準備のあたり）。

PyTorchで出力した可変バッチサイズのONNXモデルの場合、このサンプルの通りには行かず、さらに苦労したのだが、別の記事にする。

2020-09-06

電竜戦(予行演習3)の結果報告

電竜戦 dlshogi コンピュータ将棋

昨日開催された電竜戦(予行演習3)にdlshogiも参加し、結果は34チーム中4位でした。
第1回コンピュータ将棋オンライン電竜戦予行演習3 勝敗表

DL勢同士の対局

CrazyShogi

CrazyShogiのとの対局は、危なげなく勝ちました。
第1回電竜戦棋譜中継(単一棋譜)

AobaZero

AobaZeroとの対局は、後手番で80手くらいで評価値400くらい劣勢になっていました。
その後、AobaZeroに読み抜けがあったのか、dlshogiが徐々に優勢になって勝ち切りました。
第1回電竜戦棋譜中継(単一棋譜)

AobaZeroの序盤はかなり強そうです。
dlshogiは初期局面集を使用しているため序盤の局面はあまり学習していないこと、モデルのサイズが小さいこと、AobaZeroの方が学習リソースが多いことなどが、序盤の強さに影響していそうです。
序盤に対しては、改善が必要そうなので検討することにします。

使用したモデル

学習途中のSwishのモデルを使用しました。
過去のdlshogiの強化学習で生成した局面を学習させています。

2018年から開始して、390サイクルまで強化学習を行っていますが、途中で条件変更やバグ修正、改良を行っているため、あまりに古い局面は質が良くないため、2020年から開始したリーグ戦で生成した200サイクル目以降の局面を学習させています。

水匠2 1000万ノード固定に対する強さは、Swishなしの最新のモデルよりも高くなっています。

   # PLAYER                            :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 normal10_swish_341                :    39.5   43.1   139.0     250    56      58  133   12  105     5
   2 wideresnet10_selfplay_387         :    32.8   48.1   105.5     193    55      59  101    9   83     5
   3 normal10_swish_326                :    25.8   34.6   278.5     500    56      51  268   21  211     4
   4 normal10_swish_337                :    25.3   42.3   134.0     250    54      88  130    8  112     3
   5 YaneuraOu NNUE 4.91 64AVX2BMI2    :     0.0   ----   851.0    1693    50      98  817   68  808     4

White advantage = 17.19 +/- 7.79
Draw rate (equal opponents) = 4.20 % +/- 0.46

※wideresnet10_selfplay_387がSwishなし
※normal10_swish_xxxが200サイクル以降の局面を学習させたSwishのモデル、数値は何サイクル目までのデータを学習したか
※秒読み3秒

ただし、直接対局させると、最新のSwishなしのモデルの方が強いです。

   # PLAYER                       :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 wideresnet10_selfplay_387    :     0.0   ----    66.0     114    58      96   61   10   43     9
   2 normal10_swish_346           :   -56.0   61.6    48.0     114    42     ---   43   10   61     9

White advantage = 18.94 +/- 32.96
Draw rate (equal opponents) = 8.91 % +/- 2.69

生成した局面をすべて学習しきった後には、上回ることを期待しています。

20ブロック+256フィルタ+Swishのモデルも学習しており、そちらも強くなれば候補になります。

Resnetの構成の変更

dlshogiでは、過去の経緯により、あまり検証を行わずにResnetの構成をpre-activation構成にしていました。
今回学習し直す際に、オリジナルのResnet構成も学習させたところ、floodgateの棋譜に対する精度は高くなるようです。
まだ検証が十分にできていないので、別途検証する予定です。
今回は、オリジナルのResnet構成の方を使用しました。

本番大会に向けて

Swishのモデルを、最新のサイクルまで学習させることで、予行演習よりも強くできると期待しています。

dlshogiは、やねうら王ライブラリのソフトとも十分戦えるようになってきています。
しかし、トップとはfloodgateではレート差400近くあるので、まだ改良は必要だと思っています。

ハードウェア面では、いつから提供されるかは不明ですが、クラウドでA100が使用可能になればTensorCoreでINT8が使用できるようになるため、NPSが数倍になりそうという期待があります。
少なくとも電竜戦には間に合わなそうです。

最後に、電竜戦(予行演習3)に参加された皆様、運営の皆様、お疲れ様でした。