TadaoYamaokaの日記

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

PythonでAlphaZero Shogiを実装する その2

前回の日記の時点で、自己対局と学習を実装したが、学習したモデルを使って対局できるUSIエンジンを実装した。
dlshogi-zero/mcts_player.py at master · TadaoYamaoka/dlshogi-zero · GitHub


将棋ライブラリにcshogiを使用して、探索方法をdlshogiと同じ方式で並列化を行った。

書籍のために実装したpython-dlshogiは、python-shogiを使用して、スレッドで並列化をして実装していたが、スレッドを増やしてもnpsが120程度にしかならなかった。
モデルはResNet5ブロックだった。

今回は、入力特徴に履歴8局面を使用しており、ニューラルネットワークの規模も10ブロックと大きくなっている。

探索速度測定

1000プレイアウトを行った際の探索速度を測定した。並列探索数は192とした。GPUは1080Ti1枚。

python-dlshogi 119
dlshogi-zero 811

※dlshogi-zeroが今回の実装の測定結果
※1回目はキャッシュに載っていないため、1回目とは異なる局面での2回目の探索で測定

Pythonでシングルスレッドで処理しているにもかかわらずdlshogi-zeroが6.8高速になっている。
C++で実装したdlshogiはnpsが4500程度で、それと比較すると遅いが、Pythonでもそこそこの速度で探索できるようになったと思う。
コードはpython-dlshogiにできるだけ合わせているので、書籍のコードを高速化したい場合にも参考にできると思う。

シングルスレッドで実装したが、GPUで計算中はGILの影響を受けないので、2スレッドにすると2倍くらいにできると思われる。
ただし、マルチスレッドにするとデバッグが難しくなるので、技術書典に向けては実装しない予定。

PythonでAlphaZero Shogiを実装する

次の技術書典のネタとしてPythonでAlphaZero Shogiの完全コピーを実装しています。

github.com

自己対局と学習がようやく動くようになりました。

入力特徴と出力ラベルと探索の仕様はAlphaZero Shogiと完全に一致させました。

入力特徴
  • 先手の駒 14
  • 後手の駒 14
  • 繰り返し数 3
  • 先手の持ち駒の数 7
  • 後手の持ち駒の数 7
  • 手番 1
  • 手数1
  • 履歴8局面
出力ラベル
  • 移動方向×移動距離 64
  • 桂馬の動き 2
  • 移動方向×移動距離(成り) 64
  • 桂馬の動き(成り) 2
  • 駒打ち 7

高速化

Pythonで作成する目的は、本にする上で強化学習の仕組みを理解できるように実装するためです。
それでも、そこそこの速度で動かないと少し試すにも時間がかかりすぎるので、分かりやすさを損なわない程度に、できる限り高速化も行っています。

cshogi

Pythonで速度を出すために将棋ライブラリとして先日日記に書いたcshogiを使っています。
python-shogiと比べて、ビットボードの演算をC++で行っているので、指し手生成が高速になっています。

ハッシュ

ゾブリストハッシュの実装もcshogi側で実装しました。

推論のバッチ処理

dlshogiで行っているのと似た方法で、複数エージェントを同時に対局させて、GPUによる推論をバッチ処理しています。
Pythonはスレッドによる並列化はGILがあるためほとんど効果がありませんが、この方法で疑似的に並列化することでPythonでもそこそこ並列化の効果がでます。

教師あり学習対応

CSAフォーマットの棋譜を使って教師あり学習もできるので、強化学習しない場合でもそこそこ強い将棋AIが作れるようになっています。


ということで、技術書典に向けて執筆始めます(まだ1ページも書いていない・・・)

将棋AIの進捗 その27(やねうら王に初勝利)

前回記事にした自己対局の終了判定にdf-pnによる詰み探索を加えて、学習を進めた結果、valueの精度が1%近く向上しました(floodgateのR3500以上の棋譜との一致率)。

f:id:TadaoYamaoka:20190302104402p:plain
横軸の80サイクルから詰み探索を加えています。

どれくらいの棋力になったか、やねうら王 2017 Early KPPT 4.55(標準設定)と対局させてみました(GPUは1080Ti1枚、CPUはCorei7 6700K、1手3秒)。
まだ対局数は多くなく、勝率は非常に低いですが、数回は勝つことができるようになりました。
今までは一度も勝てなかったので、一つのマイルストーンを達成できた気がします。
f:id:TadaoYamaoka:20190302103044p:plain
※連続対局後に棋譜をロードしているので下側に直前の対局時の情報が残っています。

