TadaoYamaokaの日記

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

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

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

という方法で、初期局面集を作成した。
出来上がった初期局面集は、重複なしで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
f:id:TadaoYamaoka:20180603224219p:plain

この局面で王手の数は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

証明駒

詰み探索に証明駒を実装した。

証明駒は以下の論文の説明の通り実装した。
詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について

速度比較

証明駒の実装前後で速度は以下の通りとなった。
実装前の状態は、前回の日記に書いた先端ノードで2手詰めと3手詰めを行い、優越関係の反証への利用を行ったものと比較している(前回の実装に一部バグがあったので修正している)。

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

探索ノード数 処理時間
実装前 19504 71ms
実装後 20652 73ms

わずかに遅くなってしまった。

速くなる局面もあった。
sfen 7n1/+R5glK/n4s1p1/p4pkl1/2s3n2/P3PP2P/1P+pG5/2P6/9 b R2B2G2S2L8Pn 1

探索ノード数 処理時間
実装前 476743 1076ms
実装後 215831 517ms

他にもテスト用の37局面で比較したが、平均して改善はわずか(0.8%)であった。

実装の変更

論文では、詰みの局面と後手の局面で、後手が1枚も持っていない種類の先手の駒を証明駒に加えるとなっているが、近接王手の場合は不要なため、近接王手以外の場合のみその処理を行うようにした。

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

探索ノード数 処理時間
変更前 20652 73ms
変更後 28433 106ms

sfen 7n1/+R5glK/n4s1p1/p4pkl1/2s3n2/P3PP2P/1P+pG5/2P6/9 b R2B2G2S2L8Pn 1

探索ノード数 処理時間
変更前 215831 517ms
変更後 187811 443ms

遅くなる局面と速くなる局面がある、37局面の合計では、6%ほどの改善であった。

考察

証明駒を実装してもそれほど改善されなかった。
証明駒にはどれくらい効果があるものかデータがあれば調べたい。もっと効果があるものであれば、どこかで実装が誤っているかもしれない。
反証駒も同様に実装できるので、試したい。

github.com

優越関係の反証への利用

先日の記事で、優越関係を反証に利用するとかえって遅くなるということを書いたが、遅くなる原因は、探索を深さで打ち切りにしていることが原因だった。

作成している詰み探索は、長手数の詰将棋を解くプログラムを開発するというより、実戦の詰み探索を短時間で行いたいという動機で作成している。
そのため、探索の深さに制限を設けていたが、最大の深さに達したときに不詰みとして扱っていたため、その局面が優越関係に利用されると不詰みでない局面が誤って不詰みとされていた。
そこで、探索の制限はノード数のみとし、深さは十分に大きい値とした。

前回2手詰め、3手詰めを行うと、不詰みの局面の探索速度が落ちることを確かめたが、優越関係を反証にも利用した場合に改善するか測定した。

不詰みの局面での速度比較

前回同様、以下の不詰みの局面での速度を比較した。
sfen position l2+S1p2K/1B4G2/p4+N1p1/3+B3sk/5P1s1/P1G3p1p/2P1Pr1+n1/9/LNS5L b R2GL8Pnp 1

探索ノード数 処理時間
1手詰めのみ(優越関係の反証への利用なし) 395634 645ms
1手詰めのみ(優越関係の反証への利用あり) 67406 88ms
2手詰め+3手詰め(優越関係の反証への利用なし) 381496 724ms
2手詰め+3手詰め(優越関係の反証への利用あり) 77426 127ms

優越関係を反証に利用することで、不詰みの局面で速度が改善している。
2手詰め+3手詰めを行うと、不詰みの局面で遅くなるのは同じ傾向だが、影響は少なくなっている。

詰み局面での速度比較

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

探索ノード数 処理時間
1手詰めのみ(優越関係の反証への利用なし) 100591 330ms
1手詰めのみ(優越関係の反証への利用あり) 97599 322ms
2手詰め+3手詰め(優越関係の反証への利用なし) 19497 70ms
2手詰め+3手詰め(優越関係の反証への利用あり) 19497 70ms

詰み局面では、優越関係を反証に利用しても影響はほとんどない。

まとめ

優越関係を反証にも利用することで不詰みの局面での速度が改善することが確かめられた。
不詰みの局面で2手詰め+3手詰めを行うと速度が低下するが影響は小さくなった。
2手詰め、3手詰めで、不詰みのチェックも行うことで改善できそうなので次に試したい。

追記

2手詰めで不詰みチェックを行うようにした。
不詰みチェックは、1手詰めで詰まない場合に、王手の手がないことチェックする。
王手の手がないことは、王手生成のロジックを流用して、王手の手が1手以上ある場合に直ちにfalseを返し、王手が1手もない場合にtrueを返す。

上記の不詰みの局面で探索速度は以下の通りとなった。

探索ノード数 処理時間
1手詰めのみ(優越関係の反証への利用あり) 67406 88ms
2手詰め+3手詰め(優越関係の反証への利用あり) 77426 127ms
2手詰め+3手詰め(優越関係の反証への利用あり+不詰みチェックあり) 57130 94ms

2手詰めで不詰みチェックを行うことで、不詰みの局面での速度が改善した。
それでも、1手詰めのみの場合より探索ノード数は減っているが、処理時間は少し遅くなっている。詰み局面での改善を考慮すると許容範囲だろう。