Pythonで〇×ゲームのAIを一から作成する　その58　最強の AI と最善手の定義とその性質

# 目次と前回の記事

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

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/058/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 | あり |

# 前回の記事のおさらい

[前回の記事](https://qiita.com/ysgeso/items/fc19eb2764e0766b59d5#ai11s-%E3%81%AE%E8%A9%95%E4%BE%A1%E5%80%A4%E3%81%AE%E8%A8%88%E7%AE%97%E6%96%B9%E6%B3%95%E3%81%AE%E4%BF%AE%E6%AD%A3)では、__`ai10s` VS `ai11s`__ で、__`ai11s`__ が __× を担当__ した際に、__`ai11s`__ が __50 %__ の __確率__ で __負けてしまう__ という __問題を修正__ するために、__下記__ の表のように __パラメータ__ の __修正__ を行いました。

|  | 修正前 | 修正後 |
|:-:|:-:|:-:|
| __「自 2 敵 0 空 1」が 1 つの場合の評価値__  | 1  | 2 | 
| __「自 1 敵 0 空 2」が 1 つあたりの評価値__ | 1  | 1 |
| __「自 0 敵 1 空 2」が 1 つあたりの評価値__ | -1 | -1 |


下記は、__パラメータ__ の __修正前__ と __修正後__ の __`ai11s`__ VS __`ai10s`__ の __対戦結果__ の表です。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __修正前__ | 22.2 | 0.0 | 77.8 | 0.0 | 50.5 | 49.5 | 11.1 | 25.3 | 63.6 |
| __修正後__ | 0.0 | 0.0 | 100.0 | 0.0 | 0.0 | 100.0 | 0.0 | 0.0 | 100.0 |

__修正結果__ からわかるように、__`ai11s`__ が __× を担当__ した際に __負けなく__ なりましたが、今度は、__〇 を担当__ した際に、__勝てなくなる__ という __新しい問題__ が __発生__ しました。

# パラメータの修正の影響の検証

__新しい問題__ が __発生__ した __原因__ は、__`ai11s`__ の __パラメータ__ の __修正__ が、__`ai10s`__ VS __`ai11s`__ の __4 手目__ の局面 __のみ__ を __考慮__ して __行われた__ からです。そのため、__4 手目__ の __局面__ に対しては、__想定通りの処理__ が行われますが、__それ以外__ の __局面__ では、__この修正__ によって __AI__ が __弱くなる__ ような __変化__ が起きている __可能性__ が __生じます__。

別の言葉で説明すると、何らかの __問題を解決__ する際に、__特定の状況のみ__ を __考慮__ に入れて __解決__ するという、__局所的__ な __解決__ を行うと、__考慮していない状況__ で __別の問題__ を __引き起こし__ てしまう __場合がある__ ということです。

:::note
このようなことは、__現実世界__ でも __よくあります__。例えば、__成績を向上__ させるために、__毎日 2 時間勉強する__ という __行動__ は、__健康である__ という __条件__ を満たしていれば __有効__ でしょう。しかし、__病気になった時__ に無理して __2 時間勉強__ を行うと、病気が悪化して治りが遅くなり、__成績__ が __逆に下がってしまう__ ことになるでしょう。
:::

## 修正前と修正後の `ai11s` VS `ai10s` の検証

__上記__ のようなことが __起きた__ こと __確認__ するために、__パラメータの修正__ が、__`ai11s`__ VS __`ai10s`__ の __対戦結果__ に、__どのような影響__ を __与えたか__ について __検証__ することにします。

これまでと __同様の手順__ で、__`ai11s`__ VS __`ai10s`__ の __検証__ を行うことができますが、__検証の作業__ は [前回の記事](https://qiita.com/ysgeso/items/fc19eb2764e0766b59d5#4-%E6%89%8B%E7%9B%AE%E3%81%A7-0-2-%E3%81%AB%E7%9D%80%E6%89%8B%E3%82%92%E8%A1%8C%E3%81%A3%E3%81%9F%E5%A0%B4%E5%90%88%E3%81%AE%E6%A4%9C%E8%A8%BC) と __ほとんど変わらない__ ので、__検証結果__ の図 __だけ__ を __示す__ ことにします。興味と余裕がある方は、これまでと同様の方法で実際に検証してみて下さい。

### 修正前の `ai11s` VS `ai10s` の検証結果

__修正前__ の __`ai11s`__ VS __`ai10s`__ では、__下図__ のような __着手__ が行われます。__赤字__ が __`ai11s`__ の __勝利__ につながる __着手の選択__ を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/20ca8f93-c6e7-93a1-869a-07d451274789.png" width="700">

この表から、__修正前__ の __`ai11s`__ は __3 手目__ で下記の __2 種類__ の __着手を行う__ ことが分かります。

* __33 %__ の __確率__ で __(2, 2)__ を __選択__ する
    * その場合は、__その次__ の __4 手目__ で __`ai10s`__ は、__66 %__ の __確率__ で __`ai11s` の勝利__ につながる __着手__ を、__33 %__ の __確率__ で __引き分け__ につながる __着手__ を行う
* __67 %__ の __確率__ で __引き分け__ につながる __(2, 0)__ の __着手__ を __選択__ する

__上記__ から、__`ai11s`__ が __勝利__ する __確率__ は、0.33 * 0.66 = __約 21.8 %__ であると __計算__ できます。これは、__実際__ の __対戦結果__ の __`ai11s`__ の __勝率__ である __約 22 %__ とほぼ __一致__ します。

### 修正後の `ai11s` VS `ai10s` の検証

__修正後__ の __`ai11s`__ VS __`ai10s`__ では、__下図__ のような __着手__ が行われます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/69f9b56f-2565-0336-6c2e-f41ab1925498.png" width="700">

__修正後__ の __`ai11s`__ は、修正前と異なり、__3 手目__ で __(2, 0)__ の __着手__ しか __選択__ しないので __必ず引き分け__ になります。なお、__3 手目__ で __(2, 0)__ の __着手__ が __行われた後__ の __`ai10s`__ と __`ai11s`__ が __選択__ する __着手__ は、__修正前__ と __修正後__ で __完全に同じ__ です。

### 検証結果からの考察

__上記__ から、__`ai11s`__ の __パラメータ__ を __修正__ することで、__実際__ に __`ai11s`__ VS __`ai10s`__ で、__`ai11s`__ が __3 手目__ に __選択__ する __着手__ が __変化する__ ことが __確認__ できました。また、その __変化__ が起きた __結果__、__`ai11s`__ の __勝率__ が __約 22 %__ から __0 %__ に __減ってしまう__ ことが __わかりました__。

ただし、__勝率が減る__ ことが必ずしも __悪いこと__ であるとは __限りません__。その __理由__ を __理解__ するためには、__最強の AI__ の __定義__ と __性質__ を __明確__ にする __必要__ があります。

# 最強の AI と最善手の定義と性質

__本記事__ の __目的__ は、__〇×ゲーム__ の __強い AI__、すなわち __最強の AI__ を作る事です。しかし、__これまでの記事__ では、この __強い AI__ や __最強の AI__ がどのようなものを指すかについて、__明確な定義__ を __行ってきません__ でした。その理由は、__AI__ を __作成__ した __体験がない__ 人に対してその定義を示してもあまり __実感がわかない__ のではないかと __思ったから__ です。

ここまでの記事で、様々な AI を作成し、対戦させてきたことで、__AI__ が __どのようなルール__ で __着手__ を __選択__ するかがある程度は __わかってきた__ のではないかと思いますので、この機会に、__強い AI__ や __最強の AI__  がどのようなものであるかについて __定義を行う__ ことにします。

## 強いとは何か

__一般用語__ としての「__強い__」には、__様々な意味__ があり、「__強い__」という __用語__ をどのような __意味__ でとらえているかは、__人__ や __状況__ によって __異なる__ でしょう。

例えば、卓球などの __個人戦__ の __スポーツ選手__ に対する __強い__ という __用語__ は、下記のような __様々な意味__ で __使われます__。もちろん、下記以外にも様々な使われ方があるでしょう。

* __試合__ の __勝率が高い__
* __世界ランキング__ が __高い__
* __大きな大会__ で __優勝__ した __実績__ がある
* 怪我をせず、__年間を通じて活躍__ する
* 負けてもスランプに陥いらないという、__強い精神力を持つ__

「__強い__」という __用語__ が __あいまい__ なままでは、__強い AI__ という __表現__ をしても、__どのように強いか__ が __明確__ では __ありません__。また、「__強い__」という __用語__ が __あいまい__ なままでは、最も強いという意味を持つ、__最強の AI__ の __意味__ も __明確__ では __ありません__。

## ゲームの性質の制限

__本記事__ は、__〇×ゲーム__ の __AI__ の __強さ__ を考えているので、__ゲームの AI__ の __強さ__ を __定義__ します。ただし、世の中の __あらゆるゲーム__ の __強さを定義__ する事は __簡単__ なことでは __ありません__。その理由は、__ゲームの性質__ によっても、__強い__ という __用語の意味__ が __変わる__ からです。

例えば、__〇×ゲーム__ のような、__運の要素がない__ ゲームと、__じゃんけん__ のような __運の要素がある__ ゲームでは、「__強い__」という __意味が異なる__ でしょう。__運の要素がない__ ゲームは、__完全__ に __実力勝負__ になるので、単純に __勝った方が強い__ ということができます。しかし、じゃんけんのような __運の要素がある__ ゲームは、__100 % 勝つ__ ということは __不可能__ なので、__1 つの試合__ の __勝敗だけ__ を見て __どちらが強いか__ を __測る__ ことは __できません__。

そこで、__本記事__ では、__話を簡単にする__ ために、__試合の結果__ が __完全__ に __実力によって決まる__ という __性質__ がある、「__二人零和有限確定完全情報ゲーム__」という __分類__ の __ゲーム__ の __強さ__ を __定義__ することにします。なお、__この用語__ は __難しそうに見える__ かもしれませんが、その __意味__ はそれほど __難しくはない__ ので安心して下さい。

「__二人零和有限確定完全情報ゲーム__」とは、__下記__ のような __性質__ を持つ __ゲーム__ です。

* __二人__：文字通り、__二人で遊ぶゲーム__ という性質
* __零和__：__プレイヤー__ の __利害__ が __完全に対立する__ という性質。例えば、__片方__ が __勝てば__、__もう片方__ が __負ける__ という __性質__ を持ち、__両方__ が __同時に勝利__ することは __ない__。二人の __利害の合計__（和）が __零になる__ ことから、__零和__ と呼ぶ
* __有限__：__合法手__ が __有限__ であり、ゲームが __有限の手番__ で __必ず終了する__ という性質。__合法手__ が __無限__ にあったり、__永遠__ に __決着がつかない__ ようなゲーム __ではない__
* __確定__：サイコロのような、__ランダムな要素__ が __存在しない__ という性質。__着手__ による __局面の変化__ が __確定__ する __性質__ を持つゲーム
* __完全情報__：ゲームの __すべての情報__ が __公開されている__ という性質

__この分類__ の __ゲーム__ には、本記事が題材とする、__〇×ゲーム__ をはじめ、将棋、チェス、オセロ[^1]など、__数多くのゲーム__ があり、__AI の研究__ の __初期の頃__ から __研究が行われてきました__。

__一般的__ に、__問題を解く際__ に、このように __条件__ を __限定__ することで、__問題__ を __簡単にする__ ことができます。例えば、__完全情報__ という __性質__ を __加える__ ことで、__公開されていない情報__ を __推測__ する __必要__ が __なくなる__ ので、__問題が簡単__ になります。__本記事__ では、以後は、__二人零和有限確定完全情報ゲーム__ という __条件を満たすゲーム__ について __説明__ することにします。

この __条件を満たさないゲーム__ に関しては、__本記事__ の __この後の説明__ の __一部__ が __当てはまらない__ 場合がある点に __注意__ して下さい。例えば、__麻雀__ や、__手札を明かさないトランプ__ のゲームは、__見えない情報__ が __存在する__ ので __完全情報__ の性質を __満たしません__。また、__じゃんけん__ は、__ランダムな要素__ は __ない__ ので __確定__ の性質は __満たします__ が、__自分__ が __手を出す際__ に、__相手__ が __出す手__ が __見えていない__ ので __完全情報__ の性質を __満たしません__。従って、二人のプレイヤーが __同時に着手__ を行うような __ゲーム__ は、__完全情報__ の性質を __満たしません__。

参考までに、__二人零和有限確定完全情報ゲーム__ の Wikipedia のリンクを下記に示します。

https://ja.wikipedia.org/wiki/%E4%BA%8C%E4%BA%BA%E9%9B%B6%E5%92%8C%E6%9C%89%E9%99%90%E7%A2%BA%E5%AE%9A%E5%AE%8C%E5%85%A8%E6%83%85%E5%A0%B1%E3%82%B2%E3%83%BC%E3%83%A0

## 二人零和有限確定完全情報ゲームの性質

__二人零和有限確定完全情報ゲーム__ には、__下記__ の __性質__ があります。なお、__説明__ が __かなり長くなる__ ので、それぞれについての __厳密な証明__ は __省略__ しますが、__〇×ゲーム__ に関しては、__探索型の AI__ を __説明__ する際に、__実際__ に __下記の性質を持つ__ ことを __示す__ 予定です。

* __原理的にはすべての局面を列挙可能__
__有限__ という __性質__ から、__原理的__ には、その __ゲーム__ の __すべての局面__ を __列挙可能__ です。ただし、__原理的__ には __可能であっても__、__オセロ__、__将棋__、__囲碁__ など、__多くのゲーム__ では、__局面の数__ が __多すぎて__、__現実的__ には __すべての局面__ を __列挙__ することは __不可能__ です。

:::note
__オセロ__ の __局面の数__ は __約 $10^{28}$__、__将棋__ の __局面の数__[^2] は __約 $10^{69}$__、__囲碁__ の __局面の数__[^3] は __約 $10^{171}$__ であると __言われています__。__オセロ__ の場合は、__1 秒間__ に __1 億__ の __局面__ を __列挙できた__ としても、__すべての局面__ を __列挙__ するためには __1 兆年以上__ かかります。
:::

* __原理的には完全攻略が可能__
__すべての局面__ を __列挙__ することが __できれば__、その __ゲーム__ の __すべての知識__ を __得ることができる__ ということなので、__原理的__ にはその __ゲーム__ の __完全攻略__ が __可能__[^4] です。__将棋__ や __囲碁__ は、__局面の数__ が __多すぎて__、__現実的__ には __完全攻略__ は __不可能__ ですが、__〇×ゲーム__ の場合は、__局面の数__ は __5478__ で、__同一局面__ を __1 つの局面__ と __みなした__ 場合は __850__ しかありません。そのため、__人間__ であっても十分に __完全攻略__ が __可能__ な __ゲーム__ です。

* __すべての局面に最善手が存在する__
__完全攻略ができる__ ということは、__すべての局面__ で、自分にとって __最も有利__ となる __合法手__ が __存在する__ ということです。__そのような合法手__ の事を __最善手__ と呼びます。なお、__すべての局面__ に __最善手__ が __存在__ することは __間違いありません__ が、 __多くのゲーム__ では、__局面の数__ が __多すぎる__ ため、__一部の局面__ でしか __最善手__ を __見つける__ ことは __できません__。

:::note
__現実の世界__ にも、__存在する__ ことと、__見つける方法__ が __わかっていても__、__現実的__ に、はそれを __見つけること__ が __ほぼ不可能__ なものが __あります__。例えば、__現時点__ で __世界__ で __最も体重が重い__ 人は __必ず存在__ します。また、__全世界の人__ の __体重__ を __今すぐ__ に __同時に測って比較__ することで、__原理的__ には その人を __見つける__ ことは __可能__ です。しかし、__現実的__ には __そのようなこと__ を __行う__ のは __不可能__ でしょう。
:::

## 最強の AI の定義

__AI__ の __強さ__ を __いきなり定義__ する事は __困難__ なので、最初に __定義しやすい__、__最強の AI__ を __定義__ し、その後で __強い AI__ を __定義__ する事にします。

__本記事__ では、__上記の性質__ を元に、__二人零和有限確定完全情報ゲーム__ における、__最強の AI__ を、__下記__ のように __定義__ する事にします。「自分にとって __最も有利__ になる __合法手__」という、__最善手__ の __意味__ を考えれば、__あたりまえ__ の __定義__ と言えるでしょう。

:::note warn
__二人零和有限確定完全情報ゲーム__ における、__最強の AI__ とは、__すべての局面__ で、__最善手__ を __選択する AI__ のことである。
:::

従って、__二人零和有限確定完全情報ゲーム__ の __最強の AI__ を作るということは、__すべての局面__ での、__最善手を見つける__ ということを __意味__ します。また、その __最善手__ は、__今後の記事__ で __説明__ する __探索型の AI__ を __作成__ することによって、__原理的__ には __みつける__ ことが __可能__ です。

ただし、__将棋__ や __囲碁__ などの、__局面の数__ が __多すぎる__ ゲームの __場合__ は、__現実的__ には __探索型の AI__ で __最善手__ を __見つける__ ことは __不可能__ です。

:::note warn
__二人零和有限確定完全情報ゲーム__ は、__原理的__ には __すべての局面__ での、__最善手を見つける__ ことが __可能__ だが、__多くのゲーム__ では、__局面の数__ が __多すぎる__ ため、__現実的__ には __最強の AI__ を __作成__ することは __不可能__ である。
:::

従って、__多くのゲーム__ では、本記事でこれまでに行ってきた __ルールベースなど__ の、__様々な方法__ を __組み合わせて__、__最強の AI__ に __近い強さ__ を持つ __AI の作成__ を __目指します__。

## 弱点の局面の定義

__最強ではない__ AI は、必ず __いずれかの局面__ で、__最善手以外__ の __合法手__ を __選択__ します。__最善手以外__ の __着手__ を行うと、__状況が悪化__ することになるので、__本記事__ では __そのような局面__ のことを、__AI__ の __弱点の局面__ と __表記__ することにします。

## 最強の AI どうしの対戦

__二人零和有限確定完全情報ゲーム__ には、__ランダム性__ が __存在しない__ ので、__局面__ ごとに、__お互い__ が __最善手__ を __指し続けた場合__ の __結果__ が __決まっています__。つまり、__最強の AI__ どうしが __対戦__ した場合、__局面__ ごとに、__勝敗__ の __結果__ は __決まっている__ ということです。

__〇×ゲーム__ のように、__ゲームの結果__ が、__勝利__、__敗北__、__引き分け__ の __3 種類__ に __分類__ される場合、__すべての局面__ は、__その局面__ から __最強の AI__ どうしが __対戦した結果__ によって、__下記__ の __3 つに分類__ することができます。__以後__ は、必要に応じて __〇×ゲームの局面__ を、__下記__ の __局面の分類__ で __表記__ することにします。

| 局面の分類 | 対戦結果 |
|:--|:--|
| __〇 の必勝の局面__  | 〇 が 勝利する  |
| __× の必勝の局面__  | × が 勝利する  |
| __引き分けの局面__[^5]  | 引き分け  |

なお、上記の __必勝__ とは、__最強の AI どうし__ が __対戦__ した場合の __結果__ を表します。__どのような AI__ が __その局面__ から __対戦__ しても __必ず勝つ__ という __意味ではない__ 点に __注意__ して下さい。

:::note
「__〇 の必勝__ の __局面__」という、__実際__ に __良く使われる表現__ には、「__最強の AI どうし__ が __対戦__ した __場合__ は」という __主語__ が __省略されている__ と考えて下さい。
:::

__すべての局面__ で、__最強の AI どうし__ が __対戦__ した場合の __結果__ が __決まっている__ ということは、__ゲーム開始時__ の __局面__ でも __結果__ が __決まっている__ ということです。

:::note warn
__二人零和有限確定完全情報ゲーム__ の __性質__ を持つ __ゲーム__ は、__ゲーム__ が __始まった時点__ で、既に __最強の AI__ どうしが __対戦__ した場合の __結果が決まっている__。

また、__一般的__ に、__ゲーム開始時__ の __局面の状況__ を使って、その __ゲーム__ を「__〇 の必勝__ の __ゲーム__」や「__必ず引き分け__ になる __ゲーム__」のように __呼ぶ__。
:::

__〇×ゲーム__ は、__最初の局面__ が __引き分けの局面__ であることが __わかっている__ ので、__〇×ゲーム__ は（__最強の AI どうし__ が __対戦__ した場合は）__必ず引き分け__ になる __ゲーム__ です。従って、__最強の AI__ どうしが __対戦__ した場合は、__〇 を担当__ しても __× 担当し__ ても __引き分け__ になります。

:::note
本記事では扱いませんが、ゲームによっては __引き分け__ が __無かったり__、__勝利__ と __敗北__ だけでなく、__お互いの点数差__ などが __重要になる__ 場合があります。例えば、サッカーのワールドカップの総当たり戦では、__同じ成績の場合__ は、__得失点差__ が __多いほう__ が __優勝__ します。そのような場合でも、__基本となる考え方__ は __大きく変わりません__。
:::

### 先後を入れ替えた場合

__二人零和有限確定完全情報ゲーム__ は、__完全情報__ の性質から、__二人のプレイヤー__ が、__交互__ に __着手__ を行うので、__ゲームの開始時__ に __どのプレイヤー__ が __着手を行う__ かが __決まっています__。__先に着手__ を行う __プレイヤー__ を __先手__、__後に着手__ を行う __プレイヤー__ を __後手__ と __呼びます__。

__二人零和有限確定完全情報ゲーム__ は、__先手の必勝__ または、__後手の必勝__ の __ゲーム__ である __場合が多い__ ので、__多くの対戦__ では __公平性__ を考えて、__先手__ と __後手__ を __入れ替えて__、__2 回対戦__ し、__総合成績__ で __勝敗を決めます__。__`ai_match`__ でも __そのような対戦__ を行います。

下記は、__ゲーム開始時__ の __それぞれ__ の __局面の状況__ に対して、__最強の AI どうし__ で、__先後__ を __入れ替え__ た __対戦結果__ です。表から、__いずれの場合__ も __勝数__ と __敗数__ が __同じ__ になります。つまり、__最強の AI どうし__ が __先後__ を __入れ替えて戦う__ と、__通算成績__ は __引き分け__ になります。これは、__同じ強さ__ の __AI どうし__ が __戦う__ と __引き分けになる__ という __直観通りの結果__ です。

| ゲーム開始時の状況 | 先手を担当 | 後手を担当 | 勝 | 負 | 分 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __先手必勝__ | 勝利 | 敗北  | 1  | 1  | 0  |
| __引き分け__ | 引き分け | 引き分け  | 0  | 0  | 2  |
| __後手必勝__ | 敗北 | 勝利  | 1  | 1  | 0  |

## 最強の AI のパラドックス

__最強の AI__ の __定義__ を行いましたが、皆さんが、__一般的__ に「__最強__」という __用語__ を __思い浮かべた時__ に、__どのような存在__ を __思い浮かべる__ でしょうか？おそらく、__どのような大会__ に __参加__ した場合でも __優勝する__ ような __存在__ を __思い浮かべる__ 人が __多いのではないか__ と思います。

しかし、__実際__ には、先程定義した __最強の AI__ は、__どのような大会__ でも __優勝できる__ とは __限りません__。__最強__ であるのに __優勝できない場合がある__ というような、__一見__ すると __矛盾__ しているように __見える__ が、__実際__ には __真実__ であるような __性質__ のことを __パラドックス__ と呼びます。どのような場合に優勝できないことがあるかについて少し考えてみて下さい。

なお、誰でもすぐに思いつく例として、大会に __最強の AI__ が __複数参加__ する場合があると思いますが、__最強の AI__ が __1 つしか参加しない__ 場合でも、この __パラドックスは起きます__。

参考までに、__辞書__ の __パラドックス__ の __リンク__ を下記に示します。

https://www.weblio.jp/content/%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9#:~:text=%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9%EF%BC%88paradox%EF%BC%89%E3%81%A8%E3%81%AF%E3%80%81,%E8%83%8C%E7%90%86%E3%80%81%E9%80%86%E7%90%86%E3%81%A8%E3%82%82%E8%A8%80%E3%82%8F%E3%82%8C%E3%82%8B%E3%80%82

### パラドックスが起きる具体例

上記の __パラドックス__ が起きる具体的な __大会のルール__、__ゲームの設定__、__参加する AI__ についてそれぞれ __説明__ し、__どのようにパラドックス__ が __起きるか__ について __説明__ します。

#### 大会のルール

この大会では、__以下のルール__ で __優勝__ する __AI__ が __決まります__。

* __総当たり__（リーグ戦）で、__すべての AI__ どうしの __組み合わせ__ で __対戦を行う__
* __対戦__ は、__先手__ と __後手__ を __入れ替え__ て __1 回ずつ__ 行う
* __勝率__ が __最も高い AI__ が __優勝__ する

#### ゲームの設定

__下記__ は、__ゲームの設定__ を表す __図__ で、図の中の __記号や図形__ などの __意味__ は __以下の通り__ です。なお、__探索型 の AI__ の __説明__ を __行う際__ に __詳しく説明__ しますが、このような、__ゲームの全貌__ を表す __図__ のことを、__ゲーム木__ と呼びます。

* 図の __番号__ が書かれている __正方形__ が、__局面__ を表す
* __局面 1__ が、ゲームの __開始時の局面__ を表す
* __水色__ の __正方形__ が、__先手__ が __着手__ を行う __局面__ を表す
* __オレンジ色__ の __正方形__ が、__後手__ が __着手__ を行う __局面__ を表す
* __局面__ から __右に伸びる線__ は、その __局面__ の __合法手__ を表し、その __線の右__ には、その __合法手__ を __着手__ した後の __局面__ または、ゲームの __結果__ を __表記__ する
* __一番右__ は、ゲームの __結果__ を表し、__青字__ は __先手の勝利__、__黒字__ は __引き分け__ を表す

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd99f565-3572-3449-fa7c-6a280ca7cd3f.png" width="250">

図からわかるように、__このゲーム__ は、__すべての局面__ に対して、__合法手__ が __2 つずつ存在__ し、__先手__ と __後手__ が __1 回ずつ着手__ を行うと __ゲームが終了__ します。

#### 3 つの AI の設定

この大会には、__3 つ__ の __A__、__B__、__C__ という、__すべての局面__ で、__ランダム__ な __着手__ を __行わない__（__同じ局面__ であれば、__常に同じ合法手__ を __選択__ する）__AI__ が参加します。

__下図__ は、__それぞれの局面__ で、__それぞれの AI__ が __選択__ する __合法手__ を、__線の色__ で __表現__ しています。例えば、__最初の局面__ である __局面 1 から__ は、__赤い線__ が __局面 3__ に向かって __引かれている__ ので、__A__ は __局面 1__ で、着手すると __局面 3__ になるような __合法手__ を __選択__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/16770252-d917-43ac-d727-de67a88dc47a.png" width="250">

3 つの AI の中で、__A__ は __最強の AI__ です。その事を示します。

* __後手__ の __手番__ である __局面 2__ は、__着手を行う__ ことでゲームの __決着がつく__ ので、__結果__ から __明らか__ に図の __赤い線__ の __合法手__ が、__後手__（__先手ではない__ 点に __注意__ すること！）にとって __最も有利__ になる。従って、__局面 2__ の __最善手__ は __上の合法手__ である

* __後手__ の __手番__ である __局面 3__ は、__どちら__ の __合法手__ を __選択__ しても __引き分け__ になる。従って、__局面 3__ では __どちら__ の __合法手__ も __最善手__ である

* __先手__ の __手番__ である __局面 1__ で、__上の合法手__ を __選択__ した場合は、__局面 2__ になり、__局面 2__ で __後手__ が __最善手__ を __選択__ すると __引き分け__ になる。__下の合法手__ を __選択__ した場合は、__局面 3__ になり、__局面 3__ で __後手__ が __最善手__ を __選択__ すると __引き分け__ になる。従って、__局面 1__ では __どちら__ の __合法手__ も __最善手__ である

下記は、それぞれの __局面__ の __最善手__ と、それぞれの __AI__ が __選択__ する __合法手__ を表します。なお、__AI__ が __選択__ する __合法手__ が __最善手__ の場合は、__太字で表記__ します。

|  | 最善手 | A | B | C | 局面の状況 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  | __下__  | __上__  | __下__  | 引き分け |
| __局面 2__  | 上  | __上__  | 下  | 下  | 引き分け |
| __局面 3__  | 上、下  | __上__ | __上__  | __下__  |引き分け |

__上記__ から、__A__ は、__すべての局面__ で __最善手を選択__ しているので、__A__ は __最強の AI__ です。

一方、__B__ と __C__ は __局面 2 以外__ の __局面__ では __最善手__ を __選択__ しますが、__弱点__ となる __局面 2__ で __最善手__ を __選択しない__ ので、__最強の AI__ では __ありません__。

なお、上記の表から、__最初の局面__ である __局面 1__ は、__引き分けの局面__ なので、__このゲーム__ は __最強の AI どうし__ が __対戦__ すると __引き分けになる__ ことが分かります。

### 複数の最強の AI

上記の __局面 1__、__3__ のように、__合法手__ の中に __複数__ の __最善手__ が __存在__ する場合は、__最善手の中__ の、__どの合法手__ を __選択__ しても __最強の AI__ であることは __変わりません__。従って、__このゲーム__ の __最強の AI__ は、下記の __A__、__D__、__E__、__F__ の __4 種類__ が __存在__ します。

|  | 最善手 | A | D | E | F |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  | __下__  | __下__  | __上__  | __上__  |
| __局面 2__  | 上  | __上__  |  __上__   |  __上__   | __上__  |
| __局面 3__  | 上、下  | __上__ | __下__  | __上__  | __下__  |

:::note warn
__合法手の中__ に __複数__ の __最善手__ が __ある__ 場合は、__最強の AI__ は __複数存在__ する。
:::

### AI どうしの対戦結果

次に、__A__、__B__、__C__ で __総当たり戦__ を行うと、どのような __結果__ になるかを __検証__ します。

分かりやすいように、__先程の図__ を __再掲__ します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/16770252-d917-43ac-d727-de67a88dc47a.png" width="250">

__それぞれの AI__ は、__上図__ に __従って着手__ を __選択__ するので、__それぞれ__ の __組み合わせ__ の __対戦結果__ は、__局面 1 から__ はじまり、__それぞれ__ の __局面__ で、__それぞれの AI__ が __選択__ する __合法手__ を __下記__ の __表__ のように __辿っていく__ ことで、__知る__ ことができます。

|  | 経過 | 結果 |
|:-:|:-:|:-:|
| __A VS B__  | 局面 1 → 局面 3 → 引き分け | 引き分け  |
| __B VS A__  | 局面 1 → 局面 2 → 引き分け | 引き分け  |
| __A VS C__  | 局面 1 → 局面 3 → 引き分け | 引き分け  |
| __C VS A__  | 局面 1 → 局面 3 → 引き分け | 引き分け  |
| __B VS C__  | 局面 1 → 局面 2 → 先手の勝利 | B の勝利 |
| __C VS B__  | 局面 1 → 局面 3 → 引き分け | 引き分け  |

下記は、__上記の結果__ を __総当たりの表__ にしたものです。表の __記号__ は、__〇__ が __勝利__、__△__ が __引き分け__、__×__ が __敗北__ を表します。

|  | A | B | C | 勝 | 敗 | 分 | 勝率 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|--:|
| __A__  |   | △△ | △△  | 0  | 0  | 4  | 0 %  |
| __B__  | △△  |   | 〇△  | 1  |  0 | 3  | 100 % |
| __C__  | △△  | ×△|   | 0  | 1  | 3  | 0 %  |

表から、__B の勝率__ が __100 %__ で __最も高い__ ので、__B が優勝__ することがわかります。なぜ、__最強の AI ではない__、__B が優勝__ することになったかについて、少し考えてみて下さい。


## 最善手の意味とパラドックスが起きる理由

先程、「自分にとって __最も有利__ となる __合法手__」のことを __最善手__ と __説明__ しましたが、この説明は __正確__ では __ありません__。__最善手__ とは、__正確__ には、「__お互い__ が __最善手__ を __選択し続けた場合__ に、自分にとって __最も有利__ となる __合法手__」のことです。

:::note warn
__最善手__ とは、__お互い__ が __最善手__ を __選択し続けた__ 場合に、__自分__ にとって __最も有利__ となる __合法手__ のことである。
:::

つまり、__相手__ が __最善手__ を __選択しない__ 場合は、自分にとって __最も有利__ になるとは __限らない__ ということです。そのことを、具体例を挙げて説明します。

総当たり戦で、__B__ が __優勝__ する __理由__ は、__最強の AI__ である __A__ が先手で __C__ と __対戦__ した際に __引き分け__ になるのに対し、__最強ではない B__ が先手で __C__ と __対戦__ した際に __B の勝利__ になるという、__一見__ すると __おかしい__ ように __見える__ ことが起きているからです。そこで、__A VS B__、__A VS C__、__B VS C__ の __対戦__ を __検証__ してみることにします。

なお、__A__ は __最強の AI__ なので、__すべての局面__ で __最善手__ を __選択__ します。そのため、__以下の説明__ では、__A__ の __手番__ で行われる __合法手の選択__ の __説明__ は __省略__ します。

### A VS B と A VS C の検証

下記は、__A VS B__ と __A VS C__ の __対戦の経緯__ を表す表です。

|  | 経緯 |
|:-:|:-:|
| __A VS B__  | 「__局面 1（A の手番）__ → __局面 3（B の手番）__ → __引き分け__」  |
| __A VS C__  | 「__局面 1（A の手番）__ → __局面 3（C の手番）__ → __引き分け__」  |

上記から、いずれも __同じ経緯__ で __引き分け__ になることがわかります。__A VS B__ の __経緯__ の中で __B__ が __着手__ を __選択__ するのは __局面 3__ で、__B__ は __下記__ の __表__ からわかるように __局面 3__ で __最善手__ を __選択__ します。これは、__A VS C__ の場合でも __同様__ です。

|  | 最善手 | A | B | C | 局面の状況 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  | __下__  | __上__  | __下__  | 引き分け  |
| __局面 2__  | 下  | __上__  | 下  | 下  | 引き分け  |
| __局面 3__  | 上、下  | __上__ | __上__  | __下__  | 引き分け  |

また、__上記__ の __表__ から、__局面 2__ は、__B__ と __C__ はの __弱点の局面__ ですが、__上記の経緯__ では、__局面 2__ は __出現しません__。このことから、__最強 ではない AI__ であっても、__対戦の中__ で __弱点の局面__ が __生じなければ__、相手は __すべての着手__ で __最善手__ を __選択__ することが __わかります__。

__別の言葉__ で説明すると、__最強ではない AI__ には、__必ず__ どこかに __弱点があります__ が、__相手__ がその __弱点を突く__ ことが __できなければ__、__最強の AI__ と __互角の戦いができる__ ということです。

:::note warn
__最強ではない AI__ でも、__弱点__ を __突かれなけれ__ ば（__最善手__ を __選択しない__、__弱点の局面__ が __生じなければ__）、__最強の AI__ と __互角に戦う__ ことが __できる__。
:::

:::note
このようなことは __現実の世界__ でも __よくある__ 事です。例えば、あるスポーツで、__以下__ のような __2 つのチーム__ が存在する場合、__一般的__ には __チーム A__ のほうが __チーム B より__ も __強い__ と __評価されます__。__実際__ に __一年を通じて試合を行う__ と、__チーム A__ は __チーム B__ に __勝ち越す可能性が高い__ でしょう。しかし、__チーム B__ の __弱点__ となる __夏以外__ で、__試合を行う__ と、__チーム B__ は __チーム A__ と __互角に戦う__ ことが __できます__。

|  | 特徴 |
|:-:|:--|
| __チーム A__  |  __一年中__ を通じて __強い__ |
| __チーム B__  |  __暑さが苦手__ なので __夏は弱い__ が、__夏以外__ は __チーム A__ と __互角__ |
:::

__B VS A__ や __C VS A__ などの __試合結果__ が __引き分け__ になる __理由__ も、__上記__ と __同様__ に、__B__ や __C__ の __手番__  で、__B__ や __C__ の __弱点の局面__ が __生じない__ からです。__B VS A__ では、__B__ の __弱点__ の __局面 2__ が __生じる__ と __思った人__ が __いるかもしれません__ が、__その場合__ の __局面 2__ は __A の手番__ です。

### B VS C の検証

__B VS C__ は「__局面 1（B の手番）__ → __局面 2（C の手番）__ → __引き分け__」という __経緯__ で __B の勝利__ になりますが、この中で __C__ が __着手__ を __選択__ する __局面 2__ は、__下記__ の __表__ からわかるように __C__ の __弱点の局面__ なので、__C__ は __最善手__ を __選択しません__。

|  | 最善手 | A | B | C | 局面の状況 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  | __下__  | __上__  | __下__  | 引き分け  |
| __局面 2__  | 下  | __上__  | 下  | 下  | 引き分け  |
| __局面 3__  | 上、下  | __上__ | __上__  | __下__  | 引き分け  |

このことから、__B VS C__ で __B が勝利__ する __理由__ は、__C__ の __弱点の局面__ である __局面 2__ が __生じる__ ような __最善手__ を __B が選択__ したからであることがわかります。

### 検証結果からわかる事

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

* __最強の AI__ であっても、__相手__ の __弱点を突く__ ことが __できなければ__（__弱点の局面__ が __生じなければ__）、__ゲーム開始時__ の __局面の状況__ よりも __良い結果になる__ ことは __ない__。
* __最強ではない__ の __AI__ であっても、__相手__ の __弱点を突く__ ことが __できる__（__弱点の局面__ が __生じる__）場合は、__ゲーム開始時__ の __局面の状況__ よりも __良い結果になる__ 場合が __ある__。

上記を __別の言葉__ で説明すると、__AI どうし__ の __対戦結果__ は、__最強__ であるかどうかには __関係なく__、お互いの __弱点を突く__ ことが __できるか__ どうかによって __決まる__ ということです。

__下記__ は、__検証結果__ からわかったことを __一般化__ した __説明__ です。

:::note warn
__X__、__Y__、__Z__ の __3 つの AI__ の間で __対戦__ を行った場合に、__X__ VS __Y__ の __結果__ が、__X__ VS __Z__ の __結果よりも良い__ 場合でも、__X__ のほうが __Y より強い__ とは __限らない__。
:::

また、上記を __別の言葉__ で __説明__ すると、以下のようになります。

:::note warn
__2 つの AI__ の __強さを比較__ するために、それぞれの __別の AI__ との __対戦結果__ を __比較__ しても、__うまく比較できる__ とは __限らない__。
:::

__最強ではない B__ が __優勝できた理由__ は、__A__ は __C__ の __弱点__ を __つけなかった__ が、__B__ は __C__ の __弱点__ を __突くこと__ が __できたから__ であることが __わかりました__。ただし、だからといって、__最強の AI__ に __価値がない__ わけでは __ありません__。次は、そのことを説明します。

## 一般的な意味の「最善」と「最善手」の意味の違い

__一般用語__ としての「__最善__」が「__最も良い__」という __意味を表す__ ことから、__最善手__ を __選択__ し続けることで、__最も良い結果__ である __勝利することができる__ のように __勘違する人__ が __いるかもしれません__ が、__上記の検証__ からそれは __間違い__ であることがわかります。

__実際__ には __ゲーム__ の __最善手__ は、__一般的なイメージ__ の __最善__ とは __異なり__、__以下__ のような __意味を持つ__ 点に __注意__ して下さい。

* __最善手__ を __選択__ することで、__現在の局面__ の __状態__ を __維持する__。つまり、__最善手__ を __選択__ しても、__局面の状況__ が __改善することはない__
* __最善手以外__ を __選択__ した場合は、__局面の状況__ が __悪化__ する
* 従って、__局面__ の __状況が改善__ されるのは、__相手__ が __最善手以外__ を __選択した場合__ である

:::note
上記で、__最善手__ を __選択しない__ 場合は __局面の状況が悪化__ すると __説明__ しましたが、__状況の悪化__ には __種類__ が __あります__。例えば、__〇×ゲーム__ のように、__必勝__、__引き分け__、__必敗__ という、__3 種類__ の __局面の状況__ がある場合は、__局面の状況__ の __悪化__ には、「__必勝 → 引き分け__」、「__必勝→必敗__」、「__引き分け→必敗__」という __3 種類__ があります。

__状況__ が __何段階悪化するか__ によって __分類__ すると、__下記の表__ のようになります。この表は、__局面の状況__ で、それぞれに __分類される着手__ を __行った場合__ に、__局面の状況__ が __どのように変化するか__ を表します。__空欄__ は __合法手__ が __存在しない__ ことを表します。
| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | 必勝  | 引き分け  | 必敗  |
| __引き分け__  | 引き分け  | 必敗  |   |
| __必敗__ | 必敗  |   |   |

表から、__必敗__ の __状況__ では、__すべての合法手__ が __最善手__ になることが分かります。__必ず負ける__ の に、__最善手__ と呼ぶのは __変だと思うかもしれません__ が、__最も良い結果になる__ ということは __事実__ なので、__この場合__ も __最善手__ と __呼びます__。
:::

## 最強の AI の性質

上記から、__最強の AI__ は、__どのような AI__ と __対戦__ しても、__最強の AI どうし__ が __対戦__ した場合の __結果__ と __同じか__、それよりも __良い結果__ になります。

従って、__〇×ゲーム__ のように、__勝利__、__敗北__、__引き分け__ の __3 種類__ の __結果__ がある __ゲーム__ では、__最強の AI__ は __どのような AI__ と __対戦__ しても、__下記__ のような __結果__ になります。

| 局面の状況 | 結果 |
|:--|:--|
| __自分の必勝__  | __必ず勝利__ する  |
| __引き分け__  | __引き分け__ または __勝利__ する  |
| __相手の必勝__  | 勝利、引き分け、敗北の __すべての可能性がある__  |

また、__最強の AI__ と __最強ではない AI__ が __先後__ を __入れ替えて対戦__ した場合は、__下記の表__ のような __結果__ になります。表からわかるように、__どの場合__ でも、__最強の AI__ の __勝数__ が __敗数以上__ になるので、__最低__ でも __通算成績__ は __引き分け以上__ の __結果__ になります。__別の言い方__ をすると __最強の AI__ は __通算成績__ で __負けになる__ ことは __絶対にありません__。

|ゲーム開始時の状況  | 先手を担当 | 後手を担当 | 勝 | 負 | 分 |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __先手必勝__ | 勝利 | 敗北以上  | 1~2  | 0~1  | 0~1  |
| __引き分け__ | 引き分け以上 | 引き分け以上  | 0~2  | 0  | 0~2  |
| __後手必勝__ | 敗北以上 | 勝利  | 1~2  | 0~1  | 0~1  |

:::note
__先手必勝__ と __後手必勝__ は、いずれも __勝利__ が __ある__ ので、__勝数__ は __1 以上__ になります。__引き分け__ の場合は、__絶対に負けない__ ので、__敗数__ は __0__ になります。
:::

上記から、__最強の AI__ には __下記__ のような __性質がある事__ が分かります。__最強の AI__ は、__必ず勝つ__ AI __ではなく__、__絶対__ に __局面の状況__ を __悪化させない AI__ である点に __注意__  して下さい。

:::note warn
__最強の AI__ は、__どのような AI__ と __対戦__ しても、__結果__ が __ゲーム開始時__ の __局面の状況__ よりも __悪くなる__ ことは __ない__。

__先後__ を __入れ替え__ て __対戦__ を行った場合、__最強の AI__ は、__どのような AI__ と __戦っても__、__通算成績__ は __引き分け以上__ になる。すなわち、__絶対__ に __負けることはない__。
:::

:::note
__別の言葉__ で __説明__ すると、以下のようになります。

* __最強の AI__ は __最善手のみ__ を __選択__ するので、__局面の状況__ が __悪化__ することは __ない__
* __相手__ が __最善手__ を __選択するか__ どうかは、__相手次第__ なので、__局面の状況__ が __好転するか__ どうかは、__相手次第__（他力本願）である
* 従って、__先手を担当__ した場合に、__先手必勝__ のゲームでは、__最強の AI__ は __必ず勝利__ するが、__そうでないゲーム__ の場合は __勝利するか__ どうかは、__相手次第__ である
:::

### 一般的な意味の「最強」と「最強の AI」の違い

__一般的__ な __意味__ での __最強__ は、例えば __総当たり戦__ などで __優勝__ するような __意味__ で __使われます__。実際に、__最強の AI__ は、__先後__ を __入れ替え__ て __対戦を行う__ 場合は、__どのような AI__ と __戦っても__、__引き分け以上__ になり、__絶対__ に __負けることはない__ ので、__他の AI__ との __直接対決のみ__ で __優勝を決める__ ような __場合__ は、__他の AI__ と __同率で首位__ になる __場合__ は __あるかも__ しれませんが、__必ず優勝__ します。従って、__そのような意味__ では __最強__ であると __言える__ でしょう。

一方、__総当たり戦__ のように、__直接対決以外__ の __対戦結果__ が __成績に反映__ する __場合__ は、__最強の AI__ は __他の AI どうし__ の __対戦__ に __影響を及ぼす__ ことが __できないため__、__それらの対戦結果__ によっては __優勝できない可能性__ があります。現実の具体例として、__最強のチーム__ が __優勝しないようにする__ ために、__弱いチーム__ が __八百長__ をして __特定のチームだけ__ を __わざと勝たせる__ ようなことが行われた場合、__最強のチーム__ であっても __優勝__ することは __難しい__ でしょう。

:::note warn
__最強の AI__ は、__他の AI__ と __先後__ を __入れ替え__ て __対戦__ を行う場合は、__絶対に負けない__。

従って、__直接対決のみ__ で __優勝を決める__ 場合は、__最低__ でも __同率 1 位__ で __優勝できる__ という __意味__ では __最強__ である。

一方、__直接対決__ が __行われない試合がある__ 場合は、__必ず優勝できる__ とは __限らない__。

このように、__最強の AI__ とは、__一般的__ な __最強__ の __イメージ__ と __異なり__、__絶対に優勝できる AI__ のこと __ではない__ 点に __注意が必要__ である。
:::

## 複数の最強の AI の優劣

先程、__このゲーム__ の __最強の AI__ は、下記の表のように、__複数存在__ することを __説明__ しました。そのため、__A 以外__ の __別__ の __最強の AI__ であれば、__優勝できるのではないか__ と思った人がいるかもしれません。

|  | 最善手 | A | D | E | F |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  | __下__  | __下__  | __上__  | __上__  |
| __局面 2__  | 上  | __上__  |  __上__   |  __上__   | __上__  |
| __局面 3__  | 上、下  | __上__ | __下__  | __上__  | __下__  |

実際に、__局面 1__ で、__上の合法手__ を __選択する__、__E__ と __F__ の場合は、__B__ と __C__ の __弱点をつく__ ことが __できる__ ので、__下記の表__ のような __結果__ になり、__優勝できます__。

|  | E、F | B | C | 勝 | 敗 | 分 | 勝率 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|--:|
| __E、F__  |   | 〇△ | 〇△  | 2  | 0  | 2  | 100 %  |
| __B__  | ×△  |   | 〇△  | 1  |  1 | 2  | 50 % |
| __C__  | ×△  | ×△|   | 0  | 2  | 2  | 0 %  |

このことから、__複数__ の __最強の AI__  が __存在する__ 場合に、その中に __常に優劣が存在する__ と __思う人がいる__ かもしれませんが、__そうではありません__。__必勝の局面でない__ 場合に、__相手__ に __勝てるか__ どうかは、__相手__ の __弱点をつくことができるか__ によって __変化__ するからです。

__具体例__ を挙げて説明します。__下図__ のような __設定__ の __ゲーム__ では、__それぞれ__ の __局面__ の __最善手__ は __以下の表__ のようになります。__先程__ との __違い__ は、__局面 3__ で __下の合法手__ を __選択__ すると __先手が勝利__ する点です。ただし、__どの局面__ の __状況__ も __引き分け__ になる点は __同じ__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e29248b5-5e97-2bcd-f732-4635b152d63e.png" width="250">

|  | 最善手 | 局面の状況 |
|:-:|:-:|:-:|
| __局面 1__  | 上、下  | 引き分け  |
| __局面 2__  | 上 | 引き分け  |
| __局面 3__  | 上 | 引き分け  |

__このゲーム__ の __最強の AI__ は、下記の表の __G__ と __H__ の __2 種類__ があります。また、__下記の表や図__ のような __選択__ を行う、__最強ではない__、__I__ と __J__ という __AI__ があるものとします。なお、__I__ と __J__ の違いは、__弱点の局面__ が __I__ は __局面 2__、__J__ は __局面 3__ である点です。

|  | 最善手 | G | H | I | J |
|:-:|:-:|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  | __上__  | __下__  | __上__  | __下__  |
| __局面 2__  | 上  | __上__  |  __上__   |  下   | __上__  |
| __局面 3__  | 上  | __上__ | __上__  | __上__  | 下  |

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/93db69c8-5254-3d22-12c5-ae0646c070b6.png" width="200">

__下記の表__ は、__G__、__H__ が、それぞれ __I__、__J__ と __対戦__ した場合の __結果__ です。表からわかるように、__G__ は __I__ と __対戦__ した場合は __勝利__ しますが、 __J__ と __対戦__ した場合は __引き分け__ になります。一方、__H__ はその __逆の結果__ になります。

|  | I | J |
|:-:|:-:|:-:|
| __G__  | G の勝利  | 引き分け  |
| __H__  | 引き分け  | H の勝利  |

このように、__G__ と __H__ は、それぞれ __I__ と __J__ の __どちらかの弱点__ しか __つくことができない__ ので、__G__ と __H__ の __優劣__ は、下記のように __状況によって異なる__ ことになります。

* __I__ と __同様の弱点__ を持つ AI が、__J__ と __同様の弱点__ を持つ AI __よりも多い__ 場合は、__G__ のほうが __H より__ も __良い成績__ になる
* __I__ と __同様の弱点__ を持つ AI が、__J__ と __同様の弱点__ を持つ AI __よりも少ない__ 場合は、__H__ のほうが __G より__ も __良い成績__ になる
* __I__ と __同様の弱点__ を持つ AI が、__J__ と __同様の弱点__ を持つ AI __と同じ__ 場合は、__G__ と __H__ の __成績__ は __同じ__ になる

:::note warn
__最強の AI__ どうしの __優劣__ は、__それだけ__ で __決めることはできず__、__対戦相手__ の __性質__ によって __変化する__。また、__一般的__ には、__対戦相手__ が __不明__ の場合は、__最強の AI どうし__ に __優劣はない__ と __考える__ 場合が __多い__。
:::

:::note
__現実の世界__ でも、__同じくらい__ の __強さ__ を持つと考えられている __ゲームの戦法__ が __複数__ あった場合でも、__何も考えず__ に __戦法を選ぶ__ ことはあまり __しない__ でしょう。__一般的__ には __対戦相手__ の __苦手な戦法__ を __分析__ して __戦法を選択__ するはずです。ただし、__相手__ の事が __全く分からない場合__ は、__ランダム__ に __戦法を選択__ するしかないでしょう。
:::

## ランダムな着手を行う AI の場合

ここまでは、話を簡単にするために、__ランダム__ な __着手__ を __行わない__ 場合の __AI__ の __性質__ について __説明__ しました。一方、__これまでに作成__ してきた __`ai11s`__ などの __AI__ では、__評価値__ が __最大__ の __合法手__ の中から __ランダム__ に __選択__ を行う __AI を作成__ してきました。

__ランダムな着手__ を __考慮に入れた__ 場合は、__最強の AI__ を __無限に作成__ することが __できます__。例えば、ある局面に __最善手__ が  __2 つ存在__ した場合に、__ランダム__ に __最善手__ を __選択__ する __方法__ は、__最善手 1__ を __選択する確率__ を __x %__、__最善手 2__ を __選択する確率__ を  __y %__ とした場合、$x + y = 100$ を __満たせば__、__どのような値__ を __設定__ しても __構わない__ ので、__無限の組み合わせ__ があります。__必ず最善手__ を __選択__ するという __条件__ が __満たされて__ いれば、__ランダムな着手__ を行っても、__これまでに説明__ した __最強の AI__  の __性質を満たす__ ことに __変わりはありません__。

__最強でない AI__ の __場合__ は、__合法手の中__ から、__最善手__ を __選択する確率__ と、__最善手でないもの__ を __選択する確率__ によって、__AI の強さ__ が __毎回変わります__。従って、__AI どうし__ で __対戦__ した場合に、__毎回結果__ が __変わる__ 場合が生じるようになります。

なお、__すべての局面__ で __最善手__ を __選択__ する __可能性__ が __ある場合__ でも、__そうでない可能性がある__ 場合は、__最強の AI__ とは __みなされない__ 点に __注意__ して下さい。例えば、__すべての局面__ で __ランダム__ な __合法手__ を __選択__ する __`ai2`__ は、__偶然すべて__ の __着手__ で __最善手__ を __選択する可能性__ がありますが、__`ai2`__ を __最強の AI__  だと __考える人__ はおそらく __誰もいない__ でしょう。

下記は、__AI__ が __ランダムな着手__ を __行う__ 場合に、__最強の AI__ と __最強でない AI__ が、__先後__ を __入れ替え__ て __複数回対戦__ した場合の __結果__ を表す表です。

<table>
  <tr>
    <th colspan="2"></th>
    <th style="text-align: right">勝率</th>
    <th style="text-align: right">敗率</th>
    <th style="text-align: right">引分率</th>
  </th>
  <tr>
    <td rowspan="3"><strong>先手必勝<strong></td>
    <td>先手</td>
    <td style="text-align: right">100 %</td>
    <td style="text-align: right">0 %</td>
    <td style="text-align: right">0 %</td>
  </tr>
  <tr>
    <td style="text-align: right">後手</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
  </tr>
  <tr>
    <td>通算</td>
    <td style="text-align: right">50 ~ 100 %</td>
    <td style="text-align: right">0 ~ 50 %</td>
    <td style="text-align: right">0 ~ 50 %</td>
  </tr>
  <tr>
    <td rowspan="3"><strong>引き分け<strong></td>
    <td>先手</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
  </tr>
  <tr>
    <td style="text-align: right">後手</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
  </tr>
  <tr>
    <td>通算</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
  </tr>
  <tr>
    <td rowspan="3"><strong>後手必勝<strong></td>
    <td>先手</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
    <td style="text-align: right">0 ~ 100 %</td>
  </tr>
  <tr>
    <td style="text-align: right">後手</td>
    <td style="text-align: right">100 %</td>
    <td style="text-align: right">0 %</td>
    <td style="text-align: right">0 %</td>
  </tr>
  <tr>
    <td>通算</td>
    <td style="text-align: right">50 ~ 100 %</td>
    <td style="text-align: right">0 ~ 50 %</td>
    <td style="text-align: right">0 ~ 50 %</td>
  </tr>
</table>

__上記の表__ から、__ランダム性がある__ 場合も、__ランダム性がない__ 場合と __同様__ に、__局面の状況__ より __悪い結果になる__ ことは __ない__ ため、__ランダム性がない__ 場合と __同様の性質__ があります。

:::note warn
__ランダム__ に __着手を選択するか__ どうかに __関わらず__ 、__下記の性質__ がある。

__最強の AI__ は、__どのような AI__ と __対戦__ しても、__結果__ が __ゲーム開始時__ の __局面の状況__ よりも __悪くなる__ ことは __ない__。

__先後__ を __入れ替え__ て __対戦__ を行った場合、__最強の AI__ は、__どのような AI__ と __戦っても__、__通算成績__ は __引き分け以上__ になる。すなわち、__絶対__ に __負けることはない__。
:::

__逆に言えば__、__他の AI__ と __対戦__ した __結果__、__上記の表__ のように __ならない__ 場合は、__最強の AI ではない__ ということが __わかります__。

## AI の修正による結果の解釈

下記は、__先程の表__ を、__自分の視点__ で __まとめ直した__ ものです。

| 局面の状況 | 勝率 | 敗率 | 引分率 |
|:-:|--:|--:|--:|
| __自分の必勝__  | 100 %  | 0 %  | 0 %  |
| __引き分け__  | 0 ~ 100 %  | 0 %   | 0 ~ 100 %  |
| __自分の必敗__  | 0 ~ 100 %  | 0 ~ 100 %  | 0 ~ 100 %  |

この表から、__最強の AI__ は __局面の状況__ ごとに __下記__ の __性質がある__ 事が __分かります__。

### 自分の必勝の場合

__自分の必勝__ の局面では、__最強の AI__ は __引き分け__ や __敗北__ になることは __ありません__。従って、__この状況の局面__ で、__自分の AI__  が __他の AI__ と __対戦__ して __引き分け__ や __敗北__ になった場合は、__自分の AI__ に __何らかの弱点__ が __存在する__ ことを __意味します__。

:::note warn
__必勝の局面__ で、__AI を修正__ した __結果__、__敗率__ や __引分率__ が __悪化__ した場合は、__修正__ によって __欠陥が増えて__ おり、__AI__ が __弱く__ なっている __可能性が高い__。

逆に、__100 % 勝利__ した __場合__ でも、__相手の AI__ に __弱点__ がある __可能性がある__ ため、__それだけ__ で __最強の AI__ であると __断言する__ ことは __できない__。
:::

### 引き分けの場合

__引き分け__ の局面では、__最強の AI__ は、__必ず引き分け__ になります。従って、__この状況の局面__ で、__自分の AI__  が __他の AI__ と __対戦__ して __敗北__ した場合は、__自分の AI__ に __何らかの弱点__ が __存在する__ ことを __意味します__。

逆に、__この状況の局面__ で、__自分の AI__  が __他の AI__ と __対戦__ して __勝利__ した場合は、__相手の AI__ に __何らかの弱点__ が __存在する__ ことを __意味します__。

:::note warn
__引き分けの局面__ で、__AI を修正__ した __結果__、__敗率__ が __悪化__ した場合は、__修正__ によって __欠陥が増えて__ おり、__AI__ が __弱く__ なっている __可能性が高い__。

__勝率が変化__ した場合は、__相手の AI__ の __弱点が原因__ なので、__勝率が変化__ しても、__自分の AI__ の __強さが変化__ したと __断言する__ ことは __できない__。
:::

### 自分の必敗の場合

__自分の必敗__ の局面では、__最強の AI__ は、__必ず敗北__ します。従って、__この状況の局面__ で、__自分の AI__  が __他の AI__ と __対戦__ して __引き分け__ や __勝利__ した場合は、__相手の AI__ に __何らかの弱点__ が __存在する__ ことを __意味します__。

:::note warn
__必敗の局面__ で、__AI を修正__ した __結果__、__勝率__ や __引分率__ が __変化__ した場合は、__相手の AI__ の __弱点が原因__ なので、__自分の AI__ の __強さが変化__ したと __断言する__ ことは __できない__。
:::

### `ai11s` の場合

__証明__ は __今後の記事__ で行いますが、__〇×ゲーム__ の __最初の局面__ は、__引き分け__ の局面です。

そのため、__下記の表__ のように、__修正前__ と __修正後__ の __`ai11s`__ が __〇 を担当__ して、__`ai10s`__ と __対戦__ した場合に、__修正後__ のほうが __勝率が低く__ なっても __AI__ が __弱くなった__ と __断言__ することは __できません__。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __修正前__ | 22.2 | 0.0 | 77.8 | 0.0 | 50.5 | 49.5 | 11.1 | 25.3 | 63.6 |
| __修正後__ | 0.0 | 0.0 | 100.0 | 0.0 | 0.0 | 100.0 | 0.0 | 0.0 | 100.0 |

一方、__`ai11s`__ が __× を担当__ する場合は、__引き分けの局面__ であるにも関わらず、__修正前__ では __約 50 % の確率__ で __敗北__ します。これは、__修正前__ の __`ai11s`__ が __× を担当__ する場合に、__弱点が存在した__ こと表します。また、__修正後__ で __負けなくなっている__ ことから、__修正__ によって、__× を担当__ する場合は __弱点が解消__ された結果 __`ai11s`__ が __強くなった__ ことが分かります。

## `ai11s` のパラメータの修正によっておきたことの検証

__パラメータ__ の __修正__ によって __勝利できなくなった原因__ が __相手の弱点__ のせいであることを __検証__ することで、__修正__ によって __勝利できなくなった__ ことが __問題ではない__ ことを示します。

### 修正前の `ai11s` VS `ai10s` の検証
 
下記は、__修正前__ の __`ai11s`__ VS __`ai10s`__ で行われる __着手の選択__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/20ca8f93-c6e7-93a1-869a-07d451274789.png" width="700">

__図__ から、__`ai11s`__ が __勝利__ するのは、__3 手目__ で __`ai11s`__ が __(2, 0)__ に __着手__ した __場合__ であることがわかります。また、__その後__ の __4 手目__ の局面で __`ai10s`__ が行う __選択__ は __以下__ のようになっていることがわかります。

* __(1, 2)__ を __選択__ した場合は __`ai11s` が勝利__ する
* __(0, 2)__ を __選択__ した場合は __引き分け__ になる
* __(0, 1)__ を __選択__ した場合は __`ai11s` が勝利__ する

上記から、__4 手目__ の __局面__ では、__(0, 2)__ を __選択__ することが、__`ai10s`__  にとって __最も有利__ になるので、__最善手__ は __(0, 2)__ であることが __分かります__。しかし、__`ai10s`__ は __この局面__ で __最善手以外__ を __選択__ する __可能性__ があるので、__この局面__ は __`ai10s`__ の __弱点の局面__ です。

つまり、__修正前__ の __`ai11s`__ が __`ai10s`__ に __勝利できた__ のは、たまたま __相手の弱点__ を __つけていたから__ に __過ぎない__ ということです。

### 修正後の `ai11s` VS `ai10s` の検証

下記は、__修正後__ の __`ai11s`__ VS __`ai10s`__ で行われる __着手の選択__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/69f9b56f-2565-0336-6c2e-f41ab1925498.png" width="700">

図から、__`ai11s`__ VS __`ai10s`__ の __3 手目__ では、__(2, 0)__ のみが選択され、その結果 __引き分けになる__ ことが __確認__ できました。

### 3 手目の検証

上記から、__3 手目__ で __(2, 2)__ を __選択__ した場合は、__相手__ が __4 手目__ で __最善手__ を __選択__ すると __引き分け__ になります。また、__3 手目__ で __(0, 2)__ を __選択__ した場合も __引き分け__ になります。従って、__3 手目__ の __局面__ の __最善手__ は、__(2, 2)__ と __(0, 2)__ の __両方__ であることがわかります。

また、__2 つの図__ から、__3 手目__ で __(2, 0)__ に __着手__ を __行った後__ の __局面__ では、__修正前__ と __修正後__ の __`ai11s`__ は、__全く同じ選択__ を __行う__ ことが分かります。

従って、__修正前__ と __修正後__ の __`ai11s`__ の __違い__ は、__3 手目__ で行われる __選択のみ__ ですが、__どちらも最善手__ なので、__修正前__ と __修正後__ の __`ai11s`__ は、__同じ強さ__ であることが分かります。

このことから、__`ai10s`__ に __勝利できなくなった理由__ は、__AI が弱くなった__ から __ではなく__、__相手の弱点__ を __つけなくなった__ からであるため、__問題ではない__ ことが __確認__ できました。

## `ai11s` をさらに修正すべきか

__`ai11s`__ の __パラメータ__ を __さらに修正__ し、__`ai11s`__ VS __`ai10s`__ で __`ai11s`__ が __勝利できるようにする__ ことは __可能かもしれません__ が、__そのような修正__ を __行う必要__ は __ない__ でしょう。

その __理由の 1 つ__ は、そのような __修正を行う__ ことで、__別の局面__ で __新しい問題__ が __発生する可能性__ があるからです。__他の理由__ としては、__修正前__ の __`ai11s`__ が __`ai10s`__ に __勝利できていた__ のは、__`ai10s`__ の __弱点__ を __ついている__ に __すぎない__ からです。頑張ってそのような __修正__ を __行っても__、__その弱点がない AI__ と __対戦__ した場合には __勝利できません__。

本記事では、__修正後__ の __`ai11s`__ に __問題がない__ ことが __確認できた__ ので、__これ以上の修正__ を __`ai11s`__ に __行わない__ ことにします。

# AI の強さを評価する方法

ここまでで、__最強の AI__ の __強さ__ の __定義__ と、__性質__ について __説明__ しましたが、__最強ではない AI__  どうしの __強さ__ は __どのように評価する__ ことができるででしょうか。

__AI の強さ__ は、__様々な方法__ で __評価__ されます。本記事では、その中の __いくつか__ の __方法__ について説明しますが、本記事で紹介しない方法もあります。

## 最強の AI の定義と類似する方法
__最強の AI__ と __そうでない AI__ の __違い__ は、__すべての局面__ で __最善手__ を __選択するか__ どうかでした。それと __同様の考え方__ で、__2 つ__ の __X__ と __Y__ という __AI__ に、__下記__ のような __関係がある場合__ に、__X__ は __Y より__ も __強い__ と __定義__ することができます。

:::note warn
__下記の条件__ を __すべて満たす__ 場合に、__X__ は __Yより__ も __強い AI__ である。

* __すべての局面__ で、__X が選択__ した着手を行った __後__ の __局面の状況__ が、__Y が選択__ した着手を行った __後__ の __局面の状況__ と __同じ__ か、__良い状況__ になる
* __1 つ以上__ の __局面__ で、__X が選択__ した着手を行った __後__ の __局面の状況__ が、__Y が選択__ した着手を行った __後__ の __局面の状況より__ も __良い状況__ になる
:::

__上記の条件__ が満たされていれば、__X__ と __Y__ が __最強の AI__ と __対戦__ した場合は、__同じ結果__ または、__X__ のほうが __Y より__ も __良い結果__ になります。その __理由__ は、以下の通りです。

* __どのような局面__ でも、__X__ のほうが、__Y より__ も __不利__ な __局面の状況__ になるような __合法手__ を __選択__ することは __ない__
* __相手__ が __最強の AI__ の場合は、相手は __最善手のみ__ を __選択__ するので、__局面の状況__ が __変化__ することは __ない__

:::note warn
__最強の AI__ と __対戦__ した場合は、__強い AI__ は、__弱い AI__ と __同じ__ か、__それよりも良い結果__ になる。逆に言えば、__強い AI__ の __結果__ が __弱い AI__  の __結果より悪くなる__ ことは __ない__。
:::

また、__最強の AI__ の場合と __全く同じ理由__ で、__以下の事__ が言えます。

:::note warn
__最強でない AI__ と __対戦__ した場合は、__強い AI__ のほうが、__弱い AI__ よりも __良い結果になる__ とは __限らない__。
:::

:::note
__先程の定義__ が __わかりづらい__ と思った方は、__下記__ のような __例__ を __思い浮かべる__ と良いでしょう。下記は、あるゲームの __3 人__ のキャラクターの __能力値__ です。

この中で __最強__ のキャラクターは、__すべて__ の __能力値__ が __最も高い C__ です。

また、__B__ の __すべて__ の __能力値__ は、__A__ の能力値 __以上__ で、なおかつ __1 つ以上__ の __能力値__ が __A より__ も __高い__ ので、__B__ は __A より__ も __強い__ といえます。__同様__ の理由で、__C__ は __B より__ も __強く__、__C__ は __A より__ も __強い__ と言えます。

|  | HP | 強さ | かしこさ |
|:-:|--:|--:|--:|
| __キャラクター A__  | 10  | 5  | 20  |
| __キャラクター B__  | 20  | 5 | 30  |
| __キャラクター C__  | 30  | 15 | 50  |
:::

### この定義の方法の問題点

上記で __強い AI の定義__ を行いましたが、__実際__ には __この定義__ は __多くの場合__ で あまり __役に立ちません__。その __理由__ は、__先程の例__ の、__下記の表__ の __I__ と __J__ のように、__異なる局面__ で __片方__ は __弱点ではない__ が、__もう片方__ が __弱点__ であるような __場合__ が __良くある__ からです。特に __局面__ が __多くなれば__ なるほど、__ほとんどの AI__ が __どちらが強い__ かを __判定できなく__ なります。

|  | 最善手 | I | J |
|:-:|:-:|:-:|:-:|
| __局面 1__  | 上、下  |  __上__  | __下__  |
| __局面 2__  | 上  |   下   | __上__  |
| __局面 3__  | 上  |  __上__  | 下  |

:::note warn
上記の __問題点__ から、この __AI の強さ__ の __定義__ は、__採用しない__ ことにします。

なお、__最強の AI__ の定義は、__そのまま利用__ します。
:::

:::note 
__わかりづらい__ と思った方は、__下記__ の __例__ を見て下さい。下記の場合では、__キャラクターどうし__ の __強さの関係__ を、__先程の定義__ で __決める__ ことは __できません__。また、__最強__ のキャラクターを __決める__ ことも __できません__。

|  | HP | 強さ | かしこさ |
|:-:|--:|--:|--:|
| __キャラクター A__  | 20  | 5  | 10  |
| __キャラクター B__  | 10  | 20 | 5  |
| __キャラクター C__  | 5  | 10 | 20  |
:::

## 最善手の選択の割合を利用する方法

__すべての局面__ で __最善手__ を __選択する__ という、__最強の AI__ の __定義__ から、__ゲーム__ の __すべての局面__ の中で、__AI__ が __最善手を選択__ する __局面の割合__ を __計算__ して __AI__ の __強さを評価する__ という __方法も__ 考えられますが、__実際__ には __下記の理由__ で、__多くの場合__ は __その方法__ で __AI__ の __強さを評価__ することは __不可能__ です。従って、本記事では __この方法__ も __採用しません__。

* 多くのゲームでは、__局面の数__ が __多すぎる__
* __どの合法手__ が __最善手__ であるかが __わからない局面__ が __多い__
* __局面__ の __出現率__ が __偏っている__ 場合は、__正しく__ 強さを __評価できない__。例えば __ゲーム開始時__ の __局面__ は __100 % 出現__ するが、__ほとんど出現しない局面__ もある

## __総当たり__ と __勝ち抜き戦__ による方法

__複数のもの__ の __順位を決める方法__ として、 __良く使われる__ のが __総当たり戦__ と __勝ち抜き戦__ ですが、今回の記事で説明したように、__総当たり戦__ を行っても、__AI どうし__ の __相性の問題__ から、__強い AI__ が __優勝する__ とは __限りません__ し、__勝ち抜き（トーナメント）戦__ では __限られた組み合わせ__ でしか __対戦__ が __行われない__ という __問題__ があり、__運よく苦手な相手__ が __対戦する前__ に __負けてしまった__ ために __弱い AI__ が __優勝してしまう場合__ が __あります__。

ただし、__AI どうし__ の __相性の問題__ は、__多様な AI__ を __数多く用意__ することで、ほとんど __問題__ には __ならなくなります__。その __理由__ は、__相性の問題__ は、__一般的__ に __特定の AI どうし__ で __発生する__ からです。__多様な AI__ を __数多く用意__ すれば、__そのような問題__ は __全体の中__ の __一部__ として __埋もれてしまい__、__全体の結果__ に __ほとんど影響__ を __与えなくなる__ からです。従って、__総当たり戦__ は、__実際__ に __順位__ を __決める方法__ として __良く使われています__。

また、その際に、__同じくらいの強さ__ の __AI を集めて__ 対戦を行うのが __一般的__ です。__現実の世界__ でも、例えば __サッカー__ の場合は、__J1__、__J2__、__J3__ のように、__同じレベル__ の __チーム__ を __集めて__ 総当たり戦を行い、__優勝チーム__ を __決めています__。

__総当たり戦__ は、__参加者__ の __2 乗__ に __比例__ した __回数__ の __対戦__ を行う __必要__ があるという __欠点__ があるため、__参加者__ が __非常に多い場合__ には __向いていません__ 。__そのような場合__ は、__参加者__ をいくつかの __ブロック__ にわけて __総当たり戦__ を行い、__各ブロック__ の __上位者__ で __総当たり戦__ や __勝ち抜き戦__ で __順位を決める__ 方法が良く __用いられます__。

高校野球のように、__数千__ の __参加者__ がいる場合は、__勝ち抜き戦だけ__ で __順位を決める__ 場合がありますが、__勝ち抜き戦__ の場合は、__優勝するため__ には __実力以外__ にも __運が必要でしょう__。

## レーティングによる強さの定義

__AI など__ の __強さを測る方法__ を __レーティング__ と呼び、__総当たり戦__ や __勝ち抜き戦以外__ にも __様々な方法__ があります。その中で、__数学的な裏付けがある__ 有名な方法として、__イロレーティング__ があり、__サッカー__ の __FIFA ランキング__ など、__多くの競技__ で __利用__ されています。

参考までに、__イロレーティング__ の Wikipedia のリンクを示します。

https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%AD%E3%83%AC%E3%83%BC%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0

:::note
__将棋の AI__ の場合は、__[コンピュータ将棋連続対局場所 (floodgate)](http://wdoor.c.u-tokyo.ac.jp/shogi/floodgate.html)__ という、__自作__ の __将棋の AI どうし__ を __対戦__ させる __場__ があり、日々 __AI どうしの対戦__ が __行われています__。__floodgate__ では、__AI の強さ__ を、先ほど説明した __イロレーティング__ で __計測__ しており、__かなりの精度__ で、__AI の強さ__ を __測ることができます__。
:::

## 参加者が少ない場合の問題点

__強さの評価__ を行う際に、__参加者__ の __数が少ない__ と、どのような方法でも __強さ__を __正確に評価__ することは __困難__ です。__参加者__ が __少ない__ とどうしても __相性の問題__ が __発生しやすかったり__、集めた __参加者__ が __弱すぎたり__、__偏ってていたり__ した場合などでは、__そこで 1 位__ に __なったとしても__、__本当に強いか__ どうかが __分からないから__ です。

:::note
__井の中の蛙__ という __ことわざ__ があるように、__地方の大会__ で __優勝__ した人が、__全国の大会__ に参加した結果、__ぼろ負け__ してしまうことは __よくある__ ことです。
:::

残念ながら、本記事のように、__一人__ で __AI を作成__ する場合は、__多様な AI__ を __数多く集めて対戦__ させることは __難しい__ ので、代わりに __基準__ となる __`ai2`__ と、__それまでに作成__ した __最も強い AI__ と __対戦__ させることで、__AI の強さ__ を __測定しています__。

なお、__イロレーティング__ は、__数多く__ の __参加者の間__ で __多種多様な対戦__ を行う __必要がある__ ので、__一人で AI を作成__ する場合の __〇×ゲーム__ の __強さの測定__ には全く __向いていません__。


# パラドックスの例の補足

以下は、__おまけの内容__ なので、__興味がない方__ は __読み飛ばして__ も __構いません__。

実は、__今回の記事__ の __パラドックスの例__ で説明した __下図__ の __ゲームの例__ は、__修正前__ の __`ai11s`__ VS __`ai10s`__ を __元に__ して __作ったもの__ です。また、パラドックスの例の __A__、__B__、__C__ という AI は、__`ai10s`__、__修正前__ と __修正後__ の __`ai11s`__ を __元に作った__ ものです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/e29248b5-5e97-2bcd-f732-4635b152d63e.png" width="200">

## 局面の対応

下記は、__上図__ の __ゲームの局面__ と、__修正前__ の __`ai11s`__ VS __`ai10s`__ の __局面__ の __対応__ を表します。

<table>
  <tr>
    <td><strong>上図のゲーム</strong></td>
    <td>局面 1</td>
    <td>局面 2</td>
    <td>局面 3</td>
  </tr>
  <tr>
    <td><strong><code>ai11s</code> VS <code>ai10s</code></strong></td>
    <td>3 手目の局面</td>
    <td>3 手目で (2, 2) に<br>着手した局面</td>
    <td>3 手目で (0, 2) に<br>着手した局面</td>
  </tr>
  <tr>
    <td><strong>類似点</strong></td>
    <td>どちらの合法手も<br>最善手である</td>
    <td>引き分けと先手の<br>勝利になる</td>
    <td>引き分けになる</td>
  </tr>
</table>  

__下図__ は __パラドックスの例__ の __ゲームの局面__ の図と、__修正前__ の __`ai11s`__ VS __`ai10s`__ の __着手の図__ を __簡略化__ した図を並べたものです。__見比べる__ ことで、__両者__ が __同じ構造__ を __持っている__ ことが __わかる__ のではないかと思います。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/bd99f565-3572-3449-fa7c-6a280ca7cd3f.png" width="200">
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/1150e441-c92a-63ca-e6fa-8aec1d02bc35.png" width="250">

## AI の対応

下図は __A__、__B__、__C__ と、__`ai10s`__、__修正前__ と __修正後__ の __`ai11s`__ の対応表です。

<table>
  <tr>
    <td><strong>上図のゲーム</strong></td>
    <td>A</td>
    <td>B</td>
    <td>C</td>
  </tr>
  <tr>
    <td><strong><code>ai11s</code> VS <code>ai10s</code></strong></td>
    <td>修正後の<br> <strong><code>ai11s</code></strong></td>
    <td>修正前の <strong><code>ai11s</code></strong> で、局面 1 で<br>上を選択した場合</td>
    <td><strong><code>ai10s</code></strong> で、局面 2 で<br>下を選択した場合</td>
  </tr>
</table>  

__修正前__ の __`ai11s`__ や __`ai10s`__ は __ランダムな着手__ を行いますが、__修正前__ の __`ai11s`__ VS __`ai10s`__ で、__`ai11s`__ が __勝利する__ のは、__上記__ の __着手__ が __選択__ された __場合だけ__ なので、__上記の表__ の __着手__ が __選択__ された __場合__ に __限定して__ 話を進めることにします。
 
下図は、__A VS B__、__B VS C__、__修正前__ の __`ai11s`__ VS __`ai10s`__、__修正後__ の __`ai11s`__ VS __`ai10s`__、で __上記の表__ に従って __選択__ する __合法手__ を表します。__図から__、__対応する AI__ が、__同様の着手__ を __選択__ することが分かります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/58ba3384-b9ed-5cb9-d910-565120af05ae.png" width="500">

## パラドックスの例による `ai11s` VS `ai10s` の説明

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

* __B VS C__ と __修正前__ の __`ai11s`__ VS __`ai10s`__ は __同じ理由__ で __B__ と __`ai11s`__ が __勝利する__
* __A VS C__ と __修正後__ の __`ai11s`__ VS __`ai10s`__ は __同じ理由__ で __引き分けになる__

従って、__修正後__ の __`ai11s`__ が __`ai10s`__ に __勝てなくなった__ 理由は、__パラドックスの例__ で __説明__ した __理由__ と __同じ理由__ であることがわかりました。

# 今回の記事のまとめ

今回の記事では、これまでに曖昧なままにしてきた、__最強の AI__ の __定義__ を行うために、__二人零和有限確定完全情報ゲーム__ という __ゲームの分類__ を紹介し、__この分類__ のゲームの __最善手__ と、__最強の AI__ の __定義__ と __性質__ の説明を行いました。

また、__AI の修正__ による __結果の解釈__ について説明し、__修正後__ の __`ai11s`__ が __`ai10s`__ に __勝てなくなったこと__ が __問題ではない__ ことを示しました

最後に、__AI の強さ__ を __測定する方法__ を __いくつか紹介__ しました。

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

今回の記事では入力したプログラムはありません。

# 次回の記事

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

# 更新履歴

| 更新日時 | 更新内容 |
|:--|:--|
| 2024/03/06 | オセロの局面の数を、26830 から 5478 に修正しました |



[^1]:Wikipedia の[リンク先](https://ja.wikipedia.org/wiki/%E4%BA%8C%E4%BA%BA%E9%9B%B6%E5%92%8C%E6%9C%89%E9%99%90%E7%A2%BA%E5%AE%9A%E5%AE%8C%E5%85%A8%E6%83%85%E5%A0%B1%E3%82%B2%E3%83%BC%E3%83%A0)に記述されているように、__厳密__ には、__チェス__ や __囲碁__ は __有限__ の性質を __満たしません__ が、__有限でない__ のは __例外的__ な場合だけなので、__一般的__ には __有限__ の性質を持つと __みなされる__ ようです
[^2]:https://www.nara-wu.ac.jp/math/personal/shinoda/legal.pdf
[^3]:https://link.springer.com/chapter/10.1007/978-3-540-75538-8_8 (有料の論文です）
[^4]:__その方法__ については、__探索型の AI__ を __説明__ する際に __紹介__ します
[^5]:__必ず勝つ__ ことを「__必勝__」のように __表現__ しますが、__必ず引き分け__ になることを表す「必分け」のような __用語__ は __存在しない__ ようです。誰か知っている方がいれば教えて頂ければうれしいです。