More than 1 year has passed since last update.

リバーシの最短全滅手順を幅優先探索であぶり出す！

Last updated at 2023-05-09Posted at 2023-05-05

はじめに

どうも、y-tetsuです。

以前、自作のリバーシ(オセロ)ライブラリを使って、全消し(全滅)パターンを探していた者です。

前回は8x8の64マス全てが一色に染まる棋譜を見つけたのですが、今回は最短で全滅となる棋譜を探してみたいと思います。

ところがこのパターン、実は以下のサイトで、既に紹介されておりますっ！！

なんと、黒手番の場合は最短9手、白手番の場合は最短10手で、相手を全滅させることができるそうです。なので、始める前からもう答えは出ちゃってますね…。

…なんですが、ここで、「はいそうですか」と素直に引き下がれないのが、下手にリバーシのプログラミングに覚えを持ってしまった、私の悲しい？性。今回の記事では、この最短全滅パターンを幅優先探索を用いたプログラムにより、「実際」に確かめてみたいと思います！

全探索アルゴリズムについて

全滅パターンを探すには、プログラムにて何かしらの指標に基づいて探索を行う必要があります。加えて、特定のパターンを間違いなく見つけ出すためには、全ての通りをもれなく探せる全探索を、概ね行う事になると思います。

全探索アルゴリズムには、大きく「深さ優先探索」と「幅優先探索」の2つがあります。

深さ優先探索と幅優先探索の違いを簡単に言うと、以下のようになります。

深さ優先探索 … 探索できる一番深いところまで一旦調べたのち、少しずつ戻っては探索を進めて、最終的に全てを探索する手法
幅優先探索 … 探索の開始地点から1歩進めるところをまず調べ切った後、2歩進めるところを調べて、終わったら次に3歩目…と徐々に探索を深くし、最終的に全てを探索する手法

詳細につきましては、すでにいくつかのサイトや記事で優れた解説がされていますので、以下などに説明を譲らせていただきたいと思います。(本記事の説明はリバーシに特化した内容となっております)

一般的に、リバーシではコンピュータAIが手を読むために局面(盤面)の探索を行います。その際は、ミニマックス法やアルファ・ベータ法といったアルゴリズムがよく紹介されます。これらはいずれも深さ優先探索をベースにしたものです。

先ほどの簡単な説明に従うと、一旦、元の局面から決まった手数(例えば8手先)まで手を進め、形勢判断を行います。その後、そこから1手戻ってはまだ調べていない別の手を打ってみて、その局面の形勢判断をし、すべて調べたら今度は2手戻ってまだ調べていない手を打ってみて…という事を、すべての局面を調べ切るまで繰り返します。最終的にAIは、その中から最も有利な局面に繋がりそうな1手を打ちます。

このような深さ優先探索が主に用いられるのは、例えば、自分だけでなく相手も最善を尽くした場合の局面の評価に向いていたり、探索中の1手が明らかに悪手だと分かった時点で、それ以降の探索をスキップ(枝刈り)できたり、などが理由に挙げられると思います。

ところが、今回はリバーシの強い手を読みたいのではなく、最短の全滅パターンを見つけたいのでした。ということで、待ってましたー！とばかりに幅優先探索の出番、という訳です。

幅優先探索をリバーシで使う

幅優先探索(BFS：Breadth-first search)ではキューと呼ばれる、先入れ先出し(FIFO：First-In-First-Out)を行うデータ構造を用います。

キューには、探索の順番待ちをしているリバーシの局面をどんどん追加していくのですが、最初に処理されるのは先に入ったものからというルールで動きます。

探索手順

それでは、幅優先探索を用いて、リバーシの最短全滅パターンを求める手順を示します。基本的に全滅パターンが見つかるまで、以下を繰り返します。

①キューに初期の局面をセットする

②現在の局面をキューの先頭から取得する

③取り出した局面が全滅パターンか調べる

④全滅パターンの場合は、そこで終了

⑤全滅パターンではない場合、打てる手をすべて見つける

⑥打てるところに手を打った局面を、それぞれキューに追加する(ただし、既定の手数に達した場合は追加しない)

⑦②～⑥を全滅パターンが見つかるか、キューが空になるまで繰り返す

※図は簡単のため4x4の盤面を例に示しております

このように、1手目の全パターンをチェックした後、2手目の全パターン、次に3手目の全パターン・・・と調べ上げていくため、最初に全滅パターンが見つかった手数が「すなわち最短手数」となる事が、お分かりいただけたのではと思います。

リバーシにおける「深さ優先・幅優先」探索の深さ方向は、言い換えると何手先まで局面を進めるか？を表し、幅方向は、どの手を打つか？を表す、というイメージを持っていただけたら、もう勝ったようなものです！！

探索の一工夫

今回調べたい全滅パターンの最短手順は、黒番で9手、白番で10手とあらかじめ分かっております。

リバーシの1局面につき、打てる手の数はだいたい10手程度と見込まれているようです。これを元にすると、黒番の最短9手を全て調べ上げようとした場合、単純計算で10億通り(10^9)もの局面を調べなければならないことになります。これはちょっと大変ですね…。

何か打てる手(リバーシだけに…)はないかと考えたところ、以下の元の局面の反転形と回転形を同一とみなせば、類似の探索をスキップできそうです。

(元の局面)

(A1H8ラインの斜め反転形)

(A8H1ラインの斜め反転形)

(180°回転形)

少しでも結果が早く出て欲しいです。是非入れておきましょう！(理想的には探索数が、1/8(2^-3)程度になってるといいのですが…)

最短全滅パターンの探索

それではいざ、最短全滅パターンの探索に向かいましょう！

reversiのインストール

例によって、拙作のリバーシライブラリreversiを使います。

事前にPython 3.7.6をインストールし、以下のコマンドを実行してください。

$ py -3.7 -m pip install git+https://github.com/y-tetsu/reversi

Python3.7以降でも問題なく動くと思いますが、その際はCythonのコンパイルの関係で、Microsoft Visual C++のインストールを併せて実施願います。

探索コード

インストールしたライブラリを使って、最短9手の全滅パターンを探索するコードを示します。コードの解説は後に回しますので、興味がある方は最後の方を御覧下さい。

