Pythonで〇×ゲームのAIを一から作成する　その56　棋譜の記録と、問題のある試合経過の検証

# 目次と前回の記事

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

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/056/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>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール8](https://qiita.com/ysgeso/items/58754ba98c286f414ea4#%E3%83%AB%E3%83%BC%E3%83%AB-8-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が 1 つ以上 __存在する__ 局面になる着手を行う<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール9](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E3%83%AB%E3%83%BC%E3%83%AB-9-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __必ず勝利できる__ ように、「__自 2 敵 0 空 1__」が __2 つ以上存在する__ 局面になる着手を行う<br>そうでない場合は、__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が __1 つ存在する__ 局面になる着手を行う<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール10](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E3%83%AB%E3%83%BC%E3%83%AB-10)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __必ず勝利できる__ ように、「__自 2 敵 0 空 1__」が __2 つ以上存在する__ 局面になる着手を行う<br>そうでない場合は、__以下__ の 2 つを __総合的に判断__ して着手を行う<ul><li>__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が __1 つ存在する__ 局面になる着手を行う</li><li>__自分__ が __有利になる__ ように、「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う</li></ul>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール11](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E3%83%AB%E3%83%BC%E3%83%AB-11)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __必ず勝利できる__ ように、「__自 2 敵 0 空 1__」が __2 つ以上存在する__ 局面になる着手を行う<br>そうでない場合は、__以下__ の 3 つを __総合的に判断__ して着手を行う<ul><li>__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が __1 つ存在する__ 局面になる着手を行う</li><li>__自分__ が __有利になる__ ように、「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う</li><li>__相手__ が __不利になる__ ように、「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う</li></ul>そうでない場合は __ランダム__ なマスに __着手__ する |

基準となる __`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 |
| __[`ai8s`](https://qiita.com/ysgeso/items/085fd15fbd91d5cdf770#ai8s-%E3%81%AE%E4%BF%AE%E6%AD%A3)__  | __98.2__ | __0.1__ | 1.6 | __89.4__ | __2.5__ | 8.1 | __93.8__ | __1.3__ | 4.9 |
| __[`ai9s`](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#ai9s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __98.7__ | __0.1__ | 1.2 | __89.6__ | __2.4__ | 8.0 | __94.1__ | __1.3__ | 4.6 |
| __[`ai10s`](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#ai10s-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __97.4__ | __0.0__ | 2.6 | __85.6__ | __2.6__ | 11.7 | __91.5__ | __1.3__ | 7.2 |
| __[`ai11s`](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#ai11s-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%A8ai2ai10s-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6)__  | __98.1__ | __0.0__ | 1.9 | __82.5__ | __1.9__ | 15.6 | __90.3__ | __1.0__ | 8.7 | あり |

# `ai11s` の問題点

[前回の記事](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E3%83%AB%E3%83%BC%E3%83%AB-11)では、__[ルール 10](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E3%83%AB%E3%83%BC%E3%83%AB-10)__ に、__相手__ が __不利になる__ ように『「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う』という __条件を追加__ した __ルール 11__ を __定義__ しました。しかし、その __ルール 11__ を __実装__ した __`ai11s`__ と、__ルール 10__ を __実装__ した __`ai10s`__ を下記のプログラムで __対戦__ させると、実行結果の __通算成績__ から __`ai10s` に__ 対して __弱くなる__ ことが分かりました。今回の記事では、そのようなことが起きる __原因__ の __調べ方__ について説明します。

```python
from ai import ai_match, ai10s, ai11s

ai_match(ai=[ai11s, ai10s])
```

実行結果

```
ai11s VS ai10s
count     win    lose    draw
o        2206       0    7794
x           0    4968    5032
total    2206    4968   12826

ratio     win    lose    draw
o       22.1%    0.0%   77.9%
x        0.0%   49.7%   50.3%
total   11.0%   24.8%   64.1%
```

# AI が弱くなった場合の対処方法

これまでは、作成した __AI__ の __強さの確認__ は、__`ai_match`__ という関数で __別の AI__ と __複数回対戦__ し、その __通算成績__ を __見る__ ことで行ってきました。また、その __結果__ が __想定した結果__ と __異なる__ 場合は、__プログラムの欠陥__ を __探して修正する__ という __方法__ で __対処__ してきました。

[前回の記事](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E5%BF%85%E8%A6%81%E6%9D%A1%E4%BB%B6)で説明したように、__必要条件__ や __十分条件__ の __性質__ を満たす __条件__ であれば、__ルール__ に __組み込む__ ことで、少なくとも __AI__ が __弱くならない__ ことが __保証される__ ので、__そのような条件__ を __新しく組み込んだ__ AI が __弱くなった場合__ は、__プログラムの実装__ が __間違っている__ ことを __疑う__ という __対処法__ が __有効な場合__ が __多いでしょう__。しかし、__必要条件__ でも __十分条件__ でも __ない__ 条件は、__ルールに加えた__ 場合に、__AI__ が __弱くなる可能性__ があるので、__AI__ が __弱くなった場合__ は、__条件そのもの__ の __欠陥__ も __疑う必要__ があります。

## 問題の原因の絞り込み

__ルール 11__ の __条件__ の中で、__必要条件__ でも __十分条件__ でも __ない__ ものは __以下の通り__ です。

* __真ん中__ のマスに __優先的__ に __着手__ する
* __以下__ の __3 つ__ の条件を __総合的__ に __判断__ して着手を行う
    * __次__ の __自分の手番__ で __勝利できる__ ように「__自 2 敵 0 空 1__」が __1 つ存在する__ 着手を行う
    * __自分__ が __有利になる__ ように「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う
    * __相手__ が __不利になる__ ように「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う

この中で、「__真ん中__ のマスに __優先的__ に __着手__ する」という条件は、__初期のルール__ で __追加__ しており、__実際__ にこの条件を __ルールに組み込む__ ことによって __AI__ が __強くなった__ ことが __確認できている__ ので、__問題__ がある __可能性__ は __低そう__ です。そこで、__この条件__ の __検証__ は __後回し__ にし、__残りの条件__ に __問題がない__ ことが __分かった場合__ に __改めて調べる__ ことにします。

__3 つ__ の __条件__ を __総合的__ に __判断__ して __着手を行う__ という __条件__ に対する __評価値__ は、__それぞれの条件__ に対して、__下記の表__ のように __設定__ した __評価値の合計__ で __計算__ していますが、この __評価値__ の __計算方法__ が、__強い AI__ のための __条件__ として __ふさわしくない可能性__ があります。

| 局面の状況 | 評価値 | 
|:--|--:|
| __「自 2 敵 0 空 1」が 1 つ存在する__ | `1` |
| __「自 1 敵 0 空 2」が x 個存在する__ | `x` |
| __「自 0 敵 1 空 2」が y 個存在する__ | `-y` |

## 問題が発生している可能性が高い試合の観察

__上記__ の __評価値__ の __計算方法__ に __問題__ がある __可能性が高い__ ことが分かりましたが、この表を眺めているだけでは、__どこに問題がある__ かを __知る__ ことは __困難__ でしょう。その理由は、__〇×ゲーム__ に __勝利するため__ に、『__「自 2 敵 0 空 1」が 1 つ存在する__』、『__「自 1 敵 0 空 2」が x 個存在する__』、『__「自 0 敵 1 空 2」が y 個存在する__』の __3 つの条件__ の、それぞれの __重要度__ が __どれくらいであるか__ がはっきりと __わからない__ からです。

:::note
__はっきりとわからない理由__ は、__必要条件__ でも、__十分条件__ でも __ないから__ です。
:::

そのような場合は、__実装した AI__ が __行った対戦__ の中で、__問題が発生__ している __可能性が高い試合__ で __行われた着手__ を __観察__ することで __問題の原因__ を __探る__ という __方法__ があります。

__下記__ は、先程の __`ai11s` VS `ai10s`__ の __対戦結果__ を __再掲__ したものです。よく見ると、__`ai11s`__ が __〇 を担当__ した場合は、__勝率__ が __約 20 %__、__敗率__ が __0 %__ となっているので、__問題はなさそう__ です。一方、__× を担当__ した場合は、__勝率__ が __0 %__、__敗率__ が __50 %__ となっており、何か __問題が発生__ している __可能性が高い__ ことが __分かります__。このことから、__`ai11s` VS `ai10s`__ の __試合__ で、__`ai11s`__ が __× を担当__ して __負けた試合__ を __観察__ すれば良いことが分かります。

```
ai11s VS ai10s
count     win    lose    draw
o        2206       0    7794
x           0    4968    5032
total    2206    4968   12826

ratio     win    lose    draw
o       22.1%    0.0%   77.9%
x        0.0%   49.7%   50.3%
total   11.0%   24.8%   64.1%
```

__`ai11s`__ VS __`ai10s`__ で、__`ai11s`__ が __× を担当__ して __負ける試合__ は、__`mb.play(ai=[ai10s, ai11s])`__ を __実行__ し、__返り値__ が __`ai11s` の敗北__ を表す __`Marubatsu.CIRCLE`__  に __なった場合__ です。

そのような試合は、下記のプログラムのように、__[while 文](https://qiita.com/ysgeso/items/d2cce68c7a32bf3790ef#%E6%89%8B%E9%A0%86-5-%E3%81%AE%E5%AE%9F%E8%A3%85%E3%81%A8-while-%E6%96%87)__ を使って __`ai11s`__ が __負けるまで__、__`mb.play(ai=[ai10s, ai11s])`__ を __繰り返し呼び出す__ という __処理を行う__ ことで __観察__ することが __できます__。__最後__ に __表示された試合__ が、__`ai11s`__ が __負けた試合__ です。

:::note warn
__今回の記事__ では __以後__ は、__`ai11s`__ VS __`ai10s`__ のように __記述__ した場合は、__先に記述__ した __`ai11s`__ が __〇を担当__ して __`ai10s`__  と __対戦を行う__ ことを表すことにします。
:::

* __4 行目__：__`while True`__ による __無限ループ__ を __記述__ する
* __5、6 行目__：__`ai10s`__ VS __`ai11s`__ の __対戦__ を行い、__対戦__ の __経過__ を __表示する__。また、__その返り値__ が __`Marubatsu.CIRCLE`__ だった場合は、__`ai11s`__ が __負けている__ ので、__break 文__ を __実行__ して __無限ループ__ から __抜ける__

```python
1  from marubatsu import Marubatsu
2
3  mb = Marubatsu()
4  while True:
5     if mb.play([ai10s, ai11s]) == Marubatsu.CIRCLE:
6          break
```        

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

```python
from marubatsu import Marubatsu

mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s]) == Marubatsu.CIRCLE:
        break