まだ、上位ソフトにはまったく届いていないですが、世界コンピュータ選手権に向けては、モンテカルロ木探索を活かした定跡作成方法と、Ponderの方法を思いついているので、大会までに実装と実験を行っていく予定です。

AlphaZero方式における入力の正規化

前回AlphaZero方式で訓練データを作成する際のデータの格納方式をSQLiteに決めたので、テストのためにfloodgateの棋譜から訓練データの作成して、学習を行ってみた。

floodgateの棋譜から訓練データ作成

cshogiを使って2018年分のfloodgateのCSAファイルから訓練データを作成した。
AlphaZeroの論文の通り履歴局面は8手まで含めた。
棋譜には指し手の確率分布はないため、唯一の指し手の確率を1として生成した。
局面の繰り返し数は1までとした(速度の都合による。AlphaZeroでは4まで)。

検証データとして2019年分の棋譜から同様にデータを作成した。

訓練

AlphaZeroのモデルをスケールダウンしたResNet10ブロック、192フィルタのモデルで訓練を行った。

入力特徴量

入力特徴量は、局面の繰り返し数が1までである点以外はAlphaZeroと同じとした。

  • P1 piece 14
  • P2 piece 14
  • Repetitions 1
  • P1 prisoner count 7
  • P2 prisoner count 7
  • Colour 1
  • Total move count 1
正解データ

policyの出力は確率分布を正解として与える。floodgateの棋譜から作成したデータでは指し手の確率が1で、他が0の分布になる。
Kerasでは、categorical_crossentropyは確率分布を入力にできる。

valueは負けが-1、引き分け0、勝ちを1として正解を与える。

訓練結果

バッチサイズ256で1000ステップ学習した結果、以下のようになった。

100/100 [==============================] - 8s 82ms/step - loss: 11.4482 - policy_loss: 9.5888 - value_loss: 0.9822 - policy_categorical_accuracy: 0.0102 - value_binary_accuracy: 0.4967
1000/1000 [==============================] - 137s 137ms/step - loss: 8.9705 - policy_loss: 7.0944 - value_loss: 0.9828 - policy_categorical_accuracy: 0.0141 - value_binary_accuracy: 0.5013 - val_loss: 11.4482 - val_policy_loss: 9.5888 - val_value_loss: 0.9822 - val_policy_categorical_accuracy: 0.0102 - val_value_binary_accuracy: 0.4967

※上段が検証データの結果、下段が訓練データの結果

policyの正解率が1%、valueが49.6%となり、ほとんど学習できていない。

データの作成やネットワーク定義などに誤りがないか確認したが特に間違っていない。
そこで、入力特徴の局面の手数(Total move count)を整数のまま入力していたので、上限が1になるように正規化を行ってみた。
一般的に機械学習では、入力のスケールをそろえて正規化を行うことが重要である。

AlphaZeroの論文には特に記載されていなかったが、論文を読んだとき整数のまま入力していないのではないかと考察したことがある。

正規化

手数(Total move count)は、floodgateの棋譜では256が上限のため、256で割ることにした。
持ち駒の数も歩以外は4枚までなので4で割った。2枚しかない駒は2で割って、歩は8とかで割った方よいかもしれないが、一旦4とした。

正規化後の訓練結果
100/100 [==============================] - 8s 83ms/step - loss: 5.2102 - policy_loss: 3.5036 - value_loss: 0.8290 - policy_categorical_accuracy: 0.2384 - value_binary_accuracy: 0.6488
1000/1000 [==============================] - 137s 137ms/step - loss: 6.2560 - policy_loss: 4.4754 - value_loss: 0.8948 - policy_categorical_accuracy: 0.1724 - value_binary_accuracy: 0.5981 - val_loss: 5.2102 - val_policy_loss: 3.5036 - val_value_loss: 0.8290 - val_policy_categorical_accuracy: 0.2384 - val_value_binary_accuracy: 0.6488

policyの正解率が23.8%、vlaueの正解率が64.8%に改善した。
うまく学習できなかったのは、正規化されていないことがが原因だった。

