将棋の定跡でgameply(初期局面からの手数)って要ります?

やねうら王の標準定跡形式において、局面はsfen形式で書かれています。sfen形式は末尾にgameply(初期局面からの手数)が書かれています。やねうら王では、gameplyが異なる場合、その定跡にはヒットしませんでした。

Apery定跡形式の利点

Aperyの場合や、やねうら王でApery形式の定跡(book.bin)を使うと、gameplyを無視して定跡にヒットします。こうなっているほうが使いやすいという根強い声があって、そういう人たちがこぞってApery形式の定跡を使うため、やねうら王では、Apery形式の定跡のサポートをいつまでも続けなくてはならず、これはこれで結構な負担となっています。

個人的には、定跡形式は一本に絞りたい!その一本だけを拡張したり、使いやすくしたりしていきたいのです。

そうしないと、あっちの定跡形式にはこの機能があるけど、こっちの定跡形式にはこの機能がないだとか、この定跡形式でしか、このエンジンオプションが機能しないとか有効ではないだとか、そういう様々な問題を引き起こします。

IgnoreGamePlyオプションの追加

そこでまず、やねうら王に定跡DBに書かれているgameplyを無視するエンジンオプションを追加しました。

IgnoreGamePlyというオプションがそれです。やねうら王 V4.86以降で使えます。まだ何かバグがあるかも知れないので何かおかしいところがあればコメント欄で教えてください。

※ やねうら王 実行ファイル詰め合わせ V4.86 : https://github.com/yaneurao/YaneuraOu/releases/tag/V4.86

gameply違いの同一局面をどう扱うか

それでこのオプションを追加してから気づいたのですが、将棋には角換わりという戦型があって、この戦型がいま将棋ソフトやプロの間で大流行しているのですが、この戦型、1手、手待ちするのが最善、もしくは上位の候補手になっていることが多く、先手と後手とが協力して手待ちすることも多く、同一局面で2手gameplyの異なる局面が簡単に出現してしまうわけです。

そんなわけで、テラショック定跡も調べてみたらgameply違いの局面がたくさん登録されていたわけです。

いま、定跡DB上にある局面が、gameply = 44とgameply = 46の二通り登録されているとして、そのどちらにヒットするのが良いのでしょうか?(登録されている候補手は異なるものとします。)

これは、前者だと考えられます。前者のほうがgameplyが小さな値なので手待ちをしておらず、それゆえ、本筋で、よく指されている手順のはずで、情報(登録されている候補手)も多いと考えられるからです。

BookOnTheFlyとのIgnoreGamePlyとの相性問題

そんなわけで、同一局面の場合は、gameplyの小さいほうにヒットするようにしたのですが、やねうら王にはBookOnTheFlyと言うエンジンオプションがありまして、これをtrueにしている場合、定跡をメモリに丸読みせずに、必要なときにテキストファイルを二分探索(binary searchの訳語)で、その局面を探すので、対局開始までが早いのですよ。

いまどきの定跡ファイルは超巨大なのでメモリに丸読みする読み込み時間も馬鹿にならないので、このオプションはなかなか重宝するのですが、同一局面の手数違いが複数登録されている場合(sfen文字列の末尾の数字だけが異なる)、二分探索で一番gameplyが小さいエントリーを探すのはわりと難しいのです。

なぜなら、定跡ファイルはsfen文字列を文字列順にソートしたエントリー順に並べてあるのですが、「98」と「99」は前者のほうが(文字列比較をしたときに)小さいのですが、「99」と「100」だと後者のほうが(文字列比較をしたときに)小さいです。

うおー!そんな風になってたら、二分探索するの、めっちゃ面倒くさいやんけ!

DB上の局面のエントリー順をいまさら仕様変更して並び替えるのも嫌なので、結局、gameply違いの同一局面は、DBに書き出さない(一番gameplyの小さいエントリーだけを書き出す)ように変更しました。

makebook build_treeコマンドとのIgnoreGamePlyオプションとの相性問題

テラショック定跡をビルドするためのコマンド(makebook build_tree)も、同様にビルド元の定跡(“makebook think”コマンドで思考させた定跡)にもIgnoreGamePlyオプションみたいなことをして、gameply違いの局面にもヒットさせるべきでは?と思ったわけです。

上でも書きましたが、角換わりにおいては先後が協力して同一局面で手数をいくらでも(?)伸ばせるので、手数違いのためにいままで思考対象としていなかった局面がたくさんあることに気づいたからです。

そんなわけで、テラショック定跡のビルドでgameply違いの局面も用いるようにしました。

ところが、今度は定跡のビルドが終わらないのです。

そりゃそうです。先後協力して手数を伸ばす手順が様々あるので、千日手手順をうまく回避しながらも相当に手数を伸ばせるのです。その組み合わせたるや、膨大な数になるので、それらをすべて定跡に登録していたのでは定跡のビルドがいつまで経っても終わりません。

