Pythonで〇×ゲームのAIを一から作成する　その36　すべてのマスが埋まっていることを判定するアルゴリズム

# 目次と前回の記事

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

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

# 前回までのおさらい

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

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

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

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

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

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

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

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

## 前回までのおさらい

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

# すべてのマスが埋まっていることを判定する関数の定義

下記の、現時点での `judge` メソッドでは、__すべてのマスが埋まっている__ ことを __判定する処理__ を、__if 文__ の __条件式で記述__ しているため、この処理を __簡単に修正__ することは __できません__ 。そこで、`is_winner` のような、すべてのマスが埋まっていることを __判定する__ 処理を行う __関数を定義__ します。

```python
    def judge(self):      
        # 〇 の勝利の判定
        if self.is_winner(Marubatsu.CIRCLE):
            return Marubatsu.CIRCLE
        # × の勝利の判定
        elif self.is_winner(Marubatsu.CROSS):
            return Marubatsu.CROSS   
        # 引き分けの判定
        elif not(self.board[0][0] == Marubatsu.EMPTY or \
                 self.board[1][0] == Marubatsu.EMPTY or \
                 self.board[2][0] == Marubatsu.EMPTY or \
                 self.board[0][1] == Marubatsu.EMPTY or \
                 self.board[1][1] == Marubatsu.EMPTY or \
                 self.board[2][1] == Marubatsu.EMPTY or \
                 self.board[0][2] == Marubatsu.EMPTY or \
                 self.board[1][2] == Marubatsu.EMPTY or \
                 self.board[2][2] == Marubatsu.EMPTY):
            return Marubatsu.DRAW
        # 上記のどれでもなければ決着がついていない
        else:
            return Marubatsu.PLAYING     
```

## `is_full` の定義

具体的には、以下のような __メソッドを定義__ します。

* __処理__：__すべてのマスが埋まっている__ かどうかを __判定__ する
* __名前__：__うまっている（full）__ことを判定するので、__`is_full`__ とする
* __入力__：なし
* __出力__：__すべてのマスが埋まっている__ 場合は __`True`__ を、__そうでなければ `False`__ を返す

このメソッドの定義は下記のプログラムのようになります。具体的には、`judge` メソッドの __該当する if 文の条件式__ の __計算結果__ を __return 文で返す__ 処理を行います。

```python
from marubatsu import Marubatsu

def is_full(self):
    return not(self.board[0][0] == Marubatsu.EMPTY or \
               self.board[1][0] == Marubatsu.EMPTY or \
               self.board[2][0] == Marubatsu.EMPTY or \
               self.board[0][1] == Marubatsu.EMPTY or \
               self.board[1][1] == Marubatsu.EMPTY or \
               self.board[2][1] == Marubatsu.EMPTY or \
               self.board[0][2] == Marubatsu.EMPTY or \
               self.board[1][2] == Marubatsu.EMPTY or \
               self.board[2][2] == Marubatsu.EMPTY)

Marubatsu.is_full = is_full
```

`judge` メソッドは、下記のプログラムのように修正します。具体的には、__引き分けの判定の条件式__ を __`self.is_full()` に修正__ しただけです。

```python
def judge(self):      
    # 〇 の勝利の判定
    if self.is_winner(Marubatsu.CIRCLE):
        return Marubatsu.CIRCLE
    # × の勝利の判定
    elif self.is_winner(Marubatsu.CROSS):
        return Marubatsu.CROSS   
    # 引き分けの判定
    elif self.is_full():
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING     

Marubatsu.judge = judge
```

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

