Pythonで〇×ゲームのAIを一から作成する　その45　勝てる場合に勝つAIと、浅いコピーと深いコピー

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/1e8732db6cd1b0104276

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/045/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>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | あり |

基準となる __`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 | あり |

# ルールその 5（勝てる場合に勝つ）

__ルール 3、4__ は、__有利__ だと __思われる__ マスに __優先的__ に __着手__ するというアプローチでしたが、__ルール 5__ では、__別の観点__ の __ルール__ を考えてみることにします。

__〇× ゲーム__ を __何回か遊べば__ すぐにわかると思いますが、__自分の手番__ の __合法手__ の中で __勝利できる__ マスが __存在__ する場合は、その __マスに着手__ すれば __その時点で勝ち__ になるので、__絶対__ にそこに __着手すべき__ です。しかし、__ルール 3、4__ では、__勝てる場合__ でも __別のマスに着手__ する __場合がある__ ため、__多くの場合__ で __勝てる試合__ を __逃して__ しまいます。

そこで、以下の __ルール 5__ で着手を行う __`ai5`__ を作成することにします。

1. __勝てるマス__ が __存在__ すれば、__そこに着手__ する
2. __勝てるマス__ が __存在しなければ__、__ランダム__ なマスに __着手__ する

## ルール 5 の検証

この __ルール 5__ によって、__基準__ となる __`ai2` より強くなる__ かどうかについて __検証__ します。

__勝てるマスが存在__ する場合に、そこに __必ず着手する場合__ と、__ランダムに着手する場合__ を比較すると、以下の表のようになります。

|  | 結果 |
|:-:|:-:|
| __必ず着手する場合__  | 100% 勝利  |
| __ランダムに着手する場合__  | 勝利、敗北、引き分けのいずれか  |

表からわかるように、__ランダムに着手する__ 場合でも __勝利する可能性__ があるので、__必ず着手する__ 場合のほうが、__結果が良くなる__ とは __限りません__ が、__ランダムに着手する__ 場合の __ほうが__、__必ず着手する__ 場合 __より__ 結果が __悪くなる__ ことは __ない__ ことがわかります。

上記から、__ルール 5__ によって実装された __`ai5`__ と __他の AI__  が __対戦__ した場合の __通算成績__ は、__`ai2`__ が __同じ AI__ と __対戦__ した __通算成績__ と比較すると、__必ず良い成績__（または同等の成績）になることがわかります。従って、__一般的__ に __`ai5`__ のほうが、__`ai2` より__ も __強い__ と言えます。


__上記のルール__ の AI を __実装__ するためには、__着手__ することで __勝利__ できる __合法手があるか__ どうかを __判定__ する __必要__ があります。その判定方法について少し考えてみて下さい。

## 着手することで勝利できる合法手を調べる方法

__`Marubatsu`__ クラスは、`move` メソッドで __着手__ を行った際に、ゲームが __決着したか__ どうかを __判定__ して __`status` 属性__ に __代入__ するという __処理__ を行います。従って、__着手__ することで __勝利__ できる __合法手__ は、__実際__ に __合法手__ を __順番__ に __着手__ した際の __`status` 属性__ によって __調べる__ ことができます。そこで、下記のプログラムのように __`ai5`__ を __実装__ することにします。

* __5 行目__：__for 文__ の __反復可能オブジェクト__ に __`legal_moves`__ を __記述__ することで、__合法手__ を __順番に取り出し__ てローカル変数 __`move`__ に __代入__ するという __繰り返し処理__ を行う
* __6、7 行目__：ローカル変数 __`move`__ から __x 座標__ と __y 座標__ を __取り出し__ て __`x`__ と __`y`__ に __代入__ し、__`mb` の `move` メソッド__ を __呼び出し__ て __(x, y)__ のマスに __着手__ を行う
* __8、9 行目__：__`mb`__ の __`status` 属性__ が、__手番__ を表す __`mb.turn` と等しい__ 場合に、__勝利している__ と __判定__ できるので、その場合はローカル変数 __`move`__ を __着手__ する __座標__ として __返す__
* __10 行目__：__勝利__ できる __合法手__ が __存在__ する場合は、9 行目の __return 文__ が __実行__ されることで、__関数の処理__ が __終了__ するので、__繰り返し処理__ が __終了__ した __時点__ で、__勝利__ できる __合法手__ が __存在しない__ ことが __確定__ する。その場合は、__ランダムな着手__ を表す __座標__ を __返す__

```python
 1  from random import choice
 2
 3  def ai5(mb):
 4      legal_moves = mb.calc_legal_moves()
 5      for move in legal_moves:
 6          x, y = move
 7          mb.move(x, y)
 8          if mb.status == mb.turn:
 9              return move
10      return choice(legal_moves)
```

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

```python
from random import choice

def ai5(mb):
    legal_moves = mb.calc_legal_moves()
    for move in legal_moves:
        x, y = move
        mb.move(x, y)
        if mb.status == mb.turn:
            return move
    return choice(legal_moves)
```
</details>

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

```diff_python
from random import choice

-def ai2(mb):
+def ai5(mb):
    legal_moves = mb.calc_legal_moves()
+   for move in legal_moves:
+       x, y = move
+       mb.move(x, y)
+       if mb.status == mb.turn:
+           return move
    return choice(legal_moves)
```
</details>


次に、下記のプログラムで __`ai5`__ が __正しく実装されたか__ どうかを __確認__ します。なお、2 行目では、後で __利用__ する __予定__ の __`ai_match`__、__`ai3`__、__`ai4`__ を __ついでにインポート__ しています。

実行結果から、以下の __2 点__ が __おかしい__ ことがわかります。

* 「__( 1 , 2 ) のマスにはマークが配置済です__」という __エラーメッセージが表示__ される
* その後で、いきなり __8 つのマス__ に __着手__ が行われた __ゲーム盤が表示__ される

このようなおかしな結果になった理由について少し考えてみて下さい。

```python
from marubatsu import Marubatsu
from ai import ai_match, ai2, ai3, ai4

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

実行結果

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

