TadaoYamaokaの日記

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

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

前回はじゃんけんを例にして後悔の最小化アルゴリズムを試した。
今回は、クーンポーカーを例にして反事実的後悔(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 zz \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は⼆⼈零和不完全情報ゲームの場合にナッシュ均衡に収束すること証明されているが、この記事では証明については触れなかった(証明に興味のある方は論文を参照してほしい)。

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

不完全情報ゲームのアルゴリズムについて詳しくなりたいと思い、不完全情報ゲームの基本的なアルゴリズムである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)の最小化を試したい。

dlshogiの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倍になった。
予測精度が落ちているため、推論速度が上がった分とバランスして強さにどれくらい影響がでるのか別途測定したい。

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データセットをダウンロードする。
bashwgetが必要なため、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モデルの場合、このサンプルの通りには行かず、さらに苦労したのだが、別の記事にする。

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

昨日開催された電竜戦(予行演習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)に参加された皆様、運営の皆様、お疲れ様でした。

Likelihood of superiorityについて

昨日の記事でcshogiに、2つのプログラム間の連続結果からLOS(Likelihood of superiority)の算出を実装したことを書いたが、その計算式は、チェスで使用されている式をそのまま適用した。

LOSについて

測定された勝率がどれくらい確からしいかを表したのがLOSである。
100%で確実に強いと言える。

これは、仮説検定(H_0:P(勝ち)=P(負け)、H_1:P(勝ち)>P(負け))の片側検定のp値と等価である。
つまり、
LOS = 1 - p値
である。

チェスで使用されている近似式

Match Statistics - Chessprogramming wiki
の説明では、チェスで使用されている近似式は、勝ち、引き分け、負けの3項分布における、勝ちの確率が、以下の正規分布で近似できることを前提にしている。
\displaystyle
{\bf N} (N/2, N(1-draw\_ratio)) \\
= {\bf N}(N/2, wins + losses)

そうすると、勝ちと負けの差は、2つの正規分布の差になるので、それも正規分布になる。
正規分布の差の公式を当てはめると、
\displaystyle
{\bf N}(0, 2(wins + losses))
となる。

LOSは、これの積分で求められるので、誤差関数を使うと、
\displaystyle
LOS = \frac{1}{2} \left( 1 + erf( \frac{wins - losses}{\sqrt{2wins + 2losses}})  \right)
で計算できる。

この式については、以下のフォーラムに議論の過程が残っている。
Likelihood of superiority - TalkChess.com
Calculating the LOS (likelihood of superiority) from results - TalkChess.com


将棋に当てはめて良いか

3項分布の近似が
\displaystyle
{\bf N}(N/2, wins + losses)
となる部分の根拠を探したが、見つけられなかった。

将棋では、引き分けがチェスに比べて少ないため、むしろ2項分布で近似した方がよい気がしている。

2項分布を正規分布で近似する場合は、
\displaystyle
{\bf N}(N/2, N \cdot \frac{1}{2} \cdot \frac{1}{2})
となる。

N=100、引き分けが0の場合で、2つの正規分布の形を比較すると、
チェスの近似式

plt.plot(x, norm.pdf(x, 50, np.sqrt(100)))
f:id:TadaoYamaoka:20200829185708p:plain

2項分布

plt.plot(x, binom.pmf(x, 100, 0.5))
f:id:TadaoYamaoka:20200829185837p:plain

だいぶグラフの形が異なる。

まとめ

チェスで使用されているLOSについて、式がどのように導出されているかを調べた。
しかし、近似式の根拠をはっきり書いている記述が見つけられなかった。

チェスに比べて引き分けが少ない将棋に、近似式をそのまま当てはめると誤差が大きいような気がしている。
統計にそこまで詳しいわけでないので、統計に強い方のアドバイスがもらいたいと思っている。

cshogiにElo rating測定機能を追加

Cythonを使った高速なPythonの将棋ライブラリcshogiに、Elo rating測定機能を追加した。

誤差とLOS

連続対局を行い、Elo ratingと誤差(95%信頼区間)をレポートする。
何%の確率で強いと言えるかを表すLOS(Likelihood of superiority)も表示する。
LOSが95%を超えない場合は、追加で対局が必要であるという判断ができる。

