Pythonで〇×ゲームのAIを一から作成する　その44　ルールベースのAIとAIの検証

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/729c5425573cf1e8051f

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/044/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)__  | ランダムなマスに着手する |


基準となる __`ai2`__ との __対戦結果__（単位は %）は以下の通りです。太字は `ai2 VS 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 |


# AI の種類

前回の記事で、__AI の強さ__ を __評価__ するための、__AI どうしの対戦__ を行う __環境__ が整いましたので、今回の記事から、__強い__ 〇× ゲームの __AI の作成__ を開始します。

〇× ゲームのような、ゲームの AI を作成する手法には、大きく分けて、__ルールベース__、__探索型__、__機械学習型__ の 3 種類があります[^1]。最初に、この中で、__初期__ の AI から __よく使われてきた__、__ルールベースの AI__ について説明します。なお、この 3 種類の手法は、単独で利用される場合だけでなく、__組み合わせて利用__ される場合もあり、本記事でも紹介する予定です。

__ルールベース__ の AI とは、__解決すべき問題__ に対する、__人間の知識__ を __ルール化__ し、その __ルールに基づいて__  AI が __判断を行う__ という AI です。

ルールベースの AI には、主に以下のような __利点__ と __欠点__ があります。

* __利点__
    * __問題__ を __完全に解決__ する __方法__ を __ルール化__ できれば、__ルールベース__ の AI を使って、__100 % 正しい判断__ を __行う__ ことが __できる__
    * __ルール化__ を __行う__ ことが __できれば__、__ルール__ を __if 文など__ の __条件分岐__ を __組み合わせて記述__ することが __できる__ ので、__プログラム__ を __記述しやすい__
    * __ルール__ を __順番__ に __適用__ することで __判断を行う__ ので、__AI__ が行った __判断の理由__ の __説明__ がしやすい。また、その __結果を元__ に、__ルール__ の __評価__ や __改良__ を __行う__ ことが __できる__
* __欠点__
    * 人間の知識をルール化するため、__解決すべき問題__ を、__人間__ が __熟知__ している __必要__ がある。例えば、__将棋の AI__ を __ルールベース__ で __作成__ する場合は、__将棋が強い__ 人 __でなければ__、__強い AI__ を __作る__ ことは __できない__
    * __ルール__ は、__厳密__ に __記述__ する必要がある。そのため、理屈ではなく、__感覚__ で __行っている__ ようなことを __ルール化__ することは __困難__ である。例えば、__人間__ が __歩く__ 際に、__どのように__ 体を __動かしているか__ の __ルール__ を、__説明できる人__ は __ほとんどいない__ だろう
    * __ルール__ をプログラムで __記述__ するのが __困難__ な __場合がある__
    * __複雑な問題__ の場合は、その __問題__ を __完全に解決する方法__ が __誰にもわからない__ 場合がある。そのような場合は、その問題に対する __不完全な知識__ を __ルール化__ するしかないが、そのような __AI が行う判断__ も当然 __不完全__ なものになってしまう。例えば、__勘違い__ などによって __間違ったルール化__ を行ってしまうと、__間違った判断__ が行われてしまう
    * 問題解決のための __ルール__ が __増えた__ 結果、__収拾がつかなくなる__ 場合がある。例えば、ルールが __多くなりすぎ__ ると、__AI__ が行った __判断__ が、__どのルール__ によって __行われた__ ものであるかの __判断がつけづらくなる__。また、__新しいルール__ を __作成__ する際には、__それまでのルール__ との __整合性__ を気にしながら作成する必要があるため、__ルールの数__ が __多く__ なれば __なるほど__、__新しいルール__ を __作成__ するのが __困難__ になる。


言葉の説明だけではよくわからないと思いますので、実際に __〇× ゲーム__ の __AI__ を __ルールベース__ で __作成__ することで、上記の __利点__ と __欠点__ の一部について __説明__ します。この先の説明を読む前に、〇× ゲームの強い AI を作るためのルールについて少し考えてみて下さい。

## `ai1` と `ai2` の分類

実は、__`ai1`__ と __`ai2`__ は、__ルールベース__ の __AI に分類__ されます。その理由は、__`ai1`__ の __アルゴリズム__ である「左上から順に空いているマスを探し、最初に見つかったマスに着手する」と、__`ai2`__ の「ランダムなマスに着手する」は、いずれも __着手するマス__ を __決めるため__ の __ルール__ だからです。__ルールベース__ の AI の __ルール__ は、AI の __アルゴリズム__ であると __言い換えても良い__ でしょう。なお、__`ai1`__ と __`ai2`__ の __ルール__ は、いずれも __強い AI__ を __作成する__ ための __ルールではない__ 点が、これから作成する AI と異なります。

以後は、__`ai1`__ の「左上から順に空いているマスを探し、最初に見つかったマスに着手する」を __ルール 1__、__`ai2`__ の「ランダムなマスに着手する」を __ルール 2__ と __表記__ し、わかりやすいように、今後作成する __ルールの番号__ と、__AI__ の __関数の番号__ を __合わせる__ ことにします。

# ルール 3 （真ん中のマスに優先して着手する）

__〇× ゲーム__ を __ある程度遊んだ__ ことがある人は、__真ん中__ の __(1, 1)__ のマスに __着手__ すると __勝ちやすい__ ということが __なんとなく理解__ できるようになるのではないかと思います。そこで、__そのこと__ と、__ルール 2__ を __組み合わせ__ た 下記のような __ルール 3__ が考えることにします。

1. __真ん中__ の __マス__ が __空いていれば__、__そこに着手__ する
2. __真ん中__ の __マス__ が __空いていなければ__、__ランダム__ なマスに __着手__ する

__思いついたルール__ を __何も考えず__ に __実装__ すると、__見当違い__ な __ルール__ であった場合に __時間の無駄__ になるので、__実装__ を __行う前__ に、その __ルール__ が __有効であるか__ どうかについて、今回は簡単に __考察__ することにします。当たり前だと思う人が多いかもしれませんが、__真ん中__ のマスに __着手__ すると __勝ちやすい__ ことの __理由__ について __論理的な説明__ ができる人はどれくらいいるでしょうか？その理由について少し考えてみて下さい。

なお、__ルール__ の __実装__ が __簡単に行える__ 場合は、__考察せず__ に AI を __実装__ する場合もあります。

## 真ん中のマスへの着手が有利である理由の考察

__真ん中のマス__ への __着手__ が __有利である__ ことを __示す__ ためには、__真ん中以外__ のマスへの __着手__ と __比較__ する必要があります。その際に、__他__ の __8 マス__ すべてとの __比較__ を行う __必要__ は __ありません__。その __理由__ は、__〇× ゲーム__ の __ゲーム盤__ は __正方形__ なので、__ゲーム盤__ を __90 度__ ずつ、3 回 __回転__ した場合に、__ゲーム盤__ が __ぴったり__ と __重なり__、__隅__ の __マス__ を、他の __すべて__ の __隅のマス__ に __移動__ することが __できる__ からです。従って、__4 つ__ の __隅のマス__ は __同じ性質を持つ__ と __みなす__ ことができます。__同様の理由__ で、__4 つ__ の __辺のマス__ も __同じ性質を持つ__ と __みなす__ ことができるので、__隅__ と __辺__ の __2 種類__ のマスへの __着手__ と __比較すればよい__ ことが分かります。

次に、__有利である__ ことを __表す指標__ を __決める__ 必要があります。__わかりやすい指標__ として、その __マスに着手__ することで、__何種類__ の __勝ち方が生じる__ かを __数える__ というものが __考えられます__。具体的には、__着手__ した __マスを含む__、__勝利の並び__ の __種類__ を __数え__ ます。


下図は、__真ん中__ のマス、__隅__ のマス、__辺__ のマスの __それぞれ__ に対して、その __マスを含む__、__勝ち方__ の __並び__ を __列挙__ したものです。__真ん中__ のマスに __着手__ することで、__最も多い__ 4 種類の __勝ち方__ があるので、__この指標__ では __真ん中の着手__ が __最も有利__ であることが分かります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e65aadea-c0de-c810-c3c7-95e2d32b4630.png" width="500">

__相手の立場__ に立って __考える__ と、__真ん中__、__隅__、__辺__ に __着手__ した場合は、__それぞれ__ 上図の __勝ち方__ を __相手から奪う__ ことになります。〇× ゲームの __勝ち方__ は __横 3 通り__、__縦 3 通り__、__斜め 2 通り__ の __計 8 通り__ なので、__真ん中に着手__ することで、__相手__ の __勝ち方__ を __最も少ない__ 8 - 4 = __4 通り__ に __限定__ できます。その 4 通りは、下のような __図を書く__ ことで __確認__ できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5b9bdd8e-83ba-6706-f17c-0a6948ff9f45.png" width="350">

先程、__ルールベース__ の __AI__ には「人間の知識をルール化するため、__解決すべき問題__ を、__人間__ が __熟知__ している __必要__ がある」という __欠点__ があると説明しましたが、__〇×ゲーム__ の AI の __ルール化__ を行うためには、上記のような __〇×ゲームに関する知識__ が必要になります。

## ルールの作成時に厳密な証明が必要かどうか

__上記の考察__ では、「__マスに着手__ することで、__何種類__ の __勝ち方__ が __生じる__ かを __数える__」という、__一見する__ と非常に __もっともらしく見える__ 指標を使って、__真ん中__ のマスに __着手__ をすることが __有利__ であることを __示しました__ が、__この指標__ が __本当__ に __有利__ であることを __正確に示す__ 指標 __であるか__ の __証明__ は __行われていません__。従って、__上記の考察__ から、__真ん中__ に __着手__ することが __有利__ である __可能性が高そう__ だということは __言えます__ が、__絶対に有利__ であるということが __証明__ されたわけでは __ありません__。

__理想的__ には、__ルール__ が __正しい__ ことを __厳密に証明したほうが良い__ ですが、__実際__ には __厳密な証明__ が __困難__ または __不可能__ であることが良くあります。実際に、__〇× ゲーム__ で、__真ん中__ のマスに __優先的に着手__ する __ルール__ が __正しい__ ことを __厳密に証明__ することは __かなり困難__ です。どれだけ困難であるかは、今後の記事で実際に紹介する予定です。

従って、__思いついたルール__ が __正しいか__ どうかの __厳密な証明__ が __困難__ な場合は、__有利__ である __可能性が高い__ ことが __分かった時点__ で、__とりあえず__ そのルールで __AI を実装__ し、__他の AI__ と実際に __対戦__ することで __強くなったかどうか__ を __検証する__ という方法を取るのが __一般的__ です。__検証__ した __結果__、その __ルール__ で __強くなる__ ことが分かれば __採用__ し、__そうでなければ__ そのルールは __廃棄__ します。また、その際に、その __ルール__ で __強くなった__（うまくいかなかった）__理由__ を __考察__ することで、__問題の性質__ を __理解__ し、__既存のルール__ の __改良案__ や、__新しいルール__ の __作成__ に __つなげて__ いきます。これは、__現実の世界__ で、__問題を解決する際__ に、__さまざまな方法__ を __考案__ し、__実際__ に __試した結果__ で __判断する__ という、__試行錯誤__ を行う __手法と同じ__ です。

本記事でも、__真ん中__ のマスへの __着手__ が __最も有利__ であるという __厳密な証明__ を __行わず__ に、とりあえず __AI を作成__ し、__他の AI__ と __対戦__ することで __検証を行う__ ことにします。

## `ai3` の実装

下記は、先程の __ルール 3__ を再掲したものです。__このルール__ を元に __`ai3`__ を __実装__ します。

1. __真ん中__ の __マス__ が __空いていれば__、__そこに着手__ する
2. __真ん中__ の __マス__ が __空いていなければ__、__ランダム__ なマスに __着手__ する

__真ん中のマス__ が __空いていれば__、__そこに着手__ するという処理は、__ルールベースの利点__ で説明したように __if 文__ による __条件分岐__ を使って __簡単に記述__ でき、__ランダム__ なマスに __着手__ する __処理__ は、__`ai2`__ と __同じ処理__ なので、__`ai3`__ は、下記のプログラムのように記述できます。

* __5、6 行目__：__真ん中__ の __マス__ である __(1, 1)__ のマスが __空であるかどうか__ を __if 文__ で __判定__ し、__空の場会__ は、__着手__ する マスの __座標__ として、__`1, 1`__ を __返す__
* __7、8 行目__：__真ん中__ の __マス__ が __空でない場合__ は、__`ai2`__ と __同様の方法__ で、__合法手の中__ から __ランダム__ なマスを __選択__ し、その __座標__ を __返す__

```python
1  from marubatsu import Marubatsu
2  from random import choice
3
4  def ai3(mb):
5      if mb.board[1][1] == Marubatsu.EMPTY:
6          return 1, 1
7      legal_moves = mb.calc_legal_moves()
8      return choice(legal_moves)
```

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

```python
from marubatsu import Marubatsu
from random import choice

