Pythonで〇×ゲームのAIを一から作成する その165 スカウト法のアルゴリズムと性質

目次と前回の記事

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

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

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

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

スカウト法

今回の記事では、null window search を使った手法の一つである スカウト（scout）法 について説明します。スカウト法について記事を書いた後でいくつか勘違いしていたことに気が付きましたので、一度書いた内容を大幅に修正したため更新が遅くなりました。

スカウト法は move ordering を前提 とする手法ですが、前回の記事で説明したように move ordering の 精度は通常は 100 % ではない ので、今回の記事では move ordering の 精度が 100 % ではないという前提 で話を進めることにします。

また、max ノードと min ノードでの考え方は同じなので、今回の記事でも特に記述がなければ max ノードの場合での説明を行います。

なお、勘違いしていたのは move ordering が 100 % の場合にスカウト法で行われる処理で、その点については次回以降の記事で説明します。

参考までに Chess Programming wiki と Wikipedia のスカウト法のリンクを下記に紹介します。Wikipedia のほうはスカウト法を改良したネガスカウト法のリンクですが、行われる処理はスカウト法と本質的に同じです。スカウト法の論文などの参考文献について知りたい方は、リンク先の記事を参照して下さい。

今回の記事で利用する記号

今回の記事では以下の記号を使って説明を行います。

• 以前の記事と同様に、ノードの評価値を計算する際の α 値と β 値の初期値 を $\boldsymbol{α}$、$\boldsymbol{β}$ と表記する。また、次の子ノードの評価値を計算する時点での α 値と β 値 は、α 値、β 値 と表記して区別する
• αβ 法でノードの評価値を計算する際に下記の記号を用いる
  • α 値と β 値の範囲 を表す ウィンドウ を (α 値, β 値) のように () の記号で表記 する
  • $\boldsymbol{i}$ 番目の子ノードの評価値 を $\boldsymbol{s_i}$ と表記する
  • それまでに計算されたノードの評価値 を $\boldsymbol{s}$ と表記する。$s$ は max ノードではそれまでに計算された子ノードの評価値の最大値、min ノードでは最小値である
• $a$ と $b$ の最大値を $max(a, b)$、最小値を $min(a, b)$ と表記する

数学では $a$ より大きく $b$ より小さい範囲のように、端を含まない範囲 を $(a, b)$ と表記します。また、$a$ 以上 $b$ 以下の範囲のように 端を含む範囲 を $[a, b]$ のように表記します。また、両方を組み合わせた $a$ 以上 $b$ 未満の範囲は $[a, b)$ と表記します。

このような数値の範囲のことを数学では 区間 と呼びます。参考までに、区間に関する wikipedia のリンクを下記に示します。

スカウト法のアルゴリズム

スカウト法 は move ordering を行う αβ 法 に下記の 手順 3 の修正を加えた処理を行う というアルリズムです。下記では置換表に関する処理を省略していますが、置換表に関する処理を含め、下記の手順 3 以外は move ordering を行う αβ 法と全く同じ処理 を行います。

1. move ordering を行う
2. 先頭の子ノードの評価値の計算処理 を αβ 法と同じ 方法で計算する
3. 2 番目以降の子ノード の評価値の計算処理を以下の手順で行う。以下は $i$（$i ≧ 2$）番目の子ノードの評価値 $s_i$ を計算する場合の処理の説明である
   • max ノード の場合は以下の手順で計算を行う
     1. ウィンドウを (α 値, α 値 + 1) とした αβ 法 で $s_i$ を計算し、$s$ を更新する
     2. $s$ の値に応じて以下の処理を行う
        • β 値 ≦ $\boldsymbol{s}$¹ の場合は $s$ をこのノードの評価値として処理を終了するという、β 狩り の処理を行う
        • α 値 < $\boldsymbol{s}$ < β 値 の場合は ウィンドウを (α 値, β 値) とした αβ 法と同じ方法 で 計算しなおす。$s$ や α 値の更新、β 狩りの処理も αβ 法と同じ
        • $\boldsymbol{s}$ ≦ α 値 の場合は何もしない
   • min ノード の場合は以下の手順で計算を行う
     1. ウィンドウを (β 値 - 1, β 値) とした αβ 法 で $s_i$ を計算し、$s$ を更新する
     2. $s$ の値に応じて以下の処理を行う
        • $\boldsymbol{s}$ ≦ α 値 の場合は $s$ をこのノードの評価値として処理を終了するという、β 狩り の処理を行う
        • α 値 < $\boldsymbol{s}$ < β 値 の場合は ウィンドウを (α 値, β 値) とした αβ 法と同じ方法 で 計算 しなおす。$s$ や β 値の更新、α 狩りの処理も αβ 法と同じ
        • β 値 ≦ $\boldsymbol{s}$ の場合は何もしない

