実は最近、ふと「あっ、詰将棋のデータがあればいいのに！」と思うことがありました。ただ、ふだんから将棋を研究しているわけでもないので、手元に詰将棋のデータが裸で転がっているなどということがあるはずもなく……
軽い気持ちで「無いなら作ろうか」と思ったものの、詰将棋を一から考えようとすると結構難しいことがわかりました。
インターネットであれこれ検索しながら、とりあえず一手詰めの詰将棋を自動生成するプログラムを作ってみました。

調査

スマホやPC向けの詰将棋アプリはかなり昔からあります。どのアプリも、まさか詰将棋を一つ一つ人が作っているわけでもないだろうし、詰将棋を生成するアルゴリズムなんて、ネットを検索すればいくらでも出てくるだろう、なんならソースコードだって結構転がってるのではないかと思い、ザッと検索してみました。

アルゴリズム

はじめに1997年に書かれた論文が見つかりました。

『逆算法による詰将棋の自動創作』https://www.jstage.jst.go.jp/article/jjsai/13/3/13_452/_pdf

え？ 論文？
四半世紀以上前とはいえ、詰将棋を生成するアルゴリズムって、論文で論じないといけないような難しい話だったのですね。

内容は、詰み局面から手を戻して行きながら詰将棋を作るというもののようです。確かに、コンピュータで作るならこれがよさそうです。

次に、2017年のブログ記事が見つかりました。

こちらはランダムに駒を並べて詰み状態を作り出し、前出の論文と同じく、一手ずつ巻き戻して行くという流れのようです。

どうやら、アルゴリズムでいきなり詰み状態を作るのは思った以上に大変そうですが、この記事にあるようにランダムに駒を配置してみて、当たりが出るまで何度もやり直せばいいのかもしれません。人間がやると大変ですが、そのためのコンピュータですからね。

ざっと調べてみて、将棋のアルゴリズムはいろいろ研究されているようですが、詰将棋を作るアルゴリズムについては思ったよりも情報が少ないようです。

データ構造

さて、将棋盤のマスや駒のデータをどう設計したものでしょうか。
そういえば昔、BASIC全盛期の頃、よく将棋プログラムの作り方がコンピュータ関連雑誌に掲載されていた記憶があります。あの頃ちゃんと読んでおけばよかったなぁ、などと思いながら、将棋盤のクラスをPythonで書きはじめたのですが、いやいや、こんなの絶対いろんな人が無数に作ってるはずだし、よく探せばライブラリが公開されてるんじゃないの？ と思い直し、インターネットで検索してみました。

cshogi というライブラリが見つかりました。

Jupyter Notebook に盤面のイメージが表示できるようなので何かと便利そうです。
ふだん Python でプログラムを書くときは VSCode 上の Jupyter Notebook を使うことが多いので、筆者の開発環境ともマッチしています。これをそのまま使わせていただきましょう。

pip でインストールします。

pip install cshogi

開発

詰み局面の作成

当初、どうやってランダムに盤面上に駒をばらまこうかと考えたのですが、cshogi を使えば、そんなことは考えなくていいことがわかりました。
cshogi では、現状の局面で将棋のルール上合法な指し手のリストを得ることができます。ここから繰り返しランダムに指し手を選んで行くだけで確実に詰み局面を作成できることに気付きました。
このあたりを一から作るとなるとかなり面倒なので、cshogi ライブラリを使って正解だったなと実感しました。

下のプログラムを Jupyter Notebook 上で動かすと、詰み状態の盤面が生成されます。

import cshogi
import random
from IPython.display import display
from kanjize import number2kanji

# 初期局面生成
board = cshogi.Board()

while(True) :
    if board.turn == cshogi.BLACK :
        player = '先手'
    else :
        player = '後手'
    movnum = board.move_number # いま何手目か
    ran = random.randrange(len(list(board.legal_moves))) # 合法手の数に合わせた乱数を生成
    lastmove = list(board.legal_moves)[ran] # 指し手を決定
    board.push(lastmove) # 一手指す

    # 入玉は詰将棋に向かないと思うので、入玉したらリセットしてはじめからやり直し
    if board.is_nyugyoku() == True :
        board.reset()
    # 詰み局面になったら終了
    elif board.is_game_over() == True :
        break

# 結果の表示
display(board)
print('終局')
print(f'{movnum}手で{player}の勝ち')

mfrom = cshogi.move_from(lastmove)
mto = cshogi.move_to(lastmove)
if cshogi.move_is_drop(lastmove) == True :
    print('From: 持ち駒')
