Pythonで〇×ゲームのAIを一から作成する　その59　演繹法とヒューリスティックによる問題の解決

# 目次と前回の記事

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

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/059/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/c1285c93cbfbdbdc7b77)で、__〇×ゲーム__ の __強い AI__ を __作成__ するための __条件__ を、__必要条件__、__十分条件__、その __どれでもない条件__ に __分類__ して __説明__ を行いましたが、その際にはまだ __最強の AI__ とはどのようなものであるかの __説明__ を __行っていません__ でした。

そのため、__これまでの記事__ で __行ってきた__、__さまざま__ な __ルールの条件__ を __考え__、その __条件を処理__ するプログラムを __記述__ することで、__強い AI__ を __作成__ するという __方法__ が、__最強の AI__ の __作成__ に __つながる方法であるか__ どうかは __説明__ していません。


前回の記事で、__二人零和有限確定完全情報ゲーム__ における、__最善手__ と __最強の AI__ を __下記__ のように __定義__ しました。

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

__最強の AI__ とは、__すべての局面__ で、__最善手__ を __選択する AI__ のことである。
:::

今回の記事では、__この定義__ に __基づいて__、__〇×ゲーム__ の __最強の AI__ を作るための __条件__ を説明し、__これまでの手順__ と、__最強の AI__ を __作る手順__ の __関係__ について __説明__ します。

# 用語の定義

前回の記事で「__最強の AI__」の __定義__ を行いましたが、__これまでの記事__ では、「__これまでに作成__ した __最強の AI__」のように、__全く同じ用語__ を、__異なる意味__ で __利用__ してきました。__後者__ は、「__これまでに作成__ した __AI の中__」での __最も強い AI__ という __意味__ なので、__前者__ の用語とは __意味が異なります__。これでは __紛らわしい__ ので、以後は、__後者の場合__ は、__これまでに作成__ した中で「__最も強い AI__」のように、__用語__ を __使い分ける__ ことにします。

:::note warn
| 用語 | 用語の意味 |
|:--|:--|
| __最強の AI__  | [前回の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E6%9C%80%E5%BC%B7%E3%81%AE-ai-%E3%81%A9%E3%81%86%E3%81%97%E3%81%AE%E5%AF%BE%E6%88%A6)で定義した、__文字通り__ の __最強 の AI__ のことを表す  |
| __最も強い AI__  | __いくつかの AI の中__ で __最も強い AI__ という意味  |
:::

# 〇×ゲームの最強の AI の再定義

__これまで__ に行ってきた __AI__ の __作成方法__ によって、__最強の AI__  を __作成できる__ ことを __示す__ ために、__下記__ の __最強の AI__ の __定義__ を、__別の言い方__ で __再定義__ することにします。

「__最強の AI__ とは、__すべての局面__ で、__最善手__ を __選択する AI__ のことである」

[前回の記事](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)のノートで、__下記__ のような __説明__ を行いました。

* __最善手__ を __選択しない__ 場合は __局面の状況__ が __悪化__ する
* __〇×ゲーム__ の場合は、__状況の悪化__ には 「__必勝 → 引き分け__」、「__必勝→必敗__」、「__引き分け→必敗__」という __3 種類__ がある
* __合法手__ を、__状況__ が __何段階悪化するか__ によって __分類__ すると、__下記の表__ のようになる

この表は、__局面の状況__ で、それぞれに __分類される着手__ を __行った場合__ に、__局面の状況__ が __どのように変化するか__ を表します。__空欄__ は __合法手__ が __存在しない__ ことを表します。

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | 必勝  | 引き分け  | 必敗  |
| __引き分け__  | 引き分け  | 必敗  |   |
| __必敗__ | 必敗  |   |   |

先程説明したように、__最強の AI__ の __定義__ は「__すべての局面__ で __最善手__ を __選択__ する」なので、__上記の表__ を使って __最強の AI__ の __再定義__ を行うと、「__すべての局面__ で、下記の __太字の合法手__ を __選択__ する」のようになります。

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __必勝__  | 引き分け  | 必敗  |
| __引き分け__  | __引き分け__  | 必敗  |   |
| __必敗__ | __必敗__  |   |   |

表からわかるように、__必敗の局面__ では、__すべて__ の __合法手__ が __最善手__ になるので、__すべての AI__ が __必敗の局面__ では __最善手__ を __選択__ します。従って、上記の表から __必敗の局面__ の __状況__ を __削除__ することができます。

:::note warn
__最強の AI__ とは、__下記__ の __表__ の __すべて__ の __局面の状況__ で、__太字__ の __合法手__ を __選択する AI__ である。

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __必勝__  | 引き分け  | 必敗  |
| __引き分け__  | __引き分け__  | 必敗  |   |
:::

# これまでに作成したルールの条件の意味

__これまで__ に __作成__ した __ルール__ の __条件__ によって、__最強の AI__ に __近づく__ ことができる __理由__ を __説明__ します。

__これまで__ の記事で __作成__ した __AI__ の __ルールの条件__ は、__下記__ を __目指す__ ものです。

1. __真ん中__ のマスに __着手__ する
2. __自分__ が __勝利できる__
3. __相手__ が __勝利できない__
4. __自分__ が __勝利できそうになる__
5. __相手__ が __勝利できなさそうになる__

上記の条件のうちの、__条件 2__ と __3__ は、__下記__ のように __言い換える__ ことができます。

2\. __自分の必勝__ の __局面__ で __最善手__ を __選択__ する
3\. __自分の必敗__ の __局面以外__ で、__必敗の局面__ になるような __合法手__ を __選択しない__

__この 2 つ__ の __それぞれの条件__ と、__最強の AI__ の __定義__ との __関係__ について説明します。

## 自分が勝利できる条件

「__自分__ が __勝利できる__」__条件__ は、__必勝の局面__ で、__最善手__ を __選択__ するという __条件__ です。従って、__この条件__ は、__必勝の局面__ で __下記の表__ の <font color="blue">青字</font> の合法手を __選択__ し、__その結果__ <font color="red">赤字</font> の合法手が __選択されなくなります__。一方、__この条件__ は、__引き分けの局面__ では __適用されない__ ので、__引き分けの局面__ では __すべての合法手__ が __選択__ される __可能性__ が __あります__。

* __太字__：__最強の AI__ が __選択__ する __必要がある__ 合法手
* <ins>下線</ins>：__ルールの条件__ によって __選択される__ 合法手
* <font color="blue">青字</font>：__ルールの条件__ によって、__結果__ として __選択__ が __行われる__ 合法手
* <font color="red">赤字</font>：__ルールの条件__ によって、__結果__ として __選択__ が __行われなくなる__ 合法手
* 黒字：__ルールの条件__ とは __無関係__ な合法手で、__選択__ が行われる __可能性がある__ 合法手

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __<font color="blue"><ins>必勝</ins></font>__  | <font color="red">引き分け</font>  | <font color="red">必敗</font>  |
| __引き分け__  | __引き分け__  | 必敗  |   |

