振り飛車最強決定戦（本戦） in Qhapaq

※　この記事は 振り飛車最強決定戦（前哨戦） in Qhapaq - qhapaq’s diaryの続編です

前回の記事で三間飛車（２手目３２飛）、四間飛車、ゴキゲン中飛車、角交換四間飛車の勝率を測定してみた結果、序盤の角交換をQhapaqは良くないと思っていること、振り飛車における肝は振り飛車側が如何に開戦のタイミングを握るかであることが予想されました。

しかしながら、今まで調べた戦型では振り飛車の勝率は全て40%前後であり、振り飛車は不利という定説を覆すには至りませんでした。そこで、本稿ではこうした傾向をベースに、数ある振り飛車戦略の中から振り飛車側が戦えそうな戦略を更に抽出、検証していきます。

 

０．向かい飛車とダイレクト向かい飛車の検討を忘れてた

３４５筋に飛車を振って満足していましたが、向かい飛車も検討するべきでした。

 

f:id:qhapaq:20170216232945p:plain

向かい飛車。余談ですが私が最初に覚えた将棋の戦形は向かい飛車です。

勝率：801-43-519 （39 %）　左翼を守るために離れ駒になった金が腐る展開になりやすいようでした。中飛車と同じですね。

 

f:id:qhapaq:20170216233014p:plain

 ダイレクト向かい飛車。NHKの佐藤千田戦は本当にエキサイティングでした。

勝率：1286-39-813 （38 %）　角交換系の例にもれず振り飛車の勝率は悪いです。居飛車側の攻め駒が豊富すぎてとにかく攻めを受け止められない展開になりがちです。

 

ここまで見てきたように、振り飛車の序盤形では振り飛車の不利を覆すことができませんでした。ならば、しょうがありません。人間の棋譜からもう少し進んだ局面を用意しましょう。

 

１．初期局面から１０手以上進んだ定跡局面を使う

ほぼ無限と言ってもいい振り飛車戦略の中から何を選べばいいかはよく解らなかったので、今までの研究で示唆されてきたこと（相手に攻めのタイミングを握らせないのが鍵）をある程度満たす、振り飛車戦略の中から、タイトルホルダーの棋譜を使って検証してみることにします。

 

・四間飛車穴熊

f:id:qhapaq:20170216233128p:plain

初期陣形は広瀬穴熊より引用。６６銀からの持久戦が苦手と聞いていますが。。。

勝率 292-21-192（39%）：四間飛車穴熊対策でよく書かれている66銀型に持ち込まれ、そのまま作戦負けする棋譜が多かったです。人間とコンピュータの読みが一致したのに少し感動しました。

 

・藤井システム

f:id:qhapaq:20170216232402p:plain

銀河戦の船江 vs 藤井戦より引用。研究者の例にもれず、私も藤井ファンです。

勝率：1072-48-1069（50%）　そう、藤井システムこそQhapaqが思う最強の振り飛車システムなのです。次章でもう少し細かく解説します。

 

２．藤井システムの棋譜の評価値

 勝率が高い振り飛車戦略というと最初に疑わなければならないのが、この初期陣形になる前に、居飛車が悪い手を指しているのではないかということです。

しかし、Qhapaqの検証によれば、藤井システムの初期形までに居飛車があからさまな悪手は指していないようです。というのも、上図の初期形のQhapaqでの評価値（４コアPCで２分程度検討）は200程度の先手良しであり、四間飛車の初期陣形（76歩、33歩、26歩、44歩、48銀、44飛）の評価値（180程度で先手良し）とさほど変わらないからです。以下、実際にどんな棋譜が出てきたか簡単に紹介したいと思います。

 

３．居飛車の藤井システム対策の検証

７７角なので穴熊での持久戦に絞って検証します。

# コンピュータ的には３５歩からの急戦も有力だそうですが（Qhapaqに検証させると66歩、88玉、35歩が主な候補手となる）

f:id:qhapaq:20170217011912p:plain

さて、藤井システムで穴熊模様を撃破するとなると、船江藤井戦のような桂馬を８５に単騎で跳ねる展開を期待しがちですが、Qhapaqで特によく見る局面は上図に出てくるような美濃囲い＋端歩攻めという超古典的陣形です。この局面の評価値も200弱程度先手が良いと言っていますが、実際の勝率は５割程度でるようです。

Qhapaq藤井システムの対穴熊陣形で特に目立つ（桂単騎跳ね急戦以外のほぼ全ての対穴熊に言えること）のは

・銀冠にはしない。美濃のまま戦う

・５４に銀か金を配置する

という点です。

 

ここから予想するに（あくまで私の勝手な予想ですが）

・藤井システムを見せることで６６銀型の穴熊を妨害する（５７の銀を腐りやすくする）

・角道を塞いできたら美濃囲い＋腰掛け銀でコビンをカバーしながら玉頭の戦闘準備を整える

・穴熊に対する玉頭攻め vs 美濃囲いに対する横からの攻めの構図に持ち込むことで防御力の差を無力化する

