Pythonで〇×ゲームのAIを一から作成する　その112　弱解決の AI であるかの判定と枝狩りによる探索の効率化

# 目次と前回の記事

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

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

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

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

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

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

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

# 弱解決の AI であるかどうかの判定

[以前の記事](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)では、〇× ゲームの AI が __弱解決の AI であるか__ どうかを、__ランダムな着手を行う `ai2s` と十分な回数だけ対戦__ させ、__一度も敗北しないかどうかで判定__ を行いました。この判定方法は 判定したい AI に __`ai2s` が勝利する着手が存在する場合__ に、その着手を __偶然選択しない可能性が 0 にはならない__ ので、AI が 弱解決の AI であるかどうかを __100 % 判定することはできません__。そこで、今回の記事では別の方法で __弱解決の AI であるかどうかを 100 % 判定する処理を実装__ する事にします。

[以前の記事](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E8%A7%A3%E6%B1%BA%E3%81%A8%E3%81%9D%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明したように、__弱解決の定義__ は、「ゲームの開始時の局面の状態が判明しており、__どのような相手と対戦しても__、その __局面の状況以上の結果になる合法手を選択する方法が判明__ しているゲームのこと」です。〇×ゲームは __ゲーム開始時の局面の状況__ は __引き分けの局面__ なので、ゲーム開始時の局面から対戦を行った場合に、どのような相手と対戦しても __敗北しないこと__ が弱解決の AI の条件です。その条件をどのように判定すればよいかについて少し考えてみて下さい。

:::note
上記では、敗北しないことが条件であると説明しましたが、その AI がゲーム開始時の局面から対戦を行った場合に __出現する全ての局面で最善手を選択する__ という条件で判定できるのではないかと __思った人がいるかもしれません__。しかし、その方法は弱解決の AI であるかを判定する方法としては __厳密には正しくありません__。

[以前の記事](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#%E5%BC%B1%E8%A7%A3%E6%B1%BA%E3%81%A7%E3%82%88%E3%81%8F%E3%81%82%E3%82%8B%E8%AA%A4%E8%A7%A3)で説明しましたが、〇×ゲームのような引き分けのゲームの場合は、__必ず引き分け以上の結果になる__ ことが弱解決の条件です。従って、相手が最善手を選択しなかった結果、__必勝の局面になった場合に最善手を選択せず__ に引き分けになったとしても、__弱解決の AI の条件を満たします__。

出現する全ての局面で最善手を選択するという条件は、弱解決の条件よりも __厳しい条件__ です。従って、その条件を満たす場合は、必ず弱解決の AI であることが保証されますが、その逆は必ずしも正しくはありません。

本記事では実装しませんが、出現する全ての局面で最善手を選択するという条件を判定する処理を記述することもできます。興味がある方は実装してみて下さい。
:::

## 判定のアルゴリズムとゲーム木の探索

どのような相手と対戦しても敗北しないということは、AI がゲーム開始時の局面から着手を行った際に出現する局面の中に、__AI が敗北する局面が一つも存在しない__ ということです。

AI がゲーム開始時の局面から着手を行った際に出現する局面は、ゲーム木のルートノードから、__下記の条件を満たす子ノードを辿って出現するノード__ の局面です。

* AI の手番の場合は、その AI が行う可能性のあるすべての合法手に対応する子ノード
* AI の手番でない場合は、全ての合法手に対応する子ノード

従って、ゲーム木の中で、__上記の条件を満たす部分木__ のノードをすべて調べ、その中に __AI が敗北する局面が存在しない場合__ に弱解決の AI であると判定することができます。

以下は、弱解決であるかどうかを判定する下記のアルゴリズムです。

1. 〇 の担当と × の担当の両方で下記の手順で判定を行い、__両方で弱解決であると判定__ された場合に、弱解決の AI であると判定する
2. ゲーム開始時の局面から以下の着手を行うすべての局面を調べ。AI が敗北する局面が 1 つも存在しなければ、担当した手番では弱解決の AI であると判定する
    * AI が担当する手番では、その AI が行う可能性のあるすべての合法手を着手する
    * AI が担当しない手番では、すべての合法手を着手する

:::note
プログラミングに慣れた方で、もっと効率的なアルゴリズムを思いついた人がいるかもしれませんが、最初は上記の愚直なアルゴリズムから紹介し、もっと効率的なアルゴリズムについては今回の記事の後半で紹介します。
:::

:::note warn
このような、ゲーム木の中のノードの中からから __特定の条件を満たすノードを探す__ ことを __ゲーム木の探索__ と呼びます。

また、ゲーム木に限らず、数多くのデータの中から __特定の条件を満たすデータを探す処理__ のことを __探索__ と呼び、探索を幅優先アルゴリズムで行うことを __幅優先探索__、深さ優先アルゴリズムで行うことを __深さ優先探索__ と呼びます。
:::

上記の手順 2 は、ゲーム木のルートノードから、条件を満たす __全ての子ノードを辿っていく処理__ になるので、__再帰呼び出しによる深さ優先アルゴリズム__ で記述することができます。また、手順 1 から __〇 と × の担当で異なる処理を行う必要がある__ ことがわかります。

強解決の AI であるかの判定を Check_solved のメソッドとして定義したので、弱解決の AI であるかの判定も同様に Check_solved のメソッドとして下記のように定義する事にします[^1]。深さ優先アルゴリズムで処理を行うので、このメソッドは __深さ優先探索__ を行う処理です。

__名前__：弱解決（weakly solved）であるかを判定するので `is_weakly_solved` とする
__処理__：指定した手番を担当した場合に AI が弱解決であるかを再帰呼び出しを使って判定する
__入力__：下記の仮引数にデータを代入する
* `node`：判定を行うゲーム木のノード
* `ai`：判定を行う AI の関数
* `turn`：判定を行う AI が担当する手番
* `params`：AI が必要とするパラメーター

__出力__：弱解決と判定された場合は `True`、そうでない場合は `False` を返す

## `calc_legal_moves` の修正

上記のアルゴリズムの手順 2 では、AI が担当しない手番では __すべての合法手を着手する__ ので、合法手の一覧を計算する Marubatsu クラスの __`calc_legal_moves` メソッドを利用します__ が、このメソッドには以下のような __問題点がある__ ことに気が付きましたので修正します。

ゲーム木を作成する [`create_tree_by_df`](https://qiita.com/ysgeso/items/db7cfe4a1f14d9cb9368#create_tree_by_df-%E3%81%AE%E5%AE%9A%E7%BE%A9) では、ノード `N` に対して、全ての子ノードを計算する処理を行います。その際に、下記のプログラムの 2 行目のように、__ゲーム中であるという条件が満たされる場合__ に __`calc_legal_moves`__ を利用して __合法手の一覧を計算__ しました。

```python
1  def create_tree_by_df(self, N):
2      if N.mb.status == Marubatsu.PLAYING:
3          legal_moves = N.mb.calc_legal_moves()
4          for x, y in legal_moves:
以下略
```

このような処理が必要となるのは、Marubatsu クラスの __`calc_legal_moves`__ が、下記のプログラムのように __空いているマスの一覧を計算する__ という処理 __だけ__ を行っているため、ゲームの __決着がついた局面でも複数の合法手を返す__ 可能性があるからです。

```python
def calc_legal_moves(self):
    legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
                        for x in range(self.BOARD_SIZE)
                        if self.board[x][y] == Marubatsu.EMPTY]
    return legal_moves
```

しかし、よく考えると __ゲームの決着がついている局面__ には __合法手は存在しない__ ので __空の list を返すようにするべき__ です。また、そのように `calc_legal_moves` 修正することで、__`create_tree_by_df`__ の 4 行目の __for 文の繰り返し処理が一度も実行されなくなる__ ので、__2 行目__ のゲームの決着がついているかどうかの __判定を行う必要が無くなります__。

そこで、`calc_legal_moves` を下記のように修正します。

* __4、5 行目__：ゲームの決着がついている場合は、空の list を返すように修正する

```python
 1  from marubatsu import Marubatsu
 2
 3  def calc_legal_moves(self):
 4      if self.status != Marubatsu.PLAYING:
 5          return []
 6      legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
 7                          for x in range(self.BOARD_SIZE)
 8                          if self.board[x][y] == Marubatsu.EMPTY]
 9      return legal_moves
10
11  Marubatsu.calc_legal_moves = calc_legal_moves
```

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

```python
from marubatsu import Marubatsu

def calc_legal_moves(self):
    if self.status != Marubatsu.PLAYING:
        return []
    legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
                        for x in range(self.BOARD_SIZE)
                        if self.board[x][y] == Marubatsu.EMPTY]
    return legal_moves

Marubatsu.calc_legal_moves = calc_legal_moves
```
</details>

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

```diff_python
from marubatsu import Marubatsu

def calc_legal_moves(self):
+   if self.status != Marubatsu.PLAYING:
+       return []
    legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
                        for x in range(self.BOARD_SIZE)
                        if self.board[x][y] == Marubatsu.EMPTY]
    return legal_moves

Marubatsu.calc_legal_moves = calc_legal_moves
```
</details>

次に、`create_tree_by_df` を下記のプログラムのように修正します。

* 4 行目の下にあった if 文を削除し、削除した if 文のインデントを全て無くす

```python
1  from tree import Mbtree, Node
2  from copy import deepcopy
3
4  def create_tree_by_df(self, N):
5      legal_moves = N.mb.calc_legal_moves()
インデント以外は元と同じなので略
6
7  Mbtree.create_tree_by_df = create_tree_by_df
```

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

```python
from tree import Mbtree, Node
from copy import deepcopy

def create_tree_by_df(self, N):
    legal_moves = N.mb.calc_legal_moves()
    for x, y in legal_moves:
        mb = deepcopy(N.mb)
        mb.move(x, y)
        node = Node(mb, parent=N, depth=N.depth + 1)
        N.insert(node)
        self.nodelist.append(node)
        self.nodelist_by_depth[node.depth].append(node)
        self.nodenum += 1
        self.create_tree_by_df(node)

Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

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

```diff_python
from tree import Mbtree, Node
from copy import deepcopy

def create_tree_by_df(self, N):
-   if N.mb.status == Marubatsu.PLAYING:
-        legal_moves = N.mb.calc_legal_moves()
+   legal_moves = N.mb.calc_legal_moves()
インデント以外は元と同じなので略

Mbtree.create_tree_by_df = create_tree_by_df
```
</details>

上記の修正後に下記のプログラムを実行して、`create_tree_by_df` を利用してゲーム木を作成し、`draw_subtree` で作成したゲーム木のルートノードから深さ 1 までの部分木を表示すると、実行結果のように正しく表示されることが確認できます。

```python
mbtree = Mbtree(algo="df")
mbtree.draw_subtree(mbtree.root, maxdepth=1)
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1dd48436-7c77-6816-6c36-d1938d8c62d0.png" width="100">

なお、`calc_legal_moves` を上記のように修正しても、これまで __`calc_legal_moves`__ を利用しているプログラムを __修正する必要はありません__。その理由は、これまでのプログラムでは __ゲームの決着がついた局面で `calc_legal_moves` の値を利用することがなかったからです__。

従って、`create_tree_by_df` 以外でも、`if N.mb.status == Marubatsu.PLAYING:` のような if 文の判定を削除することができる場所がいくつかありますが、そのままでも正しい処理が行われるのでそれらについては修正しないことにします。修正したい人は `calc_legal_moves` でプログラムを検索してそのような個所を探し出して修正すると良いでしょう。

## `is_weakly_solved` の定義

`is_weakly_solved` は __再帰呼び出し__ によって計算を行うので、__仮引数 `node` から辿れる部分木__ の中に、一つでも相手が勝利するノードがあれば `False` を、そうでなければ `True` を返すという処理を行います。

また、__`node` の局面__ が __決着がついているか__ どうかで、下記の処理を行います。

* 決着がついている場合は、相手が勝利していれば `False` を、いなければ `True` を返す
* 決着がついていない場合は、下記に対応するすべての子ノードに対して再帰呼び出しを行う。__再帰呼び出しの返り値が `False` になる場合__ は、__子ノードの中に相手が勝利する局面が存在する__ ことを意味するので、すべての再帰呼び出しの返り値が `True` の場合は `True` を、そうでなければ `False` を返す
    * AI が担当する手番では、その AI が行う可能性のあるすべての合法手を着手する
    * AI が担当しない手番では、すべての合法手を着手する

また、決着がついていない場合の処理は、前後の式が両方共 `True` の場合に `True` を計算する __and 演算子__ を使って、下記のアルゴリズムで計算できます。

* 結果を計算する変数を用意し、__`True` で初期化__ する
* 再帰呼び出しの返り値とその変数を __and 演算子で演算__ し、その変数に代入する

上記の計算を行うことで、一つでも再帰呼び出しの返り値が `False` になった場合は、結果を計算する変数が `False` になります。

下記は、上記のアルゴリズムに従って、`is_weakly_solved` を定義したプログラムです。

* __3 行目__：`is_strongly_solved` と同様に、静的メソッドとして定義する
* __4 行目__：先程説明した 4 つの仮引数を持つ関数として `is_weakly_solved` を定義する。その際に `params` の実引数を省略できるようにデフォルト値が `None` の仮引数とする
* __5、6 行目__：`params` が `None` の場合に空の dict を代入する
* __7、8 行目__：`node` の局面が AI の勝利か引き分けの場合は `True` を返す
* __9、10 行目__：ゲーム中でない場合は相手が勝利しているので、`False` を返す。11 行目以降の処理は、ゲーム中の場合のみ行われる
* __12、13 行目__：`node` の局面が AI が担当する手番の場合は、`ai` が選択する着手の一覧を計算して `moves` に代入する
* __14、15 行目__：`node` の局面が相手が担当する手番の場合は、合法手の一覧を計算して `moves` に代入する
* __16 行目__：決着がついていない場合の返り値（return value）を計算する変数 `retval` の値を `True` で初期化する
* __17 行目__：`moves` 内に記録されたそれぞれの着手に対する繰り返し処理を行う
* __18、9 行目__：`children_by_moves` 属性を使って `move` の着手を行った子ノードを計算し、その子ノードに対する `is_weakly_solved` の再帰呼び出しを行う。再帰呼び出しの返り値と `retval` を and 演算子で計算し、`retval` に代入する
* __19 行目__：`retval` を返り値として返す

```python
 1  from util import Check_solved
 2
 3  @staticmethod
 4  def is_weakly_solved(node, ai, turn, params=None):
 5      if params is None:
 6          params = {}
 7      if node.mb.status == turn or node.mb.status == Marubatsu.DRAW:
 8          return True
 9      elif node.mb.status != Marubatsu.PLAYING:
10          return False
11
12      if turn == node.mb.turn:
13          moves = ai(node.mb, candidate=True, **params) 
14      else:
15          moves = node.mb.calc_legal_moves()
16      retval = True
17      for move in moves:
18          childnode = node.children_by_move[move]
19          retval = Check_solved.is_weakly_solved(childnode, ai, turn, params) and retval
20      return retval
21
22  Check_solved.is_weakly_solved = is_weakly_solved  
```

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

```python
from util import Check_solved

@staticmethod
def is_weakly_solved(node, ai, turn, params=None):
    if params is None:
        params = {}
    if node.mb.status == turn or node.mb.status == Marubatsu.DRAW:
        return True
    elif node.mb.status != Marubatsu.PLAYING:
        return False
        
    if turn == node.mb.turn:
        moves = ai(node.mb, candidate=True, **params) 
    else:
        moves = node.mb.calc_legal_moves()
    retval = True
    for move in moves:
        childnode = node.children_by_move[move]
        retval = Check_solved.is_weakly_solved(childnode, ai, turn, params) and retval
    return retval

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

上記のプログラムを実行後に弱解決の AI ではない `ai2s` と、弱解決の AI である `ai14s` と、強解決の AI である `ai_gt6` を `is_weakly_solved` を利用して計算することにします。

下記のプログラムの実行結果から、`ai2s` は 〇 を担当した場合と × を担当した場合のいずれも False になり、弱解決の AI ではないことが確認できます。

```python
from ai import ai2s, ai14s, ai_gt6

print(Check_solved.is_weakly_solved(mbtree.root, ai2s, Marubatsu.CIRCLE))
print(Check_solved.is_weakly_solved(mbtree.root, ai2s, Marubatsu.CROSS))
```

実行結果

```
False
False
```

下記のプログラムの実行結果から、`ai14s` は 〇 を担当した場合と × を担当した場合のいずれも True になり、弱解決の AI であることが確認できます。

```python
print(Check_solved.is_weakly_solved(mbtree.root, ai14s, Marubatsu.CIRCLE))
print(Check_solved.is_weakly_solved(mbtree.root, ai14s, Marubatsu.CROSS))
```

実行結果

```
True
True
```

下記のプログラムの実行結果から、`ai_gt6` は 〇 を担当した場合と × を担当した場合のいずれも True になり、弱解決の AI であることが確認できます。強解決の AI のほうが 弱解決の AI よりも条件が厳しいので、これは当然の結果です。

```python
from util import load_bestmoves

bestmoves = load_bestmoves("../data/bestmoves_by_board.dat")
params = {"bestmoves_by_board": bestmoves}
print(Check_solved.is_weakly_solved(mbtree.root, ai_gt6, Marubatsu.CIRCLE, params))
print(Check_solved.is_weakly_solved(mbtree.root, ai_gt6, Marubatsu.CROSS, params))
```

実行結果

```
True
True
```

## 再帰呼び出しを開始する処理を行う関数の定義

上記のプログラムでは、弱解決であるかどうかを判定する際に、〇 の手番と × の手番で __2 回 `is_weakly_solved` を呼び出す必要がある__ 点が面倒です。また、`is_weakly_solved` を呼び出す際に __`mbtree.root`__ と __手番を表すデータ__ を __毎回記述する必要がある__ 点も面倒です。

再帰呼び出しによる処理を行う際は、__再帰呼び出しを開始する処理を行う関数を別に定義する__ ことで、プログラムの __記述を簡潔にする__ ことができるのでその方法を紹介します。

再帰呼び出しを開始する処理を行う __関数やメソッドの名前__ は、再帰呼び出しの関数とは __別の名前にする__ 必要がありますが、その 2 つには __似たような名前を付けるのが一般的__ です。良く使われるのが、再帰呼び出しの関数名の語尾に `_` や、`_r`[^2] などを付け加えるというものです[^3]。今回の場合は __再帰呼び出しを開始するメソッド__ の名前を __`is_weakly_solved`__ に、__再帰呼び出しのメソッド__ の名前を __`is_weakly_solved_r`__ とすることにします。

まず、下記のプログラムのように、再帰呼び出しのメソッドである `is_weakly_solved` の名前を `is_weakly_solved_r` という名前に変更します。

* __2 行目__：メソッドの名前を `is_weakly_solved_r` に修正する。なお、__`params` の値が `None` の場合に行う処理__ は、この関数を呼び出す __`is_weakly_solved` で行う__ ので、`is_weakly_solved_r` で __改めて行う必要はない__。そのため、`params` を通常の仮引数とし、2 行目の下にあった `params` に対する処理は削除した
* __5 行目__：再帰呼び出しで呼び出すメソッドの名前を `is_weakly_solved_r` に修正する

```python
1  @staticmethod
2  def is_weakly_solved_r(node, ai, turn, params):
元と同じなので省略
3      for move in moves:
4          childnode = node.children_by_move[move]
5          retval = Check_solved.is_weakly_solved_r(childnode, ai, turn, params) and retval
6      return retval
7
8  Check_solved.is_weakly_solved_r = is_weakly_solved_r  
```

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

```python
@staticmethod
def is_weakly_solved_r(node, ai, turn, params):
    if node.mb.status == turn or node.mb.status == Marubatsu.DRAW:
        return True
    elif node.mb.status != Marubatsu.PLAYING:
        return False
        
    if turn == node.mb.turn:
        moves = ai(node.mb, candidate=True, **params) 
    else:
        moves = node.mb.calc_legal_moves()
    retval = True
    for move in moves:
        childnode = node.children_by_move[move]
        retval = Check_solved.is_weakly_solved_r(childnode, ai, turn, params) and retval
    return retval

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

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

```diff_python
@staticmethod
-def is_weakly_solved(node, ai, turn, params=None):
+def is_weakly_solved_r(node, ai, turn, params):
-   if params is None:
-       params = {}
元と同じなので省略
    for move in moves:
        childnode = node.children_by_move[move]
-       retval = Check_solved.is_weakly_solved(childnode, ai, turn, params) and retval
+       retval = Check_solved.is_weakly_solved_r(childnode, ai, turn, params) and retval
    return retval

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

次に、`is_weakly_solved` を下記のように再定義します。元の `is_weakly_solved` には、ノードと手番を代入する仮引数が必要でしたが、__AI が弱解決であるかどうか__ を調べるために __必要なデータ__ は __AI の関数とそのパラメータだけ__ のはずです。それは、強解決の AI であるかを判定する `is_strongly_solved` の仮引数が `ai` と `params` だけであることからもわかります。

実際に `is_weakly_solved` に必要な仮引数も `ai` と `params` だけで、元々あった `node` と `turn` は下記のように `is_weakly_solved` のプログラムの中に記述することができます。

なお、せっかくなので、[仮引数 `verbose`](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#play-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E4%BF%AE%E6%AD%A3-2%E9%80%94%E4%B8%AD%E7%B5%8C%E9%81%8E%E3%81%AE%E9%9D%9E%E8%A1%A8%E7%A4%BA) を追加し、`verbose` が `True` の場合は 〇 の手番、× の手番、全体のそれぞれで弱解決の AI であるかを表示するようにしてみました。ただし、返り値は全体の結果のみを返すことにします。

* __2 行目__：仮引数を、AI と AI のパラメータと、デフォルト値を `True` とする `verbose` を仮引数とするように修正する
* __5 行目__：ゲーム木のデータをファイルから読みこむ
* __6 行目__：ルートノードを `root` に代入する
* __7、8 行目__：〇 の手番と × の手番のそれぞれで `is_weakly_solved_r` を呼び出して弱解決の AI であるかどうかを計算し、結果を変数に代入する
* __9 行目__：AI が弱解決の AI あるかを計算する
* __10 ~ 13__：`verbose` が `True` の場合に結果を `print` で表示する
* __14 行目__：結果を返り値として返す

```python
 1  @staticmethod
 2  def is_weakly_solved(ai, params=None, verbose=True):
 3      if params is None:
 4          params = {}
 5      mbtree = Mbtree.load("../data/aidata")
 6      root = mbtree.root
 7      circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
 8      cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
 9      result = circle_result and cross_result
10      if verbose:
11          print("   o", circle_result)
12          print("   x", cross_result)
13          print("Both", result)
14          return result
15
16  Check_solved.is_weakly_solved = is_weakly_solved
```

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

```python
@staticmethod
def is_weakly_solved(ai, params=None, verbose=True):
    if params is None:
        params = {}
    mbtree = Mbtree.load("../data/aidata")
    root = mbtree.root
    circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
    cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
    result = circle_result and cross_result
    if verbose:
        print("   o", circle_result)
        print("   x", cross_result)
        print("Both", result)
    return result

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

上記を実行後に下記のプログラムで `ai2s` を判定すると、実行結果に先程と同様に 〇、×、両方のいずれも `False` が表示されることが確認できました。先ほどのプログラムと比較して、__1 行で実引数を 1 つだけ記述すれば良い__ のでかなり __簡潔に記述__ できます。

```python
print(Check_solved.is_weakly_solved(ai2s))
```

実行結果

```
   o False
   x False
Both False
False
```

## `is_weakly_solved` の改良

上記のプログラムを実行すると、筆者のパソコンでは 約 45 秒ほど時間がかかりましたが、そのうちの何秒かは `is_weakly_solved` を実行するたびに行われる、__25 MB もの大きさ__ がある __`aidata.mbtree` からデータを読み込む処理に費やされた時間__ です。そこで、__`is_strongly_solved`__ で行っているように、`aidata.mbtree` から __読み込んだデータ__ を __`mbtree` というクラス属性に代入する__ ことでファイルからのデータの読み込みを __最初の 1 回だけで済ませる__ という工夫を行うことにします。

`aidata.mbtree` のデータを代入するクラス属性の名前を __`mbtree`__ とし、下記のプログラムのように `is_wealky_solved` を修正します。

* __4、5 行目__：Check_solved クラスのクラス属性 `mbtree` 属性が `None` の場合にファイルからデータを読み込んで、`mbtree` 属性に代入する
* __6 行目__：`root` の計算を `Check_solved.mbtree.root` に修正する

```python
 1  def is_weakly_solved(ai, params=None, verbose=True):
 2      if params is None:
 3          params = {}
 4      if Check_solved.mbtree is None:
 5          Check_solved.mbtree = Mbtree.load("../data/aidata")
 6      root = Check_solved.mbtree.root
 7      circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
 8      cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
元と同じなので省略
 9
10  Check_solved.is_weakly_solved = is_weakly_solved
```

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

```python
@staticmethod
def is_weakly_solved(ai, params=None, verbose=True):
    if params is None:
        params = {}
    if Check_solved.mbtree is None:
        Check_solved.mbtree = Mbtree.load("../data/aidata")
    root = Check_solved.mbtree.root
    circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
    cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
    result = circle_result and cross_result
    if verbose:
        print("   o", circle_result)
        print("   x", cross_result)
        print("Both", result)
    return result

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

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

```diff_python
def is_weakly_solved(ai, params=None, verbose=True):
    if params is None:
        params = {}
-   mbtree = Mbtree.load("../data/aidata")
+   if Check_solved.mbtree is None:
+       Check_solved.mbtree = Mbtree.load("../data/aidata")
-   root = mbtree.root
+   root = Check_solved.mbtree.root
    circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
    cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
元と同じなので省略

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

次に、__`mbtree` というクラス属性を `None` で初期化__ する必要があります。本当は下記のプログラムの 4 行目のように、__Check_solved クラスの定義の中で初期化処理を記述する必要がある__ のですが、marubatsu.ipynb の中でクラスを定義し直すと、先程修正したメソッドの記述を全て行う必要がある点がかなり面倒です。

```python
1  class Check_solved:
2      bestmoves_by_board = None
3      mblist_by_board = None
4      mbtree = None
元と同じなので省略
```

そこで、本記事では、下記のプログラムで直接 Check_solved のクラス属性に `None` を代入して初期化することにします。なお、この __初期化処理は必ず必要になる__ ので、次回以降の記事で Check_solved を util.py からインポートして利用する際には、上記の修正を __util.py__ に記述した __Check_solved の定義に必ず記述しておく必要がある__ 点に注意して下さい。

```python
Check_solved.mbtree = None
```

実行結果は同じなので省略しますが、上記の実行後に、下記のプログラムで `ai2s` に対して `is_weakly_solved` を実行すると、`mbtree` 属性にまだファイルから読み込んだデータが代入されていないので処理に 45 秒ほど時間がかかります。

```python
print(Check_solved.is_weakly_solved(ai2s))
```

その後、もう一度同じプログラムを実行すると、今度は `mbtree` 属性にデータが代入されているので約 2/3 の 30 秒ほどで処理が完了します。

```python
print(Check_solved.is_weakly_solved(ai2s))
```

続けて、下記のプログラムで `ai14s` と `ai_gt6` のチェックを行うとこちらは処理がすぐに完了します。`ai2s` と比較して処理時間が短い理由についてはこの後で説明します。また、実行結果から正しく処理が行われることが確認できます。

```python
print(Check_solved.is_weakly_solved(ai14s))
print(Check_solved.is_weakly_solved(ai_gt6, params))
```

実行結果

```
   o True
   x True
Both True
True
   o True
   x True
Both True
True
```

# 枝狩りによる処理の効率化

上記で弱解決の AI であるかを判定する処理は実装できていますが、`ai2s` に対して `is_weakly_solved`　の処理を行うと約 30 秒もの時間がかかってしまいます。その理由は `is_weakly_solved_r` が __効率の悪い処理を行っているから__ なので、処理を効率化します。

まず、改良後と比較を行うことができるようにするために、下記のプログラムで `ai2s`、`ai14s`、`ai_gt6` のそれぞれに対する処理時間を `%%timeit` で計測します。その際に、`verbose=False` を記述しないとメッセージが大量に表示されてしまう点に注意して下さい。

なお、下記の処理は、約 30 秒かかる処理が 7 回行われるので 3 分以上かかります。

```python
%%timeit
Check_solved.is_weakly_solved(ai2s, verbose=False)
```

実行結果

```
28.7 s ± 85.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

```python
%%timeit
Check_solved.is_weakly_solved(ai14s, verbose=False)
```

実行結果

```
306 ms ± 2.95 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

```python
%%timeit
Check_solved.is_weakly_solved(ai_gt6, params, verbose=False)
```

実行結果

```
179 ms ± 1.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

下記はそれぞれの処理時間を表にまとめたものです。その際に、わかりやすいように単位をミリ秒に統一しました。

| AI | 処理時間 |
|:-:|--:|
| `ai2s`  | 28700 ms  |
| `ai14s`  | 306 ms  |
| `ai_gt6`  | 179 ms  |

## 相手が勝利した局面を発見した場合の枝狩り

`is_weakly_solved_r` では、AI がゲーム開始時から着手を行った場合に出現する全てのノードをチェックする処理を行いますが、チェックの際に __相手が勝利する局面が見つかった時点__ で __弱解決の AI であることが確定する__ ので、__残りのノードをチェックするのは無駄__ です。

:::note warn
木構造のデータの探索の際に __途中で結果が判明した場合など__ で、__必要のない探索を行わないようにする__ ことを __枝狩り__ と呼び、枝狩りを行うことで __探索するノードの数を減らし__、__処理時間を短くする__ ことができるようになります。
:::

例えば `is_weakly_solved` は深さ優先アルゴリズムで探索の処理を行う過程で、左のノードから赤い矢印の順番で再帰呼び出しの処理を行うと、__太い赤枠の × が勝利している局面のノードをチェックした時点__ で、その AI が __弱解決の AI ではないことが確定__ します。そのため、図の __暗い色で表示された残りのノードを探索する必要はなくなります__。暗い色のノードの探索を行わないという処理が、ゲーム木から暗い色の __ノードの枝を刈り取る様子に似ている__ ことから、この処理に __枝狩り__（pruning）という名前が付けられたようです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a90b7529-72df-dc35-f382-30d649736e73.png" width="200">


### 再帰呼び出しが行われた回数を数えるための修正

まず、__枝狩りの効果を実感できるようにする__ ために、__再帰呼び出しが何回行われたかを数える__ ように、`is_weakly_solved_r` と `is_weakly_solved` を修正することにします。

具体的には下記の方法で再帰呼び出しの回数を数えます。

* `Check_solved` の `count` というクラス属性で再帰呼び出しの回数を数える
* `count` 属性は `is_weakly_solved` で処理を開始する際に `0` で初期化する。なお、初期化処理は `is_weakly_solved` 内で行うので、先程の `mbtree` 属性のように、Check_solved の定義の最初で初期化処理を行う必要はない
* `is_weakly_solved_r` の最初で `count` 属性を 1 増やすことで再帰呼び出しの回数を数える

まず、`is_weakly_solved` を下記のプログラムのように修正します。

* __3 行目__：最初に `count` 属性を 0 で初期化する

```python
1  @staticmethod
2  def is_weakly_solved(ai, params=None, verbose=True):
3      Check_solved.count = 0
元と同じなので省略
4
5  Check_solved.is_weakly_solved = is_weakly_solved
```

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

```python
@staticmethod
def is_weakly_solved(ai, params=None, verbose=True):
    Check_solved.count = 0
    if params is None:
        params = {}
    if Check_solved.mbtree is None:
        Check_solved.mbtree = Mbtree.load("../data/aidata")
    root = Check_solved.mbtree.root
    circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
    cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
    result = circle_result and cross_result
    if verbose:
        print("   o", circle_result)
        print("   x", cross_result)
        print("Both", result)
    return result

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

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

```diff_python
@staticmethod
def is_weakly_solved(ai, params=None, verbose=True):
+   Check_solved.count = 0
元と同じなので省略

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

次に、`is_weakly_solved_r` を下記のプログラムのように修正します。

* __3 行目__：最初に `count` 属性を 1 増やす
 
```python
1  @staticmethod
2  def is_weakly_solved_r(node, ai, turn, params):
3      Check_solved.count += 1
元と同じなので省略
4
5  Check_solved.is_weakly_solved_r = is_weakly_solved_r  
```

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

```python
@staticmethod
def is_weakly_solved_r(node, ai, turn, params):
    Check_solved.count += 1
    if node.mb.status == turn or node.mb.status == Marubatsu.DRAW:
        return True
    elif node.mb.status != Marubatsu.PLAYING:
        return False
        
    if turn == node.mb.turn:
        moves = ai(node.mb, candidate=True, **params) 
    else:
        moves = node.mb.calc_legal_moves()
    retval = True
    for move in moves:
        childnode = node.children_by_move[move]
        retval = Check_solved.is_weakly_solved_r(childnode, ai, turn, params) and retval
    return retval

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

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

```diff_python
@staticmethod
def is_weakly_solved_r(node, ai, turn, params):
+   Check_solved.count += 1
元と同じなので省略

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

上記の修正後に下記のプログラムを実行し、`ai2s`、`ai14s`、`ai_gt6` のそれぞれに対して何回再帰呼び出しが行われたかを表示します。

下記の実行結果から、`ai2s` の場合は __1099892 回も再帰呼び出しが行われる__ ことが確認できます。これは、ゲーム木のノードの数の 549946 の 2 倍で、〇 の担当と × の担当の両方でルートノードからゲーム木を探索しているからです。100 万回以上もの再帰呼び出しが行われていることが、この __処理に時間がかかる理由__ です。

```python
Check_solved.is_weakly_solved(ai2s)
print(Check_solved.count)
```

実行結果

```
   o False
   x False
Both False
1099892
```

下記の実行結果から `ai14s` の場合は 3244 回しか再帰呼び出しが行われていないことが確認できます。これは __多くの局面__ で `ai14s` が行う着手が __合法手の一覧よりも少ないため__ です。

```python
Check_solved.is_weakly_solved(ai14s)
print(Check_solved.count)
```

実行結果

```
   o True
   x True
Both True
3244
```

下記の実行結果から `ai_gt6` の場合は 92128 回の再帰呼び出しが行われる確認できます。`ai14s` よりも回数が多いのは、__`ai_gt6` が全ての最善手を選択する__ のに対し、__`ai14s`__ は最善手の中の __一部しか選択しない場合がある__ からです。例えばゲーム開始時の局面では、9 つの全ての合法手が最善手ですが、`ai14s` は真ん中のマスしか選択しません。

```python
Check_solved.is_weakly_solved(ai_gt6, params)
print(Check_solved.count)
```

実行結果

```
   o True
   x True
Both True
92128
```

下記は先ほどの表に再帰呼び出しの回数を加えたものです。__再帰呼び出しの回数__ と __処理時間__ に __関係がある__ ことがわかります。なお、`ai_gt6` のほうが `ai14s` より再帰呼び出しの回数多いのに処理時間が短いのは、__`ai14s` そのものの処理時間__ が、`ai_gt6` の処理時間よりも __かなり長いから__ です。

| AI | 処理時間 |回数|
|:-:|--:|--:|
| `ai2s`  | 28700 ms  | 1099892 |
| `ai14s`  | 306 ms  | 3244 |
| `ai_gt6`  | 179 ms  | 92128 |

### `is_weakly_solved_r` の修正

__相手が勝利した際の枝狩り__ は、下記のプログラムのように `is_weakly_solved_r` の繰り返し処理の中で、__再帰呼び出しの返り値が `False` の場合__ に、残りの繰り返し処理を実行せずに __即座に `False` を返す__ ようにすることで行うことができます。

* 2 行目の前にあった `retval = True` は必要が無くなったので削除する
* __4、5 行目__：再帰呼び出しの返り値が `False` の場合に `False` を返すように修正する
* __6 行目__：繰り返し処理が終了した時点で、全ての再帰呼び出しの返り値が `True` であることが確定するので、`True` を返すように修正する

```python
1  @staticmethod
元と同じなので省略
2      for move in moves:
3          childnode = node.children_by_move[move]
4          if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params):
5              return False
6      return True
7
8  Check_solved.is_weakly_solved_r = is_weakly_solved_r  
```

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

```python
@staticmethod
def is_weakly_solved_r(node, ai, turn, params):
    Check_solved.count += 1
    if node.mb.status == turn or node.mb.status == Marubatsu.DRAW:
        return True
    elif node.mb.status != Marubatsu.PLAYING:
        return False
        
    if turn == node.mb.turn:
        moves = ai(node.mb, candidate=True, **params) 
    else:
        moves = node.mb.calc_legal_moves()
    for move in moves:
        childnode = node.children_by_move[move]
        if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params):
            return False
    return True

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

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

```diff_python
@staticmethod
元と同じなので省略
-   retval = True
    for move in moves:
        childnode = node.children_by_move[move]
-       retval = Check_solved.is_weakly_solved_r(childnode, ai, turn, params) and retval
+       if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params):
+           return False
-   return retval
+   return True

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

上記の修正後に下記のプログラムで `ai2s`、`ai14s`、`ai_gt6` のそれぞれに対して何回再帰呼び出しが行われたかを表示すると、実行結果のように __`ai2s` の回数__ が __58 のように劇的に削減された__ ことが確認できます。これは、`ai2s` は全ての合法手を選択するので、__すぐに敗北するノードが探索されるから__ です。一方、`ai14s` と `ai_gt6` は __敗北することがない__ ので、__再帰呼び出しの回数は変化しません__。

```python
Check_solved.is_weakly_solved(ai2s)
print(Check_solved.count)
Check_solved.is_weakly_solved(ai14s)
print(Check_solved.count)
Check_solved.is_weakly_solved(ai_gt6, params)
print(Check_solved.count)
```

実行結果

```
   o False
   x False
Both False
58
   o True
   x True
Both True
3244
   o True
   x True
Both True
92128
```

次に、下記のプログラムでそれぞれの処理時間を計測します。

```python
%%timeit
Check_solved.is_weakly_solved(ai2s, verbose=False)
```

実行結果

```
28.6 s ± 117 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

```python
%%timeit
Check_solved.is_weakly_solved(ai14s, verbose=False)
```

実行結果

```
313 ms ± 3.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

```python
%%timeit
Check_solved.is_weakly_solved(ai_gt6, params, verbose=False)
```

実行結果

```
190 ms ± 1.69 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

下記は修正前と修正後の処理時間と再帰呼び出しの回数をまとめたものです。A が修正前、B が修正後を表します。表から __`ai2s` の処理速度が劇的に減り__、それ以外は回数が変わらないのでほとんど変化しないことがわかります。

| AI | 処理時間A | 回数A | 処理時間B | 回数B |
|:-:|--:|--:|--:|--:|
| `ai2s`  | 28700 ms  | 1099892 | 3.15 ms | 58 |
| `ai14s`  | 306 ms  | 3244 | 305.00 ms | 3244 |
| `ai_gt6`  | 179 ms  | 92128 | 191.00 ms | 92128 |

:::note
2024/09/02 追記

実は、下記のプログラムの 3 行目のように、__and 演算子の前に `retval` を記述する__ ように修正しても、相手が勝利した局面を発見した場合の枝狩りを行えます。

これは、[以前の記事](https://qiita.com/ysgeso/items/1fdd19037bbf64082a42#and-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%A8-or-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E7%9F%AD%E7%B5%A1%E8%A9%95%E4%BE%A1)で説明した、and 演算子の前に記述された式が `False` になった場合は、and 演算子の後ろの式が実行されないという、__短絡評価が行われる__ ことが原因です。具体的には、下記のような処理によって枝狩りが行われます。

* `is_weakly_solved_r` の返り値が `False` になると、`retval` の値が `False` になる
* その後の繰り返し処理では、下記の計算が行われ、短絡評価により後ろの再帰呼び出しは実行されない<br>`retval = False and Check_solved.is_weakly_solved_r(略)`

```python
for move in moves:
    childnode = node.children_by_move[move]
    retval = retval and Check_solved.is_weakly_solved_r(childnode, ai, turn, params)
```

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

```diff_python
for move in moves:
    childnode = node.children_by_move[move]
-   retval = Check_solved.is_weakly_solved_r(childnode, ai, turn, params) and retval
+   retval = retval and Check_solved.is_weakly_solved_r(childnode, ai, turn, params)
```
</details>

上記のプログラムでも問題はないのですが、短絡評価より __`return False` のほうが残りの処理が行われなくなることが明確になる__ ので本記事では上記は採用しません。 
:::

## `board` 属性の値が同じ局面に対する枝狩り

〇×ゲームのゲーム木には、ゲーム盤の状況を表す __`board` 属性の値が同じ局面が多数存在する__ ので、`is_weakly_solved_r` でゲーム木を探索する際に、__既にチェック済__ の `board` 属性の値を持つノードを __再び探索する__ ことが __良くあります__。

__同じ `board` 属性__ の値を持つ局面に対して __AI が行う着手の一覧は同じになる__ ので、__`is_weakly_solved_r` の返り値の値も同じ__ になります。従って、探索の際に __既にチェック済__ の `board` 属性の値を持つノードを __再び探索した場合__ は、__そのノードの子ノードの探索を省略する__ という、枝狩りを行うことができます。

また、先程 __相手が勝利したノードを探索した時点で `False` を返す__ ように `is_weakly_solved_r` を修正したので、__新しいノードを探索__ した時点で、__それまでに探索した全てのノード__ に対する `is_weakly_solved_r` の __返り値は `True`__ になります。従って、__既にチェック済__ のノードに対する `is_weakly_solved_r` の __返り値は `True`__ になります。

ノードがチェック済であるかの判定は、[前回の記事](https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e#set-%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E9%AB%98%E9%80%9F%E5%8C%96)と同様の方法で、`registered_board` という変数に代入した __set を利用する__ ことで行うことができます。具体的には、`is_weakly_solved_r` を下記のプログラムのように修正します。

* __2 行目__：仮引数に `registered_boards` を追加する
* __3 行目__：ノードの局面の `board` 属性を文字列に変換する
* __4、5 行目__：変換した文字列が `registered_boards` に登録されている場合は、このノードはチェック済なので `True` を返す。__このノードは探索しない__ ので、この処理は 6 行目の __`count` 属性の値を 1 増やす処理の前に行う必要がある__
* __7 行目__：登録されていない場合は、局面を表す文字列を `registered_boards` に追加する
* __10 行目__：再帰呼び出しの際の実引数に `registered_boards` を追加する

```python
 1  @staticmethod
 2  def is_weakly_solved_r(node, ai, turn, params, registered_boards):
 3      txt = node.mb.board_to_str()
 4      if txt in registered_boards:
 5          return True
 6      Check_solved.count += 1
 7      registered_boards.add(txt)
元と同じなので省略 
 8      for move in moves:
 9          childnode = node.children_by_move[move]
10          if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params, registered_boards):
11              return False
12      return True
13
14  Check_solved.is_weakly_solved_r = is_weakly_solved_r  
```

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

```python
@staticmethod
def is_weakly_solved_r(node, ai, turn, params, registered_boards):
    txt = node.mb.board_to_str()
    if txt in registered_boards:
        return True
    Check_solved.count += 1
    registered_boards.add(txt)
    if node.mb.status == turn or node.mb.status == Marubatsu.DRAW:
        return True
    elif node.mb.status != Marubatsu.PLAYING:
        return False
        
    if turn == node.mb.turn:
        moves = ai(node.mb, candidate=True, **params) 
    else:
        moves = node.mb.calc_legal_moves()
    for move in moves:
        childnode = node.children_by_move[move]
        if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params, registered_boards):
            return False
    return True

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

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

```diff_python
@staticmethod
-def is_weakly_solved_r(node, ai, turn, params):
+def is_weakly_solved_r(node, ai, turn, params, registered_boards):
+   txt = node.mb.board_to_str()
+   if txt in registered_boards:
+       return True
    Check_solved.count += 1
+   registered_boards.add(txt)
元と同じなので省略
    for move in moves:
        childnode = node.children_by_move[move]
-       if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params):
+       if not Check_solved.is_weakly_solved_r(childnode, ai, turn, params, registered_boards):
            return False
    return True
    
Check_solved.is_weakly_solved_r = is_weakly_solved_r  
```
</details>

次に、`is_weakly_solved` の中で `is_weakly_solved` を呼び出す処理を下記のプログラムのように修正します。

* __3 ~ 6 行目__：`is_weakly_solved_r` の実引数の最後に空の set を追加する

```python
1  @staticmethod
2  def is_weakly_solved(ai, params=None, verbose=True):
元と同じなので省略
3      circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE,
4                                                     params, set())
5      cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS,
6                                                     params, set())
元と同じなので省略
7
8  Check_solved.is_weakly_solved = is_weakly_solved
```

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

```python
@staticmethod
def is_weakly_solved(ai, params=None, verbose=True):
    Check_solved.count = 0
    if params is None:
        params = {}
    if Check_solved.mbtree is None:
        Check_solved.mbtree = Mbtree.load("../data/aidata")
    root = Check_solved.mbtree.root
    circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params, set())
    cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params, set())
    result = circle_result and cross_result
    if verbose:
        print("   o", circle_result)
        print("   x", cross_result)
        print("Both", result)
    return result

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

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

