TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

将棋でディープラーニングする その30(探索アルゴリズム)

DeepLearning モンテカルロ木探索 コンピュータ将棋

まだ方策ネットワークもバリューネットワークも精度が低いが、精度を上げるのは一旦保留して、対局時の方法について検討する。

以前に考察したように、将棋は読みが重要なゲームであるため、探索を用いず方策ネットワークのみで指しても強くならないと思われる。

AlphaGoでは、モンテカルロ木探索をベースにして、方策ネットワークとバリューネットワークをうまく組み合わせている。

UCTアルゴリズム

代表的なモンテカルロ木探索のアルゴリズムであるUCTアルゴリズムでは、以下のように探索を行う。
毎回ルートノードからUCBが大きいノード（後手では小さいノード）を選択しながらツリーを下っていく。
末端ノードに到達したら、そこからrollout policyに従い終局までプレイする（これをプレイアウトと言う）。
プレイアウトの結果を、末端ノードからツリーを逆に上りながら、ノードの報酬として記録する（これをバックアップと言う）。
末端ノードは一定回数を訪問したら、合法手でノードを展開する。
最終的にルートの子ノードで最も訪問した手を選択する。
f:id:TadaoYamaoka:20170603234401p:plain:w200

UCBは、以下の式で計算される。
\displaystyle \overline{x_j} + \sqrt{\frac{2\log n}{n_j}}
\overline{x_j}は期待報酬、nは親が同じノードの訪問数の合計、n_jはノードの訪問数

この式は、(期待値)+(バイアス項)という構成になっており、期待報酬が高いところを選択するが、訪問数が少ないノードを優遇するという意味を持つ。

PUCTアルゴリズム

AlphaGoでは、UCTアルゴリズムの代わりに方策ネットワークとバリューネットワークを使ったPUCTアルゴリズム*1を採用している。
PUCTアルゴリズムでのノード選択の基準は、以下の式で計算される。
\displaystyle \begin{equation} Q(s_t,a)+u(s_t,a) \end{equation}

Q(s_t,a)はバリューネットワークの出力とプレイアウトの結果の平均で、期待報酬を表す。
u(s,a)は、以下の式で表される。
\displaystyle u(s,a) = c_{puct} p(s,a) \frac{\sqrt{\sum_b N_r(s,b)}}{1 + N_r(s,a)}
c_{puct}は定数、p(s,a)は方策ネットワークの出力を事前確率として使用する。
N_r(s,a)はノードaの訪問数を表す。
\sum_b N_r(s,b)は親が同じノードの訪問数になる。

PUCTの値の役割は、UCBと同じだが、期待報酬にバリューネットワークの出力を使い、バイアス項に方策ネットワークの出力を使うことで、候補手選択の精度を高めている。

将棋への応用

将棋では囲碁のようにプレイアウトで終局までプレイしてもあまり精度が上がらないことが知られている。
将棋のように狭い読みが必要なゲームでは、プレイアウトで求めた期待報酬が実際の報酬と乖離することが多いためと考えられる。

そのため、PUCTアルゴリズムを将棋に適用する場合は、プレイアウトを使わずに、バリューネットワークの出力のみを期待報酬として用いた方が有効と考えられる。
ノードは1回訪問したら展開し、選択したノードのバリューネットワークの出力を上位のノードにバックアップする。

AlphaGoでは、方策ネットワークとバリューネットワークの計算中に、並列でプレイアウトを行うことで、効率を上げている。
プレイアウトを行わない場合は、各ノードで方策ネットワークとバリューネットワークの計算を待つ必要がある。

モンテカルロ木探索は、ルートノードから並列化を行うことで効果がある知られているため、GPUの処理限界まで並列化を行い効率を上げることが有効と思われる。

並列化を行っても、従来の評価関数ベースの探索に比べたら探索ノードはかなり少なくなると思われる。
そのため、方策ネットワークとバリューネットワークのモデルの精度が高くないと強いプログラムはできない。

モデルの精度向上は別課題として、次回からPUCTアルゴリズムの実装を試したい。

*1:http://gauss.ececs.uc.edu/Workshops/isaim2010/papers/rosin.pdf