以下のような形式で、結果がレポートされる。

100 of 100 games finished.
Apery_WCSC28 vs Gikou 2 (v2.0.2): 62-38-0 (62.0%)
Black vs White: 60-40-0 (60.0%)
Apery_WCSC28 playing Black: 36-14-0 (72.0%)
Apery_WCSC28 playing White: 26-24-0 (52.0%)
Gikou 2 (v2.0.2) playing Black: 24-26-0 (48.0%)
Gikou 2 (v2.0.2) playing White: 14-36-0 (28.0%)
Elo difference: 85.0 +/- 71.2, LOS: 99.2 %, DrawRatio: 0.0 %

cutechessを参考にしている。

複数プログラムでの測定

強さの測定は、同系統のプログラム同士だと勝率の差が付きやすくあまり信用ができない傾向がある。
そのため、系統が違う複数のプログラムを混ぜて測定を行う必要がある。

複数プログラムの対局結果から、Elo ratingを算出するのは単純ではなく、Bayesian Eloのようなベイズ推定で事後確率から事前確率を推測するアルゴリズムが必要になる。

Ordo

Leela Chess Zeroのテストでは、Ordoというツールが使用されている。
Ordoでは以下のような形式で、複数プログラムのレーティング差がレポートできる。

   # PLAYER                 :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W     D    L  D(%)
   1 sf                     :     0.0   ----  2073.5    4000    52      98  800  2547  653    64
   2 lc0_policytempdecay    :    -9.6    9.0   973.0    2000    49      85  338  1270  392    64
   3 lc0                    :   -16.6    9.5   953.5    2000    48     ---  315  1277  408    64

Ordoは、チェスのデファクトスタンダードであるPGNフォーマットを入力とする。
PGNには、プログラム名と結果を含む7個の必須の項目だけ記述されていればよく、将棋の対局結果も問題なく記述できる。

PGN出力機能

そこでcshogiにも、連続対局の結果をPGNで出力する機能を追加した。
出力したPGNをOrdoに入力すると、以下のような結果が表示できる。

PS C:\> ordo-win64.exe -Q -D -a 0 -A "Gikou 2 (v2.0.2)" -W -n8 -s1000 -U "0,1,2,3,4,5,6,7,8,9,10" -p games.pgn
0   10   20   30   40   50   60   70   80   90   100 (%)
|----|----|----|----|----|----|----|----|----|----|
***************************************************

   # PLAYER              :  RATING  ERROR  POINTS  PLAYED   (%)  CFS(%)    W    D    L  D(%)
   1 Apery_WCSC28        :    89.8   75.7    62.0     100    62      99   62    0   38     0
   2 Gikou 2 (v2.0.2)    :     0.0   ----    38.0     100    38     ---   38    0   62     0

White advantage = 75.74 +/- 39.21
Draw rate (equal opponents) = 0.00 % +/- 0.00

オプション「-W」を付けると、先手有利を補正した上のレーティングになる。
推定された先手のレーティングは、「White advantage」に表示される。
※チェスのツールのためWhiteが先手なので注意

上記は2プログラムの例だが、複数プログラムの対局の組み合わせで連続対局を行い、結果のPGNを連結して、Ordoに入力すれば、複数プログラムのレーティングが計算できる。

使い方

インストール方法

ソースからインストールする場合
pip install git+https://github.com/TadaoYamaoka/cshogi
ビルド済みwheelパッケージからインストールする場合

OS、Pythonのバージョン別にファイルが分かれているため、Releaseから対応するファイルのURLを指定する。
Windows、Python3.7の場合:

pip install https://github.com/TadaoYamaoka/cshogi/releases/download/v0.0.5/cshogi-0.0.5-cp37-cp37m-win_amd64.whl

コマンド例

> python -m cshogi.cli C:\apery_wcsc28\bin\apery_wcsc28_bmi2.exe C:\gikou2_win\gikou.exe --options1 Byoyomi_Margin:0 --options2 ByoyomiMargin:0 --byoyomi 100  --games 100 --opening records2016_10818.sfen --pgn games.pgn