Pythonで〇×ゲームのAIを一から作成する　その109　強解決の AI であるかの判定

# 目次と前回の記事

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

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

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

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

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

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

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

# データファイルの保存場所の変更

これまでの記事では、データが保存された aidata.mbtree や bestmoves.dat などのファイルを __marubatsu.ipynb と同じフォルダに保存__ していましたが、記事が変わるたびにそれらのファイルを記事に対応するフォルダにコピーするのは、__ディスク容量の無駄遣い__ になります。

そこで、今回の記事から、記事を保存するフォルダの __親フォルダに data という名前のフォルダを作成__ し、__その中にデータファイルを保存する__ ことにします。

下記は github のその data フォルダのリンクです。

https://github.com/ysgeso/marubatsu/blob/master/data

## 相対パスの記述方法

これまでは、ファイルを開く際に aidata.mbtree のように、 __ファイル名だけ__ の __ファイルのパス（住所のこと）を記述__ してきましたが、そのようなファイルの記述の方法を __相対パス__ と呼びます。相対パスでは、__実行する python のファイル__（本記事の場合は marubatsu.ipynb のことです）を __基準__ として、__相対的にファイルがどこにあるかを示す__ 方法で、ファイル名だけを記述した場合は、同じフォルダ内のファイルを示すことになります。

相対パスでは、__別のフォルダ__ を下記のように記述します。

* __`フォルダ名/`__ と記述することで、記述した __フォルダ名のフォルダ__ を表す
* __`../`__ と記述することで __親フォルダ__ を表す

先程 aidata.mbtree などのデータファイルを、marubatsu.ipynb が保存されているフォルダから見て、__親フォルダ__ の中の __data__ フォルダの中に保存することにしたので、aidata.mbtree の __相対パス__ は __`../data/aidata.mbtree`__ と記述します。

:::note
ハードディスクを表す C ドライブから順に辿ってファイルのパスを記述する方法を __絶対パス__ と呼びます。エラーメッセージなどで表示される下記の `c:\Users\ys\ai\marubatsu\107\ai.py` が絶対パスで、下記の場合は、C ドライブから順に Uses、ys、ai、marubatsu、107 の順で開いたフォルダ内の `ai.py` という意味を表します。基準となるフォルダが変わると表記が変化する相対パスと異なり、__絶対パス__ は同じファイルは __常に同じパスで記述される__ という特徴があります。

```
File c:\Users\ys\ai\marubatsu\107\ai.py:47, in ai_match(ai, params, match_num)
```
:::

# ルールベースの AI が強解決であるかどうかの検証

前回までの記事で、〇×ゲームの __全ての局面に対する最善手の一覧を計算__ しました。そのようなデータがあれば、以下のようなアルゴリズムで、__任意の AI が強解決の AI であるか__ どうかを __判定__ することができます。

〇×ゲームの、__決着がついていない全ての局面__ に対して下記の処理を行う

1. __その AI が着手する__ 可能性のある __合法手の一覧__ を計算する
2. 手順 1 で計算した合法手の一覧が、その局面の __最善手の一覧に完全に含まれているか__ どうかを判定する
3. __含まれていない合法手が存在する__ 場合は、その AI は __最善手を選択しない局面が存在する__ ので、__強解決の AI ではないことが判明し__、処理を完了する
4. 存在しない場合は、次の局面があれば、次の局面に対して手順 1 ~ 4 の処理を行う
5. __次の局面が存在しない__ 場合は、__全ての局面で最善手のみを選択する__ ことが確定するので、__強解決の AI である__ ことが判明する  

なお、強解決の AI は、全ての局面で __いずれかの最善手を選択できれば良い__ ので、手順 2 では AI が着手する可能性のある合法手の一覧と、その局面の最善手の一覧が __完全に一致する必要はありません__。

