Pythonで〇×ゲームのAIを一から作成する　その110　データ型による演算子の処理の違いによるバグとboard 属性を利用した局面の表現

# 目次と前回の記事

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

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

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

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

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

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

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

# 前回の記事のバグの説明

前回の記事では、`ai14s` が強解決の AI であることを示したつもりだったのですが、それは __最初に定義した `is_strongly_solved` にバグがあったため__ であることが判明しました。

:::note alert
この後で示しますが、実際には __`ai14s` は強解決の AI ではありません__。
:::

今回の記事では最初にそのバグの原因を説明します。

## バグの発見の経緯

[前回の記事](https://qiita.com/ysgeso/items/80f19df519a6a856bbf8#is_strongly_solved-%E3%81%AE%E5%AE%9A%E7%BE%A9)では、最初に `is_strongly_solved` を下記のプログラムのように定義しました。

```python
from util import load_bestmoves, load_mblist
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
```

そして、下記のプログラムを実行し、実行結果に `True` が表示されたので `ai14s` が強解決の AI だと判断しました。

```python
from ai import ai14s

is_strongly_solved(ai14s)
```

実行結果

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

[前回の記事](https://qiita.com/ysgeso/items/80f19df519a6a856bbf8#%E5%8C%85%E5%90%AB%E9%96%A2%E4%BF%82%E3%81%AB%E3%81%AA%E3%81%84%E5%B1%80%E9%9D%A2%E3%81%AE%E6%95%B0%E3%82%92%E8%A1%A8%E7%A4%BA%E3%81%99%E3%82%8B)では、その後で下記のプログラムのように `is_strongly_solved` を `Check_solved` クラスの静的メソッドとして定義するように改良し、`ai2s` に対して `is_strongly_solved` でチェックを行ったのですが、その時点で満足してしまい、__`ai14s` に対するのチェックを怠ってしまいました__。

```python
class Check_solved:
    bestmoves = load_bestmoves()
    mblist = load_mblist()
    
    @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
```

前回の記事を投稿した後で、念のために下記のプログラムで __`ai14s` をチェック__ した所、実行結果のように `ai14s` が 294778 - 294690 = __88 の局面で最善手以外の合法手を選択する__ ため、__強解決の AI ではない__ という、先程と異なる判定が表示されました。

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

実行結果

```
100%|██████████| 294778/294778 [00:51<00:00, 5721.66it/s]
294690/294778 99.97%
False
```

この __2 つの結果は矛盾する__ ので、どちらか（もしくは両方）のプログラムが間違っていることがわかりました。

## バグを発生させてしまった理由

結論から言うと、__最初に定義したプログラムが間違っています__。そこで、間違ったプログラムを記述してしまった理由について説明します。

下記は[前回の記事](https://qiita.com/ysgeso/items/80f19df519a6a856bbf8#%E3%83%AB%E3%83%BC%E3%83%AB%E3%83%99%E3%83%BC%E3%82%B9%E3%81%AE-ai-%E3%81%8C%E5%BC%B7%E8%A7%A3%E6%B1%BA%E3%81%A7%E3%81%82%E3%82%8B%E3%81%8B%E3%81%A9%E3%81%86%E3%81%8B%E3%81%AE%E6%A4%9C%E8%A8%BC)で説明した __強解決の AI であるかを判定__ するためのアルゴリズムです。

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

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

記述が長くなるので、以下の説明では A と B という記号を下記の意味で使います。

* ある局面での __AI が着手する可能性のある合法手の一覧__ を表す集合を __A__ とする
* 同じ局面の __合法手の一覧を表す集合__ を __B__ とする

上記の手順 2 では、A の要素が B の要素に完全に含まれているという、数学では $A ⊆ B$ という記号で記述される、__包含関係__ があることを判定します。そして、次の手順 3 では $A ⊆ B$ __ではない場合__ に __強解決の AI ではない__ ことを判定します。

python の集合を表す set は、$A ⊆ B$ であることを __`<=`__ という演算子で計算できるので、最初に定義した `is_strongly_solved` では、上記の手順 3 で __そうではないことを判定__ するために、下記のプログラムのように __`>`__ という演算子で判定しましたが、__それがバグの原因です__。

```python
if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
    return False
```

### 数値と set に対する `<=` 演算子と `>` の違い

このようなミスをしてしまった理由は、__数値__ と __set__ で __`<=`__ 演算子と __`>`__ 演算子が行う __計算の性質__ が下記のように __異なるから__ です。

* 数値に対する `<=` 演算子は、前の数値が後の数値「__以下__」であることを判定する
* 数値に対する `>` 演算子は、前の数値が後の数値「__より大きい__」ことを判定する
* 従って、2 つの数値 `a`、`b` に対して、`a <= b` と `a > b` の計算結果は、__必ず `True` と `False` が逆になる__

従って、数値に対しては `<=` と `>` は逆の意味の計算を行うため、`<=` の条件が満たされないことを判定するために、`<` 演算子を利用することができます。

何を当たり前のことを言っているのだと思っている人がいるかもしれませんが、__set__ では `<=` 演算子と `>` 演算子は、同じ記号を使っていますが __上記と異なる__ 下記の __計算を行います__。

* set に対する `<=` 演算子は、前の集合を a、後ろの集合を b とすると、以下のいずれかの場合に `True` を計算する
    * a の全ての要素が b の要素に含まれる（$a ⊆ b$ という包含関係）
    * a と b の要素が等しい（$a = b$ という相当関係）
* set に対する `>` 演算子は、以下の場合に `True` を計算する
    * b の全ての要素が a の要素に含まれるが`a` と `b` の要素は等しくない（$a ⊃ b$ という包含関係。$a ≠ b$ である）

set に対する `a <= b` と `a > b` の計算は数値の場合と異なり、__逆の計算を行うわけではありません__。そのため、その 2 つの計算結果が __必ずしも `True` と `False` のように逆になるとは限らない__ ので、__`<=` の条件が満たされないことを判定するために、`<` 演算子を利用することはできません__。

具体例を挙げて説明します。例えば、下記のプログラムのように `a` の全ての要素が `b` に含まれる場合は、`b` の要素の中に `a` に含まれない要素は絶対に存在しないので `a <= b` と `a > a` の計算結果は `True` と `False` が逆になります。

```python
a = set([1, 2])
b = set([1, 2, 3])
print(a <= b)
print(a > b)
```

実行結果

```
True
False
```

下記のプログラムのように、`a` と `b` の前後を入れ替えても同様です。このように、__どちらかが片方を包含している場合__ は、`True` と `False` は確かに逆になります。

```python
print(b <= a)
print(b > a)
```

実行結果

```
False
True
```

しかし、下記のプログラムのように、`a` と `b` に __それぞれお互いの要素に含まれない要素が存在する場合__ は、`a <= b` と `b > a` の __両方が `False` になります__。これは、__どちらの集合ももう片方の集合に対する包含関係にない場合__ です。

```python
a = set([1, 2])
b = set([2, 3])
print(a <= b)
print(a > b)
```

実行結果

```
False
False
```

:::note warn
Python の __`<=`__ 演算子と __`>`__ 演算子は以下のような関係にある。

* __数値型__ のデータに対しては、それぞれが必ず逆の計算を行うため、__両方の計算結果は必ず `True` と `False` が逆になる__
* __set__ に対しては、下記のように __必ずしも逆の計算が行われるわけではない__ 
    * 片方が __包含関係にある__ 場合は、__`True` と `False`__ になる
    * どちらも __包含関係にない__ 場合は、__両方とも `False` になる__
:::

:::note
同じ演算子が異なる計算を行う他の例としては、数値に対しては加算を行い、文字列に対しては結合を行う `+` 演算子があります。

これまで説明していませんでしたが、Python ではクラスに特殊メソッドを定義する事で、`+` や `<=` 等の __演算子が行う処理を自分で定義する事ができます__。そのため、他にも同様の例が無数に存在します。

なお、その方法については必要になった時点で紹介します。
:::

### 間違った判定が行われる理由

下記のプログラムが間違っているのは、`A <= B` ではないことを判定するために `A > B` という式を記述していることです。`A <= B` と `A > B` の __両方が `False` になる局面__ では、AI が __最善手を選択しないにもかかわらず__、__`A > B` が `False` になる__ ため、強解決の AI ではないにもかかわらず、下記のプログラムではそのことを __正しく判定できません__。

```python
if set(ai(mb, candidate=True)) > set(bestmoves[tuple(mb.records)]):
    return False
```

一方、修正後の下記のプログラムでは、__`A <= B` の条件を満たす局面の数を数え__、その後で __そのような局面の数が全局面の数と等しい場合__ に強解決の AI であることを判定しているので、強解決の AI であることを __正しく判定することができます__。

```python
if set(ai(mb, candidate=True)) <= set(Check_solved.bestmoves[tuple(mb.records)]):
     count += 1
```                

### 演算子の記号による錯覚

上記のような間違ったプログラムを記述してしまった原因は、数値に対する `<=` と `>` の演算子が逆の計算を行うため、set に対しても __同様に逆の計算を行う__ と __錯覚して勘違いしてしまったから__ です。数学の世界で集合の包含関係を $A ≦ B$ ではなく、$A ⊆ B$ のように __別の記号を使って表す__ のは、集合に対する $⊆$ という記号の性質が、数値に対する $≦$ とは __異なる性質を持つ__ からです。

:::note warn
残念ながら python だけでなく、ほとんどのプログラム言語では、__演算子には__ `<` のような __半角の記号しか使うことができない__ ので、python では `<=` という演算子を集合の $⊆$ という演算子として __代用__ しています。そのため、__演算子の見た目から__ 筆者が行ったような __勘違いが起きやすい__ ので __気を付ける必要があります__。
:::

なお、修正後の `Check_solved.is_strongly_solved` は正しい処理を行うので、プログラムを修正する必要はありません。

# `ai14s` が最善手を選択しない局面の検証

先程の下記のプログラムの実行結果から、`ai14s` には __最善手を選択しない局面が 88 個ある__ ことがわかりました。そこで、__どのような局面で `ai14s` が最善手を着手しないかを検証できる__ ように `is_strongly_solved` を修正することにします。

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

実行結果

```
100%|██████████| 294778/294778 [00:51<00:00, 5721.66it/s]
294690/294778 99.97%
False
```

具体的には、下記のプログラムのように、__最善手を選択しない局面であると判定した場合に__、「その局面」、「AI が選択する着手の一覧」、「最善手の一覧」を __記録し__、関数の __返り値として返す__ ように修正することにします。

* __4 行目__：最善手以外の、間違った（incorrect）着手が含まれている局面のデータを記録する `incorrectlist` という変数を空の list で初期化する
* __6 ~ 8 行目__：AI が選択する着手の候補の集合と、最善手の集合を `candidate` と `bestmoves` に代入し、それを使って判定を行うように修正する。なお、変数に代入した理由は 11 行目でそれらの値を記述する必要があるからである
* __10、11 行目__：間違った着手が含まれている場合に、「その局面」、「AI が選択する着手の一覧」、「最善手の一覧」を要素とする tuple を `incorrectlist` の要素に追加する
* __14 行目__：返り値に、`incorrectlist` を含めるように修正する

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

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

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

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

## 最善手を着手しない局面の表示

上記の修正後に、下記のプログラムで `ai14` を `is_strongly_solved` で判定し、その結果を `result` と `incorrectlist` に代入します。

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

実行結果

```
100%|██████████| 294778/294778 [00:50<00:00, 5833.35it/s]
294690/294778 99.97%
```

`incorrectlist` には 88 個の要素があり、それらをすべて表示すると実行結果の表示が長くなるので、下記のプログラムのように、__最初の要素のみを表示__ してみることにします。

```python
mb, candidate, bestmoves = incorrectlist[0]
print(mb)
print("candidate", candidate)
print("bestmoves", bestmoves)
```

実行結果

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

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

:::note
下記のプログラムで表示すればよいと思った人がいるかもしれませんが、実行結果のようにゲーム盤がクラスの情報として表示されてしまいます。

```python
print(incorrectlist[0])
```

実行結果

```
(<marubatsu.Marubatsu object at 0x0000020B2AE5D0D0>, {(1, 1)}, {(0, 1), (0, 2), (2, 2)})
```
:::

## 最善手を着手しない局面の検証

上記の結果から、`ai14s` は、下記の局面では (1, 1) のみを着手しますが、確かにその着手は最善手の一覧である (0, 1), (0, 2), (2, 2) には入っていません。

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

直観的には真ん中の (1, 1) のマスは有利になるマスなので、(1, 1) が最善手ではないといわれても納得できない人がいるかもしれません。そこで、念のため (1, 1) が本当に __最善手ではないことを検証__ してみることにします。

(1, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(2, 2) に 〇 が着手を行うと 〇 が勝利するので、× は (2, 2) に着手を行う必要があります。

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

(2, 2) に × が着手を行うと下記の局面になります。この局面では、(2, 1) に × が着手を行うと × が勝利するので、〇 は (2, 1) に着手を行う必要があります。

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

(2, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(0, 1) に 〇 が着手を行うと 〇 が勝利するので、× は (0, 1) に着手を行う必要があります。

```
Turn x
o.x
.oO
..x
```

(0, 1) に × が着手を行うと下記の局面になります。長くなるので省略しますが、この局面から 〇 がどこに着手を行っても × が最善手を着手すると引き分けになります。特に難しくはないと思いますので、実際に確認してみて下さい。

```
Turn o
o.x
Xoo
..x
```

次に、最善手の一覧の中の (0, 1) が最善手であることを実証してみることにします。

(0, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(0, 2) に 〇 が着手を行うと 〇 が勝利するので、× は (0, 2) に着手を行う必要があります。

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

(0, 2) に × が着手を行うと下記の局面になります。この局面では、(1, 1) に × が着手を行うと × が勝利するので、〇 は (1, 1) に着手を行う必要があります。

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

(1, 1) に 〇 が着手を行うと下記の局面になります。この局面では、(2, 1) と (2, 2) のどちらかに 〇 が着手を行うと 〇 が勝利しますが、× がその両方を阻止することはできないので、この時点で 〇 の勝利が確定します

```
Turn X
o.x
oO.
x..
```

上記から __この局面は必勝の局面__ であることがわかりますが、(1, 1) の着手を行うと引き分けになるので、この局面で __`ai14s` は最善手を選択しない__ ことが確認できました。

## `ai14s` が弱解決の AI でなくなるかどうかの検証

`ai14s` は強解決の AI ではないことが確認できましたが、最善手を選択しない局面があっても、__弱解決の AI ではないとは限りません__。その理由は、弱解決の AI は、その AI がゲーム開始時の局面から着手を行った際に __出現しない局面__ に対しては __最善手を選択する必要がない__ からです。

そこで、__先程の局面が__、`ai14s` ががゲーム開始時の局面から着手を行った際に __出現しない局面であるか__ どうかを検証することにします。

下記のプログラムで __`ai14s` がゲーム開始時の局面で行う着手の一覧__ を表示すると、実行結果に [(1, 1)] が表示されることから、__必ず (1, 1) に着手を行います__。

```python
from marubatsu import Marubatsu

mb = Marubatsu()
ai14s(mb, candidate=True)
```

実行結果

```
[(1, 1)]
```

先程検証した最善手以外の着手を選択する可能性がある下記の局面では、__〇 の 2 手目の手番__ で、__〇 が (1, 1) 以外のマスに着手されている__ ので、この局面は `ai14s` が 〇 を担当した場合に __出現することはありません__。従って、この局面で `ai14s` が最善手を選択していなくても弱解決の AI であることに影響はありません。

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

他の最善手以外の着手を選択する可能性がある局面に対するチェックは大変なので行いませんが、ランダムな着手を行う `ai2s` との対戦で `ai14s` は敗北しないので、`ai14s` が弱解決の AI である可能性は高いでしょう。

# `board` 属性による最善手の対応表

[以前の記事](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#dict-%E3%81%AE%E3%82%AD%E3%83%BC%E3%81%A8%E3%81%97%E3%81%A6%E5%88%A9%E7%94%A8%E5%8F%AF%E8%83%BD%E3%81%AA%E5%B1%80%E9%9D%A2%E3%82%92%E8%A1%A8%E3%81%99%E3%83%87%E3%83%BC%E3%82%BF)では、局面のデータからゲーム木のノードを探すために、__棋譜を表す `records` 属性__ を使って __局面を表すデータを表現__ しました。また、[以前の記事](https://qiita.com/ysgeso/items/949d18e60939d510c931#%E6%AD%A3%E3%81%97%E3%81%84%E5%90%84%E6%B7%B1%E3%81%95%E3%81%AE%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%95%B0%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95)でゲーム木には 549946 個のノードがあることがわかっているので、局面を表すデータは 50 万以上ある事になります。

一方、〇× ゲームではゲーム盤の状況を表す __`board` 属性の値が同じであれば__、その局面に至るまでの棋譜に関わらず __最善手は同じになる__ ので、__最善手を計算するだけであれば__、ゲーム盤の状況を表す __`board` 属性のデータを使って局面のデータを表現してもかまいません__。

また、ゲーム開始時の局面から (0, 0)、(1, 1)、(2, 2) の順で着手が行われた場合と、(2, 2)、(1, 1)、(0, 0) の順で着手が行われた場合のように、棋譜が異なっていても __`board` 属性の値が同じになる局面が多数存在する__ ため、`board` 属性の種類は 549946 よりは少なくなります。そのため、`board` 属性の値をキーとした局面と最善手の対応表は、棋譜を表す `records` 属性の値をキーとした局面と最善手の対応表よりも __データサイズを小さくすることができます__。

そこで、`board` 属性の値をキーとした局面と最善手の対応表を作成することにします。

## `board` 属性のハッシュ可能なデータへの変換

`board` 属性の値は、下記のプログラムの実行結果のように、__list を入れ子にしたデータ__ です。__list はハッシュ可能なデータではない__ ので、このままでは __dict のキーとして利用することはできません__。そのため、`board` 属性の値を[以前の記事](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#dict-%E3%81%AE%E3%82%AD%E3%83%BC%E3%81%A8%E3%81%97%E3%81%A6%E5%88%A9%E7%94%A8%E5%8F%AF%E8%83%BD%E3%81%AA%E5%B1%80%E9%9D%A2%E3%82%92%E8%A1%A8%E3%81%99%E3%83%87%E3%83%BC%E3%82%BF)で `records` 属性の値に対して行ったように、__ハッシュ可能なデータに変換する必要があります__。

```python
print(mb.board)
```

実行結果

```
[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
```

その際に、下記のプログラムのように、`records` 属性を変換した場合と同じ方法で組み込み関数 [`tuple` を使って変換を行う](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#dict-%E3%81%AE%E3%82%AD%E3%83%BC%E3%81%A8%E3%81%97%E3%81%A6%E5%88%A9%E7%94%A8%E5%8F%AF%E8%83%BD%E3%81%AA%E5%B1%80%E9%9D%A2%E3%82%92%E8%A1%A8%E3%81%99%E3%83%87%E3%83%BC%E3%82%BF)と、実行結果のように、変換された __tuple の要素は list のままになる__ のでハッシュ可能なデータにはなりません。

```python
print(tuple(mb.board))
```

実行結果

```
(['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.'])
```

### `board` 属性の文字列への変換

このような場合は、list の要素も tuple に変換するプログラムを記述する必要がありますが、そのようなプログラムを記述するのは少々面倒です。別の方法として、`board` 属性のように、__要素がすべて文字列データの場合__ は、__全ての要素を連結__ することで、ハッシュ可能なデータである __文字列型のデータに変換する__ という方法があります。例えば、上記のデータの場合は、下記のような 9 文字の文字列型のデータに変換します。

```
.........
```

:::note
このような変換を行う場合は list の __全ての要素__ が __同じ長さの文字列である必要__ があります。異なる長さの文字列の場合は、下記のように間に "," 等の記号を挟んで結合しなければ、どこで区切ればよいかがわからなくなるためです

```
.,.,.,.,.,.,.,.,.
```
:::

:::note
詳細は省略しますが、`board` 属性の値を文字列型のデータに変換したほうが、tuple に変換した場合よりも __データのサイズが小さくなるという利点があります__。
:::

list の要素の連結は、[以前の記事](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#join-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AB%E3%82%88%E3%82%8B%E6%96%87%E5%AD%97%E5%88%97%E3%81%AE%E5%A4%89%E6%8F%9B)で説明した、文字列型のデータの __`join`__ メソッドを使って行うことができます。以前の記事では、下記のプログラムのように、list の要素に文字列が代入されていた場合の連結を行いましたが、`board` 属性では list の要素に list が入れ子で代入されているので下記のプログラムではうまく変換できません。

```python
coords = ['A1', 'A2', 'B1', 'B2', 'C1']
print("".join(coords))
```

実行結果

```
A1A2B1B2C1
```

`board` 属性の場合は、下記のプログラムのように、__list の要素を順番に連結__ して文字列に変換してから、__`+` 演算子を使って結合__ を行う必要があります。実行結果のように、正しく連結が行われていることが確認できます。

* __1 行目__：連結した文字列を計算する `txt` を空文字で初期化する
* __2 行目__：`board` 属性から各列（column）のデータを表す要素を順番に取り出す繰り返し処理を行う
* __3 行目__：列のデータは文字列を要素とする list なので、`join` を使って要素を連結することができ、連結した文字列を `+` 演算子で `txt` に結合する

```python
1  txt = ""
2  for col in mb.board:
3      txt += "".join(col)
4  print(txt)
```

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

```python
txt = ""
for col in mb.board:
    txt += "".join(col)
print(txt)
```
</details>

実行結果

```
.........
```

なお、変換された文字列は、ゲーム盤のマスを表す文字を、左上の (0, 0) のマスから __縦方向の列ごとに文字列に変換__ します。従って、上記の実行結果の文字列は、先頭の文字から (0, 0)、(0, 1)、(0, 2)、(1, 0)、(1, 1)・・・の順でゲーム盤のマスを表します。

:::note
わかりづらくなるので本記事では採用しませんが、下記のプログラムのように、list 内包表記を使って、1 行で上記の処理を記述することもできます。

```python
txt = "".join(["".join(col) for col in mb.board])
print(txt)
```

実行結果

```
.........
```

上記のプログラムでは、下記のプログラムのように list 内包表記を使って、list の各要素を連結した新しい list を作成し、その list に対して連結を行っています。

```python
print(["".join(col) for col in mb.board])
```

実行結果

```
['...', '...', '...']
```

こちらの方が良いと思った人は採用して下さい。
:::

### `board` を文字列に変換するメソッドの定義

上記の処理を毎回記述するのは面倒なので、Marubatsu クラスに下記のようなメソッドを定義する事にします。

__名前__：__`borad`__ 属性を文字列（string）型のデータに変換するので __`board_to_str`__ と命名する
__処理__：__`board`__ 属性の要素を連結した文字列を作成する
__入力__：なし
__出力__：__`board`__ 属性の要素を連結した文字列

下記は、`board_to_str` メソッドの定義です。先ほど説明した処理を行っているだけなので、特に難しい点はないと思いますので説明は省略します。

```python
def board_to_str(self):
    txt = ""
    for col in self.board:
        txt += "".join(col)
    return txt

Marubatsu.board_to_str = board_to_str
```

下記のプログラムで、いくつかの局面で `board_to_str` 属性を呼び出したものです。実行結果から正しく動作しすることが確認できます。

```python
print(mb.board_to_str())
mb.move(0, 0)
print(mb.board_to_str())
mb.move(1, 0)
print(mb.board_to_str())
mb.move(0, 2)
print(mb.board_to_str())
mb.move(2, 2)
print(mb.board_to_str())
```

実行結果
```
.........
o........
o..x.....
o.ox.....
o.ox....x
```

## `board` 属性を利用した局面と最善手の対応表の作成

`board` 属性を利用した局面と最善手の対応表は下記のアルゴリズムで作成できます。

* 対応表を表すデータを空の dict で初期化する
* ゲーム木の全てのノードの局面に対して下記の処理を行う
* その局面を文字列に変換したデータが、__dict のキーに存在していなければ__、その局面の __最善手を対応表に登録する__。dict のキーに存在している場合は登録済なので何もしない

下記は対応表を作成するプログラムです。なお、対応表を代入する変数の名前は `bestmoves_by_board` としました。

* __3 行目__：ゲーム木のデータをファイルから読み込む
* __4 行目__：`best_moves_by_board` を空の dict で初期化する
* __5 行目__：すべてのゲーム木のノードに対する繰り返し処理を行う
* __6 行目__：局面の `board` 属性を文字列に変換して `txt` に代入する
* __7 行目__：`best_moves_by_board` のキーに `txt` が存在しないことを判定する
* __8 行目__：存在しない場合は、`txt` のキーの値にそのノードの最善手の一覧を代入する

```python
1  from tree import Mbtree
2
3  mbtree = Mbtree.load("../data/aidata")
4  bestmoves_by_board = {}
5  for node in mbtree.nodelist:
6      txt = node.mb.board_to_str()
7      if not txt in bestmoves_by_board.keys():
8          bestmoves_by_board[txt] = node.bestmoves
```

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

```python
from tree import Mbtree

mbtree = Mbtree.load("../data/aidata")
bestmoves_by_board = {}
for node in tqdm(mbtree.nodelist):
    txt = node.mb.board_to_str()
    if not txt in bestmoves_by_board.keys():
        bestmoves_by_board[txt] = node.bestmoves
```
</details>

上記のプログラムを実行後に、下記のプログラムを実行して `bestmoves_by_board` の要素の数を表示すると、実行結果から〇×ゲームの __ゲーム盤の種類は 5478 種類__ であることがわかります。これは、__ゲーム木のノードの数の約 1/100__ です。

```python
len(bestmoves_by_board)
```

実行結果

```
5478
```

`bestmoves_by_board` は今後も利用するので、下記のプログラムでファイルに保存します。

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

作成した __bestmoves_by_board.dat__ のファイルサイズは __約 20 KB__ でした。これは、bestmoves.dat の約 2800 KB と比較して __1/100 以下__ なので、実際に __大幅にデータの量が減っている__ ことが確認できました。

## `bestmoves_by_board` を利用した AI の定義

この `bestmoves_by_board` を使って下記のプログラムのように __`gt_ai6`__ という強解決の AI を定義することができます。[`ai_gt5`](https://qiita.com/ysgeso/items/d2c309058e2c60d2e476#%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E8%A8%88%E7%AE%97%E3%81%AB%E5%BF%85%E8%A6%81%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E5%88%86%E9%9B%A2)との違いは、仮引数の名前と、dict のキーに `mb.board_to_str()` を記述する点です。

また、この後で `is_strongly_solved` を利用して `ai_gt6` が強解決の AI であるかどうかを検証するので、__仮引数 `candidate` を追加__ しました。

* __3 行目__：デフォルト値を `False` とする仮引数 `candidate` を追加する
* __4、5 行目__：`candidate` が `False` の場合は最善手の一覧を返す
* __6、7 行目__：`candidate` が `False` の場合は最善手の中からランダムに選んだ着手を返す

```python
1  from random import choice
2
3  def ai_gt6(mb, bestmoves_by_board, candidate=False):
4      if candidate:
5          return bestmoves_by_board[mb.board_to_str()]
6      else:
7          return choice(bestmoves_by_board[mb.board_to_str()])
```

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

```diff_python
from random import choice

def ai_gt6(mb, bestmoves_by_board, candidate=False):
    if candidate:
        return bestmoves_by_board[mb.board_to_str()]
    else:
        return choice(bestmoves_by_board[mb.board_to_str()])
```
</details>

<details><summary><strong><code>ai_gt5</code>からの修正箇所</strong></summary>

```diff_python
from random import choice

-def ai_gt5(mb, bestmoves):
+def ai_gt6(mb, bestmoves_by_board, candidate=False):
-   return choice(bestmoves[tuple(mb.records)])
+   if candidate:
+       return bestmoves_by_board[mb.board_to_str()]
+   else:
+       return choice(bestmoves_by_board[mb.board_to_str()])
```
</details>

上記のプログラムを実行後に、下記のプログラムで `ai_match` を使って `ai2s` と対戦を行うと、実行結果のように `ai_gt5` VS `ai2s` とほぼ同じ通算成績になることが確認できます。

```python
from ai import ai2s, ai_match

ai_match(ai=[ai_gt6, ai2s], params=[{"bestmoves_by_board": bestmoves_by_board}, {}])
```

実行結果（実行結果はランダムなので下記と異なる場合があります）

```
ai_gt6 VS ai2s
100%|██████████| 10000/10000 [00:30<00:00, 322.85it/s]
count     win    lose    draw
o        9683       0     317
x        7780       0    2220
total   17463       0    2537

ratio     win    lose    draw
o       96.8%    0.0%    3.2%
x       77.8%    0.0%   22.2%
total   87.3%    0.0%   12.7%
```

次に、`is_strongly_solved` を利用して `ai_gt6` が強解決の AI であることを確認したいのですが、__`is_strongly_solved`__ は、`ai_gt6s` のような __`mb` 以外の仮引数を必要とする AI の関数には対応していない__ ので修正する必要があります。

# `Check_solved` クラスの修正と改良

上記で説明した修正以外にも、`Check_solved` クラスには改良の余地があるのでそれらを順番に修正することにします。

## `is_strongly_solved` メソッドの修正

まず、`is_strongly_solved` メソッドが `ai_gt6` を検証できるようにするために、下記のプログラムのように仮引数 `params` を追加します。

* __2 行目__：デフォルト値を `None` とする仮引数 `params` を追加する
* __3、4 行目__：`params` が `None` の場合に `params` に空の dict を代入する
* __8 行目__：`ai` の実引数に `**params` を追加する

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

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

```python
@staticmethod
def is_strongly_solved(ai, params=None):
    if params is None:
        params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist):
        candidate = set(ai(mb, candidate=True, **params))
        bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist)
    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
@staticmethod
-def is_strongly_solved(ai):
+def is_strongly_solved(ai, params=None):
+   if params is None:
+       params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(Check_solved.mblist):
-       candidate = set(ai(mb, candidate=True))
+       candidate = set(ai(mb, candidate=True, **params))
        bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
        if candidate <= bestmoves:
            count += 1
        else:
            incorrectlist.append((mb, candidate, bestmoves))
    nodenum = len(Check_solved.mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist
    
Check_solved.is_strongly_solved = is_strongly_solved
```
</details>

上記の修正後に下記のプログラムで、`ai_gt6` が強解決の AI であることを検証すると、実行結果のように強解決の AI であることが確認できます。なお、1 行でプログラムを記述すると長くなるので 2 行に分けてプログラムを記述しました。また、`incorrectlist` の値は強解決の AI であることを検証するだけであれば必要がないので表示していません。

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

実行結果

```
100%|██████████| 294778/294778 [00:01<00:00, 270543.00it/s]
294778/294778 100.00%
True
```

## `bestmoves_by_board` を利用した判定

`is_strongly_solved` では、強解決の AI であることを判定する際に、決着がついた局面を除いた 294778 個[^1]のゲーム木のノードに対して処理を行っていましたが、この中には __大量の同じ `board` 属性を持つ局面が存在する__ のでかなり __無駄な処理__ を行っています。

### `mblist_by_board` の計算と保存

そこで、__`board` 属性が異なる局面__ を集めた __`mblist_by_board`__ を作成し、それと先程作成した `bestmoves_by_board` を使って判定を行うように修正することにします。

`mblist_by_board` は、`bestmoves_by_board` を計算する際に、下記のプログラムで計算できます。なお、下記のプログラムでは、`bestmoves_by_board` を改めて計算し直していますが、これは __`mblist_by_board` を計算する際に必要となる__ からです。

* __2 行目__：`mblist_by_board` を空の list で初期化する
* __7、8 行目__：`txt` が `bestmoves_by_board` のキーに存在せず、ゲーム中の局面の場合に、`mblist_by_board` の要素に `mb` を追加する

```python
1  bestmoves_by_board = {}
2  mblist_by_board = []
3  for node in mbtree.nodelist:
4      txt = node.mb.board_to_str()
5      if not txt in bestmoves_by_board.keys():
6          bestmoves_by_board[txt] = node.bestmoves
7          if node.mb.status == Marubatsu.PLAYING:
8              mblist_by_board.append(mb)
```

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

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

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

```diff_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)
```
</details>

上記のプログラムを実行後に、下記のプログラムを実行して `mblist_by_board` の要素の数を表示すると、実行結果から〇×ゲームのゲーム盤のうち、__決着がついていない局面の種類は 4520 種類である__ ことがわかります。

```python
len(mblist_by_board)
```

実行結果

```
4520
```

`mblist_by_board` は今後も利用するので、下記のプログラムでファイルに保存します。

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

__mblist_by_board.dat のファイルサイズは 38 KB__ で、mblist.dat の 約 2300 KB と比較して __大幅に小さくなる__ ことが確認できます。

## `Check_solved` クラスの修正

次に、下記のプログラムのように `Check_solved` が今回の記事で保存したデータを利用するように修正します。

* __2 行目__：クラス属性の名前を `bestmoves_by_board` にし、bestmoves_by_board.dat からデータを読み込むように修正する
* __3 行目__：クラス属性の名前を `mblist_by_board` にし、mblist_by_board.dat からデータを読み込むように修正する
* __11、18 行目__：`mblist` を `mblist_by_board` に修正する
* __13 行目__：`bestmoves` を `bestmoves_by_board` に修正し、キーに `board_to_str` メソッドで計算した文字列を記述するように修正する


```python
 1  class Check_solved:
 2      bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
 3      mblist_by_board = load_mblist("../data/mblist_by_board.dat")
 4   
 5      @staticmethod
 6      def is_strongly_solved(ai, params=None):
 7          if params is None:
 8              params = {}
 9          count = 0
10          incorrectlist = []
11          for mb in tqdm(Check_solved.mblist_by_board):
12              candidate = set(ai(mb, candidate=True, **params))
13              bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
14              if candidate <= bestmoves:
15                  count += 1
16              else:
17                  incorrectlist.append((mb, candidate, bestmoves))
18          nodenum = len(Check_solved.mblist_by_board)
19          print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
20          return count == nodenum, incorrectlist
```

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

```python
class Check_solved:
    bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
    mblist_by_board = load_mblist("../data/mblist_by_board.dat")
    
    @staticmethod
    def is_strongly_solved(ai, params=None):
        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
```
</details>

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

```diff_python
class Check_solved:
-   bestmoves = load_bestmoves()
+   bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
-   mblist = load_mblist()
+   mblist_by_board = load_mblist("../data/mblist_by_board.dat")
    
    @staticmethod
    def is_strongly_solved(ai, params=None):
        if params is None:
            params = {}
        count = 0
        incorrectlist = []
-       for mb in tqdm(Check_solved.mblist):
+       for mb in tqdm(Check_solved.mblist_by_board):
            candidate = set(ai(mb, candidate=True, **params))
-           bestmoves = set(Check_solved.bestmoves[tuple(mb.records)])
+           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)
+       nodenum = len(Check_solved.mblist_by_board)
        print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
        return count == nodenum, incorrectlist
```
</details>

上記の修正後に、下記のプログラムで `ai14s` が強解決の AI であるかを判定します。実行結果から、__`ai14s` は強解決の AI ではなく__、4520 - 4468 = __52 種類の局面で最善手を選択しない__ ことが確認できました。また、__修正前は同じ処理に 50 秒かかった__ のに対し、調べる局面の数が大幅に減ったことで __1 秒で処理が終了__ していることも確認できます。

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

実行結果

```
100%|██████████| 4520/4520 [00:01<00:00, 2639.10it/s]
4468/4520 98.85%
False
```

次に、下記のプログラムで `ai_gt6` が強解決の AI であるかを判定します。実行結果から、`ai_gt6` は強解決の AI である事が確認できました。なお、こちらは修正前でも 1 秒で処理が完了していたので、処理速度の差はほとんど感じられないかもしれませんが、下記では 0 秒と表示され、これはおそらく四捨五入した秒数なのでこちらも __処理速度が速くなっていることが確認できます__。

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


実行結果

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

## `Check_solved` の問題点と修正

`Check_solved` には以下のような問題点があります。

* `Check_solved` の定義を実行した際に __ファイルからデータを読み込む__
* `Check_solved` は util.py に記述されているので、util.py に記述されている __他の `gui_play` などの関数をインポートした際__ にも、`Check_solved` は実行されてしまい、__ファイルが読み込まれてしまう__
* そのため、例えば `gui_play` をインポートした後で、__`Check_solved` を利用しないような場合でも__、__利用しないファイルの読み込みが行われる__ せいで __無駄な待ち時間が生じる__

このような問題を解決するアルゴリズムを下記に示します。

* ファイルから読み込んだデータを代入するクラス属性は __`None` で初期化__ する
* __ファイルのデータが実際に必要になる__ `is_strongly_solved` を実行した際に、対応するクラス属性の値が __`None` の場合にファイルからデータを読み込み、クラス属性に代入__ する
* クラス属性の値が `None` でない場合は、そのクラス属性に必要なデータが代入されているのでそれを利用する

上記のアルゴリズムで、クラスの定義を実行した際にファイルを読み込まず、__必要になった時点__ でファイルを __一度だけ読み込む__ ようにすることができます。

下記は、そのように `Check_solved` を修正したプログラムです。

* __2、3 行目__：クラス属性を `None` で初期化する
* __7 ~ 10 行目__：クラス属性の値が `None` の場合にファイルからデータを読み込んでそのクラス属性に代入する

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

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

```python
class Check_solved:
    bestmoves_by_board = None
    mblist_by_board = None
    
    @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")            
        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
```
</details>

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

```diff_python
class Check_solved:
-   bestmoves_by_board = load_bestmoves("../data/bestmoves_by_board.dat")
+   bestmoves_by_board = None
-   mblist_by_board = load_mblist("../data/mblist_by_board.dat")
+   mblist_by_board = None
    
    @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")            
        if params is None:
            params = {}
元と同じなので省略
```
</details>

上記の修正後に、下記のプログラムで `ai14s` と `ai_gt6` が強解決の AI であるかを判定することで、実行結果から修正したプログラムが正しく動作することを確認できます。

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

実行結果

```
100%|██████████| 4520/4520 [00:01<00:00, 2644.79it/s]
4468/4520 98.85%
False
100%|██████████| 4520/4520 [00:00<00:00, 110638.59it/s]
4520/4520 100.00%
True
```

# 今回の記事のまとめ

今回の記事では、前回の記事のバグの原因と、__数値と set__ で __`<=`__ と __`>`__ 演算子が __行う処理が異なる__ ことを説明しました。

また、__`board` 属性を利用して最善手の対応表を作成する__ ことで、データを保存する __ファイルのサイズが大幅に小さくなり__、強解決の AI であるかを判定する __処理時間を大幅に減らす__ ことができることを説明しました。

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

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/110/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [marubatsu_new.py](https://github.com/ysgeso/marubatsu/blob/master/110/marubatsu_new.py)  | 今回の記事で更新した marubatsu.py |
| [ai_new.py](https://github.com/ysgeso/marubatsu/blob/master/110/ai_new.py)  | 今回の記事で更新した ai.py |
| [util_new.py](https://github.com/ysgeso/marubatsu/blob/master/110/util_new.py)  | 今回の記事で更新した util.py |
| [bestmoves_by_board.dat](https://github.com/ysgeso/marubatsu/blob/master/data/bestmoves_by_board.dat)  | `board` 属性を利用した局面と最善手の一覧の対応表保存するファイル |
| [mblist_by_board.dat](https://github.com/ysgeso/marubatsu/blob/master/data/mblist_by_board.dat)  | `board` 属性を利用した決着がついていない局面の一覧を保存するファイル |

# 次回の記事

https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e

[^1]:この数字は、実行結果の `is_strongly_solved` の実行結果の「294778/294778」確認できます