Pythonで〇×ゲームのAIを一から作成する　その171　その他の αβ 法の効率を改善するアルゴリズムと αβ 法の最大効率の証明

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/3cb0369dc4b3014e1e13

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

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

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

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

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

# その他の αβ 法の効率を改善するアルゴリズム

これまでに __αβ 法の効率を改善__ するアルゴリズムとして __[null window search](https://qiita.com/ysgeso/items/7fe6c130a6fcf34260dc)__ を利用した __[スカウト法](https://qiita.com/ysgeso/items/da45166e2bb5ac75e67e)__ と __[MTD(f) 法](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4)__ を紹介しました。今回の記事では他の αβ 法の効率を改善するためのアルゴリズムをいくつか紹介します。ただし、それらのアルゴリズムの実装は行わないので、興味がある方は実際に実装してみて下さい。

また、他にも様々なアルゴリズムが考案されているので興味がある方は調べてみて下さい。参考までに Chess Programming wiki の αβ 法の記事のリンクを下記に紹介します。

https://www.chessprogramming.org/Alpha-Beta

また、1999 年に発表された論文なのでかなり古いですが、ゲーム木の探索のトレンドをまとめた論文のリンクを下記に紹介します。下記の論文で行なわれた検証では MTD(f) 法はスカウト法よりも 1 ~ 15 % 程効率が高かったそうです。

https://www.researchgate.net/publication/2643632_Trends_in_Game_Tree_Search

## SSS* と Dual*

__SSS*__[^1]と __Dual*__[^2] は __MTD(f) 法より前に考案__ されたアルゴリズムですが、アルゴリズムが複雑で理解しづらい点と、枝狩りの効率化を行うために必要となる処理の効率があまり高くなく、__総合的に見るとあまり効率が良くない__ 点から、__MTD(f) として作り直された__ ようです[^3]。正直に言うと、筆者もこれらのアルゴリズムについてはちゃんと理解していません。参考までに Chess Programming wiki の該当する記事のリンクを下記に紹介します。

https://www.chessprogramming.org/SSS*_and_Dual%2A

## MTD(∞) 法

[以前の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E7%89%B9%E5%BE%B4)で説明したように、MTD(f) 法の __MTD__ は Memory-enhanced Test Driver の略で、ミニマックス値が指定した値よりも __大きいかどうかのテスト__（判定）の処理の効率を __置換表を利用__ して高めた __アルゴリズムのこと__ を表します。従って、__MTD(f) 法以外__ の __MTD に分類される__ アルゴリズムがあります。

MTD(∞) 法は MTD(f) 法と似ていますが、__ミニマックス値を推定せず__ に __最初に常に `f` を正の無限大として計算__ する手法です。null window search を行うたびに `f` が ∞ からミニマックス値に向かって減っていくことでミニマックス値が求められますが、__null window search の回数__ が MTD(f) 法と比べて __多くなる可能性が高い__ ため、精度の高いミニマックス値を推定することができる場合は MTD(f) 法の方が効率が高くなります。そのためこのアルゴリズムが実際に使われることはほとんどないと思います。

:::note
同様に最初の`f` を常に負の無限大や 0 としてミニマックス値を計算すると、おそらく MTD(―∞) 法や MTD(0) 法となるのではないかと思います。
:::

## C* と Nega C*

C* は __二分法__ でミニマックス値を __効率よく計算__ するアルゴリズムです。Nega C* は C* と同様ですが min ノードの評価値の正負を反転させることで処理をまとめたアルゴリズムです。 

参考までに Chess Programming wiki の該当する記事のリンクを下記に紹介します。

https://www.chessprogramming.org/NegaC%2A

### 二分法とは何か

__二分法__（bisection method）は __何かを探索__ する際に、「__全体を半分にわけて__ その __どちらに__ 探索したいものが __含まれているかを探す__」という処理を __繰り返す__ というアルゴリズムです。探索したいものが __2 つの集合のどちらに含まれているかを効率よく判定できる場合__ に、__効率が良い探索のアルゴリズム__ として様々な場面で __実際に良く使われます__。

具体的な使用例としては、二分法で __辞書から単語を探す__ のがわかりやすいでしょう。辞書は __単語が__ アルファベット順やあいうえお順などの __順番の並べられている__ ので、特定のページを開いた時に __調べたい単語がそのページよりも前にあるか__ どうかを __効率よく判定__ することができます。辞書から単語を二分法で探索する具体的なアルゴリズムは以下の通りです。

1. 辞書のちょうど __真ん中のページを開く__。二分法の __名前__ は、この作業によって辞書のページが __同じページ数__ の __2 つの集合に二分される__ ことが __由来である__
2. 開いたページの __先頭の単語を見る__ ことで、調べたい単語が __開いたページより前にあるかどうか__ を判定し、調べたい単語が __含まれていないほう__ を __検索の対象から取り除く__。この作業によって検索の対象となる __ページの数が半分__ になる
3. 辞書のページが __1 ページになるまで手順 1、2 を繰り返し__、1 ページになったら __そのページから単語を探す__

二分法では、手順 1、2 の処理を行うたびに __探索範囲を半分にする__ ことができるので、$\boldsymbol{n}$ __回の探索__ を行うことで __探索範囲__ を $\boldsymbol{2^n}$ __分の 1 に減らす__ ことができます。たとえば $\boldsymbol{2^{10} = 1024}$ なので、手順 1、2 の処理を __10 回行う__ ことで __1000 ページの辞書__ の中から __必ず目的の単語が入ったページを検索__ することができます。$\boldsymbol{2^{20} = 約 100 万}$ なので、二分法を使えば __たった 20 回以下__ の手順 1、2 の処理で __100 万ページ__ の辞書の中から単語を検索することができます。このように二分法は効率が良いので実際に良く使われます。

:::note
探索したいものが 2 つの集合のどちらに含まれているかを __効率よく判定できない場合__ は __二分法を利用することはできません__。例えば本の中から特定の単語を探すには、索引などのヒントがなければ最初のページから順番に探すしかないでしょう。

一般的に、二分法行うためには、辞書のように単語を順番に並べ替える（ソート）などの、事前の作業を行う必要があります。コンピューターでは、ソート済みのデータに対して二分法を利用した探索のアルゴリズムの事を __二分探索__ と呼びます。ソート済のデータを作成する際に __二分木__ という __木構造のデータ__ が良く使われます。

参考までに二分法、二分探索、二分木の Wikipedia のリンクを下記に紹介します。
:::

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%B3%95

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8

### C* のアルゴリズム

__null window search__ を利用することで __ミニマックス値が特定の値以上であるか__ どうかを __効率よく判定__ することができます。C* は null window search を利用することで __二分法による探索__ を行うことができます。

:::note
null window search は確かに効率が良いのですが、先程の辞書の例ほど効率よくミニマックス値が特定の値以上であるかどうかを判定することはできないので null window search を一定以上の回数行うと、通常のウィンドウ幅の αβ 法で αβ 値を計算するよりも効率が悪くなります。そのため C* の効率が常に αβ 法よりも良くなるとは限りません。ミニマックス値の推定の精度が悪い場合に MTD(f) 法の効率が αβ 法より悪くなる場合があるのも同様の理由です。
:::

__C* のアルゴリズム__ は以下の通りです。なお、__無限大が含まれた数値の平均__ を __計算することはできない__ ので、C* では最初の __ミニマックス値の範囲の下界と上界__ を無限大ではない、__有限の値に設定する必要__ があります。

1. __ミニマックス値の下界と上界__ を、__ミニマックス値の範囲を含む__ 何らかの __有限の値に設定する__
2. __下界と上界が等しくなるまで__ 下記の処理を __繰り返す__
    1. $\boldsymbol{α}$ __= (下界 + 上界) / 2__ を計算し、($\boldsymbol{α}$, $\boldsymbol{α + 1}$) を __ウィンドウ__ とする __null window search で αβ 値を計算__ する。ただし、$α$ が整数でない場合は切り捨てるものとする
    2. __αβ 値__ $\boldsymbol{> α}$ の場合は fail high なのでミニマックス値は __αβ 値 以上__ である。従って __下界を αβ 値 で更新__ する。__そうでなければ__ fail low なのでミニマックス値は __αβ 値以下__ である。従って __上界を αβ 値 で更新__ する

:::note
MTD という名前はついていませんが、C* は MTD(f) 法と同様に同じノードに対して null window search を複数回行うので、__置換表を利用したほうが良い__ でしょう。
:::

:::note
C* のアルゴリズムは __厳密には二分法ではありません__。その理由は __null window search__ ではミニマックス値が特定の値以上であるか __以上の厳密な判定__ を行うことができ、__C* ではその性質を利用しているから__ です。

具体的には ($\boldsymbol{α}$, $\boldsymbol{α + 1}$) というウィンドウで null window search を行なった結果、αβ 値として $\boldsymbol{α}$ __未満の値が計算__ された場合は、ミニマックス値の範囲として $\boldsymbol{α}$ __以下よりも厳密__ な __αβ 値以下である__ ことが判定できます。同様に αβ 値として $\boldsymbol{α+1}$ __より大きな値が計算__ された場合は、ミニマックス値の範囲として $\boldsymbol{α+1}$ __以上よりも厳密__ な __αβ 値以上である__ ことが判定できます。

下記は __厳密な二分法__ で計算するように C* のアルゴリズムを修正したものです。修正した部分を太字にしました。

1. ミニマックス値の下界と上界を、ミニマックス値の範囲を含むような何らかの有限の値に設定する
2. 下界と上界が等しくなるまで下記の処理を繰り返す
    1. $α$ = (下界 + 上界) / 2 を計算し、($α$, $α + 1$) を ウィンドウとする null window search で αβ 値を計算する。ただし、$α$ が整数でない場合は切り捨てるものとする
    2. αβ 値 > $α$ の場合は fail high なのでミニマックス値は $\boldsymbol{α + 1}$ __以上__ である。従って、下界を $\boldsymbol{α + 1}$ で更新する。そうでなければ fail low なのでミニマックス値は $\boldsymbol{α}$ __以下__ である。従って、上界を $\boldsymbol{α}$ で更新する

__C*__ で更新される __ミニマックス値の範囲__ は、__αβ 値__ が $\boldsymbol{α}$ または $\boldsymbol{α + 1}$ __の場合__ は __二分法と変わりません__ が、__それ以外の場合__ は二分法よりも __狭くなります__。従って、__C* は二分法以上の効率__ で計算を行うことができます。
:::

### C* と MTD(f) 法の効率の比較

__C* のアルゴリズム__ は MTD(f) 法と同様に、__ミニマックス値の範囲__ を null window search の結果によって __狭めていく__ というものです。__C*__ が二分法を使って null window search のたびに __ミニマックス値の範囲を半分以下に減らす__ のに対し、__MTD(f) 法__ は null window search のたびに __`f` と新しく計算した αβ 値の差だけしか__ ミニマックス値の __範囲が減りません__。そのため一見すると C* の方が MTD(f) 法よりも効率が高いように思えるかもしれませんが、__精度の高いミニマックス値を推定できる場合__ は __MTD(f) のほうが効率が高くなる傾向__ があります。

このことをわかりやすく説明するために、具体例として __ミニマックス値の範囲の初期値__ を __[-1000, 1000]__、__ミニマックス値を `30`__ とした場合に C* と MTD(f) 法で行なわれる計算を比較します。

まず、__C* で行なわれる計算__ を下記の表で示します。C* は先程のノートで説明したように __最悪の場合は二分法と同じ効率になる__ ので、以下の計算では null window search の計算結果である αβ 値として、__fail low__ の場合は $\boldsymbol{α}$ が、fail high の場合は $\boldsymbol{α + 1}$ が計算されたものとします。下記の表から __最悪の場合でも__ C* では __11 回の null window search__ でミニマックス値を計算できることがわかります。

|回数|ウィンドウ|αβ 値|αβ 値の範囲|更新後のミニマックス値の範囲|
|--:|--:|--:|--:|--:|
|__1__| (0, 1) |1| fail high|[1, 1000]|
|__2__| (500, 501) | 500 |fail low| [1, 500]|
|__3__| (250, 251) | 250 |fail low| [1, 250] |
|__4__| (125, 126) | 125 |fail low| [1, 125] |
|__5__| (63, 64) | 63 |fail low|[1, 63] |
|__6__| (32, 33) | 32 |fail low|[1, 32] |
|__7__| (16, 17) | 17 |fail high|[17, 32] |
|__8__| (24, 25) | 25 | fail high|[25, 32] |
|__9__| (28, 29) | 29 | fail high|[29, 32]|
|__10__| (30, 31) | 30 | fail low|[29, 30]|
|__11__| (29, 30) | 30 | fail high|[30, 30]|

:::note
$α$ = (下界 + 上界) / 2 の切り捨てとしたのは、__切り上げで計算すると__ 上記の 11 回目の計算でウィンドウが (30, 31)、αβ 値が 30 で fail low のように __10 回目と同じ結果になる__ ため、__ミニマックス値の範囲__ が [29, 30] のまま __変化しなくなるから__ です。
::: 

__MTD(f) 法__ では[以前の記事](https://qiita.com/ysgeso/items/bdde35673f9ffc1127f4#mtdf-%E6%B3%95%E3%81%AE%E5%8A%B9%E7%8E%87)で説明したように、null window search の回数と、ミニマックス値の推定値である $f$、ミニマックス値である $s$ の間には下記の表のような関係があります。

|条件|最小回数|最大回数|
|:-:|:-:|:-:|
|$\boldsymbol{f < s}$|$2$|$s - f + 2$|
|$\boldsymbol{f = s}$ |$2$|$2$|
|$\boldsymbol{f > s}$|$2$|$f - s + 1$|

従って、__ミニマックス値の推定値__ として __22 を推定__ した場合は __最大で__ $30 - 22 + 2 = \boldsymbol{10}$ __回__、__39 を推定__ した場合は最大で $39 - 30 + 1 =\boldsymbol{10}$ __回__ の null window search が計算されるので、__22 ~ 39 の範囲__ のミニマックス値を __推定する__ と __MTD(f) 法の方が__ C* よりも __最悪の場合に効率が高く__ なります。

このことを __辞書で単語を探す場合に例えて説明__ すると以下のようになります。

__1000 ページの英語の辞書__ の中から __30 ページ目に記載__ されている __`apple`__ という単語を __二分法で探す__ のは、先程の C* の表の __2 回目から探索を行った場合と同じ__ と考えることができるため __10 回__ ページを開く必要があります。

一方、__MTD(f) と同様の考え方__ で単語を探す場合は、__`apple`__ という単語が __明らかに辞書の先頭のほうにある__ ことから `apple` が __載っていそうなページ__ として __先頭のほうにあるページ__ を開き、そこから __1 ページずつ単語を探す__ という方法をとります。例えば `apple` が載っていそうなページとして __開いたページが 30 ページ目__ の場合は、__ページを開く回数__ は $30 - 25 + 1 = \boldsymbol{6}$ __回ですみます__。このように、単語が載っている __ページの推定の精度が高ければ__、二分法よりも __推定したページから順番に探す方が速く見つける__ ことができます。

__精度の高いミニマックス値を推定できる場合__ は __MTD(f) のほうが効率が高くなる傾向__ があるのは、このことによく似ています。

本記事ではまだ説明していませんが、__反復深化__ という手法を用いることで __精度の高いミニマックス値を推定することができる__ ので、一般的には __C* はほとんど使われていない__ のではないかと思います。

## Aspiration Windows

MTD(f) 法で行う __null window search__ では、αβ 値が __exact value の範囲になることはない__ ので、必ず __2 回以上__ の null window search を行う必要があります。

Aspiration Windows では、__推定したミニマックス値を含む__ ような __狭いウィンドウ幅__ で αβ 値の計算を行ないます。そのため、__推定したミニマックス値が正しければ__、__1 回の狭いウィンドウ幅__ での αβ 値の計算によってミニマックス値を計算することができるため、__MTD(f) 法よりも効率が高くなることが期待__ できます。

ただし、ミニマックス値の __推定値を間違えた場合__ でウィンドウの範囲内にミニマックス値が入らない場合は __2 回以上__ の αβ 値の計算が必要になります。また、その際の __ウィンドウ幅__ は __null window search よりも広い__ ため、__MTD(f) 法よりも効率が悪くなってしまう__ という問題があります。

上記から、Aspiration Windows を利用する場合は __ウィンドウ幅を広げすぎると効率が悪くなる__ が、__ウィンドウ幅を狭くしすぎる__ とミニマックス値がウィンドウの __範囲内に入らなくなる可能性が高くなる__ という問題があるため、__適切なウィンドウ幅を決めるのが難しい__ という問題があります。また、MTD(f)法と同様に、__ミニマックス値の推定値の精度が非常に重要__ となります。

スカウト法や MTD(f) と比較して Aspiration Windows のほうが効率が良くなるかどうかについては、__ゲーム木の性質や、ミニマックス値の推定値の精度に左右されます__。

参考までに Chess Programming wiki の該当する記事のリンクを下記に紹介します。

https://www.chessprogramming.org/Aspiration_Windows

## 探索の並列化

最近のコンピューターには __複数の CPU が搭載されている__ ので、探索の処理を __複数の CPU__ で手分けして __同時に行う__ ことで __処理時間を減らす__ という手法があります。このような、__複数の処理を同時に行う処理__ のことを __並列処理__（parallel processing）と呼びます。並列処理は実際に効果的ですが、正しく行うためには気をつけなければならない点が数多くあるので、実装はそれほど簡単ではありません。また、残念ながら $n$ 個の CPU で並列処理を行っても処理時間が $1/n$ になることは通常はありません。

本記事では並列処理については今のところは扱う予定はありません。

参考までに Chess Programming wiki の該当する記事のリンクを下記に紹介します。

https://www.chessprogramming.org/Parallel_Search

## ヒューリスティックな探索

これまでの記事で紹介した ミニマックス法や αβ 法などでは、いずれも __正確なミニマックス値を計算__ していましたが、ゲーム木の __ノードの数が多くなる__ と計算に時間がかかりすぎるようになるため、__正確なミニマックス値を計算できなくなります__。そのような場合は __ミニマックス値の近似値を計算__ する __[ヒューリスティック](https://qiita.com/ysgeso/items/d7f60ba34f167f77a87e#%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%BC%E7%A7%91%E5%AD%A6%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E3%83%92%E3%83%A5%E3%83%BC%E3%83%AA%E3%82%B9%E3%83%86%E3%82%A3%E3%83%83%E3%82%AF)な探索__ を行います。ヒューリスティックな探索については次回以降の記事で紹介します。

# αβ 法の最大効率の証明

以下の記事の証明は理解しなくても大きな問題はありません。数式がかなり出てくるので数学が苦手な方は飛ばしてもらっても構いません。

[以前の記事](https://qiita.com/ysgeso/items/bdcbc31e6d6abf38cf29#mbtree-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-move_bestmove_to_head-%E3%81%AE%E5%AE%9A%E7%BE%A9)で、αβ 法で __最も効率よく枝狩りを行なえる場合__ は計算する必要があるノード数が __全体のノードの数の平方根の値くらいになる__ ということを説明しました。そのことは、[以前の記事](https://qiita.com/ysgeso/items/d444cd3b3336e5786882)の __完璧な move ordering での検証を利用__ することで証明することができます。

## 検証を行うゲーム木の性質と検証方法

あらゆるゲーム木での証明を行うことは非常に難しいので、__深さが__ $\boldsymbol{d}$ で、リーフノード以外の __すべてのノードに $\boldsymbol{n}$ 個の子ノード__ が存在するゲーム木の場合で説明します。

:::note
このようなゲーム木のことを __バランス木（平衡木）__ と呼びます。
:::

ただし、__ルートノードの深さを 0__、$\boldsymbol{n ≧ 2}$ とします。$n ≧ 2$ としたのは、すべてのノードの子ノードの数が 1 の場合は __αβ 法で枝狩りが行われることはない__ ため、ミニマックス法と αβ 法の __効率が常に同じになる__ からです。

:::note
__他の形状のゲーム木では平方根の値くらいになるとは限りません__。例えば 〇× ゲームのゲーム木は深さが浅い程子ノードの数が多くなるのでこの性質を満たしません。
:::

__ミニマックス法__ では __すべてのノードの評価値を計算__ します。また、__αβ 法__ で __最も効率よく枝狩りを行える__ のは __完璧な move ordering__ を行った場合です。そこで、下記を比較することで αβ 法の最大効率を計算することにします。

* ミニマックス法で計算されるノードの数
* 完璧な move ordering での αβ 法で計算されるノードの数

## ミニマックス法で計算されるリーフノードの数

これまでの記事では、__評価値を計算したすべてのノードの数__ で効率を比較してきましたが、__評価値を計算したリーフノードの数__ で効率を比較するという方法も __良く使われます__。本記事では __計算を簡単にするため__、ミニマックス法と最大効率の αβ 法を、評価値が計算された __リーフノードの数で比較__ することにします。

計算がかなり面倒になりますが、ノードの総数で比較したい方は計算してみて下さい。その場合の結論はリーフノードで比較した場合と変わらないことが確認できると思います。

### リーフノードの数で比較する理由

リーフノードの数で比較しても良い理由について説明します。

リーフノード以外のノードが $\boldsymbol{n}$ __個の子ノードを持つゲーム木__ は、__深さが 1 増えるたび__ に __ノードの数が $\boldsymbol{n}$ 倍__ になります。従って __深さが $\boldsymbol{i}$ のノードの数__ は $\boldsymbol{n^i}$ となるため、深さが $d$ の __リーフノードの数__ は $\boldsymbol{n^d}$ となります。

__深さが $\boldsymbol{d}$__ のゲーム木の __ノードの数の総数__ は、深さが __0 ~ $\boldsymbol{d}$__ までの __ノードの数の合計__ なので、以下の式で計算することができます。

$n^0 + n^1 + n^2 + ・・・ n^d$

数学では、このような式の中の __特定の数を増やしながら__ その __合計を計算する式__ を __Σ__（ギリシャ文字のシグマの大文字）という記号を使って、下記のように __簡潔に記述__ します。この記法は高校の数学で習うもので、良く使われます。

$\sum_{i=0}^{d}n^i$

この式に対して、下記の理由から $\boldsymbol{n^d ≦ \sum_{i=0}^{d}n^i < 2n^d}$ という __式が成り立ちます__。これは、子ノードの数が $n$、深さが $d$ のバランス木の __ノードの数の総数__ が、__リーフノードの数の倍以上にはならない__ ことを表します。ノードの数は深さが 1 つ増えるたびに $n$ 倍になるため、$\boldsymbol{n}$ や $\boldsymbol{d}$ __が大きい場合__ はノードの総数の代わりに __リーフノードの数を使って比較を行っても結果はそれほど大きくかわりません__。

:::note
$n^d ≦ \sum_{i=0}^{d}n^i < 2n^d$ が成り立つ理由は以下の通りです。

$n^d ≦ \sum_{i=0}^{d}n^i $ であることは、以下の式から明らかです。

$\sum_{i=0}^{d}n^i = n^0 + n^1 + ・・・ + n^d$

$\sum_{i=0}^{d}n^i$ は $n ≠ 1$ の場合は以下の式で計算することができます。その理由については次のノートで説明します。

$\sum_{i=0}^{d}n^i = \frac{n^{d+1} - 1}{n - 1}$  

また、上記の式は下記のように書き直すことができます。

$\frac{n}{n - 1}n^d - \frac{1}{n - 1}$  

$n ≧ 2$ の場合は $1 < \frac{n}{n - 1} ≦ 2$ なので、$\frac{n}{n - 1}n^d ≦ 2n^d$ です。

また、$n ≧ 2$ の場合は $0 < \frac{1}{n- 1} ≦ 1$ です。

上記から $\sum_{i=0}^{d}n^i = \frac{n}{n - 1}n^d - \frac{1}{n - 1} < \frac{n}{n - 1}n^d ≦ 2n^d$ となるので、$\sum_{i=0}^{d}n^i < 2n^d$ であることがわかります。
:::

:::note
$n ≠ 1$ の場合に下記の式が成り立つ理由について説明します。

$\sum_{i=0}^{d}n^i = \frac{n^{d+1} - 1}{n - 1}$  

$\sum_{i=0}^{d}n^i$ に $(n - 1)$ を乗算して式を展開すると下記のようになります。

$(\sum_{i=0}^{d}n^i)(n - 1) = (n^0 + n^1 + ・・・ + n^{d})(n - 1)$

$= (n^1 + n^2 + ・・・ + n^{d + 1}) - (n^0 + n^1 + ・・・ + n^{d})$

$= n^{d + 1} - n^0 = n^{d + 1} - 1$

上記の両辺を改めて $n - 1$ で割り算すると下記の先程の式が求められます。

$\sum_{i=0}^{d}n^i = \frac{n^{d+1} - 1}{n - 1}$  

なお、数学では 0 で割り算を行うことはできないので、$n ≠ 1$ という条件が必要になります。
:::

## 最大効率のアルファベータ法で計算されるリーフノードの数

αβ 法は精度が 100 % の move ordering を行なった際に効率が最大となります。

その場合に計算されるゲーム木のノードは [以前の記事](https://qiita.com/ysgeso/items/d444cd3b3336e5786882#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E5%88%86%E9%A1%9E%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81) から下図のようになります。
__① → ② → ① → ② の 繰り返しの図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c5da1ebe-38b1-4f9b-90ab-f5d926a92685.png" width="500">

__③ → ④ → ③ → ④ の繰り返しの図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/785a08bf-8de9-4570-9b6f-73e94a038cbd.png" width="500">

__⑤ → ⑥ → ⑤ → ⑥ の繰り返しの図__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c0c62944-2c8f-4ed8-8818-1a9661359ed6.png" width="500">

### ルートノードが max ノードの場合のゲーム木の分割

ルートノードは max ノードと min の場合がありますが、__どちらも同様の性質を持つ__ ので、ルートノードが max ノードの場合のみ説明を行います。

__ルートノードが max ノード__ の場合のゲーム木は __下図の 2 種類の部分木に分割__ できます。

* ルートノードの最初の子ノード（2 のノード）をルートノードとする部分木
* それ以外のノードを持つ部分木

表記を短くするために、ゲーム木全体を $T$、前者の部分木を $U$、後者の部分木を $V$ と表記し、$T$ が $U$ と $V$ の __ノードで構成されること__ を $\boldsymbol{T=U+V}$ と表記することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/469a97c3-e407-459b-a5ac-c038ec2f7e83.png" width="500">

また、__$\boldsymbol{T}$ のリーフノードの数__ は、上記で分割した __2 つの部分木 $\boldsymbol{U}$ と $\boldsymbol{V}$ のリーフノードの合計__ で計算されます。

### V のリーフノードの数の計算

先に $\boldsymbol{V}$ の __リーフノードの数__ を計算することにします。

当然ですが、__深さが 0__ のルートノードの __数は 1__ です。

__深さが 1__ のノードの数は、ルートノードの __最初のノードを除く必要がある__ ので、$\boldsymbol{n - 1}$ になります。

__深さが 1 以降__ のノードでは、下記の子ノードの計算が行われます。

* __深さが奇数__ のノードでは、__最初の子ノードのみが計算__ される
* __深さが偶数__ のノードでは、$\boldsymbol{n}$ __個のすべての子ノードが計算__ される

従って、__深さが 6 までのノードの数__ は以下の表のようになります。

|0|1|2|3|4|5|6|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$1$|$n-1$|$n-1$|$(n - 1)×n$|$(n - 1)×n$|$(n - 1)×n×n$|$(n - 1)×n×n$|

上記の式の () を外し、式を $\boldsymbol{n}$ __のべき乗で書き直す__ と以下の表のようになります。

|0|1|2|3|4|5|6|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$1$|$n^1-1$|$n^1-1$|$n^2 - n^1$|$n^2 - n^1$|$n^3 - n^2$|$n^3 - n^2$|

上記の表から深さ $i$ のノードの数は以下の式で計算できることがわかります。

* $i$ が 0 の場合は 1 となる
* $i$ が偶数の場合は $n^{\frac{i}{2}} - n^{\frac{i}{2}-1}$ となる
* $i$ が奇数の場合は $n^{\frac{i+1}{2}} - n^{\frac{i+1}{2}-1}$ となる

$V$ の深さ $i$ のノードの数は、ゲーム木の深さ $\boldsymbol{i}$ __によって変化する__ ので、その数を $\boldsymbol{v(i)}$ という関数で表記することにします。

:::note warn
$V$ の深さ $i$ のノードの数を表す $\boldsymbol{v(i)}$ は下記の式で計算される。

* $i$ が 0 の場合は 1
* $i$ が偶数の場合は $n^{\frac{i}{2}} - n^{\frac{i}{2}-1}$
* $i$ が奇数の場合は $n^{\frac{i+1}{2}} - n^{\frac{i+1}{2}-1}$
:::

リーフノードの深さは $d$ なので、$\boldsymbol{V}$ __のリーフノードの数__ は $\boldsymbol{v(d)}$ で計算できます。

### U の性質の考察

$U$ は下図の __2 をルートノードとする部分木__ ですが、よく見ると __その構造__ は __深さが $\boldsymbol{d - 1}$ である点を除くと $\boldsymbol{T}$ と全く同じ__ であることがわかります。そこで、$U$ を $\boldsymbol{T'}$ __と表記__ することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/af1c0b9d-03f1-4643-b0c5-ae18fca8f962.png" width="500">

$T'$ は $T$ と同様に下記の 2 種類の部分木に分割することができます。

* $T'$ のルートノードの __最初の子ノード__ をルートノードとする部分木
* それ以外の $T'$ のノードを持つ部分木

前者を $T''$、後者を $V'$ と表記することにすると、$\boldsymbol{V'}$ は __深さが $\boldsymbol{d-1}$__ である点を除けば、$\boldsymbol{V}$ __と全く同じ構造__ を持ちます。図は省略しますが、$\boldsymbol{T''}$ __の構造__ は深さが $\boldsymbol{d-2}$ である点を除けば $\boldsymbol{T}$ __と同じ__ です。

### T のリーフノードの数の計算式

上記から、__深さが__ $\boldsymbol{i}$ の $T$、$V$ と __同じ構造を持つ部分木__ をそれぞれ $T(i)$、$V(i)$ と表記すると、$i ≧ 2$ の場合に下記の式が成り立つことがわかります。

$T(i) = T(i - 1) + V(i)$

$\boldsymbol{T}$ は __深さが__ $\boldsymbol{d}$ __のゲーム木__ なので、$T$ は __下記の式__ で表すことができることがわかります。

$T = T(d)$
$= T(d - 1) + V(d)$ 
$= T(d - 2) + V(d - 1) + V(d)$ 
$= T(d - 3) + V(d - 2) + V(d - 1) + V(d)$ 
$= ・・・$
$= T(0) + V(1) + V(2) + ・・・ + V(d)$

__深さが 0 の木__ はルートノードしか存在しないのでの $\boldsymbol{T(0)}$ __のリーフノードの数は 1__ です。また、__深さが__ $\boldsymbol{d}$ の $\boldsymbol{V}$ __のリーフノードの数は__ $\boldsymbol{v(d)}$ で計算できるので、$\boldsymbol{V(i)}$ __のリーフノードの数__ は $\boldsymbol{v(i)}$ で計算できます。$\boldsymbol{v(0) = 1}$ なので、$\boldsymbol{T}$ __のリーフノードの数__ は以下の式で計算できます。

$1 + v(1) + v(2) + ・・・ + v(d)$
$= v(0) + v(1) + v(2) + ・・・ + v(d)$
$=\sum_{i=0}^{d}v(i)$

:::note warn
$\boldsymbol{T}$ __のリーフノードの数__ は下記の式で計算できる。

$\boldsymbol{\sum_{i=0}^{d}v(i)}$

ただし、$v(i)$ は以下の式で計算する。

* $i$ が 0 の場合は 1
* $i$ が偶数の場合は $n^{\frac{i}{2}} - n^{\frac{i}{2}-1}$
* $i$ が奇数の場合は $n^{\frac{i+1}{2}} - n^{\frac{i+1}{2}-1}$
:::

### d が偶数の場合の T のリーフノードの数の計算

次に、上記の $T$ のリーフノードの数を計算する式の計算を行うことにします。

$v(i)$ が計算する式は $\boldsymbol{i}$ __が偶数と奇数で異なる__ ので、上記の式を計算する際は $\boldsymbol{d}$ が __偶数の場合と奇数の場合で分けて考えたほうが良い__ でしょう。

そこで、$\boldsymbol{d}$ __が偶数の場合__ のリーフノードの数を __先に計算する__ ことにします。

同様の理由で、$\sum_{i=0}^{d}v(i)$ の合計を計算する際に $\boldsymbol{i}$ __が偶数の場合と奇数の場合で分けて考えたほうが__ 計算が __わかりやすくなります__。

$\boldsymbol{i}$ __が偶数の場合__ の $T$ のリーフノードの数を計算する式は __下記の表の合計__ になります。

|0|2|4|6|・・・|$\boldsymbol{d}$|
|:-:|:-:|:-:|:-:|:-:|:-:|
|$1$|$n^1-1$|$n^2 - n^1$|$n^3 - n^2$|・・・|$n^{\frac{d}{2}} - n^{\frac{d}{2}-1}$|

上記の表のそれぞれの __式の前後を入れ替える__ と以下のようになります。

|0|2|4|6|・・・|$\boldsymbol{d}$|
|:-:|:-:|:-:|:-:|:-:|:-:|
|$1$|$-1 + n^1$|$-n^1 + n^2$|$-n^2 + n^3$|・・・|$-n^{\frac{d}{2}-1} + n^{\frac{d}{2}}$|

これらの合計を計算すると、__隣り合った数字が打ち消しあう__ ため、$\boldsymbol{n^{\frac{d}{2}}}$ __だけが残ります__。従って、$\boldsymbol{i}$ __が偶数__ の場合の __合計は__ $\boldsymbol{n^{\frac{d}{2}}}$ となります。

$\boldsymbol{i}$ __が奇数__ の場合は下記の表のようになります。なお、$\boldsymbol{i}$ __が__ $\boldsymbol{d-1}$ の場合は $i$ が奇数の場合の $v(i) = n^{\frac{i+1}{2}} - n^{\frac{i+1}{2}-1}$ に $i = d - 1$ を代入することで以下のように計算しました。

$v(d-1) = n^{\frac{(d-1)+1}{2}} - n^{\frac{(d - 1)+1}{2}-1}$
$=n^{\frac{d}{2}} - n^{\frac{d}{2}-1}$
$=-n^{\frac{d}{2}-1} + n^{\frac{d}{2}}$

|1|3|5|・・・|$\boldsymbol{d-1}$|
|:-:|:-:|:-:|:-:|:-:|
|$-1 + n^1$|$-n^1 + n^2$|$-n^2 + n^3$|・・・|$-n^{\frac{d}{2}-1} + n^{\frac{d}{2}}$|

上記の表のそれぞれの計算式は $i$ が __偶数の場合とほぼ同じ__ ですが、__最初の 1 がない__ 点が __異なります__。従って $\boldsymbol{i}$ __が奇数__ の場合の __合計は__ $\boldsymbol{n^{\frac{d}{2}}} - 1$ となります。

このことから、$\boldsymbol{d}$ __が偶数の場合__ の __リーフノードの数__ は $\boldsymbol{n^{\frac{d}{2}} + n^{\frac{d}{2}} - 1}$ となります。なお、$2n^{\frac{d}{2}} - 1$ のように __まとめない理由はこの後で説明__ します。

### d が奇数の場合の T のリーフノードの数の計算

$\boldsymbol{d}$ __が奇数の場合__ は、__最も深い偶数のノードの深さ__ は $\boldsymbol{d - 1}$ となります。従って $\boldsymbol{i}$ __が偶数の場合__ の合計は $d$ が偶数の場合の $\boldsymbol{n^{\frac{d}{2}}}$ の式の $d$ を$\boldsymbol{d-1}$ __に置き換えた__ $\boldsymbol{n^{\frac{d-1}{2}}}$ となります。

__最も深い奇数のノードの深さ__ は $\boldsymbol{d}$ なので、$\boldsymbol{i}$ __が奇数の場合__ の合計は$d$ が偶数の場合の $\boldsymbol{n^{\frac{d}{2}}} - 1$ の式の $d-1$ を$\boldsymbol{d}$ __に置き換える__ ことで計算できます。$d-1$ を$d$ に置き換えるということは、$d$ を$\boldsymbol{d+1}$ __に置き換える__ ということなので $\boldsymbol{n^{\frac{d+1}{2}} - 1}$ になります。

従って $\boldsymbol{d}$ __が奇数の場合__ の __リーフノードの数__ は $\boldsymbol{n^\frac{d-1}{2} + n^{\frac{d+1}{2}} - 1}$ となります。

### T のリーフノードの数の計算式

上記をまとめると以下のようになります。

|$\boldsymbol{d}$|リーフノードの数|
|:-:|--:|
|__偶数__|$n^{\frac{d}{2}} + n^{\frac{d}{2}} - 1$|
|__奇数__|$n^\frac{d-1}{2} + n^{\frac{d+1}{2}} - 1$|

$d$ が偶数の場合と奇数の場合で __式が異なるのはわかりづらい__ ので、__1 つの式でまとめる__ ことにします。まとめる際には __数値__ の __小数点以下での切り上げ__ と __切り下げ__ を行うので、それらを表す __数学の記号を紹介__ します。

* $x$ の小数点以下の切り上げを $\lceil x \rceil$ と記述する。例えば $\lceil 2 \rceil = 2$、$\lceil 2.5 \rceil = 3$ である
* $x$ の小数点以下の切り下げ $\lfloor x \rfloor$ と記述する。例えば $\lfloor 2 \rfloor = 2$、$\lfloor 2.5 \rfloor = 3$ である

$\boldsymbol{d}$ __が奇数の場合__ は $\boldsymbol{\frac{d}{2}}$ を小数点以下で切り下げると $\boldsymbol{\frac{d-1}{2}}$ に、$\boldsymbol{\frac{d}{2}}$ を小数点以下で切り上げると $\boldsymbol{\frac{d+1}{2}}$ になります。従って $d$ が奇数の場合は以下の式が成り立ちます。

$n^\frac{d-1}{2} + n^{\frac{d+1}{2}} - 1 = n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} - 1$

例えば $d$ が __5 の場合__ は以下の表のようになり、__上記の式で正しく計算できる__ ことが確認できます。

|$\boldsymbol{d}$|$\boldsymbol{\frac{d}{2}}$|$\boldsymbol{\lfloor \frac{d}{2} \rfloor}$|$\boldsymbol{\frac{d-1}{2}}$|$\boldsymbol{\lceil \frac{d}{2} \rceil}$|$\boldsymbol{\frac{d+1}{2}}$|
|--:|--:|--:|--:|--:|--:|
|__5__|2.5|2|2|3|3|


一方、$\boldsymbol{d}$ __が偶数の場合__ は $\boldsymbol{\frac{d}{2}}$ __は常に整数になる__ ので $\frac{d}{2}$ を __切り上げても切り下げても__ その __値は変わりません__。従って、$d$ が奇数の場合は以下の式が成り立ちます。
 
$n^\frac{d}{2} + n^{\frac{d}{2}} - 1 = n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} - 1$

例えば $d$ が __6 の場合__ は以下の表のようになり、__上記の式で正しく計算できる__ ことが確認できます。

|$\boldsymbol{d}$|$\boldsymbol{\frac{d}{2}}$|$\boldsymbol{\lfloor \frac{d}{2} \rfloor}$|$\boldsymbol{\lceil \frac{d}{2} \rceil}$|
|--:|--:|--:|--:|
|__6__|3|3|3|


上記から下記の事がわかります。

:::note warn
$d$ が偶数でも奇数でも $T$ の __リーフノードの数__ は __下記の 1 つの式で表される__。

$n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} - 1$
:::

## 効率の比較

__ミニマックス法__ の場合のリーフノードの数と、__最大効率の αβ 法__ の __リーフノードの数__ を __表す式__ は以下の表のようになります。

||計算式|
|:--|:--|
|__ミニマックス法__|$n^d$|
|__最大効率の αβ 法__ |$n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} - 1$|

$\boldsymbol{n}$ と $\boldsymbol{d}$ が __ある程度以上大きい場合__ は、$\boldsymbol{n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil}}$ の値が __1 を無視しても良い程に大きくなる__ ので、__最大効率の αβ 法の計算式__ の __-1 を無視することができます__。例えば $n=10$、$d=10$ の場合は下記の表のようにリーフノードの数が計算されるので、$n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil}$ で計算して比較しても __結果にほとんど影響を与えません__。

