TadaoYamaokaの日記

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

将棋AIの進捗 その33(末端ノードでの詰み探索)

dlshogiでは末端ノードで短手数(7手)の詰み探索を実施しているが、終盤ではゲーム木中に詰みの局面が多くなり、王手の合法手も多くなるため、探索速度が大幅に低下することがあった。
先日MCTSにAND/OR木を組み込む実装を行ったことで、MCTSで詰み探索を行うことができるようになったので、詰みの手数を短くしても良いのではないかと思って、5手に減らして強さを確認してみた。

以下のような終盤の局面で、7手の場合と5手の場合で速度を比較すると、
f:id:TadaoYamaoka:20190813232004p:plain
position sfen 7nl/5kP2/3p2g1p/2p1gp3/p6sP/s1BGpN3/4nPSp1/1+r4R2/L1+p3K1L w GSNLPb6p 122

7手詰め 2783 nps
5手詰め 11757 nps

となり、7手と5手で探索速度に大きな差があることがわかった。

次に、5手詰めにした場合に、技巧2と1手3秒、やねうら王互角局面集を使用して100局対局して勝率を測定した。
結果は以下の通り。

勝敗数 勝率 信頼区間(95%)
7手詰め 38勝58負9分 41% 52.0%~32.2%
5手詰め 43勝51負6分 45% 55.8%~36.0%

勝率が上がっているが、100回対局では有意とは言えない差のため、対局数を増やして確認する必要がある。
少なくとも、5手詰めにしても弱くはなっていないことが確かめられた。
これがAND/OR木の効果なのかは、AND/OR木を外して別途確認する予定。
また、3手詰めにするとどうなるかも確認したい。


探索の工夫で、技巧2(CPU 4コア)にGPU1枚(2080Ti)で40%以上勝てるようになった。
今学習しているSENetのモデルがうまく学習できればもう少しで(GPU1枚で)技巧2を超えられそうである。

2019/8/14追記

末端ノードでの詰み探索を3手にした場合、以下の通りとなった。

探索速度
3手詰め 18914 nps
技巧2に対する勝率
勝敗数 勝率 信頼区間(95%)
3手詰め 29勝65負6分 30% 40.8%~22.4%

3手にした場合は、探索速度は5手詰めより1.6倍となっているが、勝率は明らかに低くなり弱くなっている。
末端ノードでの詰み探索の深さによる局面評価の精度と、探索速度による精度をバランスさせる必要があることがわかった。
実験からは、5手詰めが最も強くなりそうである。

ただし、現在7手詰めで探索速度が低下するのは、CPUがボトルネックになっているため、GPUに対するCPUのコア数を増やすことで対処できると考えている。