先日100テラショック定跡を公開した。本記事では、その生成手法について詳しく書く。

※　100テラショック定跡、公開しました

■　従来手法

コンピュータ将棋の定跡生成手法として現在最先端の手法はshotgun方式と呼ばれるものである。

これはSDT5(第5回将棋電王トーナメント)で準優勝したshotgunおよび、WCSC28(第28回世界コンピュータ将棋選手権)で優勝したHefeweizenの用いていた定跡生成手法である。

■　shotgun方式

shotgunの手法については次の論文に詳しい。

※　コンピュータ将棋における定跡生成法の一提案
: https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=192055&file_id=1&file_no=1

■　テラショック定跡とshotgun方式との比較

また、テラショック定跡について、shotgunの作者である芝先生からは次のようなコメントを頂戴している。

竹部先生がやねうら王チーム側についたので軽い煽りを入れたつもりが間髪入れず完全にお返しを喰らった感じになりました。横歩取り３３角に対する同飛成ですが，同飛成らずまで生成している様子。

■　shotgun方式の不満

shotgun方式は優秀な手法であると思う。しかし、人間が悪手を取り除くようなメンテナンスが必要である点や、実戦ベースの指し手であり実際に探索した指し手ではない点などが私の肌に合わなかった。

そこで、なるべく少ない作業工数(≒プログラムの行数)で定跡をメンテナンスフリーな形で自動生成できないかと考えた。

幸い、やねうら王には与えられたsfenファイルの局面に対して思考する機能がすでに搭載されている。例えば与えられたsfenファイル(book/records2019.sfen)に対して、depth 32で20手まで思考させるならば次のようにコマンドを書く。

makebook think book/records2019.sfen book/book2019.db moves 20 depth 32

この思考された局面をleaf node(末端node)として扱い、minimax(実際のコードはNegamax)のようなことをすれば良いだけであった。なんだ？すでに出来ていたのか！

■　テラショック定跡生成手法

1) makebook think コマンドで思考されたファイルbook2019.dbがあるものとする。
2) このbook2019.dbの定跡を読み込んで、以下の処理を行い、user_book1.dbを書き出す。

【疑似アルゴリズム】

※　VMDは、Value , Move , Depthの値が入っている構造体であるとする。
※　read_bookは上記1)で生成した定跡
※　write_bookは上記2)で生成すべき定跡
※　posを初期局面で初期化して、nega_max(pos)とすると定跡生成完了。

■　解説

全合法手を各nodeで生成して、それによって1手進めて、read_bookにhitするかを判定しているというところがミソで、不成の指し手であろうとその指し手で進めた局面がread_bookにあるなら、これが登録される仕組みである。

ということは、上記1)の方法で読み込ませたsfenに出現した局面すべてがleaf nodeになりうるということである。1)で用いたmakebook thinkコマンドは定跡DB上にすでに候補手が存在して局面に対しては二度思考しないため、効率よく思考対象局面を抽出することができる。

■　何のsfenを与えるべきか？

1)の方法で何の局面を与えるかということが問題になるが、まずはプロの棋譜を16手目ぐらいまで与えた。次に自己対局棋譜やNNUEkai、dolphinとの対局棋譜などを与えた。

■　この手法の優れているところ

この手法には、ある種の学習機能がある。

例えば、自分がベストと思っている変化があるとして、その末端で相手に何か良い指し手を指されてその後形勢を損ねたとしよう。そのsfenファイルを1)のときに与えると、そこで出現した局面が思考対象局面となり、候補手が得られる。上の疑似アルゴリズムを見てわかるように、このときの候補手と実戦で現れた局面との双方がleaf nodeになり、ベストな変化をNegamaxで採用するわけである。

この形勢を損ねた変化のほうが(相手にとって)良い変化であると判断されれば、2)で定跡を生成したときに、この変化を自動的に回避するようになる。

このため、悪手を人間が見て取り除くような作業の必要がなく、この定跡はメンテナンスフリーであると言える。

■　千日手の処理

千日手のスコアの処理については上の疑似アルゴリズムでは詳しく書いていないが、実際のコードではある親nodeが先手であるときのVMDと後手であるときのVMDとをpairにして返すことにより、先手のContempt(この符号を反転させたものが千日手を受け入れるスコア)と後手のContemptとして異なる値を取れるようにしてある。

あと同一nodeに訪問したとき用にwrite_bookに書き出すと同時に、unordered_mapにその局面のVMDの値を保存してある。そこにhitしたらnega_max()は、その値をそのまま返すというような処理をしている。ただし、それは千日手局面であるかの判定をしたあとでなければならない。(千日手のほうを優先しないと、2度目の訪問で千日手扱いにならないため)

■　まとめ

テラショック定跡の手法は計算資源をバカ食いする。この点においてshotgun方式と比較して優れているとは言えない。しかし、計算資源をどんどん投与して強いソフトで定跡を掘り続けたときに、将棋のある戦型に対して結論めいたものが得られるというような可能性はある。

現在の最先端のソフトはR4500前後であるようだが、さらに桁違いに強いソフトで桁違いの計算資源を投与して生成されたテラショック定跡を見てみたいという気持ちは大いにある。

あと、将棋以外のゲームでもゲーム木を探索するタイプのゲームであればこの手法が適用できると思うので活用されたし。