AlphaZero Chess/Shogiの論文を読む

DeepMindからAlphaGo Zeroと同じ方法で、チェスと将棋でトップレベルを上回ったという論文が発表されました。
[1712.01815] Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm

ドメイン知識を用いないスクラッチから強化学習のみで達成しています。
将棋やチェスはモンテカルロ木探索(MCTS)は向かず、Mini-Max探索の方が良いというのが常識のようになっていましたが、将棋やチェスでもディープラーニングと組み合わせることでMCTSが有効であることが示されたというのも大きな成果だと思います。

まだ全部読み切れていませんが、気になる個所から読んだ内容を書いていきます。

個人的に一番気になるのは、入力特徴と出力ラベルの表現方法です。
チェスについても書かれていますが、将棋のみについて書きます。

入力特徴

• 先手の駒の配置×14種類
• 後手の駒の配置×14種類
• 繰り返し回数(3まで)(千日手用)
• 先手の持ち駒の枚数×7種類
• 後手の持ち駒の枚数×7種類

これを8手の履歴局面分。
これに、先手か後手かの特徴(1面)と合計手数(1面)を加えて合計で(14+14+3+7+7)×8+2=362面。

出力ラベル

• 桂馬以外の駒の位置×方向(8)×距離(8) = 64
• 桂馬の位置×方向(2)
• 桂馬以外の駒が成る場合(64)
• 桂馬が成る場合(2)
• 持ち駒から打つ位置×7種類

合計で、64+2+64+2+7=139面

他の表現方法も考えられるが、これで合理的な手を学習できたとのこと。

考察

入力特徴

私が試している将棋AIでは入力特徴は、

• 先手の駒の配置×14種類
• 後手の駒の配置×14種類
• 先手の持ち駒×7種類×枚数
• 先手の持ち駒×7種類×枚数
• 駒の効き×14種類
• 位置ごとの効き数(1)
• 王手かどうか(1)

としていましたが、これとの比較で言うと、
まず、千日手を判定する情報が加わっています。
AlphaGo Zeroでは、コウを識別するために履歴局面を使っていましたが、入力特徴として与えています。

持ち駒は種類ごとの枚数で、7面となっています。
ニューラルネットワークの入力は0～1で正規化する場合が多いですが、枚数をどのような値で入力しているかは書かれていません。
AlphaGoでは整数はOneHotエンコーディングで複数枚で入力していましたが、整数をそのまま数値で入力して問題ないのでしょうか。
※「the number of captured prisoners of each type」で7面を、枚数なしで種類のみと解釈しましたが、コメントを頂いたので修正しました。

効きや王手の情報は入っていません。

8手の履歴局面を入力していますが、私が以前に実験したところでは履歴は効果ありませんでした。教師ありではなく自己対局による強化学習では必要なのかもしれません。

先手後手の特徴がありますが、将棋の場合は局面の価値は、先手でも後手でも変わらないと思いますが、必要なのでしょうか。あっても影響はないと思いますが。

合計手数が1面のみで表現されていますが、具体的にどのように値を入力するかが書かれていません。例えば256手を0～1の範囲の実数として入力するのでしょうか。
また、手数が同じでも局面の進み具合は異なるので、そのまま手数を入力してしまってよいか疑問です。
技巧などは、局面の進み具体を手番ではなく進行度という尺度で表現しています。

出力ラベル

私が試している将棋AIでは、

• 移動先の座標
• 移動方向(8+2(桂馬の動き))

として表現しています。
それとの比較で言うと、
座標は移動先ではなく、移動元で表現しています。
持ち駒から打つ場合は、移動先なのだから、移動先でそろえた方がよいと思っていますが、あまり違いはないかもしれません。

移動方向に加えて、移動距離も表現しています。
移動距離がなくても移動する駒は一意に特定できるので、必要かどうかは疑問です。
私の実験では、出力ラベルは必要最低限にした方がよいです。
私は以前は、移動する駒にもラベルを割り当てていましたが、ない方が良いことが分かったので、移動方向のみにしました。
AlphaZeroでも移動する駒は表現していません。

AlphaGoZeroの囲碁の入力特徴と出力ラベルの表現をベースにしていることがうかがえます。
必ずしも将棋でベストな表現ではないと思いますが、マシンパワーがあれば、結果は同じということでしょうか。