正規化のために割る数は、floodgateの手数は256が上限だが、自己対局ではAlphaZeroでは512が上限となっているので、調整が必要と思われる。
tanhで、上限を1にしても良さそうである。
tanh(x/100)は以下のようなグラフになる。
f:id:TadaoYamaoka:20190227001923p:plain

試しにtanhでも学習してみた。

100/100 [==============================] - 8s 82ms/step - loss: 5.3477 - policy_loss: 3.5811 - value_loss: 0.8875 - policy_categorical_accuracy: 0.2261 - value_binary_accuracy: 0.6177
1000/1000 [==============================] - 137s 137ms/step - loss: 6.3605 - policy_loss: 4.5126 - value_loss: 0.9604 - policy_categorical_accuracy: 0.1700 - value_binary_accuracy: 0.5321 - val_loss: 5.3477 - val_policy_loss: 3.5811 - val_value_loss: 0.8875 - val_policy_categorical_accuracy: 0.2261 - val_value_binary_accuracy: 0.6177

policyの正解率が22.6%、vlaueの正解率が61.7%となった。
256で割った方が良いが、自己対局の場合は手数が増えるためtanhの方がよいかもしれない。

LeelaChessZeroではどうしているかソースを調べてみたが、手数の入力は未実装だった。
時間があるときにELF Open GoとかLeelaZeroも調べてみたい。

余談

SQLiteのデータをハードディスクに保存すると、作成後再起動するまではキャッシュに乗っているためランダムアクセスしても早かったが、一度PCを再起動すると悲惨なほどランダムアクセスが遅くなった。
保存先をSSDに変えると解決した。アクセス速度が10倍ほど改善した。
SQLiteでランダムアクセスする場合はSSDが必須と言える。

SQLiteによる教師データの管理

先日AlphaZero方式で教師データを生成する際に、データを固定サイズにすることを検討した。
しかし、指し手の確率分布を保存するには、合法手500手近くの領域が必要となるため、1回の訓練ステップ全てのデータをメモリに載せるのは厳しいことがわかった。
AlphaZeroでは、過去ゲーム数100万からランダムサンプリングするので、1ゲーム平均80手とすると、訪問数を2byteで確保すると、500手×80手×100万×2byte=80GBが必要になる。

現在実験しているdlshogiでは、教師データは単一の指し手のみ保存しているため、一度に500万局面を学習しても必要メモリは2GBに収まる。

そこで、すべてメモリに読み込む方式はあきらめ、ファイルからランダムアクセスを行うようにする。
ゲームごとに局面数が異なるため、ゲーム数をウィンドウサイズとした場合、ゲームごとの局面数を管理しておく必要がある。
局面のデータとゲームごとの局面数の管理を自前で行うのも面倒なので、データベースを使用することにした。
データベースにサーバが必要になると煩雑になるのでPythonで標準で使えるSQLiteで実装することにした。
将来的にスケールアウトしたい場合もSQLiteから他のRDBMSに移行するのは難しくない。

ランダムサンプリング

SQLiteで、ゲーム数をウィンドウサイズとしてランダムサンプリングするには、単純なSQLでは、ORDER BY RANDOM() LIMIT Nで行えるが、これはデータ数が多い場合に非常に遅くなる。

WITH RECURSIVEを使う

SQLiteは、WITH RECURSIVE構文で仮想なテーブルを再帰的に定義できる。
SQLite Query Language: WITH clause
これを使うと、関数型プログラミングのようなことができる。

ランダムで100個の数値を得るには以下のように行う。

WITH RECURSIVE
    rand_id(id) AS (
        SELECT RANDOM()
        UNION ALL SELECT RANDOM() FROM rand_id
        LIMIT 100)
SELECT ABS(id) FROM rand_id

これを使うと、ウィンドウサイズを指定したランダムサンプリングが実現できる。

WITH RECURSIVE
    rand_id(id) AS (
        SELECT RANDOM()
        UNION ALL SELECT RANDOM() FROM rand_id
        LIMIT {n_samples})
SELECT hcps, repetition, total_move_count, legal_moves, visits, game_result FROM training_data AS A
    JOIN (
        SELECT ABS(id) % ((SELECT MAX(rowid) FROM training_data) - (SELECT MIN(rowid) FROM training_data WHERE game_id >= {min_game_id})) + (SELECT MIN(rowid) FROM training_data WHERE game_id >= {min_game_id}) AS B
        FROM rand_id)
    ON A.rowid = B

