逆算方式による詰将棋の問題生成プログラム

将棋を始めた ので、詰将棋を毎日のように解いているのだけど、せっかくなら詰将棋の問題を自動生成してみたい、と思って試してみた。

前提知識

詰将棋とはどんなものか

  1. 攻め方(先手)が玉方(後手)の玉を詰ますのが目的。
  2. 攻め方は必ず王手をかける(玉方は必ず王手をはずす)。
  3. 玉方は盤上と攻め方の持駒以外すべての駒(ただし玉は除く)を合駒として使用できる。
  4. 玉方は最善を尽くし、最も長く手数がかかるように逃げる。
  5. 玉方は無駄な合駒をしない。
  6. その他は指し将棋のルール通り。二歩、打ち歩詰め、行き所のない駒、連続王手の千日手はいけない。

(日本将棋連盟の詰将棋ページより)

手法

コンピュータによる詰将棋の解答・問題生成というのは20年くらい前から既に様々な論文などで研究されているようだ。生成については、主に「ランダム法」「逆算法」といった方式があるらしい。

あまり論文にちゃんと目を通して調べてはいないけど、だいたい手法は述べられているものの 実際に利用できそうな公開されているプログラムが見当たらなかったので、自分で作ってみることにした。

手法について調べる前に最初に思いついたのが逆算法だったので、その方式で。

詰み状態の生成

逆算法は、詰みの状態から巻き戻すような形で問題を生成していくので、まずは最終的な「詰み」の形を生成する。

とりあえずは一般的な詰将棋ということで玉は攻め方(先手)は無しで後手側だけに存在する前提。 まずは何も考えずそれ以外の38個の駒をランダムに配置してみよう。

f:id:sugyan:20171119212056p:plain

…まず二歩があるし、王手もかかってないし、関係ない駒が多すぎる。 少し条件を追加してみる。

  • 二歩を回避
    • 1筋につき1個しか歩が置かれないように
    • 無理矢理置かず 適当に後手側の持駒に
  • 有り得ない駒配置を回避
    • 先手だと1段目に歩・香車、2段目以下に桂馬、などは有り得ない
    • 成らせる、もしくは後手側に変えてしまう
  • 成駒を追加
    • せっかくなので成れる位置に居る駒は適当な確率で成らせる
    • 飛車・角はもうちょっと下の方でも成って良いことにする

f:id:sugyan:20171119212106p:plain

これで一応、有り得なくはない局面になった…かな。 たまに王手になっている状態のものは出るけど、「詰み」の状態にはなかなか遠い。関係ない場所に居る駒が多すぎる。 さらに以下の条件を追加する。

  • 後手側の玉の位置を1〜4筋、1〜4段に限定
    • その他の駒を、その近くに集中させる

f:id:sugyan:20171119212111p:plain

惜しい!

f:id:sugyan:20171119212116p:plain

王手すらかかってない!

f:id:sugyan:20171119212120p:plain

OK!

感覚としては、上述の条件で10回程度試行すれば、「詰み」の状態は得られるようだった。

ところで「詰み」とは。

  • 既に王手がかかっている状態であり、
  • どう応じても必ず王が取られてしまう状態
    • どの応手を選択しても王手状態から逃れることができない

というロジックで判定する必要がある。

1手前に戻す

さて、「詰み」が出来たので、そこから逆算していきたいところだけど、まだちょっと関係ない駒が多すぎるので、「詰み」の状態が崩れない 影響を受けない駒を取り除いて後手側の持駒にする。

とはいえ最終的に出来上がる問題には効果のある位置にある駒もあるかもしれないので、すべては取り除かず、確率として8割程度を消す感じで。

f:id:sugyan:20171119212125p:plain

だいぶスッキリした「詰み」状態になっている。

ここから、先手側を1手「戻す」ことで王手状態でなくなれば、それを辿る手が正解となる1手詰の問題が出来上がる、はず。

1手前の有り得る状態、とは。

  • 盤上の先手駒の動き得る範囲から逆算
  • 持駒を使う場合も
    • しかし打ち歩詰めは回避する

たとえば歩が一歩手前に居るかもしれないし、成っていない駒は持駒の中から打たれたものかもしれない。成駒なんかは金の動ける範囲での前の位置かもしれないし、桂馬が跳ねてそこに成ったものかもしない、など色んなパターンを考慮する必要はある。