個人レベルで試すなら、学習効率の良い入力特徴と出力ラベルの表現を模索することも必要だと思います。

続く。。。
AlphaZero Chess/Shogiの論文を読む その2(AlphaGo Zeroとの差分) - TadaoYamaokaの開発日記
AlphaZero Chess/Shogiの論文を読む その3 - TadaoYamaokaの開発日記

将棋でディープラーニングする その50(ブートストラップ【訂正】)

以前に書いたブートストラップの説明に誤りがあったのと、Chainerで誤差逆伝播の効率化ができたので、追加記事を書きます。

間違っていた内容

以前に書いた記事で、2確率変数の交差エントロピーは、確率変数がシグモイド関数の場合、

で表され、偏微分が、

となることを説明したが、偏微分するのは確率変数qの方なので、ニューラルネットワークの出力をqにする必要があります。
それを教師データの評価値を勝率にした値をqに与えていたので、間違った計算をしていました。

使用していた

def cross_entropy(p, q):
    return F.mean(-p * F.log(q) - (1 - p) * F.log(1 - q))

を使って、pの方をニューラルネットワークの出力として、以下のパーセプトロンで学習すると一見lossは下がりますが、間違った値に収束します。

import numpy as np
import cupy as cp
import chainer
from chainer import cuda, Variable
from chainer import optimizers
from chainer import Chain
import chainer.functions as F
import chainer.links as L

class Model(Chain):
    def __init__(self):
        super(Model, self).__init__()
        with self.init_scope():
            self.l1 = L.Linear(2, 5)
            self.l2 = L.Linear(5, 1)

    def __call__(self, x):
        h1 = F.relu(self.l1(x))
        return self.l2(h1)

def cross_entropy(p, q):
    return F.mean(-p * F.log(q) - (1 - p) * F.log1p(-q))

model = Model()
model.to_gpu()

optimizer = optimizers.SGD()
optimizer.setup(model)

x = Variable(cp.array([[0.2, 0.8], [0.6, 0.4]], dtype=np.float32))
t = Variable(cp.array([[0.4], [0.6]], dtype=np.float32))

for i in range(10000):
    y = model(x)
    y2 = F.sigmoid(y)
    loss = cross_entropy(y2, t) # fault
    print('loss = ', loss.data)
    model.cleargrads()
    loss.backward()
    optimizer.update()

print('y = \n', y2.data)
print('loss = \n', loss.data)

学習後の値は

y =  [[ 0.04580102], [ 0.94369036]]

となりました。

pとqを逆にして、

    loss = cross_entropy(t, y2) # correct

とすると、

y =  [[ 0.40164709], [ 0.59817547]]

と、正しい値に収束します。

ということで、今まで間違った学習をしていましたヾ(*｀Д´*)ノ"

誤差逆伝播の効率化

順伝播を計算して、微分はChainerの計算グラフの処理に任せていましたが、微分は上記で書いた

の式で計算できるので、これをChainerのFunctionで実装しました。

import numpy

from chainer import cuda
from chainer import function
from chainer.functions.activation import sigmoid
from chainer import utils
from chainer.utils import type_check

class SigmoidCrossEntropy2(function.Function):

    def __init__(self):
        pass

    def check_type_forward(self, in_types):
        type_check.expect(in_types.size() == 2)

        x_type, t_type = in_types
        type_check.expect(
            x_type.dtype == numpy.float32,
            t_type.dtype == numpy.float32,
            x_type.shape == t_type.shape
        )

    def forward(self, inputs):
        xp = cuda.get_array_module(*inputs)
        x, t = inputs

        loss = t * xp.log1p(xp.exp(-x)) - (1 - t) * (xp.log(xp.exp(-x)) - xp.log1p(xp.exp(-x)))

        count = max(1, len(x))
        self.count = count

        return utils.force_array(
            xp.divide(xp.sum(loss), self.count, dtype=x.dtype)),

    def backward(self, inputs, grad_outputs):
        xp = cuda.get_array_module(*inputs)
        x, t = inputs
        gloss = grad_outputs[0]
        y, = sigmoid.Sigmoid().forward((x,))
        gx = xp.divide(
            gloss * (y - t), self.count,
            dtype=y.dtype)
        return gx, None