ただし、rowidが連続していることを前提としている。重複も許容している。
重複を排除したい場合はDISTINCTをうまく使えばできる。

SQLiteを使う場合は、固定サイズにこだわる必要はないため、合法手の分だけ保存すればよいのでディスクサイズの節約にもなる。

レイヤー融合を将棋AIの推論で試してみる

先日試したレイヤー融合をdlshogiのニューラルネットワークで試してみた。

dlshogiはWideResNetを採用しているので、conv->bnのレイヤー融合を適用できるのは、残差ブロックの2つ目の畳み込み層とBatchNormになる。
f:id:TadaoYamaoka:20170511224719p:plain

推論比較

レイヤー融合前後で推論時間を比較してみた。

条件
  • 10ブロック、192フィルタのWideResNet
  • 10万局面の推論時間
  • バッチサイズ128
  • GPUは1080 Ti
  • 5回測定の平均
レイヤー融合前 12.65123224 sec
レイヤー融合後 12.51427692 sec

推論時間はレイヤー融合後で98.9%にしかならなかった。

条件2

FP16での推論時間を比較してみた。

  • GPUは2080 Ti
レイヤー融合前 4.58465764 sec
レイヤー融合後 4.50548268 sec

FP16でも推論時間はレイヤー融合後で98.2%にしかならなかった。

dlshogiのWideResNetにはレイヤー融合は、期待するほどの効果がなかった。


テストをしていてvalueのバイアスが一部漏れていたというバグを見つけてしまった。
期待するほど効果はなかったがバグが見つかったので良しとしよう。

畳み込み層とBatchNormalizationのレイヤー融合をChainerで試してみた

畳み込み層のフィルタは行列で表すことができる。
BatchNormalizationも、入力の要素ごとに適用するスカラーの式だが、カーネルサイズ1×1の畳み込みで表すことができる。

推論のフェーズでは、BatchNormalizationの平均と分散は、学習時の統計情報を使うことで、固定の行列とすることができる。
つまり、推論では畳み込み層のフィルタと行列の合成(レイヤー融合)が可能である。

Chainerではレイヤー融合の機能は提供されていないため、自力で実装する必要がある。
Chainerで実装したサンプルを探したが見つからなかったので、こちらのPyTorchのサンプルを参考に実装してみた。

実装

モデルの定義

以下の通り、畳み込み層とBatchNormalizationの後に全結合層を行う、レイヤー融合の対象とするモデルを定義する。

class MyNet(Chain):

    def __init__(self, filters=64, units=64, n_out=10):
        super(MyNet, self).__init__()
        with self.init_scope():
            self.conv1 = L.Convolution2D(in_channels=3, out_channels=filters, ksize=3, stride=1)
            self.bn2 = L.BatchNormalization(filters)
            self.l3 = L.Linear(None, units)
            self.l4 = L.Linear(None, n_out)

    def forward(self, x):
        h1 = F.relu(self.bn2(self.conv1(x)))
        h2 = F.relu(self.l3(h1))
        return self.l4(h2)
レイヤー融合関数

畳み込み層とBatchNormalizationを融合して1つの畳み込み層とする関数を以下の通り実装する。

def fuse_conv_and_bn(conv, bn):
    # init
    fusedconv = L.Convolution2D(
        conv.W.shape[1],
        conv.out_channels,
        ksize=conv.ksize,
        stride=conv.stride,
        pad=conv.pad
    )

    # prepare filters
    w_conv = conv.W.data.reshape(conv.out_channels, -1)
    w_bn = np.diag(np.divide(bn.gamma.data, np.sqrt(bn.eps + bn.avg_var)))
    np.copyto(fusedconv.W.data, np.matmul(w_bn, w_conv).reshape(fusedconv.W.data.shape))

    # prepare spatial bias
    if conv.b is not None:
        b_conv = conv.b.data
    else:
        b_conv = np.zeros(conv.W.data.shape[0])
    b_bn = bn.beta.data - np.divide(np.multiply(bn.gamma.data, bn.avg_mean), np.sqrt(bn.avg_var + bn.eps))
    np.copyto(fusedconv.b.data, b_conv + b_bn)

    # we're done
    return fusedconv