αβ 法との違い は以下の通りです。

• 2 番目以降の子ノード の評価値を計算する際に αβ 法以下のウィンドウ幅 で計算を行う
• 2 番目以降の子ノードの 評価値の計算結果によって、その子ノードの評価値を αβ 法と同じウィンドウで計算し直す 場合がある

なお、置換表に関する処理 は αβ 法とスカウト法で 全く同じ なので、置換表を利用する場合とそうでない場合の両方でスカウト法を利用することができます。以後は置換表を利用しない場合の説明を行ないますが、置換表を利用する場合でも説明の内容は同じです。

スカウト法の性質

スカウト法 は move ordering の精度が 100 % でない場合 に、move ordering の精度が充分高ければ 枝狩りの効率が αβ 法 以上になることが期待できる² ように αβ 法を改良 したアルゴリズムです。

逆に言えば、move ordering の精度が悪く、評価値が低いノードが先頭に並べ替えられてしまった場合 は、スカウト法によって 枝狩りの効率 が αβ 法よりも 悪くなる可能性が高くなります。

先程説明したスカウト法のアルゴリズムによって上記のような性質が得られる理由について少し考えてみて下さい。

なお、スカウト法によって どの位の枝狩りの効率の上昇が得られるか は、ゲーム木の内容によっても異なります。従って、ゲームの種類 や、同じゲームでも 局面の違いによって はスカウト法で 効率の上昇がほとんど得られない場合があります。

スカウト法の性質に関する筆者の誤解

先程紹介したスカウト法と同様の処理を行う ネガスカウト法の wikipedia では「NegaScout が効率よく機能するかどうかは手の並べ替えの精度に依存しており、初めに調べる手が最善手である場合に最も効率が良くなる」と記載されています。そのため、今回の記事では最初は以下のような説明を記述していましたが、それは 筆者の誤解である ことがわかったので記事を大幅に修正しました。もしかするとそのように勘違いしている人がいるかもしれませんので、下記の説明がどのように間違っているかについては次回以降の記事で説明します。

move ordering の精度が 100%で、先頭の子ノードの評価値が最も高い場合にスカウト法の効率が αβ 法と比較して最も高くなる。

上記の説明は 間違っている ので赤い背景色のノートにしました。

なお、上記で引用した Wikipedia の説明は厳密には間違ってはいない と思いますが、誤解を産みやすい表現 だと思います。その点についても次回以降の記事で説明する予定です。

スカウト法の考え方

スカウト法 では 最初の子ノード の評価値は αβ 法と同じ方法で計算 されるので、最初の子ノードの評価値の 計算の効率 と 計算結果 である $\boldsymbol{s_1}$ の値は 変わりません。従って、子ノードの数が 1 以下 の場合に行なわれる処理は αβ 法と変わらない ので、以下では 子ノードが 2 つ以上ある場合について説明 します。

スカウト法で行われる仮定

スカウト法は、精度が高い move ordering によって 最も高い評価値の子ノードが先頭に移動した と 仮定 し、その場合に枝狩りの効率が高くなるように αβ 法に改良を加えたアルゴリズムです。もちろん通常は move ordering の精度は 100% ではないため、この仮定は正しくない場合もあります。

null window search による効率化

(α 値, β 値) をウィンドウとする αβ 法 は、正確なミニマックス値を計算したい範囲をウィンドウ とし、ウィンドウの範囲外が計算 された場合は ミニマックス値 が α 値 以下または β 値以上 であることを判定することができるアルゴリズムです。

また、αβ 法では ウィンドウ幅が狭い程、α 狩りや β 狩りの 枝狩りが行われやすくなる という性質を持ちます。なお、範囲を狭くした際に枝狩りの効率が変わらない場合がありますが、効率が悪くなることはありません。以前の記事で説明した null window search はそのことを利用した枝狩りの効率化の手法です。

最も高い評価値の子ノードが先頭に移動するという スカウト法の仮定が正しければ 2 番目以降のすべての子ノードの評価値 は最初の子ノードの評価値である $\boldsymbol{s_1}$ 以下 になり、($\boldsymbol{s_1}$ , β 値) というウィンドウの αβ 法で 2 番目以降の子ノードの評価値を計算 すると、その すべてが fail low となります。