と言った戦い方が、Qhapaqが思う、勝てる振り飛車側のストーリーのようです。

 

４．結局なんで勝てるの？

評価値が似たようなものであるにもかかわらず、勝率に大きな差がでる理由として、特にありそうなのが「コンピュータの評価軸が誤っている」、「読みぬけが生じやすい局面である」です。

前者（コンピュータが特定の局面で判断を誤る）についてはまふ氏の検証（アマチュアなどの棋譜を元に従来のコンピュータ定跡よりも強い定跡を作ってる方）でも示唆されています。しかし、今回の検証は手がバラけやすいように持ち時間を調整（0.1-2秒）しているため、評価関数の質に起因するミスはある程度緩和（流石に１０％も差は出ないと思う）できていると思われます。

となると考えられるのが、居飛車側が読み抜けしやすい展開が多いという話です。枝の複雑さは評価値にはなかなか出にくいですが、コンピュータも、人間同様に自分の手の読みぬけが致命傷になる、いわゆる”苦労の多い展開”では読みぬけの確率が上がるので、評価値外の実力差の要素には成り得ます。

 

５．藤井システムを指しこなすコンピュータの難しさ

ここまで来ると、藤井システムを指しこなすコンピュータ（またはその定跡）を作りたくなります。しかし残念ながら、藤井システムの良さが評価値に出ないためコンピュータによる自動調整は難しいです（過去に量子ガシャを試したときも居飛車穴熊相手に穴熊を組みたがる傾向が強かったですし）。また、初手からの手数が長いため、人間が手動で棋譜を食わせようとしてもその変化が膨大になってしまいます。

 

ただ、こうした知見は局面をニュアンスで判断できる人間には有益な話だと思います。コンピュータは人間を遥かに凌駕した計算力で局面を判断するため、人間との読み筋の違いが取り沙汰されますが、枝狩りの考え方などは人間にも近いところもあります。コンピュータ同士の自己対戦から、勝ちやすい戦型を探すことは人間の棋力向上に役立つのではないでしょうか。

 

６．次回予告

さて、コンピュータに指させることができるかは別にしても、藤井システムを使えば振り飛車も戦えそうという結論が得られたため、振り飛車戦型探索は再びお休みに入ります、

 

次回からは、「エンジニアこそテニミュを見に行くべき」と題しまして、ひたすらテニミュの面白さを紹介していきます。

 

テニミュの話だけしかしないと、将棋大好きな皆様は記事を読んでくれないでしょうから、人間のスパーリング相手になるコンピュータ将棋の理論とその実装についても少し触れる予定です。

振り飛車最強決定戦（前哨戦） in Qhapaq

プロ棋士の大半が居飛車を指す時代。コンピュータ将棋でも相手が飛車を振るとついガッツポーズをしてしまいがちですが、藤井銀河の爆誕や久保九段の王将戦での活躍など、振り飛車のポテンシャルはまだまだ底が見えていません。

本稿では、藤井猛九段のインタビューで先発の三本柱と言われていた三間、四間、中飛車のなかから、最強の振り飛車は何であるかを検証してみます。それと同時に、コンピュータ流の振り飛車の考え方について考察してみたいと思います。

 

１．選手入場

 本稿ではノーマル四間、ゴキゲン中飛車、３２飛車戦法、角交換四間飛車に出場してもらいます（全て振り飛車を後手番とします）。誤差を真面目に削るには万単位で戦わせなければならないのですが、面倒だったのでノーマル四間以外は約500試合ずつです。お時間あるようでしたら、どれが優勝するか予想してみてください。

ノーマル四間飛車

f:id:qhapaq:20170208212547p:plain

今なお絶大な人気を誇る、振り飛車の主役です。

 

ゴキゲン中飛車

f:id:qhapaq:20170208214320p:plain

２０００年代後半の後手番勝率の上昇に貢献した戦略の一つです。

なお、英語名称はCheerful Central Rookだそうです。

 

二手目３２飛

f:id:qhapaq:20170208214354p:plain

王座戦で羽生挑戦者が採用したことでとてつもないインパクトを

稼いだ戦略です。３２飛車を嫌がり初手を２６歩にする居飛車党も居るとか。

 

角交換四間飛車

f:id:qhapaq:20170208214722p:plain

藤井銀河の二度目の升田幸三賞受賞の立役者。

なお、研究者界隈では藤井銀河の人気は羽生三冠をも凌ぐとかなんとか。

 

２．対戦結果

 ノーマル四間飛車：40.5%

ジリジリした駒組が多い。水平線効果からかノーリスクで穴熊を許すなどの人間ならやらない類の作戦負けをしやすい。

ゴキゲン中飛車：40.5%

超速３７銀はあまりみない。居飛車側は５筋を守るのに使った金銀をそのまま玉の防御にも使えるのに対し、振り飛車側は４１の金が最後まで浮くのが痛い。大駒交換から守備力の差で負ける展開が目につくが、居飛車急戦に毒されたQhapaqは割とそれに気付かない。

 