```
</details>

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

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

Turn x
...
.O.
...

Turn o
...
.o.
..X

Turn x
O..
.o.
..x

Turn o
o.X
.o.
..x

Turn x
o.x
.oO
..x

Turn o
o.x
Xoo
..x

Turn x
o.x
xoo
O.x

Turn o
oXx
xoo
o.x

winner draw
oxx
xoo
oOx

Turn o
...
...
...

Turn x
...
.O.
...

Turn o
..X
.o.
...

Turn x
..x
.o.
O..

Turn o
..x
Xo.
o..

Turn x
..x
xo.
o.O

Turn o
.Xx
xo.
o.o

winner o
.xx
xo.
oOo
```
:::note
このプログラムで、__〇__ が __絶対に勝利しない__ ような __AI どうし__ の __対戦を行う__ と、__無限ループ__ から __抜けられない__ ので、__処理__ が __終わらなくなる__ 点に __注意__ して下さい。
:::

### 上記のプログラムの問題点

__上記__ のプログラムを __何度か実行__ すれば __わかる__ と思いますが、上記のプログラムには、__`ai11s`__ が __負けるまで__ 何度も __対戦を行う__ ので、__運が悪い__ と __`ai11s`__ が __負けていない試合__ が __延々と表示__ されてしまいます。__実際__ に、__上記__ の __実行結果__ では、__最初__ に __引き分け__ の試合が __表示__ され、__その次__ に __`ai11s`__ が __負ける試合__ が __表示__ されます。__表示__ する __必要がある__ のは、__`ai11s`__ が __負けた試合だけ__ なので、__余計な表示__ が行われるのは __望ましくありません__。

:::note
上記の場合は、__`ai11s`__ が __負ける可能性__ が __50 % もある__ ので __運が悪くない限り__、__余計な試合__ が __数多く表示__ されることは __ありません__ が、__`ai11s`__ が __負ける可能性__ が __低い場合__ は、__余計な試合__ がものすごく __多く表示されてしまう__ ことになります。
:::

そこで、上記の __プログラム__ を __修正__ し、__`ai11s`__ が __負けた試合だけ__ を __表示__ するようにします。どのように修正すれば良いかを少し考えてみて下さい。

### 棋譜の必要性

__余計な試合__ を __表示しない__ ようにするために、下記のプログラムの __3 行目__ のように、__`verbose=False`__ を __記述__ して __`play`__ メソッドを __呼び出す__ という方法を __思いついた人__ が __いるかもしれません__ が、__この方法__ では、__`ai11s`__ が __負けた試合__ も __表示されなく__ なります。

```python
mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        break
```     

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

```diff_python
mb = Marubatsu()
while True:
-   if mb.play([ai10s, ai11s]) == Marubatsu.CIRCLE:
+   if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        break

```
</details>


実行結果
```
```

__考え方__ は __間違っていない__ のですが、残念ながら、__下記__ のような __理由__ で、__`verbose=False` だけ__ では、__`ai11s`__ が __負けた時だけ__ 試合経過を __表示__ することは __できません__。

* __`verbose=False`__ は、__ゲーム__ を __開始する前__ に __指定__ する __必要__ がある
* __`ai11s`__ が __負けるか__ どうかは、__ゲームが終了__ するまで __わからない__

この __問題を解決__ する __方法の一つ__ は、ゲームを __行う際__ に、__行われた着手__ を __記録しておく__ という方法です。__一般的__ に、__ゲーム__ で __プレイヤー__ が行った __行動の記録__ の事を __棋譜__ と呼ぶので、本記事でも __棋譜__ という __用語を使う__ ことにします。

__棋譜__ を __記録しておく__ ことで、__ゲームの終了後__ に、__新しいゲーム__ を __開始__ し、その __棋譜通り__ に __着手を行う__ ことで、__試合経過__ を __再現__ することが __できます__。

__〇×ゲーム__ の __棋譜__ を __どのように記録__ すればよいかについて少し考えてみて下さい。

## 棋譜の記録の実装

まず、__棋譜__ をどのような __データ構造__ で表現するかを __決める必要__ があります。__棋譜__ は、__行われた着手__ を __順番に並べた__ ものなので、__着手__ を表す __データ__ を __要素__ として持つ __list__ 使って __表現__ することが __できます__。

__棋譜__ は、__〇×ゲーム__ に __関するデータ__ なので、__`Marubatsu`__ クラスの __インスタンス__ の __属性__ に __記録__ することにします。__棋譜__ の __英語__ は __record__ なので、__`records`__ という __名前__ にします。