将棋でディープラーニングする その29(強化学習【修正版】)

DeepLearning コンピュータ将棋

以前にRL policy networkを学習する際の報酬に応じた勾配の実装方法について記述したが、計算方法に誤りがあった。

softmax_cross_entroyを修正して、backwardの際の勾配に重みを掛けていたが、lossを計算する際に重みが掛けられていないため、間違ったlossを使用していた。

Twitterでアドバイスを頂いたので、その方法で実装し直した。

softmax_cross_entroyは出力がスカラー値になっているが、オプションにreduce='no'を指定すると、平均される前のバッチの状態でlossが取得できる。

そのlossに対して重みを掛けた後に、平均をとることで、正しいlossが計算できる。

Chainerでは以下のように実装する。

loss = F.mean(F.softmax_cross_entropy(y, t, reduce='no') * z)
loss.backward()

※zはバッチごとの報酬

この実装で計算される損失は、出力と報酬により以下の関係になる。

出力 報酬 損失
正解 正 正の小さい値 〇
正解 負 負の小さい値
誤り 正 正の大きい値
誤り 負 負の大きい値 〇

※出力正解は選択された行動の遷移確率が高い場合で、誤りは遷移確率が低い場合
上記表の〇のデータが増えるように学習される。
つまり、損失の期待値を最小化する。

RL policy networkの学習

勾配計算を修正後、RL policy networkの学習をやり直した。
f:id:TadaoYamaoka:20170603160527p:plain
前回は途中で値が発散して学習できなくなったが、とりあえず1000イテレーション分学習ができた。
500イテレーション置きにパラメータを保存して、保存したパラメータと自己対戦するようにしている。
500イテレーションまではわずかに勝率が上がって、それ以降は勝率が落ちている。
学習が成功しているとは言い難い。
モデルの精度が低いと、対戦相手のミスで勝利することもあり、意味ある勝敗にならないことが原因と思われる。
あるいは、まだ学習方法に誤りがあるかもしれない。

elmo_for_learnの教師データで強化学習

自己対戦の結果の精度が低いと思われるので、elmo_for_learnで生成したデータの勝敗データを使用してRL policy networkの学習を行った。
f:id:TadaoYamaoka:20170603162602p:plain
学習率0.001、ミニバッチサイズ64で試したところ、はじめ順調にlossが低下していたが、途中で値が発散してしまった。

学習率変更

学習率を半分の0.0005にしてみたが、やはり発散する。
f:id:TadaoYamaoka:20170603202241p:plain


強化学習うまくいかないので、一旦保留することにします。

github.com

将棋でディープラーニングする その28(学習の高速化その2)

DeepLearning コンピュータ将棋

学習の高速化のため先日作成したPythonから使えるC++の将棋ライブラリ（cppshogi）に、RL policy networkも対応させました。

以前は将棋ライブラリとしてpython-shogiを使用していましたが、全てcppshogiに置き換えました。
これによって、学習がかなり高速化しています。

RL policy networkの学習

RL policy networkの学習の自己対戦が、以前は16ゲームをミニバッチとした1回のイテレーションに1分半かかっていましたが、4秒で終わるようになりました。
これでRL policy networkの学習をまともに行うことができるようになります。

また、今回は学習時にelmoの評価関数で各局面の評価値を求めて、その値をシグモイド関数で推定勝率に変換して、下記式のv(s_t^i)に使用しています。
\displaystyle \Delta \rho = \frac{\alpha}{n} \sum_{i=1}^n \sum_{t=1}^{T^i} \frac{\partial \log p_\rho (a_t^i \mid s_t^i)}{\partial \rho} (z_t^i - v(s_t^i))
これにより、すでに評価値が高い局面で勝利した場合は報酬が少なくなり、評価値が低い局面から勝利した場合には報酬が多くなるように学習できるようになります。
つまり、勝敗に影響がある手をうまく学習できるようになります。

elmo_for_learnで1億局面を生成し、SL policy networkで学習させたモデルを使って、RL policy networkを学習させたところ、一応学習が進むことを確認しました。
f:id:TadaoYamaoka:20170602225632p:plain