else :
    print('From:', mfrom // 9 + 1, number2kanji(mfrom % 9 + 1))
print('To:', mto // 9 + 1, number2kanji(mto % 9 + 1), end='')
if cshogi.move_is_promotion(lastmove) == True :
    print(' 成')
    promotion = True
else :
    promotion = False

実際に将棋を指しているのは上半分の while ループの中です。下半分で結果を表示しています。
結果はこんな感じに表示されます。

先手・後手、共に合法手ではあるものの、双方ランダムに指しているので何手で終わるかは予想できません。しかし、乱数を発生しているだけで何の思考ルーチンも回していないので1000手や2000手なら一瞬で終わります。ランダムに指しているのですから千日手も気にする必要はなく、あっという間に詰み局面にたどり着きます。

また、指し手を簡易的に表示するとき int型から漢数字に変換するために、Kanjize というライブラリを使っています。これは便利！

こちらも pip でインストールできます。

pip install kanjize

盤面を180度回転

ランダムに駒を進めているので、先手が勝ったり後手が勝ったりするのですが、後手が勝った局面のまま詰将棋にしてしまうと、盤面がひっくり返ってしまうので、後手の勝ちで終了した場合、盤面を180度回転させて先手と後手を入れ替えます。

from copy import deepcopy

if board.turn == cshogi.BLACK :
    pieces_tmp = board.pieces.copy()
    pieces_in_hand_tmp = deepcopy(board.pieces_in_hand)

    # 位置はそのまま、各駒の先手と後手を入れ替える
    for num in range(81) :
        if pieces_tmp[num] != 0 :
            if pieces_tmp[num] >= cshogi.WPAWN :
                pieces_tmp[num] = pieces_tmp[num] - cshogi.WPAWN + 1
            else :
                pieces_tmp[num] = pieces_tmp[num] + cshogi.WPAWN - 1

    # 180度回転
    pieces_tmp.reverse()
    lastmove = cshogi.move_rotate(lastmove) # 最後の手の座標も回転させておく

    # 回転後の盤面生成
    board.set_pieces(pieces_tmp, (pieces_in_hand_tmp[1], pieces_in_hand_tmp[0])) # 持ち駒を先手/後手入れ替える
    board.turn = cshogi.WHITE

# 結果の表示
display(board)

mfrom = cshogi.move_from(lastmove)
mto = cshogi.move_to(lastmove)
if cshogi.move_is_drop(lastmove) == True :
    print('From: 持ち駒')
else :
    print('From:', mfrom // 9 + 1, number2kanji(mfrom % 9 + 1))
print('To:', mto // 9 + 1, number2kanji(mto % 9 + 1), end='')
if promotion == True :
    print(' 成')

結果はこんな感じ

指し手もちゃんと180度回転しています。

詰みに関係のない駒をはずす

詰んだ状態を維持しつつ関係のない駒をはずして、はずした駒は「王」以外すべて後手の持ち駒にします。

盤上の各マスを順番に見て、駒があったら消してみて、詰んでいるかどうかチェックし、詰んでいたらそのまま。詰んでいなかったら元に戻す。という作業を全マスについて繰り返します。

from copy import deepcopy

# pice_type を、hand_piecesに変換する
hand_pieces_to_pice_type_list = []
for hp in range(cshogi.HPAWN, len(list(cshogi.HAND_PIECES))) :
    hand_pieces_to_pice_type_list.append(cshogi.hand_piece_to_piece_type(hp))

def piece_type_to_hand_piece(piece_type) :
    return hand_pieces_to_pice_type_list.index(piece_type)

pieces_tmp = board.pieces.copy()
pieces_in_hand_tmp = deepcopy(board.pieces_in_hand)

board_tmp = cshogi.Board()
for num in range(len(pieces_tmp)) :
    # 盤面の駒を順に
    if board.piece_type(num) != cshogi.NONE and board.piece_type(num) != cshogi.KING :
        # 駒の種類を調べる
        ptype = board.piece_type(num)
        if ptype >= cshogi.PROM_PAWN :
            ptype = ptype - cshogi.PROM_PAWN + 1
        # 調べた駒を持ち駒の種類に合わせる（PAWN → HPWAN）
        hptype = piece_type_to_hand_piece(ptype)

        ptype_tmp = pieces_tmp[num] # 戻す時のために駒を一時保存
        pieces_tmp[num] = cshogi.NONE # 今の場所から消す

        # 後手の持ち駒に加える
        pieces_in_hand_tmp[cshogi.WHITE][hptype] = pieces_in_hand_tmp[cshogi.WHITE][hptype] + 1

        board_tmp.set_pieces(pieces_tmp, pieces_in_hand_tmp) # 新盤面の作成
        board_tmp.turn = cshogi.WHITE # ターンを後手番にする
        
        if board_tmp.is_game_over() != True :
            # 王手になっていなかったら戻す
            pieces_tmp[num] = ptype_tmp
            pieces_in_hand_tmp[cshogi.WHITE][hptype] = pieces_in_hand_tmp[cshogi.WHITE][hptype] -1

    elif board.piece(num) == cshogi.BKING :
        # 先手の王は消す
        pieces_tmp[num] = cshogi.NONE

        board_tmp.set_pieces(pieces_tmp, pieces_in_hand_tmp) # 新盤面の作成
        board_tmp.turn = cshogi.WHITE # ターンを後手番にする

        if board_tmp.is_game_over() != True :
            # 王手になっていなかったら戻す
            pieces_tmp[num] = cshogi.BKING



# 先手の持ち駒はすべて後手の持ち駒に移す
for num in range(len(cshogi.HAND_PIECES)) :
    pieces_in_hand_tmp[cshogi.WHITE][num] += pieces_in_hand_tmp[cshogi.BLACK][num]
    pieces_in_hand_tmp[cshogi.BLACK][num] = 0

board_tmp.set_pieces(pieces_tmp, pieces_in_hand_tmp) # 新盤面の作成
board_tmp.turn = cshogi.WHITE # ターンを後手番にする

# 結果の表示
display(board_tmp) # 詰み状態

mfrom = cshogi.move_from(lastmove)
mto = cshogi.move_to(lastmove)
if cshogi.move_is_drop(lastmove) == True :
    print('From: 持ち駒')
else :
    print('From:', mfrom // 9 + 1, number2kanji(mfrom % 9 + 1))
print('To:', mto // 9 + 1, number2kanji(mto % 9 + 1), end='')
if promotion == True :
    print(' 成')

かなり駒が減ってスッキリします。

盤上から消した駒は「王」以外の駒をすべて後手の持ち駒にするのですが、この処理でちょっとした罠にハマってしまいました。

cshogi ライブラリの中で、駒の種類を表す定数（PIECE_TYPES）と、持ち駒を表す定数（HAND_PIECES）は別々に宣言されています。

HAND_PIECES から PIECE_TYPES に変換するには、cshogi.hand_piece_to_piece_type() という関数が準備されています。
今回必要なのはこの逆、PIECE_TYPES を HAND_PIECES に変換したいのですが、これに対応する関数が見つかりませんでした。

何か上手い方法はないものかと探していると、定数の宣言部分が cshogi のドキュメントに載っているのを見つけました。

PIECE_TYPES の宣言部分はこうです。

PIECE_TYPES_WITH_NONE = [
        NONE,
        PAWN,      LANCE,      KNIGHT,      SILVER,
        BISHOP,       ROOK,
        GOLD,
        KING,
    PROM_PAWN, PROM_LANCE, PROM_KNIGHT, PROM_SILVER,
    PROM_BISHOP,  PROM_ROOK,
] = range(15)

PIECE_TYPES = [
        PAWN,      LANCE,      KNIGHT,      SILVER,
        BISHOP,       ROOK,
        GOLD,
        KING,
    PROM_PAWN, PROM_LANCE, PROM_KNIGHT, PROM_SILVER,
    PROM_BISHOP,  PROM_ROOK,
]

先に PIECE_TYPES_WITH_NONE で、NONE を 0 で宣言して、PIECE_TYPES で　PAWN 以降を切り出しているので、PAWN（歩）が 1、KING（王）が 8 になります。

対して、HAND_PIECES はこうです。

HAND_PIECES = [
        HPAWN,     HLANCE,     HKNIGHT,     HSILVER,
        HGOLD,
        HBISHOP,      HROOK,
] = range(7)

NONE がなく、HPAWN（持ち駒の歩）は 0 からはじまって、HROOK（持ち駒の飛）が 6 で終わっています。

PIECE_TYPES の駒は、成り状態の駒を除けば PAWN から KING までの８種類。
普通の将棋では KING が持ち駒になることはないので、HAND_PIECES 側に HKING はない。だから、HAND_PIECES は０～６の７つしかない。また、HAND_PIECES が表しているのは駒そのものではなくて駒の入れ物なので NONE は必要ない。ああ、だから定数の値が一つずつずれているのだなと理解しました。

つまり、PIECE_TYPES から HAND_PIECES に変換するためには、盤上の駒をつまみ上げて KING 以外なら 1 引いてやればいい。例えば PAWN だったら、1 引いてやれば HPAWN になるのだと理解したわけです。

とはいえ、定数宣言されているものをソースコードにいきなり

hand_pieces =  piece_types - 1

とするのはちょっと野暮だなと思い、

hand_pieces =  piece_types - ( cshogi.HPAWN - cshogi.PAWN )

としていたのですが、これがどうもうまく動かない。
盤上の駒を持ち駒に戻すと、ときどき駒の種類が変わってしまうのです。

上手くいくときもあるので何度もソースを見直してもなかなか原因がわかりません。
何かを見落としているなと思いながら、何気にドキュメントを見直すと、なんと、PIECE_TYPES と HAND_PIECES では、GOLD（金）の位置が、全く違うことに気付きました。

表にするとこんな感じです。

なるほど、PIECE_TYPES では、成る駒と成らない駒を分けておいた方が便利なので「金」を「王」に並べたのですね。
片や HAND_PIECES では、「金」は「銀」の横にあった方が馴染みが良いということなのでしょうか？

仕方ないので上記のソースコードでは、PIECE_TYPES から HAND_PIECES に変換する関数 piece_type_to_hand_piece(piece_type) を作っています。
下記の部分です。

# pice_type を、hand_piecesに変換する
hand_pieces_to_pice_type_list = []
for hp in range(cshogi.HPAWN, len(list(cshogi.HAND_PIECES))) :
    hand_pieces_to_pice_type_list.append(cshogi.hand_piece_to_piece_type(hp))

def piece_type_to_hand_piece(piece_type) :
    return hand_pieces_to_pice_type_list.index(piece_type)

せっかく既に hand_piece_to_piece_type() があるので、これを使って逆変換用のリストを生成しています。

一手戻して詰将棋にする

さて、少し回り道はしたものの、とりあえず詰将棋の解答にあたる局面ができたので、一手戻して詰将棋の問題を生成します。

最後に指した手は覚えているので、この駒をどこかに動かして、詰み状態を解除してやれば詰将棋の完成です。
後々、三手詰めに拡張することを考えれば、該当の駒をどこに戻すべきか盤上を探索するべきかなとも思いましたが、今回は超手抜きで、元々覚えている指し手の通り、一手前のマスに戻すことにします。

pieces_new = board_tmp.pieces.copy()
pieces_in_hand_new = deepcopy(board_tmp.pieces_in_hand)

# 最後に成っていた場合は、一手前の状態に戻す
if promotion == True :
    last_ptype_1 = board.piece_type(mto) - (cshogi.PROM_PAWN - cshogi.PAWN)
else :
    last_ptype_1 = board.piece_type(mto)

pieces_new[mto] = cshogi.NONE # 最後に指したマスの駒を消す

# 一手前のマスに駒を置く
# 持ち駒だった場合は先手の持ち駒に戻す
if cshogi.move_is_drop(lastmove) == True :
    
    pieces_in_hand_new[cshogi.BLACK][piece_type_to_hand_piece(last_ptype_1)] += 1
else:
    pieces_new[mfrom] = last_ptype_1

board_new = cshogi.Board()
board_new.set_pieces(pieces_new, pieces_in_hand_new)

# 問題の表示
print('【問題】')

display(board_new)

続けて解答を表示するコードも書いておきます。
こちらは、元々の詰み状態の盤面を表示するだけですが、駒の元の位置と駒の種類、指した後の位置と成ったかどうかも含めて表示して解答としました。

# 解答の表示
print('【解答】')

display(board_tmp) # 詰み状態

# 最後の手

PIECE_TYPES_KANJI = [
        'NONE',
        '歩', '香', '桂', '銀',
        '角','飛',
        '金',
        '王',
        'と', '成香', '成桂', '成銀',
        '馬', '龍'
]

mfrom = cshogi.move_from(lastmove)
mto = cshogi.move_to(lastmove)
if cshogi.move_is_drop(lastmove) == True :
    print('From: 持ち駒', end=' ')
else :
    print('From:', mfrom // 9 + 1, number2kanji(mfrom % 9 + 1), end=' ')
print(PIECE_TYPES_KANJI[last_ptype_1])

print('To:', mto // 9 + 1, number2kanji(mto % 9 + 1), end=' ')
if promotion == True :
    print('成')

これでとりあえず、一手詰めの詰将棋の問題と解答が量産できるプログラムができました。

ただ、お気づきの方も多いと思いますが、６一にある「と金」が７一に寄っても詰むので、答えが２つありますね。
どうやら、答えが複数あるのは「余詰め」といって詰将棋としてはあまりよくない様子。
ただ、これをアルゴリズムで避けるのはちょっと面倒。
一手詰めだと、問題を作ってしまってから解答が複数あるかどうかを検査するのが妥当な気がします。
このあたりは今後の改良ポイントかもしれません。

あと、指し手の表記法が日本将棋連盟で決められているものと違います。
勝手な表記になっていて気持ち悪いという方には申し訳ありません。日本将棋連盟の表記法に沿ったものにしようとすると、同じマスに複数の同じ駒が動けるかなど、盤面にある駒をサーチしないと正しく表記できないので、ひとまずこれでご勘弁を。

まだまだ改良すべき箇所は残っているものの、とりあえず、これで一手詰め詰将棋量産プログラムは完成とします。
更にこの後、三手詰めに進むかどうかは、今後の気分次第ということで。😆