Pythonで〇×ゲームのAIを一から作成する　その63　最善手の優劣

# 目次と前回の記事

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

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/063/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>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール12](https://qiita.com/ysgeso/items/70c50f75319373399871#%E9%99%90%E5%AE%9A%E7%9A%84%E3%81%AA%E6%9D%A1%E4%BB%B6%E3%81%AE%E8%BF%BD%E5%8A%A0%E3%81%AB%E3%82%88%E3%82%8B%E3%83%AB%E3%83%BC%E3%83%AB-12-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __必ず勝利できる__ ように、「__自 2 敵 0 空 1__」が __2 つ以上存在する__ 局面になる着手を行う<br>そうでない場合は、__斜め方向__ に __〇×〇__ が __並び__、__他の 6 マス__ が __空のマス__ の場合に、__いずれか__ の __辺のマス__ に着手を行う<br>そうでない場合は、__以下__ の 3 つを __総合的に判断__ して着手を行う<br><ul><li>__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が __1 つ存在する__ 局面になる着手を行う</li><li>__自分__ が __有利になる__ ように、「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う</li><li>__相手__ が __不利になる__ ように、「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う</li></ul>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[ルール12 改](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#%E3%83%AB%E3%83%BC%E3%83%AB-12-%E6%94%B9%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __相手__ が __勝利できる__ 着手を __行わない__<br>そうでない場合は、__次__ の __自分の手番__ で __必ず勝利できる__ ように、「__自 2 敵 0 空 1__」が __2 つ以上存在する__ 局面になる着手を行う<br>そうでない場合は、__斜め方向__ に __〇×〇__ が __並び__、__他の 6 マス__ が __空のマス__ の場合に、__いずれか__ の __辺のマス__ に着手を行う<br>そうでない場合は、__以下__ の 3 つを __総合的に判断__ して着手を行う<br><ul><li>__次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が __1 つ存在する__ 局面になる着手を行う</li><li>__自分__ が __有利になる__ ように、「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う</li><li>__相手__ が __不利になる__ ように、「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う</li></ul>そうでない場合は __ランダム__ なマスに __着手__ する |

__ルール 11、12__ で __評価値を計算__ する際の __パラメータ__ は以下の通りです。

|  | `ai11s`<br>ver 1 | `ai11s`<br> ver 2 | `ai11s` ver 3<br>`ai12s` |
|:-:|:-:|:-:|:-:|
| __「自 2 敵 0 空 1」が 1 つの場合の評価値__  | 1  | 2 | 2 |
| __「自 1 敵 0 空 2」が 1 つあたりの評価値__ | 1  | 1 | 0.5 |
| __「自 0 敵 1 空 2」が 1 つあたりの評価値__ | -1 | -1 | 1 |


基準となる __`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` ver 1](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` ver 2](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#ai11s-%E3%81%AE%E4%BF%AE%E6%AD%A3)__ | __98.8__ | __0.0__ | 1.2 | __87.7__ | __2.4__ | 10.0 | __93.2__ | __1.2__ | 5.6 | |
| __[`ai11s` ver 3](https://qiita.com/ysgeso/items/70c50f75319373399871#%E4%BF%AE%E6%AD%A3%E3%81%97%E3%81%9F%E3%83%91%E3%83%A9%E3%83%A1%E3%83%BC%E3%82%BF%E3%81%A7%E3%81%AE-ai2-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6)__  | __99.1__ | __0.0__ | 0.9 | __87.7__ | __0.8__ | 11.5 | __93.4__ | __0.4__ | 6.2 | |
| __[`ai12s` ver 2](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#ai12s-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E7%A2%BA%E8%AA%8D)__  | __98.9__ | __0.0__ | 1.1 | __88.2__ | __0.0__ | 11.8 | __93.5__ | __0.0__ | 6.5 | |
| __[`ai12s` ver 3](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6)__  |  __95.8__ | __0.0__ | 4.2 | __86.9__ | __0.0__ | 13.1 | __91.3__ | __0.0__ | 8.7 | あり |

# `ai12s` ver 2 VS `ai2` と `ai12s` ver 3 VS `ai2` の違いの検証 

[前回の記事](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6)では、「__勝てる場合__ に __勝つ__」と、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』に対する __評価値__ に __どちらも 200__ に __設定__ した __`ai12s` ver 3__ を作成しましたが、その際に、下記の表のように、__`ai12s` ver 2__ VS __`ai2`__ と __比較__ して、__`ai12s` ver 3__ VS __`ai2`__ のほうが __引き分け率__ が __増えてしまう__ という __バグが発生__ することが __わかりました__。


| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __[`ai12s` ver 2](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#ai12s-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E7%A2%BA%E8%AA%8D)__  | __98.9__ | __0.0__ | 1.1 | __88.2__ | __0.0__ | 11.8 | __93.5__ | __0.0__ | 6.5 |
| __[`ai12s` ver 3](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%81%AA-ai-%E3%81%A8%E3%81%AE%E5%AF%BE%E6%88%A6)__  |  __95.8__ | __0.0__ | 4.2 | __86.9__ | __0.0__ | 13.1 | __91.3__ | __0.0__ | 8.7 |

また、__[対戦を検証](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#ai12s-ver-2-vs-ai2-%E3%81%A8-ai12s-ver-3-vs-ai2-%E3%81%AE%E9%81%95%E3%81%84%E3%81%AE%E8%A1%A8%E7%A4%BA)__ することで、__`ai12s` ver 3__ の __バグの原因__ となっている __局面を発見__ しました。今回の記事では、最初にその __バグの原因__ を __検証__ します。

下図は、前回の記事で発見した、__結果__ が __異なる `ai12s` ver 2__ VS __`ai2`__ と __`ai12s` ver 3__ VS __`ai2`__  の __試合経過__ を __上下に並べた__ ものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7f30dd96-e7b0-276b-cc72-cb229849668d.png" width="700">

図から、__同じ[乱数の種](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#%E4%B9%B1%E6%95%B0%E3%81%AE%E7%A8%AE)__ を使っているため、__4 手目まで__ は __同じ着手__ が __選択__ されていることが __わかります__。そこで、__5 手目以降__ の __`ai12s` ver2__ と __ver 3__  の __着手を検討__ することにします。なお、__`ai2`__ は __ランダムな着手__ を行う __AI__ なので、__`ai2`__ の __着手の検討__ は __省略__ します。

## 5 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/83f4a1b8-9feb-432f-07c2-c6f7cb36d91f.png" width="140">

__`ai12s` ver 2__ は、「__勝てる場合__ に __勝つ__」という __条件__ の __評価値__ が __最も高い__ ので、__上記の局面__ で __(0, 2)__ に __着手__ して __勝利__ します。特に難しい点はないでしょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/350cf81d-6d27-b8df-b7a8-65eceff3a048.png" width="140">

次に、__`ai12s` ver 3__ が __上記の局面__ で __計算__ する __評価値__ を下記のプログラムで __表示__ します。

```python
from marubatsu import Marubatsu
from ai import ai12s

mb = Marubatsu()
mb.move(1, 1)
mb.move(2, 1)
mb.move(2, 0)
mb.move(2, 2)
ai12s(mb, score_victory=200, debug=True)
```

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

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

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

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): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 200 best score -inf
UPDATE
  best score 200
  best moves [(0, 0)]
====================
move (1, 0)
Turn x
.Oo
.ox
..x

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=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 3})
score 200 best score 200
APPEND
  best moves [(0, 0), (1, 0)]
====================
move (0, 1)
Turn x
..o
Oox
..x

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): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 1,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 2.5 best score 200
====================
move (0, 2)
winner o
..o
.ox
O.x

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

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

</details>

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

| |  | 勝利 |「201」 | 「021」 | 「102」 | 「012」 | 評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| | __評価値__ | `200` | 1：`+2`<br>2~：`200` | `-100` | 1 つで<br>`+0.5` | 1 つで<br>`-1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/21e84a6e-90f0-b920-6333-bb5bbf67f171.png" width="65">  |  | 2 |  | 2 | 1 | 200 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a7e243fc-5b73-af33-2371-bd56e0ef9ad6.png" width="65">  |  | 3 |  |  | 1 | 200 |
| 3 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/c0e02564-8de2-119e-1deb-9d619a6ccbb2.png" width="65">  |  | 1 |  | 3 | 1 | 2.5 |
| 4 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/28c8e200-11e8-22d2-9510-851e232db859.png" width="65">  | 1 | |  | 3 |  | 200 |
| 5 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/992cedcb-842a-864e-0c9d-0ac59ba0dd9c.png" width="65">  |  | 2 |  | 1 |  | 200 |

__`ai12s` ver 3__ は、「__勝てる場合__ に __勝つ__」と、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』に対する __評価値__ が __どちらも 200__ に __設定__ されており、__上記の表__ でも __そのようになっています__。そのため、__この局面__ では、__勝利__ する __合法手 4__ だけでなく、__合法手 1__、__2__、__5__ の __評価値__ も __200__ になるため、__合法手 1__、__2__、__4__、__5__ の __中から__ ランダムに __選択__ が行われることが __わかります__。そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。

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

:::note
「__勝てる場合__ に __勝つ__」と、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という __条件__ の __評価値__ は、__ヒューリスティック__ な __条件より__ も __優先順位が高い__ ため、__ヒューリスティックな条件__ による __評価値__ は __考慮されない__ ので __200__ に __なります__。
:::

従って、__上記の局面__ では、1 / 4 = __25 %__ の __確率__ で __(1, 2)__ が __選択__ されたことが __わかります__。

## 7 手目の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8077c167-022f-b396-b61a-cf09cdb2b879.png" width="140">

__`ai12s` ver 3__ が、__上記の局面__ で __計算__ する __評価値__ を __下記__ のプログラムで __表示__ します。

```python
mb.move(1, 2)
mb.move(0, 2)
ai12s(mb, score_victory=200, debug=True)
```

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

```
Start ai_by_score
Turn o
..o
.ox
Xox

legal_moves [(0, 0), (1, 0), (0, 1)]
====================
move (0, 0)
Turn x
O.o
.ox
xox

defaultdict(<class 'int'>,
            {Markpat(last_turn=1, turn=1, empty=1): 2,
             Markpat(last_turn=1, turn=2, empty=0): 2,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 2})
score 200 best score -inf
UPDATE
  best score 200
  best moves [(0, 0)]
====================
move (1, 0)
winner o
.Oo
.ox
xox

score 200 best score 200
APPEND
  best moves [(0, 0), (1, 0)]
====================
move (0, 1)
Turn x
..o
Oox
xox

defaultdict(<class 'int'>,
            {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): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1,
             Markpat(last_turn=2, turn=1, empty=0): 2})
score 2.5 best score 200
====================
Finished
best score 200
best moves [(0, 0), (1, 0)]
```

</details>

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

| |  | 勝利 |「201」 | 「021」 | 「102」 | 「012」 | 評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| | __評価値__ | `200` | 1：`+2`<br>2~：`200` | `-100` | 1 つで<br>`+0.5` | 1 つで<br>`-1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/00fcdb4c-151e-3909-2269-193bba57c48e.png" width="65">  |  | 2 |  |  |  | 200 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/605fa92b-25e6-8b91-9026-bf3401255268.png" width="65">  | 1 | 1 |  |  | 1 | 200 |
| 3 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f04e7c52-6d38-7bb0-36a4-d4945062b6e6.png" width="65">  |  | 1 |  | 1 |  | 2.5 |

__上記__ から、__合法手 1__、__2__ の __評価値__ が __200__ で __最も高い__ ので、__その中__ から __合法手が選択__ されることが __わかります__。そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。

```
best score 200
best moves [(0, 0), (1, 0)]
```

従って、__上記の局面__ は、1 / 2 = __50 %__ の __確率__ で __(0, 0)__ が __選択__ されたことが __わかります__。

## 8 手目以降の検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7d80e04f-d0f9-d2de-eb96-dfcc7d87532b.png" width="210">

上記は、__8 手目以降__ の __図__ ですが、__7 手目__ で __`ai12s` ver 3__ が、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という __条件を満たす__、__必勝の局面__ での __最善手__ を __選択__ したにもかかわらず、__引き分け__ に __なっています__。何故このようなことが起こったかについて少し考えてみて下さい。

上記の __`ai2`__ が __8 手目__ で __着手__ した __(1, 0)__ は、__1 回__ の __着手__ で、__2 つ__ ある「__自 2 敵 0 空 1__」の __マークのパターン__ を __同時__ に __無くしています__。これが、__引き分け__ になる __原因__ です。

このことから、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という __条件__ は、実は __必勝の局面__ での __最善手__ を __選択__ するための __[十分条件](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#%E5%8D%81%E5%88%86%E6%9D%A1%E4%BB%B6) ではなかった__ ことが __わかります__。

__この条件__ の __問題点__ は、__一度__ の __相手の着手__ で、__複数__ の「__自 2 敵 0 空 1__」の __マークのパターン__ が __同時になくなる__ 場合があることですが、そのようなことが起きるのは、__複数__ の「__自 2 敵 0 空 1__」の __マークのパターン__ の中の __空のマス__ が __1 つ__ で __共通している__ ような __場合__ です。

__図で説明__ すると、__下図__ の __7 手目__ の局面では、「__自 2 敵 0 空 1__」の __マークのパターン__ が __黄色い行__ と __オレンジの列__ の __2 つ__ が __あります__ が、それぞれの __マークのパターン__ の中の __空のマス__ は、__緑__ の __(0, 1)__ の __マス__ で __共通__ しており、__1 つ__ しかありません。この場合は、__相手__ が __緑のマス__ に __着手__ を行うことで、「__自 2 敵 0 空 1__」の __マークのパターン__ が __無くなります__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8116bb8d-8a70-97c4-7354-334b5f67dea6.png" width="65">

従って、__この条件__ を __必勝の局面__ で __最善手__ を __選択__ するための __十分条件にする__ ためには、__下記__ の __2 つ目__ の __条件__ を __加える__ ように __修正__ する __必要__ が __あります__。

* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う
* ただし、それらの __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する

ところで、__`ai12s` ver 2__ と __`ai12s` ver 3__ は、__どちらもルール 12__ の __条件__ で __合法手__ を __選択__ していますが、__ルール 12__ には、__上記__ の「それらの __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する」という __条件__ は __存在しません__。それにもかかわらず、__`ai12s` ver 2__ VS __`ai2`__ では、上図のような、__問題__ のある __局面__ は __出現しません__。

その __理由__ について __検証__ してみた所、__`ai12s` ver 2__ が『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手』を __行った場合__ に、__上記__ の __2 つ目__ の「それらの __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する」という __条件__ を __必ず満たす__ ことが __判明__ しました。

次は、そのようなことがおきる __理由__ について __説明__ します。

## `ai12s` ver 2 が条件を満たす理由

__`ai12s` ver 2__ が『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手』を __行った場合__ に、__上記__ の __2 つ目の条件__ を __必ず満す__ ことを __示す__ ための __方法の一つ__ に、__`ai12s` ver 2__ が __上記の条件__ に __反する__、__下記__ のような __合法手__ を __選択しない__ ことを __示す__ という __方法__ が __あります__。

* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う
* ただし、それらの __マークのパターン__ の中の __空のマス__ が、__1 つだけ存在__ する

下記は、__上記の条件__ を満たす __`ai12s` ver 3__ VS __`ai2`__ の __7 手目__ を __選択__ した __局面__ です。__緑色__ のマスが、「__自 2 敵 0 空 1__」の __マークのパターン__ で、__1 つ__ だけ __存在__ する __空のマス__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8116bb8d-8a70-97c4-7354-334b5f67dea6.png" width="65">

__〇×ゲーム__ は、__一度__ の __手番__ で、__一つのマス__ にしか __着手__ を行えない __ゲーム__ なので、__上記の局面__ の、__1 つ前__ の __〇 の手番__ である __5 手目__ の __局面__ では、__4 つ__ ある __〇 のマーク__ の中の、__いずれか 1 つ__ が __配置されていない状態__ になっています。そのため、__1 つ前__ の __〇 の手番__ の __局面__ は、__以下__ の __いずれか__ に __なります__。

* __黄色__ の __マス__ の __いずれか 1 つ__ の __〇__ が __配置されていない__
* __オレンジ__ の __マス__ の __いずれか 1 つ__ の __〇__ が __配置されていない__

__上記__ の __いずれの場合__ であったとしても、__1 つ前__ の __〇 の手番__ の __局面__ では、__他の色__ の __2 つのマス__ に __〇 が配置__ されています。また、__緑のマス__ も、必ず __空のマス__ なので、__1 つ前__ の __〇 の手番__ の __局面__ では、必ず「__自 2 敵 0 空 1__」が __1 つ存在__ することになります。

__実際__ に、先程の __`ai12s` ver 2__ VS __`ai2`__ の __5 手目__ の局面では、__(0, 0)__ の __マス__ が __空いています__ が、__オレンジ色__ の __列__ に「__自 2 敵 0 空 1__」が __1 つ存在__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/91cea2ff-3c48-eccf-adf3-4cd6d4b8ccf5.png" width="65">

__下記__ のような __条件__ を満たす __合法手を選択__ するためには、__上図__ の __局面__ で __(0, 0)__ に __着手__ を __行う必要__ が __あります__。

* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う
* ただし、それらの __マークのパターン__ の中の __空のマス__ が、__1 つだけ存在__ する

__`ai12s` ver 2__ は、「__勝てる場合__ に __勝つ__」という __条件__ が __最も優先順位__ が __高い__ ので、__上図の局面__ では __必ず (0, 1)__ に __着手__ して __勝利__ します。従って、__`ai12s` ver 2__ が __合法手__ を __選択__ する場合に、__上記__ のような __条件__ を満たす __合法手__ を __選択__ することは __ありません__。

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

* 『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という __条件だけ__ では、__必勝の局面__ で __最善手__ を __選択__ するための __十分条件__ には __ならない__
* 「__勝てる場合__ に __勝つ__」という __条件__ を、__上記の条件__ よりも __優先順位__ を __高くする__ ことで、__上記の条件__ が __十分条件__ に __なる__

__`ai12s` ver 3__ は、__上記__ の __条件__ を __満たさない__ ため、先程の __7 手目__ の局面のように、__`ai12s` ver 2__ が __最善手__ を __必ず選択__ する __局面__ で、__最善手__ を __選択できず__ に __引き分け__ に __なる場合__ が __あります__。これが、__`ai12s` ver 2__ VS __`ai2`__ と __比較__ して、__`ai12s` ver 3__ VS __`ai2`__ のほうが __引き分け率__ が __増えてしまう__ という __バグ__ の __原因__ です。

なお、__`ai12s` ver 2__ が、__上記__ で __説明__ した __理由__ から、__必勝の局面__ で __最善手__ を __選択__ するための __十分条件__ になっていることは、__筆者__ も __想定しておらず__、前回の記事で __`ai12s` ver 3__ の __問題__ が __見つかるまで__ は、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という __条件だけ__ で、__十分条件__ に __なっている__ と __勘違い__ していました。そのため、__`ai12s` ver 2__ が __必勝の局面__ で __最善手__ を __必ず選択__ するように __なっていた__ のは、__単なる偶然__ に __すぎません__。

:::note warn
このように、__ルールベースの AI__ では、__正しい__ と __思っていた条件__ が 実は __正しくなかった__ ということが __良くあります__。そのため、作成した __AI__ による __対戦__ が __意図通り__ の __結果__ に __ならなかった場合__ は、__プログラム__ だけでなく、__ルール__ の __条件__ を __見直す必要__ がある __場合がある__ ことを __忘れない__ ようにして下さい。
:::

:::note
__ルール 12__ の、「__相手__ が __勝利できる__ 着手を __行わない__」という __条件__ が『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という __条件より__ も __優先順位__ が __高い__ ことは、上記と __同じ__ ような __意味__ を __持ちます__。もし、「__相手__ が __勝利できる__ 着手を __行わない__」という __条件__ の __優先順位__ を __低くしてしまう__ と、__次__ の __相手の手番__ で __相手__ が __勝利__ してしまう __可能性が生じる__ からです。

従って、__厳密__ には、先程の __必勝の局面__ で __最善手__ を __選択__ するための __十分条件__ は __以下__ のようになります。

* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う
* ただし、「__勝てる場合__ に __勝つ__」や「__相手__ が __勝利できる__ 着手を __行わない__」という __条件__ を __優先__ する

なお、__記述__ が __長くなる__ ので、「__相手__ が __勝利できる__ 着手を __行わない__」という __条件の記述__ は __以後__ も __省略__ することにします。
:::

## 2 つの十分条件の違い

下記は、最初に紹介した __必勝の局面__ で __最善手__ を __選択__ するための __十分条件__ です。

* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う
* ただし、それらの __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する

一方、__下記の条件__ を __満たした場合__ に、__上記の条件__ が __満たされる__ ので、__下記の条件__ も、__必勝の局面__ で __最善手__ を __選択__ するための __十分条件__ であると言えます。

* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う
* ただし、「__勝てる場合__ に __勝つ__」という __条件__ を __優先__ する[^1]

このように、__同じ問題__ に対して、その __問題を解決__ するための __異なる十分条件__ が __考えられる__ ことが __あります__ が、そのような場合は、__どちらの十分条件__ を使っても __構わない__ ので、__使いやすい__ ほうを __利用__ すると __良いでしょう__。

例えば、__`ai12s` ver 2__ は、上記の __後者__ の __十分条件__ を __利用__ していますが、「__勝てる場合__ に __勝つ__」という __条件__ を __優先する処理__ は、__簡単__ に __記述できます__。

一方、__前者__ の __十分条件__ の、「それらの __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する」という __条件__ を __利用__ して __最善手を選択__ することも __でき__、そちらの場合には、__下記__ のような __利点__ と __欠点__ があります。

__利点__

* 「__勝てる場合__ に __勝つ__」場合と、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』場合の __評価値__ に __同じ値__ を __設定__ しても、__`ai12s` ver 3__ のような __問題__ は __発生しない__

__欠点__

* 「__自 2 敵 0 空 1__」の __マークのパターン__ の中の __空のマス__ の __数を数える__ プログラムの __記述__ はそれほど __簡単ではなく__、__処理__ が __複雑になる__ ため __処理時間__ が __長く__ なる

なお、この後で説明しますが、それぞれの __評価値__ に __同じ値__ を __設定__ すると __別の問題__ が __発生する__ ことになるため、__上記の利点__ はあまり __有効__ では __ありません__。そのため、__本記事__ では __前者の十分条件__ によるプログラムは __記述しない__ ことにします。興味と時間がある方は、実際にプログラムを記述してみると良いでしょう。

## `ai12s` ver 2 と `ai12s` ver 3 の優劣

__`ai12s` ver 3__ には、__上記__ で __説明__ したような __問題点__ がありますが、__ランダムな AI__ に対する __敗率__ が __0 %__  であることから、__弱解決の AI__ であることには __変わりはありません__。

このような __問題点__ があるにも __関わらず__、__`ai12s` ver 3__ が __弱解決の AI__ である __理由__ は、__〇×ゲーム__ が __引き分けのゲーム__ だからです。[以前の記事](https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34#%E5%BC%B1%E8%A7%A3%E6%B1%BA%E3%81%AE-ai-%E3%81%AE%E6%80%A7%E8%B3%AA%E3%81%AE%E3%81%BE%E3%81%A8%E3%82%81)で説明したように、__引き分けのゲーム__ での __弱解決の AI__ は、__必勝の局面__ では、__必敗の局面__ につながる __合法手__ を __選択しない__ という __制約しかない__ ので、__最善手ではない__、__引き分け__ に __つながる合法手__ を __選択__ しても __かまいません__。先ほどの __7 手目__ の __局面__ では、__`ai12s` ver3__ は、__必勝の局面__ で、__最善手ではない__、__引き分け__ につながる __合法手__ を __選択__ しているので、__弱解決の AI__ の __条件__ を __満たしています__。

__弱解決の AI__ は __自分の必勝のゲーム__ では、__最強の AI__ と __同じ強さ__ を持ちますが、__そうでない__ 場合は、このように、__弱解決の AI どうし__ の中で、__優劣__ は __存在__ します。実際に、__`ai12s` ver 2 より__ も、__`ai12s` ver 3 のほう__ が、__最強の AI__ に __近い AI__ です。従って、__本記事__ では __`ai12s` ver 3__ の __パラメータ__ は __採用しない__ ことにします。

# 必勝の局面での最善手の優劣

下記の __2 つの条件__ は、__いずれも__、__必勝の局面__ で __最善手__ を __選択__ するための __十分条件__ です。

* __勝てる場合__ に __勝つ__
* 「__自 2 敵 0 空 1__」の __マークのパターン__ が __2 つ以上存在__ し、それらの __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する __合法手__ を __選択__ する

従って、それらの __条件__ を満たす __合法手__ が __両方存在__ する場合は、その __どちらを選択__ しても、__AI の強さ__ という __観点__ からは、__強さ__ は __変わりません__。

しかし、__AI__ と __人間__ が __対戦__ する場合に、__人間にとって__、__一般的__ に __どちらの最善手__ が __好ましく思えるか__ という __観点__ では、この __2 種類__ の __最善手__ は __異なります__。

## 人間にとって最善手に違いが生じる例

__具体例__ を示します。__下図__ の __〇 の手番__ の __局面__ では、__黄色__ の __(2, 2)__ に __着手__ すると __〇 が勝利__ するので、__(2, 2)__ は __最善手__ です。また、__オレンジ__ の __4 つ__ のマスのどこに __着手__ を行っても、『「__自 2 敵 0 空 1__」の __マークのパターン__ の中の __空のマス__ が、__2 つ以上存在__ する』ので、それらも __最善手__ です。つまり、__この局面__ では __すべて__ の __合法手__ が __最善手__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/200c0231-1ef9-c451-2080-3e6cbc0d263b.png" width="65">

__`ai12s` ver 2__ は、「__勝てる場合__ に __勝つ__」という __条件__ が __優先される__ ので、__(2, 2) のみ__ を __選択__ します。そのことは、__下記__ のプログラムの __実行結果__ の __最後の行__ からも __確認できます__。

```python
mb = Marubatsu()
mb.move(1, 1)
mb.move(1, 0)
mb.move(0, 0)
mb.move(1, 2)
ai12s(mb, debug=True)
```

実行結果の __最後の行__

```
best moves [(2, 2)]
```
<details><summary><strong>実行結果全体（長いのでクリックして開いてください）</strong></summary>

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

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

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=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 200 best score -inf
UPDATE
  best score 200
  best moves [(2, 0)]
====================
move (0, 1)
Turn x
ox.
Oo.
.x.

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): 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): 3})
score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1)]
====================
move (2, 1)
Turn x
ox.
.oO
.x.

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): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 2})
score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1), (2, 1)]
====================
move (0, 2)
Turn x
ox.
.o.
Ox.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             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): 3})
score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1), (2, 1), (0, 2)]
====================
move (2, 2)
winner o
ox.
.o.
.xO

score 300 best score 200
UPDATE
  best score 300
  best moves [(2, 2)]
====================
Finished
best score 300
best moves [(2, 2)]
```
</details>


一方、__2 種類__ の __最善手__ の __評価値__ が __同じ__ である __`ai12s` ver 3__ の場合は、__すべての合法手__ の __評価値__ が __同じ値__ になる[^2]ので、__すべての合法手__ の中から __ランダム__ に __選択__ が行われます。そのことは、__下記__ のプログラムの __実行結果__ の __最後の行__ からも __確認できます__。

```python
ai12s(mb, score_victory=200, debug=True)
```

```python
from ai import ai12s
from marubatsu import Marubatsu

mb = Marubatsu()
mb.move(1, 1)
mb.move(1, 0)
mb.move(0, 0)
mb.move(1, 2)
ai12s(mb, debug=True)
```

実行結果の __最後の行__

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

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

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

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

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=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 2,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score 200 best score -inf
UPDATE
  best score 200
  best moves [(2, 0)]
====================
move (0, 1)
Turn x
ox.
Oo.
.x.

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): 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): 3})
score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1)]
====================
move (2, 1)
Turn x
ox.
.oO
.x.

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): 1,
             Markpat(last_turn=1, turn=2, empty=0): 1,
             Markpat(last_turn=2, turn=0, empty=1): 2})
