Pythonで〇×ゲームのAIを一から作成する　その179　深さの上限を 2 以上としたミニマックス法で計算される確率分布の性質

Last updated at 2025-07-13Posted at 2025-07-06

目次と前回の記事

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

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
test.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

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

用語と記号

今回の記事でも前回の記事に引き続き下記の表の用語と記号を用いることにします。

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

深さの上限を 2 としたミニマックス法で計算される確率分布の性質

前回の記事では、下記の条件で 深さの上限を 1 としたミニマックス法での max ノード $\boldsymbol{N}$ の近似値のミニマックス値の 確率分布の性質を検証 しました。

静的評価関数が任意の $d$ に対して同一の標準偏差 $σ$ の正規分布に従う確率分布で近似値を計算する
max ノードであるノード $N$ が 2 つ以上の複数の子ノード $A$、$B$、$C$・・・を持つ
それぞれの子ノードの局面の難しさを $d_A$、$d_B$、$d_C$ ・・・のように表記した場合に、$M(d_A) ≧ M(d_B) ≧ M(d_C) ・・・$ の条件を満たすものとする。別の言葉で説明すると、ノード $\boldsymbol{A}$ に対して計算される 近似値の平均が最も大きい ことを表す
$N$ は max ノードなので、$N$ と $A$ の 局面の形勢判断の難しさは同じ（$d_N = d_A$）であるものとする

その結果、下記の性質が成り立つ ことを示しました。

$M(d_N, 1) ≧ M(d_A, 0) = M(d_N, 0)$
$S(d_N, 1) ≦ S(d_A, 0) = S(d_N, 0)$

上記の式を言葉で説明すると以下のようになります。

max ノード $N$ に対して深さの上限を 0 と 1 としたミニマックス法で近似値のミニマックス値を計算すると、下記の性質が成り立つ
- 平均は深さの上限を 1 としたほうが同じかより大きくなる
- 標準偏差は深さの上限を 1 としたほうが同じかより小さくなる

前回の記事では説明しませんでしたが、$N$ が min ノードの場合 は max ノードと 正負が反転する以外は同様の性質を持つ ので下記の性質が成り立ちます。ばらつきは正負とは関係がない ので 標準偏差 は $N$ が min ノードの場合も減ります。

$M(d_N, 1) ≦ M(d_A, 0) = M(d_N, 0)$
$S(d_N, 1) ≦ S(d_A, 0) = S(d_N, 0)$

max ノードと min ノードで平均の場合の符号が異なるのがわかりづらいので、$N$ が max ノード の場合は $\boldsymbol{Nmax}$ のように表記することで、上記を下記のように記述することにします。なお、$M(d_{Amin}, 0) = M(d_{Nmin}, 0)$ となる理由は、$\boldsymbol{A}$ が min ノード の場合に $A_{min}$ の $\boldsymbol{A}$ を $\boldsymbol{N}$ で置き換えた場合 は $\boldsymbol{N}$ を min ノードとして考える必要がある からです。

なお、標準偏差 の場合は max ノードと min ノードで結果は変わらないので 表記は変えない ことにします。

$M(d_{Nmax}, 1) ≧ M(d_{Amin}, 0) = M(d_{Nmin}, 0)$
$M(d_{Nmin}, 1) ≦ M(d_{Amax}, 0) = M(d_{Nmax}, 0)$
$S(d_N, 1) ≦ S(d_N, 0)$

上記のうち 標準偏差が減る という性質は ばらつきの精度が高くなる ことを意味するので 良い性質 ですが、平均が変化 するという性質は 近似値の精度が低くなる ので 良い性質ではありません。ただし、平均が変化する という性質は 深さの上限を増やす ことで 緩和することができます。

今回の記事では、そのことを説明するために 深さの上限を 2 以上 とした場合の検証を行うことにします。

条件の設定

下記は検証を行う際の 前提条件 です。この前提条件のうちの 最初の 4 つの条件 は前回の記事で設定した 深さの上限を 1 とした場合の 前提条件と同じ です。残りの条件 は 深さの上限を 2 とする際に 必要となる条件 ですが、max ノードと min ノードが変わっただけで、基本的には最初の 4 つの条件と同じ ものです。なお、$N$ が min ノードの場合は max ノードと正負が反転する以外は同様の性質を持つので説明を省略します。

静的評価関数が任意の $d$ に対して同一の標準偏差 $σ$ の正規分布に従う確率分布で近似値を計算する
max ノードであるノード $N$ が 2 つ以上の複数の子ノード $A$、$B$、$C$・・・を持つ
それぞれの子ノードの局面の難しさを $d_A$、$d_B$、$d_C$ ・・・のように表記した場合に、$M(d_A) ≧ M(d_B) ≧ M(d_C) ・・・$ の条件を満たすものとする。別の言葉で説明すると ノード $\boldsymbol{A}$ に対して計算される 近似値の平均が最も大きい ことを表す
$N$ は max ノードなので、$N$ と $A$ の 局面の形勢判断の難しさは同じ（$d_N = d_A$）であるものとする
min ノードであるノード $N$ の子ノード $A$、$B$、$C$、・・・が 2 つ以上の複数の子ノードを持ち、$A$ の子ノードを $AA$、$AB$、$AC$ ・・・のように表記するものとする
$A$ のそれぞれの子ノードである局面の難しさを $d_{AA}$、$d_{AB}$、$d_{AC}$ ・・・のように表記した場合に、$M(d_{AA}) ≦ M(d_{AB}) ≦ M(d_{AC}) ・・・$ の条件を満たすものとする。別の言葉で説明すると ノード $\boldsymbol{AA}$ に対して計算される 近似値の平均が最も小さい ことを表す
$A$ は min ノードなので、$A$ と $AA$ の 局面の形勢判断の難しさは同じ（$d_A = d_{AA}$）であるものとする
他の $N$ の子ノードである $B$、$C$、・・・に対しても、同様に $M(d_{BA}) ≦ M(d_{BB}) ≦ M(d_{BC}) ・・・$、$d_{B} = d_{BA}$ などの条件を満たすものとする

N の子ノードの確率分布の性質

$\boldsymbol{N}$ の 子ノード $\boldsymbol{A}$、$\boldsymbol{B}$、$\boldsymbol{C}$、・・・に対して計算される 近似値のミニマックス値 は、min ノードである点 を除けば、前回の記事で検証した 深さの上限が 1 のミニマックス法で計算される近似値のミニマックス値と 同じ方法で計算 が行われます。先ほど説明したように、max ノードと min ノードでは 大小が反転する以外は同じ計算 が行われるので、min ノード $A$ に対して 下記の性質が満たされます。

$M(d_{Amin}, 1) ≦ M(d_{AAmax}, 0) = M(d_{Amax}, 0)$
$S(d_A, 1) ≦ S(d_{AA}, 0) = S(d_A, 0)$

下記は、下図の条件で min ノード $A$ の確率分布を計算し、その平均、標準偏差、グラフを表示するプログラムです。実行結果から $A$ と $AA$ の確率分布を比べると、平均が 0 から -2.35 に減り、標準偏差が 5 から 4.15 に減る ことが確認できます。

