角換りは終わったのかについて1万文字程度で

投稿日時: 投稿者:

先月のゴールデンウィークに行われた第33回世界コンピュータ将棋選手権(WCSC33)で弊やねうら王チームが準優勝したあと(この準優勝は本当に準優勝であって、ビールにおつまみで乾杯するという意味ではない)、角換りという戦型について以下のツイートをした。

https://twitter.com/yaneuraou/status/1655418988980211712

この前者のツイートにはインプレッションが172万もあり、Yahooニュースや朝日新聞デジタルなど多くのメディアで取り上げられた。

AIで角換わりが終わった？　藤井聡太竜王「こちらの立場としては」(朝日新聞デジタル)
https://digital.asahi.com/articles/ASR5005B4R5YUCVL046.html

私のツイートは、「1886局面の指し手を覚えるだけで先手側は公開されてる水匠（探索局面数は1億までの任意）に対して評価値+300に出来ることが証明された。」であり、本当にこのままの意味なのだが、このままの意味以上に拡大解釈する人がたくさんいるようなので、一つ一つ前提条件を説明しながら、いま将棋AIの世界で何が起こっているのかを詳細に書こうというのが本記事の狙いである。

上のツイートの反響がすごくて、何らか説明責任を果たさなければいけないという義務感からこの記事を書き始めたわけだが、非常に長文になりそうで、書くのがすでにだるい。読むのもだるいかも知れないが、書くのはもっとだるいのである。まあ、興味のあるところだけ適宜拾い読みしていただければそれで構わない。こちらも軽い気持ちでだらだら1万文字程度書く。

2022年までの将棋AI界の定跡生成アルゴリズム

WCSC32のやねうら王のPR文書にだいたいの歴史が書いてある。年代など細かいところは間違いがあるかも知れないが、大雑把に説明するにはこれで十分ではないかと思う。2022年までの歴史が5ページ、テラショック定跡手法と言う提案手法のアルゴリズムの説明が7ページで計12ページもある。将棋AIに搭載されている定跡についての歴史的資料として、わりと価値があるのではないかと思う。

WCSC32 やねうら王PR文書
https://www.apply.computer-shogi.org/wcsc32/appeal/YaneuraOu/WCSC_PR.pdf

2022年までの歴史について知りたければ、是非↑のPR文書の5ページ目までをご覧いただきたい。

一言で言うと自動生成された定跡 VS 手動で入力された定跡という長い歴史があり、ようやくここ近年になって自動生成した定跡が手動で入力された定跡を上回るようになってきたかも？というところである。2022年時点ではそんなものであった。

2023年の将棋AI界の定跡生成アルゴリズム

このあと、2023年になってWCSC33では少なくとも優勝、準優勝チームであるdlshogiチームとやねうら王チームは自動生成された定跡を用いていた。

dlshogiチームがどうやって定跡を生成したのかはWCSC33のdlshogiチームのPR文書にある。

WCSC33 dlshogi PR文書(WCSC33終了後版)
https://www.apply.computer-shogi.org/wcsc33/appeal/dlshogi_with_HEROZ/dlshogi_with_HEROZ_appeal_detail_wcsc33_2.pdf

以下に引用する。

dlshogiチームは平時よりHEROZ社内の計算資源(A100×8が複数台？)を用いており、定跡生成も1ヶ月かけて生成したとある。

「後手がどのように指しても先手番が評価値 400 以上になることがわかった。そのため、角換わりの基本図は回避が必要と判断した。」

となかなか衝撃的なことが書いてある。詳細のアルゴリズムについては書かれていないのでよくわからないし、A100×8、AWSで借りると1時間4000円ぐらいするので、それが複数台で丸一ヶ月ともなると、1000万円ぐらいになりかねない。これは、アルゴリズムが公開されていたとしても容易に真似することはできない。

無論、やねうら王チームでそこまでのコストはかけられないし、かけてもいない。

やねうら王チームでは、チームメンバーの一人であるたややんさん(水匠開発者であり弁護士でもある)が、用意した定跡を用いた。

たややんさんの定跡生成はPythonのスクリプトを用いており、300行程度の短いスクリプトである。スクリプトについては現時点では一般向けには非公開であるが、アルゴリズム自体は簡単なので将棋AI開発者ならば簡単に追試できるであろう。

