目次と前回の記事
これまでに作成したモジュール
以下のリンクから、これまでに作成したモジュールを見ることができます。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| test.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
深さ制限探索
これまでに紹介した ゲーム木を探索 することで ミニマックス値を計算 する、ミニマックス法や αβ 法などのアルゴリズムでは、ゲームの 決着がついた局面 を表すリーフノードの 勝敗の状況を表す評価値 を元に ミニマックス値の計算 を行ないました。ゲームの決着がついた局面では 100 % 正しい評価値 を計算することができるので、計算された ミニマックス値はその局面の状況を正確に表す値 になります。従って、この手法 で計算されたミニマックス値を利用して作成した AI は 強解決の AI になります。
この手法の問題点 は、ミニマックス値を計算する 処理時間 がゲーム木の中で 評価値を計算するノードの数に比例 することです。下記は〇×ゲーム、オセロ、将棋、囲碁の局面の、同一局面を考慮した場合の種類を表す表で、ゲーム木の 全てのノードの評価値を計算 する ミニマックス法 では、ゲーム開始時の局面のミニマックス値を計算するために 下記の表の数のノードの評価値の計算 を行う必要があります。そのため ミニマックス法 では、〇× ゲームのような 小規模なゲーム木の場合 は 短時間でミニマックス値を計算 することができますが、オセロや将棋のような 大規模なゲーム木の場合 は、ノードの数が多すぎるためミニマックス値を求めることは 現実的に不可能 になります。
| 〇×ゲーム | オセロ | 将棋 | 囲碁 | |
|---|---|---|---|---|
| 局面の種類 | 5478 | $10^{28}$ | $10^{69}$ | $10^{171}$ |
| 局面の種類の平方根 | 約74 | $10^{14}$ | $10^{34.5}$ | $10^{85.5}$ |
枝狩りを行う αβ 法 は 前回の記事で説明したように、子ノードの数が同じである バランス木では 最も枝狩りの効率が高い場合 は ノードの数の平方根に比例 する数のノードを計算する必要がありますが、上記の表のように 大規模なゲーム木の場合 は平方根であってもノードの数が多すぎるため、ミニマックス値を求めることは 現実的に不可能 です。
一般的に ゲーム木のノードの数 は深さが 1 つ深くなるたびに数倍になる という、指数関数的に増加 します。そこで ゲーム木の探索の際 に、計算を行う ノードの深さを制限する ことで計算する ノードの数を減らし、現実的な時間内に計算が終わるようする という、深さ制限探索（depth limited search）という手法が、オセロや将棋などの 大規模なゲーム木の探索 を行う際に 良く用いられます。
深さ制限探索 は、ゲーム木を探索する任意のアルゴリズム に対して適用することができます。本記事では 深さ制限探索を適用する ゲーム木の探索 アルゴリズムの事 を ベースとなるアルゴリズム と表記することにします。
深さ制限探索 は、ゲーム木以外の様々なデータ構造を探索するアルゴリズム に対しても適用することができますが、本記事では 深さ制限探索の ベースとなるアルゴリズムが ミニマックス法や αβ 法などの、ゲーム木の探索アルゴリズムの場合 の説明を行います。
深さ制限探索 はベースとなるアルゴリズムでゲーム木の探索を行う際に、探索するノードの 深さの上限を制限 することで 処理時間を短くする代わりに、計算結果 としてが正確な値ではない 近似値 を求める ヒューリスティック なアルゴリズムです。そのため深さ制限探索を利用して、強解決の AI を作成することはできません1。
次回の記事で説明しますが、深さ制限探索は 一般的に下記のような性質 があります。
- 深さの上限が大きくなるほど処理時間が増える
- 深さの上限が大きくなるほど近似値の精度が高くなる
上記の性質から 処理時間 と 近似値の精度 は両立しない トレードオフの関係 になるため、適切な深さの上限を決めることが重要 になります。処理時間が長すぎることが大きな問題となることが多いので、一般的には制限時間の制約から深さの上限を決めることが多いのではないかと思います。
参考までに深さ制限探索の Wikipedia のリンクを紹介します。
評価関数
任意の局面 に対して 評価値を計算 する関数のことを、評価関数（evaluation function）と呼びます。ゲーム木に関する深さ制限探索のアルゴリズムでは、下記の性質を持つ 静的評価関数 を定義する必要があります。
- 任意の局面に対して、その 局面の情報だけから 局面の状況を表す 評価値 と呼ばれる数値を計算する
- 評価値は ベースとなるアルゴリズムに応じた値 を計算する。これまでに紹介したミニマックス法などの探索アルゴリズムでは先手が有利であるほど大きな数値を計算するが、後述するネガマックス法では手番のプレイヤーが有利であるほど大きな数値を計算する
静的（static）とは、あらかじめ与えられた 状態が変化しない ことを表す用語で、静的評価関数の静的は局面の評価値を計算する際に 局面の状況を変えず に その局面の情報だけから 評価値を計算することが名前の由来です。
一方、ミニマックス法などの ゲーム木の探索を行うアルゴリズム は 局面の状況を変えた 子孫ノードの情報を利用して計算するので 静的評価関数ではありません。静的の反対語は動的（dynamic）ですが、筆者の調べた範囲では静的評価関数の反対語として動的評価関数という用語はほとんど使われていないと思います。そこで、本記事では ゲーム木の探索を行う評価関数 のことを静的評価関数と区別して 探索ベースの評価関数 と表記することにします。
深さ制限探索で静的評価関数を利用する必要がある理由については次回の記事でします。
一般的に、決着がついていない局面 の状況を、その 局面の情報だけから正確に判定することは困難 です。そのため、静的評価関数 は 決着がついていない局面 の評価値を 正しく計算できるとは限りません。深さ制限探索が 近似値を計算する理由 は、静的評価関数が計算する評価値が近似値 だからです。
逆に言えば、静的評価関数が 100 % 正確な評価値を計算できる場合は深さ制限探索の計算結果も 100 % 正しくなります。ただし、そのような静的評価関数を作成することができる場合は、その静的評価関数だけを使って最善手を計算できるので、そもそもゲーム木の探索を行う必要はありません。以後の記事では 原則として静的評価関数 が評価値の 近似値を計算するものとします。
これまでに定義した評価値を計算するルールベースの AI
本記事でこれまでに作成した ルールベースの AI の中で、ai1s ~ ai14s は、キーワード引数に calc_score=True を記述することで 任意の局面の評価値 を 局面の情報だけから計算する ことができるので 静的評価関数 です。ただし、それらの関数が計算する評価値は「先手 がどれくらい有利であるか」ではなく、「直前の手番のプレイヤー がどれくらい有利であるか」を表します。そのため、それらの関数をミニマックス法や αβ 法をベースとする深さ制限探索の評価関数として利用する場合は、先手の手番の場合 は評価値に -1 を乗算 して 符号を反転する 必要があります。この点の詳細については次回の記事で説明します。
また、ルールベースの AI の中で 最も強い ai14s は 以前の記事で説明したように 弱解決の AI なので、一部の局面で正しい評価値を計算できません。そのため、ai1s ~ ai14s はいずれも評価値の 近似値を計算 する静的評価関数です。
静的評価関数が計算する評価値の一般的な性質
ゲーム木に対する深さ制限探索で用いられる 静的評価関数の一般的な性質 を説明します。
深さ制限探索 では、これまでに説明した深さを制限しないゲーム木の探索と同様に null window search が行なわれることがある ので、静的評価関数が計算する 評価値として は、整数の値を計算 するのが 一般的 なようです。本記事で定義した ai11s ~ ai14s は 整数以外の評価値を計算する場合がある ので、 null window search を行う スカウト法などをベースとする深さ制限探索で利用する場合は、評価値として 整数のみが計算されるように修正したほうが良い でしょう。ミニマックス法や通常の αβ 法の場合は整数以外の評価値を計算しても大きな問題はありませんが、特に理由がなければ整数を計算したほうが良いでしょう。
静的評価関数が 評価値を計算する局面 は、以下の 3 種類に分類 されます。
- 必ず局面の状況を正確に判定できる、ゲームの決着がついた局面
- 決着がついていない が、局面の状況を正確に判定できる局面。例えば 〇× ゲームの 〇 の手番で、次の着手で 〇 が勝利できる局面など
- 決着がついておらず、局面の状況を正確に判定できない局面
評価値の計算方法の方針 には様々な手法がありますが、その中の一つに 大きな正の整数 $\boldsymbol{s}$ を決め、評価値を 下記の表のように計算する というものがあります。先手の勝利の局面の評価値を $s + 1$ としたのは、先手の必勝の局面よりも先手の勝利の局面が優先されるようにするためです。
| 状況 | 評価値 |
|---|---|
| 決着がついた先手の勝利の局面 | $s + 1$ |
| 先手の必勝と正確に判定できる局面 | $s$ |
| 先手が有利と判定する局面 | $1$ 以上 $s$ 未満の整数 |
|
決着がついた引き分けの局面 引き分けと正確に判定できる局面 |
$0$ |
| 後手が有利と判定する局面 | $s-1$ 以上 $-1$ 以下の整数 |
| 後手の必勝と正確に判定できる局面 | $-s$ |
| 決着がついた後手の勝利の局面 | $-s - 1$ |
上記の評価値 を利用する AI は 最短の勝利を目指さない 最善手を計算します。最短の勝利を目指す 最善手を計算する場合は $s$ と $s + 1$ の代わりに「$\boldsymbol{s}$ + そのゲームの最長の手数2 - 先手が勝利する局面の最短手数」を計算することで、先手の必勝及び、先手の勝利の局面の評価値が以下のようになります。
- 評価値が $\boldsymbol{s}$ 以上 になる
- 先手がより早く勝利できる 局面の評価値が より高く なる
最遅の敗北を目指す場合 は $\boldsymbol{-s}$ の代わりに「$\boldsymbol{-s}$ - (そのゲームの最長の手数 - 先手が敗北する局面の最短手数)」を計算します。
上記のように評価値を計算する理由は、評価値を見るだけで どちらがどのくらい有利であるか、先手や後手が必勝の局面の場合は 後何手でどちらが勝利するか を 評価値を見て判断できるようになるから です。具体的には正の値で大きいほど先手が有利、0 が互角、負の値で小さいほど後手が有利という意味になります。
上記のような利点が無くなってしまいますが、ベースとなるアルゴリズムに対応した評価値を計算する という 性質が満たされていれば、上記の表とは 別の基準で評価値を計算 しても かまいません。例えば以前の記事で定義したルールベースの ai10s は、下記の表のような上記とは 全く異なる基準 の -1 ~ 12 という の評価値を計算しています。
| 順位 | 局面の状況 | 個別 | 評価値 |
|---|---|---|---|
| 1 | 真ん中のマスに着手している | 12 |
|
| 2 | 自分が勝利している | 11 |
|
| 4 | 「自 2 敵 0 空 1」が 2 つ以上存在する | 10 |
|
| 5 |
「自 2 敵 0 空 1」が 1 つ存在する 「自 1 敵 0 空 2」が x 個存在する |
1 (0～1)x (0～8) |
0～9 |
| 3 | 相手が勝利できる | -1 |
深さ制限探索のアルゴリズム
深さ制限探索の アルゴリズム は以下の通りです。
ベースとなる αβ 法やスカウト法などの ゲーム木の探索 でノード $N$ に対するミニマックス値の近似値の計算を行う際に、下記の処理を行う。
- 深さの上限 $\boldsymbol{d}$ を決める
- $N$ をルートノードとした、深さが $\boldsymbol{d}$ までのノード から構成される 部分木 に対して下記の計算を行う
- リーフノード以外 のノードの評価値の計算は、ベースとなるゲーム木の探索と同じ方法 で行う
- リーフノード の評価値の計算は 静的評価関数で行う
ベースとなる ゲーム木の 探索アルゴリズム そのものは、深さの 制限をなくし、リーフノードのみ の評価値を 100 % の精度 で計算できる 静的評価関数 を用いた 深さ制限探索と考える ことができます。
本記事での深さ制限探索の表記方法
本記事では 深さの上限を $\boldsymbol{d}$、静的評価関数を eval_func とする 深さ制限探索(depth limited search) のことを下記のように表記することにします。なお、この表記法は 本記事独自 のもので、一般的な表記法ではありません。
DLS(ベースとなるアルゴリズム, d, eval_func)
例えばベースとなるアルゴリズムが αβ 法、深さの上限が 3、静的評価関数が ai2s の場合は DLS(αβ 法, 3, ai2s) と表記します。
深さを制限しない 場合のゲーム木の探索は 深さの上限 を 無限大 とした深さ制限探索とみなすことができます。従って通常のミニマックス法は DLS(ミニマックス法, ∞, eval_func) と表記することができます。ただし、この場合の eval_func は 決着がついた局面 の評価値を 正しく評価できる静的評価関数 です。
静的評価関数 そのものは 深さが 0 のルートノードの 計算しか行わない ので、深さの上限を 0 とした深さ制限探索です。従って静的評価関数は DLS(なし, 0, eval_func) と表記することができます。なお、ベースとなるアルゴリズム はルートノードしか計算しないため なんでもかまわない ので なし と表記しました。
@ai_by_score が行う処理の説明と改良
深さ制限探索 によって着手を選択する AI の関数 は、深さを制限しない通常のミニマックス法や αβ 法などで着手を選択する ai_mmdfs などの AI と同様に、@ai_by_score というデコレータ式を利用して定義 することができますが、@ai_by_score が行う処理に わかりづらい点がある と思いましたので、今回の記事ではその補足説明を行うことにし、深さ制限探索の AI の実装は次回の記事で行うことにします。デコレータについて忘れた方は以前の記事を復習して下さい。
静的評価関数を @ai_by_score でラップした場合に行なわれる処理
先程の深さ制限探索のアルゴリズムを見た方は、これまでに本記事で定義したルールベースで局面の評価値を計算する ai1s ~ ai14s が 深さ 1 を上限 とする 深さ制限探索 の処理を行なっていることに気づいたかもしれません。また、それらの関数は @ai_by_score という デコレータ式を利用して定義 されています。そこで、最初に @ai_by_score を用いて定義されたそれらの関数 が 深さ 1 を上限 とする 深さ制限探索 を行うことを説明します。
@ai_by_score がラップして 機能を拡張する上記の関数 は 任意の局面 に対して局面の情報だけから 直前の局面の手番 のプレイヤーが 有利になるほど大きな値 となる 評価値を計算 するので、静的評価関数 です。
また、@ai_by_score を利用して 定義された関数 は下記の処理を行います。なお、下記ではラップされた静的評価関数を eval_func と表記します。
-
仮引数
mb_origに代入された 局面に対して、合法手が着手された局面をすべて計算 する - 計算した それぞれの局面の評価値 を静的評価関数である
eval_funcを呼び出すことで 計算する -
eval_funcが計算する評価値 は、mb_origの局面に合法手を着手した局面の直前の手番のプレイヤー、すなわちmb_origの局面のプレイヤーが有利になるほど大きな値 を計算する。従って、最も高い評価値 が計算された合法手がmb_origの局面の最善手 となる - 最も高い評価値 が計算された 合法手が複数存在する場合 は、その中から ランダムに選んだ合法手 を最善手として返す
上記の処理は、mb_orig をルートノード とした部分木の 深さ 1 のノードまでの計算 を行うので、深さが 1 を上限 とする 深さ制限探索 です。
上記の 深さ制限探索 の ベースとなるアルゴリズム がミニマックス法だと思う人がいるかもしれませんが、実際にはこの後で説明するミニマックス法を改良した ネガマックス法 が ベースとなるアルゴリズム です。上記をまとめると以下のようになります。
@ai_by_score を利用して 定義された関数 が行う処理は、ラップされた静的評価関数を eval_func と表記すると下記のように表記できる。
DLS(ネガマックス法, 1, eval_func)
ネガマックス法
ネガマックス法 については以前の記事で言及しましたが詳しく説明していませんでした。@ai_by_score を利用して定義した関数が行う処理を 理解するために必要 となるので、ネガマックス法について説明します。
ミニマックス法 は、すべてのノード で 先手が有利なほど大きな値 となる評価値を計算するアルゴリズムで、下記のように max ノードと min ノード で 行う処理が異なります。
- 先手が有利なほど大きな値となるようにリーフノードの評価値を計算する
- 先手が最も有利な着手を選択する必要がある max ノードの評価値として、子ノードの評価値の最大値を計算する
- 後手が最も有利な着手を選択する必要がある min ノードの評価値として、子ノードの評価値の最小値を計算する
それに対して ネガマックス法 は、max ノードと min ノード で 同じ方法で評価値を計算する ようにミニマックス法を改良したアルゴリズムで、プログラムを ミニマックス法よりも簡潔に記述できる という利点があります。
ネガマックス法は すべてのノード で、ノードの局面の手番のプレイヤーが有利なほど大きな値 となる評価値を計算するアルゴリズムで、下記のように ノードの種類に関わらず同じ方法 で各ノードの 評価値を計算 します。
- その局面の手番のプレイヤーが有利なほど大きな値となるようにリーフノードの評価値を計算する
- ノードの種類に関わらず、下記の手順でノードの評価値を計算する
- 子ノードの評価値 に -1 を乗算して符号を反転 させる
- 上記で符号を反転した子ノードの評価値の 最大値 をそのノードの評価値とする
上記のアルゴリズムで すべてのノード で その手番のプレイヤーにとって最も有利 な子ノードの 評価値が計算される 理由は以下の通りです。
先手の手番である max ノード の場合は、下記の理由から 先手にとって最も有利 な子ノードの評価値が計算されます。
- max ノードの 子ノードの min ノード では 後手が有利なほど大きな値 となる評価値が計算される
- max ノードの子 ノードの評価値に -1 を乗算して符号を反転 すると、先手が有利なほど大きな値 となる評価値に 変換される
- 従って、符号を反転した子ノードの評価値の最大値 は、先手にとって最も有利 な子ノードの評価値となる
後手の手番である min ノード の場合は、下記の理由から 後手にとって最も有利 な子ノードの評価値が計算されます。
- min ノードの 子ノードの max ノード では 先手が有利なほど大きな値 となる評価値が計算される
- min ノードの子 ノードの評価値に -1 を乗算して符号を反転 すると、後手が有利なほど大きな値 となる評価値に 変換される
- 従って、符号を反転した子ノードの評価値の最大値 は、後手にとって最も有利 な子ノードの評価値となる
ネガマックス法 という 名前 は、子ノードの評価値の符号の 反対（negative） を計算することで、常に子ノードの評価値の 最大値（maximum） を計算することが由来です。
ネガマックス法の実装例
ネガマックス法 は、ミニマックス法と比べて max ノードと min ノードで行う 処理を 1 つにまとめる ことができるという 利点がある ので 実際に良く使われます。ただし、プログラムの意味がわかりづらくなる という欠点があるので、本記事ではこれまで深さを限定しないミニマックス法を実装する際には採用しませんでした。
下記は、ミニマックス法 で計算を行う ai_mmdfs 内で定義された、ノードの評価値を計算 するローカル関数 mm_search の定義です。このプログラムでは、17 ~ 20 行目 で max ノードと min ノード で行う処理を 別々に記述 しています。
1 def mm_search(mborig):
2 nonlocal count
3 count += 1
4 if mborig.status == Marubatsu.CIRCLE:
5 return 1
6 elif mborig.status == Marubatsu.CROSS:
7 return -1
8 elif mborig.status == Marubatsu.DRAW:
9 return 0
10
11 legal_moves = mborig.calc_legal_moves()
12 score_list = []
13 for x, y in legal_moves:
14 mb = deepcopy(mborig)
15 mb.move(x, y)
16 score_list.append(mm_search(mb))
17 if mborig.turn == Marubatsu.CIRCLE:
18 return max(score_list)
19 else:
20 return min(score_list)
下記は、mm_search を ネガマックス法の処理 を行うように 修正したプログラム です。nega max search なので関数の名前を nm_search に変更しました。修正点は以下のとおりです。
-
1 行目：関数名を
nm_searchに修正した - 4 ~ 13 行目：リーフノード の評価値の計算処理を、手番のプレイヤーが有利なほど大きな値を計算 するように修正する。具体的には 11、12 行目で 後手の × の手番の場合 に評価値の 符号を反転 する
-
20 行目：子ノードの評価値を list に登録する際に、
nm_searchで計算した子ノードの評価値の 符号を反転した値 を登録する -
21 行目：常に
score_listの 最大値を計算 するように修正する
1 def nm_search(mborig):
2 nonlocal count
3 count += 1
4 if mborig.status != Marubatsu.PLAYING:
5 if mborig.status == Marubatsu.CIRCLE:
6 score = 1
7 elif mborig.status == Marubatsu.CROSS:
8 score = -1
9 elif mborig.status == Marubatsu.DRAW:
10 score = 0
11 if mborig.turn == Marubatsu.CROSS:
12 score *= -1
13 return score
14
15 legal_moves = mborig.calc_legal_moves()
16 score_list = []
17 for x, y in legal_moves:
18 mb = deepcopy(mborig)
19 mb.move(x, y)
20 score_list.append(-nm_search(mb))
21 return max(score_list)
修正箇所
-def mm_search(mborig):
+def nm_search(mborig):
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
+ if mborig.status != Marubatsu.PLAYING:
+ if mborig.status == Marubatsu.CIRCLE:
+ score = 1
+ elif mborig.status == Marubatsu.CROSS:
+ score = -1
+ elif mborig.status == Marubatsu.DRAW:
+ score = 0
+ if mborig.turn == Marubatsu.CROSS:
+ score *= -1
+ return score
legal_moves = mborig.calc_legal_moves()
score_list = []
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
- score_list.append(mm_search(mb))
+ score_list.append(-nm_search(mb))
- if mborig.turn == Marubatsu.CIRCLE:
- return max(score_list)
- else:
- return min(score_list)
+ return max(score_list)
ネガマックス法 では、21 行目のように 子ノードからノードの評価値を計算する処理 は 1 つにまとまります が、リーフノード の評価値の 計算処理 と、子ノードの評価値 を計算する 20 行目の 処理の意味がわかりづらくなる という欠点があります。
ai_mmdfs の中の mm_search を nm_search に置き換えるだけではネガマックス法にはなりません。それ以外の部分もネガマックス法に合わせて修正する必要があります。興味がある方は実際に実装してみて下さい。
ネガアルファ法とネガスカウト法
αβ 法 や スカウト法 なども 同様の方法 で max ノードと min ノードで 行われる処理をまとめる ことができ、それぞれを ネガアルファ法、ネガスカウト法 と呼びます。なお、ネガアルファ法 では、子ノードの評価値の符号を反転させるだけでなく、子ノードの計算を行う際に ウィンドウの範囲 を (α 値, β 値) ではなく (－β 値, －α 値) とする必要があるため、さらにわかりづらくなります。ネガスカウト法でも同様です。そのため、本記事ではわかりやすさを重視してネガアルファ法とネガスカウト法の実装は行いません。
参考までにネガマックス法、ネガアルファ法、ネガスカウト法の疑似コードが載っている Wikipedia のリンクを下記に紹介します。
MTD(f) 法はルートノードのミニマックス値を、null window search のみを利用して行う手法なので、ネガ MTD(f) 法のような手法はありません。
@ai_by_score を利用して定義された関数が行う処理
@ai_by_score を利用して定義された関数が行う処理が DLS(ネガマックス法, 1, eval_func)（ネガマックス法で深さが 1 を上限とする深さ制限探索）であることを示します。
下記は、@ai_by_score を利用して 定義された関数 が行う処理の再掲です。mb_orig から見て 深さが 1 のノードまでしか処理を行っていない ので、深さの上限を 1 とする 深さ制限探索 を行っていることは明らかです。
-
仮引数
mb_origに代入された 局面に対して、合法手が着手された局面をすべて計算 する - 計算した それぞれの局面の評価値 を静的評価関数である
eval_funcを呼び指すことで 計算する -
eval_funcが計算する評価値 は、mb_origに合法手を着手した局面の直前の手番のプレイヤー、すなわちmb_origの局面のプレイヤーが有利になるほど大きな値 を計算する。従って、最も高い評価値 が計算された合法手がmb_origの局面の最善手 となる - 最も高い評価値 が計算された 合法手が複数存在する場合 は、その中から ランダムに選んだ合法手 を最善手として返す
静的評価関数 eval_func は 直前の局面の手番 のプレイヤーが 有利になるほど大きな値 となる評価値を計算するので、親ノードの局面の手番 のプレイヤーが 有利になるほど大きな評価値を計算 することになります。先ほどのネガマックス法の実装例の nm_search では、子ノードの評価値を計算する 関数の返り値の符号を反転 させていましたが、@ai_by_score を利用して定義された関数では 子ノードの評価値の符号を反転する処理 を、eval_func の処理の中 で行なっていることになります。
上記から、@ai_by_score を利用して定義された関数が行う処理が DLS(ネガマックス法, 1, eval_func) であることが示されました。
@ai_by_score をネガマックス法で処理を行うように実装した理由
本記事で、@ai_by_score を先程わかりづらいと説明した ネガマックス法で処理を行うように実装した理由 は以下の通りで、ミニマックス法やネガマックス法の 性質を意識して決めたわけではありません。
-
ai1s~ai14sを定義した時点では、ゲーム木の説明はまだ行なっていなかった ので、ミニマックス法やネガマックス法のことは考慮していなかった - 合法手を着手した局面の評価値から最善手を選択 する処理を行う際に、合法手を着手した局面が 合法手を着手したプレイヤーからみてどれだけ有利であるか を表す評価値を計算したほうが 直観的にわかりやすい と筆者が考えたから
探索ベースの評価関数を @ai_by_score でラップした場合に行なわれる処理
ai_mmdfs や ai_abs_all などの、ゲーム木の探索 を行うことで着手を選択する AI でも @ai_by_score を利用して定義 していますが、その場合は @ai_by_score が ラップする関数 は静的評価関数ではなく、探索ベースの評価関数 である点が ai1s ~ ai14s と異なります。
また、その場合にゲーム木の探索を 1 種類のベースとなる探索アルゴリズムで行なっていると思った人がいるかもしれませんが、実際には @ai_by_score を利用して定義したことが原因 で、下記のように 2 種類の探索アルゴリズム が使われます。
- ルートノード に対しては、探索ベースの評価関数を利用した DLS(ネガマックス法, 1, 探索ベースの評価関数) で処理を行う
- 深さ 1 のそれぞれの子ノード に対しては、ゲームの決着がついた局面の評価値を計算できる静的評価関数を利用した DLS(探索アルゴリズム, ∞, 静的評価関数) で処理を行う
2 種類の探索アルゴリズムを利用するのが不自然だと思う人がいるかもしれませんが、これには理由があります。どのような理由があるかについて少し考えてみて下さい。
2 種類の探索アルゴリズムを利用することの利点
2 種類の探索アルゴリズム を利用することの 利点 は、探索アルゴリズムの種類に関わらず、最善手が複数存在する場合 にその中から ランダムに着手を選択できる ことです。1 種類の探索アルゴリズム で計算を行う場合は、ミニマックス法以外 の探索アルゴリズムでは そのようなことはできません。その理由について少し考えてみて下さい。
ミニマックス法 では、すべてのノードでミニマックス値が計算 されるので、最善手が複数存在する場合に 最善手を着手した子ノードのミニマックス値が同じ になります。一方、αβ 法やスカウト法などの、αβ 法を利用するアルゴリズム は、下記のような理由から、最初の子ノード以外 は 正確なミニマックス値 を 計算できない場合 があるため、複数の最善手が存在する場合でも、その中の 最初に見つかった最善手しかわかりません。
- αβ 法やスカウト法では、ルートノードの最初の子ノード の αβ 値 を計算する際の、exact value の範囲を表す ウィンドウの範囲内 に 計算される可能性がある評価値がすべて含まれる ので、正確なミニマックス値 を 計算できる
- 一方、2 番目以降の子ノード の αβ 値を計算する際の ウィンドウの範囲 は 狭くなっていく ため、 ウィンドウの範囲内 に 子ノードのミニマックス値が含まれない場合 が生じ、その場合に計算されるのは ミニマックス値の範囲 となる。そのため、2 番目以降の子ノード の 正確なミニマックス値 を 計算できない場合がある
MTD(f) 法の場合は最初の子ノードから null window search を行うので上記とは異なりますが、αβ 値の性質から最善手が複数存在する場合にその中の 1 つの最善手しか計算できない点は変わりません。本記事では説明を省略しますが、興味がある方はその理由について考えてみて下さい。
わかりづらいと思いますので、具体例を挙げます。ルートノードが max ノード で 子ノードのミニマックス値が 2、2、0 の場合は、最初と 2 番目の子ノードの合法手が最善手 となります。ミニマックス法 では ミニマックス値 として 2、2、0 が計算されるので 最初と 2 番目の合法手が最善手 であることが計算できます。
一方、αβ 法 では下記の表のような計算が行われます。
| 子ノード | ウィンドウ | ミニマックス値 | 計算される αβ 値 | αβ 値の範囲 | 判明したミニマックス値 |
|---|---|---|---|---|---|
| 最初の子ノード | (-∞, ∞) | 2 | 2 | exact value | 2 |
| 2 番目の子ノード | (2, ∞) | 2 | 2 | fail low | 2 以下 |
| 3 番目の子ノード | (2, ∞) | 0 | 0 以上 2 以下の値 | fail low | αβ 値以下 |
上記の表から、2 番目以降の子ノード の αβ 値 として 2 が計算された場合でも、下記の理由からそれらの ミニマックス値が 2 であると判定することはできません。
- 2 番目の子ノード の αβ 値として 2 が必ず計算 されるが fail low の範囲 である。そのため実際のミニマックス値が 2 であっても 2 番目の子ノード のミニマックス値は 2 以下であることしかわからない
- 3 番目の子ノード のミニマックス値は 0 なので fail low の範囲 として αβ 値は 0 以上 2 以下のいずれかの値 が計算される。そのため、αβ 値として 2 が計算される場合がある が、その場合も 3 番目の子ノード のミニマックス値は 2 以下であることしかわからない
従って、上記の計算結果からわかること は 以下の点だけ になります。
- 子ノードの ミニマックス値の最大値が 2 である
- 子ノードの中で 最大のミニマックス値 を持つのは 最初の子ノード である
このように ルートノード から ミニマックス法以外 の探索アルゴリズムで計算を行う場合は、最善手は最初にみつかったもののみ しかわかりません。そのような AI でも構わない場合 は 1 つの探索アルゴリズムで計算を行ってもかまいません。また、その場合は 1 種類の最善手しか選択されなくなる代わり に、ルートノードの 2 番目以降の子ノードの αβ 値を計算する際の ウィンドウが狭くなる ので 枝狩りの効率を向上 させることができます。本記事では実装しませんが、興味がある方はそのような AI を実装してみて下さい。
一方、ルートノード に対して探索ベースの評価関数を利用した DLS(ネガマックス法, 1, 探索ベースの評価関数) で処理を行うことで、すべての子ノードで正確なミニマックス値を計算することができるようになるので、複数の最善手がある場合 でも、そのすべてを正しく計算 できるようになります。
探索ベースの評価関数 を @ai_by_score でラップ することで下記の処理が行われ、複数の最善手がある場合 にその中から ランダムな着手を行うことができる。
- ルートノード に対しては、探索ベースの評価関数を利用した DLS(ネガマックス法, 1, 探索ベースの評価関数) で処理を行う
- 深さ 1 のそれぞれの子ノード に対しては、ゲームの決着がついた局面の評価値を計算できる静的評価関数を利用した DLS(探索アルゴリズム, ∞, 静的評価関数) で処理を行う
同様の理由で αβ 法だけを利用すると、ルートノードの子ノードをミニマックス値の高い順に並べることで、合法手を良い手の順に並べるようなことはできません。
@ai_by_score での置換表の共有
@ai_by_score が行う処理の説明を記述している際に、現状の ai_mmdfs などの ゲーム木の探索を行う AI の関数 では ルートノードの子ノード の評価値を 探索ベースの評価関数で計算する際 に 置換表が共有されない という 問題がある ことに気が付きました。置換表が共有されない理由について説明します。
ゲーム木の探索 によって 評価値を計算する関数 では、いずれも下記のプログラムのように ルートノードの評価値を計算する関数呼び出し を行う際に、置換表を表す実引数に空の dict を記述 して呼び出しています。下記は ai_abs_all の場合のプログラムですが、他の場合でも同様 です。そのため、@ai_by_score の処理の中で ルートノードの子ノードの評価値を計算する際 は、置換表は 毎回空の dict で初期化される ので置換表は共有されません。
score = ab_search(mb, {}, alpha=alpha, beta=beta)
これまでに紹介した ゲーム木の探索を行うアルゴリズム はいずれも 置換表の利用の有無 によって計算される ミニマックス値が変わることはありません。そのため、ルートノードの子ノードの ミニマックス値を計算した後の置換表 のデータは、次の子ノード のミニマックス値を計算する際に そのまま利用 できます。そのような 置換表の共用 を行なえるようにする方法について少し考えてみて下さい。
置換表を共有するための探索ベースの評価関数の修正
上記で説明したように、ai_abs_all などの 置換表を利用できる探索ベースの評価関数 は、現状では 空の dict を置換表として計算を開始 します。置換表を共有できるようにするため には、下記のような修正を行う必要があります。
- 共有する置換表を代入 する 仮引数を追加 する
- その置換表 を使って ルートノードの計算を開始 する
下記はそのように置換表を利用したミニマックス法で計算を行う ai_mmdfs_tt を修正 したプログラムです。なお、互換性を重視してこれまで通り 置換表を共有しない場合にも対応 できるような修正を行ないました。
-
6 行目：仮引数
ttを、デフォルト値をNoneとしたデフォルト引数として追加した -
7、8 行目：
ttがNoneの場合はttに空の dict を代入して初期化することで、これまで通りに置換表を共有しない場合の処理を行うようにした。なお、ttの デフォルト値を空の dict としてはいけない理由 について忘れた方は以前の記事を復習すること -
9 行目：
ttを置換表としてルートノードの計算を開始するように修正する
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_mmdfs_tt(mb, debug=False, tt=None, shortest_victory=False):
元と同じなので省略
7 if tt is None:
8 tt = {}
9 score = mm_search(mb, tt)
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_mmdfs_tt(mb, debug=False, tt=None, shortest_victory=False):
count = 0
def mm_search(mborig, tt):
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
boardtxt = mborig.board_to_str()
if boardtxt in tt:
return tt[boardtxt]
legal_moves = mborig.calc_legal_moves()
score_list = []
for x, y in legal_moves:
mb = deepcopy(mborig)
mb.move(x, y)
score_list.append(mm_search(mb, tt))
if mborig.turn == Marubatsu.CIRCLE:
score = max(score_list)
else:
score = min(score_list)
from util import calc_same_boardtexts
boardtxtlist = calc_same_boardtexts(mborig)
for boardtxt in boardtxtlist:
tt[boardtxt] = score
return score
if tt is None:
tt = {}
score = mm_search(mb, tt)
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_mmdfs_tt(mb, debug=False, shortest_victory=False):
+def ai_mmdfs_tt(mb, debug=False, tt=None, shortest_victory=False):
元と同じなので省略
+ if tt is None:
+ tt = {}
- score = mm_search(mb, {})
+ score = mm_search(mb, tt)
dprint(debug, "count =", count)
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
置換表の共有方法
次に、上記の修正を行った ai_mmdfs_tt を使って、置換表を共有する方法 について少し考えてみて下さい。
置換表を共有するために @ai_by_score を修正する必要があると思った方がいるかもしれませんが、@ai_by_score を修正する必要はありません。置換表を共有するためには、下記のプログラムのように キーワード引数 tt={} を記述して ai_mmdfs_tt を呼び出すだけで済みます。なお、下記は ゲーム開始時の局面の のミニマックス値を 置換表を共有 して計算するプログラムで、それぞれの子ノード の評価値を計算する際に 計算されたノードの数 を表示するために、キーワード引数 debug=True を記述しました。
mb = Marubatsu()
ai_mmdfs_tt(mb, tt={}, debug=True)
実行結果
Start ai_by_score
Turn o
...
...
...
legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn x
O..
...
...
count = 1820
score 0 best score -inf
UPDATE
best score 0
best moves [(0, 0)]
====================
move (1, 0)
Turn x
.O.
...
...
count = 421
score 0 best score 0
APPEND
best moves [(0, 0), (1, 0)]
====================
略
キーワード引数 tt={} を記述するだけ で 置換表が共有されるようになる理由 について説明します。@ai_by_score では、ルートノードである mborig の 子ノードの評価値を計算する処理 を ラッパー関数 wrapper 内 の下記のプログラムで行っています。なお、説明に必要がない処理は省略しました。
1 @wraps(eval_func)
2 def wrapper(mb_orig, debug=False, *args, rand=True,
3 analyze=False, calc_score=False, **kwargs):
略
4 legal_moves = mb_orig.calc_legal_moves()
5 for move in legal_moves:
6 mb = deepcopy(mb_orig)
7 x, y = move
8 mb.move(x, y)
9 score = eval_func(mb, debug, *args, **kwargs)
略
ai_mmdfs_tt(mb, tt={}, debug=True) を実行すると、ラッパー関数の仮引数に tt は存在しない ので 仮引数 kwargs には 下記の dict が代入 されます。**kwargs について忘れた方は以前の記事を復習して下さい。
{
"tt": {}
}
従って、最初の子ノードの評価値を計算 する際の kwargs には上記の dict が代入 された状態で呼び出されるので、9 行目 が行う処理は ai_mmdfs_tt(mb, debug, tt={}) となり、空の dict を置換表として計算 が行われます。
最初の子ノードの評価値を計算 すると、置換表の値が更新される ので kwargs は 以下の内容で更新 されます。
{
"tt": 最初の子ノードの計算によって更新された置換表を表す dict
}
従って、次の子ノード に対して 9 行目で行う処理 は ai_mmdfs_tt(mb, debug, tt=更新された置換表) となり、最初の子ノードの評価値を計算した際の 置換表が共有される ことになります。以後の子ノード の評価値を計算する際も 同様に同じ置換表が共有 されます。
下記は、先程の実行結果の中から 計算されたノードの数 を抜き出し、その 合計を計算 した表です。四隅 に着手を行う 1、3、7、9 番目の子ノードと、四辺 に着手を行う 2、4、6、8 番目の子ノードの局面は 同一局面 なので、それぞれの最初以外の子ノードの計算 は 置換表のデータを利用できる ため計算されたノードの数が 1 になる ことが確認できます。
| 子ノード | count |
|---|---|
| 1 | 1820 |
| 2 | 421 |
| 3 | 1 |
| 4 | 1 |
| 5 | 23 |
| 6 | 1 |
| 7 | 1 |
| 8 | 1 |
| 9 | 1 |
| 合計 | 2270 |
次に、下記のプログラムでキーワード引数 tt={} を 記述しない ことで、ルートノード のミニマックス値を 置換表を共有せずに 計算し、その結果を比較することにします。
ai_mmdfs_tt(mb, debug=True)
実行結果
Start ai_by_score
Turn o
...
...
...
legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn x
O..
...
...
count = 1820
score 0 best score -inf
UPDATE
best score 0
best moves [(0, 0)]
====================
move (1, 0)
Turn x
.O.
...
...
count = 1817
score 0 best score 0
APPEND
best moves [(0, 0), (1, 0)]
====================
略
下記は、実行結果の中から計算されたノードの数を抜き出し、その合計を計算した表です。四隅に着手を行う 1、3、7、9 番目の子ノードと、四辺に着手を行う 2、4、6、8 番目の子ノードの局面は 同一局面 ですが、置換表を共有しないため 同じ数のノードが計算 されていることが確認できます。
| 子ノード | count |
|---|---|
| 1 | 1820 |
| 2 | 1817 |
| 3 | 1820 |
| 4 | 1817 |
| 5 | 643 |
| 6 | 1817 |
| 7 | 1820 |
| 8 | 1817 |
| 9 | 1820 |
| 合計 | 15191 |
置換表を 共有する 場合の 合計は 2270、共有しない 場合の 合計は 15191 になることから、置換表を共有 することで 大幅に処理の効率を上げることができる ことが確認できました。
置換表を共有した場合に強解決の AI であることの確認
置換表を共有した場合の ai_mmdfs_tt が強解決の AIであることを下記のプログラムで確認すると、実行結果から 強解決の AI であることが確認 できました。
from util import Check_solved
Check_solved.is_strongly_solved(ai_mmdfs_tt, params={"tt": {}})
実行結果
100%|██████████| 431/431 [00:00<00:00, 1354.21it/s]
431/431 100.00%
処理時間の差の確認
上記では処理時間が 00:00 と表記されていることから 1 秒以内で処理が終わる事 が確認できます。また、また、VSCode のセル には 計算時間が 0.3 秒 と表示されていました。
一方、下記のプログラムで 置換表を共有しない 場合で 同じ処理 を行うと、実行結果から処理時間が 00:05 と 約 5 秒かかった ことが確認できます。また、VSCode のセルには 計算時間が 5.2 秒 と表示されます。
Check_solved.is_strongly_solved(ai_mmdfs_tt)
実行結果
100%|██████████| 431/431 [00:05<00:00, 82.96it/s]
431/431 100.00%
上記から、置換表を共有 することで Check_solved.is_strongly_solved の処理 が 約 20 倍弱 ほど 速く計算できる ことが確認できました。
次に、実戦での処理時間の差を比較 するために ai2s とのランダムな対戦 を 100 回行った場合で比較 することにします。なお、対戦回数を 100 回としたのは、1000 回だと置換表を共有しない場合の処理時間に時間がかかりすぎるからです。
下記は 置換表を共有しない ai_mmdfs VS ai2s の対戦を 100 回行うプログラムで、実行結果から 処理時間が 02:26 と、約 150 秒 ほどかかったことが確認できます。
from ai import ai2s, ai_match
ai_match(ai=[ai_mmdfs_tt, ai2s], match_num=100)
実行結果
ai_mmdfs_tt VS ai2s
100%|██████████| 100/100 [02:26<00:00, 1.46s/it]
count win lose draw
o 89 0 11
x 74 0 26
total 163 0 37
ratio win lose draw
o 89.0% 0.0% 11.0%
x 74.0% 0.0% 26.0%
total 81.5% 0.0% 18.5%
下記は 置換表を共有する ai_mmdfs VS ai2s の対戦を 100 回行うプログラムで、実行結果から処理時間が 00:00 と、1 秒以内で処理が完了したことが確認できます。
ai_match(ai=[ai_mmdfs_tt, ai2s], params=[{"tt": {}}, {}], match_num=100)
実行結果
ai_mmdfs_tt VS ai2s
100%|██████████| 100/100 [00:00<00:00, 103.11it/s]
count win lose draw
o 98 0 2
x 74 0 26
total 172 0 28
ratio win lose draw
o 98.0% 0.0% 2.0%
x 74.0% 0.0% 26.0%
total 86.0% 0.0% 14.0%
上記の結果から、実戦 においても 置換表の共有によって大幅な処理時間の短縮 を行えることが確認できました。
他の置換表を利用する関数の修正
他の置換表を利用する AI の関数 も、同様の方法で置換表を共有 することができるようになります。そこで、αβ 法の ai_abs_all、スカウト法の ai_scout、MTD(f) 法の ai_mtdf の 3 つの関数を 置換表を共有できるように修正 することにします。なお、他の置換表を利用することができる αβ 法の関数については ai_abs_all で同じ処理を行うことができるので修正は省略します。
下記は修正したプログラムですが、表記が長くなるので折りたたみました。また、修正箇所は ai_mmdfs_tt とほぼ同じなので説明は省略します。
ai_abs_allの修正プログラム
@ai_by_score
def ai_abs_all(mb, debug, shortest_victory=False, init_ab=False,
use_tt=False, tt=None, 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")
if tt is None:
tt = {}
score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
dprint(debug, "count =", count)
if calc_count:
return count
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
ai_scoutの修正プログラム
@ai_by_score
def ai_scout(mb, debug=False, shortest_victory=False,
init_ab=False, use_tt=False, tt=None, 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:
x, y = legal_moves[0]
mb = deepcopy(mborig)
mb.move(x, y)
score = ab_search(mb, tt, alpha, beta)
alpha = max(alpha, score)
if score < beta:
for x, y in legal_moves[1:]:
mb = deepcopy(mborig)
mb.move(x, y)
score = max(score, ab_search(mb, tt, alpha, alpha + 1))
if score >= beta:
break
elif score > alpha:
score = max(score, ab_search(mb, tt, alpha, beta))
if score >= beta:
break
alpha = max(alpha, score)
else:
x, y = legal_moves[0]
mb = deepcopy(mborig)
mb.move(x, y)
score = ab_search(mb, tt, alpha, beta)
beta = min(beta, score)
if score > alpha:
for x, y in legal_moves[1:]:
mb = deepcopy(mborig)
mb.move(x, y)
score = min(score, ab_search(mb, tt, beta - 1, beta))
if score <= alpha:
break
elif score < beta:
score = min(score, ab_search(mb, tt, alpha, beta))
if score <= alpha:
break
beta = min(beta, score)
if use_tt:
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 = -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")
if tt is None:
tt = {}
score = ab_search(mb, tt=tt, alpha=alpha, beta=beta)
dprint(debug, "count =", count)
if calc_count:
return count
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
ai_mtdfの修正プログラム
@ai_by_score
def ai_mtdf(mb, debug=False, shortest_victory=False,
init_ab=False, use_tt=False, tt=None, f=0, 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
lbound = min_score if init_ab else float("-inf")
ubound = max_score if init_ab else float("inf")
if tt is None:
tt = {}
dprint(debug, " count | ウィンドウ | αβ 値 | type | MM の範囲")
while lbound != ubound:
beta = f + 1 if lbound == f else f
prevcount = count
f = ab_search(mb, tt, alpha=beta - 1, beta=beta)
if f >= beta:
lbound = f
type = "fail high"
else:
ubound = f
type = "fail low "
dprint(debug, f"{count - prevcount:5.0f}/{count:5.0f} | ({beta - 1:2.0f}, {beta:2.0f}) | {f:2.0f} | {type} | [{lbound:4.0f}, {ubound:4.0f}]")
score = f
if calc_count:
return count
if mb.turn == Marubatsu.CIRCLE:
score *= -1
return score
下記のプログラムでそれぞれについて置換表を共有した場合に強解決の AI であるかを確認すると、いずれも強解決の AI であることが確認 できます。なお、スカウト法では最善手を推定するための関数として ai14s を利用しました。
from ai import ai14s
Check_solved.is_strongly_solved(ai_abs_all, params={"use_tt": True, "tt": {}})
Check_solved.is_strongly_solved(ai_scout, params={"use_tt": True, "tt": {}, "ai_for_mo": ai14s})
Check_solved.is_strongly_solved(ai_mtdf, params={"use_tt": True, "tt": {}, "f": 0})
実行結果
100%|██████████| 431/431 [00:00<00:00, 1549.70it/s]
431/431 100.00%
100%|██████████| 431/431 [00:00<00:00, 576.61it/s]
431/431 100.00%
100%|██████████| 431/431 [00:00<00:00, 1221.49it/s]
431/431 100.00%
また、下記のプログラムで αβ 法 で計算を行う ai_abs_all VS ai2s の対戦を 置換表を共有しない場合とする場合 で行い、処理時間を比較 することにします。
ai_match(ai=[ai_abs_all, ai2s], params=[{"use_tt": True, "tt": {}}, {}], match_num=100)
実行結果
ai_abs_all VS ai2s
100%|██████████| 100/100 [01:11<00:00, 1.41it/s]
count win lose draw
o 96 0 4
x 79 0 21
total 175 0 25
ratio win lose draw
o 96.0% 0.0% 4.0%
x 79.0% 0.0% 21.0%
total 87.5% 0.0% 12.5%
ai_match(ai=[ai_abs_all, ai2s], params=[{"use_tt": True}, {}], match_num=100)
実行結果
ai_abs_all VS ai2s
100%|██████████| 100/100 [00:01<00:00, 98.88it/s]
count win lose draw
o 100 0 0
x 75 0 25
total 175 0 25
ratio win lose draw
o 100.0% 0.0% 0.0%
x 75.0% 0.0% 25.0%
total 87.5% 0.0% 12.5%
実行結果から 置換表を共有しない場合は 約 70 秒、共有する場合は約 1 秒 となり、αb 法 の場合でも 置換表を共有したほうが処理速度が大幅に短くなる ことが確認できました。
本記事では省略しますが、興味がある方は ai_scout と ai_mtdf でも同様の比較を行ってみて下さい。
今回の記事のまとめ
今回の記事では 深さ制限探索 について説明し、ai1s ~ ai14s の ルールベースで評価値を計算する AI が DLS(ネガマックス法, 1, eval_func)（ネガマックス法で深さが 1 を上限とする深さ制限探索）という 処理を行っていた ことを説明しました。
また、@ai_by_score を利用して ゲーム木の探索を行う AI が 2 種類の探索アルゴリズム で計算を行なっていることを説明しました。
最後に、ゲーム木の探索を行う AI で 置換表を共有 できるように改良することで、処理時間を大幅に短縮 できるようにしました。
次回の記事では @ai_by_score を利用した深さ制限探索の処理を実装します。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
| ai.py | 本記事で更新した ai_new.py |
次回の記事