def ai3(mb):
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
    legal_moves = mb.calc_legal_moves()
    return choice(legal_moves)
```
</details>

<details><summary><strong>修正箇所（<code>ai2</code> との比較です）</strong></summary>

```diff_python
-def ai2(mb):
+def ai3(mb):
+   if mb.board[1][1] == Marubatsu.EMPTY:
+       return 1, 1
    legal_moves = mb.calc_legal_moves()
    return choice(legal_moves)
```
</details>

__`ai_match`__ で __複数回の対戦__ を __行う前__ に、__`ai3`__ が __正しく実装されたか__ どうかを __確認__ するために、__`play`__ メソッドを使って、__`ai2`__ と __対戦__ を行い、__途中経過__ を __表示__ することにします。実行結果から、__〇 を担当__ する __`ai3`__ が、__最初__ に __(1, 1)__ に __着手__ することが __確認__ できます。

:::note
本記事では __`ai3`__ が __〇 の担当__ で __1 度__ しか __確認__ しませんが、__心配な方__ は __`ai3`__ が __〇 の担当__ と、__× の担当__ で __何度か `play`__ メソッドを __実行__ し、__`ai3`__ が、__(1, 1)__ が __空いていれば__ そこに __必ず着手__ することを __確認__ して下さい。

本記事の __確認__ では、__対戦相手__ を __ランダムな着手__ を行う __`ai2`__ としていますが、__`mb.play(ai=[ai3, None])`__ を __実行__ して、__人間相手で確認__ することも __できます__。
:::

```python
from ai import ai1, ai2