スカウト法の 仮定が正しければ ($\boldsymbol{s_1}$ , β 値) というウィンドウの β 値を $\boldsymbol{s_1}$ より大きなどのような値に変更 しても、fail low という計算結果は変わりません。従ってウィンドウの $\boldsymbol{s_1}$ を変えず に ウィンドウ幅を null window search になるまで減らす ことで、枝狩りの効率を同じかそれ以上にする ことができます。これがスカウト法による効率化の考え方です。

ただし、以前の記事で説明したように、ウィンドウ幅を 0 にしてしまうと枝狩りの効率が悪く なるので、実際には 以前の記事で説明したように、ウィンドウ（exact value の範囲）の中に評価値として計算される値が必要最小限となるようなウィンドウを設定 する必要があります。今回の場合は ウィンドウの中 に評価値として計算される値を 1 つも入れる必要はありません。また、評価値として整数のみが計算 され、ウィンドウの端が整数 であることから、以前の記事で説明したように、ウィンドウ幅として 1 を設定 することで null window search を行うことができます。

先程のアルゴリズムで 2 番目以降の max ノードの子ノードの評価値を計算する際に ウィンドウを (α 値, α 値 + 1) としたのは 枝狩りの効率が高い null window search を行うため です。min ノードで (β 値 - 1, β 値) としたのも同様の理由です。

αβ 法とスカウト法では、2 番目以降の子ノードの評価値を計算する際に下記の処理を行い、スカウト法の 仮定が正しい場合 はどちらも 同じ fail low の計算結果 が得られます。

• αβ 法：ウィンドウが (α 値, β 値) の αβ 法
• スカウト法：ウィンドウが (α 値, α 値 + 1) の null window search

評価値が整数の場合は、(α 値, β 値) のウィンドウ幅は 1 以上、(α 値, α 値 + 1) のウィンドウ幅は 1 になります。従ってスカウト法の 仮定が正しければ スカウト法の場合の ウィンドウ幅 は αβ 法のウィンドウ幅 以下 になるため、枝狩りの効率 は αβ 法 以上 になります。

ところで、上記のアルゴリズムでは null window search のウィンドウ を (${s_1}$ ,${s_1}$ + 1) ではなく、(α 値, α 値 + 1) としています。その理由は少し後で説明しますが、余裕がある方はその理由について少し考えてみて下さい。

スカウト法の実装例の多く は 評価値として整数が計算されることが前提 となっており、特にその説明もなくウィンドウ幅を 1 としている場合が多いようですが、評価値として実数が計算される場合 は、ウィンドウ幅を 何も考えずに 1 と設定するのは避けたほうが良い でしょう。

例えば、評価値として実数が計算される場合 は、αβ 法の計算の過程で子ノードの評価値を計算する際の ウィンドウ幅が 1 未満になることがあります。そのような場合にスカウト法の処理で ウィンドウ幅を 1 に設定してしまうと、ウィンドウ幅を逆に広げてしまう ことになり、枝狩りの 効率が悪くなってしまうことがあります。従って、評価値として実数が計算される場合 は、ウィンドウ幅を 最低でも αβ 法のウィンドウ幅よりも狭く設定することが重要 となります。

スカウト法の仮定が間違っていた場合の処理

move ordering の精度が 100 % ではない場合は、どれだけ精度が高くてもスカウト法の仮定が間違う 場合が生じ、その場合は 2 番目以降 に 最初の子ノードよりも評価値が高い子ノードが存在 することになります。そのため、その子ノードの評価値を計算すると fail low ではない評価値が計算 されますが、null window search では 正しい評価値を計算することはできない ので、αβ 法と同じウィンドウで計算をやりなおします。

ただし、スカウト法で (α 値, α 値 + 1) というウィンドウで計算された評価値が β 値以上 の場合は以下の理由から計算をやりなおさずに、即座に β 狩りを行うことができます。これが先程のアルゴリズムの手順 3-2 で「β 値 ≦ $\boldsymbol{s}$ の場合は β 狩りを行う」とした理由です。

• αβ 法では (α 値, β 値) というウィンドウで評価値を計算し、計算結果が β 値以上になった場合は β 枝狩りを行う
• (α 値, α 値 + 1) というウィンドウで計算された評価値が β 値以上 の場合は、α 値 < β 値なので fail high の範囲になる³
• 従って ミニマックス値は β 値以上になる ことが確定するので (α 値, β 値) というウィンドウで評価値を計算しなおさなくても、β 狩りを行うことができる