from tree import calc_discrete_ndist, calc_pdist, calc_stval, draw_pdist

pdistAA = calc_discrete_ndist(0, 5, area=20)
pdistAB = calc_discrete_ndist(1, 5, area=20)
pdistA = calc_pdist([pdistAA, pdistAB], maxnode=False)
print(calc_stval(pdistA))
draw_pdist(pdistAA, label="pdistAA")
draw_pdist(pdistA, label="pdistA", alpha=0.8)

実行結果

(-2.349041216719884, 17.213367568249353, 4.148899561118508)

これは、$N$ の 他の子ノード $B$、$C$・・・に対しても同様で、例えばノード $B$ に対して下記の式が成り立ちます。

$M(d_{Bmin}, 1) ≦ M(d_{Bmax}, 0)$
$S(d_B, 1) ≦ S(d_B, 0)$

N の確率分布の性質

上記から、$N$ の 子ノードの確率分布 は、いずれも 静的評価関数 が計算した場合の 確率分布より も 平均と標準偏差の両方が減った分布 になります。また、その確率分布は正規分布ではありませんが、正規分布に似た形状の分布 になります。

前回の記事で行った検証 では、max ノード $N$ の 子ノードの確率分布が正規分布に従っていました が、その検証において子ノードの確率分布が 正規分布に完全に従っている必要はありません。max ノード $N$ の 子ノードの確率分布 が上記のような 正規分布に似た分布でも 前回の記事で行った検証と同じ理由から 下記の性質が満たされます。

$M(d_{Nmax}, 2) ≧ M(d_{Amin}, 1) = M(d_{Nmin}, 1)$
$S(d_N, 2) ≦ S(d_A, 1) = S(d_N, 1)$

標準偏差の性質

上記から、標準偏差に関する下記の 2 つの式が成り立つ ことがわかりました。

$S(d_A, 1) ≦ S(d_A, 0)$
$S(d_N, 2) ≦ S(d_A, 1) = S(d_N, 1)$

$d_N = d_A$ なので、上記の式は下記のようにまとめることができます。

$S(d_N, 2) ≦ S(d_N, 1) ≦ S(d_N, 0)$

上記から深さの上限を 0, 1, 2 とした場合の $\boldsymbol{N}$ の確率分布の標準偏差 は、深さの上限が大きいほど単調減少する ことがわかります。

平均の性質

平均に関しては下記の 2 つの式が成り立ちます。

$M(d_{Amin}, 1) ≦ M(d_{Amax}, 0)$
$M(d_{Nmax}, 2) ≧ M(d_{Amin}, 1) = M(d_{Nmin}, 1)$

$d_N = d_A$ なので、$A$ を $N$ で置き換えると上記の式は下記のようになります。

$M(d_{Nmin}, 1) ≦ M(d_{Nmax}, 0)$
$M(d_{Nmax}, 2) ≧ M(d_{Nmin}, 1)$

前回の記事で、深さの上限を 0 から 1 とした場合の max ノード $\boldsymbol{N}$ の確率分布の平均 は、子ノードの確率分布の 標準偏差が大きい程大きく増える ことを示しました。同様に、min ノード の場合は子ノードの確率分布の 標準偏差が大きい程大きく減ります。

先程示したように $N$ の 子ノード の確率分布の 標準偏差 は、$N$ の 孫ノード の確率分布の 標準偏差よりも小さい ため、$\boldsymbol{M(d_{Nmax}, 0)}$ から $\boldsymbol{M(d_{Nmin}, 1)}$ への 減り幅 のほうが、$\boldsymbol{M(d_{Nmin}, 1)}$ から $\boldsymbol{M(d_{Nmax}, 2)}$ への 増え幅よりも大きい ことになります。

従って、下記の式が成り立ちます。

$M(d_{Nmin}, 1) ≦ M_(N_{max}, 2) ≦ M_(d_{Nmax}, 0)$

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

深さの上限を 1、2 とした場合の 確率分布の平均 は 深さの上限を 0 とした場合の 平均よりも小さい
深さの上限を 0 とした場合の 平均からの減り幅 は、深さの上限を 2 とした場合のほうが、深さの上限を 1 とした場合よりも 小さい

上記を別の言葉で説明すると以下のようになります。

max ノード $N$ の子ノード $A$ の確率分布の平均は、$A$ の子ノード $AA$ の確率分布の平均よりも小さくなるので $A$ の局面の形勢判断は過小評価 される
$N$ の確率分布の平均は、$A$ の確率分布の平均よりも大きくなるので $N$ の局面の形勢判断を過大評価 する。ただし、過大評価の度合い は上記の 過小評価の度合いよりも小さい
従って、$\boldsymbol{N}$ の局面の形勢判断 は過小評価を行った後で、より小さな過大評価を行うので 全体としては過小評価を行う ことになるが、その 過小評価の度合い は $\boldsymbol{A}$ に対して行われる 過小評価よりも小さくなる

上記で判明した深さの上限が 0、1、2 までの確率分布の平均の性質を見てもあまりピンとこない人が多いのではないかと思います。深さの上限と確率分布の平均の関係 は、深さの上限をさらに大きくすることで明確になる ので、この後で深さの上限をさらに増やした場合の検証で説明することにします。

確率分布の平均が減る理由

前回の記事で行った検証では 深さの上限を 0 から 1 とすることで確率分布の 平均が増えた ので、今回の検証で平均が減ったことに違和感を覚えた人がいるかもしれません。

前回の記事の検証と今回の記事の検証の違いは、深さの上限を 1 とした場合のミニマックス値の近似値を計算するノードが、前回の記事では max ノード であり、今回の記事では min ノード である点です。

$N$ が min ノードの場合 に 深さの上限が 2 の計算を行った場合は、正負が逆になる ので下記の式が成り立ちます。

$M(d_{Nmin}, 0) ≦ M_(N_{min}, 2) ≦ M_(d_{Nmax}, 1)$

この式から深さの上限を 2 とした場合の部分を取り除くと、深さの上限を 0 から 1 とすることで 確率分布の平均が増える ことを表す下記の式になります。

$M(d_{Nmin}, 0) ≦ M_(d_{Nmax}, 1)$

検証結果の確認

上記の検証結果が正しいこと を、今回の記事で 設定した条件を満たす 下記の設定で、深さの上限を 2 とした場合の $N$ の確率分布を計算することで 確認する ことにします。なお、わかりやすさを重視 して、下図のように 規則正しいゲーム木 で計算を行うことにしました。興味と余流がある人は、他の設定で $N$ の確率分布を計算してみて下さい。

静的評価関数が任意の $d$ に対して平均が $M(d)$、標準偏差が 5 の正規分布に従う確率分布で近似値を計算する
ゲーム木は、下図のような max ノードである $N$ をルートノードとする、深さが 2 でリーフノード以外の ノードが 3 つの子ノードを持つ
黒枠のノードが max ノードを、赤枠のノードが min ノードを表す
図のノードの中の数値がそのノードが属する $N_{mean}(s)$ の集合の $s$ を表す