( 1 , 2 ) のマスにはマークが配置済です
winner o
oxo
xox
oX.
```

## バグの原因の調査

__バグの原因__ を __調べる__ 方法の一つに、プログラムの __処理__ で __利用__ する __変数の値__ が __変化__ する際に、__その値__ を __表示__ するという方法があります。__`ai5`__ の場合は、下記の場合で __`print`__ を使って __変化__ した __変数の値__ を __`print`__ で __表示__ すると良いでしょう。なお、このような __バグの調査や修正__ のために行う __表示__ の事を、__デバッグ表示__ と呼びます。

* __3、5 行目__：__代入__ によって __`legal_moves`__ と __`move`__ の値が __変化__ した __直後__ で、__`print`__ でその __変数の値__ を __表示__ する
* __8、9 行目__：7 行目の __`move`__ メソッドの __処理__ で、__ゲーム盤__ の __状況__ と、__10 行目の式__ で __利用__ する __`mb.status`__ と __`mb.turn`__ の __値が変化__ するので、__それらの値__ を __表示__ する

```python
 1  def ai5(mb):
 2      legal_moves = mb.calc_legal_moves()
 3      print("legal_moves", legal_moves)
 4      for move in legal_moves:
 5          print("move", move)
 6          x, y = move
 7          mb.move(x, y)
 8          print(mb)
 9          print("status", mb.status, "turn", mb.turn)
10          if mb.status == mb.turn:
11              return move
12      return choice(legal_moves)
```

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

```python
def ai5(mb):
    legal_moves = mb.calc_legal_moves()
    print("legal_moves", legal_moves)
    for move in legal_moves:
        print("move", move)
        x, y = move
        mb.move(x, y)
        print(mb)
        print("status", mb.status, "turn", mb.turn)
        if mb.status == mb.turn:
            return move
    return choice(legal_moves)
```
</details>

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

```diff_python
def ai5(mb):
    legal_moves = mb.calc_legal_moves()
+   print("legal_moves", legal_moves)
    for move in legal_moves:
+       print("move", move)
        x, y = move
        mb.move(x, y)
+       print(mb)
+       print("status", mb.status, "turn", mb.turn)
        if mb.status == mb.turn:
            return move
    return choice(legal_moves)
```
</details>

:::note
上記では、__`ai5`__ の __処理の中__ で __利用__ する、__値が変化__ する __変数__ を __すべて表示__ していますが、そのような __変数__ の __数が多い__ 場合は、__すべての変数__ を __表示__ すると、表示が多くなりすぎて __わかりづらく__ なります。そのような場合は、__バグの原因__ となる __可能性の高い__ 変数に __絞って表示__ すると良いでしょう。
:::

次に、改めて __`play`__ メソッドを __実行__ して、__`ai5`__ で行われた __処理の経過__ を __確認__ します。
```python
mb.play(ai=[ai5, ai2]);
```

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

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
move (0, 0)
Turn x
O..
...
...

status playing turn x
move (1, 0)
Turn o
oX.
...
...

status playing turn o
略
```

### 1 回目の繰り返し処理の調査

実行結果の __`legal_moves`__ の行の表示から、__9 つ__ の __すべてのマス__ が __合法手__ になっていることが __確認__ できます。__この部分__ には __問題はなさそう__ です。

下記は、__`ai5`__ の 4 行目の、__`for move in legal_moves:`__ の __1 回目__ の __繰り返し処理__ で __表示__ された __実行結果__ の抜粋です。__実行結果__ から、__以下の処理__ が行われたことが分かります。

* __合法手__ として __(0, 0)__ が __取り出され__、__(0, 0)__ のマスに __着手__ が行われる
* __(0, 0)__ に __〇 が配置__ される
* ゲームの __決着がついていない__ ので、__`mb.status`__ に __`"playing"`__ が __代入__ される
* __実行結果__ から、__`mb.turn`__ に __`"x"`__ が __代入__ される

```
move (0, 0)
Turn x
O..
...
...
status playing turn x
```

明らかに、__〇__ は __勝利しておらず__、実際に 10 行目の __`if mb.status == mb.turn:`__ の __条件式__ は __`False`__ になるので、この後で、__次__ の __合法手__ に対する __繰り返し処理__ が __実行__ されます。

実は、この時点で `ai5` の __処理__ には __バグがある__ ことがわかりますが、__初心者__ がそのことに __気づく__ ことは __難しい__ と思います。そのバグについては __この後__ で __判明__ することになるので、__現時点__ では __気づかなかったことにして__ 話を進めます。興味がある方は、どこにどのようなバグがあるかについて少し考えてみて下さい。

### 2 回目の繰り返し処理の調査

下記は、__`ai5`__ の 4 行目の、__`for move in legal_moves:`__ の __2 回目__ の __繰り返し処理__ で __表示__ された __実行結果__ の抜粋です。__実行結果__ から、__以下の処理__ が行われたことが分かります。

* __合法手__ として __(1, 0)__ が __取り出され__、__(1, 0)__ のマスに __着手__ が行われる
* __(1, 0)__ に __× が配置__ される
* ゲームの __決着がついていない__ ので、__`mb.status`__ に __`"playing"`__ が __代入__ される
* __実行結果__ から、__`mb.turn`__ に __`"o"`__ が __代入__ される

この __実行結果__ から、先程の __バグ__ のうちの __片方__ の __原因__ が何であるかがわかります。それが何であるかについて少し考えてみて下さい。

```
move (1, 0)
Turn o
oX.
...
...

status playing turn o
```

__合法手__ として、(0, 0) の次の __(1, 0)__ が __取り出される__ 点は __正しい__ のですが、ゲーム盤に __2 つ__ の __マークが配置__ される点が __間違って__ います。その __原因__ は、1 回目の繰り返し処理で、__(0, 0)__ のマスに __着手__ を __行った後__ で、__続けて__ 2 回目の繰り返し処理で __(1, 0)__ のマスに __着手__ を行っているからです。__この後__ で、このような __処理__ が __繰り返された結果__、__いきなり 8 つのマス__ に __着手__ が行われた __ゲーム盤が表示__ されるという __バグが発生__ することになります。

この __バグ__ を __解決__ するためには、__繰り返しのたび__ に、__ゲーム盤__ の __状態__ を、__`ai5`__ を __実行した時__ の状態に __戻す__ 必要があります。

__バグ__ の __一つ__ である「いきなり __8 つのマス__ に __着手__ が行われた __ゲーム盤が表示__ される」点の __原因が判明__ しましたが、「__( 1 , 2 ) のマスにはマークが配置済です__」という __エラーメッセージが表示__ される __原因__ がまだ __判明していない__ ので、引き続き __調査を続ける__ ことにします。

### 7 回目の繰り返し処理の調査

__3 ~ 6 回目__ の __繰り返しの処理__ の __実行結果__ を __調査__ した所、上記で発見した、__続けて__ マークが __配置__ される点を __除けば__、特に __不審な処理__ が行われている点は __見つけられませんでした__ ので、その説明は省略し、その次の繰り返し処理を調査します。

下記は、__`ai5`__ の 4 行目の、__`for move in legal_moves:`__ の __7 回目__ の __繰り返し処理__ で __表示__ された __実行結果__ の抜粋です。__実行結果__ から、__以下の処理__ が行われたことが分かります。

