Pythonで〇×ゲームのAIを一から作成する　その163　null window search

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/094fc04eb693b208fa02

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

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

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

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

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

# αβ 法の効率化の手法

__αβ 法__ を利用することで、__ミニマックス法と同じ評価値__ を、ミニマックス法よりも __効率よく計算__ することができますが、__計算時間は短いほうが望ましい__ ので、αβ 法を __さらに効率化するための様々な手法__ が考えられています。本記事ではこれまでに以下のような αβ 法の効率化を紹介済です。

* __move ordering__
[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29)で紹介した __子ノードの評価値の計算__ を、__評価値が高い順__ に行うように __並べ替える__ という手法のことです。以前の記事ではこの手法の呼び方について紹介するのを忘れていましたが、この手法のことを __move ordering__（直訳すると合法手の並べ替え）と呼びます
* [__置換表付き αβ 法__](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394)[^1]
* __α 値と β 値の初期値を評価値の最小値と最大値に設定__ する手法
[以前の記事](https://qiita.com/ysgeso/items/b90305993d682ff16793#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E5%88%9D%E6%9C%9F%E5%80%A4%E3%81%AE%E5%A4%89%E6%9B%B4%E3%81%AB%E3%82%88%E3%82%8B%E6%9E%9D%E7%8B%A9%E3%82%8A)で説明した効率化です。実はこの手法は今回の記事で説明する null window search を利用した効率化の手法と類似しています

上記のうち __move ordering__ が αβ 法の枝狩りの __効率の上昇に最も大きく寄与する__ と言われています。

__置換表付き αβ 法__ は、__同一局面が頻繁に生じる__ ようなゲームでは効率の上昇に大きく寄与します。

本記事では __null window__、または __null window search__ と呼ばれる手法を利用した __αβ 法__（または αβ 法に類似するアルゴリズム）__の効率を向上させる__ いくつかのアルゴリズムを紹介することにします。なお、null window search の適切な日本語訳を探したのですが見つからなかったので、本記事では null window search と英語でそのまま表記することにします。

:::note
null window を直訳すると「（中身が）0 のウィンドウ」という意味になりますが、下記の Chess programming の wiki では null window という用語が「A Null Window, 略, is a way to 略」のように説明されており、「手法（way）」という意味で null window という用語が使われているようです。
:::

:::note
null window には以下のような様々な呼び方があるようです。

* zero window：ウィンドウ幅（意味は後述します）が 0 なため
* scout window：確証はありませんが、おそらく次回の記事で説明する scout 法で null window の手法がはじめて利用されたため
* narrow window：実際にはウィンドウ幅が 0 ではなく非常に小さな狭い（narrow）値とするのが一般的であるため
:::

参考までに null window の Chess programing の wiki と、null window search の Wikipedia のリンクを下記に示します。

https://www.chessprogramming.org/Null_Window

https://ja.wikipedia.org/wiki/MTD-f#Null_Window_Search

# null window search

最初に null window search を説明するために必要ないくつかの __用語を説明__ します。

なお、説明を短くするために[以前の記事](https://qiita.com/ysgeso/items/42c2140766dd59906a02#%E4%BB%8A%E5%9B%9E%E3%81%AE%E8%A8%98%E4%BA%8B%E3%81%A7%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E8%A8%98%E5%8F%B7)と同様に、ノードの評価値を計算する際の __α 値と β 値の初期値__ を __単に__ $\boldsymbol{α}$、$\boldsymbol{β}$ __と表記__ することにします。

## ウィンドウとウィンドウ幅

αβ 法では、__ノードの評価値__ として $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __の範囲内の値が計算__ された場合は、__正確なミニマックス値が計算__ されます。__本記事__ ではその __範囲内として計算された評価値__ のこと __厳密（exact）なミニマックス値が計算される__ ことから本記事独自の用語として __exact value と表記__ してきました。αβ 法では、この $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __の範囲__[^2]のことを __ウィンドウ__（window）、__範囲の幅__（$= β - α$） のことを __ウィンドウ幅__（window width）と呼びます。

本記事では以後は __exact valut の範囲と同じ__ である $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __の範囲__ のことを __ウィンドウ__ と表記することにします。

:::note
コンピューター用語では、αβ 法に限らず __何らかの範囲を表すもの__ のことを __window と呼ぶ__ ことが良くあります。これは、__現実の窓__（window）が __範囲を持つことが由来__ となっています。

また、アプリケーションが表示される四角い領域のことを window と呼ぶのは、窓のような四角い範囲の領域にアプリケーションの内容を表示することが由来です。
:::

## null

__null__ とは __数学で 0 を意味する用語__ で、__null window__ とは __ウィンドウ幅が 0__ の状態、すなわち $α$ __と__ $β$ __が等しい状態__ を意味します。ただし、null window search では、実際には後述する理由から __ウィンドウ幅__ を 0 ではなく、__1 などの小さな値とするのが一般的__ です。

## null window search とは何か

以下の説明では αβ 法で評価値を計算するノードのことを $N$ と表記することにします。

__これまでに説明__ してきた __αβ 法__ では $N$ の評価値を計算する際に、__正確なミニマックス値が計算__ される exact value の範囲である __ウィンドウ__（$α$ と $β$ の範囲）を以下のいずれかに設定することで、__評価値の範囲を全て含む__ ようにしました。また、$N$ の __子孫ノードの評価値を計算__ する際は、ウィンドウを __親ノードの評価値の計算に影響を与える範囲__ として設定していました。その結果 $N$ の __正確なミニマックス値を求める__ ことができます。

* $α$ と $β$ を負の無限大と正の無限大とする
* $α$ と $β$ を評価値の最小値と最大値とする

逆に言えば、$N$ の評価値を計算する際の __ウィンドウ__ が、__評価値として計算される値の範囲__（これまでの例では -1 ~ 1 や -2 ~ 3 の範囲）__を含まない__ 場合は、$N$ の評価値として __fail low__ や __fail high__  の範囲の値が __計算される場合があり__、その場合は __正確なミニマックス値を計算することはできません__。

:::note
$α$ と $β$ は __ウィンドウには含まれない__ ので、上記の $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __を評価値の最小値と最大値とする場合__ は実際には __評価値の範囲がすべて含まれるわけではありません__。ただし、その場合は __fail low__ と __fail high__ に __含まれる評価値__ が「評価値の最小値」と「評価値の最大値」の __1 種類しか存在しない__ ため、fail low や fail high の範囲として計算された評価値が __正確なミニマックス値__ となります。
:::

ただし、正確な評価値を計算することができなくても、__fail low__ の場合は「ミニマックス値が __計算された評価値以下__ であること」、__fail high__ の場合は「ミニマックス値が __計算された評価値以上__」であることは __わかります__。

また、__ウィンドウを狭くする__ ことで α 狩りと β 狩りの対象とならない exact value の範囲が減り、__枝狩りが行われやすくなる__ ため、__計算時間が短く__ なるというメリットが生じます。

そこで、$N$ やその子孫ノードの評価値を計算する際に、__正確なミニマックス値を計算する必要がない__ 場合は、__ウィンドウを狭く設定__ することで __計算時間を短くする__ という工夫を行う場合があります。

その際に、__ウィンドウ幅__ を __0 または 0 に近い値に設定__ することで、__枝狩りの効率を高める手法__ のことを __null window search__ と呼びます。なお、一般的には後述する理由から __ウィンドウ幅を 0 としません__ が、__そのような場合でも null window search と呼びます__。

:::note warn
__null window search__ とは __αβ 法__ で __ウィンドウ幅を 0 または 0 に近い値に設定__ してノードの評価値の計算を行うという手法のことである。
:::

従って、__null window search__ の __計算手順__ は __αβ 法と完全に同じ__ です。

# ウィンドウ幅が 0 の null window search

最初に __ウィンドウ幅が 0__ の null window search について説明し、一般的に null window search では __ウィンドウ幅を 0 にしない理由__ について説明します。

:::note
null window search でウィンドウ幅を 0 にしない理由を説明した文章を筆者には見つけられなかったので、__本記事でのウィンドウ幅を 0 にしない理由の説明は筆者が考えたもの__ です。そのため間違っているかもしれません。間違いに気づいた方がいらっしゃればコメントなどで指摘して頂けると助かります。
:::

## ウィンドウ幅が 0 の場合の αβ 法が計算する評価値の意味

__これまでの記事での αβ 法__ では[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%CE%B1-%E5%80%A4%E3%81%A8-%CE%B2-%E5%80%A4%E3%81%AE%E9%96%A2%E4%BF%82%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E8%A3%9C%E8%B6%B3)で説明した理由から、$α < β$、すなわち $α$ と $β$ が等しくなることはないので、__ウィンドウ幅が 0 になることはありませんでした__。

ただし、$N$ の評価値を計算する際に $α$ と $β$ を __わざと等しく設定する場合__ はその限りではありません。これまでの記事の説明では $α < β$ が等しくないという前提で説明を行なってきたので、 __ウィンドウ幅が 0__（$α = β$）__の場合に αβ 法で計算される評価値の性質__ について説明します。

下記は[以前の記事](https://qiita.com/ysgeso/items/c43a1c7dc65b746c8394#%CE%B1%CE%B2-%E6%B3%95%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%AE%E3%81%8A%E3%81%95%E3%82%89%E3%81%84%E3%81%A8%E7%94%A8%E8%AA%9E%E3%81%AE%E4%BF%AE%E6%AD%A3)で説明した、$\boldsymbol{α < β}$ の場合に αβ 法が計算する評価値の意味の再掲です。
$S_N$ はミニマックス法で計算した本当の評価値である ミニマックス値、$S_N'$ は αβ 法で計算した αβ 値を表す記号です。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α$  | $S_N ≦ S'_N$  | ミニマックス値は $S'_N$ 以下<br>ミニマックス値の上界がわかる | fail low | 
| $α < S'_N < β$  | $S_N = S'_N$  | ミニマックス値が求められる | exact value |
| $β ≦ S'_N$  | $S'_N ≦ S_N$   | ミニマックス値は $S'_N$ 以上<br>ミニマックス値の下界がわかる| fail high |

$\boldsymbol{α = β}$ の場合は上記の表の $α < S'_N < β$ __の範囲は存在しない__ ので、上記の表は下記の表のようになり、一見すると exact value の範囲は存在しなくなるように見えるかもしれませんが、__実際には exact value の範囲は存在します__。どのように存在するかについて少し考えてみて下さい。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N ≦ α = β$  | $S_N ≦ S'_N$  | ミニマックス値は $S'_N$ 以下<br>ミニマックス値の上界がわかる | fail low | 
| $α = β ≦ S'_N$  | $S'_N ≦ S_N$   | ミニマックス値は $S'_N$ 以上<br>ミニマックス値の下界がわかる| fail high |

:::note
$α = β$ なので $β$ を $α$ に書き換えることもできますが、書き換えてしまうと $β < S'_N$ が fail high の範囲であることが直観的にわかりづらくなってしまうので書き換えないことにし、代わりに $S'_N < α = β$ のように記述することで $α = β$ であることが明確になるようにしました。
:::

上記の表では $S'_N ≦ α = β$ と $α = β ≦ S'_N$ が別の行に記載されていますが、$α = β$ なので、$\boldsymbol{S'_N = α}$ __の場合は__ $\boldsymbol{S'_N = β}$ __でもある__ ので、$S'_N = α = β$ の場合は $S'_N ≦ α$ と $β ≦ S'_N$ の __両方に含まれます__。そこで、$S'_N = α = β$ __の場合を分ける__ と下記の表のようになります。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:-:|
| $S'_N < α = β$  | $S_N ≦ S'_N$  | ミニマックス値は $S'_N$ 以下<br>ミニマックス値の上界がわかる | fail low | 
| $S'_N = α = β$  | $S_N ≦ S'_N$<br>かつ<br>$S'_N ≦ S_N$ | ミニマックス値は<br>$S'_N$ 以下かつ $S'_N$ 以上 | fail low<br>かつ<br>fail high | 
| $α = β < S'_N$  | $S'_N ≦ S_N$   | ミニマックス値は $S'_N$ 以上<br>ミニマックス値の下界がわかる| fail high |

$S_N ≦ S'_N$ かつ $S'_N ≦ S_N$ という条件は $S_N = S_N'$ を意味します。従って $S'_N = α = β$ の場合は __正確なミニマックス値__ が求められるので __exact value__ となります。下記はそのように上記の表を修正したものです。

| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|:-:|:-:|:--|:--|
| $S'_N < α = β$  | $S_N ≦ S'_N$  | ミニマックス値は $S'_N$ 以下<br>ミニマックス値の上界がわかる | fail low | 
| $S'_N = α = β$  | $S_N = S_N'$ | ミニマックス値は $S'_N$ である | exact value | 
| $α = β < S'_N$  | $S'_N ≦ S_N$   | ミニマックス値は $S'_N$ 以上<br>ミニマックス値の下界がわかる| fail high |

__ウィンドウ幅が 0 の場合__ は $α$ と $β$ が __exact value である__ という点が、ウィンドウ幅が正の場合と __異なります__。 

:::note warn
__ウィンドウ幅が 0__（$α = β$）の場合に αβ 法で評価値を計算する __null window search を行う__ ことで、そのノードの __ミニマックス値の範囲__ が __以下のいずれかである__ ことを計算することができる。

* 計算された評価値以下である（$S'_N < α = β$ の場合）
* 計算された評価値と等しい（$S'_N = α = β$ の場合）
* 計算された評価値以上である（$α = β < S'_N$ の場合）

別の視点からみると、__ウィンドウ幅が 0__ の __null window search__ を行うことで、ノードの __ミニマックス値__ が __特定の値__（設定した $α$（= $β$））__よりも大きい__ か、__等しい__ か、__小さい__ かの __いずれであるかを計算__ することができる。
:::

今回の記事のこの後で紹介する手法では、__ミニマックス値__ が特定の値 __よりも大きい__ か、__等しい__ か、__小さい__ かの __すべての結果を利用__ しますが、__null window search__ を利用した効率化のアルゴリズムの多くは、ミニマックス値が特定の値と等しいかどうかではなく、__特定の値よりも大きい__（または __小さい__）__かどうか__ を __効率よく調べることができる__ という性質を利用します。具体例は次回の記事で紹介します。


## 評価値が 3 種類の場合の null window search の利用例

ウィンドウ幅が 0 の __null window search を利用する具体例__ として、今回の記事では __評価値が 3 種類__ の場合の例を紹介します。具体的には　〇×ゲームで評価値として __-1、0、1 の 3 種類__ のみが計算される、__最短の勝利を目指さない__ 評価値を計算する場合の例です。従って、評価値が -2 ~ 3 の範囲で 3 種類よりも多い、__最短の勝利を目指す__ 評価値を計算する __場合はこの手法は利用できません__。また、これまでの例ではでてきていませんが、__評価値として実数が計算されるような場合でも利用できません__。

なお、後述しますが __この手法__ は本記事で既に紹介済である、最短の勝利を目指さない場合に $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __を評価値の最小値と最大値とする__ という手法と __本質的に同じ__ です。従って、この手法による __枝狩りの効率__ は $α$ と $β$ を評価値の最小値と最大値とする場合と __同じになります__。それにも関わらずこの手法を最初に紹介したのは、行なう処理が直観的にわかりやすいと思ったからです。また、この手法の説明を行う過程で、__一般的にウィンドウ幅を 0 としない理由が確認できる__ という理由もあります。

具体的には $N$ の評価値を αβ 法で計算する際に、$α$ と $β$ の __両方__ を __3 つの評価値の真ん中の値__ である 0 とした __ウィンドウ幅が 0__ の __null window search として計算__ する[^3]と、下記の理由から __必ず正確なミニマックス値を計算__ することができます。

* $N$ の評価値として __-1 が計算__ された場合は __fail low の範囲__ なのでミニマックス値の範囲は __-1 以下__ であることが計算されるが、__-1 以下の評価値は -1 しか存在しない__ ので -1 は __正確なミニマックス値__ である
* 同様の理由で $N$ の評価値として __1 が計算__ された場合も __正確なミニマックス値__ である
* $N$ の評価値として __0 が計算__ された場合は、先程のウィンドウ幅が 0 の場合の説明から __exact value の範囲__ となるので、 __正確なミニマックス値__ である
* 上記から、__全ての場合で正確なミニマックス値を計算__ することができる

### `ai_nws_3score` の定義

上記の方法で評価値を計算する __AI の関数を定義__ する事にします。最初に __置換表を利用しない場合__ の __`ai_nw_3score`__ という関数を定義します。なお、関数の名前の nws は null window search、3score は 3 種類の評価値（score）が計算されるという意味です。

`ai_nw_3score` はこれまでに作成した、__αβ 法__ で最短の勝利を目指さない __3 種類の評価値を計算__ し、$N$ の評価値を計算する際の __$\boldsymbol{α}$ と $\boldsymbol{β}$ を評価値の最小値と最大値__ とする AI である __[`ai_abs3`](https://qiita.com/ysgeso/items/523e03ff877cb033889b#%E3%83%AB%E3%83%BC%E3%83%88%E3%83%8E%E3%83%BC%E3%83%89%E3%81%A7%E6%AD%A3%E3%81%97%E3%81%84%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%8C%E8%A8%88%E7%AE%97%E3%81%95%E3%82%8C%E3%82%8B%E7%90%86%E7%94%B1)__ を下記のプログラムのように修正して定義することにします。具体的には 9 行目で $N$ の評価値を計算する際の $α$ と $β$ を __共に 0 に修正__ して __ウィンドウ幅を 0 とします__。

```python
 1  from ai import ai_by_score, dprint
 2  from marubatsu import Marubatsu
 3  from copy import deepcopy
 4  
 5  @ai_by_score
 6  def ai_nws_3score(mb, debug=False):   
 7      count = 0
 8      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 9      score = ab_search(mb, 0, 0)
10      dprint(debug, "count =", count)
11      if mb.turn == Marubatsu.CIRCLE:
12          score *= -1
13      return score
```

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

```python
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
def ai_nws_3score(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        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, alpha, beta))
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return score
                
    score = ab_search(mb, 0, 0)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
-def ai_abs3(mb, debug=False):   
+def ai_nws_3score(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
-   score = ab_search(mb, -1, 1)
+   score = ab_search(mb, 0, 0)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

:::note
$α = β$ なので上記のプログラムの `beta` を削除して `alpha` に置き換えることもできますが、修正を間違えて __バグが発生する可能性がある__ 点と、__修正しなくてもプログラムは正しく動作する__ 点からそのような修正は行わないことにします。
:::

上記を定義後に下記のプログラムで __`ai_nw_3score`__ が __強解決の AI であるか__ どうかを確認すると、実行結果のように __強解決の AI ではない__ という表示が行なわれます。従って、`ai_nw_3score` には __バグが存在する__ ということがわかります。どこが間違っているかについて少し考えてみて下さい。

```python
from util import Check_solved

result, _ = Check_solved.is_strongly_solved(ai_nws_3score)
print(result)
```

実行結果

```
100%|██████████| 431/431 [00:00<00:00, 437.23it/s]
343/431 79.58%
False
```

### バグの原因の考察と修正

このバグの原因は、__ウィンドウ幅が 0 の場合__ と __そうでない場合__ で __α 狩りと β 狩りが行なわれる条件が異なるから__ です。

先程説明したように __ウィンドウ幅を 0 とした場合__ の αβ 法では、そうでない場合と比べて __fail low__、__exact value__、__fail high の範囲__ が以下の表のように __異なります__。

|ウィンドウ幅|fail low|exact value|fail high|
|:--|:--|:--|:--|
| __0__ | $S_N' < α = β$ | $S_N' = α = β$ | $α = β < S_N'$ |
| __正の値__ | $S_N' ≦ α$ | $α < S_N' < β$ | $β ≦ S_N'$ |

上記の表のように、__ウィンドウ幅が 0 の場合__ は $α$（= $β$）は __exact value__ ですが、ウィンドウ幅が __0 でない場合__ は $α$ と $β$ は __exact value ではありません__。

__max ノード__ で __β 狩りが行なわれる条件__ は子ノードの評価値が __fail high の範囲となる__ ことですが、その __条件は下記の表のように異なる__ ので、その部分のプログラムを $\boldsymbol{β < S_N'}$ __を計算する条件式で判定するように修正する__ 必要があります。

|ウィンドウ幅|fail high|
|:--|:--|
| __0__ | $β < S_N'$ |
| __正の値__ | $β ≦ S_N'$ |

同様に __min ノード__ で __α 狩りが行なわれる条件式__ も $S_N' ≦ α$ から $\boldsymbol{S_N' < α}$ __を計算する式に修正する必要__ があります。

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

* __11 行目__：max ノードで β 狩りが行なわれる条件式を `score >= beta` から `score > beta` に修正した
* __21 行目__：min ノードで α 狩りが行なわれる条件式を `score <= alpha` から `score < alpha` に修正した

```python
 1  @ai_by_score
 2  def ai_nws_3score(mb, debug=False):
 3      count = 0
 4      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              score = float("-inf")
 7              for x, y in legal_moves:
 8                  mb = deepcopy(mborig)
 9                  mb.move(x, y)
10                  score = max(score, ab_search(mb, alpha, beta))
11                  if score > beta:
12                      return score
13                  alpha = max(alpha, score)
14              return score
15          else:
16              score = float("inf")
17              for x, y in legal_moves:
18                  mb = deepcopy(mborig)
19                  mb.move(x, y)
20                  score = min(score, ab_search(mb, alpha, beta))
21                  if score < alpha:
22                      return score
23                  beta = min(beta, score)   
24              return score
元と同じなので省略
```

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

```python
@ai_by_score
def ai_nws_3score(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        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, alpha, beta))
                if score > beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
                if score < alpha:
                    return score
                beta = min(beta, score)   
            return score
                
    score = ab_search(mb, 0, 0)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
@ai_by_score
def ai_nws_3score(mb, debug=False):
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        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, alpha, beta))
-               if score >= beta:
+               if score > beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
-               if score <= alpha:
+               if score < alpha:
                    return score
                beta = min(beta, score)   
            return score
元と同じなので省略
```
</details>

上記を修正後に下記のプログラムで __`ai_nw_3score`__ が __強解決の AI であることを確認__ することができます。

```python
result, _ = Check_solved.is_strongly_solved(ai_nws_3score)
print(result)
```

実行結果

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

このように、__ウィンドウ幅を 0 にした場合とそうでない場合__ では、αβ 法の __α 狩りと β 狩りに関する処理を変更する必要__ があります。これが __ウィンドウ幅を 0 とした null window search__ が __一般的に利用されない理由の一つ__ だと思いますが、__この後で説明する理由の方が重要__ だと思います。

## 枝狩りの効率の比較

次に、__ウィンドウ幅を 0__ にすることで __枝狩りの効率がどのように変化したか__ を __`ai_abs3`__ と __`ai_nws_3score`__ で __ゲーム開始時の局面__ の評価値を計算した際に __計算されるノードの数を表示__ する下記のプログラムで比較することにします。

```python
from ai import ai_abs3

mb = Marubatsu()
ai_abs3(mb, calc_score=True, debug=True)
ai_nws_3score(mb, calc_score=True, debug=True)
```

実行結果

```
count = 16811
count = 94978
```

実行結果から、__ウィンドウ幅を 0__ とした場合のほうが __計算したノードの数が約 6 倍も多く__、__効率が悪くなっている__ ことが確認できました。ウィンドウ幅が小さいほうが枝狩りの効率が高くなるはずなのに、逆に効率が悪くなっている点に驚いた人がいるかもしれませんが、これには理由があります。何故このようなことが起きるかについて少し考えてみて下さい。

## 枝狩りの効率が悪くなる理由

枝狩りの効率が悪くなる理由は、__ウィンドウ幅を 0とした場合__（$α = β$）に子ノードの評価値として $\boldsymbol{α}$（= $β$） __が計算された場合__ は __必ず exact value__ とみなされるため __枝狩りが行なわれない__ からです。

また、__ウィンドウ幅を 0__ とした場合は、下記の理由から $N$ の __全ての子孫ノード__ の評価値を計算する際の $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ が __$\boldsymbol{N}$ の $\boldsymbol{α}$ と $\boldsymbol{β}$ と同じ値__ になります。なお、表記が紛らわしいですが 「$\boldsymbol{α}$」 はそのノードの評価値を計算する際の __α 値の初期値__、「__α 値__」は子ノードの評価値を計算する際に受け継ぐ __その時点での α 値__ のことを表します。

* 子ノードの評価値を計算する際の $α$ と $β$ は __親ノードの α 値と β 値を受け継ぐ__
* __max ノード__ では、子ノードに受け継ぐ __α 値と β 値__ は __以下のように計算__ される
    * __α 値__ は max ノードではそれまでに計算した __子ノードの評価値__ と $\boldsymbol{α}$ のうちの __最大値__ である
    * ただし、__子ノードの評価値__ が $\boldsymbol{β}$（= $α$）__を超えた場合__ は __β 狩りが行われる__
    * 従って __max ノード__ で子ノードに受け継ぐ __α 値は常に__ $\boldsymbol{α}$ __となる__
    * __β 値__ は $β$ のまま __変化しない__
* 同様の理由で __min ノード__ でも子ノードに受けつぐ __α 値と β 値は常に__ $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __となる__

従って、$N$ に限らず、$N$ __の全ての子孫ノード__ で $α$（= $β$）が計算された場合に __枝狩りが行われなくなります__。先程の例の場合は $N$ とその子孫ノードの評価値を計算する際に __常に__ $\boldsymbol{α = β = 0}$ __となる__ ので、どのノードであっても __子ノードの評価値として 0 が計算__ された場合に __枝狩りが行われることはありません__.

一方で $α = -1$、$β = 1$ としてノード $N$ の評価値を計算する場合は、__ウィンドウ幅が正の値__（$β - α >  0$）なので $N$ の __子孫ノード__ の評価値を計算する際の __ウィンドウ幅も正の値__ となります。そのため、$N$ の max ノードの子孫ノードの $\boldsymbol{β}$ __が 0 となった場合__ に子ノードの評価値として __0 が計算__ されると __β 狩りが行われます__。min ノードの場合も同様です。

上記をまとめると以下のようになります。これが __null window search__ で __ウィンドウ幅を 0 にしない最も大きな理由__ だと思います。

:::note warn
__ウィンドウ幅を 0 とした場合__ は、$\boldsymbol{α}$（= $β$）__が exact value の範囲となってしまう__ ため、子ノードの評価値として $α$（= $β$） が計算された場合に __α 狩りまたは β 狩りが行なわれなくなる__。そのため、その分だけ __枝狩りの効率が悪くなってしまう__。
:::

:::note
評価値として $α$（= $β$）が計算されることがない場合はノードの評価値が exact value として計算されることはないので、ウィンドウ幅を 0 にしても枝狩りの効率が悪くなることはありません。例えば評価値として -1、0、1 が計算される場合に $α = β = 0.5$ として計算を行う場合などです。

ただし、null window search を利用した多くのアルゴリズムでは $α$ や $β$ に実際に評価値として計算される値を設定する（具体例については次回の記事で説明します）ので、ウィンドウ幅を 0 とすることはほとんどないでしょう。
:::

# ウィンドウ幅が正の null window search

上記で説明したように __ウィンドウ幅を 0__ としてしまうと __枝狩りの効率が悪くなります__ が、逆に言えば __ウィンドウ幅が 0 でなければそのような問題は発生しません__。また、ウィンドウ幅が __正の値の場合__ はウィンドウ幅が __狭い程__ 枝狩りが行われない __exact value の範囲が狭くなる__ ため __枝狩りが行われやすくなります__。そのため __null window search__ で __枝狩りの効率を上げる__ ためには __ウィンドウ幅を出来るだけ小さな正の値__ として設定する必要があります。

ただし、残念ながら __0 に最も近い正の値を求めることはできません__。例えば $n$ という値が 0 に最も近い正の値であるとした場合は、$n / 2$ という $n$ よりも __さらに 0 に近い正の値が存在__ してしまうので __矛盾してしまう__ からです。そのため、null window search を行う際のウィンドウ幅として __常に採用できる最適な値は存在しません__。

null window search では __一般的にウィンドウ幅を 1 と設定することが多い__ ようです。Wikipedia の null window search の説明でもそのように記載されていますが、その理由については記述されていません。__ウィンドウ幅を 1 とする具体的な理由についての説明が見つけられなかった__ ので、その理由について後で __筆者なりに考察した内容を説明することにします__。

https://ja.wikipedia.org/wiki/MTD-f#Null_Window_Search

## ウィンドウの設定方法

上記では __一般的にウィンドウ幅を 1 と設定することが多い__ と説明しましたが、__1 でなければならないという理由はありません__。また、ウィンドウ幅を出来るだけ小さな正の値として設定する必要があると説明しましたが、実際には __枝狩りの効率が最も高くなるような値以下__ であれば、__ウィンドウ幅にどのような値を設定しても枝狩りの効率は変わりません__。

そこで null window search で __ウィンドウをどのように設定するべきか__ について説明します。

### ウィンドウの設定方法の考え方

null window search では、__ウィンドウ（枝狩りが行なわれない exact value の範囲）を狭くする__ ことで、__枝狩りの効率を上げることが重要__ です。従って、__ウィンドウの中__ には、__正確なミニマックス値を計算したい評価値の値のみを含む範囲とする__ ことが __最も枝狩りの効率が高く__ なります。

具体例として、先程紹介した __評価値__ が -1、0、1 の __3 種類しかない場合__ の null window search の利用例でのウィンドウの設定方法の考え方について説明します。次回の記事では別の場合での考え方について説明します。

ウィンドウ幅が正の null window search は、__ウィンドウの範囲をできるだけ小さく設定した αβ 法__ なので、__ミニマックス値が以下のいずれかであることを判定__ することができます。

* $α$ 以上である
* $α$ と $β$ の間（$α$ と $β$ は含まない）である。この場合は正確なミニマックス値が求められる
* $β$ 以下である

先程紹介した利用例は、__3 種類の評価値__ が上記の __3 種類の範囲の中__ にそれぞれ __1 つずつ含まれるようにする__ ことで、正確なミニマックス値を計算するという手法です。

そのため、ウィンドウは __必ずその目的を満たすことができるような範囲として設定__ する必要があります。具体的には __以下の条件を満たす必要__ があります。

* -1 のみが fail low の範囲に含まれる
* 0 のみが exact value の範囲に含まれる
* 1 のみが fail high の範囲に含まれる

この条件を満たすための $α$ と $β$ は以下のいずれかになります。

* $α = β = 0$
* $-1 ≦ α < 0 < β ≦ 1$

前者は先程説明したウィンドウ幅が 0 の場合で、__後者はウィンドウ幅が__ $\boldsymbol{β - α}$ という __正の値__ になります。前者は効率が悪いことを先程示したので、__後者の条件を満たす__ $\boldsymbol{α}$ __と__ $\boldsymbol{β}$ __を決めることでウィンドウが決まります__。

### `ai_nws_3score2` の定義

$\boldsymbol{α}$ __と__ $\boldsymbol{β}$ は $-1 ≦ α < 0 < β ≦ 1$ を __満たしていればどのような値でもかまいません__。先程 null window search ではウィンドウ幅を 1 と設定することが多いと説明しましたので、__上記の条件を満たす__ $α = -0.5$、$β = 0.5$ とした __ウィンドウ幅を 1 とする null window search__ で計算を行う __`ai_nws_3score2`__ を下記のプログラムのように定義することにします。

* __2 行目__：関数の名前を `ai_nws_3score2` に修正する
* __11、21 行目__：ウィンドウ幅が 0 ではなくなったので、α 狩りと β 狩りを行う条件式を元に戻す
* __26 行目__：$N$ の評価値を計算する際の $α$ と $β$ を -0.5 と 0.5 に修正する

```python
 1  @ai_by_score
 2  def ai_nws_3score2(mb, debug=False):   
 3      count = 0
 4      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              score = float("-inf")
 7              for x, y in legal_moves:
 8                  mb = deepcopy(mborig)
 9                  mb.move(x, y)
10                  score = max(score, ab_search(mb, alpha, beta))
11                  if score >= beta:
12                      return score
13                  alpha = max(alpha, score)
14              return score
15          else:
16              score = float("inf")
17              for x, y in legal_moves:
18                  mb = deepcopy(mborig)
19                  mb.move(x, y)
20                  score = min(score, ab_search(mb, alpha, beta))
21                  if score <= alpha:
22                      return score
23                  beta = min(beta, score)   
24              return score
25                  
26      score = ab_search(mb, -0.5, 0.5)
27      dprint(debug, "count =", count)
28      if mb.turn == Marubatsu.CIRCLE:
29          score *= -1
30      return score
```

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

```python
@ai_by_score
def ai_nws_3score2(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        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, alpha, beta))
                if score >= beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
                if score <= alpha:
                    return score
                beta = min(beta, score)   
            return score
                
    score = ab_search(mb, -0.5, 0.5)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

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