```diff_python
@staticmethod
def is_weakly_solved(ai, params=None, verbose=True):
元と同じなので省略
-   circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params)
+   circle_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CIRCLE, params, set())
-   cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params)
+   cross_result = Check_solved.is_weakly_solved_r(root, ai, Marubatsu.CROSS, params, set())
元と同じなので省略

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

上記の修正後に下記のプログラムで `ai2s`、`ai14s`、`ai_gt6` のそれぞれに対して処理を行うと、実行結果のように __弱解決であるかを正しく判定できている__ ことが確認できます。また、__それぞれの処理の回数が減っている__ ので、__枝狩りの効果があった__ ことが確認できます。

```python
Check_solved.is_weakly_solved(ai2s, verbose=False)
print(Check_solved.count)
Check_solved.is_weakly_solved(ai14s, verbose=False)
print(Check_solved.count)
Check_solved.is_weakly_solved(ai_gt6, params, verbose=False)
print(Check_solved.count)
```

実行結果

```
   o False
   x False
Both False
45
   o True
   x True
Both True
1366
   o True
   x True
Both True
5700
```

次に、下記のプログラムでそれぞれの処理時間を計測します。

```python
%%timeit
Check_solved.is_weakly_solved(ai2s, verbose=False)
```

実行結果

```
2.83 ms ± 9.52 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
```

```python
%%timeit
Check_solved.is_weakly_solved(ai14s, verbose=False)
```

実行結果

```
178 ms ± 13.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
```

```python
%%timeit
Check_solved.is_weakly_solved(ai_gt6, params, verbose=False)
```

実行結果

```
35.3 ms ± 427 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

