コンピュータ将棋における定跡とメタゲーム

1:00 第一版リリース

本稿はコンピュータ将棋アドベントカレンダー 12/11の記事として投稿されたものです。

www.adventar.org

定跡合戦は大会ドラマ上、切っても切れない存在であると同時に、コンピュータ将棋における数少ないメタゲーム要素の一つでもあります。本稿では第四回電王トーナメントまでの定跡の変遷とその思想、更に、今後流行るかもしれない定跡理論について解説いたします。

shogi1.com

棋譜解析という名のチキンレース

コンピュータ将棋開発者の間でも、序盤をどのように指すのが一番良いのかは度々議論されてきました。第四回電王トーナメント前までは定跡は人間や強いソフトの棋譜を解析(変な序盤になってないか、ソフトに読ませ、評価値が悪い棋譜を削る)することで、作られていましたが、読みが浅いと深く読んだ定跡を搭載した相手に苦しく、深く読ませると定跡に搭載できる棋譜が減り、自分だけ定跡から外れた状態になりやすいというジレンマが存在していました。

また、評価関数が変化するたびに定跡もそれに合わせたものにしたいと考えると、何度も棋譜を解析するのは開発効率が悪く、いつ定跡を考えるかというチキンレースにも開発者は苦しむはめになりました。

チキンレースから降りるという発想】

この状態を打破したのが、WCSC26後にリリースされたやねうら大定跡です。やねうら大定跡は点数が良い棋譜を使うのではなく、棋譜の局面でコンピュータが深く考えて出した最善手(またはそれに点数が近い手)を指す方式となっていました。

棋譜の手を直接使わなくなったおかげで、異なるソフトが同じ手を定跡として搭載している確率は飛躍的に減少し、従来の定跡に比べ、かなり早い段階で双方定跡から外れた状態を実現できるようになりました。定跡から外れるような変な手(初手58金とか)は必ずしも良い手ではありませんでしたが、ponanzaでの検証でも大きなデメリットがないことは示唆されていたし、加えて、当時のソフトはボナメソベース(6月技巧もこれ)のものが多く、力戦系を苦手とするものが多かったので、大定跡は多くの定跡に対して良い勝率を得ることができました。

 

各手の勝率:Ponanza調べ 76歩51.39% 26歩51.23% 78金51.07% 68玉49.95% 38銀49.93% 58玉49.86% 96歩49.77% 36歩49.69% 48銀49.6%

 

【時間攻めの武器としての定跡】

大定跡の活躍は、定跡は有利な形を作るためのものではなく、時間攻めの要素として活用するという発想をもたらしてくれました。

例えば、将棋が100手で決着がつくとすれば、最初の10手を自分だけ定跡で0.1秒指しできると持ち時間が1割増えることに相当します。これはレートに換算して20強の価値があり、ponanza解析による初手で変な手を指すデメリットを打ち消すには十分です。

この思想を最大限活用したのが第4回電王トーナメントの真やねうら定跡です。

 

yaneuraou.yaneu.com

大会二日目では真やねうら定跡を搭載した†白美神†が襲いかかってきたため、Qhapaqは大変なピンチを迎えました。しかし、幸いにも(?)前日に新しく実装した時間攻めルーチンが逆に†白美神†を追い詰めることに成功しました。

 

【定跡不要論】

Qhapaqが大会1日目の深夜に実装した機能。それは、「序盤は16手は1手15秒しか読まない」というものでした。序盤は深く読んでも変な手を指しても大勢に影響は出ないのなら、定跡なんて入れず、短い時間で指すようにすれば、評価関数と定跡の不整合などの問題も起こらないという発想です。

※:偉そうに解説してますが、浮かむ瀬が似たようなことをしていたので便乗しただけです

この戦略は少なくとも明確な悪手は指さなかった(評価値は双方100程度で先手良しのまま16手目まで抜けた)し、定跡チキンレースから完全に脱却できるため、定跡の時代は終わったなという気持ちにその時はなりました...

 

【スナイパーとしての定跡】

しかし最近、この定跡不要論を揺るがす新たな定跡が生まれました。そう、まふ定跡です。

http://www.uuunuuun.com/single-post/2016/11/06/%E6%8A%80%E5%B7%A7%E6%96%B0%E5%AE%9A%E8%B7%A1