```diff_python
def judge(self):      
    # 〇 の勝利の判定
    if self.is_winner(Marubatsu.CIRCLE):
        return Marubatsu.CIRCLE
    # × の勝利の判定
    elif self.is_winner(Marubatsu.CROSS):
        return Marubatsu.CROSS   
    # 引き分けの判定
-   elif not(self.board[0][0] == Marubatsu.EMPTY or \
-            self.board[1][0] == Marubatsu.EMPTY or \
-            self.board[2][0] == Marubatsu.EMPTY or \
-            self.board[0][1] == Marubatsu.EMPTY or \
-            self.board[1][1] == Marubatsu.EMPTY or \
-            self.board[2][1] == Marubatsu.EMPTY or \
-            self.board[0][2] == Marubatsu.EMPTY or \
-            self.board[1][2] == Marubatsu.EMPTY or \
-            self.board[2][2] == Marubatsu.EMPTY):
+   elif self.is_full():
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING     

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

下記のプログラムを実行することで、修正した `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
```

# `is_full` のアルゴリズム その 1 （for 文を利用する）

`is_full` で行う処理は、〇×ゲームの __すべてのマスを順番に調べ__、__すべてのマスが埋まっている__ 場合は __`True`__、__そうでない__ 場合は __`False` を返す__ という処理です。

この処理は、[前回の記事](https://qiita.com/ysgeso/items/d457f37df8671e930603#is_same-%E3%81%AE%E5%AE%9F%E8%A3%85)で定義した最初の `is_same` の __処理と同様__ なので、下記のプログラムのように __同じアルゴリズム__ で記述することができます。

* __2、3 行目__：__2 重の for 文__ によって、〇×ゲームの __すべてのマス__ に対する __繰り返し処理__ を行う
* __4、5 行目__：__(x, y)__ のマスが __埋まっていない__、すなわち __空のマスの場合__ は、すべてのマスが __埋まっていない__ ことが __確定__ するので、5 行目の __return 文__ で、__`False`__ を返す
* __7 行目__：__すべてのマスが埋まっている__ 場合は、5 行目の __return 文__ が __実行されることはない__ ので、2 ~ 5 行目の __for 文の処理__ が __必ず完了__ する。そのため、__for 文の後__ の 7 行目で __`True` を返す__

なお、元の `is_full` と大きく変わっているので、修正箇所は省略します。

```python
1  def is_full(self):
2      for y in range(self.BOARD_SIZE):
3          for x in range(self.BOARD_SIZE):
4              if self.board[x][y] == Marubatsu.EMPTY:
5                  return False
6                  
7      return True
8
9  Marubatsu.is_full = is_full
```

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

```python
def is_full(self):
    for y in range(self.BOARD_SIZE):
        for x in range(self.BOARD_SIZE):
            if self.board[x][y] == Marubatsu.EMPTY:
                return False
                
    return True

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

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

```python
test_judge()
```

:::note
上記のプログラムを、下記のプログラムのような、2 重の for 文で記述することもできます。

```python
def is_full(self):
    for col in self.board:
        for cell in col:
            if cell == Marubatsu.EMPTY:
                return False
                
    return True

Marubatsu.is_full = is_full
```

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

```diff_python
def is_full(self):
-   for y in range(self.BOARD_SIZE):
+   for col in self.board:
-       for x in range(self.BOARD_SIZE):
+       for cell in col:
-           if self.board[x][y] == Marubatsu.EMPTY:
+           if cell == Marubatsu.EMPTY:
                return False
                
    return True

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


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

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

# `is_full` のアルゴリズム その 2 （`in` 演算子を利用する）

〇×ゲームのマスの中に、__空のマスが存在するかどうか__ は、[以前の記事](https://qiita.com/ysgeso/items/1a8a4319ef3c896ef271#in-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%A8-not-in-%E6%BC%94%E7%AE%97%E5%AD%90) で説明した、__`in` 演算子__ を利用して調べることができます。`in` 演算子は、文字列型や __list__ などの、__反復可能オブジェクト__ の __要素__ に、__指定したデータ__ が __存在しているかどうか__ を __調べる__ という処理を行うメソッドで、__指定したデータ__ が __存在する__ 場合は __計算結果__ が __`True`__ に、__存在しない__ 場合は __`False`__ になります。

〇×ゲームの __ゲーム盤のデータ__ は、__`board` 属性__ の中に、__反復可能オブジェクト__ である __list__  で代入されているので、下記のプログラムのように記述すれば良いと思う人が __いるかもしれません__。

```python
def is_full(self):
    if Marubatsu.EMPTY in self.board:
        return False
    else:
        return True

Marubatsu.is_full = is_full
```

しかし、上記のように `is_full` を修正し、`test_judge` メソッドを実行すると、下記の実行結果のように、期待される返り値が `playing` になるのテストケースで __エラーメッセージが表示__ されます。

```python
test_judge()
```
実行結果
```
Start
test winner = playing

====================
test_judge error!
Turn o
...
...
...