そこで、一度調べた局面はメモリ上にcache(一時保存しておくこと)しておくことにしました。このcacheは以前もしてあったのですが、gameplyも引っ付けた形でcacheしてあったため、上のように、IgnoreGamePlyを導入するとgameply違いの局面が無数にあって、cacheが膨大な量になってしまうのです。

そこで、このcacheからもgameplyの部分を取り除きました。

makebook build_treeコマンドとMaxMovesToDrawオプションとの相性問題

しかし、これは正しいのでしょうか。

例えばMaxMovesToDraw = 320(320手引き分けルール)で指すときに、320手目の局面はどの指し手を指しても引き分けになるはずです。つまり、定跡に登録するのであれば、ここですべての候補手は千日手スコアを返さないとおかしいのです。

そこで”makebook build_tree”コマンドでmax_game_plyを指定できるようにしました。

ところが、この320手目の局面のgameply違い(例えばgameply = 100)で同一局面が出現する場合、どうなるでしょうか。
その局面では、すべての候補手が千日手スコアだなんてことはないはずです。

しかし、上で書いたように、定跡の書き出し時に同一局面は、gameplyが一番小さな局面しか書き出さないように改造してしまいました。

やっちまったなぁ~!

おまけに、gameply違いの局面で候補手のスコアが異なるため、上で書いたcacheの技法が使えません。cacheできないと定跡ビルドがいつまで経っても終わりません。

やっちまったなぁ~!

しかも、同一局面で候補手のスコアが異なるケースがあるということは、IgnoreGamePlyオプションみたいなのを導入したら駄目だということじゃないですか?

やっちまったなぁ~!

そもそも、千日手で引き分けスコアをつけている局面、そこまでの経路(手順)が違うと千日手にならないけど、本当に引き分けのスコアをつけていいの?

やっちまったなぁ~!

結局どうすんの?

そんなわけで、色々と難しい問題を引き起こすことがわかったのですが、結論的には、
・定跡ビルドのときにmax_game_plyを指定する機能はつけない(つけられない)
・定跡を書き出すときは同一局面はgameplyの一番小さな局面のエントリーだけを書き出す
ということです。

ループとDAGのある問題

結局、将棋のような千日手のあるゲーム、コンピューターサイエンスの用語で言うところのDAG(Directed acyclic graph : 有向非巡回グラフ)とループのある問題は、df-pnアルゴリズムのようなテクニックが必要になるということなんですけど、まあ、これがとても難しいので、テラショック定跡のビルドルーチンに組み込みたくないわけです。

そんなわけでテラショック定跡のビルドルーチンは、「まあ、現実的には大丈夫だろう」という程度のコードでごまかしてあります。たぶん、大丈夫です…たぶん…。

オセロの定跡ビルド

オセロにおいては、テラショック定跡のようにminimaxで定跡ツリーを作っていく手法は以前からあるらしいのですが(私は知りませんでした)、オセロでは千日手絡みの問題は起きません。そういう意味ではminimaxとそこそこ相性が良いわけです。

将棋のようなゲームに適用するのは本当は少々無理があって、その無理が今回IgnoreBookPlyオプションを導入したことで色々と一気に表面化したわけですが、まあ、一応、無事動いているようですけど…たぶん。

他のチームもテラショック定跡生成手法を導入する?

来年には確実に上位チームの仲間入りをすると思われるNoviceチームが、テラショック定跡を導入を検討しているようです。

