読者です 読者をやめる 読者になる 読者になる

両成将棋における腰掛け馬のススメ

ponanzaに勝ったら300万円貰えるチャレンジが今年も始まったようです。特に目新しいのがオプションとして選べる飛車、角の両方が初手から成っている+先手というハンディキャップでしょう。

この初期局面は先手が既に1000点前後良いことに加え、コンピュータ将棋は平手で他のソフトを殴り倒せるようにチューニングするので、相手の評価ミスを誘えるのではないかと、検証部隊が動き始めているようです。

www.fgfan7.com

fg_fanさんが検証してしまっている以上、私の記事にどれだけの価値があるかは謎ですが、Qhapaqの検証によるとオススメの指し手が少し異なるようなので此処に記録しておきます。

 

Qhapaq側の検証では手が短いこと、手のバリエーションが少ないことを特に重要視しています。具体的には持ち時間を変えたりmultipvによる検証をすることで、ponanzaが未知の手を指してくる可能性を少しでも下げようとしています。故に、最終的には先手が+1500-1700程度になっているとはいえ、もしかしたら人間的な勝ちやすさは伴っていないかも知れません。

 

1.66歩、78馬の構え

初手から66歩、84歩、68馬、85歩、68龍

f:id:qhapaq:20170312010921p:plain

一目珍妙な構えですが、Qhapaq的にはこれがベストのようです。34と23の拠点を睨むことで、相手の玉形に大きな制約をかけると同時に、6筋攻めも見せています。相手は23の地点を金駒で守りたい関係で、相振り飛車にしにくくもなっています。戦型絞るの is 大事。

振り飛車模様にしたので、ここから暫くは玉の整備になります。相手の陣形は23を守らなければならない+此方が振り飛車の関係で32銀からの居角美濃になる見込みが高いです。こちらもとりあえず美濃にしておけば安心でしょう。

 

2.銀と腰掛け馬による速攻

図1から32銀、48玉、86歩、同歩、同飛、88銀、82飛、58金、42玉、38銀、72銀、39玉、31玉、28玉、52金、76歩、64歩、77銀、63銀、75歩、74歩、同歩、34歩、76銀、74銀、56馬、75歩、74銀、89飛成、75銀

f:id:qhapaq:20170312011018p:plain

玉を整備したら(整備しなくてもいいのでしょうけど、玉は固めておいたほうが人間的には安心)銀を76に繰り出し馬を56に据えて6筋を攻撃します。この時点でQhapaq的には1600点程度の先手有利。初期陣形と違って駒がさばけていて玉が硬いので、人間的にも割と勝ちやすい局面だと思います。

 

3.7筋に龍を振り直すパターン

図1から32銀、48玉、86歩、同歩、同飛、88銀、82飛、58金、42玉、38銀、72銀、76歩、64歩、77銀、63銀、75歩、34歩、39玉、74歩、同歩、72金、76銀、74銀、77龍、88歩打、56馬、73歩打、75歩打、65銀、同歩、89歩成、67龍、65歩、同龍、51金、45馬

f:id:qhapaq:20170312011117p:plain

相手が早めに34歩から此方を牽制してきた場合、34馬として歩得することも可能ですが、相手の牽制を無視して攻めるのが早いようです。

攻め駒の並べ方は先ほどと同じで、76歩、77銀、75歩、76銀、56馬から攻めを組み立てていきます。腰掛け馬によって、6筋の突破を見せると同時に、相手の74歩を強く牽制しています。7筋の駒を牽制するだけなら55や46に馬を置く手も考えられますが、相手から角交換を見せる手があるせいか、短い持ち時間でやると逆転されてしまうことがあるようです。

 

4.まとめ

Qhapaqで検証する限りでは、66歩、78馬、68龍から美濃囲いを作り、88銀、76歩、77銀、75歩、56馬の形で攻めるのが手の変化が少なくて良いようです。この他の変化としては、77銀から86歩打、56馬、88龍と向かい飛車にする手も有効なようです。

飛車同士の睨み合い自体は角交換四間飛車でもある形ですが、56の馬が相手の78筋を牽制しているため、飛車同士の睨み合いを有利に進めるという寸法です。