下記は、上記の設定で $N$ の確率分布を計算し、その平均、標準偏差、グラフを表示するプログラムです。

1 ~ 5 行目：$N$ の孫ノードの確率分布を計算する
7 ~ 9 行目：$N$ の子ノードの確率分布を計算する
11 行目：$N$ の確率分布を計算する
13 ~ 18 行目：$N$、$A$、$AA$ の確率分布の平均、標準偏差、グラフを表示する

 1  pdistCA = calc_discrete_ndist(-2, 5, area=20)
 2  pdistBA = pdistCB = calc_discrete_ndist(-1, 5, area=20)
 3  pdistAA = pdistBB = pdistCC = calc_discrete_ndist(0, 5, area=20)
 4  pdistAB = pdistBC = calc_discrete_ndist(1, 5, area=20)
 5  pdistAC = calc_discrete_ndist(2, 5, area=20)
 6  
 7  pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
 8  pdistB = calc_pdist([pdistBA, pdistBB, pdistBC], maxnode=False)
 9  pdistC = calc_pdist([pdistCA, pdistCB, pdistCC], maxnode=False)
10  
11  pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)
12  
13  print(calc_stval(pdistAA))
14  print(calc_stval(pdistA))
15  print(calc_stval(pdistN))
16  draw_pdist(pdistAA, label="pdistAA")
17  draw_pdist(pdistA, label="pdistA", alpha=0.8)
18  draw_pdist(pdistN, label="pdistN", alpha=0.5)

行番号のないプログラム

pdistCA = calc_discrete_ndist(-2, 5, area=20)
pdistBA = pdistCB = calc_discrete_ndist(-1, 5, area=20)
pdistAA = pdistBB = pdistCC = calc_discrete_ndist(0, 5, area=20)
pdistAB = pdistBC = calc_discrete_ndist(1, 5, area=20)
pdistAC = calc_discrete_ndist(2, 5, area=20)

pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
pdistB = calc_pdist([pdistBA, pdistBB, pdistBC], maxnode=False)
pdistC = calc_pdist([pdistCA, pdistCB, pdistCC], maxnode=False)

pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)

print(calc_stval(pdistAA))
print(calc_stval(pdistA))
print(calc_stval(pdistN))
draw_pdist(pdistAA, label="pdistAA")
draw_pdist(pdistA, label="pdistA", alpha=0.8)
draw_pdist(pdistN, label="pdistN", alpha=0.5)

実行結果

(-3.3306690738754696e-16, 25.08040342281806, 5.008033887946253)
(-3.3155263675920765, 14.289116783779123, 3.7800948114801463)
(-1.0574856958804562, 7.288277471989034, 2.6996809944860214)

下記は、$d_N = d_A = d_{AA}$ であるノード $\boldsymbol{N}$、$\boldsymbol{A}$、$\boldsymbol{AA}$ の確率分布の平均と 標準偏差 をまとめた表です。$AA$、$A$、$N$ の確率分布はそれぞれ 深さの上限を 0、1、2 とした場合の確率分布が計算されます。表から、深さの上限を 2 とすることで、平均が深さの上限を 1 とした場合よりも 0 に近く なり、標準偏差が減る ことが確認できました。また、上記のグラフからもそのことが確認できます。

ノード	深さの上限	平均	標準偏差
$\boldsymbol{AA}$	0	0.00	5.00
$\boldsymbol{A}$	1	-3.32	3.78
$\boldsymbol{N}$	2	-1.06	2.70

深さの上限を 3 以上にした場合の検証

次に、深さの上限 を 3 以上に増やした場合 の検証を行います。

条件の設定

下記は検証を行う際の 前提条件 で、深さの上限を 2 とした場合の前提条件を整理しました。

静的評価関数が任意の $d$ に対して同一の標準偏差 $σ$ の正規分布に従う確率分布で近似値を計算する
深さの上限を $m$ とした深さ制限探索でノード $N$ の確率分布を計算する
$N$ をルートノードとするゲーム木の任意のノードを $X$、$X$ の子ノードを $A$、$B$、$C$ と表記する場合に、下記の条件が成り立つように子ノードを並べ替えると、常に $\boldsymbol{M(d_X) = M(d_A)}$ が成り立つ
- $X$ が max ノードの場合に、$M(d_A) ≧ M(d_B) ≧ M(d_C) ・・・$
- $X$ が min ノードの場合に、$M(d_A) ≦ M(d_B) ≦ M(d_C) ・・・$

3 つ目の条件を別の言葉で表すと、「親ノード $\boldsymbol{X}$ と、静的評価関数による子ノードの近似値の計算によって 平均的に最善手と計算される子ノード $\boldsymbol{A}$ の 局面の形勢判断の難しさは同じ である」となります。

3 つ目の条件は すべてのノードで成り立つ 条件なので「深さの上限を $m$ とした深さ制限探索によって、ルートノードの $N$ の局面から $\boldsymbol{m}$ 手目まで に 平均的に最善手として計算される合法手 を着手した 局面の形勢判断の難しさはすべて同じ」という条件になります。

ノードの表記法

先程は $N$ の子ノードを $A$、$B$、$C$、・・・、$A$ の子ノードを $AA$、$AB$、$AC$、・・・のように表記しました。同様に、子ノードの名前を 親ノードの名前の後ろに $A$、$B$、$C$、・・・という アルファベットをくっつけた名前で表記 することで、ゲーム木の すべての $N$ の子孫ノード を アルファベットの組み合わせで表記 することができます¹。例えば $AA$ の子ノードを $AAA$、$AAB$、$AAC$、・・・のように表記します。今回の記事では以後はこの記法でゲーム木のノードを表記することにします。

また、そのように表記した場合は、$A$、$AA$、$AAA$、・・・のように すべてが A で表記されるノード が 平均的に最善手であると計算されるノード となり、3 つ目の条件から それらの局面の形勢判断の難しさは同じ になるので下記の式が成り立ちます。

$d_N = d_A = d_{AA} = d_{AAA} = ・・・$
$M(d_N) = M(d_A) = M(d_{AA}) = M(d_{AAA}) = ・・・$

標準偏差の性質

先程の検証と 同様の理由 から、深さの上限を 3 とした場合の確率分布の 標準偏差 に関しては 下記の式が成り立ちます。

$S(d_N, 3) ≦ S(d_A, 2) ≦ S(d_{AA}, 1) ≦ S(d_{AAA}, 0)$

$d_N = d_A = d_{AA} = d_{AAA}$ から下記の式が成り立つので、深さの上限が 3 までの場合も 深さの上限を増やすほど標準偏差が減る ことになります。

$S(d_N, 3) ≦ S(d_N, 2) ≦ S(d_N, 1) ≦ S(d_N, 0)$

証明は省略しますが、同様の理由で下記の式が成り立ちます。この式から、深さの上限を増やすほど標準偏差が減る ことがわかります。

$S(d_N, 0) ≧ S(d_N, 1) ≧ S(d_N, 2) ≧ S(d_N, 3) ≧ S(d_N, 4) ≧ ・・・$