下記は修正前と修正後の処理時間と再帰呼び出しの回数をまとめたものです。C が `board` 属性が同じノードを枝狩りした場合を表します。表からいずれの回数も減っており、特に __`ai_gt6` の回数と処理時間が大幅に減っている__ ことが確認できます。

| AI | 処理時間A | 回数A | 処理時間B | 回数B |処理時間C | 回数C |
|:-:|--:|--:|--:|--:|--:|--:|
| `ai2s`  | 28700 ms  | 1099892 | 3.15 ms | 58 | 2.83 ms | 45 |
| `ai14s`  | 306 ms  | 3244 | 305.00 ms | 3244 | 178.00 ms | 1366 |
| `ai_gt6`  | 179 ms  | 92128 | 191.00 ms | 92128 | 35.30 ms | 5700| 

:::note warn
このように、枝狩りを行うことで、探索の回数を減らすことができ、処理時間を減らすことができます。
:::

## さらなる枝狩りのアイディア

`is_weakly_solved` の処理は、枝狩りを行うことでいずれの場合も 1 秒未満で行うことができるようになりました。__別の枝狩りを行うことでさらに処理時間を減らす__ ことができますが、__この処理時間で不満はないの__ で、本記事ではこれ以上の枝狩りは行わないことにします。

以下に、さらなる枝狩りのアイディアをいくつか紹介しますので、興味がある方は実装してみて下さい。