min_reversi.py

from collections import deque

from reversi import BitBoard
from reversi import C as c
from reversi import Move, UPPER, LOWER

from util import flip_diagonalA1H8, flip_diagonalA8H1, rotate180, popcount


C2N = {c.black: 0, c.white: 1}
N2C = {0: c.black, 1: c.white}

MAX_DEPTH = 9  # 探索手数の上限


def bfs(board_info):
    # 探索キュー
    frontier = deque()
    frontier.append(board_info)

    # 探索済み
    explored = {}
    explored[board_info[:3]] = True

    # 最短の全滅パターン
    perfect_win = []

    # 幅優先探索
    while frontier:
        # キューの先頭を取得
        child = frontier.popleft()

        # ゴールの判定
        if is_goal(child, perfect_win):
            return perfect_win

        # 子を元に次の探索対象をチェック
        for next_info in successors(child):
            # 探索済みの場合はスキップ
            if next_info[:3] in explored:
                continue

            # 探索済みを記憶
            add_explored(next_info, explored)

            # キューの後ろに追加
            frontier.append(next_info)

    print('\n--- no frontier ---')
    return perfect_win


def is_goal(board_info, result):
    _, bb, wb, record = board_info

    # 黒か白どちらかが全滅の場合は格納
    if bb == 0 or wb == 0:
        board = BitBoard(ini_black=bb, ini_white=wb)
        result.append((board, record))
        print()
        print(f'*** perfect win {len(result)} ***')
        print(board)
        print(record)
        return True

    return False


def successors(board_info):
    color, bb, wb, record = board_info

    # 最大手数に到達したら探索終了
    depth = popcount(bb) + popcount(wb) - 4
    if depth >= MAX_DEPTH:
        return []

    # 次に打てる手を全て取得
    turn = N2C[color]
    board = BitBoard(ini_black=bb, ini_white=wb)
    moves = board.get_legal_moves(turn)

    # パスの場合は手番を入れ替える
    if not moves:
        turn = c.white if turn == c.black else c.black
        moves = board.get_legal_moves(turn)
        # どちらもパスの場合は終了
        if not moves:
            return []

    # 次の盤面を取得
    next_turn = c.white if turn == c.black else c.black
    next_boards = []
    for move in moves:
        # 一手打つ
        board.put_disc(turn, *move)

        # 棋譜生成
        case = UPPER if turn == c.black else LOWER
        next_record = record + str(Move(*move, case=case))

        # 次の盤面情報を追加
        bb, wb, _ = board.get_bitboard_info()
        next_boards.append((C2N[next_turn], bb, wb, next_record))

        # 盤面を元に戻す
        board.undo()

    return next_boards


def add_explored(board_info, explored):
    color, bb, wb, _ = board_info

    # 元の盤面を記憶
    explored[(color, bb, wb)] = True

    # A1H8反転を記憶
    explored[(color, flip_diagonalA1H8(bb), flip_diagonalA1H8(wb))] = True

    # A8H1反転を記憶
    explored[(color, flip_diagonalA8H1(bb), flip_diagonalA8H1(wb))] = True

    # 180°回転を記憶
    explored[(color, rotate180(bb), rotate180(wb))] = True


if __name__ == '__main__':
    from datetime import datetime

    start = datetime.now()
    print('start', start.strftime('%Y/%m/%d %H:%M:%S'))

    board = BitBoard()
    bb, wb, _ = board.get_bitboard_info()
    board_info = (C2N[c.black], bb, wb, "")

    # 幅優先探索で最短全滅パターンを探す
    perfect_win = bfs(board_info)

    print()
    with open('result.txt', 'w') as f:
        for i, (board, record) in enumerate(perfect_win, 1):
            f.write("\n")
            f.write(f'*** perfect win {i} ***\n')
            f.write(str(board) + "\n")
            f.write(record + "\n")

    end = datetime.now()
    print('end  ', end.strftime('%Y/%m/%d %H:%M:%S'))
    elpsed = end - start
    print('elp  ', elpsed)

9手先で全滅パターンを見つけたら、探索を終了し盤面と棋譜を残します。

util.pyはユーティリティのコードで、盤面の反転や回転、2進数のビットが1の個数を数えるための関数などが入っています。こちらも説明は後回しにします。

(実行方法)

py -3.7 min_reversi.py

実行環境

Windows10 64bit
ディスプレイサイズ 1366x768 以上
プロセッサ 1.6GHz 以上
メモリ 4.00GB 以上

実行結果

コード実行後、カレントフォルダにresult.txtが作成されます。以下のような記載がされていると思います。(筆者の環境で、大体1分20秒ほどかかりました)

*** perfect win 1 ***
   a b c d e f g h
 1□□□□〇□□□
 2□□□〇□□□□
 3□〇〇〇〇□□□
 4□□□〇〇〇□□
 5□□□〇〇□□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

D3c3B3d2E1d6D7e3F4

最終盤面の様子と、棋譜が記載されています。

早速、この棋譜の進行を見てみましょう。

たしかに！今確かに、黒が白を全滅させました！無事、黒による最短9手の全滅パターンが見つかりましたっ！！

……が、…ちょっと待って下さい。参考にしたサイトの結果と、なんか違うようですね。「左右対称のきれいな形になる」との事でしたが、全然違いますねぇ！！

最短全滅パターンの探索2

どうやら、最短9手のパターンは1つだけではないようです。

探索コード

ということで、こうなったら最短9手の全パターンを見つけてやろうじゃありませんか！

以下をコメントアウトして下さい。これにより、9手で見つかる全パターンを探すようになります。

min_reversi.py

def is_goal(board_info, result):
    _, bb, wb, record = board_info

    # 黒か白どちらかが全滅の場合は格納
    if bb == 0 or wb == 0:
        board = BitBoard(ini_black=bb, ini_white=wb)
        result.append((board, record))
        print()
        print(f'*** perfect win {len(result)} ***')
        print(board)
        print(record)
        # ↓↓↓行コメントアウト
        #return True

    return False

端的に、元は全滅パターンが見つかった瞬間、処理終了としていたところを、変更後は終了させないようにしました。