２手目３２飛：37％

角交換四間飛車：37.5％

居飛車側からのコンピュータ特有の攻め将棋が炸裂しやすい。振り飛車（もとい美濃囲い）は角の打ち込みには確かに強いが、壁銀を繰り出しての玉頭攻めなどと組み合わせられると後手が何もできずにやられることもしばしば。戦形の再現性が少なく、見ていて目が痛くなる。

 

結果は、ノーマル四間≒ゴキゲン中飛車 ＞ 32飛車≒角交換 となりました。渡辺竜王が最近後手番で採用しているゴキ中が強いのは予想通りでしたが、ノーマル四間飛車が強いのは驚きました。私個人は、ノーマル四間飛車が戦いにくいからこそ、他の振り飛車の手法が生まれた経緯からノーマル四間が一番弱いだろうと思っていました。

 

さて、偉そうに決定戦と宣ってますが、各々の試合の誤差は大きく、この順位はさほど当てになるものではありません。しかし、どうやら、序盤に角を交換する（2手目32飛はQhapaqだと殆ど角交換になる）のは損であるというのがQhapaqの見解ではあるようです。

# まあ、角交換系とそうでないのを足しても1000ちょいにしかならず、2σの誤差は抜けられてないのですが。

 

３．コンピュータが考える振り飛車の肝

大会結果では角交換系は散々な目にあっていますが、コンピュータは後手の角交換系を苦手としているかといえば、必ずしもそうではありません。

過去に行った振り飛車定跡の研究では振り飛車側は相手の陣形が自分の陣形より薄いと見るや、自分から積極的に角交換を持ちかけています。

これらのデータから、コンピュータが考える振り飛車の肝は飛車を動かす手損を、形の良さ（美濃囲いは角打ちに強い。角が相手の玉を直接睨んでいるetc）で埋め合わせることであると予想ができます。

ノーマル四間の45歩のように、自分が望んだタイミングで戦いを始めることが大事であり、角交換で下手に居飛車に攻撃力を与えてしまうとむしろ困るというわけです。

 

４．次回予告

本大会で優勝したノーマル四間飛車やゴキ中を以てしても、コンピュータ将棋の後手勝率が47-8％程度であることを考えると、振り飛車はかなり苦しい状況と言えます。しかし、本稿の実験を通じて振り飛車の肝は、手の損を形の得に変換してから開戦するという、開戦のタイミング制御であることが示唆されました。

 

そして次回、後手番平均勝率ライン（47%）に匹敵する不利じゃない振り飛車が遂に爆誕します。（現在手元PCで検証中。このまま行けば８０％ぐらいの確率で平均ラインに届きそう。）

 

長かった振り飛車の冒険の一つの終点とも言える戦略が何であるか、皆様是非予想してみてください...

汎関数を用いた時間攻めの導出（の数学的解説）

前回の記事で紹介した汎関数を用いた時間攻めの導出について解説したのですが、読者の方から数式をもう少し解説して欲しいとのリクエストをいただきましたので、此方にて解説します。

数学マニアじゃない方にも雰囲気が伝わる用に善処はしますが、元が理系大学生が３−４年頃に習うものなので、それなりに高難易度な話です。

 

１．問題条件の定式化

T(x) ・・・x手目に使う持ち時間（単位は秒）

R(x,t) ・・・x手目にt秒使った時に正しい手をさせる確率

F(T(x)) = \sum_{x} R(x,T(x)) = R(1,T(1))+R(2,T(2))... ・・・今回最大化したいパラメタ。各々の局面において正しい手を指せる確率の和

\sum T(x) = H ・・・持ち時間の総和はHとする

持ち時間を制御することで最大化したいのは、厳密には勝率であり、各々の局面において正しい手を指せる確率の和ではありません。しかし、この記事 で検証したように、この指標はそれなりの精度で勝率と対応してくれていると考えています。

なお、 F(T(x))が所謂汎関数というやつです。

 

２．ラグランジュの未定乗数法を使って最適な時間配分が満たすべき条件を求める

時間を無駄にしている ＝ 本来読むべき局面でない局面に時間を使っている ＝ 無駄に読んだ局面と読むべき局面とでは同じ時間を費やしても得られる利得が後者のほうが大きい という思考実験をすれば、「無駄のない時間配分では、どの局面についても時間対効果が同じになっているのだろう」という予想を立てることができます。即ち

\frac{\partial R(x,t)}{\partial t} = 一定

 とするのが最適な時間配分となります。（ラグランジュの未定乗数法を用いだ導出はオマケを参照）

 

３．実験結果から、stockfishの時間配分が２の条件を満たしていることを証明する

レートの持ち時間依存性から考える技巧の敗因と探索部最適化で行った持ち時間に差があるソフト同士の勝率から、将棋の探索部は以下のような特徴を持つことが示唆されています。

