Pythonで〇×ゲームのAIを一から作成する　その137　ミニマックス法による探索の実装方法の種類と評価値を動的に計算する実装方法

# 目次と前回の記事

https://qiita.com/ysgeso/items/2381dd4e3283cbed49a0

https://qiita.com/ysgeso/items/94b7ad004fc31c6e9a0a

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

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.py](https://github.com/ysgeso/marubatsu/blob/master/137/marubatsu.py)  | Marubatsu、Marubatsu_GUI クラスの定義|
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/137/ai.py)  |  AI に関する関数 |
| [test.py](https://github.com/ysgeso/marubatsu/blob/master/137/test.py)  |  テストに関する関数 |
|  [util.py](https://github.com/ysgeso/marubatsu/blob/master/137/util.py) |  ユーティリティ関数の定義。現在は `gui_play` のみ定義されている |
| [tree.py](https://github.com/ysgeso/marubatsu/blob/master/137/tree.py)  | ゲーム木に関する Node、Mbtree クラスの定義  |
| [gui.py](https://github.com/ysgeso/marubatsu/blob/master/137/gui.py)  |  GUI に関する処理を行う基底クラスとなる GUI クラスの定義  |

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

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

# ミニマックス法による探索の実装方法の種類

前回の記事では、引き分けの局面の最善手の優劣を計算するために、ミニマックス法で計算した評価値を修正する方法を紹介しましたが、評価値を修正する方法を考慮すると今回の記事で取り上げる話の内容が複雑になってしまうので、__今回の記事から__ は __ミニマックス法のみで評価値を計算する場合の説明__ を行います。

## 探索とは何か


__[ミニマックス法](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)__  によるゲーム木のノードの __評価値の計算__ は、そのノードの局面から __お互いが最善手を着手し続けた結果__ 到達する、__決着がついた局面__ を表すリーフノードを __探してその評価値を計算する__ というものです。このような、__特定のデータ__ の中から __特定の条件を満たすデータ__ を __見つける処理__ の事を __探索__ と呼びます。

探索に関する重要な用語を以下の表にまとめます。

| 用語 | 意味 |
|:--|:--|
| __探索__  | データの中から __条件にあうデータを見つける作業__  |
| __探索空間__  | __探索の対象__ となる __データの集合__（集まり）  |
| __探索条件__  | 探索するデータの __条件__  |
| __探索アルゴリズム__  | 探索を行うための __手順__  |
| __解__（かい）  | 探索アルゴリズムによって __探索されたデータ__  |

:::note
__探索は日常でも頻繁に行われています__。例えば、東京駅から新宿駅まで電車を使って最も安くたどり着けるルートを探すのは探索です。この場合の探索空間は「電車の路線」、探索条件は「値段が最も安いこと」、探索アルゴリズムは「目的のルートを探す手順」、解は「探索アルゴリズムで得られたルート」です。
:::

__探索アルゴリズム__ には、__探索空間__ と __探索条件__ の __性質__ によって __さまざまな種類__ があり、__ミニマックス法__ は  __[二人零和有限確定完全情報ゲーム](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E6%80%A7%E8%B3%AA%E3%81%AE%E5%88%B6%E9%99%90)__ に対して、__最善手を求めるために必要__ なゲーム木の __ノードの評価値を計算__ するための __探索アルゴリズム__ です。同じ目的の探索アルゴリズムとしては、今後の記事で紹介する αβ（アルファベータ）法などがあります。

探索アルゴリズムには数多くの種類があるので、本記事では以降は、__〇×ゲームの AI を作成する際に必要__ となる、__ゲーム木の探索アルゴリズムに限定__ して話を進めることにします。

ミニマックス法を利用した〇×ゲームの AI など、__探索を行う処理__ は __様々な方法で実装__ することができ、それぞれ __利点と欠点がある__ ため __状況によって使い分ける__ 必要があります。

## 探索結果を記録した静的なデータを作成する実装方法

一般的に __探索には時間がかかります__。そのため __あらかじめ全ての状況に対する探索__ を行い、__結果を記録しておく__ ことができれば、__探索を素早く行う__ ことができるようになります。

:::note
このような、様々な状況に対する何らかの計算をあらかじめ行い、結果をまとめたものを __計算表__ や __数表__ と呼びます。代表的な計算表には九九の表があり、九九の表を暗記することで 1 桁の掛け算の答えをすぐに求めることができます。

電卓が発明される前は、三角関数などの様々な数学で必要となる計算結果をまとめた数表の事典が作られ、実際に利用されていました。筆者は子供の頃祖父の家でそのような事典を見た記憶があります。また、Google で検索した所、数表小事典という事典の写真が掲載されている[個人のブログ](https://kuma.jugem.cc/?eid=85)が見つかりましたので紹介します。

また、コンピューターが作られたきっかけの一つが、第二次世界大戦でアメリカ軍が大砲の弾を命中させるための計算表を作るためだと言われています。
:::

:::note
以前の記事で紹介した __[メモ化](https://qiita.com/ysgeso/items/9303214ec798a920174e#%E3%83%A1%E3%83%A2%E5%8C%96%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E3%81%AE%E5%8A%B9%E7%8E%87%E5%8C%96)__ による処理の効率化と似ていると思った人がいるかもしれませんが、メモ化は __プログラムの実行中に計算した結果を記録__ して後で利用するという点が、あらかじめすべてのデータを計算して記録する方法と __異なります__。
:::

これまでの記事で作成した、ゲーム木を利用して着手を選択する AI は、下記のような方法で着手を選択します。この中で __AI の関数が行う処理は手順 4、5__ です。

1. 〇×ゲームのゲーム木を作成する
2. ゲーム木の全てのノードの評価値をミニマックス法で計算する
3. 局面と最善手の対応表を作成する
4. その対応表から現在の局面の最善手の一覧を計算する
5. 最善手の一覧からランダムに着手を選択する

上記の __手順 1 ~ 3__ は、__AI の関数が手順 4、5 で着手を選択する処理を行うより前__ に、__あらかじめ実行して作成__ します。このような、 __プログラムを実行する前__ にあらかじめ __作成しておいたデータ__ のことを __[静的なデータ](https://qiita.com/ysgeso/items/900d36483538c2745d9a#%E5%8B%95%E7%9A%84%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E3%81%A8%E9%9D%99%E7%9A%84%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF)__ と呼びます。

__探索結果を記録した静的なデータを作成__ する方法には、下記のような __利点と欠点__ があるため、__常に利用できるわけではありません__。

### 利点

この方法の利点の一つは、すべてのノードの評価値を計算するので、__正確な解（評価値）が計算__ され、__強解決の AI を作成できる__ というものです。後述しますが、探索アルゴリズムの中には 100 % 正確な解（評価値）を計算できないものがあります。

もう一つの利点は、__探索の処理__ が __あらかじめ完了している__ ため、探索の結果が記録された対応表から最善手の一覧を取り出して __素早く計算することができる__ というものです。

そのことを確認するために __ゲーム開始時の局面__ に対して、（ミニマックス法ではありませんが）__子ノードの評価値を AI の関数の中で計算__ して着手を選択する __`ai14s`__ と、局面と最善手の対応表の __静的なデータを利用__ して着手を選択する __`ai_gt7`__ の __処理速度__ を [`%%timeit`](https://qiita.com/ysgeso/items/10449c1d8e1465de1ed1#index-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E6%AC%A0%E7%82%B9%E3%81%A8timeit-%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%BC%E3%83%AB%E3%81%AB%E3%82%88%E3%82%8B%E5%87%A6%E7%90%86%E6%99%82%E9%96%93%E3%81%AE%E8%A8%88%E6%B8%AC) を利用して __比較__ してみることにします。

まず、下記のプログラムで必要なデータを変数に代入します。

```python
from marubatsu import Marubatsu
from ai import ai14s, ai_gt7
from util import load_bestmoves

mb = Marubatsu()
data = load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat")
```

下記のプログラムでゲーム開始時の局面に対する __`ai14s` の処理速度の平均を計測__ すると、実行結果のように __約 500 μs__（マイクロ（100 万分の一）秒）であることがわかります。

```python
%%timeit 
ai14s(mb)
```

実行結果

```
514 µs ± 1.34 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
```

下記のプログラムでゲーム開始時の局面に対する __`ai_gt7`__ の処理速度の平均を計測すると、実行結果のように __約 1 μs__（1 ns（ナノ秒）= 1000 μs です） であることから、静的なデータを利用した AI の処理速度の方が __約 500 倍も速い__ ことがわかります。

```python
%%timeit
ai_gt7(mb, bestmoves_and_score_by_board=data)
```

実行結果

```
971 ns ± 5.04 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
```

### 欠点

探索結果を記録した静的なデータをあらかじめ作成する方法の __欠点__ は、ゲーム木の __ノードの数が多くなる__ と、ゲーム木を __作成することが困難または不可能になる点__ です。〇×ゲームのようなノードが少ないゲームの場合は問題はありませんが、オセロ、将棋、囲碁などのゲームのゲーム木はノードの数が多すぎて __ゲーム木を作成することは現実的には不可能__ です[^1]。また、仮にゲーム木のデータを作成できたとしても、__データの量が多すぎる__ ためコンピューターのハードディスクやメモリ内に記録して __保存することは不可能__ です[^2]。そのため、__多くのゲーム__ では __この方法を利用することはできません__。

〇×ゲームの場合はこの欠点はあてはまらないため、この方法を利用して __高速に処理を行う強解決の AI を作成__ することができます。一方、__多くのゲームでは利用できない__ ので、本記事を読んで __〇×ゲームより複雑なゲームの AI を作成__ しようと思った場合は __別の方法が必要になります__。そのため、別の方法を説明し、実際にその方法で AI を実装することにします。

## 評価値を動的に計算する実装方法

あらかじめゲーム木を作成することが不可能な場合は、__AI が処理を行う際__ にミニマックス法を実際に行って子ノードの __評価値をその場で計算__ する必要があります。そのような、__プログラムの実行時に計算__ するデータの事を __[動的なデータ](https://qiita.com/ysgeso/items/900d36483538c2745d9a#%E5%8B%95%E7%9A%84%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF%E3%81%A8%E9%9D%99%E7%9A%84%E3%81%AA%E3%83%87%E3%83%BC%E3%82%BF)__ と呼びます。ただし、評価値を動的に計算したからといって、__ゲーム木のノードの数が減るわけではありません__。そのため、ゲーム木のノードの数が多すぎる場合に生じる「__ゲーム木の作成が不可能__」、「__データの記録が不可能__」という問題に対しては、以下のような方法で対処する必要があります。

### 探索空間を狭める

「__ゲーム木の作成が不可能__」という問題に対しては、行う __探索の性質を考慮した何らかの方法__ で __探索空間（探索するデータの範囲）を狭める__ という手法がとられます。例えば、「最も身長が高い日本人を探す」という探索の問題に対して、「全世界から探す」という方法は大変すぎます。そこで、__ほとんどの日本人が日本に住んでいる__ ことや、__日本の中で東京の人口が最も多い__ ことを考慮して、「日本の中だけで探す」や「東京都の中だけで探す」ように __探索の範囲を狭める__ ことで、__探索の手間と時間を大幅に減らす__ ことができます。探索の範囲を狭めることを、__探索の絞り込み__ と呼びます。

:::note
__探索空間を狭める__ ことと、探索空間を狭めるように __探索の条件を変更__ することは __同じ意味__ を持ちます。例えば「日本の中」から「最も身長が高い日本人を探す」という探索と、「世界の中」から「日本にいる最も身長が高い日本人を探す」という探索は、同じ探索です。
:::

__探索の条件に完全に一致__ するデータの事を __最適解__ と呼びます。__探索の範囲を狭める__ ことで __探索の範囲外のデータが無視される__ ことになるので、上記の例では __最も背の高い日本人が日本の国外にいた場合__ は、その人を __見つけることはできません__。探索の範囲を狭めた場合に見つかる解のように、__最適解でない可能性が生じる解__ のことを __近似解__ と呼びます。__最適解と近似解の差__ の事を __誤差__ と呼び、__誤差が少ない__ ことを __精度が高いと__ 呼びます。

:::note
__探索の範囲を狭める__ という手法は、__日常生活でも良く行われています__。例えば警察が殺人事件の容疑者を調べる際に、犯行時刻のアリバイがある容疑者を除外するのは探索の範囲の絞り込みです。
:::

探索範囲を狭めて __近似解を求める__ ということは、探索に必要な __処理時間を短くする代わり__ に正確でない解で __妥協する__ ということです。ただし、同じ妥協するにしても、近似解の __精度が高いほうが望ましい__ ことは言うまでもないでしょう。

__絞り込みを適切に行う__ ことで得られた近似解の __精度を向上__ させることができます。日本人のほとんどが日本にいることを考慮すれば、先程の「日本の中だけで探す」という絞り込みによってかなり精度の高い近似解を得ることができるでしょう。また、__絞り込みの方法__ によっては近似解ではなく、__最適解を得ることができる__ 場合もあります。例えば 1 ~ 100 までの素数を探索する際に、2 以外の偶数を探索範囲から除外するという方法で探索範囲を絞り込むことで、最適解を得ることができます。

ミニマックス法を利用した AI の場合は、ノードの局面の __最善手__ を __子ノードの評価値の最大値（または最小値）で計算__ します。ミニマックス法では、__ノードの評価値は__ そのノードの __すべての子孫ノードの評価値を計算__ することで求めるので、探索空間から __それ以外のノードを削除__ しても __最適解の評価値を得る__ ことができます。

:::note warn
従って、__ミニマックス法__ で __特定のノードの評価値を計算__ する際には、探索空間をゲーム木全体から、__そのノードをルートノード__ とするゲーム木の __部分木に狭める__ ことができます。その結果、残念ながらルートノードの評価値は全てのゲーム木のノードの評価値を計算する必要がありますが、__深さが深いノードほど__ 、__子孫ノードの数が減る__ ため __探索空間をより大きく狭める__ ことができます。
:::

他にも、ゲーム木のノードの評価値を求める際に、上記とは別の方法で __探索の範囲を狭めた上__ でミニマックス法と同じ __最適解を求める__ ことができる __αβ法__ という __効率の良い探索アルゴリズム__ があります。αβ法については、次回の記事で紹介します。

### 必要なノードのデータのみを記録する

探索の範囲を狭めた結果、現実的な時間で探索の処理を行うことが可能になった場合でも、__探索時に計算したすべてのデータ__ をコンピューターの __メモリやファイルに記録__ するには __データの量が大きすぎる__ 場合があります。そのような場合は、__必要が無くなったデータ__ を __破棄しながら計算を行う__ 必要があります。

そのような計算は特に珍しいものではありません。例えば下記の 1 から 10 までの合計を計算するプログラムは、途中で 1 までの合計、2 までの合計のような値を計算して `total` に代入していますが、__`total` の値を次の合計の値で上書きして破棄する__ という処理を行います。

```python
total = 0
for i in range(1, 11):
    total += i
print(total)
```

ミニマックス法で計算した探索結果を記録した静的なデータを作成する場合は、ゲーム木のすべてのノードの評価値を記録しておく必要がありますが、__特定のノードの評価値を動的に計算する__ 場合は、__計算の過程で作成したノードのデータ__ をずっと __記録し続けておく必要はありません__。わかりづらいと思いますので、具体例を挙げて説明します。

例えば、下図の赤枠のノードの評価値を計算するためには、__3 つの子ノードの評価値のデータが必要__ となります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b63f2be4-17b8-2384-2173-4fdf36ab504a.png" width="200">

赤枠のノードの評価値は、下図のような手順で __子ノードの評価値のデータのみを使って計算される__ ので、__子ノードの評価値が計算された後__ では、__子孫ノードのデータは必要ありません__。従って、__ミニマックス法__ では、計算の過程で __あるノードの評価値が計算された後__ では、その __子孫ノードのデータを破棄__ することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/035cfdaf-683a-c368-3679-b3ae4bc72763.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/81b8359f-6c7f-b814-5917-69e0aece56a0.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/61b6a31b-23e0-5400-21f8-4ffb2479e99f.png" width="100">

さらに、ミニマックス法でノードの評価値を計算する際に必要となるのは、子ノードの __評価値だけ__ なので、__子ノードのデータも破棄__ することができます。具体的には、下図のように 〇 の手番のノードの評価値を計算する際には __子ノードの評価値の最大値を記録__ しておけばよいので、__子ノードのデータを破棄__ することができます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e25e33ca-19f6-bc14-349b-99debf732e29.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0ff6f5c9-e5cb-678c-de53-0d6f54e8bf8f.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/079539c0-53e2-21a6-27d7-ea5fe0ca14b2.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/878465c2-4d84-a773-c610-7f62802a2d8c.png" width="100">　

上記から、ミニマックス法で __N というノード__ の評価値を計算する際に __記録する必要があるノード__ は、__ノード N から__、ミニマックス法の処理の途中で __評価値を計算中のノードまで__ のノードだけであることがわかります。〇×ゲームのゲーム木のノードの深さは最大で 9 なので、ノード N の深さが n の場合は、__最大でも 10 - n 個__[^3] のノードのデータだけを記録しておけば充分で、__他の途中で計算した大量のノードの情報はすべて破棄__ することができます。

## 深さ優先探索によるミニマックス法の実装

__ミニマックス法__ は __幅優先アルゴリズム__ と __深さ優先アルゴリズム__ の 2 種類のアルゴリズムで実装することができますが、ミニマックス法で評価値を __動的に計算する場合__ は、__深さ優先アルゴリズム__ を利用するのが __一般的__ です。

その理由は、__幅優先アルゴリズム__ では、計算の過程で __同じ深さのノード__ の情報を __すべて記録する必要がある__ ため、ゲーム木の __ノードが深くなるほど__ 記録しなければならない __ノードの数が大きく増えてしまう__ からです。

深さ優先アルゴリズムで探索を行うアルゴリズムの事を、__深さ優先探索（depth first search）__ と呼びます。そこで、ミニマックス（mini max）法を深さ優先探索で行い、最善手を選択する __`ai_mmdfs`__ という __AI の関数を定義__ する事にします。

__`ai_mmdfs`__ が行う処理は、__Mbtree__ クラスで深さ優先アルゴリズムでゲーム木を作成する __[`create_tree_by_df`](https://qiita.com/ysgeso/items/847598556d7e49fe2d87#calc_legal_moves-%E3%81%AE%E4%BF%AE%E6%AD%A3)__ と、評価値を計算する __[`calc_score_by_df`](https://qiita.com/ysgeso/items/0f83bcdf76bac5b0175f#calc_score_by_bf-%E3%81%A8-calc_score_by_df-%E3%81%AE%E4%BF%AE%E6%AD%A3)__ と __よく似ています__ が、ゲーム木のノードの __`children` 属性__ に子ノードのデータを __記録しない__ 点が __大きく異なります__。

Python では、[以前の記事](https://qiita.com/ysgeso/items/18ad5c20101c96aaecae#%E3%82%AC%E3%83%BC%E3%83%99%E3%82%B8%E3%82%B3%E3%83%AC%E3%82%AF%E3%82%B7%E3%83%A7%E3%83%B3%E3%81%AE%E4%BB%95%E7%B5%84%E3%81%BF)で説明したように、__利用できなくなったオブジェクト__ を __自動的に削除__ する __ガーベジコレクション__ という処理が行われます。作成した __子ノード__ を __`children` 属性に記録しない__ ようにすることで、そのノードの __評価値の計算の処理が行われた後で__、__子ノードの情報が__ どこからも参照されなくなって __利用できなくなる__ ので、ガーベジコレクションによって __自動的に削除されて廃棄される__ ようになります。

局面を表すデータを代入する __仮引数 `mb`__ と、デバッグ表示を行うかどうかを表す __仮引数 `debug` を持ち__、ミニマックス法で __その局面の評価値__ を計算して __返す関数__ として __`ai_mmdfs` を定義__ することで、以前の記事で定義した __[`ai_by_score`](https://qiita.com/ysgeso/items/7e1d948c4b9208ab44fb#%E3%83%87%E3%82%B3%E3%83%AC%E3%83%BC%E3%82%BF%E3%81%A8%E3%81%97%E3%81%A6%E3%81%AE-ai_by_score-%E3%81%AE%E5%AE%9A%E7%BE%A9) のデコレーター__ を使って __AI の関数を定義__ する事ができます。

なお、決着がついている __リーフノードの評価値__ は[最初にミニマックス法で評価値の計算を行う際に設定](https://qiita.com/ysgeso/items/3400391d2637eafc8899#%E3%83%AA%E3%83%BC%E3%83%95%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97)した以下の表のように計算することにします。最も早く勝利できる合法手を選択するような評価値を計算する場合については、今後の記事で実装します。

| 局面の状況 | 〇 の勝利の評価値 |
|:-:|:-:|
| __〇 の勝利__  | 1  |
| __引き分け__  | 0  |
| __× の勝利__  | -1  |

下記は、__`ai_mmds`__ の定義です。

* __5 行目__：仮引数 `mb` と仮引数 `debug` を持つ関数として `ai_mmdfs` を定義する
* __6 行目__：ミニマックス法による探索を深さ優先アルゴリズムで計算する際に、再帰呼び出しを行う関数 `mm_search` をローカル関数として定義する。この関数が行う処理は、`create_tree_by_df` や `calc_score_by_df` と同様に、評価値を計算する局面のノードを代入する `node` を仮引数として持ち、計算した評価値を返すという処理を行う。ローカル関数として定義したのは、この関数を `ai_mmdfs` 以外で利用することはないからである
* __7 ~ 12 行目__：リーフノードの場合の評価値を計算し、返り値として返す
* __14、15 行目__：リーフノードでない場合は合法手の一覧を計算し、子ノードの評価値を記録する `score_list` を空の list で初期化する
* __16 ~ 20 行目__：それぞれの合法手に対する繰り返し処理を行う
* __17、18 行目__：`node` の局面をコピーしたデータに対して合法手の着手を行う
* __19、20 行目__：子ノードのデータを作成し、そのデータを実引数に記述して `mm_search` を再帰呼び出しし、その子ノードの評価値を表す返り値を `score_list` の要素に追加する。なお、`mm_search` では、親ノードのデータやノードの深さのデータを利用しないので、ノードを作成する際にそれらに関する実引数は省略した
* __21 ~ 24 行目__：繰り返し処理の結果、`score_list` に子ノードの評価値の一覧のデータを要素として持つ list が代入されるので、ミニマックス法に従って、手番によってそれらの最大値または最小値を計算して返り値として返す
* __26、27 行目__：`ai_mmdfs` の処理として、評価値を計算する `mb` の局面を表すノードを作成し、そのノードを実引数に記述して `mm_search` を呼び出すことで、この局面の評価値を計算する。また、計算した評価値を返り値として返す処理を行う

```python
 1  from marubatsu import Marubatsu
 2  from tree import Node
 3  from copy import deepcopy
 4
 5  def ai_mmdfs(mb, debug=False):
 6      def mm_search(node):
 7          if node.mb.status == Marubatsu.CIRCLE:
 8              return 1
 9          elif node.mb.status == Marubatsu.CROSS:
10              return -1
11          elif node.mb.status == Marubatsu.DRAW:
12              return 0
13          
14          legal_moves = node.mb.calc_legal_moves()
15          score_list = []
16          for x, y in legal_moves:
17              mb = deepcopy(node.mb)
18              mb.move(x, y)
19              childnode = Node(mb)
20              score_list.append(mm_search(childnode))
21          if node.mb.turn == Marubatsu.CIRCLE:
22              return max(score_list)
23          else:
24              return min(score_list)
25      
26      node = Node(mb)
27      return mm_search(node)
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from marubatsu import Marubatsu
from tree import Node
from copy import deepcopy

def ai_mmdfs(mb, debug=False):
    def mm_search(node):
        if node.mb.status == Marubatsu.CIRCLE:
            return 1
        elif node.mb.status == Marubatsu.CROSS:
            return -1
        elif node.mb.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = node.mb.calc_legal_moves()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(node.mb)
            mb.move(x, y)
            childnode = Node(mb)
            score_list.append(mm_search(childnode))
        if node.mb.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
    
    node = Node(mb)
    return mm_search(node)
```
</details>

上記の定義後に、下記のプログラムを実行して __ゲーム開始時の局面の評価値__ を __`ai_mmdfs`__ で計算すると、実行結果のように引き分けの局面を表す __`0` という正しい評価値が計算される__ ことが確認できます。なお、`ai_mmdfs` で __ゲーム開始時の局面の評価値を計算__ すると、ゲーム木を作成する際と同様にゲーム木の __全てのノードを作成して評価値を計算する処理__ が行われるので、ゲーム木を作成する際と同様に __約 30 秒ほどの処理時間__ がかかります。

```python
mb = Marubatsu()
print(ai_mmdfs(mb))
```

実行結果

```
0
```

`ai_mmdfs` が正しく実装されているかどうかを確認するために、下図の (1, 1)、(1, 0) に着手した __〇 の必勝の局面の評価値を計算__ することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dc69f441-bd68-ce86-820c-2ae3bba61587.png" width="200">

下記のプログラムを実行すると、実行結果のように __`1` という正しい評価値が計算される__ ことが確認できます。こちらの場合は、__深さ 2 のノードをルートノードとする部分木を作成する処理__ と同様の処理が行われ、その場合の __部分木のノードの数__ はゲーム木全体のノードの数よりも __大幅に少ない__ ので __1 秒未満で計算が終了__ します。

```python
mb.move(1, 1)
mb.move(1, 0)
print(ai_mmdfs(mb))
```

実行結果

```
1
```

__ゲーム開始時の局面__ で着手を選択する際に、__約 30 秒もかかってしまう__ のは __時間がかかりすぎ__ で、この AI と対戦するのは苦痛でしょう。そのため、__何らかの工夫__ を行って、この AI の __処理時間を短くする工夫が必要__ になります。その工夫は次回の記事で紹介します。

## 探索範囲の絞り込みの確認

先程、「__ミニマックス法__ で __特定のノードの評価値を計算__ する際には、探索空間をゲーム木全体から、__そのノードをルートノード__ とするゲーム木の __部分木に狭める__ ことができます」という説明を行いました。そこで、実際に __どれくらい狭めることができているかを確認__ できるように `ai_mmdfs` を修正することにします。具体的には、`ai_mmdfs` では、__`mm_search` を呼び出すたび__ に __1 つのノードの評価値を計算する__ ので、__`mm_search` を呼び出した回数を数える__ ことで、実際に __探索を行ったノードの数を数える__ ことができます。

下記は、そのように `ai_mmdfs` を修正したプログラムで、仮引数 __`debug` に `True` が代入__ されている場合に __数えた回数を表示__ しています。

* __4 行目__：`mm_search` が呼び出された回数を数える `ai_mmdfs` のローカル変数 `count` を `0` で初期化する
* __6 行目__：`ai_mmdfs` のローカル変数 __`count`__ は、`ai_mmdfs` の __ローカル関数 `mm_search`__ にとっての __[クロージャー変数](https://qiita.com/ysgeso/items/18ad5c20101c96aaecae#%E3%82%AF%E3%83%AD%E3%83%BC%E3%82%B8%E3%83%A3%E3%83%BC%E5%A4%89%E6%95%B0)__ である。[以前の記事](https://qiita.com/ysgeso/items/7e1d948c4b9208ab44fb#%E4%BB%A3%E5%85%A5%E5%87%A6%E7%90%86%E3%81%AE%E9%81%95%E3%81%84)で説明したように、クロージャー変数は値を参照することはできるか、__`nonlocal クロージャー変数名`__ を実行しないと __代入処理を行うことはできない__ ので、__`nonlocal count` を記述__ している
* __7 行目__：`mm_search` が呼び出されたので、`count` に 1 を足す
* __9 行目__：`ai_mmdfs` の中で `mm_search` を呼び出した後で、`count` を表示する必要があるので、`mm_search` の返り値を `score` に代入するように修正する
* __10 行目__：[`dprint`](https://qiita.com/ysgeso/items/474db9ea1805993eaa34#%E3%83%87%E3%83%90%E3%83%83%E3%82%B0%E8%A1%A8%E7%A4%BA%E3%82%92%E8%A1%8C%E3%81%86%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9) を利用して `debug` が `True` の場合に `count` の値を表示する
* __11 行目__：`score` を `ai_mmdfs` の返り値として返す

```python
 1  from ai import dprint
 2
 3  def ai_mmdfs(mb, debug=False):
 4      count = 0
 5      def mm_search(node):
 6          nonlocal count
 7          count += 1
元と同じなので省略
 8      node = Node(mb)
 9      score = mm_search(node)
10      dprint(debug, "count =", count)
11      return score
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from ai import dprint

def ai_mmdfs(mb, debug=False):
    count = 0
    def mm_search(node):
        nonlocal count
        count += 1
        if node.mb.status == Marubatsu.CIRCLE:
            return 1
        elif node.mb.status == Marubatsu.CROSS:
            return -1
        elif node.mb.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = node.mb.calc_legal_moves()
        score_list = []
        for x, y in legal_moves:
            mb = deepcopy(node.mb)
            mb.move(x, y)
            childnode = Node(mb)
            score_list.append(mm_search(childnode))
        if node.mb.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
    
    node = Node(mb)
    score = mm_search(node)
    dprint(debug, "count =", count)
    return score
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
+from ai import dprint

def ai_mmdfs(mb, debug=False):
+   count = 0
    def mm_search(node):
+       nonlocal count
+       count += 1
元と同じなので省略
    node = Node(mb)
-   return mm_search(node)
+   score = mm_search(node)
+   dprint(debug, "count =", count)
+   return score
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように __ゲーム開始時の局面__ に対して __`ai_mmdfs`__ を呼び出すと、__549946 個__ のノードの評価値が計算されることが確認できます。これは、[以前の記事](https://qiita.com/ysgeso/items/0bad81b51c0ccbdbc3c7#%E3%83%8E%E3%83%BC%E3%83%89%E3%81%B8%E3%81%AE%E8%A6%AA%E3%83%8E%E3%83%BC%E3%83%89%E3%81%AE%E6%83%85%E5%A0%B1%E3%81%AE%E8%A8%98%E9%8C%B2)で確認した __〇×ゲームのゲーム木のノードの数と一致__ します。

```python
mb.restart()
print(ai_mmdfs(mb, debug=True))
```

実行結果

```
count = 549946
0
```

続けて下記のプログラムで (1, 1)、(1, 0) に着手した局面に対して __`ai_mmdfs`__ を呼び出すと、__7046 個__ のノードの評価値が計算されることが確認できます。このように、深さ 2 のノードの局面の場合の __探索空間を大幅に減らすことができる__ ことが確認できました。その結果、__処理時間__ もゲーム開始時の局面と比べて __大幅に減らす__ ことができます。

```python
mb.move(1, 1)
mb.move(1, 0)
print(ai_mmdfs(mb, debug=True))
```

実行結果

```
count = 7064
1
```

## ノードを作成しない実装方法

先程定義した __`ai_mmdfs`__ では、下記のプログラムの 3、6 行目のように、局面を表す `mb` から局面の __ノードを表す Node クラスのインスタンスを作成__ し、それを __`mm_search` の実引数に記述して呼び出す__ という処理を行っています

```python
1  def ai_mmdfs(mb, debug=False):
2      def mm_search(node):
略
3              childnode = Node(mb)
4              score_list.append(mm_search(childnode))
略
5    
6      node = Node(mb)
7      return mm_search(node)
```

ゲーム木を実際に作成する Mbtree クラスの __`create_tree_by_df`__ では、__作成した子ノードのデータ__ を Node クラスのインスタンスの __`children` 属性に記録する__ という処理を行っていたので、__ノードのデータを作成する必要__ がありました。

しかし、__`mm_serach`__ では __子ノードの情報を記録していません__。また、仮引数 __`node`__ に代入された __ノードのデータの中で__、実際に `mm_search` の中で __利用しているのは `mb` 属性の値だけ__ なので、局面のデータから __ノードのデータをわざわざ作成する必要はありません__。

そのため、__`mm_search` の仮引数__ を Marubatsu クラスのインスタンスを代入する __`mborig` に修正__ することができ、そうすることで Node クラスのインスタンスを作成するという __無駄な処理を省く__ ことができます。下記は、そのように `ai_mmdfs` を修正したプログラムです。

* __3 行目__：仮引数 `node` を `mborig` に修正する
* __6、8、10、13、16、19 行目__：`node.mb` を `mborig` に修正する
* 18 行目と 24 行目の前にあった Node クラスのインスタンスを作成する処理を削除する
* __18、24 行目__：`mm_search` の実引数を `mb` に修正する

```python
 1  def ai_mmdfs(mb, debug=False):
 2      count = 0
 3      def mm_search(mborig):
 4          nonlocal count
 5          count += 1
 6          if mborig.status == Marubatsu.CIRCLE:
 7              return 1
 8          elif mborig.status == Marubatsu.CROSS:
 9              return -1
10          elif mborig.status == Marubatsu.DRAW:
11              return 0
12        
13          legal_moves = mborig.calc_legal_moves()
14          score_list = []
15          for x, y in legal_moves:
16              mb = deepcopy(mborig)
17              mb.move(x, y)
18              score_list.append(mm_search(mb))
19          if mborig.turn == Marubatsu.CIRCLE:
20              return max(score_list)
21          else:
22              return min(score_list)
23    
24      score = mm_search(mb)
25      dprint(debug, "count =", count)
26      return score
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
def ai_mmdfs(mb, debug=False):
    count = 0
    def mm_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
        
        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))
        if mborig.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
    
    score = mm_search(mb)
    dprint(debug, "count =", count)
    return score
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
def ai_mmdfs(mb, debug=False):
    count = 0
-   def mm_search(node):
+   def mm_search(mborig):
        nonlocal count
        count += 1
-       if node.mb.status == Marubatsu.CIRCLE:
+       if mborig.status == Marubatsu.CIRCLE:
            return 1
-       elif node.mb.status == Marubatsu.CROSS:
+       elif mborig.status == Marubatsu.CROSS:
            return -1
-       elif node.mb.status == Marubatsu.DRAW:
+       elif mborig.status == Marubatsu.DRAW:
            return 0
        
        legal_moves = mborig.calc_legal_moves()
        score_list = []
        for move in legal_moves:
-           mb = deepcopy(node.mb)
+           mb = deepcopy(mborig)
            x, y = move
            mb.move(x, y)
-           childnode = Node(mb)            
-           score_list.append(mm_search(childnode))
+           score_list.append(mm_search(mb))
-       if node.mb.turn == Marubatsu.CIRCLE:
+       if mborig.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)

-   node = Node(mb)
-   score = mm_search(node)
+   score = mm_search(mb)
    dprint(debug, "count =", count)
    return score
```
</details>

上記の修正後に下記のプログラムを実行すると、実行結果のように修正前と同じ結果が表示されます。なお、Node クラスのインスタンスを作成する処理を無くしても __処理時間はほとんど変化しません__。その理由は、__Node クラスのインスタンスを作成する処理時間__ が、`ai_mmdfs` で行う処理時間の __ごく一部に過ぎない__ からです。

```python
mb.restart()
print(ai_mmdfs(mb, debug=True))
```

実行結果

```
count = 549946
0
```

また、下記のプログラを実行すると、実行結果のように修正前と同じ結果が表示されます。
```python
mb.move(1, 1)
mb.move(1, 0)
print(ai_mmdfs(mb, debug=True))
```

実行結果

```
count = 7064
1
```

:::note warn
__ミニマックス法__ によるノードの __動的な評価値の計算の処理__ では、ゲーム木を実際に作成する必要はなく、__局面を表すデータだけを使って処理を行う__ ことができます。
:::

## AI の関数としての `ai_mmdfs` の定義

__`ai_mmdfs`__ を __局面の評価値を計算する関数__ として定義したので、__`@ai_by_score`__ のデコレータ式を `ai_mmdfs` の定義の直前の行に記述することで、__AI の関数を定義できます__。ただし、その前に __`ai_mmdfs` に対して修正を行う必要があります__。どのような修正を行う必要があるかについて少し考えてみて下さい。

### `ai_mmdfs` の修正

__`ai_by_score`__ のデコレータは、その中で定義されたラッパー関数 `wrapper` の中の下記のプログラムの 3 行目のように、__最大の評価値__ を持つ子ノードになる合法手を候補手の一覧として計算します。つまり、__`ai_by_score` を利用するため__ には、__局面の評価値を計算する関数__ が、その局面の __手番に関わらず__ 常に __候補手__ として計算する合法手を着手した __局面の評価値が最大になる__ ように評価値を計算する必要があります。


```python
1  def ai_by_score(eval_func):
略
2      def wrapper(mb_orig, debug=False, *args, rand=True, analyze=False, **kwargs):
略
3              if best_score < score:
4                  best_score = score
5                  best_moves = [move]
略
```

しかし、__`ai_mmdfs`__ が計算する __評価値__ は、〇 の勝利の局面の評価値を 1、× の勝利の局面の評価値を `-1` と計算するので、__× の手番の局面__ では候補手として計算する合法手を着手した __〇 の手番の局面の評価値__ が、__最小の評価値として計算される__ という問題があります。

この問題を解決するためには、下記のプログラムの 5、6 行目のように、__`ai_mmdfs`__ の __返り値__ を __〇 の手番の局面__ の場合は __-1 を乗算__ して __正負を反転させる__ ことで、__最小値を最大値に変換する処理を行う__ 必要があります。なお、下記のプログラムでは __`@ai_by_score`__ のデコレーター式を 3 行目に記述して、__`ai_mmdfs` を AI の関数として利用__ できるようにしています。

```python
1  from ai import ai_by_score
2
3  @ai_by_score
4  def ai_mmdfs(mb, debug=False):
元と同じなので省略
5      if mb.turn == Marubatsu.CIRCLE:
6          score *= -1
7      return score
```

<details><summary><strong>行番号のないプログラム</strong></summary>

```python
from ai import ai_by_score

@ai_by_score
def ai_mmdfs(mb, debug=False):
    count = 0
    def mm_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
        
        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))
        if mborig.turn == Marubatsu.CIRCLE:
            return max(score_list)
        else:
            return min(score_list)
    
    score = mm_search(mb)
    dprint(debug, "count =", count)
    if mb.turn == Marubatsu.CIRCLE:
        score *= -1
    return score
```
</details>

<details><summary><strong>修正箇所</strong></summary>

```diff_python
+ from ai import ai_by_score

+ @ai_by_score
def ai_mmdfs(mb, debug=False):
元と同じなので省略
+   if mb.turn == Marubatsu.CIRCLE:
+       score *= -1
    return score
```
</details>

上記の修正後に下記のプログラムを実行して、先程の (1、1)、(1, 0) に着手を行った `mb` の局面に対して `ai_mmdfs` を実行すると、実行結果のように __最善手の中からランダムな着手が選択される__ ことが確認できます。

```python
print(ai_mmdfs(mb))
```

実行結果（実行結果はランダムなので下記と異なる場合があります）

```
(0, 2)
```

なお、この局面は下図のように (1, 2) 以外の合法手が最善手なので、(1, 2) が選択されることはありません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dc69f441-bd68-ce86-820c-2ae3bba61587.png" width="200">

下記のプログラムで __`debug=True`__ を実引数に記述して呼び出すと、実行結果のように __デバッグ表示が行われる__ ことが確認できます。

```python
print(ai_mmdfs(mb, debug=True))
```

実行結果

```
Start ai_by_score
Turn o
.X.
.o.
...

legal_moves [(0, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
略
Finished
best score 1
best moves [(0, 0), (2, 0), (0, 1), (2, 1), (0, 2), (2, 2)]
(2, 2)
```

下記のプログラムで __`rand=False`__ を実引数に記述して呼び出すと、実行結果のように上記の best moves の __最初の候補手__ である (0, 0) が __常に表示__ されます。

```python
print(ai_mmdfs(mb, rand=False))
```

実行結果

```
(0, 0)
```

下記のプログラムで __`analyze=True`__ を実引数に記述して呼び出すと、実行結果のように __候補手の一覧__ と、それぞれの合法手に着手した局面の __評価値の一覧__ が表示されることが確認できます。また、最善手でない (1, 2) を着手した場合の評価値が他の評価値より小さな 0 として正しく計算されていることが確認できます。

```python
from pprint import pprint

pprint(ai_mmdfs(mb, analyze=True))
```

実行結果

```
{'candidate': [(0, 0), (2, 0), (0, 1), (2, 1), (0, 2), (2, 2)],
 'score_by_move': {(0, 0): 1,
                   (0, 1): 1,
                   (0, 2): 1,
                   (1, 2): 0,
                   (2, 0): 1,
                   (2, 1): 1,
                   (2, 2): 1}}
```

## 強解決の AI であるかの確認

下記のプログラムで、__`ai_mmdfs`__ が __強解決の AI であるか__ を確認します。実行結果から強解決の AI であることが確認できました。

```python
from util import Check_solved

Check_solved.is_strongly_solved(ai_mmdfs)
```

実行結果

```
100%|██████████| 431/431 [00:15<00:00, 28.19it/s]
431/431 100.00%

(True, [])
```



# 今回の記事のまとめ

今回の記事では、ミニマックス法で __評価値を動的に計算__ し、それを利用して着手を選択する __`ai_mmdfs` を定義__ しました。ただし、現状では __ゲーム開始時の局面__ で `ai_mmdfs` が __着手を選択__ すると __約 30 秒__ もの時間がかかってしまうので、この AI で対戦を行うのは __長時間待たされる__ という苦痛を伴うことになります。そこで、次回の記事では、`ai_mmdfs` の __処理速度を向上させる方法__ について紹介します。

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

| リンク | 説明 |
|:--|:--|
| [marubatsu.ipynb](https://github.com/ysgeso/marubatsu/blob/master/137/marubatsu.ipynb)  | 本記事で入力して実行した JupyterLab のファイル |
| [ai.py](https://github.com/ysgeso/marubatsu/blob/master/137/ai_new.py)  | 本記事で更新した ai_new.py  |

# 次回の記事

https://qiita.com/ysgeso/items/f1ec6467a79d135a4af9

[^1]:[以前の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E4%BA%8C%E4%BA%BA%E9%9B%B6%E5%92%8C%E6%9C%89%E9%99%90%E7%A2%BA%E5%AE%9A%E5%AE%8C%E5%85%A8%E6%83%85%E5%A0%B1%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%AE%E6%80%A7%E8%B3%AA)で紹介したようにゲーム木のノードの数はオセロでは約 $10^{28}$、将棋では約 $10^{69}$、囲碁では約 $10^{171}$ といわれています
[^2]:1 テラバイトは $10^{12}$ バイトなので、仮に 1 つのノードのデータを 1 バイトで表現した場合でも、世界中のコンピューターの記憶装置をすべて利用してもオセロのゲーム木のノードをすべて記録することは不可能でしょう
[^3]:ノードの深さは 0 ~ 9 までの 10 種類なので、10 - n になります