score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1), (2, 1)]
====================
move (0, 2)
Turn x
ox.
.o.
Ox.

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=0, empty=3): 1,
             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): 3})
score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1), (2, 1), (0, 2)]
====================
move (2, 2)
winner o
ox.
.o.
.xO

score 200 best score 200
APPEND
  best moves [(2, 0), (0, 1), (2, 1), (0, 2), (2, 2)]
====================
Finished
best score 200
best moves [(2, 0), (0, 1), (2, 1), (0, 2), (2, 2)]
```
</details>

## 人間の心理を考慮に入れた最善手の優劣

ところで、__人間 どうし__ が __〇×ゲーム__ で __対戦__ する際に、__下図の局面__ で、__相手__ が __オレンジ色__ のマスに __着手__ を行った場合、おそらく __多くの人__ は、その場で __すぐに勝てる局面なのに__、わざわざ別の合法手を選択して __勝負を引き延ばされた__ と思い、__気分が悪くなる人__ が __多い__ のではないでしょうか[^3]。__人間どうし__ の対戦では、このような、__勝利が確定__ している局面で __勝負を引き延ばす__ ような __行為__ の事を、__なぶり殺し__ や、__舐めプ__（相手を __舐めたプレイ__ の __略__）などと呼び、__一般的__ には __マナーが悪い行為__ だと考えられています[^4]。また、そのような行為を行うと、場合によっては __喧嘩に発展する__ ことも __あります__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/200c0231-1ef9-c451-2080-3e6cbc0d263b.png" width="65">

先程示したように、__`ai12s` ver 2__ は、__上記の局面__ で __必ず黄色__ のマスに __着手__ を行って __勝利します__ が、__`ai12s` ver 3__ は __オレンジ色__ のマスに __着手__ をする __可能性__ が __あります__。__`ai12s` ver 3__ は、__決められたルール__ に従って __着手を選択__ しているだけなので、__相手__ を __侮辱する意図__ は __ありません__ し、先程も述べたように、__相手に勝利する__ という __意味__ では、__どの最善手__ を __選択__ しても __同じ結果__ になりますが、__相手__ が __AI__ であると __わかっていても__、__そのような着手__ を行う __AI__ と __対戦__ した際に、__多くの人間__ は __気分を害する__ のではないかと思います。

このように、__人間__ には __感情がある__ ため、__人間と対戦__ することを __想定した AI__ を __作成する場合__ は、__勝負を引き延ばす__ ような __最善手__ を __選択しない__ ようにしたほうが __良いでしょう__。そのためには、__勝負を長引かせない__ ような __最善手__ に __高い評価値__ を __設定する__ ことに __大きな意味__ が __生じます__。なお、__AI どうし__ でしか __対戦__ を __行わない__ のであれば、そのようなことを __気にする必要__ は __ありません__。

本記事では、作成した __AI__ と __人間__ が __対戦__ することも __想定__ しているので、そのような意味でも、`ai12s` ver 3 を採用せずに、__`ai12s` ver 2__ のほうを __採用する__ ことにします。

# 必敗の局面での最善手の優劣

[以前の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E4%B8%80%E8%88%AC%E7%9A%84%E3%81%AA%E6%84%8F%E5%91%B3%E3%81%AE%E6%9C%80%E5%96%84%E3%81%A8%E6%9C%80%E5%96%84%E6%89%8B%E3%81%AE%E6%84%8F%E5%91%B3%E3%81%AE%E9%81%95%E3%81%84)で説明したように、__必敗の局面__ では、__すべての合法手__ が __最善手__ になりますが、__それらの合法手__ に __優劣__ は __存在するでしょうか__？その点について少し考えてみて下さい。

__相手__ が __最強の AI__ の場合は、__必敗の局面__ の __合法手__ に __優劣__ は __ありません__ が、__相手__ が __最強の AI でない__ 場合は、__優劣__ が __存在__ します。例えば、__下図__ の __× の手番__ の __局面__ は、__次__ の __相手の手番__ で __オレンジ色__ の __いずれか__ に __着手__ を行うと __相手が勝利__ するので、__必敗の局面__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f578fa9a-fd21-fbbb-75c5-43f703e4b384.png" width="65">

従って、__相手__ が __最強の AI__ の場合は、__この局面__ で __×__ が __どの合法手__ を __選択__ しても、__敗北する__ ので、__結果__ は __変わりません__。__実際__ に __`ai12s` ver 2__ は、__下記__ のプログラムの __実行結果__ の __最後の行__ からわかるように、__すべての合法手__ の中から __ランダム__ に __選択__ を __行います__。

```python
mb.restart()
mb.move(1, 1)
mb.move(0, 0)
mb.move(2, 2)
mb.move(2, 1)
mb.move(1, 2)
ai12s(mb, debug=True)
```

実行結果の __最後の行__

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

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

```
Start ai_by_score
Turn x
x..
.ox
.Oo

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=0, turn=2, empty=1): 1,
             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): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -100 best score -inf
