Pythonで〇×ゲームのAIを一から作成する　その175　静的評価関数の近似値の誤差の精度とばらつきの精度

# 目次と前回の記事

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

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

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

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

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

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

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

# 深さの上限と評価値の近似値の精度の関係

前回の記事では、深さ制限探索で __深さの上限を上げる__ と __精度が高くなる理由__ には以下のようなものがあることを示しました。ただし、静的評価関数が決着がついた局面の評価値を正確に計算できるものとします。

* 深さの上限を上げると、正確な評価値を計算できる __決着がついた局面__ を静的評価関数が __計算する割合が増える__ ため
* 深さの上限を上げると、__より多くの着手が行われた局面__ に対して静的評価関数が評価値を計算することになる。__一般的__ に __着手が行われるほど形勢を判断しやすくなる__ ので __評価値の精度が上がる__

ただし、これらは __決着がつくまでに長い手数がかかる__ オセロや将棋などの __ゲームの序盤__ では __あてはまりません__ ので、今回の記事では他の理由について説明します。

今回の記事からしばらくは、〇×ゲームのような小規模なゲーム木ではなく、オセロや将棋のような __ノードの数__ が現実的な時間で __計算しきれないほど多いゲーム木__ に対する深さ制限探索について説明します。

## 用語の整理

これまでは、ミニマックス値の近似値という用語を、静的評価関数が計算した評価値と、深さ制限探索で計算された評価値の両方の場合で使用してきましたが、記事を書いていて自分でも混乱しましたので、以後は以下の用語を使うことにします。

本記事では __静的評価関数が計算する評価値__ のことを、深さの制限のないゲーム木の探索によって計算されるミニマックス値とは異なる __不正確な値が計算される場合がある__ ことから、__近似値と表記__ することにします。

__深さ制限探索__ によって計算されるミニマックス値は、静的評価関数が計算する近似値を元に計算されるので __近似値のミニマックス値__ と表記することにし、深さの制限のないゲーム木の探索によって計算される値を __正確なミニマックス値__ と表記することにします。なお、__深さの上限を 0__ とした場合は、__近似値__ と __近似値のミニマックス値__ は __同じ意味__ を表します。

なお、__一般的__ には上記のような用語の区別は行わず、AI が何らかのアルゴリズムで計算した __局面の状況を表す数値__ の事を単に __評価値__ と呼び、強解決な AI でない限り評価値は誤差を持ちます。

# 近似値のミニマックス値の精度の定義

深さ制限探索で深さの上限を上げると近似値のミニマックス値の精度が高くなる理由について説明するためには、__精度の意味を明確にする__ 必要があります。そこで、本記事における近似値のミニマックス値の __精度を定義__ することにします[^1]。

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

最初に __静的評価関数__ が __どのような近似値を計算するか__ について決めることにします。

### 決着がついた局面の計算

__決着がついた局面__ は、ゲームのルールから局面の状況を正確に計算することができるので、静的評価関数は決着がついた局面の __正確なミニマックス値を計算する__ ものとします。

### 近似値のデータ型

__深さ制限探索__ では、スカウト法などの __null window search  を利用__ する探索アルゴリズムをベースとすることがあります。null window search を行うためには、計算される __評価値が整数であることが望ましい__ ので、静的評価関数が __整数の近似値を計算する__ ことにします。

### 近似値の範囲と引き分けの除外

多くのゲームの AI では、静的評価関数が計算する __近似値の範囲__ を[以前の記事](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%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%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E6%80%A7%E8%B3%AA)で説明したように __大きな正の整数__ $\boldsymbol{s}$ を決め、近似値を __下記の表のように計算__ します。なお、最短の勝利と最遅の敗北を目指す場合は下記の表と若干異なりますが、話を簡単にするために以後の説明では __最短の勝利と最遅の敗北を目指さない場合__ を説明します。

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

上記の表からわかるように、__近似値として 0 が計算__ された場合は、決着がついた引き分けの局面、引き分けと正確に判定できる局面、互角だと判定する局面の __3 種類がある点が複雑__ です。そこで、以後は説明を簡単にするために、__引き分けがないゲームの場合の説明__ を行うことにします。下記は上記の表の修正版です。なお、引き分けがあった場合でも深さの上限を上げると精度が高くなることに変わりはないと思います。

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

近似値は、正の値で大きいほど先手が有利、負の値で小さいほど後手が有利、0 に近いほ互角であると静的評価関数がみなしていることを表します。

__将棋の AI の評価値__ の多くは -32768 ~ 32767 の整数を表現できる 2 バイトの __整数で表現されている__ ようで、その場合は $\boldsymbol{s}$ に __約 30000 という大きな値が設定__ されているようです。

本記事では具体的な $s$ は設定しませんが、上記の表のような近似値を静的評価関数が計算することにします。

:::note
将棋の AI が計算する評価値の範囲は 約 -30000 ~ 約 30000 と幅広いようですが、その数値の意味の目安は以下のように考えられているので、ほぼ互角を意味する評価値の範囲は -300 ~ 300 のようにかなり狭いようです。また、強い AI どうしが対戦した場合に、評価値が先手の優勢になると、ほぼ確実に先手が勝利するようです。

|評価値|目安|
|:--|:--|
|1000 以下 | 後手が勝勢 |
|-700 ~ -600|後手が優勢|
|-300 前後| 後手が有利|
|0 前後|互角|
|300 前後| 先手が有利|
|600 ~ 700|先手が優勢|
|1000 以上 | 先手が勝勢 |

