やねうら王の標準定跡形式において、局面はsfen形式で書かれています。sfen形式は末尾にgameply(初期局面からの手数)が書かれています。やねうら王では、gameplyが異なる場合、その定跡にはヒットしませんでした。
Apery定跡形式の利点
Aperyの場合や、やねうら王でApery形式の定跡(book.bin)を使うと、gameplyを無視して定跡にヒットします。こうなっているほうが使いやすいという根強い声があって、そういう人たちがこぞってApery形式の定跡を使うため、やねうら王では、Apery形式の定跡のサポートをいつまでも続けなくてはならず、これはこれで結構な負担となっています。
個人的には、定跡形式は一本に絞りたい！その一本だけを拡張したり、使いやすくしたりしていきたいのです。
そうしないと、あっちの定跡形式にはこの機能があるけど、こっちの定跡形式にはこの機能がないだとか、この定跡形式でしか、このエンジンオプションが機能しないとか有効ではないだとか、そういう様々な問題を引き起こします。
IgnoreBookPlyオプションの追加
そこでまず、やねうら王に定跡DBに書かれているgameplyを無視するエンジンオプションを追加しました。
IgnoreBookPlyというオプションがそれです。やねうら王 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とのIgnoreBookPlyとの相性問題
そんなわけで、同一局面の場合は、gameplyの小さいほうにヒットするようにしたのですが、やねうら王にはBookOnTheFlyと言うエンジンオプションがありまして、これをtrueにしている場合、定跡をメモリに丸読みせずに、必要なときにテキストファイルを二分探索(binary searchの訳語)で、その局面を探すので、対局開始までが早いのですよ。
いまどきの定跡ファイルは超巨大なのでメモリに丸読みする読み込み時間も馬鹿にならないので、このオプションはなかなか重宝するのですが、同一局面の手数違いが複数登録されている場合(sfen文字列の末尾の数字だけが異なる)、二分探索で一番gameplyが小さいエントリーを探すのはわりと難しいのです。
なぜなら、定跡ファイルはsfen文字列を文字列順にソートしたエントリー順に並べてあるのですが、「98」と「99」は前者のほうが(文字列比較をしたときに)小さいのですが、「99」と「100」だと後者のほうが(文字列比較をしたときに)小さいです。
うおー！そんな風になってたら、二分探索するの、めっちゃ面倒くさいやんけ！
DB上の局面のエントリー順をいまさら仕様変更して並び替えるのも嫌なので、結局、gameply違いの同一局面は、DBに書き出さない(一番gameplyの小さいエントリーだけを書き出す)ように変更しました。
makebook build_treeコマンドとのIgnoreBookPlyオプションとの相性問題
テラショック定跡をビルドするためのコマンド(makebook build_tree)も、同様にビルド元の定跡(“makebook think”コマンドで思考させた定跡)にもIgnoreBookPlyオプションみたいなことをして、gameply違いの局面にもヒットさせるべきでは？と思ったわけです。
上でも書きましたが、角換わりにおいては先後が協力して同一局面で手数をいくらでも(?)伸ばせるので、手数違いのためにいままで思考対象としていなかった局面がたくさんあることに気づいたからです。
そんなわけで、テラショック定跡のビルドでgameply違いの局面も用いるようにしました。
ところが、今度は定跡のビルドが終わらないのです。
そりゃそうです。先後協力して手数を伸ばす手順が様々あるので、千日手手順をうまく回避しながらも相当に手数を伸ばせるのです。その組み合わせたるや、膨大な数になるので、それらをすべて定跡に登録していたのでは定跡のビルドがいつまで経っても終わりません。
そこで、一度調べた局面はメモリ上にcache(一時保存しておくこと)しておくことにしました。このcacheは以前もしてあったのですが、gameplyも引っ付けた形でcacheしてあったため、上のように、IgnoreBookPlyを導入すると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できないと定跡ビルドがいつまで経っても終わりません。
やっちまったなぁ～！
しかも、同一局面で候補手のスコアが異なるケースがあるということは、IgnoreBookPlyオプションみたいなのを導入したら駄目だということじゃないですか？
やっちまったなぁ～！
そもそも、千日手で引き分けスコアをつけている局面、そこまでの経路(手順)が違うと千日手にならないけど、本当に引き分けのスコアをつけていいの？
やっちまったなぁ～！
結局どうすんの？
そんなわけで、色々と難しい問題を引き起こすことがわかったのですが、結論的には、
・定跡ビルドのときにmax_game_plyを指定する機能はつけない(つけられない)
・定跡を書き出すときは同一局面はgameplyの一番小さな局面のエントリーだけを書き出す
ということです。
ループとDAGのある問題
結局、将棋のような千日手のあるゲーム、コンピューターサイエンスの用語で言うところのDAG(Directed acyclic graph : 有向非巡回グラフ。ここでは局面の合流ぐらいの意味)とループのある問題は、df-pnアルゴリズムのようなテクニックが必要になるということなんですけど、まあ、これがとても難しいので、テラショック定跡のビルドルーチンに組み込みたくないわけです。
そんなわけでテラショック定跡のビルドルーチンは、「まあ、現実的には大丈夫だろう」という程度のコードでごまかしてあります。たぶん、大丈夫です…たぶん…。
オセロの定跡ビルド
オセロにおいては、テラショック定跡のようにminimaxで定跡ツリーを作っていく手法は以前からあるらしいのですが(私は知りませんでした)、オセロでは千日手絡みの問題は起きません。そういう意味ではminimaxとそこそこ相性が良いわけです。
将棋のようなゲームに適用するのは本当は少々無理があって、その無理が今回IgnoreBookPlyオプションを導入したことで色々と一気に表面化したわけですが、まあ、一応、無事動いているようですけど…たぶん。
他のチームもテラショック定跡生成手法を導入する？
来年には確実に上位チームの仲間入りをすると思われるNoviceチームが、テラショック定跡を導入を検討しているようです。
テラショック定跡の生成部、実装の難しい部分は一通り書いておいたので、まあ、改良して使ってください。(｀･ω･´)ｂ
やねうら王式の定跡生成部、うちも実装するかぁ
— kuma@Novice (@naonza0) June 1, 2019
おまけ — 角換わりとテラショック定跡
それでテラショック定跡のビルド部を上記のように修正してみたところ、角換わりの40手目～70手目付近の局面では、手待ちするような指し手とか駒をバックさせる指し手が軒並み千日手スコアっぽくなりました。(千日手スコアを先手-50、後手-150にしての定跡ビルド) つまり、攻めない指し手は千日手局面に到達するということですね。当たり前かも知れませんけども。
以前のテラショック定跡は、先後協力して手待ちしたりした局面とかが掘れてなかったので、千日手スコアになっていなかったところが結構あったのですが、そういう局面がだいぶ減ってきました。
そして仕掛ける指し手に千日手スコアがついていないということは先手が仕掛ける指し手が瞬間的には成立しているということであり、今後の研究が望まれます。
いや～、角換わりの流行りの形、全部の候補手に千日手スコアがついたらどうしようかと思っていたのですが、そんな簡単じゃ全然なさそうですね！将棋はまだまだ楽しめそうです。
試行錯誤の考察を読むのは楽しいです。
ある局面における評価や候補手は、それでの手順や手数とは無関係のはずで、そんなことはもちろん百も承知のはずで、にもかかわらずこれが問題になるということは、えーとつまり、定跡ファイルがツリー構造であることに起因している？
有向グラフ構造(?)ならうまくいく？んなことできる？んなわけねえ？そういうことじゃねえ？
定跡生成中にgameply違いの同一局面が現れたときだけ、思考時間を延ばせば、同一局面において優先されるべき、より正しい(?)評価ができるのでは？
てかそもそも定跡ファイルの話で320手ルールが影響するの？序盤定跡を作る場合は無視してもいいのでは？
(素人が深く考えずに書いています)
> てかそもそも定跡ファイルの話で320手ルールが影響するの？序盤定跡を作る場合は無視してもいいのでは？
角換わりで先後が手待ちして千日手を巧妙に回避しながら手数を伸ばした場合、仕掛けの前に320手まで達することがあって、その局面では次の一手で321手になるため、320手ルールのもとでは詰み以外のすべての指し手が引き分けスコア(評価値)であるべきですが、その同一局面が40手目付近で出現した場合は、引き分けスコアがついていてはならないので、このように定跡DB上、同一局面であってもgameplyによって候補手のスコアが異なるという問題があります。
角換わりは先後が協力して手数をいくらでも伸ばせるので、序盤定跡を作る時にも1000手とか2000手付近まで手数が伸びるため、この問題を無視するわけにはいかないです。
あーなるほど！とてもすっきり理解できました(`･ω･´)
そして解決がとても難解であることも・・・(^ω^;)
詰みや王手へつながる状態が必ずしも高評価するべき状態であるともいえないように思えてきたｗ
２点伺いますので教えて下さい。自分では定跡作成は行わないつもりでソフト対局使用だけの設定です。
1. テラショック定跡をstandard_book.db形式でソフト同士の対局で使う場合はIgnoreBookPlyをtrueとFalseのどちらにした方が勝率が高くなりますか？
2. 評価値のない定跡をbook.bin形式で使う場合IgnoreBookPlyをtrueとFalseのどちらにした方が勝率が高くなりますか？
一般論としてはIgnoreBookPlyをオンにしたほうが定跡にヒットする確率は上がりますから、定跡がそこまで悪い指し手ではないなら、思考時間を節約できる分だけ得だと言えます。
ただし、両方のソフトで同じ定跡を使っても、特定の局面・特定の戦型にしかいかないことが多いので、その局面・戦型の勝率を計測していることにしかならないですが…。
手数はエンジン側で何とかすべきでは。
320手で想定で作った定跡が512手になると使えないとかありえないですし。
千日手を積極的に狙いに行く場合と絶対回避する場合で定跡が両対応できるのかはわかりませんが。
> 320手で想定で作った定跡が512手になると使えないとかありえないですし。
build_treeしなおせばいいので、都度、定跡ビルドしなおし自体は私はわりとありかと思いますけども。例えば、Contemptの値もbuild_treeしたときの設定値でminimaxの結果が変わるので、千日手を狙うときもContemptを変更してのbuild_treeをする必要があります。
それとは別に、IgnoreBookPly = falseを前提とした定跡を作ろうと思うと角換わりで手数の引き伸ばしがあるとものすごい組み合わせがあって超膨大な定跡ファイルになってしまうので、現実的ではなさそうです(´ω｀)
なのでgameply込みの定跡を使うのは無理があるという結論になりそうです。
「千日手スコアを先手-50、後手-150にしての定跡ビルド」となっていますが、これはなんでなんですか？？
-2ではいけないのでしょうか？
あるいはプロ棋士のように引き分けは先後入れ替えて指し直すのを将棋の本則のルールと考えるならば、引き分け成立によって先後逆の初期局面になるわけですから、引き分け局面の評価値は先手−59後手59（初期局面の評価値）とするのが論理的に正しいように思うのですが…
> -2ではいけないのでしょうか？
-2にすると、後手側から見た初期局面での評価値が-70程度ですので、積極的に千日手を狙いに行ってしまう定跡になってしまいます。(´ω｀)
通常の対局において、そんな定跡が欲しいのかという問題がありまして。(欲しいときはまあそれでもいいんですけども..)
先後の入れ替えには対応しているのでしょうか？
手待ちの際には先後を入れ替えた同一局面が出てくるように感じるのですが
すでに対応されているのか、または、それが杞憂なのか気になります
先後入れ替え局面にhitするようにはしてなかったですが、なるほど、hitするようにすれば思考時間を少し節約できそうではありますね。考えておきます。
やねうら王をgoogle colaboratoryで使える様にしてください。
まず、AlphaZero化しないと…(´ω｀)
どこで報告すればよいのか分からないのでここで
自分で作成したやね定跡をテラショック形式に変換した場合にとある局面が定跡に登録されない（伝播しない）状況が発生しています。
具体的には▲7六歩△3二金と進んだ場合の3手目の局面に指し手と評価値が付きません。
色々と試行錯誤をしましたが、以下のことが分かりました。
・テラショック変換前の定跡の最大手数が6の場合は問題なく伝播する
・7手目以降まで掘った定跡の場合は例外なく▲7六歩△3二金の局面が定跡に登録されない
・変換前の定跡には間違いなく問題の局面は登録されている（メモ帳で開いて確認済み）
・build_treeで変換した後に上記局面が消える（メモ帳で開いて確認済み）
・▲7六歩△3二金以降の局面も登録されていたりいなかったりである
例：▲7六歩△3二金▲1六歩（登録あり）
▲7六歩△3二金▲2六歩（登録なし）
▲7六歩△3二金▲2六歩△8四歩（登録あり）
以上、問題が漠然とし過ぎていて申し訳ないのですが、自力では問題特定が出来そうにないので報告してみました。
更に必要な情報があれば提供も出来ます（DBファイル含む）ので原因究明をお願いします。
ご報告ありがとうございます。その変換前の定跡ファイルを添えて、「この局面が登録されていない」という局面を書いて、私にメール(yaneurao@gmail.com)お願いいたします。(´ω｀)人
やね様最高です！ほしいものリスト協力するから機能のリクエストさせてー！
1. 評価値を勝率で出力するオプションが欲しい
やっぱり評価値って直感的じゃない気がするんです。
ニコ生とか見てても「評価値○○ってどのくらいの差ですか？」「ちょっと逆転は難しい差ですね」みたいなやりとりをしょっちゅう見る。
かくいう自分も頭の中で「評価値○○だと勝率○○くらいかな？」とか変換しつつ把握してる気がします。
だから例のポナンザの式で最初から勝率に変換したものを100倍して0から100までの整数とかにして出力するオプションが欲しいです。
どうしても勝率で見た方が分かりやすいって人のための選択肢として。
USIでは歩1枚を100点と決まってるとかGUI側でどうにかするのが本筋じゃないかとかそんなこと百も承知なんだけど、でもエンジンにそのオプション付いてても誰も困らないですよね？？？
2. 定跡の指し手の選択率を評価値に依存させるオプションが欲しい
強さとは関係ないかもしれないけど人間が対局して楽しむためには、最善手を高確率で指してくるけどたまに次善手も指すみたいなのが自然な感じで大事だと思うんです。
従来の定跡だとConsiderBookMoveCountで採択率を使ってこれが実現できたけど、テラショックだとBookEvalDiffを大きくすると下位の手も本命の手と同じ割合で指してくるし、かといって小さくすると最善手しか指さなくなる。
それで気付いたんだけど「定跡ファイルの評価値の差を採択率として使えるようなオプション」が有れば（人間のユーザーにとっては）とても便利だと思いませんか？
例えば「BookEvalDiffの範囲内でヒットした定跡の指し手について最善手との評価値の差+1を出してそれに採択率を反比例させる」みたいなオプション作れないでしょうか？？
変なこと書き込んですみませんでした。応援してます(^^)
1.は面白いとは思います。しかし、現在すでにオプション項目が多くて、どれか削ろうかと考えてたりするので、何か方法を考えます。
2.は目的は理解できますが、もう少しいい方法がありそうな…。
お返事ありがとうございます！
テラショック定跡のビルド時に100000*exp(評価値/15)みたいな値（定数は適当な例として書きました）を自動的に計算して、これを指し手の出現頻度の列に入れてしまうのはどうでしょうか？
ConsiderBookMoveCountをオフで使うときは邪魔にならず、オンにしたときは評価値が高いほど出現頻度が高くなる自然な分布で対局を楽しめるということで特に問題ないように思うのですが。
あるいは対局時にConsiderBookMoveCountがオンで出現頻度が全部1の定跡のときはその都度評価値から同じように出現頻度を計算するというのでもいいのですが……。
見当外れなことを言っていたらすみません(><)
定跡ファイル自体を書き換えるのは、あまりスマートでもないような…。まあ、考えときます。
考えていただけるだけでありがたいです！よろしくお願いします！(^^)
がいしゅつ（←なぜか変換できない）だったらすみません、Apery形式の定跡サポートが負担とありますが、素人的にはApery形式をやねうら形式等変換に変換すればイイんじゃね？とか思っちゃいます。
この定跡形式の変換は結構難しいのでしょうか。
変換したときに本当に等価になるのかよくわからないという問題があったり…。(Aperyの定跡フォーマットのほうが、やねうら王の定跡フォーマットより属性が多い場合)
うーむ、Apery形式が選ばれるのには属性が多い可能性もあるのかもしれませんね…
この辺りは棋譜フォーマットが乱立しているコム将界らしいなと感じたりw
そして『将棋神やねうら王2』では戦型指定ができるようにしないといけないので、やねうら王の定跡フォーマットに戦型が記入されるという…。