表から、__この条件__ は __引き分けの局面__ で、__最善手ではない__、__必敗の局面__ につながる __合法手__ が __選択__ される __可能性がある__ という点が、__最強の AI__ の __定義__ と __異なります__。

:::note
上記の場合は、「__<font color="blue"><ins>必勝</ins></font>__」の部分に <font color="blue">青字</font> と <ins>下線</ins> の __両方が設定__ されているので、<font color="blue">青字</font> と <ins>下線</ins> の __違い__ が __わかりづらい__ と思います。__次の例__ では、<font color="blue">青字</font> と <ins>下線</ins> が __別々__ に __設定される__ ので、__その違い__ については __次の例__ で __説明__ します。
:::

## 相手が勝利できない条件

「__相手__ が __勝利できない」条件__ は、__必敗の局面__ に __つながる合法手__ を __選択しない__ という __条件__ です。従って、__この条件__ によって、__下図__ の 
取り消し線
 が __引かれている__、__必敗の局面__ に __つながる合法手__ が __選択されない__ ようにすることが __できます__。__その結果__、__それ以外__ の <font color="blue">青字</font> の __合法手__ が __選択される__ ようになります。

* 
取り消し線
：__ルールの条件__ によって __選択__ を __行わない__ 合法手

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __<font color="blue">必勝__</font>  | <font color="blue">引き分け</font>  | 
<font color="red">必敗</red>
  |
| __引き分け__  | __<font color="blue">引き分け</font>__  | 
<font color="red">必敗</font>
  |   |

表から、__この条件__ は __必勝の局面__ で、__最善手ではない__、__引き分けの局面__ につながるの __合法手__ が __選択__ される __可能性がある__ という点が、__最強の AI__ の __定義__ と __異なります__。

:::note
__先程__ の場合と __異なり__、<font color="blue">青字</font> の __合法手__ は、__条件__ によって __直接選択__ される __合法手ではなく__、__必敗の局面__ に __つながる合法手__ を __選択__ から __除外する__ ことで、__結果__ として __選択される__ ようになった __合法手__ です。そのため、__上記__ の表では、__選択される__ <font color="blue">青字</font> の __合法手__ には __下線__ を __引きません__。

__１ つ前__ の __自分が勝利できる__ 条件の __表で__ 、「__必勝の局面__」の <font color="red">赤字</font> の __合法手__ に 
取り消し線
 が __引かれていない理由__ も __同様__ で、<font color="red">赤字</font> の __合法手__ は、__ルールの条件__ によって __直接除外__ されている __わけではなく__、<ins>下線</ins> の __合法手__ を __選択する__ ことによって、__結果__ として __除外された__ からです。
:::

:::note
__最強の AI__ の __定義__ を __別の言い方__ で __再定義__ した __理由__ は、そのように定義し直すことで、__ルールの条件__ が __選択__ する __合法手__ を、__最強の AI__ の __定義__ の __表__ を使って __説明できるようになる__ からです。
:::

## 2 つの条件の組み合わせ

「__自分__ が __勝利できる__」条件と「__相手__ が __勝利できない__」条件を __組み合わせる__ ことで、__下記__ の表ように、__選択__ される <font color="blue">青字</font> の __合法手__ が、__最善手__ を表す __太字__ の __合法手のみ__ になるので、__すべて__ の __局面の状況__ で、__最善手のみ__ が __選択される__ ようになります。従って、__最強の AI__ を __作成する__ ためには、「__自分__ が __勝利できる__」条件と、「__相手__ が __勝利できない__」条件の __2 つの条件__ を __組み合わせればよい__ ことが __わかります__。

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __<font color="blue">必勝__</font>  | <font color="red">引き分け</font>  | 
<font color="red">必敗</red>
  |
| __引き分け__  | __<font color="blue">引き分け</font>__  | 
<font color="red">必敗</font>
  |   |

従って、__最強の AI__ の __定義__ を、__以下__ のように、さらに __再定義__ することができます。

__最強の AI__ とは、下記の __両方の条件__ を __満たす AI__ である。

1. __必勝の局面__ になる __合法手__ が __存在する場合__ は、__必ずその合法手__ を __選択する__
2. __必敗以外の局面__ で、__必敗の局面__ につながる __合法手__ を __選択しない__

上記の事から、これまでの __強い AI__ を __作成する__ ための __ルール__ の中の __下記の条件__ が、__最強の AI__ を __作成__ するための __正しい条件__ であることが __分かります__。

* __自分__ が __勝利できる__
* __相手__ が __勝利できない__

:::note
上記で __両方の条件__ を __満たす__ と説明しましたが、__1 つ目__ の __条件__ が __満たされた場合__ は、__必敗の局面__ になる __合法手__ を __選択していない__ ので、__2 つ目__ の __条件__ は __必ず満たされます__。逆に __2 つ 目__ の __条件__ が __満たされた__ 場合に、__1 つ目__ の条件が __満たされる__ とは __限らない__ 点に __注意__ して下さい。
:::

## 他の条件の考察

__最強の AI__ の __定義__ を __満たす条件__ は、__他にも存在__ します。

例えば、「__相手__ が __勝利できない__」という __条件__ の __代わり__ に、「__引き分けの局面__ で、__引き分けの局面__ に __つながる__ 合法手を __選択する__」という __条件__ はどうでしょうか。__下記__ は、__そのような条件__ によって __選択__ される __合法手__ の __表__ です。

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __必勝__  | 引き分け  | 必敗  |
| __引き分け__  | __<font color="blue"><ins>引き分け</ins></font>__  | <font color="red">必敗</font>  |   |

__この条件__ と、「__自分__ が __勝利できる__」条件を __組み合わせる__ ことで、__下記__ の表のように、__すべて__ の __局面の状況__ で、__最善手のみ__ が __選択される__ ようになります。

| 局面の状況 | 最善手 | 1 段階悪化する着手 | 2 段階悪化する着手 |
|:-:|:-:|:-:|:-:|
| __必勝__  | __<font color="blue"><ins>必勝</ins></font>__  | <font color="red">引き分け</font>  | 
<font color="red">必敗</red>
  |
| __引き分け__  | __<font color="blue"><ins>引き分け</ins></font>__  | <font color="red">必敗</font>  |   |

