電竜戦振り返り（１日目）
２０２０年１１月２１日〜２２日にかけて世界将棋AI電竜戦が行われています。将棋電王トーナメント以来の冬の陣ということで私も「deqshi」、「Qhapaq overfit adventure」として参加をしています。本稿ではソフト開発の裏話を紹介したいと思います。
なお、１日目予選を経て、deqshiは15位、qhapaqは8位となり、それぞれ決勝戦はbリーグ、aリーグで戦うこととなります。先日の対局を見ていただいた方、応援してくれた方に改めてお礼申し上げます。
【deqshiの開発でひたすらスタックする】
deqshiのコンセプトはdlshogiとやねうら王を利用して、その双方より強いエンジンを作ることです。ソフトの合議自体はこれまでも多く研究されていますが、それらの研究では合議に使うソフトの相対的な強さは使うハードによらずほぼ同じ、すなわち、安価な家庭用PCで検証した結果を、本番系のクラスタにも使いまわすことが出来ました。
ところが、dlshogiとやねうら王は用いるハードが異なる（GPU or CPU）ため、どちらが強いかは個々人が用意できる環境に大きく依存します。私のゲームノートPCはGPUが貧弱であるため、dlshogiよりもやねうら王のほうが強いですが、本番環境ではGPU側はV100を8台使うのに対し、CPU側は20スレッドであり、この環境なら恐らく互角〜dlshogiやや有利程度であると思われます。
そこで今回のクラスタではdlshogiかやねうら王の強い方を主軸にして、もう片方のエンジンにはそれをサポートする情報を与えるという設計にし、pr文章に記載したようなペナルティつき楽観合議を用いることにしました。これなら計算環境が変わってもパラメタを調整するだけで同じクラスタを使いまわすことが出来ます。本大会についてはこの計算条件ならdlshogiのほうが恐らく強いと思ったのと、折角だから深層学習を前に押し出そうということで、dlshogiを主軸に添え、やねうら王に適宜修正させる戦略としました。
また、過去の対局でdlshogiは序盤がやねうら王よりも強い一方で、終盤に頓死などをして逆転負けを喫することが多かったので、ある程度評価値が有利になったら、やねうら王に代打をさせるルーチンも追加しました。dlshogiによる序盤のお膳立てがあればローカルの2スレのやねうら王でも4スレ、8スレのやねうら王倒せていた（テスト対局ではほぼ逆転負けされなかった）し、dlshogiに対しても遅れを取ることはなかった（リレー形式側の勝率は55%ぐらい）のですが本番では......
deqshiの開発はdlshogiの山岡さんと共同で行いました。山岡さんのブログでも大会前日に夜遅くまでデバッグしていたと言及されていますが、クラスタのバグは勿論、細やかな開発環境の違いにも右往左往（例えば、私は対局を将棋所でしているのに対し、山岡さんは自作スクリプトでやってるとか）しており、本当に生きた心地がしない開発でした。
でも楽しかったです。デスマに付き合ってくれた山岡さんには改めてお礼申し上げます。
【突貫でqhapaqを作る】
qhapaqのコンセプトは飛車を振るになりました。正直deqshiの開発のデスマ化により凝ったコンセプトを用意できなかった面も大きいです。評価関数自体は水匠に対して振り飛車で勝率45%、各種互角局面で55%程度勝てるものが用意できていたのですが、deqshiのデスマでクラスタなどを用意する余裕がなく、チームメンバのマシンを借りることとなり、多分勝てんやろと思ったため、振り飛車を応援することにしました（takeshi賞もあるし）
決勝リーグで対策をされる可能性もあるので、細かい仕様はまだ伏せておきます。
【連続対局をしくじる】
当日はどうしても外せない用事が昼にはいっていたため、qhapaqを連続対局設定にしていましたが、見事に失敗して2試合ほど不戦敗になってしまいました。対戦相手の方々にお詫びすると同時に、お力添えいただいた方々にお礼申し上げます。
deqshiは山岡さんに操縦してもらっていたため無事でした。クラスタがクラッシュしないかヒヤヒヤしていましたが、連続対局含めて機能していたようです。
【deqshi vs みずうら王】
今回のクラスタの調整では、ほぼすべての局面でdlshogiの指し手が採択されました。これ自体は想定の範囲内の挙動でした。deqshi内のやねうら王は計算力、定跡の品質差が著しく、やねうらミラーとして勝つのは絶望的に見えたし、dlshogiは練習試合で後手番から中盤にまくり返すことに成功していたからです。
しかし、本番のみずうら王はやね師匠の定跡も加わってか大変強く、チャンスらしいチャンスがないまま負けてしまいました。Grampus戦についても同様です。
本当はdlshogiがやねうら王に勝ちやすい定跡を整備したり、もう少し序盤にやねうら王の意見を取り入れたかったのですが、そこまで用意する余裕がありませんでした。
【振り飛車qhapaq強い】
一方のqhapaqは対局失敗以外は絶好調でした。チームメンバの計算機と雑に流した計算機が滅茶苦茶強かったのです。
本日は2つのEPYC 7452で戦います。スリッパ？知りませんな。90万したらしいです。提供は @toku51n
— Yuki (@yuk__to) 2020年11月20日
スリッパ以上にご家庭向きではない計算機が投入されており（将棋ソフトへの適性という意味では恐らくスリッパに劣るのだが）、無事に動いた試合はまさかの全勝でした。
【同門対決】
deqshiもqhapaqも2敗で迎えた9試合目はまさかのdeqshi vs qhapaqの同門対決。予選突破のボーダーラインは恐らく8-2であったため、負けた方は予選敗退が決定となります。双方にとっての天王山、その結果がこちらとなります。
qhapaqの逆転勝ち。とはいえ、試合としては完全にdeqshiのペースでした。図の88銀に対して同玉が悪手で、評価値が1000程度ひっくり返ってしまったのですが、同玉はqhapaqの読み筋でもありました。すなわち
qhapaq「同玉されても負けただと思うがヤケクソじゃー！」
qhapaq「あれ、よく見たら勝ちだった」
ということです。最後は完全に振り飛車の神が微笑んだ形になりました。この他にもnozomi戦やAmaetadine戦も相当危険な橋を渡っていたと思います。が、最終的には不戦敗以外全勝だったので、なんだかんだで振り飛車強いのかもしれません。
【大会のお礼と感想】
まずは大会を企画してくださった皆様、視聴してくださった皆様、寄付やシステム開発で大会を支えてくださった皆様にお礼申し上げます。また、連続対局への失敗やマッチメイクシステムについて色々文句を言ったことをお詫び申し上げます。
参加者として感想を述べると、1人で2チーム以上参加できるルールはとても快適でした。これのお陰でdlshogiとの共同開発とqhapaqの開発を両立することが出来たので、非情に助かりました（1人1チームと言われたら多分deqshi単体になった....かな）。
個人的には持ち時間のルールも良かったと思います。適度にドキドキできる一方で、割と余裕を持って試合回数をこなせるので見ていて楽しかったです。
マッチメイクの方法についてはwcscの手法によせたほうが良いと思います。大会の目的が強さの格付けであるとするのであれば、今回のマッチメイクは残念ながら、明確に失敗していたと思います。例えば、上位陣が直接対決をせず、きふわらべクローンと戦い続けた結果、勝てども勝てども勝ち星の差が埋まらないという事態はwcsc型のマッチングでは起こらない現象です。
もっとも、電竜戦は予行練習も数行っていたし、内部でテスト計算もするなど事前検査はかなり真剣にやっており、本番にガチ参加者（ときふわらべクローン）が大量参加したという超想定外の挙動に対するバグみたいなものであったと考えています。運営の経営手腕の問題ではないと思うし、考えようによっては誰が勝つかわからないドキドキ感が割り増したと言えなくもありません。
それでは本日もよろしくお願いします。
将棋の先手勝率＝52%に騙されてはいけない
Qhapaq アドベント将棋記事15日目
将棋における最初の勝負所は「先手を引くか後手を引くか」といえましょう。先手に戦型の選択権があり、後手のほうが苦労が多いのは人間でもコンピュータでも同じです。コンピュータ将棋では、先手の勝率は約6割あります。故に振り駒の時点で勝った側がガッツポーズをすることだってあります。
しかし、これはあくまでコンピュータの話です。コンピュータは人間に比べ戦型の好みが一つのものに偏りやすく、小さな違いが大きく評価される傾向にあるだけに過ぎません。実際、プロ棋士の将棋では先手の勝率は約52%であり、これは将棋の優れたゲームバランスを示唆するものでもあります。
と、思われてきました。が、違うと思います。本稿ではプロ棋士の後手勝率も実効的には４割ぐらいしかない45%弱である仮説をデータを駆使して紹介したいと思います。
2020.07.29、記事の誤っていた部分を修正＋藤井棋聖に関するデータを追加
【プレイヤーの強さの差を無視している】
棋士全体の先手勝率から先後のバランスを考えることの致命的な欠点は、プレイヤーの強さの差を無視していることです。思考実験として筆者と羽生善治九段とで100本勝負をしてみましょう。先手後手は対局毎に入れ替えるとします。先手勝率はどうなるでしょう。まず間違いなく、50%になります。先後の有利関係なしに実力差がありすぎて、羽生九段が100-0で勝つからです。勿論、プロ棋士は筆者よりも遥かに高いレベルでしのぎを削り合っています。とはいえ、プレイヤーの強さの違いを無視するのは流石に問題があると言えましょう。全く実力差がないのであれば、約３０年間も７つ（8つ）しかないタイトルを一人の棋士が握り続けることはまずないでしょう。
【プレイヤーを固定して、先後に由来するハンデを測定する】
そこで本稿では、プレイヤーを固定して、そのプレイヤーの先手/後手の勝率差がどのぐらい出るかから、先手がどのぐらい後手に対して有利かを測定してきます。幸いプロ棋戦では先後の決定に段位などの序列を用いることはないため、先手のときだけ強い相手と戦うといった現象は起こらないと言えます。
本稿では加藤一二三九段、羽生善治九段、渡辺明二冠、藤井聡太棋聖の先手、後手毎の勝率を測定していきます。なお、これらの棋士について全ての棋譜を集約できたわけではありません。特に古い棋譜の抜けが激しいので、加藤九段の勝率は実際よりも低く見積もられています。なお、特定の時期の棋譜が抜けることは上記仮説には影響がでないと考えています。
【レーティングに換算して60ぐらい損している】
加藤一二三九段 = 先手勝率51%、後手勝率41.5% = 先後レート差 60
羽生善治九段 = 先手勝率73%、後手勝率66% = 先後レート差 65
渡辺明二冠 = 先手勝率 68.5%、後手勝率60.5% = 先後レート差 60
藤井聡太棋聖 = 先手勝率 86%、後手勝率79% = 先後レート差 85
時代によらず、だいたいEloレーティングに換算して70前後、損をしていることが解りました。面白いことにも、これは今のコンピュータ将棋の先手後手の勝率差(60%-40%)におよそ近い値です。
本研究によれば、仮に同じ強さの棋士が戦った場合の先手の勝率は60%55%ちょいになると予想されます。観戦者につきましては、より真剣な表情で振り駒を眺めるべきでありましょう。
【追記：どこを間違えたか】
羽生九段の強さをX、相手の強さをY、先手であるときに入るボーナスをZとすると
羽生九段先手時の勝率から計算されるレート差 = X - Y + Z
羽生九段後手時の勝率から計算されるレート差 = X - Y - Z (相手にボーナスが入る)
先手、後手間のレートの差分 = 2Z
羽生九段先手 vs 羽生九段後手のときのレート差 = Z
というわけで、先手後手の勝率から計算されるレート差を半分にする必要があるところを、綺麗サッパリ忘れていたようです。
幸いにして、勝率52%に騙されてはいけないという命題には影響がでていないものの.....これは恥ずかしい、本稿の内容をうっかり吹聴したフレンズの皆様、申し訳ありませんでした。
やねうら王搭載の詰将棋ルーチンの千日手対応
Qhapaq アドベント将棋記事 14日目
やねうら王（tnk-）に搭載のdf-pnベースの詰将棋エンジンが図巧の1番を解けないことが発覚しました。時折聞かれる「コム将棋の開発ってどうやってやるの」という問への答えとして使えそう課題なので、図巧の1番の解決を目指したライブデバッギングをネタの水増しとしてやっていきたいと思います。
【1日目】
【まずどの局面で詰まないのかを二分探索する】
図巧の答えを見たい人はこちら。
図巧の１番は６９手目という超大作です。詰むはずの局面を詰まないと言われただけで問題が見えるレベルのサイズではありません。というわけで、まずは２分探索をして、何手目から読ませたら詰まなくなるのかを確かめます。
30手目から...詰む
16手目から...詰む
8手目から...詰まない
12手目から...詰まない
14手目から...詰む
ということで、どうやら１３手目に対して不詰の変化がある（模範解答は１４手目が正確ではない）と主張していることが解りました。
となると、１３手目の１５飛車打に対して、tnkの詰め将棋ルーチンはどんな手で詰まないと主張しているかを知るのが良さそうなことが解ります。打ち歩詰めや合法手生成が間違っているのか、はたまた本当に不詰なのか......
【2日目】
【詰まない変化を追いかける】
次にやねうら王を改造し、不詰の局面でどのような変化を提案するかを調べます。不詰の変化を全列挙するのは大変なので、特定の変化（手順をmove形式で与える）についてのみ、ハッシュテーブルに保存されたpn、dnをとりだせるようにした上で、詰みの場合は詰みの手を、不詰の場合は不詰の手を返すようにします。
その結果、13手目から探索をした場合▲15飛車打、14手目△25飛車打の手順が不詰である（▲15飛車打、14手目△25飛車打したあとの局面を初期局面にした場合は詰むにもかかわらず！）という出力が得られました。
となれば、何かしかの影響で、詰み手順の中の局面が不当に不詰に書き換えられていると予想できます。
【ハッシュの重複を探す】
局面の評価を書き換えうる要素としてまず浮かぶのが局面のハッシュ（キー）の重複です。この詰め将棋エンジンではキーは32bitであるため、億単位の局面を探索すれば重複がありえます。幸いにも、上述の「詰まない」と言われる局面で探索される局面の数は数千万オーダーなので、局面のsfen文字列を全て保持してもメモリは爆発しなさそうです。
そこで、局面が新しく探索されるたびに、その局面のハッシュとsfenのペアを保存し、異なる局面が同じハッシュを持っていないかをチェックしました（mapでデータを扱えば局面数をNとした場合の計算量はO(NlogN)なので全ての組み合わせについて検証が可能です）。ところが、局面のハッシュ衝突は見られませんでした。となると、少なくとも今回の問題ではハッシュ衝突は原因ではないようです。
【千日手の処理がどうやらおかしいようだ】
ハッシュが原因ではないということで、不詰にされた局面をよく眺めると、どうやら千日手周りの局面で評価がおかしいことに気付きました。tnkの詰め将棋エンジンでは千日手になった局面は不詰の評価を付けていますが間違いです。というのも、「千日手の変化は不詰」であっても「千日手の変化の途中で出てくる局面が不詰」とは限らないからです。例えば以下のような局面で千日手の筋が見つかったことを理由にこれらの局面を不詰にすると、本当は詰む問題について詰まないという結論が出てしまいます。
【問題の要件をまとめる】
千日手周りの問題を処理するには以下の要件を満たす必要があります。
・何らかの理由で千日手周りの変化の検討を打ち切る
・千日手を構成する局面のpn、dnを不当に不詰に変えてしまわない
【3日目】
【千日手処理を書き換える】
問題の要件と今回用いた解決方法を改めて図にまとめると以下のようになります。従来のルーチンでは千日手になった局面を詰まないとみなしていたため、左図のような変化で詰みを見つけることが出来ません。そこで、今回の改造では「千日手の変化で不詰とするのは千日手の変化の中でもっとも開始局面から遠い局面（末端局面）とする」、「末端局面が攻め手側の場合は、親局面に戻る手を違法とする」ことで今まで扱えなかった変化で詰み筋を見つけられるようにしました。
【以下、感想戦】
【原著論文の実装しょぼくね？】
原著論文の実装ではこんなありがちなケースも解けないのか、と思うかも知れませんが、通常の千日手の変化であれば、局面をそもそもループなどせず、攻め手側が別の手を探索してくれます。というのも、普通であれば局面を深く探索するほど局面のpn、dnは増えるため、ループをする時点で親局面や兄弟局面のpnを千日手の変化のpnが上回るからです。
今回の千日手で厄介だったのは受け手側に千日手を拒否する選択権がなかった（王手に対して合法手が１つしかなかった）ことです。これだと手を何度ループしてもpnは1から増えない（pn=1は詰みを除けば最も魅力的な変化）ため、攻め手側も千日手の変化を望んでしまうのです。
【問題は完全解決したのか】
ぶっちゃけしてないと思います。あくまで変な不詰が出る変化が少し減っただけと言えましょう。上記改造の脆弱性としては、例えば、千日手を構成する各々の局面の初期局面からの距離が探索の過程で変わる（より短い手数でその局面にたどり着く方法が見つかる）などがありえます。
【以下、個人的ポエム】
連休を詰将棋の改良に使った感想は「詰将棋の解析は1日でならない」というものでした。やねうら王に搭載されている詰将棋ルーチンの原著論文では、千日手周りの処理についての解説は殆どなく、千日手の処理は「不詰判定の一部」とみなしているようです（恐らく、論文通りの実装した結果が上記の脆弱性なので、解説を端折ってるか論文のやり方に不備があるかだと思います。正直な話、今回考えたハックを原著論文の技術を正しく実装しただけと言われたらちょっとムカつく）。
詰将棋界隈にはまだまだ上がおり、超難しい詰将棋を安定して解かせるという意味では、脊尾詰やなのは詰めのほうがまだまだ格上なのではと正直思います。とはいえ、やねうら王には詰将棋以外のルーチンも搭載されていること、ごく一部の難しい詰将棋でなければ現状の実装でも十分解けること、計算事態が高速であること、オープンソースであり様々な環境で動くこと（個人的にはこれが一番大事）などを考えれば不完全であっても十分な価値があり、一歩ずつでも品質を高めていくのは大事なのではないかなと思います。
今回作ったデバッグ用のコードの中では、詰め将棋探索後にユーザが特定の局面を指定することで、その局面のpn/dnを見られるルーチンは便利だなと思いました。詰将棋エンジンの隠しコマンドとしてコイツもプルリクしたいところです。
【おまけ】
なのは詰めなどの既存ルーチンがwindowsでしか動かないバイナリでしか配られていないと言った所、linuxで動かす方法を色々教えてもらいました。皆様ありがとうございます。
暫く日記の更新が滞ってましたが、手強い問題解決のコツの一つに、気がめいらないように休憩をちょくちょく入れるというのもありますのでそういうことで......
やねうら王搭載の詰将棋ルーチンの改造中継（ver 2）
Qhapaq アドベント将棋記事 13日目
前回の記事もマージしています。
やねうら王（tnk-）に搭載のdf-pnベースの詰将棋エンジンが図巧の1番を解けないことが発覚しました。時折聞かれる「コム将棋の開発ってどうやってやるの」という問への答えとして使えそう課題なので、図巧の1番の解決を目指したライブデバッギングをネタの水増しとしてやっていきたいと思います。
【1日目】
【まずどの局面で詰まないのかを二分探索する】
図巧の答えを見たい人はこちら。
図巧の１番は６９手目という超大作です。詰むはずの局面を詰まないと言われただけで問題が見えるレベルのサイズではありません。というわけで、まずは２分探索をして、何手目から読ませたら詰まなくなるのかを確かめます。
30手目から...詰む
16手目から...詰む
8手目から...詰まない
12手目から...詰まない
14手目から...詰む
ということで、どうやら１３手目に対して不詰の変化がある（模範解答は１４手目が正確ではない）と主張していることが解りました。
となると、１３手目の１５飛車打に対して、tnkの詰め将棋ルーチンはどんな手で詰まないと主張しているかを知るのが良さそうなことが解ります。打ち歩詰めや合法手生成が間違っているのか、はたまた本当に不詰なのか......
【2日目】
【詰まない変化を追いかける】
次にやねうら王を改造し、不詰の局面でどのような変化を提案するかを調べます。不詰の変化を全列挙するのは大変なので、特定の変化（手順をmove形式で与える）についてのみ、ハッシュテーブルに保存されたpn、dnをとりだせるようにした上で、詰みの場合は詰みの手を、不詰の場合は不詰の手を返すようにします。
その結果、13手目から探索をした場合▲15飛車打、14手目△25飛車打の手順が不詰である（▲15飛車打、14手目△25飛車打したあとの局面を初期局面にした場合は詰むにもかかわらず！）という出力が得られました。
となれば、何かしかの影響で、詰み手順の中の局面が不当に不詰に書き換えられていると予想できます。
【ハッシュの重複を探す】
局面の評価を書き換えうる要素としてまず浮かぶのが局面のハッシュ（キー）の重複です。この詰め将棋エンジンではキーは32bitであるため、億単位の局面を探索すれば重複がありえます。幸いにも、上述の「詰まない」と言われる局面で探索される局面の数は数千万オーダーなので、局面のsfen文字列を全て保持してもメモリは爆発しなさそうです。
そこで、局面が新しく探索されるたびに、その局面のハッシュとsfenのペアを保存し、異なる局面が同じハッシュを持っていないかをチェックしました（mapでデータを扱えば局面数をNとした場合の計算量はO(NlogN)なので全ての組み合わせについて検証が可能です）。ところが、局面のハッシュ衝突は見られませんでした。となると、少なくとも今回の問題ではハッシュ衝突は原因ではないようです。
【千日手の処理がどうやらおかしいようだ】
ハッシュが原因ではないということで、不詰にされた局面をよく眺めると、どうやら千日手周りの局面で評価がおかしいことに気付きました。tnkの詰め将棋エンジンでは千日手になった局面は不詰の評価を付けていますが間違いです。というのも、「千日手の変化は不詰」であっても「千日手の変化の途中で出てくる局面が不詰」とは限らないからです。例えば以下のような局面で千日手の筋が見つかったことを理由にこれらの局面を不詰にすると、本当は詰む問題について詰まないという結論が出てしまいます。
【問題の要件をまとめる】
千日手周りの問題を処理するには以下の要件を満たす必要があります。
・何らかの理由で千日手周りの変化の検討を打ち切る
・千日手を構成する局面のpn、dnを不当に不詰に変えてしまわない
今回は此処まで。
次回はこれらの要件を満たす千日手の処理方法を考えます（次回が最終回です。問題は（多分）解けます）
【おまけ】
なのは詰めなどの既存ルーチンがwindowsでしか動かないバイナリでしか配られていないと言った所、linuxで動かす方法を色々教えてもらいました。皆様ありがとうございます。
暫く日記の更新が滞ってましたが、手強い問題解決のコツの一つに、気がめいらないように休憩をちょくちょく入れるというのもありますのでそういうことで......
今の詰将棋ルーチンが図巧の1番を解けない話
Qhapaqアドベント将棋記事12日目（深夜34時にお送りします）
前々回の記事で解説したdf-pnベースの詰め将棋ルーチンですが、やねうら王（tnk）に搭載されているdf-pnベースのルーチンで図巧（江戸時代に作られたクッソ難しい詰将棋集）の1番が解けないことが発覚しました。時折聞かれる「コム将棋の開発ってどうやってやるの」という問への答えとして使えそう課題なので、ここから暫くは図巧の1番の解決を目指したライブデバッギングをネタの水増しとしてやりたいと思います。
図巧第1番とか pic.twitter.com/bWUljBBFDs
— かず (@kazu_nanoha) 2020年7月21日
ご報告いただいた、かずさん（なのはの中の人）にお礼申し上げます。
【まずどの局面で詰まないのかを二分探索する】
図巧の答えを見たい人はこちら。
図巧の１番は６９手目という超大作です。詰むはずの局面を詰まないと言われただけで問題が見えるレベルのサイズではありません。というわけで、まずは２分探索をして、何手目から読ませたら詰まなくなるのかを確かめます。
30手目から...詰む
16手目から...詰む
8手目から...詰まない
12手目から...詰まない
14手目から...詰む
ということで、どうやら１３手目に対して不詰の変化がある（模範解答は１４手目が正確ではない）と主張していることが解りました。
となると、１３手目の１５飛車打に対して、tnkの詰め将棋ルーチンはどんな手で詰まないと主張しているかを知るのが良さそうなことが解ります。打ち歩詰めや合法手生成が間違っているのか、はたまた本当に不詰なのか......
今日はここまで。次回は詰め将棋ルーチンを改造して不詰の変化を出力できるようにする....できるといいなあ。
【細かい補足】
ハッシュテーブルが品切れになって盤面の評価が不適切になっている可能性も調査当初はありましたが、ハッシュサイズを変えながら二分探索をすることで、その可能性は低いことも示せました。問題の分割、大事です。
高速な詰将棋アルゴリズムを完全に理解したい（完成版）
Qhapaq アドベント将棋記事10日目
今の詰将棋アルゴリズムで最強と言われているハッシュテーブル+df-pn探索(depth first - proof number)による詰将棋アルゴリズムの完全理解を目指していきます。
参考文献： memo.sugyan.com
【proof numberとは】 proof numberとは平たく言えば詰将棋専用の盤面評価値みたいなものです。通常の盤面評価値と違って、詰み証明のための評価値(pn)と不詰証明のための評価値(dn)があります。pn、dnは「この局面の詰み(proof number)/不詰(disproof number)を証明する為に調べなければならない局面の数」であり、値が小さいほど詰み/不詰に近いという扱いになります。そして、詰み /不詰が証明された局面についてはpn、dnは0になります。局面のpn、dn（厳密には非0のpn、dn）はあくまで探索途中での予測値にすぎないことに注意してください。即ち、pn、dnは探索の途中で増えたり減ったりします。
【ハッシュテーブルとは】 雑に言えば局面毎のpn、dnを保存する辞書のようなものです。将棋などのゲームでは手順前後により重複した局面が多々でてくるため、一度探索した局面を覚えておくことで計算の効率を向上させます。
【proof numberの更新】 ある局面のproof numberはその局面（親局面）から到達できる局面（子局面）のpn、dnを用いることで更新できます。各人が最善を尽くすという仮定により、攻める側の手番では「候補手の中でどれか一つでも詰みが見つかれば詰み」、「不詰を証明するには全ての手で不詰を証明しなければならない」という条件が、受ける側の手番では「候補手の中でどれか一つでも不詰が見つかれば良い」、「詰みを証明するには全ての手で詰みを証明しなければならない」となっていることに気をつけてください。即ち、pn、dnの更新方法はどちらの手番であるかによって変わります。
辞書の扱いにも注意してください。辞書に局面が記載されていない場合、pn=dn=1で初期化された状態で辞書に局面が追加されます。
【pn、dnを使った深さ優先探索】 ハッシュテーブルを用いたdf-pn探索では各局面のpn,dnを逐次更新しながら、攻める側はできるだけ相手の受けが少ないような手（= 子局面のpnが小さいもの）を、受ける側はできるだけ次の王手が続きにくい手( = 子局面のdnが小さいもの)を優先して探索することで詰み、不詰みを高速に証明しようとしています。具体例として以下のようなpn,dnの木を使ってみましょう。現在、親局面（攻め側の手番）から最もpnが小さい局面へ探索対象が移った状態です。同じ親局面から行くことができる手を兄弟局面、今見ている局面から行くことができる局面を子局面と呼びます。
１．局面探索でまず最初に行うのは、子局面pn,dnを用いて今居る局面のpn,dnを更新することです。更新方法は上述したとおりです。
２．その後、今見ている局面のpn,dnを更新した後で、兄弟局面のpn, dnと比較を行います（より厳密にはpn, dnの2番手の値などを事前に保存しておき（付録のコード内でthpn, thdnと呼ばれている変数です）、それと比較を行います。）
３−１．このとき、今見ている局面のpn, dnが兄弟局面に比べて小さいなら、今見ている局面から最もpn、または、dn（攻め手側ならpn、受け手側ならdnを使う）が小さい子局面に探索対象を移します。
３−２．一方、pn、dnが他の兄弟局面に負けているのであれば（厳密には親局面から予測される兄弟局面のNo2との値の最大値を上回ったら）、親局面に探索対象を戻します。
探索対象が変わったら、新しい探索対象の小局面を用いてpn, dnを更新に戻ります（１の手順）。
この探索を繰り返していくと、どこかしらの局面で詰み、または不詰み（王手の合法手がない局面）に到達します。それらの局面に到達したら、詰みの場合はpn=0、dn=∞、不詰みの局面はpn=∞、dn=0として親局面に探索対象を移します。
上記ルーチンを繰り返すことで、初期局面のpnが0になれば詰み、dnが0になれば不詰みであることを示すことが出来ます。
【inc_flagを利用した無限ループ回避】 しかし実は、上述のアルゴリズム単体は局面がループした場合に対して脆弱性があります。以下の図をみてみましょう。（原著論文の図面を改変したもの。）
上図面のように局面のループがあると、pn/dnの更新の時点で当該局面のpn, dnは親局面のpn, dnを超えてしまいます。そのため、上述の３−２のルーチンに従い、探索局面を親局面に戻さなければなりません（２も参照）。そのため、局面P以降は探索されることがなく、局面Qが唯一の詰み筋であった場合、詰み筋を見つけることが出来ません。これを避けるためには、自分よりも先祖の局面にループした場合の特殊処理を挟む必要があります。以下の図を見てみましょう。
tanuki-などで採用されているアルゴリズムでは以下の条件をすべて満たす場合、局面を親に戻すためのしきい値thpn, thdnを書き換えることで、強制的に子局面を探索させるようにしています。
- 子局面に自分よりも初期局面からの距離が短い、かつ、詰み/不詰みが解っていない局面がある
- 子局面から戻された探索ではない
ループした局面のpn, dnはほかの子局面よりも大きいため、正当な子局面への探索をすることが出来ます。 上記アルゴリズムを行うことで局面の詰み/不詰みを高速に判定することが出来ます。
【df-pnで見つかる詰み筋について】 df-pnで見つかった詰み局面は最短手数であることが保証されていません。あくまでpn, dnが小さい局面から探していくため、手数が短くても変化が広い詰み筋は後回しになるからです。ちゃんと短い手数の詰み筋を見つけるにはdf-pnに手数の制限を加える必要があります。例えば、深さN以上の局面については強制的に不詰とすることで、手数をN手に縛った探索を行い、詰み筋が見つかるか否かを判別することができます（この表現、実は正しくない。詳細はオマケ参照）。
【まとめ】df-pnを使った詰将棋ルーチンについて解説をしました。本技術を用いればかなり超手数の詰将棋も見つけられるようです。
【付録】 tanuki-の詰将棋エンジンに搭載されているアルゴリズムの原著論文（英語）の疑似コードに日本語の解説を付けたもの。コードが読める人だとこっちのほうが解りやすいかも。
func DFPNwithTCA(n, thpn, thdn, inc_flag) {
// この関数が再帰的に呼ばれる。n=局面
// thpn = n のproof number(pn)がこれ以上なら探索を打ち切る
// thdn = nのdisproof number(dn)がこれ以上なら探索を打ち切る
// inc_flag thpn, thdnを増やすことで探索を強制的に打ち切らないようにする
// nが詰み、または、王手をかける手がない（不詰確定）の場合、探索を打ち切る
if (n is a terminal node) {
handle n
return;
}
first time = true; // ループに入って最初の処理かを判別
// 以下無限ループ
while (1) {
// n が探索されるのはこれが初めてならthpn, thdnの拡張は不要
if (n is a leaf) {
inc flag = false;
}
// nの子局面の中にnよりも元局面からの深さが浅い局面がある = ループしている、かつ、子局面の詰み、不詰みが確定していない
if (n has an unproven old child) {
inc flag = true; // inc_flagをon
}
// 局面nから合法手を生成、子局面のpn, dnからnのpn,dnを計算する
expand_and_compute_pn_dn(n);
if (first time && inc flag) {
thpn = max(thpn, pn(n) + 1);
thdn = max(thdn, dn(n) + 1);
}
// 局面nのpn, dnが thpn, thdnより多い
// ≒局面nの兄弟局面の中にnよりpn, dnが小さい局面がある可能性がある
if (pn(n) ≥ thpn || dn(n) ≥ thdn) break;
first time= false;
// 局面nの子局面のなかでpn, dnが最も小さいもの、２番めに小さいものを探す
n1, n2 = find_best_and_second_best_child(n);
if (n is an OR node) {
// 攻め側の場合のpn, dnの更新
thpn child = min(thpn, pn(n2) + 1);
thdn child = thdn - dn(n) + dn(n1);
else {
// 受け側の場合の更新
thpn child = thpn - pn(n) + pn(n1);
thdn child = min(thdn, dn(n2) + 1);
}
// 一番いい子ノードに対して再帰的に探索
DFPNwithTCA(n1, thpn child, thdn child, inc flag);
}
【おまけ df-pnのN手詰ルーチン】 深さN以上の局面については強制的に不詰とするというルーチンは実は愚直に実装するとクラッシュする恐れがあります。というのも、詰将棋の各々の局面に到達するために掛かる手順は一通りである保証はなく、N手以上のものから、N以下のものまで含まれうるからです。例えば、あるルートでの探索でN手以上かかって不詰と判断された局面が例えば別の詰み筋の変化の中に含まれていると「親局面も子局面も詰みが確定した不詰みの局面」が生じてしまいます。これを防ぐ簡単な方法としてはN手以上かかった、かつ、未だ探索されたことのない局面についてのみ不詰とするというものがあります。しかしこの方法も、詰将棋の各々の局面に到達するために掛かる手順は一通りではないという問題を根本的には解決できておらず、N手で詰まないということを厳密に証明することはできません。
