Pythonで〇×ゲームのAIを一から作成する　その173　ai_by_mmscore の定義と深さ制限探索による AI の実装

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108

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

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

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

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

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

# 深さ制限探索による AI の定義

今回の記事では、前回の記事で説明した __深さ制限探索__ を利用した AI を実装します。

下記は[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E6%B7%B1%E3%81%95%E5%88%B6%E9%99%90%E6%8E%A2%E7%B4%A2%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)で説明した深さ制限探索アルゴリズムの再掲です。

__ベースとなる__ αβ 法やスカウト法などの __ゲーム木の探索__ でノード $N$ に対するミニマックス値の近似値の計算を行う際に、下記の処理を行う。

* __深さの上限__ $\boldsymbol{d}$ を決める
* $N$ をルートノードとした、__深さが__ $\boldsymbol{d}$ __までのノード__ から構成される __部分木__ に対して下記の計算を行う
    * __リーフノード以外__ のノードの評価値の計算は、__ベースとなるゲーム木の探索と同じ方法__ で行う
    * __リーフノード__ の評価値の計算は __静的評価関数で行う__

## 本記事で利用する用語

今回の記事でも前回の記事に引き続き下記の用語を使用します。

__深さ制限探索__ は、__ゲーム木を探索する任意のアルゴリズム__ に対して適用することができます。本記事では 深さ制限探索を適用する __ゲーム木の探索__ アルゴリズムの事を __ベースとなるアルゴリズム__ と表記することにします。

__任意の局面__ に対して __局面の状況を表す評価値__ を計算する関数のことを __評価関数__ と呼びます。また、__局面の情報だけから__ 評価値を計算する評価関数のことを __静的評価関数__、__ゲーム木の探索__ を用いて評価値を計算する関数のことを __探索ベースの評価関数__ と表記します。

[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E6%9C%AC%E8%A8%98%E4%BA%8B%E3%81%A7%E3%81%AE%E6%B7%B1%E3%81%95%E5%88%B6%E9%99%90%E6%8E%A2%E7%B4%A2%E3%81%AE%E8%A1%A8%E8%A8%98%E6%96%B9%E6%B3%95)で説明したように、本記事では __深さの上限を__ $\boldsymbol{d}$、__静的評価関数を `eval_func`__ とする __深さ制限探索(depth limited search)__ のことを下記のように表記することにします。なお、この表記法は __本記事独自__ のもので、一般的な表記法ではありません。

__DLS(ベースとなるアルゴリズム, d, `eval_func`)__

## `@ai_by_score` を利用した深さ制限探索の実装方法

下記は[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E9%9D%99%E7%9A%84%E8%A9%95%E4%BE%A1%E9%96%A2%E6%95%B0%E3%82%92-ai_by_score-%E3%81%A7%E3%83%A9%E3%83%83%E3%83%97%E3%81%97%E3%81%9F%E5%A0%B4%E5%90%88%E3%81%AB%E8%A1%8C%E3%81%AA%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86)で説明した、__静的評価関数__ を __`@ai_by_score` でラップ__ した場合に行なわれる処理の再掲です。

@ai_by_score を利用して __定義された関数__ が行う処理は、ラップされた静的評価関数を `eval_func` と表記すると下記のように表記できる。

DLS(ネガマックス法, 1, `eval_func`)

__上記は__ 深さ 1 までのゲーム木の探索を行うので、__深さの上限を 1__ とする __深さ制限探索__ と考えることができます。

下記は[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E6%8E%A2%E7%B4%A2%E3%83%99%E3%83%BC%E3%82%B9%E3%81%AE%E8%A9%95%E4%BE%A1%E9%96%A2%E6%95%B0%E3%82%92-ai_by_score-%E3%81%A7%E3%83%A9%E3%83%83%E3%83%97%E3%81%97%E3%81%9F%E5%A0%B4%E5%90%88%E3%81%AB%E8%A1%8C%E3%81%AA%E3%82%8F%E3%82%8C%E3%82%8B%E5%87%A6%E7%90%86)で説明した、__探索ベースの評価関数__ を __`@ai_by_score` でラップ__ した場合に行なわれる処理の再掲です。

* __ルートノード__ に対しては、探索ベースの評価関数を利用した __DLS(ネガマックス法, 1, 探索ベースの評価関数)__ で処理を行う
* __深さ 1 のそれぞれの子ノード__ に対しては、ゲームの決着がついた局面の評価値を計算できる静的評価関数を利用した __DLS(探索アルゴリズム, ∞, 静的評価関数)__ で処理を行う

__`@ai_by_score` を利用__ した __深さ制限探索の AI の実装方法__ は、上記とよく似ています。具体的には、__深さの上限を制限__ した __探索ベースの評価関数__ を __`@ai_by_score` でラップ__ します。下記はその場合に行われる処理で、上記と異なる部分を太字にしました。

* ルートノードに対しては、__深さの上限を制限した__ 探索ベースの評価関数を利用した DLS(ネガマックス法, 1, 探索ベースの評価関数) で処理を行う
* 深さ 1 のそれぞれの子ノードに対しては、__任意の局面__ の評価値を計算できる静的評価関数を利用した DLS(探索アルゴリズム, __深さの上限__, 静的評価関数) で処理を行う

:::note warn
__深さの上限を制限__ する __探索ベースの評価関数__ を __`@ai_by_score` によってラップ__ することで、__深さ制限探索__ によって着手を選択する __AI の関数を定義__ することができる。
:::

## 深さ制限探索で着手を選択する場合の深さの上限の性質

深さ 1 のノードに対して行われる __深さ制限探索__ の __深さの上限を__ $\boldsymbol{d}$ と表記すると、上記の処理は __ルートノードから__ $\boldsymbol{1 + d}$ __までの深さ__ のノードの探索を行うので、__全体としてみる__ と __深さの上限を__ $\boldsymbol{d + 1}$ とした __深さ制限探索__ が行われることになります。

$\boldsymbol{d ≧ 0}$ なので、深さ制限探索によって着手を選択する AI での __ルートノードからの深さの上限は必ず 1 以上__ になるということを意味します。そのようになる理由は、ルートノードの __最善手__ を __子ノードの評価値によって計算__ するためには、必ず __深さが 1 である__ ルートノードの __子ノードの評価値を計算する必要がある__ からです。