```diff_python
@ai_by_score
-def ai_nws_3score(mb, debug=False):   
+def ai_nws_3score2(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        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, alpha, beta))
-               if score > beta:
+               if score >= beta:
                    return score
                alpha = max(alpha, score)
            return score
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, alpha, beta))
-               if score < alpha:
+               if score <= alpha:
                    return score
                beta = min(beta, score)   
            return score
                
-   score = ab_search(mb, 0, 0)
+   score = ab_search(mb, -0.5, 0.5)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

上記の定義後に下記のプログラムで __`ai_nw_3score2` が強解決の AI である__ ことを確認することができます。

```python
result, _ = Check_solved.is_strongly_solved(ai_nws_3score2)
print(result)
```

実行結果

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

### 枝狩りの効率の確認

下記のプログラムで __ゲーム開始時の局面__ の評価値を計算する際に __計算されたノードの数__ を表示すると、先程の __`ai_abs3` と同じ 16811__ が表示されます。これは、__`ai_abs3` と `ai_nws_3score2` の枝狩りの効率が同じ__ であること表しますが、何故同じになるかについて少し考えてみて下さい。

```python
ai_nws_3score2(mb, calc_score=True, debug=True)
```

実行結果

```
count = 16811
```

先程説明したように、-1、0、1 の 3 種類の評価値が計算される場合に、null window search のウィンドウの範囲を以下のいずれかに設定する必要があります。

* $α = β = 0$
* $-1 ≦ α < 0 < β ≦ 1$

__`ai_abs3`__ では $α = -1$、$β = 1$ として $N$ の評価値を計算しますが、これは __上記の 2 つ目の条件を満たしています__。つまり、__`ai_abs3`__ と __`ai_nws_3score2`__ はウィンドウの範囲やウィンドウ幅は異なりますが、行なっている処理は __全く同じ意味の null window search を行なっている__ ということです。従って、枝狩りの効率が同じであることは当然です。

:::note warn
__`ai_abs3`__ と __`ai_nws_3score2`__ はウィンドウの範囲やウィンドウ幅は異なるが、__全く同じ意味の null window search を利用した処理__ を行っている。
:::

## null window search の条件

上記のような、__ウィンドウ幅が 0 でない場合__ の処理を null window search と呼ぶのに __違和感がある__ 人がいるかもしれません。また、ここまでの説明では、__null window search と呼ぶためのウィンドウ幅の条件がはっきりしません__。そこで、筆者なりに考えた __null window search と呼ばれるための条件を説明__ します。この解釈は間違っているかもしれないので、間違っている場合はコメントなどで指摘していただければ助かります。

__null window search と呼んで良い条件__ は、__ウィンドウ幅を実際に 0 として計算しても良い場合__ だと思います。例えば上記の場合は $α = β = 0$ として __ウィンドウ幅 が 0__ の αβ 法で計算を行なっても枝狩りの効率は悪くなりますが __正しい計算を行うことができます__。

一方、__最短の勝利を目指す場合__ は評価値の範囲が -2 ~ 3 の整数で評価値の種類が 6 種類となりますが、その際に $α$ と $β$ を負の無限大と正の無限大ではなく、評価値の最小値と最大値である __-2 と 3 に設定__ してウィンドウ幅を狭くするという工夫は __null window search と呼ぶことはできない__ と思います。その理由は、この場合は fail low と fail high の範囲に取りうる評価値が 1 つしかないことを利用しているため、$-2 ≦ α < -1$、$2 < β ≦ 3$ という条件が必要となるため、$β - α > 2 - (-1) = 3$ となるため __ウィンドウ幅を 0 とすることができないから__ です。

:::note
ウィンドウ幅を 0 とすることはできませんが、ウィンドウの範囲から -2 と 3 という評価値を取り除いて __ウィンドウ幅を狭めることで枝狩りの効率を高めている__ という点では、最短の勝利を目指さない場合と __同様の工夫を行なっています__。
:::

## ウィンドウ幅に 1 が一般的に設定される理由の推察

筆者が調べた範囲では __null window search でウィンドウ幅に 1 が一般的に設定される理由__ はおそらく以下のようなものだと考えられます。正しい理由をご存じの方がいればコメントなどで教えて頂ければ助かります。

### 初期の論文のウィンドウ幅が 1 となっている

null window search に関する初期の論文[(An optimization of alpha-beta search, SIGART Bulletin, Issue 72)](https://dl.acm.org/doi/10.1145/1056447.1056450)でウィンドウ幅 を 1 とした例が紹介されているので、もしかするとそれが踏襲されているのかもしれません。

### 整数を評価値として計算する場合はウィンドウ幅として 1 が適している

先程紹介した [null window の Chess programing の wiki](https://www.chessprogramming.org/Null_Window) には理由は説明されていませんが、下記のように __評価値が整数__（integer）の場合は $α = β - 1$、すなわち __ウィンドウ幅を 1__ とすると説明されています。

With integers a null-window is defined as alpha == beta - 1. 

これは、__評価値として整数のみが計算される場合__ は __ウィンドウ幅を 1__ とし、__ウィンドウの境目__ である $α$ と $β$ を __整数に設定する__ ことで __ウィンドウの範囲内に取りうる評価値が 1 つも含まれない__ ようにすることができるからだと思います。

例えば __ウィンドウ幅を 1__ とし $α$ と $β$ を __0 と 1 のような整数として設定__ した場合は、__exact value の範囲__ は $0 < S_N' <1 $ となるので __整数である評価値が一つも含まれなくなります__。

今回の記事で紹介した `ai_nws_score2` ではそうなっていませんが、__null window search__ を利用した __アルゴリズムの多く__ は、__ウィンドウの範囲内__ に __正確に計算したい評価値を含む必要がありません__。従って、__評価値として整数のみが計算__ される場合は、__ウィンドウの境目を整数__ とし、__ウィンドウ幅を 1__  にすることが多くの場合で __適していると言える__ でしょう。

### 評価値が実数になる場合の null window search のウィンドウ幅

__評価値として実数（整数以外の値）が計算される場合__ は、ウィンドウ幅を __1 よりも狭くしたほうが枝狩りの効率が良くなる__ 可能性が生じます。null window search を行う際の __ウィンドウを設定する際__ には、何も考えずにウィンドウ幅を 1 とするのではなく、__ウィンドウの範囲内__ にある、__正確な値を計算する必要がない__ 評価値が __計算される確率が充分に小さくなるような範囲を設定__ したほうが良いでしょう。

## 置換表つき αβ 法の場合

__置換表付き αβ 法__ でも __`ai_nws_3score2` と同様の方法__ で __null window search__ を利用することができます。そのような計算を行う __`ai_nws_3score_tt`__ は、置換表付き αβ 法の処理を行う __`ai_abs_tt4`__ を下記のプログラムのように修正することで定義できます。

なお、__`ai_abs_tt4`__ は仮引数 __`shortest_victory`__ によって __最短の勝利を目指す評価値を計算する機能を持ちます__ が、最短の勝利を目指す場合の評価値は __3 種類ではない__ ので、__`ai_nws_3score_tt`__ では __`shortest_victory` に関する処理は削除__ しました。また、$-1 ≦ α < 0 < β ≦ 1$ の条件が満たされていれば、__他のウィンドウ幅でも構わない__ ことを示すために、$α = -0.05$、$β = 0.05$ としてウィンドウ幅を 0.1 にしました。

* __2 行目__：関数の名前を `ai_nws_3score` に修正した
* __2、8、10、13、14 行目__：`shortest_victory` に関する処理を削除した
* __16 行目__：ルートノードの評価値を計算する際の α 値と β 値の初期値を -0.05 と 0.05 に修正する

```python
 1  @ai_by_score
 2  def ai_nws_3score_tt(mb, debug=False):
 3      count = 0
 4      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
 5          nonlocal count
 6          count += 1
 7          if mborig.status == Marubatsu.CIRCLE:
 8              return 1
 9          elif mborig.status == Marubatsu.CROSS:
10              return -1
11          elif mborig.status == Marubatsu.DRAW:
12              return 0
元と同じなので省略
13      min_score = -1
14      max_score = 1
15  
16      score = ab_search(mb, {}, alpha=-0.5, beta=0.5)
17      dprint(debug, "count =", count)
18      if mb.turn == Marubatsu.CIRCLE:
19          score *= -1
20      return score
```

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

```python
@ai_by_score
def ai_nws_3score_tt(mb, debug=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
            return 1
        elif mborig.status == Marubatsu.CROSS:
            return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        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, 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

        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 = -1
    max_score = 1

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

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

```diff_python
@ai_by_score
def ai_nws_3score_tt(mb, debug=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
+           return 1
        elif mborig.status == Marubatsu.CROSS:
-           return (mborig.move_count - 10) / 2 if shortest_victory else -1
+           return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
元と同じなので省略
-   min_score = -2 if shortest_victory else -1
+   min_score = -1
-   max_score = 3 if shortest_victory else 1
+   max_score = 1

-   score = ab_search(mb, {}, alpha=min_score, beta=max_score)
+   score = ab_search(mb, {}, alpha=-0.05, beta=0.05)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

:::note
`ai_nws_3score_tt` では、全てのノードで正確なミニマックス値を計算することができるので、置換表にミニマックス値の下界と上界を分けて記録する必要はありません。ただし、置換表にミニマックス値だけを記録るように修正しなくてもプログラムは正しく動作するのでそのような修正は行わないことにします。
:::

上記の定義後に下記のプログラムで __`ai_nw_3score_tt` が強解決の AI である__ ことを確認することができます。

```python
result, _ = Check_solved.is_strongly_solved(ai_nws_3score_tt)
print(result)
```

実行結果

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

下記のプログラムで __ゲーム開始時の局面__ の評価値を計算する際に __計算したノードの数__ を __`ai_abs_tt4`__ と __`ai_abs_3score_tt`__ で計算すると、__どちらも同じ計算結果が表示される__ ことが確認できます。これは先程説明したように __`ai_abs_tt4`__ のウィンドウである $α = -1$、$β = 1$ と、__`ai_abs_3score_tt`__ のウィンドウである $α = -0.05$、$β = 0.05$ が __実質的に同じ計算を行なっている__ からです。

```python
from ai import ai_abs_tt4

ai_abs_tt4(mb, calc_score=True, debug=True)
ai_nws_3score_tt(mb, calc_score=True, debug=True)
```

実行結果

```
count = 832
count = 832
```

# 今回の記事のまとめ

今回の記事では __null window search__ について説明し、null window search で __一般的にウィンドウ幅を 0 としない理由__ について説明しました。また、null window search の __利用例の一つ__ を説明し、その方法が __既に紹介していた方法と実質的に同じ__ であることを説明しました。

次回の記事では null window search によって枝狩りの効率を向上させる手法について説明します。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/97c293d8876190849ec8

[^1]:リンク先の記事が置換表付き αβ 法の説明ですが、その記事ではまだ「置換表付き αβ 法」とは表記していませんでした。置換表付き αβ 法と表記し始めたのはその次の記事からです
[^2]:ウィンドウの範囲に $α$ と $β$ は含まれません
[^3]:$α$ と $β$ を 0 としたことが null window search の条件ではない点に注意して下さい。$α$ と $β$ を __同じ値にする__ ことで __ウィンドウ幅を 0 とした__ ことが null window search の条件です