実行結果

こちらも大体1分20秒ほどで結果が得られると思います。

今回対応した、反転と回転を除外した場合、全部で36通りの全滅パターンが見つかりました。無事、きれいなひし形のパターンもあぶり出せましたよ！！

:
:

*** perfect win 34 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□〇□□□□
 3□□〇〇〇□□□
 4□〇〇〇〇〇□□
 5□□〇〇〇□□□
 6□□□〇□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c5D6c3B4e3D2c4F4

:
:

今回のコードで最短9手を探索した場合、反転や回転の同形パターンを除くと、全部で516,133局面ありました。同形パターンを除外しない場合は、2064,245局面でした。目標の1/8には及びませんでしたが、1/4程度と割と狙い通り？探索数を減らせていたようです。(実行時間も、だいたい1/4程度となっていました)

黒手番の9手全滅パターンの手順は「57通り」との記事もお見かけし、一応確認してみました。どうもこれは初手を"F5"で固定し、同一局面のスキップを一切行わない場合の結果のようです。条件を合わせてみると、本プログラムの探索ロジックでも、同じく「57通り」という結果が得られました。(詳しくは、最短全滅手順57通りをあぶり出すにまとめました。)

後日談ですが、対称形や反転形のスキップで実行時間を1/4に削減できた理由は、単に4つある初手を1つに絞れたことによる所が大きいようです。よく確認してみると、同形スキップで探索数は削減できていても、結局記憶した局面との一致確認にそれなりの時間を要するようで、あまり改善効果は見られない結果でした。今回の探索の一工夫としては、単に初手F5で固定しておくだけでよかったようです…。

最短全滅パターンの探索3

さて、残るは白手番の最短10手の全パターンです。

探索コード

もうおわかりですね？以下のMAX_DEPTHを、9から10に変えて実行して下さい。

min_reversi.py

MAX_DEPTH = 10  # 探索手数の上限

実行結果

大体15分ぐらいお時間いただければ、結果が得られると思います。

結構な実行時間を要して申し訳ないですが、白の最短10手もしっかりあぶり出せました！！

最終的に、黒手番の最短9手が36通り、白手番の最短10手が28通り見つかりました。計64通りと、リバーシのマス目の数と奇跡的に一致しています！運命を感じずにはいられませんねっ！！せっかくなので、記念に全て載せておきます。(折り畳んでいます。内容間違ってたらゴメンナサイ…)

最短9+10手の全滅手順(64通り)

*** perfect win 1 ***
   a b c d e f g h
 1□□□□〇□□□
 2□□□〇□□□□
 3□〇〇〇〇□□□
 4□□□〇〇〇□□
 5□□□〇〇□□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

D3c3B3d2E1d6D7e3F4

*** perfect win 2 ***
   a b c d e f g h
 1〇□□□□□□□
 2□〇□□□□□□
 3□〇〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3B3e3F3f4F5b2A1

*** perfect win 3 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□□□□
 3□〇〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3B3e3F3f4F5d2D1

*** perfect win 4 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

D3c3B3e3F3f4F5d6D7

*** perfect win 5 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□□〇□
 8□□□□□□□□

D3c3B3e3F3f4F5f6G7

*** perfect win 6 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇□□□□
 4□□〇〇〇□□□
 5□□□〇〇□□□
 6□□□〇〇□□□
 7□□□〇□〇□□
 8□□□□□□〇□

D3c3B3d6E6f7D7c4G8

*** perfect win 7 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇□□□□□□
 3〇〇〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3F5f4F3e3B2b3A3

*** perfect win 8 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇□□□□□□
 3□□〇〇〇〇〇〇
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3F5f4F3e3B2g3H3

*** perfect win 9 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□□□□
 3□□〇〇□□〇□
 4□〇〇〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3F5f4G3d2D1c4B4

*** perfect win 10 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□〇□□□□
 3□□〇〇〇□〇□
 4□〇〇〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3F5f4G3e3D2c4B4

*** perfect win 11 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□□□□
 3□□〇〇□□〇□
 4□〇〇〇〇〇□□
 5□□□〇〇□□□
 6□□□□〇□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3E6f4G3d2D1c4B4

*** perfect win 12 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□〇□□□□
 3□□〇〇〇□〇□
 4□〇〇〇〇〇□□
 5□□□〇〇□□□
 6□□□□〇□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3E6f4G3e3D2c4B4

*** perfect win 13 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇〇〇〇〇□□
 3□□〇〇〇□□□
 4□□□〇〇□□□
 5□□□〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F2c2D2c3F5e2B2

*** perfect win 14 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇〇〇〇〇□□
 3□□〇〇〇□□□
 4□□□〇〇□□□
 5□□□〇〇□□□
 6□□□□〇□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F2c2D2c3E6e2B2

*** perfect win 15 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□〇□□
 3□□□〇〇□□□
 4□□〇〇〇□□□
 5□〇〇〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F2c4B5d2D1c5F5

*** perfect win 16 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4〇〇〇〇〇□□□
 5□〇〇〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F2c4B5c5F5b4A4

*** perfect win 17 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4□□〇〇〇〇〇□
 5□〇〇〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F2c4B5c5F5f4G4

*** perfect win 18 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4□□〇〇〇□□□
 5□〇〇〇〇〇□□
 6□〇□□□□□□
 7〇□□□□□□□
 8□□□□□□□□

D3e3F2c4B5c5F5b6A7

*** perfect win 19 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4□□〇〇〇□□□
 5□〇〇〇〇〇□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

D3e3F2c4B5c5F5d6D7

*** perfect win 20 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4□□〇〇〇□□□
 5□〇□〇〇□□□
 6□□〇〇〇□□□
 7□□□〇□□□□
 8□□□□□□□□

D3e3F2c4B5c6E6d6D7

*** perfect win 21 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F5c5B5f4F3d2D1

*** perfect win 22 ***
   a b c d e f g h
 1□□□□□□〇□
 2□□□□□〇□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F5c5B5f4F3f2G1

*** perfect win 23 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□〇□□□□□□
 7〇□□□□□□□
 8□□□□□□□□

D3e3F5c5B5f4F3b6A7