__`@ai_by_score`__ が __2 種類の探索アルゴリズムを利用する理由__ は、[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#2-%E7%A8%AE%E9%A1%9E%E3%81%AE%E6%8E%A2%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%AE%E5%88%A9%E7%82%B9)で説明したように __最善手が複数存在する場合__ にその中から __ランダムに着手を選択できる__ ようにするためです。__最善手の中から 1 つを選択できれば良い__ 場合は、__1 種類の探索アルゴリズム__ で実装することができますが、__その場合でも__ 子ノードの評価値を計算する必要があるので __深さの上限は必ず 1 以上__ になります。

:::note warn
ルートノードの __子ノードの評価値によって最善手を計算__ する AI は、__深さの上限が 1 以上の深さ制限探索__ を行う。
:::

なお、__ノードの評価値を計算__ する場合は __深さの上限__ は __0 でもかまいません__。実際に __静的評価関数__ は __深さの上限が 0__ の深さ制限探索とみなすことができます。

# `ai_by_mmscore` の定義

上記で説明した方法で `@ai_by_score` を利用して深さ制限探索の AI を定義することをできますが、その方法にはいくつかの問題があるため、本記事では __別の `ai_by_mmscore` という関数を定義__ し __`@ai_by_mmscore` を利用して深さ制限探索の AI を定義__ することにします。

具体的には、__探索ベースの評価関数__ を __`@ai_by_score` でラップ__ した場合に __いくつかの問題が発生__ します。__深さ制限探索__ は __探索ベースのゲーム木の探索を行う__ ので `@ai_by_score` を利用して定義すると __同じ問題が発生__ します。どのような問題が発生するかについて少し考えてみて下さい。

## `@ai_by_score` の問題点

__`@ai_by_score`__ は[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#ai_by_score-%E3%81%8C%E8%A1%8C%E3%81%86%E5%87%A6%E7%90%86%E3%81%AE%E8%AA%AC%E6%98%8E%E3%81%A8%E6%94%B9%E8%89%AF)で説明したように __ネガマックス法__ で __ルートノードの子ノードの探索__ を行うため、__子ノードの局面の評価値__ として __直前の手番のプレイヤーが有利になるほど大きな値__ を計算します。

:::note
ネガマックス法の評価関数は、[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E3%83%8D%E3%82%AC%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95%E3%81%AE%E5%AE%9F%E8%A3%85%E4%BE%8B)でネガマックス法の実装例で示したように、__その局面の手番__ のプレイヤーが有利になるほど大きな値を計算し、計算された __子ノードの評価値の符号を反転__ するのが一般的ですが、__`@ai_by_score` の評価関数__ はそれとは __異なる評価値を計算__ します。

`@ai_by_score` はネガマックス法でルートノードの評価値の計算を行いますが、評価関数が上記の逆に __直前の手番__ のプレイヤーが有利になるほど大きな値を計算することで、計算された子ノードの評価値の __符号を反転しなくても良い__ ようにします。
:::

そのことが原因で、__`ai_mmdfs`__ や __`ai_ab_all`__ などの、__ゲーム木の探索__ によって局面の __ミニマックス値を計算__ する場合に __`@ai_by_score`__ を利用すると、評価関数が __評価値を__ 返り値として __返す処理を行う際__ に、計算した __ミニマックス値を__ 直前の手番のプレイヤーが有利になるほど大きな値になるように __変換する処理が必要__ となります。

具体的には、__ミニマックス値__ は先手である __〇 の手番のプレイヤーが有利なほど大きな値__ を計算するので、__〇 の手番の場合__ は計算した __ミニマックス値の符号を反転__ させる必要があります。その処理は `ai_mmdfs` などの関数の __最後に記述された下記のプログラム__ で行います。

```python
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```

__上記の符号を反転する処理__ は __直観的にわかりづらい__ ので、__ミニマックス値を計算する評価関数__ を利用できる __`ai_by_mmscore`__ という __関数を定義__ することにします。

__`ai_by_mmscore`__ が行う処理は、__以下の点を除けば `ai_by_score` とほぼ同じ__ です。名前の __`mmscore`__ は __ミニマックス値（mini-max score）によって着手を選択する__ ことが由来です。

* __評価関数が計算する評価値__ が __ミニマックス値__ である
* __ルートノードの子ノードの計算__ をネガマックス法ではなく、__ミニマックス法で行う__

## 置換表の共有の有無を表す仮引数の追加

[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#ai_by_score-%E3%81%A7%E3%81%AE%E7%BD%AE%E6%8F%9B%E8%A1%A8%E3%81%AE%E5%85%B1%E6%9C%89)で __`@ai_by_score`__ を使って定義された AI の関数が子ノードの評価値を計算する際に __置換表を共有する方法__ を紹介しましたが、その方法は `ai_mmdfs_tt(mb, tt={}, debug=True)` のように __キーワード引数 `tt={}` を記述して呼び出す__ いうものでした。

この方法には以下のような問題があります。

* 置換表を共有する際に記述する __`tt={}`__ の __意味がわかりづらい__
* 置換表を共有することで [処理時間が大幅に減る](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E5%B7%AE%E3%81%AE%E7%A2%BA%E8%AA%8D)ため、__置換表を共有する場合__ は __キーワード引数の記述を省略__ できるようにし、__置換表を共有しない場合__ に何らかの __キーワード引数を記述__ するようにしたほうが便利である

この問題を解決する方法として、__`ai_by_score`__ の __ラッパー関数 `wrapeer`__ に __`True` が代入__ された場合に __置換表を共有（share）__ する処理を行う __`share_tt` という仮引数を追加__ し、下記のように `ai_by_score` を修正するという方法を考えた人がいるかもしれませんが、__この方法ではうまくいかない場合__ があります。

* __8 行目__：デフォルト値を `True` とする `share_tt` という仮引数を追加する
* __10 行目__：ローカル変数 `tt` に `share_tt` が `True` の場合は空の dict を、そうでない場合は `None` を代入する
* __20 行目__：評価関数を呼び出す際にキーワード引数 `tt=tt` を記述するように修正することで、`share_tt` が `True` の場合は `tt` に代入された置換表を表す dict が共有され、`None` の場合は置換表が共有されなくなる

```python
 1  from ai import dprint
 2  from functools import wraps
 3  from random import choice
 4  from copy import deepcopy
 5  
 6  def ai_by_score(eval_func):
 7      @wraps(eval_func)
 8      def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
 9                  analyze=False, calc_score=False, **kwargs):
元と同じなので省略
10          tt = {} if share_tt else None
11          if analyze:
12              score_by_move = {}
13          for move in legal_moves:
14              dprint(debug, "=" * 20)
15              dprint(debug, "move", move)
16              mb = deepcopy(mb_orig)
17              x, y = move
18              mb.move(x, y)
19              dprint(debug, mb)
20              score = eval_func(mb, debug, tt=tt, *args, **kwargs)
元と同じなので省略
```

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

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

def ai_by_score(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):
        if calc_score:
            return eval_func(mb_orig, debug, *args, **kwargs)

        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 = []
        tt = {} if share_tt else None
        if analyze:
            score_by_move = {}
        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, debug, tt=tt, *args, **kwargs)
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = 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 analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
            }
        elif rand:   
            return choice(best_moves)
        else:
            return best_moves[0]
        
    return wrapper
```
</details>

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

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

def ai_by_score(eval_func):
    @wraps(eval_func)
-   def wrapper(mb_orig, debug=False, *args, rand=True,
+   def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):
元と同じなので省略
+       tt = {} if share_tt else None
        if analyze:
            score_by_move = {}
        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, debug, tt=tt, *args, **kwargs)
+           score = eval_func(mb, debug, tt=tt, *args, **kwargs)
元と同じなので省略
```
</details>

### `@ai_by_score` の修正がうまくいく例

まず、この方法で __うまくいく場合__ について説明します。

上記の修正後に、__修正した `@ai_by_score` を利用して__ 下記のプログラムのように __探索ベースの評価関数__ を利用した __`ai_abs_all` を再定義__ します。`ai_abs_all` の定義そのものは何も変更していないのでプログラムは折りたたみました。

<details><summary><strong><code>ai_abs_all</code> の再定義</strong></summary>

```python
from marubatsu import Marubatsu

@ai_by_score
def ai_abs_all(mb, debug, shortest_victory=False, init_ab=False,
               use_tt=False, tt=None, ai_for_mo=None, params={},
               sort_allnodes=False, calc_count=False):           
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
    score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

下記のプログラムで __ゲーム開始時の局面__ に対して再定義した `ai_abs_all` を実行すると、実行結果のように __着手が選択__ されます。

```python
mb = Marubatsu()
ai_abs_all(mb, share_tt=False)
```

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

```
(1, 2)
```

また、下記のプログラムで __置換表を共有する場合としない場合__ で __強解決の AI であるか__ どうかを判定すると、__いずれも強解決の AI である__ ことが確認できます。

__置換表を共有する場合__

```python
from util import Check_solved
Check_solved.is_strongly_solved(ai_abs_all, params={"use_tt":True})
```

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

__置換表を共有しない場合__

```python
Check_solved.is_strongly_solved(ai_abs_all, params={"use_tt":True, "share_tt":False})
```

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

また、[前回の記事](https://qiita.com/ysgeso/items/8d4abe8fab3cfec55108#%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E5%B7%AE%E3%81%AE%E7%A2%BA%E8%AA%8D)と同様に、下記のプログラムで __`ai2s`__ との対戦を 100 回ずつ行うと、__処理時間__ が 26 秒と 92 秒となり __置換表を共有したほうが大幅に短くなる__ ことが確認できます。

```python
from ai import ai2s, ai_match

ai_match(ai=[ai_abs_all, ai2s], params=[{"use_tt": True}, {}], match_num=100)
ai_match(ai=[ai_abs_all, ai2s], params=[{"use_tt": True, "share_tt": False}, {}], match_num=100)
```

実行結果

```
ai_abs_all VS ai2s
100%|██████████| 100/100 [00:26<00:00,  3.83it/s]
count     win    lose    draw
o          95       0       5
x          75       0      25
total     170       0      30

ratio     win    lose    draw
o       95.0%    0.0%    5.0%
x       75.0%    0.0%   25.0%
total   85.0%    0.0%   15.0%

ai_abs_all VS ai2s
100%|██████████| 100/100 [01:32<00:00,  1.08it/s]
count     win    lose    draw
o          96       0       4
x          72       0      28
total     168       0      32

ratio     win    lose    draw
o       96.0%    0.0%    4.0%
x       72.0%    0.0%   28.0%
total   84.0%    0.0%   16.0%
```

### `@ai_by_score` の修正がうまくいかない例

次に、`@ai_by_score` を利用して、下記のプログラムのように常に評価値として 0 を計算する __静的評価関数__ を利用した __`ai2s` を再定義__ します。

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

上記の実行後に下記のプログラムでゲーム開始時の局面に対して `ai2s` で着手を選択すると、実行結果のような __エラーが発生__ します。

```python
ai2s(mb)
```

実行結果

```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[8], line 1
----> 1 ai2s(mb)

Cell In[1], line 29
     27 mb.move(x, y)
     28 dprint(debug, mb)
---> 29 score = eval_func(mb, debug, tt=tt, *args, **kwargs)
     30 dprint(debug, "score", score, "best score", best_score)
     31 if analyze:

TypeError: ai2s() got an unexpected keyword argument 'tt'
```

エラーメッセージは、`ai2s` が予期せぬ（unexpected）キーワード引数（keyword argument）`tt` を持つという意味で、実際に __`ai2s` は置換表を利用しない静的評価関数__ なので __仮引数 `tt` を持ちません__。

先程の修正によって __`@ai_by_score`__ が __ラップできる評価関数__ は以下のような性質を持つようになります。

* ラップする評価関数は __仮引数 `tt`__ によって __置換表を共有__ することができる、__探索ベースの評価関数__ である必要がある
* 置換表を利用しない __静的評価関数は利用できない__

このように、__先程の修正__ によって __`@ai_by_score`__ は __置換表を利用しない__、__静的評価関数__ を __ラップすることができなくなる__ という問題が発生します。

これから定義する __`ai_by_mmscore`__ がラップする関数は __ミニマックス値を計算__ する __探索ベースの評価関数__ です。従って、それらの関数を __仮引数 `tt`__ によって __置換表を共有__ できるように __定義する__ ことで、上記の問題は発生しなくなります。

## `ai_by_mmscore` の定義

__`ai_by_mmscore`__ と __`ai_by_score`__ の __違い__ は以下の通りです。

* ラップする __評価関数が計算する値__ が __ミニマックス値__ である
* __ルートノードの子ノードの計算__ をネガマックス法ではなく、__ミニマックス法で行う__
* ラップする評価関数は __探索ベースの評価関数__ で、置換表を共有するかどうかを表す __仮引数 `share_tt`__ を持つ

__`ai_by_mmscore`__ は __`ai_by_score` を修正__ することで下記のプログラムのように定義できます。なお、`share_tt` に関する修正は先ほど説明済なので省略します。

* __1 行目__：関数名を `ai_by_mmscore` に修正した
* __5 行目__：`mb_orig` が max ノードであるかどうかを判定してローカル変数に代入する
* __6 行目__：最善手の評価値の初期値をノードの種類に応じた値で初期化する
* __17 行目__：12 行目で計算した子ノードのミニマックス値がこれまでの最善手よりも優れているかを、ミニマックス法でノードの種類に応じた条件式で判定するように修正する。なお、and 演算子のほうが or 演算子よりも優先順位が高いので条件式の中の () は不要だが、わかりやすさを重視して () を記述した

```python
 1  def ai_by_mmscore(eval_func):
 2      @wraps(eval_func)
 3      def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
 4                  analyze=False, calc_score=False, **kwargs):
