AlphaZeroの価値関数の目標をQ値にすると改善する

この記事で、AlphaZeroの再実装を試した際に、価値関数の学習目標をゲームの結果からQ値に変更することで、エラー率が低下するという報告がされています。
medium.com

ゲームの結果とQ値の平均を目標とするとさらにエラー率が低下し、ゲームの結果からQ値に段階的に変更することでさらにエラー率が低下しています。

Q値について

Q値には、シミュレーションをおこなった後の、ルートノードにバックアップされた価値の平均が使用されています。

redditの記事

[D] Improvement to the AlphaZero Value Target : MachineLearning

考察

ゲームの結果だけでなく、探索の評価値から予測した勝敗を学習目標とする考え方は、コンピュータ将棋の学習でもelmoが導入して以来、普及しています。
実際の結果の推定値を使用して学習する方法は、ブートストラップ法とも呼ばれています。

私が開発しているdlshogiの強化学習でも、価値関数の学習に、ゲームの結果とシミュレーション後のルートノードのQ値の平均を使用しています。
ただし、Q値は、最善応手にバックアップされた価値の平均としています。
第 28 回世界コンピュータ将棋選手権dlshogiアピール文章

私も以前に、価値関数の学習にブートストラップ法が効果があることを確認していましたが、実験数が少なく客観的な検証はできていませんでした。
上記の記事の実験では、AlphaZero方式の学習でもブートストラップ法が有効であることが実験で示されています。

dlshogiでは、AlphaZeroの学習はGoogleのマシンパワーがないと不可能と思われていますが、学習の工夫で個人レベルでもなんとかなることを示せたら良いと思っています（できるかどうかはわかりませんが・・・・）。

【Androidアプリ】電卓アプリをアップデート

ほぼ自分用のアプリですが、電卓アプリをアップデートしました。
play.google.com

累乗と階乗の演算子の優先順位が除算と同じになっていたというバグの修正です。
JavaCCで文法を定義していましたが、編集ミスで階乗と除算が逆になっていました。

電卓アプリはごまんとありますが、式を編集してボタンに割り当てできる機能があります。
料理で、塩の量は食材の0.8%がベストらしいので、「×0.8%」を割り当てて使ったりできます。
広告なしの無料アプリです。

将棋AIの進捗 その24(自己対局による強化学習)

これまではAperyの初期局面集にfloodgateの棋譜を加えたものを初期局面集として自己対局を行っていたが、中終盤のバリエーションを増やすため、

• やねうら王教師局面からAperyの初期局面集を作成(評価値200以内局面を抽出)
• 初期局面集から詰みの局面を除く

という方法で、初期局面集を作成した。
出来上がった初期局面集は、重複なしで394,003,767局面になった。
これだけあれば、自己対局で局面が重複することはないため、自己対局の効率を上げることができる。

自己対局による重複局面数の比較

初期局面集を変更する前後で、自己対局の結果生成された局面の重複率は以下の通りであった。

条件

• 自己対局で500万局面生成したときの重複率
• 初期局面集からランダムに局面を選択し、1手ランダムで指した局面を初期局面として自己対局

	重複率
変更前	0.1869%
変更後	0.0767%

変更後の初期局面集を使うことで、重複率が変更前の41%に減っている。

自己対局による強化学習の進捗

elmoで深さ8で生成した教師局面4.9億局面で事前学習したモデルから、自己対局で1イテレーション500万局面生成を19イテレーション繰り返して学習したモデルで、教師ありで収束するまで学習したモデル(11億局面)とだいたい同じ強さになった。

事前学習したモデルでは、教師ありで収束するまで学習したモデルとの1手3秒の対局で、2勝8敗(勝率20%)でだったが、19イテレーション強化学習したモデルでは、5勝5敗(勝率50%)とほぼ同じ強さになった。
GPSFishとの対局でも、5勝5敗(勝率50%)となっている。

対局数が少なく検証が不十分だが、自己対局による強化学習で教師あり学習より強くできることがある程度確認できた。
しばらくこの方法で強化学習を続ける予定である。

モデルの検証

いままではelmoで深さ8で生成した教師局面を学習局面とテスト局面に分けて、モデルの検証を行っていたが、自己対局による強化学習を行うとelmoで生成した局面に対して、policyの一致率もvalueの一致率も低下する傾向にあった。
これでは学習が進んでいることがわかりにくいため、テスト局面を2017年以降のfloodateのレート3500以上の棋譜から作成するようにした。
以下のツールで、CSA形式のファイルから評価値と対局ソフトのレートを条件を指定してhcpe形式で局面を抽出した。
ElmoTeacherDecoder/csa_to_hcpe.py at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub
重複局面を除いて856,923局面が抽出できた。

このテスト局面を使用すると、自己対局による強化学習で学習したモデルのpolicyの一致率もvalueの一致率は以下のようになった。

