Pythonで〇×ゲームのAIを一から作成する　その111　同一局面の計算と同一局面を考慮した強解決の AI の判定

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6

## これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

| リンク | 説明 |
|:--|:--|
| [marubatsu.py](https://github.com/ysgeso/marubatsu/blob/master/111/marubatsu.py)  | Marubatsu、Marubatsu_GUI クラスの定義|
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/111/ai.py)  |  AI に関する関数 |
| [test.py](https://github.com/ysgeso/marubatsu/blob/master/111/test.py)  |  テストに関する関数 |
|  [util.py](https://github.com/ysgeso/marubatsu/blob/master/111/util.py) |  ユーティリティ関数の定義。現在は `gui_play` のみ定義されている |
| [tree.py](https://github.com/ysgeso/marubatsu/blob/master/111/tree.py)  | ゲーム木に関する Node、Mbtree クラスの定義  |
| [gui.py](https://github.com/ysgeso/marubatsu/blob/master/111/gui.py)  |  GUI に関する処理を行う基底クラスとなる GUI クラスの定義  |

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

# 強解決の AI であるかを判定する局面の数の削減

前回の記事では、〇×ゲームのゲーム盤を表す __[board 属性の値を文字列型のデータに変換](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E5%B1%9E%E6%80%A7%E3%81%AE%E6%96%87%E5%AD%97%E5%88%97%E3%81%B8%E3%81%AE%E5%A4%89%E6%8F%9B)__ し、それを利用することで〇×ゲームの[ゲーム盤の種類が 5478 種類](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#board-%E5%B1%9E%E6%80%A7%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E5%B1%80%E9%9D%A2%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E5%AF%BE%E5%BF%9C%E8%A1%A8%E3%81%AE%E4%BD%9C%E6%88%90)であることを示しました。これは、ゲーム木のノードの数が 549946 であるのに対して約 1/100 になっているため、局面と最善手の対応表を表すデータも約 1/100 の大きさに減らすことができました。

また、その中から[決着がついている局面を除いた局面の種類は 4520 種類](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#mblist_by_board-%E3%81%AE%E8%A8%88%E7%AE%97%E3%81%A8%E4%BF%9D%E5%AD%98)であることを示し、それを利用して強解決の AI であるかを判定するように `Check_solved` クラスを修正しました。実は、__強解決の AI であるか__ を判定するために __必要な局面の種類をさらに減らす__ ことができます。どのようにして減らすことができるかについて少し考えてみて下さい。

# 合法手に最善手しか存在しない局面の削減

強解決の AI であるかを判定するためには、局面に対して __AI が最善手以外の着手を選択するか__ どうかを判定する必要があります。局面の中には __すべての合法手が最善手__ になっている局面があり、そのような局面では __すべての AI が最善手のみを選択__ します。従って、それらの局面を強解決の AI であるかを判定する __局面の一覧から削除__ することができます。

## 局面の一覧の計算

下記は、[前回の記事](https://qiita.com/ysgeso/items/c4c7220d8c2f0ac3b6e6#mblist_by_board-%E3%81%AE%E8%A8%88%E7%AE%97%E3%81%A8%E4%BF%9D%E5%AD%98)で記述した `board` 属性の値が異なり、なおかつ決着がついていない局面の一覧を計算して `mblist_by_board` に代入するプログラムです。

```python
bestmoves_by_board = {}
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
        if node.mb.status == Marubatsu.PLAYING:
            mblist_by_board.append(node.mb)
```

__全ての合法手が最善手であるか__ どうかは、__合法手の数__ と、__最善手の一覧の数__ が __等しいか__ どうかで判定できます。従って、上記のプログラムで計算した `mblist_by_board` からそれらの局面を除いた局面の一覧は、下記のプログラムで計算することができます。

* __10 行目__：`mblist_by_board` に局面を加える条件に、合法手の数を表す子ノードの数と最善手の数が一致しないという条件を加える

```python
 1  from marubatsu import Marubatsu
 2  from tree import Mbtree
 3
 4  mbtree = Mbtree.load("../data/aidata")
 5  bestmoves_by_board = {}
 6  mblist_by_board = []
 7  for node in mbtree.nodelist:
 8      txt = node.mb.board_to_str()
 9      if not txt in bestmoves_by_board.keys():
10          bestmoves_by_board[txt] = node.bestmoves
11          if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
12              mblist_by_board.append(node.mb)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from marubatsu import Marubatsu
from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
bestmoves_by_board = {}
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
from marubatsu import Marubatsu
from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
bestmoves_by_board = {}
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
-       if node.mb.status == Marubatsu.PLAYING:
+       if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

上記の修正後に下記のプログラム実行して `mblist_by_board` の要素の数を表示すると、実行結果から __強解決の AI であることを判定するために必要な局面の数が 3191__ であることが判明しました。

```python
print(len(mblist_by_board))
```

実行結果

```
3191
```

## プログラムの改良

上記のプログラムでは `node.mb` と同じ局面が `mblist_by_board` に登録されているかどうかを __判定するために `bestmoves_by_board` を計算__ していますが、その判定を行うために __わざわざ `bestmoves_by_board` を計算する必要はない__ ので、その点を改良することにします。

具体的には、下記のプログラムのように `mblist_by_board` に `node.mb` が __登録済（registerd）であるかを表す `registered_boards`__ という list を `bestmoves_by_board` の代わりに計算するように修正します。

* __1 行目__：`mblist_by_board` に `mb` が登録済であるかを表す `registered_boards` を空の list で初期化する
* __5 行目__：`board` 属性の値を変換した文字列を表す `txt` が `registered_boards` の要素に存在するかを判定するように修正する
* __6 行目__：`registered_boards` の要素に `txt` を追加する

```python
1  registered_boards = []
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4     txt = node.mb.board_to_str()
5     if not txt in registered_boards:
6         registered_boards.append(txt)
7         if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
8             mblist_by_board.append(node.mb)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
registered_boards = []
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards.append(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
-bestmoves_by_board = {}
+registered_boards = []
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
-   if not txt in bestmoves_by_board.keys():
+   if not txt in registered_boards:
-       bestmoves_by_board[txt] = node.bestmoves
+       registered_boards.append(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

上記の修正後に下記のプログラムを実行すると、修正前と同じの数の `mblist_by_board` が計算できたことが確認できます。

```python
print(len(mblist_by_board))
```

実行結果

```
3191
```

## set による処理の高速化

__上記のプログラム__ を実行すると筆者のパソコンでは __約 17 秒__ の時間がかかりましたが、__修正前のプログラムでは 1 秒以内__ で処理が完了しました。__処理時間が大幅に増えた理由__ は、__list に対して要素の中にデータが存在するか__ どうかを判定する処理は、__dict のキーの中にデータが存在するか__ どうかを判定する処理と比較して __処理の効率が大幅に悪いから__ です。

__同じデータが重複して存在しない__ ようなデータの中に、__特定のデータが存在するかどうかを判定__ する場合は、list ではなく、__set を利用することで高速に処理を行う__ ことができます。下記は、先程のプログラムを set を使うように修正したプログラムです。

* __1 行目__：`registered_boards` を __空の set で初期化__ するように修正する
* データが要素に含まれているかどうかの __判定は list と set で同じ__ なので、5 行目のプログラムを __修正する必要はない__
* __6 行目__：set に要素を追加するのは `append` ではなく `add` なのでそのように修正する

```python
1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          registered_boards.add(txt)
7          if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
8              mblist_by_board.append(node.mb)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards.add(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
-registered_boards = []
+registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
-       registered_boards.append(txt)
+       registered_boards.add(txt)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果は同じになりますが、処理時間が 1 秒未満になることが確認できます。

```python
print(len(mblist_by_board))
```

実行結果

```
3191
```

:::note
dict のキーが、set の要素と同様に同じ名前のキーが重複せず、ハッシュ可能なデータしか利用できないのは dict のキーと set が同じ仕組みで管理されているからです。そのため、最初の `bestmoves_by_board` のキーで判定を行っていたプログラムと上記のプログラムの処理速度はほとんど変わりません。

なお、データを追加する処理に関しては list と set で大きな違いはありません。
:::

## データの保存と `is_strongly_soved` の修正と確認

データが作成できたので、下記のプログラムでファイルに保存します。ファイル名は良い名前が思いつかなかったので、mblist_by_board2.dat としました。

```python
import pickle
import gzip
with gzip.open("../data/mblist_by_board2.dat", "wb") as f:
    pickle.dump(mblist_by_board, f)
```

作成された __ファイルサイズは 30 KB__ で、`mblist_by_board.dat` の __38 KB よりもさらにサイズが小さくなります__。

次に、このデータで正しく強解決の AI であるかを判定できるかを確認するために、Check_solved クラスの `is_strongly_solved` を下記のプログラムのように修正します。なお、修正箇所は 9 行目で読み込むファイルを mblist_by_board2.dat に変えただけです。

```python
 1  from util import Check_solved, load_bestmoves, load_mblist
 2  from tqdm import tqdm
 3
 4  @staticmethod
 5  def is_strongly_solved(ai, params=None):
 6      if Check_solved.bestmoves_by_board is None:
 7          Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
 8      if Check_solved.mblist_by_board is None:
 9          Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board2.dat")
元と同じなので省略
10
11  Check_solved.is_strongly_solved = is_strongly_solved
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from util import Check_solved, load_bestmoves, load_mblist
from tqdm import tqdm

@staticmethod
def is_strongly_solved(ai, params=None):
    if Check_solved.bestmoves_by_board is None:
        Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
    if Check_solved.mblist_by_board is None:
        Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board2.dat")            
    if params is None:
        params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist_by_board):
        candidate = set(ai(mb, candidate=True, **params))
        bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist_by_board)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist

Check_solved.is_strongly_solved = is_strongly_solved
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
from util import Check_solved, load_bestmoves, load_mblist
from tqdm import tqdm

@staticmethod
def is_strongly_solved(ai, params=None):
    if Check_solved.bestmoves_by_board is None:
        Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
    if Check_solved.mblist_by_board is None:
-       Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board.dat")
+       Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board2.dat")
元と同じなので省略

Check_solved.is_strongly_solved = is_strongly_solved
```
</details>

上記の修正後に、下記のプログラムで強解決でない `ai2s`、`ai14s` と強解決の `ai_gt6` を `is_strongly_solved` で判定できるかどうかを確認します。

下記の実行結果のように `ai2s` が強解決の AI でないことを正しく判定できます。また、__`ai2s`__ は __全ての合法手の中からランダムに着手を選択する__ ので、__最善手でない合法手が必ず混じっている局面を集めた__ mblist_by_board2.dat のデータに対してチェックを行うと、実行結果のように __0 % が表示__ されます。

```python
from ai import ai2s, ai14s, ai_gt6
result, incorrectlist = Check_solved.is_strongly_solved(ai2s)
print(result)
```

実行結果

```
100%|██████████| 3191/3191 [00:00<00:00, 4117.52it/s]
0/3191 0.00%
False
```

下記の実行結果のように `ai14s` が強解決の AI でないことが正しく判定できます。また、正しく判定できない局面の数は 3191 - 3139 = 52 種類であることがわかります。

```python
result, incorrectlist = Check_solved.is_strongly_solved(ai14s)
print(result)
```

```
100%|██████████| 3191/3191 [00:00<00:00, 3317.61it/s]
3139/3191 98.37%
False
```

下記の実行結果のように `ai_gt6` が強解決の AI であることが正しく判定できます。

```python
from util import load_bestmoves
bestmoves = load_bestmoves("../data/bestmoves_by_board.dat")
result, incorrectlist = Check_solved.is_strongly_solved(ai_gt6, params={"bestmoves_by_board": bestmoves})
print(result)
```

実行結果

```
100%|██████████| 3191/3191 [00:00<00:00, 265287.59it/s]
3191/3191 100.00%
True
```

# 同一局面の削減

[以前の記事](https://qiita.com/ysgeso/items/e78980b366e123ca57f1#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E6%89%B1%E3%81%84)で〇×ゲームには __回転による同一局面__ と、__線対称な同一局面__ が存在することを説明しました。__同一局面に対する最善手は__、元の局面の最善手を __同じように回転、反転__ させたものに __一致します__。

わかりづらいと思いますので、具体例を挙げます。下記の __左の局面__ は 次に (2, 2) に 〇 が着手を行うと 〇 が勝利するので __最善手は (2, 2)__ です。左の局面を __時計回りに 90 度回転__ させた __右の局面は同一局面です__ が、その最善手は __左の局面の最善手__ である (2, 2) を同じく __時計回りに 90 度回転させた (0, 2)__ になります。

```
o..  .xo
xo.  .o.
...  ...
```

## 同一局面に対する着手が一致する AI の定義と性質

__AI が選択する着手の一覧__ が、__同一局面に対しても同じだけ回転、反転した着手の一覧に一致する場合__ は、__ある局面__ に対して AI が最善手のみを着手するかどうかを判定することで、その局面に対する __すべての同一局面に対しても判定を行ったことになります__。

例えば、そのような AI が上記の左の局面で最善手のみを選択することが確認できれば、右の局面に対する確認を行わなくても、右の局面で最善手のみを選択することがわかります。従って、そのような AI に対しては、強解決の AI であるかを判定する局面の一覧から __同一局面を削除__ することができます。

:::note warn
本記事ではそのような性質を持つ AI のことを、__同一局面に対する着手が一致する AI__ と表記することにします。
:::

これまでに作成してきた〇×ゲームの AI は、左上のマスから優先的に着手を行うという __[ルール 1](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#%E6%9C%80%E5%88%9D%E3%81%AB%E8%A6%8B%E3%81%A4%E3%81%8B%E3%81%A3%E3%81%9F%E7%A9%BA%E3%81%84%E3%81%A6%E3%81%84%E3%82%8B%E3%83%9E%E3%82%B9%E3%81%AB%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai)__ で着手を選択する __`ai1` と `ai1s` のみがその条件を満たしません__。実際に __`ai1s`__ は上記の __左の局面では (1, 0) を選択__ し、__右の局面__ では (1, 0) を時計回りに 90 度回転させた (2, 1) とは __異なる (0, 0) を選択__ します。

ただし、__それ以外のルール__ はいずれもゲーム盤を回転、反転した際に __選択する着手が同様の回転、反転を行うようなルール__ なので、__`ai1` と `ai1s` 以外の AI はすべて同一局面に対する着手が一致する AI__ です。また、〇×ゲームの性質を考えると、よほど特別なルールでない限りは、同一局面に対する着手が一致する AI になるでしょう。

## 同一局面を考慮した局面の一覧を計算するアルゴリズム

最初に、__同一局面を考慮した場合の〇×ゲームの局面の一覧__ を計算することにします。

同一局面を考慮した局面の一覧は、下記のアルゴリズムで計算することができます。

* 局面を登録済であるかどうかを表すデータを空の set で初期化する
* 局面の一覧を表すデータを空の list で初期化する
* ゲーム木の全てのノードの局面に対して下記の処理を行う
* その局面を文字列に変換したデータが、登録済であるかを表す set に存在していなければ、下記の処理を行う。存在している場合は登録済なので何もしない
    * 局面の一覧を表す list にその局面を追加する
    * 局面を登録済であるかどうかを表す set に、その局面を含む、すべての同一局面を文字列に変換したデータを登録する

このアルゴリズムは、__以下の点を除けば__ 先程の `mblist_by_board` を計算するプログラムと __全く同じ__ です。

* `mb.node` だけでなく、`mb.node` の全ての同一局面を文字列に変換したデータを `registerd_borads` に追加する
* 決着がついているかどうかと、全ての合法手が最善手であるかの判定を行わず、全ての局面を `mblist_by_board` に登録する

従って、上記のアルゴリズムは、先程のプログラムを修正した下記のプログラムのように記述できます。6 行目の処理をどのように記述すれば良いかについて少し考えてみて下さい。

```python
1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          # ここに node のすべての同一局面を表す文字列を registerd_boards に追加する処理を記述する
7          mblist_by_board.append(node.mb)
```

<details><summary><strong>修正箇所</strong></summary>

```diff_python
registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
-       registered_boards.add(txt)
+       # ここに node のすべての同一局面を表す文字列を registerd_boards に追加する処理を記述する
-       if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
-           mblist_by_board.append(node.mb)
+       mblist_by_board.append(node.mb)
```
</details>

## 同一局面の計算の考え方

上記の 6 行目の処理を記述するためには、__任意の局面の同一局面をすべて計算__ する必要があります。そのために、同一局面がどのようなものであるかをおさらいします。

[以前の記事](https://qiita.com/ysgeso/items/e78980b366e123ca57f1#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%81%AE%E4%B8%80%E8%A6%A7)で説明したように、同一局面には最大で下記の 8 種類が存在します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86ce95b0-6999-5e72-7f7e-59d36839fb29.png" width="630">

同一局面を表す `board` 属性のデータは、上図の __左のゲーム盤のデータを元__ に、__残りの 7 つのゲーム盤のデータを計算する__ 処理を行うことで計算することができます。

### 左から 2 番目の同一局面の計算方法

まず、__一番左のゲーム盤__ のデータを、__左から 2 番目の同一局面__ のゲーム盤のデータに __変換する方法__ を考えることにします。このような変換の処理に慣れている人であれば頭の中だけで変換を行う方法を思いつくことができますが、そうではない場合は、最初に __変換後と変換前__ のそれぞれの __数字の座標__ を下記のように __表にまとめる__ ことをお勧めします。

| 数字 | 変換後の座標 | 変換前の座標 |
|:-:|:-:|:-:|
| 1  | (2, 0)  | (0, 0)  |
| 2  | (2, 1)  | (1, 0)  |
| 3  | (2, 2)  | (2, 0)  |
| 4  | (1, 0)  | (0, 1)  |
| 5  | (1, 1)  | (1, 1)  |
| 6  | (1, 2)  | (2, 1)  |
| 7  | (0, 0)  | (0, 2)  |
| 8  | (0, 1)  | (1, 2)  |
| 9  | (0, 2)  | (2, 2)  |

おそらく、この表をみてもピンとこない人が多いのではないかと思います。そのような場合は、下記の表のように __x 座標と y 座標に分けた表__ を作成すると良いでしょう。

| 数字 | 変換後の x 座標 | 変換後の y 座標 | 変換前の x 座標 | 変換前の y 座標 |
|:-:|:-:|:-:|:-:|:-:|
| 1  | 2  | 0  |  0 | 0  |
| 2  | 2  | 1  |  1 | 0  |
| 3  | 2  | 2  |  2 | 0  |
| 4  | 1  | 0  |  0 | 1  |
| 5  | 1  | 1  |  1 | 1  |
| 6  | 1  | 2  |  2 | 1  |
| 7  | 0  | 0  |  0 | 2  |
| 8  | 0  | 1  |  1 | 2  |
| 9  | 0  | 2  |  2 | 2  |

この表から、以下の事がわかります。

* 変換後の y 座標と、変換前の x 座標が等しい
* 変換後の x 座標と変換前の y 座標は、__同じ座標に対して同じ値が対応__ している

そこで、__変換後の x 座標と変換前の y 座標の対応__ をまとめると以下の表のようになります。

| 変換後の x 座標 | 変換前の y 座標|
|:-:|:-:|
| 2  | 0  |
| 1  | 1  |
| 0  | 2  |

この表から「変換後の x 座標 + 変換前の y 座標 = 2」になることがわかるので、__変換後の x 座標__ は「__2 - 変換前の y 座標__」という __式で計算できる__ ことがわかります。

上記から、__左から 2 番目__ の同一局面の __(x, y) のマスの内容__ は、__一番左の局面の (y, 2 - x) のマスの内容__ になることがわかります。

従って、__一番左の局面__ を表すデータが __`mb` に代入__ されている場合に、__左から 2 番目__ の同一局面を表すゲーム盤のデータは、__下記のプログラムで計算__ することができます。

* __1 行目__：同一局面のゲーム盤を計算する `board` を空の list で初期化する
* __2 行目__：同一局面の各列に対する繰り返し処理を行う
* __3 行目__：同一局面の x 列のデータを計算する `col` を空の list で初期化する
* __4 行目__：同一局面の x 列の各マスに対する繰り返し処理を行う
* __5 行目__：同一局面の (x, y) のマスを表す、元の局面の (y, 2-x) のマスのデータを `col` の要素に追加する
* __6 行目__：同一局面の x 列のデータを `board` の要素に追加する

```python
1  board = []
2  for x in range(mb.BOARD_SIZE):
3      col = []
4      for y in range(mb.BOARD_SIZE):
5          col.append(mb.board[y][2 - x])
6      board.append(col)
```

このプログラムが正しく動作することを、下記のプログラムで下記の図の __一番左と同じ局面を作成__ し、__左から 2 番目の同一局面を作成できているか__ どうかで確認することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86ce95b0-6999-5e72-7f7e-59d36839fb29.png" width="630">

* __1 ~ 5 行目__：上図の一番左の局面のデータを作成してゲーム盤を表示する
* __7 ~ 12 行目__：上記のプログラムを記述して左から 2 番目の同一局面のデータを計算する
* __13、14 行目__：計算したデータを `mb` の `board` 属性に代入して上書きし、`print(mb)` でその局面を表示する

```python
 1  mb = Marubatsu()
 2  mb.move(1, 1)
 3  mb.move(0, 0)
 4  mb.move(1, 0)
 5  print(mb)
 6
 7  board = []
 8  for x in range(mb.BOARD_SIZE):
 9      col = []
10      for y in range(mb.BOARD_SIZE):
11          col.append(mb.board[y][2 - x])
12      board.append(col)
13  mb.board = board
14  print(mb)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
mb = Marubatsu()
mb.move(1, 1)
mb.move(0, 0)
mb.move(1, 0)
print(mb)

board = []
for x in range(mb.BOARD_SIZE):
    col = []
    for y in range(mb.BOARD_SIZE):
        col.append(mb.board[y][2 - x])
    board.append(col)
mb.board = board
print(mb)
```
</details>

実行結果

```
Turn x
xO.
.o.
...

Turn x
..x
.oo
...
```

実行結果から図の一番左と、左から 2 番目と __同じ局面が表示される__ ので、正しい処理が行われることが確認できました。

## 同一局面を表す文字列の計算

上記では左から 2 番目の同一局面のデータを計算しましたが、__実際に必要になる__ のはその局面を __文字列に変換したデータ__ です。そのデータは、下記のプログラムのように、`board_to_str` メソッドを使って計算できますが、一旦ゲーム盤のデータを作成してから文字列に変換するのは __無駄がある__ ので、__一番左の局面__ のデータから __直接同一局面を表す文字列を計算する__ ことにします。どのように計算すればよいかについて少し考えてみて下さい。

```python
print(mb.board_to_str())
```

実行結果

```
'....o.xo.'
```

そのプログラムは、下記のように元のプログラムと比較してシンプルに記述できます。

* __1 行目__：同一局面のゲーム盤の文字列を表す `txt` を空文字で初期化する
* __4 行目__：同一局面の (x, y) のマスを表す、元の局面の (y, 2-x) のマスのデータを `+` 演算子を使って `txt` に結合する

```python
1  txt = ""
2  for x in range(mb.BOARD_SIZE):
3      for y in range(mb.BOARD_SIZE):
4          txt += mb.board[y][2 - x]
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
txt = ""
for x in range(mb.BOARD_SIZE):
    for y in range(mb.BOARD_SIZE):
        txt += mb.board[y][2 - x]
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
-board = []
+txt = ""
for x in range(mb.BOARD_SIZE):
-   col = []
    for y in range(mb.BOARD_SIZE):
        txt += mb.board[y][2 - x]
-       col.append(mb.board[y][2-x])
-   board.append(col)
```
</details>

上記のプログラムが正しく動作することは、下記のプログラムで先程 `print(mb)` で表示した文字列と同じ文字列が表示されることで確認できます。先ほどのプログラムで、`mb` の __`board` 属性を同一局面のデータに置き換えてしまった__ ので、下記のプログラムのように __`mb` のデータを作り直す必要がある__ 点に注意して下さい。

```python
mb = Marubatsu()
mb.move(1, 1)
mb.move(0, 0)
mb.move(1, 0)

txt = ""
for x in range(mb.BOARD_SIZE):
    for y in range(mb.BOARD_SIZE):
        txt += mb.board[y][2 - x]
print(txt)
```

実行結果

```
....o.xo.
```

## 全ての同一局面を表す文字列の計算

__残りの同一局面__ は __同様の方法で文字列に変換__ することができます。下図のそれぞれの同一局面の (x, y) のマスが、一番左の局面のどのマスの値になるかを考えて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86ce95b0-6999-5e72-7f7e-59d36839fb29.png" width="630">

下記はそれぞれの同一局面の (x, y) のマスと一番左の局面のマスの座標の対応表です。

| 同一局面 | (x, y) に対応する元の局面の座標 |
|:-:|:-:|
| 2  | (y, 2 - x)  |
| 3  | (2 - x, 2 - y)  |
| 4  | (2 - y, x)  |
| 5  | (2 - x, y)  |
| 6  | (x, 2 - y)  |
| 7  | (2 - y, 2 - x)  |
| 8  | (y, x)  |

上記の __7 つ__ の同一局面への __変換の処理__ を __1 つずつ記述するのは大変__ なので、7 つの変換の処理を __for 文でまとめて行いたい__ のですが、その方法について少し考えてみて下さい。

上記それぞれの __x 座標と y 座標を表す式__ をよく見ると、__`2`、`x`、`-x`、`y`、`-y` のうちのいくつかを使った式__ で表されていることがわかります。そのため、それぞれの x 座標と y 座標は以下の式で表現できます。

$a×2 + bx + cy$、ただし a は 0 または 1、b と c は -1、0、1 のいずれか

例えば、2 つ目の同一局面の座標は、下記の式で表現できます。

(y, 2 - x) = (0 * 2 +  0 * x +  1 * y, 1 * 2 + -1 * x +  0 * y)

下記は、それぞれの同一局面の x 座標と y 座標を上記の式で表現した際の a、b、c の値を表にまとめたものです。

<table border>
<tr>
  <th rowspan="2">同一局面</th>
  <th rowspan="2">(x, y) に対応する元の局面の座標</th>
  <th colspan="3" style="text-align:center">x 座標</th>
  <th colspan="3" style="text-align:center">y 座標</th>
</tr>
<tr>
  <th style="text-align:center">a</th>
  <th style="text-align:center">b</th>
  <th style="text-align:center">c</th>
  <th style="text-align:center">a</th>
  <th style="text-align:center">b</th>
  <th style="text-align:center">c</th>
</tr>
<tr>
  <td style="text-align:center">2</td>
  <td style="text-align:center">(y, 2 - x) </td> 
  <td style="text-align:right">0</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">-1</td>
  <td style="text-align:right">0</td>
</tr>
<tr>
  <td style="text-align:center">3</td>
  <td style="text-align:center">(2 - x, 2 - y)</td> 
  <td style="text-align:right">1</td>
  <td style="text-align:right">-1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">-1</td>
</tr>
<tr>
  <td style="text-align:center">4</td>
  <td style="text-align:center">(2 - y, x) </td> 
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">-1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
</tr>
<tr>
  <td style="text-align:center">5</td>
  <td style="text-align:center">(2 - x, y)</td> 
  <td style="text-align:right">1</td>
  <td style="text-align:right">-1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
</tr>
<tr>
  <td style="text-align:center">6</td>
  <td style="text-align:center">(x, 2 - y)</td> 
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">-1</td>
</tr>
<tr>
  <td style="text-align:center">7</td>
  <td style="text-align:center">(2 - y, 2 - x)</td> 
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">-1</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">-1</td>
  <td style="text-align:right">0</td>
</tr>
<tr>
  <td style="text-align:center">8</td>
  <td style="text-align:center">(y, x)</td>  
  <td style="text-align:right">0</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
  <td style="text-align:right">1</td>
  <td style="text-align:right">0</td>
</tr>
</table>

__7 種類の同一局面__ のそれぞれに対して上記の __a, b, c の 6 つのデータを用意__ することで、7 つの同一局面を表す文字列を __for 文を使ってまとめて計算__ することができます。そこで、__指定した局面__ に対するの __同一局面を表す文字列の一覧を計算__ する下記のような関数を定義する事にします。

__名前__：同一（same）局面のゲーム盤（board）を表す文字列（text）の一覧を計算（calculate）するので、`calc_same_boardtexts` とする
__処理__：指定した局面の同一局面を表す文字列の一覧を計算する
__入力__：計算の対象となる局面のデータを仮引数 `mb` に代入する
__出力__：同一局面を表す文字列の一覧を表す set を返り値として返す

__返り値を__ list ではなく __set にした理由__ は、例えばゲーム開始時の局面のように、__7 つの同一局面__ の中の __いくつかまたは全部__ が __全く同じゲーム盤になる場合がある__ からです。set にすることで、__同く同じ文字列を set に登録しても__、set の要素が __重複しなくなります__。

`calc_same_boardtexts` は下記のプログラムのように定義できます。

* __1 行目__：`mb` を仮引数とする `calc_same_boardtexts` を定義する
* __2 ~ 8 行目__：上記の表のデータを要素とする、2 次元配列の list を `data` に代入する。`data` の 1 つ目のインデックスは 7 つの同一局面の番号を、2 つ目のインデックスは同一局面のマスの値を計算するために必要となる 6 つのデータを表す
* __9 行目__：同一局面を表す文字列の集合を計算する `boardtexts` を初期化する。その際に、`mb` 自身も同一局面の 1 つなので、`mb` を文字列に変換したデータを要素として持つ set で初期化する
* __10 行目__：7 つの同一局面を表す文字列を順番に計算する繰り返し処理を for 文で記述する。`data` からは 同一局面のマスの値を計算するために必要となる 6 つのデータを `xa` ～ `yc` までの変数に代入する。この変数の名前は、x 座標を計算する a を `xa` のようにした
* __11 ～ 14 行目__：先程記述したプログラムと同様の方法で同一局面を表す文字列を計算する。その際に 14 行目では、`xa` ～ `yc` の値を使って (x, y) のマスに対応する `mb` のゲーム盤のマスの座標を計算する
* __15 行目__：計算した同一局面を表す文字列を `boardtexts` の集合に追加する
* __16 行目__：`boardtexts` を返り値として返す

```python
 1  def calc_same_boardtexts(mb):
 2      data = [ [ 0,  0,  1, 1, -1,  0],
 3               [ 1, -1,  0, 1,  0, -1],
 4               [ 1,  0, -1, 0,  1,  0],
 5               [ 1, -1,  0, 0,  0,  1],
 6               [ 0,  1,  0, 1,  0, -1],
 7               [ 1,  0, -1, 1, -1,  0],
 8               [ 0,  0,  1, 0,  1,  0], ]
 9      boardtexts = set([mb.board_to_str()])
10      for xa, xb, xc, ya, yb, yc in data:
11          txt = ""
12          for x in range(mb.BOARD_SIZE):
13              for y in range(mb.BOARD_SIZE):
14                  txt += mb.board[xa * 2 + xb * x + xc * y][ya * 2 + yb * x + yc * y]
15          boardtexts.add(txt)
16      return boardtexts
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def calc_same_boardtexts(mb):
    data = [ [ 0,  0,  1, 1, -1,  0],
             [ 1, -1,  0, 1,  0, -1],
             [ 1,  0, -1, 0,  1,  0],
             [ 1, -1,  0, 0,  0,  1],
             [ 0,  1,  0, 1,  0, -1],
             [ 1,  0, -1, 1, -1,  0],
             [ 0,  0,  1, 0,  1,  0], ]
    boardtexts = set([mb.board_to_str()])
    for xa, xb, xc, ya, yb, yc in data:
        txt = ""
        for x in range(mb.BOARD_SIZE):
            for y in range(mb.BOARD_SIZE):
                txt += mb.board[xa * 2 + xb * x + xc * y][ya * 2 + yb * x + yc * y]
        boardtexts.add(txt)
    return boardtexts
```
</details>

上記のプログラムを実行した後で、下記のプログラムで先程の図の左の局面に対して、同一局面を表す文字列の一覧を計算します。

```python
print(calc_same_boardtexts(mb))
```

実行結果（見やすいように、途中で改行ました）

```
{'...oo.x..', 'xo..o....', '....o..ox', '....o.xo.',
 '.ox.o....', 'x..oo....', '..x.oo...', '....oo..x'}
```

上記の実行結果と、下記の図を見比べて正しく計算されていることを確認して下さい。なお、`x..oo....` は、__左から順番__ に __0 列目__ の 3 マス、__1 列目__ の 3 マス、__2 列目__ の 3 マスを表します。横ではなく、 __縦方向に順番に並んでいる__ 点に注意して確認して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86ce95b0-6999-5e72-7f7e-59d36839fb29.png" width="630">

なお、__返り値を set にした__ ことで、下記のプログラムのように、ゲーム開始時の局面のように、__同一局面を表すゲーム盤が 1 つしかない場合__ は、`calc_same_bardtexts` の返り値の __set の集合が 1 つ__ になります。

```python
mb.restart() # ゲームをリセットしてゲーム開始時の局面にする
print(calc_same_boardtexts(mb))
```

実行結果

```
{'.........'}
```

:::note
同一局面を計算するアルゴリズムには、下記のようなものもあります。興味がある方は実装してみて下さい。

* 時計回りに 90 度回転した局面を計算する関数を定義する
* x = 1 の軸を中心に反転した局面を計算する関数を定義する
* 時計回りに 90 度回転する処理を 3 回繰り返すことで同一局面を 3 つ計算できる
* その後で、局面を反転することで同一局面を 1 つ計算できる
* その後で、時計回りに 90 度回転する処理を 3 回繰り返すことで同一局面を 3 つ計算できる
:::

## 同一局面を考慮した局面の一覧の計算

同一局面を表す文字列の一覧の計算を行えるようになったので、それを利用することで同一局面を考慮した局面の一覧を下記のプログラムで計算できます。

* __6 行目__：`node.mb` の局面の同一局面を表す文字列の一覧を計算し、`registerd_boards` の要素に追加する。__set に別の set の全ての要素を追加する処理__ は、集合の両方の要素を持つ __[和集合を計算する `|` 演算子](https://qiita.com/ysgeso/items/3b8967122379079a2a82#set-%E3%81%A9%E3%81%86%E3%81%97%E3%81%AE%E6%BC%94%E7%AE%97)__ を使って行うことができる

```python
1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          registered_boards |= calc_same_boardtexts(node.mb)
7          mblist_by_board.append(node.mb)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
        mblist_by_board.append(node.mb)
```
</details>

上記の実行後に下記のプログラムを実行することで、実行結果から〇×ゲームで __同一局面を考慮した場合の局面の数は 765 種類__ であることが確認できました。

```python
print(len(mblist_by_board))
```

実行結果

```
765
```

## 同一局面を考慮したデータによる強解決の AI であるかどうかの判定

次に、同一局面を考慮した強解決の AI であることを判定するためのデータを作成し、そのデータを使って強解決の AI であるかどうかの判定を行うことにします。

まず、上記のプログラムに下記のプログラムの 7 行目を追加することで、[今回の記事の最初](#局面の一覧の計算)で行ったのと同じ方法で、ゲームの決着がついている局面と、合法手と最善手が一致している局面を除いた `mblist_by_board` を計算します。

```python
1  registered_boards = set()
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in registered_boards:
6          registered_boards |= calc_same_boardtexts(node.mb)
7          if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
8              mblist_by_board.append(node.mb)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
        if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
            mblist_by_board.append(node.mb)
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
registered_boards = set()
mblist_by_board = []
for node in mbtree.nodelist:
    txt = node.mb.board_to_str()
    if not txt in registered_boards:
        registered_boards |= calc_same_boardtexts(node.mb)
-       mblist_by_board.append(node.mb)
+       if node.mb.status == Marubatsu.PLAYING and len(node.children) != len(node.bestmoves):
+           mblist_by_board.append(node.mb)
```
</details>

上記の実行後に下記のプログラムを実行することで、実行結果から __強解決の AI であることを判定するために必要な局面の数は 431 種類__ であることがわかりました。最初は 50 万以上の局面を調べていたのと比べて 1/1000 以下になっていることがわかります。

```python
print(len(mblist_by_board))
```

実行結果

```
431
```

### データの保存と `is_strongly_soved` の修正と確認

データが作成できたので、下記のプログラムでファイルに保存します。ファイル名は最小（minimum）の局面数なので `mblist_by_board_min` としました。

```python
with gzip.open("../data/mblist_by_board_min.dat", "wb") as f:
    pickle.dump(mblist_by_board, f)
```

作成された __ファイルのサイズは 5 KB__ で、`mblist_by_board2.dat` の 30 KB よりも __さらにサイズが小さくなる__ ことが確認できました。

次に、このデータで正しく強解決の AI であるかを判定できるかを確認するために、Check_solved クラスの `is_strongly_solved` を下記のプログラムのように修正します。

なお、メソッドの修正箇所は 6 行目で読み込むファイルを mblist_by_board_min.dat に変えた点だけですが、__`Check_solved` クラスの定義を実行し直さない場合__ は、__`mblist_by_board` 属性の値__ には先程 `is_strongly_solved` を実行した結果  __mblist_by_board2.dat から読み込んだデータが代入されたままになっている__ ので、9 行目のように __その属性に `None` を代入する必要がある__ 点に注意して下さい[^1]。

```python
1  @staticmethod
2  def is_strongly_solved(ai, params=None):
3      if Check_solved.bestmoves_by_board is None:
4          Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
5      if Check_solved.mblist_by_board is None:
6          Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board_min.dat")
元と同じなので省略
7
8  Check_solved.is_strongly_solved = is_strongly_solved
9  Check_solved.mblist_by_board = None
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
@staticmethod
def is_strongly_solved(ai, params=None):
    if Check_solved.bestmoves_by_board is None:
        Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
    if Check_solved.mblist_by_board is None:
        Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board_min.dat")            
    if params is None:
        params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist_by_board):
        candidate = set(ai(mb, candidate=True, **params))
        bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist_by_board)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist

Check_solved.is_strongly_solved = is_strongly_solved
Check_solved.mblist_by_board = None
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
@staticmethod
def is_strongly_solved(ai, params=None):
    if Check_solved.bestmoves_by_board is None:
        Check_solved.bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
    if Check_solved.mblist_by_board is None:
-       Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board2.dat")
+       Check_solved.mblist_by_board = load_mblist("../data/mblist_by_board_min.dat")
元と同じなので省略

Check_solved.is_strongly_solved = is_strongly_solved
+Check_solved.mblist_by_board = None
```
</details>

上記の修正後に、下記のプログラムで強解決でない `ai2s`、`ai14s` と強解決の `ai_gt6` を `is_strongly_solved` で判定できるかどうかを確認します。

下記の実行結果のように `ai2s` が強解決の AI でないことを正しく判定できます。また、修正前と同様に実行結果には 0 % が表示されます。

```python
result, incorrectlist = Check_solved.is_strongly_solved(ai2s)
print(result)
```

実行結果

```
100%|██████████| 431/431 [00:00<00:00, 3734.25it/s]
0/431 0.00%
False
```

下記の実行結果のように `ai14s` が強解決の AI でないことが正しく判定できます。また、正しく判定できない局面の数は 431 - 424 = 7 種類であることがわかります。

```python
result, incorrectlist = Check_solved.is_strongly_solved(ai14s)
print(result)
```

```
100%|██████████| 431/431 [00:00<00:00, 2177.32it/s]
424/431 98.38%
False
```

正しく判定できない局面が 7 種類しかないようなので、せっかくなので下記のプログラムでその局面を表示してみることにします。実行結果から __6 つが真ん中の (1, 1)__ を、1 つが __四隅の (0, 0)__ を最善手であると __間違って判断している__ ことが確認できました。__`ai14s` は初手で真ん中のマスに着手を行う AI__ であり、いずれの局面も (1, 1) のマスに着手が行われていないことから、いずれも `ai14s` がゲーム開始時の局面から着手を行った場合には __出現しない局面であり__、__`ai14s` が弱解決の AI であることに影響を与えない__ ことが確認できました。

興味がある方は、それぞれの局面の最善手がどのように間違っているかを確認して下さい。

```python
for mb, candidates, best_moves in incorrectlist:
    print(mb)
    print("candidates", candidates)
    print("best_moves", best_moves)
```

実行結果

```
Turn o
o.X
...
...

candidates {(1, 1)}
best_moves {(0, 1), (0, 2), (2, 2)}
Turn x
oOx
...
...

candidates {(1, 1)}
best_moves {(2, 1), (2, 2)}
Turn x
o.x
...
.O.

candidates {(1, 1)}
best_moves {(2, 2)}
Turn x
xo.
..O
...

candidates {(1, 1)}
best_moves {(0, 2)}
Turn x
.o.
x.O
...

candidates {(0, 0)}
best_moves {(2, 0), (2, 2)}
Turn o
.o.
...
X..

candidates {(1, 1)}
best_moves {(0, 0)}
Turn x
.o.
..O
x..

candidates {(1, 1)}
best_moves {(2, 2), (0, 0)}
```

下記の実行結果のように `ai_gt6` が強解決の AI であることが正しく判定できます。

```python
result, incorrectlist = Check_solved.is_strongly_solved(ai_gt6, params={"bestmoves_by_board": bestmoves})
print(result)
```

実行結果

```
100%|██████████| 431/431 [00:00<00:00, 143540.18it/s]
431/431 100.00%
True
```

# 今回の記事のまとめ

今回の記事では、同一局面を考慮した局面の一覧を計算する方法を紹介し、〇×ゲームの __同一局面を考慮した局面の種類が 765 種類__ しかないことを示しました。

また、__同一局面を考慮__ した場合に __強解決の AI であるかを判定するために必要な局面が 431 種類__ しかないことを示し、その局面の一覧を使って強解決の AI であるかを判定するように `is_strongly_solved` を修正しました。

# 本記事で入力したプログラム

今回の記事で定義した `calc_same_boardtexts` は util.py に保存することにします。

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/111/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [util_new.py](https://github.com/ysgeso/marubatsu/blob/master/111/util_new.py)  | 今回の記事で更新した util.py |
| [mblist_by_board2.dat](https://github.com/ysgeso/marubatsu/blob/master/data/mblist_by_board2.dat)  | 合法手の一覧と最善手が同じ局面を除いた決着がついていない局面の一覧を保存するファイル |
| [mblist_by_board_min.dat](https://github.com/ysgeso/marubatsu/blob/master/data/mblist_by_board_min.dat)  | 合法手の一覧と最善手が同じ局面と、同一局面を除いた決着がついていない局面の一覧を保存するファイル |

# 次回の記事

https://qiita.com/ysgeso/items/847598556d7e49fe2d87

[^1]:筆者も最初はそのことに気づかずに、この後で `is_strongly_solved` を実行した際に繰り返しの数に 431  ではなく 3191 が表示されてしまい、しばらく原因について悩みました