・正しい手をさせる確率Rは読んだ手の深さに浅い領域では線形依存する（R = \alpha(x) d。dは深さ。\alpha(x)は局面の複雑さを意味するパラメータ。複雑な局面ほど大きくなります（複雑な局面ほど深く読むと反省することが多いため、手の深さの価値が上がる））

・消費時間は読む手数に指数関数的に依存する（T(d) = \beta^{d}。T(d)はd手読むのにかかる時間）

ここで、\frac{\partial R(x,t)}{\partial t}を計算すると

\frac{\partial R(x,t)}{\partial t} = \frac{\partial d(t)}{\partial t}\frac{\partial R(d)}{\partial d} = \frac{1}{\ln \beta} \frac{1}{\beta^{d(t)}} \alpha(x)（d(t)はt秒使った時に読める深さ）

これを一定にするには、\frac{\alpha(x)}{\beta^{d(t)}}が一定である必要があります。stockfishでは測定の中で手が変化する確率を計算しているため、\alpha(x)はある程度の精度で求められています。また、\beta^{d(t)} - 1 = (\beta -1) (1+\beta + \beta^{2}+...+\beta^{d(t)-1})であるため、\beta^{d(t)}は大雑把に言って今まで使った持ち時間とみなすことができます。

以上より、stockfishの時間配分ルーチン

「手の変化する確率と、消費時間の比率がある一定量に達したら探索を打ち切る」が浅めの読みの近似において最適な戦略であることが証明できます。

 

おまけ.ラグランジュの未定乗数法の例題と持ち時間の導出

ラグランジュの未定乗数法は２で述べたことをより一般的な話に落としこんだものです。wikipediaの記事が解りやすいので読んでみることをオススメします。あまり高度な説明は此処では扱いませんが、例題をひとつ紹介しますので、参考にしてください。

ラグランジュの未定乗数法 - Wikipedia

 

例題：x,yが x^{2} + 2y^{2} = 1を満たすときf(x,y)=x+yの最大値を求めよ。

x,yが束縛条件を満たすのであれば、x+yの最適化は、 F(x,y) = x+y - \lambda (x^{2} + 2y^{2}-1)と等しい。

x+y - \lambda (x^{2} + 2y^{2}-1)をx,yで偏微分すると

\frac{\partial f}{\partial x} = 1-\lambda 2x ...(1)

\frac{\partial f}{\partial y} = 1-\lambda 4y ...(2)

 となる。(1,2)を同時に0にし、かつ、 x^{2} + 2y^{2} = 1を満たすx_{0},y_{0},\lambdaを求めると

x_{0}=\frac{1}{2\lambda} , y_{0}= \frac{1}{4\lambda}。

x_{0}^{2}+2y_{0}^{2} = \frac{3}{8\lambda^{2}}=1

\lambda = \pm \frac{1}{2}\sqrt{\frac{3}{2}}

よって、

x = \pm \sqrt{\frac{2}{3}}

y = \pm \sqrt{\frac{1}{6}}

解が２つ出てるのは、ラグランジュの未定乗数法で得られるのは値の極であるため、最小値も同時に得られてしまうからです。今回の問題（最大値）は２つ出てきた解のうちの、x = \sqrt{\frac{2}{3}}y =  \sqrt{\frac{1}{6}}の方となります。

 

おまけ２．将棋の持ち時間への適用

将棋の持ち時間についても同様にF(T(x))の代わりに

G(T(x)) =  R(1,T(1))+R(2,T(2))... - \lambda (T(1)+T(2)+...-H)

の最適化を考えます。

\frac{\partial G(T(x))}{\partial T(n)} = \frac{\partial R(1,T(n))}{\partial T(n)}- \lambda

から、\lambdaが何であるかはHに依存するものの、兎にも角にも\frac{\partial R(x,t)}{\partial t}が一定でなければならないことが解ります。

コンピュータ将棋流の時間攻めと電王戦の攻防

何を隠そう、私が最初に覚えた将棋の小技は時間攻めです。素人将棋では時間なんてそもそもカウントしないことも多いですが、プロ棋士（に限らずある程度将棋を指す人）の対局では持ち時間を意識した水面下の戦いは切っても切れない存在です。

終盤の圧倒的な読みの精度と、残り時間が何秒だろうと決して慌てない鉄壁の精神を持つコンピュータ同士の戦いでは時間攻めは意識されることのほうが少ないものかもしれません。が、将棋電王トーナメント本戦の計４時間という長丁場は、この手の戦に慣れていない開発者の精神には十分すぎるダメージを与えてくれました。それこそ今でも稀に夢に出るぐらい。

さて、コンピュータが慌てふためいてくれない関係で、コンピュータ将棋の時間制御は長らく似たようなルーチン（stockfishの受け売り）が使われ続けているのですが、果たしてこれは正しいのでしょうか。

