LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その163　null window search

Last updated at Posted at 2025-04-03

目次と前回の記事

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

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

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

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

αβ 法の効率化の手法

αβ 法 を利用することで、ミニマックス法と同じ評価値 を、ミニマックス法よりも 効率よく計算 することができますが、計算時間は短いほうが望ましい ので、αβ 法を さらに効率化するための様々な手法 が考えられています。本記事ではこれまでに以下のような αβ 法の効率化を紹介済です。

  • move ordering
    以前の記事で紹介した 子ノードの評価値の計算 を、評価値が高い順 に行うように 並べ替える という手法のことです。以前の記事ではこの手法の呼び方について紹介するのを忘れていましたが、この手法のことを move ordering（直訳すると合法手の並べ替え）と呼びます
  • 置換表付き αβ 法1
  • α 値と β 値の初期値を評価値の最小値と最大値に設定 する手法
    以前の記事で説明した効率化です。実はこの手法は今回の記事で説明する null window search を利用した効率化の手法と類似しています

上記のうち move ordering が αβ 法の枝狩りの 効率の上昇に最も大きく寄与する と言われています。

置換表付き αβ 法 は、同一局面が頻繁に生じる ようなゲームでは効率の上昇に大きく寄与します。

本記事では null window、または null window search と呼ばれる手法を利用した αβ 法（または αβ 法に類似するアルゴリズム）の効率を向上させる いくつかのアルゴリズムを紹介することにします。なお、null window search の適切な日本語訳を探したのですが見つからなかったので、本記事では null window search と英語でそのまま表記することにします。

null window を直訳すると「（中身が）0 のウィンドウ」という意味になりますが、下記の Chess programming の wiki では null window という用語が「A Null Window, 略, is a way to 略」のように説明されており、「手法（way）」という意味で null window という用語が使われているようです。

null window には以下のような様々な呼び方があるようです。

  • zero window：ウィンドウ幅（意味は後述します）が 0 なため
  • scout window：確証はありませんが、おそらく次回の記事で説明する scout 法で null window の手法がはじめて利用されたため
  • narrow window：実際にはウィンドウ幅が 0 ではなく非常に小さな狭い（narrow）値とするのが一般的であるため

参考までに null window の Chess programing の wiki と、null window search の Wikipedia のリンクを下記に示します。

null window search

最初に null window search を説明するために必要ないくつかの 用語を説明 します。

なお、説明を短くするために以前の記事と同様に、ノードの評価値を計算する際の α 値と β 値の初期値 を 単に $\boldsymbol{α}$、$\boldsymbol{β}$ と表記 することにします。

ウィンドウとウィンドウ幅

αβ 法では、ノードの評価値 として $\boldsymbol{α}$ と $\boldsymbol{β}$ の範囲内の値が計算 された場合は、正確なミニマックス値が計算 されます。本記事 ではその 範囲内として計算された評価値 のこと 厳密（exact）なミニマックス値が計算される ことから本記事独自の用語として exact value と表記 してきました。αβ 法では、この $\boldsymbol{α}$ と $\boldsymbol{β}$ の範囲2のことを ウィンドウ（window）、範囲の幅（$= β - α$） のことを ウィンドウ幅（window width）と呼びます。

本記事では以後は exact valut の範囲と同じ である $\boldsymbol{α}$ と $\boldsymbol{β}$ の範囲 のことを ウィンドウ と表記することにします。

コンピューター用語では、αβ 法に限らず 何らかの範囲を表すもの のことを window と呼ぶ ことが良くあります。これは、現実の窓（window）が 範囲を持つことが由来 となっています。

また、アプリケーションが表示される四角い領域のことを window と呼ぶのは、窓のような四角い範囲の領域にアプリケーションの内容を表示することが由来です。

null

null とは 数学で 0 を意味する用語 で、null window とは ウィンドウ幅が 0 の状態、すなわち $α$ と $β$ が等しい状態 を意味します。ただし、null window search では、実際には後述する理由から ウィンドウ幅 を 0 ではなく、1 などの小さな値とするのが一般的 です。

null window search とは何か

以下の説明では αβ 法で評価値を計算するノードのことを $N$ と表記することにします。

これまでに説明 してきた αβ 法 では $N$ の評価値を計算する際に、正確なミニマックス値が計算 される exact value の範囲である ウィンドウ（$α$ と $β$ の範囲）を以下のいずれかに設定することで、評価値の範囲を全て含む ようにしました。また、$N$ の 子孫ノードの評価値を計算 する際は、ウィンドウを 親ノードの評価値の計算に影響を与える範囲 として設定していました。その結果 $N$ の 正確なミニマックス値を求める ことができます。

  • $α$ と $β$ を負の無限大と正の無限大とする
  • $α$ と $β$ を評価値の最小値と最大値とする

逆に言えば、$N$ の評価値を計算する際の ウィンドウ が、評価値として計算される値の範囲（これまでの例では -1 ~ 1 や -2 ~ 3 の範囲）を含まない 場合は、$N$ の評価値として fail low や fail high の範囲の値が 計算される場合があり、その場合は 正確なミニマックス値を計算することはできません。