平均の性質

先程の検証と 同様の理由 から、深さの上限を 3 とした場合の確率分布の平均に関しては 下記の式が成り立ちます。

$N$ が max ノードの場合
- $M(d_{Nmax}, 3) ≧ M(N_{Amin}, 2)$
- $M(d_{Amin}, 2) ≦ M(N_{AAmax}, 1)$
- $M(d_{AAmax}, 1) ≧ M(N_{AAAmin}, 0)$
$N$ が min ノードの場合
- $M(d_{Nmin}, 3) ≦ M(N_{Amax}, 2)$
- $M(d_{Amax}, 2) ≧ M(N_{AAmin}, 1)$
- $M(d_{AAmin}, 1) ≦ M(N_{AAAmax}, 0)$

$d_N = d_A = d_{AA} = d_{AAA}$ から上記は下記のようになります。

$N$ が max ノードの場合
- $M(d_{Nmax}, 3) ≧ M(N_{Nmin}, 2)$
- $M(d_{Nmin}, 2) ≦ M(N_{Nmax}, 1)$
- $M(d_{Nmax}, 1) ≧ M(N_{Nmin}, 0)$
$N$ が min ノードの場合
- $M(d_{Nmin}, 3) ≦ M(N_{Nmax}, 2)$
- $M(d_{Nmax}, 2) ≧ M(N_{Nmin}, 1)$
- $M(d_{Nmin}, 1) ≦ M(N_{Nmax}, 0)$

上記から、max ノード では子ノードより 平均が増え、min ノードでは減ります。また、その性質は 深さの上限が 4 以上の場合も同様 です。

ゲーム木は max ノードと min ノード が 交互に繰り返され、平均の増減の量に関係する 標準偏差 は 深さの上限が増えるほど減る ので、深さの上限と確率分布の平均の関係を表すグラフは、下図のような 特定の値に近づいていくジグザグのグラフ になります。

なお、深さの上限を 1 以上 とした場合の確率分布の平均が 深さの上限を 0 とする確率分布の 平均よりも増えるか どうかは、静的評価関数が近似値を計算する リーフノードの親ノードの種類 によって以下のように決まります。上図はリーフノードの親ノードが max ノードの場合のグラフで、その場合は深さの上限が奇数の場合は $N$ は max ノードに、奇数の場合は min ノードになります。

リーフノードの親ノードが max ノードの場合は増える
リーフノードの親ノードが min ノードの場合は減る

検証結果の確認

上記の検証結果が正しいことを、先程 設定した条件を満たす 下記の設定で $N$ の確率分布を計算することで確認します。

静的評価関数が任意の $d$ に対して平均が $M(d)$、標準偏差が 5 の正規分布に従う確率分布で近似値を計算する
深さの上限が 0 ~ 10 のそれぞれの場合に対して max ノード $N$ の確率分布の計算を行う
$M(d_N) = 0$ とする
max ノード $X$ の子ノードを $A$、$B$、$C$ と表記した場合に、 $M(d_X) = M(d_A) = M(d_B) + 1 = M(d_C) + 2$ とする
min ノード $X$ の子ノードを $A$、$B$、$C$ と表記した場合に、 $M(d_X) = M(d_A) = M(d_B) - 1 = M(d_C) - 2$ とする

従って、平均的に最善手であると計算されるノード は $A$、$AA$、$AAA$、・・・では、$\boldsymbol{M(d_N) = M(d_A) = M(d_{AA}) = M(d_{AAA}) = ・・・ = 0}$ となります。

下図は上記の設定で 深さの上限を 2 とした場合のゲーム木の図で、先程の検証で利用したゲーム木と同じ であることがわかります。

深さの上限が 2 の場合の計算の改良

深さの上限が 2 の場合の計算は先程のプログラムで行うことができますが、同様のアルゴリズム で 深さの上限 を 3、4、5・・・と 増やしていくと、静的評価関数が計算する リーフノードの数 が 深さが増えるごとに 3 倍 になっていくため、同様の手順で プログラムを記述することは非常に困難 になります。そこで、別のアルゴリズムで計算 を行うことにします。どのようなアルゴリズムで計算できるかについて少し考えてみて下さい。

先程の図から、ノード $\boldsymbol{B}$ のそれぞれの 子ノードの確率分布の平均 は、ノード $\boldsymbol{A}$ のそれぞれの 子ノードの確率分布の平均から 1 を引いた値 であることがわかります。そのため証明は省略しますが、$\boldsymbol{A}$ の確率分布と $\boldsymbol{B}$ の確率分布は、平均が $\boldsymbol{B}$ のほうが 1 小さい 点を除けば、同じ形状 をしていることになります。同様に $\boldsymbol{C}$ の確率分布は 平均が $\boldsymbol{A}$ よりも 2 小さい 点を除けば同じ形状をしています。

そのことを下記の先ほど計算した $A$、$B$、$C$ の確率分布の平均と標準偏差を表示するプログラムで確認します。

print(calc_stval(pdistA))
print(calc_stval(pdistB))
print(calc_stval(pdistC))

実行結果

(-3.3155263675920765, 14.289116783779123, 3.7800948114801463)
(-4.315526367592078, 14.289116783779125, 3.7800948114801467)
(-4.315526367592078, 14.289116783779125, 3.7800948114801467)

下記の表から実際に $A$ と $B$ と $C$ の 平均が 1 ずつ異なり、標準偏差は全て同じ であることが確認できます。

	平均	標準偏差
$\boldsymbol{A}$	-3.32	3.78
$\boldsymbol{B}$	-4.32	3.78
$\boldsymbol{C}$	-5.32	3.78

また、下記の $A$、$B$、$C$ の確率分布のグラフを表示するプログラムの実行結果から、それぞれの確率分布の形状が同じ であることが確認できます。

draw_pdist(pdistA, label="pdistA")
draw_pdist(pdistB, label="pdistB", alpha=0.8)
draw_pdist(pdistC, label="pdistC", alpha=0.5)

このことから、$\boldsymbol{A}$ の確率分布の計算結果 を表す dict の キーを 1 つずつ減らした dict を計算 することで $\boldsymbol{B}$ の確率分布を計算できる ことがわかります。$C$ の場合はキーを 2 つ減らします。そこで、確率分布 を表す dict のキー を指定した値だけ 移した（translate）確率分布を計算する translate_pdist という関数を下記のプログラムで定義することにします。

1 行目：元の確率分布と、キーをずらす値を代入する仮引数を持つ関数として translate_pdist を定義する
2 行目：キーを移動した確率分布を計算する変数を空の dict で初期化する
3、4 行目：元の確率分布からキーとキーの値を取り出し、trans_pdist のキーを diff だけずらした値に代入する
5 行目：計算した trans_pdist を返り値として返す

1  def translate_pdist(pdist, diff):
2      trans_pdist = {}
3      for key, value in pdist.items():
4          trans_pdist[key + diff] = value
5      return trans_pdist

行番号のないプログラム

