DNNの方策に従来型エンジンのbestmoveをブレンドする【コンピュータ将棋】

第31回世界コンピュータ将棋選手権の参加申込が始まり、私も久々にコンピュータ将棋の研究を再開しました。

評価関数としてDNNを使い、MCTSで探索を行う将棋AIの弱点として、読みぬけの問題があります。ここで読みぬけとは、DNNが出力した方策で、ほぼ確率0の指し手が実は有力だった場合に全く探索されず、相手がその手を指してきて評価値が一気に悪化するという現象を指しています。評価関数の精度向上はもちろん重要ですが、2020年秋の電竜戦で、評価関数の学習に相当なコストをかけているdlshogiの評価値が一気に悪くなった対局があったように思います（読みぬけなのかどうかは定かではありませんが）。この問題に対処するアイデアとして、KPPT・NNUE評価関数などを用いる従来の全幅探索型のエンジンと協調して探索することを考えます。DNNは局面を表す行列に巨大な係数行列を掛けて方策を出力する一方、全幅探索型のエンジンは数手先まで探索することにより方策を出力する仕組みで、相補的に使えるのではないかと期待しています。

具体的なアルゴリズムですが、ある局面に対し、DNNで評価すると同時に全幅探索型のエンジンで数手分の探索を行い、指し手と評価値をDNNの出力とブレンドすることにしました。MCTSにおける末端局面Bに対し、DNNが出力する方策ベクトル $P_D(B)$ (合法手それぞれに対する指し手確率)、全幅探索型のエンジンでNノード分探索した結果の最善手(bestmove)を確率1とする方策ベクトル $P_S(B)$ を係数 $\alpha$ を用いて $(1 - \alpha)P_D(B) + \alpha P_S(B)$ とし、これを方策として用います。同様に、DNNが出力する勝率 $V_D(B)$ (勝ちを1、負けを-1とするスカラー)、全幅探索型のエンジンの評価値を600で割ってtanhに通した勝率 $V_S(B)$ に対し、係数 $\beta$ を用いて $(1 - \beta)V_D(B) + \beta V_D(B)$ を勝率として用います。

非常に小さな環境で実験を行いました。小さすぎて評価結果が怪しいのでご了承ください。Pythonを用いた（並列化のない）純粋なMCTSを実装し、DNNの評価と同時に全幅探索型のエンジンをUSIプロトコル経由で呼び出して局面の評価を行います。全幅探索型のエンジンとして、やねうら王4.89+elmo2019評価関数(NNUE型)を用い、1000ノード固定で探索させました。DNNは、KPPT評価関数の探索結果から教師あり学習した64チャンネル19層のCNNです。教師データに対する方策正解率37.8%、勝敗正解率78.9%となっており実用的なモデルよりかなり弱いです。対局の開始局面として、平手初期局面から24手進んだ互角局面集を用いました。

そもそものDNNの強さを評価しました。やねうら王1000ノード固定探索を基準として、DNNだけでMCTS探索した場合の勝率を測定しました。

MCTSノード数	勝-負-分
500	31-67-2
1000	53-44-3
2000	71-25-4

探索ノード数が500~1000ノードの間でやねうら王1000ノード分と同じ強さになるようです。もう少し強いDNNモデルで評価すべきでした。

先述のアルゴリズムで評価関数をブレンドしたものを、ブレンドなしのDNNのみの評価関数と対戦させて勝率を測定しました。いずれもノード数は1000です。

$\alpha$	$\beta$	勝-負-分
0.01	0.01	52-41-3
0.1	0.1	40-0-0
0.5	0.5	43-0-0
1.0	1.0	56-9-0
0.5	0.0	52-0-0
1.0	0.0	49-0-0

従来型エンジンの探索結果を10%ブレンドするだけで、ブレンド前に100%勝てるという結果になりました。この極端な結果の原因は、DNN評価関数が弱く、従来型エンジンで1000ノード読んだ結果のほうが圧倒的に強いためであると考えられます。MCTSの1ノードの評価のために従来型エンジンを1000ノード分探索させているので、MCTSで1000ノード探索させることで実質的には100万ノード分の探索をさせていることになります。肯定的な結果ではあるものの、実験条件が本来の対局と乖離していてよくわからないというのが正直なところです。

純粋なMCTSの実装ではDNNをバッチサイズ1で評価することになり、1000ノード分の評価に10秒ほどかかってしまい、これ以上ノード数を増やした実験は困難です。またやねうら王の探索ノード数設定を1000以下に設定しても、実際には局面に応じて1000近い局面が読まれてしまうためこれ以上小さく設定することもできませんでした。純粋な環境での実験は諦め、並列化された実用的な探索エンジンに実装して試したいと考えています。例えばdlshogiには末端局面での詰み探索が搭載されているので、これをNNUE等の評価関数を用いた通常の探索に置換すれば実験できそうです（ソースコードをほとんど読んでいないのでどの程度簡単かはわかりません）。