約 -30000 ~ 約 30000 という評価値はわかりづらいので、評価値に計算を行う[^2]ことで 0 ~ 1 の範囲に置き換えて 59 % のようにパーセントで表記することがよくあります。0 % に近いほど後手が有利、50 % に近いほど互角、100 % に近い程先手が有利であることを意味します。なお、小数点以下の数値は四捨五入して表示しますが、どちらかが必勝の局面であることが判明していない場合に 0 % や 100 % と表記すると誤解が生じるため、その場合は 1 % や 99 % と表記するのが一般的なようです。

パーセントで評価値が表示された場合に、その値を 80 % の確率で先手が勝利するという、先手の勝率の意味だと誤解している人が多いのではないかと思いますが、この数字は勝率を表す値ではありません。80 % という数字は有利さの目安を表す数字だと考えて下さい。100 点満点の 80 点のように考えると良いかもしれません。
:::

## 静的評価関数の近似値の誤差の精度

__[二人零和有限確定完全情報ゲーム](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E6%80%A7%E8%B3%AA%E3%81%AE%E5%88%B6%E9%99%90)__ は、すべての __局面の状態__ が「先手の勝利の局面」、「引き分けの局面」、「後手の勝利の局面」の __3 種類のいずれかに分類__ されます。先程 __引き分けがない__ ことにしたので、その場合はそれぞれの局面の状態の __正確なミニマックス値__ は、最短の勝利を目指さない場合は $-s-1$、$s+1$ のように __2 種類の整数で表現__ できます。

ただし、__ほとんどの局面__ では、その __局面の情報だけから__ その局面が __どの状況であるかを判断__ することは __不可能__ です。そのため、静的評価関数はゲームの決着がついていない局面では様々な計算を行うことで、その局面が __先手にとってどれだけ有利であるか__ を表す $-s$ ~ $s$ という __幅広い範囲の近似値を計算__ します。別の言葉で説明すると、__引き分けの無いゲーム__ の場合の __正の近似値__ は、その局面が __先手の必勝の局面__ であることを静的評価関数が __どれだけ自信をもって判定しているかを表す__ と考えることができます。

静的評価関数の __近似値の精度__ は、そうして計算された __近似値__ とその局面の __正確なミニマックス値の間の誤差__ で表されます。__誤差が少ないほど精度が高く__、誤差が 0 の場合に精度が 100 % になります。この後で説明するもう一つの精度と区別するため、以後はこの精度の事を __近似値の誤差の精度__ と表記することにします。

ただし、この __近似値の誤差は一定ではなく__、局面の __形勢判断が困難であるほど大きく__ なるため、__近似値の誤差__ は局面の __形勢判断の困難さによって決まる__ と考えることができます。具体的には、先手の必勝の局面の場合は __形勢判断が困難であるほど__ $s$ からの __誤差が大きくなる__ ので __0 に近い近似値__ や、形勢判断を間違った場合は負の近似値が計算されます。

従って、__近似値の誤差の精度が高い__ 静的評価関数は、精度が低い静的評価関数と比べて、__形勢判断の難しさが同程度__ の局面に対して計算される __近似値の誤差が少ない__ と言い換えることができます[^3]。

:::note
一般的にゲームの序盤の局面は形勢判断が難しいため誤差が大きく、終盤の局面は形勢判断が簡単なので誤差は小さくなります。

例えば、現状で存在するどの将棋の AI も、ゲーム開始時の局面の評価値はわずかに先手が有利であることを表す小さな正の整数を近似値として計算するようです。将棋のゲーム開始時の局面がどの状況の局面であるかはまだ判明していませんが、一般的に将棋は先手のほうが有利なゲームだと考えられています。もし将棋が先手の必勝のゲームであれば、ゲーム開始時の局面の正確なミニマックス値は $s$ になるはずなので非常に大きな誤差が発生していることになります。

囲碁には引き分けはないので、ゲーム開始時の局面は先手の必勝または後手の必勝の局面のどちらかです。しかし、現状で存在するどの囲碁の AI もゲーム開始時の局面の評価値はほぼ 0 に近い近似値を計算するようなのでその誤差は $s$ という大きな値になります。

これらのことから、将棋や囲碁のゲームの開始時の局面は最も形勢判断が困難な局面の一つであると言えるのではないかと思います。

なお、将棋には引き分けがあるので、将棋が引き分けのゲームであればゲーム開始時の局面の誤差はほとんどないことになりますが、ゲーム開始時の局面の形勢判断が困難であることは間違いないでしょう。先程引き分けを除外した理由は、引き分けの局面の誤差の性質が、それ以外の状況の局面の誤差と大きく異なるからです。
:::

## 形勢判断の難しさを判定する仮想的な関数

残念ながら __局面の形勢判断の難しさ__ を __正確に判定する方法はありません__ が、現状で存在する __強い将棋や囲碁の AI__ が、__同じ局面__ に対して __似たような評価値を計算する__ ことを考えると、__局面の形勢判断の難しさ__ というものが __実際に存在する__ ことは間違いなさそうです[^4]。また、将棋や囲碁などでプロ棋士が __この局面は難解な局面__ であり、__どちらが優勢かを判断することができない__ という解説を行うことが実際に良くあります。そこで、本記事では __形勢判断の難しさを正確に判定__ できる以下のような __関数が存在すると仮定__ し、その __仮想的な関数__ を使って説明を行うことにします。