def sigmoid_cross_entropy2(x, t):
    return SigmoidCrossEntropy2()(x, t)

ChainerのGitHubリポジトリのソースのSigmoidCrossEntropyを改造して作りました。
cudaの処理を書く必要があると思っていましたが、cupyの関数だけで実装できました。
この関数の入力は、logitsになるので、sigmoidの計算が不要で、

    y = model(x)
    loss = sigmoid_cross_entropy2(y, t)

と記述できます。

この関数に置き換えても、

y = [[ 0.40164712], [ 0.59817553]]

と、正しい値に収束することを確認しました。

将棋AIのバリューネットワークの損失をブートストラップ項のみにして、学習してみたところ、2000万局面の学習で、

	一致率
修正前	0.7061
修正後	0.7537

となって、正しく学習できることを確認しました。
むしろ修正前がそれなりに学習できていたのが不思議です。Policyも同時に学習していた効果かもしれません。バリューのみでは測定していません。

ということで、一から学習をやり直しています。

2017/12/9 追記

ブートストラップ項の修正版で再学習を行いました。
4.9億局面学習したところで、GPSfishと1手3秒50局で、

対局数50 先手勝ち26(54%) 後手勝ち22(45%) 引き分け2
dlshogi
勝ち20(41%) 先手勝ち11(45%) 後手勝ち9(37%)
GPSfish 0.2.1+r2837 gcc 4.8.1 osl wordsize 32 gcc 4.8.1 64bit
勝ち28(58%) 先手勝ち15(62%) 後手勝ち13(54%)

となりました。
バグがあったバージョンよりも同じ学習局面数で、勝率が伸びています。
序盤の事前探索による定跡化なしでこの勝率なので、35億局面学習した電王トーナメント版のdlshogiよりも強くなっていそうです。

Jupyter QtConsoleのTips

ほぼ自分用のメモ。

OSのコマンド実行

先頭に「!」を付ける。
例）

!dir

参考：IPython reference — IPython 8.1.0 documentation

グラフをインラインで表示

%matplotlib inline

参考：IPython reference — IPython 8.1.0 documentation

グラフを別ウィンドウで表示

%matplotlib

グラフをpngや、svgなどフォーマットを選んで保存できる。

随時追記予定

将棋AIの進捗 その9(千日手対応)

dlshogiを千日手に対応させました。

対応方法は以下の通り。

• value networkで評価中に千日手チェックを行い、value networkの評価が終わったら、value networkの値を使わずに千日手チェックの結果を使うようにする。
• 同じ局面でも経路によって千日手チェックの結果は異なるため、ハッシュのvalue networkの評価値を上書きしない。
• 同じ局面を探索したときに、以前に千日手になった局面は、再度千日手チェックを行い、千日手の場合、探索を打ち切る。

経路が異なると千日手チェックの結果が変わることに注意が必要です。
千日手チェックは、AperyのPosition::isDrawが使えたので楽に実装できました。
千日手チェックを自分で実装すると大変なので、ライブラリはありがたいです。

効果

対応前は、GPSfishと50回対局で8回千日手になりましたが、対応後は1回も千日手にはならないようになりました。
ループする無駄な局面を探索しなくなるので、強さも上がるかと思いましたが、勝率が上がることはなかったです。

将棋でディープラーニングする その49(再学習)

ResNetのブロック数を10にして、elmoで生成した深さ8の局面を使って、学習をやり直しています。
スクラッチからの学習も試したいところですが、モデルの性能を評価するには、既存将棋ソフトで生成した棋譜は役に立ちます。

tanhバージョン

はじめ、vlaue networkの出力をtanhにしたモデルで学習していましたが、3.4億局面学習してもGPSfishに1勝もできないので以前より弱くなりました。
policyの一致率は45.2%、valueの一致率は77.8%と一致率の数値は、以前のモデルの3.4億局面学習時がpolicyが42.9%、valueが77.6%であったのに比べて高い数値になっています。
一致率は高いのに弱くなった理由について調べたところ、polciyの予測する指し手が以前に比べて絞られすぎており、数手の予測手以外の手をMCTSで探索しないようになっていました。
学習データにフィットしすぎていて、policyが尖った状態になっていました。
policyの損失関数は同じなのに、valueの出力がsigmoidからtanhに変わって損失が交差エントロピーからMSEに変わったことで、policyにも影響が出たようです。
policyとvalueの損失の割合を変えるなどで解決できるかもしれませんが、tanhを使うのはやめることにしました。