テラショック定跡の生成部、実装の難しい部分は一通り書いておいたので、まあ、改良して使ってください。(`・ω・´)b

おまけ — 角換わりとテラショック定跡

それでテラショック定跡のビルド部を上記のように修正してみたところ、角換わりの40手目~70手目付近の局面では、手待ちするような指し手とか駒をバックさせる指し手が軒並み千日手スコアっぽくなりました。(千日手スコアを先手-50、後手-150にしての定跡ビルド) つまり、攻めない指し手は千日手局面に到達するということですね。当たり前かも知れませんけども。

以前のテラショック定跡は、先後協力して手待ちしたりした局面とかが掘れてなかったので、千日手スコアになっていなかったところが結構あったのですが、そういう局面がだいぶ減ってきました。

そして仕掛ける指し手に千日手スコアがついていないということは先手が仕掛ける指し手が瞬間的には成立しているということであり、今後の研究が望まれます。

いや~、角換わりの流行りの形、全部の候補手に千日手スコアがついたらどうしようかと思っていたのですが、そんな簡単じゃ全然なさそうですね!将棋はまだまだ楽しめそうです。

将棋の定跡でgameply(初期局面からの手数)って要ります?” への14件のコメント

  1. 試行錯誤の考察を読むのは楽しいです。

    ある局面における評価や候補手は、それでの手順や手数とは無関係のはずで、そんなことはもちろん百も承知のはずで、にもかかわらずこれが問題になるということは、えーとつまり、定跡ファイルがツリー構造であることに起因している?
    有向グラフ構造(?)ならうまくいく?んなことできる?んなわけねえ?そういうことじゃねえ?

    定跡生成中にgameply違いの同一局面が現れたときだけ、思考時間を延ばせば、同一局面において優先されるべき、より正しい(?)評価ができるのでは?

    てかそもそも定跡ファイルの話で320手ルールが影響するの?序盤定跡を作る場合は無視してもいいのでは?

    (素人が深く考えずに書いています)

    • > てかそもそも定跡ファイルの話で320手ルールが影響するの?序盤定跡を作る場合は無視してもいいのでは?

      角換わりで先後が手待ちして千日手を巧妙に回避しながら手数を伸ばした場合、仕掛けの前に320手まで達することがあって、その局面では次の一手で321手になるため、320手ルールのもとでは詰み以外のすべての指し手が引き分けスコア(評価値)であるべきですが、その同一局面が40手目付近で出現した場合は、引き分けスコアがついていてはならないので、このように定跡DB上、同一局面であってもgameplyによって候補手のスコアが異なるという問題があります。

      角換わりは先後が協力して手数をいくらでも伸ばせるので、序盤定跡を作る時にも1000手とか2000手付近まで手数が伸びるため、この問題を無視するわけにはいかないです。

      • あーなるほど!とてもすっきり理解できました(`・ω・´)
        そして解決がとても難解であることも・・・(^ω^;)

  2. 詰みや王手へつながる状態が必ずしも高評価するべき状態であるともいえないように思えてきたw

  3. 2点伺いますので教えて下さい。自分では定跡作成は行わないつもりでソフト対局使用だけの設定です。
    1. テラショック定跡をstandard_book.db形式でソフト同士の対局で使う場合はIgnoreBookPlyをtrueとFalseのどちらにした方が勝率が高くなりますか?
    2. 評価値のない定跡をbook.bin形式で使う場合IgnoreBookPlyをtrueとFalseのどちらにした方が勝率が高くなりますか?

    • 一般論としてはIgnoreBookPlyをオンにしたほうが定跡にヒットする確率は上がりますから、定跡がそこまで悪い指し手ではないなら、思考時間を節約できる分だけ得だと言えます。
      ただし、両方のソフトで同じ定跡を使っても、特定の局面・特定の戦型にしかいかないことが多いので、その局面・戦型の勝率を計測していることにしかならないですが…。

  4. 手数はエンジン側で何とかすべきでは。
    320手で想定で作った定跡が512手になると使えないとかありえないですし。
    千日手を積極的に狙いに行く場合と絶対回避する場合で定跡が両対応できるのかはわかりませんが。

    • > 320手で想定で作った定跡が512手になると使えないとかありえないですし。

      build_treeしなおせばいいので、都度、定跡ビルドしなおし自体は私はわりとありかと思いますけども。例えば、Contemptの値もbuild_treeしたときの設定値でminimaxの結果が変わるので、千日手を狙うときもContemptを変更してのbuild_treeをする必要があります。

      それとは別に、IgnoreGamePly = falseを前提とした定跡を作ろうと思うと角換わりで手数の引き伸ばしがあるとものすごい組み合わせがあって超膨大な定跡ファイルになってしまうので、現実的ではなさそうです(´ω`)

      なのでgameply込みの定跡を使うのは無理があるという結論になりそうです。

  5. 「千日手スコアを先手-50、後手-150にしての定跡ビルド」となっていますが、これはなんでなんですか??
    -2ではいけないのでしょうか?
    あるいはプロ棋士のように引き分けは先後入れ替えて指し直すのを将棋の本則のルールと考えるならば、引き分け成立によって先後逆の初期局面になるわけですから、引き分け局面の評価値は先手−59後手59(初期局面の評価値)とするのが論理的に正しいように思うのですが…

    • > -2ではいけないのでしょうか?

      -2にすると、後手側から見た初期局面での評価値が-70程度ですので、積極的に千日手を狙いに行ってしまう定跡になってしまいます。(´ω`)
      通常の対局において、そんな定跡が欲しいのかという問題がありまして。(欲しいときはまあそれでもいいんですけども..)

  6. 先後の入れ替えには対応しているのでしょうか?
    手待ちの際には先後を入れ替えた同一局面が出てくるように感じるのですが
    すでに対応されているのか、または、それが杞憂なのか気になります

    • 先後入れ替え局面にhitするようにはしてなかったですが、なるほど、hitするようにすれば思考時間を少し節約できそうではありますね。考えておきます。

コメントを残す

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