UPDATE
  best score -100
  best moves [(1, 0)]
====================
move (2, 0)
Turn o
x.X
.ox
.oo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=2, empty=1): 2,
             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,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score -100 best score -100
APPEND
  best moves [(1, 0), (2, 0)]
====================
move (0, 1)
Turn o
x..
Xox
.oo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=0, turn=2, empty=1): 2,
             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,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score -100 best score -100
APPEND
  best moves [(1, 0), (2, 0), (0, 1)]
====================
move (0, 2)
Turn o
x..
.ox
Xoo

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

## ランダムな AI と対戦する場合の、必敗の局面での最善手の優劣の検証

一方、__相手__ が __最強の AI でない__ 場合は、__×__ が __下図__ の __5 手目__ の __局面__ で、__それぞれ__ の __合法手__ を __選択__ した場合の __勝率__ は __異なります__。__実際__ に、__それぞれ__ の __合法手__ を __選択__ した際に、__ランダムな AI__ である __`ai2s`__ と __対戦__ した場合の __勝率__ を __検証する__ ことにします。ただし、__7 手目__ の __局面__ では、__×__ は __最善手を選択する__ ものとします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7cee68-f65d-2370-c63e-0812d9d5b77b.png" width="65">

### 5 手目で (1, 0) に着手した場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/fb3f6578-fce4-8fc0-a764-8d821b9e3ed8.png" width="350">