αβ 法と同じ (α 値, β 値) というウィンドウで 計算しなおした評価値 は、最初の子ノードの評価値である $s_1$ よりも大きいので $s$ をその値で更新し、 更新した $\boldsymbol{s}$ を子ノードの評価値の最大値であると仮定 して残りの子ノードの処理を スカウト法のアルゴリズムで続けます。

move ordering の精度が高けれ ば、最初に最大の評価値であると仮定していた $s_1$ よりも大きな評価値は 非常に高い確率で子ノードの最大値であると考えられる ので、$s$ が子ノードの評価値の最大値であるという 新しい仮定は合理的 であると考えることができます。

なお、この場合でも 残りの子ノード の評価値を計算する際の ウィンドウ は ($s$, $s$ + 1) ではなく、(α 値, α 値 + 1) とします。その理由はこの後で説明します。

以後の子ノードで $s$ よりも大きな評価値が計算された場合の処理も同様です。

スカウト法の 仮定が間違っていると判明した場合 は、新しく計算された子ノードの評価値 を 最大値と仮定しなおして 計算を続ける。

スカウト法の仮定が間違っていた場合の処理の効率

スカウト法の仮定が間違っていた場合は、αβ 法とスカウト法では以下の処理を行います。下記からわかるように、この場合は明らかに スカウト法のほうが null window search を行う分だけ 処理の効率が悪くなります。

	行う処理
αβ 法	ウィンドウが (α 値, β 値) の αβ 法
スカウト法	ウィンドウが (α 値, α 値 + 1) の null window search ウィンドウが (α 値, β 値) の αβ 法

総合的なスカウト法の効率

スカウト法の処理では、2 番目以降のそれぞれの 子ノードの評価値を計算する際の効率 が、null window search の結果によって αβ 法と比較 して以下のようになります。

• スカウト法の 仮定が正しく fail low になった場合は 効率が同じか良くなる
• スカウト法の 仮定が間違って おり fail low 以外になった場合は 効率が悪くなる

従って、スカウト法の 仮定が正しい子ノード によって得られた 効率の改善の合計 が、スカウト法の 仮定が間違っている子ノード による 効率の悪化の合計 よりも 多い場合 は、全体 としてスカウト法のほうが αβ 法よりも 効率が良くなります。逆に 悪化の合計の方が多い場合 は、スカウト法が αβ 法よりも 効率が悪くなる場合 もあります。

スカウト法の 仮定 は move ordering の 精度が高いほど正しい確率が増える ので、スカウト法の 効率は move ordering の精度と密接な関係 があります。

上記をまとめると以下のようになります。

• スカウト法 は move ordering の精度が高い程、効率が良くなる ことが 期待できる が、必ず良くなるとは限らない
• move ordering の 精度が悪い と、αβ 法よりも 効率が悪くなる場合がある

null window search のウィンドウを (α 値, α 値 + 1) とする理由

null window search のウィンドウを (${s}$ ,${s}$ + 1) ではなく、(α 値, α 値 + 1) とする
理由について説明します。

最初の子ノード の評価値である $\boldsymbol{s_1}$ は、fail low、exact value、fail high の 3 種類の場合がある ので、max ノード での それぞれの場合 について分けて説明します。min ノードの場合の考え方は同様なので説明は省略します。

fail high の場合

fail high（$β ≦ s_1$）の場合は αβ 法の場合と同様に β 狩りが行なわれ、$s_1$ がこのノードの評価値として計算されます。従って、この場合は 2 番目以降の子ノードの計算は行われず、枝狩りの効率は αβ 法と同じ になります。

exact value の場合

exact value（$α < s_1 < β$）の場合は $\boldsymbol{α < s_1}$ となります。max ノード では α 値は $\boldsymbol{max(α, s)}$ で計算 されるので、2 番目の子ノードの評価値 を計算する際の α 値 = $\boldsymbol{s_1}$ となります。従って、2 番目の子ノードの評価値を計算する際の null window search のウィンドウは (α 値, α 値 + 1) となります。

スカウト法の仮定が正しい場合

スカウト法の 仮定が正しければ 残りの子ノードの評価値はすべて $s_1$ 以下なので、それまでに計算された子ノードの評価値の最大値である $\boldsymbol{s}$ は $\boldsymbol{s_1}$ のまま更新されません。従って、α 値も $\boldsymbol{s_1}$ のまま更新されない ので null window search のウィンドウは残りの子ノードですべて (α 値, α 値 + 1) となります。

スカウト法の仮定が間違っている場合