従って、「__引き分けの局面__ で、__引き分けの局面__ に __つながる__ 合法手を __選択する__」という __条件__ でも __最強の AI__ を __作成__ すること __可能__ ですが、__この条件__ には __大きな欠点__ が __あります__。それは、__この条件__ で __合法手__ を __選択する__ ためには、__局面の状況__ が「__引き分けの局面__」__であるか__ どうかを __判定__ する __必要がある__ ことです。__多くの局面__ では __局面から__、その __局面の状況__ が __どうなっているか__ を __判定する__ ことは __簡単__ なこと __ではありません__。それに対し、「__自分__ が __勝利できる__」という __条件__ や、「__相手__ が __勝利できない__」という __条件__ は、__局面の状況__ を __判定__ する __必要がない__ 点が __優れています__。

:::note
もちろん、「__引き分けの局面__ で、__引き分けの局面__ に __つながる__ 合法手を __選択する__」という __条件を満たす__ 合法手を __見つける方法__ を __思いつく__ ことが __できれば__、__その方法__ を使って __最強の AI__ を __作成する__ ことは __可能__ です。
:::

## 必勝の局面につながる合法手が複数ある場合

実は __先程定義__ した下記の __最強の AI__ の __定義__ は、__必勝の局面__ になる __合法手__ の __数が 1 つ__ の場合は __正しい__ ですが、__複数存在__ する場合は __厳密__ では __ありません__。

__最強の AI__ とは、下記の __両方の条件__ を __満たす AI__ である。

1. __必勝の局面__ になる __合法手__ が __存在する場合__ は、__必ずその合法手__ を __選択する__
2. __必敗以外の局面__ で、__必敗の局面__ につながる __合法手__ を __選択しない__

__必勝の局面__ になる __合法手__ が __複数存在__ する場合は、__その中__ の __どの合法手__ を __選択__ しても、__最善手を選択__ したことになります。従って、__上記の定義__ の __1 つ目の条件__ は、__厳密__ には __下記__ のようになります。

__必勝の局面__ になる __合法手__ が __存在する場合__ は、__必ずその合法手__ の __いずれか__ を __選択する__