__上図左__ は、__5 手目__ で __×__ が __(1, 0)__ に __着手__ した場合の __局面__ です。__この局面__ で、__〇 を担当__ する __`ai2`__ は、__1/3__ の __確率__ で __上図の合法手__ を __選択__ します。__その後__、__×__ が __最善手__ を __選択__ すると、__上図__ のような __結果__ に __なります__。

### 5 手目で (2, 0) に着手した場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b83c6e51-5bb5-aee2-f9b1-9b1a025bd135.png" width="280">

__上図左__ は、__5 手目__ で __×__ が __(2, 0)__ に __着手__ した場合の __局面__ です。__この局面__ で、__〇 を担当__ する __`ai2`__ は、__1/3__ の __確率__ で __上図の合法手__ を __選択__ します。__その後__、__×__ が __最善手__ を __選択__ すると、__上図__ のような __結果__ に __なります__。

### 5 手目で (0, 1) に着手した場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f00659cf-effc-658c-b6f7-0fdf846ef410.png" width="280">

__上図左__ は、__5 手目__ で __×__ が __(0, 1)__ に __着手__ した場合の __局面__ です。__この局面__ で、__〇 を担当__ する __`ai2`__ は、__1/3__ の __確率__ で __上図の合法手__ を __選択__ します。__その後__、__×__ が __最善手__ を __選択__ すると、__上図__ のような __結果__ に __なります__。

### 5 手目で (0, 2) に着手した場合

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b84bc512-2a21-66e2-79df-99f9747aa477.png" width="350">

__上図左__ は、__5 手目__ で __×__ が __(0, 2)__ に __着手__ した場合の __局面__ です。__この局面__ で、__〇 を担当__ する __`ai2`__ は、__1/3__ の __確率__ で __上図の合法手__ を __選択__ します。__その後__、__×__ が __最善手__ を __選択__ すると、__上図__ のような __結果__ に __なります__。

### 5 手目の合法手のまとめ

__下記__ は、__上記__ の __5 手目__ の __それぞれの合法手__ を __選択__ した場合の __勝率__ を __まとめた表__ です[^5]。表から、__選択__ した __合法手__ によって、__敗率__ と __引き分け率__ が __変化__ し、この場合は __合法手 1__、__4__ の、__(1, 0)__ と __(0, 2)__ を __選択__ したほうが __通算成績__ が __良い__ ことが __わかります__。