以前の記事で作成したルールベースの AI である __`ai14s`__ は、__[ランダムな AI である `ai2s` との対戦による検証](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%AB%E3%82%88%E3%82%8B%E5%BC%B1%E8%A7%A3%E6%B1%BA%E3%81%AE-ai-%E3%81%AE%E5%88%A4%E5%AE%9A)__ を行った結果、__弱解決の性質を持つ可能性が高い__ ことを[以前の記事](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#ai2-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6-1)で確認しましたが、__本当に弱解決の AI であるかどうかの証明まではできませんでした__。

また、弱解決の AI は、その AI がゲーム開始時の局面から着手を行った際に __出現しない局面__ に対しては __最善手を選択するとは限らない__ という点が __強解決の AI と異なります__。ランダムな AI との対戦による検証では、それらの出現しない局面に対して最善手を着手するかどうかの検証を行うことはできなかったので、もしかるすると __`ai14s` が強解決の AI である__ という __可能性があります__。

そこで、上記のアルゴリズムを利用して `ai14s` が強解決の AI であるかどうかを検証することにします。

## AI の関数の修正

上記のアルゴリズムの手順 1 を行うためには、AI の関数が __その局面で選択する可能性がある着手の一覧を返す__ ことができるようにする必要があります。最初に評価値を利用した AI の中で最も単純なランダムな着手を選択する [`ai2s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-%E3%83%AB%E3%83%BC%E3%83%AB-2-%E3%81%AE-ai-%E3%81%AE%E5%AE%9F%E8%A3%85) に対して修正を行い、その後で `ai14s` の修正を行うことにします。

下記は `ai2s` の定義です。`ai2` では、局面の評価値を計算する `eval_func` を、常に 0 を返すように定義する事で、全ての合法手の局面の評価値が同じ 0 になるため、ランダムな着手が選択されます。

```python
def ai2s(mb, debug=False):
    def eval_func(mb):
        return 0
        
    return ai_by_score(mb, eval_func, debug=debug)
```

また、__この関数の返り値は、`ai_by_score` の返り値__ になっているので、下記に `ai_by_score` の定義の中で、__返り値を返す処理__ の部分を抜粋します。

```python
def ai_by_score(mb_orig, eval_func, debug=False, rand=True):
省略
    if rand:   
        return choice(best_moves)
    else:
        return best_moves[0]
```

上記から、`ai_by_score` は、仮引数 `rand` に `True` が代入されている場合は、最善手の一覧が代入されている `best_moves` の中からランダムに 1 つを選択して返し、`False` が代入されている場合は、`best_moves` の最初の要素を返すように定義されていることがわかります。

`ai_by_score` が計算した __その AI にとっての最善手の一覧__[^1]は `best_moves` に代入されているので、`ai_by_score` が __`best_moves` をそのまま返す__ ことができるように修正することで、AI がその局面で選択する可能性がある着手の一覧を返すことができるようになります。

### `ai_by_score` の修正

そこで、下記のプログラムのように、`ai_by_score` に `True` が代入されていた場合は __着手の候補（candidate）__ を返すという意味を持つ、__仮引数 `candidate` を追加__ することにします。

* __5 行目__：互換性を考慮して、デフォルト値を `False` とした仮引数 `candidate` を追加する
* __6、7 行目__：`candidate` が `True` の場合に `best_moves` を返すようにする

```python
 1  from ai import dprint
 2  from copy import deepcopy
 3  from random import choice
 4
 5  def ai_by_score(mb_orig, eval_func, debug=False, rand=True, candidate=False):  
元と同じなので省略
 6      if candidate:
 7          return best_moves
 8      elif rand:   
 9          return choice(best_moves)
10      else:
11          return best_moves[0]
```

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

```python
from ai import dprint
from copy import deepcopy
from random import choice

def ai_by_score(mb_orig, eval_func, debug=False, rand=True, candidate=False):   
    dprint(debug, "Start ai_by_score")
    dprint(debug, mb_orig)
    legal_moves = mb_orig.calc_legal_moves()
    dprint(debug, "legal_moves", legal_moves)
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        dprint(debug, "=" * 20)
        dprint(debug, "move", move)
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        dprint(debug, mb)
        
        score = eval_func(mb)
        dprint(debug, "score", score, "best score", best_score)
        
        if best_score < score:
            best_score = score
            best_moves = [move]
            dprint(debug, "UPDATE")
            dprint(debug, "  best score", best_score)
            dprint(debug, "  best moves", best_moves)
        elif best_score == score:
            best_moves.append(move)
            dprint(debug, "APPEND")
            dprint(debug, "  best moves", best_moves)

    dprint(debug, "=" * 20)
    dprint(debug, "Finished")
    dprint(debug, "best score", best_score)
    dprint(debug, "best moves", best_moves)
    if candidate:
        return best_moves
    elif rand:   
        return choice(best_moves)
    else:
        return best_moves[0]
```
</details>

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

```diff_python
from ai import dprint
from copy import deepcopy
from random import choice

-def ai_by_score(mb_orig, eval_func, debug=False, rand=True):  
+def ai_by_score(mb_orig, eval_func, debug=False, rand=True, candidate=False):  
元と同じなので省略
+   if candidate:
+       return best_moves
+   elif rand:   
-   if rand:   
        return choice(best_moves)
    else:
        return best_moves[0]
```
</details>

### `ai2s` の修正

次に、`ai2s` を上記の修正にあわせて下記のプログラムのように修正します。

* __1 行目__：デフォルト値を `False` とする仮引数 `candidate` を追加する
* __5 行目__：`ai_by_score` にキーワード引数 `candidate=candidate` を追加する

```python
1  def ai2s(mb, debug=False, candidate=False):
2      def eval_func(mb):
3          return 0
4        
5      return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)
```

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

```python
def ai2s(mb, debug=False, candidate=False):
    def eval_func(mb):
        return 0
        
    return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)
