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

# はじめに
どうも、y-tetsuです。

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

https://qiita.com/y-tetsu/items/6856dc50f1b130b26a56

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

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

https://uguisu.skr.jp/othello/lose_min.html

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

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



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

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

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

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

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

https://qiita.com/drken/items/996d80bcae64649a6580

一般的に、リバーシではコンピュータAIが手を読むために局面(盤面)の探索を行います。その際は、[ミニマックス法](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95)や[アルファ・ベータ法](https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%83%95%E3%82%A1%E3%83%BB%E3%83%99%E3%83%BC%E3%82%BF%E6%B3%95)といったアルゴリズムがよく紹介されます。これらはいずれも**深さ優先探索**をベースにしたものです。

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

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

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



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

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

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


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

①キューに初期の局面をセットする<br>
![bfs1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/b41c4001-a7df-33bb-d370-9706923fba58.png)

②現在の局面をキューの先頭から取得する<br>
![bfs2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/348ab783-1079-c3f2-000d-2784f57e8e5b.png)

③取り出した局面が全滅パターンか調べる<br>
![bfs3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/5ceb3c25-57db-bfab-123f-0f57610734af.png)

④全滅パターンの場合は、そこで終了<br>
![bfs4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/90974faf-751c-8bdd-a454-980f5c8021f4.png)

⑤全滅パターンではない場合、打てる手をすべて見つける<br>
![bfs5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/f824c407-38b3-63db-d3ca-ebdfd913b97a.png)

⑥打てるところに手を打った局面を、それぞれキューに追加する(ただし、既定の手数に達した場合は追加しない)<br>
![bfs6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/47d7ff0f-be80-d641-6e1f-91ff801ffed8.png)

⑦②～⑥を全滅パターンが見つかるか、キューが空になるまで繰り返す<br>
![bfs7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/9d0e2e94-d236-3bdb-1cde-f171900cb7f1.png)

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

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

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


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

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

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

(元の局面)<br>
![origin.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/035fcfdc-2568-d8f8-848d-7ac24018ab42.png)

(A1H8ラインの斜め反転形)<br>
![a1h8.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/225b95ff-76d9-1d54-6d5b-73c418ce0d2f.png)

(A8H1ラインの斜め反転形)<br>
![a8h1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/cfa77176-3aa5-9900-e121-bd35fb7c0062.png)

(180°回転形)<br>
![r180.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/17fea0f3-17b6-8ae2-a65c-4ea5fb944a75.png)

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


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


## reversiのインストール
例によって、拙作のリバーシライブラリ**reversi**を使います。

https://github.com/y-tetsu/reversi

事前に[Python 3.7.6](https://www.python.org/downloads/release/python-376/)をインストールし、以下のコマンドを実行してください。
```
$ py -3.7 -m pip install git+https://github.com/y-tetsu/reversi
```

Python3.7以降でも問題なく動くと思いますが、その際はCythonのコンパイルの関係で、[Microsoft Visual C++](https://visualstudio.microsoft.com/ja/downloads/?utm_medium=microsoft&utm_source=docs.microsoft.com&utm_campaign=button+cta&utm_content=download+vs2019+rc)のインストールを併せて実施願います。


## 探索コード
インストールしたライブラリを使って、最短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
```

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

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

![min1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/eb79cb89-fe75-267c-edb7-888b2ef125a9.gif)

たしかに！今確かに、黒が白を全滅させました！無事、黒による最短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

:
:
```

![min2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/6afcfbd7-3279-ac44-b17d-385521f37646.gif)

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

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

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


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


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

```min_reversi.py
MAX_DEPTH = 10  # 探索手数の上限
```


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

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

![min3.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/a24c0668-1308-e319-fec8-012004d914be.gif)

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

<details><summary>最短9+10手の全滅手順(64通り)</summary>

```
*** 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
```
</details>

白手番の中では、58番目の以下の進行が左右対称で**最もきれいな形**かなぁと思います。
![min4.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/3556c7ad-671d-cc99-6d6a-ae3c450be060.gif)

24番目と56番目も斜め対称できれいですし、何より**魚の兄弟**って感じが面白いです。
![min5.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/186f83ff-9615-7936-2827-19a66a44d8a2.gif)

![min6.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/c6bbb30d-b54c-0a5f-ee2a-8d1df829d8ab.gif)

また、63番目は何となく**果物**っぽくて好みです。
![min7.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/39b1cfe6-34c4-dc9a-e4db-fa18845c5451.gif)


# おわりに
幅優先探索を使って、リバーシの最短の全滅パターンを探ってきました。筆者の非力な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
引数に手番を指定すると、着手可能な手をリストで返します。

```python
moves = board.get_legal_moves(turn)
```

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

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

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

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

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

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

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

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

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

```python
# 盤面を元に戻す
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の個数を数えるための関数を用意しています。

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

https://qiita.com/ysuzuk81/items/453b08a14d23fb8c6c11

```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"を追加しておきます。
```python
    board = BitBoard()
    board.put_disc(c.black, *Move('F5'))
    bb, wb, _ = board.get_bitboard_info()
    board_info = (C2N[c.white], bb, wb, "F5")
```

同形スキップをなくすために、以下をコメントアウトしてください。
```python
        # 子を元に次の探索対象をチェック
        for next_info in successors(child):
            # 探索済みの場合はスキップ
            if next_info[:3] in explored:
                continue

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

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

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

```
*** 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
```
</details>

# 参考書籍
Pythonで幅優先探索のコードを書くにあたり、以下の書籍を参考にしました。
- 「Python計算機科学新教本」 David Kopec著 黒川 利明訳 株式会社オライリー・ジャパン [ISBN978-4-87311-881-9](https://www.oreilly.co.jp/books/9784873118819/)