*** perfect win 24 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

D3e3F5c5B5f4F3d6D7

*** perfect win 25 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□〇〇〇□□□
 3□〇□〇〇□□□
 4□□〇〇〇□□□
 5□□□〇〇□□□
 6□□□□□〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c4B3c2E2d2D1

*** perfect win 26 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□□□□
 3□〇〇〇〇〇□□
 4□□〇〇〇□□□
 5□□□〇〇□□□
 6□□□□□〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c4B3d2D1c3F3

*** perfect win 27 ***
   a b c d e f g h
 1〇□□□□□□□
 2□〇□□□□□□
 3□〇〇〇〇〇□□
 4□□〇〇〇□□□
 5□□□〇〇□□□
 6□□□□□〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c4B3c3F3b2A1

*** perfect win 28 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇〇〇□□
 4〇〇〇〇〇□□□
 5□□□〇〇□□□
 6□□□□□〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c4B3c3F3b4A4

*** perfect win 29 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇〇〇□□
 4□□〇〇〇〇〇□
 5□□□〇〇□□□
 6□□□□□〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c4B3c3F3f4G4

*** perfect win 30 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇〇〇□□
 4□□〇〇〇□□□
 5□□□〇〇□□□
 6□□□〇□〇□□
 7□□□〇□□□□
 8□□□□□□□□

D3e3F6c4B3c3F3d6D7

*** perfect win 31 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□〇〇〇〇〇□□
 4□□〇〇〇□□□
 5□□□〇〇□□□
 6□□□□□〇□□
 7□□□□□□〇□
 8□□□□□□□〇

D3e3F6c4B3c3F3g7H8

*** perfect win 32 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□〇□□□
 3□□□〇〇□□□
 4□□□〇〇□□□
 5□□〇〇〇□□□
 6□〇〇〇〇〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c6D6c5E2e6B6

*** perfect win 33 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇□□□
 5□□〇〇〇□□□
 6□〇〇〇〇〇□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F6c6D6c5F3e6B6

*** perfect win 34 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□〇□□□□
 3□□〇〇〇□□□
 4□〇〇〇〇〇□□
 5□□〇〇〇□□□
 6□□□〇□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c5D6c3B4e3D2c4F4

*** perfect win 35 ***
   a b c d e f g h
 1□□□〇□□□□
 2□□□〇□□□□
 3□□□〇〇□□□
 4□〇〇〇〇〇□□
 5□□〇〇〇□□□
 6□□□〇□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c5D6e3B4d2D1c4F4

*** perfect win 36 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□〇□□
 7□□□□□□□□
 8□□□□□□□□

D3c5F6f3F4e3B5f5F2

*** perfect win 37 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3●●●●●□□□
 4□□●●●●●□
 5□□□●●●□□
 6□□□□●□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3B3e3F5a3C4e6F4g4

*** perfect win 38 ***
   a b c d e f g h
 1□□●□□□□□
 2□□●●□□□□
 3●●●●●□□□
 4□□●●●□□□
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3D2c1C2c5B3a3

*** perfect win 39 ***
   a b c d e f g h
 1□□●□□□□□
 2□□●●□□□□
 3□□●●●●●□
 4□□●●●□□□
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3D2c1C2c5F3g3

*** perfect win 40 ***
   a b c d e f g h
 1□□●□□□□□
 2□□●●□□□□
 3□□●●●□□□
 4□□●●●□□□
 5□□●●●●□□
 6□□□□□□●□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3D2c1C2c5F5g6

*** perfect win 41 ***
   a b c d e f g h
 1□□●□□□□□
 2□□●●□□□□
 3□□●●●□□□
 4□□●●●□□□
 5□□●●●□□□
 6□□□●□□□□
 7□□□●□□□□
 8□□□□□□□□

D3c3C4e3D2c1C2c5D6d7

*** perfect win 42 ***
   a b c d e f g h
 1□●□□□□□□
 2□□●□□□□□
 3□□●●●□□□
 4□□●●●●□□
 5□□●●●●●□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3F4g5F5c5C2b1

*** perfect win 43 ***
   a b c d e f g h
 1□□□□●□□□
 2□□□□●□□□
 3□□●●●□□□
 4□□●●●●□□
 5□□●●●●●□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3F4g5F5c5E2e1

*** perfect win 44 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●□□□
 4●●●●●●□□
 5□□●●●●●□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3F4g5F5c5B4a4

*** perfect win 45 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●□□□
 4□□●●●●●●
 5□□●●●●●□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3c3C4e3F4g5F5c5G4h4

*** perfect win 46 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●□□□
 4□□●●●●□□
 5□□●●●●●□
 6□□□□●□□□
 7□□□□●□□□
 8□□□□□□□□

D3c3C4e3F4g5F5c5E6e7

*** perfect win 47 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●□□□
 4□□●●●●□□
 5□□●●●●●□
 6□□□□□□●□
 7□□□□□□□●
 8□□□□□□□□

D3c3C4e3F4g5F5c5G6h7

*** perfect win 48 ***
   a b c d e f g h
 1□□□●□□□□
 2□□●●□□□□
 3□●●●●□□□
 4□□●●●□□□
 5□□□●●□□□
 6□□□□●□□□
 7□□□□●□□□
 8□□□□□□□□

D3c3E6e3C4e7C2b3D2d1

*** perfect win 49 ***
   a b c d e f g h
 1□□□□●□□□
 2□□□□●●□□
 3□□●●●●●□
 4□□●●●□□□
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F2c3F3g3C4c5E2e1

*** perfect win 50 ***
   a b c d e f g h
 1□□□□●□□□
 2□□□□●□□□
 3□□●●●●●□
 4□□●●●●□□
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F4g3F3c3C4c5E2e1

*** perfect win 51 ***
   a b c d e f g h
 1□□□□□□□●
 2□□□□□□●□
 3□□●●●●●□
 4□□●●●●□□
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F4g3F3c3C4c5G2h1

*** perfect win 52 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●●●□
 4●●●●●●□□
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F4g3F3c3C4c5B4a4

*** perfect win 53 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●●●□
 4□□●●●●●●
 5□□●●●□□□
 6□□□□□□□□
 7□□□□□□□□
 8□□□□□□□□