例えば、__必勝の局面__ になる __合法手__ が __複数ある__ 場合は、__常に__ そのうちの __1 つのみを選択__ する __AI__ であっても、その中から __ランダムに選択__ する __AI__ であっても、__最強の AI__ の __定義__ を __満たします__。[前回の記事](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#%E8%A4%87%E6%95%B0%E3%81%AE%E6%9C%80%E5%BC%B7%E3%81%AE-ai)で説明した、__最善手__ が __複数存在__ する場合は、__最強の AI__ も __複数存在__ するという __説明__ を __思い出してください__。

__2 つ目の条件__ は、特に __修正する必要__ は __ありません__ が、__1 つ目__ と __2 つ目__ の __条件__ が __同時に満たされる__ 合法手が __複数存在した場合__ に、その中の __どの合法手__ を __選択__ しても __構わない点__ は __上記と同様__ です。

下記は、__最強の AI__ の __定義__ を __修正__ したものです。

:::note warn
__最強の AI__ とは、下記の __両方の条件__ を __満たす AI__ である。

1. __必勝の局面__ になる __合法手__ が __存在する場合__ は、__必ずその合法手__ の __いずれか__ を __選択する__
2. __必敗以外の局面__ で、__必敗の局面__ につながる __合法手__ を __選択しない__
:::

ところで、__この 2 つの条件__ は、__[ルール 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) の時点__ ですでに __ルール__ に __組み込まれている__ ので、__ルール 8__ を __実装した時点__ で __最強の AI__ に __なっていない__ のは __変__ だと __思いませんか__？実際には、それにもかかわらず、__ルール 9__、__10__、__11__ のように __条件を追加__ することで、__AI__ が __強くなっています__。そのようなことが起きる理由について少し考えてみて下さい。
## これまでのルールの条件の問題点

__これまで__ に __ルール__ に __組み込んだ__「__自分__ が __勝利できる__」や「__相手__ が __勝利できない__」という __条件__ には、__特定の局面だけ__ でしか __適用できない__ という __問題__ が __あります__。

### ルール 11 の自分が勝利できる条件の問題点

__ルール 11__ の「__自分__ が __勝利できる__」条件には __下記__ の __2 つの条件__ が __あります__。

1． __勝てる場合__ に __勝つ__
2． 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う

__これらの条件__ が、__すべて__ の __必勝の局面__ で __最善手__ を __選択__ することが __できない__ ことを __示します__。下記の __3 つの局面__ は、いずれも __〇 の手番__ で、__〇 の必勝__ の __局面__ です。
 
<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/caf5cb35-4f22-2a4b-1080-87a8d94c32a2.png" width="300"> 

下記は、その __理由__ です。

* __左の局面__：__(2, 2)__ に __着手__ することで __勝利する__
* __真ん中の局面__：__(0, 1)__ または __(0, 2)__ に __着手__ することで、「__自 2 敵 0 空 1__」が __2 つ以上存在__ するようになるので、__必勝の局面__ である
* __右の局面__：__(0, 0)__ に __着手__ すると、__相手__ は __〇 の勝利__ を __阻止するため__ に __(2, 2)__ に __着手__ する __必要__ がある。__その結果__、__上記__ の __真ん中の局面になる__ ため、__必勝の局面__ である

:::note
実は、__右の局面__ は、__(1, 2) 以外__ は、すべて __必勝の局面__ につながる __最善手__ です。興味がある方はその理由を実際に確認してみて下さい。
:::

下記は、上記の __3 つの局面__ に対して、__ルール 11__ の「__自分__ が __勝利できる__」__2 つの条件__ で __最善手__ を __選択できるか__ どうかを表す表です。__表から__ わかるように、__右の局面__ に対して、__どちらの条件__ も __最善手__ を __選択__ することは __できません__。

|  | 左の局面 | 真ん中の局面 | 右の局面 |
|:--|:-:|:-:|:-:|
| __勝てる場合__ に __勝つ__  | 〇  | ×  | ×  |
| 「__自 2 敵 0 空 1__」が __2 つ以上__<br>__存在__ する着手を行う  | ×  | 〇  | ×  |

つまり、__ルール 11__ の「__自分__ が __勝利できる__」2 つの __条件だけ__ では、__すべて__ の __必勝の局面__ で __最善手を選択__ するには、__条件が足りない__ ということです。

### ルール 11 の相手が勝利できない条件の問題点

__ルール 11__ の「__相手__ が __勝利できない__」__条件__ は、具体的には『「__自 0 敵 2 空 1__」が __存在__ する着手を __行わない__』という条件ですが、__この条件__ だけでは、__すべて__ の __必敗以外の局面__ で __必敗の局面__ に __つながる合法手__ を __選択しない__ ようにすることは __できません__。__具体例__ として、__下図の局面__ があります。__証明__ は __今後の記事__ で行いますが、__この局面の状況__ は、「__引き分けの状況__」です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8795190e-ed5b-25bc-de49-5d524b39913d.png" width="70">

__この局面__ では、__(0, 0)__ などの __隅の合法手__ が __最善手__ で、__(1, 0)__ などの __辺の合法手__ は __最善手__ では __ありません__。__(1, 0)__ が __最善手ではない理由__ は、__(1, 0)__ に __着手__ すると __先程__ の図の __右の局面__ になり、__その局面__ は __先程説明__ したように、__× の必敗の局面__ であるからです。

しかし、『「__自 0 敵 2 空 1__」が __存在__ する着手を __行わない__』という __条件__ だけでは、__上記の局面__ で __(1, 0)__ の __着手__ の __選択__ を __阻止__ することは __できません__。

__上記__ から、__ルール 11__ の __条件__ は、__最強の AI の定義__ を __満たさない__ ことがわかります。

## これまでの AI の作成の手順の意味と問題点

__これまで__ の記事で __作成__ した、下記の __AI__ の __ルールの条件__ のうち、__2__ と __3__ は、__最強の AI__ の __定義__ の __条件と同じもの__ です。従って、__これまで__ の __強い AI__  の __作成の手順__ の __方針__ は __間違っていない__ ことが __わかりました__。

1. __真ん中__ のマスに __着手__ する
2. __自分__ が __勝利できる__
3. __相手__ が __勝利できない__
4. __自分__ が __勝利できそうになる__
5. __相手__ が __勝利できなさそうになる__

また、これまでに __作成__ した __ルールの条件__ によって、__最強の AI__ が __作れていない__ のは、それらが __最強の AI__ の __定義__ の __条件__ の __一部しか満たさない__ ことが __原因__ です。

# 演繹法とヒューリスティックによる問題の解決

__最強の AI__ を __作成__ するための __条件__ と、__これまでに作成__ してきた __ルール__ の __問題点__ が __わかりました__ が、その __問題点__ を __解決__ することは __簡単ではありません__。その __理由を説明__ するために、__問題を解決__ する __手法__ を __分類__ し、__それぞれの分類__ の __性質__ を __説明__ します。

## 演繹法

__演繹法__ とは、__問題__ の __解決方法__ を、__問題__ の __前提__ から __論理的__ に __導き出す方法__ です

参考までに、演繹の Wikipedia のリンクを下記に示します。

https://ja.wikipedia.org/wiki/%E6%BC%94%E7%B9%B9

例えば、__ルール 11__ の「__自分__ が __勝利できる__」__合法手__ の __条件__ である、『「__自 2 敵 0 空 1__」が __2 つ以上存在__ する着手を行う』という条件は、[以前の記事](https://qiita.com/ysgeso/items/c1285c93cbfbdbdc7b77#2-%E3%81%A4%E7%9B%AE%E3%81%AE%E5%8D%81%E5%88%86%E6%9D%A1%E4%BB%B6%E3%82%92%E7%B5%84%E3%81%BF%E8%BE%BC%E3%82%93%E3%81%A0-ai)で、__〇×ゲーム__ の __前提__ となる __ルールから__、__筋道をたてて__、__論理的__[^1] に __見つけた条件__ です。このような __演繹法__ で __見つけた手順__ には、__下記__ のような __性質__ があります。

* __前提__ が __正しければ__、__演繹__ によって __導き出された答え__ は、__100 % 正しい__
* __手順に従う__ ことができれば、__100 % 問題を解決する__ ことが __できる__
* __手順の意味__ を __理解できなくても__、手順を覚えれば __誰でも利用__ することが __できる__

逆に言えば、__前提__ が __間違っていれば__、__正しい答え__ を __導き出す__ ことは __できません__。例えば、「__私は万能の神である__」という __間違った前提__ からは、「__私は__ 万能なので __空を飛べる__」などの、__間違った答え__ を __導くこと__ が __できてしまいます__。従って、__演繹法__ では __前提が正しい__ ことが __非常に重要__ です。

__演繹法__ の __代表例__ としてよく取り上げられるのは、「__A ならば B__ である」、「__B ならば C__ である」という __事実__ から「__A ならば C__」であるという __事実__ を __導く__、__三段論法__ があります。__本記事__ でこれまでに何度も行ってきた、__何かを説明した後で__、その __説明を元__ に、「__従って__ 〇〇である」のような __説明__ は __演繹法__ を使った __説明__ です。

他の __演繹法__ の __例__ としては、下記の $ax^2 + by + c = 0$ という __二次方程式__ の __解の公式__ があります。この __公式__ は、__論理的__ な __手順__ で __導かれたもの__ であり、__公式の意味__ を __理解しなくても__、__誰でも__ この __公式を使って__、__二次方程式の解__ を __求める__ ことが __できます__。

$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

:::note
__二次方程式__ の __解の公式__ は、__複雑な問題__ でも、__答え__ を __計算する方法__ さえ __わかっていれば__、__誰でも答えを求める__ ことが __できる__ という __例__ として出したものです。

__〇×ゲーム__ に __二次方程式__ の __解の公式__ は __必要ない__ ので、上記の公式の __意味__ や __使い方__ を __理解__ する必要は __ありません__。
:::

__演繹法__ の __問題点__ は、世の中の __多くの問題__ は、__演繹法__ を使って __答えを求める手順__ を __見つける__ ことが __できない__ ことです。また、__手順__ を __みつける__ ことが __できても__、それを __実際に行う__ ためには、__時間がかかりすぎる__ ような __問題__ もあります。

例えば、何らかの __スポーツ__ で __世界最強のチーム__ を __見つける方法__ として、__総当たり戦__ があります。__総当たり戦__ を行う __手順__ は、__全チーム__ の __全ての組み合わせ__ で __対戦を行う__ というものですが、実際に __総当たり戦を行う__ ためには、__チーム数__ が $x$ の場合は、$x(x-1)/2$ 回の __対戦を行う必要__ があります。例えば、__100 チーム__ で __総当たり戦__ を行う場合は $100 * 99 / 2 =$ __4950 回__ もの __対戦__ を __行う必要__ があります。

__問題__ を __解くための方法__ が __わからない例__ としては、「__金持ちになる__」という問題があります。おそらく、__誰でも__ この手順を行えば、__金持ちになる__ ことができるという __手順__ は __存在しない__ でしょう。他にも、「__嘘を見抜く__」という問題に対する __確実な手順__ も __存在しない__ でしょう。__一般的__ に、__現実の世界__ の __多くの問題__ は、__物事__ の __因果関係__[^2]が __複雑__ に __絡み合う__ 場合が __多い__ ため、__問題を解く__ ための、__方法__ を __みつける__ ことは __不可能__ です。

## 近似解

__100 % 正しい__ 答えを __得る手順__ が __わからなくても__、__正解__ に __一定以上近い答え__ を __得る手順__ であれば __知ることができる__ 場合があります。__そのような答え__ の事を __近似解__ と呼び、__正しい答え__ と __近似解の差__ の事を __誤差__ と呼びます。例えば、__鉛筆の長さ__ を __正確に求める__ ことは __不可能__ ですが、__定規__ を使えば、__最大で 1 mm__ の __誤差__ で __長さを測る__ ことが __できます__。なお、__近似解__ を __求める方法__ も、__演繹法の一種__ です。

近似解に対して、__100 % 正しい答え__ の事を、__最適解__ と呼びます。

__近似解__ はには __必ず誤差__ が __あります__ が、__正解より__ も __簡単に求める__ ことが __できる__ 場合が多いので、__誤差__ が __問題にならない__ ような __場合__ などで __良く使われます__。

例えば、__986 × 1023__ という __計算を行う__ のは __面倒__ ですが、__大雑把な答え__ でも __かまわない__ 場合は、どちらも __1000 に近い数字__ であることから、__1000 × 1000 = 100 万__ という __簡単な計算__ で求められる __近似解で代用__ することが __できます__。

__先程__ の __100 チーム__ の __総当たり戦__ を行う __スポーツの例__ では、下記の方法で、__最も強いチーム__ の __近似解__ を __求める__ ことが __できます__。

* __100 チーム__ を __10 チームずつ__ に __グループ分け__ する
* __グループごと__ の __10 チーム__ の __総当たり戦__ を行う
* __グループで優勝__ した __10 チーム__ で __総当たり戦__ を行う

__この方法__ の場合の __試合数__ は __下記__ の方法で __求める__ ことが __できます__。

* 10 チームの総当たり戦の __試合数__ は、$10 × 9 / 2 =$ __45 試合__ である
* 10 チームの総当たり戦は、__10 グループ__ と、決勝の総当たりで、__11 回__ 行う
* 従って、総試合数は、 $45 × 11 = $ __495 試合__ である

このように、__近似解__ の場合の __試合数__ は、先ほどの __100 チーム__ で __総当たり戦__ を行った __場合__ である __4950 試合__ の  __1/10__ になり、__大幅に減らす__ ことが __できます__。

一方、たまたま __強豪チーム__ が __多いグループ__ に __当たってしまった__ ため、__強いチーム__ が __グループ__ の __リーグ戦__ で __勝ち残れない__ というようなことがあるため、__優勝チーム__ が __本当__ に __世界一のチーム__ であるとは __限らない__ という __誤差__ があります。

なお、__最初から勝ち抜き戦__ で __優勝を決める__ 場合は、__試合数__ は __99 試合__ ですみますが、__さらに精度が落ちる__ でしょう。__夏の全国高校野球選手権__ は、毎年 __約 3500__ もの __チームが参加__ するので、__精度を犠牲__ にして、__最初から勝ち抜き戦__ を __採用__ しています。

__ルール 11__ の 下記の __3 つの条件__ は、いずれも、__最強の AI__ の __定義__ の __条件__ の __一部を満たす__ 条件なので、__ルール 11__ の __下記の条件__ のみによって __作られた AI__  は、__最強の AI__ の __近似解__ ということができます。

* __勝てる時__ に __勝つ__
* 「__自 1 敵 2 空 1__」__が存在__ する __着手__ を __行わない__
* 「__自 2 敵 0 空 1__」が __2 つ以上存在__ する __着手__ を __行う__ 	

一方、__近似解__ であっても __求める手順__ が __わからなかったり__、__手順__ を行うために __時間がかりすぎる__ 場合があります。また、__近似解__ では、__精度__ が __低すぎる__ という場合もあります。そのような場合は、__ヒューリスティック__ という __手法__ が使われます。

## ヒューリスティック

__ヒューリスティック__ は、__心理学__ や、__コンピュータ科学__ などで使われる __用語__ で、その __意味__ は __心理学__ と __コンピューター科学__ で __若干異なります__。

### 帰納法とは何か

__いずれの場合__ でも、__経験__ に __基づく__、__帰納法__ に分類される __手法__ です。__帰納法__ は、__経験から__ 問題に関する __法則を推測__ することで __問題を解く__ という方法なので、演繹法と異なり、__100 % 正しい答え__ は __得られません__ が、__理屈__ が __分からなくても__、__ある程度正しい答え__ が得られると __考えられる方法__ を __求めることができる__ という __利点__ があります。

たとえば、__毎朝日の出__ を __観察__ することで、__その経験__ から __太陽__ は __東から昇る__ という、__おそらく正しい__ であろう __法則を知る__ ことができますが、その際に、太陽が東から昇る __理由はわかりません__。__経験則__ が必ずしも __正しいとは限らない例__ として、__中世まで__ は、__太陽__ が __地球の周りをまわっている__ という、__天動説__ が __信じられていた__ ことが挙げられます。これには __宗教的な理由__ もありますが、__太陽の動きを見た際__ に、__太陽__ の方が __地球の周りをまわっている__ ように __見える__ という __経験か__ らの __間違った推測__ も __一因__ でしょう。

一方、__地球の自転__ や __太陽の位置__ などの __法則__ を __調べ__、__太陽__ が __東から昇る__ ことや、__地球__ が __太陽の周りをまわっている__ ことを __論理的__ に __導き出す__ のが __演繹法__ です。

参考までに、Wikipedia の帰納とヒューリスティックのリンクを示します。

https://ja.wikipedia.org/wiki/%E5%B8%B0%E7%B4%8D

https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%A5%E3%83%BC%E3%83%AA%E3%82%B9%E3%83%86%E3%82%A3%E3%83%83%E3%82%AF

### 心理学におけるヒューリスティック

__心理学__ における、__ヒューリスティック__ とは、__その手順__ で __問題を解く__ ことができる __保証はない__ が、自分の __経験など__ から __有効である可能性が高い__ と思われる __手順__ を __用いる__ という __手法__ のことです。__ヒューリスティック__ は日本語で、__発見的手法__ と呼ばれますが、__経験を元__ に __問題を解決__ することから、__経験則__ と __呼ばれる__ こともあります。

__ヒューリスティック__ は、__問題__ を __厳密に解く__ ための __手法__ や __近似解__ を __求める__ ための __手法__ が __発見されていない場合__ や、__問題を解くため__ に __時間をかけることができない__ 場合などで __用いられます__。なお、__ヒューリスティック__ は、__経験の少なさ__ や、__間違った経験の解釈__ を行うなどの __理由__ で、__正しい答え__ を __得られない可能性__ がある点に __注意__ が必要です。__ヒューリスティック__ によって生まれる、__認知上の偏り__ を __認知バイアス__ と呼びます。

__ヒューリスティックの例__ をいくつか挙げます。

__正解を知らない__ クイズの __問題を解く__ 場合に、__インターネットで検索__ するなどの __方法__ で、__時間をかければ正解を求める__ ことが __できます__ が、答えるまでの __制限時間__ がある場合は __その方法をとる__ ことは __できません__。そのような場合は、__経験から答えを推測__ して __解答する必要__ があります。その際に、__クイズの問題__ と __似た問題__ を __解いた経験__ が __豊富であれば__、__正解__ の __可能性が高く__ なりますが、__経験が乏しい場合__ は __正解__ の __可能性は低くなる__ でしょう。ただし、その方法で、__100 % 正解__ を __答える__ ことは __不可能__ です。

__はじめて入ったレストラン__ で、__最も美味しい__ メニューを __食べよう__ と思った場合に、__メニューの中__ から __最も美味しい__ ものを __100 % 正しく見つける方法__ はおそらく __ない__ でしょう。そのような場合は、__メニュー__ の「__名前__」、「__写真__」、「__値段__」などを __手がかり__ に、__それまで__ のさまざまな __レストランでの食事の経験__ から __選択__ するしかありません。レストランに入った __経験が多い程__、__美味しいメニューを選択__ できる __可能性が高く__ なりますが、そのような方法で、__最も美味しいメニュー__ を __100 % 選択__ することは __不可能__ です。

このように、__ヒューリスティック__ は、必ず __正しい答え__ を得ることができる __とは限りません__ が、__短い時間__ で __判断を行う__ ことが __できる__ という利点があります。__世の中__ には、__正しい答え__ を __見つける方法__ が __分かっていない場合__ や、__選択するまで__ の __時間が限られている場合__ の方が __多い__ ので、__人間__ が __日々の生活の中__ で行う __判断__ の __多く__ は、__ヒューリスティック__ による __判断__ であるといっても __間違いではない__ でしょう。

### コンピューター科学におけるヒューリスティック

__コンピュータ科学__ における __ヒューリスティック__ は、__問題__ を __解くための方法__ が __分からない__ 場合や、__問題を解くため__ に __時間がかかりすぎる__ 場合などで __利用される方法__ で、__下記__ のような __手順__ を、__満足な結果__ がでるまで __繰り返す__ ことで __問題を解きます__。

1. __問題を解くため__ の、__有望そうな方法__ を考える
2. __考えた方法__ で __問題を解き__、__結果を検証__ する
3. __検証した結果__ から、__それまでの経験__ を元に、__以下の作業__ を行い、__手順 2 に戻る__
    * __それまでに考えた方法__ を __修正する__ 
    * __新しい方法__ を考えて __加える__
    * __見込みがなさそうな方法__ を __破棄する__

上記からわかるように、この方法は「__様々な経験__ を通じて __問題__ の __解決方法__ を __改良__ する」という、__試行錯誤__ で問題を解く方法です。従って、__経験__ を __元__ に __問題を解決__ する点は、__心理学__ の __ヒューリスティックと同じ__ です。また、__そのような作業__ のことを一般的に __学習__ と呼びます。実際に、__辞書__ では、__学習__ を __下記__ のように __説明__ しています。

「人間も含めて動物が、生後に __経験を通じて知識や環境に適応__ する __態度・行動__ などを __身につけていくこと__。__不安や嫌悪__ など __好ましくないもの__ の体得も __含まれる__」

https://dictionary.goo.ne.jp/word/%E5%AD%A6%E7%BF%92/#jn-38801

また、上記の説明からわかるように、__学習__ では、__成功の経験__ だけでなく、__失敗の経験__ も __重要__ です。「__失敗から学ぶ__」という __ことわざ__ は、まさに __そのことを示しています__。

:::note
__学習を行う__ ためには、__様々な方法__ で __問題を解く__ という __試み__ を、__何度も行う__ ことが __できる必要__ があります。逆に言えば、__一度__ または、__数回しか行えない__ ような __問題__ は、__ヒューリスティック__ で解決するには __向いていません__。
:::

先程 __コンピューター科学__ における __ヒューリスティック__ と __説明__ しましたが、__この手法__ は、__元々__ は __人間__ が __問題を解決__ するために __普段行っている__「__学習__」を、__コンピューター科学__ で __応用__ したものです。従って、__ヒューリスティック__ を用いて __コンピュータ__ が __問題を解決__ する __手法の事__ を「__機械学習__」と呼びます。

下記は、__現実の世界__ での __ヒューリスティックの例__ です。

__美味しいカレー__ の __レシピを考える__ という __問題__ は、__ヒューリスティック__ では __下記の手順__ で行います。なお、__調理の手順__ まで __考慮__ に入れると __問題__ が __複雑になる__ ので、__問題__ を __簡単にする__ ため、__調理の手順__ は __決まっている__ ものとします。

1. 美味しいカレーを作るための __材料__ と、その __分量__ を __考える__
2. __実際__ に __カレーを作り__、__食べてみる__
3. __カレーの味__ を __評価__ し、__以下__ のような __改良方法を考え__、__手順 2 に戻る__
    1. __材料の量__ を __変える__
    2. __新しい材料__ を __加える__
    3. __不適切__ な __材料__ を __破棄する__

他にも、__人間__ は「__言葉__ を __覚える__」、「__自転車の乗り方__ を __覚える__」など、__さまざまなこと__ を、__ヒューリスティック__ な __試行錯誤__ による __学習__ で __身に付けていきます__。

コンピューター科学の __ヒューリスティック__ は、__得られた答え__ の __精度__ は __保証されません__ が、__近似解__ を求める __より短い時間__ で、__平均的__ に __高い精度__ で __答えを求める__ ことが __できる場合が多い__ という __特徴__ があります。

### 2 つのヒューリスティックの違い

先程説明した、__心理学__ における __ヒューリスティック__ と、__コンピューター科学__ の __ヒューリスティック__ には __密接な関係__ があります。__心理学__ における __ヒューリスティック__ は、__それまでの経験__ で得られた __学習__ を __元に__ して __素早く判断を行う方法__ のことですが、その __経験による学習__ を __行う__ のが、__コンピューター科学__ の __ヒューリスティック__ です。

従って、__それぞれ__ の __ヒューリスティック__ の __意味は__ 以下のようになります。__心理学__ の場合は、__判断を行う際__ に、__新しい学習__ は __行わない点__ が __異なります__。

|  | 意味 |
|:--|:--|
| __心理学__  | __それまでに行われた学習__ にもとづいて __判断を行う__ こと  |
| __コンピューター科学__  | __学習を行う方法__ も __含めて__、__判断を行う__ こと |

## ヒューリスティックと評価指標

__ヒューリスティック__ は、__経験から学ぶ__ 手法ですが、そのためには、__問題の解決__ を試みた __結果__ の __良し悪しを判断__ する __必要__ があります。その理由は、__結果の良し悪し__ が __判断できなければ__、__どこを改良するべきか__ が __わからない__ からです。__結果__ が __良ければ__ その __長所を伸ばす__ という __改良__ ができ、__悪ければ__ その __短所を克服する__ という __改良__ ができます。

この __結果__ の __良し悪し__ の __判断材料__ の事を __評価指標__ と呼びます。__評価指標__ には __さまざまなもの__ が __ある__ ため、__問題の性質__ に __適した__ 評価指標を __選択する必要__ があります。

例えば、__成績を上げる__ という __問題__ の場合は、__テストの点数__ が __評価指標__ になります。__スポーツ__ を __上達する__ という __問題__ の場合は、__試合の成績__ が __評価指標__ になるでしょう。

ただし、__状況__ によって __同じ評価指標__ でも __良いかどうか__ を __判断する基準__ が __変わる__ 点に __注意__ して下さい。例えば、__高校生__ が、__小学生のテスト__ で __100 点__ をとったり、__小学生相手__ に __試合で勝利__ しても、__特に良い結果__ であるとは __言えない__ でしょう。

## アルゴリズムという用語の意味の違い

__心理学__ では、__アルゴリズム__ という __用語__ は、__問題__ を __100 % 解く__ とことができる __手順__ の事を表し、__ヒューリスティック__ の __対義語__ として __使われます__。

一方、__コンピューター科学__ での __アルゴリズム__ は、__処理__ を行うための __手順__ のことを表し、その際に、__アルゴリズム__ が __問題を 100 % 解く__ ことが __できるか__ どうかは一般的に __区別しません__。従って、__ヒューリスティック__ の __対義語の意味__ では __使われません__。例えば、「__ヒューリスティック__ な __アルゴリズム__」のような __表記__ が __実際__ に __使われます__。

このように、__アルゴリズム__ という __用語__ は、__心理学__ と、__コンピューター科学__ では __異なる使われ方__ がされる点に __注意__ して下さい。__本記事__ では、もちろん __アルゴリズム__ という __用語__ を、__コンピューター科学__ の __意味__ で __使います__。

## 演繹法とヒューリスティックの併用

問題を解く際に、__演繹法__ と __ヒューリスティック__ の __両方__ を __組み合わせる__ ことが __良くあります__。例えば、__スポーツの練習__ を行う際に、__最初__ は __スポーツの入門書__ を読んで、__その通りに練習__ するのが __一般的__ ではないかと思います。多くの __入門書__ に書かれている __内容__ は、__科学的な方法など__ の __演繹法__ によって __検証__ された、__誰でも__ その方法で練習することで __ある程度のレベル__ までは __上達できる__ 方法です。

しかし __一般的__ には、__誰でもスポーツの中級者__ になることができる __手順__ は __あっても__、__誰でも上級者__ になるための __手順__ は __ありません__。__上級者__ になるためには __自分__ で __様々な経験__ を積んで __試行錯誤を行う__ という __ヒューリスティック__ な方法を __行う必要__ があります。

下記は、そのことをまとめたものです。

* __最初__ は、__演繹法__ を使って、__ある程度__ までの __精度__ で __問題を解決__ する
* __演繹法__ では __精度を上げられないレベル__ に到達したら、__ヒューリスティック__ で、__自分__ で __精度を上げる方法__ を __見つけていく__

実は、__これまでの記事__ で __〇×ゲーム__ の __強い AI__ を __作成する際__ に、__上記の手順__ で作成を __行ってきました__。__ルール 11__ の __下記の条件__ は、__演繹法__ で求めた __条件__ であり、__下記の条件__ を __組み込む__ ことで、__実際__ に __ある程度まで__ の __強い AI__ を __作成__ することができました。

* __自分__ が __勝利できる__
* __相手__ が __勝利できない__

ただし、残念ながら、__ルール 11__ の __上記の条件__ では、__すべての局面__ で __最善手__ を __選択__ することは __できません__。また、__すべての局面__ で、__最善手__ を __選択する方法__ は __わからない__ ので、__ここから__ は、__ヒューリスティック__ な __方法__ を __利用__ する __必要__ が __あります__。

## `ai11s` で行われたヒューリスティックの手順

__ルール 11__ の __下記の条件__ は、__ヒューリスティック__ による __条件__ です。

* __真ん中__ のマスに __着手__ する
* __自分__ が __勝利できそうになる__
* __相手__ が __勝利できなさそうになる__

__実際__ に、__上記の条件__ を __`ai11s`__ に __組み込む際__ に、__下記__ の __ヒューリスティック__ による __手順__ を __行っていた__ ことを示します。なお、__真ん中__ のマスに __着手する__ という条件は、__演繹法__ の __条件より__ も __前__ に __組み込んだ__ ので、下記の説明では __省略__ します。

1. __問題を解くため__ の、__有望そうな方法__ を考える
2. __考えた方法__ で __問題を解き__、__結果を検証__ する
3. __検証した結果__ から、__それまでの経験__ を元に、__以下の作業__ を行い、__手順 2 に戻る__
    * __それまでに考えた方法__ を __修正する__ 
    * __新しい方法__ を考えて __加える__
    * __見込みがなさそうな方法__ を __破棄する__

### 問題を解くための、有望そうな方法を考える

まず、__すべての局面__ で __最善手__ を __選択する合法手__ を __見つけるため__ の、__有望そう__ な __判断基準__ として、__下記の 3 つ__ を考えました。__下記__ の __判断基準__ は、__いずれも__ それを満たすことで、__すべての局面__ で __最善手__ を __100 % 見つける__ ことができることは __保証されていない__ ので、__ヒューリスティック__ です。

* __次__ の __自分の手番__ で __勝利できる__ ように、「__自 2 敵 0 空 1__」が __1 つ存在する__ 局面になる着手を行う
* __自分__ が __有利になる__ ように、「__自 1 敵 0 空 2__」が __最も多い__ 着手を行う
* __相手__ が __不利になる__ ように、「__自 0 敵 1 空 2__」が __最も少ない__ 着手を行う

次に、上記の __3 つの条件__ を __総合的__ に __判断__ するために、__それぞれ__ の __マークのパターン__ に対して __下記の表__ の __評価値__ を __割り当て__ ました。

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

### 考えた方法で問題を解き、結果を検証する

__上記の方法__ で、__`ai11s`__ VS __`ai10s`__ の __対戦__ を行い、__下記__ のような __結果__ になりました。


| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| __`ai11s`__ VS __`ai10s`__ | 22.2 | 0.0 | 77.8 | 0.0 | 50.5 | 49.5 | 11.1 | 25.3 | 63.6 |

__結果__ から、__`ai11s`__ が __× を担当__ した場合に、__50 %__ の確率で __敗北する__ という __問題点がある__ ことが __わかりました__。

### 検証した結果から修正を行う

何故 __そのような結果になった__ かを __[検証](https://qiita.com/ysgeso/items/fc19eb2764e0766b59d5#%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)__ し、__評価値__ を __計算__ するための __パラメータ__ を __下記__ のように __修正__ しました。

|  | 修正前 | 修正後 |
|:-:|:-:|:-:|
| __「自 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 |

__修正__ によって、__先程の問題__ は __解消__ されましたが、__新しく__ 〇 を担当した際に、勝てなくなるという __問題が生じました__。この問題を、__[検証した結果](https://qiita.com/ysgeso/items/3d340c07f3d515ce5fe9#ai11s-%E3%81%AE%E3%83%91%E3%83%A9%E3%83%A1%E3%83%BC%E3%82%BF%E3%81%AE%E4%BF%AE%E6%AD%A3%E3%81%AB%E3%82%88%E3%81%A3%E3%81%A6%E3%81%8A%E3%81%8D%E3%81%9F%E3%81%93%E3%81%A8%E3%81%AE%E6%A4%9C%E8%A8%BC)__、勝てなくなっても __問題がない__ と __判断__ し、__このパラメータ__ で __`ai11s`__ を __作成する__ ことに __決めました__。

## ヒューリスティックを用いる際の注意点

__ヒューリスティック__ は、__経験則__ による __解決方法__ なので、__問題__ を __解決する方法__ を __修正__ した __結果__、常に __状況が好転する__ とは __限りません__。

例えば、__`ai11s`__ の __評価値__ を __計算__ する __パラメータ__ を __下記__ の表のように __修正__ した際に、__`ai10s`__ VS __`ai11s`__ の __4 手目の局面のみ__ を __考慮__ に入れて __修正__ を行ったため、__それ以外の局面__ で __パラメータ__ の __修正__ による __悪影響__ が __生じる可能性__ があります。

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

__上記の修正__ によって、__`ai11s`__ VS __`ai10s`__ の __3 手目__ の __選択__ に __実際__ に __影響__ を __与えた__ ように、__`ai11s`__ が __他の AI__ と __対戦__ した際に、__どこかの局面__ の __選択__ に __良い影響__ と __悪い影響__ も含めて __何らかの影響__ を与えている __可能性__ が __あります__。

__他の局面__ に __良い影響のみ__ を与えているのであれば、__問題はない__ のですが、__悪い影響__ を __与えた場合__ は __問題__ です。しかし、残念ながら __ヒューリスティック__ な __条件__ は、__絶対に正しい__ という __明確__ な __根拠がない__ 条件なので、__修正__ することで、__良い影響のみ__ を与えることを __保証__ することは __できません__。

また、__ヒューリスティック__ で __問題を解決__ する場合に、お互いに __矛盾する条件__ が __存在__ することが __良くあります__。例えば、__成績をよくする__ ためには「__勉強の時間__ を __増やす__」と「__適度__ な __休息をとる__」という __条件__ が __考えられます__ が、__この 2 つの条件__ は、__どちらか__ を __増やしすぎ__ ると、__もう片方__ が __減ってしまう__ という、__矛盾する要素__ があります[^3]。そのような場合は、__それらの条件__ を、__バランスよく設定__ する __必要__ がありますが、__適切なバランス__ を __見つける__ ためには、__さまざま__ な __パラメータ__ で __実際__ に __問題の解決__ を __試みて__、その中で __最もバランスの良い__ ものを __採用する__ という __試行錯誤__ が __必要__ になります。

日本語の __ことわざ__ に、「__あちらを立てればこちらが立たず__」というものがありますが、これは、まさに __ヒューリスティック__ による __問題解決__ で __良く起きる状況__ を __表します__。

__ヒューリスティック__ は、__常に間違う可能性__ があります。特に、__特定の状況__ を __改善__ するために __パラメータを修正__ したり __条件__ を __追加__、__削除__ した場合は、__それ以外__ の __さまざまな状況__ で __状況が悪化していないか__ どうかを __必ず検証__ する __必要__ があります。

# 今回の記事のまとめ

__今回の記事__ では、__最強の AI__ の __定義__ を、下記のように __定義しなおし__、本記事で __これまで__ 行ってきた __AI のルール__ の __条件__ が、__下記__ の __最強の AI__ の __定義__ の __一部を満たす__ ような __条件である__ ことを示しました。

:::note warn
__最強の AI__ とは、下記の __両方の条件__ を __満たす AI__ である。

1. __必勝の局面__ になる __合法手__ が __存在する場合__ は、__必ずその合法手__ の __いずれか__ を __選択する__
2. __必敗以外の局面__ で、__必敗の局面__ につながる __合法手__ を __選択しない__
:::

次に、__問題__ を __解決する方法__ の __分類__ として、__演繹法__ と __ヒューリスティック__ を紹介し、__これまで__ に行ってきた __AI の作成方法__ が、__それらの方法__ に __基づいて行われてきた__ ことを __示し__、__これまで__ に行ってきた __AI の作成方法__ で、__AI の強さ__ を __最強の AI__ に __近づけていく__ ことが __できる__ ことを __示しました__。

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

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

# 次回の記事

https://qiita.com/ysgeso/items/5fe28ae6c765a169fd34

[^1]:__論理__ の事を英語で __ロジック__（logic）、__論理的__ を英語で __ロジカル__（logical）と呼びます
[^2]:__原因と結果__ の __関係__ のことです
[^3]:このような、__片方を増やす__ と、__もう片方が減る__ ような、__両立しない__ ようなもののことを、__トレードオブ__ と呼びます。また、__2 つ__ の __相反する要素__ の中から __1 つを選択しなければならない__ ような __状況__ のことを事を __ジレンマ__ と呼びます