:::note
__棋譜__ のような __記録したデータ__ を代入する __変数の名前__ には、他にも __`history`__（履歴）や __`log`__（記録）などの __名前__ が __良く使われます__。
:::

### `restart` メソッドの修正

__棋譜__ の __初期化__ は、__ゲーム__ の __開始時__ に __行う必要__ があるので、__`restart`__ メソッドの中に __その処理__ を下記のように __記述__ します。

* __8 行目__：__`records`__ 属性を、__空の list__ で __初期化__ する

```python
1   def restart(self):
2       self.initialize_board()
3       self.turn = Marubatsu.CIRCLE     
4       self.move_count = 0
5       self.status = Marubatsu.PLAYING
6       self.last_move = -1, -1          
7       self.last_turn = None
8       self.records = []
9 
10  Marubatsu.restart = restart
```

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

```python
def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1          
    self.last_turn = None
    self.records = []

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

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

```diff_python
def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1          
    self.last_turn = None
+   self.records = []

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

### `move` メソッドの修正

__棋譜__ の __更新__ は、__着手の際__ に __行う必要__ があるので、__`move`__ メソッドの中に __その処理__ を下記のように __記述__ します。

* __8 行目__：__`records`__ 属性の __要素__ に、__着手__ した __座標__ のデータを表す __`self.last_move`__ を __追加__ する。なお、この部分は、__`self.records.append((x, y))`__ と __記述しても良い__

```python
 1  def move(self, x, y):
 2      if self.place_mark(x, y, self.turn):
 3          self.last_turn = self.turn
 4          self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
 5          self.move_count += 1
 6          self.status = self.judge()
 7          self.last_move = x, y
 8          self.records.append(self.last_move)
 9           
10  Marubatsu.move = move
```

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

```python
def move(self, x, y):
    if self.place_mark(x, y, self.turn):
        self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.status = self.judge()
        self.last_move = x, y
        self.records.append(self.last_move)
            
Marubatsu.move = move
```
</details>

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

```diff_python
def move(self, x, y):
    if self.place_mark(x, y, self.turn):
        self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.status = self.judge()
        self.last_move = x, y
+       self.records.append(self.last_move)
            
Marubatsu.move = move
```
</details>

### 棋譜の表示

上記のように修正することで、__`ai11s`__ が __負けた時__ の __棋譜__ を、下記のプログラムで __表示__ することが __できるように__ なります。

* __3、4 行目__：__`ai11s`__ が __負けた時に__ 、__棋譜__ が __代入__ された __`mb.records`__ を __表示__ する

```python
1  mb = Marubatsu()
2  while True:
3     if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
4          print(mb.records)
5          break
```     

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

```python
mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        print(mb.records)
        break
```
</details>

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

```diff_python
mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
+       print(mb.records)
        break
```
</details>


実行結果（実行結果はランダムなので下記とは異なる場合があります）
```
[(1, 1), (0, 2), (2, 0), (2, 1), (1, 0), (2, 2), (1, 2)]
```

### 棋譜によるゲームの経過の表示

__棋譜__ には、__行われた着手__ が __順番に記録__ されているので、__for 文__ と __`move`__ メソッドを __利用__ することで、下記のプログラムのように、__`ai11s`__ が __負けた時__ の __試合経過__ を __表示__ することができます。__実行結果__ から、__負けた時__ の __試合だけ__ が __表示__ されることが __確認__ できます。

* __4 行目__：__`ai11s`__ が __負けた試合__ の __棋譜__ を __`records`__ に __代入__ する
* __5 行目__：__棋譜__ を使って __負けた試合__ を __再現__ するために、__`restart`__ メソッドを呼び出して、__ゲーム__ を __リセット__ する。なお、__この処理__ を __4 行目より前__ に行っては __いけない__ 点に __注意__ する事。その理由は、__`restart`__ メソッドによって __棋譜__ が __リセット__ されてしまうため、4 行目で __`records`__ に __空の list__ が __代入__ されてしまうことになるからである
* __6 行目__：__棋譜__ から __順番__ に __着手__ のデータを __取り出し__ 、__`x`__ と __`y`__ に __代入__ する
* __7、8 行目__：__(x, y)__ のマスに __着手__ を行い、その __結果__ の __ゲーム盤__ を __表示__ する

```python
1  mb = Marubatsu()
2  while True:
3      if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
4          records = mb.records
5          mb.restart()
6          for x, y in records:
7              mb.move(x, y)
8              print(mb)
9          break
```   

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

```python
mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
        records = mb.records
        mb.restart()
        for x, y in records:
            mb.move(x, y)
            print(mb)
        break
```
</details>

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

```diff_python
mb = Marubatsu()
while True:
    if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
+       records = mb.records
+       mb.restart()
+       for x, y in records:
+           mb.move(x, y)
+           print(mb)
        break
```
</details>


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

Turn o
X..
.o.
...

Turn x
x..
.o.
..O

Turn o
x..
.o.
.Xo

Turn x
x.O
.o.
.xo

Turn o
x.o
.o.
Xxo

winner o
x.o
.oO
xxo
```

### 指定した条件の試合経過を表示する関数の定義

__特定__ の __AI どうし__ の __対戦__ で、__指定__ した __結果になる__ 場合の __試合経過__ を __表示__ する際に、__毎回上記__ のような __プログラムを記述する__ のは __大変__ なので、__上記の処理__ を行う、下記のような __関数__ を __定義__ する事にします。

__名前__：__試合経過__（progress）を __表示__（show）するので __`show_progress`__ とする
__処理__：__指定__ した __AI どうし__ の対戦で、__指定__ した __結果__ の __試合経過__ を __表示__ する
__入力__：__仮引数 `ai`__ に __対戦__ を行う __AI__ を、__`winner`__ に __試合結果__ を __代入__ する
__出力__：なし

__`show_progress`__ は __下記__ のプログラムのように __定義__ します。

* __1 行目__：__仮引数__ に __`ai`__ と __`winner`__ を __記述__ する
* __2 ~ 10 行目__：__4 行目以外__ は __元のプログラム__ と __同じ__
* __4 行目__：`play` メソッドの __実引数__ に __`ai=ai`__ を __記述__ するように __修正__ し、__`play`__ メソッドの __返り値__ と 仮引数 __`winner`__  が __等しいか__ どうかを __判定__ するように修正する

```python
 1  def show_progress(ai, winner):
 2      mb = Marubatsu()
 3      while True:
 4          if mb.play(ai=ai, verbose=False) == winner:
 5              records = mb.records
 6              mb.restart()
 7              for x, y in records:
 8                  mb.move(x, y)
 9                  print(mb)
10              break
```

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

```python
def show_progress(ai, winner):
    mb = Marubatsu()
    while True:
        if mb.play(ai=ai, verbose=False) == winner:
            records = mb.records
            mb.restart()
            for x, y in records:
                mb.move(x, y)
                print(mb)
            break
```
</details>

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

```diff_python
+def show_progress(ai, winner):
    mb = Marubatsu()
    while True:
-       if mb.play([ai10s, ai11s], verbose=False) == Marubatsu.CIRCLE:
+       if mb.play(ai=ai, verbose=False) == winner:
            records = mb.records
            mb.restart()
            for x, y in records:
                mb.move(x, y)
                print(mb)
            break
```
</details>

__`ai10s`__ VS __`ai11s`__ で、__`ai11s`__ が __負ける試合__ は、__下記__ のプログラムで __表示__ できます。__実行結果__ から、__`ai11s`__ が __負ける試合__ が __正しく表示__ できていることが __確認__ できます。

```python
show_progress([ai10s, ai11s], Marubatsu.CIRCLE)
```

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

```
Turn x
...
.O.
...

Turn o
X..
.o.
...