まず、このアルゴリズムについて以下で詳しく説明する。

たややん定跡自動生成手法(WCSC33版)

具体的な定跡の自動生成アルゴリズムとその疑似コードについては、WCSC33のやねうら王チームのPR文書に書いてある。

WCSC33 やねうら王 PR文書(WCSC33終了後版)
https://www.apply.computer-shogi.org/wcsc33/appeal/yaneuraou/yaneuraou_wcsc33_after.pdf

プログラマー向けには上の文書で十分だと思うが、一般の読者向けには多少補足が必要だと思うので以下に詳しく書く。

まず実際に指定局面からの対局を行うのだが、その時に、水匠で探索ノード数を100万～1億ノードとランダムに設定するのだ。

// 「ノード」というのは局面のこと。「探索ノード数」とは調べる局面の数。これを増やすとより良い指し手を返すようになる。

また、思考スレッド(探索に用いるスレッド数。この数で並列探索を行う)は4にしてある。1にすると探索ノード数が同じなら同じ指し手を返しやすいのだが、これを2以上に設定すると、マルチスレッドの微妙にタイミングのズレにより、同じ100万ノード思考させる場合でも異なる指し手がbestmove(最善手)として返ってくることがある。

つまり、このようにして水匠がその局面で返すであろう指し手をすべて網羅するというのが、たややんさんの一つ目の工夫であり、狙いであり、この手法を成立させるトリックの一つである。

次に、対局シミュレーションにおいては、定跡木上でmin-max探索を行う。

// 定跡木というのは、定跡の流れを樹形図のようにして書いたものだと思って欲しい。木というのは、グラフ理論の用語で、さきほど出てきたノードもグラフ理論の用語である。要するに将棋とは、局面を一つのノード(頂点)とするグラフなのである。

min-max探索とは、先手はleaf node(定跡木の末端の局面)での評価値が最大になる枝(指し手)を選び、後手はleaf nodeで(先手から見た)評価値が最小になる枝を選ぶ。それが先手・後手の双方が最善を尽くすということである。このような指し手を探す探索のことをmin-max探索と言うのである。

// Minimaxとかminmaxとか書くことが多いけど、ここでは私の好みでmin-maxと書いておく。

Minimax(Wikipedia)
https://en.wikipedia.org/wiki/Minimax

このmin-max探索を定跡木の上で行うわけだが、例えば終局まで対局させてある場合、千日手引き分けでなければ、先手か後手かのいずれかは勝ちのはずである。仮にその局面から双方が最善を尽くすと先手勝ちがわかっているとする。そうするとmin-max探索を行うと、先手側は勝ちの枝(指し手)が見つかるから、思考エンジンで思考させる必要がない。単にその枝(指し手)を選べば良い。後手は、min-max探索を行うと、そのまま定跡木の枝を選んでいくと負けになってしまうことがわかる。なので、自ら思考する。思考する時に、上に書いたトリックを用いているので、指し手はある程度バラけて定跡木にない指し手が出てくるかも知れない。それを期待している。

そのようにして、どうやっても後手が負けを回避することができなくなった時、対局シミュレーションの開始局面は先手必勝だと言えるわけである。

言ってしまえば、たややん定跡自動生成手法は、上に書いたこの2つの工夫だけで成り立っている手法である。わりとシンプルで、もう少しやりようがありそうなものである。しかし、この手法が実にうまく機能するのである。(詳しくは後述)

このスクリプトを実際に動作させているデモ動画があるので、これも紹介しておく。
https://youtu.be/AOUmhOJaZ7o

角換りの1886局面について

前置きが長かったが、ここからが本題である。

冒頭のツイートの「1886局面」というのは、角換り腰掛銀同型の38手目を開始局面として、そこからの変化が1886局面しかなかったということである。

この局面からの主要な変化については、プロ棋士の遠山先生の以下のnoteの記事に詳しく書いてあるので、そちらをまずご覧いただきたい。

現代角換わり腰掛銀の「テーマ図」での後手の8つの手段を解説！
https://note.com/toyama_shogi/n/ncf9adba19abb