* 局面の形勢判断の難しさを、ある程度以上大きな正の整数である m 段階[^5]で判定し、__0 ~ m の整数__ を計算する __関数が存在する__ ものとする。__一定範囲の整数とした理由__ は、m を無限大にしたり、難しさを実数で表すと __同じ難しさの局面が 1 または数個しか存在しない__ ことになってしまい、この後で説明する __ばらつきが生じなくなってしまう__ からである
* 形勢判断の難しさは __0 が最も簡単__ で、__大きくなるほど難しい__ ものとする。ゲームの決着がついた局面は必ず形勢判断を正確にできるので難しさは 0 である

## 近似値のばらつきの精度

__先手の必勝__ の局面と __後手の必勝__ の局面で計算される __近似値が異なりますが__、その __性質はほぼ同じ__ なので、以後は __先手の必勝の局面での説明__ を行うことにします。

__理想的__ には、静的評価関数は __形勢判断が同じ難しさの局面__ に対して __同じ誤差の近似値__ を計算するべきですが、そのような静的評価関数を定義することは __現実的に不可能__ です。具体的には、先手の必勝局面で __形勢判断の難しさ__（difficulty）が $\boldsymbol{d}$ の局面を集めた __局面の集合を__ $\boldsymbol{N(d)}$ と表記すると、$N(d)$ の局面に対して計算される __近似値__ には __ばらつきが生じます__。これは、__プロの棋士__ であっても __形勢判断を常に正しく行うことができない__ 点に似ています。実際にプロの棋士が __形勢判断が簡単な局面で形勢判断を大きく誤る__ ことがあるように、精度の高い静的評価関数であっても __形勢判断が簡単な局面__ で __大きな誤差の近似値を計算__ することがあります。

そこで、本記事では $N(d)$ の局面に対して計算される近似値の __平均値__ と正確なミニマックス値との誤差を、__形勢判断の難しさが__ $\boldsymbol{d}$ の局面に対して計算される __近似値の精度__ とみなすことにします。また、その平均値を平均を表す英単語の mean の頭文字を取って $\boldsymbol{M(d)}$ と表記することにします。__近似値の精度が高い__ と同じ $d$ に対して $M(d)$ の正確なミニマックス値に対する __誤差が小さくなる__ ということです。

静的評価関数の精度には、誤差の精度以外に $N(d)$ の局面に対して計算された __近似値のばらつき__ があり、__ばらつきが少ない__ ほうが $M(d)$ に近い値が計算されやすいので __ばらつきの精度が高い__ と表記します。毎回「$N(d)$ の局面に対して計算された近似値のばらつき」と表記するのは長いので、以後は __近似値のばらつき__ のように短く表記することにします。 

__近似値のばらつきの精度__ は、誤差の精度と同様に __AI の強さに大きな影響__ を及ぼします。その理由について少し考えてみて下さい。

## 局面の状況の判定の正しさと誤差とばらつきの精度の関係

静的評価関数が、__先手の必勝__ の局面に対して __正の近似値__ を、__後手の必勝__ の局面に対して __負の近似値__ を計算した場合は __その局面の状況を正しく判定__ できています。従って、深さ制限探索で静的評価関数が近似値を計算する __すべてのノードでそのような計算が行われた場合__ は、__正確なミニマックス値が $s$ である最善手を選択__ することができます。

一方、__先手の必勝__ の局面に対して負の __近似値が計算__ された場合や、__後手の必勝__ の局面に対して __負の近似値が計算__ された場合は、__その局面の状況を正しく判定できていない__ ので、深さ制限探索で __最善手以外の合法手が選択される可能性__ が生じます。

静的評価関数が先手の必勝の局面の状況の __判定を間違える__ のは、$\boldsymbol{M(d)}$ __よりも大きなばらつき__ で近似値が __小さく計算された場合__ です。従って下記の理由から、近似値の __誤差の精度__ と、近似値の __ばらつきの精度が高い__ と静的評価関数が局面の状況を __正しく判定できる可能性が高くなり__、結果として __最善手が計算される可能性が高く__ なります。

* 近似値の __誤差の精度が高い__ 場合は、$M(d)$ は $s$ に近くなるので __大きな値になる__
* $M(d)$ が __大きな値であればあるほど__、__大きなばらつきが生じない限り__ 局面の状況を __正しく判定できる__
* 一般的に __大きなばらつきが起きる確率__ は、小さなばらつきが起き確率よりも __低い__ ので、$M(d)$ が __大きな値であればあるほど__ 間違った判定となる __負の近似値が計算される確率が低くなる__
* 近似値の __ばらつきの精度が高い__ 場合は、__大きなばらつき__ が起きる __確率が低くなる__
* そのため、ばらつきの精度が高い場合は、$M(d)$ __が小さくても__ 間違った判定となる __負の近似値が計算される確率が低くなる__

上記から、__誤差の精度__ と、__ばらつきの精度__ の __両方__ が静的評価関数が __局面の状況を正しく判定できるかどうかに大きく関わる__ ことがわかります。

### 局面の状況を正しく判定できることの重要性

