no-image

詰将棋作成アルゴリズム考察

詰将棋Solver

解く方に関しては既に研究が進んでおり、df-pnアルゴリズムを使うことでかなり超手数の詰みでも読み切れるようだ。

じゃあ逆に詰将棋を作成するアルゴリズムはあるのか?ということになるが、作成する方になるとさっぱりそういう話をきかない。

コンピュータが看寿賞や塚田賞を受賞したなんていう話はきいたことがない。ないよね?

十一手詰みくらいなら一瞬で解けるコンピュータも、十一手詰みの局面をつくれとなると難しいのだろうか?

ちなみに詰将棋ソルバーはやねうら王氏のレポジトリで配布されているtanukiと呼ばれるプログラムがめっぽう強い。

とりあえずこれを使っておけば実用上困ることはないだろう。

詰将棋のルール

詰将棋には以下のルールがある。

  • 先手は王手をかける
  • 後手は王手を解除する手を指す
  • 後手は最長手順になるように王手を回避する
  • 取られるだけの無駄な合駒はしない
無駄な合駒が発生する局面

8二の地点に何か駒を打てば王手は回避できるが何を合駒しても☗同銀成までで詰む。

このような合駒を無駄合いという。

詰将棋Maker

実は詰将棋作成アルゴリズム開発の試みが全くないかというとそうではないようだ。

ただしこれはランダムに局面を生成しているので、成果としてはアリなものの実用的かどうかと問われると疑問が残る。

とりあえず詰将棋をつくるアルゴリズムとして、以下のものが考えられる。

function Make(){
  while(!status){
    board.random(); // generate random sfen string
    status = board.dfpn(); // Check Mate
  }
}

要するにランダムに局面を生成し、df-pnアルゴリズムでチェックして詰んでいたら詰みと出力するわけである。

これはまあボゴソートと同様のアルゴリズムなので、極めて効率が悪い。

第一、これで生成される詰将棋の局面は全く実践で役立たない局面になっているだろう、こんなものでは役に立たない。

詰将棋には詰め上がり図の局面の美しさや手筋の美しさが重視される作品と、実践で役立つよくありそうな詰め将棋が存在します。

谷川浩司作
親の顔より見た詰将棋

もちろんどちらも解ければ嬉しいのですが、今回作成したいのは後者である実践でよくありそうな詰将棋なのです。

さて、こういう詰将棋どうやったらつくれる?

N手詰めからN+2手詰めはつくれるか

さて、ここにN手詰めの局面が与えられてソルバーがそれを(高々)N手で詰むと判断したとしよう。

九手詰み

例えば先程の美濃囲い崩しの詰将棋は九手詰みである。

ではこの局面をもとに手数を二手延ばして十一手詰みをつくるのは簡単だろうか?

一見すると簡単そうに見えるが実は、これが意外と簡単ではない。それを五手詰めを七手詰めにするための手順と共に説明したいと思う。

五手詰みのノード

さて、この局面の場合は後手がどう頑張っても五手先で詰むことがわかっているのでそれを一手伸ばすことは容易ではない。

むしろ、逆に遡って一手追加する方が楽そうに思える。

ちなみにこれを図示化すると以下のようになる。

五手詰めから七手詰め作成への概要図

まず、詰将棋のルールから五手詰め局面の一つ前は王手でないといけない。

また、後手が最善手を指さなければいけないというルールから王手に対する応手全てのノードの終端に詰みがなければならない。

本来はここが五手詰み以上になってはいけないし、なんなら五手詰めでもダメ(三手詰め以下でないといけない)なのだがそこはまあ多めに見て考慮しないことにする。

一般に将棋は一局面あたり八十ほど合法手があると言われているが、王手に対する応手であれば王手をかけている駒をとるか逃げるか合駒するしか選択肢がない。

取れる駒は三つくらいしかないだろうし、逃げる場所が七箇所もあるなんてことはないだろう。

つまり、合計するとどんなに多くても十手くらいしかないと思われる。

合駒の種類を考える問題だともっと増えるが、ここではそこまで難しい問題は考えないこととする。

せいぜい生成される局面は十程度なので十回ソルバーを走らせれば詰んでいるかは判定できる。

こう考えるとなんだかできそうな気もしてこなくもない。

王手局面生成

さて、詰将棋の手数を二手延ばすためには以下の作業をすれば良いことがわかった。

  1. あるN手詰めの局面を用意する
  2. その局面から一手前の王手がかかった局面を生成する
    1. 高々十通りくらいしかできないと思われる
  3. それぞれ局面に対する応手を考える
    1. 全ての応手についてソルバーを走らせる
    2. どれか一つでも詰みがあれば詰み

ここでキモとなるのは、一手前が必ず王手でなければいけないということである。

そして、そこから後手の応手で与えられた局面になっていなければいけないので、次の二パターンしか生成される手がないことがわかる。

  • 既に盤面にある角で王手をかけていた
    • 応手は歩で合駒
  • 玉の周りに何か駒を打ち、それをとった
    • 7二に何か打って☖同銀
      • 横に利く駒なので飛車か金
    • 8二に何か打って☖同玉
      • 斜めか横に利く駒なので飛車角金銀のどれか
    • 9四に桂馬を打って☖同歩

つまり、考えられるパターンは八通りしかないということである。

意外と詰まない

まず、角で王手をかける手は詰まないだろう。6四に適当に何かを合駒するだけでもう王手が続かないからだ。

次に、7二に何か駒を打つのも☖同銀では詰むだろうが、同玉とすれば詰まないだろう。6二の地点に逃げればこれはもう絶対に詰まない。

☗7四桂で詰む

桂馬を打つ手も7一に逃げられてダメ。大体、☗9四桂と打てる局面なら最初から☗7四桂と打てば☖9二玉に☗8二金で三手詰みである。

となると8二などの地点になにか駒を打ってそれをとったと考えるのが最もありそうである。

9二玉型でつくってみた

十五手詰み

アルゴリズムを理解するためにとりあえず手作業で詰んでいる局面を生成しました。

十一手詰みができるかと思ったら十五手詰みが完成しました。

作業としては以下のような流れです。

  1. 玉を9二玉に移動
  2. 先手の持ち駒をどんどん増やす
  3. 詰んだ時点で増やすのをやめる

持ち駒を増やし続けるのも現実的ではないので本当は盤上の駒を追加するとかちょっと位置をズラすとかでもいいと思うのですが、そっち方向は難しそうでした。

しかも変化によっては駒が余るので、詰将棋作品としては全然ダメです。

驚くべきはたった一路だけ玉の位置が違えば詰ませるのに必要な駒が金銀歩が一枚づつ余計に必要だったということです。

こう考えると美濃囲いはめちゃくちゃ強いですね。

ただ、玉が寄っていたとしてもいつでも☗7四桂があるのでそれだけは気をつけなければいけません(放置すれば詰み、取っても詰みの厳しい手です)

まとめ

手数を増やそうとすると一手前の状態を考えなければいけないがその局面が王手である必要がある。

すると、どうしても玉の位置変換のための捨て駒が初手にくる場合が多くなってします(むしろほとんどこれではないか?)

頭で考えても十分くらいでつくれたのでコンピュータなら一瞬だろうが、なんだか手数の増やし方と初手が捨て駒というのがどうも美しくない。

もっと効率的な手数の増やし方を模索したい。

まあでも最初はこのタイプの詰将棋メイカーつくるのもアリかもしれない。