Pythonで〇×ゲームのAIを一から作成する　その35　さまざまな勝利判定のアルゴリズム2

# 目次と前回の記事

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

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

# 前回までのおさらい

## 〇×ゲームの仕様と進捗状況

1. `正方形で区切られた 3 x 3 の 2 次元のゲーム盤上でゲームを行う`
2. `ゲーム開始時には、ゲーム盤のすべてのマスは空になっている`
3. `2 人のプレイヤーが遊ぶゲームであり、一人は 〇 を、もう一人は × のマークを受け持つ`
4. `2 人のプレイヤーは、交互に空いている好きなマスに自分のマークを 1 つ置く`
5. `先手は 〇 のプレイヤーである`
6. `プレイヤーがマークを置いた結果、縦、横、斜めのいずれかの一直線の 3 マスに同じマークが並んだ場合、そのマークのプレイヤーの勝利とし、ゲームが終了する`
7. `すべてのマスが埋まった時にゲームの決着がついていない場合は引き分けとする`

仕様の進捗状況は、以下のように表記します。

* 実装が完了した部分を `背景が灰色の長方形` で記述する
* 実装の一部が完了した部分を、__太字__ で記述する

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/035/test.py

## 前回までのおさらい

前回の記事では、〇 または × が勝利していることを判定する `is_winner` メソッドを実装するさまざまなアルゴリズムを紹介しました。今回の記事ではその続きを紹介します。

# `is_winner` のアルゴリズム その 6　（あらかじめデータを作成しない）