def translate_pdist(pdist, diff):
    trans_pdist = {}
    for key, value in pdist.items():
        trans_pdist[key + diff] = value
    return trans_pdist

translate_pdist を利用することで、先程の 深さの上限を 2 とした場合の処理 を、下記のプログラムで 簡潔に記述できる ようになります。実行結果で表示される 結果とグラフが先程と同じである ことから、下記のプログラムが正しい ことがわかります。

1 行目：$AA$ の確率分布を計算する
2、3 行目：$AB$、$AC$ の確率分布を translate_pdist を利用して $AA$ から計算する。$BA$ ~ $CC$ の確率分布の計算を行う必要はなくなったのでその処理を削除した
6、7 行目：$B$、$C$ の確率分布を、translate_pdist を利用して $A$ から計算する

 1  pdistAA = calc_discrete_ndist(0, 5, area=20)
 2  pdistAB = calc_discrete_ndist(1, 5, area=20)
 3  pdistAC = calc_discrete_ndist(2, 5, area=20)
 4  
 5  pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
 6  pdistB = translate_pdist(pdistA, -1)
 7  pdistC = translate_pdist(pdistA, -2)
 8  
 9  pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)
10  
11  print(calc_stval(pdistAA))
12  print(calc_stval(pdistA))
13  print(calc_stval(pdistN))
14  draw_pdist(pdistAA, label="pdistAA")
15  draw_pdist(pdistA, label="pdistA", alpha=0.8)
16  draw_pdist(pdistN, label="pdistN", alpha=0.5)

行番号のないプログラム

pdistAA = calc_discrete_ndist(0, 5, area=20)
pdistAB = calc_discrete_ndist(1, 5, area=20)
pdistAC = calc_discrete_ndist(2, 5, area=20)

pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
pdistB = translate_pdist(pdistA, -1)
pdistC = translate_pdist(pdistA, -2)

pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)

print(calc_stval(pdistAA))
print(calc_stval(pdistA))
print(calc_stval(pdistN))
draw_pdist(pdistAA, label="pdistAA")
draw_pdist(pdistA, label="pdistA", alpha=0.8)
draw_pdist(pdistN, label="pdistN", alpha=0.5)

修正箇所

-pdistCA = calc_discrete_ndist(-2, 5, area=20)
-pdistBA = pdistCB = calc_discrete_ndist(-1, 5, area=20)
-pdistAA = pdistBB = pdistCC = calc_discrete_ndist(0, 5, area=20)
-pdistAB = pdistBC = calc_discrete_ndist(1, 5, area=20)
-pdistAC = calc_discrete_ndist(2, 5, area=20)
+pdistAA = calc_discrete_ndist(0, 5, area=20)
+pdistAB = calc_discrete_ndist(1, 5, area=20)
+pdistAC = calc_discrete_ndist(2, 5, area=20)

pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
-pdistB = calc_pdist([pdistBA, pdistBB, pdistBC], maxnode=False)
+pdistB = translate_pdist(pdistA, -1)
-pdistC = calc_pdist([pdistCA, pdistCB, pdistCC], maxnode=False)
+pdistC = translate_pdist(pdistA, -2)

pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)

print(calc_stval(pdistAA))
print(calc_stval(pdistA))
print(calc_stval(pdistN))
draw_pdist(pdistAA, label="pdistAA")
draw_pdist(pdistA, label="pdistA", alpha=0.8)
draw_pdist(pdistN, label="pdistN", alpha=0.5)

実行結果

(-3.3306690738754696e-16, 25.08040342281806, 5.008033887946253)
(-3.3155263675920765, 14.289116783779123, 3.7800948114801463)
(-1.0574856958804562, 7.288277471989034, 2.6996809944860214)

グラフは先ほどと同じなので図を省略します。

深さの上限が 3 の場合の計算

深さの上限が 3 の場合は 深さが 2 のノード $\boldsymbol{AA}$ の確率分布 を その子ノード $\boldsymbol{AAA}$、$\boldsymbol{AAB}$、$\boldsymbol{AAC}$ から計算する 必要があります。

$N$ が max ノードの場合は 深さが 2 のノード $AA$ も max ノード で $\boldsymbol{M(d_{AA}) = 0}$ なので $\boldsymbol{M(d_{AAA}) = 0}$、$\boldsymbol{M(d_{AAB}) = -1}$、$\boldsymbol{M(d_{AAC}) = -2}$ となります。また、$AAA$、$AAB$、$AAC$ は平均が異なるだけで 確率分布の形状は同じ なので、$\boldsymbol{AAA}$ の確率分布から translate_pdist を利用して $\boldsymbol{AAB}$、$\boldsymbol{AAC}$ の 確率分布を計算 することができます。

上記から、深さの上限が 3 の場合の max ノード $\boldsymbol{N}$ の確率分布の計算 は下記のプログラムで計算を行うことができます。なお、グラフがわかりづらくなるので $AA$ の確率分布のグラフの表示は省略しました。

 1  pdistAAA = calc_discrete_ndist(0, 5, area=20)
 2  pdistAAB = translate_pdist(pdistAAA, -1)
 3  pdistAAC = translate_pdist(pdistAAA, -2)
 4  
 5  pdistAA = calc_pdist([pdistAAA, pdistAAB, pdistAAC], maxnode=True)
 6  pdistAB = translate_pdist(pdistAA, 1)
 7  pdistAC = translate_pdist(pdistAA, 2)
 8  
 9  pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
10  pdistB = translate_pdist(pdistA, -1)
11  pdistC = translate_pdist(pdistA, -2)
12  
13  pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)
14  
15  print(calc_stval(pdistAAA))
16  print(calc_stval(pdistAA))
17  print(calc_stval(pdistA))
18  print(calc_stval(pdistN))
19  draw_pdist(pdistAA, label="pdistAAA")
20  draw_pdist(pdistA, label="pdistA", alpha=0.5)
21  draw_pdist(pdistN, label="pdistN", alpha=0.5)

行番号のないプログラム

pdistAAA = calc_discrete_ndist(0, 5, area=20)
pdistAAB = translate_pdist(pdistAAA, -1)
pdistAAC = translate_pdist(pdistAAA, -2)

pdistAA = calc_pdist([pdistAAA, pdistAAB, pdistAAC], maxnode=True)
pdistAB = translate_pdist(pdistAA, 1)
pdistAC = translate_pdist(pdistAA, 2)

pdistA = calc_pdist([pdistAA, pdistAB, pdistAC], maxnode=False)
pdistB = translate_pdist(pdistA, -1)
pdistC = translate_pdist(pdistA, -2)

pdistN = calc_pdist([pdistA, pdistB, pdistC], maxnode=True)

print(calc_stval(pdistAAA))
print(calc_stval(pdistAA))
print(calc_stval(pdistA))
print(calc_stval(pdistN))
draw_pdist(pdistAA, label="pdistAAA")
draw_pdist(pdistA, label="pdistA", alpha=0.5)
draw_pdist(pdistN, label="pdistN", alpha=0.5)

修正箇所