||  | 勝率 | 敗率 | 引分率 |
|:-:|:-:|--:|--:|--:|
|1| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7b24d05d-924e-6440-7275-fa5770b0b94c.png" width="65">  | 33 %  | 33 %  | 33 %  |
|2| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/87db1e04-4f79-3a8d-06b7-0554c9b44e52.png" width="65">  | 33 %  | 66 %  |  0 % |
|3| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e64e8668-76c6-d1fe-5f73-7b07bc803030.png" width="65">  | 33 %  | 66 %  |  0 % |
|4| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0ac00ca5-eb97-7b20-e925-1a0cefed4e62.png" width="65">  | 33 %  | 33 %  |  33 %  |

__5 手目__ のそれぞれの __合法手の違い__ は、__その後__ の __相手の選択__ によって、__出現__ する __局面の状況__ が __異なる__ 点にあります。例えば、__合法手 1__、__4__ は、__相手__ の __選択次第__ で、__引き分け__ になる __可能性__ が __生じます__ が、__合法手 2__、__3__ では __そのような可能性__ は __生じません__。

## 人間からみた 5 手目の合法手の違い

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7cee68-f65d-2370-c63e-0812d9d5b77b.png" width="65">

__上図の局面__ は、__`ai12s` ver 2__ から見ると __必敗の局面__ なので、__どの合法手__ を __選択__ しても __結果__ は __変わらない__ と __判断__ して __すべての合法手__ の中から __ランダム__ に __選択__ します。しかし、__〇×ゲーム__ にある程度以上 __親しんだ人__ であれば、__上記__ の __必敗の局面__ でも __あきらめず__ に、__相手__ が __勝利__ できる __合法手を減らす__ ことができる、__(1, 0)__ や __(0, 2)__ を __選択する__ のではないかと思います。また、__この局面__ で __`ai12s` ver 2__ が例えば __(2, 0)__ に __着手__ を __行った場合__ に、__人間から見る__ と、__AI__ が __ゲームを投げ出したよう__ に __感じられる人__ が多いかもしれません。

__上記__ の __局面__ で、__人間から__ みて __最善を尽くす__ ように __見える__、__(1, 0)__ や __(0, 2)__ を __AI__  が __選択する__ ようにするための __方法__ について少し考えてみて下さい。

## 最善手の中の優劣の計算方法

__評価値__ を __利用__ する __アルゴリズム__ で、__必敗の局面__ での、__最善手__ に __優劣をつける__ 方法は、もちろん、__それぞれ__ の __合法手__ の __評価値__ を __異なる値にする__ ことです。__そのため__ には、__必敗の局面__ の __合法手__ の __評価値__ を __どのような計算__ で __異なる値にするか__ を __考える必要__ があるので、少し考えてみて下さい。

### ルール 13 の定義

__現状__ の __`ai12s` ver 2__ は、「__自 0 敵 2 空 1__」の __マークのパターン__ が __1 つ以上__ 存在する __局面__ に対して __必敗の局面__ であると __判断__ し、__-100__ という __評価値__ を __計算__ していますが、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __多い程__、__相手__ が __勝ちやすい__ と __考えること__ が __できます__。そこで、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ に対して、__その数__ が __大きい__ ほうが __評価値__ が __小さくなる__ ように __評価値__ を __計算__ するという __方法__ が __考えられます__。

__そのような方法__ で __評価値__ を __計算__ することで、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が多ければ __多い程__、__評価値__ が __低くなる__ ため、__選択されづらく__ なります。

下記は、__上記__ を __ルール 12 改__ に __加えた__、__ルール 13__ の __定義__ です。具体的には、__優先順位__ が __2__ の __条件__ に『ただし、「__自 0 敵 2 空 1__」の __数__ が __少ない着手__ を __優先__ する』を __加えました__。

| 順位 | 条件 | 種類 |
| :-:|:--|:--|
| 1 | __勝てる場合__ に __勝つ__  | 十分条件  |
| 2 | __相手__ が __勝利できる__ 着手を __行わない__<br>ただし、「__自 0 敵 2 空 1__」の __数__ が __少ない着手__ を __優先__ する | 必要条件  |
| 3 | 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う  | 十分条件  |
| 4 | __斜め方向__ に __〇×〇__ が __並び__、__他の 6 マス__ が __空のマス__ の<br>場合は、__いずれか__ の __辺のマス__ に着手を行う  | 十分条件  |
| 5 | 「__自 2 敵 0 空 1__」が __1 つ存在__ する着手を行う<br>「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う<br>「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う |
| 6 | __ランダム__ なマスに __着手__ する  |   |

### 評価値の設定

次に、__ルール 13__ の、__相手__ が __勝利できる場合__ の __評価値__ を __計算する方法__ を __考える必要__ があります。その方法としては、__下記__ のような __方法__ が __考えられます__。

* 「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ を $z$ とした場合で、$z$ が __1 以上__ の場合に __評価値__ を $-100 × z$ という __式__ で __計算__ する

:::note
__他__ にも、$-100 - 10 × z$ など、__さまざまな式__ が __考えられます__。__本記事__ が __採用する式より__ も __ふさわしい__ と思われる __式があれば__、__そちらを採用__ しても __構いません__。
:::

なお、__上記__ では $-100 × z$ という __式__ で __評価値を計算__ しましたが、$z$ に __乗算__ する __パラメータ__ には、__下記__ のような __条件__ があります。

* __負の値__ である
* __計算__ された __評価値__ の __範囲__ が、__他__ の __優先順位__ の __評価値__ の __範囲__ と __重ならない__

下記は、__そのこと__ を __確認__ するために、__それぞれ__ の __優先順位__ に対する __評価値__ の __範囲__ を __まとめた表__ です。__表__ から、__それぞれ__ の __優先順位__ で __計算__ される __評価値__ の __範囲__ が __重複していない__ ことが __確認__ できます。

| 順位 | 局面の状況 | 個別 | 評価値 | 
|:-:|:--|:-:|:-:|
| 1 | __自分が勝利している__  | | `300` |
| 3 | __「自 2 敵 0 空 1」が 2 つ以上存在する__  | | `200` |
| 4 | __片方__ の __斜め方向__ に __〇×〇__ が __並び__、<br>__いずれか__ の __辺__ の __1 つのマスのみ__ に<br>__× が配置__ されている  | | `100` |
| 5 | __「自 2 敵 0 空 1」が 1 つ存在する__<br>__「自 1 敵 0 空 2」が x 個存在する__<br>__「自 0 敵 1 空 2」が y 個存在する__| `2` (`0～2`)<br>`0.5 * x` (`0～4`)<br>`-y` (`-8~0`) | `-8～6`|
| 2 | __「自 0 敵 2 空 1」が z 個存在する__<br>ただし、__z > 0__ とする | `-100 * z`<br>(`-800 ~ -100`) | `-800 ~ -100` |

### `ai13s` の定義

__`ai12s`__ を __上記の表__ の __方法__ で __評価値を計算__ するように、__修正__ すると、__これまで__ の __`ai12s` ver 2__ や __3__ の __処理__ を __行えなくなってしまう__ ので、新しく __`ai13s`__ という __関数__ を __下記__ のように __定義__ する事にします。また、__上記__ の $z$ に __乗算__ する __パラメータ__ を __実引数__ で __変更できる__ ように、__`ai12s`__ にあった __仮引数 `score_defeat`__ を __そのまま利用__ することにします。

* __10 行目__：「__自 0 敵 2 空 1__」の __マークのパターン__ が __存在する場合__ の __評価値__ を、__上記__ の __計算式__ で __計算する__ ように __修正__ する

```python
 1  from ai import ai_by_score
 2  from marubatsu import Markpat
 3  from pprint import pprint
 4
 5  def ai13s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
 6            score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):  
 7      def eval_func(mb):         
同じなので略
 8          # 相手が勝利できる場合
 9          if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
10              return score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
同じなので略
```

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

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

def ai13s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):         
        # 自分が勝利している場合
        if mb.status == mb.last_turn:
            return score_victory

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            return score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
        # 次の自分の手番で自分が必ず勝利できる場合
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return score_sure_victory
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
            return score_special    

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

    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 Markpat
from pprint import pprint

-def ai13s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
-          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):  
+def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
+          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):  
    def eval_func(mb):         
同じなので略
        # 相手が勝利できる場合
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
-           return score_defeat
+           return score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
同じなので略
```
</details>


### `ai13s` が 5 手目で選択する合法手の確認

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7cee68-f65d-2370-c63e-0812d9d5b77b.png" width="65">

__上図__ の __局面__ で、__`ai13s`__ が __選択__ する __合法手__ を、__下記__ のプログラムで __確認します__。

```python
ai13s(mb, debug=True)
```

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

```
Start ai_by_score
Turn x
x..
.ox
.Oo

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=0, turn=2, empty=1): 1,
             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): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -100 best score -inf
UPDATE
  best score -100
  best moves [(1, 0)]
====================
move (2, 0)
Turn o
x.X
.ox
.oo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=2, empty=1): 2,
             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,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score -200 best score -100
====================
move (0, 1)
Turn o
x..
Xox
.oo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=0, turn=2, empty=1): 2,
             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,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score -200 best score -100
====================
move (0, 2)
Turn o
x..
.ox
Xoo

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

下記は、__先程の表__ に、__それぞれ__ の __合法手__ の「__自 0 敵 2 他 1__」の __マークのパターン__ の __数__ と、__上記__ の __実行結果__ に表示された __評価値__ を __加えた__ ものです。