```
</details>

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

```diff_python
-def ai2s(mb, debug=False):
+def ai2s(mb, debug=False, candidate=False):
    def eval_func(mb):
        return 0
        
-   return ai_by_score(mb, eval_func, debug=debug)
+   return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)
```
</details>

上記の修正後に、下記のプログラムでゲーム開始時の局面で `ai2s` が選択する着手の一覧を表示すると、実行結果から 9 つの全てのマスが表示されることが確認できます。

```python
ai2s(mb, candidate=True)
```

実行結果

```
[(1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
```

### `ai14s` の修正

`ai14s` は `ai2s` と同様の方法で下記のプログラムのように修正します。

* __3 行目__：デフォルト値を `False` とする仮引数 `candidate` を追加する
* __5 行目__：`ai_by_score` にキーワード引数 `candidate=candidate` を追加する

```python
1  from marubatsu import Markpat
2
3  def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100, score_special=100, \
             score_201=2, score_102=0.5, score_012=-1, debug=False, candidate=False):       
元と同じなので省略
4
5      return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)
```

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

```python
from marubatsu import Markpat

def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100, score_special=100, \
          score_201=2, score_102=0.5, score_012=-1, debug=False, candidate=False):       
    def eval_func(mb):         
        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        

        # 自分が勝利している場合
        if mb.status == mb.last_turn:
            return score_victory

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値を加算する
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            score = score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
        # 次の自分の手番で自分が必ず勝利できる場合
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return score_sure_victory
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
            return score_special    

        # 次の自分の手番で自分が勝利できる場合は評価値に score_201 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += score_201
        # 「自 1 敵 0 空 2」1 つあたり score_102 だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)] * score_102
        # 「自 0 敵 1 空 2」1 つあたり score_201 だけ、評価値を減算する
        score += markpats[Markpat(last_turn=0, turn=1, empty=2)] * score_012
        
        # 計算した評価値を返す
        return score

    return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)
```
</details>

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

```diff_python
from marubatsu import Markpat

-def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100, score_special=100, \
-          score_201=2, score_102=0.5, score_012=-1, debug=False):       
+          score_201=2, score_102=0.5, score_012=-1, debug=False, candidate=False):       
元と同じなので省略

