リバーシの全消しパターンを見てみたい！

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

突然ですが、皆さんはリバーシ(オセロ)を遊んでいて、全部黒！！や、全部白！！みたいな**全消し**(全滅、パーフェクト勝ち、完全試合とも言われるようです)の場面を実際に見たことがありますか？

残念ながら、私はありませんでした。

物心ついた頃に幾度かプレイしておりましたが、周りに特段強い人もおらず、**全消し**なんてのはおおよそ漫画の出来事ぐらいにしか思っておりませんでした。

大人になってふと振り返った時に、**全消し**の状況が一体どんないきさつで生まれるのか、非常に興味がわいてきました。

幸い、それを確かめるために必要な多少のプログラミング知識が、今はあります。

本記事は、そんな私の子供の頃の何気ない疑問を解消するためだけに行った、簡単な取り組みとその結果をご紹介する記事です。



# やったこと
身も蓋もありませんが、先に本記事の肝をさらすと次のようになります。

- ランダムな打ち手で対戦を繰り返し、全消しパターンを見つける
- 全消しパターンを眺める
- 8x8以外の盤面も調べてみる



# 全消しパターンについて
全消しパターンがどんなものか、まずは4x4の簡単な例で見てみたいと思います。(これは自力でも見つけることができると思います)

![4x4.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/f54c8fd7-e4a4-717d-32f9-bd4c7887b77c.gif)

どうですか？一手ずつ着々と場が整い、ラスト一手できれいに一色に染まる過程は、なかなかの気持ち良さがありますよね。

私はもっと見てみたくなりました。



# 作戦
全消しパターンを見つけるための作戦は、非常にシンプルです。

私が考えたものは、**全消しパターンが見つかるまで、何度もコンピュータに適当に打たせる**、というものです。

言い換えると、最終的に64マスすべて同じ色となる棋譜が出るまで、ひたすら**ガチャを回す**という作戦です。

全面一色の盤面から逆算するなども考えましたが、ない知恵をいくら絞っても徒労に終わりそうで、結局これが一番だと判断しました。

潔く、いつ見つかるかは、運に任せるとしましょう！


## リバーシのライブラリをインストール
全消しパターンを見つけるために、拙作のリバーシライブラリ**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)のインストールを併せて実施願います。


## シミュレータのコードと設定ファイル
インストールしたライブラリを使って、ランダムな打ち手で対戦シミュレートを行うコードを、以下のように作成します。

```sim.py
import timeit
from reversi import Simulator, strategies


if __name__ == '__main__':
    simulator = Simulator(
        {
            # ↓↓↓↓↓ Add players here ↓↓↓↓↓
            'RANDOM1': strategies.Random(),
            'RANDOM2': strategies.Random(),
            # ↑↑↑↑↑ Add players here ↑↑↑↑↑
        },
        './simulator_setting.json',
    )

    elapsed_time = timeit.timeit('simulator.start()', globals=globals(), number=1)
    print(simulator, elapsed_time, '(s)')

    if simulator.processes == 1:
        keys = strategies.Measure.elp_time.keys()
        for key in keys:
            print()
            print(key)
            print(' min :', strategies.Measure.elp_time[key]['min'], '(s)')
            print(' max :', strategies.Measure.elp_time[key]['max'], '(s)')
            print(' ave :', strategies.Measure.elp_time[key]['ave'], '(s)')
```

## 設定ファイル
先ほどのシミュレーションの設定ファイルを以下のように作成します。先ほどのファイルと同じ場所に置いて下さい。

```simulator_setting.json
{
    "board_type": "bitboard",
    "perfect_check": true,
    "matches": 100000,
    "processes": 2,
    "prallel": "game",
    "random_opening": 0,
    "player_names": [
        "RANDOM1",
        "RANDOM2"
    ]
}
```
設定ファイルの意味は以下の通りです。適宜変更してください。

 |パラメータ名|説明|
 |:---|:---|
 |board_type|盤面の種類(board または bitboard)を選択してください。bitboardの方が高速で通常はこちらを使用してください。|
 |perfect_check|全消しで決着した場合、結果の棋譜を"./perfect_win.txt"に保存します。|
 |matches|AI同士の対戦回数を指定してください。100を指定した場合、AIの各組み合わせにつき先手と後手で100試合ずつ対戦する動作となります。|
 |processes|並列実行数を指定してください。お使いのPCのコア数に合わせて、設定を大きくするほど、シミュレーション結果が早く得られる場合があります。|
 |parallel|並列実行する単位を指定してください。"player"(デフォルト)を指定した場合、AI対戦の組み合わせ毎に並列処理を実施します。また、"game"を指定した場合は、matchesの対戦回数をprocessesの数で分割して並列処理を実施します。シミュレートするAI対戦の組み合わせの数が、お使いのPCのコア数より少ない場合は、"game"を指定することで、より早く結果を得られる場合があります。|
 |random_opening|対戦開始から指定した手数までは、AI同士ランダムな手を打ち試合を進行します。指定された手数を超えるとAIは本来の手を打ちます。対戦開始の状況をランダムに振ることで、結果の偏りを減らしAIの強さを測りやすくします。不要な場合は0を指定してください。|
 |player_names|対戦させたいAI名をリストアップして下さい。指定する場合は第一引数の"プレイヤー情報"に含まれるものの中から選択してください。省略すると第一引数の"プレイヤー情報"と同一と扱います。リストアップされた全てのAI同士の総当たり戦を行います。|