しかし、途中から勝率が1.0になってしまい、必ず勝つ手順を覚えてしまっています。
まだ、モデルの精度がよくないため、大駒を序盤で捨ててしまい、評価値3000以上で勝ちとしているため、すぐに勝ちとなってしまいます。
モデルの精度がある程度高くないと、うまく学習できないようです。

使用したSL policy networkの精度

1億局面を学習したSL policy networkは、40%の一致率になっていますが、まだ序盤で大駒を捨てることが良くあります。
f:id:TadaoYamaoka:20170602225940p:plain
elmo_for_learnのデータは初期局面集から生成しているので、初手からの序盤の精度が落ちている可能性があります。

別のRL policy networkの学習方法

SL policy networkは局面を増やしても精度が上がらなくなっているので、別の方法を試そうと考えています。

elmo_for_learnで生成したデータは、勝敗データと評価値、指し手を含んでいるので、上記式のそれぞれz_t^i、v(s_t^i)、a_t^iとして使用可能です。
したがって、自己対戦を行わなくても、elmo_for_learnのデータで強化学習が可能です。
こちらの方法の方がうまく学習できる見込みがあります。
勝敗データを使うので、SL policy networkの精度を改善できると考えています。


次回は、elmo_for_learnのデータを使った強化学習を試す予定。

cppshogiに対応したコードをGitHubに公開しました。
python-shogiに依存したコードは削除しました。
github.com

将棋でディープラーニングする その27(対局できるようにする)

DeepLearning コンピュータ将棋

以前の対局できるバージョンは、別プロセスのUSIエンジンを補助的に使用して詰みの探索を行っていたが、Pythonから呼び出せるC++のモジュールに変更した。

elmo_for_learnのソースを流用してPythonから使用できるようにした。
cppshogiというモジュールにしている。

対局中の各局面で深さ6で評価値を求めて3000を超えた場合は、探索の結果で指すようにした。

今回は、policy networkの出力からBoltzmann分布に従う確率に応じて手を選択するようにした。
これにより指し手が固定化されなくなる。
Boltzmann分布の計算は、policy networkの出力を合法手でフィルターして、残ったロジットについて、expf(logits[i] * beta)を計算した。
本来は分布の合計が1になるように正規化するが、C++のdiscrete_distributionを使うと合計が1になっていなくても、確率分布に応じたインデックスを返却できるため、計算を簡略化した。

elmo_for_learnで生成した2千万局面で学習したSL policy networkを使って、Lesserkaiと対局させて勝つことがあるのを確認した。（勝率は低い）
f:id:TadaoYamaoka:20170529220205p:plain

elmoの教師データを使うと、floodgateの棋譜に比べて学習の進みが遅い。
f:id:TadaoYamaoka:20170529220646p:plain

まだ学習が進んでいるので、教師データを1千万ずつ生成して学習させてみる予定。

RL policy networkはまだcppshogiに対応できていないので、後日修正予定。

github.com

将棋でディープラーニングする その26(学習の高速化)

DeepLearning コンピュータ将棋

前回の日記で書いたC++でミニバッチデータを作成する処理を組み込んで、バリューネットワークの学習の速度が改善されたか確認を行った。

測定条件

  • 学習データはelmo_for_learnで生成した100万局面
  • ミニバッチサイズ32
  • 1エポック

測定結果

Python(変更前) 0:30:08
C++(変更後) 0:11:05

学習時間が37%に短縮できた。

elmoと同じ50億局面を学習するには、38.5日かかる見積もりとなる。(前回は105日の見積もり)

SL policy networkで測定

今までSL policy networkは、CSA形式の棋譜データを使用していたが、elmoで生成した教師データで学習するように変更した。
こちらもC++化による効果を確認した。

50000イテレーションの時間を比較した。(使用する学習データは異なる)

Python(変更前) 0:24:50
C++(変更後) 0:16:32

学習時間が67%に短縮された。
SL policy networkでは棋譜データからミニバッチデータを作成していたのでバリューネットワークのようにハフマン符号のデコードがなかったため、改善効果は比較的少なめである。
それでも十分速くなっている。