sigmoidバージョン

続いて、以前と同様にvalue networkの出力にsigmoidを使って、ResNetのブロック数を5から10にしたモデルで学習をやり直しました。
4億局面学習した時点で、GPSfishに1手3秒で、50回対局で38%勝つようになりました。

Eloレーティングでは、GPSfishのレーティングを2800とすると、

となり、以前のdlshogiと同等の強さになっています。
以前のdlshogiは、35.8億局面を3エポック学習していたのに対して学習効率が大幅に向上しています。

ResNetのブロック数を増やしたことで、過学習するのではないかという懸念がありましたが、そのようなことはないようです。
[1710.03667] High-dimensional dynamics of generalization error in neural networksによると、DNNの場合、大規模にしても学習データが十分にあると汎化性能を失わないそうです。

以前のdlshogiのモデルはバグがあったので、ResNetのブロック数だけの効果が測れていないので別途検証をする予定です。

世界コンピュータ将棋選手権 ライブラリ登録

dlshogiをライブラリ登録しました。
コンピュータ将棋選手権使用可能ライブラリ

ディープラーニングを使って将棋AIを開発したい方のお役に立てば幸いです。

第5回電王トーナメントバージョンは、いろいろとバグがあったので、↓このコミットがバグを修正したソースになります。
github.com
ただし、モデルファイルの互換性はなくなっています。
公開した学習済みモデルを実行するには、第5回電王トーナメントバージョンが必要です。

将棋でディープラーニングする その48(ResNet)

これまでニューラルネットワークの構成に、5ブロックのResNetを使ってきたが、層を増やすると精度がどれくらい上がるか実験を行ってみた。

これまでは、ResNetの構成は、こちらの論文（[1603.05027] Identity Mappings in Deep Residual Networks）で精度が高いとされている「full pre-activation」の構成に、こちらの論文（[1605.07146] Wide Residual Networks）で提案されている畳み込み層の間にdropoutを加えた構成を使用していた。

一方、AlphaGo Zeroでは通常のResNetの構成を使用している。

そこで、通常のResNet構成で層を増やした場合とWideResNetで層を増やした場合でも比較を行った。
また、フィルター数も変更して比較した。

比較したパターンは以下の通り。

	ResNet構成	ブロック数	フィルター枚数
パターン1	WideResNet	5	192
パターン2	通常	5	192
パターン3	通常	10	192
パターン4	通常	10	128
パターン5	通常	10	64
パターン6	WideResNet	10	192

測定結果

測定条件

• 訓練データ：1億局面
• テストデータ：100万局面
• 学習率：0.01
• 最適化：MomentumSGD
• ミニバッチサイズ：64
• 訓練局面elmoの自己対局で生成
• policyとvalueのマルチタスク学習
• 1000万局面ごとに評価

policyのtest accuracy

valueのtest accuracy

学習時間

※1000万局面あたり
※パターン1とパターン6は1080Ti、残りは1080で学習したのでそのまま比較はできないが参考として記載

考察

policyのtest accuracy

10ブロック、192フィルターのResNet、WideRestがtest accuracyが高い値になっている。
層数を増やすと精度が上がることが確かめられた。

同じ10ブロックでも、フィルター枚数を64にすると、5ブロック192フィルターより精度が落ちている。
10ブロック、128フィルターで、5ブロック192フィルターと同じくらいになっている。
層数とフィルター枚数はともに重要であり、バランスをとる必要がありそうである。

valueのtest accuracy

傾向は、policyとほぼ同じとなった。

学習時間

ResNetのブロックを倍にすると学習時間は、1.76倍になった。
層を増やすと実行時のNPSにも影響するので、精度と学習時間、対局時の速度でバランスをとる必要がある。
どれがベストか探るには実験時間がかかりすぎる。
前回35億局面学習したときよりは精度を上げたいので、今後はとりあえず10ブロックで実験していこうと思う。