元と同じなので省略
 5          maxnode = mb_orig.turn == Marubatsu.CIRCLE
 6          best_score = float("-inf") if maxnode else float("inf")
 7          best_moves = []
 8          tt = {} if share_tt else None
 9          if analyze:
10              score_by_move = {}
11          for move in legal_moves:
元と同じなので省略
12              score = eval_func(mb, debug, tt=tt, *args, **kwargs)
13              dprint(debug, "score", score, "best score", best_score)
14              if analyze:
15                  score_by_move[move] = score
16              
17              if (maxnode and best_score < score) or (not maxnode and best_score > score):
18                  best_score = score
元と同じなので省略
```

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

```python
def ai_by_mmscore(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):
        if calc_score:
            return eval_func(mb_orig, debug, *args, **kwargs)

        dprint(debug, "Start ai_by_mmscore")
        dprint(debug, mb_orig)
        legal_moves = mb_orig.calc_legal_moves()
        dprint(debug, "legal_moves", legal_moves)
        maxnode = mb_orig.turn == Marubatsu.CIRCLE
        best_score = float("-inf") if maxnode else float("inf")
        best_moves = []
        tt = {} if share_tt else None
        if analyze:
            score_by_move = {}
        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, debug, tt=tt, *args, **kwargs)
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = score
            
            if (maxnode and best_score < score) or (not maxnode and 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 analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
            }
        elif rand:   
            return choice(best_moves)
        else:
            return best_moves[0]
        
    return wrapper