静的評価関数が局面の状況を判定できず、最善手以外の合法手を選択した場合は、二人零和有限確定完全情報ゲームの __勝率に大きな影響__ を及ぼします。その理由は、[以前の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E6%84%8F%E5%91%B3%E3%81%AE%E6%9C%80%E5%96%84%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%AE%E9%81%95%E3%81%84)で説明したように、__最善手以外の着手__ を行うと __局面の状況が必ず悪化__ し、__相手が常に最善手を着手し続けた場合__ は、__局面の状況が好転することは決してない__ からです。このように、二人零和有限確定完全情報ゲームは __一度のミス__ を犯すことが __致命的な結果をもたらすゲーム__ であり、相手が弱ければ相手が最善手を着手しないことで状況が好転することはありますが、__相手が強ければ強いほど一度のミスが敗北につながってしまいます__。

この性質は、局面の状況を表す正確なミニマックス値だけでなく、__近似値のミニマックス値でも同様__ で、近似値のミニマックス値が __減るような合法手を選択__ すると、__相手がミスをしない限り__ 近似値のミニマックス値が __増えることは基本的にはありません__。

この性質は、__ミニマックス法の計算方法から明らか__ です。ミニマックス法では max ノードの評価値を子ノードの評価値の最大値で計算するので、どの合法手を選択してもその子ノードの評価値は __必ず親ノードの評価値以下の値__ になります。将棋などで良く言われる __良い手__ とは、それによって局面が直接有利になる手ではなく、__相手がミスをしやすい局面にする__ ことで、__相手のミスを誘うことで自分が有利になる__ ような着手の事を意味します。

:::note warn
__静的評価関数__ の __近似値の精度__ には、__誤差の精度__ と __ばらつきの精度__ があり、その __両方が重要__ である。

__誤差の精度が高い__ ほど、局面の状況を __正しく判定できる可能性が高くなる__。

__ばらつきの精度が高い__ ほど、誤差の精度が低くても局面の状況を __正しく判定できる可能性が高くなる__。
:::

静的評価関数の誤差の精度を上げることは簡単ではありませんが、この後で説明するように __ばらつきの精度__ は __深さ制限探索の深さの上限を上げる__ ことで __高めることができます__。

### ばらつきが小さいことの重要性

ばらつきがあっても静的評価関数が局面の状況を正しく判定できる場合でも、__ばらつきは小さいほうが望ましい__ と言えます。その理由は、ばらつきによって $M(d)$ から離れた近似値が計算された結果、ばらつきがなく $M(d)$ が近似値として計算された場合に選択される最善手よりも __形勢判断が難しい局面になる最善手が計算される場合がある__ からです。__形勢判断が容易な局面ほど__、__次の手番__ での局面の状況を __正しく判定できる可能性が高まります__。

## ばらつきの指標

__複数の数値データ__ の __ばらつきを表す指標__ に __標準偏差__ があります。本記事では __標準偏差を利用__ して、深さの上限を大きくした場合に近似値の __ばらつきの精度が上がることを説明__ するので、標準偏差について説明します。

### 標準偏差とは何か

__標準偏差__（standard deviation）とは __データの散らばり具合__ を表す __統計学や確率論の用語__ で、__大きいほど__ データが __散らばっており__、__0 の場合__ はデータが __散らばっていない__、すなわち __すべてのデータが同じ値__ であることを表します。

__標準偏差を計算__ するためには、__平均__ と __分散__ を計算する必要があります。__平均__ は良く使われる概念なので知っている人が多いと思いますが、$n$ 個のデータを $x_1$、$x_2$、・・・、$x_n$ と表記すると、それらの __合計を__ $\boldsymbol{n}$ __で割った下記の式__ で計算できます。なお、数学では平均を $\boldsymbol{\bar{x}}$ のように記述します。

$\bar{x} = \frac{1}{n}\sum_{i=1}^{n}x_i$

__分散__（variance） はそれぞれの __データと平均の差の 2 乗__ の __合計の平均__ で、分散を $v$ と表記すると下記の式で計算できます。

$v = \frac{1}{n}\sum_{i=1}^{n}(x_i - \bar{x})^2$

分散には下記のような性質があり、__すべての値が等しく__、値が全く散らばっていない場合は __0 が計算__ されます。

* 平均との差の 2 乗を計算することで、__それぞれの値__ に対して __0 以上の値が計算__ される
* __すべての値が同じ場合__ は、すべての値がが __平均と等しくなる__ ので、__分散は 0__ となる

__標準偏差__ は、__分散の平方根__ を計算します。標準偏差を $s$ と表記すると下記の式で計算できます。

$s = \sqrt{v}$

__分散は 2 乗を計算__ するので、__平均との差が大きな値が存在__ すると __非常に大きな値__ になりますが、分散の __平方根を計算__ することで平均との差が大きな値が存在しても __標準偏差は分散のような大きな値にはなりません__。

分散と標準偏差には他にも様々な重要な性質がありますが、説明すると非常に長くなるのでそれらについては必要になった時点で説明することにします。参考までに分散と標準偏差の Wikipedia のリンクを下記に紹介しますので興味がある方は勉強してみて下さい。

https://ja.wikipedia.org/wiki/%E5%88%86%E6%95%A3_(%E7%A2%BA%E7%8E%87%E8%AB%96)

https://ja.wikipedia.org/wiki/%E6%A8%99%E6%BA%96%E5%81%8F%E5%B7%AE

### データの分布による標準偏差の比較

標準偏差がどのような性質を持つかを示すために、__いくつかのデータの集合__ の __標準偏差を比較__ します。