* __合法手__ として __(0, 2)__ が __取り出され__、__(0, 2)__ のマスに __着手__ が行われる
* __(0, 2)__ に __〇 が配置__ される
* __斜め方向__ に __〇__ が __配置__ されるので、__〇 が勝利__ し、__`mb.status`__ に __`"o"`__ が __代入__ される
* __実行結果__ から、__`mb.turn`__ に __`"x"`__ が __代入__ される

```実行結果
move (0, 2)
winner o
oxo
xox
O..

status o turn x
```

__〇 が勝利する__ ので、次の 10 行目の __`if mb.status == mb.turn:`__ の __条件式__ が __`True`__ になり、11 行目で __`ai5`__ の __返り値__ として __`move`__ に代入された __(0, 2)__ が __返されるはず__ です。しかし、__実際__ には、上記の __実行結果__ の __直後__ に、__move (1, 2)__ が __表示__ されることから、この __条件式__ が __`False`__ になり、次の __8 回目__ の __繰り返し処理__ が __開始__ されてしまうという __バグ__ が __発生__ することが __判明__ します。このようなバグが発生する理由について少し考えてみて下さい。

__`if mb.status == mb.turn:`__ の __条件式__ が __`False`__ になる __理由__ は、上記の __7 回目__ の __実行結果__ の __status o turn x__ からわかるように、__7 回目__ の __繰り返し処理__ によって、__`mb.turn`__ に __`x`__ が __代入__ されるからです。また、そのようなことが起きる __原因__ は、__`move`__ メソッドを __実行__ すると、__手番__ が __入れ替わってしまう__ ためです。従って、この __バグ__ は、__10 行目__ の if 文の __条件式__ で、__`mb.status`__ と __`mb.turn`__ を __比較__ するの __ではなく__、__`mb.status`__ と、__着手__ を __行う前__ の __`mb.turn`__ を __比較__ するようにすることで __修正__ することができます。

上記が、先ほどの「1 回目の繰り返し処理の調査」の最後で説明した、__初心者__ が __発見しづらいバグ__ です。なお、「__( 1 , 2 ) のマスにはマークが配置済です__」という __エラーメッセージが表示__ される __原因__ がまだ __判明していない__ ので、引き続き __調査を続ける__ ことにします。

### よくある論理の間違い

以下のような __考え方__ で、__修正__ するという方法を考えた方がいるかもしれません。

:::note alert
下記は __間違った__ 考え方なので、__背景を赤く__ しています。

* __〇× ゲーム__ で、__自分が勝利する__ ということは、__〇 の手番__ であっても、__× の手番__ であっても、ゲームの __決着がつく__ ということである
* __決着がついた場合__ は、__`mb.status` の値__ が __`Marubatsu.PLAYING`__ では __なくなる__
* 従って、10 行目を __`if mb.status != Marubatsu.PLAYING:`__ のように __修正__ することで __自分が勝利__ したことを __判定__ することができる
:::

実際に 10 行目を __`if mb.status != Marubatsu.PLAYING:`__ に __修正__ しても、プログラムは __正しく動作__ しますが、上記の __考え方__ は __間違っています__。何が間違っているか、そして __間違っている__ にもかかわらず __正しく動作する理由__ について、少し考えてみて下さい。

#### 間違いの理由

__アルゴリズム__ を __考える__ 時に、__よくある間違い__ が、上記のような __論理的__ な __勘違い__ です。__上記の考え方__ の場合は、__以下__ のような __論理__ で話を進めています。なお、下記の __A → B__ という表記は、__A が成り立つ場合__ は __B が成り立つ__ という、__A ならば B__ という __意味__ を表します。

1. __自分が勝利__ する → ゲームの __決着がつく__
2. ゲームの __決着がつく__ → __`mb.status`__ が __`Marubatsu.PLAYING`__ と __異なる値__ になる
3. 従って、__自分が勝利__ する → __`mb.status`__ が __`Marubatsu.PLAYING`__ と __異なる値__ になる
4. 従って、__`mb.status`__ が __`Marubatsu.PLAYING`__ と __異なる値__ になる → __自分が勝利__ する

上記の __1、2__ は __正しい論理__ です。また、__3__  は __論理学__ の __三段論法__ という __正しい論理__ です。

しかし、__A ならば B__ という __論理__ が __正しい場合__ でも、その __逆__ の __B ならば A__ は __正しいとは限らない__ ので __4__ は __間違った論理__ です。例えば、「大谷選手は野球選手である」は __正しい__ ですが、「野球選手は大谷選手である」は __正しい__ とは __限りません__。__慣れていても__、__逆が正しい__ という __間違った論理__ で __話を進める__ ことは __よくある__ ので、__気を付ける必要__ があります。

上記の __考え方__ で、具体的に __間違っている部分__ は、__自分の着手__ によって __決着がついた場合__ に、__自分が勝利__ しているとは __限らない__ という点です。具体的には、__最後のマス__ に __着手__ した際に、__引き分け__ になる場合があります。__10、11 行目__ の __処理__ の __意図__ は、着手することで __勝利__ する __合法手__ を __返す__ というものですが、10 行目を __`if mb.status != Marubatsu.PLAYING:`__ のように修正すると、__引き分け__ という、__勝利しない__  合法手を __返り値__ として __返す__ という、__本来の意図__ とは __異なる処理__ が行われてしまいまう __可能性__ が生じてしまいます。

なお、__A ならば B__ が __成り立つ__ 場合に、__対偶__ の __B でないならば A でない__ は __常に成り立ちます__。__逆__ や __対偶__ などの __関係__ は __論理学__ の __基礎__ で、__アルゴリズム__ を __正しく記述__ するための __必須の知識__ です。説明が長くなるので本記事でそれらの詳しい説明は行いませんが、不安な方はしっかりと勉強して __理解しておく__ ことを __強くお勧め__ します。

#### 間違っていても正しく動作する理由


__考え方__ が __間違っていても正しく動作__ する __理由__ は、以下の通りです。

* __本来の意図__ とは __異なる処理__ が行われるのは、__引き分け__ になる __場合だけ__ である
* __〇× ゲーム__ で __引き分けになる__ のは、__空いているマス__ が __1 つ__、すなわち __合法手__ が __1 つ__ しか存在しない __場合だけ__ である
* __合法手__ が __1 つ__ の場合は、__どのような AI__ であっても、__選択__ できる __合法手は同じ__ である。従って、__本来の意図__ とは __異なる処理__ が行われても、__選択__ される __合法手__ は __変わらない__

つまり、__本来の意図__ とは __異なる処理__ が行われているにもかかわらず、プログラムが __正しく動作__ す る __理由__ は、__〇×ゲームの性質__ が __たまたまそうなっている__ という、__偶然の結果__ に過ぎないということです。