```
</details>

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

```diff_python
-def ai_by_score(eval_func):
+def ai_by_mmscore(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True, share_tt=True,
                analyze=False, calc_score=False, **kwargs):
元と同じなので省略
+       maxnode = mb_orig.turn == Marubatsu.CIRCLE
-       best_score = float("-inf")
+       best_score = float("-inf") if maxnode else float("inf")
        best_moves = []
        tt = {} if share_tt else None
        if analyze:
            score_by_move = {}
        for move in legal_moves:
元と同じなので省略
            score = eval_func(mb, debug, tt=tt, *args, **kwargs)
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = score
            
-           if maxnode and best_score < score:
+           if (maxnode and best_score < score) or (not maxnode and best_score > score):
                best_score = score
元と同じなので省略
```
</details>

## `ai_abs_all` の再定義

__`ai_by_mmscore`__ は __仮引数 `tt` を持ち__、__ミニマックス値を計算__ する __探索ベースの評価関数__ をラップすることができるので、それらの性質を持つ __αβ 法__ で着手を選択する __`ai_abs_all`__ を __`ai_by_mmscore`__ を利用して下記のプログラムのように __再定義__ することにします。

* __1 行目__：デコレータ式を `@ai_by_mmscore` に修正した
* 6 行目の後にあった __ミニマックス値を変換する処理を削除__ して __常にミニマックス値を返す__ ように修正した

```python
1  @ai_by_mmscore
2  def ai_abs_all(mb, debug, shortest_victory=False, init_ab=False,
3                 use_tt=False, tt=None, ai_for_mo=None, params={},
4                 sort_allnodes=False, calc_count=False):           
元と同じなので省略
5      if calc_count:
6          return count
7      return score
```

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

```python
@ai_by_mmscore
def ai_abs_all(mb, debug, shortest_victory=False, init_ab=False,
               use_tt=False, tt=None, ai_for_mo=None, params={},
               sort_allnodes=False, calc_count=False):           
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
    score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    return score
```
</details>

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

```diff_python
-@ai_by_score
+@ai_by_mmscore
def ai_abs_all(mb, debug, shortest_victory=False, init_ab=False,
               use_tt=False, tt=None, ai_for_mo=None, params={},
               sort_allnodes=False, calc_count=False):           
元と同じなので省略
    if calc_count:
        return count
-   if mb.turn == Marubatsu.CIRCLE:
-       score *= -1
    return score
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果から __再定義した `ai_abs_all`__ が以下の場合に __強解決の AI であることが確認__ できます。

* 置換表を利用しない場合
* 置換表を利用し、共有する場合
* 置換表を利用し、共有しない場合

```python
Check_solved.is_strongly_solved(ai_abs_all)
Check_solved.is_strongly_solved(ai_abs_all, params={"use_tt":True})
Check_solved.is_strongly_solved(ai_abs_all, params={"use_tt":True, "share_tt": False})
```

実行結果

```
100%|██████████| 431/431 [00:03<00:00, 115.10it/s]
431/431 100.00%
100%|██████████| 431/431 [00:02<00:00, 207.38it/s]
431/431 100.00%
100%|██████████| 431/431 [00:03<00:00, 131.60it/s]
431/431 100.00%
```

## `ai_mmdfs_all` の定義と `ai_scout`、`ai_mtdf` の再定義

__ミニマックス法__ で着手を選択する AI の関数は、__置換表を利用しない `ai_mmdfs`__ と __利用する `ai_mmdfs_tt`__ の 2 種類をこれまで定義しましたが、先程説明した理由から置換表を利用しない __`ai_mmdfs`__ を __`ai_by_mmscore` で再定義することはできません__。そこで、__ミニマックス法__ で __置換表の利用の有無を選択__ できる __`ai_mmdfs_all`__ を __`ai_mmdfs_tt` を修正__ して下記のプログラムのように定義することにします。

* __1 行目__：デコレータ式を `ai_by_mmscore` に修正した
* __2 行目__：デフォルト値を `False` とする仮引数 `use_tt` を追加した
* __6、8 ~ 13 行目__：`use_tt` が `True` の場合のみ置換表を利用するように修正した
* 19 行目の後にあったミニマックス値を変換する処理を削除して常にミニマックス値を返すように修正した