### 同一局面による枝狩り

[前回の記事](https://qiita.com/ysgeso/items/7cb0c709f6d5884d925e#%E5%90%8C%E4%B8%80%E5%B1%80%E9%9D%A2%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E7%9D%80%E6%89%8B%E3%81%8C%E4%B8%80%E8%87%B4%E3%81%99%E3%82%8B-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8%E6%80%A7%E8%B3%AA)で説明したように、〇×ゲームには同一局面が多数存在するので、同一局面による枝狩りを行うこともできます。ただし、同一局面による枝狩りは、__AI が選択する着手の一覧 が、同一局面に対しても同じだけ回転、反転した着手の一覧に一致する場合__ のみ行うことができる点に注意が必要です。例えば、その条件を満たさない `ai1` に対しては正しい判定を行うことはできません。

### ノードの評価値を使った枝狩り

上記のプログラムでは、決着がついた局面のノードを使って判定を行っていますが、ゲーム木の各ノードに計算された __評価値を使った枝狩り__ を行うことができます。例えば __AI が 〇 を担当する場合__ は、__評価値が -1 のノードが探索__ されると、そのノードから相手が最善手を選択し続けると敗北することになるので、__その時点で弱解決の AI ではないことが確定__ します。なお、AI が × を担当する場合は評価値が 1 のノードが探索された場合に弱解決の AI ではないことが確定します。

なお、__弱解決の AI を判定する場合は評価値が -1 のノードが探索されることはない__ ので、この枝狩りによって再帰呼び出しの回数を減らす効果は得られません。

# `is_strongly_solved` の修正

前回の記事で、`is_strongly_solved` を __同一局面を考慮__ した __mblist_by_board_min.dat を利用して判定するように修正__ しましたが、それでは __`ai1` に対する正しい判定を行うことができない__ という欠点が生じます。そこで、__同一局面を考慮しない mblist_by_board2.dat__ と考慮する mblist_by_board_min.dat のどちらを使って判定するかを __選択できるように修正__ することにします。

具体的には、下記のプログラムのように修正します。

* __5 行目__：デフォルト値を `True` とする、同一局面を考慮する（consider）かどうかを表す仮引数 `consider_samedata` を追加する
* __8 ~ 10、12 ~ 14 行目__：`consider_samedata` が `True` の場合は、mblist_by_board_min.dat を、そうでない場合は mblist_by_board2.min からファイルから読み込むように修正する
* __11、15、20、27 行目__：ファイルから読み込んだデータを `mblist` というローカル変数に代入し、それを使って処理を行うように修正する

```python
 1  from tqdm import tqdm
 2  from util import load_bestmoves, load_mblist
 3
 4  @staticmethod
 5  def is_strongly_solved(ai, params=None, consider_samedata=True):
 6      if Check_solved.bestmoves_by_board is None:
 7          Check_solved.bestmoves_by_board = load_bestmoves ("../data/bestmoves_by_board.dat")
 8      if consider_samedata:
 9          if Check_solved.mblist_by_board_min is None:
10              Check_solved.mblist_by_board_min = load_mblist("../data/mblist_by_board_min.dat")
11          mblist = Check_solved.mblist_by_board_min
12      else:
13          if Check_solved.mblist_by_board2 is None:
14              Check_solved.mblist_by_board2 = load_mblist("../data/mblist_by_board2.dat") 
15          mblist = Check_solved.mblist_by_board2        
16      if params is None:
17          params = {}
18      count = 0
19      incorrectlist = []
20      for mb in tqdm(mblist):
21          candidate = set(ai(mb, candidate=True, **params))
22          bestmoves = set(Check_solved.bestmoves_by_board[mb.board_to_str()])
23          if candidate <= bestmoves:
24              count += 1
25          else:
26              incorrectlist.append((mb, candidate, bestmoves))
27      nodenum = len(mblist)
28      print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
29      return count == nodenum, incorrectlist
30
31  Check_solved.is_strongly_solved = is_strongly_solved
```

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

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

@staticmethod
def is_strongly_solved(ai, params=None, consider_samedata=True):
    if Check_solved.bestmoves_by_board is None:
        Check_solved.bestmoves_by_board = load_bestmoves ("../data/bestmoves_by_board.dat")
    if consider_samedata:
        if Check_solved.mblist_by_board_min is None:
            Check_solved.mblist_by_board_min = load_mblist("../data/mblist_by_board_min.dat")
        mblist = Check_solved.mblist_by_board_min
    else:
        if Check_solved.mblist_by_board2 is None:
            Check_solved.mblist_by_board2 = load_mblist("../data/mblist_by_board2.dat") 
        mblist = Check_solved.mblist_by_board2        
    if params is None:
        params = {}
    count = 0
    incorrectlist = []
    for mb in tqdm(mblist):
        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(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
from tqdm import tqdm
from util import load_bestmoves, load_mblist

@staticmethod
-def is_strongly_solved(ai, params=None):
+def is_strongly_solved(ai, params=None, consider_samedata=True):
    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_min is None:
-       Check_solved.mblist_by_board_min = load_mblist("../data/mblist_by_board_min.dat")
+   if consider_samedata:
+       if Check_solved.mblist_by_board_min is None:
+           Check_solved.mblist_by_board_min = load_mblist("../data/mblist_by_board_min.dat")
+       mblist = Check_solved.mblist_by_board_min
+   else:
+       if Check_solved.mblist_by_board2 is None:
+           Check_solved.mblist_by_board2 = load_mblist("../data/mblist_by_board2.dat") 
+       mblist = Check_solved.mblist_by_board2        
    if params is None:
        params = {}
    count = 0
    incorrectlist = []
-   for mb in tqdm(Check_solved.mblist_by_board):
+   for mb in tqdm(mblist):
        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)
+   nodenum = len(mblist)
    print(f"{count}/{nodenum} {count/nodenum*100:.2f}%")
    return count == nodenum, incorrectlist

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

上記の修正後に、下記のプログラムで `ai14s` が強解決の AI であるかを、同一局面を考慮する場合と考慮しない場合で判定すると、実行結果のように異なるノード数で正しい判定が行われることが確認できます。

なお、下記のプログラムでは、先ほどと同様にクラス属性に直接 `None` を代入していますが、これらのクラス属性の初期化処理は util.py の Check_solved の定義の中に記述する必要があります。

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

実行結果

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

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

実行結果

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

# 今回の記事のまとめ

今回の記事では、弱解決の AI であるかを判定する処理を実装しました。

また、その際にゲーム木の探索について説明し、枝狩りという処理によって探索を効率的に行う手法について説明しました。

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

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/112/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [marubatsu_new.py](https://github.com/ysgeso/marubatsu/blob/master/112/marubatsu_new.py)  | 今回の記事で更新した marubatsu.py |
| [tree_new.py](https://github.com/ysgeso/marubatsu/blob/master/112/tree_new.py)  | 今回の記事で更新した tree.py |
| [util_new.py](https://github.com/ysgeso/marubatsu/blob/master/112/util_new.py)  | 今回の記事で更新した util.py |

# 次回の記事

https://qiita.com/ysgeso/items/903dc60e865ff56191fc

# 更新履歴

| 更新日時 | 更新内容 |
|:--|:--|
| 2024/09/02 | [is_weakly_solved_r の修正](#is_weakly_solved_r-の修正)にノートを追記しました |


[^1]:以前の記事でこのクラスの名前を `Chekc_strongly_solved` のようにしなかったのは、弱解決の AI であるかの判定を行うメソッドを定義する予定だったからです
[^2]:`_r` の r は、再帰呼び出し（recursive call）の英語の頭文字です
[^3]:これ以外にも、様々な名前の付け方があります