27 October 2018

    打ち歩詰めを回避するための不成

     真偽の程はわからないのですが、最新の将棋ソフトを以ってしても角不成を含む詰将棋を解くことが出来ないと小耳に挟みました。自分は最新の将棋ソフトの動向には疎くソフトも古いのしか持っていないので確認出来ませんが、有名な「谷川九段の角不成」という実戦詰将棋があって、機械学習(おそらくディープラーニングを使ったもの)を用いた最新のソフトでも6七角引不成(参考記事)からの19手詰めが解けないそうです。学習型の将棋ソフトは終盤が弱いとは聞いていました。でも自分が持っている相当古いソフト(10年以上前に購入した「AI将棋 Version13」1)で試してみたところ、見事に詰め上げることが出来たので結局はソフトに依るということでしょう。ただ最新のソフトがなぜ解けないのか、なぜそうなっている(あるいはそうしている)のでしょう?もしかしたら結構難しいのでしょうか?データ構造によっては難しい処理を強いられるかもしれないなぁとは思います。原因というか不成を読まない?理由についてはもしかしてと思い当たることもあるのですが、想像の域を出ないので他人様のことは置いといて、とりあえず自分の作ったソフトが成りと不成をちゃんと区別出来るか確認することにしました。打ち歩詰めに関しても詰将棋に関しても成る・成らないに関しても一応テストはしてますが、打ち歩詰めを回避するために敢えて成らないということが出来るかどうかちょっと心配になったからです:sweat_smile:

    19手詰めで確認したいけど

     有名な角不成の19手詰の詰将棋をそのまま自分のソフトで試してみたいところですが、自分のソフトでは19手詰めなんて出来ません。何度かこのブログでも書いていますが、有名な将棋ソフトは大抵、将棋盤をビットパターンで表現して高速に先読み出来るようになっています(BitBoardと呼ばれているようです)が、自分のソフトは通常の多次元配列データで将棋盤を表現しているので到底太刀打ち出来ません。将棋ソフトに革命をもたらしたボナンザ(Bonanza)は独自の評価関数や学習機能で有名ですが、BitBoardを最初に将棋ソフトに取り入れたのも同じ開発者(保木氏)なのでしょうか?よく知らないのですが、もしそうならそのことももっと評価されるべきだと思いますけどどうなのでしょう?2BitBoardをJavaScriptで作る人は…いないでしょうね:sweat_smile:
     話が逸れましたが、長手数の詰将棋は無理なので、5五将棋の形に修正した短手数の詰将棋問題で確認することにしました。9×9の本将棋のままでは時間が掛かり過ぎるからです。
     以下のテストは5五将棋の盤面(5×5)ですが、通常の本将棋(9×9)と同じように先手は3段目で成ることが出来、後手は5段目だけで成ることが出来るよう特殊な設定にしています。また、詰みに影響を与えないように双玉の形にして後手(玉方)の持ち駒は時間短縮のため金一枚にしました。

    1. 打ち歩詰め回避詰将棋 - 角不成(出典):
      角不成詰将棋
      先手持ち駒=無し
      詰み手順=2三角不成、1一玉、1二歩、2二玉、3二飛成、まで5手詰め
      初手2三角成は打ち歩詰めになります。

    2. 打ち歩詰め回避詰将棋 - 歩不成(出典):
      歩不成詰将棋
      先手持ち駒=歩一枚
      詰み手順=3二歩不成、1二玉、1三歩、2二玉、3三飛成、まで5手詰め
      初手3二歩成は打ち歩詰めになります。

    3. 打ち歩詰め回避詰将棋 - その他(出典):
      打ち歩詰め回避詰将棋
      先手持ち駒=桂一枚、歩一枚
      詰み手順=2四桂、同龍、1三歩、同龍、2一銀不成、まで5手詰め
      すぐに1三歩は打ち歩詰めになるので、桂馬で王手して龍で打ち歩を取らざるを得ないようにして打ち歩詰めを回避します。

    4. 玉方打ち歩詰め誘導 - 飛不成(出典):
      玉方飛不成詰将棋
      先手持ち駒=桂一枚、歩一枚
      正解手順=2四桂、同飛不成で1三歩が打ち歩詰めになるようにして即詰みを逃れます(結局は詰まされますが…)。
      玉方が飛不成で打ち歩詰めに誘導することで即詰みを逃れます。

    5. 玉方打ち歩詰め誘導の反証テスト:
      玉方飛不成詰将棋の反証
      先手持ち駒=桂一枚、香一枚
      正解手順=2四桂、同飛成
      桂馬を打たれた時に先手の持ち駒が歩ではなく香車だった場合には飛車が成る(最善手)ことを確認。(持ち駒に歩ではなく香車がある場合は、1三香と打てば詰みなので2四桂馬は悪手ですが、テストのために人間が指してます)

     一応すべてのテストで正解でした。但し、このテストは実際のアプリより深く読むように設定し、敢えて指し手の候補手を絞り込まない(αβ法を使った全件探索3)ようにして実施しています。

    詰将棋を解くことと将棋に勝つことは別物

     AI同士で対戦させて上記のテストを実施したのですが、1.と5.のテストはAI対人間でテストしています。1.は後手側、5.は先手側を人間が担当しています。ちなみに1.のケースで先手・後手ともにAIにしてAI同士で対戦させると以下のように対局が進行します。
    駒余り
     AIは特別な処理をしない限り駒が余ることに拘らないので駒余りの手順を選んでしまいました。受ける側(後手)が正確に駒が余らないように4応じないと、詰将棋として正解手順にならないので玉方(後手)は人間が指すことにしたわけです。「駒が余ってはいけない」という詰将棋独自のルールをソフトに実装するのは結構手間がかかりそうです。また、5五将棋では王手が掛かっていなくても玉が自殺する手しか存在しない時がよくあります(3三将棋だともっと頻繁に現れます)。そのような時、AIにとっては連続王手で綺麗に詰ますのも、相手の指す手を無くしてゲーム終了させるのも同じ「勝ち」なので、綺麗な詰み手順があるのにそれを選ばない時がよくあります5。そういう時に端から見ている開発者としてはがっかりするのですが、「駒が余ってはいけない」という詰将棋独自のルールも含めて、そうなるように作っていないので仕方がありません:sweat_smile:
     言いたいことは、以下の3つは微妙に意味が異なるということです。

    1. 詰将棋を解く(駒を余らせない、無駄合いをしない等の詰将棋独自のルールにもしたがう)
    2. 相手玉を詰まして勝つ(詰みを逃さない、詰みを優先する)
    3. 将棋に勝つ(連続王手による詰み手順に拘らない)

     たぶん機械学習(ディープラーニング含む)によるAIだと1.と2.の機能を実装するのは難しいのだと思います。特に1.の機能は、勝手な想像ですが外国人の開発者が将棋ソフトを作ったらよほどの将棋好きでもない限り省く(実装しようとさえ思わない)と思いますし、話題になったAlphaZeroも今後1.の機能を実装することはないでしょう(予言):sweat_smile:
     2.の機能は昔からノウハウが蓄積されてる詰み判定ルーチン(学習によるものではなく力技の探索機能)を併用することで、程度の差こそあれ実現出来るような気がします。
     ということで、角不成の詰将棋が解けない最新のAIっていうのは、純粋に機械学習によるAI機能だけで将棋を強くすることを目指していて、敢えて力技による先読み機能を実装していないソフトなのかも知れません、私の単なる憶測ですが。

    追記

     この記事を書いた時点では「最新の将棋ソフト」と聞いただけで特定のソフトを想定して書いていたわけではないのですが、最新の将棋ソフトの一つで最も有名?な「将棋神やねうら王」はオプションで不成の指し手を読むように変更出来るそうです(開発者のTweet)。オプション設定で簡単に変更出来るということは、「やねうら王」に関しては不成の指し手を敢えて読んでいなかっただけみたいです。「やねうら王」はLinuxでも動作させることが可能だと聞いたので、いつか製品版にこの機能が組み込まれたら購入して試してみようと思ってます。

    おまけ

     5×5の将棋盤で特別な設定でテストするのではなく、なぜ9×9の通常の将棋盤で玉方の持ち駒は残りの駒全てという普通の詰将棋と同じ設定でテストしないのか、疑問に思った人がいると思います。やってみるとどうなるか、9×9のGUI環境を用意するのは面倒なのでCUI環境でやってみました。

    9×9将棋盤でのテスト

     将棋盤の上部にhmmxxxggggkkkkyyyffffffffffffと表示されているのは玉方の持ち駒です(飛角角金金金銀銀銀銀…)。
     テスト1.のケースで試してみたところ、正解の初手を指すまでに約2週間(経過時間=1208445383ミリ秒)かかりました:sweat_smile:この問題を解くには6手読みが必要で、5手読みだと初手を指すまでに約3時間掛かりましたが不正解(歩を成ってしまう)で、一手読みを深くするだけで約2週間に延びてしまう様はまさに指数爆発という表現がぴったりです。
     最初は9×9の通常の将棋盤でテストをやりかけたのですが、時間が掛かり過ぎることが分かったので、5五将棋の形に修正するやり方でテストすることにしたということです。


    1. Windows用のまともなPCを持ってないので、Windows向けソフトをLinux上でWineを使って動かしてます。 

    2. 誰かが作ったというより多くの人の手によって改良されてきているのかもしれませんし、もっと古くから実装されてそうな気もします。 

    3. 「局面の静的評価を枝刈りするためのアルゴリズム=αβ法」ということで、αβ法というのは全ての局面を読まずに端折ってるから読み抜けすることもあると勘違いしている方がいるので、敢えて「αβ法を使った全件探索」と書きました。αβ法は「ある静的評価関数を使って全ノードを探索した場合と同じ結果が得られる時間短縮のためのアルゴリズム」です。一つ一つの局面を全件探索して評価する場合と同じ結果が得られますので読み抜けはありません。自分のアプリでもやっていますが、「敢えて候補手を端折って評価する方法」はαβ法とは関係ありません。 

    4. 詰将棋では同じ詰まされるにしても受ける側(玉方)が攻める側になるべく多くの駒を使わせるのが最善手。 

    5. ここで言っているのは連続王手の三手詰めが存在しているのに王手を掛けずに、同じく三手で勝つことがあるという意味です。三手で勝てるのに勝ちを逃して(手数を伸ばして)勝ってしまうという意味ではありません。「詰みより必至」という話とも違います。 



    blog comments powered by Disqus