```python
 1  @ai_by_mmscore
 2  def ai_mmdfs_all(mb, debug=False, use_tt=False, tt=None, shortest_victory=False):
 3      count = 0
 4      def mm_search(mborig, tt):
元と同じなので省略
 5          boardtxt = mborig.board_to_str()
 6          if use_tt and boardtxt in tt:
 7              return tt[boardtxt]
元と同じなので省略
 8          if use_tt:
 9              from util import calc_same_boardtexts
10  
11              boardtxtlist = calc_same_boardtexts(mborig)
12              for boardtxt in boardtxtlist:
13                  tt[boardtxt] = score
14          return score
15      
16      if tt is None:
17          tt = {}
18      score = mm_search(mb, tt)
19      dprint(debug, "count =", count)
20      return score
```

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

```python
@ai_by_mmscore
def ai_mmdfs_all(mb, debug=False, use_tt=False, tt=None, shortest_victory=False):
    count = 0
    def mm_search(mborig, tt):
        nonlocal count
        count += 1

        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        boardtxt = mborig.board_to_str()
        if use_tt and boardtxt in tt:
            return tt[boardtxt]
        
        legal_moves = mborig.calc_legal_moves()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(mborig)
            mb.move(x, y)
            score_list.append(mm_search(mb, tt))
        if mborig.turn == Marubatsu.CIRCLE:
            score = max(score_list)
        else:
            score = min(score_list)
            
        if use_tt:
            from util import calc_same_boardtexts

            boardtxtlist = calc_same_boardtexts(mborig)
            for boardtxt in boardtxtlist:
                tt[boardtxt] = score
        return score
    
    if tt is None:
        tt = {}
    score = mm_search(mb, tt)
    dprint(debug, "count =", count)
    return score
```
</details>

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

```diff_python
-@ai_by_score
+@ai_by_mmscore
-def ai_mmdfs_tt(mb, debug=False, use_tt=False, tt=None, shortest_victory=False):
+def ai_mmdfs_all(mb, debug=False, use_tt=False, tt=None, shortest_victory=False):
    count = 0
    def mm_search(mborig, tt):
元と同じなので省略
        boardtxt = mborig.board_to_str()
-       if boardtxt in tt:
+       if use_tt and boardtxt in tt:
            return tt[boardtxt]
元と同じなので省略
-       from util import calc_same_boardtexts

-       boardtxtlist = calc_same_boardtexts(mborig)
-       for boardtxt in boardtxtlist:
-           tt[boardtxt] = score
+       if use_tt:
+           from util import calc_same_boardtexts

+           boardtxtlist = calc_same_boardtexts(mborig)
+           for boardtxt in boardtxtlist:
+               tt[boardtxt] = score
        return score
    
    if tt is None:
        tt = {}
    score = mm_search(mb, tt)
    dprint(debug, "count =", count)
-   if mb.turn == Marubatsu.CIRCLE:
-       score *= -1
    return score
```
</details>

先程と同様に、下記のプログラムを実行することで、実行結果から __`ai_mmdfs_all`__ が先程と同じ 3 種類の場合に __強解決の AI であることが確認__ できます。

```python
Check_solved.is_strongly_solved(ai_mmdfs_all)
Check_solved.is_strongly_solved(ai_mmdfs_all, params={"use_tt":True})
Check_solved.is_strongly_solved(ai_mmdfs_all, params={"use_tt":True, "share_tt": False})
```

実行結果

```
100%|██████████| 431/431 [00:15<00:00, 28.04it/s] 
431/431 100.00%
100%|██████████| 431/431 [00:02<00:00, 171.20it/s]
431/431 100.00%
100%|██████████| 431/431 [00:05<00:00, 78.79it/s] 
431/431 100.00%
```

スカウト法の __`ai_scout`__ と MTD(f) 法の __`ai_mtdf`__ も __`ai_by_mmscore`__ を利用して下記のプログラムのように __再定義__ することができます。修正箇所はいずれも以下の 2 点のみなので説明は省略します。

* デコレータ式を `ai_by_mmscore` に修正する
* ミニマックス値を変換する処理を削除して常にミニマックス値を返すように修正する

<details><summary><strong><code>ai_scout</code>の再定義</strong></summary>

```python
@ai_by_mmscore
def ai_scout(mb, debug=False, shortest_victory=False,
             init_ab=False, use_tt=False, tt=None, ai_for_mo=None,
             params={}, sort_allnodes=False, calc_count=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]

        if mborig.turn == Marubatsu.CIRCLE:
            x, y = legal_moves[0]
            mb = deepcopy(mborig)
            mb.move(x, y)
            score = ab_search(mb, tt, alpha, beta)
            alpha = max(alpha, score)
            if score < beta:
                for x, y in legal_moves[1:]:
                    mb = deepcopy(mborig)
                    mb.move(x, y)
                    score = max(score, ab_search(mb, tt, alpha, alpha + 1))
                    if score >= beta:
                        break
                    elif score > alpha:
                        score = max(score, ab_search(mb, tt, alpha, beta))
                        if score >= beta:
                            break
                        alpha = max(alpha, score)
        else:
            x, y = legal_moves[0]
            mb = deepcopy(mborig)
            mb.move(x, y)
            score = ab_search(mb, tt, alpha, beta)
            beta = min(beta, score)
            if score > alpha:
                for x, y in legal_moves[1:]:
                    mb = deepcopy(mborig)
                    mb.move(x, y)
                    score = min(score, ab_search(mb, tt, beta - 1, beta))
                    if score <= alpha:
                        break
                    elif score < beta:
                        score = min(score, ab_search(mb, tt, alpha, beta))
                        if score <= alpha:
                            break
                        beta = min(beta, score)   
            
        if use_tt:
            from util import calc_same_boardtexts

            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
    score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    return score
```
</details>

<details><summary><strong><code>ai_scout</code>の再定義</strong></summary>

```python
@ai_by_mmscore
def ai_mtdf(mb, debug=False, shortest_victory=False,
             init_ab=False, use_tt=False, tt=None, f=0, ai_for_mo=None,
             params={}, sort_allnodes=False, calc_count=False):           
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return (11 - mborig.move_count) / 2 if shortest_victory else 1
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    lbound = min_score if init_ab else float("-inf")
    ubound = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
    dprint(debug, "      count | ウィンドウ | αβ 値 |      type |    MM の範囲")
    while lbound != ubound:
        beta = f + 1 if lbound == f else f
        prevcount = count
        f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
        if f >= beta:
            lbound = f
            type = "fail high"
        else:
            ubound = f
            type = "fail low "
        dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} |  ({beta - 1:2.0f}, {beta:2.0f}) |    {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
 
    score = f
            
    if calc_count:
        return count
    return score

```
</details>

