Pythonで〇×ゲームのAIを一から作成する　その176　静的評価関数の精度に関する補足と確率分布の計算を行う関数の定義

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/23c4d441e6fab315456a

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

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

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

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

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

# 図を使った前回の記事の補足説明

前回の記事を読み直してみてわかりづらい点が多いと思いましたので、最初に図を使った補足説明を行ないます。

## 用語

本記事では[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E7%94%A8%E8%AA%9E%E3%81%AE%E6%95%B4%E7%90%86)に引き続き下記の表の用語を用いることにします。記号については今回の記事でもう一度説明します。

| 用語と記号 | 意味 |
| :-- | :-- |
| __正確なミニマックス値__ | 深さの制限がないゲーム木の探索によって計算される、局面の正確なミニマックス値のこと |
| __近似値__ | __静的評価関数が計算する__ 正確なミニマックス値とは異なる __不正確な値が計算される場合がある__ 評価値のこと |
| __近似値のミニマックス値__ | __深さ制限探索__ によって計算される、静的評価関数が計算する __近似値に対するミニマックス値__ のこと |
| $\boldsymbol{d}$ | 局面の形勢判断の難しさを表す数値 |
| $\boldsymbol{N(d)}$ | 局面の形勢判断の難しさが $d$ の __局面の集合__|
| $\boldsymbol{M(d)}$ | $N(d)$ の局面に対して静的評価関数が計算する __近似値の平均値__|
| $\boldsymbol{S(d)}$ | $N(d)$ の局面に対して静的評価関数が計算する __近似値の標準偏差__（standard variation）|
| $\boldsymbol{N_{mean}(s)}$ | $M(d) = s$ となる局面の集合。静的評価関数の __ばらつきをなくした場合__ にその局面に対して __計算される近似値__ が $s$ となる局面の集合　 |

## 前提条件の説明

説明を簡単にするために以下のような前提条件を付けることにします。

* ゲームには __引き分けがない__ ものとする
* 最短の勝利や最遅の敗北を目指さないものとする
* 静的評価関数は決着がついた局面の正確なミニマックス値を正しく計算できるものとする
* それ以外の局面で静的評価関数が計算する __近似値の精度がある程度以上高い__ ものとする
* __大きな正の整数__ $\boldsymbol{s}$ を決め、静的評価関数が近似値を __下記の表のように計算__ するものとする。なお、$s$ の具体的な値は重要ではないので、本記事では具体的な値は設定しない

|状況|近似値|
|--:|--:|
|__決着がついた先手の勝利の局面__|$s + 1$|
|__先手の必勝と正確に判定できる局面__|$s$|
|__先手が有利と判定する局面__| $1$ 以上 $s$ 未満の整数 |
|__互角だと判定する局面__|$0$|
|__後手が有利と判定する局面__|  $s-1$ 以上 $-1$ 以下の整数 |
|__後手の必勝と正確に判定できる局面__|$-s$|
|__決着がついた後手の勝利の局面__|$-s - 1$|