スカウト法の仮定が間違っている場合は、どこかの子ノードで $\boldsymbol{s_1}$ よりも高い評価値が計算 され、$\boldsymbol{s}$ がその評価値で更新 されます。また、$\boldsymbol{s}$ が最も高い評価値 として 新しく仮定される ので、残りの子ノードの null window search のウィンドウは ($\boldsymbol{s}$, $\boldsymbol{s}$ + 1) になります。

先ほど説明したように $s_1$ が exact value の場合は $\boldsymbol{α < s_1}$ で、$\boldsymbol{s_1 < s}$ なので、$\boldsymbol{α < s}$ となります。また、α 値は $\boldsymbol{max(α, s)}$ で計算 されるので、α 値 = $\boldsymbol{s}$ となります。従って、残りの子ノードの null window search のウィンドウは (α 値, α 値 + 1) になります。

その後の残りの子ノードの中で、スカウト法の仮定が間違っている子ノードが存在する場合も、上記と同様の理由からそのさらに後の子ノードの null window search のウィンドウも (α 値, α 値 + 1) になります。

以上から、$s_1$ が exact value の場合は 2 番目以降の子ノードの null window search のウィンドウは すべて (α 値, α 値 + 1) になります。

別の説明

上記を別の言葉で説明すると、$s_1$ が exact value の場合は常に $\boldsymbol{α < s}$ となるため、α 値 = $\boldsymbol{max(α, s)}$ = $\boldsymbol{s}$ となるので、ウィンドウを (α 値, α 値 + 1) とすることで ミニマックス値が $\boldsymbol{s}$ 以下 であることを null window search で判定することができます。

fail low の場合

最初の子ノードの評価値 $s_1$ が exact value（$α < s_1 < β$）の場合は、上記で説明したように 2 番目以降の子ノードの評価値を計算する際の α 値は必ず $s$ になります。

一方、$s_1$ が fail low（$s_1 ≦ α$）の場合 は、以下の理由から 2 番目以降の子ノードの評価値を計算する際の α 値が $s$ ではなく $\boldsymbol{s}$ より大きな $\boldsymbol{α}$ になる場合があります。

• $i$ 番目までの 子ノードの評価値がすべて $\boldsymbol{α}$ 未満の場合 は、それまでの子ノードの評価値の最大値である $\boldsymbol{s}$ は $\boldsymbol{α}$ 未満となる
• $α 値 = max(s, α)$ なので、その場合は α 値は $s$ ではなく $\boldsymbol{s}$ より大きな $\boldsymbol{α}$ になる

このように、$s_1$ が fail low の場合 は $\boldsymbol{s}$ < α 値 となる場合がある ので、その判定を行う null window search の ウィンドウを ($s$, $s$ + 1) のように修正する必要がある と思った人がいるかもしれませんが、fail low の場合も exact value と同様に ウィンドウを (α 値, α 値 + 1) として計算したほうが効率が良くなります。その理由について少し考えてみて下さい。

常にウィンドウを (α 値, α 値 + 1) としたほうが良い理由

まず、$\boldsymbol{s < α}$ = α 値 の場合にウィンドウを ($s$, $s$ + 1) とした場合と (α 値, α 値 + 1) とした場合で 同じ評価値が計算される ことを示します。

αβ 法 では max ノードで fail low である $\boldsymbol{α}$ 以下の評価値が計算された場合 は、min ノードである 親ノードで α 狩りが行われるの で、$\boldsymbol{α}$ 以下の どのような 評価値が計算された場合 でも 親ノードの評価値の計算に影響を与えません。従って、null window search で子ノードの評価値が $\boldsymbol{α}$ 以下である事が判定されても、$α$ よりも小さい $\boldsymbol{s}$ 以下である事が判定されても、最終的に計算される 評価値は同じになります。

次に、ウィンドウを (α 値, α 値 + 1) とした場合のほうが 効率が良くなる場合がある ことを示します。

$\boldsymbol{s < α}$ の場合 に、move ordering の精度が低いため 残りの子ノードの中 に $\boldsymbol{s}$ より大きく $\boldsymbol{α}$ = α 値以下 の評価値のノードが存在した場合は、その子ノードの null window search で以下のように α 値以下であることを判定 したほうが 処理の効率が良くなります。

• null window search で α 値以下 の評価値であることを判定した場合は fail low になる
• null window search で $\boldsymbol{s}$ 以下 の評価値であることを判定した場合は null window search が fail low にならない ので、αβ 法と同じウィンドウで計算をやり直す必要が生じる