イテレーション	policyの一致率	valueの一致率
1	0.41755396	0.6928097
2	0.42115012	0.69208926
3	0.42269236	0.69095576
4	0.42438433	0.6935829
5	0.42493716	0.69430405
6	0.42519188	0.6961772
7	0.42581162	0.6924004
8	0.42696634	0.6953033
9	0.42807713	0.6971584
10	0.42900684	0.6960269
11	0.42939773	0.69955724
12	0.4297164	0.6982497
13	0.430544	0.69985163
14	0.43124306	0.6994239
15	0.43179193	0.6997897
16	0.43170047	0.7023887
17	0.4324307	0.70205444
18	0.43276954	0.70325536
19	0.43360597	0.70227855

floodgateの棋譜に対しては、policyとvalueどちらも一致率が上昇傾向にあることが確かめられた。

2018/6/20追記

自己対局による強化学習の学習開始モデルとした事前学習（49億局面）したモデルと、教師ありで収束するまで（11億局面）学習したモデルで、floodgateのレート3500以上の棋譜に対して一致率がどうなっているかを検証した。

	policyの一致率	valueの一致率
事前学習（4.9億局面）	0.4090266	0.68762606
教師ありで収束するまで（11億局面）	0.41536444	0.6936132

事前学習したモデルは自己対局による強化学習を行ったモデルよりも、policy、valueともに一致率が低い。
自己対局による強化学習を行ったモデルは、教師ありで収束するまで学習したモデルよりもpolicy、valueともに一致率が高くなっている。
自己対局による強化学習で、教師ありよりも強くできることが裏付けられた。

詰み探索の高速化

前回までに作成したdf-pnによる詰み探索を自己対局に組み込んでみたが、探索速度が遅くあまり実用にならなかった。

これまでは、モンテカルロ木探索の先端ノードで全探索の7手詰めを行っていたが、それと同じ時間になるようにdf-pnの探索ノード数を調整すると、150ノードしか探索できない。

150ノードでは、7手詰め以上の詰みを見つけられるときもあるが、7手詰めを見逃すことがあり、単純には置き換えることができない。
インライン化やテンプレート化をして高速化を行ったが、改善は数%程度で、なかなか高速化できずに困っている。

ハッシュのサイズを小さくするほど探索速度が上がるので、CPUのキャッシュヒット率が関係していそうだが、df-pnで優越関係を使用しているため、ハッシュエントリサイズが大きく、キャッシュに載せるのが難しい。
詰み探索に特化したハッシュ構造を考える必要がありそうだが、今のところ良い案が浮かばないので、詰み探索を組み込むのは宿題としておく。

github.com

バグ修正

テストしているときに、また王手のバグ修正が見つかった。
玉で開き王手する場合に、玉の自殺手を除外していなかった。

王手生成の最大数

詰み探索のMovePickerには最大合法手分の配列を確保していたが、王手生成に限れば最大合法手分よりもサイズを減らすことができる。
そこで、スタックサイズを節約するため、配列のサイズを王手生成の最大数に合わせることにした。

合法手の最大数

合法手の最大数は、以下のページで593であることが証明されている。
http://www.nara-wu.ac.jp/math/personal/shinoda/bunki.html

王手生成の最大数

王手生成の最大数は、上記のページのような証明が考え付かなかったので、自分で最大ではないかという局面を作成した。
sfen 9/R1S1k1S1R/2+P3G2/2G3G2/9/B1NL1LN1B/9/4K4/4L4 b G2S2NL17P 1

この局面で王手の数は65になる。

もしかしたら、これ以上の局面があるかもしれない。
見つけた方がいたら教えてもらえると助かります。

こんな局面になる前に詰んでいるので65あれば大丈夫だとは思いますが。

バグ修正

自作の王手生成ルーチンを使用して王手の数をカウントしていたところ、またしてもバグを見つけた。
王手生成ルーチンは、やねうら王のコードを元にしていたが、やねうら王で、

(pos.pieces(GOLDS)  & check_candidate_bb(Us, GOLD  , themKing))

となっていたところを、Aperyをベースに作成したコードで、誤って、

(pos.bbOf(Gold) & goldCheckTable(US, ksq)) |

としていた。
やねうら王の、GOLDSは、と金なども含むので、と金などの手が生成されていなかった。
Aperyでは、

(pos.bbOf(Gold, ProPawn, ProLance, ProKnight, ProSilver) & goldCheckTable(US, ksq))

とする必要があった。

追記

さっそくTwitterで65以上の局面を教えていただきました。

sfen 5S1S1/RS5k1/5G3/9/5NL1L/9/9/1K7/B8 b RB3GS3N2L18P 1
これで、67手です。

さらに、

sfen B7B/1R7/6R2/9/4k4/9/9/9/K1N6 b 4G4S3N4L18P 1

飛車で開き王手して、飛車が成らない場合と成る場合がある方が多くなります。
ただし、私の王手生成では実戦の速度重視で打ち歩詰めの考慮をしていないので、飛車は必ず成るようにしており、上の67手が最大になりそうです。

追記その2

さらに、情報をいただきました。
不成りも含めると、

91が最大になりそうです。

大駒の不成りを除く条件では、