-2, 1, 0, 1, 2 という 5 つのデータの平均、分散、標準偏差は下記のようになります。また、このデータの値ごとの数を表すグラフは下記のようになります。このような値に応じたデータの数を表すグラフの事を __ヒストグラム__ （度数分布図）と呼びます。

$\bar{x} = (-2 + -1 + 0 + 1 + 2) ÷ 5 = 0$

$v = ((-2)^2 + (-1)^2 + 1^2 + 2^2) ÷ 5 = 2$

$s = \sqrt{2} = 1.414$

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/eeff6e22-d8db-4d91-9708-7b451a46719f.png" width="300">

-1, 0, 0, 0, 1 のデータの平均、分散、標準偏差、ヒストグラムは下記のようになります。

$\bar{x} = (-1 + 0 + 0 + 0 + 1) ÷ 5 = 0$

$v = ((-1)^2 + 1^2) ÷ 5 = 0.4$

$s = \sqrt{0.4} = 0.632$

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2fd3456e-52ad-4145-8312-1c8b84983f46.png" width="300">

0, 0, 0, 0, 0 のデータの平均、分散、標準偏差、ヒストグラムは下記のようになります。

$\bar{x} = (0 + 0 + 0 + 0 + 0) ÷ 5 = 0$

$v = 0 ÷ 5 = 0$

$s = \sqrt{0} = 0$

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7edbf468-9405-4c61-b015-db4fa0bb8668.png" width="300">

下記は上記の結果を表にまとめたものです。3 種類のデータの集合の __平均値はいずれも 0__ ですが、__標準偏差__ はヒストグラムからわかるように、データが平均値に近い値が多く、平均値からの __ばらつきが少ない程小さく__ なり、__すべての値が同じ場合は 0__ になります。

|データ|$\bar{x}$|$v$|$s$|
|:--|--:|--:|--:|
| __-2, 1,0, 1, 2__ | 0 | 2.0 | 1.414 |
| __-1, 0, 0, 0, 1__ | 0 | 0.4 | 0.632 |
| __0, 0,0, 0, 0__ | 0 | 0.0 | 0.000 |

:::note
matplotlib では `hist` という関数でヒストグラムを描画することができます。下記は、上記の 3 つのヒストグラムを表示するプログラムです。

それぞれのヒストグラムで縦軸の範囲を統一するために、`plt.ylim(0, 6)` で y 軸の表示範囲を 0 ~ 6 に設定しています。

`hist` の最初の実引数にデータを表す list を、キーワード引数 `range` にヒストグラムで表示するデータの範囲を、`bins` にデータの範囲内を区切る数を記述します。ヒストグラムは区切られた範囲に含まれるデータの数を棒グラフのように表示します。

下記では、ヒストグラムで表示するデータの範囲を -2.5 から 2.5 とし、その区間を 5 つに分割したヒストグラムを表示しています。-2.5 ~ 2.5 の範囲を 5 つに分割すると、-2.5 ~ -1.5、-1.5 ~ -0.5、-0.5 ~ 0.5、0.5 ~ 1.5、1.5 ~ 2.5 の 5 つの範囲に分割され、それらの中に -2, -1, 0, 1, 2 の数値が含まれるので、分割された部分にそれぞれの数値の個数を表すヒストグラムのグラフが表示されます。

```python
import matplotlib.pyplot as plt

plt.ylim(0, 6)
plt.hist([-2, -1, 0, 1, 2], range=(-2.5, 2.5), bins=5)
plt.show()
plt.ylim(0, 6)
plt.hist([-1, 0, 0, 0, 1], range=(-2.5, 2.5), bins=5)
plt.show()
plt.ylim(0, 6)
plt.hist([0, 0, 0, 0, 0], range=(-2.5, 2.5), bins=5)
plt.show()
```

ヒストグラムの Wikipedia の記事を参考までに下記に紹介します。また、matplotlib の `hist` の詳細については下記のリンク先を参照して下さい。
:::

https://ja.wikipedia.org/wiki/%E3%83%92%E3%82%B9%E3%83%88%E3%82%B0%E3%83%A9%E3%83%A0

https://matplotlib.org/stable/api/_as_gen/matplotlib.axes.Axes.hist.html

# 深さの上限と標準偏差の関係

__深さの上限を増やす__ ことで、__近似値のばらつき__ を表す __標準偏差が減る__ ことを具体例を挙げて説明します。

なお、ゲームの決着がついた局面に対して静的評価関数は必ず正確なミニマックス値を計算することができるので、ばらつきは生じません。ばらつきが減ることを示す際に __その性質は邪魔になる__ ので、話を簡単にするために以後の説明では静的評価関数が __ゲームの決着がついた局面の評価値を計算しない__ ものとします。

## 静的評価関数の設定

計算を簡単にするために、__静的評価関数__ が __下記のような近似値を計算__ するものとします。

形勢判断の難しさが $d$ の局面の集合 $N(d)$ に対して計算される近似値の平均値を $M(d)$ とした場合に、__任意の $\boldsymbol{N(d)}$__ の局面に対して __下記の割合で近似値を計算する__。

* $M(d)$ を近似値として計算する割合が最も高い
* $i$ を自然数とした場合に $M(d) + i$ が近似値として計算される割合は、$i$ が大きくなるほど小さくなる
* $M(d) + i$ と $M(d) - i$ が近似値として計算される割合は同じである
* $d$ が異なっていても、すべての整数 $i$ に対して $M(d) + i$ が近似値として計算される割合は同じである