前回の [記事の最後](https://qiita.com/ysgeso/items/d457f37df8671e930603#is_winner-%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-%E3%81%9D%E3%81%AE-5-%E5%B7%AE%E5%88%86%E3%81%A7%E5%BA%A7%E6%A8%99%E3%82%92%E8%A8%88%E7%AE%97%E3%81%99%E3%82%8B)では、下記のプログラムのように、__最初__ に一直線上のマスの座標を作成するための __データを集めた list__ を __作成__ し、その __データを元__ に __繰り返し処理__ によって __判定__ を行いました。

この方法には、__あらかじめ__ データを __作成__ しておくことによって、__判定__ を 1 つの __繰り返し処理__ によって __まとめて行う__ ことができるという __利点__ があります。

```python
    def is_winner(self, player):
        # 一直線上のマスの座標を作成するためのデータを集めた list を代入する変数を空の list で初期化する
        judge_data_list = []
        # 横方向の座標を作成するために必要なデータを追加する
        for y in range(self.BOARD_SIZE):
            judge_data_list.append({ "coord": [0, y], "dx": 1, "dy": 0 })
        # 縦方向の座標を作成するために必要なデータを追加する
        for x in range(self.BOARD_SIZE):
            judge_data_list.append({ "coord": [x, 0], "dx": 0, "dy": 1 })
        # 左上から右下方向の座標を追加する
        judge_data_list.append({ "coord": [0, 0], "dx": 1, "dy": 1 })
        # 右上から左下方向の座標を追加する
        judge_data_list.append({ "coord": [2, 0], "dx": -1, "dy": 1 })     

        # 一直線上のマスの座標作成するためのデータを順番に取り出す繰り返し処理
        for judge_data in judge_data_list:
            # 取り出した一直線上のマスに player が配置されているかどうかを判定する
            if self.is_same(player, **judge_data):
                # 並んでいれば player の勝利なので True を返す
                return True

        # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
        return False
```

上記のプログラムでは、`is_winner` を __実行する際__ に、横方向で 3 つ、縦方向で 3 つ、斜め方向で 2 つの、__計 8 つ__ の __要素__ を持つ `judge_data_list` を __作成__ していますが、この方法では、ゲーム盤の __サイズが大きくなった__ 際に、[前回の記事](https://qiita.com/ysgeso/items/d457f37df8671e930603#is_winner-%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-%E3%81%9D%E3%81%AE-4-%E3%83%87%E3%83%BC%E3%82%BF%E3%82%92%E8%A8%88%E7%AE%97%E3%81%A7%E4%BD%9C%E3%82%8A%E5%87%BA%E3%81%99) で紹介したその 4 の方法ほどではありませんが、__多くの要素__ を持つ `judge_data_list` を __作成する必要__ があります。

`judge_data_list` のような list を __作成せず__ に、__上記と同様の処理__ を行う方法として、下記のプログラムのように、横方向、縦方向、斜め方向の __それぞれに分けて__ for 文による __繰り返し処理を行う__ という __アルゴリズム__ が考えられます。なお、修正箇所が多すぎるので、修正箇所は示しません。

```python
from marubatsu import Marubatsu

def is_winner(self, player):
    # 横方向の判定
    for y in range(self.BOARD_SIZE):
        if self.is_same(player, coord=[0, y], dx=1, dy=0):
            return True
    # 縦方向の判定
    for x in range(self.BOARD_SIZE):
        if self.is_same(player, coord=[x, 0], dx=0, dy=1):
            return True
    # 左上から右下方向の判定
    if self.is_same(player, coord=[0, 0], dx=1, dy=1):
        return True
    # 右上から左下方向の判定
    if self.is_same(player, coord=[2, 0], dx=-1, dy=1):
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner
```

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果から、すべてのテストケースで期待された処理が行われることが確認できます。

```python
from test import test_judge

test_judge()
```
実行結果
```
Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished
```

## このアルゴリズムの性質

この方法では、判定を行うための、__`self.is_same`__ と __`return True`__ を __4 箇所に記述__ する必要があるので __効率が悪い__ ように __思える__ かもしれませんが、その 5 のプログラムで記述していた、__4 つ__ の `judge_data_list.append` によって __要素を追加__ する処理が代わりに __なくなる__ ので、__結局__ のところ、記述する __プログラムの量__ は __ほぼ同じ__ です。__実際__ に、__コメントを除いた__ 場合の __`is_winner`__ の __ブロックの行数__ は その 5 も その 6 も __11 行__ で __変わりません__。

下記プログラムは、その 5 と その 6 の __横方向の判定__ に __関する部分__ を __抜き出した__ ものです。それぞれの部分が __どのように対応__ しているか __確認__ して下さい。

```python
# その 5 の横方向の座標を作成するために必要なデータを追加する処理
for y in range(self.BOARD_SIZE):
    judge_data_list.append({ "coord": [0, y], "dx": 1, "dy": 0 })

# その 6 の横方向の判定を行う処理
for y in range(self.BOARD_SIZE):
    if self.is_same(winner, coord=[0, y], dx=1, dy=0):
        return True
```

その 6 の他の __利点__ としては、もちろん人によって __意見は異なる可能性__ はありますが、その 6 のプログラムの方が、プログラムの __見た目がわかりやすい__ という利点もあります。

## プログラムの簡略化

先程のプログラムは、下記のプログラムのように、__横方向__ と __縦方向__ の __判定__ を __1 つ__ の for 文で __まとめて記述__ することもできます。なお、修正前の for 文の __変数名__ は `x` と `y` でしたが、そのままではプログラムの意味が分かりづらくなるので、変数名を __`i` に変更__ しました。 

```python
def is_winner(self, player):
    # 横方向と縦方向の判定
    for i in range(self.BOARD_SIZE):
        if self.is_same(player, coord=[0, i], dx=1, dy=0) or \
           self.is_same(player, coord=[i, 0], dx=0, dy=1):
            return True
    # 左上から右下方向の判定
    if self.is_same(player, coord=[0, 0], dx=1, dy=1):
        return True
    # 右上から左下方向の判定
    if self.is_same(player, coord=[2, 0], dx=-1, dy=1):
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner
```

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

```diff_python
def is_winner(self, player):
-   # 横方向の判定
+   # 横方向と縦方向の判定
-   for y in range(self.BOARD_SIZE):
+   for i in range(self.BOARD_SIZE):
-       if self.is_same(player, coord=[0, y], dx=1, dy=0):
+       if self.is_same(player, coord=[0, i], dx=1, dy=0) or \
+          self.is_same(player, coord=[i, 0], dx=0, dy=1):
            return True
-   # 縦方向の判定
-   for x in range(self.BOARD_SIZE):
-       if self.is_same(player, coord=[x, 0], dx=0, dy=1):
-           return True
    # 左上から右下方向の判定
    if self.is_same(player, coord=[0, 0], dx=1, dy=1):
        return True
    # 右上から左下方向の判定
    if self.is_same(player, coord=[2, 0], dx=-1, dy=1):
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner
```
</details>


下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

# `is_same` のアルゴリズム その 2 （数を数える）

次は、__`is_same`__ のさまざまなアルゴリズムを紹介します。

下記のプログラムは、[前回の記事](https://qiita.com/ysgeso/items/d457f37df8671e930603#is_same-%E3%81%AE%E4%BF%AE%E6%AD%A3)で定義した `is_same` メソッドです。前回の記事ではそのように記述しませんでしたが、下記のプログラムを `is_same` のアルゴリズム その 1 と考えて下さい。

```python
    def is_same(self, mark, coord, dx, dy):
        x, y = coord   
        for _ in range(self.BOARD_SIZE):
            if self.board[x][y] != mark:
                return False
            x += dx
            y += dy

        return True
```

上記のプログラムでは、__一直線上__ の __すべてのマス__ に、__`mark`__ のマークが __配置されているかどうか__ を判定していますが、下記のような、一直線上のマスに、__`mark`__ のマークが __配置__ されている __マスの数__ を __数える__ というアルゴリズムでも、同様の判定を行うことができます。

なお、「`mark` のマークが配置」は冗長なので、以後は「__`mark` が配置__」のように記述します。

1. __`mark` が配置__ されている __マスの数__ を __数える__
2. __数えたマスの数__ が、__一直線上のマスの数__ と __同じ__ であれば、__`mark`__ が __一直線上に並んでいる__ ので __`True` を返す__
3. __そうでなければ__　一直線上に __並んでいない__ ので __`False` を返す__

〇× ゲームの場合は、一直線上の __3 つのマス__ に `mark` が __いくつ配置されているか__ を __数え__、__3 つ__ であれば、一直線上に __並んでおり__、__それ以外__ の場合は __並んでいない__ ことになります。

下記は、このアルゴリズムで `is_same` を記述したプログラムで、修正点は以下の通りです。

* __3 行目__：__`mark`__ が配置された __マスの数を数える__ 変数 __`count`__ を __`0` で初期化__ する
* __5、6 行目__：__(x, y)__ のマスに __`mark`__ が __配置されている__ 場合は、__`count`__ に __`1` を加算__ する
* __10 行目__：__`count`__ と、一直線上の __マスの数__ を表す __`self.BOARD_SIZE`__ を __`==` 演算子で比較__ した __計算結果を返す__。その結果、この関数は、`count` と `self.BOARD_SIZE` が __等しければ `True`__ を、__そうでなければ `False`__ を返すようになる

```python
 1  def is_same(self, mark, coord, dx, dy):
 2      x, y = coord   
 3      count = 0
 4      for _ in range(self.BOARD_SIZE):
 5          if self.board[x][y] == mark:
 6             count += 1
 7          x += dx
 8          y += dy
 9
10      return count == self.BOARD_SIZE
11
12  Marubatsu.is_same = is_same
```

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

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord   
    count = 0
    for _ in range(self.BOARD_SIZE):
        if self.board[x][y] == mark:
            count += 1
        x += dx
        y += dy

    return count == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord   
+   count = 0
    for _ in range(self.BOARD_SIZE):
-       if self.board[x][y] != mark:
+       if self.board[x][y] == mark:
-           return False
+           count += 1
        x += dx
        y += dy

-   return True
+   return count == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## このアルゴリズムの性質

その 1 のアルゴリズムでは、for 文の __繰り返しの処理の中__ で、(x, y) のマスに __`mark`__ が __配置されていない__ ことが __分かった時点__ で __return 文__ によって for 文の __繰り返しの処理の途中__ であっても __関数の処理が終了__ します。一方、その 2 のアルゴリズムは、`mark` が配置される __マスを数えている__ ため、for 文が __途中で終了__ することは __ありません__。そのため、その 2 のアルゴリズムは、その 1 のアルゴリズムよりも、__平均__ すると __処理に時間がかかる__ という欠点があります。

そのため、__計算速度の面__ だけを考えれば、__その 1 のアルゴリズムの方__ が、その 2 のアルゴリズムよりも __優秀__ です。それにも関わらず、その 2 のアルゴリズムを紹介したのは、今後 AI を実装する際に、一直線上に、指定した __マーク__ が __いくつ配置されているか__ を __計算する場面__ があるからです。

また、〇×ゲームでは必要はありませんが、五目並べのような、一直線上のどこでも良いので、同じマスに __連続して__ 同じ石が __いくつ並んでいるかを数える__ 必要があるような場合は、__その 1 のアルゴリズム__ を使うことは __できません__。

# `is_same` のアルゴリズム その 3 （list と `sum`の利用）

その 2 のアルゴリズムを、__list__ と __`sum`__ という組み込み関数を使って __記述__ できます。

## list の作成と `sum` による計算

まず、以下のような性質を持つ __list を作成__ します。

* __list の要素__ は、`is_same` で __調べる__ それぞれの __マスに対応__ する
* 各 __要素__ は、`is_same` で調べるマスに __`mark` が配置されていれば `1`__、__そうでなければ `0`__ とする

上記のような list を作成することができれば、list の __要素の合計__ を計算することで、`is_same` が調べるマスのうち、__`mark` が配置__ されている __マスの数__ を __数える__ ことができます。

Python では、__`sum`__ という __組み込み関数__ を利用することで、下記のプログラムのように、__実引数に記述__ した、__反復可能オブジェクト__ の __すべての要素の合計__ を __計算__ することができます。

```python
print(sum([1, 2, 3]))
```
実行結果
```
6
```

`sum` の詳細については、下記のリンク先を参照してください。

https://docs.python.org/ja/3/library/functions.html?highlight=sum#sum

従って、`is_same` を、下記のプログラムのように記述できます。修正点は以下の通りです。

* __3 行目__：__`same_list`__ に __空の list__ を代入して __初期化__ する
* __5 ~ 8 行目__：(x, y) のマスに __`mark` が配置__ されている場合は __`0`__ を、__そうでなければ `1`__ を __`same_list`__ の __要素として追加__ する
* __12 行目__：__`sum`__ を使って、__`same_list`__ の __要素の合計__ を __計算__ し、__`self.BOARD_SIZE`__ と __等しいかどうか__ を比較した __計算結果__ を __返り値__ として __返す__ 

```python
 1  def is_same(self, mark, coord, dx, dy):
 2      x, y = coord
 3      same_list = []
 4      for _ in range(self.BOARD_SIZE):
 5          if self.board[x][y] == mark:
 6              same_list.append(1)
 7          else:
 8              same_list.append(0)
 9          x += dx
10          y += dy
11  
12      return sum(same_list) == self.BOARD_SIZE
13
14  Marubatsu.is_same = is_same
```

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

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = []
    for _ in range(self.BOARD_SIZE):
        if self.board[x][y] == mark:
            same_list.append(1)
        else:
            same_list.append(0)
        x += dx
        y += dy

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
-   count = 0
+   same_list = []
    for _ in range(self.BOARD_SIZE):
        if self.board[x][y] == mark:
-           count += 1
+           same_list.append(1)
+       else:
+           same_list.append(0)
        x += dx
        y += dy

-   return count == self.BOARD_SIZE
+   return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

上記のプログラムは、いくつかの方法で __簡略化__ できるので、その方法について説明します。

## `sum` に関する注意点

`sum` を利用する際は、反復可能オブジェクトの __要素__ は、__すべて数値型のデータ__ でなければならない点に __注意が必要__ です。例えば、下記のプログラムは、list の __要素__ に __文字列が代入__ されているので実行すると __エラーが発生__ します。

```python
print(sum(["1", "2", "3"]))
```
実行結果
```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
c:\Users\ys\ai\marubatsu\035\marubatsu.ipynb セル 10 line 1
----> 1 print(sum(["1", "2", "3"]))

TypeError: unsupported operand type(s) for +: 'int' and 'str'
```

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

* __TypeError__
データ型（type）に関するエラー
* __unsupported operand type(s) for +: 'int' and 'str'__
整数型（int type）と文字列型（str type）に対する（for）+ 演算子（operand）による演算は提供されていない（unsupported）
:::

上記のプログラムでは、list の __要素__ が __すべて文字列__ なので、エラーメッセージの、「__整数型と文字列型__ に対する + 演算子（operand）による演算」の部分が __おかしい__ のではないかと __思う人がいるかもしれない__ ので補足します。

`sum` のような、__組み込み関数の定義__ を __見ることはできません__ が、おそらく下記のプログラムのような定義になっているのではないかと __推測されます__。なお、下記のプログラムは、__本物__ の `sum` の定義 __ではなく__、__疑似的__（pseudo）なものなので、関数の名前を __`pseudo_sum`__ としました。

```python
def pseudo_sum(data):
    total = 0
    for num in data:
        total += num
    return total
```

合計を計算するためには、__途中の計算結果__ を __記憶__ しておく __変数が必要__ なので、上記のプログラムでは、2 行目で __`total`__ という変数を __`0` で初期化__ し、4 行目で __`total`__ に __list から取り出したデータ__ を __加算__ するという処理を行っています。`data` に __`["1", "2", "3"]`__ のようなデータが代入されていた場合は、3 行目の for 文の __最初の繰り返し__ で、__`num` に `"1"` が代入__ されるため、4 行目では、__`0 + "1"`__ という、__整数型と文字列型__ のデータを `+` 演算子で __演算__ するという処理が行われるため、上記のようなエラーが発生します。
 
__文字列型__ のデータは、__反復可能オブジェクト__ ですが、__同様の理由__ で、__`sum`__ の __実引数__ に __文字列型のデータを記述__ して呼び出すと、下記のプログラムのように __エラーが発生__ します。

```python
print(sum("123"))
```
実行結果
```
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
c:\Users\ys\ai\marubatsu\035\marubatsu.ipynb セル 12 line 1
----> 1 print(sum("123"))

TypeError: unsupported operand type(s) for +: 'int' and 'str'
```

## 三項演算子による簡略化

```python
        if self.board[x][y] == mark:
            same_list.append(1)
        else:
            same_list.append(0)
```

先程のプログラムの上記の部分は、[以前の記事](https://qiita.com/ysgeso/items/ed1eb1cacf9a3e7dfa29#%E4%B8%89%E9A0%85%E6%BC%94%E7%AE%97%E5%AD%90) で説明した __三項演算子__ を使うことで、下記のプログラムのように __1 行で記述__ することができます。

```python
same_list.append(1 if self.board[x][y] == mark else 0)
```

下記は、そのように修正したプログラムです。

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = []
    for _ in range(self.BOARD_SIZE):
        same_list.append(1 if self.board[x][y] == mark else 0)
        x += dx
        y += dy

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = []
    for _ in range(self.BOARD_SIZE):
-       if self.board[x][y] == mark:
-           same_list.append(1)
-       else:
-           same_list.append(0)
+       same_list.append(1 if self.board[x][y] == mark else 0)
        x += dx
        y += dy

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>


下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## 論理型（`True`、`False`）と数値型のデータの計算

上記では、三項演算子を使ってプログラムを簡略化しましたが、__この三項演算子__ は __省略できます__。

Python では、__論理型__（bool）のデータである、__`True`__、__`False`__ と __数値型__ のデータを __直接__ `+` や `-` などの __演算子__ で __演算__ することができ、その場合は、下記のプログラムのように __`True` は `1`__、__`False` は `0`__ と __みなされて計算__ が行われます。

```python
print(True + 2)     # 1 + 2 と同じ
print(False * 3)    # 0 * 3 と同じ
print(True - False) # 1 - 0 と同じ
```
実行結果
```
3
0
1
```

従って、下記のプログラムの __1 行目__ と、__2 行目__ は __全く同じ計算__ が行われます。

```python
1 if self.board[x][y] == mark else 0
True if self.board[x][y] == mark else False
self.board[x][y] == mark
```

また、__`True if self.board[x][y] == mark else False`__ という式は、__`self.board[x][y] == mark`__ の __計算結果__ が __`True` の場合は `True`__ を、__`False` の場合は `False`__ を計算する式なので、上記のプログラムの __2 行目__ と __3 行目__ は __全く同じ計算__ が行われます。

従って、上記のプログラムの 1 行目の式は、3 行目のように簡潔に記述することができます。下記は、そのように `is_same` を記述したプログラムです。

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = []
    for _ in range(self.BOARD_SIZE):
        same_list.append(self.board[x][y] == mark)
        x += dx
        y += dy

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = []
    for _ in range(self.BOARD_SIZE):
-       same_list.append(1 if self.board[x][y] == mark else 0)
+       same_list.append(self.board[x][y] == mark)
        x += dx
        y += dy

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>


下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## このアルゴリズムの性質

このアルゴリズムは、このままでは、その 2 のプログラムと比べて __短く記述できていません__ が、次で説明をする、__list 内包表記__ を使うことで、プログラムを __簡潔に記述できる__ ようになります。

なお、__三項演算子__ は、__式が複雑__ になって見た目が __わかりづらくなる傾向__ があります。上記で紹介したような、式の中に __三項演算子のみ__ を記述するような場合は __問題はありません__ が、式が __複雑になりすぎると思った場合__ は __使わないほうが良い__ でしょう。

# `is_same` のアルゴリズム その 4 （list 内包表記などを使った簡略化）

その 3 のプログラムは、__list 内包表記__ などを使って、さらに __簡略化__ することができます。

## list 内包表記を使った簡略化

[以前の記事](https://qiita.com/ysgeso/items/2a436b3819bef9a6a2b4#%E3%83%AA%E3%82%B9%E3%83%88%E5%86%85%E5%8C%85%E8%A1%A8%E8%A8%98)で説明したように、__list 内包表記__ は、下記のような for 文の __ブロックの中__ で __`append`__  の __処理のみ__ を行うプログラムを、その下のプログラムのように、__簡潔に記述__ する表記方法です。

```python
a = []
for 変数名 in 反復可能オブジェクト:
    a.append(式)
```
```python
a = [式 for 変数名 in 反復可能オブジェクト]
```

先程のプログラムは、下記の for 文による __繰り返し処理__ の __ブロックの中__ に、__`x += dx`__ と、__`y + dy`__ という __式が記述__ されているため、__list 内包表記__ を使って __記述__ することが __できません__。

```python
    same_list = []
    for _ in range(self.BOARD_SIZE):
        same_list.append(self.board[x][y] == mark)
        x += dx
        y += dy
```

従って、上記のプログラムを __list 内包表記で記述__ するためには、for 文の __ブロックの中__ から、__`x += dx`__ と __`y += dy`__ を __削除する必要__ があります。そのためには、この __2 つの式__ を __使わず__ に、__`same_list.append(self.board[x][y] == mark)`__ の部分を __計算する__ ようにプログラムを __修正する必要__ があります。その方法について少し考えてみて下さい。

__`same_list.append(self.board[x][y] == mark)`__ の __`x` と `y`__ は、for 文の __繰り返しの処理__ の中で、__繰り返しのたび__ に __`dx` と `dy` ずつ加算__ されていきます。従って、__初回__ の繰り返しを __0 回目__ とした場合、__`i` 回目__ の繰り返し処理では、__`x` と `y` の値__ は、__最初の値から__ それぞれ __`dx * i`、`dy * i` だけ加算__ された値になることがわかります。

for 文の __反復可能オブジェクト__ に __`range(式)` を記述__ した場合、for 文の __変数に代入__ されるのは、__繰り返しの回数__ なので、上記の for 文は、下記のプログラムのように修正することができます。

* __2 行目__：for 文の中の __変数名__ を `_` から __`i` に修正__ する
* __3 行目__：__`x` を `x + i * dx`__、__`y` を `y + i * dy`__ に __修正__ する

```python
    same_list = []
    for i in range(self.BOARD_SIZE):
        same_list.append(self.board[x + i * dx][y + i * dy] == mark)
```

for 文の __ブロックの中__ が、__`same_list.append` だけ__ になったので、上記のプログラムを下記のプログラムのように __list 内包表記__ を使って __1 行で記述__ することができます。

```python
same_list = [self.board[x + i * dx][y + i * dy] == mark for i in range(self.BOARD_SIZE)
```

下記は、そのように `is_same` を記述したプログラムです。

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = [self.board[x + i * dx][y + i * dy] == mark for i in range(self.BOARD_SIZE)]
    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
-   same_list = []
+   same_list = [self.board[x + i * dx][y + i * dy] == mark for i in range(self.BOARD_SIZE)]
-   for _ in range(self.BOARD_SIZE):
-       same_list.append(self.board[x][y] == mark)
-       x += dx
-       y += dy

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

:::note
上記のような __長い list 内包表記__ は見た目が __わかりづらくなる__ ので、下記のプログラムのように、__for の直前など__ で __改行__ して __読みやすくする__ ことが良く行われます。なお、__`[` と `]` の間__ であれば、__改行の前に `\` を記述__ する必要や、__インデントを揃える__ 必要は __ありません__。

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    same_list = [self.board[x + i * dx][y + i * dy] == mark
                 for i in range(self.BOARD_SIZE)]
    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
-   same_list = [self.board[x + i * dx][y + i * dy] == mark for i in range(self.BOARD_SIZE)]
+   same_list = [self.board[x + i * dx][y + i * dy] == mark
+                for i in range(self.BOARD_SIZE)]
    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>


下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```
:::

## さらなる簡略化とその利点と欠点

上記のプログラムは、__一旦__ `same_list` に __計算した list を代入__ していましたが、下記のプログラムのように、__`sum` の実引数__ に __直接__ list を計算する __list 内包表記を記述__ することもできます。ただし、この簡略化は、return 文に記述される __式が複雑__ になりすぎており、__何の処理が行われているか__ が非常に __分かりづらくなる__ という __デメリット__ が発生しています。例えば、下記の return 文には __`==` 演算子__ が __2 つ記述__ されていますが、それぞれが __何を比較__ しているかすぐにわかりますか？

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    return sum([self.board[x + i * dx][y + i * dy] == mark
                for i in range(self.BOARD_SIZE)]) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```

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

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
-   same_list = [self.board[x + i * dx][y + i * dy] == mark
-                for i in range(self.BOARD_SIZE)]
-   return sum(same_list) == self.BOARD_SIZE
+   return sum([self.board[x + i * dx][y + i * dy] == mark
+               for i in range(self.BOARD_SIZE)]) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

プログラムが __わかりづらくなる__ と、__バグが発生しやすくなる__ だけでなく、バグが発生した時の __修正も困難__ になるので、__簡略化__ することは __必ずしも良いこと__ では __ありません__。

記述したプログラムが __わかりづらいかどうか__ は、__人によって異なる__ ので、今回の記事で紹介した簡略化を __採用するかどうか__ は、__自分で判断__ して下さい。たとえば、list 内包表記がどうしても __わかりづらい__ と思った方は、__無理して__ list 内包表記を __使う必要はありません__。

ただし、以前の記事でも言及しましたが、__他人が記述__ したプログラムを __参考にする場合__ は、今回の記事で紹介したような __簡略化の記述方法の知識__ がどうしても __必要になります__。今回の記事で紹介した簡略化の方法を __自分では使わない場合でも__、そのような簡略化の方法が __存在するということ__ は、__頭の片隅__ にでも __覚えておいたほうが良い__ でしょう。具体的な方法を __暗記していなくても__、そのような方法がある事を知っていれば、__調べて理解できるようになる__ からです。

:::note warn
プログラムの __簡略化__ によってプログラムが __わかりづらくなる__ という __デメリットがある__ 場合は、簡略化することによる __メリット__ と、__デメリット__ の __どちらが上回るかを考慮__ した上で、実際に簡略化を行うかどうかの __判断を行う__ 必要がある。
:::

:::note
__`x` の値__ は __`coord[0]`__、__`y` の値__ は __`coord[1]`__ なので、上記のプログラムは、下記のプログラムのように __さらに簡略化__ することもできますが、このプログラムを見て意味がすぐに分かる人はどれだけいるでしょうか？__個人的__ には __ここまでの簡略化__ は __お勧めしません__。

```python
def is_same(self, mark, coord, dx, dy):
    return sum([self.board[coord[0] + i * dx][coord[1] + i * dy] == mark
                for i in range(self.BOARD_SIZE)]) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```

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

```diff_python
def is_same(self, mark, coord, dx, dy):
-   x, y = coord
-   return sum([self.board[x + i * dx][y + i * dy] == mark
+   return sum([self.board[coord[0] + i * dx][coord[1] + i * dy] == mark
                for i in range(self.BOARD_SIZE)]) == self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```
:::

# `is_same` のアルゴリズム その 5 （`+` 演算子の利用）

`is_same` を、[前回の記事](https://qiita.com/ysgeso/items/d457f37df8671e930603#is_winner-%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-%E3%81%9D%E3%81%AE-1--%E6%BC%94%E7%AE%97%E5%AD%90%E3%82%92%E4%BD%BF%E3%81%86)で紹介した、__`+` 演算子__ を使うアルゴリズムで実装することができます。

具体的には、下記のプログラムのように、`is_same` で __調べるマス__ の __マーク__ を表す文字列を __`+` 演算子で連結__ した __文字列を計算__ し、その文字列が __調べるマスの数__ だけ __`mark`__ が __並んだ文字列__ と __等しいかどうか__ で __判定__ を行います。修正点は以下の通りです。

* __3 行目__：一直線（line）上のマスの __マーク__ の文字列を __連結した文字列__（text）を計算するための、__`line_text`__ という変数を、__空文字で初期化__ する
* __5 行目__：__`line_text`__ に、__(x, y)__ のマスの __マーク__ の __文字列を連結__ する
* __9 行目__：__`line_text`__ と、__調べるマスの数__ を表す __`self_BOARD_SIZE`__ だけ __`mark` が 連結__ した __文字列を比較__ し、__等しい__ 場合は __`True`__、__そうでない__ 場合は __`False`__ を __返す__

```python
 1  def is_same(self, mark, coord, dx, dy):
 2      x, y = coord
 3      line_text = ""
 4      for _ in range(self.BOARD_SIZE):
 5          line_text += self.board[x][y]
 6          x += dx
 7          y += dy
 8
 9      return line_text == mark * self.BOARD_SIZE
10
11  Marubatsu.is_same = is_same
```

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

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    line_text = ""
    for _ in range(self.BOARD_SIZE):
        line_text += self.board[x][y]
        x += dx
        y += dy

    return line_text == mark * self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

<details><summary><strong>修正箇所（その 2 と比較しています）</strong></summary>

```diff_python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
-   count = 0
+   line_text = ""
    for _ in range(self.BOARD_SIZE):
-       if self.board[x][y] == mark:
-           count += 1
+       line_text += self.board[x][y]
        x += dx
        y += dy

-   return count == self.BOARD_SIZE
+   return line_text == mark * self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## list と `join` を使った記述方法

[以前の記事](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#join-%E3%83%A1%E3%82%BD%E3%83%83%E3%83%89%E3%81%AB%E3%82%88%E3%82%8B%E6%96%87%E5%AD%97%E5%88%97%E3%81%AE%E5%A4%89%E6%8F%9B) で説明したように、__文字列型__ のデータ __のみ__ を __要素__ として持つ __list の要素__ を、__`join` メソッド__ を使って、__特定の文字列__ で __間を区切って連結__ することができます。その際に、__空文字__ に対して __`join` メソッド__ を記述することで、__list の要素__ を __直接連結__ した __文字列を計算__ できます。

従って、先程のプログラムを、下記のように記述することができます。3、4 行目で __list 内包表記__ を使っていますが、__分かりづらい__ と思った人は __for 文で記述__ しても __構いません__。

* __3、4 行目__：一直線（line）上のマスの __マーク__ の文字列を __要素__ として持つ __list__  を __list 内包表記で計算__ し、__`text_list` に代入す__ る
* __5 行目__：__空文字__ に対して、__`text_list`__ を __実引数に記述__ した __`join` メソッド__ を呼び出すことで、__`text_list`__ の __要素を連結__ した __文字列を計算__ して、__`line_text`__ に代入する

```python
1  def is_same(self, mark, coord, dx, dy):
2      x, y = coord
3      text_list = [self.board[x + i * dx][y + i * dy] 
4                   for i in range(self.BOARD_SIZE)]
5      line_text = "".join(text_list)
6      return line_text == mark * self.BOARD_SIZE
7
8  Marubatsu.is_same = is_same
```

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

```python
def is_same(self, mark, coord, dx, dy):
    x, y = coord
    text_list = [self.board[x + i * dx][y + i * dy] 
                 for i in range(self.BOARD_SIZE)]
    line_text = "".join(text_list)
    return line_text == mark * self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

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

```diff_python
Marubatsu.is_same = is_same
def is_same(self, mark, coord, dx, dy):
    x, y = coord
-   line_text = ""
-   for _ in range(self.BOARD_SIZE):
-       line_text += self.board[x][y]
-       x += dx
-       y += dy
+   text_list = [self.board[x + i * dx][y + i * dy] 
+                for i in range(self.BOARD_SIZE)]
+   line_text = "".join(text_list)

    return line_text == mark * self.BOARD_SIZE

Marubatsu.is_same = is_same
```
</details>

下記のプログラムを実行することで、修正した `judge` のテストを行うことができます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## このアルゴリズムの利点と欠点

このアルゴリズムの __利点__ は、__条件式の記述__ が、最後の `line_text == mark * self.BOARD_SIZE` __のみ__ である点にあります。__条件式__ は、条件式の __計算結果__ によって、__処理の流れを変化させる__ ためのものなので、__条件式を記述__ すると、__記述した分だけ__ プログラムの __処理の流れが複雑になる__ からです。

__欠点__ としては、アルゴリズムで行われる __処理が直観的ではない__ 点が挙げられます。一直線上に __同じマークが並んでいる__ ことを __判定__ する際に、「全てのマスに同じマークが配置されているかどうかを調べる」、「マークが配置されているマスの数を数える」というアルゴリズムは、__直観的に分かりやすい__ と思いますが、このアルゴリズムのように「マークを表す文字列を連結し、連結した文字列とマークを並べた文字列を比較する」という方法は __正攻法ではなく__、__すこしひねった__ アルゴリズムなので、__直観的に分かりづらい__ のではないかと思います。

# 本記事のまとめ

本記事では、`judge` メソッドの中の、〇 と × の勝利を判定を行う __アルゴリズムを紹介__ しました。

下記の表は、それぞれのアルゴリズムの __特長を簡単にまとめた__ ものです。

| アルゴリズム | 利点 | 欠点 |
|:-:|:-:|:-:|
| `is_winner`<br>その 6 | あらかじめデータを作成しない<br>その 5 より見た目が少しわかりやすい|  判定をまとめて行えない |
| `is_same` その 2<br>（数える）| 並んでいるマークの数を数える必要がある場合に利用できる  | その 1 より処理に時間がかかる  |
| `is_same` その 3<br>（list と `sum`）| その 4 への布石なので特になし  | 慣れないとわかりづらい  |
| `is_same` その 4<br>（list 内包表記）  | プログラムを短く記述できる  | 慣れないとさらにわかりづらい  |
| `is_same` その 5<br>（`join`）  | 条件式が少ないので処理の流れが簡潔 | アルゴリズムが直観的ではない<br>初心者が思いつくのが難しい  |

本記事では、紹介したアルゴリズムの中で、__`is_winner`__ は __その 6__ を、__`is_same`__ は（どれでもあまり変わらないような気がしますが）__その 5__ を採用することにします。

次回の記事では、すべてのマスが埋まっていることを判定する様々なアルゴリズムを紹介します。

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/035/marubatsu_new.py

# 次回の記事

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

# 更新履歴

| 更新日時 | 更新内容 |
|:--|:--|
| 2023/12/11 | `is_winner` の仮引数の名前を `winner` から `player` に修正しました |