mb.judge(): draw
winner:     playing
====================
以下略
```

このエラーは、__`in` 演算子__ の __処理__ を __勘違い__ していることが原因なので、そのことを説明します。

## `in` 演算子が行う処理の注意点

下記のプログラムのように、`board` 属性には、__2 次元配列__ を表す __list__ が代入されています。

```python
mb = Marubatsu()
print(mb.board)
```
実行結果
```
[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
```

このような場合に、下記のプログラムを実行すると、`board` 属性の __9 つの要素__ に `Marubatsu.EMPTY` の __値__ である __`"."` が代入__ されているので、__`True` が計算__ されると __思う人がいるかもしれません__ が、__実際__ には実行結果のように __`False` が計算__ されます。

```python
print(Marubatsu.EMPTY in mb.board)
```
実行結果
```
False
```

__`False` が計算__ される __原因__ は、__`Marubatsu.EMPTY in mb.board`__ が、`mb.board` の __9 つ の要素__ の中に `Marubatsu.EMPTY` が __代入されているかどうか__ を __判定__ するの __ではなく__、`mb.board` の __1 つ目のインデックス__ に __対応__ する、__`mb.board[0]`、`mb.board[1]`、`mb.board[2]`__ という、__3 つの要素の中__ に `Marubatsu.EMPTY` が __代入されているかどうか__ を __判定__ するからです。

この __3 つの要素__ にはいずれも __`['.', '.', '.']`__ という __list が代入__ されているので、__文字列__ である __`Marubatsu.EMPTY`__ が __代入__ されているとは __判定されません__。

__`mb.board[0][0]`__ のような、__2 つ目以降__ の __インデックス__ に __対応する要素__ に、`Marubatsu.EMPTY` が __代入されているかどうかを判定__ するためには、__1 次元配列__ を表す __list が代入__ された __`mb.board[0]`、`mb.board[1]`、`mb.board[2]`__ の __それぞれ__ に対して __`in` 演算子で判定__ を行う必要があります。

下記のプログラムは、__`['.', '.', '.']`__ が __代入__ された、__`mb.board[0]`__ に対して、__`in` 演算子__ で `Marubatsu.EMPTY` が __代入されているかを判定__ しているので、__`True` が計算__ されます。

```python
print(Marubatsu.EMPTY in mb.board[0])
```
実行結果
```
True
```
 
 :::note warn
 __`in` 演算子__ は、指定した値が、反復可能オブジェクトの __1 つ目のインデックス__ に __対応する要素__ に __代入されているかどうか__ を __判定__ するという処理を行う。
::: 

下記は、__`self.board`__ の __1 つ目のインデックス__ の __要素ごと__ に、__`in` 演算子__ を使って __判定を行う__ ように __`is_full` を修正__ したプログラムです。修正点は以下の通りです。

* __2 行目__：`self.board` の __1 つ目のインデックス__ は、ゲーム盤の __列__（column）を表す __list__ なので、for 文の反復可能オブジェクトに `self.board` を記述すると、繰り返しの処理のたびに、ゲーム盤の __列__ のデータが __取り出される__。取り出した __列を表す list__ を __`col`__ という変数に __代入__ する
* __3、4 行目__：__`col`__ は __1 次元配列__ を表す __list__ なので、__`in` 演算子__ を使って __列の中__ に __空のマス__ が __代入されているかどうか__ を __判定__ でき、代入されていれば __すべてのマスが埋まっていない__ ことが __確定__ するので 4 行目で __`False` を返す__
* __6 行目__：__すべての列__ に __空のマス__ が __存在しない__ 場合は、4 行目の __return 文__ は __実行されない__ ので、2 ~ 4 行目の __for 文__ の処理が __必ず完了__ する。そのため、__for 文の後__ の 6 行目で __`True` を返す__


```python
1  def is_full(self):
2      for col in self.board:
3          if Marubatsu.EMPTY in col:
4              return False
5
6      return True
7
8  Marubatsu.is_full = is_full
```

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

```python
def is_full(self):
    for col in self.board:
        if Marubatsu.EMPTY in col:
            return False

    return True

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

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

```python
test_judge()
```

# `is_full` のアルゴリズム その 3 （list の平坦化）

その 2 のアルゴリズムに似ていますが、__2 次元配列__ の list を __1 次元配列__ の list に __変換__ してから、`in` 演算子を利用するという方法があります。このような、__2 次元以上__ の配列を表す __list__ を __1 次元配列__ の __list に変換__ することを、__平坦化__（flatten）と呼びます。 

list の平坦化を行うアルゴリズムはいくつかありますが、本記事では、__2 次元配列__ を表す __list を平坦化__ する __アルゴリズム__ のうちのいくつかを紹介します。__3 次元以上__ の配列を表す list を __平坦化する場合__ は、下記のアルゴリズムを __そのまま使うことはできない__ 点に注意して下さい。

## `+=` 演算子を使うアルゴリズム

`+=` 演算子を使った、下記のアルゴリズムでゲーム盤を表す __2 次元配列の list__ を __平坦化__ できます。

* __2 行目__：__`self.board`__ を __平坦化した list__ を __代入__ する __`text_list`__ を __空の list__ で __初期化__ する
* __3 行目__：ゲーム盤の __各列__ に対する __繰り返し処理__ を、__列のデータ__ を __`col` に代入__ しながら行う
* __4 行目__：__`+=` 演算子__ を使って、__`text_list`__ に __`col`__ の __それぞれの要素__ を順番に __追加__ して __拡張__ する。__`+=` 演算子__ による __list の拡張__ については、[以前の記事](https://qiita.com/ysgeso/items/59e51d983a32ac4bc5db#-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AB%E3%82%88%E3%82%8B-list-%E3%81%AE%E7%B5%90%E5%90%88) を参照すること
* __6 行目__：__`is_full`__ は、__空のマス__ が __存在する__ 場合は __`False`__、__そうでない__ 場合は __`True` を返す__ 関数なので、`in` __ではなく__、__`not in` 演算子__ を使って、__`text_list`__ の __要素の中__ に __`Marubatsu.EMPTY`__ が __存在する__ 場合は __`False`__、__存在しない__ 場合は __`True`__ を __返す__

```python
1  def is_full(self):
2      text_list = []
3      for col in self.board:
4          text_list += col
5
6      return Marubatsu.EMPTY not in text_list
7
8  Marubatsu.is_full = is_full
```

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

```python
def is_full(self):
    text_list = []
    for col in self.board:
        text_list += col

    return Marubatsu.EMPTY not in text_list

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

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

```diff_python
def is_full(self):
+   text_list = []
    for col in self.board:
-       if Marubatsu.EMPTY in col:
-           return False
+       text_list += col

-   return True
+   return Marubatsu.EMPTY not in text_list

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

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

```python
test_judge()
```

:::note
上記のプログラムを、下記のプログラムの 4 行目のように __`+=` 演算子__ の __代わり__ に __`append` メソッド__ を使えば良いと __思った方がいるかもしれません__ が、__`append` メソッド__ の場合は例えば、__`col`__ に __`['.', '.', '.']`__ が代入されていた場合は、__この値そのもの__ が __要素として追加__ されるので __うまくいきません__。__`+=` 演算子__ であれば、`['.', '.', '.']` の __中の要素__ を __順番に取り出したもの__ が、__要素として追加__ されます。

このように、__list__ に対する __`append` メソッド__ と __`+=` 演算子__ による __処理__ は似ているように __見えて__ 、__全く異なる処理__ が行われる点に __注意__ して下さい。

```python
def is_full(self):
    text_list = []
    for col in self.board:
        text_list.append(col)

    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full
```

下記のプログラムを実行することで、上記の __`is_full`__ で行われる __処理が間違っている__ ため、実行結果に __エラーメッセージが表示__ されます。

```python
test_judge()
```
実行結果
```
Start
test winner = playing

====================
test_judge error!
Turn o
...
...
...

mb.judge(): draw
winner:     playing
====================
以下略
```
:::

## `append` メソッドを使うアルゴリズム

__`append` メソッドを利用__ したい場合は、下記のプログラムのように __2 重の for 文__ による __繰り返し処理の中__ で、それぞれの __マスを表す要素__ を __`append` メソッドで追加__ します。

```python
def is_full(self):
    text_list = []
    for col in self.board:
        for cell in col:
            text_list.append(cell)

    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full
```

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

```diff_python
def is_full(self):
    text_list = []
    for col in self.board:
-       text_list.append(col)
+       for cell in col:
+           text_list.append(cell)

    return Marubatsu.EMPTY not in text_list

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

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

```python
test_judge()
```

## list 内包表記を使ったアルゴリズム

__for 文__ と __`append`__ を使って __list を作成__ するプログラムは、__list 内包表記__ を使って __記述__ することが __できる__ ので、上記のプログラムは __list 内包表記__ を使って、記述することができます。

### 入れ子になった for 文に対する list 内包表記

上記の __2 つ__ の __入れ子__ になった __for 文__ で記述されたプログラムは、__list 内包表記__ の中に __2 つ__ の __for と in を記述__ することで、下記のプログラムのように記述することができます。

```python
text_list = [cell for col in self.board for cell in col]
```

一見すると、list 内包表記への __変換__ は __難しそうに思える__ かもしれませんが、元となった下記のプログラムの __for 文の部分__ を __そのままの順番__ に __並べれば良いだけ__ なので __変換の手順__ は __簡単__ です。

```python
text_list = []
for col in self.board:
    for cell in col:
        text_list.append(cell)
```

分かりづらいと思った方は、下記のような、上記のプログラムの 2 行目の __末尾の `:`__ を __削除__ し、その __直後__ に __3 行目を並べた__ プログラムを考えてみて下さい。

なお、下記のプログラムは、入れ子になった for 文を list 内包表記へ __変換する手順__ を __わかりやすく説明__ するためのもので、__文法的__ には __間違っている__ ので実行すると __エラーが発生__ します。

```python
text_list = []
for col in self.board for cell in col:
    text_list.append(cell)
```

上記の 2 行目のプログラムを、__1 つの for 文__ として __考えて__ list 内包表記に __変換__ すると、先程説明した、下記のようなプログラムになります。

```python
text_list = [cell for col in self.board for cell in col]
```

上記の事から、`is_full` を __list 内包表記__ を使って下記のプログラムのように記述できます。

```python
def is_full(self):
    text_list = [cell for col in self.board for cell in col]
    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full
```

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

```diff_python
def is_full(self):
-   text_list = []
-   for col in self.board:
-      for cell in col:
-          text_list.append(cell)
+   text_list = [cell for col in self.board for cell in col]
    return Marubatsu.EMPTY not in text_list

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

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

```python
test_judge()
```

:::note
具体例は示しませんが、__3 つ以上__ の for 文が __入れ子__ になっている場合も、__同様の手順__ で __list 内包表記__ に __変換__ できるので、この手順で __3 次元以上__ の配列を表す list を __平坦化__ できます。
:::

### 間違った list 内包表記の記述

:::note alert
__入れ子__ になった __for 文__ で記述されたプログラムを、__list 内包表記__ に変換する際に、下記のように考えて変換する人がいるかもしれませんが、この __考え方__ は __間違っています__。

実際に、筆者も最初は list 内包表記へ変換する手順を、下記のような、__間違った考え方__ で理解していました。なお、下記の手順のうち、__背景が白い部分__ の考え方は __間違っていません__。
:::

* list 内包表記は、下記のように記述する。

```python
[式 for 変数 in 反復可能オブジェクト]
```
* 下記のプログラムでは、__`self.board` から__ 順番に __取り出した値__ を __`col` に代入__ し、その __`col` から__ 順番に __取り出した値__ を __`cell` に代入__ するという、__繰り返しの処理__ が行われる。

```python
text_list = []
for col in self.board:
    for cell in col:
        text_list.append(cell)
```

* __`self.board` から__ 順番に __取り出した値__ を __`col` に代入__ し、その __`col` を要素__ とする __list 内包表記__ は、下記のプログラムのように記述する。

```python
[col for col in self.board]
```


* __`col` から__ 順番に __取り出した値__ を __`cell` に代入__ し、その __`cell` を要素__ とする __list 内包表記__ は、下記のように記述する。

```python
[cell for cell in col]
```

:::note alert
* 上記の 2 つを __組み合わせる__ と以下のように記述できる。

```python
[cell for cell in col for col in self.board]
```

正しいように __思える__ かもしれませんが、この部分が __勘違い__ であり、__間違って__ います。
:::

下記のプログラムのように `is_full` を修正して `test_judge` を実行すると、__エラーが発生__ します。

```python
def is_full(self):
    text_list = [cell for cell in col for col in self.board ]
    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full

test_judge()
```
実行結果
```
略
c:\Users\ys\ai\marubatsu\036\marubatsu.ipynb セル 23 line 2
      1 def is_full(self):
----> 2     text_list = [cell for cell in col for col in self.board ]
      3     return Marubatsu.EMPTY not in text_list

NameError: name 'col' is not defined
```

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

* __NameError__
名前（name）に関するエラー
* __name 'col' is not defined__
`col` という名前（name）は定義（define）されていない（is not）
:::

エラーメッセージに「__`col`__ という __名前__ が __定義されていない__」と表示されるのは、list 内包表記の中の __`for cell in col for col in self.board`__ の部分が、__先頭から順番__ に __`for cell in col`__、__`for col in self.board`__ の __順番で実行__ されるからです。

そのため、__最初__ に __`for cell in col`__ を __実行__ しようとした際に、__`col`__ という __名前の変数__ には、一度も __値が代入されていない__ ので __名前解決が失敗__ するため、上記の __エラーが発生__ します。

## `sum` を使うアルゴリズム

組み込み関数 __`sum`__ は、__2 つ目の実引数__ を記述することで、__合計を計算__ する際の __初期値を設定__ することができます。`sum` の __2 つ目の仮引数__ は __`start`__ という名前の __デフォルト引数__ になっており、__そのデフォルト値__ には __`0`__ が設定されています。

参考までに、`sum` の公式ドキュメントへのリンクを再掲します。

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

__[前回の記事](https://qiita.com/ysgeso/items/a97a3cdf54087e662230#sum-%E3%81%AB%E9%96%A2%E3%81%99%E3%82%8B%E6%B3%A8%E6%84%8F%E7%82%B9)__ では、__`start`__ を __考慮しない__ `sum` の __疑似的な定義__ を紹介しましたが、__`start` を考慮に入れた場合__ の `sum` 関数の __定義__ は、__おそらく__ 下記のようなプログラムになっていると __推測されます__。

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

__2 つ目__ の __`start`__  に対応する __実引数を省略__ した場合は、__`start`__ には __`0` が代入__ されるので、__`sum`__ は __数値型の要素__ を持つ __反復可能オブジェクト__ の __要素の合計__ を __計算__ します。

一方、下記のプログラムのように、__2 つ目__ の __`start`__  に対応する __実引数__ に __空の list__ を記述した場合は、実行結果からわかるように、`sum` は __list を要素__ として持つ __反復可能オブジェクト__ の __要素を結合__ した __list を計算__ するという処理を行います。

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

下記は、上記の __`pseudo_sum` の定義__ と、先程紹介した __`+=` 演算子を使った__ アルゴリズムの __`if_full`__ の __対応する部分__ を __抜粋__ して __並べた__ プログラムです。

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

```python
def is_full(self):
    text_list = []
    for col in self.board:
        text_list += col
    略
```

上記を見比べることで、下記のプログラムのように、__`is_full`__ の __2 ~ 4 行目__ のプログラムを __`sum(self.board, start=[])`__ で置き換えることができることがわかります。


```python
def is_full(self):
    text_list = sum(self.board, start=[])
    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full
```

<details><summary><strong>修正箇所（<code>+=</code> を使ったアルゴリズムからの修正です）</strong></summary>

```diff_python
def is_full(self):
-   text_list = []
-   for col in self.board:
-       text_list += col
+   text_list = sum(self.board, start=[])
    return Marubatsu.EMPTY not in text_list

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

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

```python
test_judge()
```

このように、__`sum` の使い方__ を知っていれば、__`is_full`__  を __簡潔に記述__ することができます。

:::note
__このアルゴリズム__ で、__3 次元以上__ の配列を表す __list を平坦化__ することは __できません__。
:::

## `sum` と `pseudo_sum` の違いの補足

先程記述した __`pseudo_sum` の定義__ は、__`sum` の仕様__ から筆者がその定義を __推測__ して __記述__ したものなので、__実際__ の __`sum` の 定義__ とは __異なります__。例えば、__`pseudo_sum`__ の場合は、下記のプログラムのように、__実引数__ に反復可能オブジェクトである __文字列型__ のデータと、__`start`__ に対応する __実引数__ に __空文字列__ を記述して呼び出しても __エラーは発生しません__。

```python
print(pseudo_sum("123", start=""))
```
実行結果
```
123
```

一方、__`sum`__ の場合は、下記のプログラムのように、__同じ実引数__ を記述して呼び出すと __エラーが発生__ します。先ほど紹介した `sum` の[公式ドキュメント](https://docs.python.org/ja/3/library/functions.html?highlight=sum#sum)には、「__start の値は文字列であってはなりません__」と記述されているので、このエラーの __原因__ は、`sum` が __そのように定義__ されているからです。

:::note
公式ドキュメントに記述されていますが、`start` に __文字列を指定できない理由__ は、__`join` メソッド__ を利用したほうが、__文字列の結合__ を __高速に実行できる__ からのようです。
:::

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

TypeError: sum() can't sum strings [use ''.join(seq) instead]
```

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

* __TypeError__
データ型（Type）に関するエラー
* __sum() can't sum strings [use ''.join(seq) instead]__
`sum` は、文字列型（strings）のデータの合計（sum）を計算できない（can't）。代わり（instead） `''.join(seq)` を使うこと（use）
:::

`pseudo_sum` のように、__組み込み関数__ と __同じような処理__ を行う __関数__ を __自分で定義__ する事は __可能__ ですが、一般的には以下のような理由で、__組み込み関数__ を利用すべきでしょう。

* __組み込み関数__ は __テスト__ がしっかり __行われている__ ので、__バグが存在しない__ と考えて良い
* __組み込み関数__ のほうが、一般的に自分で定義した関数よりも __高速に処理__ を行うことができる


# `is_full` のアルゴリズム その 4 （`join` メソッドの利用）

少々 __トリッキー__ ですが、__`join` メソッド__ を利用することで、`board` 属性の __各マス__ の __文字列を連結__ し、__`in` 演算子__ を使って __その中__ に __`Marubatsu.EMPTY`__ が __存在するかどうか__ を __判定__ するというアルゴリズムがあります。下記は、そのアルゴリズムを使って、〇×ゲームの開始直後のゲーム盤に、空のマスが存在するかどうかを判定するプログラムです。

* __2 行目__：それぞれの __列__（column）の __文字列を連結__ した文字列を __要素__ とする __list を代入__ する __`col_text_list`__ を __空の list__ で __初期化__ する
* __3 行目__：ゲーム盤の __各列__ に対する __繰り返し処理__ を、__列のデータ__ を __`col` に代入__ しながら行う
* __4 行目__：__`col` に代入__ されている、__列の各マス__ の文字列を __要素__ として持つ __1 次元配列 の list__ を、__`join` メソッド__ によって __連結__ し、__`col_text`__ に __代入__ する
* __5 行目__：__`col_text`__ を __`col_text_list`__ の __要素__ として __追加__ する
* __6 行目__：__繰り返し処理が終了__ した時点で、__`col_text_list`__ に、__各列__ のマスの __文字列を連結__ した __要素__ を持つ __1 次元配列の list__ が __代入__ されることを、`print` で __表示__ して __確認__ できるようにする
* __7 行目__：__`col_text_list`__ を __`join` メソッド__ によって __連結__ し、__`board_text` に代入__ する
* __8 行目__：__`board_text`__ に、ゲーム盤の __すべてのマス__ を表す __文字列が連結__ された文字列が __代入__ されていることを `print` で __表示__ して __確認__ できるようにする
* __9 行目__：__`board_text`__ に __代入__ されている __文字列__ は、__反復可能オブジェクト__ なので、__`in` 演算子__ を使って、__その中__ に __`Marubatsu.EMPTY`__ という __文字列があるかどうか__ を確認する

実行結果から、以下のことが確認できます。
* __1 行目__：__各列__ の __マスの文字列__ を __連結__ した __要素__ を持つ __list__ が __`col_text_list`__ に __代入__ されている
* __2 用目__：ゲーム盤の __すべてのマス__ の文字列を __連結した文字列__ が __`board_text`__ に __代入__ されている
* __3 行目__：ゲーム盤のマスに __空のマスが存在する__ ことを表わす `True` が計算されている

```python
1  mb = Marubatsu()
2  col_text_list = []
3  for col in mb.board:
4      col_text = "".join(col)
5      col_text_list.append(col_text)
6  print(col_text_list)
7  board_text = "".join(col_text_list)
8  print(board_text)
9  print(Marubatsu.EMPTY in board_text)
```

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

```python
mb = Marubatsu()
col_text_list = []
for col in mb.board:
    col_text_list.append("".join(col))
print(col_text_list)
board_text = "".join(col_text_list)
print(board_text)
print(Marubatsu.EMPTY in board_text)
```
</details>

実行結果
```
['...', '...', '...']
.........
True
```

下記は、上記のプログラムを使って `is_full` を修正したプログラムです。

* __2 行目__：上記のプログラムの、__2 ~ 5 行目__ を、__list 内包表記__ を使って簡略化したプログラム
* __4 行目__：__`not in` 演算子__ を使って、__`board_text`__ の中に __`Marubatsu.EMPTY`__ が __存在する__ 場合は __`False`__、__存在しない__ 場合は __`True`__ を __返す__

```python
1  def is_full(self):
2      col_text_list = ["".join(col) for col in self.board]
3      board_text = "".join(col_text_list)
4      return Marubatsu.EMPTY not in board_text
5
6  Marubatsu.is_full = is_full
```

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

```python
def is_full(self):
    col_text_list = ["".join(col) for col in self.board]
    board_text = "".join(col_text_list)
    return Marubatsu.EMPTY not in board_text

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

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

```python
test_judge()
```

:::note
`is_full` は、下記のプログラムのように __さらに簡略化__ することもできますが、__わかりづらい__ のでこのように記述することは __お勧めしません__。

```python
def is_full(self):
    return Marubatsu.EMPTY not in "".join(["".join(col) for col in self.board])

Marubatsu.is_full = is_full
```

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

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

# `is_full` のアルゴリズム その 5 （着手の数を数える）

最後に、これまでとは __全く異なる観点__ で `is_full` の処理を行うアルゴリズムを紹介します。

〇× ゲームは、__一回の着手__ で、__必ず 1 つのマス__ に __マークを配置__ するので、__すべてのマスが埋まった時__ は、必ず __マスの総数__ と同じ、__9 回の着手__ が行われることになります。

従って、__`move` メソッド__ で着手を行う際に、__着手を行った数__ を __数えておけば__、__その数__ が __9 であるかどうか__ で __すべてのマスが埋まっているかどうか__ を __判定__ することができます。

__着手を行った数__ を __数える__ ためには、そのための __属性を用意__ する必要があります。プログラムに __新しい変数__ や __属性__ を __追加__ する場合は、その変数や属性の __名前__、__初期化処理__、__更新処理__、__利用方法__ について __考える__ 必要があります。

* __属性の名前__：__着手__（move）の回数を __数える__（count）ので、__`move_count`__ という名前にする
* __初期化処理__：`move_count` は、着手したマスの数を数えるための属性なので、__ゲームの開始時__ に __`0` で初期化__ する必要がある。`Marubatsu` クラスでは、__`restart` メソッド__ で __ゲームが再起動__ されるので、下記のプログラムの 4 行目のように、__`restart` メソッドの中__ で __初期化処理__ を行う

```python
def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    
Marubatsu.restart = restart
```

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

```diff_python
def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
+   self.move_count = 0
    
Marubatsu.restart = restart
```
</details>


* __更新処理__：`move_count` は、__着手が行われた時__ にその数を __1 つ増やす__ 処理を行う必要があるので、下記のプログラムのように、着手を行う __`move` メソッド__ の中に __その処理を追加__ する

```python
def move(self, x: int, y: int):
    if self.place_mark(x, y, self.turn):
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        
Marubatsu.move = move
```

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

```diff_python
def move(self, x: int, y: int):
    if self.place_mark(x, y, self.turn):
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
+       self.move_count += 1
        
Marubatsu.move = move
```
</details>


* __利用__：`move_count` は、__すべてのマスが埋まっているかどうか__ の __判定に使う__ ので、__`is_full`__ を下記のように __修正__ する。ゲーム盤の __マスの総数__ は、ゲーム盤の __サイズの 2 乗__ なので、その数を __べき乗__ を計算する __`**` 演算子__ を使って、__`self.BOARD_SIZE ** 2`__ のように記述して計算する

```python
def is_full(self):
    return self.move_count == self.BOARD_SIZE ** 2

Marubatsu.is_full = is_full
```

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

```python
test_judge()
```

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

このアルゴリズムの利点は、`is_full` の判定が __シンプル__ で __分かりやすくなる__ 点です。また、__判定__ で行う __処理__ が __1 つの条件式__ の計算 __だけで済む__ ので、他の `is_full` のアルゴリズムと比較して __高速に処理を行う__ ことができます。

欠点は、__新しい__ `move_count` という __属性を用意__ し、__`is_full` 以外の場所__ に __いくつかプログラムを追加する__ 必要がある点と、__初心者__ にとってはこの方法を __思いつくことが難しい__ ことでしょう。

# 本記事のまとめ

本記事では、すべてのマスが埋まっていることを判定する __さまざまなアルゴリズムを紹介__ しました。下記の表は、それぞれのアルゴリズムの __特長を簡単にまとめた__ ものです。

| アルゴリズム | 利点 | 欠点 |
|:-:|:-:|:-:|
| 修正前 | 初心者でも記述できる  | 記述が長い<br>入力ミスをしやすい |
| その 1<br>（for 文）| 短く記述できる  |  |
| その 2<br>（`in` 演算子）| ぞの 1 よりさらに短く記述できる  | `in` 演算子は 2 次元以上配列を表す list の場合は注意が必要 |
| その 3<br>（平坦化）| その 2 よりさらに短く記述できる  | `+=` と `append` の違いを理解する必要がある<br>`sum` の詳しい使い方を知っている必要がある |
| その 4<br>（`join`）| 短く記述できる  | 初心者が思いつくのが難しい |
| その 5<br>（着手を数える）| 最も短く記述できる<br>最もわかりやすく記述できる<br>処理が高速  | 新しい属性が必要<br>`is_full` 以外の場所にプログラムを追加する必要がある<br>初心者が思いつくのが難しい |


本記事では __その 5__ のアルゴリズムを採用することにします。

実は、これまでに紹介した `judge` メソッドのアルゴリズムには、__実行速度の面など__ で __改良の余地__ があります。ただし、〇×ゲームを __遊ぶだけ__ であれば __実行速度__ は __大きな問題にはならない__ ので、実行速度が __大きな問題__ になる __AI を作成する際__ に、__さらなる改良__ について紹介することにします。

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

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

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

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

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

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

https://github.com/ysgeso/marubatsu/blob/master/034/test_new.py

# 次回の記事

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