上記のような説明は非常に分かりづらいと思いますので、別の言葉で説明すると以下のようになります。

* $N(d)$ の中で近似値の __平均値__ である $M(d)$ が計算される __局面が最も多い__
* __平均値に近い値であるほど__、近似値としてその値が計算される __局面が多い__
* __平均値との差が同じ__ であれば、近似値としてその値が計算される __局面の数は同じである__
* __形勢判断の難しさが異なっていても__、$M(d) + i$ が計算される __割合は同じである__

具体例としては下記のような設定が考えられます。

|近似値|$M(d) -2$|$M(d) -1$ |$M(d)$|$M(d) + 1$|$M(d)+2$|
|:--|--:|--:|--:|--:|--:|
| 局面の割合|5%|20%|50%|20%|5%|

この設定で $M(d)$ が 0、$N(d)$ のノードの数が 100 の場合は、下記の表のようになります。

|近似値|-2|-1|0|1|2|
|:--|--:|--:|--:|--:|--:|
| 局面の数|5|20|50|20|5|

上記をヒストグラムで表示すると下記のような性質を持つ、下図のような __左右対称__ な __山形のグラフ__ になります。

* 平均値が最も多い
* 平均値から離れると少なくなる
* 平均値を軸に左右対称である

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3a1fff16-ca62-4a37-b3c6-4fbb84d82b10.png" width="300">

この設定で `d` とは別の局面の難しさ `d'` に対する $M(d')$ が -1、$N(d')$ に属するノードの数が 1000 の場合は下記の表のようになります。

|近似値|-3|-2|-1|0|1|
|:--|--:|--:|--:|--:|--:|
| 局面の数|50|200|500|200|50|

下記はそのヒストグラムで、__平均値からの差で割合が決まる__ ので、ヒストグラムの __形状は全く同じ__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/91010207-d56b-445f-b2a7-da319e428b1a.png" width="300">

:::note
ヒストグラムで、データごとの数（度数と呼びます）を指定したい場合は、下記のプログラムのようにキーワード引数 `weight` を使ってそれぞれのデータの数を記述します。下記のプログラムは上記の 2 つのヒストグラムを表示するプログラムです。

```python
plt.hist([-2, -1, 0, 1, 2], weights=[5, 20, 50, 20, 5], 
         range=(-2.5, 2.5), bins=5)
plt.show()
plt.hist([-3, -2, -1, 0, 1], weights=[50, 200, 500, 200, 50],
         range=(-3.5, 1.5), bins=5)
plt.show()
```
:::

### 設定の理由

当然ですが、__現実の静的評価関数__ は上記の設定とは __異なる性質__ を持ちます。そのため、本記事の説明は __すべての静的評価関数に当てはまるわけではありません__ が、下記で説明する理由から、__精度が高い静的評価関数__ は __おおむね上記の設定を満たす__ と考えることができると思います。

__静的評価関数__ を上記のように設定した理由は、__平均値の数が一番多く__、__平均値から離れるほど数が少なく__、平均値を中心として __左右対象__ な __データの分布__ は、同じテストを受けた学生のテストの点数の分布のように、__同じ種類のデータを複数計測__ した際に得られるデータで実際に __よく見られるからです__。

また、実際の静的評価関数が上記のような性質を正確に満たすことはありませんが、__ばらつきの精度が小さくなるほど__ ほとんどのデータが __平均値に近い値になっていく__ ので __上記の性質に近く__ なります。

:::note
このようなデータの分布として正規分布と呼ばれる分布が有名です。正規分布については次回の記事で紹介する予定です。
:::

実際には形勢判断が優しいほど計算される近似値のばらつきが減る傾向があるので、__形勢判断の難しさが異なっていても__ $M(d) + i$ が計算される __割合は同じである__ という設定が __満たされることはありません__。特にゲームの決着がついた局面は必ず正確なミニマックス値を計算できるのでばらつきは生じません。ただし、__形勢判断の難しさがあまり変わらなければ__、計算される近似値の __ばらつきはほぼ同じである__ と考えることができます。その点と、計算のしやすさを考慮して設定を決めました。

### 確率分布の期待値と標準偏差

先程の表は、__近似値の平均値との差__ を使って下記の表のように書き直すことができます。

|近似値の平均との差|-2|-1|0|1|2|
|:--|--:|--:|--:|--:|--:|
| __局面の割合__ |5%|20%|50%|20%|5%|

この表の近似値の平均との差のような、__特定の値に応じた確率が存在する変数__ のことを __確率変数__ と呼び、数学では $\boldsymbol{X}$ のように __大文字で表記__ します。$X$ を __大文字で表記__ するのは、$X$ が __複数の数値の集合__ であることを意味します。

__確率変数__ と __対応する確率__ をまとめたものを __確率分布__ と呼び、$\boldsymbol{X}$ __の要素__ である $\boldsymbol{x_i}$ __に対応する確率__（probability）の事を $\boldsymbol{P(x_i)}$ または、$\boldsymbol{p_i}$ と表記します。また、__確率は必ず合計が 1__ となるので、$X= x_1, x_2, ..., x_n$ の場合は $\boldsymbol{\sum_{i=1}^{n}p_i = 1}$ となります。

__確率分布__ に対しても __平均__、__分散__、__標準偏差__ を計算することができ、__標準偏差__ は先ほどと同様に __データの分布のばらつき__ を表します。