ただ、この戦型は相手の82の桂馬の活用を許してしまいがちであり、手の変化が豊富になりやすいので人間がponanzaを倒す上ではあまりよろしくないと思います。

 

使って負けても責任は取れませんが、戦型の一つとして覚えておいていただけると良いかと思います。

Futility marginがdepthの線形でいい理由

定跡研究の知見をまとめつつある裏で、WCSCに備えて探索部の改造にも手を出しています。

評価関数は億単位の局面を使って億単位のパラメタを最適化するという人間の直感に反するものである一方、探索部は「まずは取る手から考える」とか「この局面は仮に盛り返しても、今考えるベストな展開に及ばないだろうから探索を打ち切る」とか「ある程度考えたらそれ以上考えても仕方ないので指して相手の手を見てから考えよう」とか、割と人間的にも納得の行く理念で作られています。

しかし、その理念をコンピュータの思考に焼きなおすには、幾分かの数理的な小技が必要となります。昨今のコンピュータ将棋の探索部はstockfishから引っ張ってきたルーチンが多く、よもすれば、式の意味を解らずに枝狩りをしている人、いるのではないでしょうか?

今回はstockfishの数あるルーチンの中からfutility marginについて考察していきます。

 

1.futility margin/pruningってなんぞ

futility pruningはn手以内に今考えてる最善手のスコアを追い抜けそうにない手を枝狩りする探索ルーチンの一つです。例えば、横歩取りで横歩を取る手の暫定評価値が+100だったとします。

暫定評価値は所詮は暫定であるので、他の手(例えば飛車を引いて相掛かり風味にするなど)に抜かれる可能性があります。故に、他の手を今の点数が低いからと枝狩りするわけには行きません。しかし、見込みのない手(飛車をただで捨てる手とか)はさっさと枝狩りしてしまったほうが、有力な手に費やせる時間が増えて、レートが上昇します。

28飛車は読むとして。96歩や98香はどうだろう。どこから枝狩りすればよいのだろう。こうした判断をするときに使うのが、futility marginです。

具体的には、其の局面の浅く読んだ時の点数(score)が

bestscore - score > margin * depth *const

となった時に枝狩りを発動させます。depthは残り探索深さで、仮に読むとしたらdepth手先ぐらいまで読むということを意味します。

marginがdepthに比例するのは、将棋の局面は深く読めば読むほど評価値が変わりうるからなのですが、さて此処で問題。なぜdepthに比例なのでしょうか。やねうら王も読み太も線形にしていますが本当にこの形でいいのでしょうか?

 

2.点数の変化度はdepthではなくdepthのルートに比例する

まず、depthが1の時について考えます。1手深く読むことで評価値はずれますが、概ね(99%ぐらい?)X点以下に収まるとしましょう。

depthが2の時はどうでしょう。2手先の手の点数のブレは「1手先の点数のブレ」+「1手先の局面から見た1手先の点数のブレ」で表されます。futility margin的にはブレは概ね2X点以下に収まるとのことですが、実際に2Xが出る確率はもっと低いはずです。というのも、2手連続でめったに出ないX点を出さねばならないからです。1手深く読むことでX点点数がずれる確率が1%だとすれば、2手深く読むことで2X点点数がずれる確率は0.01%です。

細かい導出はおまけに任せますが、stockfishさん、深く読むときにビビり過ぎなのではないでしょうか?

 

3.枝狩りする局面の数を考えると釣り合う

ある局面からd手離れた局面の評価値がxずれる確率は

 e^{-x^{2}/d}

で表せるとしましょう(実際は規格化係数などがいるけど)。このとき、点数の変化値がαd以下になる確率=futility pruningして問題ない確率は

 \int_{0}^{\alpha d} e^{-x^{2}/d} dx = 1 - Z e^{-\alpha^{2} d}

で表されます(αはfutility marginの係数とする、Zはdに依存しない定数)。ガウス関数積分ガウス積分の公式 [物理のかぎしっぽ]あたりを参照してください。

しかし、d手読む予定だった局面を読むのをやめるということは、 A^{d}局面分の読みを省略するということを意味します(Aは各々局面の合法手のようなもの)。

