目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義。現在は gui_play のみ定義されている |
| tree.py | ゲーム木に関する Node、Mbtree クラスの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
αβ 法によって計算される評価値の意味
前回の記事では、局面 と α 値 と β 値の初期値 をキー とした dict による置換表 を利用した αβ 法を紹介しましたが、その方法では置換表による 枝狩りの効率が悪いという問題 があります。置換表によって効率の良い枝狩りを行うためには、αβ 法によって計算される評価値の意味 について理解する必要があります。
αβ 法では 正しい評価値を計算したいノード を ルートノードとする部分木 のノードに対する 評価値の計算を行います。その際に、ルートノードの評価値は正しく計算 されますが、それ以外のノード の評価値は 必ずしも正しく計算されません。ルートノード以外のノード で どのような評価値が計算されるか については、詳しく説明してきませんでしたので今回の記事ではそのことについて説明します。
これまでの記事の知識からわかる性質
以前の記事で説明したように、α 値と β 値は 子ノードの評価値 が α 値以下または β 値以上 の場合に ルートノードの評価値に影響を与えない ことを表す値です。
αβ 法ではその性質から、ノードの評価値が α 値の初期値以下 である場合は、そのノードの評価値を α 値の初期値以下のどのような値として計算してもかまわない ことを利用して枝狩りを行います。同様に ノードの評価値が β 値の初期値以上 の場合は、そのノードの評価値を β 値の初期値以上のどのような値として計算してもかまいません。
一方、ノードの評価値が α 値と β 値の初期値の間 の場合は、その評価値が ルートノードの評価値に影響を与える ことが保証されるため、本当の評価値が α 値と β 値の初期値の間 であるということがわかります。なお、子ノードの評価値が正しいという保証がないため、現時点での知識は計算された評価値が 正しい評価値であるという保証はありません。
上記から、αβ 法で計算した ルートノード以外の評価値 とミニマックス法で計算した 本当の評価値の間 には 下記の表のような関係がある ことがわかります。
| αβ 法で計算された評価値 | 本当の評価値 |
|---|---|
| α 値の初期値以下 | α 値の初期値以下 |
| α 値と β 値の初期値の間 | α 値と β 値の初期値の間 |
| β 値の初期値以上 | β 値の初期値以上 |
上記の表の αβ 法で計算された評価値と本当の評価値の 関係はかなりあいまい です。例えば α 値と β 値の初期値が -100 と 100 の場合に、αβ 法でそのノードの評価値が 10 と計算された場合は、そのノードの 本当の評価値 が -100 ~ 100 という 大きな範囲のいずれかの数値 であることしか言えません。そこで、今回の記事では αβ 法で計算された評価値と本当の評価値の間に もっと厳密な関係があることを示す ことにします。
記号を使ったミニマックス法と αβ 法の処理の説明
言葉だけで説明を行うと説明が長くわかりづらくなるため、今回の記事ではいくつかの記号を使って説明を行うことにします。
ミニマックス法 でのノード $N$ の 評価値の計算方法 は記号を使うと以下のようになります。
- $N$ の 子ノードの評価値 の 最小値 を $s_{min}$、最大値 を $s_{max}$ と表記する
- ミニマックス法で計算される $N$ の 評価値を $S_N$ と表記 した場合に
max ノードでは $S_N = s_{max}$、min ノードでは $S_N = s_{min}$ である
αβ 法 での max ノード $N$ の 評価値の計算方法 は記号を使うと以下のようになります。
- $N$ の α 値と β 値の初期値 を単に α、β と表記 する
- $N$ の $i$ 番の子ノードの評価値を $s_i$ と表記する。ただし $i$ は 0 から数える
- αβ 法で計算された $N$ の 評価値を $S_N'$ と表記 した場合に $S'_N$ は以下の表のように計算される
| $s_{max}$ の範囲 | $S_N'$ の値 |
|---|---|
| $s_{max} ≦ α$ | $α$ |
| $α < s_{max} < β$ | $s_{max}$ |
| $β ≦ s_{max}$ | $β ≦ s_{i}$ となる最初の $s_{i}$ |
min ノード では同様の理由で以下の表のようになります。
| $s_{min}$ の範囲 | $S_N'$ の値 |
|---|---|
| $s_{min} ≦ α$ | $s_{i} ≦ α$ となる最初の $s_{i}$ |
| $α < s_{min} < β$ | $s_{min}$ |
| $β ≦ s_{min}$ | $β$ |
ただし、ゲームの決着がついた 子ノードが存在しない リーフノード では、ミニマックス法も αβ 法もゲームの勝敗に基づいた 正しい評価値が常に計算 されます。
記号を使ったこれまでの記事の知識からわかる性質
先程説明した、これまでの記事の知識からわかる αβ 法 で計算された 評価値 $S_N'$ と、ミニマックス法 で計算される 本当の評価値 である $S_N$ の 関係の表 を記号を使って表記すると下記のような 簡潔な表 になります。
| $S_N'$ の範囲 | $S_N$ の範囲 |
|---|---|
| $S_N' ≦ α$ | $S_N ≦ α$ |
| $α < S_N' < β$ | $α < S_N < β$ |
| $β ≦ S_N'$ | $β ≦ S_N$ |
全ての子ノードの評価値が正しく計算される場合の αβ 法の評価値の性質
ノード $N$ の すべての子ノードの評価値が正しく計算される場合 は、先程の下記の表から max ノード では αβ 法 で計算された 評価値 $S_N'$ と、ミニマックス法 で計算される 本当の評価値 である $S_N$ との間には 以下の箇条書きのような関係がある ことがわかります。
| $s_{max}$ の範囲 | $S_N'$ の値 |
|---|---|
| $s_{max} ≦ α$ | $α$ |
| $α < s_{max} < β$ | $s_{max}$ |
| $β ≦ s_{max}$ | $β ≦ s_{i}$ となる最初の $s_{i}$ |
- $s_{max} ≦ α$ の場合
ミニマックス法 では $s_{max}$ を $N$ の評価値 $S_N$として計算するが、αβ 法 では $s_{max}$ 以上の値 である α が評価値 $S_N'$ として計算される。$S_N = s_{max} ≦ S_N' = α$ であることから $S_N ≦ S_N'$ である - $α < s_{max} < β$ の場合
ミニマックス法と同じ $s_{max}$ が評価値として計算されるので、$S_N = S'_N$ である - $β ≦ s_{max}$ の場合
β 狩りによって 評価値の計算が省略された子ノードの中 に $S_N'$ 以上の評価値 を持つ子ノードが 存在する可能性がある ので、本当の評価値 $S_N$ は $S'_N$ 以上の可能性がある。従って $S'_N ≦ S_N$ である
下記の表の min ノード では同様の理由から下記の箇条書きのようになります。
| $s_{min}$ の範囲 | $S_N'$ の値 |
|---|---|
| $s_{min} ≦ α$ | $s_{i} ≦ α$ となる最初の $s_{i}$ |
| $α < s_{min} < β$ | $s_{min}$ |
| $β ≦ s_{min}$ | $β$ |
- $s_{min} ≦ α$ の場合
$S_N ≦ S'_N$ である - $α < s_{min} < β$ の場合
$S_N = S'_N$ である - $β ≦ s_{min}$ の場合
$β = S'_N ≦ S_N$ である
上記を先程の表に加える と以下の表のようになります。
max ノード の場合。
| $s_{max}$ の範囲 | $S_N'$ の値 | $S_N$ と $S_N'$ の関係 |
|---|---|---|
| $s_{max} ≦ α$ | $α$ | $S_N ≦ S'_N$ |
| $α < s_{max} < β$ | $s_{max}$ | $S_N = S'_N$ |
| $β ≦ s_{max}$ | $β ≦ s_{i}$ となる最初の $s_{i}$ | $S'_N ≦ S_N$ |
min ノード の場合。
| $s_{min}$ の範囲 | $S_N'$ の値 | $S_N$ と $S_N'$ の関係 |
|---|---|---|
| $s_{min} ≦ α$ | $s_{i} ≦ α$ となる最初の $s_{i}$ | $S_N ≦ S'_N$ |
| $α < s_{min} < β$ | $s_{min}$ | $S_N = S'_N$ |
| $β ≦ s_{min}$ | $β$ | $S'_N ≦ S_N$ |
αβ 法で求められる評価値と本当の評価値の関係
αβ 法で $N$ の評価値を計算 した際に 求められる値 は $S_N'$ であり、$s_{min}$ や $s_{max}$ を 直接求めることができるとは限りません1。そこで、上記の表から αβ 法で求められるとは限らない $s_{max}$ と $s_{min}$ を 削除する ことで、αβ 法で求められる評価値 $S_N'$ と本当の評価値 $S_N$ の 関係を表す表を作成 することにします。具体的には上記の表の「$s_{max}$ の範囲」と「$S_N'$ の値」の列を「$S_N'$ の範囲」という 列にまとめます。
max ノードの場合はそれぞれ以下のようになります。
- $s_{max} ≦ α$ の場合は $S_N'$ の値は α になるので、$S_N'$ の範囲は $S_N' = α$ となる
- $α < s_{max} < β$ の場合は $S_N' = s_{max}$ なので、$S_N'$ の範囲は $α < S_N' < β$ となる
- $β ≦ s_{max}$ の場合は $β ≦ s_i = S_N'$ なので、$S_N'$ の範囲は $β ≦ S_N'$ となる
min ノードの場合も同様の考え方でそれぞれ以下のようになります。
- $s_{min} ≦ α$ の場合は $S_N' ≦ α$ となる
- $α < s_{min} < β$ の場合は $α < S_N' < β$ となる
- $β ≦ s_{min}$ の場合は $β = S_N'$ となる
上記をまとめると以下の表のようになります。
| max ノードでの $S'_N$ の範囲 | min ノードでの $S'_N$ の範囲 | $S_N$ との関係 |
|---|---|---|
| $S'_N = α$ | $S'_N ≦ α$ | $S_N ≦ S'_N$ |
| $α < S'_N < β$ | $α < S'_N < β$ | $S_N = S'_N$ |
| $β ≦ S'_N$ | $β = S'_N$ | $S'_N ≦ S_N$ |
なお、$S'_N = α$ は $S'_N ≦ α$、$β = S'_N$ は $β ≦ S'_N$ という 条件に含まれる ので、max ノードと min ノードでの $S'_N$ の範囲を下記の表のように まとめて単純化 することができます。また、表にそれぞれの行の意味と用語を加えました。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
下界（lower bound）と 上界（upper bound）は数学の用語ですが、意味がわからない人が多いのではないかと思いますので説明します。
上界と最大値 は以下のように似ていますが 異なる意味です。なお、下界は上界の逆です。
- 最大値 はある値が 実際に取りうる最大の値 を表す。例えば 1 ~ 6 までの出目が出るサイコロの出目の最大値は 6 であり、サイコロを振った時に 実際に 6 が出る可能性がある
- 上界 はある値がとりうる値の 最大値以上であればどのような値でも構わない。別の言葉で言えば、実際にその値を取りうるかどうかはわからない が、少なくともその値より大きくなることがない値 の事を表す。例えば 6 以上の全ての実数はサイコロの出目の上界であるので、10 はサイコロの出目の上界である
上記の表で「本当の評価値の最大値がわかる」と表記しなかったのは、本当の評価値 はミニマックス法を用いて ただ 1 つの値が計算される ので 範囲を持たないから です。
似たような数学の用語に上限と下限があります。上限は上界の最小値という意味を持ちます。多くの場合では、上限と最大値は同じ値になりますが、上限は存在するが最大値が存在しない場合があります。例えば 6 未満の実数には 6 は含まれないので最大値はありませんが、上限は 6 となります。
なお、実数のように最大値、上限、上界のいずれも持たないようなものもあります。
本記事でのこれらの用語の説明はわかりやすさを重視したものなので、数学での正確な用語の定義ではありません。参考までにこれらの用語の wikipedia のリンクを下記に示します。数学的な用語の定義を知りたい方は参考にして下さい。
上記の表の性質を言葉で説明すると以下のようになります。
説明を短くするために、以後は α 値の初期値以下の評価値（$S'_N ≦ α$）が計算されるノードの事を fail low、α 値と β 値の範囲内の評価値（$α < S_N' < β$）が計算されるノードの事を exact value、β 値の初期値以上の評価値（$β ≦ S'_N$）が計算されるノードのことを fail high と表記することにします。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
上記の表と、先程示した下記のこれまでの記事からわかる関係の表を見比べてみてください。上記の表の方が $S_N'$ と$S_N$ の関係を より厳密に表せている ことがわかるはずです。
| $S_N'$ の範囲 | $S_N$ の範囲 |
|---|---|
| $S_N' ≦ α$ | $S_N ≦ α$ |
| $α < S_N' < β$ | $α < S_N < β$ |
| $β ≦ S_N'$ | $β ≦ S_N$ |
上記の表の性質を利用した、置換表とは異なる方法で αβ 法の枝狩りの効率を高める方法があります。その方法については今後の記事で紹介する予定です。
αβ 法での評価値の計算方法のバリエーション
本記事ではこれまでは $N$ が max ノードで fail low（$s_{max} ≦ α$）の場合に、$N$ の 評価値を α と計算 していましたが、その場合のノードの 評価値を $s_{max}$ と計算しても構いません。そのように計算しても良い理由について忘れた方は以前の記事を復習して下さい。
ただし、$N$ の評価値を α と計算した場合と、$s_{max}$ と計算した場合では max ノードでの fail low の場合 の $S_N'$ と $S_N$ との関係がより厳密 になります。具体的には $S_N' = α$ の場合は $S_N ≦ S_N' = α $ となりますが、$S_N' = s_{max}$ の場合は $s_{max} ≦ α$ なので $S_N ≦ S_N' ≦ α$ となるため、本当の評価値 $S_N$ の上界 を表す $S_N'$ が小さくなって $S_N$ の 範囲が狭まる可能性が生じる ことになります。
例えば α 値の初期値が 0 で子ノードの評価値が -1、-2、-3 の場合は $s_{max}$ = -1 となるので、本当の評価値の範囲は下記のように $S_N' = s_{max}$ として計算したほうが狭くなります。
| $S'_N$ の計算方法 | $S_N$ の範囲 | 意味 |
|---|---|---|
| $α = 0$ | $S_N ≦ 0$ | 本当の評価値は 0 以下 |
| $s_{max} = -1$ | $S_N ≦ -1$ | 本当の評価値は -1 以下 |
同様に、$N$ が min ノードで fail high の場合の評価値を β ではなく $s_{min}$ と計算することで、$S_N$ の 範囲が狭まる可能性 が生じます。また、そのように計算することで、max ノードの場合でも min ノードの場合でも先程示した 下記の表が厳密に正しくなります4。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
次回の記事で説明しますが、本当の評価値の範囲が狭い ほうが 置換表を利用したαβ 法 の 枝狩りを効率よく行うことが出来る ので、以後の説明では αβ 法の計算を下記の表のように行うことにします。
max ノード の場合。
| $s_{max}$ の範囲 | $S_N'$ の値 | 用語 |
|---|---|---|
| $s_{max} ≦ α$ | $s_{max}$ | fail low |
| $α < s_{max} < β$ | $s_{max}$ | exact value |
| $β ≦ s_{max}$ | $β ≦ s_{i}$ となる最初の $s_{i}$ | fail high |
min ノード の場合。
| $s_{min}$ の範囲 | $S_N'$ の値 | 用語 |
|---|---|---|
| $s_{min} ≦ α$ | $s_{i} ≦ α$ となる最初の $s_{i}$ | fail low |
| $α < s_{min} < β$ | $s_{min}$ | exact value |
| $β ≦ s_{min}$ | $s_{min}$ | fail high |
これまでに上記の表のように計算していなかったのは、以前の記事で説明したようにプログラムを簡潔に記述することが出来るからです。すぐ後で実装を行いますが、上記のような計算を行うためには、α 値 や β 値とは別に子ノードの評価値の最大値（または最小値）を記録するための変数を用意する必要が生じます。
そのため、αβ 法の処理を実装する際には、本記事でこれまでに行ってきた方法で行うことがあります。例えば wikipedia の αβ 法の疑似コードではそのような処理が記述されているようです。
これまでは $N$ が max ノード で β 値以上の子ノードの評価値が計算された場合 は、β 狩りを行って その子ノードの評価値 をノードの評価値として計算していましたが、β 値をそのノードの評価値と計算 するという計算方法もあります。ただし、その場合は 本当の評価値 $S_N$ の下界が小さくなって範囲が広がる可能性が生じます。
置換表を利用する場合は範囲が狭いほうが良いので、本記事ではこれまで通りの方法で計算しますが、どちらを計算しても 処理の記述の手間は変わらない ので 本当の評価値の下界を知る必要がない場合 は、どちらを計算しても構わない でしょう。
ai_abs2 の実装
上記の方法で評価値を計算する AI を定義し、Check_Solved を利用して 強解決の AI であることを確認する ことにします。AI の関数の名前は ai_abs2 とし、αβ 法で着手を選択する AI である ai_abs を下記のプログラムのように修正して定義します。
なお、この手法によって 変更される のは、19 行目と 29 行目で 返される評価値だけ です。18 行目と 28 行目で α 値や β 値を更新する処理 は 変更しない 点に注意して下さい。
-
6 行目：関数名を
ai_abs2にする -
11 行目：〇 の手番の max ノードの子ノードの評価値の最大値を計算する変数
scoreを負の無限大で初期化する -
15 行目：子ノードの評価値を計算し、組み込み関数
maxを利用することでこれまに計算した子ノードの評価値の最大値より大きい場合にscoreの値を更新する -
19 行目：このノードの評価値として α 値ではなく、子ノードの評価値の最大値である
scoreを返すように修正する - 21、25、29 行目：× の手番の min ノードでも同様の修正を行う
1 from ai import ai_by_score, dprint
2 from marubatsu import Marubatsu
3 from copy import deepcopy
4
5 @ai_by_score
6 def ai_abs2(mb, debug=False):
7 count = 0
8 def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
9 legal_moves = mborig.calc_legal_moves()
10 if mborig.turn == Marubatsu.CIRCLE:
11 score = float("-inf")
12 for x, y in legal_moves:
13 mb = deepcopy(mborig)
14 mb.move(x, y)
15 score = max(score, ab_search(mb, alpha, beta))
16 if score >= beta:
17 return score
18 alpha = max(alpha, score)
19 return score
20 else:
21 score = float("inf")
22 for x, y in legal_moves:
23 mb = deepcopy(mborig)
24 mb.move(x, y)
25 score = min(score, ab_search(mb, alpha, beta))
26 if score <= alpha:
27 return score
28 beta = min(beta, score)
29 return score
元と同じなので省略
行番号のないプログラム
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy
@ai_by_score
def ai_abs2(mb, debug=False):
count = 0
def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
nonlocal count
count += 1
if mborig.status == Marubatsu.CIRCLE:
return 1
elif mborig.status == Marubatsu.CROSS:
return -1
elif mborig.status == Marubatsu.DRAW:
return 0
legal_moves = mborig.calc_legal_moves()
if mborig.turn == Marubatsu.CIRCLE:
score = float("-inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = max(score, ab_search(mb, alpha, beta))
if score >= beta:
return score
alpha = max(alpha, score)
return score
else:
score = float("inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = min(score, ab_search(mb, alpha, beta))
if score <= alpha:
return score
beta = min(beta, score)
return score
score = ab_search(mb)
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
修正箇所
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy
@ai_by_score
-def ai_abs(mb, debug=False):
+def ai_abs2(mb, debug=False):
count = 0
def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
legal_moves = mborig.calc_legal_moves()
if mborig.turn == Marubatsu.CIRCLE:
+ score = float("-inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
- score = ab_search(mb, alpha, beta)
+ score = max(score, ab_search(mb, alpha, beta))
if score >= beta:
return score
alpha = max(alpha, score)
- return alpha
+ return score
else:
+ score = float("inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
- score = ab_search(mb, alpha, beta)
+ score = min(score, ab_search(mb, alpha, beta))
if score <= alpha:
return score
beta = min(beta, score)
- return beta
+ return score
元と同じなので省略
上記の実行後に下記のプログラムを実行すると、実行結果から ai_abs2 が強解決の AI である ことが確認できるので、この方法で αβ 法の計算が正しく行える ことが確認できました。
from util import Check_solved
Check_solved.is_strongly_solved(ai_abs2)
実行結果
100%|██████████| 431/431 [00:04<00:00, 103.95it/s]
431/431 100.00%
(True, [])
αβ 法の評価値の性質が全ての場合で正しいことの証明
先程説明した下記の表の性質は、ノード $N$ の すべての子ノードの評価値が正しく計算された場合 のものです。実際には αβ 法で計算される子ノードの評価値 は、ミニマックス法で計算される 正しい評価値とは異なる場合 がありますが、そのような場合でも αβ 法で計算された評価値 は 常に下記の表と全く同じ性質を持ちます。別の言葉でいうと、任意のノード $N$ で下記の表の性質が成り立ちます。少々難しいかもしれませんが、余裕のある方はどのように証明すればよいかについて少し考えてみて下さい。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
なお、以下の証明が理解できなくても上記の性質を利用することは可能なので、意味がどうしてもわからないと思った方は、当面は証明の理解を後回しにしてもかまわないでしょう。
このことを証明する方法が記述された文献を見つけられなかったので、以下の証明は筆者が独自に考えたものです。そのため証明が間違っている可能性があります。もっとわかりやすい証明方法をご存じの方や間違いを見つけた方はコメントで教えて頂ければ助かります。
証明方法
〇× ゲームのような特定の手数で必ずゲームの決着がつく 有限ゲーム のゲーム木に対するミニマックス法や αβ 法の評価値の計算には 以下のような特徴 があります。
- 評価値を計算したいノードを ルートノードとする部分木 の ノードの評価値を計算する5
- 有限ゲームのゲーム木には必ず 最大の深さのノードが存在 する
- 最大の深さのノード はすべて決着がついた局面を表す リーフノード である
- リーフノードの評価値 は勝敗の結果によって必ず 正しい評価値が計算 される
- リーフノード以外 のノードの評価値は、子ノードの評価値によって計算 される
上記の性質のうち、「最も深いノードの評価値は正しく計算できる」、「親ノードの評価値は子ノードの評価値によって計算される」という特徴から、下記のような 数学的帰納法 を使ってすべてのノードで下記の表の条件が成り立つことを証明することができます。ただし、枝狩りされたノードは αβ 法の計算には利用されないので除きます。
- 最も深いノード で下記の表の条件が成り立つことを示す
- $i > 0$6 の 深さが $i$ のノード で下記の表の条件が成り立つ場合に、深さが $i-i$ のノードでも 下記の表の条件が 成り立つ ことを示す
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
数学的帰納法とは、連続する事柄 が すべて正しいこと を、以下の手順で証明するという手法です7。最初のドミノを倒すと残りのドミノが次々と倒れていく様子に似ているので、ドミノ倒しに良く例えられるようです。
- 最初の事柄が正しいことを証明する
- ある事柄が正しければ次の事柄も正しいことを証明する
なお、数学的帰納法では一般的に無限に連続する事柄がすべて正しいことを証明しますが、今回の場合は最も深いノードから深さ 0 までの有限の事柄がすべて正しいことを証明しています。
参考までに下記に Wikipedeia のリンクを挙げておきます。
最も深いノードで条件が成り立つことの証明
先程説明したように 最も深いノード には以下のような性質があります。
- 最大の深さのノード はすべて決着がついた局面を表す リーフノード である
- リーフノードの評価値 は勝敗の結果によって必ず 正しい評価値が計算 される
従って、最も深いノード では 正しい評価値が計算される ので常に $S_N = S_N'$ となります。$S_N ≦ S_N'$ と $S_N' ≦ S_N$ は $S_N = S_N'$ を含む ので、最も深いノードでは下記の表が成り立ちます。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
子ノードで成り立つ場合に親ノードでも成り立つことの証明
$i > 0$ の 深さが $i$ のノード で上記の表の条件が成り立つ場合に、その親ノードである 深さが $i-1$ のノードでも 成り立つことを証明する方法について少し考えてみて下さい。
αβ 法で評価値を計算する ゲーム木のノード は以下の 8 種類に分類 することができます。枝狩りされたノード は評価値の計算に使われないので 考慮する必要はない ので、下記の それ以外の 7 種類のそれぞれについて成り立つ ことを証明します。
- 枝狩りされたノード（以下の全ての項目は枝狩りされていないノードを表す）
- リーフノード（以下の全ての項目はリーフノード以外のノードを表す）
- max ノードで fail low
- max ノードで exact value
- max ノードで fail high
- min ノードで fail low
- min ノードで exact value
- min ノードで fail high
リーフノードの場合
リーフノードの場合は、先程正しいことを証明済です。
max ノードで fail low の場合
$N$ が深さ $i-1$ の max ノードで fail low の場合は、下記の理由から すべての深さが $i$ の子ノードが fail low になります。
- $N$ は fail low なので 全ての子ノードの評価値は $α$ 以下 である
- αβ 法 では max ノード では α 値 は子ノードの評価値が α 値より大きい場合に増加する
- 従って $N$ の評価値を計算する際に α 値は 初期値である $α$ のまま変化しない
- 従って $N$ の すべての子ノード は以下の性質から fail low の性質を持つ
- α 値の初期値 は $N$ の α 値の初期値と同じ $α$ になる
- 計算される 評価値は $α$ 以下 である
上記から、下記の理由で $N$ が深さ $i-1$ の max ノードで fail low の場合は 下記の表の条件が成り立ちます。
- 数学的帰納法の証明の前提から、深さが $i$ のノードで下記の表の条件が成り立つ
- 上記で証明したように、$N$ の 子ノードはすべて fail low である
- $N$ の子ノードの深さは $i$ である
- 2 と 3 から $N$ の 全ての子ノード評価値 には 本当の評価値の上界が計算 される
- $N$ は max ノードで fail low なので、子ノードの評価値の最大値が計算 される
- 複数の数値の 上界の最大値 は、それらの 複数の数値の上界を表す。例えば 3 つの子ノードの本当の評価値がそれぞれ「10 以下」と「20 以下」と「30 以下」と計算された場合は、その 3 つの子ノードの評価値の最大値は「30 以下」となる
- 4、5、6 から $N$ の評価値は 本当の評価値の上界が計算 され下記の表の条件が成り立つ
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
max ノードで exact value の場合
$N$ が深さ $i-1$ の max ノードで exact value の場合は、$N$ の評価値として子ノードの評価値の最大値である $s_{max}$ が計算されます（$S_N' = s_{max}$）。また その最大値は α 値の初期値と β の初期値の間 である $α < s_{max} < β$ になります。
この時、$N$ の 子ノードは 以下の理由から fail low または exact value になります。
- 子ノードの評価値の最大値である $s_{max}$ が β 未満なので β 狩りは行われない
- 従って 全ての子ノードの評価値の計算が行われる
- max ノードでは β 値は変化しないので、β 値は初期値である β のまま変化しない
- $N$ の子ノードを $C$ と表記し、$C$ の評価値の計算を開始する時点での α 値を $α_C$、β 値を $β_C$、$C$ の評価値を $S_C'$ と表記する。ただし、上記から $β_C = β$ である。このとき以下から $C$ は fail low または exact value のいずれかである ことがわかる
- $S_C' ≦ α_C$ の場合。$C$ は fail low である
- $α_C < S_C' < β_C$ の場合。$C$ は exact value である
- $β_C ≦ S_C'$ の場合。$β_C = β$ で、$S_C' ≦ s_{max} < β$ なのでこのような場合は存在しない
また、以下の理由から 評価値が $s_{max}$ である 最初の子ノードは exact value になります。
- αβ 法 では max ノード での α 値 は、「それまでに計算された子ノードの評価値の最大値」と「そのノードの α 値の初期値」のうちの 最大値 である
- $s_{max}$ は 子ノードの評価値の最大値 なので、評価値が $s_{max}$ である 最初の子ノードを計算する際 の「それまでに計算された子ノードの評価値の最大値」は $s_{max}$ 未満 である
- $α < s_{max}$ なので、そのノードの α 値の初期値 である $α$ は $s_{max}$ 未満 である
- 従って、評価値が $s_{max}$ である 最初の子ノードを計算する際の α 値 は $s_{max}$ 未満 である
- 従って、評価値が $s_{max}$ である最初の子ノードを $C$ と表記すると、$α_C < S_C' < β_C$ となるので $C$ は exact value である
上記から、下記の理由で $N$ が深さ $i-1$ の max ノードで exact value の場合は、$N$ の評価値として計算された $S_N'$ には 必ず正しい評価値が計算されます。
- 数学的帰納法の証明の前提から、深さが $i$ のノードで下記の表の条件が成り立つ
- 上記で証明したように $N$ の 子ノード は fail low または exact value である
- 上記で証明したように $N$ の 評価値が $s_{max}$ である 最初の子ノードは exact value である
- $N$ の子ノードの深さは $i$ である
- 2、3、4 から以下の理由で $N$ の 子ノードの評価値の最大値 は 正しい値が計算 される
- 評価値が $s_{max}$ である $N$ の 最初の子ノードは exact value なので、その子ノードの評価値である $s_{max}$ は 正しい評価値 である
- $N$ の 他の子ノードは fail low または exact value なので、計算された評価値は「正しい評価値の上界」または「正しい評価値」である
- $N$ の 他の子ノードの評価値 は $s_{max}$ 以下8なので、それらのノードによって計算される 評価値の上界の最大値 は $s_{max}$ 以下 になる
- $s_{max}$ と 上界が $s_{max}$ の数値の 最大値 は $s_{max}$ である9
- 従って、$N$ の 子ノードの評価値の最大値 は exact value で計算された 正しい評価値 である $s_{max}$ となる
- $N$ は max ノードで exact value なので 子ノードの評価値の最大値が計算 される
- 5 と 6 から $N$ の評価値 $S_N'$ には 本当の評価値が計算 され 下記の表の条件が成り立つ
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
max ノードで fail high の場合
$N$ が深さ $i-1$ の max ノードで fail high の場合は、$N$ の評価値として 子ノードの中で β 値以上の評価値となる最初の子ノードの評価値が計算 されます。その子ノードを $C$ と表記した場合は、下記の理由で $C$ は fail high になります。
- max ノードでは β 値は変化しないので、β 値は初期値である β のまま変化しない
- 従って、$C$ の評価値を計算する際の β 値の初期値 である $β _C$ は $N$ の β 値の初期値である β と同じ になる
- $C$ の評価値は β 値以上 なので、$β_C ≦ S_C'$ となるので $C$ は fail high である
このことから、下記の理由から $N$ が深さ $i-1$ の max ノードで fail high の場合は 下記の表の条件が成り立ちます。
- 数学的帰納法の証明の前提から、深さが $i$ のノードで下記の表の条件が成り立つ
- 上記で証明したように、$N$ の評価値が計算される $C$ は fail high である
- $N$ の子ノードである $C$ の深さは $i$ である
- 2 と 3 から $C$ の評価値には 本当の評価値の下界 が計算される
- $N$ の評価値には $C$ の評価値が計算 されるので、本当の評価値の下界が計算 され、下記の表の条件が成り立つ
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
min ノードの場合
min ノード の場合はいずれの場合でも max ノードと同様の手順で証明を行うことが出来る ので、その証明は省略します。興味がある方は証明を行ってみて下さい。
以上から必要な条件がすべて証明されたので、全ての $N$ に対して 下記の表の条件が成り立つ ことが示されました。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
ルートノードで正しい評価値が計算される理由
ルートノードで正しい評価値が計算される理由 は、上記の表 によっても 説明することが出来ます。その方法について少し考えてみて下さい。
ルートノード では α 値と β 値 として 負の無限大と正の無限大を設定 して計算を行ないます。これまでの例で計算した 評価値は必ずその範囲に収まる ので、ルートノードは exact value の性質を持ちます。従ってルートノードでは必ず正しい評価値が計算されます。
また、以前の記事で紹介した ルートノード で α 値と β 値の初期値 として 評価値の最小値と最大値を設定 する場合も下記の理由で 正しい評価値が計算されます。
-
fail low になった場合は 正しい評価値の上界が計算 されるが、以下の理由で 評価値の最小値が計算 され、それは 正しい評価値である
- α 値の初期値 は 評価値の最小値 である
- α 値の初期値未満の評価値が計算された場合は、正しい評価値 が 評価値の最小値未満である と計算されたことになり 矛盾する
- 従って fail low になった場合の評価値は 評価値の最小値が計算 される
- 評価値が 評価値の最小値未満になることはない ので、計算された評価値は 正しい評価値である
- fail high の場合も同様 に評価値の最大値が正しい評価値として計算される
- 従って、ルートノードでは必ず正しい評価値が計算される
α 値と β 値の初期値 として 評価値の最小値と最大値を設定 する場合の ai_abs3 という AI を下記のプログラムのように定義し、強解決の AI であるかを確認してみることにします。なお、ai_abs2 では評価値として -1 ~ 1 の範囲の値を計算します。
- 2 行目：関数の名前を修正する
- 3 行目：α 値と β 値の初期値を評価値の最小値と最大値である -1 と 1 にする
1 @ai_by_score
2 def ai_abs3(mb, debug=False):
元と同じなので省略
3 score = ab_search(mb, -1, 1)
4 dprint(debug, "count =", count)
5 if mb.turn == Marubatsu.CIRCLE:
6 score *= -1
7 return score
行番号のないプログラム
@ai_by_score
def ai_abs3(mb, debug=False):
count = 0
def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
nonlocal count
count += 1
if mborig.status == Marubatsu.CIRCLE:
return 1
elif mborig.status == Marubatsu.CROSS:
return -1
elif mborig.status == Marubatsu.DRAW:
return 0
legal_moves = mborig.calc_legal_moves()
if mborig.turn == Marubatsu.CIRCLE:
score = float("-inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = max(score, ab_search(mb, alpha, beta))
if score >= beta:
return score
alpha = max(alpha, score)
return score
else:
score = float("inf")
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score = min(score, ab_search(mb, alpha, beta))
if score <= alpha:
return score
beta = min(beta, score)
return score
score = ab_search(mb, -1, 1)
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
修正箇所
@ai_by_score
-def ai_abs2(mb, debug=False):
+def ai_abs3(mb, debug=False):
元と同じなので省略
- score = ab_search(mb)
+ score = ab_search(mb, -1, 1)
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
上記の実行後に下記のプログラムを実行すると、実行結果から ai_abs2 が強解決の AI である ことが確認できるので、この方法で αβ 法の計算が正しく行える ことが確認できました。
Check_solved.is_strongly_solved(ai_abs3)
実行結果
100%|██████████| 431/431 [00:02<00:00, 177.20it/s]
431/431 100.00%
(True, [])
今回の記事のまとめ
今回の記事では αβ 法で計算された評価値が下記の表の性質を持つことを証明しました。
| $S'_N$ の範囲 | $S_N$ との関係 | 意味 | 用語 |
|---|---|---|---|
| $S'_N ≦ α$ | $S_N ≦ S'_N$ | 本当の評価値は $S'_N$ 以下 本当の評価値の上界がわかる |
fail low |
| $α < S'_N < β$ | $S_N = S'_N$ | 本当の評価値が求められる | exact value |
| $β ≦ S'_N$ | $S'_N ≦ S_N$ | 本当の評価値は $S'_N$ 以上 本当の評価値の下界がわかる |
fail high |
次回の記事ではこの性質を利用した効率の良い置換表を利用した αβ 法の実装を行うことにします。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| ai.py | 本記事で更新した ai_new.py |
次回の記事
-
$s_{max}$ を直接求めることが出来るのは max ノードで $α < s_{max} < β$ の場合だけです ↩
-
αβ 法でこの場合の事を exact value と表記する例を見つけられなかったので、αβ 法でのこの場合に使われる正式な用語ではないと思います。正式な用語をご存じの方がいればコメントで教えて頂ければ助かります。なお、評価値が確定するので、確定値と呼ぶ場合もあるようです ↩
-
これらは αβ 法で実際に用いられている用語です。fail low と fail high という用語が付けられた由来については、今後の記事で説明する予定です ↩
-
先程では max ノードの場合は本当は $S_N = α$ であるのを $S_N ≦ α$ と表記していました ↩
-
ミニマックス法ではすべてのノードの評価値を計算しますが、αβ 法では枝狩りが行われるため一部のノードの評価値だけを計算します ↩
-
深さが 0 のルートノードには親ノードは存在しないのでこの条件が必要になります ↩
-
数学的帰納法という名前から誤解されがちですが、この手法は問題の証明を問題の前提から論理的に導き出しているので演繹法です ↩
-
$s_{max}$ の評価値を持つ子ノードが複数存在する場合があるので、未満ではなく以下になります ↩
-
例えば「10」と「10 以下の数値」の最大値は「10」になります ↩