この定跡は、6月技巧に搭載することで、そのレートを100前後上昇させることに成功しています。加えて、浮かむ瀬などに搭載することで定跡offの状態にも勝ち越すことができるとのことです。

まふ定跡はアマチュアの棋譜などを製作者が人力で解析したものを用いており、その制作過程について細かく評価をすることは難しいですが、定跡を抜けた直後の点数のヒストグラムをとると確かに技巧側に良い局面の割合が増えています。

まふ定跡の特に凄い点は持ち時間や定跡を使うエンジンによらず、レート上昇を成し遂げていることです。これは、まふ定跡が「序盤変な手を指さないようするもの」ではなく「相手が仮にミスをしたら咎めるもの」という毛色を持っているからと言えましょう。

「変な手を指させないようにする」という方針だと変であるか否かの判断が難しいような状態を的確に扱うことができず、評価部が変わるたびに更新をしなければなりませんが、「明確な悪手を咎める」方針であれば、評価部がよほど強くならない限りは定跡は使いまわせることになります。そして、相手が明確な悪手を指さなかった場合は、定跡に頼らずに普通に挿せばいいのです。

 

【近未来の定跡】

ここ暫くの定跡のメタゲームは、改めてまとめると

「変な手を指させないようにする(棋譜ベース)」→「相手に得をさせないようにする(大定跡)」→「自分が損をしない局面を素早く選ぶ(真定跡)」→「損をさせないだけなら定跡を切ればいい」→「相手の悪い手をリスト化すればよい」

ということができます。私自身は、今後定跡は更にスナイパー的な要素を強く持つようになると考えています。定跡を搭載せずに指させる以上に悪い手を指させない定跡を作るのは難しい(ひとつの形を避けてもまた別の形が出てくる)のに比べ、明確に悪い手をリスト化ほうが定跡の質を上げるには堅実だからです。

2020年ぐらいには、「あ、定跡が出てきたってことは、これQhapaq自分がいいと思ってますよ」ぐらい言われるかもわかりません。

 

上記思想に基づき、まふ定跡の悪手を咎める定跡を作っているところですが、まあ、苦戦してます。前回公開した定跡よりは強いのを作って公開するつもりではありますが。。。

やねうら王系列最強(?)のQhapaq定跡を公開します

まふ氏らによって作られた、技巧新定跡をヒントに独自作成した、

やねうら王のstandard_book.db形式の定跡ファイルです。手元のPCでの実験では真やねうら定跡にも大定跡にも勝ち越しているので、やねうら王で扱える定跡の中では最強かもしれません。

 

以下のページからダウンロードできます。

【重要】onedriveの課金契約がそろそろ切れるので、このファイルは引っ越しする可能性があります。twitter等で拡散する際は、本ブログのページを拡散していただけると幸いです。

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

 

# 技巧の新定跡についての詳細は定跡ファイル本体のreadme、または、uuunuuun氏によるレート検証をご参照ください。

 

【使い方】

standard_book.dbをこのファイルに挿げ替えてください。

narrowbookはonにしてください。

offでも動きますが、恐らく弱くなります(未検証)

 

【特徴】

・standarad_book形式(棋譜にある手をそのまま指す)形式です。

大定跡/真定跡形式に比べ人間的(?)な棋譜を喰わせて作っているため、定跡を長く指してくれる傾向にあり、序盤研究に使いやすい形になっています(希望的観測)。

 

・手元のPCでの0.2秒対局(2コア、一手当たりに読む鏡面は10万程度、最新版Qhapaqバイナリ(非公開、真やねバイナリより少しだけ強い))で

 

vs 定跡なし 1705 - 94 - 1519

vs 大定跡 1713 - 114 - 1503

vs 真定跡 1714 - 105 - 1535

 

と、現在公開されているやねうら王の定跡よりもほんのり強い作りになっています。

 

注:皆様が今後してくださるかもしれない検証と比べるという意味では、浮かむ瀬や真やねうら王バイナリで実験するべきなのかもしれませんが、棋譜を学習データとして再利用したいため、Qhapaqのバイナリでしか測定を行っていません。

 

【WCSC参加者へ】

まふ定跡、やねうら王ライブラリの定跡との対局棋譜をベースに作っているので、私にどれだけ著作権があるかは謎ですが、私個人はWCSC参加者の本ライブラリの仕様を妨げることは致しません。ただ、ご利用の際は、使っている旨をアピール文などに書いていただけると幸いです。仮に私に著作権があるなら、本定跡はGPLライセンスに従います。

 

