はじめに

こんにちは、社会人2年目エンジニアのYmmyです。週末の時間を有効活用すべく、この土日はPythonとFlaskを使って「挟み将棋」のWebアプリを作っていこうと思います。

挟み将棋とは（ご存じの方も多いと思いますが...）

盤上の自分の駒を動かし、相手の駒をはさんで取るゲームで、将棋の簡易版とも言えます。
ルールがシンプルなので、プログラムの題材として選びました。

盤面：9×9の正方形
勝利条件：先に相手の駒を5つとる or 相手の駒と3枚差をつける
駒の初期配置：各プレイヤーが自分の駒を横一列に配置
駒の動き方：タテヨコに好きなだけ動かせる。ただし、自分や相手の駒を飛び越えることはできない

詳細ルールは以下をご参照
日本将棋連盟TOP > 将棋の基礎知識 > はさみ将棋をやってみよう

使用した技術

言語：Python 3.9
フレームワーク：Flask
フロントエンド：tailwindcss

完成物

苦戦したこと

ルールがシンプルなので

と思っていましたが、いざ実装すると頭を捻らないといけないルールがありました。
盤面の端にある相手の駒を自分の駒および壁で閉じ込めた場合駒を取ることができる、というルールです。

簡単な例をあげると、盤面の角に相手の駒があり、自分の駒と壁で相手の駒を囲っている場合です。

PLAYER = 1
ENEMY = 2
EMPTY = 0

board = [
    [2, 1, 0, ...],
    [1, 0, 0, ...],
    [0, 0, 0, ...], ...
]

この場合、角の座標をもとに上下左右を自分の駒と壁で挟んでいるかを検証する処理が必要です。

def is_wall(y, x):
    return y < 0 or 8 < y or x < 0 or 8 < x

def check_surround(board, y, x):
    if (board[y][x] == ENEMY):
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dy, dx in directions:
            if not is_wall(y + dy, x + dx) and board[y + dy][x + dx] != PLAYER:
                return False # 壁または自分の駒で囲めていない
        return True # 相手の駒の上下左右を囲めている
    return False

edges = [(0, 0), (0, 8), (8, 0), (8, 8)]
for (y, x) in edges:
    if check_surround(board, y, x):
        board[y][x] = EMPTY

もっとも、囲っている駒が必ずしも盤面の角にあるとは限りません。
盤面の辺で囲っている場合も考慮が必要です。

[
    [1, 2, 1, ...],
    [0, 1, 0, ...],
    [0, 0, 0, ...], ...
]

改修する箇所は、edges = [(0, 0), (0, 8), (8, 0), (8, 8)] で検証対象を角のみと指定していたところを、全ての辺に拡張する点です。

edgesに全ての辺の座標を定義する方法もありますが、辺の数が多いため、二重のfor文で実装します。

def is_on_edge(y, x):
    return y == 0 or y == 8 or x == 0 or x == 8

for y in range(9):
    for x in range(9):
        if is_on_edge(y, x) and check_surround(board, y, x):
            board[y][x] = EMPTY

ここまでは、さほど複雑な処理は必要ないと思います。

ここからが複雑になります...

囲まれている相手の駒が複数の場合の考慮が必要です。

[
    [2, 2, 1, ...],
    [2, 1, 0, ...],
    [1, 0, 0, ...], ...
]

この場合、これまで作成した「一つの駒に対して上下左右を自分の駒で囲っているか」という処理では、相手の駒を囲えているかの検証ができません。
相手の駒同士が隣り合っているため、一つの駒の上下左右全てが壁または自分の駒にはなっていないためです。

というわけで、割と大きめの改修が必要です。

複数の駒の場合の処理を実装する上での手順およびポイントは以下になります。

辺に隣接した相手の駒のグループを見つけること
グループ化した駒が囲まれているか検証すること

まずは相手駒のグループを見つける処理を作成します。

処理の流れ