精度の評価

精度については以下のようになった。

train loss test accuracy
Python(変更前) 2.49 0.36
C++(変更後) 2.76 0.31

elmoの学習データを使用する精度が落ちているように見える。
これは、棋譜には序盤に重複データが多く含まれているが、elmoの学習データは異なる局面から生成しているので重複が少ないためと思われる。

1000万局面を学習

elmo_for_learnで生成した1000万局面を学習させてみた。
f:id:TadaoYamaoka:20170528233243p:plain

train loss 2.27
test accuracy 0.36
時間 1:41:08

train lossは下がり続けており、学習局面を増やせばまだ精度が上げられそうだ。

elmoと同じ50億局面を学習するには、35.1日かかる見積もりとなる。


今まで詰みの判定に外部のUSIエンジンを使用していたが、C++のライブラリを使用するようにしたので、詰みの判定処理もC++のライブラリで行うようにしたい。
今回は学習用途だったため探索の処理をコメントアウトしたが、詰みの探索ができるようにして、USIエンジンに頼らず対局できるようにする予定。

github.com

将棋でディープラーニングする その25(C++でミニバッチ作成)

DeepLearning コンピュータ将棋

先日の日記で、elmoの教師データを使用してバリューネットワークの学習を行ったところ、elmoの教師データはハフマン符号で圧縮されているため、デコードする処理に時間がかかるという問題があることがわかった。

そこで、デコード部分をC++で実装することで高速化できないか試した。
PythonからC++のモジュールを呼び出すとオーバーヘッドがあるため、できるだけまとめて処理できた方が良い。
そのため、1回の呼び出しでミニバッチデータの作成までをまとめて行うようにした。

Python側実装

Python側では、elmoの教師データのデータ構造であるHuffmanCodedPosAndEvalをNumpyの構造体として定義する。

HuffmanCodedPosAndEval = np.dtype([
    ('hcp', np.uint8, 32),
    ('eval', np.int16),
    ('bestMove16', np.uint16),
    ('gameResult', np.uint8),
    ('dummy', np.uint8),
    ])

ファイルから読み込む際は、

hcpevec = np.fromfile(args.file, dtype=HuffmanCodedPosAndEval)

のようにすることで一度で全件読み込める。

C++側の実装

Boost.Pythonを使うことで、Pythonのモジュールが実装できる。
また、Boost.Numpyを使うことで、Python側からnumpyのオブジェクトを受け取ることができる。
（詳細は、先日の日記参照）

入力は、HuffmanCodedPosAndEval型のnumpyの配列を受け取るようにする。
出力は、引数で受け取ったnumpyのオブジェクトに設定して返すようにする。
出力のnumpyのオブジェクトは、Python側でnp.emptyで事前に領域を確保しておく。

C++側では、ndarray.get_data()でメモリ領域にポインタでアクセスできる。
numpyのオブジェクトは、shapeによらずメモリ上では連続した領域になっているので、C++側ではshapeに合わせてポインタ操作を行う。

elmoの教師データのデコードは、elmoのソースコード(および派生元のApery)をそのまま流用した。
王手を入力特徴に加えているので、王手のチェックを高速で行えるように盤面管理にelmoのPositionクラスを利用した。
探索部分は不要なためコメントアウトしている。

座標系が今まで使用していたpython-shogiとは異なるが、今後はelmoのソースを流用していこうと思うので、座標系の変換は行わずそのままとした。
そのため、いままで学習したモデルは使用できなくなる。

座標系の違いについては以前の日記を参照。
駒の順番もelmoに合わせた。
python-shogiは、歩(PAWN)、香(LANCE)、桂(KNIGHT)、銀(SILVER)、金(GOLD)、角(BISHOP)、飛(ROOK)、玉(KING)の順だが、
elmo(Apery)では、歩(PAWN)、香(LANCE)、桂(KNIGHT)、銀(SILVER)、角(BISHOP)、飛(ROOK)、金(GOLD)、玉(KING)の順になる。

Python側から利用