||リーフノードの数|
|:--|--:|
|__ミニマックス法__（$n^d$）|10,000,000,000|
|__最大効率の αβ 法__（$n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} - 1$ で計算） |199,999|
|__最大効率の αβ 法__（$n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil}$ で計算） |200,000|

$\boldsymbol{d}$ __が偶数の場合__ は $\boldsymbol{\lfloor \frac{d}{2} \rfloor = \lceil \frac{d}{2} \rceil = \frac{d}{2}} $ なので、$\boldsymbol{n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} = 2n^\frac{d}{2}}$ です。また、$\boldsymbol{n^d}$ __の平方根__ である $\boldsymbol{\sqrt{n^d} = n^{\frac{d}{2}}}$ です。従って、$\boldsymbol{d}$ __が偶数の場合__ は最大効率の αβ 法のリーフノードの数は、ミニマックス法のリーフノードの数の __平方根のほぼ 2 倍__ になることがわかります。

$\boldsymbol{d}$ __が奇数__ の場合は $\boldsymbol{\lfloor \frac{d}{2} \rfloor = \frac{d-1}{2}}$、$\boldsymbol{\lceil \frac{d}{2} \rceil = \frac{d+1}{2}}$ なので以下の式が成り立ちます。

$n^{\lfloor \frac{d}{2} \rfloor} + n^{\lceil \frac{d}{2} \rceil} = n^{\frac{d-1}{2}} + n^{\frac{d+1}{2}}$
$= n^\frac{d}{2}(n^{\frac{-1}{2}} + n^{\frac{1}{2}})$
$= n^\frac{d}{2}(\frac{1}{\sqrt{n}} + \sqrt{n})$