||  | 勝率 | 敗率 | 引分率 | 「021」 | 評価値 |
|:-:|:-:|--:|--:|--:|--:|--:|
|1| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7b24d05d-924e-6440-7275-fa5770b0b94c.png" width="65">  | 33 %  | 33 %  | 33 %  | 1 |-100 |
|2| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/87db1e04-4f79-3a8d-06b7-0554c9b44e52.png" width="65">  | 33 %  | 66 %  |  0 % | 2 |-200 |
|3| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e64e8668-76c6-d1fe-5f73-7b07bc803030.png" width="65">  | 33 %  | 66 %  |  0 % | 2 | -200 |
|4| <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0ac00ca5-eb97-7b20-e925-1a0cefed4e62.png" width="65">  | 33 %  | 33 %  |  33 %  | 1 | -100 |

__表__ から、__合法手 1__、__4__ の __(1, 0)__ と __(0, 2)__ の __評価値__ が __最も高い -100__  になり、__この 2 つ__ の __合法手のみ__ が __選択される__ ようになったことが __確認__ できました。また、そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。

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

上記から、__`ai13s`__ が、__`ai12s` ver 2 より__ も、__上記の局面__ で、__相手によって__ は __成績__ が __良くなる可能性__ が __高くなる__ ような __合法手__ を __選択するようになった__ ことが __確認__ できました。

### `ai2` との対戦

__下記__ のプログラムで、__ランダムな AI__ である __`ai2` と対戦__ してみることにします。

```python
from ai import ai_match, ai2

ai_match(ai=[ai13s, ai2])

```

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

```
ai13s VS ai2
count     win    lose    draw
o        9888       0     112
x        8850       0    1150
total   18738       0    1262

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.5%    0.0%   11.5%
total   93.7%    0.0%    6.3%
```

__実行結果__ から、__敗率__ が __0 %__ であることが __確認__ できたので、__`ai13s`__ は __弱解決の AI__ である __可能性が高い__ ことが __わかりました__。