C++で作成したソースは、DLLとしてビルドする。
拡張子を、.pydにすることで、Pythonからimportして、Pythonのモジュールと同等に使用できる。

import hcp_decoder

hcpevec = np.fromfile(args.file, dtype=HuffmanCodedPosAndEval)

features1 = np.empty((len(hcpevec), 2, 14, 81), dtype=np.float32)
features2 = np.empty((len(hcpevec), 2 * MAX_PIECES_IN_HAND_SUM + 1, 81), dtype=np.float32)

result = np.empty(len(hcpevec), dtype=np.float32)
move = np.empty(len(hcpevec), dtype=np.int32)
value = np.empty(len(hcpevec), dtype=np.float32)

hcp_decoder.decode_with_value(hcpevec, features1, features2, value, move, result)

デバッグについて

C++を使うとデバッグが難しくなるが、Visual StudioのPython Tools for Visual Studioを使い、デバッグの設定で、Enable native code debuggingをチェックしていると、PythonのコードとC++のコードをシームレスにデバッグできる。

処理時間測定

elmoで生成した教師データ1万局面を使い、Pythonでデコードした場合と、C++でデコードしてミニバッチデータの作成まで行った場合で処理時間の比較を行った。
結果は以下の通りとなった。

Python 7.186秒
C++ 0.111秒

約64.7倍速くなった。
Pythonではデコードのみでミニバッチデータの作成までは行っていないので、実際はこれ以上に差がある。

C++にすることで圧倒的に速くなることが確認できたので、python-shogiからelmoから流用したソースに置き換える予定。


C++側の教師データの読み込み処理のソースをGitHubに公開しました。
github.com

なお、C++側のソースのライセンスはelmoのソースを流用しているのでGPLが適用されるようになります。

将棋でディープラーニングする その24(歩の持ち駒の上限)

DeepLearning コンピュータ将棋

前回の日記でバリューネットワークの学習時間を見積もったところ、elmoと同じ50億局面を学習するには3.5ヶ月かかる見積もりになったので、高速化を行う必要性を感じている。

ミニバッチデータの加工をPythonで行っている部分をC++に書き換えることでかなり高速化ができそうである。
それについては別途記事を書く予定。

今回は、入力特徴の歩の持ち駒について見直しを行う。
歩の持ち駒は最大で18枚になるが、実践で歩の持ち駒が18枚になることはまずあり得ない。
竜王戦の棋譜3744局から、歩の持ち駒の数について調べた。
f:id:TadaoYamaoka:20170527204036p:plain:w400
1局中の歩の持ち駒の最大枚数は、ほぼ10枚以内に収まっている。

また、1枚持っているのと、2枚持っているのでは、指し手が変わると思われるが、9枚と10枚ではほとんど影響ないと思われる。

そこで、入力特徴の歩の持ち駒に上限を設けた場合に、精度と学習時間にどのような影響があるか調べた。

はじめ竜王戦の棋譜で調べたが局数が少なすぎるのかほとんど差がみられなかった。

f:id:TadaoYamaoka:20170527204844p:plain
8枚が上限のときが若干test accuracyが良いが、誤差の範囲。
また、歩以外の持ち駒全てなしにしてもほとんど変わらなかった。
確かに盤面にない駒は持ち駒になっているので、盤面の情報に持ち駒の情報も内包しているが、学習データの少なさによるものと思われる。

floodgateの棋譜で再測定

そこで、floodgateの棋譜14,230局を使って、測定をやり直した。
f:id:TadaoYamaoka:20170527205523p:plain
歩以外の持ち駒もなしにすると、精度が落ちることが観測できた。
しかし、歩の持ち駒の枚数による違いはほとんどない。

学習時間は以下のようになった。
f:id:TadaoYamaoka:20170527205904p:plain
持ち駒の上限が増えるほど、学習時間も増える傾向がある。
歩の持ち駒の上限が2と18では、約2分の違いがある。

以上の測定結果から、歩の持ち駒の上限は制限しても精度にはあまり影響がないことがわかった。

上限を何枚にするか決め手にかけるが、18枚は無駄があるので、上限はとりえあず8枚とする。