Pythonで〇×ゲームのAIを一から作成する　その49　評価値の計算方法

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/474db9ea1805993eaa34

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

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

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

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

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

これまでに作成した AI の アルゴリズム は以下の通りです。

| 関数名 | アルゴリズム |
|:-:|:--|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __左上から順__ に __空いているマス__ を探し、__最初に見つかったマス__ に __着手__ する |
| __[`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)__  | __ランダム__ なマスに __着手__ する |
| __[`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)__  | __真ん中__ のマスに __優先的__ に __着手__ する<br>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | |
| __[`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>既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する | あり |
| __[`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>そうでない場合は __ランダム__ なマスに __着手__ する | |
| __[`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)__  | __勝てる場合__ に __勝つ__<br>そうでない場合は __相手の勝利__ を __阻止__ する<br>そうでない場合は __ランダム__ なマスに __着手__ する |
| __[`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>そうでない場合は __勝てる場合__ に __勝つ__<br>そうでない場合は __相手の勝利__ を __阻止__ する<br>そうでない場合は __ランダム__ なマスに __着手__ する |

基準となる __`ai2`__ との __対戦結果__（単位は %）は以下の通りです。__太字__ は __`ai2 VS ai2` よりも__ __成績が良い__ 数値を表します。__欠陥__ の列は、__アルゴリズム__ に __欠陥__ があるため、__`ai2`__ との __対戦成績__ が __良くても強い__ とは __限らない__ ことを表します。欠陥の詳細については、関数名のリンク先の説明を見て下さい。

| 関数名 | o 勝 | o 負 | o 分 | x 勝 | x 負 | x 分 | 勝 | 負 | 分 | 欠陥 |
|:-:|--:|--:|--:|--:|--:|--:|--:|--:|--:|:-:|
| __[`ai1`](https://qiita.com/ysgeso/items/bdbcd4c1ab1d8731df58#ai1-%E3%81%AE%E5%AE%9A%E7%BE%A9)__  | __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)__  | 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)__  | __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)__  | __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)__  | __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 |
| __[`ai7`](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%9D%E3%81%AE-7%E3%83%AB%E3%83%BC%E3%83%AB3-%E3%81%A8-%E3%83%AB%E3%83%BC%E3%83%AB-6-%E3%81%AE%E4%BD%B5%E7%94%A8)__  | __95.8__ | __0.2__ | 4.0 | __82.3__ | __2.4__ | 15.3 | __89.0__ | __1.3__ | 9.7 |

# 評価値を利用した ルール 1 で着手を行う AI の定義

前回の記事では、__評価値を利用__ した __アルゴリズム__ で __ルール 2__、__3__ で着手を行う __AI を定義__ しました。今回記事では、__ルール 1__、__4__ で着手を行う __AI を定義__ する事にします。

まず、下記の __ルール 1__ で着手を行う __`ai1s`__ を定義します。

* __左上から順__ に __空いているマス__ を探し、__最初に見つかったマス__ に __着手__ する

このルールに従って、評価値をどのように計算するかについて少し考えてみて下さい。

このルールは、下記のようなルールに __置き換える__ ことができます。

1. __(0, 0)__ のマスが空いていればそこに着手する
2. __(1, 0)__ のマスが空いていればそこに着手する
3. __(2, 0)__ のマスが空いていればそこに着手する
4. __(0, 1)__ のマスが空いていればそこに着手する
5. __(1, 1)__ のマスが空いていればそこに着手する
6. __(2, 1)__ のマスが空いていればそこに着手する
7. __(0, 2)__ のマスが空いていればそこに着手する
8. __(1, 2)__ のマスが空いていればそこに着手する
9. __(2, 2)__ のマスが空いていればそこに着手する

従って、__評価値を利用__ した __アルゴリズム__ の場合は、上記の条件のうち、__上に記述__ されている __マス__ に __着手した局面__ の __評価値__ が、__下に記述__ されている __マス__ に __着手した局面__ の __評価値より__ も __大きくなる__ ように、それぞれのマスの __評価値を設定__ すればよいことが分かります。

__一例__ として、__下図__ のように __評価値を設定__ することができます。本記事では下図の評価値を採用しますが、上記の条件が満たされていれば、__他の評価値__ を __設定__ しても __かまいません__。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/44562438-1348-c1c2-9416-b7808ed1a01f.png" width="100">

本記事では、__上記の評価値__ を __計算__ する __`ai1s`__ の __評価関数__ を __定義__ する __いくつかの方法__ を __紹介__ します。どのように定義すればよいかについて少し考えてみて下さい。

なお、マスの __座標__ から __評価値__ を __計算__ する __処理__ は、[以前の記事](https://qiita.com/ysgeso/items/1a8a4319ef3c896ef271#%E8%A4%87%E6%95%B0%E3%81%AE%E6%95%B0%E5%80%A4%E5%BA%A7%E6%A8%99%E3%82%92-list-%E3%81%A7%E8%A1%A8%E7%8F%BE%E3%81%99%E3%82%8B%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)で紹介した __数値座標__ を __xy 座標__ に __変換__ する処理の __逆__ なので、忘れた方は、そちらを __復習__ して下さい。

## `ai1s` の定義 その 1（if 文を使う方法）

下記は、__if 文__ を使ってそれぞれの __座標__ に対する __評価値__ を __計算__ する __`ai1s`__ のプログラムです。初心者でも思いつくことができる方法だと思いますので、説明は省略します。

```python
from ai import ai_by_score

def ai1s(mb, debug=False):
    def eval_func(mb):
        if mb.last_move == (0, 0):
            return 9
        elif mb.last_move == (1, 0):
            return 8
        elif mb.last_move == (2, 0):
            return 7
        elif mb.last_move == (0, 1):
            return 6
        elif mb.last_move == (1, 1):
            return 5
        elif mb.last_move == (2, 1):
            return 4
        elif mb.last_move == (0, 2):
            return 3
        elif mb.last_move == (1, 2):
            return 2
        elif mb.last_move == (2, 2):
            return 1

    return ai_by_score(mb, eval_func, debug=debug)
```

### 動作の確認

__`ai1s`__ が __正しく動作__ するかどうかを __確認__ するために、__`ai1`__ と __対戦__ を行います。[以前の記事](https://qiita.com/ysgeso/items/5725504c97a4490fbadb#ai1-%E3%81%A8-ai2-%E3%81%AE%E3%81%99%E3%81%B9%E3%81%A6%E3%81%AE%E7%B5%84%E3%81%BF%E5%90%88%E3%82%8F%E3%81%9B%E3%81%AE%E5%AF%BE%E6%88%A6%E3%81%A8%E3%81%9D%E3%81%AE%E8%A9%95%E4%BE%A1)で説明したように、__`ai1` VS `ai1`__ では、`ai1` の __アルゴリズム__ には __ランダム性はない__ ので、10000 回の __すべての対戦__ で __〇 が勝利__ します。__実行結果__ から、__`ai1s`__ を __正しく実装__ できていることが __確認__ できました。

```python
from ai import ai_match, ai1, ai4

ai_match(ai=[ai1s, ai1])
```

実行結果

```
ai1s VS ai1
count     win    lose    draw
o       10000       0       0
x           0   10000       0
total   10000   10000       0

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x        0.0%  100.0%    0.0%
total   50.0%   50.0%    0.0%
```

## `ai1s` の定義 その 2（list によるテーブルを使う方法）

[以前の記事](https://qiita.com/ysgeso/items/51c2eba867aa560808c6#excel_to_xy-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%9D%E3%81%AE-2%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB%E3%82%92%E4%BD%BF%E3%81%86%E6%96%B9%E6%B3%95)で、__Excel 座標__ から __xy 座標__ への __対応づけ__ を、__`excel_to_xy_table`__ という __dict__ を使った __テーブル__（表）で行いました。それと __同様の方法__ で、__マスの座標__ とそのマスに着手した場合の __評価値__ を __対応づける__ ことができます。ただし、その方法を利用するためには、__dict__ の __キー__ に __利用__ できる __データの種類__ を理解する必要があります。

### ハッシュ可能なオブジェクトとハッシュ値

これまでのプログラムでは、__dict__ の __キー__ には、主に __文字列型__ のデータを利用してきましたが、__dict__ の __キー__ には __ハッシュ可能なオブジェクト__（hashable）を利用することができます。__ハッシュ可能なオブジェクト__ とは、__以下__ の __性質__ を持つ __オブジェクト__ です。

* その __オブジェクト__ が __存在__ している __間__ は、決して __変更されることがない__、__ハッシュ値__（hash value）と呼ばれる __整数型__ の __データ__ を __持つ__
* __ハッシュ可能なオブジェクトどうし__ を __`==`__ 演算子で __等しいか__ どうかを __比較__ することができ、__`==`__ の __判定結果__ が __`True`__ になる場合は、必ず __同じハッシュ値__ を __持つ__

:::note
細かい話になりますが、__誤解されがち__ な点についていくつか __補足__ します。ただし、下記の補足は、__ハッシュ値__ を __直接扱う__ ようなプログラムを記述する __場合でなければ__、__気にする必要__ は __ありません__。

__ハッシュ可能なオブジェクト__ は __必ず `==`__ 演算子で __比較__ することができますが、ハッシュ可能 __でない__ オブジェクトを __`==`__ 演算子で __比較できるか__ どうかは、その __オブジェクトの種類__ によって __異なります__。例えば __list__ や __dict__ はハッシュ可能 __でない__ オブジェクトですが、__`==`__ 演算子で __比較__ することが __できます__。

上記の __2 つ目__ の __性質__ の __逆__ の、「__同じハッシュ値__ を持つ __オブジェクト__ は、__`==`__ の __判定結果__ が __`True`__ になる」は必ずしも __正しい__ とは __限りません__。__同じハッシュ値__ を持つ __オブジェクト__ が __等しくない__ と __判定__ される事を __ハッシュ値の衝突__ と呼びます。
:::

__ハッシュ可能なオブジェクト__ の __詳細__ については、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/glossary.html#term-hashable

### dict のキーにハッシュ可能なオブジェクトのみが利用できる理由

__dict__ の __キー__ に __ハッシュ可能なオブジェクトのみ__ が __利用__ できる __理由__ は、__dict__ は、__キーの値__ を、__キー__ の __ハッシュ値__ を __利用__ して __管理__ しているからです。具体的な仕組については説明が長くなるので省略しますが、簡単にいうと、下記の理由から、__ハッシュ値__ を __利用__ することで、__効率__ よく __dict__ の __キー__ と __キーの値__ を __管理__ することが __できるようになる__ からです。

* __キー__ を __指定__ して、__dict から__ その __キーの値__ を __取り出す処理__ を行う際には、__dict__ に __登録__ されている __キー__ の中 __から__、__指定したキー__ と __等しいキー__ を __探す必要__ がある
* __ハッシュ値__ を __利用__ することで、__ハッシュ可能なオブジェクトどうし__ が __等しいか__ どうかを __効率的に判定__ することができる

逆に言うと、__dict__ の __キー__ にハッシュ可能 __でない__ オブジェクトを __利用できる__ ように __してしまう__ と、__dict__ の __処理__ が __かなり遅く__ なってしまいます。

__ハッシュ__ という __概念__ は、__コンピューター__ に関する __技術__ の中で、かなり __重要な概念__ なので、興味がある方は調べてみると良いでしょう。例えば、__SNS__ などで良く使われている __ハッシュタグ__ のハッシュと、__ハッシュ値__ のハッシュは、__同じ概念__ の用語です。本記事でも、直接ハッシュ値を扱う機会があれば詳しく解説しようと思います。

参考までに、wikipedia のハッシュのリンクを下記に示します。

https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5

### ハッシュ可能なオブジェクトの種類

__Python__ の __主__ な __ハッシュ可能なオブジェクト__ は以下の通りです。

1. __数値型__、__文字列型__、__論理型__、__None 型__ などの、__単一のデータ__ を扱う、__[単一データ型](https://qiita.com/ysgeso/items/c6d4a2da7b8118a5a143#%E5%8D%98%E4%B8%80%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B%E3%81%AE%E5%AE%9A%E7%BE%A9)__ の __[イミュータブル](https://qiita.com/ysgeso/items/cc9e67c16b0814c8bc2e#%E3%83%9F%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%96%E3%83%AB%E3%81%A8%E3%82%A4%E3%83%9F%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%96%E3%83%AB)__ な __オブジェクト__
2. __Python__ の __任意のデータ型__ を、__複数組み合わせ__ てデータを表現する __[複合データ型](https://qiita.com/ysgeso/items/9efd60c7a28381e6cbf7#%E8%A4%87%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E5%9E%8B%E3%81%AE%E5%AE%9A%E7%BE%A9)__ のうち、__そのデータ型__ および、__すべての要素__ が __イミュータブル__ な __オブジェクト__
3. __自分で定義__ した __クラス__ の __インスタンス__

上記の __1__ と __2__ は、[以前の記事](https://qiita.com/ysgeso/items/cc9e67c16b0814c8bc2e#%E7%96%91%E4%BC%BC%E7%9A%84%E3%81%AA%E8%A4%87%E8%A3%BD)で説明した、__疑似的な複製__ を行うことができるデータです。

上記の __3__ は __疑似的な複製__ を行うことが __できない__ 場合がありますが、__自分で定義__ した __クラス__ の __インスタンス__ は、__インスタンス__ が __扱う__ データの __内容に関わらず__、__インスタンスごと__ に __異なるハッシュ値__ が __計算される__ と考えて下さい[^1]。

従って、__〇×ゲーム__ の __合法手__ を表す __(1, 2)__ という __tuple__ は、__それ自身__ と __すべての要素__ が __ハッシュ可能なオブジェクト__ なので、__ハッシュ可能なオブジェクト__ に __分類__ されます。

### ハッシュ値の取得方法

[以前の記事](https://qiita.com/ysgeso/items/911fafe3f80a805165d1#%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE-id-%E3%81%AE%E5%8F%96%E5%BE%97)で説明した組み込み関数 __`id`__ と __同様__ に、__一般的__ なプログラムで __`hash`__ を使って __ハッシュ値を計算__ する __必要__ がある __場面__ はあまり __多くないと__ 思いますので、興味がない方は、ハッシュ値に関する以下の説明は読み飛ばしても構いません。

__オブジェクト__ の __ハッシュ値__ は、組み込み関数 __`hash`__ の __実引数__ に __オブジェクトを記述__ して呼び出すことで __取得する__ ことができます。また、__`hash`__ の __実引数__ にハッシュ可能 __でない__ オブジェクトを __記述__ して呼び出すと __エラーが発生__ します。

組み込み関数 `hash` についての詳細は、下記のリンク先を参照して下さい。

https://docs.python.org/ja/3/library/functions.html#hash

下記のプログラムは、__いくつか__ の __データ型__ の __ハッシュ値__ を __表示__ しています。

```python
from marubatsu import Marubatsu
mb = Marubatsu()
print(hash(1))                 # 数値型のデータ
print(hash("abc"))             # 文字列型のデータ
print(hash(True))              # 論理型のデータ
print(hash(None))              # None 型のデータ
print(hash((1, "abc", True)))  # すべての要素がハッシュ可能な tuple
print(hash(mb))                # Marubatsu クラスのインスタンス（この値は毎回異なる）
```

実行結果
```
1
5133467580067694764
1
8795299436207
3819214611466916399
145277155213
```

__list__ は __ミュータブル__ なので、__ハッシュ可能なオブジェクト__ では __ありません__。従って __`hash`__ の __実引数に記述__ して呼び出すと、下記のプログラムのように __エラーが発生__ します。

```python
print(hash([1, 2, 3]))
```

実行結果
```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[4], line 1
----> 1 print(hash([1, 2, 3]))

TypeError: unhashable type: 'list'
```

:::note
上記のエラーメッセージは、以下のような意味を持ちます。

* __TypeError__
データ型（type）に関するエラー
* __unhashable type: 'list'__
list は ハッシュ可能でない（unhashable）データ型（type）である
:::

__tuple__ は __イミュータブル__ なデータですが、その __要素__ に __ミュータブル__ なデータが __含まれている__ 場合も、下記のプログラムのように __エラーが発生__ します。


```python
print(hash((1, [2, 3])))  # 要素にミュータブルな list が含まれている
```

実行結果
```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[5], line 1
----> 1 print(hash((1, [2, 3])))

TypeError: unhashable type: 'list'
```

### ハッシュ値の性質

この説明も __当面は利用__ しない __知識__ なので、興味がない方は読み飛ばしてもかまいません。

__Python__ の、__ハッシュ可能__ な __組み込み型__ のデータは、__同じ内容__ であれば、常に __同じハッシュ値__ を持ちます。例えば、下記のプログラムの __`a`__ と __`b`__ には __同一の要素の値__ を持つ __tuple__ が __代入__ されています。__`a`__ と __`b`__ は __異なるオブジェクト__ なので、下記のプログラムのように、__`id`__ を表示すると __異なる値__ が表示されますが、__ハッシュ値__ は __同一__ になります。

```python
a = (1, 2)
b = (1, 2)
print(id(a))
print(id(b))
print(hash(a))
print(hash(b))
```

実行結果（異なる数値が表示される場合があります）

```
2324448500864
2324448507456
-3550055125485641917
-3550055125485641917
```

__自分で定義__ した __クラス__ の __インスタンス__ の場合は、__基本的__[^1]には作成した __インスタンスごと__ に __異なるハッシュ値__ が表示されます。下記のプログラムは、__`Marubastu`__ クラスの 2 つの __インスタンス__ の __ハッシュ値__ を __表示__ していますが、__どちらもゲーム開始直後__ を __表します__ が、__異なるインスタンス__ に __異なるハッシュ値__ が付けられていることがわかります。

```python
mb1 = Marubatsu()
mb2 = Marubatsu()
print(hash(mb1))
print(hash(mb2))
```

実行結果（異なる値が表示される場合があります）

```
145278027657
145277956725
```

### テーブルを使った `ai1s` の定義

__ゲーム盤の座標__ を表す __tuple__ を __キー__ とし、その __キーの値__ に __キーの座標__ に __着手__ した局面の __評価値__ を __代入__ することで、__`ai1s`__ を __下記__ のプログラムのように __定義__ できます。なお、先程の `ai1s` と修正点が多すぎるので、修正箇所は省略します。

* __3 ~ 7 行目__：__座標__ から __評価値__ を __対応__ づける __テーブル__ を表す __dict__ のデータを記述し、ローカル変数 __`score_table`__ に __代入__ する
* __8 行目__：__テーブルから__ 着手した __座標__ の __評価値__ を求めて __返り値__ として __返す__

```python
 1  def ai1s(mb, debug=False):
 2      def eval_func(mb):
 3          score_table = {
 4              (0, 0): 9, (1, 0): 8, (2, 0): 7,
 5              (0, 1): 6, (1, 1): 5, (2, 1): 4,
 6              (0, 2): 3, (1, 2): 2, (2, 2): 1,
 7          }
 8          return score_table[mb.last_move]
 9
10    return ai_by_score(mb, eval_func, debug=debug)
```

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

```python
def ai1s(mb, debug=False):
    def eval_func(mb):
        score_table = {
            (0, 0): 9, (1, 0): 8, (2, 0): 7,
            (0, 1): 6, (1, 1): 5, (2, 1): 4,
            (0, 2): 3, (1, 2): 2, (2, 2): 1,
        }
        return score_table[mb.last_move]

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

### 動作の確認

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

```python
ai_match(ai=[ai1s, ai1])
```

実行結果

```
ai1s VS ai1
count     win    lose    draw
o       10000       0       0
x           0   10000       0
total   10000   10000       0

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x        0.0%  100.0%    0.0%
total   50.0%   50.0%    0.0%
```

## `ai1s` の定義 その 3（式で計算する方法）

__評価値__ を、下図のように、__規則正しく設定__ した場合は、__式__ を使って __評価値__ を __計算__ することが __できます__。どのような式を記述すればよいかについて少し考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/44562438-1348-c1c2-9416-b7808ed1a01f.png" width="100">

[以前の記事](https://qiita.com/ysgeso/items/1a8a4319ef3c896ef271#num_to_xy-%E3%81%AE%E5%AE%9A%E7%BE%A9%E3%81%9D%E3%81%AE-3-%E8%A8%88%E7%AE%97%E3%82%92%E4%BD%BF%E3%81%86%E6%96%B9%E6%B3%95)で、下図の __マス__ の __数値座標__ から、__xy 座標__ を __計算__ する __式__ を紹介しました。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8930ae16-efc9-e09b-c759-6b8e367305e3.png" width="150">

具体的には、__実引数__ に、上図のマスの __数値座標__ を記述して呼び出すと、__xy 座標__ を表す __tuple__ を __返り値__ として返す __`num_to_xy`__ を下記のプログラムのように __定義__ しました。

```python
def num_to_xy(coord):
    x = coord % 3
    y = coord // 3
    return x, y
```

一旦 __評価値__ の事を __忘れて__、__上記の関数__ の __逆の処理__、すなわち __xy 座標__ から __数値座標__ を __計算__ する __処理__ を行うプログラムを考えることにします。上図から、__数値座標__ は、__x 座標__ が __1 増える__ と __1 増える__ ことが分かります。また、__y 座標__ が __1 増える__ と __3 増える__ ことが分かります。従って、__xy 座標__ から __数値座標__ を __計算__ する __式__ は、__下記__ のように __記述__ できます。

```python
coord = x * 1 + y * 3
```

__`x * 1`__ は __`x`__ と __同じ__ なので、上記の式は __下記__ のように __記述__ できます。

```python
coord = x + y * 3
```

次に、下記の __評価値__ の __図__ と、__数値座標__ の図を __並べて__ みて、__それぞれ__ の __同じ座標__ の __マスの数字__ に __どのような関係__ が __あるか__ について考えてみて下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/44562438-1348-c1c2-9416-b7808ed1a01f.png" width="128">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/8930ae16-efc9-e09b-c759-6b8e367305e3.png" width="150">

よく見れば、__同じ座標__ の __マスの数値__ を __合計__ するといずれも __`9` になる__ ことが分かります。従って、__評価値__ と __数値座標__ の関係には、__下記の等式__ が __成り立ち__ ます。

$数値座標 + 評価値 = 9$

この等式を変形すると、以下のようになります。

$評価値 = 9 - 数値座標$

従って、__評価値__ を __`score`__ という __変数__ で表すと、__評価値__ は __下記の式__ で __計算__ できます。

```python
score = 9 - (x + y * 3)
```

上記から、__`ai1s`__ は下記のプログラムのように __定義__ できます。なお、先程の `ai1s` と修正点が多すぎるので、修正箇所は省略します。このように、__評価値__ を __規則正しい値__ に __設定__ することで __簡単な式__ で __評価値__ を __計算できる場合__ があります。

* __3 行目__：__着手__ した __座標__ から、__x 座標__ と __y 座標__ を __取り出し__ て __`x`__ と __`y`__ に __代入__ する
* __4 行目__：__先ほどの式__ を使って、__座標__ から __評価値__ を __計算__ し、その値を __返す__

```python
1  def ai1s(mb, debug=False):
2      def eval_func(mb):
3          x, y = mb.last_move
4          return 9 - (x + y * 3)
5
6      return ai_by_score(mb, eval_func, debug=debug)
```

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

```python
def ai1s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        return 9 - (x + y * 3)

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

### デバッグ表示による動作の確認

今回は、__念のため__ に本当に __正しく実装__ できているかどうかを、下記のプログラムで、__デバッグ表示__ を行うことで __確認__ することにします。__実行結果__ の __score__ の表示から、__左上のマス__ から __9__、__8__、・・・、__1__ の順で、__正しい評価値__ が __計算__ されることが __確認__ できます。

```python
from marubatsu import Marubatsu

mb = Marubatsu()
ai1s(mb, debug=True)
```

実行結果
```
Start ai_by_score
Turn o
...
...
...

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

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

score 8 best score 9
====================
move (2, 0)
Turn x
..O
...
...

score 7 best score 9
====================
move (0, 1)
Turn x
...
O..
...

score 6 best score 9
====================
move (1, 1)
Turn x
...
.O.
...

score 5 best score 9
====================
move (2, 1)
Turn x
...
..O
...

score 4 best score 9
====================
move (0, 2)
Turn x
...
...
O..

score 3 best score 9
====================
move (1, 2)
Turn x
...
...
.O.

score 2 best score 9
====================
move (2, 2)
Turn x
...
...
..O

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

### 対戦による動作の確認

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

```python
ai_match(ai=[ai1s, ai1])
```

実行結果

```
ai1s VS ai1
count     win    lose    draw
o       10000       0       0
x           0   10000       0
total   10000   10000       0

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x        0.0%  100.0%    0.0%
total   50.0%   50.0%    0.0%
```

## `ai1s` の定義 その 4（最初の最善手を採用する）

下記の __ルール 1__ には __ランダム性__ は __ありません__。

* __左上から順__ に __空いているマス__ を探し、__最初に見つかったマス__ に __着手__ する

このような場合は、[前回の記事](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%99%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)のノートで説明したように、__評価値を利用__ した __アルゴリズム__ の __手順 2__ を「__最も高い評価値__ がつけられたものが __複数ある場合__ は、__最初にみつかったもの__ を __選択__」にした __アルゴリズム__ を __利用__ することが __できます__。

具体的には、__下記__ のような __アルゴリズム__ で __処理__ を行います。

* __これまで__ の __`ai1s`__ と __異なり__、__すべての着手__ の __評価値__ を __同じ値__ にする
* __`ai_by_score`__ で計算した __最も高い評価値__ の __合法手の一覧__ を表す __`best_moves`__ の、__先頭の要素__ の __合法手__ を __採用__ する

__評価値__ は、__すべて同じ__ であれば __どのような値__ でも __構わない__ ので、__`0`__ を __設定__ します。

次に、__`ai_by_score`__ が __`best_moves`__ の中から __ランダムな合法手__ を __選択__ するか、__先頭の合法手__ を __選択__ するかを、__選べるように改良__ する __必要__ があります。

### `ai_by_score` の改良

具体的には、下記のプログラムのように、__`ai_by_score`__ を __修正__ します。

* __5 行目__：__最善手の一覧__ の中から __ランダム__ な着手を __選ぶか__ どうかを __表す__ 仮引数 __`rand`__ を __追加__ する。この仮引数を、__デフォルト値__ が __`True`__ の __デフォルト引数__ とすることで、__これまでに作成した AI__ を __変更しなくても良い__ ようにした 
* __6、7 行目__：__`rand`__ が __`True`__ の場合は __これまで通り__、__ランダム__ な合法手を __選択して返す__ 処理を行う
* __8、9 行目__：__`rand`__ が __`False`__ の場合は、__先頭の合法手__ を表す __0 番の要素__ を __返す__

:::note
__仮引数の名前__ を __`random`__ にしなかったのは、__`random`__ という __名前__ の本記事でも利用している、良く使われる __モジュールがある__ からです。
:::

```python
1  from copy import deepcopy
2  from random import choice
3  from ai import dprint
4
5  def ai_by_score(mb_orig, eval_func, debug=False, rand=True):
元と同じなので省略
6      if rand:   
7          return choice(best_moves)
8      else:
9          return best_moves[0]
```

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

```python
from copy import deepcopy
from random import choice
from ai import dprint

def ai_by_score(mb_orig, eval_func, debug=False, rand=True):
    dprint(debug, "Start ai_by_score")
    dprint(debug, mb_orig)
    legal_moves = mb_orig.calc_legal_moves()
    dprint(debug, "legal_moves", legal_moves)
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        dprint(debug, "=" * 20)
        dprint(debug, "move", move)
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        dprint(debug, mb)
        
        score = eval_func(mb)
        dprint(debug, "score", score, "best score", best_score)
        
        if best_score < score:
            best_score = score
            best_moves = [move]
            dprint(debug, "UPDATE")
            dprint(debug, "  best score", best_score)
            dprint(debug, "  best moves", best_moves)
        elif best_score == score:
            best_moves.append(move)
            dprint(debug, "APPEND")
            dprint(debug, "  best moves", best_moves)

    dprint(debug, "=" * 20)
    dprint(debug, "Finished")
    dprint(debug, "best score", best_score)
    dprint(debug, "best moves", best_moves)
    if rand:   
        return choice(best_moves)
    else:
        return best_moves[0]
```
</details>

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

```diff_python
from copy import deepcopy
from random import choice
from ai import dprint

def ai_by_score(mb_orig, eval_func, debug=False, random=True):
元と同じなので省略
    if rand:   
        return choice(best_moves)
    else:
        return best_moves[0]
```
</details>

### `ai1s` の修正

次に、__`ai1s`__ を下記のプログラムのように __修正__ します。

* __3 行目__：__評価値__ は __常に `0`__ を __返す__ ようにする
* __5 行目__：__キーワード引数 `rand=False`__ を __記述__ することで、__`ai_by_score`__ が __先頭の合法手__ を __返す__ ようにする

```python
def ai1s(mb, debug=False):
    def eval_func(mb):
        return 0

    return ai_by_score(mb, eval_func, debug=debug, rand=False)
```

### 動作の確認

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

```python
ai_match(ai=[ai1s, ai1])
```

実行結果

```
ai1s VS ai1
count     win    lose    draw
o       10000       0       0
x           0   10000       0
total   10000   10000       0

ratio     win    lose    draw
o      100.0%    0.0%    0.0%
x        0.0%  100.0%    0.0%
total   50.0%   50.0%    0.0%
```

### 仮引数 `rand` の処理の確認

__`rand=False`__ が __正しく動作するか__ どうかが心配な方は、下記のプログラムのように、__`ai1s`__ の __`ai_by_score`__ の __実引数__ から、__`rand=False`__ を __削除__ した、__`ai1s_buggy`__ を __定義__ して、__`ai1` と対戦__ すると良いでしょう。__実行結果__ から、__通算成績__ の __勝率__ と __敗率__ が __異なる__ ので、__`rand=False`__ によって __`ai_by_score`__ の __処理__ が __正しく切り替わる__ ことが __確認__ できます。

```python
def ai1s_buggy(mb, debug=False):
    def eval_func(mb):
        return 0

    return ai_by_score(mb, eval_func, debug=debug)

ai_match(ai=[ai1s_buggy, ai1])    
```

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

```
ai1s_buggy VS ai1
count     win    lose    draw
o        5151    4455     394
x        1748    7825     427
total    6899   12280     821

ratio     win    lose    draw
o       51.5%   44.5%    3.9%
x       17.5%   78.2%    4.3%
total   34.5%   61.4%    4.1%
```

# 評価値を利用した ルール 4 で着手を行う AI の定義

次は、下記の、__ルール 4__ で着手を行う __AI を定義__ します。

* __真ん中__、__隅__ のマスの __順__ で __優先的__ に __着手__ する
* 既に __埋まっていた場合__ は __ランダム__ なマスに __着手__ する

## 評価値の設定

__ルール 4__ は、__(1, 1)__、__(0, 0)__、__(2, 0)__、__(0, 2)__、__(2, 2)__ の __順番__ で __優先的__ に __着手__ を行います。__ルール 1__ の場合と __同様の方法__ でそれらのマスの __評価値__ を __設定する__ ことにした場合、__それぞれ__ のマスに __着手__ した __局面__ の __評価値__ は __5__、__4__、__3__、__2__、__1__ になります。

__上記以外__ の __マス__ しか __残っていない__ 場合は、__ランダムな着手__ を行うので、それらの __評価値__ は、__上記の場合__ の __どの評価値__ よりも __低い__、__`1` 未満__ の __同じ値__ に __設定__ すればよいことが分ります。そこで、その __評価値__ を __`0`__ にすることにします。

__下図__ は、__上記__ に従って、__それぞれのマス__ に __着手__ した場合の局面の __評価値__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/428a160a-e826-de2e-a73b-3930d5bc39e3.png" width="100">

## `ai4s` の定義の方法

この __評価値__ を __計算__ する __`ai4s`__ の __定義__ として、__先程と同様__ に __if 文__ を使う方法と、__テーブル__ を使う方法が考えられますが、__どちらも__ プログラムの __記述がかなり面倒__ です。なお、どちらも面倒ではありますが、__特に難しい点はない__ のでプログラムの __記述は省略__ します。興味と時間に余裕ががある方は実際に記述してみて下さい。また、__ルール 4__ は __ランダム性がある__ ので __先程実装__ した __`ai_by_score`__ の __`rand=False`__ の __処理__ を __利用__ することは __できません__。

そこで本記事では、__計算__ を使って __`ai4s`__ を __実装__ する __方法__ について説明します。

__真ん中__、__四隅__、__それ以外__ のマスを __分けて処理__ する __必要__ があるので、__その部分__ は __if 文__ で __記述__ する __必要__ があります。そのため、__`ai4s`__ を下記のプログラムのように記述します。

* __3、4 行目__：__真ん中__ のマスに __着手__ していた場合は __`5`__ を __返す__
* __5、6 行目__：__四隅__ のマスに __着手__ していた場合は、その __評価値__ を __式で計算__ して __返す__
* __7、8 行目__：__それ以外__ の場合は __`0`__ を __返す__

下記の __5、6 行目の__、__日本語で記述__ されている部分に、どのようなプログラムを記述す場良いかについて少し考えてみて下さい。

```python
 1  def ai4s(mb, debug=False):
 2      def eval_func(mb):
 3          if mb.last_move == (1, 1):
 4              return 5
 5          elif 四隅のマスの場合:
 6              return 四隅の場合の評価値を計算する式
 7          else:
 8             return 0
 9
10      return ai_by_score(mb, eval_func, debug=debug)
```

## 四隅のマスであることの判定方法

__単純__ に __考える__ のであれば、__下記__ のような __条件式__ を __記述__ すれば良いのですが、このプログラムは __長い__ ので、__入力が大変__、__入力ミス__ の __可能性が高くなる__ などの __欠点__ があります。

```python
elif mb.last_move == (0, 0) or mb.last_move == (2, 0) or \
     mb.last_move == (0, 2) or mb.last_move == (2, 2):
```

このような場合は、__四隅のマス__ の __座標__ と、__それ以外__ のマスの __座標__ を下記の __表__ のように __並べ__ 、__四隅__ のマスに __あって__ 、__それ以外__ のマスに __ない__、__特長を探す__ と良いでしょう。なお、__真ん中__ のマスは __最初__ に __判定済__ なので __考慮__ する必要は __ありません__。

| 位置 | 座標 |
|:-:|:--|
| __四隅__  | __(0, 0)__、__(2, 0)__、__(0, 2)__、__(2, 2)__  |
| __それ以外__  | __(1, 0)__、__(0, 1)__、__(2, 1)__、__(1, 2)__ |

上記をよく見ると、__以下の性質__ があることが分かります。

* __四隅__ の __x__、__y 座標__ は、__いずれも `0`__ または __`2`__ である
* __それ以外__ の __x__、__y 座標__ は __上記の性質__ を __満たさない__

### 四隅を判定する式の記述方法

従って、この __性質__ を __利用__ することで、__`ai4s`__ を下記のプログラムのように __記述__ できます。

* __3 行目__：__着手__ した __座標__ から、__x 座標__ と __y 座標__ を __取り出し__ て __`x`__ と __`y`__ に __代入__ する
* __6 行目__：__x 座標__ と __y 座標__ が __いずれも `0`__ または __`2`__ であることを __判定__ する。__or 演算子__ は __and 演算子より__ も __[優先順位が低い](https://qiita.com/ysgeso/items/1fdd19037bbf64082a42#%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E5%84%AA%E5%85%88%E9%A0%86%E4%BD%8D)__ ので、__`(`__ と __`)`__  で __囲う必要がある__ 点に __注意__ すること

```python
 1  def ai4s(mb, debug=False):
 2      def eval_func(mb):
 3          x, y = mb.last_move
 4          if mb.last_move == (1, 1):
 5              return 5
 6          elif (x == 0 or x == 2) and (y == 0 or y == 2):
 7              return 四隅の場合の評価値を計算する式
 8          else:
 9              return 0
10
11      return ai_by_score(mb, eval_func, debug=debug)
```

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

```diff_python
def ai4s(mb, debug=False):
    def eval_func(mb):
+       x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
-       elif 四隅のマスの場合:
+       elif (x == 0 or x == 2) and (y == 0 or y == 2):
            return 四隅の場合の評価値を計算する式
        else:
            return 0

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


### 四隅を判定する式の別の記述方法

__数字__ に __慣れた__ 方は、__上記の性質__ を __一般化__ した __下記の性質__ を __思いつく__ かもしれません。

* __四隅__ の __x__、__y 座標__ は、__いずれも偶数__ である 
* __それ以外__ の __x__、__y 座標__ は __上記の性質__ を __満たさない__

__整数__ が __偶数__ で __あるか__ どうかは、__2__ で __割った余り__ が __0 であるか__ どうかで __判定__ できます。また、__Python__ では __`%`__ という __演算子__ を使って、__割り算__ の __余り__ を __計算__ することができます。従って、__`ai4s`__ は、下記のプログラムのように、より __簡潔に記述__ できます。

* __6 行目__：__余りを計算__ することで __x 座標__ と __y 座標__ が __いずれも偶数__ であることを __判定__ する

```python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
        elif x % 2 == 0 and y % 2 == 0:
            return 四隅の場合の評価値を計算する式
        else:
            return 0

    return ai_by_score(mb, eval_func, debug=debug)
```

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

```diff_python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
-       elif (x == 0 or x == 2) and (y == 0 or y == 2):
+       elif x % 2 == 0 and y % 2 == 0:
            return 四隅の場合の評価値を計算する式
        else:
            return 0

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

## 四隅のマスの評価値の計算

__下図__ の __四隅__ のマスに __着手__ した局面の __評価値__ を __式で計算__ するためには、__`x`__ と __`y`__ を __使った式__ で、__下記の表__ のような __評価値__ を __計算__ する __式__ を考える必要があります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/428a160a-e826-de2e-a73b-3930d5bc39e3.png" width="100">　

| x | y | 評価値 |
|--:|--:|--:|
| `0`  | `0`  | `4`  |
| `2`  | `0`  | `3`  |
| `0`  | `2`  | `2`  |
| `2`  | `2`  | `1`  |

__式を考える__ ために、__`x`__ と __`y`__ と __評価値__ の __関係__ を下記のように __考察__ します。

* __`x`__ と __`y`__ が __共に `0`__ の場合の __評価値__ は __`4`__ である
* __`x`__ が __`2` 増える__ と、__評価値__ は __`1` 減る__
* __`y`__ が __`2` 増える__ と、__評価値__ は __`2` 減る__

従って、__評価値__ は __下記の式__ で __計算__ できることが分かります。__実際__ に、__上記__ の __表__ の __x__、__y__ の値をこの __式に代入__ して __正しい評価値__ が __計算__ できるかどうかを __確認__ して下さい。

```python
score = 4 - (x / 2 + y)
```

### `ai4s` の定義と動作の確認

__この式__ を __`ai4s`__ に __当てはめる__ と、下記のプログラムの __7 行目__ のようになります。

```python
 1  def ai4s(mb, debug=False):
 2      def eval_func(mb):
 3          x, y = mb.last_move
 4          if mb.last_move == (1, 1):
 5              return 5
 6          elif x % 2 == 0 and y % 2 == 0:
 7              return 4 - (x / 2 + y)
 8          else:
 9              return 0
10
11      return ai_by_score(mb, eval_func, debug=debug)
```

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

```python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
        elif x % 2 == 0 and y % 2 == 0:
            return 4 - (x / 2 + y)
        else:
            return 0

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

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

```diff_python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
        elif x % 2 == 0 and y % 2 == 0:
-           return 四隅の場合の評価値を計算する式
+           return 4 - (x / 2 + y)
        else:
            return 0

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



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

```python
ai_match(ai=[ai4s, ai4])
```

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

```
ai4s VS ai4
count     win    lose    draw
o        2520    4099    3381
x        4127    2404    3469
total    6647    6503    6850

ratio     win    lose    draw
o       25.2%   41.0%   33.8%
x       41.3%   24.0%   34.7%
total   33.2%   32.5%   34.2%
```

## 別の実装方法

上記で、__四隅に着手__ した際の __評価値__ を __改めて考える__ のが __面倒__ だと思った方はいませんか？実は、__四隅__ の __評価値__ は、__ルール 1__ と __同じ式__ で __計算__ することが __できます__。

その __理由__ は、__評価値を利用__ する __アルゴリズム__ では、「__優先したいもの__ の __評価値__ が、__それより__ も __優先したくないもの__ の __評価値__ よりも __大きくなる__」ような __評価値__ であれば、__それぞれ__ に __どのような評価値__ を __設定__ しても __構わない__ からです。具体的には、__四隅__ の __評価値__ を __下図左__ のように、__下図右__ の __ルール 1__ の __評価値__ と __同じ値__ に __設定__ しても構いません。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/01e54e76-bfca-5a49-d8ad-6f2a52eadd19.png" width="100">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/44562438-1348-c1c2-9416-b7808ed1a01f.png" width="100">

### `ai4s` の定義と動作の確認

従って、__四隅__ の __評価値__ を __計算__ する __式__は、__ルール 1__ の __評価値__ を __計算__ する __式__ と __同じ式__ を __利用__ することが __できる__ ので、__`ai4s`__ は、下記のプログラムのように __記述__ できます。

* __7 行目__：__四隅__ のマスの __評価値__ の __計算式__ を __`ai1s`__  と __同じ__ ものにする

```python
 1  def ai4s(mb, debug=False):
 2      def eval_func(mb):
 3          x, y = mb.last_move
 4          if mb.last_move == (1, 1):
 5              return 5
 6          elif x % 2 == 0 and y % 2 == 0:
 7              return 9 - (x + y * 3)
 8          else:
 9              return 0
10
11      return ai_by_score(mb, eval_func, debug=debug)
```

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

```python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
        elif x % 2 == 0 and y % 2 == 0:
            return 9 - (x + y * 3)
        else:
            return 0

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

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

```diff_python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 5
        elif x % 2 == 0 and y % 2 == 0:
-           return 4 - (x / 2 + y)
+           return 9 - (x + y * 3)
        else:
            return 0

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


__`ai4s`__ が __正しく動作__ するかどうかを __確認__ するために、__`ai4`__ と __対戦__ を行います。__実行結果__ から、__通算成績__ の __勝率__ と __敗率__ が __異なる__ ので、__`ai4s`__ を正しく実装 __できていない__ ことが __確認__ できました。__どこに問題があるか__ について少し考えてみて下さい。

```python
ai_match(ai=[ai4s, ai4])
```

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

```
ai4s VS ai4
count     win    lose    draw
o        6616    1698    1686
x        4167    2495    3338
total   10783    4193    5024

ratio     win    lose    draw
o       66.2%   17.0%   16.9%
x       41.7%   24.9%   33.4%
total   53.9%   21.0%   25.1%
```

### バグの原因

__バグの原因__ は、__真ん中__ のマスに __着手__ した場合の __評価値__ が __`5` のまま__ だからです。そのため、上記の __`ai4s`__ では、__真ん中__ のマスの __(1, 1) の __`5`__ より__ 評価値が __高い__、__(0, 0)__ と __(2, 0)__ が __優先的__ に __着手__ されてしまいます。このように、__評価値を利用__ する __アルゴリズム__ では、__評価値__ を __別の値__ に __修正__ した際に、__他の__ より __優先したい__（または __優先したくない__）ものの __評価値__ の __大小の関係__ が __変化しない__ ように __注意__ する __必要__ があります。

__四隅__ のマスに着手した際の __評価値__ を __先ほど__ のように __修正__ した場合は、__より優先__ する __真ん中__ の __(1, 1)__ の __評価値__ を、__四隅__ の __評価値__ の __最大値__ である __`9` より__ も __大きな値__ に __設定し直す__ 必要があります。__`9`__ より __大きければ__ どのような値でも __構わない__ ので __`10`__  を __設定__ することにします。なお、__真ん中__ と __四隅以外__ のマスの __評価値__ は __`0` のまま__ で __問題はありません__。

下図は、__修正後__ の __各マス__ の __評価値__ を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/10ad0b0b-ebc3-8d46-2ba5-ba97445c7c95.png" width="100">

__評価値__ の __修正__ を行う際に、先程のような __バグが発生__ することを __避ける__ ためには、上記のような __図を作成__ すると良いでしょう。他の方法としては、下記の __表__ のように、__優先したい条件__ の __順番__ で __評価値__ の __範囲__ を __表にしたもの__ を __作製__ して、__優先したいものに__ 対して、__より大きな評価値__ が __設定__ されることが __確認できる__ ようにすると良いでしょう。

| 条件 | 評価値の範囲 |
|:--|--:|
| __真ん中のマスに着手__  | 10  |
| __四隅のマスに着手__ | 1 ~ 9  |
| __それ以外のマスに着手__  | 0  |

他にも、__評価値__ を __修正__ した際に、__大小の関係__ が __簡単__ に __変化しない__ ように、__それぞれ__ の __条件__ の __評価値の範囲__ の __間隔__ を __大きめに設定__ するという方法があります。例えば、__真ん中__ のマスの着手に対する __評価値__ に __`100`__ を __設定__ することで、今後、__四隅__ のマスの着手に対する __評価値__ を __多少変えた場合__ に、間違って __`100` より大きくなる可能性__ が __低く__ なります。ただし、この方法は決して __完璧ではない__ ので、__過信せず__ に、__評価値__ を __修正__ した場合は、必ず __全体の評価値__ の __値を確認__ することを __強くお勧めします__。

### `ai4s` の修正と動作の確認

__修正__ した __評価値__ を __計算__ する __`ai4s`__ は、下記のプログラムのように __記述__ できます。

* __5 行目__：__(1, 1)__ のマスの __評価値__ を __`10`__ にする

```python
 1  def ai4s(mb, debug=False):
 2      def eval_func(mb):
 3          x, y = mb.last_move
 4          if mb.last_move == (1, 1):
 5              return 10
 6          elif x % 2 == 0 and y % 2 == 0:
 7              return 9 - (x + y * 3)
 8          else:
 9              return 0
10
11      return ai_by_score(mb, eval_func, debug=debug)
```

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

```python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 10
        elif x % 2 == 0 and y % 2 == 0:
            return 9 - (x + y * 3)
        else:
            return 0

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

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

```diff_python
def ai4s(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
-           return 10
+           return 5
        elif x % 2 == 0 and y % 2 == 0:
            return 9 - (x + y * 3)
        else:
            return 0

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

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

```python
ai_match(ai=[ai4s, ai4])
```

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

```
ai4s VS ai4
count     win    lose    draw
o        2499    4214    3287
x        4196    2414    3390
total    6695    6628    6677

ratio     win    lose    draw
o       25.0%   42.1%   32.9%
x       42.0%   24.1%   33.9%
total   33.5%   33.1%   33.4%
```

# 評価値を利用したアルゴリズムの利点

__評価値を利用__ した __アルゴリズム__ の __利点__ をいくつか紹介します。他の利点に関しては、その利点を活かした例が出てきた時に説明します。

## 評価値関数を記述するだけで、AI を定義できる

[以前の記事](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E8%A9%95%E4%BE%A1%E5%80%A4%E3%82%92%E5%88%A9%E7%94%A8%E3%81%97%E3%81%9F-ai-%E3%81%AE%E3%81%B2%E3%81%AA%E5%BD%A2%E3%81%A8%E3%81%AA%E3%82%8B%E9%96%A2%E6%95%B0%E3%81%AE%E5%AE%9A%E7%BE%A9)で __定義__ した、__評価値を利用__ した __アルゴリズム__ の __ひな形__ となる __`ai_by_score`__ を __定義__ する事で、__評価関数__ を __定義__ するだけで、__AI の関数__ を __定義できる__ ようになります。

## ランダムな選択を行うことができる

[以前の記事](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E6%9D%A1%E4%BB%B6%E3%82%92%E6%BA%80%E3%81%9F%E3%81%99%E7%9D%80%E6%89%8B%E3%81%8C%E8%A4%87%E6%95%B0%E3%81%82%E3%82%8B%E5%A0%B4%E5%90%88%E3%81%AE%E5%95%8F%E9%A1%8C%E7%82%B9)で説明した、__条件を満たす着手が複数ある場合の問題点__ を解消することができます。具体的には、__最大__ の __評価値__ を持つものが __複数__ あった場合に、その中から __ランダムに選択__ する処理を行うことができます。

## ルールの条件の優先順位を柔軟に変えることができる

[以前の記事](https://qiita.com/ysgeso/items/8f3d4b3d2c02ef51a70e#%E6%9D%A1%E4%BB%B6%E3%82%92%E5%88%A4%E5%AE%9A%E3%81%99%E3%82%8B%E9%A0%86%E7%95%AA%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E5%95%8F%E9%A1%8C%E7%82%B9)で説明した、__条件を判定する順番に関する問題点__ を解消することができます。

例えば、__ルール 4__ は、__真ん中__ のマス、__隅__ のマスの __優先順位__ で __着手__ を行いますが、その __優先順位__ を、__隅__ のマス、__真ん中__ のマスの __優先順位__ に __変える__ 場合に、「それぞれの条件 を __順番に判定__ し、__最初__ にみつかった __条件を満たす着手__ を __選択__ する」というアルゴリズムでは、下記の __`ai4`__ のプログラムを、__その下__ のプログラムのように、__真ん中__ と __隅__ の __処理__ を行うプログラムの __記述__ の __順番__ を __入れ替える__ 必要があります。

```python
略
    # 真ん中のマスの場合の処理
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
    # 隅のマスの場合の処理
    for y in range(0, 3, 2):
        for x in range(0, 3, 2):
            if mb.board[x][y] == Marubatsu.EMPTY:
                return x, y
略
```

修正後のプログラム

```python
略
    # 隅のマスの場合の処理
    for y in range(0, 3, 2):
        for x in range(0, 3, 2):
            if mb.board[x][y] == Marubatsu.EMPTY:
                return x, y
    # 真ん中のマスの場合の処理
    if mb.board[1][1] == Marubatsu.EMPTY:
        return 1, 1
略
```

一方、__評価値を利用__ する __アルゴリズム__ の場合は、計算する __評価値__ を、__下記の表__ のように __変える__ ことで、__条件__ の __優先順位__ を __変えるこ__ とができます。なお、下記の表では __四隅__ の __評価値__ を __`101` ~ `109`__ にしましたが、__`10` より多ければ__ どのような値にしても構いません。

| 条件 | 評価値の範囲 |
|:--|--:|
| __四隅のマスに着手__ | 101 ~ 109  |
| __真ん中のマスに着手__  | 10  |
| __それ以外のマスに着手__  | 0  |

__上記の評価値__ を __計算__ するために __必要__ な __`ai4s`__ の __修正__ は、下記のプログラムの __7 行目__ のように、__四隅__ の __評価値__ に __`100` を足すだけ__ で __簡単__ に行えます。ただし、下記のプログラムは、__ルール 4__ と __異なる処理__ を行うので、関数の名前は __`ai4s_fake`__[^2]としました。

```python
 1  def ai4s_fake(mb, debug=False):
 2      def eval_func(mb):
 3          x, y = mb.last_move
 4          if mb.last_move == (1, 1):
 5              return 10
 6          elif x % 2 == 0 and y % 2 == 0:
 7              return 9 - (x + y * 3) + 100
 8          else:
 9              return 0
10
11      return ai_by_score(mb, eval_func, debug=debug)
```

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

```python
def ai4s_fake(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 10
        elif x % 2 == 0 and y % 2 == 0:
            return 9 - (x + y * 3) + 100
        else:
            return 0

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

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

```diff_python
-def ai4(mb, debug=False):
+def ai4s_fake(mb, debug=False):
    def eval_func(mb):
        x, y = mb.last_move
        if mb.last_move == (1, 1):
            return 10
        elif x % 2 == 0 and y % 2 == 0:
-           return 9 - (x + y * 3)
+           return 9 - (x + y * 3) + 100
        else:
            return 0

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

なお、__`ai4s_fake`__ は、__ルール 4__ とは __異なる処理__ を行うので、__`ai4`__  との __対戦は行いません__。

# 評価値を利用したアルゴリズムの欠点

__評価値を利用__ した __アルゴリズム__ は、良いことしかないように思えるかもしれませんが、以下のような __欠点__ があるので、その点には __注意__ して下さい。

## 処理に時間がかかる場合がある

__評価値を利用__ した __アルゴリズム__ は、__最大__ の __評価値__ を持つものを __調べる必要__ があるので、必ず __すべてのデータ__ の __評価値__ を __計算__ する __必要__ があります。一方、「それぞれの条件を順番に判定し、最初にみつかった条件を満たす着手を選択する」アルゴリズムでは、__条件を満たす__ ものが __見つかった時点__ で __処理を終える__ ことができます。そのため、ルールによっては、__評価値を利用__ した __アルゴリズム__ のほうが、__処理__ に __時間がかかる場合__ があります。

例えば、__`ai1`__ と __`ai1s`__ は、__同じルール__ で __着__ 手を行う __AI__ ですが、__`ai1s`__ のほうが __処理__ に __時間がかかります__。そのことは下記の __2 つのプログラム__ を __実行__ することで __確認__ できます。

下記の、__`ai1` どうし__ で __10000 回対戦__ を行う処理は、筆者のパソコンでは __約 2.5 秒__ かかりました。なお、実行結果はこれまでと同じなので省略します。

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

一方、下記の、__`ai1s` どうし__ で __10000 回対戦__ を行う処理は、筆者のパソコンでは __約 32.7 秒__ のように、__約 10 倍以上__ の時間がかかりました。省略しますが、__`ai2s`__、__`ai3s`__、__`ai4s`__ も、対応する AI の __約 10 倍__ の __処理時間__ がかかります。興味がある方は実行してみて下さい。

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

実は、__`ai1`__ と __`ai1s`__ で __約 10 倍以上__ も __処理時間__ が __異なる__ のは、__`ai1`__ で行う __処理__ が、__特定のマス__ が __空いているかどうか__ を __調べている__ のに対し、__`ai1s`__ では、__合法手__ の __着手__ を行う際に __`Marubatsu` クラス__ の __インスタンス__ の __深いコピー__ を __作成__ するという、__時間がかかる処理__ を行っているからです。ルール __5__、__6__、__7__ のように、__着手を行う必要__ がある __処理__ の場合は、それほど __時間の差__ は __生じない__ ので、__一般的__ には __評価値を利用__ した __アルゴリズム__ の __処理速度__ が __大きく異なる__ ことは __ありません__。そのことは、__次回の記事__ で __確認__ します。

## 評価値の設定の間違いに関する欠点

__評価値を利用__ する __アルゴリズム__ では、確かに評価値を変えることで、条件の優先順位を柔軟に変えることができますが、__評価値__ の __設定__ を __間違える__ と、先程 `ai4s` の四隅の評価値を変えた時にバグが発生したように、__簡単__ に __間違った処理__ が行われます。また、__間違っていること__ に __気づきにくい__、__間違った場合__ に __原因を発見しづらい__ という __欠点__ があります。

# 今回の記事のまとめ

今回の記事では、__評価値を利用__ した __アルゴリズム__ での、__評価値__ の __設定方法__ と、__計算方法__ について __説明__ し、__ルール 1__ と __4__ の __AI__ を __評価値を利用__ した __アルゴリズム__ で定義しました。

:::note warn
__評価値を利用__ した __アルゴリズム__ では、「__優先したいもの__ の __評価値__ が、__それより__ も __優先したくないもの__ の __評価値より__ も __大きくなる__」という __条件を満たせば__、__評価値__ に __どのような値__ を __設定__ しても __かまいません__。

このように、__評価値を利用__ した __アルゴリズム__ では、__評価値__ を __柔軟に設定__ できますが、逆に言えば、__間違った評価値__ を __簡単に設定できてしまう__ ため、その点に __気をつけないと__、__簡単にバグが発生__ してしまう点に __注意__ する __必要__ があります。
:::

次回の記事では、__評価値を利用__ した __アルゴリズム__ で、残りの __ルール 5__ ~ __7__ を __実装__ する方法について説明します。

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

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

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

今回の記事では、marubatsu.py は修正していないので、marubatsu_new.py はありません。

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

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

# 次回の記事

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

[^1]:詳細は割愛しますが、インスタンスのハッシュ値を計算する処理をクラスの定義の中に、自分で記述することができます
[^2]:fake は、偽物という意味の英語です