上記が null window search のウィンドウを 常に (α 値, α 値 + 1) としたほうが良い 理由です。

ウィンドウを (α 値, α 値 + 1) と ($s$, $s + 1$) にした場合では、子孫ノードで α 狩りや β 狩りが行なわれる条件が異なるので枝狩りの効率が異なる場合がありますが、どちらも null window search なのでそれほど大きな差はない と思います。

スカウト法がピンとこない人がいるかもしれませんので、スカウト法の考え方 について別の言葉で説明します。

スカウト法は、以下と類似する考え方 で 最も高い点数を計算 するアルゴリズムです。なお、実際のスカウト法 は max ノードと min ノードでの違い、α 狩りと β 狩りなどが行なわれる、αβ 法と null window search の効率が変わらない場合があるなど、 いくつかの点で下記の手順と異なります。下記は 厳密なスカウト法の手順ではなく、スカウト法の おおまかな考え方 だと思って下さい。

1. 手間のかからない簡潔な方法で最も点数が高いと思われる候補を選ぶ（move ordering に相当）
2. その候補の点数 $s$ を計算する（最初の子ノードの αβ 法での計算に相当）
3. 残りの候補に対して下記の処理を行う
   1. その候補の点数が $s$ 以下であることを簡潔な方法で計算する（null window search に相応）
   2. $s$ より大きい場合はその候補の点数を計算しなおして $s$ を更新する（αβ 法での計算のやりなおしに相当）

上記の具体例としては、以下のような例が考えられるでしょう。

クラスの生徒の中から最も背の高い生徒の身長を下記の手順で測る。

1. 目測で最も背が高そうな生徒を 1 人選ぶ（move ordering に相当）
2. 選んだ生徒の身長（height）を身長測定器で測り、その身長を $h$ とする（αβ 法に相当）
3. 残りの生徒に対して順番に以下の手順で身長を測定する
   1. 身長測定器の天井を高さが $h$ になるように設定し、生徒が頭をぶつけずにそこを通過できるかどうかで、身長が $h$ 以下であるかどうかを判定する（スカウト法の手順 1 の判定に相当）
   2. $h$ よりも背が高い生徒がいた場合は、身長測定器で改めて身長を測ってその身長で $h$ を更新する

上記の 手順 3-1 は 手順 2 で具体的な身長を測る よりも簡潔に行うことができます。その結果、最初に選んだ生徒の身長が高ければ高い程 上記の 手順 3-1 で身長が $\boldsymbol{h}$ 以下である生徒が増え、結果として 全体の効率が高まることが期待できます。

スカウト法と αβ 法の効率の比較のための準備

スカウト法 は move ordering を前提 とするアルゴリズムなので、αβ 法 と 効率を比較するため には、同じ局面 のノードに対して 同一の move ordering を行う必要があります。その理由は、子ノードの並び方が変わる と 枝狩りの効率が変わってしまう からです。

残念ながら前回の記事で定義した αβ 法の計算を行う ai_abs_all で 先頭のみの move ordering を行うと、同じノードに対して毎回異なる move ordering が行われる 場合がある ため、同じ局面のノードに対して 同一の move ordering を 行うことができない場合がある という問題があります。そのような問題が発生する理由について少し考えてみて下さい。

今回の記事の残りでは、スカウト法と αβ 法の 比較を行うことができるように ai_abs_all を修正 することにします。

異なる move ordering が行われる場合がある理由

ai_abs_all が同じ局面のノードに対して異なる move ordering を行う場合がある理由は以下の通りです。

• 先頭のみの move ordering では、AI の関数が計算した最善手⁴を先頭に移動 する
• AI の関数が計算した 最善手が複数存在する場合 はその中から ランダムに 1 つ選択 する
• 従って、AI の関数が複数の最善手を計算 する場合は、先頭のみの move ordering は ランダムに行なわれる

そのことを実際に確認してみることにします。

ai2s は局面の評価値を常に 0 と計算するため、すべての合法手を最善手として計算 します。従って、ai2s を使って 先頭のみの move ordering を行うと、ai2s が最善手として計算したすべての子ノード の中から ランダムに選ばれた子ノードが先頭に移動 します。下記のプログラムでゲーム開始時の局面に対して ai2s を利用した move ordering を行い、その際に評価値が計算されたノードの数の表示処理を 複数回行う と、実行結果のように 毎回異なる値が表示 されます。このことから、move ordering による 並べ替えの順序が異なる と、実際に 枝狩りの効率が変わる ことが確認できました。従って、枝狩りの効率を比較 する際には 同じノードに対して同じ move ordering を行う必要があります。