先程と同様に、下記のプログラムを実行することで、実行結果から __`ai_scout`__ と __`ai_mtdf`__ が先程と同じ 3 種類の場合に __強解決の AI であることが確認__ できます。なお、スカウト法では最善手を推定するための関数として `ai14s` を利用しました。

```python
from ai import ai14s

Check_solved.is_strongly_solved(ai_scout, params={"ai_for_mo": ai14s})
Check_solved.is_strongly_solved(ai_scout, params={"ai_for_mo": ai14s, "use_tt":True})
Check_solved.is_strongly_solved(ai_scout, params={"ai_for_mo": ai14s, "use_tt":True, "share_tt": False})
Check_solved.is_strongly_solved(ai_mtdf, params={"f": 0})
Check_solved.is_strongly_solved(ai_mtdf, params={"f": 0, "use_tt":True})
Check_solved.is_strongly_solved(ai_mtdf, params={"f": 0, "use_tt":True, "share_tt": False})
```

実行結果

```
100%|██████████| 431/431 [00:05<00:00, 81.57it/s] 
431/431 100.00%
100%|██████████| 431/431 [00:03<00:00, 112.05it/s]
431/431 100.00%
100%|██████████| 431/431 [00:05<00:00, 85.48it/s] 
431/431 100.00%
100%|██████████| 431/431 [00:04<00:00, 93.00it/s] 
431/431 100.00%
100%|██████████| 431/431 [00:01<00:00, 249.91it/s]
431/431 100.00%
100%|██████████| 431/431 [00:02<00:00, 182.14it/s]
431/431 100.00%
```

# 深さ制限探索の AI の実装

下記は __深さ制限探索アルゴリズムの再掲__ です。

__ベースとなる__ αβ 法やスカウト法などの __ゲーム木の探索__ でノード $N$ に対するミニマックス値の近似値の計算を行う際に、下記の処理を行う。

* __深さの上限__ $\boldsymbol{d}$ を決める
* $N$ をルートノードとした、__深さが__ $\boldsymbol{d}$ __までのノード__ から構成される __部分木__ に対して下記の計算を行う
    * __リーフノード以外__ のノードの評価値の計算は、__ベースとなるゲーム木の探索と同じ方法__ で行う
    * __リーフノード__ の評価値の計算は __静的評価関数で行う__

上記から、__深さ制限探索を行う関数__ は __深さの上限___ と __静的評価関数__ を代入する __仮引数が必要__ になることがわかります。

先程再定義した __`ai_by_mmscore` を修正__ して深さ制限探索の AI を実装する場合に、深さ制限探索で利用する __静的評価関数__ として __`ai1s` ~ `ai14s`__ をそのまま __利用することはできません__。その理由について少し考えてみて下さい。

その理由は以下のように、`@ai_by_mmscore` と `@ai_by_score` がラップする評価関数が計算する __評価値の性質が異なる__ からです。

* __`@ai_by_mmscore`__ がラップする __評価関数__ は評価値として、先手である __〇 の手番が有利になるほど大きな値__ である __ミニマックス値を計算__ する
* __`@ai_by_score`__ がラップする __評価関数__ は評価値として、__直前の手番のプレイヤーが有利になるほど大きな値__ を計算する

## `ai_by_score` の修正

この問題を解決するためには、__`@ai_by_score`__ を利用して定義された関数が `calc_score=True` を記述して呼び出された場合に、__ミニマックス値を計算できる__ ように修正する必要があります。そこで __`ai_by_score`__ のラッパー関数 `wrapper` を下記のプログラムのように、__`True` が代入__ された場合に __ミニマックス値を返す仮引数を追加__ するように修正することにします。

なお、先程追加した `share_tt` に関する処理があるとエラーが発生するので、下記はそれらの処理を削除したプログラムに対する修正です。

* __3 行目__：ラッパー関数にデフォルト値を `False` とする仮引数 `minimax` を追加する
* __5 ~ 8 行目__：`mb_orig` の局面の評価値を計算して返す処理を行う際に、__`minimax` が `True` の場合__ は先手の 〇 の手番の場合に評価値の符号を反転させることで、__常にミニマックス値を返すように修正__ する


```python
1  def ai_by_score(eval_func):
2      @wraps(eval_func)
3      def wrapper(mb_orig, debug=False, *args, rand=True,
4                  analyze=False, calc_score=False, minimax=False, **kwargs):
5          if calc_score:
6              score = eval_func(mb_orig, debug, *args, **kwargs)
7              if minimax and mb_orig.turn == Marubatsu.CIRCLE:
8                  score *= -1
9              return score
元と同じなので省略
```

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

```python
def ai_by_score(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True,
                analyze=False, calc_score=False, minimax=False, **kwargs):
        if calc_score:
            score = eval_func(mb_orig, debug, *args, **kwargs)
            if minimax and mb_orig.turn == Marubatsu.CIRCLE:
                score *= -1
            return score

        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 = []
        if analyze:
            score_by_move = {}
        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, debug, *args, **kwargs)
            dprint(debug, "score", score, "best score", best_score)
            if analyze:
                score_by_move[move] = 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 analyze:
            return {
                "candidate": best_moves,
                "score_by_move": score_by_move,
            }
        elif rand:   
            return choice(best_moves)
        else:
            return best_moves[0]
        
    return wrapper
```
</details>

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

```diff_python
def ai_by_score(eval_func):
    @wraps(eval_func)
    def wrapper(mb_orig, debug=False, *args, rand=True,
-               analyze=False, calc_score=False, **kwargs):
+               analyze=False, calc_score=False, minimax=False, **kwargs):
        if calc_score:
-           return eval_func(mb_orig, debug, *args, **kwargs)
+           score = eval_func(mb_orig, debug, *args, **kwargs)
+           if minimax and mb_orig.turn == Marubatsu.CIRCLE:
+               score *= -1
+           return score
元と同じなので省略
```
</details>

## `ai14s` の再定義

上記の修正後に、修正した `ai_by_score` を使って下記のプログラムのように __`ai14s` を再定義__ します。

<details><summary><strong><code>ai14s</code>の再定義</strong></summary>