従って、$\boldsymbol{d}$ __が奇数の場合__ は最大効率の αβ 法のリーフノードの数は、ミニマックス法のリーフノードの数の __平方根の $\frac{1}{\sqrt{n}} + \sqrt{n}$ 倍__ になることがわかります。

$n$ が 2、5、10、100 の場合は、$\sqrt{n}$ と $\frac{1}{\sqrt{n}} + \sqrt{n}$ は以下の表のようになり、
$n$ が大きくなるにつれその違いはほとんどなくなります。

|n|$\sqrt{n}$ |$\frac{1}{\sqrt{n}} + \sqrt{n}$|
|--:|--:|--:|
|2|1.41|2.12|
|3|1.73|2.31|
|5|2.24|2.68|
|10|3.16|3.48|
|100|10.00|10.10|
|1000|31.62|31.65|

従って、$d$ が奇数の場合は最大効率の αβ 法のリーフノードの数は、ミニマックス法のリーフノードの数の __平方根のほぼ $\sqrt{n}$ 倍__ になることがわかります。

上記をまとめると以下のようになります。

:::note warn
最大効率の αβ 法のリーフノードの数の、ミニマックス法のリーフノードの数の __平方根に対する比率__ は下記のようになる。

* 深さ $d$ が偶数の場合は 約 2 になる
* 深さ $d$ が奇数の場合は 約 $\sqrt{n}$ になる