それで、たったの1886局面しかないというのがまず驚きのポイントである。1886局面はいくらなんでも少なすぎる。有段者なら1局面1分ぐらいで覚えられるだろうから、31時間ほどで覚えられることになる。プロならもっと早いかも知れない。

私はテラショック定跡(2021年)、スーパーテラショック定跡(2022年)の時に500万局面以上の定跡を生成している。それからすると1886局面は数桁少ない。

私の最初の印象は「水匠、そんなに指し手の幅がないんじゃない？」であった。

水匠は確かにその局面では1つか2つしか指し手を返さないのかも知れないけども、他のソフトはそれ以外の指し手を返すことだったあるやん？だから水匠のみで定跡作っても他のソフトと対局したら定跡外されて何の意味もなくない？

というのが私の率直な感想であった。

実際、昨年開催されたWCSC32で準優勝となった白ビールは定跡を搭載していなかった。定跡を搭載していないのに、他のソフトの定跡に嵌ることはなかった。

WCSC32 白ビール PR文書
https://www.apply.computer-shogi.org/wcsc32/appeal/White_Beer/appeal2022_v2.pdf

要するに、他のソフトで自動生成された定跡に嵌ってしまうのは、ソフトを公開(評価関数モデルを公開)しているからで、白ビールのようにソフトを非公開にしているのであれば他のソフトで作った定跡には嵌らないのではないか、というのが2022年WCSC32(5月)時点での一つの結論であり、その時点での定説でもあったわけだ。

まあ、やねうら王系は、評価関数ファイル(評価関数モデル)が非公開であっても、だいたい似た指し手になる特徴はあるから他のやねうら王系で自動生成した定跡に嵌りやすいというのはあった。しかし、白ビールのようにdlshogi系であれば、モデルを非公開にしていればそのような問題にはならないというのが、将棋AI開発者の暗黙の認識でもあったわけだ。2022年の電竜戦までは…。

2022年の電竜戦で覆った常識

ところが、その常識が完全に覆ったのである。

それは、2022年の電竜戦でdlshogiに対して、先手の水匠が角換りで(定跡の進行により)勝利したことによる。

dlshogiは最新の評価関数モデルは非公開だから非公開ソフトに分類されると思うし、dlshogiはやねうら王系ではないから指し手が似ているということもないはずである。水匠はこの時、定跡の生成にdlshogiを用いていない。つまり水匠で生成した角換りの定跡が全くの異種ソフトであるdlshogiに通用したわけである。

なぜdlshogi相手に水匠で生成した定跡が通用するのかについては私も憶測でしかないのだが、自分の理解している範囲で書いていくことにする。

たややん定跡自動生成手法の追試

まずWCSC33が終わってから私はたややん定跡生成スクリプトについて精査してみた。正直、これよりもっと効率良く定跡を生成できるスクリプトを作れると思っていた。

追試を兼ねて、私は次のように改良した。これをペタショック定跡(1億ノード×1000万局面 = 1000兆 = 1ペタ)と名付ける。

ペタショック定跡手法

【改良1】 1億ノード思考する過程で思考エンジンからは読み筋が出力されるので、その読み筋が変化するから、その読み筋の初手(次の一手)をすべて拾っておき、それらを定跡木の枝とする。こうすることで、ある局面に対しては1度しか思考しないで済む。

生成が非常に効率的になる改良のつもりだったのだが、これだと水匠がその局面で指す指し手を網羅できず、たややんの手法で生成した定跡のほうが網羅性が高かった。たややんさんの、4スレッドで何度も100万ノードから1億ノードでランダムで思考するというのがトリックであったわけだ。無駄なようでいて、実によく練られていたわけだ。たややんさんの頭の良さを軽く見ていたことが招いた私の判断ミスである。

そこで改良1に加えて、私は次の改良も入れた。

【改良2】 ある局面について複数の思考エンジンで思考させられるようにした。一つのエンジン(＝ あるエンジン と 探索ノード数 の組)では1回しか思考しないが複数のエンジンを用いているので指し手はバラけるはずである。

【改良3】 局面を延長するのは、判定用のエンジンが返した評価値が(先手から見て) -100 から + 200の間である時に限るとした。

このようにすることでmin-max探索をしながら対局シミュレーションを行うのではなく、定跡に登録されている各局面に対して未探索の局面を選び並列的に思考できる。局面数が増えてくるとmin-max探索をする時間が馬鹿にならないので、これは必須の改良だと思った。