レイヤー融合したモデル

上記の関数を使用して、レイヤー融合したモデルを定義する。

class MyFusedNet(Chain):

    def __init__(self, model, units=64, n_out=10):
        super(MyFusedNet, self).__init__()
        with self.init_scope():
            self.conv_fused = fuse_conv_and_bn(model.conv1, model.bn2)
            self.l3 = L.Linear(None, units, initialW=model.l3.W.data, initial_bias=model.l3.b.data)
            self.l4 = L.Linear(None, n_out, initialW=model.l4.W.data, initial_bias=model.l4.b.data)

    def forward(self, x):
        h1 = F.relu(self.conv_fused(x))
        h2 = F.relu(self.l3(h1))
        return self.l4(h2)

モデルの学習

CIFAR-10のデータセットを使用して、レイヤー融合前のモデル学習する。

train, test = chainer.datasets.get_cifar10()

batchsize = 128

train_iter = iterators.SerialIterator(train, batchsize, shuffle=False)
test_iter = iterators.SerialIterator(test, batchsize, False, shuffle=False)

gpu_id = 0

model = MyNet()
model.to_gpu(gpu_id)

max_epoch = 1

model = L.Classifier(model)

optimizer = optimizers.MomentumSGD()

optimizer.setup(model)

updater = training.updaters.StandardUpdater(train_iter, optimizer, device=gpu_id)

trainer = training.Trainer(updater, (max_epoch, 'epoch'), out='result')
trainer.extend(extensions.LogReport())
trainer.extend(extensions.Evaluator(test_iter, model, device=gpu_id))
trainer.extend(extensions.PrintReport(['epoch', 'main/loss', 'main/accuracy', 'validation/main/loss', 'validation/main/accuracy', 'elapsed_time']))

trainer.run()

学習済みモデルをレイヤー融合

学習済みモデルをレイヤー融合する。レイヤー融合前にモデルを一旦CPUに転送する必要がある。

model.to_cpu()

model_fused = MyFusedNet(model.predictor)

テスト

レイヤー融合前後のモデルで結果が同じになるかテストする。

x, t = test[0]
with chainer.using_config('train', False):
    y = model.predictor(x[None, ...])
    print(y)

with chainer.using_config('train', False):
    y = model_fused(x[None, ...])
    print(y)
結果
variable([[-0.4691602   0.63228214  0.3182091   2.3503518  -0.8040181
            1.8878069   2.7495365  -2.3511798   1.8371497  -0.57447565]])
variable([[-0.46915972  0.63228184  0.3182095   2.3503518  -0.8040179
            1.8878068   2.7495365  -2.3511798   1.8371491  -0.574476  ]])

非常に小さな誤差があるが、ほぼ同じ結果になった。

推論時間の比較

レイヤー融合前後で推論時間の比較を行った。

model.to_gpu(gpu_id)
model_fused.to_gpu(gpu_id)

train_iter.reset()
itr = 0
sum_train_accuracy = 0
start = time.time()
for i in range(0, len(train), batchsize):
    train_batch = train_iter.next()
    x_train, t_train = chainer.dataset.concat_examples(train_batch, gpu_id)
    with chainer.using_config('train', False):
        y_train = model.predictor(x_train)
    sum_train_accuracy += F.accuracy(y_train, t_train).data
    itr += 1
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")
print(itr, sum_train_accuracy / itr)

train_iter.reset()
itr = 0
sum_train_accuracy = 0
start = time.time()
for i in range(0, len(train), batchsize):
    train_batch = train_iter.next()
    x_train, t_train = chainer.dataset.concat_examples(train_batch, gpu_id)
    with chainer.using_config('train', False):
        y_train = model_fused(x_train)
    sum_train_accuracy += F.accuracy(y_train, t_train).data
    itr += 1
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")
print(itr, sum_train_accuracy / itr)
結果
elapsed_time:1.419318437576294[sec]
391 0.4076087
elapsed_time:1.3278264999389648[sec]
391 0.4076087

レイヤー融合後のモデルでは、推論時間が約93.5%になった。
accuracyは同じであり、精度の低下はない。
畳み込み層1層で試したが、畳み込み層が多い場合はレイヤー融合の効果は相対的に大きくなると思われる。