Pythonで〇×ゲームのAIを一から作成する　その51　〇×ゲームに勝つための条件

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48

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

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

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

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

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

これまでに作成した AI の アルゴリズム は以下の通りです。今回の記事から、左の列を「関数名」から「ルール」に変更しました。

| ルール | アルゴリズム |
|:-:|:--|
| __[ルール1](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#%E6%9C%80%E5%88%9D%E3%81%AB%E8%A6%8B%E3%81%A4%E3%81%8B%E3%81%A3%E3%81%9F%E7%A9%BA%E3%81%84%E3%81%A6%E3%81%84%E3%82%8B%E3%83%9E%E3%82%B9%E3%81%AB%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai)__  | __左上から順__ に __空いているマス__ を探し、__最初に見つかったマス__ に __着手__ する |
| __[ルール2](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA%E3%83%9E%E3%82%B9%E3%81%AB%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai)__  | __ランダム__ なマスに __着手__ する |
| __[ルール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)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | |
| __[ルール4](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>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | あり |
| __[ルール5](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>そうでない場合は __ランダム__ なマスに __着手__ する | |
| __[ルール6](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-6%E7%9B%B8%E6%89%8B%E3%81%AE%E5%8B%9D%E5%88%A9%E3%82%92%E9%98%BB%E6%AD%A2%E3%81%99%E3%82%8B)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __相手の勝利__ を __阻止__ する<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール6改](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#%E3%83%AB%E3%83%BC%E3%83%AB-6-%E6%94%B9%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール7](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手の勝利__ を __阻止__ する<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール7改](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-%E3%83%AB%E3%83%BC%E3%83%AB-7-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<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)__<br>__[`ai1s`](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#ai1s-%E3%81%AE%E4%BF%AE%E6%AD%A3)__  | __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)__<br>__[`ai2s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F%E3%83%AB%E3%83%BC%E3%83%AB-2-%E3%81%A7%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%86-ai-%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)__<br>__[`ai3s`](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E9%96%A2%E6%95%B0)__  | __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)__<br>__[`ai4s`](https://qiita.com/ysgeso/items/3afe5630d7e615a28ebf#ai4s-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E5%8B%95%E4%BD%9C%E3%81%AE%E7%A2%BA%E8%AA%8D)__  | __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)__<br>__[`ai5s`](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#ai5s-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __81.2__ | __12.3__ | 6.5 | __51.8__ | __39.8__ | 8.4 | __66.5__ | __26.0__ | 7.4 | |
| __[`ai6`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-6%E7%9B%B8%E6%89%8B%E3%81%AE%E5%8B%9D%E5%88%A9%E3%82%92%E9%98%BB%E6%AD%A2%E3%81%99%E3%82%8B)__  | __88.9__ | __2.2__ | 8.9 | __70.3__ | __6.2__ | 23.5 | __79.6__ | __4.2__ | 16.2 |
| __[`ai6s`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-6%E7%9B%B8%E6%89%8B%E3%81%AE%E5%8B%9D%E5%88%A9%E3%82%92%E9%98%BB%E6%AD%A2%E3%81%99%E3%82%8B)__  |   __88.6__ | __1.9__ | 9.5 | __69.4__ | __9.1__ | 21.5 | __79.0__ | __5.5__ | 15.5 |
| __[`ai7`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__<br>__[`ai7s`](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#ai7s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__ | __95.8__ | __0.2__ | 4.0 | __82.3__ | __2.4__ | 15.3 | __89.0__ | __1.3__ | 9.7 |

# 〇×ゲームに勝つ方法の考察の必要性

[以前の記事](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai-%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明したように、__ルールベース__ の AI は、「__解決すべき問題__ に対する、__人間の知識__ を __ルール化__ し、その __ルールに基づいて__ AI が __判断を行う__」という AI です。

従って、__ルールベース__ で __強い AI__ を __作成__ するためには、__〇×ゲーム__ に関する __深い知識__ が必要になります。__ルール 5__ の「__勝てる場合に勝つ__」と、__ルール 6__ の「__相手の勝利を阻止する__」は、〇×ゲームを少し遊べば __誰でも思いつく__ ルールだと思いますが、__それ以上に強い AI__ を作成するためには、__より深い__ 〇×ゲームの __知識が必要__ になります。

今回の記事から、__〇×ゲーム__ に __勝つ方法__ を __考察__ し、その __考察に基づいた__ AI を __作成__ します。〇×ゲームがあまり強くない人は、〇×ゲームに __勝つ方法__ について考えてみて下さい。また、〇×ゲームがある程度強い人は、その __方法__ を __ルール化__ して下さい。

# 勝利するために必要な条件

ゲームに __強くなるため__ に __必要__ な __最低限__ の __考察__ として、以下のようなものが挙げらるでしょう。そこで、まず、〇×ゲームで __勝つため__ に __必要な条件__ について __考察__ することにします。どのような条件が必要であるかについて少し考えてみて下さい。

* ゲームに __勝つため__ の __条件__
* ゲームに __負けないため__ の __条件__

〇×ゲームは、__以下__ の __性質__ を持つゲームです。

1. __交互__ に __空いているマス__ に __自分のマーク__ を __配置__ する
2. 一度 __マークが配置__ された __マス__ は、ゲーム終了まで __変化しない__
3. __8 種類__ ある __直線上の 3 マス__ の __いずれか__ に、__自分のマーク__ が __3 つ並ぶ__ と __勝利__ する

上記の __性質 3__ から、__自分__ が __勝利できる__ 局面は、__いずれか__ の __直線上の 3 マス__ が、__以下の状態__ になっている __必要がある__ ことがわかります。

* __自分のマーク__ が __2 つ配置__ されている
* __空いているマス__ が __1 つある__

:::note warn
__直線上の 3 つのマス__ の __配置の状態__ を __簡潔に表現__ するために、以後は、「直線上の 3 マスに、__自分のマーク__ が __x 個__、__相手のマーク__ が __y 個__、__空いている__ マスが __z 個__ ある」ことを、「__自 x 敵 y 空 z__」 のように __表記__ することにしま

例えば、上記の場合は、「__自 2 敵 0 空 1__」と __表記__ します。
:::

上記の考察から、以下の事が分かります。

:::note warn
__〇×ゲーム__ に __勝つため__ には、__自分の手番__ で __着手__ を行った __結果__、「__自 2 敵 0 空 1__」が 1 つ以上 __存在する__ 局面になる着手を行う __必要__ がある。
:::

:::note
〇×ゲームは、__直線上__ の __マスの数__ が常に __3__ なので、「__自 x 敵 y 空 z__」の __x__、__y__、__z__ には、$x + y + z = 3$ という関係があります。これは、__x__、__y__、__z__ のうち、__2 つの値__ が __決まる__ と、__残り__ の 1 つの __値__ が __自動的に決まる__ ということを表します。従って、「__自 x 敵 y 空 z__」は、その中の __いずれか 1 つを削除__ して「__自 x 敵 y__」のように __記述__ しても __かまいません__ が、本記事では __わかりやすさ__ を重視して __3 つ__ を __すべて記述__ することにします。

余談ですが、__複数__ の __変数__ のうち、__自由（独立に）に変更__ できる __変数__ の __数__ の事を __自由度__ と呼びます。「__自 x 敵 y 空 z__」の場合の自由度は __2__ です。

また、__`count_marks`__ の処理を、いずれかの __2 つの数__ だけを __数える__ ように __修正__ することも __可能__ ですが、そのように修正するとかえって __プログラムが複雑__ になるので、__修正しないほうが良い__ でしょう。

:::


## ルール 8 の定義

もちろん、__上記の条件__ を満たすような __着手__ を行っても、次の相手の手番で __邪魔をされる場合がある__ ので __自分の勝ち__ が __確定__ するわけでは __ありません__ が、__少なくとも__ 上記の __条件を満たす着手__ を __行わなければ__、__自分が勝利__ することは __あり得ません__。

そこで、__上記__ を満たす __着手__ を __優先的に行う__ という __条件__ を __ルール 7 改__ に加えた 下記の __ルール 8__ を考えることにします。なお、__上記の条件__ を __満たしても__、その次の __相手の手番__ で __相手が勝利__ しては __意味がない__ ので、__上記の条件__ は、「__相手__ が __勝利できる__ 着手を __行わない__」という __条件より__ も __優先順位を低く__ する __必要__ があります。

* __真ん中__ のマスに __優先的__ に __着手__ する
* そうでない場合は __勝てる場合__ に __勝つ__
* そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__
* そうでない場合は、__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が 1 つ以上 __存在する__ 局面になる着手を行う
* そうでない場合は __ランダム__ なマスに __着手__ する

__ルール 8__ の __評価値__ をどのように __設定__ すればよいかについて少し考えてみて下さい。

## 評価値の設定


下記は、__ルール 7 改__ の __評価値__ の __設定__ です。

| 優先順位 | 局面の状況 | 評価値 |
|:-:|:--|:-:|
| 1 | __真ん中のマスに着手している__ | `2`  |
| 2 | __自分が勝利している__  | `1`  |
| 4 | __相手が勝利できない__  | `0`  |
| 3 | __相手が勝利できる__  | `-1`  |

上記の表に、__ルール 8__ の『「__自 2 敵 0 空 1__」が 1 つ以上 __存在する__』 という __新しい条件__ を __追加__ した状態の __評価値を設定__ する必要があります。

下記の表は、__ルール 8__ の __条件の優先順位__ に注意しながら __評価値__ を __設定__ した例です。__上 2 つ__ の __評価値__ は、新しい条件の追加に合わせて __修正__ しました。

| 優先順位 | 局面の状況 | 評価値 |
|:-:|:--|:-:|
| 1 | __真ん中のマスに着手している__ | `3`  |
| 2 | __自分が勝利している__  | `2`  |
| 4 | __「自 2 敵 0 空 1」が 1 つ以上存在する__  | `1`  |
| 5 | __「自 2 敵 0 空 1」が存在しない__  | `0`  |
| 3 | __相手が勝利できる__  | `-1`  |

## `ai8s` の定義

局面に 「__自 2 敵 0 空 1__」が __1 つ以上存在するか__ どうかは、[前回の記事](https://qiita.com/ysgeso/items/6c0d73cc9ef4efd62d48#count_marks-%E3%81%AE%E5%AE%9A%E7%BE%A9)で定義した __`count_marks`__ メソッドで __計算__ できるので、__`ai8s`__ は、下記のように定義できます。

* __7、8 行目__：__真ん中__ のマスに着手した時の __評価値__ を __`3`__ に __修正__ する
* __11、12 行目__：__自分が勝利__ している場合の __評価値__ を __`2`__ に __修正__ する 
* __23、24、28、29、34、35、40、41 行目__：__相手__ が __勝利できない__ 局面で、__次__ の __自分の手番__ で __自分__ が __勝利できる__ かどうかを、「__自 2 敵 0 空 1__」であるかどうかで __判定__ し、その場合は __評価値__ として __`1`__ を __返す__。__`mb`__ は __相手の手番__ の局面であり、__自分の手番__ は、__`mb.last_turn`__ に __代入__ されている点に __注意__ すること

```python
 1  from ai import ai_by_score
 2  from marubatsu import Marubatsu
 3
 4  def ai8s(mb, debug=False):
 5      def eval_func(mb):
 6          # 真ん中のマスに着手している場合は、評価値として 3 を返す
 7          if mb.last_move == (1, 1):
 8              return 3
 9   
10          # 自分が勝利している場合は、評価値として 2 を返す
11          if mb.status == mb.last_turn:
12              return 2
13
14          # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
15          # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
16          # 横方向と縦方向の判定
17          for i in range(mb.BOARD_SIZE):
18              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
19              # 「自 0 敵 2 空 1」の場合は相手が勝利できる
20              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
21                  return -1
22              # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
23              elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
24                  return 1
25              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
26              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
27                  return -1
28              elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
29                  return 1
30          # 左上から右下方向の判定
31          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
32          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
33              return -1
34          elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
35              return 1
36          # 右上から左下方向の判定
37          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
38          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
39              return -1
40          elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
41              return 1
42
43          # それ以外の場合は評価値として 0 を返す
44          return 0
45
46      return ai_by_score(mb, eval_func, debug=debug)  
```

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

```python
from ai import ai_by_score
from marubatsu import Marubatsu

def ai8s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 3 を返す
        if mb.last_move == (1, 1):
            return 3
    
        # 自分が勝利している場合は、評価値として 2 を返す
        if mb.status == mb.last_turn:
            return 2

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
            elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return 1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return 1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
        elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
        elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug) 
```
</details>

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

```diff_python
from ai import ai_by_score
from marubatsu import Marubatsu

-def ai7s(mb, debug=False):
+def ai8s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 3 を返す
        if mb.last_move == (1, 1):
-           return 2
+           return 3
    
        # 自分が勝利している場合は、評価値として 2 を返す
        if mb.status == mb.last_turn:
-           return 1
+           return 2

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
+           elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+               return 1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
+           elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+               return 1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
+       elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
+       elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug) 
```
</details>


## `ai2` と `ai7s` との対戦

基準となる __`ai2`__ と、__これまで__ に作成した __最強の AI__ である __`ai7s`__ と対戦することにします。まず、下記のプログラムで __`ai2`__ と対戦します。

```python
from ai import ai_match, ai2, ai7s

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

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

```
ai8s VS ai2
count     win    lose    draw
o        9726     148     126
x        8608     854     538
total   18334    1002     664

ratio     win    lose    draw
o       97.3%    1.5%    1.3%
x       86.1%    8.5%    5.4%
total   91.7%    5.0%    3.3%
```

下記は、__`ai7` VS `ai2`__ と __`ai8s` VS `ai2`__ の対戦結果の表です。__`ai2` に対して__、__`ai8s`__ のほうが、__`ai7`__ より __勝率が高くなる__ ことが確認できますが、よく見ると、__敗率も高く__ なっています。__ルール 8__ の __条件 4__ の __追加__ で __敗率が高くなる__ のは __何かが変__ です。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai7`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__  | __95.8__ | __0.2__ | 4.0 | __82.3__ | __2.4__ | 15.3 | __89.0__ | __1.3__ | 9.7 |
| __`ai8s`__  | __97.3__ | __1.5__ | 1.3 | __86.1__ | __8.5__ | 5.4 | __91.7__ | __5.0__ | 3.3 |

次に、__`ai7s`__ と __対戦__ を行います。実行結果から、__強くしたはず__ の __`ai8s`__ が __`ai7` に__ 対して __大きく負け越している__ 点が __変__ です。これは、__ルール 8__ に __欠陥がある__ か、__`ai8s`__ が __ルール 8__ を __正しく実装できていない__ かの __どちらか__ が __原因__ です。__ルール 8__ を __見直しても__ 、特に __間違い__ は __なさそう__ なので、__`ai8s`__  に __バグがある__ 可能性が高く、実際に __`ai8s`__ には __バグがあります__。それが何であるかについて少し考えてみて下さい。

```python
ai_match(ai=[ai8s, ai7s])
```

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

```
ai8s VS ai7s
count     win    lose    draw
o        2563    3392    4045
x          92    7373    2535
total    2655   10765    6580

ratio     win    lose    draw
o       25.6%   33.9%   40.5%
x        0.9%   73.7%   25.4%
total   13.3%   53.8%   32.9%
```

## `ai8s` のバグの原因

下記は、__`ai8s`__ の __一部を抜粋__ したものです。__5 ～ 9 行目__ のプログラムに __バグがある__ ので、バグがどこにあるかが分からなかった方はその部分を探してみて下さい。

```python
1        # 横方向と縦方向の判定
2        for i in range(mb.BOARD_SIZE):
3            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
4            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
5            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
6                return -1
7            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
8            elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
9                return 1
```

__バグが発生__ する __具体的な局面__ を例に __説明__ します。例えば __下図左__ の __〇 の手番__ の局面で、__ルール 8__ で __着手を選択__ する場合の事を考えてみて下さい。その場合は、まず、__最初の合法手__ として、__下図右__ の __赤い 〇__ に __着手__ した局面に対して、__上記の処理__ を行って __評価値を計算__ することになります。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9793edab-bdb2-2094-02bc-ed2cd8118ae3.png" width="200">

__上図右__ の __局面__ に対して上記のプログラムを実行すると、__下記__ の __処理__ が行われます。

* __2 行目__：__`i`__ に __`0`__ が __代入__ されて __for 文__ の __ブロックが実行__ される
* __3 行目__：上図右の __上の行__ の「<strong>〇〇　</strong>」の __マークの数__ を __数え__、__結果__ の「__〇 2 × 0 空 1__」を表すデータ __`count`__ に __代入__ する。__元の局面__ は __〇 の手番__ なので、これは「__自 2 敵 0 空 1__」を表すデータである
* __5 行目__：__`count`__ の内容が、__敵__ が __勝利できる__、「__自 0 敵 2 空 1__」__ではない__ ので、__条件式__ が __`False`__ になる
* __8、9 行目__：__`count`__ の内容が、__次__ の __自分の手番__ で __自分__ が __勝利できる__、「__自 2 敵 0 空 1__」なので、__条件式__ が __`True`__ になり、__評価値__ として __`1`__ を返り値として __返す__
 
__上図右__ の __局面__ は、__相手__ が __勝利できる__ ので、__評価値__ として __`-1`__ を __返す必要__ がありますが、上記の手順で処理が行われるため、__`1`__ が __評価値__ として __返り__ ます。従って、__上図右__ の局面になるような __着手__ を __行うべきではない__ のに、__`ai8s`__ はそのマスに __着手__ してしまう __可能性__ が __生じます__。これが、__`ai8s`__ が __`ai7` に負け越す原因__ です。

下記のプログラムは、__上図左__ の局面に対して、__`ai8s`__ で __デバッグ表示__ を行いながら __着手を選択__ するプログラムです。__実行結果__ から、実際に __上図右__ の局面の __評価値__ として __`1`__ が __計算__ されていることが分かります。

```python
mb = Marubatsu()
mb.move(0, 0)
mb.move(0, 1)
mb.move(0, 2)
mb.move(1, 1)
print(mb)

ai8s(mb, debug=True)
```

実行結果

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

Start ai_by_score
Turn o
o..
xX.
o..

legal_moves [(1, 0), (2, 0), (2, 1), (1, 2), (2, 2)]
====================
move (1, 0)
Turn x
oO.
xx.
o..

score 1 best score -inf
UPDATE
  best score 1
  best moves [(1, 0)]
====================
move (2, 0)
Turn x
o.O
xx.
o..

score 1 best score 1
APPEND
  best moves [(1, 0), (2, 0)]
====================
move (2, 1)
Turn x
o..
xxO
o..

score 0 best score 1
====================
move (1, 2)
Turn x
o..
xx.
oO.

score -1 best score 1
====================
move (2, 2)
Turn x
o..
xx.
o.O

score -1 best score 1
====================
Finished
best score 1
best moves [(1, 0), (2, 0)]
```

また、__残りの合法手__ に着手した局面の __評価値__ は、__下記__ のように __計算__ されます。

* __(2, 0)__：__(1, 0)__ と __同様の手順__ で計算が行われ、__`1`__ が __計算__ される
* __(2, 1)__：「__自 0 敵 2 空 1__」も「__自 2 敵 0 空 1__」も __存在しない__ ので __`0`__ が __計算__ される
* __(1, 2)__、__(2, 2)__：「__自 0 敵 2 空 1__」__のみが存在__ するので、__`-1`__ が __計算__ される

__結果__ として、__最善手__ の __一覧__ に __(1, 0)__ と __(2, 0)__ のマスが __計算__ され、その __いずれか__ のマスに __着手__ が __行われます__ が、__その次__ の __相手の手番__ で 相手が __(2, 1)__ に __着手__ して __勝利__ することが __できてしまいます__。本当は、__(2, 1)__ に __着手__ することで __相手の勝利__ を __阻止できていた__ ので、__`ai8s`__ が __間違った__ 着手を __選択する__ ことが __確認__ できました。

このようなバグが発生した理由について少し考えてみてください。

## `ai8s` の修正方法 その 1

このバグは、__`ai8s`__ が、__下記__ の __ルール 8__ の表の、__優先順位__ が __3__ と __4__ の __条件__ を __繰り返し処理の中__ の __if 文__ で __まとめて判定__ しているため、__繰り返しの途中__ で __優先順位__ が __4__ の条件が、__3__ の条件 __よりも優先__ されてしまう __場合がある事__ が __原因__ です。従って、__優先順位__ が __3__ の条件が、__4__ の条件 __より__ も __必ず優先される__ ようにすることで __バグを修正__ することができます。その方法について少し考えてみて下さい。


| 優先順位 | 局面の状況 | 評価値 |
|:-:|:--|:-:|
| 1 | __真ん中のマスに着手している__ | `3`  |
| 2 | __自分が勝利している__  | `2`  |
| 4 | __「自 2 敵 0 空 1」が 1 つ以上存在する__  | `1`  |
| 5 | __「自 2 敵 0 空 1」が存在しない__  | `0`  |
| 3 | __相手が勝利できる__  | `-1`  |

__記述は大変__ ですが、__最も単純__ な方法は、下記のプログラムのように、__優先順位__ が __3__ の条件の __判定__ が __終了してから__、__優先順位__ が __4__ の条件の __判定を行う__ というものです。

* __13 ~ 27 行目__：__相手__ が __勝利できるか__ どうか __だけ__ を __判定__ するように __修正__ する
* __31 ~ 45 行目__：__次__ の __自分の手番__ で __自分__ が __勝利できるか__ を __判定__ する

比べて見ればわかると思いますが、__13 ～ 27 行目__ と、__31 ～ 45 行目__ のプログラムは、__条件式__ と、__return 文__ の __返り値__ を __除けば__ 、__全く同じ処理__ を行います。

```python
 1  def ai8s(mb, debug=False):
 2      def eval_func(mb):
 3          # 真ん中のマスに着手している場合は、評価値として 3 を返す
 4          if mb.last_move == (1, 1):
 5              return 3
 6    
 7          # 自分が勝利している場合は、評価値として 2 を返す
 8          if mb.status == mb.last_turn:
 9              return 2
10
11          # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
12          # 横方向と縦方向の判定
13          for i in range(mb.BOARD_SIZE):
14              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
15              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
16                  return -1
17              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
18              if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
19                  return -1
20          # 左上から右下方向の判定
21          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
22          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
23              return -1
24          # 右上から左下方向の判定
25          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
26          if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
27              return -1
28
29          # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
30          # 横方向と縦方向の判定
31          for i in range(mb.BOARD_SIZE):
32              count = mb.count_marks(coord=[0, i], dx=1, dy=0)
33              if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
34                  return 1
35              count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
36              if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
37                  return 1
38          # 左上から右下方向の判定
39          count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
40          if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
41              return 1
42          # 右上から左下方向の判定
43          count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
44          if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
45              return 1            
46
47          # それ以外の場合は評価値として 0 を返す
48          return 0
49
50      return ai_by_score(mb, eval_func, debug=debug) 
```

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

```python
def ai8s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 3 を返す
        if mb.last_move == (1, 1):
            return 3
    
        # 自分が勝利している場合は、評価値として 2 を返す
        if mb.status == mb.last_turn:
            return 2

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1

        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return 1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return 1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return 1            

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug) 
```
</details>

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

```diff_python
def ai8s(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 3 を返す
        if mb.last_move == (1, 1):
            return 3
    
        # 自分が勝利している場合は、評価値として 2 を返す
        if mb.status == mb.last_turn:
            return 2

        # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
        # 横方向と縦方向の判定
        for i in range(mb.BOARD_SIZE):
            count = mb.count_marks(coord=[0, i], dx=1, dy=0)
            # 「自 0 敵 2 空 1」の場合は相手が勝利できる
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
            # 「自 2 敵 0 空 1」の場合は次の自分の手番で自分が勝利できる
-           elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
-               return 1
            count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
            if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
                return -1
-           elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
-               return 1
        # 左上から右下方向の判定
        count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
-       elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
-           return 1
        # 右上から左下方向の判定
        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
        if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
            return -1
-       elif count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
-           return 1

        # そうでなく、「自 2 敵 0 空 1」がある場合は評価値として 1 を返す
        # 横方向と縦方向の判定
+       for i in range(mb.BOARD_SIZE):
+           count = mb.count_marks(coord=[0, i], dx=1, dy=0)
+           if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+               return 1
+           count = mb.count_marks(coord=[i, 0], dx=0, dy=1)
+           if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+               return 1
+       # 左上から右下方向の判定
+       count = mb.count_marks(coord=[0, 0], dx=1, dy=1)
+       if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1
+       # 右上から左下方向の判定
+        count = mb.count_marks(coord=[2, 0], dx=-1, dy=1)
+       if count[mb.last_turn] == 2 and count[Marubatsu.EMPTY] == 1:
+           return 1            

        # それ以外の場合は評価値として 0 を返す
        return 0

    return ai_by_score(mb, eval_func, debug=debug) 
```
</details>


### 修正の確認

修正したプログラムが __正しく動作__ するかを __確認__ するために、再び __`ai2`__ と __`ai7s`__ との対戦を行います。まず、基準となる __`ai2`__ と __対戦__ します。

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

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

```
ai8s VS ai2
count     win    lose    draw
o        9824      14     162
x        8938     249     813
total   18762     263     975

ratio     win    lose    draw
o       98.2%    0.1%    1.6%
x       89.4%    2.5%    8.1%
total   93.8%    1.3%    4.9%
```

下記は、__`ai7` VS `ai2`__ と __`ai8s` VS `ai2`__ の対戦結果の表です。__今度__ は __`ai2`__ に対して、__`ai8s`__ のほうが、__`ai7`__ より __勝率が高く__ なり、__敗率__ は __ほぼ変わらない__ ので、__正しく修正__ された __可能性が高い__ ことが __確認__ できます。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai7`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__  | __95.8__ | __0.2__ | 4.0 | __82.3__ | __2.4__ | 15.3 | __89.0__ | __1.3__ | 9.7 |
| __`ai8s`__  | __98.2__ | __0.1__ | 1.6 | __89.4__ | __2.5__ | 8.1 | __93.8__ | __1.3__ | 4.9 |

続いて、__`ai7s`__ との __対戦__ を行います。__実行結果__ から、__通算成績__ では、__`ai8s`__ の __勝率__ の方が __敗率より高い__ ので、__`ai8s`__ は __`ai7s` に__ 対して __強い__ ことが __確認__ できました。

```python
ai_match(ai=[ai8s, ai7s])
```

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

```
ai8s VS ai7s
count     win    lose    draw
o        3343     393    6264
x         388    2884    6728
total    3731    3277   12992

ratio     win    lose    draw
o       33.4%    3.9%   62.6%
x        3.9%   28.8%   67.3%
total   18.7%   16.4%   65.0%
```

## `ai8s` の修正方法 その 2

__先程__ の __`ai8s`__ では、__以下__ のような __手順__ で __処理__ を行いました。

* 8 種類ある __直線上の 3 マス__ に「__自 0 敵 2 空 1__」が __存在する__ 場合は __`-1`__ を返す
* 8 種類ある __直線上の 3 マス__ に「__自 2 敵 0 空 1__」が __存在する__ 場合は __`1`__ を返す

上記の __2 つの処理__ は、__同じような__、__かなり長い__ プログラムを __記述__ する必要があるので __大変__ です。そこで、上記の __2 つの処理__ を __1 つにまとめる__ ことにします。また、__1 つにまとめる__ ことで、__処理時間__ が __半分になる__ という __利点__ が得られます。どのようにすればまとめることができるかについて、少し考えてみて下さい。

### マークの数のパターンを列挙する関数の定義

:::note warn
__説明__ を __簡潔にする__ ために、以後は、「__自 2 敵 0 空 1__」のような、__直線上に配置__ された __マーク__ の __配置状況__ の事を、「__マークのパターン__」と __表記__ します。
:::

__ルール 8__ で __評価値__ を __計算__ する際に __必要な処理__ は、「__自 0 敵 2 空 1__」と「__自 2 敵 0 空 1__」という __2 種類__ の __マークのパターン__ が __存在するか__ を __調べる__ という処理です。

先ほどのプログラムでは、それらが __存在するか__ を __調べる__ ために、__8 種類__ ある __直線上の 3 マス__ の __マークのパターン__ を調べるという処理を、__2 回に分けて__ 行いました。それに対して、下記のアルゴリズムでは、__8 種類__ ある __直線上の 3 マス__ の __マークのパターン__ を __一度調べるだけ__ で __同様の処理__ を行うことができます。

1. __8 種類__ ある __直線上の 3 マス__ の __マークのパターン__ を計算し、__結果__ を __登録__ する
2. __登録__ した __データの中__ に、「__自 0 敵 2 空 1__」が __あれば `-1`__ を __返す__
3. __登録__ した __データの中__ に、「__自 2 敵 0 空 1__」が __あれば `1`__ を __返す__

別の言葉で説明すると、__特定__ の __マークのパターン__ が __存在するか__ どうかを __調べる際__ に、__マークのパターンごと__ に __8 種類__ ある __直線上の 3 マス__ を __調べ直す__ の __ではなく__、__調べた結果__ を __登録__ しておくことで、__一度調べるだけ__ で済むということです。

そこで、__`Marubatsu`__ クラスに __上記__ の __手順 1__ の __処理__ を行う、以下のような __メソッド__ を __定義__ することで、__`Marubatsu`__ クラスの __インスタンス__ に対して、__局面に存在__ する __マークのパターン__ の __一覧__ を __計算できる__ ようにします。

__名前__：__マーク__（mark）の __パターン__（pattern）を __列挙__（enumerate）するので、__`enum_markpats`__ という名前にします
__処理__：インスタンスの __局面__ の __マークのパターン__ を __列挙__ する
__入力__：なし
__出力__：__マークのパターン__ を __列挙__ した __データ__ を __返り値__ として __返す__

__マークのパターン__ を __列挙__ する __データ型__ として、真っ先に思いつくのは __list__ ではないかと思います。そこで、今回の記事では、__list を利用__ して __`enum_markpat`__ を下記のプログラムのように定義することにします。行っている処理は、__`ai8s`__ の中の __処理__ と __あまり変わらない__ ので、それほど難しくはないと思います。

* __2 行目__：__マークのパターン__ を __列挙__ した __データ__ を __代入__ するローカル変数 __`markpats`__ を __空の list__ で __初期化__ する
* __5 ~ 15 行目__：__8 種類__ ある __直線上の 3 マス__ の __マークのパターン__ を、これまでと同様の方法で __計算__ する
* __7、9、12、15 行目__：計算したそれぞれの __マークのパターン__ を、__`marks_pats`__ の __要素__ として __追加__ する
* __17 行目__：__`markpats`__ を __返り値__ として __返す__

```python
 1  def enum_markpats(self):
 2      markpats = []    
 3
 4      # 横方向と縦方向の判定
 5      for i in range(self.BOARD_SIZE):
 6          count = self.count_marks(coord=[0, i], dx=1, dy=0)
 7          markpats.append(count)
 8          count = self.count_marks(coord=[i, 0], dx=0, dy=1)
 9          markpats.append(count)
10      # 左上から右下方向の判定
11      count = self.count_marks(coord=[0, 0], dx=1, dy=1)
12      markpats.append(count)
13      # 右上から左下方向の判定
14      count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
15      markpats.append(count)
16
17      return markpats
18
19  Marubatsu.enum_markpats = enum_markpats
```

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

```python
def enum_markpats(self):
    markpats = []    
 
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        count = self.count_marks(coord=[0, i], dx=1, dy=0)
        markpats.append(count)
        count = self.count_marks(coord=[i, 0], dx=0, dy=1)
        markpats.append(count)
    # 左上から右下方向の判定
    count = self.count_marks(coord=[0, 0], dx=1, dy=1)
    markpats.append(count)
    # 右上から左下方向の判定
    count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
    markpats.append(count)

    return markpats

Marubatsu.enum_markpats = enum_markpats
```
</details>

`ai8s` の場合と異なり、計算した __マークのパターン__ は、__`markpats`__ の __要素に追加するだけ__ なので、上記のプログラムを下記のように __簡潔に記述__ することもできます。本記事では、下記の記述を採用しますが、好きな方を採用して構いません。

```python
def enum_markpats(self):
    markpats = []    
 
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        markpats.append(self.count_marks(coord=[0, i], dx=1, dy=0))
        markpats.append(self.count_marks(coord=[i, 0], dx=0, dy=1))
    # 左上から右下方向の判定
    markpats.append(self.count_marks(coord=[0, 0], dx=1, dy=1))
    # 右上から左下方向の判定
    markpats.append(self.count_marks(coord=[2, 0], dx=-1, dy=1))

    return markpats

Marubatsu.enum_markpats = enum_markpats
```
</details>

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

```diff_python
def enum_markpats(self):
    markpats = []    

    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
-       count = self.count_marks(coord=[0, i], dx=1, dy=0)
-       markpats.append(count)
+       markpats.append(self.count_marks(coord=[0, i], dx=1, dy=0))
-       count = self.count_marks(coord=[i, 0], dx=0, dy=1)
-       markpats.append(count)
+       markpats.append(self.count_marks(coord=[i, 0], dx=0, dy=1))
    # 左上から右下方向の判定
-   count = self.count_marks(coord=[0, 0], dx=1, dy=1)
-   markpats.append(count)
+   markpats.append(self.count_marks(coord=[0, 0], dx=1, dy=1))
    # 右上から左下方向の判定
-   count = self.count_marks(coord=[2, 0], dx=-1, dy=1)
-   markpats.append(count)
+   markpats.append(self.count_marks(coord=[2, 0], dx=-1, dy=1))
    
    return markpats

Marubatsu.enum_markpats = enum_markpats
```
</details>




### `enum_markpats` の実装の確認

下記のプログラムは、__いくつかの局面__ に対して、__`enum_markpats`__ メソッドを呼び出し て __計算__ した、__マークのパターン__ を __列挙__ した __データを表示__ しています。なお、__分かりやすく表示__ するために、__表示__ には[以前の記事](https://qiita.com/ysgeso/items/44884dcf168aab949508#%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93%E3%81%AE%E7%A2%BA%E8%AA%8D)で紹介した __`pprint`__ を利用します。

__実行結果__ から、__それぞれの局面__ に対して、__`enum_markpats`__ が、__8 種類__ ある __直線上の 3 マス__ の __マークのパターン__ を __要素__ とする __list を返す__ ことが __確認__ できます。

```python
from pprint import pprint
mb = Marubatsu()

print(mb)
pprint(mb.enum_markpats())

mb.move(1, 1)
print(mb)
pprint(mb.enum_markpats())

mb.move(0, 0)
print(mb)
pprint(mb.enum_markpats())

mb.move(1, 0)
print(mb)
pprint(mb.enum_markpats())
```

実行結果

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

[defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3})]
Turn x
...
.O.
...

[defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
Turn o
X..
.o.
...

[defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
Turn x
xO.
.o.
...

[defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'o': 2, '.': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
 ```

### dict と defaultdict の比較

__list など__ の、__[シーケンス型](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#%E3%82%B7%E3%83%BC%E3%82%B1%E3%83%B3%E3%82%B9%E5%9E%8B%E3%81%A8%E3%81%AF%E4%BD%95%E3%81%8B)__ の __要素の中__ に __特定の値__ の要素が __存在するか__ どうかは、__[in 演算子](https://qiita.com/ysgeso/items/1a8a4319ef3c896ef271#in-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%A8-not-in-%E6%BC%94%E7%AE%97%E5%AD%90)__ を使って __判定__ することが __できます__。また、__`in` 演算子__ は、__`==` 演算子__ を使って、__同じ値であるか__ どうかを __判定__ します。__`enum_markpats`__ は、__defaultdict__ を __要素__ とする __list を返す__ ので、__defaultdict__ に対する __`==` 演算子__ の __処理__ について説明します。

#### dict 動詞の比較

まず、__dict どうし__ を __`==` 演算子__ で __比較__ した場合の __処理__ について説明します。

__dict どうし__ を __`==` 演算子__ で __比較__ した場合は、__同一__ の __キー__ と __キーの値__ の __組み合わせ__ を持つ場合のみ __計算結果__ が __`True`__ になります。以下にいくつかの __具体例__ を示します。

* __`a`__ と __`b`__ は __同一__ の __キーとキーの値__ の __組み合わせ__ を持つので、__`True`__ になる
* __`a`__ と __`c`__ は __異なる__ の __キーとキーの値__ の __組み合わせ__ を持つので、__`False`__ になる
* __`a`__ と __`d`__ は、一部の __キーとキーの値__ が異なるので __`False`__ になる
* __`a`__ と __`e`__ のように、__両方に存在__ する __キーとキーの値__ の __組み合わせ__ が同じだが、一部の __キー__ が __片方__ の __dict にしか存在しない__ 場合は __`False`__ になる
* __`a`__ と __`f`__ のように、__キー__ の __記述の順番__ が __異なっていても__、__同一__ の __キーとキーの値__ の __組み合わせ__ を持つ場合は __`True`__ になる


```python
a = {"x": 1, "y": 2}
b = {"x": 1, "y": 2}
c = {"z": 1}
d = {"x": 1, "y": 3}
e = {"x": 1}
f = {"y": 2, "x": 1}

print(a == b)
print(a == c)
print(a == d)
print(a == e)
print(a == f)
```

実行結果
```
True
False
False
False
True
```

#### defaultdict どうしの比較

__defaultdict どうし__ の __比較__ は、__dict どうし__ の __比較__ と __同じ__ なので説明は省略します。

#### dict と defaultdict の比較

__dict__ と __defaultdict__ の __比較__ も __dict どうし__ の __比較__ と __同様__ で、下記のプログラムのように、__同一__ の __キーとキーの値__ の __組み合わせ__ を持つ場合は __`True`__ になります。

```python
from collections import defaultdict

a = {"x": 1, "y": 2}
b = defaultdict(int)
b["x"] = 1
b["y"] = 2
print(a == b)
```

実行結果

```
True
```

従って、__`enum_markpats`__ の __要素の中__ に、「__自 2 敵 0 空 1__」が存在するかどうかは、下記のプログラムのように、「__自 2 敵 0 空 1__」を表す __`{Marubatsu.CIRCLE: 2, Marubatsu.CROSS: 0, Marubatsu.EMPTY: 1 }`__ が __存在するか__ どうかで __判定できるはず__ と __考える人が多い__ かもしれません、__実行__ すると __`False`__ が __表示__ されてしまいます。

__実行結果__ に表示される __`markpats`__ の __要素の中__ には、確かに「__自 2 敵 0 空 1__」を表す __`defaultdict(<class 'int'>, {'o': 2, '.': 1})`__ が __表示されている__ のに、__`False` になる__ のは __理由があります__。その理由について説明します。

```python
print(mb)
markpats = mb.enum_markpats()
pprint(markpats)
print({Marubatsu.CIRCLE: 2, Marubatsu.CROSS: 0, Marubatsu.EMPTY: 1} in markpats)
```

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

[defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'o': 2, '.': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
False
```
#### dict と defaultdict の比較の際の注意点

__勘違いしやすい__ 点として、__下記の場合__ は、__`True` にならない__ 点に __注意が必要__ です。

* __dict__ に、比較する __defaultdict__ の __規定値__ が __代入__ されている __キーが存在__ する
* 比較する __defaultdict__ は、その __キー__ を __一度も参照していない__

具体例を挙げて説明します。下記のプログラムは、__`a`__ に __`"x"`__ というキーの値に __`1`__ を、__`"y"`__ というキーの値に __`b` の規定値__ である __`0`__ を __代入__ した __dict__ を代入します。

__`b`__ の __規定値__ が __`0`__ の __defaultdict__ には、__`"x"`__ というキーの値に __`1`__ を __代入__ します。

* __5、6 行目__：__`a`__ と __`b`__ を __表示__ すると、__`a`__ では __`"x"`__ と __`"y"`__ の __キーとキーの値__ が __表示__ されるが、__`b`__ では、__`"y"`__ という __キー__ を __一度も参照していない__ ので、__`"x"`__  の __キーとキーの値__ のみ __表示__ されまる
* __7 行目__：上記のように、__`a`__ と __`b`__ は __同じキーとキーの値__ の __組み合わせ__ を __持たない__ ので、__`a == b`__ は __`False`__ になる
* __9、11 行目__：__`a["y"]`__ と __`b["y"]`__ を比較すると、__`b["y"]`__ には、__既定値__ である __`0`__ が __自動的に代入__ されるので、__`True`__ になる。そのことは、__11 行目__ で __確認__ できる
* __12 行目__：__`b`__ には __`"y"`__ という __キーが存在するようになった__ ので、__`True`__ になる

```python
 1  a = {"x": 1, "y": 0}
 2  b = defaultdict(int)
 3  b["x"] = 1
 4
 5  print("a", a)
 6  print("b", b)
 7  print("a == b", a == b)
 8
 9  print('a["y"] == b["y"]', a ["y"] == b["y"])
10  print("a", a)
11  print("b", b)
12  print("a == b", a == b)
```

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

```python
a = {"x": 1, "y": 0}
b = defaultdict(int)
b["x"] = 1

print("a:", a)
print("b:", b)
print("a == b:", a == b)

print('a["y"] == b["y"]', a ["y"] == b["y"])
print("a:", a)
print("b:", b)
print("a == b:", a == b)
```
</details>

実行結果

```
a: {'x': 1, 'y': 0}
b: defaultdict(<class 'int'>, {'x': 1})
a == b: False
a["y"] == b["y"] True
a: {'x': 1, 'y': 0}
b: defaultdict(<class 'int'>, {'x': 1, 'y': 0})
a == b: True
```

先程、__`{Marubatsu.CIRCLE: 2, Marubatsu.CROSS: 0, Marubatsu.EMPTY: 1 } in markpats`__ が __`False`__ になったのは、__`markpats`__ の __`defaultdict(<class 'int'>, {'o': 2, '.': 1})`__ という __要素__ に __`Marubatsu.CROSS`__ という __キーが存在しない__ からです。

従って、__`enum_markpats`__ の __要素の中__ に、「__自 2 敵 0 空 1__」が存在するかどうかは、下記のプログラムのように、__`{Marubatsu.CIRCLE: 2, Marubatsu.EMPTY: 1 }`__ が __存在するか__ どうかで __判定__ する __必要__ があり、今度は __実行結果__ に __`True` が表示__ されます。

```python
print(mb)
markpats = mb.enum_markpats()
print({ Marubatsu.CIRCLE: 2, Marubatsu.EMPTY: 1 } in markpats)
```

実行結果

```
Turn x
xO.
.o.
...

[defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'x': 1, '.': 2}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1}),
 defaultdict(<class 'int'>, {'o': 2, '.': 1}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'.': 3}),
 defaultdict(<class 'int'>, {'x': 1, 'o': 1, '.': 1}),
 defaultdict(<class 'int'>, {'.': 2, 'o': 1})]
True
```

:::note warn
__dict__ と __defaultdict__ を、__`==` 演算子__ で __比較__ することが __できる__。

ただし、__dict__ の __キーの値__ が __defaultdict__ の __規定値__ であっても、__defaultdict__ の __そのキー__ が __一度も参照されていない__ 場合は、__等しい__ と __みなされい__。
:::

## __`enum_markpats`__ を利用した `ai8s` の定義

__`enum_markpats`__ メソッドを __利用__ することで、__ルール 8__ の AI を下記のプログラムのように __簡潔__ に __定義できる__ ようになります。なお、この後で、__実装した AI__ が __正しく動作するか__ どうかを __確認__ するために、__`ai8s`__ と対戦を行います。そこで、下記のプログラムでは、__`ai8s`__ と __区別__ できるように、__`ai8s2`__ という __名前__ で関数を __定義__ しています。なお、__`ai8s`__ からの修正箇所がかなり多いので、修正箇所は省略します。

* __11 行目__：__`enum_markpats`__ メソッドを呼び出して、__マークのパターン__ を __列挙__ した __list__ を __計算__ し、__`markpats`__ に __代入__ する
* __13、14 行目__：「__自 0、敵 2、空 1__」の __マークのパターン__ が __存在する__ 場合は、相手が勝利できる局面なので、__`-1`__ を __評価値__ として __返す__
* __16、17 行目__：「__自 2、敵 0、空 1__」の __マークのパターン__ が __存在する__ 場合は、__次__ の __自分の手番__ で __自分__ が __勝利できる__ 局面なので、__`1`__ を __評価値__ として __返す__
* __20 行目__：__すべての条件__ を __満たさない__ 場合は、__`0`__ を __評価値__ として __返す__

```python
 1  def ai8s2(mb, debug=False):
 2     def eval_func(mb):
 3         # 真ん中のマスに着手している場合は、評価値として 2 を返す
 4         if mb.last_move == (1, 1):
 5             return 3
 6   
 7         # 自分が勝利している場合は、評価値として 1 を返す
 8         if mb.status == mb.last_turn:
 9             return 2
10
11         markpats = mb.enum_markpats()
12         # 相手が勝利できる場合は評価値として -1 を返す
13         if {mb.turn: 2, Marubatsu.EMPTY: 1} in markpats:
14             return -1
15         # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
16         elif {mb.last_turn: 2, Marubatsu.EMPTY: 1} in markpats:
17             return 1
18         # それ以外の場合は評価値として 0 を返す
19         else:
20             return 0
21
22     return ai_by_score(mb, eval_func, debug=debug)  
```

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

```python
def ai8s2(mb, debug=False):
    def eval_func(mb):
        # 真ん中のマスに着手している場合は、評価値として 2 を返す
        if mb.last_move == (1, 1):
            return 3
    
        # 自分が勝利している場合は、評価値として 1 を返す
        if mb.status == mb.last_turn:
            return 2

        markpats = mb.enum_markpats()
        # 相手が勝利できる場合は評価値として -1 を返す
        if {mb.turn: 2, Marubatsu.EMPTY: 1} in markpats:
            return -1
        # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
        elif {mb.last_turn: 2, Marubatsu.EMPTY: 1} in markpats:
            return 1
        # それ以外の場合は評価値として 0 を返す
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)  
```
</details>

### 動作の確認

__`ai8s2`__ が __正しく動作__ するかどうかを __確認__ するために、__`ai8s`__ と __対戦__ を行います。__実行結果__ から、__`ai8s2`__ を __正しく実装__ できていることが __確認__ できます。

```python
ai_match(ai=[ai8s2, ai8s])
```

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

```
ai8s2 VS ai8s
count     win    lose    draw
o        3339     412    6249
x         405    3389    6206
total    3744    3801   12455

ratio     win    lose    draw
o       33.4%    4.1%   62.5%
x        4.0%   33.9%   62.1%
total   18.7%   19.0%   62.3%
```

## `ai8s` と `ai8s2` の処理速度の比較

先程説明したように、__`ai8s`__ は特定の __マークのパターン__ が __あるか__ どうかを __判定__ する処理を __2 回__ 行っているので、その処理を __1 回__ しか行わない __`ai8s2` より__ も処理に __時間がかかる__ ことが __予想__ されます。そこで、実際に __`ai8s` どうし__ と、__`ai8s2` どうし__ で __対戦__ を行い、__処理時間__ を __比較__ することにします。

下記の __`ai8s` どうし__ の対戦は、筆者のパソコンでは __49.1 秒__ かかりました。

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

下記の __`ai8s2` どうし__ の対戦は、筆者のパソコンでは __45.5 秒__ かかりました。

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

予想に反して __処理時間__ は __10% 程度__ しか変わりませんでしたが、__`ai8s2` のほう__ が __処理時間__ が __短い__ ことは __確認__ できました。処理時間が __大きく変わらない理由__ は、__`ai8s`__ は __マークのパターン__ が __見つかった時点__ で __処理を中断__ するのに対し、__`ai8s`__ は __必ずすべて__ の __マークのパターン__ を __計算する__ からです。

これで __`ai8s`__ は __用済み__ なので、__`ai8s` を破棄__ して、__`ai8s2`__ の __名前__ を __`ai8s` に変更__ します。

# ルールベースの AI の性質

ルールベースの AI の作成をかなり進めてきましたので、ここで、[以前の記事](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai-%E3%81%AE%E7%A8%AE%E9%A1%9E)で説明した __ルールベース__ の AI の __性質__ について具体例を元に __説明__ します。

__ルール 5、6__ で付け加えた「__勝てる場合__ に __勝つ__」と「__相手__ が __勝利できる__ 着手を __行わない__」という __2 つの条件__ は、[以前の記事](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)で __検証__ したように、その条件を満たすような着手を行うことで、__AI__ が __絶対に強くなる__ ことが __保証__ されています。

一方、__ルール 3__ の「__真ん中__ のマスに __優先的__ に __着手__ する」は、[以前の記事](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#%E7%9C%9F%E3%82%93%E4%B8%AD%E3%81%AE%E3%83%9E%E3%82%B9%E3%81%B8%E3%81%AE%E7%9D%80%E6%89%8B%E3%81%8C%E6%9C%89%E5%88%A9%E3%81%A7%E3%81%82%E3%82%8B%E7%90%86%E7%94%B1%E3%81%AE%E8%80%83%E5%AF%9F)で、__有利である可能性が高い__ ことの __考察__ は行いましたが、その条件を満たす着手がどのような場合でも __最善手である__ という __証明__ までは __行っていません__。それは、今回の __ルール 8__ で付け加えた __条件__ でも __同様__ です。例えば、__一般的__ にはそのルールに従うと __有利になる__ が、__特定の局面__ ではそのルールに従うと __不利になる__ ような __局面__ が __存在するかも__ しれません。

そのような、__厳密__ に __強くなること__ が __保証されていない__ ルールで AI を __実装しても大丈夫なのか__ と思う人がいると思いますが、__厳密__ に __強くなること__ が __保証される__ ような __ルールを作成__ することは __不可能__ な __場合が多い__ のが __現実__ です。

そのことは、オセロ、将棋、囲碁のような、ある程度以上 __複雑なゲーム__ を遊んだことがある人であれば、__どのような局面__ でも __適用できる__、__絶対に強い手__ を __選択できるルール__ が __ほとんど存在しない__ ことから理解できるのではないでしょうか。

従って、__ルールベース__ で __AI を作成__ する際には、本記事でこれまでに行ったように、下記のような __試行錯誤__ で __AI を強くする__ という手法を取ります。

1. __有効だと考えられる__ ルールを __考案__ する
2. そのルールを __実装した AI__ を __作成__ する
3. __他の AI と対戦__ させた __結果__ から __有効であるか__ どうかを __判断__ する
4. __有効であれば採用__ し、__そうでなければ破棄__ する
5. 可能であれば、対戦結果などから作成した __ルール の性質__ を __考察__ することでゲームの __知識を深め__、__次のルール__ を __作成__ する際の __参考__ にする

__ルールベース__ で __AI を作成__ する際には、__以下__ のような __難しさ__ があります。下記のうちのいくつかは、本記事で体験済です。

* __最初は__ 思いついたルールで __AI__ が __どんどん強くなっていく__ が、__次第__ に AI の __強さ__ がほとんど __向上しなくなっていく__
* ルールの __アイディアが尽きてくる__ と、__新しいルール__ を __考える__ のが __困難になる__
* __特定のルール__ に __のみ強い__ というルールを、__一般的に強い__ ルールであると __勘違い__ してしまうと、強くしたつもりが __実際には弱くなる__ 場合がある
* __ルール__ の __数が多くなる__ と、複数のルールの間で __矛盾が生じる__ ようになり、ルール間の __優先順位__ などの __整合性を取る__ ことが __困難__ になる
* __ルール__ の __数が多くなる__ と、__ルール__ を __単独で適用__ すると __強くなる__ が、__複数のルール__ を __組み合わせる__ と逆に __弱くなってしまう__ ような __状況が生じる__ 

従って、__最近 の AI__ は __人間__ が __ルールを考える__ というルールベースではなく、AI が __自動的__ に __ルール__ を __発見__ する、__機械学習__ という手法を使ったものが主流になっています。〇×ゲームの AI を機械学習で作成する方法については、今後の記事で紹介します。

なお、__〇×ゲーム__ は、__単純__ なゲームなので、__ルールベース__ でも __最強の AI を作る__ ことが __可能__ なので、引き続きルールベースで 〇×ゲームの AI を作成します。

# 今回の記事のまとめ

今回の記事では、ゲームに __勝つため__ に __必要な条件__ を __考察__ し、__ルール 8__ を __定義__ しました。また、__ルール 8__ を __実装__ するために、__マークのパターン__ を __列挙__ する __関数を定義__ しました。

今回の記事では、__マークのパターン__ の __列挙__ を __list__ を使って行いましたが、次回の記事では、__list 以外__ の方法で __マークのパターン__ を __列挙__ する __方法__ について説明します。

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/051/marubatsu_new.py

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

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

# 次回の記事

https://qiita.com/ysgeso/items/3b8967122379079a2a82