即ち、futility pruningに失敗しないためには、上述の賭けに A^{d}回連続で勝つ必要があります。

 (1 - Z e^{-\alpha^{2} d})^{A^{d}}に対して1次のテイラー展開を用いると

適切なαを選ぶことでdによらず上記の式が一定になることが確認できます。

 

 

 

おまけ.点数の変化度はdepthではなくdepthのルートに比例する(小難しい補足)

depth手先まで読むということは

 1.1手深く読むと、前の局面に比べて駒が一つ動きます(そりゃそうだ)

 2.駒が動くと、評価値は動いた駒の分だけ変化します

 3.深く読むと2のプロセスを何回も重ねあわせることになります

ということを意味します。駒を一つ動かすことによって生じる評価値の差分の分布はKPPTのパラメタで特徴つけられた関数になります。深く読むことでこの分布関数に従って、何度も評価値が変調されていきます。

実は、分布関数の形が何であろうと(例外はあるけど)、十分な数depthを重ねると、最終的な分布はガウス関数に収束していきます。中心極限定理と呼ばれる定理であり、大学初頭の統計などで出てきます。中心極限定理を用いれば半値幅はdepthのルートに比例すると予想できます。

振り飛車最強決定戦(本戦) in Qhapaq

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

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

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

 

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

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

 

f:id:qhapaq:20170216232945p:plain

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

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

 

f:id:qhapaq:20170216233014p:plain

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

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

 

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

 

1.初期局面から10手以上進んだ定跡局面を使う

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

 

四間飛車穴熊

f:id:qhapaq:20170216233128p:plain

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

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

 

藤井システム

f:id:qhapaq:20170216232402p:plain

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

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

 

2.藤井システム棋譜の評価値

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

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

 

3.居飛車藤井システム対策の検証

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

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

f:id:qhapaq:20170217011912p:plain

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

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

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

・54に銀か金を配置する

という点です。

 

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

藤井システムを見せることで66銀型の穴熊を妨害する(57の銀を腐りやすくする)

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

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

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

 

4.結局なんで勝てるの?

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

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

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

 

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

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

 

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

 

6.次回予告

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

 

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

 

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

振り飛車最強決定戦(前哨戦) in Qhapaq

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

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

 

1.選手入場

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

ノーマル四間飛車

f:id:qhapaq:20170208212547p:plain

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

 

ゴキゲン中飛車

f:id:qhapaq:20170208214320p:plain

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

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

 

二手目32飛

f:id:qhapaq:20170208214354p:plain

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

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

 

角交換四間飛車

f:id:qhapaq:20170208214722p:plain

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

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

 

2.対戦結果

 ノーマル四間飛車:40.5%

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

ゴキゲン中飛車:40.5%

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

 

2手目32飛:37%

角交換四間飛車:37.5%

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

 

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

 

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

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

 

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

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

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

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

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

 

4.次回予告

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

 

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

 

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

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

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

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

 

1.問題条件の定式化

 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))が所謂汎関数というやつです。

 

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

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

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

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

 

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

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

・正しい手をさせる確率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の時間配分ルーチン

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

 

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

ラグランジュの未定乗数法は2で述べたことをより一般的な話に落としこんだものです。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}}

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

 

おまけ2.将棋の持ち時間への適用

将棋の持ち時間についても同様に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}が一定でなければならないことが解ります。

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

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

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

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

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

 

・stockfishベースの時間制御

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

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

2.最大思考時間を決める(近似的には平均時間の5-7倍)

3.局面を読み進める

4.同時に、読みを1手深くする毎に最適手が変化する確率を見積もる

5.消費時間(にある一定の数をかけたもの)が4で求めた確率を上回ったら読みを中断する

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

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

 

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

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

これに対し、電王戦で山崎八段と戦ったponanzaは30手目で1時間26分、60手目で3時間10分、90手目で4時間30分と極めて平坦な時間の使い方をしています(まあ、ponanzaがstockfishベースの時間管理をしてる保証はないし、手によっては消費時間がばらつきはしてるのですが)。

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

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

yaneuraou.yaneu.com

1手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)。


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

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

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

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

f:id:qhapaq:20170116002610p:plain


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

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

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

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

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

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

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


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

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

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