__下記__ は、__上記__ の __実行結果__ に、__`ai12s` ver 2__ VS __`ai2`__ の __対戦結果__ を __加えた__ ものです。__実行結果__ から、__通算成績__ はどちらも __ほぼ同じ__ であることが分かりました。本当は __`ai13s` VS `ai2` のほう__ が __成績__ が __良くなる__ ことを __期待していた__ のですが、__そうはなりません__ でした。__成績__ が __変わらない原因__ について少し考えてみて下さい。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __[`ai12s` ver 2](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#ai12s-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E7%A2%BA%E8%AA%8D)__  | __98.9__ | __0.0__ | 1.1 | __88.7__ | __0.0__ | 11.3 | __93.8__ | __0.0__ | 6.2 |
| __`ai13s`__  | __98.9__ | __0.0__ | 1.1 | __88.5__ | __0.0__ | 11.5 | __93.7__ | __0.0__ | 6.3 |

### `ai12s` ver 2 VS `ai2` と `ai13s` VS `ai2` の違いの検証

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7cee68-f65d-2370-c63e-0812d9d5b77b.png" width="65">

__先程__、__上記の局面__ で、__`ai12s` ver 2__ と __`ai13s`__ が __選択__ する __合法手__ が __異なる__ ことを __確認__ しました。__それにもかかわらず__、上記の表のように __成績__ が __変わらない__ ということは、__`ai12s` ver 2__ VS __`ai2`__ と __`ai13s`__ VS __`ai2`__ の __対戦__ で、上記のような、__`ai12s` ver 2__ と __`ai13s`__ で __異なる合法手__ を __選択する局面__ が __出現しない__ ことが __原因__ である __可能性__ が __あります__。

そこで、__`ai12s` ver 2__ VS __`ai2`__ と __`ai13s`__ VS __`ai2`__ の __結果__ の __差が生じる__ ような __試合__ が __存在するか__ どうかを、[前回の記事](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#ai12s-ver-2-vs-ai2-%E3%81%A8-ai12s-ver-3-vs-ai2-%E3%81%AE%E9%81%95%E3%81%84%E3%81%AE%E8%A1%A8%E7%A4%BA)と __同様の方法__ で、__下記__ のプログラムで __検証する__ ことにします。ただし、__前回の記事__ の __プログラム__ では __結果__ に __差が生じるまで__、__無限ループ__ で __処理__ を __行いました__ が、__差が生じる__ ような __局面__ が __存在しない__ 場合は __プログラム__ が __終了しない__ ので、__1 万回繰り返し__ ても __見つからない__ 場合は、__処理を終了する__ ように __修正__ しました。

* __7 行目__：__無限ループ__ を、__10000 回繰り返す__ ように __修正__ する
* __9、12 行目__：__`ai12` ver 3__ VS `ai2` を __`ai13`__ VS `ai2` に __修正__ する

```python
 1  import random
 2  from marubatsu import Marubatsu
 3  from ai import ai2, ai12s
 4
 5  seed = 0
 6  mb = Marubatsu()
 7  while seed < 10000:
 8      winner1 = mb.play(ai=[ai12s, ai2], seed=seed, verbose=False)
 9      winner2 = mb.play(ai=[ai13s, ai2], seed=seed, verbose=False)
10      if winner1 != winner2:
11          mb.play(ai=[ai12s, ai2], seed=seed)
12          mb.play(ai=[ai13s, ai2], seed=seed)
13          break
14      seed += 1
```

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

```python
import random
from marubatsu import Marubatsu
from ai import ai2, ai12s

seed = 0
mb = Marubatsu()
while seed < 10000:
    winner1 = mb.play(ai=[ai12s, ai2], seed=seed, verbose=False)
    winner2 = mb.play(ai=[ai13s, ai2], seed=seed, verbose=False)
    if winner1 != winner2:
        mb.play(ai=[ai12s, ai2], seed=seed)
        mb.play(ai=[ai13s, ai2], seed=seed)
        break
    seed += 1
```
</details>

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

```diff_python
import random
from marubatsu import Marubatsu
from ai import ai2, ai12s

seed = 0
mb = Marubatsu()
-while True:
+while seed < 10000:
    winner1 = mb.play(ai=[ai12s, ai2], seed=seed, verbose=False)
-   winner2 = mb.play(ai=[ai12s, ai2], params=[{"score_victory": 200}, {}], \
-                     seed=seed, verbose=False)
+   winner2 = mb.play(ai=[ai13s, ai2], seed=seed, verbose=False)
    if winner1 != winner2:
        mb.play(ai=[ai12s, ai2], seed=seed)
-       mb.play(ai=[ai12s, ai2], params=[{"score_victory": 200}, {}], seed=seed)
+       mb.play(ai=[ai13s, ai2], seed=seed)
        break
    seed += 1
```
</details>

実行結果

```
```

__実行結果__ には __何も表示されない__ ので、想像した通りに、__差が生じる__ ような __局面__ が __出現しない__ ことが __わかりました__。

なお、__ゲーム開始時__ の __局面__ から __`ai13s`__ VS __`ai2`__ の __対戦__ を行った場合は、確かに __差が生じる__ ような __局面__ は __出現しません__ が、例えば __最初__ は __人間が着手__ を行い、__途中から `ai13s`__ が __着手を行う__ ような場合は、__差が生じる局面__ は __下図__ のように __実際に出現__ します。従って、__`ai13s`__ を __作成したこと__ が、__無意味__ であるというわけでは __ありません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7cee68-f65d-2370-c63e-0812d9d5b77b.png" width="65">

## 他の優先順位の条件を考慮に入れた、必敗の局面での最善手の評価値の計算

__ルール 13__ では、__必敗の局面__ での __評価値__ を __計算する際__ に、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数のみ__ を __考慮__ 入れた __式__ で __評価値__ を __計算__ しました。

__必敗の局面__ の __合法手__  の __優劣を決める__ 際に、__必敗の局面以外__ の場合で __有効であった__、__他の優先順位__ の __ヒューリスティックな条件__ の __評価値__ が __有効__ である __可能性__ が __あります__。

### ルール 14 の定義

そこで、__必敗の局面__ の __評価値__ に __ヒューリスティックな条件__ の __評価値__ を __組み込む__ という __ルール 14__ を下記のように __定義__ することにします。具体的には、__ルール 13__ の __優先順位__ が __2__ の __条件__ に『また、__優先順位__ が __5 の条件__ も __考慮__ する』を __加えました__。

| 順位 | 条件 | 種類 |
| :-:|:--|:--|
| 1 | __勝てる場合__ に __勝つ__  | 十分条件  |
| 2 | __相手__ が __勝利できる__ 着手を __行わない__<br>ただし、「__自 0 敵 2 空 1__」の __数__ が __少ない着手__ を __優先__ する<br>また、__優先順位__ が __5 の条件__ も __考慮__ する | 必要条件  |
| 3 | 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う  | 十分条件  |
| 4 | __斜め方向__ に __〇×〇__ が __並び__、__他の 6 マス__ が __空のマス__ の<br>場合は、__いずれか__ の __辺のマス__ に着手を行う  | 十分条件  |
| 5 | 「__自 2 敵 0 空 1__」が __1 つ存在__ する着手を行う<br>「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う<br>「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う |
| 6 | __ランダム__ なマスに __着手__ する  |   |

### 評価値の設定

次に、__ルール 14__ の、__優先順位が 2__ の __条件__ の __評価値__ を __計算する方法__ を __考える必要__ があります。その方法として、__下記__ のような __方法__ が __考えられます__。

* __ルール 13__ の __優先順位が 5__ の __条件__ の __評価値__ に、__優先順位が 5__ の __ヒューリスティックな条件__ の __評価値__ を __加算__ する

その際に、__先程と同様__ に、__計算__ された __評価値__ の __範囲__ が、__他__ の __優先順位__ の __条件__ の __評価値__ の __範囲__ と __重ならない__ ようにする __必要__ があります。

下記は、__そのこと__ を __確認__ するために、__それぞれ__ の __優先順位__ の __条件__ に対する __評価値__ の __範囲__ を __まとめた表__ です。__表__ から、__それぞれ__ の __優先順位__ で __計算__ される __評価値__ の __範囲__ が __重複していない__ ことが __確認__ できます。


| 順位 | 局面の状況 | 個別 | 評価値 | 
|:-:|:--|:-:|:-:|
| 1 | __自分が勝利している__  | | `300` |
| 3 | __「自 2 敵 0 空 1」が 2 つ以上存在する__  | | `200` |
| 4 | __片方__ の __斜め方向__ に __〇×〇__ が __並び__、<br>__いずれか__ の __辺__ の __1 つのマスのみ__ に<br>__× が配置__ されている  | | `100` |
| 5 | __「自 2 敵 0 空 1」が 1 つ存在する__<br>__「自 1 敵 0 空 2」が x 個存在する__<br>__「自 0 敵 1 空 2」が y 個存在する__| `2` (`0～2`)<br>`0.5 * x` (`0～4`)<br>`-y` (`-8~0`) | `-8～6`|
| 2 | __「自 0 敵 2 空 1」が z 個存在する__<br>ただし、__z > 0__ とし、__優先順位__ が __5__ の<br>__評価値__ を __加算__ する | `-100 * z`<br>(`-800 ~ -100`)<br>+`-8～6` | `-808 ~ -94` |

### 評価値を加算する際の注意点

上記では、__優先順位__ が __2__ の __評価値__ の __範囲__ が、その上の __優先順位__ が __5__ の __評価値__ の __範囲__ と __重ならない__ ことを __確認__ しましたが、__それだけ__ では __意図通り__ の __評価値__ が __計算されない__ 場合が __ある__ 点に __注意__ が __必要__ です。

例えば、__`ai13s`__ では、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __少ない合法手__ を __優先的__ に __選択__ するようにするために、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __1 つあたり__ の __評価値__ を __-100__ に __設定__ しました。

__ルール 14__ の __評価値__ を __設定__ する __際__ に、この『「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __少ない合法手__ を __優先的__ に __選択する__』という __条件__ が、__ヒューリスティックな条件__ よりも __重要である__ と __考える__ のであれば、__ヒューリスティックな条件__ による __評価値__ を __加算__ しても、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __少ない場合__ の __評価値__ が __大きくなるよう__ に、__評価値__ を __設定__ する __必要__ が __あります__。そのことを __確認したほう__ が __良い__ でしょう。

__下記__ は、「__自 0 敵 2 空 1__」の __マークのパターン__ の __1 つあたり__ の __評価値__ を __-100__ とした場合に、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __1 ~ 3__ の __場合__ のそれぞれの __評価値__ の __範囲__ を __表す表__ です。表から、この場合は、「__自 0 敵 2 空 1__」の __マークのパターン__ の __それぞれの数__ に対する __評価値の範囲__ が、__重ならない__ ので、 __マークのパターン__ の __数__ が __少ない場合__ の __評価値__ が __必ず大きくなる__ ことが __確認__ できます。

そこで、本記事では、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数__ が __1 つあたり__ の __評価値__ を __`ai13s` と同様__ に、__-100__ に __設定__ することにします。

| 局面の状況 | 個別 | 評価値 | 
|:--|:-:|:-:|
| __「自 2 敵 0 空 1」が 1 つ存在する__<br>__「自 1 敵 0 空 2」が x 個存在する__<br>__「自 0 敵 1 空 2」が y 個存在する__| `2` (`0～2`)<br>`0.5 * x` (`0～4`)<br>`-y` (`-8~0`) | `-8～6`|
| __「自 0 敵 2 空 1」が 1 個存在する__ | `-100`<br>+`-8～6` | `-108 ~ -94` |
| __「自 0 敵 2 空 1」が 2 個存在する__ | `-200`<br>+`-8～6` | `-208 ~ -194` |
| __「自 0 敵 2 空 1」が 3 個存在する__ | `-300`<br>+`-8～6` | `-308 ~ -294` |

下記は、「__自 0 敵 2 空 1__」の __1 つあたり__ の __評価値__ を __-10__ に __設定__ した場合の __表__ です。表から、この場合は、「__自 0 敵 2 空 1__」の __それぞれ__ の __マークのパターン__ の __数__ に対する __評価値__ の __範囲__ が、__他の数__ に対する __評価値__ の __範囲__ の __一部__ に __重なっている__（例えば __`-18 ~ -14`__ が __重なっている__）ことが __わかる__ ので、__目的__ を __達成できません__。

| 局面の状況 | 個別 | 評価値 | 
|:--|:-:|:-:|
| __「自 2 敵 0 空 1」が 1 つ存在する__<br>__「自 1 敵 0 空 2」が x 個存在する__<br>__「自 0 敵 1 空 2」が y 個存在する__| `2` (`0～2`)<br>`0.5 * x` (`0～4`)<br>`-y` (`-8~0`) | `-8～6`|
| __「自 0 敵 2 空 1」が 1 個存在する__ | -10<br>+`-8～6` | `-18 ~ -4` |
| __「自 0 敵 2 空 1」が 2 個存在する__ | -20<br>+`-8～6` | `-28 ~ -14` |
| __「自 0 敵 2 空 1」が 3 個存在する__ | -30<br>+`-8～6` | `-38 ~ -24` |

:::note warn
このように、__異なる優先順位__ の __評価値__ を __合計__ する場合は、上記のような __表を作成__ して、__意図通り__ の __評価値が設定__ されているかどうかを __確認__ することが __重要__ です。
:::

:::note
逆に、「__自 0 敵 2 空 1__」の __マークのパターン__ の __数より__ も、__ヒューリスティックな条件__ のほうが __重要である__ と __考える__ のであれば、__上記__ の __設定__ で __問題__ は __ありません__。
:::

### `ai14s` の定義

下記は、__上記__ の __評価値__ の __計算__ を行う __`ai14s`__ を __定義__ するプログラムです。

* __5、10 行目__：__評価値__ の __合計__ を __計算__ する変数 __`score`__ の __初期化処理__ を、__`eval_func`__ の __最初で行う__ ように __修正__ する
* __8 行目__：__相手が勝利__ できる __場合__ に、__これまで__ は 計算した __評価値__ を __return 文__ で __返していた__ のを、__`score`__ に __加算する__ ように __修正__ する。そのようにすることで、__`score`__ に __12 行目以降__ の __ヒューリスティックな条件に__ よって __計算__ された __評価値__ が __加算される__

```python
 1  def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
 2            score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
 3      def eval_func(mb):         
 4          # 評価値の合計を計算する変数を 0 で初期化する
 5          score = 0        
同じなので略
 6          # 相手が勝利できる場合は評価値を加算する
 7          if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
 8              score = score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
同じなので略
 9          # この下にあった評価値の合計を計算する変数を 0 で初期化する処理を削除する
10
11          # 次の自分の手番で自分が勝利できる場合は評価値に score_201 を加算する
12          if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
同じなので略
```

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

```python
def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):         
        # 評価値の合計を計算する変数を 0 で初期化する
        score = 0        

        # 自分が勝利している場合
        if mb.status == mb.last_turn:
            return score_victory

        markpats = mb.count_markpats()
        if debug:
            pprint(markpats)
        # 相手が勝利できる場合は評価値を加算する
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
            score = score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
        # 次の自分の手番で自分が必ず勝利できる場合
        elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
            return score_sure_victory
        
        # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
        if mb.board[1][1] == Marubatsu.CROSS and \
           (mb.board[0][0] == mb.board[2][2] == Marubatsu.CIRCLE or \
            mb.board[2][0] == mb.board[0][2] == Marubatsu.CIRCLE) and \
           (mb.board[1][0] == Marubatsu.CROSS or \
            mb.board[0][1] == Marubatsu.CROSS or \
            mb.board[2][1] == Marubatsu.CROSS or \
            mb.board[1][2] == Marubatsu.CROSS) and \
           mb.move_count == 4:
            return score_special    

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

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

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

```diff_python
-def ai13s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
-          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
+def ai14s(mb, score_victory=300, score_sure_victory=200, score_defeat=-100,
+          score_special=100, score_201=2, score_102=0.5, score_012=-1, debug=False):    
    def eval_func(mb):         
+       # 評価値の合計を計算する変数を 0 で初期化する
+       score = 0        
同じなので略
        # 相手が勝利できる場合は評価値を加算する
        if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
-           return score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
+           score += score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
同じなので略
        # 評価値の合計を計算する変数を 0 で初期化する
-       score = 0        
        # 次の自分の手番で自分が勝利できる場合は評価値に score_201 を加算する
        if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
同じなので略
```
</details>


### `ai14s` が 5 手目で選択する合法手の確認

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9b7cee68-f65d-2370-c63e-0812d9d5b77b.png" width="65">

__上図__ の __局面__ で、__`ai14s`__ が __選択__ する __合法手__ を、__下記__ のプログラムで __確認__ します。

```python
ai14s(mb, debug=True)
```

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

```
Start ai_by_score
Turn x
x..
.ox
.Oo

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

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=0, turn=2, empty=1): 1,
             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): 2,
             Markpat(last_turn=2, turn=0, empty=1): 1})