```python
from pprint import pprint
from ai import Markpat

@ai_by_score
def ai14s(mb, debug=False, score_victory=300, score_sure_victory=200,
          score_defeat=-100, score_special=100, score_201=2,
          score_102=0.5, score_012=-1):
    # 評価値の合計を計算する変数を 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
```
</details>

上記の修正によって、__`ai14s`__ がキーワード引数 __`minimax=True`__ を記述することで __先手の 〇 の手番の場合に評価値の符号が反転する__ ようになったことを確認することにします。

__ゲーム開始時__ の __〇 の手番__ に対しては __`ai14s`__ は __評価値として 0__ を返しますが、下記のプログラムのように __`minimax=True` を記述__ すると、__-0.0 のように符号が反転する__ ことが確認できます。なお、表示は異なりますが、__0.0 と -0.0__ はどちらも 0 で __同じ数値__ を表します。

```python
print(ai14s(mb, calc_score=True))
print(ai14s(mb, calc_score=True, minimax=True))
```

実行結果

```
0.0
-0.0
```

下記は (1, 1) を着手した __× の手番__ の場合で、実行結果から __どちらも同じ評価値が計算__ されることが確認できます。

```python
mb.move(1, 1)
print(ai14s(mb, calc_score=True))
print(ai14s(mb, calc_score=True, minimax=True))
```

実行結果

```
2.0
2.0
```

念のためさらに (0, 0) に着手した __〇 の手番__ の場合を確認すると、実行結果から __評価値の符号が反転する__ ことが確認できます。

```python
mb.move(0, 0)
print(ai14s(mb, calc_score=True))
print(ai14s(mb, calc_score=True, minimax=True))
```

実行結果

```
2.0
-2.0
```

## `ai_abs_dls` の定義

__深さ制限探索__ を行う AI として、__αβ 法をベース__ とした深さ制限探索で着手を選択する __`ai_abs_dls`__ という関数を __`ai_abs_all` を修正__ して定義することにします。なお、名前の dls は深さ制限探索を表す depth limited search の略です。

__`ai_abs_all` との違い__ は以下の通りです。

* __深さの上限を代入__ する仮引数 __`maxdepth` を追加__ する
* __静的評価関数__ と、静的評価関数が必要とする __パラメータ__ を代入する仮引数 __`eval_func`__、__`eval_params` を追加__ する
* 評価値は静的評価関数で計算するため __`shortest_victory` は利用できないので削除__ する
* __評価値の最小値と最大値__ は __静的評価関数によって異なる__ ため α 値と β 値の初期値を評価値の最小値と最大値に設定することはできないので __`init_ab` を削除__ する
* 深さ制限探索では move ordering はまだ説明していない反復深化という手法を利用して行うのが一般的なので、__move ordering に関する処理は削除__ する

下記は `ai_abs_dls` の定義です。

* __1 行目__：デコレータ式を `ai_by_mmscore` に修正する
* __2、3 行目__：関数名を `ai_abs_dls` に修正し、仮引数 `maxdepth`、`eval_func`、`eval_params` を追加し、仮引数 `shortest_victory`、`init_ab`、move ordering に関する仮引数を削除する。なお、追加する仮引数は仮引数 `debug` の後に記述する必要があるのでデフォルト引数とした
* __5 行目__：`mb` をルートノードとした部分木での、`ab_search` で評価値を計算する `mborig` の深さを代入する仮引数 `depth` を追加する
* __8、9 行目__：決着がついているか、`mborig` の深さを表す __`depth`__ が深さの上限を表す __`maxdepth` 以上の場合__ に静的評価関数 `eval_func` の __キーワード引数に `calc_score=True` を記述__ して呼び出すことで __`mborig` の局面の評価値を計算__ する
* __12、14 行目__：__`ab_search` の再帰呼び出し__ によって __深さが 1 増えた子ノードの評価値を計算__ するので、__深さを表す実引数に `depth + 1` を記述__ するように修正する
* __15、16 行目__：評価値の下界と上界を表す変数に負の無限大と正の無限大を代入するように修正する
* __20 行目__：__`mb` のミニマックス値を計算__ する処理を行う際に、__`mb` の深さを表す実引数に `0`__ を記述し、α 値と β 値の初期値に評価値の下界と上界を記述するように修正する
* move ordering に関する処理を削除する

```python
 1  @ai_by_mmscore
 2  def ai_abs_dls(mb, debug=False, maxdepth=1, eval_func=None, eval_params={},
 3                 use_tt=False, tt=None, calc_count=False):           
 4      count = 0
 5      def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
 6          nonlocal count
 7          count += 1
 8          if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
 9              return eval_func(mborig, calc_score=True, **eval_params)
元と同じなので省略
10          legal_moves = mborig.calc_legal_moves()
11          if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
12                  score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
元と同じなので省略
13          else:
元と同じなので省略
14                  score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
元と同じなので省略
15      min_score = float("-inf")
16      max_score = float("inf")
17  
18      if tt is None:
19          tt = {}
20      score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
21      dprint(debug, "count =", count)
22      if calc_count:
23          return count
24      return score
```

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

```python
@ai_by_mmscore
def ai_abs_dls(mb, debug=False, maxdepth=1, eval_func=None, eval_params={},
               use_tt=False, tt=None, calc_count=False):           
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt in boardtxtlist:
                tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = float("-inf")
    max_score = float("inf")

    if tt is None:
        tt = {}
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    return score
```
</details>

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