Turn x
x..
.o.
..O

Turn o
x..
.o.
.Xo

Turn x
x.O
.o.
.xo

Turn o
x.o
.o.
Xxo

winner o
x.o
.oO
xxo
```

なお、__定義__ した __`show_progress`__ は、__ai.py__ に __記述する__ ことにします。

# 同一局面の定義と扱い

試合経過の観察を行う前に、__同一局面__ に関する __定義__ と、__その扱い__ について説明します。

## 同一局面の定義

__〇×ゲーム__ の __ゲーム盤__ は、__3 x 3__ の __上下左右__ が __対象__ となる __形状__ をしています。また、将棋やチェスとは異なり、__ゲーム盤__ に __向き__ は __存在しません__[^1]。そのようなゲーム盤は、ゲーム盤を __回転させたりする__ ことで、__異なる局面__ が __別の局面__ と __一致する場合__ があります。本記事では __そのような局面__ のことを __同一局面__ と呼ぶことにします。

例えば、下図の __左の局面__ を、__時計回り__ に __90 度回転__ させると、__右の局面__ に __一致する__ ので、__この 2 つ__ は __同一局面__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0a335685-d37b-8ac6-5eb9-6badef12b711.png" width="150">

## 同一局面の種類

__〇×ゲーム__ の __同一局面__ は、以下のように __分類__ できます。

### 回転による同一局面

ある局面を __時計回り__ に __90 度ずつ回転__ した __局面__ は __同一局面__ ですが、__90 度__ の __回転__ を __4 回行う__ と __360 度__ になって __元の局面__ に __もどる__ ので、__回転__ による __同一局面__ は __4 種類__ ある事になります。それぞれの __マス__ に __1 ~ 9__ までの __番号__ を __割り当てた__ 場合、__回転__ による __同一局面__ は __下図__ の __1 行目__ のようになります。なお、__下図__ の __2 行目__ は __同一局面__ の  __具体例__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/6ab37e48-e264-92fe-3c85-1c33f47a6274.png" width="310">

### 線対称な同一局面

ある __直線__ に対して、__両側の形__ が __同じ図形__ の事を __線対称__ な __図形__ と呼びます。__線対称__ な __図形__ は、その __直線を軸__ として、__180 度ひっくり返す__ と、__同じ形__ の __図形__ になります。

__〇×ゲーム__ の場合は、__真ん中のマス__ を __通る__、__垂直__、__水平__、__左上から右下方向__、__右上から左下方向__ の __4 種類__ の __直線を軸__ として、__ゲーム盤__ の __表裏__ を __ひっくり返した局面__ が __同一局面__ になります。__下図__ は、__左上__ の __局面__ に対する、__4 種類__ の __線対称__ な __同一局面__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b5cb24c4-6cdc-c8ea-ff8c-497dadeb1f09.png" width="390">

### 同一局面の一覧

上記から、__〇×ゲーム__ では、__ある局面__ の __同一局面__ は、__最大__ で __下図__ の __8 種類__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/86ce95b0-6999-5e72-7f7e-59d36839fb29.png" width="630">

ただし、上記で「__最大で__」と __記述__ したのは、__8 種類__ ある __同一局面__ の __いくつか__ が、__完全に同じ局面__ の __場合がある__ からです。例えば、__下図__ の __1 行目__ の __局面__ に対する __同一局面__ は __4 種類__、__2 行目__ の __局面__ に対する __同一局面__ は __1 種類__ しかありません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/99161bd6-32f9-2f72-d699-fd036e61c3a2.png" width="310">

## 同一局面の性質と本記事での扱い

〇×ゲームに限らず、__ほとんどのゲーム__ では、__同一局面__ は、__見た目は違う__ かもしれませんが、__ゲームの勝敗__ を __考える上__ では、__同じ局面__ と __みなす__ ことが __できます__。そこで、__本記事__ では __同一局面__ に対しては、__その中の 1 つ__ の __局面だけ__ を __考慮__ することで、__残り__ の __同一局面__ に対する __考慮__ を __行ったとみなす__ ことにします。

# 試合経過の観察と検証

これまでは、__AI どうし__ の __試合__ の __勝敗の結果__ しか __見てきませんでした__ が、__試合__ の __経過__ を __観察__ し、__検証__ を行うことで、__AI__ が __それぞれの局面__ で、__具体的__ に __どのように__ 着手を __選択__ しているかが __わかるようになります__。また、その __検証を行う__ ことで、__ルール__ の __条件__ の __問題点__ や、その問題点の __解決法__ が __わかるようになる__ 場合があります[^2]。そこで、上記の __`ai10s`__ VS __`ai11s`__ の __試合経過__ を __観察__ し、__`a11s`__ の __問題点__ を __検証__ することにします。

わかりやすいように、先程の __試合経過__ を __図__ で __表現__ します。下図は、__黄色のマス__ が __着手__ を行ったマスを、__上に表示__ されているのはその __着手を行った AI__ を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a4a76c02-f6d9-f1bf-8bbd-e31988b52b12.png" width="500">

まず、__`ai10s`__ と __`ai11s`__ が __それぞれの局面__ に対して、__どのような判断__ に基づいて __着手を選択__ したかについて __検証__ することにします。

## 1 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/823f5378-5a52-2538-1f29-f380db27c2e1.png" width="70">

__ルール 10__ の __最も優先順位__ が __高い条件__ は、「__真ん中__ のマスに __優先的__ に __着手__ する」なので、__1 手目__ で __`ai10`__ は __必ず真ん中__ の __(1, 1)__ のマスに __着手__ を __行うはず__ です。上記の試合でも、__実際__ に __そのような着手__ が __行われています__。

__1 手目__ で __真ん中のマス__ に __着手__ が __行われた__ ので、__以後__ は __`ai10s`__ も __`ai11s`__ も、__最も高い__ 評価値が __計算__ される __合法手を選択__ します。

## 2 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/087be64e-ece1-8abb-796c-1f03501a6fa6.png" width="150">

__2 手目__ で __`ai11s`__ は __(0, 0)__ のマスに __着手__ していますが、この __マス__ が __選択された理由__ を、それぞれの __合法手__ に着手した局面の __評価値__ が __どのように計算された__ かを、__ルールに基づいて__ 実際に __調べる__ ことで __検証__ することにします。

### 評価値の確認

__`ai11s`__ が、それぞれの __合法手__ に対して __計算__ する __評価値__ は、下記のプログラムのように、__実引数__ に __`debug=True`__ を __記述__ して __`ai11s`__ を __呼び出す__ ことで __表示する__ ことが __できます__。

* __2 行目__：__2 手目__ を __着手する前__ の __局面__ を __作る__
* __3 行目__：__その局面__ に対して、__`ai11s`__ を、__デバッグ表示を行う__ ように __`debug=True`__ を __実引数に記述__ して __呼び出す__

```python
mb = Marubatsu()
mb.move(1, 1)
ai11s(mb, debug=True)
```

実行結果

```
Start ai_by_score
Turn x
...
.O.
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn o
X..
.o.
...

score -1 best score -inf
UPDATE
  best score -1
  best moves [(0, 0)]
====================
move (1, 0)
Turn o
.X.
.o.
...

score -2 best score -1
====================
move (2, 0)
Turn o
..X
.o.
...

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

score -2 best score -1
====================
move (2, 1)
Turn o
...
.oX
...

score -2 best score -1
====================
move (0, 2)
Turn o
...
.o.
X..

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

score -2 best score -1
====================
move (2, 2)
Turn o
...
.o.
..X

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

下記はそれぞれの __合法手__ を __着手した際__ の __評価値__ です。