-   return ai_by_score(mb, eval_func, debug=debug)
+   return ai_by_score(mb, eval_func, debug=debug, candidate=candidate)
```
</details>

`ai14s` はゲーム開始時の局面では真ん中のマスにしか着手を行わないので、下記のプログラムでは (1, 1) に着手した局面に対して `ai14s` を実行します。その局面では 4 隅のマスが最善手であり、実行結果からその 4 隅のマスを `ai14s` が選択することが確認できます。

```python
mb.move(1, 1)
ai14s(mb, candidate=True)
```

実行結果

```
[(0, 0), (2, 0), (0, 2), (2, 2)]
```

## 強解決であるかを判定する関数の定義

次に、AI の関数が強解決であるかを判定する下記のような関数を定義する事にします。

__名前__：強解決（strongly solved）であるかを判定するので `is_strongly_solved` とする
__処理__：AI が強解決であるかどうかを判定する
__入力__：仮引数 `ai` に判定する AI の関数を代入する
__出力__：強解決の AI の場合は `True`、そうでない場合は `False` を返す

### 判定に必要となるデータの確認

強解決の AI であるかどうかを判定するためには、任意の局面に対して、下記の手順 1、2 の処理を行う必要があります。

1. その AI が着手する可能性のある合法手の一覧を計算する
2. 手順 1 で計算した合法手の一覧が、その局面の最善手の一覧に完全に含まれているかどうかを判定する

手順 1 は先ほど計算できるようにしました。また、手順 2 のその局面の最善手の一覧は、[前回の記事](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%82%B5%E3%82%A4%E3%82%BA%E3%81%AE%E6%AF%94%E8%BC%83)で作成した bestmoves.dat に保存されたデータを利用することで計算できます。

### `load_bestmoves` 関数の定義

下記は、bestmoves.dat からファイルを読み込むプログラムです。

```python
import pickle
import gzip
with gzip.open("bestmoves.dat", "rb") as f:
    bestmoves = pickle.load(f)
```

毎回このようなプログラムを記述するのは面倒なので、bestmoves.dat を読み込む下記のような関数を定義する事にします。

__名前__：局面ごとの最善手一覧（bestmoves）が記録されたファイルを読み込むので `load_bestmoves` とする
__処理__：局面ごとの最善手一覧が記録されたファイルを読み込む
__入力__：読み込むファイルの名前を仮引数 `fname` に代入する。省略できるように、デフォルト値を先程説明した[相対パス](#相対パスの記述方法)を使って `../data/bestmoves.dat` とする
__出力__：ファイルから読み込んだデータを返り値として返す

下記は、`load_bestmoves` の定義です。難しい点はないと思いますので説明は省略します。

```python
import pickle
import gzip

def load_bestmoves(fname="../data/bestmoves.dat"):
    with gzip.open(fname, "rb") as f:
        return pickle.load(f)