```diff_python
-@ai_by_score
+@ai_by_mmscore
-def ai_abs_all(mb, debug=False, shortest_victory=False, init_ab=False,
-               use_tt=False, tt=None, ai_for_mo=None, params={},
-               sort_allnodes=False, calc_count=False):
+def ai_abs_dls(mb, debug, maxdepth=1, eval_func=None, eval_params={},
+              use_tt=False, tt=None, calc_count=False):           
    count = 0
-   def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
+   def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
-       if mborig.status == Marubatsu.CIRCLE:
-           return (11 - mborig.move_count) / 2 if shortest_victory else 1
-       elif mborig.status == Marubatsu.CROSS:
-           return (mborig.move_count - 10) / 2 if shortest_victory else -1
-       elif mborig.status == Marubatsu.DRAW:
-           return 0
+       if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
+           return eval_func(mborig, calc_score=True, **eval_params)
元と同じなので省略
        legal_moves = mborig.calc_legal_moves()
-       if ai_for_mo is not None:
-           if sort_allnodes:
-               score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
-               score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
-               legal_moves = [x[0] for x in score_by_move_list]
-           else:
-               legal_moves = mborig.calc_legal_moves()
-               bestmove = ai_for_mo(mborig, rand=False, **params)
-               index = legal_moves.index(bestmove)
-               legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        if mborig.turn == Marubatsu.CIRCLE:
元と同じなので省略
-               score = max(score, ab_search(mb, tt, alpha, beta))
+               score = max(score, ab_search(mb, depth + 1, tt, alpha, beta))
元と同じなので省略
        else:
元と同じなので省略
-               score = min(score, ab_search(mb, tt, alpha, beta))
+               score = min(score, ab_search(mb, depth + 1, tt, alpha, beta))
元と同じなので省略
-   min_score = -2 if shortest_victory else -1
-   max_score = 3 if shortest_victory else 1
+   min_score = float("-inf")
+   max_score = float("inf")
-   alpha = min_score if init_ab else float("-inf")
-   beta = max_score if init_ab else float("inf")

    if tt is None:
        tt = {}
-   score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
+   score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    if calc_count:
        return count
    return score
```
</details>

## `@ai_by_mmscore` を利用して定義した関数の処理の注意点

[先程説明](#深さ制限探索で着手を選択する場合の深さの上限の性質)した、__深さ制限探索で着手を選択__ する場合の __深さの上限の性質__ は __`@ai_by_mmscore`__ を利用して __定義した関数にも当てはまります__。

そのため、__`@ai_by_mmscore` を利用して定義された関数__ はの __仮引数 `calc_score`__ に代入された値によって、__仮引数 `maxdepth`__ に代入された __深さの上限を表す数値の意味__ が下記のように __異なる点に注意して下さい__。


:::note warn
__`@ai_by_mmscore` を利用して定義された関数__ は、__仮引数 `calc_score`__ に代入された値によって下記のような __異なる処理を行う__。

__`calc_score=True`__ の場合は、ルートノードから __深さ `maxdepth` まで__ のノードの探索によって __ルートノードのミニマックス値を計算__ する。

__`calc_score=False` の場合__ は、下記の理由からルートノードから __深さ `maxdepth + 1` まで__ のノードの探索によって __最善手を計算__ する。

* `calc_score=False` の場合は、ルートノードの __子ノードの評価値__ を深さ制限探索で __計算する際__ の __深さの上限が `maxdepth`__ となる
* ルートノードの __子ノードの深さは 1__ なので、__深さが `maxdepth + 1` まで__ のノードの探索が行われる
:::

## 動作の確認

上記の性質から、__〇× ゲーム木__ のゲーム木の __最大の深さは 9__ なので、__`ai_abs_dls`__ で __ゲーム開始時__ の最善手を計算する際に __設定できる深さの上限は 0 ~ 8__ となります。なお、深さの上限として __9 以上の値__ を設定して計算することもできますが、深さが 10 のノードは存在しないのでその場合は __深さの上限を 8 と設定した場合と同じ処理__ が行われます。

:::note
キーワード引数 `calc_score=True` を記述して呼び出した場合は、深さの上限として 0 ~ 9 を設定でき、10 以上を設定した場合は 9 を設定した場合と同じ処理を行います。
:::

下記のプログラムで、__ゲーム開始時の局面__ に対して __深さの上限を 0 ~ 8__、__静的評価関数__ を __`ai14s`__ とした場合の __`ai_abs_dls` の動作を確認__ することにします。なお、__`@ai_by_score` を利用して定義__ された `ai14s` を __静的関数として利用する場合__ は __呼び出す際のパラメータ__ に __`{"minimax": True}`__ を記述して __ミニマックス値を計算する必要がある__ ことを忘れないように注意して下さい。なお、`mb` に対して先程着手を行ったので 1 行目の `mb.restart()` でゲーム開始時の局面に戻す処理を行っています。

```python
mb.restart()
for maxdepth in range(9):
    print(maxdepth, ai_abs_dls(mb, maxdepth=maxdepth, eval_func=ai14s,
          eval_params={"minimax": True}))
```

実行結果

```
0 (1, 1)
1 (1, 1)
2 (1, 1)
3 (1, 1)
4 (1, 1)
5 (1, 1)
6 (1, 1)
7 (0, 2)
8 (0, 2)
```

実行結果から __深さの上限が 0 ~ 6 まで__ は __(1, 1) のみ__ が、__7 と 8__ の場合は __それ以外の合法手も選択されること__ が確認できました。

なお、__深さが 7 と 8__ の場合は下記のプログラムのようにそれぞれ 10 回実行することで、__ランダムな合法手が選択__ されることがわかります。

```python
for maxdepth in range(7, 9):
    for _ in range(10):
        print(maxdepth, ai_abs_dls(mb, maxdepth=maxdepth, eval_func=ai14s, eval_params={"minimax": True}))
```

実行結果

```
7 (2, 2)
7 (0, 1)
7 (0, 1)
7 (0, 2)
7 (1, 0)
7 (1, 0)
7 (2, 0)
7 (0, 0)
7 (2, 1)
7 (2, 0)
8 (0, 2)
8 (1, 2)
8 (2, 1)
8 (1, 0)
8 (2, 1)
8 (2, 2)
8 (0, 0)
8 (1, 1)
8 (1, 2)
8 (1, 0)
```

深さ制限探索で深さを増やすとどのような処理が行われるかについては次回の記事で説明します。深さが 7 と 8 の場合に上記のように異なる合法手が選択される理由についても次回の記事で説明するので、余裕がある方はその理由について少し考えてみて下さい。

なお、ミニマックス法、スカウト法、mtd(f) をベースとした深さ制限探索を行う関数も同様の方法で定義できますが、長くなったので次回以降の記事で定義することにします。

# 今回の記事のまとめ

今回の記事ではミニマックス値を計算する評価関数を `@ai_by_score` でラップする場合の問題点を説明し、その問題を解決する `ai_by_mmscore` を定義しました。また、それを利用してこれまでに作成したミニマックス値を計算する AI を再定義しました。

次に、`@ai_by_mmscore` を利用して αβ 法をベースとした深さ制限探索によって着手を選択する `ai_abs_dls` を定義しました。次回の記事では定義した `ai_abs_dls` が行う処理の性質について説明します。

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/173/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/173/ai_new.py)  | 本記事で更新した ai_new.py  |

# 次回の記事

https://qiita.com/ysgeso/items/9ca6d261d5d76130ba65