__確率分布__ では __平均値__ のことを __期待値__（expectation value）と呼び、$\boldsymbol{E(X)}$ または $\boldsymbol{μ}$（ミュー）と表記します。

$X= x_1, x_2, ..., x_n$ の場合に __期待値__ は下記の式で計算できます。

$E(X) = μ = \sum_{i=1}^{n}x_{i}p_i$

確率分布の __分散__（variation）は $\boldsymbol{V(X)}$ と表記し、下記の式で計算できます。

$V(X) = \sum_{i=1}^{n}(x_{i} - μ)^2p_i$

確率分布の __標準偏差__ は $\boldsymbol{σ(X)}$[^6]と表記し、先程と同様に __分散の平方根__ で下記の式で計算できます。

$σ(X) = \sqrt{V(X)}$

下記は上記の表の確率分布の __期待値__、__分散__、__標準偏差__ の計算です。

$μ = (m - 2) × 0.05 + (m - 1) × 0.2 + m × 0.5 + (m + 1) × 0.2 + (m + 2) ×0.5 = m$

$V(X)= (-2)^2 × 0.05 + (-1)^2 × 0.2 + 0^2 × 0.5+ 1^2  × 0.2+ 2^2 × 0.05 = 0.8$

$σ(X) = \sqrt{0.8} = 約 0.89$

上記から、先程の表の確率分布で近似値の計算を行う静的評価関数が計算する __近似値のばらつき__ を表す __標準偏差が約 0.89__ になることがわかります。

## 深さの上限によるばらつきの違いの比較方法

上記で説明した標準偏差を利用して、__形勢判断の難しさが同じ__ 局面に対して計算される __近似値のばらつき__ が、深さ制限探索で __深さの上限を上げると減る__ ことを __具体例を挙げて示す__ ことにします。

__形勢判断の難しさが同じ__ 局面に対して計算される __近似値の平均値が__ $\boldsymbol{s}$ となる局面の集合を $\boldsymbol{N_{mean}(s)}$ と表記することにします。$\boldsymbol{N_{mean}(s)}$ は __近似値のばらつきがなくなる__ ように __改良した静的評価関数__ が計算する評価値と考えることができます。

具体的には、$\boldsymbol{N_{mean}(0)}$ の局面の近似値を __深さの上限が 0 と 1__ の深さ制限探索で計算した場合の __標準偏差を計算して比較__ し、深さの上限を 1 としたほうが標準偏差が減って __ばらつきが減る__ ことを示します。

また、静的評価関数は先程と同様に下記の表の設定で近似値を計算するものとします。

|近似値の平均との差|-2|-1|0|1|2|
|:--|--:|--:|--:|--:|--:|
| __局面の割合__ |5%|20%|50%|20%|5%|

## 深さの上限が 0 の場合の標準偏差

$\boldsymbol{N_{mean}(0)}$ の局面の評価値を __深さの上限が 0__ の深さ制限探索で計算するということは、その局面の近似値を __静的評価関数で直接計算__ するということです。その場合の近似値の期待値（平均値）と標準偏差は、先程計算した値と同じになるので、下記の表のようになります。

||期待値|標準偏差|
|:--|--:|--:|
|__深さの上限が 0__ | 0 | 0.89 |

## 深さの上限が 1 の場合の標準偏差

次に、max ノードの場合で、下図のような __深さが 1__ で子ノード A、B があるゲーム木のルートノード N の __近似値のミニマックス値__ を静的評価関数で計算した場合の __標準偏差を計算__ することにします。黒丸が max ノード、赤丸が min ノードを表し、〇の中の数字はばらつきがない場合に静的評価関数が計算する近似値を表します。__ばらつきない場合__ の静的評価関数で __近似値を計算した際__ に $\boldsymbol{N_{mean}(0)}$ である __ノード N の近似値が 0 となる__ ように、2 つの子ノードは $\boldsymbol{N_{mean}(0)}$ と $\boldsymbol{N_{mean}(-1)}$ のノードとしました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ec514956-c5da-4694-ba5e-939d957938b5.png" width="300">

$\boldsymbol{N_{mean}(0)}$ である __ノード A の近似値__ は下記の表の確率分布で計算されます。

|近似値|$-2$|$- 1$|$0$|$1$|$2$|
|:--|:-:|:-:|:-:|:-:|:-:|
|__確率__|5%|20%|50%|20%|5%|

$\boldsymbol{N_{mean}(1)}$ である __ノード B の近似値__ は下記の表の確率分布で計算されます。

|近似値|$-3$|$-2$|$-1$|$0$|$1$|
|:--|:-:|:-:|:-:|:-:|:-:|
|確率|5%|20%|50%|20%|5%|

$N_{mean}(0)$ である __ノード N__ の __近似値のミニマックス値__ の __確率分布を計算__ するためには、ノード A と ノード B で計算される __近似値のすべての組み合わせ__ と __その確率を計算__ する必要があります。下記は __すべての組み合わせ__ で計算される __ルートノードの近似値とその確率__ を計算した表です。