結論から言うと、stockfishの時間制御は数学的にみてもかなり精密に作られていることが解りました。同時に、コンピュータと人間の時間の捉え方の違いや、それがもたらすドラマの存在にも気付くことができました。本稿ではコンピュータがいかに時間を捉えているかと、人間との違いについて、解説していきます。

 

・stockfishベースの時間制御

stockfishはざっくり言って以下のような思考で持ち時間を制御しています。

１．終局までの１手の平均時間を見積もる（20手目で残り時間50分、120手目ぐらいで決着がつくと予想するなら１手1分と言った要領）

２．最大思考時間を決める（近似的には平均時間の5-7倍）

３．局面を読み進める

４．同時に、読みを１手深くする毎に最適手が変化する確率を見積もる

５．消費時間（にある一定の数をかけたもの）が４で求めた確率を上回ったら読みを中断する

この中で特に優れているのが５の部分です。消費時間を増やす毎に、読みを打ち切る条件つけを厳しくすることがミソです。将棋（やチェス）は深く読めば読むほど、手が固まりやすくなると同時に読むべき局面が増えてしまうため、過去の自分の読みを信じて、煮詰まったと思ったら普段ならもう少し読む局面も放置して先に進めようという発想です。

なお、細かい導出はどう頑張っても簡単に書けなかった（もともと理系大学生が3-4年ぐらいで習うことで、その半数が首を傾げたまま卒業するような内容）ので、本稿末尾のオマケとします。

 

・コンピュータ流の時間攻めと人間の逆襲

 深く読めば読むほど、昔の自分を信じて読みを打ち切りやすくなるという仕様上、コンピュータの消費時間は人間に比べると平坦になりがちです。特に持ち時間が長いとその傾向は顕著となります。例えば、昨年末の竜王戦第７局では渡辺竜王、丸山九段の消費時間和は３０手目までが１時間３０分、４０手目までで４時間３０分、５０手目までで６時間となっています。

これに対し、電王戦で山崎八段と戦ったponanzaは３０手目で１時間２６分、６０手目で３時間１０分、９０手目で４時間３０分と極めて平坦な時間の使い方をしています（まあ、ponanzaがstockfishベースの時間管理をしてる保証はないし、手によっては消費時間がばらつきはしてるのですが）。

人間はコンピュータに比べると頭の回転速度にゆらぎが多く、また、最善手が変わった回数を数えるなどの行為を苦手とはしていますが、コンピュータ流の指し方として、試して見る価値はあると思います。人間の感情的な部分さえ無視できれば、stockfishの戦略は人間でも成り立つはずです。

 

しかし一方で、コンピュータが人間に明確に劣る点もあります。それは、試合の終わる速度を読む力です。相掛かりや振り飛車など指し手の可逆性が高く（玉から上がるか金から上がるかetc）、同時に長期戦になりやすい戦形は、本来序盤は時間を節約していくべきなのですが、コンピュータは往々にして、序盤の玉を囲う順序を考えたりして時間を浪費しがちです。統計的なデータは揃えていませんが、この記事を書いてる横でもQhapaqが相掛かりの中盤戦で時間を切らし始め、１秒将棋による逆転合戦をエンジョイしてる真っ最中です。かといって、序盤はそんなに考えるなよと下手に時間を調整すると、横歩や角換わりの急戦によく考えずに突っ込んで壮大な爆死を遂げたりもします。

コンピュータの時間管理が影で仕事をした例としては、電王戦finalでのapery vs 斎藤六段の試合も挙げられます。aperyは序盤から時間を割と均一に使うというコンピュータ的にとても正しい戦略をとっていたのですが、急戦になってしまい早くから形勢を損ねることになってしまいました。コンピュータ的には「相手がこの局面で使える時間は俺と似たようなものだし、俺は悪くないと思ってるのだから大丈夫」と目論んでいたのですが、ほんの数手、物凄く深く読むべき瞬間をコンピュータは理解できなかったのです。斎藤六段はそこを理解し勝利をモノにしたのは人間の為す芸術と言えると思います。

 

・おまけ：汎関数微分を用いた最適な持ち時間配分の導出

持ち時間が一定の将棋では、ある手を長く考えると、別の手は早く指す必要があります。限られた時間の中で勝率を最適化するには、局面ごとにどれぐらい考えるかを決めねばなりません。

 時間を無駄にしている ＝ 本来読むべき局面でない局面に時間を使っている ＝ 無駄に読んだ局面と読むべき局面とでは同じ時間を費やしても得られる利得が後者のほうが大きい という思考実験をすれば、「無駄のない時間配分では、どの局面についても時間対効果が同じになっているのだろう」という予想を立てることができます。

汎関数微分をつかうと上記予想が正しいことが証明できます。数式で言えば、Y手目の局面について、X秒考えて正しい手がさせる確率がF(X,Y)であるとしたとき、正しい手がさせる確率の期待値を最大化させるにはF(X,Y)をXで微分した値がYによらず一定になるようにすればよいわけです。

 さて、前回の記事の検証によると、コンピュータが正しい手が指せる確率は、深さが浅い時は手の深さに線形になっているようです。N手読むのにかかる時間が2のN乗に比例する（最近のソフトは激しい枝狩で精々２手ぐらいしか枝を分けてないとどっかで読んだ）とすれば、時間を投資することで得られる利得は近似的には今まで消費した時間に反比例する（2^N-1 = 1+2+...2^N-1）ことになります。