D3e3F4g3F3c3C4c5G4h4

*** perfect win 54 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●●●□
 4□□●●●●□□
 5□□●●●□□□
 6□□●□□□□□
 7□●□□□□□□
 8□□□□□□□□

D3e3F4g3F3c3C4c5C6b7

*** perfect win 55 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●●●□
 4□□●●●●□□
 5□□●●●□□□
 6□□□□●□□□
 7□□□□●□□□
 8□□□□□□□□

D3e3F4g3F3c3C4c5E6e7

*** perfect win 56 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●□□□
 4□□●●●□□□
 5□□●●●●●□
 6□□□□●●□□
 7□□□□●□□□
 8□□□□□□□□

D3e3F6c5F5g5C4c3E6e7

*** perfect win 57 ***
   a b c d e f g h
 1□□□□□□□□
 2□□●□□□□□
 3□□□●●□□□
 4□□□●●●□□
 5□□●●●●●□
 6□□□●●□□□
 7□□□□●□□□
 8□□□□□□□□

D3c5D6e7F5g5E6c2F4e3

*** perfect win 58 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□●□□□□
 3□□□●□□□□
 4□□●●●□□□
 5□●●●●●□□
 6□□●●●□□□
 7□□□●□□□□
 8□□□□□□□□

D3c5E6d2C4f5C6b5D6d7

*** perfect win 59 ***
   a b c d e f g h
 1□□□●□□□□
 2□□□●□□□□
 3□●●●●□□□
 4□□□●●□□□
 5□□●●●□□□
 6□□□●●□□□
 7□□□□●□□□
 8□□□□□□□□

D3c5E6e3C3b3D6e7D2d1

*** perfect win 60 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□●●●●□□□
 4□□□●●□□□
 5□□●●●□□□
 6□□□●●□□□
 7□□□●●□□□
 8□□□●□□□□

D3c5E6e3C3b3D6e7D7d8

*** perfect win 61 ***
   a b c d e f g h
 1□□□●□□□□
 2□□□●□□□□
 3□□●●●●□□
 4□□□●●□□□
 5□□●●●□□□
 6□□□●●□□□
 7□□□□●□□□
 8□□□□□□□□

D3c5E6f3E3c3D6e7D2d1

*** perfect win 62 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□●●●●□□
 4□□□●●□□□
 5□□●●●□□□
 6□□□●●□□□
 7□□□●●□□□
 8□□□●□□□□

D3c5E6f3E3c3D6e7D7d8

*** perfect win 63 ***
   a b c d e f g h
 1□□□□□□□□
 2□□●□□□□□
 3□□□●□□□□
 4□□●●●□□□
 5□●●●●●□□
 6□□●●●□□□
 7□□□●□□□□
 8□□□□□□□□

D3c5E6f5C4c2C6b5D6d7

*** perfect win 64 ***
   a b c d e f g h
 1□□□□□□□□
 2□□●□□□□□
 3□□□●□□□□
 4□□□●●□□□
 5●●●●●●□□
 6□□●●●□□□
 7□□□●□□□□
 8□□□□□□□□

D3c5E6f5C6c2B5a5D6d7

白手番の中では、58番目の以下の進行が左右対称で最もきれいな形かなぁと思います。

24番目と56番目も斜め対称できれいですし、何より魚の兄弟って感じが面白いです。

また、63番目は何となく果物っぽくて好みです。

おわりに

幅優先探索を使って、リバーシの最短の全滅パターンを探ってきました。筆者の非力なPCとPython製(+Cython)の自作ライブラリでは、処理の遅さやメモリ消費が、かなり一杯いっぱいでした。今回の取り組みを通して、個人的に幅優先探索の理解を深められたと思います。

筆者は趣味でPythonで挑みましたが、CやC++、Rustなどで書けば難なく解けてしまいそうです。また、他にも探索数を大幅に削減できる工夫の余地があるかもしれませんね。いつかそのようなトライもやってみようかなと思ったり、思わなかったりします。

本記事に記載した、全ての全滅パターンを覚えれば、知り合いを一杯食わせてウキャキャできるかも？しれませんね。

それでは皆様、よきリバーシ・ライフを！

コード解説

補足として、作ったコードの中身の説明を残しておきたいと思います。

min_reversi.py

min_reversi.pyでは、幅優先探索を使ってリバーシのルール通り局面を調べ、全滅パターンを見つけます。

インポート

min_reversi.py

from collections import deque

from reversi import BitBoard
from reversi import C as c
from reversi import Move, UPPER, LOWER

from util import flip_diagonalA1H8, flip_diagonalA8H1, rotate180, popcount

キューの使用のためdequeをインポートしています。

また、リバーシの操作のため、BitBorad(ボード)、c(手番)、Move(打ち手)をインポートしています。UPPERとLOWERは棋譜出力のために、打ち手の表記を大文字にするか小文字にするか指定するための定義です。

utilは今回の処理の補足用に作成したコードです。盤面の反転を求めるflip_diagonalA1H8(A1H8反転)やflip_diagonalA8H1(A8H1反転)、盤面の回転を求めるrotate180(180°回転)、2進数でビットが1の数を数えるpopcountをそれぞれインポートしています。

外部変数

min_reversi.py

C2N = {c.black: 0, c.white: 1}
N2C = {0: c.black, 1: c.white}

MAX_DEPTH = 9  # 探索手数の上限