|ノード A|ノード B|ノード N|確率の計算式|確率|
|--:|--:|--:|--:|--:|
|-2|-3|-2|0.05*0.05|0.0025|
|-2|-2|-2|0.05*0.20|0.0100|
|-2|-1|-1|0.05*0.5|0.0250|
|-2|0|0|0.05*0.20|0.0100|
|-2|1|1|0.05*0.05|0.0025|
|-1|-3|-1|0.2*0.05|0.0100|
|-1|-2|-1|0.2*0.20|0.0400|
|-1|-1|-1|0.2*0.5|0.1000|
|-1|0|0|0.2*0.20|0.0400|
|-1|1|1|0.2*0.05|0.0100|
|0|-3|0|0.5*0.05|0.0250|
|0|-2|0|0.5*0.20|0.1000|
|0|-1|0|0.5*0.5|0.2500|
|0|0|0|0.5*0.20|0.1000|
|0|1|1|0.5*0.05|0.0250|
|1|-3|1|0.2*0.05|0.0100|
|1|-2|1|0.2*0.20|0.0400|
|1|-1|1|0.2*0.5|0.1000|
|1|0|1|0.2*0.20|0.0400|
|1|1|1|0.2*0.05|0.0100|
|2|-3|2|0.05*0.05|0.0025|
|2|-2|2|0.05*0.20|0.0100|
|2|-1|2|0.05*0.5|0.0250|
|2|0|2|0.05*0.20|0.0100|
|2|1|2|0.05*0.05|0.0025|

上記のような、__複数の集合の中__ から __1 つずつ要素を取り出し__ た場合の __すべての組み合わせの事__ を __直積__ またはデカルト積と呼びます。参考までに Wikipedia の直積に関する項目のリンクを下記に紹介します。

https://ja.wikipedia.org/wiki/%E7%9B%B4%E7%A9%8D%E9%9B%86%E5%90%88

上記の表から、__ノード N のそれぞれの近似値__ が計算される __確率を計算__ すると下記の表のようになります。また、式は省略しますが __期待値と標準偏差を計算__ し、__深さの上限が 0__ の場合と __比較できる__ ようにしました。

|評価値|-2|-1|0|1|2|期待値|標準偏差|
|:--|--:|--:|--:|--:|--:|--:|--:|
|__深さの上限が 1__|1.25%|17.5%|52.5%|23.75%|5%|0.1375|0.80|
|__深さの上限が 0__|5.00%|20.0%|50.0%|20.00%|5%|0|0.89|

上記から、__深さの上限を 1__ とすることで、実際に __標準偏差が少し減る__ ことが確認できます。一方で、__期待値が少し増える__ という問題があることもわかります。

:::note
2025/06/21 修正

確率分布のグラフのことをヒストグラムと表記していましたが、__ヒストグラム__（度数分布図）の __縦軸は個数を表す__ ので、__縦軸が__ 個数ではなく __割合を表す__ 確率分布のグラフをヒストグラムとするのは間違いだと思いましたので修正しました。
:::

下図は 2 つの確率分布のグラフを重ねて表示するプログラムです。__重ねて表示__ すると __最初に表示したグラフが見えなくってしまう__ ので、深さの上限が 1 の場合のグラフを表示する際に __グラフの透明度__ を表す __キーワード引数 `alpha`__ を記述して後ろが __透けて見える半透明なグラフ__ を表示しました。

```python
import japanize_matplotlib

plt.hist([-2, -1, 0, 1, 2], weights=[0.05, 0.2, 0.5, 0.2, 0.05], 
         range=(-2.5, 2.5), bins=5, label="深さの上限が 0")
plt.hist([-2, -1, 0, 1, 2], weights=[0.0125, 0.175, 0.525, 0.2375, 0.05],
         range=(-2.5, 2.5), bins=5, alpha=0.7, label="深さの上限が 1")
plt.legend()
```

実行結果

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/32722d3e-568c-4b37-87a3-024b3d0f2ee3.png" width="300">

グラフからばらつきが減っていることが実感できないかもしれませんが、オレンジ色のグラフが少し右にずれているので、平均値が少し増えていることは目で確認できると思います。

# 今回の記事のまとめ

今回の記事では、静的評価関数が計算する近似値の精度には、__誤差の精度__ と __ばらつきの精度__ があることを説明しました。

また、__ばらつきを表す指標__ として __標準偏差__ を紹介し、標準偏差を利用して深さ制限探索で __深さの上限を 0 から 1__ とした場合に、ばらつきを表す __標準偏差が実際に少しだけ減る__ という具体例を示しました。

ただし、その際に平均値が少し上昇してしまうという問題があることもわかりました。次回の記事では深さの上限を増やした場合の性質についてより詳しく説明します。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/21f5991c80f4a83455c7

# 更新履歴

| 更新日時 | 更新内容 |
|:--|:--|
| 2025/6/21 | 確率分布のグラフのことをヒストグラムと表記していたのを修正しました |

[^1]:この定義は筆者が独自に考えたものなので一般的ではないと思います
[^2]:説明は省略しますが、評価値を $s$ とした場合に、$\frac{1}{1 + e^{-as}}$ という計算を行ないます。$a$ は正の定数で、この計算を行う関数のことをシグモイド関数と呼びます。詳細は Wikipedia の[シグモイド関数](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%B0%E3%83%A2%E3%82%A4%E3%83%89%E9%96%A2%E6%95%B0)を参照して下さい
[^3]:これは、難しい局面に対して正確に形勢を判断できる人が強いという、ごく当たり前のことです
[^4]:すべての局面で正確なミニマックス値を計算することができれば、すべての局面の形勢判断をそれを使って行うことができるので局面の形勢判断は常に容易になりますが、将棋のようなゲームでそのようなことを行うことは現状では不可能です
[^5]:例えば数千から数万程度の値が考えられます
[^6]:$σ$ はギリシャ文字のシグマの小文字です