Pythonで〇×ゲームのAIを一から作成する　その47　評価値を利用するアルゴリズム

# 目次と前回の記事

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

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/047/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)__  | __ランダム__ なマスに __着手__ する |
| __[`ai3`](https://qiita.com/ysgeso/items/1e8732db6cd1b0104276#ai3-%E3%81%AE%E5%AE%9F%E8%A3%85)__  | __真ん中__ のマスに __優先的__ に __着手__ する<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 |

# これまでのアルゴリズムの欠点

__これまで作成__ してきた AI は、__[ルール 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)__ のように、ルールに __複数の条件__ が存在する場合は、「__それぞれの条件__ を __順番に判定__ し、__最初__ にみつかった __条件を満たす着手__ を __選択__ する」という __アルゴリズム__ で __実装__ してきましたが、この __アルゴリズム__ には __欠点__ があります。

また、詳細は次回以降の記事で説明しますが、その __欠点__ があるため、これまでに作成した最強の AI である __`ai7` より強い AI__ を、__このアルゴリズム__ で __作成__ することは __困難__ です。

そこで、今回の記事では、__このアルゴリズム__ の __欠点__ を __説明__ し、その __欠点を解消__ できる、__評価値を利用する__ という __アルゴリズム__ を __説明__ します。また、__これまでに実装__ してきた __AI__ を、__評価値を利用__ する __アルゴリズム__ で __実装する方法__ について __説明__ します。

## 条件を判定する順番に関する問題点

__これまで__ の __アルゴリズム__ では、__ルール__ の中に __複数__ の __条件がある__ 場合は、__条件__ の __優先順位__ に従って、__判定の順番__ を __正しく記述__ する必要があります。例えば、[前回の記事](https://qiita.com/ysgeso/items/e08c41f93109496fb9f9#%E3%83%AB%E3%83%BC%E3%83%AB%E3%81%AE%E6%89%8B%E9%A0%86%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E6%B3%A8%E6%84%8F%E7%82%B9)で説明したように、__ルール 6__ のアルゴリズムの __手順__ を __入れ替える__ と、__間違った処理__ が行われます。

この点に関しては、この後で説明する、__評価値を利用__ する __アルゴリズム__ の場合でも、__評価値__ をルールに従って __正しく計算__ する __必要がある__ ので、大きく変わるわけではありません。

問題は、__何らかの理由__ で __条件__ の __優先順位__ を __変える場合__ で、__判定__ を行うプログラムの __記述の順番__ を正しく __入れ替える__ 必要があるため、プログラムの __修正が大変__ です。

次回の記事で説明しますが、__評価値を利用__ する __アルゴリズム__ では、条件の __優先順位__ を __変える__ 際に、__評価値__ の __計算式__ を __修正__ するという手法をとるため、処理の __記述の順番__ を __入れ替える__ 必要は __ありません__。そのため、プログラムの __修正__ を __比較的簡単__ に行えます。

## 条件を満たす着手が複数ある場合の問題点

__ルール 5__ の、「__勝てる場合__ に __勝つ__」という条件は、下記の局面の __2 つ__ の青いマスのように、__複数の合法手__ がその __条件を満たす__ 場合があります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/46f76db1-5cf3-096b-9737-f510de2cf00c.png" width="100"> 

上記の局面に対し、__`ai5`__ は、__最初に見つかった__ 1 のマスを __必ず選択__ してしまいます。もちろん、__1__ のマスを __選択__ すれば __〇 が勝利__ するので、__強い AI を作成__ するという __意味__ では全く __問題ありません__ が、__人間にとって__ は、__1 と 2__ を __ランダムに選択__ する AI のほうが __面白味が高い__ のではないでしょうか。しかし、__最初に見つかった合法手__ を __選択__ するという __アルゴリズム__ では、そのような __ランダム性__ のある __着手__ を行うことは __できません__。

## 結果が `True`、`False` 以外の条件を考慮したい場合の問題点

__これまで__ の __ルール__ の __条件__ は、__いずれも__「真ん中のマスに着手したかどうか」のように、__結果__ が __`True`__ か、__`False`__ の __いずれか__ になるものばかりでした。

それに対し、例えば __参考書を買う__ 時に、「__ページ数__ が __最も多い__ 本を __選ぶ__」のような、__数値の大きさ__ を __比較__ するような __条件__ の __ルール__ は、__すべての参考書__ を __調べなければ__ どれが最も小さいかを __判定__ することは __できない__ ので、これまでの、「__最初に見つかったもの__ を __選択__ する」という __アルゴリズム__ は __利用できません__。

## 複数の条件を組み合わせて考慮したい場合の問題点

__これまで__ の 〇×ゲームの __ルール__ では、この __問題は起きない__ ので、__別の例__ で __説明__ します。

お店で __ヨーグルトを買う__ 時に、「__値段__」、「__容量__」、「__賞味期限__」の __3 つ__ を __判断基準__ にして __どの商品を買うか__ を __選択__ する場合の事を考えてみて下さい。

例えば、それぞれについて、__下記__ のような __判断基準__ を __設定__ することにします。

1. __値段__ が __200 円以下__
2. __容量__ が __200 g 以上__
3. __賞味期限__ が __3 日後以降__

「__それぞれの条件__ を __順番に判定__ し、__最初__ にみつかった __条件を満たす商品__ を __選択__ する」場合は、上記の __判断基準__ の __優先順位__ を __設定__ し、その __順番で判定__ を行うことになります。

例えば、下記の表の __3 種類__ の __商品__ に対して、上記の __1__、__2__、__3__ の __優先順位__ で __商品を選択__ する場合、__最初__ に __値段が 200 円以下__ であることが __判明__ した __商品 B__ が __選択__ されます。

|  | 値段 | 容量 | 賞味期限 | 条件 1 | 条件 2 | 条件 3 | 条件を満たす数 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| __商品 A__  | 230  | 300  | 5  |   | 〇  | 〇  | 2  |
| __商品 B__  | 180  | 150  | 1  | 〇  |   |   | 1  |
| __商品 C__  | 160  | 120  | 2  | 〇  |   |   | 1  |


しかし、__この方法__ では、__商品 B より後__ の商品は __チェックされない__ ので、__商品 B__ より __安い__、__商品 C__ が __選択されない__ という __問題__ があります。

__他のルール__ として、上記の __判断基準__ を __最も多く満たす__ 商品を __選択する__ というルールが考えられます。例えば、上記の場合、__商品 C__ が __最も多く__ の __判断基準を満たす__ ので __商品 C__ を __選択__ します。しかし、__最も多く__ の __判断基準__ を満たす商品を __見つけるため__ には、__すべての商品__ を __調べる必要__ があるので、「__それぞれの条件__ を __順番に判定__ し、__最初__ にみつかった __条件を満たす商品__ を __選択__ する」方法で __このルール__ を __作成__ することは __できません__。


# 評価値を利用するアルゴリズム

__上記の問題__ を __解決__ する方法に、下記の __評価値を利用__ する __アルゴリズム__ があります。__手順 2__ から、このアルゴリズムで、__ランダム性__ のある __選択を行う__ ことが __できます__。

:::note warn
以下の手順で、__複数のもの__ の中 __から__ 、__一つを選択__ する。

1. __それぞれ__ の __もの__ に対して __決められた計算__ を行うことで、__点数__ をつける。その __点数__ の事を __評価値__ と __呼ぶ__
2. __最も高い評価値__ がつけられた __ものを選択__ する。__最高点__ の __評価値__ がつけられたものが __複数ある__ 場合は、その中から __ランダムに__ 一つを __選択__ する
:::

:::note
__ランダム性__ が __重要でない__ 場合は、__手順 2__ で、__最も高い評価値__ がつけられたものが __複数ある場合__ は、__最初にみつかったもの__ を __選択__ するアルゴリズムもあります。
:::

__最も優秀__ なものを __評価値を利用__ する __アルゴリズム__ で __選択__ することは、__現実の世界__ でも、__下記の表__ のように __良く行われています__。

|  | 評価値 |
|:-:|:-:|
| __テスト__  | 点数  |
| __マラソン__  | ゴールするまでに要した時間  |
| __野球などのスポーツ__  | 得点  |

先程の __ページ数__ が __最も多い__ 参考書を選択する例では、参考書の __ページ数__ が __評価値__ です。

先程の __ヨーグルト__ を __選択__ する例では、__条件__ を __満たす数__ が __評価値__ で、下記の場合は __最も評価値が高い__、__商品 A__ が __選択__ されることになります。

|  | 値段 | 容量 | 賞味期限 | 条件 1 | 条件 2 | 条件 3 | 条件を満たす数 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| __商品 A__  | 230  | 300  | 5  |   | 〇  | 〇  | 2  |
| __商品 B__  | 180  | 150  | 1  | 〇  |   |   | 1  |
| __商品 C__  | 160  | 120  | 2  | 〇  |   |   | 1  |

このように、__評価値を利用__ することで、__数値の大きさ__ を __条件__ とする __選択__ や、__複数の条件__ を __組み合わせ__ て __考慮__ する __選択__ を行うことが __できる__ ようになります。

また、__評価値を利用__ することで、先ほど説明した「__条件を判定__ する __順番__ に関する __問題点__」を __改善__ することができます。具体例については次回の記事で説明します。


## 評価値を利用した 〇× ゲームの AI の記述

__評価値を利用__ した __アルゴリズム__ による __〇× ゲーム__ の AI は、下記のプログラムのように、__現在の局面__ に対して __それぞれの合法手__ を __着手__ した __局面の評価値__ を __計算__ し、その中で __最も評価値が高くなる合法手__ から __選択__ するという __処理を記述__ します。なお、コメントの部分は、この後で具体的なプログラムを記述します。

__現在の局面__ に対して、__それぞれの合法手__ を __着手__ する __処理__ は、__ルール 5__ の AI で行う __処理と同じ__ なので、__2 ~ 5 行目__ の処理の __記述__ は、__`ai5`__ のプログラムと __同様__ です。

```python
 1  def ai(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      for move in legal_moves:
 4          mb = deepcopy(mb_orig)
 5          x, y = move
 6          mb.move(x, y)
 7          # mb の局面の評価値を計算する
 8          # 最も高い評価値が得られる合法手の一覧を計算する
 9
10      # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する
```        

# 評価値を利用した ルール 2 の AI の実装

__これまでに作成__ してきた __AI__ は、__いずれも評価値を利用__ した __アルゴリズム__ で __実装__ することが __できます__。最初に、下記の __ルール 2__ の __AI__ を、__評価値を利用__ した __アルゴリズム__ で __実装__ する __方法__ を紹介します。なお、ルール 1 より先に ルール 2 を実装するのは、__ルール 2__ のほうが __簡単に実装できる__ からです。ルール 1 の実装方法については次回の記事で紹介します。

* __ランダム__ なマスに __着手__ する

__評価値を利用__ する __アルゴリズム__ で、__ルール 2__ を __実装__ する場合は、__現在の局面__ に対して __合法手__ を __着手__ した __すべて__ の __局面__ の __評価値__ を __同じ値__ にします。その __理由__ は、__評価値を利用__ する __アルゴリズム__ では、先程説明したように、「__最高点__ の __評価値__ がつけられたものが __複数ある場合__ は、__その中__ から __ランダムに__ 一つを __選択__ する」という処理を行うからです。

## 関数の名前について

__評価値__ の事を、__英語__ で __score__ と __表記__ するので、その __頭文字__ をとって、__評価値__ を __利用__ して __ルール x__ の処理を行う __関数の名前__ を __`aixs`__ のように __命名__ することにします。例えば、これから実装する __ルール 2__ の処理を行う __関数__ は、__`ai2s`__ という __名前__ で __定義__ します。

__`ai2s`__ は、先程のプログラムの __コメント__ を __順番に埋めていく__ という手順で __実装__ します。

## 評価値の計算処理の記述

下記は、__評価値__ を __利用__ した __アルゴリズム__ で __ルール 2__ の処理を行う __関数 `ai2s`__  を __定義__ するプログラムです。下記のプログラムは、先程の __評価値__ を __利用__ した __プログラム__ の、__7 行目__ の 「__`mb` の局面の評価値を計算する__」 の __コメントの処理__ を 11 行目に __記述__ しています。


__すべての局面__ に対して __同じ評価値__ を __計算__ すれば良いので、その __評価値__ には __どのような数値__ を __設定__ しても __かまいません__ が、おそらく __`0`__ が __最も分かりやすい__ のではないかと思いますので、本記事では __`0` を設定__ することにしました。また、計算した __評価値__ を __代入__ する __変数の名前__ は __`score`__ にしました。

なお、__後で利用__ するので __2 行目__ で __`choice`__ を __インポート__ しています。

```python
 1  from copy import deepcopy
 2  from random import choice
 3
 4  def ai2s(mb_orig):
 5      legal_moves = mb_orig.calc_legal_moves()
 6      for move in legal_moves:
 7          mb = deepcopy(mb_orig)
 8          x, y = move
 9          mb.move(x, y)
10          # mb の局面の評価値を計算する
11          score = 0
12          # 最も高い評価値が得られる合法手の一覧を計算する
13
14      # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する
```

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

```python
from copy import deepcopy
from random import choice
 
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        # mb の局面の評価値を計算する
        score = 0
        # 最も高い評価値が得られる合法手の一覧を計算する

    # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する
```
</details>

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

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

def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        # mb の局面の評価値を計算する
+       score = 0
        # 最も高い評価値が得られる合法手の一覧を計算する

    # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する
```
</details>

次に、上記のプログラムの __12 行目__ のコメントの、「__最も高い評価値__ が得られる __合法手__ の __一覧を計算__ する」という __処理__ を __記述__ します。どのように記述すれば良いかについて少し考えてみて下さい。

なお、__ルール 2__ では、__すべての局面__ の __評価値__ が __等しい__ ので、__最も高い評価値__ を __計算__ する __必要はない__ のではないかと思う人がいるかもしれませんが、今後、__局面__ によって __評価値__ が __異なるルール__ を __実装__ する際に __必要になる__ ので、この機会に __実装する__ ことにします。

:::note
__`ai2s`__ では、__着手__ に __関係なく__、__評価値__ が __常に `0`__ になるので、__合法手__ の __着手__ の __処理__ を行う、上記のプログラムの __7 ~ 9 行目__ を __記述__ する __必要__ は __ありません__。ただし、これは __ルール 2__ が __例外__ なだけで、__局面__ の __状況に応じて__、__評価値を計算__ する __ルール__ の場合は __記述__ する __必要__ があるので、__本記事__ でも __記述する__ ことにします。
:::

## 最も高い評価値の記録

「__最も高い評価値__ が得られる __合法手__ の __一覧を計算__ する」という __処理__ を行うためには、__最も高い評価値__ が __何であるか__ を __記録__ する __必要__ があります。そこで、__最も高い__ 評価値、すなわち __最高__（best）の評価値を __`best_score`__ という __名前__ の __変数__ に __記録__ することにします。

次に、この __`best_score`__ の __初期化処理__ を __記述__ する __必要__ があります。その処理を __どこに記述__ し、__どのような値__ で __初期化__ すればよいかについて少し考えてみて下さい。

__記述__ する __場所__ は、__合法手__ を __着手__ した __局面__ の __評価値を計算__ する __より前__ のどこかです。ただし、__for 文__ の __ブロックの中__ にその処理を __記述__ すると、__繰り返しのたび__ に __`best_score`__ が __初期化されてしまう__ ので、__for 文より前__ に __記述__ する __必要__ があります。具体的には、__`legal_moves = mb_orig.calc_legal_moves()`__ の __前後__ の __どちらか__ の行に __記述すれば良い__ でしょう。__本記事__ では __その後の行__ に __記述__ することにします。

次に、__`best_score`__ を __どのような値__ で __初期化__ するかを __決めます__。__`best_score`__ は、__それまでの局面__ の __評価値__ の中の __最高値__ を表しますが、__初期化__ した __時点__ では、まだ一度も __評価値__ は __計算されていません__。そこで、下記のプログラムの __3 行目__ のように、__とりあえず__、__データ__ が __存在しない__ ことを表す __`None`__ で __初期化__ することにします。

```python
 1  def ai2s(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = None
 4      for move in legal_moves:
 5          mb = deepcopy(mb_orig)
 6          x, y = move
 7          mb.move(x, y)
 8          # mb の局面の評価値を計算する
 9          score = 0
10          # 最も高い評価値が得られる合法手の一覧を計算する
11
12      # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する    
```  

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

```python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = None
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        # mb の局面の評価値を計算する
        score = 0
        # 最も高い評価値が得られる合法手の一覧を計算する

    # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する  
```
</details>

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

```diff_python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
+   best_score = None
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        # mb の局面の評価値を計算する
        score = 0
        # 最も高い評価値が得られる合法手の一覧を計算する

    # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する  
```
</details>


## 最も高い評価値の判定方法

次に、10 行目の「__最も高い評価値__ が得られる __合法手__ の __一覧を計算__ する」という __処理__ を __記述__ します。どのような __アルゴリズム__ で記述すれば良いかについて少し考えてみて下さい。

__それまで__ の __局面__ の中で __最も高い評価値__ を表す __`best_score`__ と、__`move`__ を __着手__ した __局面__ での __評価値__ を表す __`score`__ の __関係__ を __整理__ すると、__下記の表__ のようになります。

| 関係を表す式 | 関係が `True` の場合の意味 |
|:-:|:--|
| __`best_score is None`__  | __最初__ の __合法手__ を __着手__ した __局面__ |
| __`best_score < score`__  | __`score`__ がそれまでの __評価値__ の中の __最大値__ より __大きい__  |
| __`best_score == score`__  | __`score`__ がそれまでの __評価値__ の中の __最大値__ と __等しい__  |
| __`best_score > score`__  | __`score`__ がそれまでの __評価値__ の中の __最大値__ より __小さい__  |

上記の表の __それぞれの場合__ に行う __処理__ は以下のようになります。

### 最初の合法手を着手した局面

__評価値__ を __計算__ する __最初の局面__ なので、その __評価値__ が __最も高い評価値__ になります。また、「__最も高い評価値__ が得られる __合法手__ の __一覧__」は、その時に __着手__ した __`move` のみ__ です。従って、__下記の処理__ を行う必要があります。

* __`best_score`__ を __`score`__ の __値__ で __更新__ する
* 「__最も高い評価値__ が得られる __合法手__ の __一覧__」を、その時に __着手__ した __`move`__ で __更新__ する

### `score` がそれまでの評価値の最大値より大きい

この場合も、その __評価値__ が __最も高い評価値__ になります。また、それまでの「__最も高い評価値__ が得られる __合法手__ の __一覧__」を __破棄__ して、その時に __着手__ した __`move` のみ__ で __上書き__ する必要があります。それらの処理は、__最初の合法手を着手した局面__ で行う処理と __同じ__ です。

### `score` がそれまでの評価値の最大値と等しい

この場合は、__最も高い評価値__ の値は __変化しない__ ので、下記の処理のみが必要です。

* 「__最も高い評価値__ が得られる __合法手__ の __一覧__」に、その時に __着手__ した __`move`__ を __追加__ する

### `score` がそれまでの評価値の最大値より小さい

この場合は、特に __何もする必要はありません__。

### プログラムの記述

__上記__ から、__最も高い評価値__ を __判定__ する __処理__ は、下記のプログラムのように記述できます。

* __10、11 行目__：「__最初__ の __合法手__ を __着手__ した __局面__」 または 「__`score`__ がそれまでの __評価値__ の __最大値__ より __大きい__ 場合」の処理を記述する
* __14、15 行目__：__`score`__ がそれまでの __評価値__ の __最大値__ と __等しい__ 場合の処理を記述する
* __16 行目__：Python では、__ブロックの中__ に __プログラムを 1 つも記述しない__ と __エラー__ になるので、そのような場合は __`pass` を記述__ する __必要__ がある

なお、__`score`__ がそれまでの __評価値__ の __最大値__ より __小さい__ 場合は、__何もする必要はない__ ので、その場合のプログラムを __記述__ する __必要__ は __ありません__。

```python
 1  def ai2s(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = None
 4      for move in legal_moves:
 5          mb = deepcopy(mb_orig)
 6          x, y = move
 7          mb.move(x, y)
 8          score = 0
 9          # 最初の合法手を着手した局面 または score がそれまでの評価値の中の最大値より大きい
10          if best_score is None or best_score < score:
11              best_score = score
12              # 「最も高い評価値が得られる合法手の一覧」を、その時に着手した move で更新する
13          # score がそれまでの評価値の中の最大値と等しい
14          elif best_score == score:
15              # 「最も高い評価値が得られる合法手の一覧」に、その時に着手した move を追加する
16              pass
17
18      # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する   
```

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

```python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = None
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score is None or best_score < score:
            best_score = score
            # 「最も高い評価値が得られる合法手の一覧」を、その時に着手した move で更新する
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            # 「最も高い評価値が得られる合法手の一覧」に、その時に着手した move を追加する
            pass

    # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する 
```
</details>

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

```diff_python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = None
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        score = 0
+       # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
+       if best_score is None or best_score < score:
+           best_score = score
+           # 「最も高い評価値が得られる合法手の一覧」を、その時に着手した move で更新する
+       # score がそれまでの評価値の中の「最大値と等しい」
+       elif best_score == score:
+           # 「最も高い評価値が得られる合法手の一覧」に、その時に着手した move を追加する
+           pass

    # 最も高い評価値が得られる合法手の一覧の中からランダムに着手を選択する   
```
</details>

## 最も高い評価値が得られる合法手の一覧の処理

最後に、__最も高い評価値__ が得られる __合法手__ の __一覧__ に関する __処理__ を __記述__ します。__強い AI__ が行う __処理__ は、__合法手__ の中で __最も良い手__、すなわち __最善手__（best move）を __求める__ ことなので、__そのデータ__ を __代入__ する __変数__ の __名前__ を __`best_moves`__ と命名することにします。__合法手__ の __一覧__ なので、__`best_moves`__ に __代入__ する __データ__ には __list__ を利用することにします。下記は、__`best_moves`__ に関する __処理__ を `ai2s` に __記述__ したプログラムです。

* __4 行目__：__for 文__ による __繰り返し処理__ の __前__ で、__`best_moves`__ を __空の list__ で __初期化__ する

* __13 行目__：「__最も高い評価値__ が得られる __合法手__ の __一覧__」を、その時に __着手__ した __`move`__ で __更新__ する処理は、__`best_moves`__ に、__`move` のみ__ を __要素__ とする __list__ を __代入__ する処理なので、__`best_moves`__ に __`[move]`__ を __代入__ する。__`move` ではない__ 点に __注意__ すること

* __16 行目__：「__最も高い評価値__ が得られる __合法手__ の __一覧__」に、その時に __着手__ した __`move`__ を __追加__ する処理を、__`append`__ メソッドを使って行う

* __18 行目__：__`choice`__ を使って __`best_moves`__ の中から __ランダムな着手__ を __返り値__ として __返す__

```python
 1  def ai2s(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = None
 4      best_moves = []
 5      for move in legal_moves:
 6          mb = deepcopy(mb_orig)
 7          x, y = move
 8          mb.move(x, y)
 9          score = 0
10          # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
11          if best_score is None or best_score < score:
12              best_score = score
13              best_moves = [move]
14          # score がそれまでの評価値の中の「最大値と等しい」
15          elif best_score == score:
16              best_moves.append(move)
17
18      return choice(best_moves) 
```

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

```python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = None
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score is None or best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

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

```diff_python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = None
+   best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score is None or best_score < score:
            best_score = score
+           best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
-           pass
+           best_moves.append(move)

+    return choice(best_moves)  
```
</details>

## 動作の確認

__`ai2s`__ が __正しく動作__ するかどうかを __確認__ する __方法__ の一つに、__同じルール__ で __着手を選択__ する __`ai2`__ と __対戦させる__ という方法があります。__同じルール__ で __着手を選択__ するのであれば、対戦した際の __通算成績__ の __勝率__ と __敗率__ が __ほぼ同じになる__ からです。

下記のプログラムの実行結果から、__通算成績__ の __勝率__ と __敗率__ が __ほぼ同じ__ であることが __確認__ できるので、__`ai2s`__ を __正しく実装__ できている __可能性が高い__ ことが __確認__ できました。

この方法で __100% 正しく__ 実装できていることを __確認できる__ わけでは __ありません__ が、__精度は高い__ と思いますので、__以後__ は、__この方法__ で __正しく実装できているか__ を __確認__ します。

```python
from ai import ai_match, ai1, ai2, ai3

ai_match(ai=[ai2s, ai2])
```

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

```
ai2s VS ai2
count     win    lose    draw
o        5819    2919    1262
x        2938    5814    1248
total    8757    8733    2510

ratio     win    lose    draw
o       58.2%   29.2%   12.6%
x       29.4%   58.1%   12.5%
total   43.8%   43.7%   12.6%
```

## 負の無限大を利用した、`None` を使わない記述方法

先程のプログラムでは、11 行目の条件式に、__`None`__ であることを __判定__ する __`best_score is None`__ を __記述__ していますが、これを __記述しなくても済む__ 方法があります。

Python では、__正の無限大__ を表す __浮動小数点数型__ のデータを __`float("inf")`__[^1]、__負の無限大__ を表す __浮動小数点数型__ のデータを __`float("-inf")`__ のように __記述__ することが __できます__。

:::note
__`inf`__ とだけ記述すれば良いのではないかと思う人がいるかもしれませんが、__`inf`__ は、__そのような名前__ の __変数__ と __みなされる__ ので __うまくいきません__。また、__`"inf"`__ と記述すると、__文字列型__ のデータと __みなされる__ ので __うまくいきません__。
:::

__正の無限大__ は、__数値型__ のデータの中で __最も大きな値__、__負の無限大__ は、__数値型__ のデータの中で __最も小さい値__ であると __みなされます__。また、__正の無限大どうし__ や、__負の無限大どうし__ を __比較__ すると __等しい__ とみなされます。下記のプログラムは、無限大の比較の例です。

```python
print(float("inf") > 1000000000000000000000)   # 正の無限大とかなり大きな数字の比較
print(float("-inf") < -1000000000000000000000) # 正の無限大とかなり小さな数字の比較
print(float("inf") == float("inf"))            # 正の無限大どうしの比較
print(float("-inf") == float("-inf"))          # 負の無限大どうしの比較
print(float("-inf") < float("inf"))            # 負の無限大と正の無限大の比較
```

実行結果

```
True
True
True
True
True
```

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

* __3 行目__：__`best_score`__ を __負の無限大__ で __初期化__ する
* __11 行目__：__条件式__ から __`best_score is None`__ を __削除__ する

```python
 1  def ai2s(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = float("-inf")
 4      best_moves = []
 5      for move in legal_moves:
 6          mb = deepcopy(mb_orig)
 7          x, y = move
 8          mb.move(x, y)
 9          score = 0
10          # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
11          if best_score < score:
12              best_score = score
13              best_moves = [move]
14          # score がそれまでの評価値の中の「最大値と等しい」
15          elif best_score == score:
16              best_moves.append(move)
17
18      return choice(best_moves) 
```

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

```python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

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

```diff_python
def ai2s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
-   best_score = None
+   best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
-       if best_score is None or best_score < score:
+       if best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

### プログラムが正しく動作する理由

このプログラムが __正しく動作__ する __理由__ を説明します。

__最初の局面__ に対する __評価値__ の __計算__ を __行う前__ の時点では、__`best_score`__ と __`best_moves`__ の __値__ は、__3__、__4__ 行目の __処理__ から __変化していない__ ので、__下記の表__ のようになります。

| 変数 | 値 |
|:-:|:-:|
| __`best_score`__  | `float("-inf")`  |
| __`best_moves`__  | []  |

__`ai2s`__ では、__評価値__ の値が __必ず `0`__ になりますが、__今後作成__ する __AI__ のことを __考慮__ して、__評価値__ の値が __どのような数値__ になっても __正しい処理__ が __行われる__ ことを __示します__。

### 最初の局面で評価値の値が負の無限大以外になった場合

__最初の局面__ に対する __評価値__ の値が、__負の無限大以外__ の値になった場合は、__11 行目__ の __`if best_score < score:`__ の __条件式__ の __計算結果__ が __`True`__ になります。従って、__12__、__13__ 行目の __処理__ が行われますが、これは、__修正前__ の、__`best_score`__ に __`None`__ が __代入__ されていた場合と __全く同じ処理__ が行われるということを __意味__ します。

従って、__最初の局面__ に対する __評価値__ の値が、__負の無限大以外__ の値になった場合は、__修正前__ と __修正後__ で、__全く同じ処理__ が行われ、__`best_score`__ には、__最初の局面__ の __評価値__ である __`score`__ が、__`best_moves`__ には __`[move]`__ が __代入__ されます。

### 最初の局面で評価値の値が負の無限大になった場合

__最初の局面__ に対する __評価値__ の値が、__負の無限大__ になった場合は、__11 行目__ の __`if best_score < score:`__ の __条件式__ の __計算結果__ が __`False`__ になります。

その場合は、次の __15 行目__ の __`elif best_score == score:`__ が __実行__ されますが、__`best_score`__ と __`score`__ には __どちらも負の無限大__ が __代入__ されているので、その __条件式__ の __計算結果__ は __`True`__ になります。そのため、16 行目の __`best_moves.append(move)`__ が実行されますが、__`best_moves`__ には __空の list__ が代入されているので、__`best_moves`__ の値は __`[move]`__ になります。

__`best_score`__ の値は __変化しません__ が、__元々代入__ されていた __負の無限大__ は、__最初の局面__ の __評価値__ と __等しい__ ので、__`best_score`__ の値は __`score`__ と __等しく__ なります。

従って、__最初の局面__ に対する __評価値__ の値が、__負の無限大__ の場合も、__修正前__ と __修正後__ で、__全く同じ処理__ が行われます。以上の事から、__最初の局面__ の __評価値__ が __どのような値__ であっても、__修正前__ と __修正後__ で __同じ処理__ が行われることが __示されました__。

### 2 つ目以降の局面に値する処理

__2 つ目以降__ の __局面__ に対する __処理の記述__ は、__修正後__ と __修正前__ で __変わらない__ ので、__2 つ目以降__ の __局面__ に対しても、__修正前__ と __修正後__ で __同じ処理__ が行われることが分かります。以上の事から、__修正前__ と __修正後__ のプログラムが、常に __同じ処理__ を行うことが __示されました__。

## 動作の確認

先程と __同様の方法__ で、修正した __`ai2s`__ が __正しく動作__ するかどうかを __確認__ します。実行結果から、__`ai2s`__ を __正しく実装__ できていることが __確認__ できました。

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

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

```
ai2s VS ai2
count     win    lose    draw
o        5874    2901    1225
x        2876    5890    1234
total    8750    8791    2459

ratio     win    lose    draw
o       58.7%   29.0%   12.2%
x       28.8%   58.9%   12.3%
total   43.8%   44.0%   12.3%
```

# 評価値を利用した ルール 3 の AI の実装

次に、__評価値を利用__ した __アルゴリズム__ で __ルール 3__ の AI を __実装__ する方法を __説明__ します。なお、__ルール 1 より先__ に __ルール 3__ を __実装__ するのは、ルール 2 の時と同様に、__ルール 3 のほう__ が __簡単__ に __実装できる__ からです。

下記は __ルール 3__ を __再掲__ したものです。

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

__評価値を利用__ した __アルゴリズム__ で上記の __ルール 3__ を __実装__ するために、__評価値__ を __どのように計算__ すれば良いかについて少し考えてみて下さい。

__評価値を利用__ した __アルゴリズム__ では __以下__ のように __評価値__ を __設定__ します。

* ルールの __条件__ のうち、__優先順位__ が __高い__ 条件を満たすものの __評価値__ を、それよりも __優先順位__ が __低い__ 条件を満たすものの __評価値より__ も __高く設定__ する
* __優先順位__ が __同じ__ 条件を満たす、__ランダム__ に __選択__ したいものの __評価値__ を、すべて __同じ値__ に __設定__ する

__ルール 3__ の場合は、__真ん中のマス__ に __優先的__ に __着手__ し、__真ん中のマス__ が __埋まっていた場合__ は、__ランダムなマス__ に __着手__ するので、__評価値__ は __下記__ のように __設定__ します。

* __真ん中__ のマスに __着手__ した __局面__ の __評価値__ に、__最も高い評価値__ を __設定__ する
* __真ん中__ のマス __以外__ に __着手__ した __局面__ の __評価値__ を、すべて __同じ値__ に __設定__ する

__上記の条件__ を __満たしていれば__ 、__どのような評価値__ を __設定__ しても __かまいません__。本記事では、__以下の表__ のように __評価値__ を __設定__ することにします。

| 局面 | 評価値 |
|:-:|--:|
| __真ん中__ のマスに __着手__ した __局面__  | `1`  |
| __真ん中__ のマス __以外__ に __着手__ した __局面__  | `0`  |

:::note
他の値を設定したい人は、__条件を満たす__ 好きな __値を設定__ して下さい。
:::

## `ai3s` の定義

下記は、__上記の表__ の __評価値を計算__ するように、__`ai3s`__ を __定義__ したプログラムです。

* __9 ~ 12行目__：__着手__ した __座標__ が __真ん中__ の __(1, 1)__ の場合は __`score`__ に __`1`__ を、__そうでない場合__ は __`0`__ を __代入__ する

```python
 1  def ai3s(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = float("-inf")
 4      best_moves = []
 5      for move in legal_moves:
 6          mb = deepcopy(mb_orig)
 7          x, y = move
 8          mb.move(x, y)
 9          if x == 1 and y == 1:
10              score = 1
11          else:
12              score = 0
13          # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
14          if best_score < score:
15              best_score = score
16              best_moves = [move]
17          # score がそれまでの評価値の中の「最大値と等しい」
18          elif best_score == score:
19              best_moves.append(move)
20
21      return choice(best_moves)
```

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

```python
def ai3s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if x == 1 and y == 1:
            score = 1
        else:
            score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

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

```diff_python
-def ai2s(mb_orig):
+def ai3s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
-       score = 0
+       if x == 1 and y == 1:
+           score = 1
+       else:
+           score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

## 動作の確認

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

```python
ai_match(ai=[ai3s, ai3])
```

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

```
ai3s VS ai3
count     win    lose    draw
o        6995    1839    1166
x        1911    6972    1117
total    8906    8811    2283

ratio     win    lose    draw
o       70.0%   18.4%   11.7%
x       19.1%   69.7%   11.2%
total   44.5%   44.1%   11.4%
```

## tuple どうしの比較を利用した `ai3s` の記述

__座標__ を表す __`move`__ に代入される __データ__ は、__x 座標__ と __y 座標__ を __表す__、__2 つの要素__ を持つ __tuple__ です。先ほどのプログラムでは、__`move`__ に __真ん中__ のマスの __座標__ を表す __`(1, 1)`__ という __tuple__ が __代入されているか__ どうかを、__tuple__ の __各要素__ を __`x`__ と __`y`__ に __代入__ してから __`x == 1 and y == 1`__ という __条件式__ を記述することで __判定__ していましたが、この __判定__ を行う __条件式__ を、より __簡潔に記述__ することができます。

具体的には、__2 つ__ の __tuple__ が、__同じ値__ の __要素__ を __持つか__ どうかを、下記のプログラムの 2、3 行目のように、__`==` 演算子__ を使って __判定__ することができます。

```python
move = (1, 1)
print(move == (1, 1))
print(move == (1, 2))
```

実行結果

```
True
False
```

従って、__`ai3s`__ は、下記のプログラムのように記述することができます。

* __9 行目__：__`move == (1, 1)`__ によって、__(1, 1)__ のマスに __着手したか__ どうかを __判定__ する

```python
 1  def ai3s(mb_orig):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = float("-inf")
 4      best_moves = []
 5      for move in legal_moves:
 6          mb = deepcopy(mb_orig)
 7          x, y = move
 8          mb.move(x, y)
 9          if move == (1, 1):
10              score = 1
11          else:
12              score = 0
13          # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
14          if best_score < score:
15              best_score = score
16              best_moves = [move]
17          # score がそれまでの評価値の中の「最大値と等しい」
18          elif best_score == score:
19              best_moves.append(move)
20
21      return choice(best_moves)
```

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

```python
def ai3s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if move == (1, 1):
            score = 1
        else:
            score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

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

```diff_python
def ai3s(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)
        if x == 1 and y == 1:
            score = 1
        else:
            score = 0
        # 最初の合法手を着手した局面 または score がそれまでの評価値の中の「最大値より大きい」
        if best_score < score:
            best_score = score
            best_moves = [move]
        # score がそれまでの評価値の中の「最大値と等しい」
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

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

```python
ai_match(ai=[ai3s, ai3])
```

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

```
ai3s VS ai3
count     win    lose    draw
o        6945    1909    1146
x        1948    6878    1174
total    8893    8787    2320

ratio     win    lose    draw
o       69.5%   19.1%   11.5%
x       19.5%   68.8%   11.7%
total   44.5%   43.9%   11.6%
```

## tuple どうしの比較の注意点

__`==`__ 演算子を使って __tuple__ どうしを __比較__ する際に、__外側__ の __`(`__ と __`)`__ を __省略__ すると、下記のプログラムのような、__意図しない計算__ が __行われる__ 点に __注意__ して下さい。

```python
move = (1, 1)
print(move == 1, 1)  # print((1 == move, 1)) とみなされる
print(1, 1 == move)  # print((1, 1 == move)) とみなされる
```

実行結果

```
False 1
1 False
```

上記の計算が行われる __理由__ は、__2 行目__ の __`move == 1, 1`__ という __式__ は、__1 つ目__ の __要素__ が __`move == 1`__、__2 つ目__ の __要素__ が __`1`__ である、__`(move == 1, 1)`__ という __tuple__ の __外側__ の __`(`__ と __`)`__ が __省略された式__ であると __みなされる__ からです。__`move == 1`__ の計算結果は __`False`__ なので、__実行結果__ には __`(False, 1)`__ という __tuple__ を __表す__、「__False 1__」 が __表示__ されます。3 行目も __同様__ に、__`(1, 1 == move)`__ という __tuple__ と __みなされます__。

## list どうしの比較と、注意点

__list どうし__ の __比較__ も、下記のプログラムの __2、3 行目__ のように、__tuple どうし__ の比較と __同様__ に、__`==`  演算子__ を使って __行う__ ことが __できます__。

ただし、__4 行目__ のように、__要素の値が同じ__ であっても、__list__ と __tuple__ を __`==`__ 演算子で __比較__ すると __`False`__ になる点に __注意__ して下さい。

```python
move = [1, 1]
print(move == [1, 1])
print(move == [1, 2])
print(move == (1, 1))
```

実行結果

```
True
False
False
```

# 評価値を利用した AI のひな形となる関数の定義

今回の記事で実装した __`ai2s`__ と __`ai3s`__ は、__評価値__ を __計算__ する __以外の処理__ は __完全に共通__ します。下記のプログラムは、__`ai2s`__ と __`ai3s`__ の __共通する部分__ を __抜き出したもの__ です。なお、関数名は、仮の名前として `ai` としました。

__共通しない__ のは、真ん中の「__mb の局面の評価値を計算する処理__」の __部分だけ__ です。

```python
def ai(mb_orig):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)

        # mb の局面の評価値を計算する処理
        
        if best_score < score:
            best_score = score
            best_moves = [move]
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```

これは、__ルール 2__、__3 以外__ のルールを __評価値を利用__ した __アルゴリズム__ で __実装__ する場合も __同様__ です。その理由は、上記で抜き出したプログラムが行う処理が、__評価値を利用__ した __アルゴリズム__ で __必ず行わなければならない__、__共通の処理__ だからです。

このことから、__評価値を利用__ した __アルゴリズム__ では、__異なるルール__ の __AI__ を実装する際に、__局面__ の __評価値__ を __計算__ する __処理のみ__ が __異なる__ ことがわかります。

__評価値を利用__ した __アルゴリズム__ で __AI__ の __関数を記述__ する際に、__毎回__ 上記の __コメント以外__ のプログラムを __記述__ するのは __大変__ なので、上記の __共通する部分__ の処理を行う、__ひな形__ となる __関数を定義__ し、__評価値の計算__ を行う __処理のみ__ を __記述__ することで、__評価値を利用__ した __アルゴリズム__ の __AI__ を __簡潔に実装__ できるようにします。

## 関数名の設定と、仮引数の追加

まず、__ひな形__ となる __関数の名前__ を決める必要があります。__評価値__（score）を利用する AI なので、__`ai_by_score`__ という __名前にする__ ことにします。

__ひな形__ となる __関数の中__ で、「__mb の局面の評価値を計算する処理__」は、関数の __仮引数__ に __代入__ した __関数__ を __呼び出して行う__ ことにします。これは、__`Marubatsu`__ クラスの __`play`__ メソッドや、__`ai_match`__ の __実引数__ に、__AI の処理__ を行う __関数__ を __記述__ することで、__`play`__ メソッドや __`ai_match`__ の中で __その関数__ による __処理を行う__ ことができるようにした手法と __同じ__ です。

__評価値__ を __計算__ する __関数__ のことを、__評価関数__（__evaluate function__）と呼ぶので、その __関数を代入__ する __仮引数の名前__ は、それらの単語を略してつなげた __`eval_func`__ と命名しました。

下記は、先程のプログラムの __関数名__ を __`ai_by_score`__ に __変更__ し、__仮引数__ に __`eval_func`__ を __追加__ したプログラムです。

```python
def ai_by_score(mb_orig, eval_func):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)

        # eval_func を使って、mb の局面の評価値を計算する処理
        
        if best_score < score:
            best_score = score
            best_moves = [move]
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```

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

```diff_python
-def ai(mb_orig):
+def ai_by_score(mb_orig, eval_func):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)

-       # mb の局面の評価値を計算する処理
+       # eval_func を使って、mb の局面の評価値を計算する処理
        
        if best_score < score:
            best_score = score
            best_moves = [move]
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

## 評価関数の仕様

__`ai_by_score`__ の中で、__評価関数__ を __利用する処理__ を __記述__ するためには、__評価関数__ の __入力__（__仮引数__）と __出力__（__返り値__）の __仕様__ を決める必要があります。

__評価関数__ は、__局面__ の __評価値を計算__ する __処理__ を行うので、__仮引数__ に __現在の局面__ を表す __`Marubatsu` クラス__ の __インスタンス__ を __代入__ し、__返り値__ として __評価値を返す__ ことにします。

__評価関数__ の __仕様__ が __決まった__ ので、__`ai_by_score`__ の「__eval_func を使って、mb の局面の評価値を計算する処理__」の部分には、下記のプログラムの __10 行目__ のように、__`eval_func`__ の __実引数__ に __`mb`__ を __記述__ して呼び出し、その __返り値__ を __`score` に代入__ する処理を記述します。

```python
 1  def ai_by_score(mb_orig, eval_func):
 2      legal_moves = mb_orig.calc_legal_moves()
 3      best_score = float("-inf")
 4      best_moves = []
 5      for move in legal_moves:
 6          mb = deepcopy(mb_orig)
 7          x, y = move
 8          mb.move(x, y)
 9
10          score = eval_func(mb)
11        
12          if best_score < score:
13              best_score = score
14              best_moves = [move]
15          elif best_score == score:
16              best_moves.append(move)
17
18      return choice(best_moves)
```

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

```python
def ai_by_score(mb_orig, eval_func):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)

        score = eval_func(mb)
        
        if best_score < score:
            best_score = score
            best_moves = [move]
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

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

```diff_python
def ai_by_score(mb_orig, eval_func):
    legal_moves = mb_orig.calc_legal_moves()
    best_score = float("-inf")
    best_moves = []
    for move in legal_moves:
        mb = deepcopy(mb_orig)
        x, y = move
        mb.move(x, y)

+       score = eval_func(mb)
        
        if best_score < score:
            best_score = score
            best_moves = [move]
        elif best_score == score:
            best_moves.append(move)

    return choice(best_moves)
```
</details>

## `ai_by_score` を利用した、ルール 2 で着手を行う AI の定義

__`ai_by_score`__ を __使って__、__ルール 2__ で __着手__ を行う __AI__  の __定義__ を行う __方法__ を説明します。

まず、__ルール 2__ の __評価関数__ を __定義__ する必要があります。__先ほど実装__ した __`ai2s`__ と同様に、 __すべての局面__ の __評価値__ を __0__ にすれば良いので、__評価関数__ は、下記のプログラムのように、__常に 0 を返す関数__ として __定義__ します。

```python
def eval_func(mb):
    return 0
```

__`ai2s`__ は、__`ai_by_score`__ と上記の __`eval_func`__ を使って、下記のように __定義__ できます。

```python 
def ai2s(mb):
    return ai_by_score(mb, eval_func)
```

このように、__ひな形__ となる __`ai_by_score`__ を __定義__ した事で、__評価関数__ の __定義__ と、__`return ai_by_score(mb, eval_func)`__ を __記述するだけ__ で __AI を作成できる__ ようになります。

## 動作の確認

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

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

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

```
ai2s VS ai2
count     win    lose    draw
o        5774    2869    1357
x        2912    5830    1258
total    8686    8699    2615

ratio     win    lose    draw
o       57.7%   28.7%   13.6%
x       29.1%   58.3%   12.6%
total   43.4%   43.5%   13.1%
```

## `ai_by_score` を利用した、ルール 3 で着手を行う AI の定義

次に、__`ai_by_score`__ を使って、__ルール 3__ で着手を行う __AI__ を __定義__ することにします。

そのためには、__ルール 3__ の __評価関数__ を __定義__ する __必要__ がありますが、__ルール 2__ の __評価関数__ の __名前__ に __`eval_func`__ という __名前__ を __使った__ ので、その関数の名前には __別の名前__ を __付ける必要__ があります。また、__`ai3s`__ と __評価関数__ の __定義__ を __別々に記述__ すると、その __2 つの関数__ の __関係__ が __わかりづらくなる__ という __欠点__ があります。そこで、それらの __問題__ を __解決__ する __方法__ として、__AI の関数__ と __評価関数__ を、__1 つにまとめる方法__ を紹介します。

### ローカル関数

その方法は、__評価関数__ を __AI__ の __ローカル関数__ として __定義__ するというものです。__ローカル関数__ は、__関数の中__ に __定義した関数__ の事で、__以下__ の __ローカル変数__ と __同様の性質__ を持ちます。

* __ローカル関数__ は __その関数__ の __ブロックの中__ でしか __利用できない__
* __異なる関数__ の中で、__同一の名前__ の __ローカル関数__ を __異なる関数__ として __定義できる__

上記のような性質を持つ __理由__ は、__ローカル変数__ も、__ローカル関数__ も、[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c#%E3%83%AD%E3%83%BC%E3%82%AB%E3%83%AB%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93)で説明した、その __関数の__、__ローカル名前空間__ で __管理__ されるからです。

従って、__`ai2s`__ は、下記のプログラムのように定義できます。

* __2 行目__：__評価関数__ を __`ai3s`__ の __ローカル関数__ として __`eval_func`__ という __名前__ で __定義__ する
* __3、4 行目__：__直前の着手__ は、__`mb`__ の __[`last_move`](https://qiita.com/ysgeso/items/1800a353cb609a0fef4e#%E7%9B%B4%E5%89%8D%E3%81%AE%E7%9D%80%E6%89%8B%E3%82%92%E8%A8%98%E9%8C%B2%E3%81%99%E3%82%8B%E5%B1%9E%E6%80%A7) 属性__ に __代入__ されるので、それが __真ん中__ のマスを表す __`(1, 1)`__ と __等しい__ 場合は __評価値__ として __`1`__ を __返す__
* __5、6 行目__：それ以外の場合は、__評価値__ として __`0`__ を __返す__
* __8 行目__：__`ai_by_score`__ の __実引数__ に __`eval_func`__ を記述して呼び出した __返り値__ を __返す__

```python
1  def ai3s(mb):
2      def eval_func(mb):
3          if mb.last_move == (1, 1):
4              return 1
5          else:
6              return 0
7
8      return ai_by_score(mb, eval_func)
```

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

```python
def ai3s(mb):
    def eval_func(mb):
        if mb.last_move == (1, 1):
            return 1
        else:
            return 0

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

:::note
__2 行目__ の __評価関数__ の __名前__ は、__好きな名前__ で定義しても __構いません__ が、__その場合__ は、__8 行目__ の __実引数__ の __評価関数__ に __その名前__ を __記述__ する __必要__ があります。
::: 

## 動作の確認

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

```python
ai_match(ai=[ai3s, ai3])
```

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

```
ai3s VS ai3
count     win    lose    draw
o        6915    1948    1137
x        1876    7001    1123
total    8791    8949    2260

ratio     win    lose    draw
o       69.2%   19.5%   11.4%
x       18.8%   70.0%   11.2%
total   44.0%   44.7%   11.3%
```

## ローカル関数の利点

__ローカル関数__ を __利用__ することで、以下のような __利点__ を __得る__ ことができます。

* __AI の関数__ と __評価関数__ を、__一つ__ の __関数の定義__ で __まとめる__ ことが __できる__
* __どの AI__ を __実装__ する __場合__ でも、__評価関数__ の __名前__ として、__常に `eval_func`__ という __共通の名前__ を __利用できる__ ので、__AI ごと__ に、__異なる名前__ を __考える必要__ が __なくなる__

## ローカル関数に関する補足

__一般的__ に __関数__ は、__特定の処理__ を、プログラムの __さまざまな場所__ から __利用できるようするこ__ とが __目的__ で __定義__ しますが、__その目的__ で __ローカル関数__ を __利用__ することは __できません__。従って、__ローカル関数__ は、今回の記事で紹介したような、__ローカル関数の利点__ を __有効に活用__ できるような __場面以外__ では __あまり使われません__。

__ローカル関数__ は、__クラスの定義__ の __ブロックの中__ で __定義する__、__メソッドに似ている__ ように __見えるかもしれません__ が、クラスの __メソッド__ は、クラスの定義の __ブロックの外__ で、そのクラスの __インスタンス__ から呼び出して __利用__ することが __できます__ が、__ローカル関数__ は、ローカル関数を定義した関数の __ブロックの外__ で __利用__ することが __できない__ 点が __異なります__。


__関数__ の __ブロックの中__ で、__ローカル関数__ を __定義する前__ で、__そのローカル関数__ を呼び出して __利用__ することは __できません__。これは、[以前の記事](https://qiita.com/ysgeso/items/95282cb1532602799052#%E9%96%A2%E6%95%B0%E5%91%BC%E3%81%B3%E5%87%BA%E3%81%97%E3%82%92%E8%A8%98%E8%BF%B0%E3%81%A7%E3%81%8D%E3%82%8B%E5%A0%B4%E6%89%80)で説明した、__グローバル関数__ を __定義する前__ で、__そのグローバル関数__ を呼び出して __利用__ することが __できない__ のと __同じ__ です。[以前の記事](https://qiita.com/ysgeso/items/cd3e1c0731b859bf5e2c) で説明した、__名前空間の仕組み__ 正しく理解していれば、そのことは __明らか__ でしょう。

従って、下記のプログラムのように、__`ai3s_buggy`__ を定義して、__`ai_match(ai=[ai3s, ai3])`__ を呼び出すと、下記の実行結果のように __エラーが発生__ します。なお、__関数名__ の一部の __buggy__ は、__バグのある__ という __意味__ の英語です。

```python
def ai3s_buggy(mb):
    return ai_by_score(mb, eval_func)

    def eval_func(mb):
        if mb.last_move == (1, 1):
            return 1
        else:
            return 0

ai_match(ai=[ai3s_buggy, ai3])        
```

実行結果
```
略
Cell In[19], line 2
      1 def ai3s_buggy(mb):
----> 2     return ai_by_score(mb, eval_func)
      4     def eval_func(mb):
      5         if mb.last_move == (1, 1):

UnboundLocalError: cannot access local variable 'eval_func' where it is not associated with a value
```

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

* __UnboundLocalError__

ローカル（Local）変数（または関数）が名前空間に登録されていない（unbound）ことを表すエラー

* __cannot access local variable 'eval_func' where it is not associated with a value__

値（vaule）が関連付けられていない（whiere it is not associated）eval_func というローカル（local）変数（または関数）（variable）をアクセス（利用）（access）できない（cannot）
:::

## ローカル関数を利用した、ルール 2 で着手を行う AI の定義

せっかくなので、下記のプログラムのように、__ルール 2__ についても、__ローカル関数__ を __利用__ した __`ai2s`__ の __定義__ を行います。

```python
def ai2s(mb):
    def eval_func(mb):
        return 0
        
    return ai_by_score(mb, eval_func)
```

## 動作の確認

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

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

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

```
ai2s VS ai2
count     win    lose    draw
o        5921    2857    1222
x        2829    5896    1275
total    8750    8753    2497

ratio     win    lose    draw
o       59.2%   28.6%   12.2%
x       28.3%   59.0%   12.8%
total   43.8%   43.8%   12.5%
```

# 今回の記事のまとめ

今回の記事では、__評価値を利用__ した __アルゴリズム__ を __紹介__ し、__評価値を使った AI__ の __ひな形__ となる __処理__ を行う __`ai_by_score`__ を __定義__ する事で、__AI の処理__ を行う __関数__ を __評価関数__ を __記述するだけ__ で、__簡潔__ に __AI の関数__ を __記述__ する __方法__ を __説明__ しました。

また、__実際__ に __ルール 2、3__ を、__評価値を利用__ した __アルゴリズム__ で __定義__ しました。

今回の記事の内容からは、評価値を利用したアルゴリズムの __利点__ が __あまり感じられない__ かもしれません。次回の記事では引き続き、ルール 1、4 ~ 7 を評価値を利用したアルゴリズムで定義し、__評価値を利用__ した __アルゴリズム__ の __利点と欠点__ について __説明__ します。

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

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

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

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

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

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

# 次回の記事

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

[^1]:inf は、無限大を表す infinity の略です