ただ生成すべきは1手詰の問題なので、1手前は「王手ではない」状態になっている必要がある。 なので、上図の場合は必然的に3四の龍が別の位置に居た、という状態が選ばれることになるだろう。

2三2五3六 のどこかに居た状態であれば、王手ではないので大丈夫そう。

f:id:sugyan:20171119212128p:plain

というわけで出来たのが上図。ここから ▲3四龍 と動けば玉はどこにも逃げられず、詰みとなる。

とはいえなんかまだ関係ない駒が多いな… というわけで改めて、問題に関係ない、取り除いても問題ない駒を排除する。

ついでに、成香・成桂など通常の問題図にはあまり現れない慣習がある?ので、微妙な成駒は金将やと金があればそれに置き換えるなどの処理をする。ここでは金を優先にしたので と金 が 金将 に置換される。問題には影響ない。

f:id:sugyan:20171119212134p:plain

これで1手詰の問題が完成となる。 この問題の場合は1, 2段目が完全に無駄な空白になってしまっているので 全駒を丸ごと上段に(さらに右にも)ずらしてしまっても良さそうだけど 特にそういう処理は入れていない…

解答をSolverでチェック

上述の例はたまたま上手くいったけど、場合によっては 1手巻き戻した結果が 1手詰の問題にはなっているものの「解が複数ある」という状態になってしまうこともある。

f:id:sugyan:20171119212136p:plain

例えばこういう場合。元々は2二に成銀が居る状態から巻き戻して作られたのだけど、実際には ▲2二飛成 でも正解になってしまう。正解が複数できてしまう、「余詰」という不完全作品になってしまう。

なので これは失敗とみなして最初から作り直すべき。 ということで 「正解が1通りしか無いこと」をチェックするためのSolverが必要となる。

1手詰だけを考えるのであれば、これはとりあえず先手の動かし得る手を全探索して 詰みになる手を列挙していけば良いだけなので Solverというほどのものじゃなくてもいいかも。

3手詰への拡張

さて、とりあえず1手詰は作れるようになったので、次は1段階ステップアップして3手詰の問題生成にチャレンジ。 基本的には同じ考え方で、

詰み -> 先手を巻き戻してNOT王手に

から

詰み -> 先手を巻き戻してNOT王手に -> 後手を巻き戻して王手に -> 先手を巻き戻してNOT王手に

と巻き戻しを増やすことに。 1手詰の場合は先手の動きだけ考えれば良かったが、3手詰から先は後手側の動きも入ってくるので面倒になる。

まず最初の巻き戻しだけど、1手詰の問題を生成する場合は

  • 詰み方が1通りしかないようにする
  • 関係ない駒は最終的に取り除く

という処理をしていたけど、3手詰における最終手は複数通りあっても良いし、やはり周りの駒が問題に影響することもあるので完全には取り除かないでおく。とにかく「あと1手で詰む」という状態になっていれば良い(駒余りなどは避ける必要あるけど)。

次の後手側の巻き戻し。問題を解く際には最善手で逃げることを考えないといけないけど、そのへんは考えず とりあえず有り得る状態を作り出す。

前の状態が王手で 今が1手詰の王手ではない状態、ということは

  • 玉が安全地帯に動いて逃げた
  • 後手側の駒(玉も含む)が王手をかけていた駒を取った
  • 飛車・角・香車などの道を塞ぐように持駒を打った

というパターンが考えられる。 なので、巻き戻す際には

  • 玉を先手駒の効きがある位置に突っ込む
  • 後手側の玉付近の駒の位置に 先手側の王手駒があった状態にする
  • 成駒でない駒を取り除く

ということを考えることになる。 特に2番目のパターンが複雑で、まずその位置から王手をかけられる駒でないといけないし、それを取れる位置に後手の駒が居ないといけない。

f:id:sugyan:20171119212139p:plain

例えばこの図でいう3一の歩は、持駒から打った状態しか有り得ないので、この位置から先手側の駒で王手していた、ということは有り得ない。

そして有り得る状態のパターンはかなり多くなり、例えば上図で2二の銀が元々1一とかに居て 何かしら先手の駒を取ってこうなった、と考えるとその駒は 歩、香車、金、成銀、… つまり桂馬と角以外すべてが有り得る。

ので、生成され得るパターンも膨れ上がることになる。