【作り方】

死に覚え形式で作っています。人間の棋譜+評価関数に乱数を乗せたコンピュータの棋譜から作り上げたstandard_book.db形式の定跡を、各種ソフト(Qhapaqバイナリ+新やねうら王+定跡なし、真やね、大定跡、及び、技巧 with まふ定跡)と戦わせ、勝てた棋譜から新たなstandard_book.dbを作るという作業を繰り返すことでレートを上げています。此処に公開するのは四世代目の定跡です。

雑巾絞りにおけるランダムムーブの意味考

コンピュータ将棋の評価関数を強くする方法に「雑巾絞り」というものがあります。簡単に言えば、1-2手先までしか読まない設定の弱いコンピュータの見解(先手/後手のどちらがいいか、次に何を指すべきか)を3-8手程度まで先を読んだ相対的に強いコンピュータが修正するという手法です。

この手法は第26回コンピュータ将棋選手権から第4回電王トーナメントにかけて、コンピュータ将棋開発者の間で爆発的に流行しました。多くの開発者は雑巾絞りの最適化にまい進してましたし、大会結果そのものも、雑巾を上手く絞れたかに成績が強く依存していたといっても過言ではありません。

雑巾絞り用の教師局面を作成する際に、多くのソフトは極めて短い持ち時間(1局1秒以内に終わる程度)で対局させたものは使わず、何手かに1回、ランダムで手を動かすようにしています。

将棋の手の大半はパスに劣るという格言があるように、ランダムで行われる手の殆どはすさまじく酷い手です。故に、1-2割の確率でランダムムーブを行わせていた浮かむ瀬(apery)の教師データには将棋が強い人から見たらあり得ないほどの悲惨な局面が含まれていたはずです。

この仕様を目の当たりにして、私は「こんな悲惨な局面だらけの学習が効率的なはずがない」とMultiPVの上位3手を評価値の差に応じてランダムに選ぶなどの教師生成を行っていたのですが、どうしてかランダムムーブ入りの教師よりも弱くなってしまいました。教師局面の数は同じなのに、です。

この問題についていろいろ考えた結果以下のような仮説にたどり着きました。

【感覚的な話】

将棋にはいくつもの優れた形があります。矢倉囲いや美濃囲い、棒銀、腰掛銀などが一例です。では、矢倉囲いと美濃囲い、棒銀と腰掛銀はどちらの方がより高得点な形でしょうか。

人間であれば、駒の並びを論理的にとらえて評価したり、他の駒の動きによるとお茶を濁すことができますが、駒の並びに点数をつけ、それらの和を局面の点数としているコンピュータにはそういう芸当はできません。

コンピュータにこうした形の価値を学ばせる簡単な方法、それこそが、形を崩すとどれだけ困るかを確認することなのです。人間と同じ、試しに変な手を指してみて、指導してもらう方が、理由もわからずに定跡本に従って指すよりも強くなるというわけです。

 

で、これをもう少し難しく書くとこういうことになります

【数学的な話】

雑巾絞りにおける学習とは、教師局面の点数を教師として与えられた点数に近づけることに等しいです。学習が収束するとは、教師局面に対する誤差の和に対する各評価パラメタによる微分が0になることを意味します。

しかし、実際の学習ではこれら微分値が綺麗に0になることはありません。教師データそのものに誤差があったり、ミニバッチ法によって評価パラメタは逐次更新されていくからです。結果、評価パラメタは極小点から教師局面に対する誤差の和に対する、各評価パラメタの二回微分の値の逆数程度にぶれることになります。

各評価パラメタの二回微分値は教師局面のなかで当該パラメタが何回出現したかに比例します。教師局面の数が同じなら、各パラメタの二回微分値の和はオーダー的には同じになりますが、MultiPVなどで過度に定跡系に偏った棋譜については、よく出るパラメタ(88の玉と89の桂馬とか)と滅多に出ないパラメタの差が大きくなってしまいます。

結果、評価パラメタのブレの総和(出現回数の逆数の和)は増えてしまうため、適切な値に収束しにくくなります。パラメタの数が有限である以上、あまり無意味な局面は教師に入れたくないのですが、ランダムムーブを入れることでパラメタのブレの巨大化を防ぐ効果が、無意味な局面が入るデメリットを打ち消してくれているようです。