4S4/R1S3k1S/4+P3+P/9/8N/4N3N/1L7/B8/5L1LK b RB4GSNL16P 1
74になりそうです。
（私の王手生成では香車の2段目不成も除いたので73になりました。）

教えていただきありがとうございました！

優越関係を利用した証明数と反証数の初期化

局面Aが局面Bを優越する場合、Aの証明数はBの証明数以上になる性質がある。
そのことを利用すると、Aの証明数は、AとAに優越されるすべての局面の証明数の最大値をAの証明数とすることができる。
反証数についても同様に優越関係を利用できる。

これをそのまま詰み探索に適用すると、かなりの局面で探索ノードが増えて遅くなってしまった。
原因は追究できていないが、探索ノードが多い局面ほど遅くなる傾向があるため、サイクルとDAGが関係していると疑っている。

そこで、先端ノードのみでこの性質を利用して証明数と反証数を初期化するようにした。

速度比較

優越関係を利用して証明数と反証数の初期化を実装する前後で探索速度は以下のようになった。

15手詰みの局面

sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

	探索ノード数	処理時間
優越関係利用なし	28372	108ms
優越関係利用あり	7200	31ms

探索ノード数が25.3%になり、処理時間は28.7%になり、大幅に速くなった。

テスト用局面のほとんどの局面で改善しており、テスト用の37局面の合計で、処理時間が85%になった。

まとめ

優越関係を証明済、反証済局面以外の局面にも利用することで、探索速度を改善できた。
はじめ先端ノード以外でも利用していて効果がなかったため採用を見送っていたが、先端ノードのみに適用してみたら効果あった。
先端ノード以外に適用できない件はできれば原因を調べたい。

上記の15手詰みの局面で探索ノード数は、なのは詰め64bit版の16929よりも少なくなっている。
しかし、処理時間はなのは詰めは19msで、まだ及んでいない。
持ち駒の実装を詰み探索に特化すればもう少し改善できそうであるが、詰み探索の改良は一旦保留して、自己対局による強化学習の方に現状の詰み探索を組み込む予定。

github.com

反証駒

前回までに実装した詰み探索では、ループの対策を行っておらず、最大深さまでループする局面があった。
ほとんどの局面では閾値がうまく働いて無限ループにならないが、以下の19手詰めの局面で最大深さまでループが発生していたため、優越関係を反証に利用すると、最大深さに達した局面が不詰み扱いになるため、誤って不詰みと判定されていた。
sfen ln6K/1ksPg1sG1/5s2p/ppp3p2/9/P1P3P2/4+p3P/1+r7/LN3L2L w RBSb2g2n7p 1

完全なループの対策をする方法もあるようだが、とりあえず簡易な実装として千日手チェックを行い千日手となった局面にはハッシュに印をつけて、優越関係では利用しないようにした（親のノードにも影響するので完全な対策にはなっていない）。
判定が誤ることなくても、ある程度ループしている局面があったようで、千日手チェックを入れるとテスト用の37局面の合計で3%程速くなった。

反証駒

前回証明駒を実装したが、反証駒も実装した。
反証駒は、証明駒とは逆に不詰みを証明するための後手の最小の持ち駒のことを示す。

ハッシュは、すべて先手の駒で保持しているため、後手の駒を先手の駒に読み替えて実装する必要があった。

不詰みの局面では、後手側では、反証駒を0にして、先手が1枚も持っていない種類の駒を反証駒に加える。
これを先手の持ち駒で表現すると、先手が持っている種類の持ち駒に後手の持ち駒を加える（後手の持ち駒を0にすると同義）。
先手が1枚も持っていない種類の駒を反証駒に加える部分は、もとから先手の持ち駒は0なので処理は不要となる。

ANDノードでは、後手が駒を打った場合は反証駒を減らし、後手が駒を取った場合は反証駒に加える。

ORノードでは、子局面の反証駒の積集合とする。また、先手が一枚も持っていない種類の駒の反証駒を0にする。

速度比較

反証駒を実装する前後で速度を比較した。

15手詰みの局面

sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

	探索ノード数	処理時間
証明駒のみ	28372	108ms
証明駒＋反証駒	28372	110ms

探索ノード数は変わっておらず、処理時間も誤差の範囲である。

不詰み局面

sfen +B2B1n2K/7+R1/p2p1p1ps/3g2+r1k/1p3n3/4n1P+s1/PP7/1S6p/L7L b 3GS7Pn2l2p 1

	探索ノード数	処理時間
証明駒のみ	952464	2158ms
証明駒＋反証駒	910453	2062ms

探索ノード数が減っており、4.4%程処理時間が速くなっている。

テスト用の37局面の合計では、4.9%程速くなった。

考察

反証駒の実装前後で、処理速度の改善は5%以下であった。
証明駒の効果と同程度である。両方組み合わせると局面に依存するがテストした局面の合計では10%程改善した。
探索ノード数が多い局面ほど、効果があるようである。

証明駒も反証駒も参考にできるオープンソースがないため、実装があっているかあまり自信がない。
github.com