mb = Marubatsu()
mb.play(ai=[ai3, ai2])
```

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

```
Turn o
...
...
...

Turn x
...
.O.
...

Turn o
.X.
.o.
...

Turn x
Ox.
.o.
...

Turn o
oxX
.o.
...

Turn x
oxx
.oO
...

Turn o
oxx
Xoo
...

winner o
oxx
xoo
..O

'o'
```

## セルの最後の行の計算結果の表示

[以前の記事](https://qiita.com/ysgeso/items/4d55e73d6571fe85aa49#importlibreload-%E3%82%92%E4%BD%BF%E3%81%86)のノートで簡単に説明しましたが、__JupyterLab__ では、__セル__ の __最後の行__ の __式の計算結果__ が、__`print`__ を __記述しなくても表示__ されます。上記の実行結果の __最後__ に表示される __`o`__ は、__`mb.play(ai=[ai3, ai2])`__ の __返り値__ です。

__セル__ の __最後の行__ の __計算結果__ が __表示されない__ ようにする __方法__ として、下記のプログラムのように、__行の最後__ に __半角の `;`__（セミコロン） を __記述__ するという __方法__ があります。なお、実行結果は、最後に `o` などが表示されなくなるだけなので省略します。

```python
mb.play(ai=[ai3, ai2]);
```

__`;`__ は、__文__ を __区切る記号__ で、例えば、__`a = 1; b = 2`__ のように __文__ を __`;` で区切る__ ことで、__1 行__ に __2 つ以上__ の __文__ を __記述__ することが __できます__。上記のように __行の最後__ に __`;`__ を __記述__ することで、__`mb.play(ai=[ai3, ai2])`__ が、その __行__ で __最後に計算された式__ とは __みなされなくなる__ ので、__`mb.play(ai=[ai3, ai2])`__ の __計算結果__ が、__表示されなく__ なります。以後は、セルの __最後の行__ の __計算結果__ を __表示したくない場合__ に、__行の最後__ に __`;` を記述__ することにします。

### `print` の表示との違い

[以前の記事](https://qiita.com/ysgeso/items/4d55e73d6571fe85aa49#importlibreload-%E3%82%92%E4%BD%BF%E3%81%86)のノートでも簡単に説明しましたが、__セル__ の __最後の行__ の __式の計算結果__ の __表示__ と、__`print`__ による __式の計算結果__ の __表示__ が __異なる場合__ があります。

例えば、__`None`__ は、下記のプログラムのように、__セル__ の __最後の行__ に __記述__ した場合と、__`print`__ で __表示__ した場合は、__表示の結果__ が __異なります__。

__最後の行__ の __式__ の __計算結果__ が __`None`__ の __場合__ は __何も表示されません__。

```python
None
```

実行結果
```
```

__`print`__ で __`None`__ を __表示__ した __場合__ は、__None__ が __表示__ されます。

```python
print(None)
```

実行結果
```
None
```

下記のプログラムのように、__セル__ の __最後の行__ で __`ai_match`__ を __実行__ した場合に、__余計な表示__ が __行われない__ のは、__`ai_match`__ が __return 文__ によって __値を返さない関数__ だからです。[以前の記事](https://qiita.com/ysgeso/items/95282cb1532602799052#%E5%87%BA%E5%8A%9B%E3%81%8C%E5%AD%98%E5%9C%A8%E3%81%97%E3%81%AA%E3%81%84%E9%96%A2%E6%95%B0)で説明したように、__return 文__ で __終了しない__ 関数は、関数の __返り値__ として __`None` が返り__、その __`None`__ は __画面に表示されない__ ので、__余計な表示__ は __行われません__。

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

下記のような、__セル__ の __最後の行__ で __`print`__ で __表示を行う__ プログラムで、__余計な表示__ が __行われない理由__ も、__`print`__ が __`None`__ を __返り値__ として __返すから__ です。

```python
print(1)
```
実行結果
```
1
```

:::note
__セル__ の __最後の行__ の __計算結果__ の __表示__ と、__`print`__ による __表示__ が __異なる場合がある理由__ は、__セル__ の __最後の行__ の __計算結果__ が、__オブジェクト__ の __`__repr__`__ メソッドを使って __文字列に変換__ したものを __表示__ するのに対し、__`print`__ が __オブジェクト__ の __`__str__`__ メソッドを使って __文字列に変換__ したものを __表示__ するからです。

__`__repr__`__ メソッドと、__`__str__`__ メソッドの __違い__ については、[以前の記事](https://qiita.com/ysgeso/items/ed1eb1cacf9a3e7dfa29#marubatsu-%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE-__str__-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AE%E5%AE%9A%E7%BE%A9) のリンク先をスクロールした所にある __ノートを参照__ して下さい。
:::


## `ai2` との対戦

`ai3` が実装できたので、下記のプログラムで、__基準__ となる __`ai2`__ と __対戦__ します。

```python
from ai import ai_match

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

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

```
ai3 VS ai2
count     win    lose    draw
o        6932    1922    1146
x        3885    4765    1350
total   10817    6687    2496

ratio     win    lose    draw
o       69.3%   19.2%   11.5%
x       38.9%   47.6%   13.5%
total   54.1%   33.4%   12.5%
```

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

| 関数名 | 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`__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 |

表から、__`ai1`__ 程ではありませんが、__`ai3`__ は、__`ai2`__ に __対して強い AI__ であることがわかります。このように、__適切なルール__ であれば、__ルール 3__ のような __非常に単純なルール__ であっても、__AI の強さ__ を __向上__ させることが __可能__ です。

## `ai1` との対戦

次に、下記のプログラムで、__`ai3`__ と __`ai1`__ の __対戦__ を行います。

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

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

```
ai3 VS ai1
count     win    lose    draw
o        3666    5663     671
x         838    9162       0
total    4504   14825     671

ratio     win    lose    draw
o       36.7%   56.6%    6.7%
x        8.4%   91.6%    0.0%
total   22.5%   74.1%    3.4%
```

また、__比較__ を行うために、__`ai2` から見た `ai1`__ との __対戦__ を行います。

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

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

```
ai2 VS ai1
count     win    lose    draw
o        5138    4459     403
x        1740    7844     416
total    6878   12303     819

ratio     win    lose    draw
o       51.4%   44.6%    4.0%
x       17.4%   78.4%    4.2%
total   34.4%   61.5%    4.1%
```

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

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |  
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai3`__ VS __`ai1`__  | 36.7 | 56.6 | 6.7 | 8.4 | 91.6 | 0.0 | 22.5 | 74.1 | 3.4 |
| __`ai2`__ VS __`ai1`__  | 51.4 | 44.6 | 4.0 | 17.4 | 78.4 | 4.2 | 34.4 | 61.5 | 4.1 |