これに気づいた時、私は「やった、これはtimemanの革命やで」と喜び勇んだわけですが、実際にstockfish（やそれを元にしたソフト）のソースコードを見ると、読みを打ち切る条件が手が変わる確率が消費時間の定数倍を下回った時になっていたという。

レートの持ち時間依存性から考える技巧の敗因と探索部最適化

前の記事でも述べたとおり、探索部の最適化を阻む最大の壁は最適な探索パラメータ（アルゴリズム）が持ち時間に依存することです。本番の長い持ち時間(WCSCでは1試合1時間程度、電王トーナメントでは4時間)で探索パラメタを最適化するのは尋常じゃない計算リソースが必要となるため、探索部の最適化は十分な計算リソースを持った強豪ソフトがほぼ独占的な強さを持っているのが現状です。この差を埋めるには、短い持ち時間でも探索部を最適化できる方法を探す必要があるのですが、其のためには、探索部の持ち時間依存性の出処を探る必要があります。

というのも、第四回電王トーナメントでの技巧は、風のうわさに0.1秒から1秒程度の対局で探索部を最適化してたと聞いていますが、これが本当なら、技巧がトーナメント本番で頓死を重ねたのは、技巧の不運だけではなく、最適化の手法にも問題があったのではないかと思っているからです。

そこで、本稿ではweb上に存在するレートの持ち時間依存性のデータを元に、できるだけ少ないリソースで探索部を最適化する方法について幾つかの予想を垂れ流してみます。

注：あくまで私の予想です。正しいという保証はありません。

１．既存の実験データ
やねうらお氏の実験結果

yaneuraou.yaneu.com

１手1秒-8秒ぐらいの間での実験結果をまとめています。

 

uuunuuun氏の実験結果

http://www.uuunuuun.com/single-post/2016/07/09/%E8%AA%AD%E3%81%BF%E3%81%AE%E6%B7%B1%E3%81%95%E3%82%92%E5%88%B6%E9%99%90%E3%81%97%E3%81%9F%E6%8A%80%E5%B7%A7%E3%81%AE%E3%83%AC%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0


探索深さを変えながら技巧を戦わせることで、技巧の勝率のdepth依存性を求めています。depthは厳密には持ち時間とは異なるパラメタなのですが、雑に言えば探索時間はdepthに対して指数関数的な形を持つため、depth差を持ち時間差に焼き直して考えることが可能です。

やねうらお氏のコメント
やねうら王のコメントに

// 終盤で大きく持ち時間を変えると、勝率が5割に寄ってしまうのでそれには注意。

という書き込みがあります（source/extra/timeman.cpp）。


２．なぜ、depthに対して線形にレートが変わるのか
実験データ１，２によると、レート差は持ち時間の比率（≒探索深さ）で近似的に表せるようです。持ち時間２倍ならパワーは２倍と言われると何となく納得してしまいそうですが、実際何が起こっているのでしょうか。

持ち時間を長くすると強くなるということは、幾つかの局面の評価が持ち時間に依存して異なり、また、長い持ち時間のほうが正確な予言ができているということを意味します。

中終盤の勝負所では、正しい手を選べば勝てる一方、間違った手を選べば負けるという少々強引な仮定をしてみましょう。このとき、両者の勝率差は、各々が其の局面を正しく評価できる確率の差となります。言い換えれば、小さいdepthにおいては、局面を正確に読める確率はdepthに線形依存しているというわけです。
加えて、やねうらお氏のコメントから、終盤の詰みが絡んだ局面のほうが、depthに対して急な傾きをしていることが予想されます。

また、depthが増えると正確さの上昇率は鈍ることが予想されます。というか、最後まで線形でい続けると、どこかで読みが正しい確率が１になってしまうので、鈍らざるを得ないはずです。以上をまとめると下のような感じになります。

f:id:qhapaq:20170116002610p:plain


３．探索部を最適化するコツ
探索部の最適化は総じて深さと正確さの損益分岐点を求める問に帰着します。持ち時間が一定とすれば、深く読めるようになるほど、局面を読み落とすリスクが高まるため、両者が釣り合う点を探す必要があるのです。

グラフを見直すと、短い持ち時間での探索最適化でありがちなミスは、depthを上げることによる正確さの上昇を過剰に見積もってしまう（特に終盤）ことであると予想されます。こうした傾向は第四回電王トーナメントでの技巧の頓死や真やねうら王の探索パラメタのstockfishとの比較(+vs魔女の持ち時間依存性についての考察)とも一応合致しています。

以上を踏まえると、短い持ち時間で探索部を最適化する際には、以下のような手が有効であること予想されます。