| 合法手 | (0, 0) | (1, 0) | (2, 0) | (0, 1) | (2, 1) | (0, 2) | (1, 2) | (2, 2) |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| __評価値__  | -1  | -2  | -1  | -2  | -2  | -1  | -2  | -1  |

__評価値__ の __最大値__ は __-1__ なので、__評価値__ が __-1__ である __(0, 0)__、__(2, 0)__、__(0, 2)__、__(2, 2)__ の中から __ランダム__ に __着手__ が __選択される__ ことが分かります。そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。

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

__実際__ に __行われた着手__ である __(0, 0)__ は、その __4 つ__ の __候補の中__ に __入っている__ ので、__(0, 0)__ が __着手された理由__ が __確認__ できました。

### 同一局面をまとめる

__2 手目__ の __合法手__ は、__真ん中のマス__ を __除いた 8 マス__ がありますが、__隅のマス__ に __着手__ した場合は、__ゲーム盤__ を __回転__ することで __(0, 0)__ のマスに __着手__ した場合と __同一局面__ になります。__同様__ に、__辺__ のマスに __着手__ した場合は、__ゲーム盤__ を __回転__ することで __(1, 0)__ のマスに __着手__ した場合と __同一局面__ になります。下図はそのことを表した図です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/16f43aa7-a87a-e908-5b01-f61251b27dcd.png" width=330">

また、__実際__ に __隅に着手__ した場合の __評価値__ は __すべて -1__ に、__辺に着手__ した場合の __評価値__ は __すべて -2__ になっていることから、__同一局面__ に対する __評価値__ が __同じになる__ ことが __確認__ できます。従って、__上記の表__ を、__下記__ のように __まとめる__ ことが __できます__。


| 合法手 | 評価値 |
|:-:|:-:|
| __隅の 4 マス__ | -1  |
| __辺の 4 マス__ | -2  |

### デバッグ表示にマークのパターンの数を表示する修正

__`ai11s(mb, debug=True)`__ の __実行結果__ の __表示__ には、それぞれの __合法手__ を着手した局面の __評価値__ は __表示されます__ が、その評価値が __どのように計算されたか__ は __表示されません__。そこで、下記のプログラムのように、__`ai11s`__ が __評価値__ を __計算する際__ に __利用__ する、__マークのパターン__ の __数__ を __表示__ するように __`ai11s` を修正__ することにします。

* __8、9 行目__：__仮引数 `debug`__ が __`True`__ の場合に、__`count_markpats`__ が __計算__ した、__マークのパターン__ を __表示__ するように __修正__ する

```python
 1  from pprint import pprint
 2  from ai import ai_by_score
 3  from marubatsu import Markpat
 4
 5  def ai11s(mb, debug=False):
 6     def eval_func(mb):      
元と同じなので省略
 7         markpats = mb.count_markpats()
 8         if debug:
 9             pprint(markpats)
10          # 相手が勝利できる場合は評価値として -100 を返す
11          if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
12              return -100
元と同じなので省略
```

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

```python
from pprint import pprint
from ai import ai_by_score
from marubatsu import Markpat

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

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 100 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 100

        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に 1 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += 1
        # 「自 1 敵 0 空 2」の数だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)]
        # 「自 0 敵 1 空 2」の数だけ、評価値を減算する
        score -= markpats[Markpat(last_turn=0, turn=1, empty=2)]
        
        # 計算した評価値を返す
        return score

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

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

```diff_python
from pprint import pprint
from ai import ai_by_score
from marubatsu import Markpat

def ai11s(mb, debug=False):
    def eval_func(mb):      
元と同じなので省略
        markpats = mb.count_markpats()
+       if debug:
+           pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
元と同じなので省略
```
</details>


__上記の修正__ を行うことで、__先程と同じ__ 下記のプログラムを __実行__ すると、__評価値__ を __表示する直前__ に、__マークのパターンの数__ が __表示__ されるようになります。

```python
mb = Marubatsu()
mb.move(1, 1)
ai11s(mb, debug=True)
```

実行結果

```
略
move (0, 0)
Turn o
X..
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -inf
略
```

<details><summary><strong>実行結果の全体（長いのでクリックして表示して下さい）</strong></summary>

```
Start ai_by_score
Turn x
...
.O.
...

legal_moves [(0, 0), (1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
====================
move (0, 0)
Turn o
X..
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -inf
UPDATE
  best score -1
  best moves [(0, 0)]
====================
move (1, 0)
Turn o
.X.
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (2, 0)
Turn o
..X
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0)]
====================
move (0, 1)
Turn o
...
Xo.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (2, 1)
Turn o
...
.oX
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (0, 2)
Turn o
...
.o.
X..

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0), (0, 2)]
====================
move (1, 2)
Turn o
...
.o.
.X.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 3,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -2 best score -1
====================
move (2, 2)
Turn o
...
.o.
..X

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(0, 0), (2, 0), (0, 2), (2, 2)]
====================
Finished
best score -1
best moves [(0, 0), (2, 0), (0, 2), (2, 2)]
```
</details>

__`ai9s`__、__`ai10s`__ も下記のプログラムのように、__同様の方法__ で __修正__ することにします。

<details><summary><strong><code>ai9s</code>（長いのでクリックして表示して下さい）</strong></summary>

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

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -1 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -1
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 2 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 2
        # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            return 1
        # それ以外の場合は評価値として 0 を返す
        else:
            return 0

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

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

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

        markpats = mb.count_markpats()
+       if debug:
+           pprint(markpats)
        # 相手が勝利できる場合は評価値として -1 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -1
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 2 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 2
        # 次の自分の手番で自分が勝利できる場合は評価値として 1 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            return 1
        # それ以外の場合は評価値として 0 を返す
        else:
            return 0

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

<details><summary><strong><code>ai10s</code>（長いのでクリックして表示して下さい）</strong></summary>

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

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 100 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 100

        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に 1 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += 1
        # 「自 1 敵 0 空 2」の数だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)]
        
        # 計算した評価値を返す
        return score

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

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

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

        markpats = mb.count_markpats()
+       if debug:
+           pprint(markpats)
        # 相手が勝利できる場合は評価値として -100 を返す
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return -100
        # 次の自分の手番で自分が必ず勝利できる場合は評価値として 100 を返す
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return 100

        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に 1 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
            score += 1
        # 「自 1 敵 0 空 2」の数だけ、評価値を加算する
        score += markpats[Markpat(last_turn=1, turn=0, empty=2)]
        
        # 計算した評価値を返す
        return score

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

### ローカル関数のブロックの中の名前解決

下記は __修正__ した __`ai11s`__ の一部を再掲したプログラムです。先程は、下記のプログラムの __12 行目__ の __`debug`__ が、__1 行目__ の __`ai11s`__ の __仮引数 `debug`__ と __同じものである__ として __説明__ を行いましたが、__12 行目__ の __`debug`__ は、__グローバル関数__ である __`ai11s`__ の __ブロックの中__ に __記述__ されてはいますが、__同時__ に __ローカル関数__ である __`eval_func`__ の __ブロックの中__ にも __記述__ されています。そこで、__ローカル関数の中__ で行われる __名前解決__ について説明します。

```python
 1  def ai11s(mb, debug=False):
 2      def eval_func(mb):      
 3          # 真ん中のマスに着手している場合は、評価値として 300 を返す
 4          if mb.last_move == (1, 1):
 5              return 300
 6     
 7          # 自分が勝利している場合は、評価値として 200 を返す
 8          if mb.status == mb.last_turn:
 9              return 200