表から、__`ai3`__ は __`ai1` に__ 対して __全体__ で __勝率__ が __22.5%__ と __大きく負け越している__ ことが分かります。また、__x の手番__ の場合は、__勝率__ が __8.4%__ と __とんでもなく低い__ ことが分かります。

さらに、__`ai2`__ VS __`ai1`__ の __結果__ と __比較__ すると、__`ai2` より__ も、__`ai3`__ のほうが __`ai1` に対して__ さらに __成績が悪い__ ことが分かります。先ほどの、__`ai3` VS `ai2`__ の結果では、__`ai3`__ が __`ai2` に__ 対して __強い__ ことがわかりましたが、__`ai1` と対戦__ した場合は、__`ai2` のほう__ が、__`ai3` より__ も __`ai1` に__ 対して __強い__ という __逆の結果__ になることがわかります。

__強さ__ を __不等号__ の __記号__ で表す（__大きいほう__ が __強い__）と、下記のようになります。

* __`ai3` VS `ai2`__ では、__`ai3` > `ai2`__ である
* __`ai1`__ に __対する戦績__ では、__`ai2` > `ai3`__ である

:::note warn
以前に説明したことの繰り返しになりますが、上記のように、__特定の AI__ との __対戦結果__ は、__対戦__ した __AI の間__ の __相対的__ な __強さ__ のみ __測ります__。__全体的__ な __強さ__ を __測る__ ためには、__さまざま__ な __AI__ と __対戦__ した __結果__ を __検証__ する __必要__ があります。
:::


本記事の最初で述べたように、__ルールベース__ の AI の __利点__ の一つに、「__AI__ が行った __判断の理由__ の __説明__ がしやすい」というものがあります。実際に、上記のような __逆の結果__ になる __理由__ を __考察__ することが __できる__ ので、その理由について少し考えてみて下さい。

## 対戦結果の考察