・複数の持ち時間（３点以上）で勝率を測定し、持ち時間が長くなるとともに勝率が落ちている場合は最適化をやり直す

・終盤は最適化をoffにして比較する

・評価値解析ツールQhashimaを使って、勝率の上昇において、逆転勝利の数がどの程度あるかを確かめる

・評価値が一定値になったら自動投了するようにする（終盤の過大評価による逆転を防ぐため）


４．おまけ：Qhapaqの追加検証
探索部の最適化については、まだ深くやっていない＋詳細に書くと大会で勝てなくなるので書けませんが、depthの重要さの局面依存性を確かめるべく、全ての手を1秒で指すソフトに対し、30-60手目だけは1秒で指すソフト、60-90手目だけは2秒で指すソフトを戦わせ、各々の勝率を測定してみました。

30-60　370-42-295
60-90　380-50-270

双方において勝率が上がる一方で、1秒程度の持ち時間では、まだまだ終盤のウエイトが大きいことがわかります。（0.5秒でやると、もっと差が開くのですが、ハードの事情でデータが回収できないのです orz）

ライブラリとして公開しているQhapaqのソフト/ツール一覧

2017.1.22更新

以下のツールをライブラリとして公開します。

現状のQhapaqのツールは定跡や棋譜解析ソフトであり、定義上、ライブラリ登録をしなくても使えるはずなのですが、念の為ここに公開しておきます。

ライブラリ申請の状況などについても此方で公開します。

 

評価値、勝率解析ソフト「Qhashima」

https://github.com/qhapaq-49/Qhashima

 

量子焼きなましを用いた定跡生成ツール群「量子ガシャ、やねうら王Quaga」

https://1drv.ms/u/s!Ag5CrRBmeQHym19Ql_bDEC7fJB19

 

量子焼きなましを用いて作った定跡

https://1drv.ms/u/s!Ag5CrRBmeQHym1eN0ayk5kjCjBLA　（戦型自由）

https://1drv.ms/u/s!Ag5CrRBmeQHym2NaMKyetTfVAaJX　（四間飛車）

https://1drv.ms/u/s!Ag5CrRBmeQHym1zqL3m1rtKNKQNv　（一手損）

 

【WCSC２７での利用について】

WCSC運営より以下のような回答をいただきました（以下は頂いた返信の抜粋です）。

大会を運営してくださってる方々に、この場を借りてお礼申し上げます。

 

---quote---

現在いただいているものは、ルール上
ライブラリ登録がなくとも使用可能ですが、一方で、ライブラリ規程では
ライブラリは「将棋の指し手生成に関わるプログラム」として、
「開発部」に限定していませんので、ライブラリとして受け付けます。

　CSAサイトでの公開にあたっては
「2017年1月15日時点の内容は、開発部を含まないため、
参加者は、本ライブラリを使用したことを明記する必要はありません」
として公開したいと思います。

---quote---

Stockfishベース探索の終盤力が弱いかもしれない件について

あけましておめでとうございます。電王よりリア充になりたいです。あとnatureに論文出したいです。WCSCでは新人賞と独創性をガチで狙いに行ってます。カステラの法則信者なので書いておきます。今年もよろしくおねがいします。

雑巾絞りによって評価関数学習が大分標準化された一方で、枝狩りの最適化は手法が未だに群雄割拠の状態です。silent majorityが大樹の枝に７割勝っていたような大進歩が未だに残されているかもしれません。最近はstockfish（チェスの強いソフト）を流用するのがブームのようですが、実はstockfish、将棋のそのまま流用すると、終盤が強くない可能性があるのです。

 

１．幾つかの実験結果

stockfishの終盤力に問題がある説の根拠は以下の４つの実験結果です。

 

一、やねうら王Mid vs 真やねうら王 in 0.2秒対局ではMidが勝率53％程度で勝ち越す（10000局程度）

二、やねうら王Mid vs 浮かむ瀬 in 0.2秒対局では浮かむ瀬が勝率55-60％程度で勝ち越す（定跡が異なるので厳密なデータにならない）

三、１秒対局になると真やねうら王と浮かむ瀬の強さはどっこいになるらしい

参考：uuunuuun氏のブログでの考察

四、終盤のfutility margin（≒読んだ深さや手の序列（高い駒を取られるような手は序列が下になる）に応じて枝狩りされやすさを調整する）はあまりやらないほうが強そう

参考：http://www.computer-shogi.org/wcsc26/appeal/Qhapaq/qhaq-2016-may2.pdf （Qhapaqの技術文書 from WCSC26）

 

２．この実験結果が意味することは何か

一、持ち時間によって最適なパラメタが変わる

実験 一、二、三の結果を比べると、最適な枝狩りパラメタは持ち時間によって変わりうることが示唆されています。どうやら、stockfishのパラメタをそのまま使うと、短い持ち時間に過度に最適化されやすい傾向にあるようです。

二、stockfishは枝を狩りすぎている？