ある程度プログラミングに上達した方が、上記の __正しく動作する理由__ をちゃんと __理解した上__ で、10 行目に __`if mb.status != Marubatsu.PLAYING:`__ を __記述__ するのは __問題はありません__ が、__初心者__ の方などで、__理由はよくわからない__ が、__うまくいく__ という __理由__ でそのように __記述__ するのは、後で __プログラムを修正__ する際などで __バグの原因__ に __なりやすい__ ので、__避けたほうが良い__ と思います。本記事ではこの記述は採用しません。

また、__正しく動作__ する __理由__ が __理解できている__ 場合でも、__複雑な論理__ で行われる __処理__ は __時間がたつ__ と __忘れてしまう可能性__ が __非常に高くなる__ ので、そのような場合は、__コメント__ を記述して、そのことを __説明しておいたほうが良い__ でしょう。

### 8 回目の繰り返し処理の調査

下記は、__`ai5`__ の 4 行目の、__`for move in legal_moves:`__ の __8 回目__ の __繰り返し処理__ で __表示__ された __実行結果__ の抜粋です。__実行結果__ から、__以下の処理__ が行われたことが分かります。

* __合法手__ として __(1, 2)__ が __取り出され__、__(１, 2)__ のマスに __着手__ が行われる
* __(1, 2)__ に __× が配置__ される
* 7 回目の繰り返し処理の結果、__斜め方向__ に __〇__ が既に __配置__ されているので、__〇 が勝利__ し、__`mb.status`__ に __`"o"`__ が __代入__ される
* __実行結果__ から、__`mb.turn`__ に __`"o"`__ が __代入__ される

```実行結果
move (1, 2)
winner o
oxo
xox
oX.

status o turn o
```

8 回目の繰り返しで、__(1, 2)__ のマスに __着手__ を行った 結果、__(1, 2)__ に __×__ のマークが __配置__ されます。__その結果__、__×__ が __勝利__ することは __ありません__ が、__7 回目__ の  __〇__  の __(0, 2)__ への __着手__ によって斜め方向に 〇 が並んでおり、__〇 が勝利__ しているため、__`mb.status`__ に __"o" が代入__ されます。また、8 回目の __× の着手__ が行われたので、__〇__ の __手番になる__ ので、__`mb.status`__ に __`o`__ が __代入__ されます。従って、10 行目の __`if mb.status == mb.turn:`__ の __条件式__ が __`True`__ になり、11 行目で __`ai5`__ の __返り値__ として、__`move`__ に代入された __(1, 2)__ が __返されます__。

__`play`__ メソッドは、__`ai5`__ の __返り値__ である __(1, 2)__ のマスに __着手__ を行いますが、上記の実行結果からわかるように、__(1, 2)__ のマスには、__`ai5`__ の __処理__ で __既に `x`__ が __配置済__ です。__そのため__、「( 1 , 2 ) のマスにはマークが配置済です」という __エラーメッセージが表示__ されます。

この __エラーメッセージ__ は、__`ai5`__ の __処理__ によって、__ゲーム盤__ に __合法手__ が __すべて着手__ されてしまうことが __原因__ なので、先程の「__繰り返しのたび__ に、__ゲーム盤__ の __状態__ を、__`ai5`__ を __実行した時__ の状態に __戻す__」という方法で __修正__ することが __できます__。

## バグの修正方法

上記の調査によって、__バグの原因__ と下記の __修正方法__ がわかりました。

* __繰り返しのたび__ に、__ゲーム盤__ の __状態__ を、__`ai5`__ を __実行した時__ の状態に __戻す__ 
* __if 文__ の __条件式__ で、__`mb.status`__ と __`mb.turn`__ を __比較__ するの __ではなく__、__`mb.status`__ と、__着手__ を __行う前__ の __`mb.turn`__ を __比較__ するようにする

まず、上記の __1 つ目__ の __修正__ を行うことにします。1 つ目の処理を行う __アルゴリズム__ は __いくつかあります__ が、今回の記事では、__データ__ を __コピー__（複製）する、以下のようなアルゴリズムを紹介します。他のアルゴリズムについては、今後の記事で紹介する予定です。

1. __`move`__ メソッドで __着手を行う前__ に、__`mb`__ を __コピーしたデータ__ を __作成__ する
2. __複製したデータ__ に対して __`move`__ メソッドで __着手__ を行う

__`ai5`__ の __仮引数__ である __`mb` に__ 対して __着手__ を行うの __ではなく__、__繰り返しのたびに__、__`mb`__ を __コピー__ し、__コピーしたデータに__ 対して __着手__ を行うことで、__繰り返しのたび__ に、__ゲーム盤__ の __状態__ を、__`ai5`__ を __実行した時__ の状態に __戻す__ ことができます。

上記の処理を行うためには、__データ__ を __コピー__ する必要がありますが、__データ__ の __コピー__ には __2 種類__ があり、正しく __使い分ける必要__ があるので、そのことを説明します。

## データのコピー（複製）と copy モジュール