このような結果になった __理由__ を調べるためには、__それぞれ__ の __組み合わせ__ で __どのような対戦__ が　__行われる__ かを __考察__ する必要があります。そのような考察は、[以前の記事](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#ai1-%E3%81%8C-ai2-%E3%81%AB%E5%8B%9D%E3%81%A1%E8%B6%8A%E3%81%99%E7%90%86%E7%94%B1)で説明した、「`ai1` が `ai2` に勝ち越す理由」で既に行っており、今回も __同様の考察__ を行います。

今回は、__`ai3`__ が __〇 を担当__ する場合と、__× を担当__ する場合に __分けて考察__ します。

### 用語の説明

__〇__ や __×__ を __担当する AI__ が、__何手目__ の __着手__ を __行ったか__ を「〇 の 1 手目の着手」、__全体__ で __何手目__ の __着手__ を __行ったか__ を「1 手目の着手」のように __表記__ すると、「__手目__」という __表記__ の __意味__ が __まぎらわしくなる__ ので、本記事では以降は、__〇__ や __×__ の __手数__ は「〇 の 1 __回目__ の着手」、全体の手数は「1 __手目__ の着手」のように、__区別__ して __表記__ することにします。

### `ai3` が 〇 を担当する場合

__`ai1`__ は、__左上のマス__ から __順番__ に __空いているマス__ に __着手__ を行うので、__`ai3`__ が __〇 を担当する場合__ には、__3 回目まで__ に、__上の行__ の __いずれか__ の __マスに着手__ を行わなければ __敗北__ してしまいます。しかし、__`ai3`__ は __1 回目__ で __必ず__ 真ん中の __(1, 1)__ に __着手を行う__ ので、__残りの 2 回__ で、__上の行__ の __いずれかのマス__ に __着手__ を行わなければなりません。従って、__`ai2` よりも__、__不利な状況__ で __`ai1`__ と __対戦__ することになり、__`ai2` VS `ai1`__ よりも __対戦成績__ が __悪く__ なります。

:::note
[以前の記事](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#ai1-%E3%81%8C-ai2-%E3%81%AB%E5%8B%9D%E3%81%A1%E8%B6%8A%E3%81%99%E7%90%86%E7%94%B1)では失念していましたが、__`ai3`__ が __〇 を担当__ する場合は、__3 回目まで__ に、__2 行目__ の __(0, 1)__、__(1, 1)__、__(2, 1)__ の 3 マスに __着手__ を行うことで、__`ai1` より先__ に __勝利__ する __場合__ が __あります__。ただし、詳しい計算方法は省略しましすが、__`ai3` VS `ai1`__ で、__`ai3`__ が __3 回目まで__ に __2 行目__ の 3 マスに __着手__ して __勝利__ する __確率__ は __約 5%__  程度 __しかない__ ので、__上記の考察__ に __大きな影響__ は __与えません__。

__`ai2` VS `ai1`__ で __`ai2`__ が __3 回目まで__ に __2 行目__ または __3 行目__ の 3 マスに __着手__ して __勝利__ する __確率__ は __約 4%__ なので、__前回の記事__ の __考察__ にも __大きな影響__ は __与えません__。 
:::

### `ai3` が × を担当する場合

この場合は、__`ai3`__ は __2 回目まで__ に、__上の行__ の __いずれかのマス__ に __着手__ を __行う必要__ がありますが、__`ai1`__ は __1 回目__ で __必ず (0, 0)__ に __着手を行う__ ため、__`ai3`__ の __1 回目__ では __真ん中__ の __マス__ が __空いている__ ので、__必ず (1, 1)__ に __着手__ を行います。さらに、__`ai1`__ は __2 回目__ で __必ず (1, 0)__ に __着手__ を行うので、__`ai3`__ は __2 回目__ で残った __6 マスの中__ から __(2, 0)__ に __着手__ を行わなければ __負けてしまいます__ します。従って、この場合も __`ai3`__ は、__`ai2` よりも__、__不利な状況__ で __`ai1`__ と __対戦__ することになり、__`ai2` VS `ai1`__ よりも __対戦成績__ が __悪く__ なります。

図で書くと、__`ai3`__ が __× を担当__ する場合は、__3 手目まで__ は、__必ず下図__ の __着手__ が __行われます__。__×__ の __2 回目__ の __着手__ で、__黄色いマス__ に __着手__ を __行わなければ__、__その次__ に __〇__ が __黄色のマス__ に __着手__ して __× は敗北__ しますが、__阻止__ する __確率__ は 1/6 = __約 16.7 %__ しかありません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/14209234-4ce3-f28a-6d99-d3b68b5866bb.png" width="100">

### 考察のまとめ

上記のことから、__`ai3`__ は、__どちらの手番__ でも __1 回目__ で __必ず (1, 1)__ に __着手__ を行うため、__`ai2`__ が __一番上の行__ で __3 回の着手__ で __勝利__ しようとする __場合__ に対して、__ランダムな着手__ で __邪魔をする機会__ が __`ai2` より__ も __1 回分減ってしまう__ ことになります。そのため、__`ai3` VS `ai1`__ の __対戦成績__ は、__`ai2` VS `ai1`__ よりも __下がって__ しまいます。

ただし、この結果は、__`ai3`__ の __アルゴリズム__ が __`ai1`__ の __アルゴリズムに__ 対して __極端に相性が悪い__ せいです。__`ai3` VS `ai1`__ と __`ai2` VS `ai1`__ の __結果だけ__ から、__一般的__ に見て __`ai2`__ と __`ai3`__ の __どちらが強いか__ を __判断__ することは __できない__ 点に __注意__ して下さい。__一般的な強さ__ については、__他のさまざまな AI__ と __対戦__ し、__総合的__ に __判断__ する __必要__ があります。

## `ai3` との対戦

せっかくなので、さらに __`ai3` どうし__ で __対戦__ させてみることにします。

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

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

```
ai3 VS ai3
count     win    lose    draw
o        6801    2000    1199
x        1919    6939    1142
total    8720    8939    2341

ratio     win    lose    draw
o       68.0%   20.0%   12.0%
x       19.2%   69.4%   11.4%
total   43.6%   44.7%   11.7%
```

下記は、上記の結果と __`ai3` VS `ai2`__ の対戦結果を表にまとめたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |  
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai3`__ VS __`ai3`__  | 68.0 | 20.0 | 12.0 | 19.2 | 69.4 | 11.4 | 43.6 | 44.7 | 11.7 |
| __`ai3`__ VS __`ai2`__ | 69.2 | 18.9 | 11.8 | 39.1 | 47.0 | 13.9 | 54.1 | 33.0 | 12.9 |

表から、__`ai3`__ が __〇 を担当__ した場合は、__相手__ が __`ai2`__ と __`ai3`__ の場合で、__対戦成績__ が __ほとんど変わらない__ が、__× を担当__ した場合は、__相手__ が __`ai2` のほう__ が __対戦成績が良くなる__ ことが分かります。このような結果になる理由について少し考えてみて下さい。

先程と同様に、__`ai3`__ が __〇 を担当__ する場合と、__× を担当__ する場合に __分けて考察__ します。

### `ai3` が 〇 を担当する場合

__`ai3` VS `ai3`__ の場合は、__必ず最初__ に __(1, 1)__ に __着手が行われる__ ので、__× を担当__ する __`ai3`__ は、__1 回目__ で __(1, 1)__ が __空ではありません__。従って、__× を担当__ する __`ai3`__ の __すべての手番__ で __ランダムなマス__ に __着手__ を行うことになるので、__`ai3` VS `ai2`__ で __`ai2`__ が × を担当する場合と __全く同じ処理__ が行われることになります。そのため、__`ai3`__ が __〇 を担当__ する場合は、相手が __`ai2`__ と __`ai3`__ の場合で、__対戦成績__ が __ほぼ同じ__ になります。

### `ai3` が × を担当する場合

__`ai3` VS `ai3`__ の場合は、__× を担当__ する __`ai3`__ は、__1 回目__ で __(1, 1)__ が __空ではない__ ので、__真ん中__ に __着手__ することは __できません__ が、__`ai2` VS `ai3`__ の場合は 1 回目で __`ai2`__ が __(1, 1)__ に __着手__ を行うとは __限らない__ ので、__有利__ になる __(1, 1)__ に __着手できる可能性__ があります。そのため、__`ai2`__ と対戦する方が、__`ai3`__ と対戦するよりも __対戦成績__ が __良く__ なります。

このように、作成した AI の間で、__さまざまな組み合わせ__ で __対戦__ を行い、その __結果__ を __考察__ することで、__さまざまな__ ことが __わかる__ ようになります。また、__わかったこと__ を __利用__ して、__ルール__ の __欠点__ や、__改良点__ を __見つける__ ことが __できる場合__ があるので、__考察__ は __重要__ です。

ただし、__作成__ した __AI の数__ が __多くなる__ と、__組み合わせ__ の __数__ が __多くなりすぎる__ ので、__今後__ は今回のように、__すべて__ の __組み合わせ__ で __対戦__ を行うことは __しません__。

# ルール 4（四隅のマスに優先して着手する）

__ルール 3__ では、__真ん中__ の __マス__ に __優先して着手__ を行いますが、__真ん中__ の __マス__ が __埋まっている__ 場合に、__次に有利__ だと考えられる __四隅__ の __いずれか__ の __マス__ に __着手__ するという __ルール 4__ が考えられます。ただし、__四隅__ の __いずれか__ のマスに __着手__ する __処理__ は、プログラムの __記述__ が __複雑__ になるので、__`ai1`__ の __アルゴリズム__ と __同様__ に、下記のような、__左上のマス__ から __順に__、__四隅のマス__ を __調べ__、__最初__ に __見つかった__、__空いているマス__ に __着手__ することにします。

1. __真ん中__ の __マス__ が __空いていれば__ 、__そこに着手__ する
2. __真ん中__ の __マス__ が __空いていなければ__、次に __四隅のマス__ を __左上__ から __順に調べ__、__最初__ に __見つかった__、__空いているマス__ に __着手__ する
3. __四隅__ も __空いていなければ__、__ランダムなマス__ に __着手__ する

この __ルール 4__ で __本当__ に AI が __強くなるか__ どうかを __考察__ することは __可能__ ですが、__思いついたルール__ で __AI を作成__ し、__他の AI__ と __対戦__ を行った __結果__ から __考察__ したほうが __分かりやすい__ 場合があるので、__AI__ を __簡単に実装できる場合__ などでは、__思いついたルール__ を __考察せず__ に __実装__ することも __良くあります__。そこで、今回は __先に__ この __ルール 4__ が __良いか__ どうかの __考察__ を __行わず__ に、__`ai4`__ を __作成__ して他の AI と __対戦__ した __結果__ をから __考察__ することにします。

下記は、上記の __ルール 4__ で着手を行う、__`ai4`__ を定義するプログラムです。

* __4 ~ 7 行目__：__四隅のマス__ の __座標__ は、__(0, 0)__、__(0, 2)__、__(2, 0)__、__(2, 2)__ なので、__`x` 座標__ と __`y` 座標__ を __0__ から __3 未満__ まで __2 ずつ増やし__ ながら __繰り返し処理__ を行うことで、__左上__ の __マス__ から __順番__ に、__四隅__ の __マスの座標__ を __調べる__ ことができる。__2 ずつ増やし__ ながら行う __繰り返し処理__ は、[以前の記事](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#range-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9)で説明した、__`range`__ の __`step`__ を使って __`range(0, 3, 2)`__ のように __記述__ できる。__それ以外__ の部分は、__`ai1`__ の __処理と同様__ の __方法__ で __記述__ できる

```python
1  def ai4(mb):
2      if mb.board[1][1] == Marubatsu.EMPTY:
3          return 1, 1
4      for y in range(0, 3, 2):
5          for x in range(0, 3, 2):
6              if mb.board[x][y] == Marubatsu.EMPTY:
7                  return x, y
8      legal_moves = mb.calc_legal_moves()
9      return choice(legal_moves)
```

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

```python
def ai4(mb):
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
    for y in range(0, 3, 2):
        for x in range(0, 3, 2):
            if mb.board[x][y] == Marubatsu.EMPTY:
                return x, y
    legal_moves = mb.calc_legal_moves()
    return choice(legal_moves)
```
</details>

<details><summary><strong>修正箇所（<code>ai3</code> との比較です）</strong></summary>

```diff_python
-def ai3(mb):
+def ai4(mb):
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
+   for y in range(0, 3, 2):
+       for x in range(0, 3, 2):
+           if mb.board[x][y] == Marubatsu.EMPTY:
+               return x, y
    legal_moves = mb.calc_legal_moves()
    return choice(legal_moves)
```
</details>

次に、__`ai4`__ が __正しく実装されたか__ どうかを __確認__ します。実行結果から、__〇 を担当__ する __`ai4`__ が、__1 回目__ で __(1, 1)__ に __着手した後__ で、__空いている四隅__ の __マス__ に、__左上__ から __順番__ に __着手__ を __行い__、__四隅__ が __埋まった後__ は __ランダム__ な __着手__ を行うことが __確認__ できます。

```python
mb.play(ai=[ai4, ai2]);
```
実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
Turn o
...
...
...

Turn x
...
.O.
...

Turn o
.X.
.o.
...

Turn x
Ox.
.o.
...

Turn o
ox.
.o.
..X

Turn x
oxO
.o.
..x

Turn o
oxo
.o.
X.x

Turn x
oxo
.oO
x.x

Turn o
oxo
Xoo
x.x

winner draw
oxo
xoo
xOx
```

## `ai2` との対戦

__`ai4`__ が実装できたので、下記のプログラムで、__基準__ となる __`ai2` と対戦__ します。

```python
ai_match(ai=[ai4, ai2])
```
実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai4 VS ai2
count     win    lose    draw
o        8303     952     745
x        5723    3304     973
total   14026    4256    1718

ratio     win    lose    draw
o       83.0%    9.5%    7.4%
x       57.2%   33.0%    9.7%
total   70.1%   21.3%    8.6%
```

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

| 関数名 | 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`__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 |
| __`ai4`__  | __83.0__ | __9.5__ | 7.4 | __57.2__ | __33.0__ | 9.7 | __70.1__ | __21.3__ | 8.6 |

表から、__`ai4`__ は、__`ai2`__ に __対して__、__`ai1` より__ も __強い AI__ であることがわかります。なお、__`ai4` VS `ai2`__ の __対戦結果__ の __考察__ については、__この後__ の __`ai3` との対戦__ の所で __行います__。

## `ai1` との対戦

次に、__`ai1`__ との __強さを比較__ するために、下記のプログラムで __`ai1` と対戦__ します。

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

実行結果

```
ai4 VS ai1
count     win    lose    draw
o       10000       0       0
x       10000       0       0
total   20000       0       0

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x      100.0%    0.0%    0.0%
total  100.0%    0.0%    0.0%
```

実行結果から、__`ai4`__ は __`ai1` に 100% 勝利__ することが分かりました。その __理由__ は、実際に、下記のプログラムのように、__`play`__ メソッドで __1 回__ ずつ __手番を入れ替えて対戦__ して __表示__ される __途中経過__ を __見て考察__ するのが __わかりやすい__ でしょう。

### `ai4` が 〇 を担当する場合

__`ai4`__ と __`ai1`__ の __アルゴリズム__ から、__必ず__ 下記のように、〇 __(1, 1)__、× __(0, 0)__、〇 __(2, 0)__、× __(1, 0)__、〇 __(0, 2)__ の __順__ で __着手__ が行われ、__`ai4` が__ 担当する __〇__ が __勝利__ します。

```python
mb.play(ai=[ai4, ai1]);
```

実行結果
```
Turn o
...
...
...

Turn x
...
.O.
...

Turn o
X..
.o.
...

Turn x
x.O
.o.
...

Turn o
xXo
.o.
...

winner o
xxo
.o.
O..
```

### `ai4` が 〇 を担当する場合

__`ai4`__ と __`ai1`__ の __アルゴリズム__ から、__必ず__ 下記のように、〇 __(0, 0)__、× __(1, 1)__、〇 __(1, 0)__、× __(2, 0)__、〇 __(0, 1)__、× __(0, 2)__ の __順__ で __着手__ が行われ、__`ai4` が__ 担当する × が __勝利__ します。

```python
mb.play(ai=[ai1, ai4]);
```

実行結果
```
Turn o
...
...
...

Turn x
O..
...
...

Turn o
o..
.X.
...

Turn x
oO.
.x.
...

Turn o
ooX
.x.
...

Turn x
oox
Ox.
...

winner x
oox
ox.
X..
```

この __結果__ から、やはり __`ai1`__ は __強い AI__ であるとは __言えなさそう__ であることが分かりました。従って、__以後は__ 新しい __AI を作成__ した際に、__`ai1` との対戦__ は __省略__ することにします。

## `ai3` との対戦

次に、下記のプログラムで __`ai3`__ と対戦することにします。

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

実行結果

```
ai4 VS ai3
count     win    lose    draw
o        8313     945     742
x        2735    7014     251
total   11048    7959     993

ratio     win    lose    draw
o       83.1%    9.4%    7.4%
x       27.4%   70.1%    2.5%
total   55.2%   39.8%    5.0%
```

下記は、上記の結果を表に加えたものです。なお、__上 の 4 つ__ は __`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`__  | __69.3__ | __19.2__ | 11.5 | __38.9__ | __47.6__ | 13.5 | __54.1__ | __33.4__ | 12.5 |
| __`ai4`__  | __83.0__ | __9.5__ | 7.4 | __57.2__ | __33.0__ | 9.7 | __70.1__ | __21.3__ | 8.6 |
| __`ai4`__ VS __`ai3`__  | 83.1 | 9.4 | 7.4 | 27.4 | 70.1 | 2.5 | 55.2 | 39.8 | 5.0 |

実行結果から、__`ai4`__ は、__〇 を担当__ する場合は、__`ai3` に__ 対して __83.1%__ の __勝率__ で __大きく勝ち越し__ ます。その理由について少し考えてみて下さい。

一方、__× を担当__ する場合は、__勝率__ が __27.4% しか__ なく、__敗率__ は __70.1% も__ あります。__特に__、この __70.1%__ という __敗率__ は、__他の AI__ が __× を担当__ して __`ai2` と対戦__ したどの __結果__ よりも、__かなり大きい__ ので、この __ルール 4__ には何か __大きな欠陥__ が __潜んでいそう__ です。その欠陥が何かについて少し考えてみて下さい。

### `ai4` が 〇 を担当する場合

`ai4` は、__〇 を担当__ した場合、__必ず 1 回目__ で __(1, 1)__ に __着手__ を行うので、__× を担当__ する __`ai2`__ または __`ai3`__ は、__すべて__ の __着手__ で __ランダム__ な __着手__ を行います。そのため、__`ai4` VS `ai3`__ と、__`ai4` VS `ai2`__ では、__×__ を __`ai2` が担当__ しても、__`ai3` が担当__ しても __全く同じ処理__ が行われます。従って、__`ai4` VS `ai2`__ と __`ai4` VS `ai3`__ の __対戦成績__ は __ほぼ同じ__ になります。

「__`ai2`__ または __`ai3`__」 のような __記述__ は __冗長__ なので、__以後__ の 「__`ai4` が 〇を担当する場合__」の __説明__ では __`ai3` に ついてのみ言及__ することにします。

__`ai4`__ は、__2 回目以降__ は、__(0, 0)__、__(2, 0)__、__(0, 2)__、__(2, 2)__ の __順__ で __空いているマス__ に __着手__ を行いますが、1 回目で __(1, 1)__ に __〇 が配置済__ なので、__(0, 0)__、__(2, 2)__ または、__(2, 0)__、__(0, 2)__ の __2 つのマス__ に __着手__ できれば __`ai4`__ の __勝利__ になります。__`ai3`__ は、__ランダム__ なマスに __着手を行う__ ため、__それを阻止__ するような __着手__ を偶然行う __確率__ は、__直観的__ に __低そう__ で、実際に、先程の表の __`ai4` VS `ai3`__ の __対戦成績__ は __`ai4`__ が __80% 以上__ で __大きく勝ち越し__ ます。このことから、__`ai3`__ は、__〇 を担当__ する __`ai4`__ にとって __かなり相性が良い__ と __考察__ できます。

:::note
__現実の世界__ では、__結果__ に対する __原因__ を __説明できない__ 場合もあり、そのような場合は、例えば `ai4` が `ai3` に __大きく勝ち越す__ という __結果__ だけを __重要視__ します。なお、そのような場合は、__原因__ が __わからない__ ので、__結果の改善__ は __困難__ です。
:::

#### おおまかな確率の計算

上記の __考察__ は、__直観的__ なものなので、__仮説__ にすぎません。__本当に正しいか__ どうかを __確認__ するためには、__〇 が勝利__ する __場合__ の __確率__ を __計算__ する __必要__ があります。

__〇__ が __勝利__ する __正確な確率__ を __計算__ するのは __かなり面倒__ ですが、多くの場合では、__AI どうし__ の __強さの考察__ を行う際に、__確率__ を __厳密に計算__ する __必要__ は __ありません__。[以前の記事](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#ai1-%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%E3%81%ABai2-%E3%81%8C-2-%E6%89%8B%E9%80%A3%E7%B6%9A-%E3%81%A7-%E4%B8%8A%E3%81%AE%E8%A1%8C-%E3%81%AB-%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%82%8F%E3%81%AA%E3%81%84-%E7%A2%BA%E7%8E%87)でも、__おおまかな確率__ を __計算__ する __例を紹介__ しましたが、今回の記事でも __大まかな確率__ を __計算__ することで、__上記の考察__ が __正しいそう__ であるかどうかを __確認__ することにします。

:::note
多くの方には関係のない話になると思いますが、__論文で発表__ する __場合など__ では、__厳密な確率__ を __計算__ する __必要__ があります。
:::

#### `ai4` VS `ai3` の着手の、おおまかな組み合わせの数の計算

__〇 が勝利__ する __確率__ を __計算__ するためには、__`ai4` VS `ai3`__ で行われる __着手__ の大まかな __組み合わせの数__ を __計算__ する __必要__ があります。

__`ai4`__ は、__5 箇所__ の __マス__ に __優先的__ に __着手__ を行うので、__〇 の 3 回目__ の __着手__ を行う __5 手目まで__ で、その __すべて__ のマスが __埋まる__ ことは __ありません__。そのため、__〇 の 3 回目__ の __着手__ が __ランダム__ に __行われる__ ことは __ありません__。従って、__6 手目まで__ の __着手__ の組み合わせは、__ランダム__ に行われる __× の 3 回__ の __着手__ の __組み合わせだけ__ を __考慮__ することで、おおまかに、8 * 6 * 4 = __約 192 通り__ と __計算__ することができます。

:::note
__×__ の __1 回目__ の __着手__ は __2 手目__ なので __残り__ の __マスの数__ は __8__、__2 回目__ の __着手__ は __4 手目__ なので __残り__ の __マスの数__ は __6__、__3 回目__ の __着手__ は __残り__ の __マスの数__ は __4__ となります。
:::

もちろん、__5 手目__ に __ゲームが決着する場合__ や、__7 手以上__ の __ゲームが存在__ するので、__この組み合わせの数__ は __`ai4` VS `ai2`__ がとりうる __着手の組み合わせ__ の数と __一致しません__ が、__近い数字__ である __可能性が高い__ ので、この __数値__ をおおまかな __全体の組み合わせの数__ とします。

#### 〇 が勝利する場合のおおまかな確率の計算

__厳密ではありません__ が、__〇 が勝利__ するのは、主に以下の図ような場合です。__例外__ として、__先に × が勝利__ する場合や、__斜め以外__ の __方向__ で __〇 が勝利__ する場合がありますが、それほど __確率は高くなさそう__ なので、とりあえず __無視__ することにします。

下図は、__〇 を担当__ する __`ai4`__ が __(0, 0)__、__(2, 0)__、__(0, 2)__、__(2, 2)__ の __いずれか__ の __マスに着手__ することで __勝利__ する __5 つのケース__ を表しています。図の __赤色のマス__ は、__〇__ が __マスの中__ に記述された __回数__ の __手番で__ そのマスに __着手を行う__ ことを表しています。__青色のマス__ は、__×__ が、__マスの中__ に記述された __回数以下__ の __手番__ でそのマスに __着手を行う__ ことを表します。

この __5 通り__ が __ピンとこない__ 方は、__`ai4`__ と __`ai3`__ の __アルゴリズム通り__ に、__実際__ に __何度か__ 〇×ゲームの __着手__ を __紙に書いて__ 確認してみると良いでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ff639cfd-79a3-8d04-28da-a0ba80de2450.png" width="350">

分かりづらいと思いますので、図の __1__ と __2__ と __4__ について説明します。

図の __1__ は、__〇__ が __(1, 1)__、__(0, 0)__、__(2, 0)__、__(0, 2)__ の __順__ で __着手__ を行って __勝利__ する __場合__ を表しています。__×__ は、__3 回__ の __手番__ で、__白色__ の __5 つのマス__ の __いずれか__ に __着手__ を行います。

図の __2__ は、__〇__ が __(1, 1)__、__(0, 0)__、__(2, 0)__、__(2, 2)__ の __順__ で __着手__ を行って __勝利__ する __場合__ を表しています。__×__ は、__3 回目__ までの __いずれか__ の __手番__ で、__(0, 2)__ のマスに __着手__ し、__それ以外__ の __2 回__ の手番で、__白色__ の __4 つのマス__ の __いずれか__ に __着手__ を行います。その __理由__ は、__3 回目まで__ に __×__ が __(0, 2)__ に __着手__ を __行わない__ と、__先に 〇__ が __(0, 2)__ に __着手してしまう__ からです。

図の __4__ は、__〇__ が __(1, 1)__、__(0, 0)__、__(2, 2)__ の __順__ で __着手__ を行って __勝利__ する __場合__ を表しています。図の 2 と __同様の理由__ で __×__ は、__1 回目__ と __2 回目__ の手番で、__(2, 0)__ 、__(0, 2)__ または __(0, 2)__、__(2, 0)__ の __順番__ で __着手__ を行います。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/ff639cfd-79a3-8d04-28da-a0ba80de2450.png" width="350">

下記の表は、それぞれの図の __番号__ の __着手__ が行われる __手順__ の __組み合わせ__ を表します。

| 番号 | x の 1 手目 | x の 2 手目 | x の 3 手目 | 組み合わせ | 合計 |
|:-:|:-:|:-:|:-:|:-:| --: |
| __1__ | 5 通り  | 4 通り  | 3 通り  | 5 * 4 * 3 = 60  | 60 | 
| __2__ | (0, 2)<br>4 通り<br>4 通り| 4 通り<br>(0, 2)<br>4 通り  | 3 通り<br>3 通り<br>(0, 2)  | 4 * 3 = 12<br>4 * 3 = 12<br>4 * 3 = 12  | 36 |
| __3__ | (2, 0)<br>4 通り| 4 通り<br>(2, 0)  | 3 通り<br>3 通り  | 4 * 3 = 12<br>4 * 3 = 12  | 24 |
| __4__ | (2, 0)<br>(0, 2) | (0, 2)<br>(2, 0)  | 4 通り<br>4 通り  | 4<br>4| 8 |
| __5__ | (0, 0)  | 5 通り  |   | 5  | 5 |

表から、__すべての組み合わせ__ は 60 + 36 + 24 + 8 + 5 = __133 通り__ であることがわかります。

先ほど計算した、__全体__ の __組み合わせの数__ である __192 通り__ を __利用__ することで、__おおまかな 〇 の勝率__ を 133 / 192 = __約 69.3%__ と __計算__ することができます。この __計算結果__ は、先程の __考察__ の、__〇 が勝利しやすい__ ことを __裏付け__ ています。また、__上記以外__ の __手順__ で __〇 が勝利__ する __場合もある__ ことを __考慮__ すると、先ほどの表の __`ai4` VS `ai3`__ の __〇 の勝率__ の __83.1%__ と __近い数字__ と言えるので、__おおまかな計算結果__ の __精度__ が __妥当__ であることが __確認__ できます。

#### × が勝利する場合のおおまかな確率の計算

せっかくなので、__×__ が __勝利__ する場合の __大まかな確率__ も __計算__ してみることにします。

下図は、__× を担当__ する __`ai3`__ が __先に勝利する場合__ を __列挙__ したものです。図から、__× が先に勝利__ する __着手__ の __組み合わせ__ が __16 通り__ であることがわかります。

図の __数字__ は、__全体__ の __着手の順番__ を表し、__赤__ が __〇 が 100%__ その __手番で__ マスに __着手を行う__ ことを、__オレンジ__ が __〇 がランダム__ にその __手番で__ マスに __着手を行う__ ことを、__青__ が __× がランダム__ にその __手番で__ マスに __着手を行う__ ことを表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/923f6d17-1a59-e8e3-0023-bec646a445ff.png" width="450">

従って、__× の勝率__ は __おおまか__ に 16 / 192 = __約 8.3%__ と __計算__ することができ、先程の __`ai4` VS `ai3`__ の __表__ の __〇__ の __敗率__ の __9.4%__ と __ほぼ一致する__ ことが分かります。

上記の、__大まかな確率__ の __計算結果__ により、先程行った __考察__ が 100% ではありませんが、__おおむね正しそう__ であることが __確認__ できました。

### `ai4` が × を担当する場合

__`ai4`__ が __× を担当__ する場合は、__`ai3`__ は、__1 回目__ で __必ず (1, 1)__ に __着手__ を行います。その後、__`ai4`__ は __(0, 0)__、__(2, 0)__、__(0, 2)__、__(2, 2)__ の __順__ で __マス__ が __空いていれば着手__ を行おうとしますが、〇× ゲームでは、__× の手番__ は __最大__ で __4 回__ しか回ってこないので、__4 回__ の __着手__ で __そのすべてのマス__ が __空いていた場合__ は、__下図の__ ような __着手を行う__ ことになるため、__× が勝利__ することは __ありません__。つまり、__〇__ が __1 回目__ で __(1, 1)__ に __着手__ を __行った場合__ は、__`ai4`__ は、__勝利を目指す着手__ を __行わない__ ということです。これが、__`ai3`__ に __大きく負け越す原因__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/517fd803-cb8d-9425-01b3-e81827accfcc.png" width="350">

一方、__`ai2`__ は __1 回目__ で __(1, 1)__ に __着手__ を行う __確率__ は 1/9 = __約 11%__ なので、__上記__ のような __非常に不利な状況__ になる __確率__ は約 11 % __しかありません__。また、__`ai2`__ が __1 回目__ で __(1, 1)__ に __着手__ を __行わない__ 場合は、__`ai4`__ が __(1, 1)__ に __着手を行います__。もちろん、__先に `ai2`__ が __どこかのマス__ に __着手__ を行っているので、__`ai4`__ が __〇 を担当__ する __場合__ よりは __勝率は下がり__ ますが、先程の考察から __高い勝率__ が __期待__ できます。__実際__ に先程の __`ai4` VS `ai2`__ の __表__ の __×__ の __勝率__ の __57.2%__ が示すように、__高い勝率__ が得られています。

## ルール 4 の評価

上記のことから、__`ai4`__ の __ルール 4__ は、__`ai1`__ や __`ai2`__ に対しては __強い AI__ であるかもしれませんが、__実際__ には __大きな欠陥__ のある __ルール__ であることがわかりました。

従って、本記事では __`ai4`__ を __欠陥のある AI__ と __判断する__ ことにします。

ルール 4 は、本記事の最初で説明した __ルールベース__ の AI の __欠点__ の「__勘違い__ などによって __間違ったルール化__ を行ってしまうと、__間違った判断__ が行われてしまう」の実例です。__一見__ すると __有効そう__ に __見える__ ルールが、__必ずしも強い__ AI に __結びつかないことがある__ ことが、__ルールベース__ の __AI の作成__ の __難しい所__ です。従って、__思いついたルール__ が __本当に有効か__ どうかについては、__必ず検証する必要__ があることを __忘れないように__ して下さい。

なお、__思い付き__ の __アイディア__ が __常に悪い__ というわけではありません。__見込みのなさそう__ な __アイディア__ を __ダメ元__ で __実装__ したら __うまくいった__ ということもあるからです。

# 今回の記事のまとめ

今回は、以下の表のようなアルゴリズムの __`ai3`__ と __`ai4`__ を実装し、__他の AI__ と __対戦__ することで、それぞれの __アルゴリズム__ を __検証__ しました。

| 関数名 | アルゴリズム | 欠陥 | 
|:-:|:--|:--|
| __`ai3`__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | |
| __`ai4`__  | __真ん中__、__隅__ のマスの __順__ で __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | あり |

__`ai3`__、__`ai4`__ は、__どちらも__、__基準__ となる __`ai2`__ より __強くなる__ ことを __確認__ できましたが、__`ai4`__ の __アルゴリズム__ には __欠陥__ があることが __判明__ しました。

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

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

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

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

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

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

# 次回の記事

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

[^1]:実際には、他にも分類の方法がありますが、本記事ではこの 3 つで分類することにします