from marubatsu import Marubatsu
from ai import ai2s, ai_abs_all

mb = Marubatsu()
for _ in range(5):
    print(ai_abs_all(mb, ai_for_mo=ai2s, calc_score=True, calc_count=True))

実行結果

14504
12347
15300
15799
14739

全ノードの move ordering の場合は AI が計算した子ノードの評価値の順で並べ替えを行います。その際に利用する list の sort メソッドや組み込み関数 sorted は 同じ大きさの値を並べ替える際 に、順序を変えずに並べ替え を行います。そのため、同じデータに対して必ず同じ並べ替えが行われる ので この問題は発生しません。

αβ 法の処理にランダム性はないので、move ordering にランダム性がなく、同じ局面のノードで同じ move ordering が行われる 場合は 同じ処理が行われます。

そのことは先ほどのプログラムにキーワード引数 sort_allnodes=True を記述することで、全ノードの move ordering を行うように修正した下記のプログラムの実行結果が、すべて同じになることから確認できます。

for _ in range(5):
    print(ai_abs_all(mb, ai_for_mo=ai2s, sort_allnodes=True, calc_score=True, calc_count=True))

実行結果

18297
18297
18297
18297
18297

なお、同じ大きさの値を順序を変えずに行う 並べ替えのことを 安定ソート（stable sort）と呼びます。一方、同じ値が複数存在する場合 に、それらの 順番が入れ替わる可能性があるソート の事を 不安定ソート と呼びます。Python の sort メソッドや組み込み関数 sorted は安定ソートを行います。

参考までに、下記に安定ソートの Wikipedia の記事のリンクを示します。

ai_abs_all の修正

この問題は、AI の関数が複数の最善手を計算した場合 に常にその中の 特定の合法手を選択する ようにすることで解決できます。AI の関数は キーワード引数 rand=False を記述 を記述して呼び出すことで、AI の関数が計算した複数の最善手の中の 先頭の合法手が常に選択される よう定義したので、ai_abs_all を下記のプログラムのように修正することにします。

• 17 行目：先頭のみの move ordering を行うための AI の関数を呼び出す際に、キーワード引数 rand=False を記述するように修正する

 1  from ai import ai_by_score, dprint
 2  from copy import deepcopy
 3  
 4  @ai_by_score
 5  def ai_abs_all(mb, debug=False, shortest_victory=False,
 6                 init_ab=False, use_tt=False, ai_for_mo=None,
 7                 params={}, sort_allnodes=False, calc_count=False):        
 8      count = 0
 9      def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
10          if ai_for_mo is not None:
11              if sort_allnodes:
12                  score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
13                  score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
14                  legal_moves = [x[0] for x in score_by_move_list]
15              else:
16                  legal_moves = mborig.calc_legal_moves()
17                  bestmove = ai_for_mo(mborig, rand=False, **params)
18                  index = legal_moves.index(bestmove)
19                  legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
元と同じなので省略

行番号のないプログラム

from ai import ai_by_score, dprint
from copy import deepcopy