$α$ と $β$ は ウィンドウには含まれない ので、上記の $\boldsymbol{α}$ と $\boldsymbol{β}$ を評価値の最小値と最大値とする場合 は実際には 評価値の範囲がすべて含まれるわけではありません。ただし、その場合は fail low と fail high に 含まれる評価値 が「評価値の最小値」と「評価値の最大値」の 1 種類しか存在しない ため、fail low や fail high の範囲として計算された評価値が 正確なミニマックス値 となります。

ただし、正確な評価値を計算することができなくても、fail low の場合は「ミニマックス値が 計算された評価値以下 であること」、fail high の場合は「ミニマックス値が 計算された評価値以上」であることは わかります。

また、ウィンドウを狭くする ことで α 狩りと β 狩りの対象とならない exact value の範囲が減り、枝狩りが行われやすくなる ため、計算時間が短く なるというメリットが生じます。

そこで、$N$ やその子孫ノードの評価値を計算する際に、正確なミニマックス値を計算する必要がない 場合は、ウィンドウを狭く設定 することで 計算時間を短くする という工夫を行う場合があります。

その際に、ウィンドウ幅 を 0 または 0 に近い値に設定 することで、枝狩りの効率を高める手法 のことを null window search と呼びます。なお、一般的には後述する理由から ウィンドウ幅を 0 としません が、そのような場合でも null window search と呼びます。

null window search とは αβ 法 で ウィンドウ幅を 0 または 0 に近い値に設定 してノードの評価値の計算を行うという手法のことである。

従って、null window search の 計算手順 は αβ 法と完全に同じ です。

ウィンドウ幅が 0 の null window search

最初に ウィンドウ幅が 0 の null window search について説明し、一般的に null window search では ウィンドウ幅を 0 にしない理由 について説明します。

null window search でウィンドウ幅を 0 にしない理由を説明した文章を筆者には見つけられなかったので、本記事でのウィンドウ幅を 0 にしない理由の説明は筆者が考えたもの です。そのため間違っているかもしれません。間違いに気づいた方がいらっしゃればコメントなどで指摘して頂けると助かります。

ウィンドウ幅が 0 の場合の αβ 法が計算する評価値の意味

これまでの記事での αβ 法 では以前の記事で説明した理由から、$α < β$、すなわち $α$ と $β$ が等しくなることはないので、ウィンドウ幅が 0 になることはありませんでした。

ただし、$N$ の評価値を計算する際に $α$ と $β$ を わざと等しく設定する場合 はその限りではありません。これまでの記事の説明では $α < β$ が等しくないという前提で説明を行なってきたので、 ウィンドウ幅が 0（$α = β$）の場合に αβ 法で計算される評価値の性質 について説明します。

下記は以前の記事で説明した、$\boldsymbol{α < β}$ の場合に αβ 法が計算する評価値の意味の再掲です。
$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

$\boldsymbol{α = β}$ の場合は上記の表の $α < S'_N < β$ の範囲は存在しない ので、上記の表は下記の表のようになり、一見すると exact value の範囲は存在しなくなるように見えるかもしれませんが、実際には exact value の範囲は存在します。どのように存在するかについて少し考えてみて下さい。

$S'_N$ の範囲 $S_N$ との関係 意味 用語
$S'_N ≦ α = β$ $S_N ≦ S'_N$ ミニマックス値は $S'_N$ 以下
ミニマックス値の上界がわかる		 fail low
$α = β ≦ S'_N$ $S'_N ≦ S_N$ ミニマックス値は $S'_N$ 以上
ミニマックス値の下界がわかる		 fail high

$α = β$ なので $β$ を $α$ に書き換えることもできますが、書き換えてしまうと $β < S'_N$ が fail high の範囲であることが直観的にわかりづらくなってしまうので書き換えないことにし、代わりに $S'_N < α = β$ のように記述することで $α = β$ であることが明確になるようにしました。

