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

先日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の作者である芝先生からは次のようなコメントを頂戴している。

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

■ 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前後であるようだが、さらに桁違いに強いソフトで桁違いの計算資源を投与して生成されたテラショック定跡を見てみたいという気持ちは大いにある。

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

テラショック定跡の生成手法」への11件のフィードバック

  1. 書きなぐったので説明わかりにくいですね。いずれきちんと書き直すかも。

    一言で言うと与えられたsfenの局面をleaf nodeとしてminimaxしてるだけなんですけど…。

    • 評価値付きの定跡(makebook thinkコマンドで生成したもの)でないとテラショック定跡にならないです(´ω`)
      評価値付きの定跡をテラショック定跡に変換するコマンドは…気が向いたら公開します。
      課題局面の周辺を自動で掘り進めてくれるほうがいいような気がしてて、もうちょっと改良しようと思ってます。

  2. テラショックの堀り進めプロジェクトは、かつてのやねうら真定跡のようにユーザーに課題局面を分散して思考してもらう感じになるのでしょうか?
    やねうら王のWCSC連覇を応援してるので、気になって夜しか眠れません。
    http://yaneuraou.yaneu.com/2016/07/11/%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8B%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E5%AE%9A%E8%B7%A1%E3%82%92%E4%BD%9C%E3%82%8B/

    • 掘り進めプロジェクト、仮に2000万円分の予算で掘るとして、2年後にソフトの改良で+R400になれば、4倍相当ですので500万円ぐらいの予算で同じ分だけ掘れることになります。ですので、あまり大きな予算でいますぐ掘ってももったいない意味もあって、大きなスポンサーがつかない限りは年間予算で言うとせいぜい100万円ぐらいで掘れる範囲で掘っていくぐらいで良いのかなーと思っています。

      まあ、ユーザーの協力を得たほうがいいのかもしれませんけど、その仕組みをつくるのもタダではなくて…(´ω`)

  3. make bookを使った定跡生成は、棋譜の「数」と「質」のどちらが重要になってくるのでしょうか?悪手を最終的に避けてくれるのであれば質より数でしょうか?

    • テラショック定跡手法のことでしょうか?

      まあ定跡にhitしないと話になりませんけども、それでもmin-maxのようなことをするので末端の評価値が最悪のケースで初期局面まで上がってくるので、末端の局面に1つでもノイズがあるとそれに影響を受ける程度にはセンシティブですから、質が悪いと自分が良かれと思ってその局面に誘導して、実は良くないということが頻繁にありえるような…。

  4. 棋譜の質はある程度必要なのですね。
    最近、もっと効率よく自分の欲しい棋譜を得たいと思い、
    「N手目になるまで、指定した深さまで探索して自動で最善手を出力する処理をやねうらおうにさせるバッチファイル」
    を作っているのですが、USIの送受信の仕組みが分からず、やねうらおうから最善手を取得する際、
    やねうらおうが自動生成するログ履歴から bestmoves を取得する
    という方法を取ろうと考えています。
    バッチファイルでのUSI送受信をもっとスムーズにするのは可能でしょうか?ちなみにバッチファイルの理由は、cmdで簡単に取り扱えるからです。また、個人的にはJavaが良かったのですが、外部プロセスとのやり取りをプログラムしたことがなかったのもあって、バッチにしました
    長文すみませんm(_ _)m

    • batchファイル、あまりお勧めしないです。

      USIのプロトコル以前の問題として、USIは標準入出力を経由してやりとりするだけなので、Javaですとjava.lang.Processで子プロセス起動して、その標準入出力をリダイレクトすればいいだけだと思いますが、私はJavaはあんまり使ってないのでよくわかりません。

      Python覚えて、Ayaneを使うのが一番簡単だと思います。
      https://github.com/yaneurao/Ayane

      Pythonなら、shogi.csaとかで簡単に局面操作ができますし…。
      https://bleu48.hatenablog.com/entry/2018/07/06/011128

      • なるほど
        たしかにpythonの方が記述量少ないですし使いやすそうですね
        python勉強してあやねる用にプログラム作り直します
        返信ありがとうございますm(_ _)m

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です