Pythonで〇×ゲームのAIを一から作成する　その46　相手の勝利を阻止するAI

# 目次と前回の記事

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/046/marubatsu.py

https://github.com/ysgeso/marubatsu/blob/master/046/ai.py

## これまでに作成した AI

これまでに作成した AI の アルゴリズム は以下の通りです。

| 関数名 | アルゴリズム |
|:-:|:--|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __左上から順__ に __空いているマス__ を探し、__最初に見つかったマス__ に __着手__ する |
| __[`ai2`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai2-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __ランダム__ なマスに __着手__ する |
| __[`ai3`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | |
| __[`ai4`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-4%E5%9B%9B%E9%9A%85%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__  | __真ん中__、__隅__ のマスの __順__ で __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | あり |
| __[`ai5`](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-5%E5%8B%9D%E3%81%A6%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AB%E5%8B%9D%E3%81%A4)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __ランダム__ なマスに __着手__ する | |

基準となる __`ai2`__ との __対戦結果__（単位は %）は以下の通りです。__太字__ は __`ai2 VS ai2` よりも__ __成績が良い__ 数値を表します。__欠陥__ の列は、__アルゴリズム__ に __欠陥__ があるため、__`ai2`__ との __対戦成績__ が __良くても強い__ とは __限らない__ ことを表します。欠陥の詳細については、関数名のリンク先の説明を見て下さい。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __78.1__ | __17.5__ | 4.4 | __44.7__ | __51.6__ | 3.8 | __61.4__ | __34.5__ | 4.1 | あり |
| __[`ai2`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai2-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | 58.7 | 28.8 | 12.6 | 29.1 | 58.6 | 12.3 | 43.9 | 43.7 | 12.5 | |
| __[`ai3`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 | |
| __[`ai4`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-4%E5%9B%9B%E9%9A%85%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__  | __83.0__ | __9.5__ | 7.4 | __57.2__ | __33.0__ | 9.7 | __70.1__ | __21.3__ | 8.6 | あり |
| __[`ai5`](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-5%E5%8B%9D%E3%81%A6%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AB%E5%8B%9D%E3%81%A4)__  | __81.3__ | __11.9__ | 6.8 | __52.2__ | __39.4__ | 8.5 | __66.8__ | __25.6__ | 7.6 | |

# ルールその 6（相手の勝利を阻止する）

__弱い AI__ に対してどれだけ __大幅に有利__ な __AI を作成__ しても __強い AI__  を __作った__ ことには __なりません__。例えば、__じゃんけん__ で __パーしか出さない AI__ は、じゃんけんで __グーしか出さない AI__ に __100% 勝利__ しますが、誰もそのような AI が __強いとは思わない__ でしょう。そのため、__強い AI__ を __作成__ する際には、__対戦相手__ として __強い AI__ を __想定__ する必要があります。

[前回の記事](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#ai2-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6)で、自分が __勝てる時__ に __勝つ__ という __ルール 5__ が __ある場合__ と __ない場合__ では、__ある場合のほう__ が __強くなる__[^1] ことを示しました。従って、__対戦相手__ として __強い AI__ を __想定__ する場合は、__自分だけ__ でなく、__相手__ も __ルール 5 で着手する__ ことを __想定__ する必要があります。

例えば、下図（__数字__ のマスは __空いているマス__ を表します）の __〇 の手番__ の局面で、__1 以外__ のマスに __着手__ を行うと、__次__ の __相手の手番__ で __× が 1__ に __着手__ を行うと __× が勝利__ するので、__〇__ が __次__ の __× の手番__ で __負けない__ ようにするためには __必ず 1 に着手__ する __必要__ があります。

![78.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3205df87-58eb-435f-ac41-5ed509867b52.png)

そこで、__ルール 5__ に、__次の相手の手番__ で __相手が勝つ__ ことが __可能__ な __着手__ を __行わない__ ルールを __加えた__、下記の __ルール 6__ で __`ai6`__ を __実装__ することにします。下記の __手順 2__ を __別の言葉__ で表現すると、「__相手__ が __勝利するマス__ に __自分で着手__ して __邪魔__ をする」のようになります。

1. __勝てるマス__ が __存在__ すれば、__そこに着手__ する
2. そうでなければ、__合法手__ を __着手__ した __局面__ のうち、__次__ の __相手の手番__ で、__相手が着手__ すると __相手が勝利__ するマスが __存在すれば__ 、__そこに着手__ して __邪魔__ をする
3. 上記のいずれでもなければ __ランダム__ なマスに __着手__ する

## ルールの手順に関する注意点

上記の __手順 1__ と __2__ を __入れ替え__ ては __いけない__ 点に __注意__ して下さい。その理由は、__勝てる場合__ に __勝っておけば__、__相手の手番__ が __来る__ ことは __ない__ からです。例えば、下図の __〇 の手番__ の局面で、上記の __ルール 6 を適用__ した場合は、__2__ のマスに __着手__ して __〇 の勝利__ になりますが、上記の __手順 1__ と __2__ を __入れ替えたルール__ では、__次__ の __× 手番__ で __1__ に __× が着手__ すると __× の勝利__ になるので、__1 に着手__ してしまい、__勝利を逃してしまう__ ことになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1ef75e7f-d8e9-3f25-a2b5-31fe061e1269.png" width="100">

別の言葉で説明すると、__ルール 6__ の __手順 1__ と __2__ の __順番を入れ替えた場合__ は、__自分の勝ちより__ も、__相手の勝利の邪魔__ を __優先__ することになります。

上記を __当たり前__ だと __思う__ 人が __いるかも__ しれませんが、__ルールの数__ が __多く__ なったり、__ルール__ の __条件__ が __複雑__ な場合は、__ルール__ の __手順__ の __順番__ を __正しく決める__ ことが __難しく__ なります。__個々__ の __手順__ は __間違っていなくても__、__手順の順番__ を __間違ってしまう__ と、__間違ったルール__ になってしまうので、__手順__ の __順番__ に __注意する必要__ があることを忘れないで下さい。

__ルール 6__ の AI が、__ルール 5__ の AI よりも __強くなる__ ことは __ほぼ自明__ で、__簡単に検証できる__ ので省略します。気になる方は、__[ルール 5 の検証](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB-5-%E3%81%AE%E6%A4%9C%E8%A8%BC)__ と同様に __表を書いて検証__ してみて下さい。

## 合法手が 1 つしかない場合の処理

__ルール 6__ は、__相手__ の __勝利を阻止__ することが __目的__ ですが、__合法手__ が __1 つ__ しかない場合は、__相手の手番__ が __回ってこない__ ので、次の __相手の手番__ を __考慮__ する __ルール 6__ を __適用__ することは __できません__。従って、__`ai6`__ の __先頭__ に、__下記__ のプログラムを __記述する必要__ があります。

* __4、5 行目__：組み込み関数 __`len`__ を使って、__`legal_moves`__ の __要素の数__ を __計算__ することで、__合法手の数__ を __計算__ し、__その数__ が __1__ の場合は、__`legal_moves[0]`__ を __返す__

```python
1  def ai6(mb_orig):
2      legal_moves = mb_orig.calc_legal_moves()
3      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
4      if len(legal_moves) == 1:
5          return legal_moves[0]
6      # 以下、ルール 6 の処理を記述する
```

:::note
__合法手__ が __1 つ__ しかない場合は、5 行目に __`return legal_moves`__ を __記述__ すれば良いと __思う人__ が __いるかもしれません__ が、__`legal_moves`__ は __list__ なので、__要素__ が __1 つ__ しかない場合でも、その __要素を参照__ する場合は、__インデックス__ を __指定__ して、__`return legal_moves[0]`__ のように __記述する必要__ がある点に __注意__ して下さい。
:::

上記の __4、5 行目__ を __記述__ することで、__合法手__ が __1 つ__ しかない場合は、__`ai6`__ は __ルール 6__ を __適用しない__ ことになります。従って、__以後__ の __ルール 6__ に関する __処理__ では、説明がなくても、__合法手__ が __2 つ以上ある場合__ の __処理を行う__ と考えて下さい。

:::note
[前回の記事](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E9%96%93%E9%81%95%E3%81%A3%E3%81%A6%E3%81%84%E3%81%A6%E3%82%82%E6%AD%A3%E3%81%97%E3%81%8F%E5%8B%95%E4%BD%9C%E3%81%99%E3%82%8B%E7%90%86%E7%94%B1)で説明したように、__合法手__ が __1 つ__ しかない場合は、__どのような ルール__ であっても、__選択__ できる __合法手は同じ__ なので、__合法手__ が __1 つ__ しかない場合に __ルール 6__ を __適用__ しても、 __選択される合法手__ は __常に同じ__ です。従って、本記事では省略しませんが、上記のプログラムの __4、5 行目__ は __省略__ することが __できます__。

ただし、[前回の記事](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E9%96%93%E9%81%95%E3%81%A3%E3%81%A6%E3%81%84%E3%81%A6%E3%82%82%E6%AD%A3%E3%81%97%E3%81%8F%E5%8B%95%E4%BD%9C%E3%81%99%E3%82%8B%E7%90%86%E7%94%B1)で説明したように、__プログラムを修正__ する際などで __バグの原因__ に __なりやすい__ ので、__意味がわからず__ に __省略__ するのは __避けたほうが良い__ でしょう.

:::

## ルール 6 の実装方法

__相手が勝利__ できる __マス__ は、__以下__ のような __条件のマス__ です。

* その __マス__ が __相手__ の __合法手__（空いているマス）である
* その __マスを含む__ 一直線上の __3 マスのうち__、__2 マス__ に __相手のマークが配置__ されている __ものがある__

__上記の条件__ を __満たすマス__ を __探す__ プログラムを記述する方法は、それほど __簡単ではありません__ ので、今回の記事では、__上記とは別__ の、__これまでに記述__ したプログラムを __うまく利用__ できる、下記のような __考え方__ で __ルール 6__ を __実装__ することにします。なお、__上記の条件__ を満たすマスが __あるかどうか__ を __判定__ する __方法__ については、今後の記事で紹介します。

* __自分の手番__ で、__着手__ することで __勝利__ できる __合法手__ を __調べる処理__ は __`ai5`__ で __実装済__
* ということは、__相手の手番__ で、__着手__ することで __相手が勝利__ できる __合法手__ も __同様の方法__ で __調べる__ ことが __できる__

### ルール 6 のアルゴリズム

__ルール 6__ は、下記の __アルゴリズム__ で __実装__ することができます。下記のアルゴリズムのうち、__手順 1__、__2__、__4__ は、__ルール 5__ の __アルゴリズム__ と __同じ__ です。__異なる__ のは、__手順 3__ ですが、手順 __1__、__2__ と、手順 __3-1__、__3-2__ で行う __処理の内容__ が、__手番__ が __自分と相手__ で __異なる__ ことを __除けば__、__まったく同じ処理__ を __行う__ ことに __注目__ して下さい。

1. __現在の局面__ の __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
2. __自分が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
3. 上記の __手順 1__ で __着手__ を行った __それぞれの局面__ に対して、__下記の処理__ を行う
    1. __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
    2. __相手が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
2. 上記の __手順 1 ~ 3__ の __処理__ が __すべて終了__ した時点で、__自分が勝利__ できる合法手も、__相手が勝利__ できる合法手も __存在しない__ ことが __確定__ するので、__ランダムな着手__ を行う

__わかりづらい__ と思った人のために、__ルール 6__ の __アルゴリズム__ の __処理の実例__ を紹介します。上記の説明の意味が良くわかった人はこの部分は飛ばしてもらっても構いません。

#### ルール 6 のアルゴリズムの処理の例 1

下図の場合の __処理の手順__ を示します。図の __数字のマス__ は、__空いているマス__ を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1ef75e7f-d8e9-3f25-a2b5-31fe061e1269.png" width="100">

* __手順 1、2__ で、上図の __現在の局面__ に対して、__1__ ~ __5__ の __順__ で __〇__ の __着手__ を行う
* __2 に着手__ した時点で、__〇 が勝利__ するので、__2__ のマスを __採用__ して __終了__ する

__採用__ された __2 のマス__ に __〇 が 着手__ することで、下図のように __〇 が勝利__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2cc43a8e-a987-2178-f14d-d04c777980b2.png" width="100">

#### ルール 6 のアルゴリズムの処理の例 2

下図の場合の __処理の手順__ を示します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2688fb2e-5962-2be7-e02c-5976aada6d5d.png" width="100">

* __手順 1、2__ で、上図の __現在の局面__ に対して、__1__ ~ __5__ の __順__ で __〇__ の __着手__ を行う
* __どのマス__ に __着手__ を行っても __〇__ は __勝利しない__ ので、__手順 3 へ__ 進む
* 上図の __1__ に __着手__ した __下図の局面__ に対して、下図の __2__ ~ __5__ の __順__ で __×__ の __着手__ を行う。なお、図の __青いマス__ は、__直前__ に __着手__ が行われた __マス__ を表す

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d88ebcf7-9f90-cab8-3370-e2ef81180dd2.png" width="100">

* __どのマス__ に __着手__ を行っても __×__ は __勝利しない__ ので、__現在の局面__ の __2__ に __着手__ した __下図の局面__ に対して、下図の __1__、__3__ ~ __5__ の __順__ で __×__ の __着手__ を行う

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/13e24a9a-a8b5-d6f3-cc3d-6a7efcbf4bbb.png" width="100">

* __1 に着手__ した時点で、__× が勝利__ するので、__1__ のマスを __採用__ して __終了__ する

__採用__ された __1 のマス__ に __〇 が 着手__ することで、下図のように __× の勝利__ を __阻止__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/368e1f16-a9e9-a503-56a9-cce567089c36.png" width="100">

#### ルール 6 のアルゴリズムの処理の例 3

下図の場合の __処理の手順__ を示します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0eb802e2-3aa1-e19d-4769-cbf470f3cbae.png" width="100">

* __手順 1、2__ で、上図の __現在の局面__ に対して、__1__ ~ __5__ の __順__ で __〇__ の __着手__ を行う
* __どのマス__ に __着手__ を行っても __〇__ は __勝利しない__ ので、__手順 3 へ__ 進む
* 上図の __1__ ~ __5__ に __着手__ した __下図__ の __それぞれの局面__ に対して、__順番__ に、下図の __それぞれ__ の空いている __1__ ~ __5__ の __順__ で __×__ の __着手__ を行う

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0c0e7e33-1c0b-4a75-072e-62fb5d012f08.png" width="450">

* __すべての局面__ で __どのマス__ に __着手__ を行っても __×__ は __勝利しない__ ので __手順 3 が終了__ する
* __手順 4__ が実行され、__現在の局面__ の __1__ ~ __5__ の中から __ランダムなマス__ を __採用__ する
 
### `ai6` の実装

下記は、先程のアルゴリズムを再掲したものです。

1. __現在の局面__ の __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
2. __自分が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
3. 上記の __手順 1__ で __着手__ を行った __それぞれの局面__ に対して、__下記の処理__ を行う
    1. __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
    2. __相手が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
2. 上記の __手順 1__ の __繰り返しが終了__ した時点で、__自分が勝利__ できる合法手も、__相手が勝利__ できる合法手も __存在しない__ ことが __確定__ するので、__ランダムな着手__ を行う

先ほど説明したように、__手順 1、2__ と、__手順 3-1、3-2__ で行う __処理の内容__ は、__手番__ が __自分と相手__ で __異なる__ ことを __除けば__、__まったく同じ処理__ を行うので、 __`ai6`__ は、下記のプログラムのように実装することができます。

* __6 ~ 15 行目__：上記の __手順 1、2__ の処理を行う部分で、この部分は、__合法手__ が __1 つ__ しかない場合の __8、9 行目__ の __処理を除けば__、__`ai5` と同じ__
* __18 ~ 24 行目__：__18 行目__ のプログラムが __実行__ されるということは、__元の局面__ である __`mb_orig`__ に対して、__`move`__ に __着手__ を行った __`mb`__ の __局面__ で、__自分__ が __勝利していない__ 場合である。その場合は、__手順 3-1、3-2__ の処理を、__6 ~ 15 行目__ と __同様の方法__ で行う。__6 ~ 15 行目__ と、__18 ~ 24 行目__ の __違い__ は以下の通り
    * __合法手__ が __1 つ__ しかない場合の __処理がない__
    * __`mb_orig`__ → __`mb`__
    * __`legal_moves`__ → __`next_legal_moves`__
    * __`move`__ → __`next_move`__
    * __`mb`__ → __`next_mb`__

```python
 1 from random import choice
 2 from copy import deepcopy
 3
 4  def ai6(mb_orig):
 5      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 6      legal_moves = mb_orig.calc_legal_moves()
 7      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 8      if len(legal_moves) == 1:
 9         return legal_moves[0]
10      for move in legal_moves:
11          mb = deepcopy(mb_orig)
12          x, y = move
13          mb.move(x, y)
14          if mb.status == mb_orig.turn:
15              return move
16          # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
17          # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
18          next_legal_moves = mb.calc_legal_moves()       
19          for next_move in next_legal_moves:
20              next_mb = deepcopy(mb)                
21              x, y = next_move
22              next_mb.move(x, y)
23              if next_mb.status == mb.turn:
24                  return next_move
25        
26      return choice(legal_moves)
```

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

```python
from random import choice
from copy import deepcopy
 
def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)
```
</details>

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

```diff_python
from random import choice
from copy import deepcopy

-def ai5(mb_orig):
+def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
+       next_legal_moves = mb.calc_legal_moves()       
+       for next_move in next_legal_moves:
+           next_mb = deepcopy(mb)                
+           x, y = next_move
+           next_mb.move(x, y)
+           if next_mb.status == mb.turn:
+               return next_move
        
    return choice(legal_moves)
```
</details>

:::note
__6 ~ 15 行目__ と、__18 ~ 24 行目__ の __処理__ は __よく似ている__ ので、これまでのプログラムで行ってきたように、__for 文__ による __繰り返し処理__ で __まとめる__ ことができるように __思えるかもしれません__ が、__18 ~ 24 行目__ の処理は、6 行目の __for 文の中__ に __入れ子で記述__ されているため、この  __2 つの処理__ を __for 文__ による __繰り返し処理__ でうまく __まとめる__ ことは __困難です__。このような場合は、__再起呼び出し__ という方法を使って __まとめる__ ことが __できます__ が、その方法については今後の記事で紹介します。
:::

本当は、[前回の記事](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#ai5-%E3%81%AE%E4%BF%AE%E6%AD%A3)のように、__`mb.play(ai=[ai6, ai2])`__ を __実行__ して __`ai2`__ と __対戦__ した __結果を表示__ することで、__`ai6`__ を __正しく実装できているか__ どうかを __確認すべき__ なのですが、__ルール__ が __複雑になる__ と、__ランダムな着手__ を行う __`ai2`__ と __対戦しても__、なかなか __ルール__ を __正しく実装できたこと__ を __確認できる局面__ が __訪れない可能性が高く__ なります。そのような場合は、__`mb.play(ai=[ai6, None])`__ や、__`mb.play(ai=[None, ai6])`__ を実行して、__自分__ で __ルール__ を __正しく実装できているか__ どうかを __確認できる__ ような __局面に誘導__ して __確認する__ と良いでしょう。本記事では確認作業を省略しますが、__気になる方__ は __実際に確認__ して下さい。

__他の方法__ として、実装した AI と __他の AI__ で __複数回対戦__ し、__意図通り__ の __成績__ になることを __確認する__ ことで、__正しく実装__ できていると __推測する__ という方法もあります。__ルール__ が __複雑__ になって __確認が困難__ な場合などで、この方法で __確認作業__ を __代用__ することがありますが、__意図通りの成績__ になっても、__正しく実装__ されているとは __限らない__ 点に __注意が必要__ です。

## `ai2` との対戦

__`ai6`__ が __実装__ できたので、下記のプログラムで、__基準__ となる __`ai2`__ と __対戦__ します。なお、__`ai6`__ は、__`deepcopy`__ や __`move`__ メソッドを __何度も実行__ する必要があるので、__処理__ に __時間__ がかかります。そのため、筆者のパソコンでは処理に __約 80 秒__ の時間が __かかりました__。

:::note
__同じプログラム__ でも、コンピュータの __CPU の性能__、__メモリの量__、__同時に実行__ している __アプリケーション__ など、__さまざまな理由__ で処理にかかる __時間__ は __異なり__ ます。
:::

```python
from ai import ai_match, ai2, ai3, ai4, ai5

ai_match(ai=[ai6, ai2])
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai6 VS ai2
count     win    lose    draw
o        8797     147    1056
x        6772     675    2553
total   15569     822    3609

ratio     win    lose    draw
o       88.0%    1.5%   10.6%
x       67.7%    6.8%   25.5%
total   77.8%    4.1%   18.0%
```

__80 秒__ は __長い__ ので、下記のプログラムのように、__1000 回__ の __対戦__ を行ってみました。__実行__ には 10000 回の __1/10__ の __約 8 秒__ かかりましたが、__10000 回__ の __対戦結果__ と __比較__ して __ほとんど__ 結果は __変わらない__ ので __1000 回__ でも __問題はない__ でしょう。[以前の記事](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#%E4%BB%8A%E5%9B%9E%E3%81%AE%E8%A8%98%E4%BA%8B%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)では 1 分で行える回数としましたが、__今後__ は時間がかかる場合は、__1000 回__ で __対戦を行う__ ことにします。


```python
ai_match(ai=[ai6, ai2], match_num=1000)
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai6 VS ai2
count     win    lose    draw
o         876      16     108
x         679      58     263
total    1555      74     371

ratio     win    lose    draw
o       87.6%    1.6%   10.8%
x       67.9%    5.8%   26.3%
total   77.8%    3.7%   18.6%
```

下記は、上記の結果（10000 回のほう）を表に加えたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __78.1__ | __17.5__ | 4.4 | __44.7__ | __51.6__ | 3.8 | __61.4__ | __34.5__ | 4.1 | あり |
| __[`ai2`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai2-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | 58.7 | 28.8 | 12.6 | 29.1 | 58.6 | 12.3 | 43.9 | 43.7 | 12.5 | |
| __[`ai3`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 | |
| __[`ai4`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-4%E5%9B%9B%E9%9A%85%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__  | __83.0__ | __9.5__ | 7.4 | __57.2__ | __33.0__ | 9.7 | __70.1__ | __21.3__ | 8.6 | あり |
| __[`ai5`](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-5%E5%8B%9D%E3%81%A6%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AB%E5%8B%9D%E3%81%A4)__  | __81.2__ | __12.3__ | 6.5 | __51.8__ | __39.8__ | 8.4 | __66.5__ | __26.0__ | 7.4 | |
| __`ai6`__  | __88.0__ | __1.5__ | 10.6 | __67.7__ | __6.8__ | 25.5 | __77.8__ | __4.1__ | 18.0 | |

表から、__`ai6`__ は、__他の__ どの __AI より__ も __基準__ となる __`ai2` に__ 対して __強い__ ことがわかります。また、__〇 を担当__ した場合、__× を担当__ した場合、__通算__ の場合の __敗率__ は __いずれも 7 % 以下__ なので、__相手の勝利__ を __阻止__ する __ルール 6__ の __効果__ が表れていることが __確認__ できます。

### ルール 6 で負ける場合がある理由

__相手の勝利__ を __阻止__ する __ルール__ なのに、__負ける場合がある__ 点について疑問に思った方がいるかもしれません。そのような方は、__負ける場合がある__ 理由について少し考えてみて下さい。

具体的には、以下の __2 つの条件__ を満たす __局面__ では、__ルール 6__ でも __負ける__ ことになります。

* 下図のように、どのマスに着手しても __自分__ が __勝つことができない__
* 下図の __黄色のマス__ のように、次の手番で __相手が勝利できる__ マスが __2 つ以上__ ある

下図では、__片方のマス__ しか __邪魔__ を __できない__ ので、__相手の勝利__ を __阻止できません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/de3be28b-9111-bffb-962a-0c2796203661.png" width="100">

なお、__上記__ のような __局面__ になってしまった場合は、ルール 6 に限らず、__どのようなルール__ を使っても __相手の勝利__ を __阻止__ することは __不可能__ です。

## `ai6` のバグの修正

プログラミングに __慣れている方__ は既に __気がづいているかも__ しれませんが、実は __`ai6`__ には、__ルール 6__ を __正しく実装できていない__ という __バグ__ があります。正直に言うと、筆者は、最初は __正しいつもり__ で上記の __`ai6`__ を __実装__ し、__後からバグ__ がある事に __気が付きました__。__ルール 6__ と、__`ai6`__ のプログラムを __見比べて__、どこが間違っているかについて考えてみて下さい。

なお、上記で __バグのある `ai6`__ で __`ai2`__ と __対戦を行った__ のは、__バグを修正__ することで、__`ai6` VS `ai2`__ の __成績__ が __向上する__ ことを __示したい__ からです。

### バグの原因

下記は、先程のアルゴリズムを再掲したものです。

1. __現在の局面__ の __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
2. __自分が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
3. 上記の __手順 1__ で __着手__ を行った __それぞれの局面__ に対して、__下記の処理__ を行う
    1. __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
    2. __相手が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
2. 上記の __手順 1__ の __繰り返しが終了__ した時点で、__自分が勝利__ できる合法手も、__相手が勝利__ できる合法手も __存在しない__ ことが __確定__ するので、__ランダムな着手__ を行う

バグの __原因__ は、__`ai6`__ が、__手順 2__ を __正しく実装していない__ 点にあります。

上記の __手順 2__ の「__自分が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する」は、__合法手__ を __すべて調べた結果__ の事を表しています。従って、__手順 3__ は、__手順 1、2__ の処理が __完了__ した __後で__ 行う必要があります。しかし、__`ai6`__ では、__合法手__ を __すべて調べた後ではなく__、合法手を __一つ調べるたび__ に、__手順 3 の処理__ を行っています。

__この違い__ が __どのように影響__ するかを、__下図の局面__ で __説明__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d27f3040-7b3d-b9f7-b670-4a765999f2f1.png" width="100">

### ルール 6 のアルゴリズムの処理を正しく行った場合

* __手順 1、2__ で、上図の __最初の局面__ に対して、__1__ ~ __5__ の __順__ で __〇__ の __着手__ を行う
* __4 に着手__ した時点で、__〇 が勝利__ するので、__4__ のマスを __採用__ して __終了__ する

__採用__ された __4 のマス__ に __〇 が 着手__ することで、下図のように __〇 が勝利__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/251596ca-c2c8-079e-049d-79249ef12104.png" width="100">

### ルール 6 のアルゴリズムを間違って実装した `ai6` の場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d27f3040-7b3d-b9f7-b670-4a765999f2f1.png" width="100">

* __手順 1、2__ で、上図の __最初の局面__ に対して、__1__ ~ __5__ の __順__ で __〇__ の __着手__ を行う
* __1__ に __着手__ した場合、下図のように、__〇__ は __勝利していない__。__`ai6`__ は __手順 1、2__ の処理が __すべて終了する前__ に、__下図の局面__ で、__手順 3__ の __処理__ を行う（__この処理が間違い__）

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8ad87f67-ed55-cb51-dc8e-8be7a1a1eb23.png" width="100">

* 上図で、__3 に着手__ した時点で、__× が勝利__ するので、__3__ のマスを __採用__ して __終了__ する

__採用__ された __3 のマス__ に __〇 が 着手__ することで、下図のように __× の勝利__ を __阻止__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9dd1c063-478f-aa66-c6db-a11b89eea639.png" width="100">

上記のように、__間違った処理__ を行う __`ai6`__ は、__〇 の勝利__ を __逃す__ 結果になります。

### `ai6` のバグの内容

上記から、__`ai6`__ の __バグ__ を __言葉で表現__ すると、以下のようになります。

以下の __2 つの条件__ が __同時に満たされる局面__ で、__自分が勝利せず__ に __相手の勝利を阻止__ してしまう __場合がある__

* __自分の着手__ で __自分が勝利__ できる __合法手__ が __ある__
* __いずれか__ の __自分の着手__ の __後__ の __相手の着手__ で、__相手が勝利__ できる __合法手__ が __ある__

### `ai6` の修正

バグの __原因__ は、__手順 1、2__ の処理を __すべて行う前__ に __手順 3 を行う__ ことにあります。そこで、__手順 1、2__ の __処理__ を __先に行ってから__、__手順 3__ の __処理を行う__ ようにすることで、__`ai6`__ の __バグを修正__ することができます。また、__手順 3__ の __処理__ は、__自分が勝利__ する __合法手__ が __存在しない__ 場合に __行う処理__ です。従って、__手順 3__ は、下記のプログラムのように、__修正前__ の __`ai6`__ のプログラムから、__手順 2__ の __処理__ を __削除__ したプログラムで __記述__ できます。

* __7 ~ 12 行目__：この __繰り返し処理__ の中で、__手順 1、2__  の処理 __のみを行う__ ように __修正__ する
* __14 ~ 26 行目__：__元__ の __`ai6`__ の __繰り返し処理__ の中から、__手順 2__ の「__自分が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する」__処理__ を __削除__ したプログラムを __記述__ する

__14 ~ 26 行目__ のプログラムが、__修正前__ の __`ai6`__ のプログラムから、__手順 2__ の __処理__ を行う、下記の __11、12 行目__ のプログラムを __削除__ したものと __同じ__ であることを __確認__ して下さい。

```python
 1  def ai6(mb_orig):
 2      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 3      legal_moves = mb_orig.calc_legal_moves()
 4      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 5      if len(legal_moves) == 1:
 6          return legal_moves[0]
 7      for move in legal_moves:
 8          mb = deepcopy(mb_orig)
 9          x, y = move
10          mb.move(x, y)
11          if mb.status == mb_orig.turn:
12              return move
13      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
14      for move in legal_moves:
15          mb = deepcopy(mb_orig)
16          x, y = move
17          mb.move(x, y)
18          # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
19          # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
20          next_legal_moves = mb.calc_legal_moves()       
21          for next_move in next_legal_moves:
22              next_mb = deepcopy(mb)                
23              x, y = next_move
24              next_mb.move(x, y)
25              if next_mb.status == mb.turn:
26                  return next_move
27        
28      return choice(legal_moves)
```

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

```python
def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)
```
</details>

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

```diff_python
def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
+   for move in legal_moves:
+       mb = deepcopy(mb_orig)
+       x, y = move
+       mb.move(x, y)
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)
```
</details>

## 修正後の `ai6` と `ai2` の対戦

__修正後__ の __`ai6`__ で、__`ai2`__ と改めて __対戦__ を行うことにします。

```python
ai_match(ai=[ai6, ai2], match_num=1000)
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai6 VS ai2
count     win    lose    draw
o         889      22      89
x         703      62     235
total    1592      84     324

ratio     win    lose    draw
o       88.9%    2.2%    8.9%
x       70.3%    6.2%   23.5%
total   79.6%    4.2%   16.2%
```

下記は、__修正前__ と __修正後__ の __`ai6`__ と、__`ai2`__ で __対戦__ した場合の __成績__ を表にしたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __`ai6`__ 前  | __88.0__ | __1.5__ | 10.6 | __67.7__ | __6.8__ | 25.5 | __77.8__ | __4.1__ | 18.0 | あり |
| __`ai6`__ 後  | __88.9__ | __2.2__ | 8.9 | __70.3__ | __6.2__ | 23.5 | __79.6__ | __4.2__ | 16.2 |  |

表から、__バグを修正__ した __結果__、すべての場合で __勝率__ が __2% 程__ することがわかります。

なお、__成績__ が __ほんの少し__ しか __向上__ しない理由の検証は省略しますが、おそらく __バグ__ が __勝敗に影響__ するような __局面__ が __ほとんど出現しない__ からだと思います。興味と余裕がある方は、実際に検証してみて下さい。

## `ai6` の改良 その 1（重複する処理を省く）

下記は、先程修正した __`ai6`__ の __一部__ を __抜粋__ したプログラムです。よく見ると、__2 ~ 5 行目__ と、__9 ~ 12 行目__ で __全く同じ処理__ が __記述__ されているため、__同じ処理__ を __2 度行う__ という __無駄__ が生じています。また、その部分で行われる __`deepcopy`__ による __データの深いコピー__ や、__`move`__ メソッドで __勝敗判定__ を行う __処理__ は、それなりに __時間がかかる__ ので、そのような処理を __2 回__ も __行う__ ことで、プログラムの __処理__ に、__余計な時間__ がかかってしまいます。

実際に __筆者のパソコン__ で __`ai_match(ai=[ai6, ai6], match_num=1000)`__ を実行すると、__同じ処理__ を __2 回行わない__ がバグのある __修正前__ では __8.4 秒__、__修正後__ では __9.4 秒__ かかりました。

```python
 1  def ai6(mb_orig):
略
 2      for move in legal_moves:
 3          mb = deepcopy(mb_orig)
 4          x, y = move
 5          mb.move(x, y)
 6          if mb.status == mb_orig.turn:
 7              return move
 8      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
 9      for move in legal_moves:
10          mb = deepcopy(mb_orig)
11          x, y = move
12          mb.move(x, y)
略
```

### 改良の方法

上記のプログラムの __2 行目__ の __繰り返し処理__ と、__9 行目__ の __繰り返し処理__ には、__同一__ の __`for move in legal_moves:`__ という __記述__ が行われています。また、__2 ~ 7 行目__ の __処理__ を __実行__ しても繰り返し処理の __反復可能オブジェクト__ に記述されている __`legal_moves`__ の __値__ は __変化しない__ ので、__2 行目__ と __9 行目__ の __繰り返し処理__ では、どちらも __同じ値__ が __順番__ に __`legal_moves`__ から __取り出され__ て __`move` に代入__ されます。

__それぞれ__ の __for 文__ の __ブロック__ の __3 ~ 5 行目__ と、__10 ~ 12 行目__ では __同一の処理__ が行われるので、__2 行目__ の __for 文__ の __ブロック__ の __5 行目__ の処理で __計算__ される __`mb` の値__ と、__9 行目__ の __for 文__ の __ブロック__ の __12 行目__ の処理で __計算__ される __`mb` の値__ は、__`move`__ に代入された値が __同じであれば__、必ず __同じ内容__ になります。

上記から、__2 行目__ の __for 文__ の __n 回目__ の繰り返し処理の __5 行目__ で計算される __`mb`__ と、__9 行目__ の __for 文__ の __n 回目__ の繰り返し処理の __12 行目__ で計算される __`mb`__ の値は、__同じ内容__ になります。従って、__5 行目__ で __計算__ した __`mb`__ を __list__ に __記録__ しておくことで、__10 ~ 12 行目__ の処理を行う代わりに、__記録した list__ から __対応するデータ__ を __取り出して利用__ することができます。

別の言葉で説明すると、__手順 3__ で __必要となる__、「__現在の局面__ に対して __それぞれ__ の __合法手__ を __着手__ した __局面__」 は、__手順 1、2__ の __処理__ を行う際に、__計算する__ ので、__その時__ にそれらの __局面__ を __list に記録__ しておき、__手順 3__ で __再利用できる__ ということです。

### 改良版の `ai6` の実装

下記は、そのような処理を行うように __`ai6`__ を __改良__ したプログラムです。

* __7 行目__：__8 行目__ の __for 文__ の __繰り返し処理__ の中の __11 行目__ で __計算__ した __`mb`__ を __記録__ するための __list__ を __代入__ する __`mb_list`__ を、__空の list__ で __初期化__ する
* __12 行目__：__`mb_list`__ の __要素__ に __`mb` を追加__ して __記録__ する
* __16 行目__：元の for 文の代わりに、__`mb_list`__ から __順番__ に __要素__ を __取り出し__、__`mb`__ に代入するという、__for 文__ による __繰り返し処理__ を行う。この __16 行目__ の __処理__ で、先程の __改良前__ の __9 ~ 12 行目__ と __同じ処理__ が行われる（そのことは、下記の __修正箇所__ で __確認できる__）

```python
 1  def ai6(mb_orig):
 2      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 3      legal_moves = mb_orig.calc_legal_moves()
 4      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 5      if len(legal_moves) == 1:
 6          return legal_moves[0]
 7      mb_list = []
 8      for move in legal_moves:
 9          mb = deepcopy(mb_orig)
10          x, y = move
11          mb.move(x, y)
12          mb_list.append(mb)
13          if mb.status == mb_orig.turn:
14              return move
15      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
16      for mb in mb_list:
17          # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
18          # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
19          next_legal_moves = mb.calc_legal_moves()       
20          for next_move in next_legal_moves:
21              next_mb = deepcopy(mb)                
22              x, y = next_move
23              next_mb.move(x, y)
24              if next_mb.status == mb.turn:
25                  return next_move
26        
27      return choice(legal_moves)
```

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

```python
def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    mb_list = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        mb_list.append(mb)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
    for mb in mb_list:
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)
```
</details>

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

```diff_python
def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
+   mb_list = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
+       mb_list.append(mb)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
-   for move in legal_moves:
-       mb = deepcopy(mb_orig)
-       x, y = move
-       mb.move(x, y)
+   for mb in mb_list:
        # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
        # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
        next_legal_moves = mb.calc_legal_moves()       
        for next_move in next_legal_moves:
            next_mb = deepcopy(mb)                
            x, y = next_move
            next_mb.move(x, y)
            if next_mb.status == mb.turn:
                return next_move
        
    return choice(legal_moves)
```
</details>

下記は、__改良後__ に __`ai6` VS `ai2`__ に __対戦__ を行うプログラムです。__実行結果__ は __修正前__ と __ほぼ同じ__ ですが、__処理時間__ は、筆者のパソコンでは __9.4 秒__ から __8.5 秒__ に短縮されました。

```python
ai_match(ai=[ai6, ai2], match_num=1000)
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai6 VS ai2
count     win    lose    draw
o         896      15      89
x         702      60     238
total    1598      75     327

ratio     win    lose    draw
o       89.6%    1.5%    8.9%
x       70.2%    6.0%   23.8%
total   79.9%    3.8%   16.4%
```

## `ai6` の改良 その 2（アルゴリズムの改良）

下記は __ルール 6__ の __アルゴリズム__ を __再掲__ したものです。実は、下記の __アルゴリズム__ を、より __効率の良い__ ものに __改良__ することが __できます__。その方法について少し考えてみて下さい。

1. __現在の局面__ の __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
2. __自分が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
3. 上記の __手順 1__ で __着手__ を行った __それぞれの局面__ に対して、__下記の処理__ を行う
    1. __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
    2. __相手が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する
2. 上記の __手順 1__ の __繰り返しが終了__ した時点で、__自分が勝利__ できる合法手も、__相手が勝利__ できる合法手も __存在しない__ ことが __確定__ するので、__ランダムな着手__ を行う

上記の __アルゴリズム__ の __手順 3__ では、__現在の局面__ に対して、__合法手__ を __着手__ した __それぞれ__ の __局面__ に対して、__相手の合法手__ を __すべて着手__ しています。そのため、例えば __現在の局面__ の __合法手__ が __n 通り__ だった場合、__最大__[^2] で __n * (n - 1) 通り__[^3] の __着手__ を行う必要があります。


理由はこの後で詳しく説明しますが、__手順 3__ は、下記のような __効率のよい__ アルゴリズムに __置き換える__ ことができます。

3\. __現在の局面__ を __相手の手番__ と __みなす__
　　1. __現在の局面__ の __合法手の一覧__ から __順番__ に __合法手__ を __取り出し__ て __着手__ を行う
　　2. __相手が勝利__ する __合法手__ があれば、__それを採用__ して __終了__ する

このアルゴリズムであれば、例えば __現在の局面__ の __合法手__ が __n 通り__ だった場合、__最大__ で __n 通り__ しか __着手__ を行う __必要がなくなる__ ので、__処理の時間__ を __短縮__ することができます。

下記の表は __合法手の数__ と、それぞれのアルゴリズムで必要となる __着手の数__ の __最大値__ です。表から、__合法手__ の数が __多いほど__、必要な __着手__ の __最大値__ を __大幅に減らす__ ことができることが分かります。また、__〇× ゲーム__ は、__最初__ の __合法手__ の数が __9__ で、__1 手ごと__ に合法手の数が __1 ずつ減る__ ので、表の __合計__ を計算することで __1 試合当たり__ で必要となる __着手の計算回数__ の __最大値__ を __見積もる__ ことができます。表から __改良版のアルゴリズム__ では、__合計__ が __約 1/5__ になるので、かなりの __計算時間__ の __削減__ を __期待__ できるでしょう。

| 合法手の数 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 合計 | 
|:--|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __元のアルゴリズム__  | 2  | 6  | 12  | 20  | 30  | 42  | 56  | 72 | 240 |
| __改良版のアルゴリズム__  |  2  | 3  | 4  | 5  | 6   | 7  | 8  | 9 | 44 | 
 
:::note
上記は __概算__ に __すぎない__ ので、__正確ではない__ 点に __注意__ して下さい。例えば、上記の計算では、ゲームが __8 手以内__ で __決着__ する場合を __考慮していません__。
:::

上記のアルゴリズムが __正しい理由__ について少し考えてみて下さい。

### 改良版のアルゴリズムが正しい理由

__〇× ゲーム__ は __下記の性質__ があるゲームです。

* 一度 __マークを配置したマス__ は、その __内容が変更される__ ことは __決してない__
* 一度の __手番__ で自分の __マークを配置できるマス__ は __1 マスだけ__ である
* 自分と相手の __手番__ は __交互に回ってくる__

__上記の性質__ から、__自分の手番__ の __局面__ の __合法手__ に、__次__ の __相手の手番__ で __相手が着手__ することで __相手が勝利するか__ どうかは、__以下の場合を除いて変化__ することは __ありません__。

1. __自分の着手__ で __自分が勝利__ する（__相手の手番__ が __回ってこない__）
2. __自分__ がそのマスに __着手する__（__相手__ がそのマスに __着手できない__）

例えば、__下図__ の __局面__ で、__〇__ が __2 に着手__ すると __〇 が勝利__ し、__1 に着手__ すると __次__ の __相手の × の手番__ で __×__ は __1 に着手できません__ が、__それ以外__ の __どの合法手__ に __〇 が着手__ しても、__1 に × が着手__ して __× が勝利__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dd546555-c89a-a743-e2e3-71e807934017.png" width="100">

__手順 3__ の処理を __実行__ するということは、__現在の局面__ で __〇__ がどの __合法手に着手__ しても __勝利できない__ ことが __確定__ したということなので、上記の __条件 1__ が __満たされる__ ことは __ありません__。また、__手順 3__ の __意図__ は、__相手__ がそのマスに __着手__ することで、__相手が勝利するか__ どうかを __調べる__ ことなので、上記の __条件 2__ は __考慮__ に入れる __必要__ は __ありません__。

従って、__改良前__ の __手順 3__ の __処理__ を行う際に、自分は上記の __条件 1、2 以外__ の合法手に __着手した局面__ で、__相手__ が __勝利できるか__ どうかを __判定__ しますが、先ほど説明したように、__条件 1、2 以外__ のマスに __着手__ を行った場合は、__相手の着手__ による __勝利__ に __影響__ を __与えません__。

__改良前__ の __手順 3__ で、__自分の着手__ が、__相手の着手__ による __勝利__ に __影響を与えない__ ということは、__自分__ が __着手しない場合__ でも __相手の勝利__ に __影響を与えない__ ということなので、__手順 3__ で、__現在の局面__ を __相手の手番__ と考えても __相手の勝利__ を __調べる__ ことが __できます__。以上が、__改良__ した __アルゴリズム 3__ によって、__ルール 6__ の __処理__ を行うことができる __理由__ です。

#### 具体例による説明

言葉の説明だけでは __わかりづらい__ と思いますので、__具体例__ を挙げて __説明__ します。

__下図の局面__ で、__次__ の __相手の × の手番__ で、__相手__ が __1__ に __着手__ した場合に、__× が勝利するか__ どうかを __判定__ することを考えてみて下さい。

![82.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/abefabe4-8c30-3b7e-6920-6e386314b1a7.png)

__この局面__ では、__〇__ は __合法手__ の 1 ~ 5 のどのマスに __着手__ しても __勝利できず__、__手順 1、2__ で __処理__ が __終了__ することは __ない__ ので、__手順 3__ の処理が __行われます__。

__手順 3__ では、__上図の局面__ で、__1 ~ 5__ の __それぞれ__ のマスに __〇 が着手__ を行った __下図__ の __それぞれの局面__ で、__× が勝利__ できる __合法手__ が __あるかどうか__ を調べます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2fb4c8f6-5972-ea94-0e23-576221714b97.png" width="400">

次に、__手順 3__ で __×__ が __1__ のマスに __着手__ して __勝利できるか__ どうかを __どのように判定__ しているかを考えてみて下さい。

__手順 3__ では、上図の __2 ~ 4__ の __局面__ で、__実際__ に __1__ のマスに __× が着手__ を行った、下図の __2 ~ 4__ の __局面__ の状態を __調べる__ ことで、その __判定__ を行います。しかし、__下図__ からわかるように、__現在の局面__ で、__〇__ が __1 以外__ の 2 ~ 4 のどのマスに __着手__ を行っても、その __次__ の __× の手番__ で __×__ が __1__ に __着手__ を行うと __× が勝利します__。

このようなことが起きるのは、先ほど説明した __〇× ゲームの性質__ が __原因__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/65f8f04e-8041-7173-851b-195c2a729485.png" width="350">

__〇__ が __1 以外__ のどの合法手に __着手__ しても __× の勝利__ に __影響を与えない__ ということは、__〇 の 着手__ が、__× の 勝利__ に __影響しない__ という事を意味します。従って、下図の「__着手なし__」のように、__現在の局面__ で  __〇__ が __着手を行わず__ に __×__ が __1 に着手__ を行っても、__× が勝利__ します。

上記は、__× が着手__ することで __× が勝利__ する __1 のマス__ についての説明ですが、__着手__ しても __× が勝利しない__、__2 ~ 4__ のマスについても、__同様の理由__ で、__現在の局面__ で __〇__ が __着手を行わなくても__、__× が勝利しない__ という __結果__ に __影響__ を与えることは __ありません__。気になる方は、上記のような __図__ を書いて __確認__ してみて下さい。

上記の事から、__手順 3__ の __処理__ で、__〇__ が __着手を行う必要がない__、すなわち、__現在の局面__ を __相手の手番__ の局面と __みなして__ 処理を行っても __良い__ ことがわかります。

### 改良版のアルゴリズムを使った `ai6` の実装

下記のプログラムは、__改良版__ のアルゴリズムで __`ai6`__ を __実装__ したプログラムです。

* __`mb_list`__ に関する __処理__ は __必要が無くなった__ ので __削除__ した
* __16 行目__：__`legal_moves`__ に対する __繰り返し処理__ を行うように __修正__ する
* __18 行目__：__`mb`__ の __手番__ を __入れ替える__
* __19 行目__：__入れ替えた手番__ を __`enemy_turn`__ に __代入__ して __とっておく__
* __20、21 行目__：__相手の手番__ で __合法手__ に __着手__ を行う
* __22、23 行目__：__相手が勝利__ していた場合は、その __合法手__ を __返り値__ として __返す__

なお、__元のプログラム__ では、__相手の手番__ の __局面__ を表す __`mb`__ を __コピー__ した __`mb_next`__ に対して __着手__ を行っていたので、22 行目では __相手の手番__ を __`mb.turn`__ のように __記述__ できました。一方、__改良版__ では __`mb`__ に対して __着手__ を行うので、__`mb.turn`__ は __自分の手番__ になります。そのため、__19 行目__ で __相手の手番__ を __`enemy_turn`__ に __代入__ して __記録__ しておく __必要__ があります。

```python
 1  from marubatsu import Marubatsu
 2 
 3  def ai6(mb_orig):
 4      # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
 5      legal_moves = mb_orig.calc_legal_moves()
 6      # 合法手が 1 つしかない場合は、その合法手を返り値として返す
 7      if len(legal_moves) == 1:
 8          return legal_moves[0]
 9      for move in legal_moves:
10          mb = deepcopy(mb_orig)
11          x, y = move
12          mb.move(x, y)
13          if mb.status == mb_orig.turn:
14              return move
15      # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
16      for move in legal_moves:
17          mb = deepcopy(mb_orig)
18          mb.turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
19          enemy_turn = mb.turn
20          x, y = move
21          mb.move(x, y)
22          if mb.status == enemy_turn:
23              return move
24       
25      return choice(legal_moves)
```

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

```python
from marubatsu import Marubatsu

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        mb.turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
        enemy_turn = mb.turn
        x, y = move
        mb.move(x, y)
        if mb.status == enemy_turn:
            return move
       
    return choice(legal_moves)
```
</details>

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

```diff_python
from marubatsu import Marubatsu

def ai6(mb_orig):
    # mb_orig の合法手の中で、自分が勝利できる合法手があればそこに着手する
    legal_moves = mb_orig.calc_legal_moves()
    # 合法手が 1 つしかない場合は、その合法手を返り値として返す
    if len(legal_moves) == 1:
        return legal_moves[0]
-   mb_list = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
-       mb_list.append(mb)
        if mb.status == mb_orig.turn:
            return move
    # 〇 が勝利する合法手が存在しないことが確定したので、手順 3 を行う
-   for mb in mb_list:
+   for move in legal_moves:
-       # mb は、mb_orig に対して、move に着手を行った、相手の手番の局面
-       # mb の合法手の中で、相手が勝利できる合法手があればそこに着手して相手の勝利を阻止する
-       next_legal_moves = mb.calc_legal_moves()       
-       for next_move in next_legal_moves:
-           next_mb = deepcopy(mb)                
-           x, y = next_move
-           next_mb.move(x, y)
-           if next_mb.status == mb.turn:
-               return next_move
+       mb = deepcopy(mb_orig)
+       mb.turn = Marubatsu.CROSS if mb.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE
+       enemy_turn = mb.turn
+       x, y = move
+       mb.move(x, y)
+       if mb.status == enemy_turn:
+           return move
       
    return choice(legal_moves)
```
</details>

下記は、__修正後__ の __`ai6`__ と __`ai2`__ で __対戦__ を行うプログラムです。__実行結果__ は __修正前__ と __ほぼ同じ__ ですが、__処理時間__ は、筆者のパソコンでは __8.5 秒__ から __2.8 秒__ に、__大幅に短縮__ されました。これは、__約 1/3__ の __短縮__ なので、__先程__ の __概算__ の __1/5__ ほどは __短縮されていません__ が、実際に __アルゴリズムの改良__ によって __処理時間__ を __かなり短縮__ できることが __確認__ できました。

:::note warn
このように、__同じ処理__ を行う場合でも、__アルゴリズム__ によって、__処理の速度__ が __大きく変わる__ 場合があります。ただし、初心者の方が、今回の記事で紹介したようなアルゴリズムを自分で考えるのは難しいでしょう。__自分__ で __効率の良いアルゴリズム__ を __考える__ ためには、__さまざまなアルゴリズム__ を __体験__ して __勉強__ する __必要__ があります。本記事でさまざなアルゴリズムを紹介しているのはそのためです。
:::

実行時間が短縮されたので、__以後__ は __10000 回__ の __対戦を行う__ ことにします。

```python
ai_match(ai=[ai6, ai2], match_num=1000)
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai6 VS ai2
count     win    lose    draw
o         896      17      87
x         692      56     252
total    1588      73     339

ratio     win    lose    draw
o       89.6%    1.7%    8.7%
x       69.2%    5.6%   25.2%
total   79.4%    3.6%   17.0%
```

### 他の AI との対戦

他の `ai3`、`ai4`、`ai5`、と自分自身と対戦してみます。

```python
ai_match(ai=[ai6, ai3])
```

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

```
ai6 VS ai3
count     win    lose    draw
o        8685     147    1168
x        6193     577    3230
total   14878     724    4398

ratio     win    lose    draw
o       86.9%    1.5%   11.7%
x       61.9%    5.8%   32.3%
total   74.4%    3.6%   22.0%
```

```python
ai_match(ai=[ai6, ai4])
```

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

```
ai6 VS ai4
count     win    lose    draw
o        9240     373     387
x        6615    2903     482
total   15855    3276     869

ratio     win    lose    draw
o       92.4%    3.7%    3.9%
x       66.1%   29.0%    4.8%
total   79.3%   16.4%    4.3%
```

```python
ai_match(ai=[ai6, ai5])
```

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

```
ai6 VS ai5
count     win    lose    draw
o        8878     228     894
x        6549    1372    2079
total   15427    1600    2973

ratio     win    lose    draw
o       88.8%    2.3%    8.9%
x       65.5%   13.7%   20.8%
total   77.1%    8.0%   14.9%
```

```python
ai_match(ai=[ai6, ai6])
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai6 VS ai6
count     win    lose    draw
o        3091    1693    5216
x        1765    3127    5108
total    4856    4820   10324

ratio     win    lose    draw
o       30.9%   16.9%   52.2%
x       17.6%   31.3%   51.1%
total   24.3%   24.1%   51.6%
```

下記は、上記の結果を表にまとめたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai6` VS `ai2`__  | 88.9 | 2.2 | 8.9 | 70.3 | 6.2 | 23.5 | 79.6 | 4.2 | 16.2 |
| __`ai6` VS `ai3`__  | 86.9 | 1.5 | 11.7 | 61.9 | 5.8 | 32.3 | 74.4 | 3.6 | 22.0 |
| __`ai6` VS `ai4`__  | 92.4 | 3.7 | 3.9 | 66.1 | 29.0 | 4.8 | 79.3 | 16.4 | 4.3 |
| __`ai6` VS `ai5`__  | 88.8 | 2.3 | 8.9 | 65.5 | 13.7 | 20.8 | 77.1 | 8.0 | 14.9 |
| __`ai6` VS `ai6`__  | 30.9 | 16.9 | 52.2 | 17.6 | 31.3 | 51.1 | 24.3 | 24.1 | 51.6 |

__上記の結果__ から、以下のような __考察__ を行いました。

* __`ai6`__ は、__これまでに作成__ した __すべての AI__ に対して __大きく勝ち越す__ ので、__ルール 6__ の __効果__ が __非常に大きい__ ことが __確認__ できる
* __`ai4`__ に対して、__勝率が高い__ ので、__`ai4`__ には __欠陥がありそう__ であることが __再確認__ できる
* __`ai6`__ の __通算の勝率__ は、__相手__ が __`ai5`__ のほうが __`ai3` より高い__ ので、__`ai6` を基準__ とした __強さ__ は、__`ai3` &gt; `ai5`__ のように見えるかもしれないが、__敗率__ は __`ai5`__ のほうが __`ai3` よりかなり大きい__ ので、__`ai6` を基準__ とした __強さ__ は、__`ai3` &lt; `ai5`__ であると __考察__ できる
* __自分自身__ との __対戦__ では、__約 50 %__ で __引き分け__ になるので、__〇× ゲーム__ は、__強い AI どうし__ が __対戦__ すると、__引き分け__ の __可能性__ が __高くなる__ ゲームであることが __推測__ できる

# ルールその 7（ルール3 と ルール 6 の併用）

__[ルール 3](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-3-%E7%9C%9F%E3%82%93%E4%B8%AD%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__ と __ルール 6__ は、完全に __異なるアプローチ__ のルールなので、__両方__ のルールを __併用__ することが __できます__。そこで、両方のルールを併用した下記の __ルール 7__ を考えます。

1. __真ん中__ の __マス__ が __空いていれば__、__そこに着手__ する（__ルール 3__）
2. __勝てるマス__ が __存在__ すれば、__そこに着手__ する（__ルール 6__）
3. そうでなければ、__合法手__ を __着手__ した __局面__ のうち、__次__ の __相手の手番__ で、__相手が着手__ すると __相手が勝利__ するマスが __存在すれば__ 、__そこに着手__ して __邪魔__ をする（__ルール 6__）
4. 上記のいずれでもなければ __ランダム__ なマスに __着手__ する

この __ルール 7__ で着手を行う __`ai7`__ は、下記のように __簡単に記述__ することができます。

* __2、3 行目__：__(1, 1)__ のマスが __空いている__ 場合に、__(1, 1)__ を __返り値__ として __返す__（ルール 3）
* __4 行目__：__ルール 6__ で __着手__ を __選択__ する、__`ai6(mb)`__ を __呼び出し__ 、その __返り値__ を __返す__

```python
def ai7(mb):
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
    return ai6(mb):
```

## `ai2` との対戦

下記のプログラムで、基準となる __`ai2`__ との対戦を行います。

```python
ai_match(ai=[ai7, ai2])
```

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai7 VS ai2
count     win    lose    draw
o        9578      22     400
x        8227     240    1533
total   17805     262    1933

ratio     win    lose    draw
o       95.8%    0.2%    4.0%
x       82.3%    2.4%   15.3%
total   89.0%    1.3%    9.7%
```

下記は、上記の結果を表に加えたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __78.1__ | __17.5__ | 4.4 | __44.7__ | __51.6__ | 3.8 | __61.4__ | __34.5__ | 4.1 | あり |
| __[`ai2`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai2-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | 58.7 | 28.8 | 12.6 | 29.1 | 58.6 | 12.3 | 43.9 | 43.7 | 12.5 | |
| __[`ai3`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 | |
| __[`ai4`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E3%83%AB%E3%83%BC%E3%83%AB-4%E5%9B%9B%E9%9A%85%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%AB%E5%84%AA%E5%85%88%E3%81%97%E3%81%A6%E7%9D%80%E6%89%8B%E3%81%99%E3%82%8B)__  | __83.0__ | __9.5__ | 7.4 | __57.2__ | __33.0__ | 9.7 | __70.1__ | __21.3__ | 8.6 | あり |
| __[`ai5`](https://qiita.com/ysgeso/items/ff28a95dff50322e6b16#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-5%E5%8B%9D%E3%81%A6%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AB%E5%8B%9D%E3%81%A4)__  | __81.2__ | __12.3__ | 6.5 | __51.8__ | __39.8__ | 8.4 | __66.5__ | __26.0__ | 7.4 | |
| __`ai6`__  | __88.9__ | __2.2__ | 8.9 | __70.3__ | __6.2__ | 23.5 | __79.6__ | __4.2__ | 16.2 |
| __`ai7`__  | __95.8__ | __0.2__ | 4.0 | __82.3__ | __2.4__ | 15.3 | __89.0__ | __1.3__ | 9.7 |

表から、__`ai7`__ の成績は、__`ai6`__ よりも __大幅に向上__ することがわかります。従って、__ルール 3__ と __ルール 6__ を __併用__ することが __有効である__ ことがわかりました。

### 他の AI との対戦

__`ai3`__、__`ai4`__、__`ai5`__、__`ai6`__ と __自分自身__ と __対戦__ してみます。

```python
ai_match(ai=[ai7, ai3])
```

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

```
ai7 VS ai3
count     win    lose    draw
o        9580      19     401
x        6130     582    3288
total   15710     601    3689

ratio     win    lose    draw
o       95.8%    0.2%    4.0%
x       61.3%    5.8%   32.9%
total   78.5%    3.0%   18.4%
```

```python
ai_match(ai=[ai7, ai4])
```

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

```
ai7 VS ai4
count     win    lose    draw
o       10000       0       0
x        6581    2934     485
total   16581    2934     485

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x       65.8%   29.3%    4.9%
total   82.9%   14.7%    2.4%
```

```python
ai_match(ai=[ai7, ai5])
```

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

```
ai7 VS ai5
count     win    lose    draw
o        9540      36     424
x        8109     543    1348
total   17649     579    1772

ratio     win    lose    draw
o       95.4%    0.4%    4.2%
x       81.1%    5.4%   13.5%
total   88.2%    2.9%    8.9%
```

```python
ai_match(ai=[ai7, ai6])
```

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

```
ai7 VS ai6
count     win    lose    draw
o        3024     431    6545
x         706    1556    7738
total    3730    1987   14283

ratio     win    lose    draw
o       30.2%    4.3%   65.5%
x        7.1%   15.6%   77.4%
total   18.6%    9.9%   71.4%
```

```python
ai_match(ai=[ai7, ai7])
```

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

```
ai7 VS ai7
count     win    lose    draw
o        2989     414    6597
x         397    3039    6564
total    3386    3453   13161

ratio     win    lose    draw
o       29.9%    4.1%   66.0%
x        4.0%   30.4%   65.6%
total   16.9%   17.3%   65.8%
```

下記は、上記の結果を表にまとめたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai7` VS `ai2`__  | 95.8 | 0.2 | 4.0 | 82.3 | 2.4 | 15.3 | 89.0 | 1.3 | 9.7 |
| __`ai7` VS `ai3`__  | 95.8 | 0.2 | 4.0 | 61.3 | 5.8 | 32.9 | 78.5 | 3.0 | 18.4 |
| __`ai7` VS `ai4`__  | 100.0 | 0.0 | 0.0 | 65.8 | 29.3 | 4.9 | 82.9 | 14.7 | 2.4 |
| __`ai7` VS `ai5`__  | 95.4 | 0.4 | 4.2 | 81.1 | 5.4 | 13.5 | 88.2 | 2.9 | 8.9 |
| __`ai7` VS `ai6`__  | 30.2 | 4.3 | 65.5 | 7.1 | 15.6 | 77.4 | 18.6 | 9.9 | 71.4 |
| __`ai7` VS `ai7`__  | 29.9 | 4.1 | 66.0 | 4.0 | 30.4 | 65.6 | 16.9 | 17.3 | 65.8 |

__上記の結果__ から、以下のような __考察__ を行いました。

* __`ai7`__ は、__`ai5` 以前__ の AI に __対して__ は __圧倒的な強さ__ を持つため、__ルール 6__ は __強い AI__ を __作成__ する際に __非常に重要__ である __可能性__ が __高い__
* __`ai7`__ は、__`ai6`__ に対して __通算__ の __勝率__ が __敗率より高い__ ので、__真ん中__ のマスに __優先的に着手__ することが __有効__ であることが __確認__ できる
* __`ai7`__ が __〇を担当__ した場合で、__`ai6`__ と __`ai7`__ に対する __成績__ が __ほぼ同じ__ になるが、その理由は[以前の記事](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%8C-%E3%80%87-%E3%82%92%E6%8B%85%E5%BD%93%E3%81%99%E3%82%8B%E5%A0%B4%E5%90%88-1)で説明した理由と同じである
* __`ai7` VS `ai6`__ や __`ai7` VS `ai7`__ は、__引き分け率__ が __約 50%__ の __`ai6` VS `ai6` より__ もさらに __引き分け率__ が __高い__ ので、やはり、__〇× ゲーム__ は、__強い AI どうし__ が __対戦__ すると、__引き分け__ の __可能性__ が __高くなる__ ゲームであるという __推測__ が __正しい可能性__ が __高く__ なった
* __`ai7`__ が __〇 を担当__ した場合は __`ai4`__ に対する __勝率__ が __100%__ になるので、__`ai4`__ は、__× を担当__ する場合に __致命的な欠陥__ があることが __再確認__ できた


## ルール 3 と ルール 6 の順番

先程の __ルール 7__ では、__ルール 3__ を __適用した後__ で __ルール 6__ を __適用__ していますが、下記のように、その __順番を逆__ にしたルールも考えられます。

1. __勝てるマス__ が __存在__ すれば、__そこに着手__ する（__ルール 6__）
2. そうでなければ、__合法手__ を __着手__ した __局面__ のうち、__次__ の __相手の手番__ で、__相手が着手__ すると __相手が勝利__ するマスが __存在すれば__ 、__そこに着手__ して __邪魔__ をする（__ルール 6__）
3. __真ん中__ の __マス__ が __空いていれば__、__そこに着手__ する（__ルール 3__）
4. 上記のいずれでもなければ __ランダム__ なマスに __着手__ する

今回の記事の最初で、ルールの __手順__ の __順番__ を __変える__ と、__結果__ が __変化する場合がある__ ので __注意__ する __必要__ があると説明しましたが、__ルール 7__ の場合は、__ルール 3__ と __ルール 6__ を適用する __順番__ を __変えても__、__結果__ は __変化しません__。その理由について考えてみて下さい。

### ルール 3 によって着手が行われる条件

__ルール 3__ によって __着手__ が行われる __条件__ は、__真ん中のマス__ が __空いている__ ことです。従って、__真ん中__ のマスが __空いていない場合__ は、__ルール 3__ によって __着手__ は __行われません__。

### ルール 6 によって着手が行われる条件

__ルール 6__ によって __着手__ が行われる __条件__ は、__次__ の __自分の着手__ で __自分が勝利できる__ か、__次__ の __相手の着手__ で __相手が勝利できる__ 場合です。

__〇× ゲーム__ では、__自分のマーク__ を __3 つ並べる__ ことで __勝利する__ ので、__〇__ も __×__ も、__1、2 回目__ の着手で __勝利__ することは __あり得ません__。従って、__〇__ と __×__ の __1 回目__ の着手で、__ルール 6__ が __適用__ されることは __ありません__。

### 〇 の 1 回目の着手の場合

上記から、__〇__ の __1 回目__ の着手で、__ルール 6__ が __適用__ されることは __ありません__。従って、__ルール 3__ と __ルール 6__ を適用する __順番__ は、__〇__ の __1 回目__ の着手に __影響__ を __与えません__。

__〇__ の __1 回目__ の着手では、__真ん中__ のマスは __必ず空いている__ ので、__ルール 3__ が __適用__ されて __真ん中__ のマスに __着手__ が行われます。

### × の 1 回目の着手の場合

__同様の理由__ で、__×__ の __1 回目__ の着手で、__ルール 6__ が __適用__ されることは __ありません__。従って、__ルール 3__ と __ルール 6__ を適用する __順番__ は、__×__ の __1 回目__ の着手に __影響__ を __与えません__。

__真ん中__ のマスが __空いている__ 場合は __ルール 3__ が __適用__ されて __真ん中__ のマスに __着手__ が行われ、空いていない場合はランダムなマスに着手が行われます。__その結果__ として、__×__ の __1 回目__ の __着手の後__ では、__必ず真ん中__ のマスが __空ではなくなります__。

### 2 回目以降の着手の場合

上記の事から、__2 回目以降__ の __着手__ では、__〇 の場合__ も、__× の場合__ も __真ん中__ のマスが __空いていない__ ので、__ルール 3__ が __適用__ されることは __ありません__。従って、__ルール 3__ と __ルール 6__ を適用する __順番__ は、__2 回目以降__ の着手に __影響__ を __与えません__。

以上から、__すべての場合__ で、__ルール 3__ と __ルール 6__ を適用する __順番__ は、ルール 7 の着手に __影響__ を __与えない__ ことがわかります。

# 今回の記事のまとめ

今回は、以下の表のようなアルゴリズムの __`ai6`__  を実装しました。また、__これまでに作成__ した __ルール 3__ と __ルール 6__ を __組み合わせ__ た __`ai7`__ を実装し、その __2 つのルール__ を __組み合わせる__ ことで __かなり強い AI__ を __作成__ することができたことを確認しました。

まだ __最強ではありません__ が、__`ai7`__ は __それなりに強い AI__ になっていると思いますので、__実際__ に __`mb.play(ai=[None, ai7])`__ と __`mb.play(ai=[ai7, None])`__ を実行して __`ai7` と対戦__ して、その __強さを確認__ してみて下さい。

| 関数名 | アルゴリズム |
|:-:|:--|
| __`ai6`__  | 勝てる場合に勝つ<br>そうでない場合は相手の勝利を阻止する<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __`ai7`__  | 真ん中のマスが空いていればそこに着手する<br>そうでない場合は、勝てる場合に勝つ<br>そうでない場合は相手の勝利を阻止する<br>そうでない場合は __ランダム__ なマスに __着手__ する |

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

以下のリンクから、本記事で入力して実行した JupyterLab のファイルを見ることができます。

https://github.com/ysgeso/marubatsu/blob/master/046/marubatsu.ipynb

今回の記事では、marubatsu.py は修正していないので、marubatsu_new.py はありません。

以下のリンクは、今回の記事で更新した ai.py です。

https://github.com/ysgeso/marubatsu/blob/master/046/ai_new.py

# 次回の記事

https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e

[^1]:正確には、強さが変わらない場合もあります
[^2]:__最大__ としたのは、__× が勝利__ する合法手が __見つかった時点__ で手順 3 の __処理が終了__ するからです
[^3]:__合法手__ が __1 つ__ の場合は __1 * 0 = 0__ になると思う人がいるかもしれませんが、今回の記事の最初の方で説明したように、__合法手__ が __1 つ__ しかない場合は、__ルール 6__ は __適用しません__