@ai_by_score
def ai_abs_all(mb, debug=False, shortest_victory=False,
               init_ab=False, use_tt=False, ai_for_mo=None,
               params={}, sort_allnodes=False, calc_count=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
        elif mborig.status == Marubatsu.CROSS:
            return (mborig.move_count - 10) / 2 if shortest_victory else -1
        elif mborig.status == Marubatsu.DRAW:
            return 0
        
        if use_tt:
            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 ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
                bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
        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

        if use_tt:
            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 = -2 if shortest_victory else -1
    max_score = 3 if shortest_victory else 1
    alpha = min_score if init_ab else float("-inf")
    beta = max_score if init_ab else float("inf")

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

修正箇所

from ai import ai_by_score, dprint
from copy import deepcopy

@ai_by_score
def ai_abs_all(mb, debug=False, shortest_victory=False,
               init_ab=False, use_tt=False, ai_for_mo=None,
               params={}, sort_allnodes=False, calc_count=False):        
    count = 0
    def ab_search(mborig, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
        if ai_for_mo is not None:
            if sort_allnodes:
                score_by_move = ai_for_mo(mborig, analyze=True, **params)["score_by_move"]
                score_by_move_list = sorted(score_by_move.items(), key=lambda x:x[1], reverse=True)
                legal_moves = [x[0] for x in score_by_move_list]
            else:
                legal_moves = mborig.calc_legal_moves()
-               bestmove = ai_for_mo(mborig, **params)
+               bestmove = ai_for_mo(mborig, rand=False, **params)
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]
元と同じなので省略

上記の修正後に下記のプログラムを実行すると、実行結果のように 毎回同じ数値が表示される ようになったことから、先頭のみの move ordering が 常に同じ並べ替えを行うようになった ことが確認できます。

mb = Marubatsu()
for _ in range(5):
    print(ai_abs_all(mb, ai_for_mo=ai2s, calc_score=True, calc_count=True))

実行結果

18297
18297
18297
18297
18297

最善手が複数存在する場合の move ordering の補足

最善手⁵が複数存在する場合 は、move ordering で 最善手の中のどの合法手を先頭に移動 しても 枝狩りの効率が変わらないのではないか と思う人がいるかもしれませんが、そうではありません。そのようなことが起きる理由は、同じ最善手のノードであっても 子孫ノードの構成が異なる と、move ordering の順番によって 子孫ノードでの α 狩りや β 狩りが行なわれる状況が異なる からです。

例えば下図の 赤枠の局面のノード の 3 つの子ノード はすべて評価値が 1 なので すべてが最善手 です。赤枠のノードの評価値の計算 を、図の赤枠の子ノードを 上から順に αβ 法で計算 すると、以下のような計算が行われるため、黒色の 2 つのノード が α 狩りによって枝狩り が行われます。

1. 赤枠の最初の子ノードの評価値を計算する際のウィンドウは (-∞, ∞) である
2. 赤枠の最初の子ノードの評価値が計算された結果、赤枠の 2 番目の子ノードの評価値を計算する際のウィンドウは (1, ∞) になる
3. 赤枠の 2 番目の子ノードの最初の子ノードの評価値が 1 として計算されると、1 ≦ α 値 = 1 で fail low なので α 狩りが行われ、黒色の 2 つのノードの計算が省略される

なお、上記でどのように枝狩りが行われるかについては、下記のプログラムを実行し、6 番目のフレームからの処理を表示することでも確認することができます。

from tree import Mbtree, Mbtree_Anim

mbtree = Mbtree.load("../data/abtree_root")
Mbtree_Anim(mbtree, isscore=True)

一方、move ordering によって上図の 赤枠の上から 2 番目の子ノードを先頭に移動 して最初に計算すると、先程と異なりそのノードの評価値を計算する際の ウィンドウが (-∞, ∞) となるため、その最初の子ノードの評価値が 1 と計算されても α 狩りは行われません。そのため上図の 黒色の 2 つのノードの枝狩りが行われなくなり、その分だけ 枝狩りの効率が悪くなります。上記のプログラムではそのような move ordering を行った場合の処理の視覚化を行えないので、余裕がある方は実際に順番に α 値と β 値を計算して α 狩りが行われないことを確認して下さい。

理想的 には最善手の子ノードの中から 最も枝狩りの効率が高くなる子ノードを探して先頭に移動したほうが良い のですが、残念ながら下記の理由からそのような処理を行うと 処理の効率がかえって悪化する のでそのような処理は行いません。

• AI の関数が計算した最善手の子ノードの中から、どの子ノードを先頭に移動すれば最も効率が良くなるかを 確認するため には、実際にそれらの子ノードを先頭に移動して計算して比較する必要 がある
• その際には、AI の関数が計算した最善手の数だけ αβ 法と同様の処理が必要 となる
• その結果、全体の処理時間 が αβ 法の数倍 になってしまう

今回の記事のまとめ

今回の記事ではスカウト法のアルゴリズムと性質の説明を行いました。また、αβ 法の効率と比較するための ai_abs_all の修正を行いました。

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

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

次回の記事

1. (α 値, α 値 + 1) というウィンドウで計算を行ったので、その場合の fail high の範囲を表す α 値 + 1 値 ≦ $s$ の場合に β 狩りを行うのではないかと思うかもしれませんが、そうではありません。その理由については後述します。min ノードの場合も同様です ↩

2. 期待できるとしたのは、効率が 変わらない 場合や 悪化 する 場合がある からです ↩

3. 評価値が整数のみの場合は、exact value の範囲に計算される評価値は一つも存在しないので、必ず fail high の範囲になります ↩

4. 強解決ではない AI の関数が計算した最善手は、必ずしも本当の最善手とは限らない点に注意して下さい ↩

5. 強解決でない AI が計算した間違っている可能性がある最善手ではなく 本当の最善手 のことです ↩