score -98.5 best score -inf
UPDATE
  best score -98.5
  best moves [(1, 0)]
====================
move (2, 0)
Turn o
x.X
.ox
.oo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=2, empty=1): 2,
             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,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score -197.5 best score -98.5
====================
move (0, 1)
Turn o
x..
Xox
.oo

defaultdict(<class 'int'>,
            {Markpat(last_turn=0, turn=1, empty=2): 1,
             Markpat(last_turn=0, turn=2, empty=1): 2,
             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,
             Markpat(last_turn=2, turn=1, empty=0): 1})
score -198.5 best score -98.5
====================
move (0, 2)
Turn o
x..
.ox
Xoo

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

下記は、__先程の表__ から __勝率など__ を __削除__ し、__評価値__ の __計算__ で __利用__ する __マークのパターン__ の __数__ と、__上記__ の __実行結果__ に表示された __評価値__ を __加えた__ ものです。

| |  | 「201」 | 「021」 | 「102」 | 「012」 | 評価値 |
|:-:|:-:|:-:|:-:|:-:|:-:|--:|
| | __評価値__ | 1：`+2`<br>2~：`200` | 1 つで<br>`-100` | 1 つで<br>`+0.5` | 1 つで<br>`-1` | |
| 1 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/7b24d05d-924e-6440-7275-fa5770b0b94c.png" width="65">  | 1 | 1 | 1 | 1 | -98.5 |
| 2 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/87db1e04-4f79-3a8d-06b7-0554c9b44e52.png" width="65">  | 1  | 2  | 1  | |-197.5 |
| 3 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e64e8668-76c6-d1fe-5f73-7b07bc803030.png" width="65">  | 1  | 2  | 1 | 1 | -198.5 |
| 4 | <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/0ac00ca5-eb97-7b20-e925-1a0cefed4e62.png" width="65">  | 1  | 1  |  1  |  | -97.5 |

表から、__合法手 4__ の __(0, 2)__ の __評価値__ が __最も高い -97.5__ になり、__この合法手のみ__ が __選択__ されるようになったことが __確認__ できました。また、そのことは、下記の __実行結果__ の __最後の 2 行__ からも __確認__ できます。

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

なお、__`ai13s`__ と __`ai14s`__ は、上記のように __同じ局面__ で __異なる合法手__ を __選択する__ ようになりましたが、__どちら__ が __強い AI であるか__ を、__ランダムな AI__ と __対戦__ して __判定__ することは __できません__。__その理由__ は、先程説明したように、__この局面__ は、__ランダムな AI__ と __対戦__ した際に __生じない局面__ だからです。__`ai13s`__ と __`ai14s`__ の __どちら__ が __最強の AI に近い__ かどうかについては、__探索型の AI__ を __作成する際__ に __確認する__ ことにします。



### `ai2` との対戦

__下記__ のプログラムで、__ランダムな AI__ である __`ai2` と対戦__ してみることにします。

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

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

```
ai14s VS ai2
count     win    lose    draw
o        9900       0     100
x        8885       0    1115
total   18785       0    1215

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.8%    0.0%   11.2%
total   93.9%    0.0%    6.1%
```

__実行結果__ から、__敗率__ が __0 %__ であることが __確認__ できたので、__`ai14s`__ は __弱解決の AI__ である __可能性が高い__ ことが __わかりました__。

下記は、__上記__ の __実行結果__ に、__`ai12s` ver 2__ VS __`ai2`__ と __`ai13s`__ VS __`ai2`__ の __対戦結果__ を __加えた__ ものです。__実行結果__ から、__通算成績__ は __いずれもほぼ同じ__ であることが __わかりました__。

なお、__通算成績__ が __変わらない理由__ は、__`ai13s`__ と __`ai14s`__ の __違い__ が、__`ai13s`__ VS __`ai2`__ や __`ai14s`__ VS __`ai2`__ で __出現しない局面__ に対する __評価値__ の __計算__ だからです。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __[`ai12s` ver 2](https://qiita.com/ysgeso/items/b8b4123e3919357583d7#ai12s-%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%A8%E7%A2%BA%E8%AA%8D)__  | __98.9__ | __0.0__ | 1.1 | __88.7__ | __0.0__ | 11.3 | __93.8__ | __0.0__ | 6.2 |
| __`ai13s`__  | __98.9__ | __0.0__ | 1.1 | __88.5__ | __0.0__ | 11.5 | __93.7__ | __0.0__ | 6.3 |
| __`ai14s`__  | __99.0__ | __0.0__ | 1.0 | __88.8__ | __0.0__ | 11.2 | __93.9__ | __0.0__ | 6.1 |

# 今回の記事のまとめ

今回の記事では、最初に __`ai12s` ver 3__ の __バグの原因__ を __検証__ しました。このように、__ルールベースの AI__ では、__正しい__ と __思っていた条件__ が __正しくなかった__ ということが __あります__。

次に、__必勝の局面__ と、__必敗の局面__ での、__最善手の優劣__ について __説明__ しました。__いずれの場合__ も、__相手__ が __最強の AI__ の __場合__ は __最善手__ に __優劣__ は __ありません__ が、__最強ではない AI__ や __人間__ と __対戦__ する場合を __考慮に入れる__ と、__最善手__ の間に __優劣が生じる__ 場合が __あります__。

特に __人間と対戦__ を行うことを __想定する__ 場合は、__必勝の局面__ の場合では __人間の心理__ を __考慮に入れた優劣__ を __評価値の計算__ に __組み込んだほうが良い__ でしょう。

また、__必敗の局面__ でも、__評価値__ の __計算__ を __工夫__ することによって、__相手__ が __最強の AI でない__ 場合に、__より良い結果__ になる __確率が高い__ 最善手を __選択できる__ ようになることを説明しました。ただし、その際に、計算される __評価値の範囲__ に __注意__ する __必要がある__ ことを __忘れないで下さい__。

なお、今回の記事では説明を省略しましたが、__引き分けの局面__ の __最善手__ にも、__同様の意味__ での __優劣__ が __存在します__。

__ルールベースの AI__ について、__〇×ゲーム__ で __思いつく範囲__ の __説明__ は __ほぼ行った__ のではないかと思いますので、__ルールベースの AI__ に関する __説明__ は __今回の記事__ で __終わり__ にします。ただし、ルールベースの AI に関する __重要な内容__ を __思いついた場合__ は、__適宜説明__ します。

:::note
本記事では、__マークのパターン__ を __利用__ した __ルール__ の __条件__ を作成してきましたが、__局面の状況__ を __うまく表す他の性質__ を考え、その性質を使って __条件__ を __考える__ ことも __できます__。興味や時間がある方は考えてみると良いでしょう。
:::

ここまでの記事を読んで、__ルールベース__ で __AI を作成__ することが、__非常に大変__ であることが __実感できた__ のではないかと __思います__。また、__〇×ゲーム__ は、__単純なゲーム__ なので、__ルールベースの AI__ でも、__弱解決の AI__ を __作成__ することが __できました__ が、__〇×ゲームより__ も __複雑なゲーム__ の __ほとんど__ は、__ルールベースの AI__ で __弱解決の AI__ を __作成__ することは __非常に困難__ か、__ほぼ不可能__ です。そのため、これまでに何度か言及してきましたが、__最近__ では __ルールベース__ で __ゲームの AI__ を __作成__ することは __主流__ では __なくなっています__。

それにもかかわらず、__本記事__ が __最初__ に、__主流ではない__、__ルールベース__ で __AI を作成__ してきた __主な理由__ は、__以下の通り__ です。

* __ルールベース の AI__ の __考え方__ が、__人間__ が __問題__ を __解決__ するための __考え方__ に __似ている__
* __昔__ は、__ルールベース の AI__ が __主流__ であった
* __〇×ゲーム__ であれば、__ルールベース__ で __弱解決の AI__ を __作成できる__
* __ルール__ を __少しづつ加えていく__ ことで、__AI__ を __作り上げていく__ ことが __できる__
* __初心者__ が __プログラミング__ の __基礎__ を __学ぶため__ の __重要な題材__ が __豊富__ である

次回からは、〇×ゲームの AI に関する別の内容を説明したいと思います。

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

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

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

今回の記事では marubatsu.py は変更していません。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/10d1d01192c014173e4b

[^1]:「__相手__ が __勝利できる__ 着手を __行わない__」という __条件の記述__ は __省略__ しています
[^2]:__この局面__ では、__`ai12s` ver 2__ は、最善手を選択しない場合があるという __問題__ は __発生しません__
[^3]:もちろん、何も思わない人もいるでしょう
[^4]:将棋のプロ棋士どうしの対局では、__勝敗__ が __明らか__ になった __局面__ で、__敗北__ を __悟った側__ が __投了する__（負けを認める）するのが __一般的__ です
[^5]:それぞれの __勝率__ を __小数点以下 1 桁__ で __四捨五入__ しているので、__合計__ は __100 %__ に __なりません__