10
11          markpats = mb.count_markpats()
12          if debug:
13              pprint(markpats)
略
```

下図は、__`ai11s`__ の __グローバルスコープ__ と __ローカルスコープ__ を __図示__ したものです。図のように、__グローバル関数__ である __`ai11` の中__ に __定義__ された __ローカル関数 `eval_func`__ に対しても __ローカルスコープ__ が作られ、__3 種類__ の __スコープ__ は __入れ子__ の __構造__ になります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/cb9eba58-e333-64ae-b2de-4f549ef5982c.png" width="500">

上図の、水色の __ローカル関数__ の __ローカルスコープ内__ での __名前解決__ の __手順__ は、__難しそうに思えるかも__ しれませんが、__実際__ には[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E5%90%8D%E5%89%8D%E3%81%AE%E8%A1%9D%E7%AA%81%E3%81%A8%E5%90%8D%E5%89%8D%E8%A7%A3%E6%B1%BA)で説明した __手順と同じ__ です。

__ローカル関数__ の __ブロックの中__ で __代入処理__ が行われた場合は、[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E4%BB%A3%E5%85%A5%E5%87%A6%E7%90%86%E3%81%AB%E3%82%88%E3%82%8B%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93%E3%81%B8%E3%81%AE%E7%99%BB%E9%8C%B2%E3%81%A8%E6%9B%B4%E6%96%B0)で説明した場合と __同様__ に、__その関数__ の __ローカル名前空間__ が __管理__ する __名前__ に __値が代入__ されます。

__ローカル関数__ の __ブロックの中__ で __変数の値__ が __参照__ された場合は、[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E5%BC%8F%E3%81%AE%E4%B8%AD%E3%81%AB%E8%A8%98%E8%BF%B0%E3%81%95%E3%82%8C%E3%81%9F%E5%90%8D%E5%89%8D%E8%A7%A3%E6%B1%BA)で説明した __下記の手順__ と __同じ手順__ で __名前解決__ が行われます。

1. 名前が記述されている __式をスコープ__ とする __入れ子__ になった __名前空間__ のうち、__最も内側にある__ 名前空間を __選択__ する
2. 選択した名前空間の中から __名前を探す__
3. 名前が __見つかった__ 場合は、その名前空間を使って、名前からオブジェクトを __対応づける__
4. 名前が __見つからなかった__ 場合は、__一つ外側__ の名前空間を __選択__ して、手順 2 へ戻る
5. 手順 4 で、外側の名前空間が __存在しない場合__ は、__NameError__ という __エラーが発生__ する

__この手順__ に従って、下記の __12 行目__ の __`debug`__ の __名前解決__ は、__下記の手順__ で行われます。

1. __12 行目__ の __`debug`__ をスコープとする __最も内側__ の __名前空間__ は、__ローカル関数 `eval_func`__ の __名前空間__ である
2. __12 行目__ の __`debug`__ は、__ローカル関数 `eval_func`__ の __名前空間__ に __登録されていない__
3. __1 つ外側__ の __名前空間__ は、__グローバル関数 `ai11s`__ が管理する __名前空間__ である
4. __`ai11s`__ の __仮引数 `debug`__ は __`ai11s`__ の __名前空間__ に __登録されている__ ので、__名前がみつかる__
5. __`ai11s`__ の __ローカル変数 `debug`__ の __値__ を使って、__12 行目__ の __処理__ が __行われる__

```python
 1  def ai11s(mb, debug=False):
 2      def eval_func(mb):      
 3          # 真ん中のマスに着手している場合は、評価値として 300 を返す
 4          if mb.last_move == (1, 1):
 5              return 300
 6     
 7          # 自分が勝利している場合は、評価値として 200 を返す
 8          if mb.status == mb.last_turn:
 9              return 200
10
11          markpats = mb.count_markpats()
12          if debug:
13              pprint(markpats)
略
```

:::note warn
__グローバル変数__ と __ローカル変数__ が __同じ名前__ であっても __異なる変数__ であるように、「__グローバル関数__ の __ローカル変数__」と、そのグローバル関数の中で定義された「__ローカル関数__ の __ローカル変数__」は、__同じ名前__ であっても __異なる変数__ である。
:::

例えば、上記のプログラムの場合、__`ai11s`__ の __ローカル変数 `mb`__ と、__`eval_func`__ の __ローカル変数 `mb`__ は __同じ名前__ であっても、__異なる変数__ です。

「__グローバル関数__ の __ローカル変数__」と、そのグローバル関数の中で定義された「__ローカル関数__ の __ローカル変数__」の関係は、__グローバル変数__ と __ローカル変数__ の __関係__ に __似ています__。

### global と nonlocal

__global__ と __nonlocal__ を使うと __バグが発生しやすくなる__ ので、__特別な理由__ がない限り、あまり __使わないほうが良い__ でしょう。__本記事__ でも __nonlocal__ を __利用__ する __予定はない__ ので、この部分は __興味がない方__ は __読み飛ばして__ も __構いません__。

[以前の記事](https://qiita.com/ysgeso/items/b0732427b90a1ec27243#global-%E3%82%92%E4%BD%BF%E3%81%86%E6%96%B9%E6%B3%95)で、__関数のブロック__ の中で、__`global 変数名`__ を記述することで、__その変数__ が __グローバル変数__ と __みなされるようになる__ ことを説明しました。

__ローカル関数__ の場合は、その __外側__ に __グローバル名前空間__ と __グローバル関数のローカル名前空間__ があるので、__`global 変数名`__ だけでは、そのうちの __グローバル名前空間__ にしか __対応できません__。そのため、Python では、__`nonlocal 変数名`__ を __記述__ することで、その __変数名__ を __一つ外側__ の __名前空間に登録__ された __名前__ と __みなす__ ことができるようになっています。

下記は __global__ と __nonlocal__ を利用した __例__ です。__処理の内容__ は、__コメント__ を見て下さい。

```python
a = 1 # グローバル変数 a に 1 を代入する
b = 2 # グローバル変数 b に 2 を代入する

def x():
    def y():
        global b                 # b をグローバル変数とみなす
        print("global b =", b)   # グローバル変数 b を表示する

    def z():
        nonlocal b               # b を 1 つ外側の名前空間である x のローカル変数とみなす
        print("nonlocal b =", b) # x のローカル変数 b を表示する

    global a                # a をグローバル変数とみなす
    print("global a =", a)  # グローバル変数 a を表示する
    b = 3                   # 関数 x のローカル変数 b に 3 を代入する
    y()                     # ローカル関数 y を呼び出す
    z()                     # ローカル関数 z を呼び出す
      
x() # 関数 x を呼び出す
```

実行結果
```
global a = 1
global b = 2
nonlocal b = 3
```

__global__ と __nonlocal__ の詳細については、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/reference/simple_stmts.html#the-global-statement

https://docs.python.org/ja/3/reference/simple_stmts.html#the-nonlocal-statement

### 評価値の計算方法の検証

下記は、先程実行した __`ai11s(mb, debug=True)`__ の __実行結果__ を __元__ に、それぞれの __合法手__ に __着手__ を行った __局面__ の __マークのパターン__ の __数__ と、__評価値__ を __表にまとめた__ ものです。

表のそれぞれの意味は以下の通りです。なお、以後は、__合法手__ を表の __左の列の番号__ を使って、__合法手 1__ のように __表記__ することにします。

* __1 行目__ では、__マークのパターン__ 「__自 x 敵 y 空 z__」を「__xyz__」のように表記する
* __2 行目__ は、それぞれの __マークのパターン__ に対する __評価値__ を表す
* __3 行目以降__ の __ゲーム盤の図__ では、__着手__ を行った __合法手__ の __マス__ を __水色__ で __表示__ する。また、__同一局面__ のうちの __1 つのみ__ を __表示__ する

||  | 「201」 | 「021」 | 「102」 | 「012」 | 評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|| __評価値__ | 1：`+1`<br>2~：`100` | `-100` | 1 つで<br>`+1` | 1 つで<br>`-1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e4eef0af-a914-ac77-8336-dc74607f7ad3.png" width="70"> |   |   | 2  | 3  | -1 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/41f02452-0b8d-e4d8-7211-bfc417b52e55.png" width="70">  | | | 1  | 3  | -2  |