上記の表では $S'_N ≦ α = β$ と $α = β ≦ S'_N$ が別の行に記載されていますが、$α = β$ なので、$\boldsymbol{S'_N = α}$ の場合は $\boldsymbol{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$
かつ
$S'_N ≦ S_N$		 ミニマックス値は
$S'_N$ 以下かつ $S'_N$ 以上		 fail low
かつ
fail high
$α = β < S'_N$ $S'_N ≦ S_N$ ミニマックス値は $S'_N$ 以上
ミニマックス値の下界がわかる		 fail high

$S_N ≦ S'_N$ かつ $S'_N ≦ S_N$ という条件は $S_N = S_N'$ を意味します。従って $S'_N = α = β$ の場合は 正確なミニマックス値 が求められるので exact value となります。下記はそのように上記の表を修正したものです。

$S'_N$ の範囲 $S_N$ との関係 意味 用語
$S'_N < α = β$ $S_N ≦ S'_N$ ミニマックス値は $S'_N$ 以下
ミニマックス値の上界がわかる		 fail low
$S'_N = α = β$ $S_N = S_N'$ ミニマックス値は $S'_N$ である exact value
$α = β < S'_N$ $S'_N ≦ S_N$ ミニマックス値は $S'_N$ 以上
ミニマックス値の下界がわかる		 fail high

ウィンドウ幅が 0 の場合 は $α$ と $β$ が exact value である という点が、ウィンドウ幅が正の場合と 異なります。

ウィンドウ幅が 0（$α = β$）の場合に αβ 法で評価値を計算する null window search を行う ことで、そのノードの ミニマックス値の範囲 が 以下のいずれかである ことを計算することができる。

  • 計算された評価値以下である（$S'_N < α = β$ の場合）
  • 計算された評価値と等しい（$S'_N = α = β$ の場合）
  • 計算された評価値以上である（$α = β < S'_N$ の場合）

別の視点からみると、ウィンドウ幅が 0 の null window search を行うことで、ノードの ミニマックス値 が 特定の値（設定した $α$（= $β$））よりも大きい か、等しい か、小さい かの いずれであるかを計算 することができる。

今回の記事のこの後で紹介する手法では、ミニマックス値 が特定の値 よりも大きい か、等しい か、小さい かの すべての結果を利用 しますが、null window search を利用した効率化のアルゴリズムの多くは、ミニマックス値が特定の値と等しいかどうかではなく、特定の値よりも大きい（または 小さい）かどうか を 効率よく調べることができる という性質を利用します。具体例は次回の記事で紹介します。

評価値が 3 種類の場合の null window search の利用例

ウィンドウ幅が 0 の null window search を利用する具体例 として、今回の記事では 評価値が 3 種類 の場合の例を紹介します。具体的には　〇×ゲームで評価値として -1、0、1 の 3 種類 のみが計算される、最短の勝利を目指さない 評価値を計算する場合の例です。従って、評価値が -2 ~ 3 の範囲で 3 種類よりも多い、最短の勝利を目指す 評価値を計算する 場合はこの手法は利用できません。また、これまでの例ではでてきていませんが、評価値として実数が計算されるような場合でも利用できません。

なお、後述しますが この手法 は本記事で既に紹介済である、最短の勝利を目指さない場合に $\boldsymbol{α}$ と $\boldsymbol{β}$ を評価値の最小値と最大値とする という手法と 本質的に同じ です。従って、この手法による 枝狩りの効率 は $α$ と $β$ を評価値の最小値と最大値とする場合と 同じになります。それにも関わらずこの手法を最初に紹介したのは、行なう処理が直観的にわかりやすいと思ったからです。また、この手法の説明を行う過程で、一般的にウィンドウ幅を 0 としない理由が確認できる という理由もあります。

具体的には $N$ の評価値を αβ 法で計算する際に、$α$ と $β$ の 両方 を 3 つの評価値の真ん中の値 である 0 とした ウィンドウ幅が 0 の null window search として計算 する3と、下記の理由から 必ず正確なミニマックス値を計算 することができます。

  • $N$ の評価値として -1 が計算 された場合は fail low の範囲 なのでミニマックス値の範囲は -1 以下 であることが計算されるが、-1 以下の評価値は -1 しか存在しない ので -1 は 正確なミニマックス値 である
  • 同様の理由で $N$ の評価値として 1 が計算 された場合も 正確なミニマックス値 である
  • $N$ の評価値として 0 が計算 された場合は、先程のウィンドウ幅が 0 の場合の説明から exact value の範囲 となるので、 正確なミニマックス値 である
  • 上記から、全ての場合で正確なミニマックス値を計算 することができる

ai_nws_3score の定義

上記の方法で評価値を計算する AI の関数を定義 する事にします。最初に 置換表を利用しない場合 の ai_nw_3score という関数を定義します。なお、関数の名前の nws は null window search、3score は 3 種類の評価値（score）が計算されるという意味です。

ai_nw_3score はこれまでに作成した、αβ 法 で最短の勝利を目指さない 3 種類の評価値を計算 し、$N$ の評価値を計算する際の $\boldsymbol{α}$ と $\boldsymbol{β}$ を評価値の最小値と最大値 とする AI である ai_abs3 を下記のプログラムのように修正して定義することにします。具体的には 9 行目で $N$ の評価値を計算する際の $α$ と $β$ を 共に 0 に修正 して ウィンドウ幅を 0 とします。

 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_nws_3score(mb, debug=False):   
 7      count = 0
 8      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 9      score = ab_search(mb, 0, 0)
10      dprint(debug, "count =", count)
11      if mb.turn == Marubatsu.CIRCLE:
12          score *= -1
13      return score
行番号のないプログラム 
from ai import ai_by_score, dprint
from marubatsu import Marubatsu
from copy import deepcopy

@ai_by_score
def ai_nws_3score(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, 0, 0)
    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_abs3(mb, debug=False):   
+def ai_nws_3score(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
-   score = ab_search(mb, -1, 1)
+   score = ab_search(mb, 0, 0)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score

$α = β$ なので上記のプログラムの beta を削除して alpha に置き換えることもできますが、修正を間違えて バグが発生する可能性がある 点と、修正しなくてもプログラムは正しく動作する 点からそのような修正は行わないことにします。

上記を定義後に下記のプログラムで ai_nw_3score が 強解決の AI であるか どうかを確認すると、実行結果のように 強解決の AI ではない という表示が行なわれます。従って、ai_nw_3score には バグが存在する ということがわかります。どこが間違っているかについて少し考えてみて下さい。

from util import Check_solved

result, _ = Check_solved.is_strongly_solved(ai_nws_3score)
print(result)

実行結果

100%|██████████| 431/431 [00:00<00:00, 437.23it/s]
343/431 79.58%
False

バグの原因の考察と修正

このバグの原因は、ウィンドウ幅が 0 の場合 と そうでない場合 で α 狩りと β 狩りが行なわれる条件が異なるから です。

先程説明したように ウィンドウ幅を 0 とした場合 の αβ 法では、そうでない場合と比べて fail low、exact value、fail high の範囲 が以下の表のように 異なります。

ウィンドウ幅 fail low exact value fail high
0 $S_N' < α = β$ $S_N' = α = β$ $α = β < S_N'$
正の値 $S_N' ≦ α$ $α < S_N' < β$ $β ≦ S_N'$

上記の表のように、ウィンドウ幅が 0 の場合 は $α$（= $β$）は exact value ですが、ウィンドウ幅が 0 でない場合 は $α$ と $β$ は exact value ではありません。

max ノード で β 狩りが行なわれる条件 は子ノードの評価値が fail high の範囲となる ことですが、その 条件は下記の表のように異なる ので、その部分のプログラムを $\boldsymbol{β < S_N'}$ を計算する条件式で判定するように修正する 必要があります。

ウィンドウ幅 fail high
0 $β < S_N'$
正の値 $β ≦ S_N'$

同様に min ノード で α 狩りが行なわれる条件式 も $S_N' ≦ α$ から $\boldsymbol{S_N' < α}$ を計算する式に修正する必要 があります。

下記はそのように ai_nws_3score を修正したプログラムです。

  • 11 行目：max ノードで β 狩りが行なわれる条件式を score >= beta から score > beta に修正した
  • 21 行目：min ノードで α 狩りが行なわれる条件式を score <= alpha から score < alpha に修正した
 1  @ai_by_score
 2  def ai_nws_3score(mb, debug=False):
 3      count = 0
 4      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              score = float("-inf")
 7              for x, y in legal_moves:
 8                  mb = deepcopy(mborig)
 9                  mb.move(x, y)
10                  score = max(score, ab_search(mb, alpha, beta))
11                  if score > beta:
12                      return score
13                  alpha = max(alpha, score)
14              return score
15          else:
16              score = float("inf")
17              for x, y in legal_moves:
18                  mb = deepcopy(mborig)
19                  mb.move(x, y)
20                  score = min(score, ab_search(mb, alpha, beta))
21                  if score < alpha:
22                      return score
23                  beta = min(beta, score)   
24              return score
元と同じなので省略
行番号のないプログラム 
@ai_by_score
def ai_nws_3score(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, 0, 0)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
修正箇所 
@ai_by_score
def ai_nws_3score(mb, debug=False):
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        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:
+               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:
+               if score < alpha:
                    return score
                beta = min(beta, score)   
            return score
元と同じなので省略

上記を修正後に下記のプログラムで ai_nw_3score が 強解決の AI であることを確認 することができます。

result, _ = Check_solved.is_strongly_solved(ai_nws_3score)
print(result)

実行結果

100%|██████████| 431/431 [00:05<00:00, 82.11it/s] 
431/431 100.00%
True

このように、ウィンドウ幅を 0 にした場合とそうでない場合 では、αβ 法の α 狩りと β 狩りに関する処理を変更する必要 があります。これが ウィンドウ幅を 0 とした null window search が 一般的に利用されない理由の一つ だと思いますが、この後で説明する理由の方が重要 だと思います。

枝狩りの効率の比較

次に、ウィンドウ幅を 0 にすることで 枝狩りの効率がどのように変化したか を ai_abs3 と ai_nws_3score で ゲーム開始時の局面 の評価値を計算した際に 計算されるノードの数を表示 する下記のプログラムで比較することにします。

from ai import ai_abs3

mb = Marubatsu()
ai_abs3(mb, calc_score=True, debug=True)
ai_nws_3score(mb, calc_score=True, debug=True)

実行結果

count = 16811
count = 94978

実行結果から、ウィンドウ幅を 0 とした場合のほうが 計算したノードの数が約 6 倍も多く、効率が悪くなっている ことが確認できました。ウィンドウ幅が小さいほうが枝狩りの効率が高くなるはずなのに、逆に効率が悪くなっている点に驚いた人がいるかもしれませんが、これには理由があります。何故このようなことが起きるかについて少し考えてみて下さい。

枝狩りの効率が悪くなる理由

枝狩りの効率が悪くなる理由は、ウィンドウ幅を 0とした場合（$α = β$）に子ノードの評価値として $\boldsymbol{α}$（= $β$） が計算された場合 は 必ず exact value とみなされるため 枝狩りが行なわれない からです。

また、ウィンドウ幅を 0 とした場合は、下記の理由から $N$ の 全ての子孫ノード の評価値を計算する際の $\boldsymbol{α}$ と $\boldsymbol{β}$ が $\boldsymbol{N}$ の $\boldsymbol{α}$ と $\boldsymbol{β}$ と同じ値 になります。なお、表記が紛らわしいですが 「$\boldsymbol{α}$」 はそのノードの評価値を計算する際の α 値の初期値、「α 値」は子ノードの評価値を計算する際に受け継ぐ その時点での α 値 のことを表します。

  • 子ノードの評価値を計算する際の $α$ と $β$ は 親ノードの α 値と β 値を受け継ぐ
  • max ノード では、子ノードに受け継ぐ α 値と β 値 は 以下のように計算 される
    • α 値 は max ノードではそれまでに計算した 子ノードの評価値 と $\boldsymbol{α}$ のうちの 最大値 である
    • ただし、子ノードの評価値 が $\boldsymbol{β}$（= $α$）を超えた場合 は β 狩りが行われる
    • 従って max ノード で子ノードに受け継ぐ α 値は常に $\boldsymbol{α}$ となる
    • β 値 は $β$ のまま 変化しない
  • 同様の理由で min ノード でも子ノードに受けつぐ α 値と β 値は常に $\boldsymbol{α}$ と $\boldsymbol{β}$ となる

従って、$N$ に限らず、$N$ の全ての子孫ノード で $α$（= $β$）が計算された場合に 枝狩りが行われなくなります。先程の例の場合は $N$ とその子孫ノードの評価値を計算する際に 常に $\boldsymbol{α = β = 0}$ となる ので、どのノードであっても 子ノードの評価値として 0 が計算 された場合に 枝狩りが行われることはありません.

一方で $α = -1$、$β = 1$ としてノード $N$ の評価値を計算する場合は、ウィンドウ幅が正の値（$β - α > 0$）なので $N$ の 子孫ノード の評価値を計算する際の ウィンドウ幅も正の値 となります。そのため、$N$ の max ノードの子孫ノードの $\boldsymbol{β}$ が 0 となった場合 に子ノードの評価値として 0 が計算 されると β 狩りが行われます。min ノードの場合も同様です。

上記をまとめると以下のようになります。これが null window search で ウィンドウ幅を 0 にしない最も大きな理由 だと思います。

ウィンドウ幅を 0 とした場合 は、$\boldsymbol{α}$（= $β$）が exact value の範囲となってしまう ため、子ノードの評価値として $α$（= $β$） が計算された場合に α 狩りまたは β 狩りが行なわれなくなる。そのため、その分だけ 枝狩りの効率が悪くなってしまう。

評価値として $α$（= $β$）が計算されることがない場合はノードの評価値が exact value として計算されることはないので、ウィンドウ幅を 0 にしても枝狩りの効率が悪くなることはありません。例えば評価値として -1、0、1 が計算される場合に $α = β = 0.5$ として計算を行う場合などです。

ただし、null window search を利用した多くのアルゴリズムでは $α$ や $β$ に実際に評価値として計算される値を設定する（具体例については次回の記事で説明します）ので、ウィンドウ幅を 0 とすることはほとんどないでしょう。

ウィンドウ幅が正の null window search

上記で説明したように ウィンドウ幅を 0 としてしまうと 枝狩りの効率が悪くなります が、逆に言えば ウィンドウ幅が 0 でなければそのような問題は発生しません。また、ウィンドウ幅が 正の値の場合 はウィンドウ幅が 狭い程 枝狩りが行われない exact value の範囲が狭くなる ため 枝狩りが行われやすくなります。そのため null window search で 枝狩りの効率を上げる ためには ウィンドウ幅を出来るだけ小さな正の値 として設定する必要があります。

ただし、残念ながら 0 に最も近い正の値を求めることはできません。例えば $n$ という値が 0 に最も近い正の値であるとした場合は、$n / 2$ という $n$ よりも さらに 0 に近い正の値が存在 してしまうので 矛盾してしまう からです。そのため、null window search を行う際のウィンドウ幅として 常に採用できる最適な値は存在しません。

null window search では 一般的にウィンドウ幅を 1 と設定することが多い ようです。Wikipedia の null window search の説明でもそのように記載されていますが、その理由については記述されていません。ウィンドウ幅を 1 とする具体的な理由についての説明が見つけられなかった ので、その理由について後で 筆者なりに考察した内容を説明することにします。

ウィンドウの設定方法

上記では 一般的にウィンドウ幅を 1 と設定することが多い と説明しましたが、1 でなければならないという理由はありません。また、ウィンドウ幅を出来るだけ小さな正の値として設定する必要があると説明しましたが、実際には 枝狩りの効率が最も高くなるような値以下 であれば、ウィンドウ幅にどのような値を設定しても枝狩りの効率は変わりません。

そこで null window search で ウィンドウをどのように設定するべきか について説明します。

ウィンドウの設定方法の考え方

null window search では、ウィンドウ（枝狩りが行なわれない exact value の範囲）を狭くする ことで、枝狩りの効率を上げることが重要 です。従って、ウィンドウの中 には、正確なミニマックス値を計算したい評価値の値のみを含む範囲とする ことが 最も枝狩りの効率が高く なります。

具体例として、先程紹介した 評価値 が -1、0、1 の 3 種類しかない場合 の null window search の利用例でのウィンドウの設定方法の考え方について説明します。次回の記事では別の場合での考え方について説明します。

ウィンドウ幅が正の null window search は、ウィンドウの範囲をできるだけ小さく設定した αβ 法 なので、ミニマックス値が以下のいずれかであることを判定 することができます。

  • $α$ 以上である
  • $α$ と $β$ の間（$α$ と $β$ は含まない）である。この場合は正確なミニマックス値が求められる
  • $β$ 以下である

先程紹介した利用例は、3 種類の評価値 が上記の 3 種類の範囲の中 にそれぞれ 1 つずつ含まれるようにする ことで、正確なミニマックス値を計算するという手法です。

そのため、ウィンドウは 必ずその目的を満たすことができるような範囲として設定 する必要があります。具体的には 以下の条件を満たす必要 があります。

  • -1 のみが fail low の範囲に含まれる
  • 0 のみが exact value の範囲に含まれる
  • 1 のみが fail high の範囲に含まれる

この条件を満たすための $α$ と $β$ は以下のいずれかになります。

  • $α = β = 0$
  • $-1 ≦ α < 0 < β ≦ 1$

前者は先程説明したウィンドウ幅が 0 の場合で、後者はウィンドウ幅が $\boldsymbol{β - α}$ という 正の値 になります。前者は効率が悪いことを先程示したので、後者の条件を満たす $\boldsymbol{α}$ と $\boldsymbol{β}$ を決めることでウィンドウが決まります。

ai_nws_3score2 の定義

$\boldsymbol{α}$ と $\boldsymbol{β}$ は $-1 ≦ α < 0 < β ≦ 1$ を 満たしていればどのような値でもかまいません。先程 null window search ではウィンドウ幅を 1 と設定することが多いと説明しましたので、上記の条件を満たす $α = -0.5$、$β = 0.5$ とした ウィンドウ幅を 1 とする null window search で計算を行う ai_nws_3score2 を下記のプログラムのように定義することにします。

  • 2 行目：関数の名前を ai_nws_3score2 に修正する
  • 11、21 行目：ウィンドウ幅が 0 ではなくなったので、α 狩りと β 狩りを行う条件式を元に戻す
  • 26 行目：$N$ の評価値を計算する際の $α$ と $β$ を -0.5 と 0.5 に修正する
 1  @ai_by_score
 2  def ai_nws_3score2(mb, debug=False):   
 3      count = 0
 4      def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 5          if mborig.turn == Marubatsu.CIRCLE:
 6              score = float("-inf")
 7              for x, y in legal_moves:
 8                  mb = deepcopy(mborig)
 9                  mb.move(x, y)
10                  score = max(score, ab_search(mb, alpha, beta))
11                  if score >= beta:
12                      return score
13                  alpha = max(alpha, score)
14              return score
15          else:
16              score = float("inf")
17              for x, y in legal_moves:
18                  mb = deepcopy(mborig)
19                  mb.move(x, y)
20                  score = min(score, ab_search(mb, alpha, beta))
21                  if score <= alpha:
22                      return score
23                  beta = min(beta, score)   
24              return score
25                  
26      score = ab_search(mb, -0.5, 0.5)
27      dprint(debug, "count =", count)
28      if mb.turn == Marubatsu.CIRCLE:
29          score *= -1
30      return score
行番号のないプログラム 
@ai_by_score
def ai_nws_3score2(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, -0.5, 0.5)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
修正箇所 
@ai_by_score
-def ai_nws_3score(mb, debug=False):   
+def ai_nws_3score2(mb, debug=False):   
    count = 0
    def ab_search(mborig, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        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:
+               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:
+               if score <= alpha:
                    return score
                beta = min(beta, score)   
            return score
                
-   score = ab_search(mb, 0, 0)
+   score = ab_search(mb, -0.5, 0.5)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score

上記の定義後に下記のプログラムで ai_nw_3score2 が強解決の AI である ことを確認することができます。

result, _ = Check_solved.is_strongly_solved(ai_nws_3score2)
print(result)

実行結果

100%|██████████| 431/431 [00:03<00:00, 120.86it/s]
431/431 100.00%
True

枝狩りの効率の確認

下記のプログラムで ゲーム開始時の局面 の評価値を計算する際に 計算されたノードの数 を表示すると、先程の ai_abs3 と同じ 16811 が表示されます。これは、ai_abs3 と ai_nws_3score2 の枝狩りの効率が同じ であること表しますが、何故同じになるかについて少し考えてみて下さい。

ai_nws_3score2(mb, calc_score=True, debug=True)

実行結果

count = 16811

先程説明したように、-1、0、1 の 3 種類の評価値が計算される場合に、null window search のウィンドウの範囲を以下のいずれかに設定する必要があります。

  • $α = β = 0$
  • $-1 ≦ α < 0 < β ≦ 1$

ai_abs3 では $α = -1$、$β = 1$ として $N$ の評価値を計算しますが、これは 上記の 2 つ目の条件を満たしています。つまり、ai_abs3 と ai_nws_3score2 はウィンドウの範囲やウィンドウ幅は異なりますが、行なっている処理は 全く同じ意味の null window search を行なっている ということです。従って、枝狩りの効率が同じであることは当然です。

ai_abs3 と ai_nws_3score2 はウィンドウの範囲やウィンドウ幅は異なるが、全く同じ意味の null window search を利用した処理 を行っている。

null window search の条件

上記のような、ウィンドウ幅が 0 でない場合 の処理を null window search と呼ぶのに 違和感がある 人がいるかもしれません。また、ここまでの説明では、null window search と呼ぶためのウィンドウ幅の条件がはっきりしません。そこで、筆者なりに考えた null window search と呼ばれるための条件を説明 します。この解釈は間違っているかもしれないので、間違っている場合はコメントなどで指摘していただければ助かります。

null window search と呼んで良い条件 は、ウィンドウ幅を実際に 0 として計算しても良い場合 だと思います。例えば上記の場合は $α = β = 0$ として ウィンドウ幅 が 0 の αβ 法で計算を行なっても枝狩りの効率は悪くなりますが 正しい計算を行うことができます。

一方、最短の勝利を目指す場合 は評価値の範囲が -2 ~ 3 の整数で評価値の種類が 6 種類となりますが、その際に $α$ と $β$ を負の無限大と正の無限大ではなく、評価値の最小値と最大値である -2 と 3 に設定 してウィンドウ幅を狭くするという工夫は null window search と呼ぶことはできない と思います。その理由は、この場合は fail low と fail high の範囲に取りうる評価値が 1 つしかないことを利用しているため、$-2 ≦ α < -1$、$2 < β ≦ 3$ という条件が必要となるため、$β - α > 2 - (-1) = 3$ となるため ウィンドウ幅を 0 とすることができないから です。

ウィンドウ幅を 0 とすることはできませんが、ウィンドウの範囲から -2 と 3 という評価値を取り除いて ウィンドウ幅を狭めることで枝狩りの効率を高めている という点では、最短の勝利を目指さない場合と 同様の工夫を行なっています。

ウィンドウ幅に 1 が一般的に設定される理由の推察

筆者が調べた範囲では null window search でウィンドウ幅に 1 が一般的に設定される理由 はおそらく以下のようなものだと考えられます。正しい理由をご存じの方がいればコメントなどで教えて頂ければ助かります。

初期の論文のウィンドウ幅が 1 となっている

null window search に関する初期の論文(An optimization of alpha-beta search, SIGART Bulletin, Issue 72)でウィンドウ幅 を 1 とした例が紹介されているので、もしかするとそれが踏襲されているのかもしれません。

整数を評価値として計算する場合はウィンドウ幅として 1 が適している

先程紹介した null window の Chess programing の wiki には理由は説明されていませんが、下記のように 評価値が整数（integer）の場合は $α = β - 1$、すなわち ウィンドウ幅を 1 とすると説明されています。

With integers a null-window is defined as alpha == beta - 1.

これは、評価値として整数のみが計算される場合 は ウィンドウ幅を 1 とし、ウィンドウの境目 である $α$ と $β$ を 整数に設定する ことで ウィンドウの範囲内に取りうる評価値が 1 つも含まれない ようにすることができるからだと思います。

例えば ウィンドウ幅を 1 とし $α$ と $β$ を 0 と 1 のような整数として設定 した場合は、exact value の範囲 は $0 < S_N' <1 $ となるので 整数である評価値が一つも含まれなくなります。

今回の記事で紹介した ai_nws_score2 ではそうなっていませんが、null window search を利用した アルゴリズムの多く は、ウィンドウの範囲内 に 正確に計算したい評価値を含む必要がありません。従って、評価値として整数のみが計算 される場合は、ウィンドウの境目を整数 とし、ウィンドウ幅を 1 にすることが多くの場合で 適していると言える でしょう。

評価値が実数になる場合の null window search のウィンドウ幅

評価値として実数（整数以外の値）が計算される場合 は、ウィンドウ幅を 1 よりも狭くしたほうが枝狩りの効率が良くなる 可能性が生じます。null window search を行う際の ウィンドウを設定する際 には、何も考えずにウィンドウ幅を 1 とするのではなく、ウィンドウの範囲内 にある、正確な値を計算する必要がない 評価値が 計算される確率が充分に小さくなるような範囲を設定 したほうが良いでしょう。

置換表つき αβ 法の場合

置換表付き αβ 法 でも ai_nws_3score2 と同様の方法 で null window search を利用することができます。そのような計算を行う ai_nws_3score_tt は、置換表付き αβ 法の処理を行う ai_abs_tt4 を下記のプログラムのように修正することで定義できます。

なお、ai_abs_tt4 は仮引数 shortest_victory によって 最短の勝利を目指す評価値を計算する機能を持ちます が、最短の勝利を目指す場合の評価値は 3 種類ではない ので、ai_nws_3score_tt では shortest_victory に関する処理は削除 しました。また、$-1 ≦ α < 0 < β ≦ 1$ の条件が満たされていれば、他のウィンドウ幅でも構わない ことを示すために、$α = -0.05$、$β = 0.05$ としてウィンドウ幅を 0.1 にしました。

  • 2 行目：関数の名前を ai_nws_3score に修正した
  • 2、8、10、13、14 行目：shortest_victory に関する処理を削除した
  • 16 行目：ルートノードの評価値を計算する際の α 値と β 値の初期値を -0.05 と 0.05 に修正する
 1  @ai_by_score
 2  def ai_nws_3score_tt(mb, debug=False):
 3      count = 0
 4      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
 5          nonlocal count
 6          count += 1
 7          if mborig.status == Marubatsu.CIRCLE:
 8              return 1
 9          elif mborig.status == Marubatsu.CROSS:
10              return -1
11          elif mborig.status == Marubatsu.DRAW:
12              return 0
元と同じなので省略
13      min_score = -1
14      max_score = 1
15  
16      score = ab_search(mb, {}, alpha=-0.5, beta=0.5)
17      dprint(debug, "count =", count)
18      if mb.turn == Marubatsu.CIRCLE:
19          score *= -1
20      return score
行番号のないプログラム 
@ai_by_score
def ai_nws_3score_tt(mb, debug=False):        
    count = 0
    def ab_search(mborig, tt, 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
        
        boardtxt = mborig.board_to_str()
        if boardtxt in tt:
            lower_bound, upper_bound = tt[boardtxt]
            if lower_bound == upper_bound:
                return lower_bound
            elif upper_bound <= alpha:
                return upper_bound
            elif beta <= lower_bound:
                return lower_bound
            else:
                alpha = max(alpha, lower_bound)
                beta = min(beta, upper_bound)
        else:
            lower_bound = min_score
            upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        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, tt, alpha, beta))
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mb = deepcopy(mborig)
                mb.move(x, y)
                score = min(score, ab_search(mb, tt, alpha, beta))
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
        from util import calc_same_boardtexts

        boardtxtlist = calc_same_boardtexts(mborig)
        if score <= alphaorig:
            upper_bound = score
        elif score < betaorig:
            lower_bound = score
            upper_bound = score
        else:
            lower_bound = score
        for boardtxt in boardtxtlist:
            tt[boardtxt] = (lower_bound, upper_bound)
        return score
                
    min_score = -1
    max_score = 1

    score = ab_search(mb, {}, alpha=-0.05, beta=0.05)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
修正箇所 
@ai_by_score
def ai_nws_3score_tt(mb, debug=False):
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        count += 1
        if mborig.status == Marubatsu.CIRCLE:
-           return (11 - mborig.move_count) / 2 if shortest_victory else 1
+           return 1
        elif mborig.status == Marubatsu.CROSS:
-           return (mborig.move_count - 10) / 2 if shortest_victory else -1
+           return -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
元と同じなので省略
-   min_score = -2 if shortest_victory else -1
+   min_score = -1
-   max_score = 3 if shortest_victory else 1
+   max_score = 1

-   score = ab_search(mb, {}, alpha=min_score, beta=max_score)
+   score = ab_search(mb, {}, alpha=-0.05, beta=0.05)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score

ai_nws_3score_tt では、全てのノードで正確なミニマックス値を計算することができるので、置換表にミニマックス値の下界と上界を分けて記録する必要はありません。ただし、置換表にミニマックス値だけを記録るように修正しなくてもプログラムは正しく動作するのでそのような修正は行わないことにします。

上記の定義後に下記のプログラムで ai_nw_3score_tt が強解決の AI である ことを確認することができます。

result, _ = Check_solved.is_strongly_solved(ai_nws_3score_tt)
print(result)

実行結果

100%|██████████| 431/431 [00:03<00:00, 142.96it/s]
431/431 100.00%
True

下記のプログラムで ゲーム開始時の局面 の評価値を計算する際に 計算したノードの数 を ai_abs_tt4 と ai_abs_3score_tt で計算すると、どちらも同じ計算結果が表示される ことが確認できます。これは先程説明したように ai_abs_tt4 のウィンドウである $α = -1$、$β = 1$ と、ai_abs_3score_tt のウィンドウである $α = -0.05$、$β = 0.05$ が 実質的に同じ計算を行なっている からです。

from ai import ai_abs_tt4

ai_abs_tt4(mb, calc_score=True, debug=True)
ai_nws_3score_tt(mb, calc_score=True, debug=True)

実行結果

count = 832
count = 832

今回の記事のまとめ

今回の記事では null window search について説明し、null window search で 一般的にウィンドウ幅を 0 としない理由 について説明しました。また、null window search の 利用例の一つ を説明し、その方法が 既に紹介していた方法と実質的に同じ であることを説明しました。

次回の記事では null window search によって枝狩りの効率を向上させる手法について説明します。

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

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

次回の記事

  1. リンク先の記事が置換表付き αβ 法の説明ですが、その記事ではまだ「置換表付き αβ 法」とは表記していませんでした。置換表付き αβ 法と表記し始めたのはその次の記事からです ↩

  2. ウィンドウの範囲に $α$ と $β$ は含まれません ↩

  3. $α$ と $β$ を 0 としたことが null window search の条件ではない点に注意して下さい。$α$ と $β$ を 同じ値にする ことで ウィンドウ幅を 0 とした ことが null window search の条件です ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?