高速な詰め将棋アルゴリズム完全に理解したい（その１）
Qhapaq アドベント将棋記事６日目
※：執筆時間不足の関係で複数回続きます。申し訳ないです ※：現在の記事の最新版はこちらです（連作ではなく、全ての解説を最新版に記載しています）
昨今のコンピュータ将棋は超高速で詰め将棋を解くことが出来る。という文言は多くの将棋プレイヤーが聞いたことがあるとは思います。
今の詰将棋のルーチンの屋台骨となっているのはdf-pnアルゴリズムです。df-pnアルゴリズムは凄く雑に言えば「攻める時は逃げる側の逃げる手が少なそうな手を、逃げる時は攻める側の次の手が少なそうな手を優先して選ぶ」というものです。例えば以下の記事などに詳細が記されています。
さてしかし、実際の将棋ソフトでは本当に深さ優先探索をしているわけではありません。というのも、純粋なdf-pnアルゴリズムには並列処理がしにくい、局面の無限ループを回避し難いという問題があるからです。
そこで本稿からしばらくの間、今のtanuki-詰め将棋エンジンに実装されているdf-pnアルゴリズムの概要を説明していきたいと思います。今回はアルゴリズムの原著論文（英語）の疑似コードに逐一日本語の解説を付けていきます。
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);
}
AIの対抗系から終盤問題を作ったらいい感じかも知れない件
Qhapaqアドベント将棋記事 5日目
棋力向上には詰将棋をやれ仮説に従って、コンピュータ将棋を駆使して終盤の詰み筋問題の自動生成をしたところ、問題が難しくなりすぎて悶絶してからはや一日。敬愛する将皇の終盤問題の多くが対抗系であることに目をつけ、QRLに保存されている振り飛車将棋ソフトの棋譜から終盤問題を生成し直したらいい感じの問題が作られるようになった気がしてきました。
【とりあえず問題をあげてみる】
・実践型から作った詰め将棋
l6nk/6+Ssl/p2p3pp/4P1g2/2Pn+r2NP/6SP1/P2G5/9/LN3PK1L b RBGS5Pbg3p 1
詰み手順例：２１成銀、同玉、４１飛打、３１銀、３２銀打、同玉、４３角打、２２玉、２１金打（４手目で３１に合駒をしても、３２銀打、同玉、４３角打、４１玉、５２金打）
凄く雑な表現ですが、いい感じな気がします。
穴熊の玉を引きずり出す、１路離して飛車を打つ、将棋の終盤ででてくるエッセンスがいい感じに組み込まれています。対抗形は長年愛された戦型だけあって将棋のエッセンスがよく入ってるなあ。
【何故良くなったのか、本当に良くなったのか】
正直わかりません。そもそも本当に問題として解きやすくなったかも謎です。偶然私にも詰み筋が見える問題が出来ただけかも知れません。
敢えて予想するなら、対抗系の将棋は玉を囲って双方駒をさばいて、さばいた駒で相手の陣形を早く崩壊させた方が勝ちという戦いが多いため、攻める側の持ち駒が似たようなものになりやすく、玉の崩し方定跡も整備されているからではなかろうか......
【おまけ：将皇の中で難問とされていた問題を解けた人に棋力アンケートを取ってみた】
アンケートに協力いただいた将棋が強い皆様、そして、私と同じように挑戦して爆死した将棋若葉マークの皆様、心よりお礼申し上げます!
アンケートの様子からすると将皇の詰み問題はアマ段位では割と解けてしまうらしいので、段位者向けのやや難しめの問題を作ることを目指そうと思います！!
【おまけ２：先程の将棋から余計な駒を取り除いた詰め将棋】
7nk/6+Ss1/8p/6g2/8P/6SP1/9/9/6K1L b RBGPrb2gs3n3l14p 1
最短手数は27手詰め、最短手数の詰み上がり図に余り駒はない、27手以上かかる詰み筋もあるようです。興味がある人は上記sfenをやねうら王に突っ込んで対局してみてください。答えを見ずに詰ませられた人がいたら....貴方は凄い。是非感想を教えてください（さっき段位者向けぐらいの問題といった奴誰だ。私か。）
想定解（白抜き）：２２成銀、同玉、４２飛打、３２飛打、３１銀打、同玉、４１金打、２２玉、３２飛成、同玉、４１飛打、３３玉、１１角打、２４玉、２５歩、同金、同銀、同玉、４５飛成、３５歩、２６歩打、同玉、１６金打、２７玉、１７金、３７玉、５５角成 まで。４手目で飛車が合い駒になるのは、それ以外の駒だと、１１角打、２３玉、１２銀打、２４玉で斜めに行けない駒なら２３金打で詰み、金銀角を埋めても２５歩、同金、３４金打、同玉、４４飛成で詰みだから。む、難しい。けど心なしか良い問題な気がする。
AI作の終盤クイズが難しすぎる件
Qhapaq アドベント将棋記事 4日目
棋力向上には詰将棋をやれ仮説に従って、現在、詰将棋を無限に作ってくれるエンジンを開発しています。将棋ソフトの棋譜をベースに問題を作れば、棋譜の版権問題に引っかからずに実戦的な詰将棋を生成できるのではないかと思い詰将棋エンジンの改造に勤しんではいるのですが、中々役に立つものを作るのは難しい.....という開発日記です。
【大雑把な作り方】
将棋ソフト同士の対局棋譜に対して、駒を増やしたり減らしたりしながらひたすら詰みチェックを行い、詰んだ局面を採用するという雑な設計思想になっています。昨今の詰将棋ソルバは十数手程度の詰み筋なら1秒もかけずに見つけることができるので、局面の質よりも数の暴力を優先し、作られた棋譜を何らかの形でスクリーニングするという戦略をとります。
詰将棋アルゴリズムとして近代のソフトに取り入れられているdf-pn法について知りたい方には以下の記事をおすすめします（tanuki-/やねうら王に実装された詰将棋ソルバはdf-pnの発展系なのですが、その内容は少々難しいので割愛。ニーズがあったら今後記事にするかも）。
【終盤クイズとしての運用】
作成された詰む局面は大抵の場合、複数の詰み筋があったり、詰む際に駒が余ってしまいます。しかし、これ自体は棋力向上という観点では大きな問題にはならないと考えています。というのも、玉側を将棋ソフトに持たせて対局するという形にすれば、想定解より長い手順をプレイヤーが指したとしてもそれに対応してできるだけ詰まないような手を返すということができるからです。この技術をいち早く取り入れているのが将皇の「終盤問題」です。将皇ではプレイヤーは詰み筋のある実戦形の局面から最善を尽くして逃げてくるソフト相手に玉を詰ませるという課題にチャレンジできます。私自身、終盤力向上を目指してこのサイトで練習をしていますが、実に良いサイトだと思います。
今回私が作ろうとしているのは将皇のサービスの類型であり、局面を将棋ソフトの力を使って無限に作成しまくれることを売りにしようとしています。が......
【作られた局面を見てみる】
例えば以下のような問題が生成されます。
ちなみに、答えの一例（最短の詰み手順の一つ）は79龍、同玉、78桂成、同玉、６６桂打、６７玉、７６金打、６８玉、８８飛成、７８合、７８同龍、５９玉、５８龍です。
どうでしょう。変化が狭いからまだ簡単に見える気もしますが、１３手詰（最後の無駄合いを除いても９手）です。ちとゴツい気もします。しかし残念ながら、自動生成される問題がこのぐらいの手数で収まることは稀です。大体は下記のような感じになります。
この問題の答えの一例（最短の詰み手順の一つ）は、２４桂、１３玉、１２飛打、２４玉、３４金打、１５玉、２４銀打、１６玉、１４飛成、２７玉、１８角打、３７玉、１７龍、２７桂打、同龍、４６玉、５７馬、だそうです。無駄合いを抜いても１５手。
敢えて言おう。解けぬ
こんな長大な問題ばかり作られるのは将棋ソフト同士が数手詰レベルの頓死に引っかかってくれないからです。高度な将棋ソフト同士の戦いでは双方十数手詰めを水面下で読み合いながら殴り合っているので、詰み局面を見つけようとするとどうしてもこんなのばっかりになってしまうのです。
それならば、実際に詰むまで戦わせて詰む数手前の局面を使うというのも考えられますが、これをやると今度は負けを確信したソフトはゲームの手数を伸ばすためだけに無駄に駒を捨てまくるという仕様が邪魔をしてきます。将棋ソフトは人間を超えた終盤戦を見せる一方で、最後の最後の局面は将棋素人でも簡単にわかるようなダメダメな終盤手を指してしまうものなのです。
【今後の課題】
七手詰ぐらいの終盤問題なら将皇が沢山提供してくれているので、そもそも初心者向けの終盤問題を作ること自体が筋が悪いのかも知れません。そして、詰将棋理論に基づけば段位者でも詰将棋の練習をすべきとのことなので、段位者向けの問題すればいいのかも知れません。
しかし、、それならば段位者がどのぐらいの問題なら解けるかを知らねばなりません。案外上述の問題ぐらいでいいのかも知れないですし、やはり、難易度調整ルーチンが必要なのかも知れません。残念ながら私にはこれを論じるだけの棋力が足りない......
果たして私はこの問題を解くことができるのか。こうご期待。
【今回は】データからみる長考を棋力に変換するコツ【ネタ記事】
Qhapaq アドベント将棋記事 3日目
アマチュア将棋とプロの将棋の大きな違いの一つが「持ち時間」です。例えば名人戦となると2日で9時間（アマ棋戦は長くても1時間程度）となります。中盤の構想に時間を使うべきなのか、終盤に残して詰み筋を逃さないようにするべきなのかは棋界の未解決問題の一つであり、棋士毎の色が出る要素でもあります。
結局の所、持ち時間はどう使えばいいのか。本来であれば棋士の性格や戦型に依存するというべきなのですが、本稿ではあえてこれらを無視してデータから検討をしてみたいと思います。
（今回は独自検証ではなく、YSSの研究の再利用ですが......）
（今回のネタバレ）
【持ち時間別の悪手率の解析】
本稿ではプロ棋士の手の正確さを、持ち時間別に解析することで持ち時間の使い方を考察します。手の正確さとしては悪手度を用います。悪手度とは局面毎にコンピュータ将棋が導き出した評価値と実際に棋士が指した手に対する差分を用いたものです。悪手率については前々回の記事か、YSSの研究を読むことをおすすめします（下の図面はYSSの研究記事からの引用です）。
YSSの研究ではタイトル別の各棋士の悪手度（厳密には悪手度から予測されるレーティングの差分）を計算しています。結果は以下のようになっています。
ご覧のように、2日間のタイトル戦は目に見えて棋士が強くなっているのが解ります。一方で、1日間タイトルとNHK杯とでは悪手のレベルに大きな違いがないことが解ります。
この差分はコンピュータの将棋ではありえないことです。コンピュータの棋力は基本的に持ち時間に対してlogで上昇します。即ち、持ち時間1時間、2時間、4時間のソフトがあったら、1時間と2時間の戦力差と2時間と4時間の戦力差は同じになります。
【将棋棋士はなぜ2日タイトルでのみ強くなるのか】
夜の間に考えている、体力の問題などはパッと思いつく仮説ですが、これらの仮説では1日制 vs NHK杯の違いの少なさを説明できません。1日制のタイトルでも休憩時間はあるからです。また、昨今の完全情報ゲームでありがちなコンピュータを使ったカンニング疑惑についても、大山名人などのコンピュータ黎明期の棋士についても同じ傾向がでているため違うと言えます。この問題に熟慮を加えた結果、ある仮説が浮かびました。
その仮説とは......2日制のタイトルでは夜の休憩が長すぎて一度将棋のこと忘れざるを得ないです。脚本でありがちな一回考えたストーリーが後日見直したらつまらなく見えるというものです。
過去の記事で言及したようにプロ棋戦で重要なウエイトを占めるのは中盤の大局観です。中盤は勉強量が物を言う序盤や読みの深さが肝となる終盤とは違い、感覚的な盤面評価が肝要となります。2日制のタイトル戦の多くは中盤で1日目が終わることも鑑みると、中盤の大局観を一晩おいて考え直せるというのが棋力向上に繋がっているのではないでしょうか。
ちなみにこの発想、コンピュータ将棋での実験では正しいと言われています。評価関数の小さいノイズを入れたソフト（単体ではノイズを入れないものより僅かに弱い）を複数用意して合議をさせるとレーティングが向上することが実験的に示されています。
優れた大局観を発揮するには一旦将棋のことを忘れて考え直すことが肝要である。この仮説が成り立つのであれば、1日棋戦の昼休みに考えるなどもってのほかです。ひふみんのように賛美歌を口ずさんだり、相手の背中側に立ってみたり、滝を止めようとしてみたり、ウヒョーと言ってみるほうが良いと言えましょう。ウヒョー
※当のひふみんも2日制に比べて1日制の手の精度はイマイチだったようですが...
藤井二冠が誕生する確率
藤井七段によるダブルタイトル挑戦は今の将棋界で最もホットなトピックと言っても過言でないでしょう。最年少タイトル更新、一気に二冠かなどとも言われていますが、実際問題、藤井七段が藤井二冠になる確率はどのぐらいなのでしょうか。少し計算してみましょう。
【Eloレーティングによる勝率推定】
藤井七段がタイトルを取れる確率を計算するには、タイトルホルダーと藤井七段の各対局における勝率を見積もる必要があります。そこで今回はEloレーティングを用いて各カードにおける勝率を推定してみます。Eloレーティングとは平たく言えばプレイヤーの強さを数値化したもので、プレイヤー同士の勝率はレーティングの差から計算できます。例えば、プレイヤーAがプレイヤーBよりレーティングが100高い場合、A側の勝率は65%と予測されます。
Eloレーティングはチェス業界では長らく使われている戦闘力の指標であり、グランドマスターなどの称号の認定にも用いられています。各プレイヤーの相性などに起因した誤差も生じえますが、ある程度の精度でプレイヤー同士の勝率を当てられているそうです。オンラインゲームのマッチングなどでもよく用いられます。
Eloレーティングは各プレイヤーがゲームをする毎にプレイヤー間でやり取りされる（負けた側のレートの一部が勝った側に移る）形式になっており、プロ棋士についても有志によってレーティングがなされています。
今回は棋士レーティングの老舗である棋士ランキングのデータを用いて各対局の勝率を予測します。ちなみに、このサイトによると藤井七段のレーティングは現時点で既に1位だそうです。なんてこった......
【棋聖戦】
藤井七段と渡辺棋聖のレート差から藤井七段の各試合における勝率は約58%と予測されます。棋聖戦は既に2-1になっているので、渡辺棋聖が2勝する前に1勝すれば棋聖獲得です。
10000回のシミュレーションの結果、藤井七段がタイトルを取れる確率は約82%と予測されます。
【王位戦】
藤井七段と木村王位のレート差から藤井七段の各試合における勝率は約73%と予測されます。王位戦は現在1-0なので、木村王位が4勝する前に3勝すれば王位獲得です。
10000回のシミュレーションの結果、藤井七段がタイトルを取れる確率は約95%と予測されます。
【二冠になる確率】
棋聖奪取確率が82%、王位奪取確率が95%なので藤井二冠が爆誕する確率は約78%と予測されます。タイトル戦と普段の棋戦の持ち時間や雰囲気の違いを考えるとレーティングから勝率を予測するのが必ずしも適切であるとは限りませんが、もし誰かが「藤井二冠が誕生するに1000円賭ける」と言ってきた場合「実現したら1250円をあげよう」と言ってあげましょう。または「将棋賭博はアカンで」と注意してあげましょう。
将棋が強くなりたいならとにかく詰め将棋をやれ仮説
「将棋がどうやったら強くなるか」は将棋指しにとって長年の議題であると言えましょう。将棋が強くなる方法論にフォーカスした考察は詰め将棋や戦型の解説本に比べれば数は少ないものの、昭和から令和まで続く一大コンセプトになっています。
将棋の勉強方法として最も長く親しまれているのは詰め将棋でしょう。多くの詰め将棋本が棋力向上を謳っていますし、今最も熱い棋士である藤井聡太七段も詰将棋解答選手権を5連覇中であると同時に、詰め将棋に立脚した終盤の正確さに定評があります。
一方で、詰め将棋が棋力向上に本当に役に立つかについては、長らく懐疑的な意見もでています。最近の有名な記事でいえば若手強豪の一人である増田六段がマイナビのインタビューで挙げた「詰め将棋意味ない説」あたりが解りやすいです。
詰め将棋が意味があるのか、ないのか。はたまた、将棋は終盤勝負なのか、序盤や中盤の作戦勝負なのか。記事を調べれば調べるほど頭がこんがらがるこの問題を、今回はコンピュータに聞いてみたいと思います。
【解析方法】
インターネット対局の棋譜に対して、棋力別、局面の進行度別にコンピュータ将棋を用いた手の評価を行いました。各盤面でコンピュータが導き出した最善手の評価値と、実際に指された手の評価値の差分を悪手度とし、棋力毎にどういった局面で悪手を指しやすいかを評価してきます。
【悪手度とレーティングの相関】
横軸が段位から推定されるレーティング（強さ、右に行くほど強い）で縦軸は悪手度（上に行くほど悪手が少なくて強い）です。初手から40手目まで（序盤）、40手目から80手目まで（中盤）、80手目以降（終盤）の悪手度をプロットしたものです。
棋力はレーティング1500ぐらいでアマ初段、レーティング3000を超えるとセミプロ〜プロと言われています。
さて、このグラフを見るとアマ初段ぐらいまでは序盤の悪手度が高いことが解ります。初心者のうちは序盤の重要な定跡を覚えておらず、序盤で大ポカをしてしまう危険があることを示唆しています。多くの戦型解説書が「アマ初段ぐらいまで」をターゲットとしてるのは極めて理にかなってると言えましょう。
中盤、終盤の悪手度を比べると、中盤は棋力向上に対して改善が緩やかなのに対し、終盤は急激に良くなっていくのが解ります。特に注目するべきはプロレベルになってくると、中盤の悪手度は終盤の悪手度とほぼ並ぶ点です。増田六段がインタビューで述べてた「詰め将棋は意味ない」というのは「詰め将棋は（プロレベルになって以降は終盤よりも中盤のミスのほうが響くことが多いので相対的に）意味ない」ということだったのかも知れません。
【詰め将棋で上がる勝率は1〜2割？】
さて、プロレベルの人間を除けば将棋のミスの最も大きな部分が終盤にあることが示唆されました。では終盤における詰め将棋の重要度はいかほどなのでしょうか。本稿ではこれを「詰め将棋が完璧なら勝てた対局の割合」を用いて評価していきます。
より具体的には、相手玉に詰みがある局面で手を間違えて自分が不利（評価値-2000以下）な局面にしてしまった対局 ＋ 自分が有利な局面(評価値+2000以上)で手を間違えて自玉が詰みになってしまった対局の割合を段位毎にプロットしていきます。結果がこちら（横軸がレーティング、縦軸が詰め将棋が完璧だったら勝てた試合の割合）。
驚くべきことにも（？）アマ数段レベルに至るまで、詰め将棋が完璧ならば勝てたであろう試合は１割程度あるという予想が得られました。
この勝率変化をどう捉えるかは人次第なところではあると思いますが、棋譜のビッグデータ解析（？）をする限りでは、「プロ級でない限りは詰め将棋をとにかくやれ」が結論のようです。
角換わりの銀の行き場のナッシュ均衡
本稿はQhapaq Research Labの棋譜検索ツールの宣伝記事です。
今では序盤研究のお供としても活用されるようになったコンピュータ将棋ですが、コンピュータ将棋同士の対局での序盤研究では長らく勝率ベースの定跡作成が用いられています。高精度な昨今の評価関数でも序盤の評価値の微妙な差は見分け難いので、沢山戦わせて勝ちやすい戦型を選ぼうというわけです。
ではここで問題、居飛車角換わりには棒銀、腰掛け銀、早繰り銀がありますが、一番勝率が高いのはどれでしょう.....？
というわけで実際に検索してみましょう。QRLでは将棋ソフトのレート測定に用いた棋譜のデータベースがあります。そしてそのデータベースでは様々な戦型を検索することが出来ます。角換わりの棋譜数を戦型別に検索することで勝率の高い戦型を探すことが可能です。
Qhapaq Research Lab kifu_no_na wa
検索できるタグ一覧
コンピュータ将棋の棋譜検索 in Qhapaq Research Lab - django-\/\/ i K |
【解析結果】
この表において特筆すべき点は3つです。
１．後手腰掛け銀（特に相腰掛け銀）の引き分け率が高い
２．相早繰り銀の先手勝率が低い（こちらは統計誤差的にちと怪しいが）
３．腰掛け銀 vs 棒銀も引き分け率が高い（これも統計誤差的に怪しいが）
表を眺めながら角換わりの銀のナッシュ均衡を考えると恐らく以下のようになります。
１．先手は腰掛け銀にする
先手は銀の態度を先に決めることになりがち故に、相早繰り銀になるリスクを考えると腰掛け銀。相早繰り銀で後手腰掛け銀への勝率を上げる、引き分け率を下げるという手もあるが、どちらも増分は微々たるもの。
２．後手は引き分けを狙いたければ腰掛け銀か棒銀、引き分けを避けたいなら早繰り銀
引き分けを勝ちと考えるか負けと考えるかで最適解が変わります。角換わりの銀は三すくみなどと言われてましたが今の将棋ソフトにとってはどれも大差ないようです。実戦的には先手は腰掛け銀、後手は自分の研究手をぶつけるといった形になりそうです。先手のほうが対策しなければならない手が広い分、事前研究コスト的な意味ではしんどいと思われます。
というわけで、角換わりの銀ですが、先手はとりあえず腰掛けましょう。後手は好きにしてくださいでFA。
【追記：本研究の課題】
この研究ではどのソフトの棋譜であるかは加味していません。QRLの棋譜データに入ってるソフトは新しめのものが多く、人間よりは強いだろうとは思います。が、強いソフトと弱いソフトのレート差は数百程度あるので、特定の強いソフトが特定の戦略を取りやすい場合、勝率にブレが生じる可能性が有ります。
気になる人はソフト名も含めて絞り込み検索をしてみると良いでしょう（読者の課題とするってやつです。言ってみたかったんだ
【追記２：個人的な疑問】
人間視点で見た角換わりの戦型ってどうなってるんでしょう。最近は角換わりブームも少し落ち着いた気がしますが、先手側で対応しなければならないことが増えすぎて、角換わりを先手が拒否する傾向が出てきた......とか？