[以前の記事](https://qiita.com/ysgeso/items/cc9e67c16b0814c8bc2e#%E3%81%BE%E3%81%A8%E3%82%81) で説明したように Python の __代入文__ は、__データ__ を __共有__ するという __処理__ を行うので、__1 つの代入文だけ__ で __list__ や __dict__ などの [__複合データ型__](https://qiita.com/ysgeso/items/9efd60c7a28381e6cbf7#%E8%A4%87%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B%E3%81%AE%E5%AE%9A%E7%BE%A9) の __データ__ の __コピー__ を __行う__ ことは __できません__。忘れた方は、[以前の記事](https://qiita.com/ysgeso/items/c6d4a2da7b8118a5a143#%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0-a-%E3%81%A8-b-%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81) の __プログラム A と B__ について __復習__ して下さい。

:::note
[疑似的な複製](https://qiita.com/ysgeso/items/cc9e67c16b0814c8bc2e#%E7%96%91%E4%BC%BC%E7%9A%84%E3%81%AA%E8%A4%87%E8%A3%BD%E3%81%AE%E5%AE%9A%E7%BE%A9) が行われる __数値型__、__文字列型__、__論理型__ などのデータは、__1 つの代入文だけ__ で __コピー__（複製） と __同等の処理__ を行うことができます。
:::

__データ__ の __コピーの処理__ を __自分で記述__ することは __可能__ ですが、Python には __データ__ を __コピー__ するための __copy__ という __モジュール__ があるので、それを利用すると良いでしょう。

__copy モジュール__ には __浅いコピー__ を行う __`copy`__ と __深い（deep）コピー__ を行う __`deepcopy`__ という __関数__ が __定義__ されており、__状況に応じて__ 適切に __使い分ける必要__ があります。

copy モジュールの詳細については、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/copy.html?highlight=copy#module-copy

### 「複合オブジェクト」と「複合データ型」の用語の統一

上記のリンク先では、「__複合オブジェクト__」は、以下のように説明されています。

「リストやクラスインスタンスのような __他のオブジェクト__ を __含むオブジェクト__」

これは、[以前の記事](https://qiita.com/ysgeso/items/9efd60c7a28381e6cbf7#%E8%A4%87%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B%E3%81%AE%E5%AE%9A%E7%BE%A9) で下記のように定義した「__複合データ型__」と __意図__ は __ほぼ同じ__ です。

「Python の __任意のデータ型__ を、__複数組み合わせて__ データを表現する __データ型__」

以前の記事を執筆した際には、「複合オブジェクト」という用語を見つけられなかったので、「複合データ型」という用語を定義して使いましたが、本家のドキュメントに __同じ意図__ の __用語__ があることが今回わかったので、__以後__ は「__複合オブジェクト__」の方を __使用__ します。
### 浅いコピー

上記のリンク先では、__copy モジュール__ の、__`copy`__ という名前の __関数__ が行う、__浅いコピー__ という __処理__ は、__下記__ のように __説明__ されています。

「__浅いコピー__（shallow copy）は __新たな複合オブジェクト__ を __作成__ し、その後（可能な限り）__元のオブジェクト中__ に見つかった __オブジェクト__ に対する __参照__ を __挿入__ します」

__`copy`__ による __浅いコピー__ で行われる __処理__ の __ポイント__ は以下の通りです。

* __見た目__ は __コピー元__ と __同じデータ__ が作成される
* __任意__ の __データ型__ のデータを __コピーできる__
    * __オブジェクト__ の場合は、__コピー元__ と __同じ属性__ を持つ __オブジェクト__ が __作成__ される
    * __list__ の場合は、__コピー元__ と __同じ要素__ を持つ __list__ が __作成__ される
    * __dict__ の場合は、__コピー元__ と __同じキーの値__ を持つ __dict__ が __作成__ される
* ただし、__浅いコピー__ で __コピー__ された __データ__ の __属性__（__要素__、__キーの値__）は、__複製__ されるの __ではなく__、__代入文__ と __同様の方法__ で __共有__ される

上記の性質の中の、__3 つ目__ の __性質__ が __非常に重要__ なので、具体例を挙げて説明します。その際に、__dict__ で説明すると __わかりやすい__ と思いましたので、__dict__ で __説明__ します。

#### 浅いコピーで行われる処理

__実引数__ に __記述__ した __dict__ の __浅いコピー__ を __作成__ して __返す関数__ を __自分で記述__ する場合は、下記のようなプログラムになります[^1]。

* __1 行目__：__コピー元__ の __dict__ を __代入__ する __仮引数__ の __名前__ を __`data`__[^2] とする 
* __2 行目__：__`data`__ の __浅いコピー__ を __代入__ する __`new_dict`__ を __空の dict__ で __初期化__ する
* __3 行目__：__`items` メソッド__ を使って、__`data`__ の __キー__ と __キーの値__ を __順番に取り出して__、__`key`__ と __`value`__ に __代入__ するという __for 文__ による __繰り返し処理__ を行う
* __4 行目__：__`new_dict`__ の __`key`__ という __キーの値__ に __`value`__ を __代入__ することで、__`data`__ と __`new_dict`__ の __同じ名前__ の __キー__ が、__同じデータ__ を __共有__ するようにする
* __5 行目__：__`data`__ の __浅いコピー__ が __代入__ された __`new_dict`__ を __返り値__ として __返す__

```python
def copy_dict(data):
    new_dict = {}
    for key, value in data.items():
        new_dict[key] = value
    return new_dict
```

下記のプログラムは、__dict__ が代入された __`a`__ を __`copy_dict`__ を使って __浅いコピー__ を行い、__`b` に代入__ しています。その結果、__3、4 行目__ では、__`a`__ と __`b`__  で __同じ表示__ が行われます。

```python
a = { "c": 1, "d": [2, 3] }
b = copy_dict(a)
print(a)
print(b)
```

実行結果

```
{'c': 1, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]}
```

次に、下記のプログラムの 1 行目で、__`b["c"]`__ に __`5`__ を __代入__ しても、実行結果から、__`a["c"]`__ の __値__ は __変化しない__ ので、__`a`__ と __`b`__ の __値__ は __独立__ しているように __見えるかもしれません__。

```python
b["c"] = 5
print(a)
print(b)
```

実行結果

```
{'c': 1, 'd': [2, 3]}
{'c': 5, 'd': [2, 3]}
```


しかし、下記のプログラムの 1 行目で __`b["d"][0]`__ に __`6`__ を __代入__ すると、実行結果のように __`a["d"][0]`__ の __値__ も __`6`__ に __変化__ してしまいます。これは、先ほど説明したように、__`a["d"]`__ と __`b["d"]`__ が、__同じデータ__ を __共有__ しているからです。この __現象__ の __原因__ は、[以前の記事](https://qiita.com/ysgeso/items/c6d4a2da7b8118a5a143#%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0-a-%E3%81%A8-b-%E3%81%AE%E5%87%A6%E7%90%86%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)で説明した __プログラム A と B__ の __違い__ と __同様__ です。

```python
b["d"][0] = 6
print(a)
print(b)
```

実行結果

```
{'c': 1, 'd': [6, 3]}
{'c': 5, 'd': [6, 3]}
```

#### 浅いコピーによってコピーされた場合の図

下図の __左__ は、__浅いコピー__ が行われた __直後__ の __`a`__ と __`b`__ を、下図の __右__ は、その後で __`b["c"] = 5`__ と __`b["d"][0] = 6`__ を __実行__ した __直後__ の __`a`__ と __`b`__ の __状態__ を表しています。

![75.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86424950-63a6-78d2-da7f-c1ab4b83ba66.png)

#### `copy` 関数による浅いコピー

この __性質__ は、下記のプログラムのように、自作の `copy_dict` の代わりに、__copy モジュール__ の __`copy` 関数__ を __利用__ しても __同様__ です。なお、__`copy_dict`__ と __`copy`__ の __違い__ は、__`copy_dict`__ が __dict のみ__ を __コピーできる__ のに対し、__`copy`__ は __任意のデータ__ を __コピーできる__ 点です。

```python
from copy import copy

a = { "c": 1, "d": [2, 3] }
b = copy(a)
print(a, b)
b["c"] = 5
print(a, b)
b["d"][0] = 6
print(a, b)
```

実行結果

```
{'c': 1, 'd': [2, 3]} {'c': 1, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]} {'c': 5, 'd': [2, 3]}
{'c': 1, 'd': [6, 3]} {'c': 5, 'd': [6, 3]}
```

#### 浅いコピーの性質

上記のことから、__list__、__dict__、__オブジェクト__ などの、__複合オブジェクト__ を __浅いコピー__ で __コピー__ した場合は、以下の点に注意する必要があります。

:::note warn
* __すべて__ の __属性の値__（__要素__、__キーの値__）に、__疑似的な複製__ が行われる __データ__ が __代入__ されている __場合__ は、__データ__ が __完全にコピー__ されたと __みなしても良い__
* __疑似的な複製__ が __行われない__ データが __代入__ されている __属性の値__（__要素__、__キーの値__）は __複製__ されず、__コピー元__ のデータと __共有__ が行われる
:::

#### `Marubatsu` クラスのインスタンスの浅いコピー

__`copy`__ によって、下記のプログラムの 2 行目のように、__`Marubatsu`__ クラスの __インスタンス__ である __`mb`__ のような __オブジェクト__ に対する __浅いコピー__ を __行う__ ことが __できます__。そのため、3、4　行目のように、__コピー元__ の __`mb`__ と、__浅いコピー__ が行われた __`mb2`__ の __ゲーム盤__ を __表示__ すると __同じ内容__ が __表示__ されます。

```python
mb = Marubatsu()
mb2 = copy(mb)
print(mb)
print(mb2)
```

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

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

しかし、__`mb.board`__ と __`mb2.board`__ は __同じ__ 2 次元配列を表す __list__ を __共有__ するので、下記のプログラムのように、__`move`__ メソッドを使って __`mb`__ のゲーム盤の __(0, 0)__ のマスに __着手__ を行うと、下記の実行結果のように、__`mb2`__ のゲーム盤の __(0, 0)__ にも __着手__ が行われてしまいます。

そのため、__`ai5`__ で __`mb`__ を __コピー__ して、__同じ内容__ だが、__独立__ した __ゲーム盤__ を持つ __データ__ を __作成__ するという __目的__ で __`copy`__ を __利用__ することは __できません__。

```python
mb.move(0, 0)
print(mb)
print(mb2)
```

実行結果
```
Turn x
O..
...
...

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

なお、上記の実行結果で、__`mb`__ のゲーム盤には __turn x__ が、__`mb2`__ のゲーム盤には __turn o__ が __表示__ される __理由__ は、__`mb.turn`__ と __`mb2.turn`__ には __疑似的な複製__ が行われる __文字列型__ のデータが __代入__ されているので、__`mb.turn`__ の値を __変更__ しても、__`mb2.turn`__ は __変化しない__ からです。

### 深いコピー

__複合オブジェクト__ を __コピー__ する際に、__共有__ を一切 __行わず__ に、__すべて__ の __属性__（__要素__、__キーの値__）を __コピー__ する __処理__ の事を __深い（deep）コピー__、または __完全なコピー__ と呼びます。__深いコピー__ は、__copy モジュール__ の、__`deepcopy`__ という名前の __関数__ で行うことができます。

なお、__深いコピー__ が __行う処理__ は、これまでの記事で説明していない __再起呼び出し__ という __記述__ が __必要__ となるので、具体的なプログラムは紹介しません。再起呼び出しについては必要になった時点で紹介します。

下記は、先程のプログラムの __`copy`__ を __`deepcopy`__ に変えて、__深いコピー__ を __行う__ ようにしたものです。実行結果から、__`b["c"][0]`__ に __`6`__ を __代入__ しても、__`a["c"][0]"`__ の __値__ が __変化しない__ ので、__`b`__ は __`a`__ を __完全にコピー__ した、__`a`__  とは __独立したデータ__ であることが __確認__ できます。

```python
1  from copy import deepcopy
2
3  a = { "c": 1, "d": [2, 3] }
4  b = deepcopy(a)
5  print(a, b)
6  b["c"] = 5
7  print(a, b)
8  b["d"][0] = 6
9  print(a, b)
```

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

```python
from copy import deepcopy

a = { "c": 1, "d": [2, 3] }
b = deepcopy(a)
print(a, b)
b["c"] = 5
print(a, b)
b["d"][0] = 6
print(a, b)
```
</details>

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

```diff_python
-from copy import copy
+from copy import deepcopy

a = { "c": 1, "d": [2, 3] }
-b = copy(a)
+b = deepcopy(a)
print(a, b)
b["c"] = 5
print(a, b)
b["d"][0] = 6
print(a, b)
```
</details>


実行結果

```
{'c': 1, 'd': [2, 3]} {'c': 1, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]} {'c': 5, 'd': [2, 3]}
{'c': 1, 'd': [2, 3]} {'c': 5, 'd': [6, 3]}
```

下図は、上記のプログラムで __深いコピー__ を __行った直後__ の状況を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/4829b46a-b17b-7eb9-1053-e241aa681890.png" width="400"><br>

下図は、__`b["c"] = 5`__ と __`b["d"][0] = 6`__ を実行した __直後__ の状況を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1d1c7728-3f06-fd38-4e7d-0af36d40b5bd.png" width="400">

### 深いコピーによる `mb` のコピー

__`deepcopy`__ を利用することで、下記のプログラムのように、ゲーム盤のデータを代入する __`board` 属性__ を __含め__、__`mb`__ が __管理__ する __すべての属性__ を __完全にコピー__ することができます。下記の __6、7 行目__ のプログラムの実行結果の __表示__ からわかるように、先ほどと異なり、__`mb`__ に対して __(0, 0)__ に __着手__ を行っても、__`mb2`__ で __着手__ は __行われません__。

```python
1  mb = Marubatsu()
2  mb2 = deepcopy(mb)
3  print(mb)
4  print(mb2)
5  mb.move(0, 0)
6  print(mb)
7  print(mb2)
```

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

```python
mb = Marubatsu()
mb2 = deepcopy(mb)
print(mb)
print(mb2)
mb.move(0, 0)
print(mb)
print(mb2)
```
</details>

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

```diff_python
mb = Marubatsu()
-mb2 = copy(mb)
+mb2 = deepcopy(mb)
print(mb)
print(mb2)
mb.move(0, 0)
print(mb)
print(mb2)
```
</details>


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

Turn o
...
...
...

Turn x
O..
...
...

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

### 浅いコピーと深いコピーの使い分け

どのような場合でも深いコピーを使えば良いと思う人がいるかもしれませんが、__深いコピー__ には、下記のような __欠点__ があるので、__状況に応じて使い分ける必要__ があります。

1. コピーする __データ__ の __サイズ__ が __大きい__ 場合は、__浅いコピー__ と __比較__ して __時間がかかる__
2. __コピー元__ と __同じ大きさ__ の __データ__ が __新しく作られる__ ため、コピーする __データ__ の __サイズ__ が __大きい__ 場合は __コンピューター__ の __メモリ__ がその分だけ __必要__ になる
3. __コピー元__ と __コピー先__ で、__一部の属性__ を __共有したい__ 場合は __利用できない__

上記の 1、2 から __浅いコピー__ の方が、__処理の時間__ が __短く__、必要な __メモリの量__ も __少ない__ ので、__浅いコピー__ で __十分な場合__ は __浅いコピー__ を __使ったほうが良い__ でしょう。

上記の 3 から、__コピー元__ のデータと、__コピー先__ のデータの間で、__一部の属性__ を __共有したい__ 場合などでは、深いコピーではなく、__浅いコピー__ を __利用する必要__ があります。

__慣れないうち__ は、__浅いコピー__ と __深いコピー__ の __使い分け__ が __わかりづらい__ と思いますので、本記事では __データ__ を __コピーする際__ には、__どちらを使うべきか__ について __説明__ します。

## `ai5` の修正

下記は、`ai5` のバグの __修正方法__ を __再掲__ したものです。

* __繰り返しのたび__ に、__ゲーム盤__ の __状態__ を、__`ai5`__ を __実行した時__ の状態に __戻す__ 
* __if 文__ の __条件式__ で、__`mb.status`__ と __`mb.turn`__ を __比較__ するの __ではなく__、__`mb.status`__ と、__着手__ を __行う前__ の __`mb.turn`__ を __比較__ するようにする

__1 つ目__ の修正を行うためには、__ゲーム盤__ を __完全にコピー__ するために、__`deepcopy`__ を使って __深いコピー__ を行う __必要__ があります。

__2 つ目__ の修正で必要となる、__着手__ を __行う前__ の __手番__ のデータは、__コピー元__ の __データ__ の __`turn` 属性__ に代入されています。

従って、__`ai5`__ は、下記のプログラムのように __修正__ することができます。なお、先程 __デバッグ表示__ のために __挿入__ した __`print`__ は __削除__ しました。

* __1、2 行目__：__元__（original）の __`mb`__ であることを __表す__ ようにするために、__仮引数__ の __名前__ を __`mb_orig`__ に __修正__ し、__2 行目__ の __`mb`__ を __`mb_orig`__ に __修正__ する
* __4 行目__：__`deepcopy`__ を使って、__`mb_orig`__ の __深いコピー__ を __作成__ し、__`mb`__ に __代入__ する
* __7 行目__：__`mb.status`__ は、__着手を行う前__ の __手番__ と __比較__ する __必要__ があるので、__`mb.turn`__ を、__着手前__ の __手番__ を表す __`mb_orig.turn`__ に __修正__ する

```python
1  def ai5(mb_orig):
2      legal_moves = mb_orig.calc_legal_moves()
3      for move in legal_moves:
4          mb = deepcopy(mb_orig)
5          x, y = move
6          mb.move(x, y)
7          if mb.status == mb_orig.turn:
8              return move
9      return choice(legal_moves)
```

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

```python
def ai5(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if mb.status == mb_orig.turn:
            return move
    return choice(legal_moves)
```
</details>

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

```diff_python
-def ai5(mb):
+def ai5(mb_orig):
-   legal_moves = mb.calc_legal_moves()
+   legal_moves = mb_orig.calc_legal_moves()
    for move in legal_moves:
+       mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
-       if mb.status == mb.turn:
+       if mb.status == mb_orig.turn:
            return move
    return choice(legal_moves)
```
</details>


改めて __`play`__ メソッドを __実行__ して、__`ai5`__ の __処理__ を __確認__ します。実行結果から、__〇__ の __4 回目__ で、__勝利できる (1, 1)__ の __着手を行う__ ことが __確認__ できます。実行結果は __ランダム__ なので、不安な方は、__何度か実行__ して、__意図した処理が行われる__ ことを __確認__ して下さい。

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

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

Turn x
...
...
.O.

Turn o
...
...
.oX

Turn x
...
...
Oox

Turn o
.X.
...
oox

Turn x
.xO
...
oox

Turn o
Xxo
...
oox

winner o
xxo
.O.
oox
```

## `ai2` との対戦

__`ai5`__ が __実装__ できたので、下記のプログラムで、__基準__ となる __`ai2`__ と __対戦__ します。なお、__筆者のパソコン__ では、10000 回の対戦を行うと、__約 16 秒__ かかりました。あまり __時間がかかる__ ようであれば、__対戦の回数__ を __減らして__ ください。

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

実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
ai5 VS ai2
count     win    lose    draw
o        8133    1189     678
x        5218    3937     845
total   13351    5126    1523

ratio     win    lose    draw
o       81.3%   11.9%    6.8%
x       52.2%   39.4%    8.5%
total   66.8%   25.6%    7.6%
```

下記は、上記の結果を __基準__ となる __`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`__  | __81.3__ | __11.9__ | 6.8 | __52.2__ | __39.4__ | 8.5 | __66.8__ | __25.6__ | 7.6 | |

表から、__`ai5`__ は、__`ai2` に__ 対して、__`ai4` より__ は __若干弱い__ が、__`ai1` より__ も __強い__ AI であることが __わかります__。また、ルール 3 の説明をした際の、__`ai5`__ は __`ai2` より__ も __必ず強くなる__ という __考察__ が __正しいこと__ が、__対戦の結果__ から __確認__ できました。

## `ai3` と `ai4` との対戦

これまでに作成した __`ai3`__、__`ai4`__ と __対戦__ して、__強さを比較__ することにします。

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

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

```
ai5 VS ai3
count     win    lose    draw
o        7240    1989     771
x        3936    5282     782
total   11176    7271    1553

ratio     win    lose    draw
o       72.4%   19.9%    7.7%
x       39.4%   52.8%    7.8%
total   55.9%   36.4%    7.8%
```

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

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

```
ai5 VS ai4
count     win    lose    draw
o        6050    3663     287
x        2718    7073     209
total    8768   10736     496

ratio     win    lose    draw
o       60.5%   36.6%    2.9%
x       27.2%   70.7%    2.1%
total   43.8%   53.7%    2.5%
```

下記は、上記の結果に __`ai4` VS `ai3`__ を加えたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai5` VS `ai3`__  | 72.4 | 19.9 | 7.7 | 39.4 | 52.8 | 7.8 | 55.9 | 36.4 | 7.8 |
| __`ai4` VS `ai3`__  | 83.1 | 9.4 | 7.4 | 27.4 | 70.1 | 2.5 | 55.2 | 39.8  | 5.0 |
| __`ai5` VS `ai4`__  | 60.5 | 36.6 | 2.9 | 27.2 | 70.7 | 2.1 | 43.8 | 53.7 | 2.5 |

### __`ai5` VS `ai3`__ と __`ai4` VS `ai3`__ による考察

上記の __`ai5` VS `ai3`__ と __`ai4` VS `ai3`__ の結果から、以下のような __考察__ を行いました。

* __`ai5` VS `ai3`__ の __通算成績__ では、__`ai5`__ の __勝率__ が __55.9%__、__敗率__ が __36.4%__ となっているため、__`ai5`__ は、__`ai3` に__ 対して __かなり強そう__ である
* __`ai4` VS `ai3`__ の __通算成績__ と __ほぼ同じ成績__ なので、__`ai3` に__ 対しては、__`ai4` と `ai5`__ は __ほぼ同じ強さ__ を持つ
* __`ai5` VS `ai3`__ は、__`ai4` VS `ai3`__ の場合と __異なり__、__× の手番__ を __担当__ する際に、__極端に弱い__ ということは __ない__ ので、__`ai5`__ には、__`ai4`__ のような __欠陥__ は __ない__

従って、__`ai5`__ は __`ai3` に__ 対して、__`ai4`__ と __同等の強さ__ を持ち、なおかつ __`ai4`__ のような __欠陥__ を __持たない__ ことがわかり、__ルール 5__ の __効果が大きい__ ことが考察できます。

:::note
__上記__ の考察は、__筆者の考察__ に __すぎない__ ので、__他の観点__ から __別の考察__ を行うことも __可能__ です。興味がある方は、別の観点から考察を行ってみて下さい。
:::

### __`ai5` VS `ai4`__ と __`ai2` VS `ai2`__ による考察

次に、__`ai5` VS `ai4`__ との __対戦結果__ を考察します。

__通算成績__ は __`ai4`__ のほうが __良い__ ので、__ルール 5__ は、__ルール 4__ に対して __相性が悪い__ ことがわかります。ただし、__〇 を担当__ した場合は __強い__ が、__× を担当__ した場合は __弱い__ ような、__担当__ した __マーク__ によって __強さ__ が __大きく異なる場合__ があるので、__通算成績__ だけでなく、__〇 を担当__ した場合と、__× を担当__ した場合の __それぞれの成績__ に対する考察が必要です。

__〇×ゲーム__ は、__〇 を担当__ したほうが __有利__ なゲームなので、__`ai5`__ が __〇 や × を担当__ した場合の __結果だけ__ を見ても、その __成績が良いか__ どうかを __判断できない__ ので、それらの __成績__ を __評価__ するためには、__何らかの指標__ が必要になります。

例えば、__テストの点数__ で __90 点__ を取った場合に、__平均点__ が __50 点__ の場合と、__95 点__ の場合で、その点が __良い点__ であるかどうか __評価__ が __大きく変わり__ ます。

そこで、テストの平均点のような __指標__ として、__ランダムな着手__ を行う __`ai2` VS `ai2`__ の __〇 を担当__ した場合の __成績__ と、__× を担当__ した場合の __成績__ を __利用する__ ことにします。もちろん、この指標が 〇× ゲームの __本当__ の 〇 と × の __有利さ__ を表している __保証はありません__ が、__現時点__ では他に __有力な指標__ が __ない__ ので、今回の記事ではこの指標を使うことにします。

例えば、ある __AI__ が __〇 を担当__ した際の __成績__ が、__`ai2` VS `ai2`__ で、__`ai2`__ が __〇 を担当__ した際の __成績__ よりも __良ければ__、__その AI__ は、__対戦相手の AI__ に対して、__〇 を担当__ した場合の __相性__ が __通常より__ も __良い__ と __判断__ することにします。

下記は、__`ai5` VS `ai4`__ と __`ai2` VS `ai2`__ の成績を表にしたものです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai5` VS `ai4`__  | 60.5 | 36.6 | 2.9 | 27.2 | 70.7 | 2.1 | 43.8 | 53.7 | 2.5 |
| __`ai2` VS `ai2`__  | 58.7 | 28.8 | 12.6 | 29.1 | 58.6 | 12.3 | 43.9 | 43.7 | 12.5 |

上記の表から、__`ai5` VS `ai4`__ について、以下のような __考察__ を行いました。

* __`ai5`__ が __〇 を担当__ した場合の __成績__ と __指標__ となる成績は、__勝率__ は __`60.5%`__ と __`58.7%`__ で __2%__ ほど __高い__ が、__敗率__ も __`36.6%`__ と __`28.8%`__ で __8 %__ ほど __高い__。従って、__総合的__ にみると、__指標より__ も __成績__ が __少し悪い__ と __考察__ できる
* __`ai5`__ が __× を担当__ した場合の __成績__ と __指標__ となる成績は、__勝率__ は __1.9% 低く__、__敗率__ は __12.1% も高い__。従って、__通常より__ も __成績が悪い__ と __考察__ できる

上記から、__通算成績だけでなく__、__〇 を担当__ した場合も、__× を担当__ した場合も、__`ai5`__ は __`ai4` に__ 対して __通常より__ も __相性が悪い__ ことが __考察__ できました。また、__× を担当__ した場合の方が __〇 を担当__ した場合 __より__ も __相性__ がさらに __悪い__ ということも __考察__ できます。

# 今回の記事のまとめ

今回は、以下の表のようなアルゴリズムの __`ai5`__ を実装し、__他の AI__ と __対戦__ することで、__`ai5`__ の __強さ__ を __検証__ しました。また、__`ai5`__ を __実装__ するために __必要__ な、__浅いコピー__ と __深いコピー__ について説明しました。


| 関数名 | アルゴリズム |
|:-:|:--|
| __`ai5`__  | 勝てる場合に勝つ<br>そうでない場合は __ランダム__ なマスに __着手__ する |


__`ai5`__ は __`ai4` に__ 対しては __弱い__ ですが、__`ai4` VS `ai3`__ の場合と __異なり__、__どちらの手番__ でも __`ai3` に__ 対して __強く__、__`ai4`__ のような __欠陥__ を __持たない__ ことが __確認__ できました。

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

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

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

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

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

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

# 次回の記事

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

[^1]:このプログラムは、まだ説明していない __dict 内包表記__ で記述することができますが、__浅いコピー__ の中で __代入処理__ が行われることを __明確__ にするために、わざと __dict 内包表記__ を __使わない方法__ で __記述__ しています。dict 内包表記については、今後の記事で説明する予定です
[^2]:__`dict`__ という __名前__ は、__組み込み関数__ として __使われている__ ので、__仮引数の名前__ を __`data`__ にしました