```

上記の実行後に、下記のプログラムで `bestmoves` に bestmoves.dat から読み込んだデータを代入します。

```python
bestmoves = load_bestmoves()
```

### 手順 2 の処理に必要となるデータの計算

次に、手順 2 の処理の例として、ゲーム開始後に (1, 1) に着手を行った下記の局面で `ai2s` と `ai14s` に対して手順 2 の処理を行うことにします。

```python
print(mb)
```

実行結果

```
Turn x
...
.O.
...
```

そのためには、この局面の最善手の一覧と、この局面で `ai2s` と `ai14s` が選択する着手の一覧を計算する必要があります。

下記は、[前回の記事](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#%E3%83%8E%E3%83%BC%E3%83%89%E3%82%92%E6%8E%A2%E3%81%99%E5%87%A6%E7%90%86%E3%81%AE%E5%8A%B9%E7%8E%87%E5%8C%96)で説明した tuple と `records` 属性を使ってこの局面の最善手の一覧を計算するプログラムです。

```python
bestmove = bestmoves[tuple(mb.records)]
print(bestmove)
```

実行結果

```
[(0, 0), (2, 0), (0, 2), (2, 2)]
```

下記はこの局面で `ai2s` と `ai14s` が行う着手の一覧を計算するプログラムです。

```python
moves_ai2s = ai2s(mb, candidate=True)
moves_ai14s = ai14s(mb, candidate=True)
print(moves_ai2s)
print(moves_ai14s)
```

実行結果

```
[(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
[(0, 0), (2, 0), (0, 2), (2, 2)]
```

人間の目で見れば以下の事がわかりますが、この判定をプログラムで行う必要があります。

* `ai2s` が行う着手の一覧の中に、最善手ではない着手が混じっている
* `ai14s` が行う着手は全て最善手である

### set を利用した包含関係の計算

上記の判定を行うために必要な知識は、実は[以前の記事](https://qiita.com/ysgeso/items/3b8967122379079a2a82)で説明済ですが、忘れた方が多いのではないかと思いますので、簡単に説明します。

合法手の一覧や、AI が選択する着手の一覧のように、__重複しないデータを集めたもの__ を __[集合](https://qiita.com/ysgeso/items/3b8967122379079a2a82#%E9%9B%86%E5%90%88%E3%81%A8%E3%81%AF%E4%BD%95%E3%81%8B)__ と呼びます。

手順 2 が行う処理は、__AI が選択する着手の一覧の集合__ が、__最善手の一覧の集合__ に __完全に含まれているか__ どうかを判定することですが、このような、ある集合の要素が別の集合の要素に完全に含まれていることを __[包含関係](https://qiita.com/ysgeso/items/3b8967122379079a2a82#%E5%8C%85%E5%90%AB%E9%96%A2%E4%BF%82%E3%81%A8%E7%9B%B8%E5%BD%93%E9%96%A2%E4%BF%82)__ と呼びます。

Python では、包含関係の判定などの、__集合に関する演算__ を __[set](https://qiita.com/ysgeso/items/3b8967122379079a2a82#set-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)__ という __集合を表すデータ型__ で行うことができ、2 つの set が包含関係にあるかどうかは __[`<=`](https://qiita.com/ysgeso/items/3b8967122379079a2a82#%E5%8C%85%E5%90%AB%E9%96%A2%E4%BF%82%E3%81%A8%E7%9B%B8%E5%BD%93%E9%96%A2%E4%BF%82%E7%AD%89%E3%81%97%E3%81%84%E3%81%AE%E5%88%A4%E5%AE%9A)__ という演算子を使って判定することができます。

Python では __list のデータを__、下記のプログラムのように、組み込み関数 __[`set`](https://qiita.com/ysgeso/items/3b8967122379079a2a82#list-%E3%81%8B%E3%82%89%E3%81%AE%E4%BD%9C%E6%88%90)__ を使って  __set に変換__ することができます。set を `print` で表示すると、実行結果のようにその要素が `{}` で記号で囲まれて表示されます。なお、list を set に変換する際には、その全ての要素がハッシュ可能なデータである必要があります。

```python
print(set(moves_ai2s))
```

実行結果

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

下記のプログラムのように、set どうしを `<=` 演算子で包含関係にあるかどうかを判定することで、実行結果から以下の事がわかります。

* __`ai2s`__ が選択する着手の一覧は、最善手の一覧に __包含されない__
* __`ai14s`__ が選択する着手の一覧は、最善手の一覧に __包含される__

```python
print(set(moves_ai2s) <= set(bestmove))
print(set(moves_ai14s) <= set(bestmove))
```

```python
False
True
```

逆に、包含関係にないことは、下記のプログラムのように `>` 演算子を使って判定することができます。

```python
print(set(moves_ai2s) > set(bestmove))
print(set(moves_ai14s) > set(bestmove))
```

実行結果

```
True
False
```

### `mblist` の保存と `load_mblist` の定義

強解決の AI であるかどうかを判定するためには、〇×ゲームの __決着がついていない全ての局面__ に対して処理を行う必要があり、決着がついていない全ての局面は、[前回の記事](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#ai-%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E5%B7%AE%E3%81%AE%E8%A8%88%E6%B8%AC)で下記のようなプログラムで計算しました。

```python
from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
mblist = []
for node in mbtree.nodelist:
    if node.mb.status == Marubatsu.PLAYING:
        mblist.append(node.mb)
```

ただし、毎回このような処理を記述するのは面倒なので、下記のプログラムで `mblist` のデータを `../data/mblist.dat` というパスのファイルに保存することにします。

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

次に、`load_bestmoves` と同様の方法で、このファイルを読み込んで返り値として返す `load_mblist` を下記のプログラムのように定義します。

```python
def load_mblist(fname="../data/mblist.dat"):
    with gzip.open(fname, "rb") as f:
        return pickle.load(f)
```

### `is_strongly_solved` の定義

:::note alert
下記の __`is_strongly_solved` にはバグがある__ ことが判明しました。次回の記事でバグを説明するために、__あえて間違いのまま説明を進めます__。バグの詳細については次回の記事で説明します。
:::

強解決の AI であるかを判定する方法と、計算するために必要なデータを得る手段がが揃ったので、`is_strongly_solved` は、以下のようなプログラムで定義できます。

* __3 行目__：判定を行う AI の関数を代入する仮引数 `ai` を記述する
* __4 行目__：各局面の最善手の一覧を表すデータをファイルから読み込む
* __5 行目__：決着がついていない局面の一覧を表すデータをファイルから読み込む
* __6 行目__：決着がついていない全ての局面に対する繰り返し処理を行う。局面の数が多いので、[`tqdm`](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#%E3%83%97%E3%83%AD%E3%82%B0%E3%83%AC%E3%82%B9%E3%83%90%E3%83%BC%E3%81%AB%E3%82%88%E3%82%8B%E9%80%94%E4%B8%AD%E7%B5%8C%E9%81%8E%E3%81%AE%E8%A1%A8%E7%A4%BA) を使ってプログレスバーを表示するようにする
* __7 行目__：先ほど説明した方法を使って、`mb` の局面に対して `ai` が行う着手の一覧が、最善手の一覧に対して __包含関係にない__ ことを判定する
* __8 行目__：包含関係にない場合は、__強解決の AI ではない__ ので、`False` を返して終了する
* __9 行目__：__繰り返し処理が完了__ した場合は、__全ての局面が包含関係__ なので `True` を返す

```python
1  from tqdm import tqdm
2
3  def is_strongly_solved(ai):
4      bestmoves = load_bestmoves()
5      mblist = load_mblist()
6      for mb in tqdm(mblist):
7          if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
8              return False
9      return True
```

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

```python
from tqdm import tqdm

def is_strongly_solved(ai):
    bestmoves = load_bestmoves()
    mblist = load_mblist()
    for mb in tqdm(mblist):
        if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
            return False
    return True
```
</details>

### `ai2s` と `ai14s` の判定

まず、下記のプログラムで `ai2s` が強解決の AI であるかを判定すると、実行結果のように `False` が表示されるので強解決の AI ではないことがわかりました。`ai2s` はランダムな着手を行うので当然の結果でしょう。なお、__繰り返しの途中で処理が終了__ したので、プログレスバーは __0% で表示が止まります__。

```python
is_strongly_solved(ai2s)
```

実行結果

```
  0%|          | 1/294778 [00:00<?, ?it/s]
False
```

次に、下記のプログラムで `ai14s` が強解決の AI であるかを判定すると、実行結果のように `True` が表示されるので強解決の AI であることがわかりました。このことから、__[ルール 14](https://qiita.com/ysgeso/items/6b78ddb53b254a850457#%E3%83%AB%E3%83%BC%E3%83%AB-14-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ が実は __強解決の AI を作成するルールであった__ ことがわかりました。

:::note alert
`is_strongly_solved` にはバグがあるため、__`ai14s` が強解決の AI であるという判定は間違いである__ ことが判明しました。詳細については次回の記事で説明します。
:::

```python
is_strongly_solved(ai14s)
```

実行結果

```
100%|██████████| 294778/294778 [00:46<00:00, 6373.50it/s]
True
```

## `is_strongly_solved` の改良

`is_strongly_solved` には、いくつかの改良点があるので改良することにします。

### データファイルの読み込みの問題の修正

`is_strongly_solved` では __毎回__ `load_bestmoves` と `load_movelist` で __ファイルからデータを読み込むため__、`is_strongly_solved` を実行してからプログレスバーが表示されるまでに少し時間がかかります。

__何度も `is_strongly_solved` を実行する場合__ に __毎回同じファイルを読み込むのは無駄__ なので、一度  `is_strongly_solved` を実行した後では、__読み込んだデータをとっておき__、__次回からは__ それらのファイルを __読み込まないようにする__ ように修正することにします。

そのような処理を行う方法の一つに、__`is_strongly_solved`__ を __クラスのメソッドとして定義__ し、ファイルから読み込んだ `bestmoves` と `movelist` をその __クラス属性に代入する__ という方法が考えられます。その理由は、__クラスの定義の中で記述__ された __クラス属性への代入処理__ は、__クラスの定義を実行した際に一度だけ実行される__ からです。

また、__そのクラス__ はこれまでの記事で定義してきたクラスのようにインスタンスを作成して利用するのではなく[^2]、インスタンスを介さずに __クラスから__ `is_strongly_solved` メソッドを __直接呼び出して利用__ します。そのため、`is_strongly_solved` は __インスタンスの情報を利用しない__、__静的メソッド__ として定義します。また、インスタンスを作成しないので、 __`__init__` メソッドを定義する必要はありません__。

クラスの名前は、AI が解決されているか（solved）どうかを判定（check）する処理を行うので、__`Check_solved`__ という名前にし、下記のプログラムのように定義します。



* __2、3 行目__：クラス属性 `bestmoves` と `mblist` にファイルから読み込んだデータを代入する。クラス属性に値を代入する処理は[以前の記事](https://qiita.com/ysgeso/items/ad5e7ddb071653fd2ac5#%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E5%B1%9E%E6%80%A7%E3%81%AE%E8%A8%98%E8%BF%B0%E6%96%B9%E6%B3%95)で説明したようにメソッドの定義の前に記述し、この処理はクラスの定義を実行した際に 1 度だけ実行される
* __5 ~ 10 行目__：このクラスはインスタンスを作成して利用しないので、`@staticmethod` を記述して静的メソッドとして `is_strongly_solved` を定義する。メソッドの中でクラス属性を利用する際には、`クラス名.クラス属性名` と記述する必要がある点に注意する事


```python
 1  class Check_solved:
 2      bestmoves = load_bestmoves()
 3      mblist = load_mblist()
 4   
 5      @staticmethod
 6      def is_strongly_solved(ai):
 7          for mb in tqdm(Check_solved.mblist):
 8              if set(ai(mb, candidate=True)) > set(Check_solved.bestmoves[tuple(mb.records)]):
 9                  return False
10          return True
```

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

```python
class Check_solved:
    bestmoves = load_bestmoves()
    mblist = load_mblist()
    
    @staticmethod
    def is_strongly_solved(ai):
        for mb in tqdm(Check_solved.mblist):
            if set(ai(mb, candidate=True)) > set(Check_solved.bestmoves[tuple(mb.records)]):
                return False
        return True
```
</details>

上記を実行すると、2、3 行目の処理が実行されて、ファイルからデータが読み込まれるので、処理の完了までに少し時間がかかります。

`is_storngly_solved` は、下記のプログラムのように `Check_solved` のインスタンスを作成せずに __静的メソッドを直接呼び出す__ ことで実行します。その際に `bestmoves` などをファイルから読み込むという __無駄な処理は行われません__。なお、実行結果は先ほどと同様です。

```python
Check_solved.is_strongly_solved(ai14s)
```

実行結果

```
100%|██████████| 294778/294778 [00:53<00:00, 5468.21it/s]
True
```

### 包含関係にない局面の数を表示する

`ai2s` に対して `is_strongly_solved` メソッドを実行すると `False` だけが表示されるのが物足りないと思った人はいないでしょうか。そこで、局面の中で __包含関係にある数を数えて表示__ することで、全ての局面の中で __どのくらいの割合で最善手を着手する局面があるか__ を表示するように改良することにします。

下記は、そのように `is_strongly_solved` メソッドを改良したプログラムです。

* __3 行目__：包含関係を満たす局面の数を数える `count` を `0` で初期化する
* __5、6 行目__：包含関係にある場合に、`count` を `1` 増やす。元は包含関係にないことを判定していたが、ここでは __包含関係があることを判定__ している点に注意する事
* __7 行目__：局面の数（`Check_solved.mblist` の要素の数に等しい）を計算する
* __8 行目__：「包含関係にある局面の数/全局面の数」と「包含関係にある局面の数の割合」を表示する
* __9 行目__：__強解決の AI__ の場合は、__包含関係にある局面の数と全局面の数が等しい__ ので、それを計算して返り値として返す

```python
 1  @staticmethod
 2  def is_strongly_solved(ai):
 3      count = 0
 4      for mb in tqdm(Check_solved.mblist):
 5          if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
 6              count += 1
 7      nodenum = len(Check_solved.mblist)
 8      print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
 9      return count == nodenum
10
11  Check_solved.is_strongly_solved = is_strongly_solved
```

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

```python
@staticmethod
def is_strongly_solved(ai):
    count = 0
    for mb in tqdm(Check_solved.mblist):
        if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
            count += 1
    nodenum = len(Check_solved.mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum

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

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

```diff_python
@staticmethod
def is_strongly_solved(ai):
    count = 0
    for mb in tqdm(Check_solved.mblist):
-       if set(ai(mb, candidate=True)) > set(Check_solved.bestmoves[tuple(mb.records)]):
+       if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
-           return False
+           count += 1
-   return True
+   nodenum = len(Check_solved.mblist)
+   print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
+   return count == nodenum

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

上記の修正後に、下記のプログラムを実行すると、実行結果より `ai2s` が最善手のみを選択する局面が全体の約 60 % もある事がわかります。これは、__深さが深いノードの数が多く__、深さが深いノードは __合法手の数が少ない__ ので、__全ての合法手が最善手になる局面が多い__ ことが原因だと思われます。例えば、深さが 8 のノードは合法手が最大でも 1 つしかないので、全ての合法手が必ず最善手になります。

```python
Check_solved.is_strongly_solved(ai2s)
```

実行結果

```
100%|██████████| 294778/294778 [00:43<00:00, 6851.92it/s]
173985/294778 59.02%
False
```

本記事では行いませんが、興味がある方は、`ai1s` ~ `ai13s` を最善手の一覧を返すことができるように修正し、`is_strongly_solved` を実行してみて下さい。

# 今回の記事のまとめ

今回の記事では、AI が強解決の AI であるかを判定する方法を紹介しました。また、その方法で判定を行った結果、`ai14s` が強解決の AI であることが判明しました。

:::note alert
`is_strongly_solved` にはバグがあるため、__`ai14s` が強解決の AI であるという判定は間違いである__ ことが判明しました。詳細については次回の記事で説明します。
:::

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

今回の記事で定義した `load_bestmoves`、`load_mblist`、`Check_solved` クラスは util.py に保存することにします。

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/109/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [ai_new.py](https://github.com/ysgeso/marubatsu/blob/master/109/ai_new.py)  | 今回の記事で更新した ai.py |
| [util_new.py](https://github.com/ysgeso/marubatsu/blob/master/109/util_new.py)  | 今回の記事で更新した util.py |
| [mblist.dat](https://github.com/ysgeso/marubatsu/blob/master/data/mblist.dat)  | 決着がついていない局面の一覧を保存するファイル |

# 次回の記事

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

| 更新日時 | 更新内容 |
|:--|:--|
| 2024/8/25 | `is_strongly_solved` にバグがあり、`ai14s` が強解決の AI であるという判定が間違っていたことを追記しました |

[^1]:ここでいう最善手とは、仮引数 `eval_func` に渡された関数によって計算された局面の評価値が、最も高くなるような合法手の一覧です。従って、この `best_moves` はその AI が最善と考えた合法手の一覧にすぎないので、本当の最善手とは異なる点に注意して下さい
[^2]:インスタンスを作成することは可能ですが、__作成しても意味はありません__。