+pdistAAA = calc_discrete_ndist(0, 5, area=20)
+pdistAAB = translate_pdist(pdistAAA, -1)
+pdistAAC = translate_pdist(pdistAAA, -2)

-pdistAA = calc_discrete_ndist(0, 5, area=20)
+pdistAA = calc_pdist([pdistAAA, pdistAAB, pdistAAC], maxnode=True)
pdistAB = translate_pdist(pdistAA, 1)
pdistAC = translate_pdist(pdistAA, 2)
元と同じなので省略

実行結果

(-3.3306690738754696e-16, 25.08040342281806, 5.008033887946253)
(3.3155263675920765, 14.289116783779122, 3.7800948114801463)
(1.057485695880457, 7.288277471989038, 2.6996809944860223)
(2.4702263833536686, 4.137711788478128, 2.0341366199147313)

実行結果をまとめた下記の表と上図のグラフから、深さの上限が 3 の場合の $N$ の 標準偏差 2.03 が、先程の 深さの上限が 2 の場合の 2.70 と比べて減っている ことがわかります。平均に関する考察は後で行います。

ノード	深さの上限	平均	標準偏差
$\boldsymbol{AAA}$	0	0.00	5.00
$\boldsymbol{AA}$	1	3.32	3.78
$\boldsymbol{A}$	2	1.06	2.70
$\boldsymbol{N}$	3	2.47	2.03

深さの上限が 3 の場合の計算の改良

先程のプログラムをよく見ると、2、3、5 行目、6、7、9 行目、10、11、13 行目で 同じような処理 を行っているので、この部分を 繰り返し処理 を利用して下記のプログラムのように 改良する ことができます。繰り返しのたび に 深さの上限が 1 ずつ増えた確率分布 が計算されるので、計算した確率分布を pdistlist という list の要素に追加 することで、インデックスが深さの上限を表す 確率分布の一覧を表す list が計算 されます。実行結果は先ほどと同じなので、正しく計算できていることが確認できます。

1 行目：深さが 3 のノードの親ノードは max ノードなので、親ノードが max ノードであるかどうかを表す変数に True を代入する
2 行目：深さが 3 の $AAA$ の確率分布を計算し、pdistA に代入する。この後の繰り返し処理では最初の子ノードの確率分布を pdistA という変数に代入することにするので、変数の名前を pdistA に変更した
3 行目：このノードの平均、標準偏差を計算して表示する
4 行目：pdistA は深さの上限を 0 とした場合の確率分布なので、深さの上限ごとの確率分布を記録する pdistlist を pdistA を要素として持つ list で初期化する
6 行目：深さが 2、1、0 の最初の子ノードの計算を行うので 3 回分の繰り返し処理を行う
7 ~ 9 行目：pdistA の親ノードが max ノードの場合の pdistA の残りの 2 つの兄弟ノードの確率分布の計算を行う
10 ~ 12 行目：pdistA の親ノードが min ノードの場合の pdistA の残りの 2 つの兄弟ノードの確率分布の計算を行う
13 行目：pdistA、pdistB、pdistC の親ノードの確率分布の計算を行う。計算結果は、次の繰り返し処理での最初の子ノード となるので、pdistA に代入する
14、15 行目：計算した確率分布を pdistlist の要素に追加し、その平均、標準偏差を計算して表示する
16 行目：次に計算する親ノードは max ノードと min ノードが入れ替わるので、maxnode の値を not 演算子で反転する
18 ~ 20 行目：pdistlist の中から深さが 3、1、0 の $AAA$、$A$、$N$ の確率分布を取り出してグラフで表示する

 1  maxnode = True
 2  pdistA = calc_discrete_ndist(0, 5, area=20)
 3  print(calc_stval(pdistA))
 4  pdistlist = [pdistA]
 5  
 6  for _ in range(3):
 7      if maxnode:
 8          pdistB = translate_pdist(pdistA, -1)
 9          pdistC = translate_pdist(pdistA, -2)
10      else:
11          pdistB = translate_pdist(pdistA, 1)
12          pdistC = translate_pdist(pdistA, 2)
13      pdistA = calc_pdist([pdistA, pdistB, pdistC], maxnode=maxnode)
14      pdistlist.append(pdistA)
15      print(calc_stval(pdistA))
16      maxnode = not maxnode
17      
18  draw_pdist(pdistlist[0], label="pdistAAA")
19  draw_pdist(pdistlist[2], label="pdistA", alpha=0.8)
20  draw_pdist(pdistlist[3], label="pdistN", alpha=0.5)

行番号のないプログラム

maxnode = True
pdistA = calc_discrete_ndist(0, 5, area=20)
print(calc_stval(pdistA))
pdistlist = [pdistA]

for _ in range(3):
    if maxnode:
        pdistB = translate_pdist(pdistA, -1)
        pdistC = translate_pdist(pdistA, -2)
    else:
        pdistB = translate_pdist(pdistA, 1)
        pdistC = translate_pdist(pdistA, 2)
    pdistA = calc_pdist([pdistA, pdistB, pdistC], maxnode=maxnode)
    pdistlist.append(pdistA)
    print(calc_stval(pdistA))
    maxnode = not maxnode
    
draw_pdist(pdistlist[0], label="pdistAAA")
draw_pdist(pdistlist[2], label="pdistA", alpha=0.8)
draw_pdist(pdistlist[3], label="pdistN", alpha=0.5)

実行結果

(-3.3306690738754696e-16, 25.08040342281806, 5.008033887946253)
(3.3155263675920765, 14.289116783779122, 3.7800948114801463)
(1.057485695880457, 7.288277471989038, 2.6996809944860223)
(2.4702263833536686, 4.137711788478128, 2.0341366199147313)

グラフは先ほどと同じなので図を省略します。

任意の深さの上限までの計算を行う関数の定義

上記で計算した pdistlist は、リーフノードを max ノードとした場合 の、深さの上限が 0 から 3 までの $N$ の確率分布を表します。従って、6 行目の繰り返しの回数を増やす ことで、より多くの深さの上限 での $\boldsymbol{N}$ の確率分布を計算 することができます。ただし、リーフノードを max ノード としたため、深さの上限が奇数 の場合は $N$ は max ノード 、深さの上限が偶数 の場合は min ノード となります。

$N$ を常に max ノードとして計算するプログラムを記述するのは少し面倒なので、先程の設定を少し変更して、下記の設定で $N$ の確率分布を計算するプログラムを定義することにします。具体的には下記の 太字の 3 番目の設定を追加 しました。

静的評価関数が任意の $d$ に対して平均が $M(d)$、標準偏差が 5 の正規分布に従う確率分布で近似値を計算する
深さの上限が 0 ~ 10 のそれぞれの場合に対してノード $N$ の確率分布の計算を行う
リーフノードの親ノードを max ノードとする。従って、深さが奇数の場合は $\boldsymbol{N}$ は max ノード、偶数の場合は $\boldsymbol{N}$ は min ノードとなる
$M(d_N) = 0$ とする
max ノード $X$ の子ノードを $A$、$B$、$C$ と表記した場合に、 $M(d_X) = M(d_A) = M(d_B) + 1 = M(d_C) + 2$ とする
min ノード $X$ の子ノードを $A$、$B$、$C$ と表記した場合に、 $M(d_X) = M(d_A) = M(d_B) - 1 = M(d_C) - 2$ とする