表から、__どの合法手__ に __着手__ しても、__相手が有利__ になる「__自 0 敵 1 空 2__」の __数__ は __同じ__ ですが、__自分が有利__ になる「__自 1 敵 0 空 2__」の __数__ は、__隅に着手__ したほうが __多くなり__、その結果、__隅__ に __着手__ したほうが __評価値__ が __高くなる__ ことが分かりました。そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。従って、__この局面__ では、__`ai11s`__ は __100 % 隅のマス__ に __着手__ を行います。また、実際に __`ai11s`__ は __隅のマス__ に __着手__ を __行っています__。

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

このように、__`ai11s`__ が __具体的__ に __どのように__ 評価値を __計算しているか__ を __検証__ することで、__`ai11s`__ が __選択した着手__ の __根拠__ が __明確__ になります。また、その結果、AI が __意図通り__ の処理を行うことを __確認__ できたり、__不具合の原因__ を __発見__ したりすることができる場合があります。実際に、__上記__ の場合は、__意図通り__ の処理を __行っていること__ が __確認__ できます。


## 3 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/33c9ecf2-36d8-00e9-d407-3420640dc60d.png" width="150">

__本記事__ の __目的__ は、__`ai11s`__ が __選択__ する __着手__ の __検証__ ですが、__`ai10s`__ の __ルール__ は、__`ai11s`__ の __ルール__ に __かなり似ている__ ので、__`ai10s`__  が __選択__ する __着手__ も __検証__ することにします。

__2 手目__ の __検証__ と __同様__ に、下記のプログラムで __`ai10s`__ がそれぞれの __合法手__ に対してどのような __評価値__ を __計算__ するかを __表示__ し、その __結果__ を __表にまとめる__ ことにします。

* __1、2 行目__：__2 手目__ の __(0, 0)__ の __着手__ を行い、__`ai10s`__ を __呼び出す__。

```python
mb.move(0, 0)
ai10s(mb, debug=True)
```

<details><summary><strong>実行結果（長いのでクリックして開いてください）</strong></summary>

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

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 3 best score -inf
UPDATE
  best score 3
  best moves [(1, 0)]
====================
move (2, 0)
Turn x
x.O
.o.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 3
UPDATE
  best score 4
  best moves [(2, 0)]
====================
move (0, 1)
Turn x
x..
Oo.
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 2,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 3 best score 4
====================
move (2, 1)
Turn x
x..
.oO
...

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 4
APPEND
  best moves [(2, 0), (2, 1)]
====================
move (0, 2)
Turn x
x..
.o.
O..

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 4
APPEND
  best moves [(2, 0), (2, 1), (0, 2)]
====================
move (1, 2)
Turn x
x..
.o.
.O.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score 4 best score 4
APPEND
  best moves [(2, 0), (2, 1), (0, 2), (1, 2)]
====================
move (2, 2)
Turn x
x..
.o.
..O

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 5,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 5 best score 4
UPDATE
  best score 5
  best moves [(2, 2)]
====================
Finished
best score 5
best moves [(2, 2)]
```

</details>


下記は、__上記の結果__ を __まとめた表__ です。なお、__ルール 10__ は、「__自 0 敵 2 空 1__」に関する __条件__ は __ありません__ ので、先程の表と異なり、「__012__」の __列__ は __存在しません__。また、先程は、同一局面を 1 つにまとめると説明しましたが、__同一局面__ が __2 つの場合__ は、__両方表記__ したほうが __分かりやすい__ 気がしましたので、下図では __同一局面__ を __横に並べて表記__ します。

| |  | 「201」 | 「021」 | 「102」 | 評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| | __評価値__ | 1：`+1`<br>2~：`100` | `-100` | 1 つで<br>`+1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c1784898-ca3a-4419-96a1-b7e709fd13c5.png" width="140"> | 1 | | 2 | 3 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b4a1ceef-b876-c68e-64b1-04b577993a15.png" width="140"> | 1 | | 3 | 4 |
| 3 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f2a5b0ad-c738-498d-3dc1-95e5eca66c9c.png" width="140"> | 1 | | 3 | 4  |
| 4 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/87124f4a-c5f4-687b-2671-c11c89e82cdd.png" width="65">  |  | | 5 | 5 |

表から、__`ai10s`__ が __実際__ に __着手__ を行った、__合法手 4__ の __(2, 2)__ に __着手__ した場合の __評価値__ が __5__ で __最も高くなる__ ことが __確認__ できました。そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。従って、__この局面__ では、__`ai10s`__ は __100 % (2, 2)__ に __着手__ を行います。

```
best score 5
best moves [(2, 2)]
```

__合法手 4__ には「__自 2 敵 0 空 1__」は __存在しません__ が、それが __1 つ存在__ する __合法手 2、3__  と __比較__ して、自分が有利になる「__自 1 敵 0 空 2__」が __2 つ多い__ ので、__合法手 4__ を __選択__ することは、__ルール 10__ の __意図通り__ と __言える__ でしょう。

## 4 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/57fbb5bd-3c78-f001-b490-ba3f056db57e.png" width="150">

__これまで__ と __同様__ に、下記のプログラムで __`ai11s`__ がそれぞれの __合法手__ に対して __どのように__ 評価値を __計算__ するかを __表示__ し、その __結果__ を __表にまとめます__。

```python
mb.move(2, 2)
ai11s(mb, debug=True)
```

<details><summary><strong>実行結果（長いのでクリックして開いてください）</strong></summary>

```
Start ai_by_score
Turn x
x..
.o.
..O

legal_moves [(1, 0), (2, 0), (0, 1), (2, 1), (0, 2), (1, 2)]
====================
move (1, 0)
Turn o
xX.
.o.
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 4,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -2 best score -inf
UPDATE
  best score -2
  best moves [(1, 0)]
====================
move (2, 0)
Turn o
x.X
.o.
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -1 best score -2
UPDATE
  best score -1
  best moves [(2, 0)]
====================
move (0, 1)
Turn o
x..
Xo.
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 4,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -2 best score -1
====================
move (2, 1)
Turn o
x..
.oX
..o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1})
score -1 best score -1
APPEND
  best moves [(2, 0), (2, 1)]
====================
move (0, 2)
Turn o
x..
.o.
X.o

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -1 best score -1
APPEND
  best moves [(2, 0), (2, 1), (0, 2)]
====================
move (1, 2)
Turn o
x..
.o.
.Xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 3,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1})
score -1 best score -1
APPEND
  best moves [(2, 0), (2, 1), (0, 2), (1, 2)]
====================
Finished
best score -1
best moves [(2, 0), (2, 1), (0, 2), (1, 2)]
```

</details>

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