実際、角換りは手待ちみたいなのが主流なので、局面の合流(別の手順を経て同一局面に到達すること)がすこぶる多く、min-max探索を愚直に行うと組み合わせ爆発して現実的な時間で求まらなくなるのだ。

ところが、この改良3により、思考対象とすべき局面が大量に増えてしまったのである。

角換りのテーマ図(38手目)から思考させたところ、以下のようになった。plyとは手数のことで、例えば、ply = 56 , 27355/110518なら、56手目の局面は定跡DBには110518局面登録されていて27355局面が探索済みである。という風に読む。当然ながら残りの局面を探索する時、改良3の条件を満たすと57手目の定跡DBの局面が増えることになる。

おわかりいただけるだろうか。私は38手目なんか中盤だからちょっと指したら形勢が傾いて改良3の条件から外れてそこで定跡の進行は打ち切られると軽く考えていた。ところが改良3の条件を入れているにも関わらず1手ごとに2倍近くに指数関数的に増えていくのである。水匠1億ノードで見てほぼ形勢互角の局面がそれだけの数あるということだ。

WCSC33が終わったあとたややん定跡生成手法の追試をしようと思った私はスクリプトを2,3日で書き上げて、そこから4台のPCを用いてエンジンを320並列で動かして局面を調べ続け、現在(初手から)100万局面ほど探索した(定跡DBに探索済みとして登録されている局面数が100万)わけなのだが、全然終わりそうにない。このペースで増えていくならあと丸一ヶ月かけても60手目まで掘れるかどうかである。

おまけに、たややん定跡手法で1日で生成した定跡のほうが、私の定跡より長い手数まで定跡を持っていて、かつ、網羅性が高いのである。

私のほうはあと数ヶ月掘ってみるつもりではあるが、無駄なことをしている感じもある。評価値-100～200の範囲の局面をすべて掘ろうだなんて人類には早すぎたのかも知れない。

私が書いた定跡採掘のスクリプトは、dlshogiの山岡さんが公開されているcshogiというPythonのライブラリを利用していて、これを用いると以下のように局面図がSVGで出力できて嬉しい。探索中の局面一覧がブラウザで閲覧できるのでテンション爆上がりである。cshogiには大変お世話になっているのでこのタイミングで紹介しておく次第である。

cshogi: 高速なPythonの将棋ライブラリ
https://github.com/TadaoYamaoka/cshogi

テラショック定跡手法とペタショック定跡手法の比較

テラショック定跡手法の時はもっとひどかった。テラショック定跡では、思考エンジンとしてふかうら王を用いていた。

// ふかうら王はdlshogiと同じくDeep Learningを用いた将棋エンジンであり、dlshogi互換のソフトだと思って欲しい。

ふかうら王は、思考した時にすべての候補手の評価値を一気に返す機能があるので、これを用いてベストな評価値の指し手(bestmove)との評価値の差が小さいものはありえる指し手として定跡に登録していた。

つまりは、特定のエンジンに対する定跡を生成しようとしたのではなく、私はその時、将棋というゲームの真の結論が知りたかったわけである。将棋の真理を探求している気分になって浮かれていたのである。おかけで1手進むごとに2倍以上の速度で局面が増えていき、500万局面掘っても20手目前後ぐらいまでしか掘れていなかった。(部分的にはもう少し掘れていたが)

「将棋というゲームの真の結論を知る」という課題は、人類が挑戦するには早すぎたわけである。

そこで、今回の手法では特定のエンジンの指し手に限定するとしたのであった。特定のエンジンの指し手ならば簡単に網羅できるだろうと思ったわけである。

ところが、結論は上に書いた通りで、ペタショック定跡手法のように評価値ベースで定跡局面を延長していくと1手ごとに局面数は2倍近くになり、組み合わせ爆発を容易に起こすというものであった。

私は評価値が互角ぐらいの形勢から遠ざからない局面集合みたいなものを手に入れたかったのだが、それすらも人類にはまだ早すぎたようである。

ペタショック定跡手法の失敗