下記は、0 から指定した値までの深さの上限 での $N$ の 確率分布の一覧を表す list を計算 して返す関数です。なお、静的評価関数の標準偏差 に 任意の値を設定できる ような工夫を行ないました。

1 行目：深さの上限の最大値、静的評価関数の確率分布の標準偏差と確率変数の平均からの範囲を代入する仮引数を持つ関数として pdistlist を定義する
3 行目：仮引数の値を使って、最初のリーフノードの確率分布を計算する
7 行目：深さの上限の最大値の回数だけ繰り返し処理を行う
19 行目：結果を返り値として返す

 1  def calc_pdistlist(maxdepth, std, area):
 2      maxnode = True
 3      pdistA = calc_discrete_ndist(0, s=std, area=area)
 4      print(calc_stval(pdistA))
 5      pdistlist = [pdistA]
 6  
 7      for _ in range(maxdepth):
 8          if maxnode:
 9              pdistB = translate_pdist(pdistA, -1)
10              pdistC = translate_pdist(pdistA, -2)
11          else:
12              pdistB = translate_pdist(pdistA, 1)
13              pdistC = translate_pdist(pdistA, 2)
14          pdistA = calc_pdist([pdistA, pdistB, pdistC], maxnode=maxnode)
15          print(calc_stval(pdistA))
16          pdistlist.append(pdistA)
17          maxnode = not maxnode
18  
19      return pdistlist

行番号のないプログラム

def calc_pdistlist(maxdepth, std, area):
    maxnode = True
    pdistA = calc_discrete_ndist(0, s=std, area=area)
    print(calc_stval(pdistA))
    pdistlist = [pdistA]

    for _ in range(maxdepth):
        if maxnode:
            pdistB = translate_pdist(pdistA, -1)
            pdistC = translate_pdist(pdistA, -2)
        else:
            pdistB = translate_pdist(pdistA, 1)
            pdistC = translate_pdist(pdistA, 2)
        pdistA = calc_pdist([pdistA, pdistB, pdistC], maxnode=maxnode)
        print(calc_stval(pdistA))
        pdistlist.append(pdistA)
        maxnode = not maxnode

    return pdistlist

上記の定義後に、下記のプログラムで 深さの上限を 0 ~ 10 まで とした $N$ の 確率分布を計算 します。実行結果から、深さが増えるごとに標準偏差が減ることが確認できます。

pdistlist = calc_pdistlist(maxdepth=10, std=5, area=20)

実行結果

(-3.3306690738754696e-16, 25.08040342281806, 5.008033887946253)
(3.3155263675920765, 14.289116783779122, 3.7800948114801463)
(1.057485695880457, 7.288277471989038, 2.6996809944860223)
(2.4702263833536686, 4.137711788478128, 2.0341366199147313)
(1.5810896131331647, 2.32549463336302, 1.5249572562413085)
(2.1082385879036574, 1.4433538439597406, 1.20139662225251)
(1.7932839331837163, 0.9570428189161515, 0.9782856530258182)
(1.9814822532380678, 0.6974331486027796, 0.8351246305808371)
(1.8637607164970327, 0.5451993371484996, 0.73837614882152)
(1.940878140636157, 0.45313361598245533, 0.673152000652494)
(1.8870550771977217, 0.3897355342392095, 0.6242880218610714)

深さの上限ごとの平均、標準偏差のグラフを表示する関数の定義

calc_pdistlist は 深さの上限ごとの平均と標準偏差を数値で表示 しますが、数値だけではわかりづらい のでそれらを グラフで表示する関数 を下記のプログラムで定義することにします。特に難しい点はないと思いますので説明は省略します。

import matplotlib.pyplot as plt

def draw_pdistlist(pdistlist):
    meanlist = []
    stdlist = []
    for pdist in pdistlist:
        mean, var, std = calc_stval(pdist)
        meanlist.append(mean)
        stdlist.append(std)
        
    plt.plot(meanlist, label="平均")
    plt.plot(stdlist, label="標準偏差")
    plt.xlabel("深さの上限")
    plt.legend()

上記の定義後に、下記のプログラムで先程計算した深さの上限ごとの確率分布の平均と標準偏差のグラフを表示します。

draw_pdistlist(pdistlist)

実行結果

実行結果から、標準偏差 が 深さの上限が増えるごとに減っていく ことが確認できます。

また、平均に関しては max ノードと min ノードが交互に出現することから、増加と減少を交互に繰り返します が、深さの上限が増えると標準偏差が減る ため、深さの上限が増えると 増減の量が減って いきます。そのため、平均のグラフは実行結果のような ジグザグのグラフ になり、最終的には 一定の値に収束する ことが確認できます。静的評価関数 の確率分布の 標準偏差が 5 の場合は 平均は 2 付近の値に収束する ようです。なお、リーフノードの親ノードが max ノード なので、平均は 深さの上限が 0 の場合より大きく なります。

下記は、深さの上限を 0 と 10 とした場合の 確率分布のグラフを表示 するプログラムです。実行結果の図から 深さの上限を 10 とした場合は、約 60 % の確率で 2 が、残りの約 30 % の確率で 1 か 3 が計算され、ばらつきが非常に小さくなっている ことが確認できます。

draw_pdist(pdistlist[0], label="深さの上限 = 0")
draw_pdist(pdistlist[10], label="深さの上限 = 10", alpha=0.8)

実行結果

下記は、静的評価関数 の確率分布の 標準偏差を 3 とし、深さの上限を 20 まで計算してグラフを表示するプログラムです。

pdistlist = calc_pdistlist(maxdepth=20, std=3, area=20)
draw_pdistlist(pdistlist)

実行結果

(2.220446049250313e-16, 9.083333332957029, 3.013856886608425)
(1.6779806749322914, 5.335091459888748, 2.309781690958855)
(0.5822054512762135, 2.877594231203306, 1.6963473203336945)
(1.2320826883980767, 1.764053566417004, 1.328176782818087)
(0.8383285291236408, 1.1191159518132996, 1.0578827684641146)
(1.070106704100822, 0.7906505318335182, 0.8891853191734095)
(0.9271626896079963, 0.5993767356868668, 0.7741942493243326)
(1.018595244251562, 0.48695205645758927, 0.6978195013451467)
(0.9563213870734977, 0.41377076078167246, 0.6432501541248726)
(1.001107364031916, 0.3648036470634704, 0.6039897739725983)
(0.96679497946502, 0.32771503468060087, 0.5724640029561692)
(0.9940684474441828, 0.300289562865973, 0.5479868272741353)
(0.9713269227971754, 0.2765213363684348, 0.5258529607869816)
(0.9904432418654793, 0.25793168009883655, 0.507869747178188)
(0.9737921984340022, 0.24065745545310088, 0.4905685023043172)
(0.9881956097451189, 0.22677216210853687, 0.476206008055901)
(0.9753545371898359, 0.21346045053118134, 0.4620178032621485)
(0.9866606304636979, 0.2025801035733635, 0.450088995170248)
(0.9764270299668687, 0.19196855241404512, 0.43814216005087336)
(0.9855547478968173, 0.18318749886526625, 0.4280040874399055)
(0.9771985084942731, 0.17451985920848662, 0.41775574108381397)