真やねうら王の 2016-late-param_body.h を見ると、調整前後でLMR周り（とても雑に言えばfutilityの兄弟）の枝狩の頻度が減らされており、stockfishのデフォルト設定では枝を狩りすぎであることが示唆されています。これはQhapaqの実験四とも一貫性が取れています。

 

３．stockfishは終盤に枝を狩りすぎている（私の見解）

チェスと将棋の特に終盤での特に大きな違いはゲーム中に存在する駒の数です。将棋では大駒を切って敵陣に穴を開け、相手の守り駒を取りながら駒損を解消するといった攻めが成り立ちますが、チェスでは成り立ちにくいです。故に、大駒を切るような攻めは早期に枝狩りすることが良い方針となります。また、「駒の数が減っていれば引き分けだろう」という判断が概ね正しいため、枝を狩りまくっても形勢を読み誤る確率が将棋に比べ少ないと言えます。

大駒を切るような攻めは長い手順になりがちであるため、持ち時間が短く手順を読み切れないうちは読むだけ無駄な手とみなされてしまうため、枝狩りしたほうがいい（Midが0.2秒将棋では真やねより強い）のですが、手順を最後まで読みきれる持ち時間があるならその限りではないというわけです。

 

４．より強い探索ルーチンを作るためにやってみたいこと

最低限、局面進行度に合わせて枝狩りを変えるべきだと思います。長い手順の攻めを警戒する必要があるのは玉がピンチであるときであると考えれば、進行度はKKPあたりを使うのが良いでしょう。

加えて、枝狩りパラメタの最適化作業そのものを高速化することを考えたほうが良いと考えています。パラメタの持ち時間依存性がある以上、長い持ち時間で検証をするべきである一方、長い持ち時間での勝率ベースの最適化は物凄く計算コストがかかるからです。

量子ガシャは当初、枝狩りパラメタの最適化のために生み出した手法だったのですが、Blunderが昔やっていたような方法（各々の局面に対し、枝狩りを少なくして、深く読んだものを教師として枝狩りを最適化する）を検討するべきかもしれません。数十個のパラメタを最適化するのであれば、1000局面ぐらいあれば十分である見込みは高いですし。

 

# seleneの開発者がブログでponanzaの探索部の強さについて指摘していましたが、嘗てBlunderがやっていた研究が枝狩り最適化に活かされているのかもしれません。

 

おまけ．まふ氏もstockfishが終盤弱いと思っているらしい

河童定跡の最大のライバル（？）である、まふ定跡の作者のまふ氏もstockfishの終盤に疑問を感じていらっしゃるようです。原文はまふ定跡のreadmeをご参照ください。

/* ---引用---

私はStockfish系が致命的に将棋と合っていない箇所が終盤に向かうプロセスだと思います。
チェスは駒がどんどん減って行き、終盤は一定の駒数から完全解析されています。
ここまで行かなくとも、ある程度減った段階でほぼパターン化されエンドゲームとなっています。
floodgateで浮かむ瀬同士やＳＭの対局を見ると、一定の局面からはまったく同じ局面進行が続くことが多いです。
これはチェスが駒がどんどん減り、自分の勝ちパターンに近づけて行くプログラムだからだと思われます。
将棋はまったく逆で、終盤に行くほど持ち駒が増え局面が激化します。
上記が主な原因ですが、Stockfish系に定跡を搭載しても同じパターンで勝ち負けが偏るので、Stockfish系の同ソフト対局では上手くなったかどうか分かりにくいからです。

---引用---*/

 

/* ---引用---

■読み太githubの気になること.txtへの私なりの回答
 
＞読み太にやねうら王の評価関数を乗せるとフリーソフト最強らしいのだが、floodgateに放流しても妙に弱い。
浮かむ瀬より強くなっているように見えたのは持ち時間1秒～3秒の短時間の将棋だけ……かも。調べていないのでわからない。 自己対戦の持ち時間は3秒で500~1000局やってきたが10秒くらいでやるべきだろうか。
 
Readme 5(技巧版ver8)にも書きましたが、 私はStockfish系が致命的に将棋と合っていない箇所が終盤に向かうプロセスだと思います。 チェスは駒がどんどん減って行き、終盤は一定の駒数から完全解析されています。
ここまで行かなくとも、ある程度減った段階でほぼパターン化されエンドゲームとなっています。
floodgateで浮かむ瀬同士やＳＭの対局を見ると、一定の局面からはまったく同じ局面進行が続くことが多いです。 これはチェスが駒がどんどん減り、自分の勝ちパターンに近づけて行くプログラムだからだと思われます。
将棋はまったく逆で、終盤に行くほど持ち駒が増え局面が激化します。 上記が主な原因ですが、Stockfish系に定跡を搭載しても同じパターンで勝ち負けが偏るので、Stockfish系の同ソフト対局では上手くなったかどうか分かりにくいです。
つまり、Stockfish系の影響が強いソフトでは、定跡で勝率がかなり偏ります。

---引用---*/