ペタショック定跡手法では、定跡を書き出す時にmin-max探索を行う。min-max探索も合流を含むと組み合わせ爆発を起こすのだが、私は組み合わせ爆発を起こさない画期的なアルゴリズムを発明した。このアルゴリズムについては然るべきところで発表する予定である。(将棋AI Discordで発表済み。またやねうら王のGitHubでは適用済み。)

それはそれとして、実際に書き出してみると先手が角換りを避けて、後手が角換りを目指す定跡になってしまっている。もし角換りが先手必勝だと言うなら、この定跡は使えねぇゴミである。

なぜこのようなゴミが生成されてしまったかと言うと、(現在掘れている)角換りの55手目付近では評価値は先手から見て+20ぐらいなのである。形勢が傾くところまでまだ到達してないわけである。それに対して初期局面は+70ぐらいであるから、55手目に近づけば近づくほど評価値は減っていくわけで、ベストな評価値のところ目指そうとすると、先手はまだ探索が終わっていないplyの小さなノード(要するに開始局面からの手数が少ない局面でまだその先を調べていない局面)を目指そうとするわけである。後手は逆に+20なら御の字であるから、喜び勇んでその局面を目指すわけである。

このようにして先手は角換りを回避し、後手は角換りを目指すという本末転倒な定跡(使わないほうがマシ)が生成されるわけだ。

たややん定跡自動生成手法の再評価

このように自分で自分なりの工夫をいくつも追加して、満を持して、たややん定跡手法を追試しようとした結果、私は見事に大爆死したわけである。そうして私はたややんさんの優秀さを思い知ったわけである。偉大なるたややんであった。

ペタショック定跡手法はその後、さらにいくつかの工夫とアルゴリズム的なブレイクスルーを経て復活する(これについて詳しくは別の記事に譲る)のだが、ともかく、一見成功しそうにないアイデアなのに見事にうまく機能しているのがたややんの定跡自動生成手法なのである。

たややんの手法が素晴らしいのは、ちゃんと優劣が付くところまでは局面が延長されることにある。そこまで延長されているので、ペタショック定跡のようにplyが小さいところまでしか掘れていないノードを目指すことがない。つまり、定跡生成は、広く浅く調べてはならないのである。狭く深く調べないといけない。これがペタショック定跡大爆死から私が学んだことである。

「そうは言っても、狭く深く調べたら、他のソフトで定跡にない指し手を指されたらそれまででしょう？」と思う方もおられるだろう。私もずっとそう思ってきた。

ところが、角換りに関してはどうもそうでもないようなのである。これは一体どういう原理なのであろうか？

なぜ狭く深くでうまくいくのか？

これに関して私の仮説を述べる。

将棋は勝ち筋が一つしかなく、ある指し手以外はすべて悪手ということは多々ある。そういう局面は珍しくもない。

しかし、ある程度形勢に差があると勝ち方は複数あることもまた珍しくはない。

おそらく角換りは後者のような性質を持っている局面が多いのであろう。だから、水匠がその局面でひねり出すすべての指し手を以てしても回避できずに先手が優勢にできる時、実際にその局面は(どのような指し手を以てしても後手は回避できずに)先手優勢である可能性が極めて高いということなのである。

このような性質をたややん定跡自動生成手法はうまく利用しており、そしてそれゆえうまく機能するのである。だから、たった1886局面で角換りが先手必勝だと結論付けるのに十分なのである。(と私は考えた)

無論、そうは言っても水匠とは桁違いに強いソフトを用意すればそのような定跡の穴を見つけることはできるだろうし、(やねうら王系とは異なるソフトを用いれば)水匠の定跡にない指し手を発見することもできるだろうし、これが決定版と言うつもりは毛頭ないのだが、少なくともやねうら王系のソフトだと後手は回避難しいことは確かなので、大会ではやねうら王系のソフトでは後手の角換りは避けるに越したことはない。

人間の将棋への影響

「将棋AIの、それも一部の将棋ソフトでの指し手に限った話でしょ？人間の将棋には影響は皆無では？」と言う意見も聞かれるし、私もそう思うところはあるのだが、現実問題として、藤井聡太七冠誕生した先日名人戦の対局でも第3局、第5局目で後手の藤井さんが角換りを避けて(?)雁木にしたことで話題となった。