| |  | 「201」 | 「021」 | 「102」 | 「012」 |評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| | __評価値__ | 1：`+1`<br>2~：`100` | `-100` | 1 つで<br>`+1` | 1 つで<br>`-1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/3d1fdd6a-2a1d-06e2-1ff7-f9bb9aae2216.png" width="140"> | 1 | | 1 | 4 | -2 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/2a606113-076e-2b87-8268-a76e4bfd89b7.png" width="140"> | 1 | | 1 | 3 | -1 |
| 3 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5f16999c-609b-1748-91af-2ff41108eefe.png" width="140"> | 0 | | 2 | 3  | -1 |

表から、__合法手 2__ と __3__ の __評価値__ が __`-1`__ で __最も高い__ ことが分かります。そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。

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

__合法手 2__ と __3__ の __着手__ はそれぞれ __2 通りずつ__ あるので、__合法手 3__ と __合法手 4__ の __着手__ が行われる __確率__ は、__それぞれ__ 2 / 4 = __50 %__ であることが分かります。従って、__この局面__ では、__50 %__ の確率で、__合法手 2__ または __合法手 3__ の __着手__ が __行われる__ ことが分かります。__実際の対戦__ で __`ai11s`__ が __合法手 3__ の __(1, 2)__ に __着手を行った__ のは、__50 % の確率__ で __行われた__ からです。

また、__合法手 2__ と __3__ の __評価値__ が __同じ__ になる __理由__ は、「__自 2 敵 0 空 1__」と「__自 1 敵 0 空 2__」の __数__ の __合計__ が __等しい__ からであることが __確認__ できました。これは、__ルール 11__ の __意図通り__ の __計算__ です。

## 5 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b996fa05-5840-723e-fa21-2c5ef947d306.png" width="150">

__これまで__ と __同様__ に、下記のプログラムで __`ai10s`__ がそれぞれの __合法手__ に対して __どのように__ 評価値を __計算__ するかを __表示__ し、その __結果__ を __表にまとめます__。

```python
mb.move(1, 2)
ai10s(mb, debug=True)
```

<details><summary><strong>実行結果（長いのでクリックして開いてください）</strong></summary>

```
Start ai_by_score
Turn o
x..
.o.
.Xo

legal_moves [(1, 0), (2, 0), (0, 1), (2, 1), (0, 2)]
====================
move (1, 0)
Turn x
xO.
.o.
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 3,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 2})
score 3 best score -inf
UPDATE
  best score 3
  best moves [(1, 0)]
====================
move (2, 0)
Turn x
x.O
.o.
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 3,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 100 best score 3
UPDATE
  best score 100
  best moves [(2, 0)]
====================
move (0, 1)
Turn x
x..
Oo.
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 3,
             Markpat(last_turn=2, turn=0, empty=1): 1,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 3 best score 100
====================
move (2, 1)
Turn x
x..
.oO
.xo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 2,
             Markpat(last_turn=1, turn=0, empty=2): 1,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 100 best score 100
APPEND
  best moves [(2, 0), (2, 1)]
====================
move (0, 2)
Turn x
x..
.o.
Oxo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=1, turn=0, empty=2): 2,
             Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1,
             Markpat(last_turn=2, turn=1, empty=0): 2})
score 3 best score 100
====================
Finished
best score 100
best moves [(2, 0), (2, 1)]
```
</details>

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

| |  | 「201」 | 「021」 | 「102」 | 評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| | __評価値__ | 1：`+1`<br>2~：`100` | `-100` | 1 つで<br>`+1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7e8cef61-6aa7-83ea-2ba7-c31c592bbf5e.png" width="65">  |  | | 3 | 3 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/d9ea7c27-0456-faf3-f641-e0b8d7d88c1f.png" width="65">  | 2 | | 1 | 100 |
| 3 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/19c9d439-9cb4-0988-b7fd-81267e5dee84.png" width="65">  | 1 | | 2 | 3 |
| 4 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1e733a5a-fb40-5d53-88fb-a097da8144fe.png" width="65">  | 2 | | 1 | 100 |
| 5 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8604ebab-b59f-e354-ae07-a715cbffdcaa.png" width="65">  | 1 | | 2 | 3 |

__表__ から、__`ai10s`__ は、__最も評価値__ が __高い__、__合法手 2__ と __4__ の __いずれかの着手__ を行うことが分かり、そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。__実際__ に __`ai10s`__ はそのうちの片方である __合法手 2__ を __選択__ しました。

```
best score 100
best moves [(2, 0), (2, 1)]
```

__合法手 2__ または __4__ の __着手__ を行うことで、「__自 2 敵 1 空 0__」が __2 つ存在__ するようになるので、__次の手番__ で __`ai10s`__ が __必ず勝利__ できるようになります。従って、__この後__ の __`ai11s`__ の __着手__ に __関わらず__、__この時点__ で __`ai10s`__ の __勝利が確定__ し、__実際の対戦__ でも __`ai10s`__ が __勝利__ しています。そのため、__この後__ の __着手の検証__ を __行う必要はない__ でしょう。

## `ai10s` VS `ai11s` で行われる着手の選択のまとめ

__上記の検証__ から、__`ai10s` VS `ai11s`__ で行われる __着手__ の __選択__ は、__下図__ のようになることが分かります。なお、__同一局面__ がある場合は、__そのうちの一つ__ の __局面のみ__ を __表示__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/5861a470-a3b7-08c6-2c9a-8f84a055516f.png" width="600">

__図__ から __わかる__ ように、__`ai10s` VS `ai11s`__ では、__3 手目まで__ は、__必ず上図__ と __同一局面__ になるような __着手__ が __行われます__。__4 手目__ の __`ai11s`__ の __着手__ で、__50 %__ の __確率__ で __異なる着手__ が __選択__ されます。__4 手目__ で __図__ の __上の着手__ が __行われた場合__ は、__5 手目__ で __`ai10s`__ が __2 通り__ の __着手__ を行う __可能性__ がありますが、__何れの場合__ でも __`ai10s`__ が __100 % 勝利__ します。

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

* __3 手目__ までは、__常に同一局面__ になる __着手__ が行われる
* __4 手目__ で __`ai11s`__ は、それぞれ __50 %__ の __確率__ で __2 通り__ の __着手__ を行う
* __4 手目__ の __`ai11s`__ が、__図__ の __上の着手__ を行った場合は、__`ai10s`__ が __必ず勝利__ する。

このことから、__`ai10s` VS `ai11s`__ の対戦で、__`ai11s`__ が __敗北__ するのは、__4 手目__ で __図__ の __上の着手__ を __行う可能性がある__ ためであることが __推測__ されます。

なお、__4 手目__ の __`ai11s`__ の __着手__ で、__図__ の __下の着手__ が行われた __場合__ に __どうなるか__ は、その __検証__ をまだ __行っていない__ ので __現時点__ では __わかりません__。

長くなったので今回の記事はここまでにします。次回の記事では、__図__ の __下の着手__ が行われた __場合__ の検証と、__`ai11s`__ が __図__ の __上の着手__ を __行わないようにする__ ことで、__`ai10s`__ に __負けないよう__ に __修正__ する __方法__ について __説明__ します。

# 今回の記事のまとめ

今回の記事では、__`ai10s` VS `ai11s`__ で __`ai11s`__ が __負ける原因__ を __調べるため__ に、試合の __棋譜__ を __記録__ するように __`Marubatsu`__ クラスを __修正__ しました。また、その後で、__特定の AI どうし__ で、__特定の結果__ になる __試合経過__ を __表示する関数__ を __定義__ しました。

また、その __関数を利用__ して、__`ai10s` VS `ai11s`__ で行われる __着手__ が __どのように選択されるか__ を __検証__ し、__`ai11s`__ が __敗北する原因__ となる __可能性が高い着手__ を __発見__ しました。

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

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

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

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

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

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

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

# 次回の記事

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

[^1]:将棋やチェスでは、それぞれの __プレイヤー__ は、__特定の方向__ から __ゲーム盤__ を __見ます__。そのため、__ゲーム盤__ を __回転__ したりすると、__同一局面__ では __なくなります__
[^2]:もちろん、検証しても、問題点や解決法が __わからない場合__ もあります