{変数名	用途
C2N	reversiライブラリの`c`オブジェクトの手番の色を数値(黒:0、白:1)に変換するための辞書
N2C	手番の色を示す数値をreversiライブラリの`c`オブジェクトに変換するための辞書
MAX_DEPTH	局面を探索する最大の手数(10より大きい値は動作確認していません)

幅優先探索(BFS)

キュー(frontier)を使って、先頭から探索待ちの局面(child)を取り出し、探索終了かどうかをis_goalによりチェックします。終了時は結果を返します。終了していない場合は、successerに局面を渡し、その局面から1手打った次の局面を順に取得します。同じ局面を探索してしまうことを防ぐため、ここで見つかった局面は探索済み局面(explored)に記憶しておきます。最後にキューの末尾に順に局面を追加し、探索待ちの列に並ばせます。

min_reversi.py

def bfs(board_info):
    # 探索キュー
    frontier = deque()
    frontier.append(board_info)

    # 探索済み
    explored = {}
    explored[board_info[:3]] = True

    # 最短の全滅パターン
    perfect_win = []

    # 幅優先探索
    while frontier:
        # キューの先頭を取得
        child = frontier.popleft()

        # ゴールの判定
        if is_goal(child, perfect_win):
            return perfect_win

        # 子を元に次の探索対象をチェック
        for next_info in successors(child):
            # 探索済みの場合はスキップ
            if next_info[:3] in explored:
                continue

            # 探索済みを記憶
            add_explored(next_info, explored)

            # キューの後ろに追加
            frontier.append(next_info)

    print('\n--- no frontier ---')
    return perfect_win

探索終了条件

is_goalは探索の終了条件を返します。探索終了時はTrueそうでない場合Falseを返します。bbとwbはそれぞれ黒と石の配置のビットボード表現です。64ビットを8x8の64マスに当てはめて、ビットを1にした部分に石が置かれている事を表現しています。値が0の場合は石が置かれていない事を表しているため、これを元に全滅を判定しています。全滅パターンを見つけた場合、その時の盤面と棋譜を結果のリストに追加しています。

min_reversi.py

def is_goal(board_info, result):
    _, bb, wb, record = board_info

    # 黒か白どちらかが全滅の場合は格納
    if bb == 0 or wb == 0:
        board = BitBoard(ini_black=bb, ini_white=wb)
        result.append((board, record))
        print()
        print(f'*** perfect win {len(result)} ***')
        print(board)
        print(record)
        return True

    return False

BitBoardオブジェクト

reversiライブラリのBitBoardオブジェクト作成時のオプションとして、ini_blackとini_whiteが用意されています。これはそれぞれ黒と白の初期盤面を指定する際に使用します。与える値はビットボード表現の数値として下さい。

次の探索局面の追加

successorsはボード情報(board_info)を受け取り、次に打てる手をそれぞれ打った時の局面を生成して返します。

最大手数に達していたら、これ以上局面を追加しないよう制限をかけることにより、上限手数で必ず探索が終了するようにしています。

また、パスの場合は手番を入れ替えたり、どちらもパスの場合は終了として局面を追加しない処理も含まれています。

(board_infoの中身)

インデックス	名前	用途
board_info[0]	color	黒か白の手番
board_info[1]	bb	黒が置かれた場所を示す、ビットボード表現の数値
board_info[2]	wb	白が置かれた場所を示す、ビットボード表現の数値
board_info[3]	record	今まで打った手の棋譜

min_reversi.py

def successors(board_info):
    color, bb, wb, record = board_info

    # 最大手数に到達したら探索終了
    depth = popcount(bb) + popcount(wb) - 4
    if depth >= MAX_DEPTH:
        return []

    # 次に打てる手を全て取得
    turn = N2C[color]
    board = BitBoard(ini_black=bb, ini_white=wb)
    moves = board.get_legal_moves(turn)

    # パスの場合は手番を入れ替える
    if not moves:
        turn = c.white if turn == c.black else c.black
        moves = board.get_legal_moves(turn)
        # どちらもパスの場合は終了
        if not moves:
            return []

    # 次の盤面を取得
    next_turn = c.white if turn == c.black else c.black
    next_boards = []
    for move in moves:
        # 一手打つ
        board.put_disc(turn, *move)

        # 棋譜生成
        case = UPPER if turn == c.black else LOWER
        next_record = record + str(Move(*move, case=case))

        # 次の盤面情報を追加
        bb, wb, _ = board.get_bitboard_info()
        next_boards.append((C2N[next_turn], bb, wb, next_record))

        # 盤面を元に戻す
        board.undo()

    return next_boards

popcountは2進数のビットが1の個数を数える関数です。後述のutil.pyを参照してください。

reversiライブラリで使用しているメソッドについても補足しておきます。

get_legal_move

引数に手番を指定すると、着手可能な手をリストで返します。

moves = board.get_legal_moves(turn)

put_disc

引数に手番と、X座標、Y座標を指定すると、盤面に手を打ちます。以下の例では*にてmove(タプル)の中身を、XとYに展開して与えています。

# 一手打つ
board.put_disc(turn, *move)

タプルなどのiterableに対して*iterableとすると、中身を展開(アンパック)することができます。*iterableを関数の引数に指定すると、中身が展開されてそれぞれの要素が個別の引数として渡されます。

cオブジェクト

手番を表すcオブジェクトはc.blackで黒手番、c.whiteで白手番を表します。

Moveオブジェクト

Moveオブジェクトを使うと、打ち手のXY座標を"A1"や"H8"などの文字列に変換することができます。caseオプションにUPPERを指定した場合はアルファベットを大文字にし、LOWERを指定した場合は小文字の出力となります。本記事では黒手番を大文字、白手番を小文字として棋譜を作成しています。

# 棋譜生成
case = UPPER if turn == c.black else LOWER
next_record = record + str(Move(*move, case=case))

get_bitboard_info

盤面のビットボード表現の数値を取得できます。黒のビットボード、白のビットボード、石が置けない場所のビットボード、の3つの値を返します。3つ目の値は今回は使用しないため_で捨てています。局面の記憶を、BitBoardオブジェクトそのもので行うと、メモリ消費量が莫大なものになってしまったため、ビットボードの数値を扱う形で対応しています。同じくcオブジェクトについても単なる数値に直しています。

# 次の盤面情報を追加
bb, wb, _ = board.get_bitboard_info()
next_boards.append((C2N[next_turn], bb, wb, next_record))

undo

直前に打った手を元に戻します。

# 盤面を元に戻す
board.undo()

探索済みの局面の記憶

add_exploredにより、探索済みの局面を記憶し、同じ局面を再探索してしまうことを防ぎます。反転と回転を同形とみなして余計な探索をスキップしています。反転や回転に用いた関数は、後述のutil.pyを参照してください。

盤面の記憶に使用する情報は、手番プラス、黒と白のビットボード(石の配置)をタプルにして使用しています。

min_reversi.py

def add_explored(board_info, explored):
    color, bb, wb, _ = board_info

    # 元の盤面を記憶
    explored[(color, bb, wb)] = True

    # A1H8反転を記憶
    explored[(color, flip_diagonalA1H8(bb), flip_diagonalA1H8(wb))] = True

    # A8H1反転を記憶
    explored[(color, flip_diagonalA8H1(bb), flip_diagonalA8H1(wb))] = True

    # 180°回転を記憶
    explored[(color, rotate180(bb), rotate180(wb))] = True

探索の実施

ボード情報を用意して、bfsを呼び、結果をファイルに出力しています。ついでに実行時間も表示させています。

min_reversi.py

if __name__ == '__main__':
    from datetime import datetime

    start = datetime.now()
    print('start', start.strftime('%Y/%m/%d %H:%M:%S'))

    board = BitBoard()
    bb, wb, _ = board.get_bitboard_info()
    board_info = (C2N[c.black], bb, wb, "")

    # 幅優先探索で最短全滅パターンを探す
    perfect_win = bfs(board_info)

    print()
    with open('result.txt', 'w') as f:
        for i, (board, record) in enumerate(perfect_win, 1):
            f.write("\n")
            f.write(f'*** perfect win {i} ***\n')
            f.write(str(board) + "\n")
            f.write(record + "\n")

    end = datetime.now()
    print('end  ', end.strftime('%Y/%m/%d %H:%M:%S'))
    elpsed = end - start
    print('elp  ', elpsed)

util.py

盤面の反転や回転、2進数のビットが1の個数を数えるための関数を用意しています。

盤面の回転には以下の記事が大変参考になりました。ありがとうございました！

util.py

def delta_swap(x, mask, delta):
    t = (x ^ (x >> delta)) & mask
    return x ^ t ^ (t << delta)


def flip_horizontal(x):
    x = delta_swap(x, 0x5555555555555555, 1)
    x = delta_swap(x, 0x3333333333333333, 2)
    return delta_swap(x, 0x0F0F0F0F0F0F0F0F, 4)


def flip_vertical(x):
    x = delta_swap(x, 0x00FF00FF00FF00FF, 8)
    x = delta_swap(x, 0x0000FFFF0000FFFF, 16)
    return delta_swap(x, 0x00000000FFFFFFFF, 32)


def flip_diagonalA1H8(x):
    x = delta_swap(x, 0x00AA00AA00AA00AA, 7)
    x = delta_swap(x, 0x0000CCCC0000CCCC, 14)
    return delta_swap(x, 0x00000000F0F0F0F0, 28)


def flip_diagonalA8H1(x):
    x = delta_swap(x, 0x0055005500550055, 9)
    x = delta_swap(x, 0x0000333300003333, 18)
    return delta_swap(x, 0x000000000F0F0F0F, 36)


def rotate180(x):
    return flip_vertical(flip_horizontal(x))


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F
    x = x + (x >> 8)
    x = x + (x >> 16)
    return (x + (x >> 32)) & 0x000000000000007F

最短全滅手順57通りをあぶり出す

筆者のコードを使って、初手"F5"、同形スキップなしの条件に変更し、9手の最短全滅手順57通りを見つける方法を示します。

コード変更箇所

以下のように初期盤面を"F5"着手にし、棋譜の初期値にも"F5"を追加しておきます。

    board = BitBoard()
    board.put_disc(c.black, *Move('F5'))
    bb, wb, _ = board.get_bitboard_info()
    board_info = (C2N[c.white], bb, wb, "F5")

同形スキップをなくすために、以下をコメントアウトしてください。

        # 子を元に次の探索対象をチェック
        for next_info in successors(child):
            # 探索済みの場合はスキップ
            if next_info[:3] in explored:
                continue

            # 探索済みを記憶
            # ↓↓↓行コメントアウト
            #add_explored(next_info, explored)

実行結果

以下の通り1分40秒ほどで、57通りの全滅手順があぶり出されます！！

最短9手の全滅手順(同形スキップなし57通り)

*** perfect win 1 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□〇〇〇〇□□
 5□□〇〇〇〇□□
 6□□〇〇□□□□
 7□□〇□□□□□
 8□□□□□□□□

F5f4C3c6C5d6F3c4C7

*** perfect win 2 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□□□□
 4□□〇〇〇〇〇□
 5□□〇〇〇〇□□
 6□□〇〇□□□□
 7□□〇□□□□□
 8□□□□□□□□

F5f4C3c6C5d6G4c4C7

*** perfect win 3 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7c5B5f6F3

*** perfect win 4 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7g5H5f6F3

*** perfect win 5 ***
   a b c d e f g h
 1〇□□□□□□□
 2□〇□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7f6F3b2A1

*** perfect win 6 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□〇□□□
 3□□〇□〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7f6F3e3E2

*** perfect win 7 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7f6F3c5B5

*** perfect win 8 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7f6F3g5H5

*** perfect win 9 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□〇〇□□
 7□□□□〇〇□□
 8□□□□〇□□□

F5f4C3e6F7f6F3e7E8

*** perfect win 10 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇〇□
 8□□□□□□□〇

F5f4C3e6F7f6F3g7H8

*** perfect win 11 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇□□□□□
 4□□□〇〇〇〇□
 5□□□〇〇〇〇〇
 6□□□□〇□〇□
 7□□□□□〇□□
 8□□□□□□□□

F5f4C3e6F7g6G4g5H5

*** perfect win 12 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□〇
 3□□□〇〇〇〇□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4D3d6D7e3F3g3H2

*** perfect win 13 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4D3d6D7e3F3c5B5

*** perfect win 14 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4D3d6D7e3F3g5H5

*** perfect win 15 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇□□□□
 7□□〇〇□□□□
 8□〇□□□□□□

F5f4D3d6D7e3F3c7B8

*** perfect win 16 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇□□□□□□
 3□□〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4F3f6F7e3D3c3B2

*** perfect win 17 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4F3f6F7e3D3c5B5

*** perfect win 18 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f4F3f6F7e3D3g5H5

*** perfect win 19 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇〇□
 8□□□□□□□〇

F5f4F3f6F7e3D3g7H8

*** perfect win 20 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□〇〇□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4G3e6D7c5B5d6D3

*** perfect win 21 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□〇〇□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4G3e6D7g5H5d6D3

*** perfect win 22 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□□□〇□
 4□□〇〇〇〇□□
 5□〇〇〇〇〇□□
 6□□〇□〇□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4G3e6D7c6C4c5B5

*** perfect win 23 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□〇□□□
 3□□□〇〇□〇□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇〇□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4G3e6D7d6D3e3E2

*** perfect win 24 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□〇〇□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4G3e6D7d6D3c5B5

*** perfect win 25 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□〇〇□□□
 7□□□〇□□□□
 8□□□□□□□□

F5f4G3e6D7d6D3g5H5

*** perfect win 26 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇〇□□□
 7□□〇〇□□□□
 8□〇□□□□□□

F5f4G3e6D7d6D3c7B8

*** perfect win 27 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇〇□□□
 7□□□〇〇□□□
 8□□□□〇□□□

F5f4G3e6D7d6D3e7E8

*** perfect win 28 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇□□〇□
 4□□□〇〇〇〇□
 5□□□〇〇〇〇□
 6□□□□□〇〇□
 7□□□□□□〇□
 8□□□□□□□□

F5f4G3g6G5f6D3g4G7

*** perfect win 29 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□□□〇□
 4□□〇〇〇〇〇□
 5□□□〇〇〇〇□
 6□□□□□〇〇□
 7□□□□□□〇□
 8□□□□□□□□

F5f4G3g6G5f6C4g4G7

*** perfect win 30 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□〇〇〇〇〇□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□〇□□□□
 7□□□〇□□□□
 8□□□□□□□□

F5d6C3f3E3f4D7d3G3

*** perfect win 31 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□〇□□□
 4□□□〇〇〇□□
 5□□〇〇〇〇〇□
 6□□□〇〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5d6C5f4E3f6G5e6E7

*** perfect win 32 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□〇□□□
 4□□□〇〇〇□□
 5□□〇〇〇〇〇〇
 6□□□〇〇□□□
 7□□□□〇□□□
 8□□□□□□□□

F5d6C5f4E7g5H5e6E3

*** perfect win 33 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□〇□□□
 4□□□〇〇〇□□
 5□□〇〇〇〇〇□
 6□□□〇〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5d6C5f4E7f6G5e6E3

*** perfect win 34 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□〇□□□
 4□□□〇〇〇□□
 5□□〇〇〇〇〇□
 6□□□〇〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5d6C5f6E7f4G5e6E3

*** perfect win 35 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇□
 6□□□□〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5f6D3e3F2f4G5e6E7

*** perfect win 36 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□〇〇□□□
 4□□□〇〇□□□
 5□□□〇〇〇〇〇
 6□□□□〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5f6D3e3F2g5H5e6E7

*** perfect win 37 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇□□□□□□
 3□□〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6D3e3F3f4F7c3B2

*** perfect win 38 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6D3e3F3f4F7c5B5

*** perfect win 39 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6D3e3F3f4F7g5H5

*** perfect win 40 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇〇□
 8□□□□□□□〇

F5f6D3e3F3f4F7g7H8

*** perfect win 41 ***
   a b c d e f g h
 1□□□□□〇□□
 2□□□□□〇□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□□〇□
 8□□□□□□□□

F5f6D3e3F3f4G7f2F1

*** perfect win 42 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇〇□
 8□□□□□〇□□

F5f6D3e3F3f4G7f7F8

*** perfect win 43 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6D3e3F3c5B5f4F7

*** perfect win 44 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6D3e3F3g5H5f4F7

*** perfect win 45 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□□〇□□□
 4□□〇〇〇〇□□
 5□□□〇〇〇〇□
 6□□□□〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5f6C4e3F2f4G5e6E7

*** perfect win 46 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□〇□□
 3□□□□〇□□□
 4□□〇〇〇□□□
 5□□□〇〇〇〇〇
 6□□□□〇〇□□
 7□□□□〇□□□
 8□□□□□□□□

F5f6C4e3F2g5H5e6E7

*** perfect win 47 ***
   a b c d e f g h
 1□□□□□□□□
 2〇□□□□□□□
 3□〇□□□□□□
 4□□〇〇〇□□□
 5□〇〇〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6C4c5F7b3B5e6A2

*** perfect win 48 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇□□□□□□
 3□□〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7f4D3e3F3c3B2

*** perfect win 49 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7f4D3e3F3c5B5

*** perfect win 50 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7f4D3e3F3g5H5

*** perfect win 51 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇〇□
 8□□□□□□□〇

F5f6F7f4D3e3F3g7H8

*** perfect win 52 ***
   a b c d e f g h
 1□□□□□□□□
 2□〇□□□□□□
 3□□〇〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7f4F3e3D3c3B2

*** perfect win 53 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□〇〇〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7f4F3e3D3c5B5

*** perfect win 54 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇〇〇
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7f4F3e3D3g5H5

*** perfect win 55 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□〇〇〇□□
 4□□□〇〇〇□□
 5□□□〇〇〇□□
 6□□□□□〇□□
 7□□□□□〇〇□
 8□□□□□□□〇

F5f6F7f4F3e3D3g7H8

*** perfect win 56 ***
   a b c d e f g h
 1□□□□□□□□
 2〇□□□□□□□
 3□〇□□□□□□
 4□□〇〇〇□□□
 5□〇〇〇〇〇□□
 6□□□□〇〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7c5C4b3B5e6A2

*** perfect win 57 ***
   a b c d e f g h
 1□□□□□□□□
 2□□□□□□□□
 3□□□□〇□□□
 4□□□〇〇〇□〇
 5□〇〇〇〇〇〇□
 6□□□□□〇□□
 7□□□□□〇□□
 8□□□□□□□□

F5f6F7g5H4c5B5f4E3

参考書籍

Pythonで幅優先探索のコードを書くにあたり、以下の書籍を参考にしました。

「Python計算機科学新教本」 David Kopec著黒川利明訳株式会社オライリー・ジャパン ISBN978-4-87311-881-9

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up