また後手が角換りを避けて雁木に進行する場合、雁木が得意な対局相手であるなら、先手は雁木にされるのも嫌なので、先手側が角換りと雁木を拒否して振り飛車にするという作戦も考えられるようである。ここ数日でバキバキの居飛車党だった棋士が突然振り飛車を採用するケースが出てきた。

そんなわけで角換りが終わったというのが、(私の予想に反して)AIの世界だけの話ではなくなりつつあるようだ。

定跡の集合の大きさについて

やや蛇足ではあるが、定跡の集合の大きさについてざっと書いておく。定跡とは、各局面で(定跡の)指し手を選んでいった時に到達できる局面の数であるから、指し手の選択の幅が定跡の集合の大きさを決定付けるわけである。

だから、指し手の幅(ある局面の指し手の数の平均)について、大きい順に並べていくことにする。

1.ランダムプレイヤー

ランダムプレイヤーとはすべての合法手をランダムに選択するプレイヤーのことである。すべての指し手が含まれるので、ランダムプレイヤーによる定跡は、(平手の初期局面から合法手で到達可能な)すべての局面からなる集合である。

将棋では平均合法手の数は100程度なので、平均160手で終局だとしたら、100の160乗もある。実際には、もっと小さくて10の68乗ぐらいだと言われている。

2.アマ初段

アマ初段ぐらいになると、ある局面の指し手は(ポカを除けば)たぶん平均的には5手ぐらいか？

３．プロ棋士

プロ棋士になると悪い指し手はアマ初段よりは格段に減って、ある局面の指し手は平均的には3手ないと思う。

４．将棋AIで評価値がbestmoveから30程度の差の指し手

これは私の以前の調査から、2手より少し大きいぐらいの数字とわかっている。(2.2とか2.5とかそれくらい)

５．水匠で100万ノードから1億ノードで返しうる指し手の集合

これは2手よりは少し小さいとわかっている。

無論、アマ初段には見つけられないけどプロ棋士には見つけられる良い指し手みたいなのもたまにはあるけど、そういうレアケースを考えて集合の包含関係を書くと意味のない図になってしまうので、レアケースについては考えないことにする。要するにある局面における平均の指し手の数に応じた集合の大きさで、大きいほうの集合は小さいほうの集合を完全に包含するものとする。

そうすると図はシンプルになり、以下のようになる。

しかも、たややん定跡自動生成手法による定跡は、先手が必勝法を見つけた時点で先手はそれ以外の指し手を選択した時の変化を調べる必要がないので、平手の初期局面から水匠が指しうる指し手によって到達可能な局面の集合よりさらに小さな集合であることにも留意する必要があるだろう。要するに、みんなが想像してるよりずっとずっと小さい。だからこそ角換りが1886局面しかないのである。

まとめ

プロ棋士の考える定跡(プロ棋士が指しうる指し手からmin-max探索した時に得られる定跡)より、水匠の指しうる指し手(をmin-max探索した)定跡の集合のほうがずっとずっと小さい。

今回書いたのは、そういう小さい集合(小さな将棋ワールドと言っても良いと思う)の話でしかないのだが、しかし、今回書いたようにそれが「AIの世界だけの話でしょ」と言い切れないのもまた事実のようなのである。

未解明な部分も多く、私の憶測も交えて書かざるを得なかったが、現時点での私の理解を正直に書いたつもりである。

この記事により読者諸氏の将棋AIによる定跡に対する解像度(理解度)が上がったのなら幸いである。

「角換りは終わったのかについて1万文字程度で」への4件のフィードバック

  1. ＞無論、アマ初段には見つけられないけどプロ棋士には見つけられる良い指し手みたいなのもたまにはある
    文脈的にこれ逆の話ですよね？

    返信 ↓

    • そこ、話がわりとややこしいのですが、「アマ初段のほうが指し手の幅が広い」かつ「指し手の幅が広いほうが集合は大きい」「集合が大きいほうが小さいほうを完全に包含するといまは考える」(この記事の文脈では、正しいベン図を描きたいのではなく、集合の大小関係をざっくり示したいのでこの仮定が必要となります)という文脈でして、この3つから「アマ初段の指し手はプロの指し手をすべて包含する」という結論になり、本記事の図のような包含関係にあると説明しています。

      返信 ↓

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です