従って $\boldsymbol{n}$ __を定数と考える__ と、最大効率の αβ 法のリーフノードの数は、ミニマックス法のリーフノードの数の __平方根に比例する__。
:::

先程示したようにバランス木の __全ノードの数__ は __リーフノードの数の 2 倍以下__ なので、__全ノードの数__ で比較しても最大効率の αβ 法のノードの数がミニマックス法のノードの数の __平方根に比例する__ ことに変わりはありません。

__別の見方__ をすると、__最大効率の αβ 法__ では、同じ数のノードの評価値を計算することで、__ミニマックス法のほぼ倍の深さ__ のゲーム木を __探索できる__ ということです。

証明方法は異なりますが、An analysis of alpha-beta pruning という論文でバランス木での αβ 法の最大効率がミニマックス法の平方根に比例することが証明されているので参考までにそのリンクを紹介します（論文の閲覧は有料です）。

https://www.sciencedirect.com/science/article/abs/pii/0004370275900193

# 今回の記事のまとめ

今回の記事では他の αβ 法を改善するアルゴリズムをいくつか紹介しました。また、__バランス木__ では最大効率の αβ 法の効率がミニマックス法の効率の __平方根に比例する__ ことを示しました。

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

今回の記事で入力したプログラムはありません。

# 次回の記事

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

[^1]:SSS は state space search の略で、* はスターと読みます。アルゴリズムの名前に * が付く由来は A* というアルゴリズムにあります。* の意味については [A* の Wikipedia の記事](https://ja.wikipedia.org/wiki/A*) の「歴史」の項目を参照して下さい
[^2]:Dual とは数学の双対問題（dual problem）から付けられた名前で、Dual* は SSS* の双対問題です。双対問題の説明を行うと長くなるので、興味がある方は [双対問題の Wikipedia](https://ja.wikipedia.org/wiki/%E5%8F%8C%E5%AF%BE%E5%95%8F%E9%A1%8C) を参照して下さい
[^3]:[Chess Programming wiki](https://www.chessprogramming.org/SSS*_and_Dual*)では、次のように説明されていました。"However, it turned out the algorithmic overhead was too big to pay off the saved nodes. Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin pointed out, that SSS* can be reformulated as a sequence of alpha-beta null window calls with a Transposition Table. "