実行結果から、静的評価関数 の確率分布の 標準偏差を小さくする ことで、平均が 2 より小さい 1 付近の値に収束 することが確認できました。また、標準偏差は約 0.5 まで小さくなる ことが確認できます。

下記は、深さの上限を 0 と 20 とした場合の確率分布のグラフを表示するプログラムです。実行結果の図から 深さの上限を 20 とした場合は、約 70 % の確率で 1 が、残りの約 30 % の確率で 0 か 2 が計算され、ばらつきがさらに小さくなっている ことが確認できます。

draw_pdist(pdistlist[0], label="深さの上限 = 0")
draw_pdist(pdistlist[20], label="深さの上限 = 20", alpha=0.8)

実行結果

深さの上限と確率分布の標準偏差と平均の関係のまとめ

今回の記事の検証をまとめると以下のようになります。

静的評価関数が任意の $d$ に対して同一の標準偏差 $σ$ の正規分布に従う確率分布で近似値を計算する
$N$ をルートノードとするゲーム木の任意のノードを $X$、$X$ の子ノードを $A$、$B$、$C$ と表記する場合に、下記の条件が成り立つように子ノードを並べ替えると、常に $\boldsymbol{M(d_X) = M(d_A)}$ が成り立つ
- $X$ が max ノードの場合に、$M(d_A) ≧ M(d_B) ≧ M(d_C) ・・・$
- $X$ が min ノードの場合に、$M(d_A) ≦ M(d_B) ≦ M(d_C) ・・・$

上記の条件が満たされる場合に深さ制限探索で $N$ の近似値のミニマックス値を計算すると、深さの上限を増やす ことで $N$ の 確率分布 が下記のような性質を持つ。

標準偏差が減る
深さの上限が 0 の場合 と比較した 平均の変化が少なくなる

上記を別の言葉で説明すると、深さ制限探索 によるミニマックス法は、深さの上限を増やす ことでミニマックス値の近似値の 誤差の精度を大きく落とさず に、ばらつきの精度が向上する ということを表します。以前の記事で説明したように ばらつきの精度の向上 は AI の強さに大きな影響を及ぼす ので、深さの上限を増やすことが AI の強さの向上 につながります。

現実の静的評価関数と設定した条件の違い

現実の静的評価関数 は検証の際に設定した 上記の条件を完全に満たすとは限りません。具体的にどのような点が現実の静的評価関数と異なるかについて説明します。

そもそも、以前の記事で仮定した 局面の形勢判断の難しさ というものが、本当に存在するかどうかがが不明 ですし、仮に存在した場合でも形勢判断の難しさが同じ局面に対して、静的評価関数が 正規分布に従う確率分布 で近似値を 計算するという保証はありません。例えば現実に存在するプロ棋士よりも強い将棋の AI の静的評価関数は、正規分布に従う場合ではまず起こり得ないようなとんでもなく大きな間違った計算を行うことが実際にあるようです。

静的評価関数が 任意の $\boldsymbol{d}$ に対して 同一の標準偏差 $σ$ の正規分布に従う確率分布で近似値を計算するという設定も、以前の記事で説明したように 形勢判断が優しい局面であるほど標準偏差が小さくなる 傾向があるため現実の静的評価関数がこの性質を完全には満たしません。

一般的に ゲームの決着が近くなるほど局面の形勢判断は容易 になります。そのため、$d_N = d_A = d_{AA} = d_{AAA} = ・・・$ という条件は、$N$ からあまり手数が進んでいないノードの場合はほぼ正しいですが、手数が進めば進むほど $d_N$ から離れた値になります。

上記のように、検証の際に設定した条件 は現実の静的評価関数には 完全には当てはまらない ので、深さの上限を増やした場合に、本記事で説明した理由から どのような場合でも AI が強くなるとは限りません。例えば、深さの上限を大きくすることで逆に間違った合法手を最善手として選択することもあります。

一方で検証した際に設定した条件は、下記のように 傾向としてはおおむね正しい のではないかと思います。

強い AI の静的評価関数は 形勢判断の正確性が高い ので、形勢判断の難しさが同じ局面に対して 正規分布に似た確率分布 で近似値を計算する 可能性が高い
形勢判断の難しさが近い場合 は、標準偏差はそれほど変わらない
子ノードの局面の形勢判断の難しさが 大きく異なる場合 は前回の記事で説明したように子ノードの $M(d)$ が大きく異なるので 標準偏差が異なっていても 親ノードの近似値のミニマックス値の 計算に影響を与える可能性が低い
ノードの深さがあまり変わらなければ、親ノードと平均的に最善手として計算される合法手の子孫ノードの局面の 形勢判断の容易さはほとんど変わらない

そのため、本記事の検証内容は完全に正しいわけではありませんが、深さの上限を増やすことで AI が一般的に強くなる理由の一つを説明できている のではないかと思います。

今回の記事のまとめ

今回の記事では、深さの上限が確率分布の性質に与える影響 ついて検証し、深さの上限を増やす ことで 誤差の精度を大きく落とさず に ばらつきの精度を向上させる ことができるという、AI が強くなる理由の一つ を説明しました。

次回の記事では、深さの上限を増やすことによって AI が強くなる別の理由について説明する予定です。

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

今回の記事で定義した translate_pdist、calc_pdistlist、draw_pdistlist は tree.py に保存することにします。

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
tree.py	本記事で更新した tree_new.py

次回の記事

An analysis of alpha-beta pruningという論文では、アルファベットではなく数字を使ってノードを表記する手法が示されているようですが、数字でノードを表記すると評価値と区別が付けづらいのではないかと思いましたので本記事ではアルファベットを採用しました。 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その179 深さの上限を 2 以上としたミニマックス法で計算される確率分布の性質

目次と前回の記事

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

用語と記号

深さの上限を 2 としたミニマックス法で計算される確率分布の性質

条件の設定

N の子ノードの確率分布の性質

N の確率分布の性質

標準偏差の性質

平均の性質

確率分布の平均が減る理由

検証結果の確認

深さの上限を 3 以上にした場合の検証

条件の設定

ノードの表記法

標準偏差の性質

平均の性質

検証結果の確認

深さの上限が 2 の場合の計算の改良

深さの上限が 3 の場合の計算

深さの上限が 3 の場合の計算の改良

任意の深さの上限までの計算を行う関数の定義

深さの上限ごとの平均、標準偏差のグラフを表示する関数の定義

深さの上限と確率分布の標準偏差と平均の関係のまとめ

現実の静的評価関数と設定した条件の違い

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その179　深さの上限を 2 以上としたミニマックス法で計算される確率分布の性質