盤面の全てのマスを走査する
対象マスが盤面の辺かつ敵の駒があれば、対象マスを基点にグループを探す

def get_adjacent_positions(y, x):
    """指定した位置の上下左右の隣接マスを取得"""
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    adj = []
    for dy, dx in directions:
        yy, xx = y + dy, x + dx
        if 0 <= yy < 9 and 0 <= xx < 9:
            adj.append((yy, xx))
    return adj

visited = [[False for _ in range(9)] for _ in range(9)]
groups = []
for y in range(9):
    for x in range(9):
        if is_on_edge(y, x) and board[y][x] == ENEMY and not visited[y][x]:
            queue = [(y, x)]
            group = []
            visited[y][x] = True
            while queue:
                current = queue.pop(0)
                group.append(current)
                for adj in get_adjacent_positions(current[0], current[1]):
                    ay, ax = adj
                    if board[ay][ax] == ENEMY and not visited[ay][ax]:
                        visited[ay][ax] = True
                        queue.append((ay, ax))
            groups.append(group)

補足・解説

get_adjacent_positions(y, x)：
隣接する上下左右のマスの座標を取得する関数です。ポイントは盤面外（壁）の座標を返さないという点です。有効座標のみ返すことで、「そのマスは壁か」という処理が不要になります。
visited：
全マスに対して１マス毎にグループ化できるか検証する都合、同じマスを何度も確認することになり、計算量が増えてしまいます。そのため、一度検証してグループ化されたマスは、何度も検証されることのないようにフラグを設定します。
queueとgroup：
いずれもグループ化するマスを格納する変数ですが、それぞれ役割があります。queueの目的はグループ化できるマスを探すことで、一方groupは名の通りグループ化したマスを格納することが目的です。そのため、queueは隣接マスをグループ化できるか未検証となっているマスを格納し、groupは隣接マスの検証を実施したマスを格納します。
while quete: ...：
このwhileループが、グループ化するメインの処理になります。未検証の隣接マス（queueに格納されているマス）がなくなったタイミングでwhileループを抜け、グループ化が完了します。この処理は幅優先探索（BFS）と呼ばれます。

グループ化できたので、次のステップはグループ化した駒を囲えているか検証します。

処理の流れ

グループ化したマスそれぞれの隣接マスを取得
①の隣接マスがグループを囲うマスとなっている場合、自分の駒が配置されているか検証

def is_group_enclosed(group, board):
    """グループが自分の駒で囲まれているかを判定"""
    for (y, x) in group:
        adj = get_adjacent_positions(y, x)
        for (ay, ax) in adj:
            if board[ay][ax] == ENEMY and (ay, ax) not in group:
                # グループ外に相手の駒がある場合は囲まれていない
                return False
            elif board[ay][ax] == EMPTY:
                # 空マスがある場合も囲まれていない
                return False
    return True

for group in groups:
    if is_group_enclosed(group, board):
        for (y, x) in group:
            board[y][x] = EMPTY

補足・解説

ポイントは次のif文です！

if board[ay][ax] == ENEMY and (ay, ax) not in group:
    # グループ外に相手の駒がある場合は囲まれていない
    return False

グループ外に相手の駒がある場合は囲まれていない

コメントを逆説的に言うと、検証対象のマスが相手の駒であってもgroupの一員であればグループを囲うマスではないため、検証対象外となります。

このif文があるおかげで、複数の相手の駒を囲っている場合でも正しく囲いの判定ができるようになります。

以上で処理の解説は終わりです。お疲れさまでした。

最後に

実装したソースコードは以下のGitHubで公開しています。

Webアプリで使用するため、HasamiShogiクラスに書き換えていますが、処理内容に変更はないです。

見切り発車で設計せずにいきなり実装を始めると、考慮漏れが次々出てきて、最終的には原型が残っていない状況に陥りました。反省です。
次は相手AIの作成に挑戦しようと思います。どうしてもモデルの学習時間が必要になるため土日だけで完成できるか難しいところではありますが...