TadaoYamaokaの日記

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

「GCT電竜」とdlshogi(NVIDIA GPU非搭載PC対応版)の公開

「GCT電竜」とdlshogi(NVIDIA GPU非搭載PC対応版)を公開します。

ダウンロード

Release 世界将棋AI 電竜戦バージョン(「GCT電竜」同梱) · TadaoYamaoka/DeepLearningShogi · GitHub

NVIDIA GPUに対応したTensorRT版と、NVIDIA GPU非搭載のWindows PCでも動作するOnnxRuntime版を含みます。

世界将棋AI 電竜戦で優勝した「GCT電竜」のモデルを含みます。
(GCTのモデルの開発者は加納さんです。配布は私の方で一本化して欲しいという意向です。)

OnnxRuntime版について

Windows 10 version 1903以降のPCであれば実行可能です。
ただし、探索速度は、TensorRT版にくらべて落ちます。

NVIDIA GeForce 2080Tiの場合、初期局面の探索速度に、以下の差があります。

バージョン NPS
OnnxRuntime版 5715
TensorRT版 41280

約7.2倍の差があります。

最高のパフォーマンスを出すには、TensorRT版をTensorCore搭載のNVIDIAGPU(NVIDIA GeForce 2080Tiなど)で動かすことを推奨します。

検討での使用

ShogiGUIの検討機能で使うには、一部対応できていない機能があります。
「深さ」の指定はできません。
候補手の数は、現状1手のみです。
時間無制限でも、UCT_NodeLimitで設定したノード数に達すると探索を終了します。

MultiPV対応は、Qhapaqさんからのプルリクエストをもらっているので、後日対応予定です。

検討では、設定でDNN_Batch_Sizeを256など大きめにした方がNPSが上がります。

【電竜戦】チームdlshogiのGCTが決勝リーグで優勝しました

本日開催されたコンピュータ将棋の大会「電竜戦」で、チームdlshogiのGCTが決勝リーグで優勝しました!

コンピュータ将棋の大会でディープラーニングを使用したソフトが優勝するのは初です。
2017年からdlshogiの開発を始めてやっと優勝までたどり着きました。

GCTについて

元々GCTは、加納さんがdlshogiを使用して開発したソフトです。
探索部分はdlshogiで、モデルの学習に使うデータをdlshogiとは別のもので行っています。

今大会では、私とチームで参加して、dlshogiの強化学習のデータや、学習方法、定跡作成方法など共有して、加納さんが主体でモデルの学習・定跡作成をしています。
今回の成果は、私のdlshogi単体では成し遂げたられなかったので、GCTが優勝してくれたことに感謝しています。

チームの経緯

加納さんとは将棋AI開発前からの知り合いで、以前から気楽に情報交換を行っていました。

NVIDIA A100が発表されてから、いつからクラウドで使用可能になるのかという話をしていたところ、ちょうどよいタイミングで、AWSで使用可能になりました。

AWSのA100のインスタンスp4d.24xlargeは、vCPU上限申請が必要なため、申請を行ったところ私の方では断られてしまいました
加納さんは申請が通ったため、貸してもらうことにしました。
その際、お互いチームとして参加するという話になり、インスタンスを貸してもらう代わりとして、GCTにはdlshogiの強化学習で生成したデータ(600万局面×直近100サイクル)を提供しました。

GCTとdlshogiの違い

GCTとdlshogiの違いは以下の通りです。

探索部 モデル 事前学習データ 強化学習データ 定跡
GCT dlshogiと同一 dlshogiで実験中のswishのモデル floodgate, elmo, AobaZero dlshogiで生成したデータにAobaZeroの棋譜を混ぜて学習 dlshogiの定跡作成方法に水匠2の定跡を使用
dlshogi dlshogiと同一 以前から使用しているResNetモデル elmo dlshogiで生成したデータ dlshogiの定跡作成方法にfloodgateの統計を使用

大会で使用したハードは、どちらもNVIDIA A100×8です。

dlshogiは6位という結果だったので、モデルの精度の差が大きかったと思います。

モデルのサイズは、どちらもResNet10ブロックで同じです。
やはり一番差がでたのは、事前学習にAobaZeroの棋譜を使用したことだと考えています。
(連続対局での勝率は別途確認するつもりです。)

精度のデータは共有してもらったので、別途まとめるつもりです。

今後の予定など

GCTのモデルとdlshogiを普通のPC(NVIDIAGPU非搭載)でも動くようにしたものを後日公開する予定です。

最後に

大会を開催していただいた運営の皆様、初めての大会の立ち上げで苦労もあったと思いますが、本当にお疲れ様でした。
そして、参加者の皆様、お疲れ様でした。

【電竜戦】dlshogiライブラリ使用の3ソフトが2日目決勝リーグに進出します

本日、コンピュータ将棋のオンライン大会「電竜戦」の1日目が開催されました。

私が開発しているdlshogiは、56チーム中10位で、2日目のA級リーグ(決勝)に進出します。
他にもdlshogiライブラリを使用しているソフトが合計で3チーム決勝リーグ進出します!

第1回世界将棋AI 電竜戦 勝敗表

dlshogi

ディープラーニングMCTSを使用したソフトが、大会で決勝リーグに進出するのは初です。
3位の「二番絞りプレミアム生」と4位の「GCT」もdlshogiライブラリを使用しているソフトです。
(本家なのに10位なのは悔しい・・・
しかし、10位なのでバレルハウス賞を頂きました。ありがとうございます。)

GCT

「GCT」にはチームdlshogiのメンバとしても参加しています。
dlshogiの強化学習で生成したデータを提供しています。
dlshogiで実験中のswishのモデルを使用しているので、本家より強くなっている可能性はあります。

deqshi

qhapaqさんとの合同チームの「deqshi」は、15位で残念ながら決勝リーグには進めませんでした。
こちらは、dlshogiとやねうら王の合議を採用しています。
クラスタ部分のメインの開発はqhapaqさんです。
昨日は夜遅くまでデバッグしていました(;'∀')
明日のB級での上位を目指します。

感想

直前で探索パラメータを変更したことが影響したのか、作成した定跡が序盤でおかしな評価値を付けるようになって終始安心して観れませんでした。
10戦目の「二番絞りプレミアム生」戦で負けたことが、一番悔しかったです。
AobaZeroの棋譜も学習して、大きなモデルサイズを使用しているということで、dlshogiの今後の方針を考え直すべきかと思いました。
逆に言えば、まだまだdlshogiには成長の余地があるということで、いろんな方がdlshogiの開発に参加してくれることを願っています。


ということで、明日2日目もNVIDIA A100インスタンスに課金してがんばります。

公式放送

1日目
www.youtube.com
2日目
youtu.be

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インスタンスを借りて参加するかもしれません。

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のアップグレードで対応することにした。

【勉強ノート】不完全情報ゲームのアルゴリズム 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)の最小化を試したい。