[以前の記事](https://qiita.com/ysgeso/items/9ca6d261d5d76130ba65#ai2s-%E3%81%AE%E5%A0%B4%E5%90%88)で説明したように、静的評価関数が __でたらめな近似値__ や、__精度が低い近似値__ を計算すると、深さの上限を上げても __近似値のミニマックス値の精度が高くなることはありません__。「静的評価関数が計算する近似値の精度がある程度以上高いものとする」という前提条件を付けた理由はそのためです。ある程度以上という表現はあいまいですが、そのゲームの上級者以上のレベルの強さの AI を作成できるような精度だと考えて下さい。

## 静的評価関数が計算する近似値の意味

静的評価関数は決着がついている局面に対しては正確なミニマックス値を計算できるので、以後は __決着がついていない局面の説明を行う__ ことにします。

ゲームに引き分けがないことにしたので、__すべての局面__ は __先手の必勝の局面__ と __後手の必勝の局面__ の __2 種類__ に分類されます。従って決着がついていない局面の __正確なミニマックス値__ は $\boldsymbol{s}$ __または__ $\boldsymbol{-s}$ となります。

__静的評価関数__ が __先手の必勝の局面__ に対して __正の近似値を計算__ した場合は、その局面が先手の必勝の局面であると __正しく判定している__ という意味になり、その数値が __小さいほど自信がなく__、__大きいほど__ 先手の必勝であることを __確信している__ という事を意味します。負の近似値を計算した場合はその逆の意味になります。

## 局面の形勢判断の難しさの概念の導入

静的評価関数が計算する __近似値__ は、局面の __形勢判断の難しさ__ を表していると考えることができます。形勢判断が難しく、どちらの必勝であるかが __はっきりしない局面__ は近似値として __0 に近い値が計算__ され、形勢判断が簡単で __先手の必勝__ であることが __明確な局面__ は近似値として $\boldsymbol{s}$ __に近い値が計算__ されます。

また、__ある程度以上強い複数の将棋の AI__ が __同じ局面でほぼ同じ評価値を計算__ することから、__形勢判断の難しさ__ を __数値として計算できる__ と __仮定__ して話を進めることにします。具体的には、局面の __形勢判断の難しさ__ を __0 以上__ $\boldsymbol{m}$ __以下の整数__ で計算する __仮想的な関数を仮定__ することにします。ゲームの __決着がついた局面__ は局面の状況を必ず正しく判定できるので __難しさは 0__、どちらの必勝の局面かが __判断できない最も形勢判断が難しい局面__ の __難しさは__ $\boldsymbol{m}$ となります。

以後は説明を簡潔にするために、その仮想的な関数によって計算される __局面の形勢判断の難しさ__ を単に $\boldsymbol{d}$ __と表記__ することにします。また、形勢判断の難しさが $d$ の __局面の集合__ を $N(\boldsymbol{d})$ と表記することにします。

### 形勢判断の難しさに関する補足

実際には将棋や囲碁のような複雑なゲームの局面の形勢判断の難しさを __厳密に計算__ する関数を定義することは __現実的には不可能__ だと思います。その理由の一つは、形勢判断の難しさを __厳密に定義することがほぼ不可能__ だからです。

難しさを定義することが困難な具体例として、小学校で学ぶ __整数の四則演算__（＋－×÷）が挙げられると思います。一般的に四則演算は __＋、－、×、÷ の順で難しい__ と言えるように __思えるかもしれません__ が、__そうとは限りません__。

例えば __2 桁の整数の四則演算__ であれば、__足し算の方が掛け算よりも難しいと思う__ かもしれませんが、$89 + 48$ と $20 × 30$ を比べるとおそらく __ほとんどの方__ が $\boldsymbol{20 × 30}$ __の方が簡単__ だというと思います。

また、__多くの人__ は $\boldsymbol{19 × 21}$ __は難しいと思う__ のではないかと思いますが、$\boldsymbol{(x - 1)(x + 1) = x^2 -1}$ という __数学の公式を知っていれば__、$19 × 21 = (20 - 1)(20 + 1) = 20 ^2 - 1 = 400 - 1 = 399$ のように、__暗算で簡単に計算__ することができます。

また、ほとんどの人が暗算はとても無理だと思う $\boldsymbol{255 × 257}$ は、__コンピューター科学を専門とする人__ であれば $(256 - 1) × (256 + 1) = 256 × 256 - 1 × 1 = 65536 - 1 = 65535$ のように __簡単に暗算できる人が多いでしょう__。これは、コンピューター科学を専門とする人は __2 進数に関する計算に親しんでおり__、$2^8 = 256$、$256 × 256 = 2 ^ {16} = 65536$ であることを __暗記している人が多い__ からです。

このように一見すると難しさを簡単に定義できそうな整数の四則演算でさえ、実際には __厳密な難しさを定義することは困難__ で、その人の __知識によって__ 同じ問題でも __難しさは大きく変わります__。これは将棋や囲碁のようなゲームの局面も同様で、プロであっても自分が __得意な局面とそうでない局面__ があるため、同じ局面であっても形勢判断が簡単だと考える人と、そうでないと考える人が存在します。クイズの問題の難易度なども同様でしょう。

ただし、厳密な難しさを定義することはできなくても __大雑把で良いのであれば何らかの方法__ で、多くの人が __ある程度納得できるような__ 整数の四則演算の __難しさを定義することはできる__ のではないかと __思います__。__本記事で仮定する形勢判断の難しさ__ も厳密なものではなく、何らかの方法で定義した __そのゲームの上級者が納得できるようなもの__ だと考えて下さい。

## 静的評価関数の誤差の精度を表すグラフ

静的評価関数の __近似値__ の __誤差の精度が高い__ ということは、形勢判断が難しい局面に対して精度が低い静的評価関数よりも __自信をもって形勢判断を行うことができる__ ということを意味します。現実の世界に当てはめると、将棋の初心者にとってどちらが優勢であるかを判断できないよう __難解な局面でも__、__将棋が強くなればなるほど__ どちらが有利であるかを __正確に判断することができる__ ようになります。

前回の記事ではこのことを言葉だけで説明したのでわかりづらかったのではないかと思いましたので、そのことを __図で説明する__ ことにします。なお、下図はあくまでイメージです。実際の静的評価関数がこのような __単調増加__ する __滑らかな形のグラフになるとは限らない__ 点に注意して下さい。静的評価関数によっては __特定の性質を持つ局面の形勢判断を行うことが得意__ なものもあるので、グラフが __波打つような形になるものもある__ でしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/93901132-93ee-48d3-b2b6-4938601b4562.png" width="500">

上図は __先手の必勝の局面__ に対して __3 種類の静的評価関数__ が計算する __近似値を表す__ グラフです。グラフの __横軸が局面の形勢判断の難しさ__ を、__縦軸__ がその難しさの局面に対して静的評価関数が計算する __近似値の平均値__ を表します。[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E9%9D%99%E7%9A%84%E8%A9%95%E4%BE%A1%E9%96%A2%E6%95%B0%E3%81%AE%E8%A8%AD%E5%AE%9A)では局面の難しさが $d$ の局面に対して計算される近似値の平均値を $\boldsymbol{M(d)}$ と表記しましたので、本記事でもその記号で表記することにします。また、以後はグラフ内の「静的評価関数 A」のグラフを単に A のように表記することにします。

__先手の必勝の局面__ なので、__正確なミニマックス値__ は __常に青色の線__ が表す $\boldsymbol{s}$ となります。従って、$\boldsymbol{s}$ __と__ 静的評価関数が計算した __$\boldsymbol{M(d)}$ との差__ が __誤差__ となります。

図から 3 種類の静的評価関数は __すべての__ $\boldsymbol{d}$ で __A、B、C の順__ で $\boldsymbol{M(d)}$ __と__ $\boldsymbol{s}$ __との誤差が小さい__ ので、誤差の精度は __A、B、C の順で精度が高い__ と言えます。

:::note
実際には静的評価関数によって __形勢判断が得意な局面が異なる__ ことがあるので、ある $d$ に対しては A のほうが誤差が少ないが、別の $d$ に対しては B の方が誤差が少ないこともあります。そのような場合は上記の __グラフの線は交差__ します。
:::

上図の __A の静的評価関数の精度__ を __さらに高める__ と、下図の __Z、Y__ のようにグラフが __正確なミニマックス値__ を表す __青色のグラフに近づいていきます__。このことから、静的評価関数の __誤差の精度を高める__ ということは __青色のグラフ__ の近似値を __計算することを目指す__ という事を意味し、__精度が 100 %__ になると __青色のグラフと一致する__ ようになることがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4e8b629f-e308-4df7-89fb-5483c646000f.png" width="500">

逆に静的評価関数の __精度が低くなる__ と、下図の __D、E__ のように計算される $\boldsymbol{M(d)}$ __が 0 に近づいていきます__。このことから、__近似値として 常に 0 を計算__ する __`ai2s`__ は __最も精度が低い__ 静的評価関数であると __考えることができます__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7b847819-be4d-4133-b528-99486c5f7dae.png" width="500">

## 静的評価関数のばらつき

上記のグラフは静的評価関数が、__同じ難しさ__ の形勢判断の局面に対して計算する __近似値の平均値__ を表しますが、__実際に計算__ される近似値には __ばらつきが生じます__。また、その __ばらつき__ は[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E3%81%B0%E3%82%89%E3%81%A4%E3%81%8D%E3%81%AE%E6%8C%87%E6%A8%99)で説明した __標準偏差__ で __数値として表す__ ことができます。

同じテストを受けた学生のテストの点数の分布のように、__同じ種類のデータを複数計測__ した際に得られるデータの[ヒストグラム](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E3%83%87%E3%83%BC%E3%82%BF%E3%81%AE%E5%88%86%E5%B8%83%E3%81%AB%E3%82%88%E3%82%8B%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE%E3%81%AE%E6%AF%94%E8%BC%83)は、下図のような __平均値付近を中心とした山形の分布__ になるのが __一般的__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/57338402-eb34-4947-8400-852cf5295ffb.png" width="300">

もちろん、実際の静的評価関数が $N(d)$ に対して計算する近似値の分布は平均値を中心とした山形になるとは限りませんが、__ばらつきが少なくなる__（精度が高くなる）と __ほとんどの値が平均値に近くなる__ ので、__平均値を中心__ とした __左右対称の山形の分布__ に __近づきます__。先程「静的評価関数が計算する __近似値の精度がある程度以上高い__ ものとする」という前提条件をつけたので、本記事では __$N(d)$__ に対して静的評価関数が計算する __近似値の分布__ が近似値の __平均値である__ $\boldsymbol{M(d)}$ __を中心__ とする __左右対称となる山形__ であるものとします。

### 形勢判断の難しさとばらつきの精度の関係

__形勢判断が簡単な局面__ であればあるほど、__正確な形勢判断を行なえる__ ことは明らかです。実際に、__形勢判断が最も容易__ なゲームの __決着がついた局面__ は必ず正確なミニマックス値を計算できるので、近似値のばらつきを表す __標準偏差は 0__ になります。従って、__形勢判断が難しいほど__ 近似値のばらつきを表す __標準偏差は大きくなる__ と考えることができます。本記事では $M(d)$ の局面に対して計算された __近似値の標準偏差__ を $\boldsymbol{S(d)}$ と表記することにします。

下図は __先手の必勝の局面__ に対して 3 種類の静的評価関数が計算する $\boldsymbol{S(d)}$ __を表すグラフ__ です。グラフの __横軸が局面の形勢判断の難しさ__ を、__縦軸__ がその難しさの局面に対して静的評価関数が計算する __近似値の標準偏差__ を表します。図から 3 種類の静的評価関数はすべての場合で __F、G、H の順で標準偏差が小さい__ ので、__ばらつきの精度__ は __F、G、H の順で高い__ と言えます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8cee7d10-f151-446b-9116-36216e9c34d8.png" width="500">

:::note
上記のグラフは単調減少する直線ですが、実際の静的評価関数に対するグラフの形状は単調減少するとは限らないので、波打つような曲線になるものもあるでしょう。
:::

このように、__局面の形勢判断の難しさ__ によって __ばらつきは変化__ しますが、一方で局面の形勢判断の難しさを表す $\boldsymbol{d}$ __が近い__、すなわち近似値の平均値を表す $\boldsymbol{M(d)}$ __の値が近ければ__、__ばらつきはほぼ同じになる__ とみなすことができます。[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E9%9D%99%E7%9A%84%E8%A9%95%E4%BE%A1%E9%96%A2%E6%95%B0%E3%81%AE%E8%A8%AD%E5%AE%9A)で __形勢判断の難しさに関わらず__、計算される __近似値の分布の形が同じ__ であるとした理由は、[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%8C-1-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE) で __深さの上限が 1__ の場合の近似値のミニマックス値の __標準偏差の計算__ を行う際に、静的評価関数が計算する子ノードの __$\boldsymbol{M(d)}$ が 0 と -1__ のように __近い場合__ に対する計算を行なったからです。

## 静的評価関数の誤差の精度と形勢判断の正確さの関係

次に、__誤差の精度__ が __形勢判断の正確さに及ぼす影響__ について図で説明します。なお、具体的な数値を使って計算するとかえってわかりづらくなると思いますので、__具体的な数値は最小限__ にし、__図の見た目から判断できる__ ような例で説明します。

__B のほうが誤差の精度が高い__ 2 つの静的評価関数 __A と B__ があり、__近似値のばらつきの精度は同じ__ であるとします。B のほうが誤差の精度が高いので、先手の必勝で $d$ が同じである $N(d)$ の局面に対して計算する __近似値の平均値__ $\boldsymbol{M(d)}$ は __B のほうが大きく__ なります。

下図は、先手が必勝で形勢判断の難しさが $d$ の局面に対する __近似値の平均値__ $\boldsymbol{M(d)}$ を __A が 3__、__B が 5__ と計算した場合に計算される近似値の __[確率分布](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E7%A2%BA%E7%8E%87%E5%88%86%E5%B8%83%E3%81%AE%E6%9C%9F%E5%BE%85%E5%80%A4%E3%81%A8%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)のヒストグラム__ です。

$M(d) = 3$ の場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cd046434-bea9-40c7-9322-27cc4a9691be.png" width="350">　

$M(d) = 5$ の場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/98d7fcc1-17a3-4388-82a8-9149570a101a.png" width="350">

__ばらつきの精度が同じ__ で $\boldsymbol{M(d)}$ __の値が近い__ ことから、__グラフの形状はどちらも同じ__ としました。__先手の必勝の局面__ なので、__正の近似値を計算__ した場合に __形勢を正しく評価__ したことになります。従って __0 以下の近似値が計算__ される、__オレンジの部分__ の __全体の面積に対する割合__ が __間違った形勢判断__ を行う __割合__ を表します。図から明らかに __近似値の平均値が高い B__ のヒストグラムのほうが __オレンジの部分の面積が狭い__ ので、__B__ のほうが __形勢を正しく評価できる確率が高い__ ことがわかります。このことから、静的評価関数の __誤差の精度が高いほう__ が __形勢判断をより正確に行なえる確率が高い__ ことがわかります。

## 静的評価関数のばらつきの精度と形勢判断の正確さの関係

次に、__ばらつきの精度__ が __形勢判断の正確さに及ぼす影響__ について図で説明します。

__D のほうがばらつきの精度が高い__  2 つの静的評価関数 __C と D__ があり、__近似値の誤差の精度は同じ__ であるとします。下記の 2 つのグラフは __先手の必勝の局面__ で、C と D が $\boldsymbol{M(d)}$ __が 3__ の局面に対して計算した __近似値の確率分布のヒストグラム__ を表します。__D__ のほうが __ばらつきの精度が高い__ ので __ヒストグラムの幅が狭__ くなり、__間違った形勢判断__ を行う __オレンジの部分の面積が狭く__ なります。

__ばらつきの精度が低い C のヒストグラム__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cd046434-bea9-40c7-9322-27cc4a9691be.png" width="350">　

__ばらつきの精度が高い D のヒストグラム__

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/34ceb2ea-114c-4a55-941b-a91d475316a5.png" width="350">　

見た目ではその違いがわかりづらいのではないかと思いましたので、上記の __2 つのグラフを重ねた__ 下図のグラフを示します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/69fd9c06-50ab-4816-8ea3-2f789ccf944c.png" width="350">　

__赤色の部分__ が __D が間違った形勢判断を行う__ 0 以下の近似値を計算した __部分です__。図から __明らかに C__ が間違った形勢判断を行うオレンジ色の面積 __よりも小さい__ ことがわかります。このように、__ばらつきの精度が高いほう__ が __形勢判断をより正確に行える__ ことがわかります。

上記から、静的評価関数の __誤差の精度__ と、__ばらつきの精度__ が、__どちらも__ 形勢判断をより正確に行うために __重要であることが確認__ できました。

## 高い近似値を選択したほうが良い理由

静的評価関数が計算する __近似値にばらつきが存在せず__、静的評価関数が __先手の必勝の局面に対して正の近似値__、__後手の必勝の局面に対して負の近似値__ を計算する場合は、その __値の大小に関わらず常に正しく形勢判断を行う__ ことができます。その場合は、静的評価関数が計算した __近似値が正の合法手を指し続ければ__、それが __どの子ノードの合法手であっても__ 先手が __必ず勝利する__ ことができます。

一方、__現実の静的評価関数__ が計算する __近似値__ には __ばらつきが存在__ します。__ばらつきが存在する場合__ は、先程説明したように、__近似値の平均値が高い__ 子ノードの __合法手を選択したほうが__、__形勢判断を間違う可能性が低く__ なります。[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E5%B1%80%E9%9D%A2%E3%81%AE%E7%8A%B6%E6%B3%81%E3%82%92%E6%AD%A3%E3%81%97%E3%81%8F%E5%88%A4%E5%AE%9A%E3%81%A7%E3%81%8D%E3%82%8B%E3%81%93%E3%81%A8%E3%81%AE%E9%87%8D%E8%A6%81%E6%80%A7)で説明したように、__二人零和有限確定完全情報ゲーム__ では、__一度のミスが勝率に大きな影響__ を及ぼすので、__形勢判断を正しく行う__ ことができる __確率が高い局面になるような合法手を選択__ することが __非常に重要__ です。これが、静的評価関数が __正確なミニマックス値を計算できなくても__、__ミニマックス法__ に従って max ノードで __最も高い近似値__ の子ノードを __選択するべきである理由__ です。min ノードで最も低い近似値の子ノードを選択するべきである理由も同様です。

# 深さの上限が 1 の場合の計算を行う関数の定義

[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%8C-1-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)では、__深さの上限が 1__ の場合に計算される __近似値のミニマックス値__ の __確率分布__ とその __期待値[^1]と標準偏差__ の計算を __手作業で行いました__ が、その際に __かなりの手間__ がかかりました。前回の記事とは異なる __様々な状況で同様の計算を行う__ のは __大変なの__ で、__その確率分布の計算を行う__ 下記のような __関数を定義__ することにします。なお、確率分布の期待値と標準偏差の計算を行う関数についてはその後で定義することにします。

__名前__：近似値のミニマックス値の __確率分布（probability distribution）の計算__ を行うので __`calc_pdist`__ とする
__処理__：__2 つの子ノード__ に対して計算される __近似値の確率分布__ を使って __max ノード__ である局面の近似値のミニマックス値の __確率分布を計算__ する
__入力__：仮引数 __`pdistA`__、__`pdistB`__ に 2 つの子ノードの __近似値の確率分布__ を代入する
__出力__：__max ノード__ の近似値のミニマックス値の __確率分布を表すデータ__

## 確率分布を表すデータ構造

上記の関数を定義するためには、__近似値の確率分布__ を表すデータの __データ構造を考える__ 必要があります。どのようなデータ構造にすれば良いかについて少し考えてみて下さい。

本記事では下記のようなデータ構造で確率分布を表すことにします。なお、__list で表現しなかった理由__ は、list の __インデックス__ に __負の値を設定できない__ からです。

* __キーを近似値__、__キーの値を__ その近似値が計算される __確率__ とした __dict__

例えば、[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%AB%E3%82%88%E3%82%8B%E3%81%B0%E3%82%89%E3%81%A4%E3%81%8D%E3%81%AE%E9%81%95%E3%81%84%E3%81%AE%E6%AF%94%E8%BC%83%E6%96%B9%E6%B3%95)で用いた、任意の $d$ に対して下記のような __確率分布で近似値を計算__ する __静的評価関数__ を考えることにします。

|近似値の平均値 $\boldsymbol{M(d)}$ との差|-2|-1|0|1|2|
|:--|--:|--:|--:|--:|--:|
| __局面の割合__ |5%|20%|50%|20%|5%|

[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%8C-1-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)と同様に、下図の max ノードである __ノード N__ の近似値のミニマックス値を __深さの上限が 1__ の深さ制限探索で計算した場合の __確率分布__ とその __標準偏差を計算__ することにします。黒枠のノードが max ノード、赤枠のノードが min ノードを表します。__円の中の数値__ は、その局面が $\boldsymbol{M(d) =}$ __円の中の数値__ となる局面の集合に属することを表し、静的評価関数の __ばらつきをなくした場合__ にその局面に対して __計算される近似値__ を表します。[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%AB%E3%82%88%E3%82%8B%E3%81%B0%E3%82%89%E3%81%A4%E3%81%8D%E3%81%AE%E9%81%95%E3%81%84%E3%81%AE%E6%AF%94%E8%BC%83%E6%96%B9%E6%B3%95)ではこの $M(d) = s$ となる局面の集合を $\boldsymbol{N_{mean}(s)}$ と表記することにしました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b866a8d7-c492-48fc-994f-d286ddfd8113.png" width="250">　


上図の $M_{mean}(0)$ と $M_{mean}(1)$ に属する __ノード A__ と __ノード B__ を静的評価関数で計算した際の __確率分布 `pdistA`__ と __`pdistB`__ は下記のプログラムのように記述できます。

```python
pdistA = {
    -2: 0.05,
    -1: 0.2,
     0: 0.5,
     1: 0.2,
     2: 0.05
}
pdistB = {
    -3: 0.05,
    -2: 0.2,
    -1: 0.5,
     0: 0.2,
     1: 0.05
}
```

## `product` による直積の計算方法

[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%8C-1-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)で行なったように、上図のノード N の近似値のミニマックス値の __確率分布を計算__ するためには、__ノード A__ と __ノード B__ で計算される __近似値のすべての組み合わせ__ と __その確率を計算__ する必要があります。そのような __複数の集合の中__ から __1 つずつ要素を取り出した__ 場合の __すべての組み合わせの事__ を __直積__ と呼び、Python で効率的な __イテレータ__ を作成する関数を集めた __itertools__ という組み込みモジュールの __`product`__ という関数を利用して __直積を計算__ することができます。イテレータについてはこの後で説明します。

__`product`__ は実引数に記述した __集合を表す__ list などの __反復可能オブジェクト__ の __直積を計算__ し、計算した __直積を表すイテレーター__ を __返り値として返す__ 処理を行います。

`product` の詳細については下記のリンク先を参照して下さい。

https://docs.python.org/ja/3.13/library/itertools.html#itertools.product

__`product`__ の具体的な __使用例__ を示します。下記のプログラムは、__`["A", "B", "C"]`__ と __`[1, 2]`__ を実引数に記述して __`product`__ を呼び出すプログラムで、直積の集合を表す __イテレータ__ が返されます。

```python
from itertools import product

prod = product(["A", "B", "C"], [1, 2])
print(prod)
```

実行結果

```
<itertools.product object at 0x0000019BF4620580>
```

### イテレータの性質

[以前の記事](https://qiita.com/ysgeso/items/0d64d1ddba1982b5a5d3#%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%A8%E3%82%A4%E3%83%86%E3%83%AC%E3%83%BC%E3%82%BF)で list などの __反復可能オブジェクト__ と __イテレータ__ は似ているが __異なるものである__ と説明しました。その __違いの一つ__ が __`print` での内容の表示__ で、イテレータの場合は上記の実行結果のようにその __具体的な内容は表示されません__。

一方、__イテレータ__ は反復可能オブジェクトと同様に、下記のプログラムのように __for 文__ を利用することでその __中身を順番に取り出す__ ことができ、実行結果から __`["A", "B", "C"]`__ と __`[1, 2]`__ の __すべての組み合わせ__ が __tuple の形式__ で __計算されている__ ことが確認できます。

```python
for data in prod:
    print(data)
```

実行結果

```
('A', 1)
('A', 2)
('B', 1)
('B', 2)
('C', 1)
('C', 2)
```

また、`product` で作成した __イテレータ__ を __`list` の実引数に記述__ して呼び出すことで、下記のプログラムのように __`list` の形式にデータを変換__ することができます。

```python
print(list(product(["A", "B", "C"], [1, 2])))
```

実行結果

```
[('A', 1), ('A', 2), ('B', 1), ('B', 2), ('C', 1), ('C', 2)]
```

:::note
先程 for 文で使用した `prod` を下記のプログラムで `list` に変換して表示すると中身が空の list が表示されます。このように、イテレータは list などの反復可能オブジェクトと異なり __for 文での使用後は利用できなくなる__ ので、再利用できない __使い捨てのデータ__ であると言えます。

```python
print(list(prod))
```

実行結果

```
[]
```

イテレータと反復可能オブジェクト（iterable）の具体的な違いについての知識は、`product` を利用する際に必要ではないので必要になった時点で説明することにします。興味がある方は下記の Python の公式のドキュメントを参照して下さい。
:::

https://docs.python.org/ja/3.13/glossary.html#term-iterator

https://docs.python.org/ja/3.13/glossary.html#term-iterable

### `product` による確率分布を表す集合の直積の計算方法

下記のプログラムで先程の __`pdistA` と `pdistB`__ を __`product` の実引数に記述__ して __list に変換__ すると、実行結果のようにノード A と ノード B で計算される __5 × 5 = 25 通り__ の __近似値の組み合わせを表す tuple__ を要素として持つ __list__ が表示されますが、それぞれの __組み合わせの確率を計算するために必要__ な __確率のデータが含まれていない__ という問題があります。

```python
from pprint import pprint

pprint(list(product(pdistA, pdistB)))
```

実行結果

```
[(-2, -3),
 (-2, -2),
 (-2, -1),
 (-2, 0),
 (-2, 1),
 (-1, -3),
 (-1, -2),
 (-1, -1),
 (-1, 0),
 (-1, 1),
 (0, -3),
 (0, -2),
 (0, -1),
 (0, 0),
 (0, 1),
 (1, -3),
 (1, -2),
 (1, -1),
 (1, 0),
 (1, 1),
 (2, -3),
 (2, -2),
 (2, -1),
 (2, 0),
 (2, 1)]
```

__近似値が計算される確率__ を __組み合わせのデータ内に入れる__ ためには、下記のプログラムのように dict の __キーとキーの値の一覧__ を表す __`items` メソッドの返り値__ を `product` の実引数に記述します。実行結果から、 `((ノード A の近似値, その確率), (ノード B の近似値, その確率))` という __tuple で 25 通りの組み合わせが計算__ されることが確認できます。

```python
pprint(list(product(pdistA.items(), pdistB.items())))
```

実行結果

```
[((-2, 0.05), (-3, 0.05)),
 ((-2, 0.05), (-2, 0.2)),
 ((-2, 0.05), (-1, 0.5)),
 ((-2, 0.05), (0, 0.2)),
 ((-2, 0.05), (1, 0.05)),
 ((-1, 0.2), (-3, 0.05)),
 ((-1, 0.2), (-2, 0.2)),
 ((-1, 0.2), (-1, 0.5)),
 ((-1, 0.2), (0, 0.2)),
 ((-1, 0.2), (1, 0.05)),
 ((0, 0.5), (-3, 0.05)),
 ((0, 0.5), (-2, 0.2)),
 ((0, 0.5), (-1, 0.5)),
 ((0, 0.5), (0, 0.2)),
 ((0, 0.5), (1, 0.05)),
 ((1, 0.2), (-3, 0.05)),
 ((1, 0.2), (-2, 0.2)),
 ((1, 0.2), (-1, 0.5)),
 ((1, 0.2), (0, 0.2)),
 ((1, 0.2), (1, 0.05)),
 ((2, 0.05), (-3, 0.05)),
 ((2, 0.05), (-2, 0.2)),
 ((2, 0.05), (-1, 0.5)),
 ((2, 0.05), (0, 0.2)),
 ((2, 0.05), (1, 0.05))]
```

## `calc_pdict` の定義

下記は __`calc_pdict`__ を定義するプログラムです。近似値のミニマックス値の __確率分布__ は、__それぞれの組み合わせ__ で計算される __近似値の確率を加算__ することで計算します。その際に、[以前の記事](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#defaultdict-%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%9F%E9%9B%86%E8%A8%88)で説明した __defaultdict を利用した集計__ を行なっています。

* __1 行目__：確率分布を計算する際に必要となる defaultdict をインポートする
* __3 行目__：仮引数 `pdistA`、`pdistB` を持つ関数として定義する
* __4 行目__：近似値のミニマックス値の確率分布を表す `result` をデフォルト値を 0 とする defaultdict で初期化する
* __5 行目__：`pdistA` と `pdistB` の直積を表すデータを計算する
* __6 行目__：直積からそれぞれの子ノードの近似値と確率を取り出して繰り返し処理を行う
* __7 行目__：max ノードなので 2 つの子ノードの近似値の最大値が近似値のミニマックス値となるのでその計算を行う
* __8 行目__：その組み合わせの近似値が計算される確率を計算する
* __9 行目__：`result` の 近似値のミニマックス値のキーの値に、8 行目で計算した確率を加算する
* __10 行目__：計算された近似値のミニマックス値の確率分布を返り値として返す

```python
 1  from collections import defaultdict
 2  
 3  def calc_pdist(pdistA, pdistB):
 4      result = defaultdict(int)
 5      productdata = product(pdistA.items(), pdistB.items())
 6      for ((scoreA, probA), (scoreB, probB)) in productdata:
 7          score = max(scoreA, scoreB)
 8          prob = probA * probB
 9          result[score] += prob
10      return result
```

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

```python
from collections import defaultdict

def calc_pdist(pdistA, pdistB):
    result = defaultdict(int)
    productdata = product(pdistA.items(), pdistB.items())
    for ((scoreA, probA), (scoreB, probB)) in productdata:
        score = max(scoreA, scoreB)
        prob = probA * probB
        result[score] += prob
    return result 
```

</details>

下記は、`pdistA` と `pdistB` を子ノード A、B が計算する近似値の確率分布とした場合の、近似値のミニマックス値の確率分布を計算するプログラムで、__[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%8C-1-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)で計算した確率分布とほぼ同じ__ 内容が計算されていることが確認できます。

```python
pprint(calc_pdist(pdistA, pdistB))
```

実行結果

```
defaultdict(int,
            {-2: 0.012500000000000002,
             -1: 0.17500000000000002,
             0: 0.525,
             1: 0.23750000000000004,
             2: 0.05000000000000001})
```

### 誤差についての補足

前回の記事では __近似値が -2__ に対する __確率を 0.0125 と計算__ しましたが、上記では __0.012500000000000002__ というほんの少しだけ異なる確率が計算されています。

これは、Python に限らずコンピューターが内部では数値を 2 進数で計算しているため、小数点以下を含む 10 進数の数値を正確に計算することができない場合があるからです。

具体例として __10 進数の 0.1__ は 2 進数では .00011001100110011・・・ のような __無限に 0011 が繰り返される__ 値になるので正確に表現することはできません。

このような誤差は、四捨五入などを行うことで __見た目は発生していないような工夫__ がされていますが、誤差が無くなっているわけではないので下記の __`0.1 * 3`__ の計算結果が __`0.30000000000000004`__ になることから、__誤差の存在が表面化__ することが実際にあります。

```python
print(0.1 * 3)
```

実行結果

```
0.30000000000000004
```

このような __誤差は非常に小さい__ ので __多くの計算では無視しても問題ありません__ が、場合によってはこのような __誤差によって意図しない計算結果が生じる__ という __バグが発生することがある__ 点に注意が必要です。バグの具体例については今後の記事で紹介する予定です。

## 期待値と標準偏差の計算

次に、__確率分布__ から __期待値__(expectation value)、__分散__(variance)、__標準偏差__(standard deviation) の __統計データ__（statistic value）を計算する関数 __`calc_stval`__ を下記のプログラムのように定義することにします。行っている処理は、[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E7%A2%BA%E7%8E%87%E5%88%86%E5%B8%83%E3%81%AE%E6%9C%9F%E5%BE%85%E5%80%A4%E3%81%A8%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)で説明した式で確率分布の期待値、分散、標準偏差を計算して返しているだけなので説明は省略します。

```python
def calc_stval(pdist):
    e = 0
    for s, p in pdist.items():
        e += s * p
    var = 0
    for s, p in pdist.items():
        var += ((s - e) ** 2) * p
    std = var ** 0.5
    return e, var, std
```

下記のプログラムで、__`pdistA`__、__`pdistB`__、と先程計算した __ノード N の確率分布__ の統計データを計算すると、実行結果のように __[前回の記事](https://qiita.com/ysgeso/items/23c4d441e6fab315456a#%E6%B7%B1%E3%81%95%E3%81%AE%E4%B8%8A%E9%99%90%E3%81%8C-1-%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE)とほぼ同じ__ 結果が計算されるので __正しい値が計算された__ ことが確認できます。なお、下記の計算でも先程説明した極微小な誤差が発生しています。

```python
print(calc_stval(pdistA))
print(calc_stval(pdistB))
print(calc_stval(calc_pdist(pdistA, pdistB)))
```

実行結果

```
(-2.7755575615628914e-17, 0.8, 0.8944271909999159)
(-1.0, 0.8, 0.8944271909999159)
(0.13750000000000007, 0.6435937500000002, 0.8022429494860022)
```

# 今回の記事のまとめ

今回の記事では最初に図を使った前回の記事の補足説明を行いました。

次に、深さの上限が 1 の深さ制限探索での近似値のミニマックス値の確率分布と統計データを計算する関数を定義しました。

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

今回の記事で定義した `calc_pdist` と `calc_stval` はゲーム木に関連する処理なので、`tree.py` に保存することにします。

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

# 次回の記事

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

[^1]:__期待値__ はデータの集合から複数のデータを取り出した場合に __想定される平均値__ のことを表す用語です。一方、平均値は __実際に取り出したデータ__ に対する平均値のことなのでその意味は異なります。__確率分布__ は個々の __データが発生する確率を表す__ ので、確率分布から計算される平均値は __期待値__ と表現されます