まぁそうやって多くのパターンが有り得るけども、全部を検証する必要はなくて それらの中からランダムで選択して生成したものが偶然にでも良い形になっていれば良いのだけど。

こうして後手側の巻き戻しで王手状態が作れたら、1手詰のときと同様にまた先手側を「王手ではない」状態に巻き戻す。

こちら側のロジックは同じで問題ないけど、唯一違う部分としては最終手ではないので打ち歩が許される、くらいかな。王の目の前に歩がいる状態が、持駒から打ったものとして処理しても許される。

3手詰Solver

上述のように 先手 -> 後手 -> 先手 と巻き戻したことでなんとなく3手で詰む問題になりそうだけど、「後手は最善手で逃げる」ということを考慮せずに巻き戻しているので、実際には全然意図通りにならないことが多い。

3手戻したのに結局1手で詰めてしまうものになっていることもあるし、意図せず5手詰や7手詰の状態になっていることもあるし、余詰だらけになったり そもそも解けない問題になってしまうこともある。

というわけで1手詰の場合と同様に、

  • 3手で詰める問題である
    • 駒余りなどもない
  • 少なくとも1手目は一通りの解しかない
    • 3手目は複数あっても良い

といったことを検証し、そうでない場合はもう一度作り直し、という方針でいきたい。

…が、1手詰と違って3手詰以上の問題を解く解答プログラムはなかなか奥が深く、簡単ではなかった。

少なくとも3手程度なら全探索しても現実的な計算量で済むのでは、と思ったけど 合駒・無駄合駒というルールがあり 実際には3手で詰むものも 素直に全探索していると 合駒 -> 同飛 が続いて7手になってしまう、などといったことが起こる。じゃあ無駄合駒を判定してそれは打てないよう考慮して判定、と思っても「どういう条件なら無駄合駒なのか」という明確なルールが存在しない(!)という難しい問題…。「無駄合駒」でググって調べるだけでもだいぶ面白かった。

あと再帰的に調べる際には不詰(もうどうやっても詰ますことができない)になったら探索を打ち切れるのだけど、その不詰の判定も難しく、パッと見ではこれはもう詰まないでしょ という局面からもルールに則った無駄な追いかけっこ状態は起こり得るので それを上手く判定できないとどんどん探索が深くなり無限に時間がかかる。

とりあえずは探索する深さを限定させて それ以降はもう解けない、という制限を設けることで だいたいの3手詰くらいなら解けるようになったけど、パターンによっては数百msかかってしまい、厳しい。

これが遅いせいで、3手詰問題の生成は現状 数秒〜十数秒かかってしまう。

調べると「df-pnアルゴリズム」「最良優先探索」といったものを使うことで長手数のものも解けるようになる、ということだったので ここは今後の課題として早く確実に解けるSolverを実装しておきたい。 5手詰以上の問題を生成しようと思うと このチェックのためのSolverがボトルネックになってしまうので、ここが解決されないと厳しいな、という感じ。


ともあれ、Solverでのチェックが出来れば 1手詰の問題と同様に不要な駒を取り除いたり後処理をして、こんな感じの問題が出来上がる。

f:id:sugyan:20171119215709p:plain

はい。▲2二歩成 △1三玉 ▲2三飛 の3手詰になって…ますよね?

成果物

とりあえずは何となく3手詰の問題までは生成できるようになった、ということで 自動生成された問題を定期的に呟くTwitter BOTは作ってみた。

まだまだ潰しきれていない判定バグなどがあって不完全な問題が出ることもあるかもしれないけど。見つけ次第 随時なおしていきたいと思います。

Chat BOTでも使えるようにと開発を進めているけど、その話は後日 別の場所で…

所感

3手詰の問題生成程度なら、難しいアルゴリズムの知識など無くても とりあえず作ることができる、というのを実感した。 ただ、ひたすら面倒臭いけどw

将棋のルールをプログラムのロジックに落とし込む、というだけでもなかなか大変で。駒によって動きが違うし 大きく動ける駒も途中で阻まれれば先には行けないし 成駒や不成も有り得るし 無駄合駒とか複雑なルールがあったり…

とにかくif文やswitch文だらけでつらい感じのプログラムが出来上がりやすい…。 キレイに書くのはとても難しい、でもプログラミングの練習にはなかなか良い題材かも、というのも思ったりもしたのでした。