## フォルダ構成
ファイルの配置は以下のようになります。Cドライブ以外のフォルダに移動させても問題ありません。

```
C:.
 sim.py                 … ランダム対戦のシミュレータ
 simulator_setting.json … シミュレータの設定ファイル
```


# 全消しパターンの棋譜を残す
全消しパターンが見つかる確率は、今回の設定(20万回のランダム対戦)を1回実行して、1個見つかるかなぁ？ぐらいのものでした(体感で約20万分の1)。

## 実行方法
以下を実行してください。(*sim.py*は先ほど用意したもの)

```
py -3.7 sim.py
```

## 結果の確認
全消しパターンが見つかれば、実行フォルダに以下のようなファイルが作成されます。作られていなければ、あたりが引けるまで何度も実行してください。

```perfect_win.txt

-------------------------------------------
2023/04/16 13:36:37
-------------------------------------------
* Black perfect win *

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

(black) 64 - 0 (white)
C4c3E6d6C2f4F6b4G3g7E3f2C6g5H8f7A4g6G4h6E2c7B8d2G2g8C5h2H4c1F8e1E7a5A6c8H7f5B6h3A3b7H5a7A8e8B5d7B3g1D8d3F1b2H1B1a2A1F3D1

```
最後の行の、C4c3E6...が棋譜になります。アルファベット大文字が先手の黒の手番、小文字が後手の白の手番としています。


# 全消しパターンを眺める
それでは、ゲットした棋譜のゲーム進行を眺めてみましょう。

## 黒の全消し勝利
![8x8_black.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/8fc6fd46-2bc5-34aa-b0d8-8bb82f815ce9.gif)


```
C4c3E6d6C2f4F6b4G3g7E3f2C6g5H8f7A4g6G4h6E2c7B8d2G2g8C5h2H4c1F8e1E7a5A6c8H7f5B6h3A3b7H5a7A8e8B5d7B3g1D8d3F1b2H1B1a2A1F3D1
```

## 白の全消し勝利
![8x8_white.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/f6fdf138-4ffc-7305-2ddf-332312df9c0e.gif)


```
F5d6C7g5G6f4G4d7C5b7F3b4D8f6F7g7B8e7B5b6G8h5H7e2E8e6H4g3E3h8C6f8A6a5H2a7F2c8D3f1A4h3E1a8G1h6G2d2C4c3C2h1B3b2D1b1A2a3a1c1
```

ようやく願いが叶いました！全消しは確かに実在しました！！めでたし、めでたし。

そうそう、そういえば8x8以外の盤面だと、どうなるんでしょうね？

私はもっと見てみたくなりました。


# 8x8以外の盤面の全消しパターン
今回は8x8以外の盤面でもガチャを回してみました。3つほど当たりが出たので、ご紹介したいと思います。

## かざぐるま型
![kazaguruma.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/75d0b11d-1635-b6d0-7b13-ece43f90e4b2.gif)


(棋譜)
```
F5f4D3f6G3f3G6c3G4d6C6g5E3h3F2e2H2b7C2d2G2b2H4g7D1G8C1E6f7E7f8C4C7c5E8d7B6b5A5b4A6A7B3B1
```

(設定ファイル)

```simulator_setting.json
{
    "board_type": "bitboard",
    "board_name": "Kazaguruma",
    "perfect_check": true,
    "matches": 100000,
    "processes": 2,
    "prallel": "game",
    "random_opening": 0,
    "player_names": [
        "RANDOM1",
        "RANDOM2"
    ]
}
```

## ハート型
![heart.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/64f241a7-9a31-c47d-3f5c-9735d9da0255.gif)


(棋譜)
```
F5f6E6f4E3f2G3d6G5g4C3h5H4c5C7h3B4b2G6d7C6g2E7f3D3d8F7b5A4b6B3c4c2a3a5e8
```

(設定ファイル)

```simulator_setting.json
{
    "board_type": "bitboard",
    "board_name": "Heart",
    "perfect_check": true,
    "matches": 100000,
    "processes": 2,
    "prallel": "game",
    "random_opening": 0,
    "player_names": [
        "RANDOM1",
        "RANDOM2"
    ]
}
```


## ドーナツ型
![torus.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2653390/ac721fec-3abd-144b-b3b4-8cc4bff936e8.gif)


(棋譜)
```
A4g3H5c3D2a5A6f6D6h4H3b3C2e1C6c1D1a3F3b6C7b2E6e7D8h6F1g6F7f2E3g1D7a7f8E8g2h2e2d3c8B7b8g7
```

(設定ファイル)

```simulator_setting.json
{
    "board_type": "bitboard",
    "board_name": "Torus",
    "perfect_check": true,
    "matches": 100000,
    "processes": 2,
    "prallel": "game",
    "random_opening": 0,
    "player_names": [
        "RANDOM1",
        "RANDOM2"
    ]
}
```


# おわりに
全消しパターンをいろいろと探ってきました。今回の方法はお宝探し感があって、とてもワクワクできました。

結局ランダムに見つけたものなので、打ち筋はあり得ないものになっていると思います。そのあたりはどうかご容赦ください。

何はともあれ、子供の頃の疑問は無事に解消されてよかったです。

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