探索木の可視化

第3回世界将棋AI電竜戦も終わってひと段落がついたので、掲題の通り、前から気になっていた探索木の可視化をやってみました。

将棋ソフト界隈ではαβ法などの説明でよく登場する探索木ですが、将棋ソフト開発者側も基本的にいつも見えているのはGUIが表示している読み筋の冒頭だけで、対局中の探索でどのように探索木が伸びていっているのかまでは見えていません。
そこで好奇心半分、探索部の復習半分として探索木の可視化を試してみました。

■対象ソフトの選定
山岡さんの書籍「強い将棋ソフトの創りかた」でも使われているpython-dlshogi2を用いました。
最初からDL系ソフトで可視化することを考えていたのと、
探索部がpythonで書かれているので扱いやすく、実行時に逐一ビルドが必要ないことから採用しました。
※モデルや探索部はpython-dlshogi2をそのまま利用しています。

■グラフの可視化手段
graphvizを用いました。
タプルを列挙するだけで簡単に有向グラフが描ける手軽さから採用しました。

■可視化方法について
mcts_player.pyの中身を書き換える形で実装しました。
先述の本でも解説されている通り、MCTSを用いるDL系将棋ソフトは以下①～③を繰り返すことで探索木を成長させます。
①選択
②展開・評価
③バックアップ

このとき、③にてバックアップを行う際にcurrent_nodeとそこに紐づくchild_nodeの情報を保持しているため、
current_nodeをキーに順次リストへ追加していくようにしました。（既に存在する場合はchild_nodeを更新する）

上記のようにして探索木を可視化したのがこちら。（※探索木が巨大（非常に横長）になるため、goコマンド実行直後の７六歩の手を探索したところで止めています）

ちなみに、もう少しだけ探索木を伸ばすと以下のようになります。横が長すぎて直接はてなブログに画像を上げれなかったのでgoogleドライブから見てください。(pcからの方が見やすいです)
drive.google.com
４手先でさえこれだけ広がってくるので、将棋がどれだけ候補手が多いゲームかが少し体感できた気がします。

今回はお試しということでpngファイルとして可視化しましたが、graphvizはさらに巨大な探索木を出力しようとするとpngファイルではつぶれてしまうのでsvg形式やPDFにする必要があるかもしれないです。

では、今度は「DL系とNNUE系で探索木の伸び方がどう変わってくるのか？」、「DL系はNNUE系と比べて本当に狭く深く読んでいるのか？」という話が気になってくるのですが、NNUE系ソフトはソースコード全然読んだことがなく不慣れ（やねうら王コマンド叩いたことくらいしかない）なので、もし誰か既にやっている方orやってくれる方がいたら教えていただけると嬉しいです。