TadaoYamaokaの日記

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

将棋AIの進捗 その32(MCTSの探索にAND/OR木を導入する)

Leela Chess Zeroの状況を定期的にウォッチしないとなと思って、issueを眺めていたら"Exact-Win Strategy for Overcoming AlphaZero" #799という投稿がされていた。
Leela Zeroのissue#2276にも同様の投稿がある。
ざっくり説明すると、子ノードが勝ちの場合、そのノードを再度探索しないという探索のアイディアである。

元の論文「Exact-Win Strategy for Overcoming AlphaZero」では、この方法によりLeela Zeroのオリジナルに対して61%の勝率になると報告されている。

元の論文は有料だが、Leela Zeroのissueに抜粋が掲載されている。
f:id:TadaoYamaoka:20190810094745p:plain

要約すると、

  1. 子ノードに1つでも確定した勝ち(囲碁の場合2回のパス)、負け、引き分けがあると、そのノードは選択しない。
  2. 子ノードに1つでも確定した負けがあると、その親ノードを勝ちとマークする。すべての子ノードが勝ちの場合、負けとマークする。すべて引き分けの場合、引き分けとしてマークする。

ということだ。

MCTSの探索に、負けが確定した局面を探索しないという枝刈りと、AND/OR木による詰み探索を導入するアイディアと解釈できる。

dlshogiでは、MCTSの探索中に短手数(7手)の詰み探索を導入している。
終盤では勝敗が確定するノードが現れやすいため、この探索の導入には効果があると思われる。
例えば、ノードが8手詰みの局面で、子ノードに詰み探索に勝ちが確定した局面あったとしても無駄な探索を行ってしまう。
この方法によって探索が効率化できる。
また、8手以上の詰みでも、探索によりAND/OR木を成長できるので、MCTSでも確実な詰みの判断ができる。

dlshogiでは、すでに詰み探索を導入しているため、論文のノードに確定した勝ち負けをマークするという部分はすでに実装されているため、論文の探索方法を容易に実装できるため、試してみた。

次のような10手詰め(後手負け)の局面で、
f:id:TadaoYamaoka:20190810210934p:plain
sfen lnS+N5/6Gg1/p1pp+R3p/4ppS2/1p1sk4/2P1LlP2/PP1P1+p2P/1KGS2+b2/LN1r1+n2+b w G4P 96

試したところ、探索の改良前は、3秒の探索で、27483ノードの探索して評価値-2956だったが、改良後は、230ノードの探索で詰み(負け)が確定できた。

終盤では、このような局面がゲーム木の途中に多数現れるため、探索の効率化につながると予測できる。

実際に勝率に効果が表れるかは、別途連続対局で効果を確認したい。

なお、Leela Zeroでは、勝敗が確定する局面はそれほど多くないという理由で保留されている。
Leela Chess Zeroは、効果を検証中のようだ。

2019/8/12追記

技巧2と1手3秒で100回対局して勝率を比較した。

勝敗数 勝率 信頼区間(95%)
改善前 35勝61負4分 36% 46.4%~27.5%
改善後 38勝58負9分 41% 52.0%~32.2%

勝率は高くなっているが、信頼区間95%では強くなったとは言えなそうだ。
さらに対局数を増やして確認する必要がある。

信頼区間の計算方法
import math
def UCB(X, N, Z):
    return (X+Z*Z/2+Z*math.sqrt(X*(N-X)/N+Z*Z/4))/(N+Z*Z)
def LCB(X, N, Z):
    return (X+Z*Z/2-Z*math.sqrt(X*(N-X)/N+Z*Z/4))/(N+Z*Z)
UCB(35, 100-4, 1.96)
LCB(35, 100-4, 1.96)
UCB(38, 100-9, 1.96)
LCB(38, 100-9, 1.96)

参考:Wilson score interval を使う。 - 中野智文のブログ