Pythonで〇×ゲームのAIを一から作成する　その33　引き分けの判定に対するテストと組み合わせ網羅テスト

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/24a604d82249f61e199d

# 実装の進捗状況と前回までのおさらい

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

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

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

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

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

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

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

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

## 前回までのおさらい

前回の記事では、× の勝利を判定する if 文の MC/DC のテストを行い、`test_judge` メソッドの改良を行いました。今回の記事では、残りのテスト行います。

# 改良条件判断網羅(MC/DC)によるテストの続き

次は、残りの __引き分けを判定__ する if 文の [MC/DC](https://qiita.com/ysgeso/items/728cee8982fe0ed9da38#%E6%94%B9%E8%89%AF%E6%9D%A1%E4%BB%B6%E5%88%A4%E6%96%AD%E7%B6%B2%E7%BE%85modified-condition--dicision-coverage) の __テスト__ を行います。

## 引き分けの場合のテストケース

下記は、`judge` メソッドの中で、__引き分けの判定__ を行う __if 文__ です。

```python
        # 引き分けの判定
        if 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[1][1] == Marubatsu.EMPTY or \
            self.board[0][2] == Marubatsu.EMPTY or \
            self.board[1][2] == Marubatsu.EMPTY or \
            self.board[2][2] == Marubatsu.EMPTY):
            winner = Marubatsu.DRAW 
```

__他の 2 つ__ の if 文と __異なり__、この if 文の __条件式__ には __not 演算子__ が記述されています。この条件式のように、__or 演算子のみ__ で __連結__ された式に対して、__not 演算子__ で __`True` と `False`__ を __反転__ した式は、__and 演算子のみ__ で __連結__ された式に __変換__ することができます。

### ド・モルガンの法則

具体的には、下記の __1 行目の式__ と、__2 行目の式__ の計算結果は、__常に同じ__ になります。このような法則の事を「__ド・モルガンの法則__」と呼びます。

```python
not(a or b or c)
(not a) and (not b) and (not c)
```

分かりにくいかもしれませんが、このことを __言葉で説明__ すると以下のようになります。

__`not(a or b or c)`__ が __`True`__ になる __場合__ は、__`a or b or c`__ が __`False`__ になります。これは、__`a`、`b`、`c`__ が __すべて `False`__ である __場合だけ__ なので、その場合は、__`not a`、`not b`、`not c`__ は __すべて `True`__ になります。従って、__`(not a) and (not b) and (not c)`__ も __`True`__ になります。

__`not(a or b or c)`__ が __`False`__ になる __場合__ は、__`a or b or c`__ が __`True`__ になります。この場合は、__`a`、`b`、`c`__ の __いずれか 1 つ以上__ が __`True`__ になるので、__`not a`、`not b`、`not c`__ の __いずれか 1 つ以上__ が __必ず `False`__ になります。従って、__`(not a) and (not b) and (not c)`__ も __`False`__ になります。

上記の事から、__`not(a or b or c)`__ と __`(not a) and (not b) and (not c)`__ の計算結果は __常に等しい__ ことになります。なお、上記では、__or 演算子__ で __連結__ する式は `a`、`b`、`c` の __3 つ__ ですが、__式の数__ が __いくつであっても__ この __法則は成り立ちます__。

図で説明すると以下のようになります。

下図の黄色い部分が、__`a or b or c`__、外側の水色の部分が __`not(a or b or c)`__ を表します。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/dce680fe-ec98-819b-5510-bf05b20c5664.png" width="200">

下図のオレンジ色の部分がそれぞれ __`not a`、`not b`、`not c`__ を表します。__`(not a) and (not b) and (not c)`__ は、下の 3 つの図の __すべて__ で __オレンジ色__ になっている部分なので、それは上図の水色の部分の __`not(a or b or c)`__ と __等しい__ ことがわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/12435cc1-e80b-9cc8-b372-8c3077c6ee6f.png" width="600">


参考までに、ド・モルガンの法則の法則の wikipedia へのリンクを下記に記します。

https://ja.wikipedia.org/wiki/%E3%83%89%E3%83%BB%E3%83%A2%E3%83%AB%E3%82%AC%E3%83%B3%E3%81%AE%E6%B3%95%E5%89%87

__`not(self.board[0][0] == Marubatsu.EMPTY)`__ は、__`self.board[0][0] != Marubatsu.EMPTY`__ と __同じ意味__ を持つので、引き分けを判定する if 文の __条件式__ は、__ド・モルガンの法則__ を __利用__ することで、下記のプログラムのように __書き換える__ ことができます。

```python
        # 引き分けの判定
        if self.board[0][0] != Marubatsu.EMPTY and \
           self.board[1][0] != Marubatsu.EMPTY and \
           self.board[2][0] != Marubatsu.EMPTY and \
           self.board[0][1] != Marubatsu.EMPTY and \
           self.board[1][1] != Marubatsu.EMPTY and \
           self.board[1][1] != Marubatsu.EMPTY and \
           self.board[0][2] != Marubatsu.EMPTY and \
           self.board[1][2] != Marubatsu.EMPTY and \
           self.board[2][2] != Marubatsu.EMPTY:
            winner = Marubatsu.DRAW 
```

[以前の記事](https://qiita.com/ysgeso/items/728cee8982fe0ed9da38#and-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E3%81%BF%E3%81%A7%E9%80%A3%E7%B5%90%E3%81%95%E3%82%8C%E3%81%9F%E5%A0%B4%E5%90%88) で説明したように、__and 演算子のみ__ で __連結__ された __条件式__ に対する __MC/DC__ の __テストケース__ として、__下記の性質を満たす__ ようなテストケースが必要になります。

* __and 演算子__ で __連結__ された __式__ の計算結果が __すべて `True` になる__ テストケース
* __and 演算子__ で __連結__ された __式__ の計算結果のうち、__1 つだけ__ が __`False` になる__ テストケース

なお、`judge` メソッドの引き分けを判定する if 文の条件式を上記のように __書き換えた理由__ は、__MC/DC のテスト__ を行うための __テストケース__ を __簡単に求める__ ことができるようにするためです。

従って、この条件式を、__実際__ に上記のように __修正__ する __必要はありません__。修正前と、修正後の条件式は、いずれも __同じ計算__ を行うので、__分かりやすいと思った__ ほうを __採用__ して下さい。本記事では、修正せずに、元の条件式を採用することにします。

### すべて `True` になる テストケース

__修正後__ の __条件式__ で、__すべてが `True`__ になるのは、__すべて__ のマスが __空でない__ 場合です。従って、__すべてのマス__ に何らかの __マークが配置__ された __テストケースを用意__ すれば良いことがわかります。

__すべてのマス__ に __マークが配置__ されたテストケースは、__かなりの種類__ がありますが、__MC/DC のテスト__ では、そのような __条件を満たす__ テストケースを __1 つだけ用意__ すれば良いので、__命令網羅(C0)__ のテストを行った際に __[作成](https://qiita.com/ysgeso/items/273ed49a00b90c753031#%E5%BC%95%E3%81%8D%E5%88%86%E3%81%91%E3%81%AE%E5%A0%B4%E5%90%88%E3%81%AE%E3%83%86%E3%82%B9%E3%83%88)__ した、下図のテストケースを用意することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/9c9bdc10-1f9d-9c10-bfc0-fc5041becb2c.png" width="250">

:::note
上図以外のテストケースを用意したい人は、__8 手目まで__ で __〇 か × が勝利__ すると、そこで __ゲームが終了__ してしまうため、__8 手目まで__ で __決着がつかないよう__ に 9 つの __着手を行う__ 必要がある点に注意して下さい。
:::

上記のテストケースに対する __`judge` メソッド__ の __期待される返り値__ は、__〇 も × も__ 3 つ __並んでいない__ ので、下図の __フローチャート__ から、__`Marubatsu.DRAW`__ である事がわかります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/f6aed8fb-6397-3878-6c3f-6baac0e9829a.png" width="500">

下記は、上記のテストケースを記述したプログラムです。

```python
from marubatsu import Marubatsu

testcases = {
    # 引き分けの場合のテストケース
    Marubatsu.DRAW: [
        "A1,A2,B1,B2,C2,C1,A3,B3,C3",
    ],  
}
```

上記のテストケースに対して、実引数に __`debug=True` を記述__ して `test_judge` を実行します。

```python
from test import test_judge

test_judge(testcases, debug=True)
```
実行結果
```
Start
test winner = draw
Turn x
oox
xxo
oxo

o
Finished
```

実行結果の __ゲーム盤の表示__ から、テストケースによって __正しいマスにマークが配置__ されることが __確認__ できます。また、__エラーメッセージ__ が __表示されない__ ので、このテストケースに対して、__`mb.judge()`__ が __期待される返り値を返す__ ことが __確認__ できます。

### 1 つだけが `False` になる テストケース

__修正後__ の __引き分けを判定__ する if 文の __条件式__ の中の __1 つだけ__ が __`False` になる__ テストケースでは、9 つのマスのうち、__1 つのマスだけが空__ になるので、全部で __9 つ__ のテストケースが __必要__ になることがわかります。__MC/DC のテスト__ では、そのような __条件を満たす__ 場合は __どのようなテストケース__ でも __構わない__ ので、先程と同様に、__7 手目まで__ で __ゲームが終了しない__ ように気を付けて、__下図__ のテストケースを __用意__ することにします。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/303456b9-0c65-1a8a-b9b7-01e06848a0fa.png" width="300">


上図は、いずれも __決着がついていない__ 状態なので、__`judge`__ メソッドの __期待される返り値__ は、いずれも __`Marubatsu.PLAYING`__ になります。

:::note
__決着がついている__ 状態のテストケースを __用意__ しても __かまいません__ が、その場合は、__期待される返り値__ が何になるかを __考えて__ テストケースを __記述__ する必要があります。
:::

下記は、上図のテストケースを記述したプログラムです。

```python
testcases = {
    # 1 つだけマークが配置されていない場合のテストケース
    Marubatsu.PLAYING: [
        "C3,A2,B1,B2,C2,C1,A3,B3",
        "A1,A2,C3,B2,C2,C1,A3,B3",
        "A1,A2,B1,B2,C2,C3,A3,B3",
        "A1,C3,B1,B2,C2,C1,A3,B3",
        "A1,A2,B1,C3,C2,C1,A3,B3",
        "A1,A2,B1,B2,C3,C1,A3,B3",
        "A1,A2,B1,B2,C2,C1,C3,B3",
        "A1,A2,B1,B2,A3,C1,C2,C3",
        "A1,A2,B1,B2,C2,C1,A3,B3",
    ],  
}
```

上記のテストケースに対して、実引数に __`debug=True`__ を記述して `test_judge` を実行します。

```python
test_judge(testcases, debug=True)
```
実行結果
```
Start
test winner = playing
Turn o
.ox
xxo
oxo

oTurn o
o.x
xxo
oxo

oTurn o
oo.
xxo
oxx

oTurn o
oox
.xo
oxx

oTurn o
oox
x.o
oxx

oTurn o
oox
xx.
oxo


====================
test_judge error!
Turn o
oox
xx.
oxo

mb.judge(): draw
winner:     playing
====================
Turn o
oox
xxo
.xo

oTurn o
oox
xxo
o.x

oTurn o
oox
xxo
ox.

o
Finished
```

実行結果の __ゲーム盤の表示__ から、テストケースによって __正しいマスにマークが配置__ されることが __確認__ できます[^1]。一方、__(2, 1) のマス__ に __マークを配置しない__ テストケースで、__エラーメッセージが表示__ されます。エラーメッセージのうち、__`winner` が `"playing"`__ なのは __正しい__ ので、__`mb.judge()`__ の __返り値__ が __`"draw"`__ になっている点が __おかしいこと__ がわかります。

そのことを念頭に置いて `judge` メソッドの __引き分けを判定__ する if 文の __条件式__ を __調べてみる__ と、__(2, 1) のマス__ が __空__ であること __判定__ する下記の 7 行目の式が __`self.board[1][1] == Marubatsu.EMPTY`__ のように、__(1, 1) のマスを判定__ するようになっていることがわかります。

```python
 1        # 引き分けの判定
 2        if not(self.board[0][0] == Marubatsu.EMPTY or \
 3            self.board[1][0] == Marubatsu.EMPTY or \
 4            self.board[2][0] == Marubatsu.EMPTY or \
 5            self.board[0][1] == Marubatsu.EMPTY or \
 6            self.board[1][1] == Marubatsu.EMPTY or \
 7            self.board[1][1] == Marubatsu.EMPTY or \ # この行が間違っている
 8            self.board[0][2] == Marubatsu.EMPTY or \
 9            self.board[1][2] == Marubatsu.EMPTY or \
10            self.board[2][2] == Marubatsu.EMPTY):
11            winner = Marubatsu.DRAW
```

従って、その部分を、下記のプログラムのように __修正すれば良い__ ことがわかります。

```python
        # 引き分けの判定
        if 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 \ # [2][1] に修正する
            self.board[0][2] == Marubatsu.EMPTY or \
            self.board[1][2] == Marubatsu.EMPTY or \
            self.board[2][2] == Marubatsu.EMPTY):
            winner = Marubatsu.DRAW
```

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

```diff_python
        # 引き分けの判定
        if 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[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):
            winner = Marubatsu.DRAW
```
</details>

長くなるので省略しますが、`judge` メソッドを上記のように __修正後__ に、下記のプログラムを実行することで、修正後の `judge` メソッドで __期待された返り値が返されること__ が __確認__ できます。

なお、テストケースによってゲーム盤に __正しくマスが配置されるかどうか__ は、先程 __確認済__ なので、`test_judge` の実引数に __`debug=True`__ を __記述__ する __必要はありません__。

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

これが、`judge` メソッドの、3 つあるバグの中の __2 つ目のバグ__ で、このバグも 1 つ目のバグと __同様__ に、__データの入力ミス__ が __原因__ となるバグです。

これで、`judge` メソッドの __2 つ目__ の __バグ__ を __発見__ して __修正__ することができました。

### `test_judge` の修正

気づいていない人が多いかもしれませんが、先程の __`test_judge(testcases, debug=True)`__ の __実行結果__ の __表示__ には、少し __おかしな所__ があります。それが何かを考えてみて下さい。

ヒント：おかしな点は、下記の中にあります。

```
Start
test winner = playing
Turn o
.ox
xxo
oxo

oTurn o
略
```

よく見ると、上記の「略」のすぐ上の行に、__`oTurn o`__ という、おかしな表示が行われています。

この、`Turn` の __直前__ の __`"o"`__ は、`judge` メソッドが __期待された返り値を返した__ 時に、__`print("o", end="")`__ によって __表示__ されたものです。__`debug=True`__ の場合は、__`"o"` の後__ で __次の__ テストケースの __ゲーム盤を表示__ するので、__`"o"` の後__ で __改行を行う__ 必要があります。また、その場合は、`"o"` のように __短く表示__ する __必要はない__ ので、__元の `"ok"` を表示__ したほうが __わかりやすい__ でしょう。下記のプログラムはそのように修正したプログラムです。

修正箇所は 14 ~ 17 行目で、__`md.judge()`__ が __期待された返り値を返した際__ に、__`debug` が `True`__ の場合は、__`"ok"`__ を、__そうでなければ__、__`"o"`__ を __改行せず__ に __表示__ するように修正しています。

```python
 1  def test_judge(testcases, debug=False):
 2      print("Start")
 3      for winner, testdata_list in testcases.items():
 4          print("test winner =", winner) 
 5          for testdata in testdata_list:
 6              mb = Marubatsu()
 7              for coord in [] if testdata == "" else testdata.split(","):
 8                  x, y = excel_to_xy(coord)            
 9                  mb.move(x, y)
10              if debug:
11                  print(mb)
12
13              if mb.judge() == winner:
14                  if debug:
15                      print("ok")
16                  else:
17                      print("o", end="")
18              else:
19                  print()
20                  print("====================")
21                  print("test_judge error!")
22                  print(mb)
23                  print("mb.judge():", mb.judge())
24                  print("winner:    ", winner)
25                  print("====================")
26          print()
27      print("Finished")
```

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

```python
def test_judge(testcases, debug=False):
    print("Start")
    for winner, testdata_list in testcases.items():
        print("test winner =", winner) 
        for testdata in testdata_list:
            mb = Marubatsu()
            for coord in [] if testdata == "" else testdata.split(","):
                x, y = excel_to_xy(coord)            
                mb.move(x, y)
            if debug:
                print(mb)

            if mb.judge() == winner:
                if debug:
                    print("ok")
                else:
                    print("o", end="")
            else:
                print()
                print("====================")
                print("test_judge error!")
                print(mb)
                print("mb.judge():", mb.judge())
                print("winner:    ", winner)
                print("====================")
        print()
    print("Finished")
```
</details>

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

```diff_python
def test_judge(testcases, debug=False):
    print("Start")
    for winner, testdata_list in testcases.items():
        print("test winner =", winner) 
        for testdata in testdata_list:
            mb = Marubatsu()
            for coord in [] if testdata == "" else testdata.split(","):
                x, y = excel_to_xy(coord)            
                mb.move(x, y)
            if debug:
                print(mb)

            if mb.judge() == winner:
-               print("o", end="")
+               if debug:
+                   print("ok")
+               else:
+                   print("o", end="")
            else:
                print()
                print("====================")
                print("test_judge error!")
                print(mb)
                print("mb.judge():", mb.judge())
                print("winner:    ", winner)
                print("====================")
        print()
    print("Finished")
```
</details>

修正後に、`test_judge(testcases, debug=True)` を実行することで、下記の実行結果のように、おかしな部分の __表示が修正__ されたことが確認できます。

```python
test_judge(testcases, debug=True)
```
実行結果
```
Start
test winner = playing
Turn o
.ox
xxo
oxo

ok
Turn o
略
```

### MC/DC のテストをまとめて行う

__MC/DC のテスト__ に __必要__ なテストケースが __すべて揃った__ ので、__すべてのテストケース__ を __まとめてテストを行う__ ことにします。下記は、すべてのテストケースを記述したプログラムです。

```python
testcases = {
    # 決着がついていない場合のテストケース
    Marubatsu.PLAYING: [
        # ゲーム盤に一つもマークが配置されていない場合のテストケース
        "",
        # 一つだけマークが配置されていない場合のテストケース
        "C3,A2,B1,B2,C2,C1,A3,B3",
        "A1,A2,C3,B2,C2,C1,A3,B3",
        "A1,A2,B1,B2,C2,C3,A3,B3",
        "A1,C3,B1,B2,C2,C1,A3,B3",
        "A1,A2,B1,C3,C2,C1,A3,B3",
        "A1,A2,B1,B2,C3,C1,A3,B3",
        "A1,A2,B1,B2,C2,C1,C3,B3",
        "A1,A2,B1,B2,A3,C1,C2,C3",
        "A1,A2,B1,B2,C2,C1,A3,B3",
    ],   
    # 〇の勝利のテストケース
    Marubatsu.CIRCLE: [
        "A1,A2,B1,B2,C1",
        "A2,A1,B2,B1,C2",
        "A3,A1,B3,B1,C3",
        "A1,B1,A2,B2,A3",
        "B1,A1,B2,A2,B3",
        "C1,A1,C2,A2,C3",
        "A1,A2,B2,A3,C3",
        "A3,A1,B2,A2,C1",
    ],
    # × の勝利のテストケース
    Marubatsu.CROSS: [
        "A2,A1,B2,B1,A3,C1",
        "A1,A2,B1,B2,A3,C2",
        "A1,A3,B1,B3,A2,C3",
        "B1,A1,B2,A2,C1,A3",
        "A1,B1,A2,B2,C1,B3",
        "A1,C1,A2,C2,B1,C3",
        "A2,A1,A3,B2,B1,C3",
        "A1,C1,B1,B2,A2,A3",
    ],
    # 引き分けの場合のテストケース
    Marubatsu.DRAW: [
        "A1,A2,B1,B2,C2,C1,A3,B3,C3",
    ], 
}
```

このテストケースに対して、`test_judge` を実行することで __MC/DC のテスト__ を行うことができます。実行結果から、__すべてのテストケース__ で __期待される返り値が返される__ ことが __確認__ できます。

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

__MC/DC テスト__ を行うことで、`judge` メソッドの 3 つあるバグのうちの __2 つを発見__ し、__修正__ することができました。残念ながら、MC/DC テストでは __発見できないバグ__ が __1 つ残っています__。

残りのバグは、次の経路組み合わせ網羅によって発見することができます。

# 経路組み合わせ網羅によるテスト

[経路組み合わせ網羅](https://qiita.com/ysgeso/items/728cee8982fe0ed9da38#%E7%B5%8C%E8%B7%AF%E7%B5%84%E3%81%BF%E5%90%88%E3%82%8F%E3%81%9B%E7%B6%B2%E7%BE%85path-coverage) は、可能な限り、複数の __条件分岐__ の __すべての経路__ の __組み合わせ__ を網羅します。ただし、すべての経路を網羅すると、__組み合わせ爆発__ が非常に __起きやすい__ ため、多くの場合で経路組み合わせ網羅によるテストを行うことは __現実的ではありません__。


例えば、__`judge`__ メソッドの __経路組み合わせ網羅__ に __必要__ なテストケースの __数を計算__ します。

* 1 つ目の if 文の条件式は、__8 つの式__ が or 演算子で連結されているので、経路は $2^8 =$ __256 通り__
* 2 つ目の if 文の条件式も同様なので、経路は __256 通り__
* 3 つ目の if 文の条件式は、__9 つの式__ が and 演算子で連結されているので、経路は $2^9 =$ __512 通り__
* 従って、__すべての経路の組み合わせ__ は、$256 * 256 * 512 =$ __33554432（約3000万）通り__

`judge` メソッドの場合、__通ることが不可能__ な __経路がある__[^2]ため、実際には上記で計算した数のテストケースがすべて必要になることはありませんが、__かなり多く__ のテストケースが __必要__ になるため、__経路組み合わせ網羅__ でテストを行うことは __現実的ではありません__。

## 簡易的な組み合わせ網羅

上記は __厳密な__ 経路組み合わせ網羅の説明ですが、__すべて__ の if 文の条件式に対して __`True` と `False`__ になるような __組み合わせを網羅__ するテストケースでテストを行うという、__簡易的な__ 経路組み合わせ網羅[^3]を考えることができます。この場合は、厳密な場合と比較して __組み合わせ爆発__ は __おきづらい__ ので、実際に `judge` メソッドに対してこのテストを行うことができます。

分かりにくいと思いますので、`judge` メソッドを具体例として説明します。

`judge` メソッドには、__3 つの if 文__ があり、その __条件文__ の __計算結果__ の __すべての組み合わせは__ $2 * 2 * 2 =$ __8 通り__ になります。従って、簡易的な経路組み合わせ網羅では、下記の条件を満たす、__8 つ__ のテストケースを用意すれば良いことがわかります。

下記の __表__ はその __すべての組み合わせ__ を表したものです。以降は、それぞれを、表の __左の列__ に記述した __番号で表す__ ことにします。

|| 〇の勝利の判定 | ×の勝利の判定 | 引き分けの判定 |
|:-:|:-:|:-:|:-:|
|1| `False`  | `False`  | `False`  |
|2| `False`  | `False`  | `True`  |
|3| `False`  | `True`  | `False`  |
|4| `False`  | `True`  | `True`  |
|5| `True`  | `False`  | `False`  |
|6| `True`  | `False`  | `True`  |
|7| `True`  | `True`  | `False`  |
|8| `True`  | `True`  | `True`  |

次に、__各条件__ を満たすテストケースに対する、__`judge`__ メソッドの __期待される返り値__ を考えます。

1. この場合は、期待される返り値は明らかに __`Marubatsu.PLAYING`__ です
2. この場合は、期待される返り値は明らかに __`Marubatsu.DRAW`__ です
3. この場合は、期待される返り値は明らかに __`Marubatsu.CROSS`__ です
4. この場合は、__勝利の判定__ と、__引き分けの判定__ が __共に `True`__ になります。__一見する__ と、このような状況は __あり得ない__ ように __思えるかもしれません__ が、__引き分けの判定__ を行う __条件式__ が、__すべてのマスが埋まっている__ ことを __判定__ していることを考えると、__最後の 9 手目__ で __マークを配置__ した際に __× が勝利__ した場合は、__この条件が満たされる__ ことがわかります。このことから、__3 つ目の if 文__ が「__引き分けを判定__」しているの __ではなく__、「__すべてのマスが埋まっているかどうか__」を __判定__ していることがわかります。このような、__似ている__ が __実際には違う__ ことを判定するという __勘違い__ は、__プログラムを実装__ する際に __よく発生し__、そのことが __原因__ で __バグが発生__ することが __よくあります__。実際に、__この勘違い__ が、`judge` メソッドの __3 つ目のバグの原因__ になっています。なお、__〇×ゲームの性質__ から、__9 手目__ は、__必ず 〇 の手番__ になるので、__9 手目で × が勝利__ することは __あり得ません__。従って、__4 の条件を満たす__ テストケースは __存在しません__
5. この場合は、期待される返り値は明らかに __`Marubatsu.CIRCLE`__ です
6. この場合は、上記の __4 で説明__ したように、__最後の 9 手目__ でマークを __配置__ した際に __〇が勝利する場合__ です。従って、期待される返り値は __`Marubatsu.CIRCLE`__ になります
7. __〇×ゲームの性質__ 上、__〇 の勝利__ と __× の勝利__ が __同時に起きる__ ことは __ありません__。従って、この条件を満たすテストケースは __存在しません__
8. 7 と同様の理由で、この条件を満たすテストケースは __存在しません__

下記は、上記の考察結果を表にしたものです。上記の考察から、__3 つ目の if 文__ で行う __処理の意味__ が __間違っていた__ ことが分かったので、「__引分の判定__」を「__全てのマスが埋まっているか__」に __修正__ しました。なお、× は、そのようなテストケースが __存在しない__ ことを表します。

|| 〇の勝利の判定 | ×の勝利の判定 | 全てのマスが埋まっているか | 期待される返り値 |
|:-:|:-:|:-:|:-:|:-:|
|1| `False`  | `False`  | `False`  | `Marubatsu.PLAYING` |
|2| `False`  | `False`  | `True`  | `Marubatsu.DRAW` |
|3| `False`  | `True`  | `False`  |`Marubatsu.CROSS` |
|4| `False`  | `True`  | `True`  | × |
|5| `True`  | `False`  | `False`  |`Marubatsu.CIRCLE` |
|6| `True`  | `False`  | `True`  |`Marubatsu.CIRCLE` |
|7| `True`  | `True`  | `False`  | × |
|8| `True`  | `True`  | `True`  | × |

## テストの実施

__簡易的な経路組み合わせ網羅__ によるテストでは、__上記の 5 種類__ のテストケースを __用意__ すれば良いことがわかります。上記の中で、__1、2、3、5__ のテストケースは、__MC/DC で作成__ したものを __流用__ することができます。そのため、__新しく作る__ 必要があるテストケースは、__6 の一つだけ__ です。

本記事では、6 のテストケースとして、下図のようなものを用意することにします。__9 手目__ で __〇 が勝利__ する必要があるため、__9 手目の着手__ を __(0, 2)__ にする __必要__ がある点に注意して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/960ec230-a9ad-db78-c3f5-973aa7f01c2c.png" width="100">

下記は、簡易的な経路組み合わせ網羅の 5 個のテストケースを記述したプログラムです。

```python
testcases = {
    Marubatsu.PLAYING: [
        "", # 1 のテストケース
    ],
    Marubatsu.CIRCLE: [
        "A1,A2,B1,B2,C1",             # 5 のテストケース
        "A1,B1,A2,B2,B3,C1,C3,C2,A3", # 6 のテストケース
    ],
    Marubatsu.CROSS: [
        "A2,A1,B2,B1,A3,C1", # 3 のテストケース
    ],
    Marubatsu.DRAW: [
        "A1,A2,B1,B2,C2,C1,A3,B3,C3", # 2 のテストケース
    ], 
}
```

上記のテストケースに対して、実引数に __`debug=True`__ を記述して `test_judge` を実行します。

```python
test_judge(testcases, debug=True)
```

実行結果
```
Start
test winner = playing
Turn o
...
...
...

ok

test winner = o
Turn x
ooo
xx.
...

ok
Turn x
oxx
oxx
ooo


====================
test_judge error!
Turn x
oxx
oxx
ooo

mb.judge(): draw
winner:     o
====================

test winner = x
Turn o
xxx
oo.
o..

ok

test winner = draw
Turn x
oox
xxo
oxo

ok

Finished
```
実行結果の __ゲーム盤の表示__ から、テストケースによって __正しいマス__ に __マークが配置__ されることが __確認__ できます。一方、__6 のテストケース__ に対して、`judge` メソッドが、__期待される `"o"` ではなく__、__`"draw"` を返す__ という __エラーメッセージが表示__ されます。

## エラーの原因の検証

下図は、6 のテストケースに対して `judge` メソッドを実行した際の __フローチャート__ です。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/a1d44aba-dbc5-d0b9-36c5-a84519f48433.png" width="500">

図からわかるように、__〇 の勝利__ の if 文の __条件式が `True`__ になった結果、図の __紫色の文字__ で表示された __`winner = Marubatsu.CIRCLE`__ が __実行__ されますが、__その後__ の __全てのマスが埋まっている__ ことを判定する if 文の __条件式__ も __`True`__ になるので、__赤色の文字__ で表示された __`winner = Marubatsu.DRAW`__ がその後で実行され、`winner` の値が `Marubatsu.DRAW` で __上書き__ されてしまいます。

これが、`judge` メソッドの __3 つ目のバグの原因__ です。

## バグの修正方法 その 1

このバグを修正する方法はいくつかありますが、__〇 の勝利__ と __判定__ された時点で、__〇 の勝利__ であると __確定する__ 場合は、__独立した if 文__ を 3 つ __並べるのではなく__、__elif__ や __else__ を使って、__一つの if 文__ で __条件分岐を記述__ する方法が __簡単__ です。

下記はそのように修正したプログラムです。修正した箇所は以下の通りです。なお、__条件式が長い__ ので、それぞれの条件式の部分は、「〇 の勝利判定を行う条件式」のように __言葉で表記__ します。

* __2 つ目__ と __3 つ目__ の __if__ を __elif__ に __修正__ した
* __2 つ目__ と __3 つ目__ の __if 文の前__ にあった __空行を削除__ した

元のプログラムでは、__間に空行__ を __記述する__ ことで、3 つの __if 文__ が __異なる__ if 文であることが __明確になる__ ようにしていましたが、__修正後__ は __1 つの if 文__ になったので、__間の空行を削除__ しました。

```python
    def judge(self):      
        # 判定を行う前に、決着がついていないことにしておく
        winner = Marubatsu.PLAYING
        # 〇 の勝利の判定
        if 〇の勝利判定を行う条件式:
            winner = Marubatsu.CIRCLE        
        # × の勝利の判定
        elif × の勝利判定を行う条件式:
            winner = Marubatsu.CROSS     
        # すべてのマスが埋まっていない事の判定
        elif すべてのマスが埋まっていない事を判定する条件式:
            winner = Marubatsu.DRAW

        # winner を返り値として返す
        return winner   
```

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

```diff_python
    def judge(self):      
        # 判定を行う前に、決着がついていないことにしておく
        winner = Marubatsu.PLAYING
        # 〇 の勝利の判定
        if 〇の勝利判定を行う条件式:
            winner = Marubatsu.CIRCLE     
        # × の勝利の判定
-
-       if × の勝利判定を行う条件式:
+       elif × の勝利判定を行う条件式:
            winner = Marubatsu.CROSS     
        # すべてのマスが埋まっていない事の判定
-
-       if すべてのマスが埋まっていない事を判定する条件式:
+       elif すべてのマスが埋まっていない事を判定する条件式:
            winner = Marubatsu.DRAW

        # winner を返り値として返す
        return winner   
```
</details>

__修正後__ の `judge` メソッドの __フローチャート__ は以下のようになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/756c700a-7210-0c97-5fbf-eba6c0e6e482.png" width="700">

下記のプログラムによって、__すべてのテストケース__ に対して `judge` メソッドが __期待される処理を返す__ ようになったことが __確認__ できます。

```python
test_judge(testcases, debug=True)
```

実行結果
```
Start
test winner = playing
o
test winner = o
oo
test winner = x
o
test winner = draw
o
Finished
```

## バグの修正方法その 2

他の修正方法として、__ゲームの決着がついていない状態__ では、if 文の __3 つの条件式__ の __すべてが `False`__ になることから、下記のプログラムのように、__`else` のブロック内__ で、__`winner`__ に __`Marubatsu.PLAYING`__ を __代入__ するように修正する方法があります。

```python
    def judge(self):      
        # 〇 の勝利の判定
        if 〇の勝利判定を行う条件式:
            winner = Marubatsu.CIRCLE
        # × の勝利の判定
        elif × の勝利判定を行う条件式:
            winner = Marubatsu.CROSS     
        # すべてのマスが埋まっていない事の判定
        elif すべてのマスが埋まっていない事を判定する条件式:
            winner = Marubatsu.DRAW
        # 上記のどれでもなければ決着がついていない
        else:
            winner = Marubatsu.PLAYING   

        # winner を返り値として返す
        return winner   
```

下記のプログラムを実行することによって、この修正方法で正しくテストが行えることが確認できます。なお、実行結果は先ほどと同様なので省略します。

```python
test_judge(testcases)
```

### 修正方法その 1 と その 2 の違い

修正方法その 1 と、その 2 のプログラムは、__全く同じ処理__ を行うように __見えるかも__ しれませんが、__実際__ には、以下のように、__微妙に__ 行われる __処理が異なります__。

* 修正方法その 1 のプログラムでは、if 文を実行する前に、__必ず__ `winner = Marubatsu.PLAYING` が __実行__ される
* 修正方法その 2 のプログラムでは、if 文のすべての条件式が `False` の __場合のみ__ `winner = Marubatsu.PLAYING` が __実行される__

__`judge`__ メソッドの __場合__ は、この違いは __全く問題にならない__ ので、わかりやすいと思ったほうを採用して構いませんが、__この違い__ がプログラムの __処理に影響を及ぼす場合__ があります。

例えば、下記のように、__`judge` メソッドを修正__ する場合の事を考えてみて下さい。

* __`judge`__ メソッドを __実行__ し、__ゲームが続行中__ であることが __判定された場合__ に、`print("playing")` を実行して __`"playing"`__ という文字列を __画面に表示__ する

__修正方法その 1__ を元に、下記のプログラムのように、4 行目に `print("playing")` を記述してしまうと、この __4 行目__ は、if 文を実行する前に __必ず実行__ されるので、__`judge`__ メソッドを __実行__ すると __必ず `"playing"` が表示__ されてしまいまうという __バグが発生__ します。

```python
1    def judge(self):      
2        # 判定を行う前に、決着がついていないことにしておく
3        winner = Marubatsu.PLAYING
4        print("playing")
5        # 〇 の勝利の判定
6        if 〇の勝利判定を行う条件式:
7            winner = Marubatsu.CIRCLE
8        略
```

一方、__修正方法その 2__ を元に、下記のプログラムのように、8 行目に `print("playing")` を記述した場合は、この __8 行目__ は、if 文の __すべての条件式が `False`__  の __場合のみ実行__ されるので、正しい処理が行われます。

```python
1    def judge(self):      
2        # 〇 の勝利の判定
3        if 〇の勝利判定を行う条件式:
4        略
5        # 上記のどれでもなければ決着がついていない
6        else:
7            winner = Marubatsu.PLAYING   
8            print("playing")
9        略
```

このように、__処理の流れ__ を __正しく理解せず__ にプログラムを記述すると、__思わぬバグが発生__ してしまうことがあるので、__処理の流れを意識__ してプログラムを記述することを __こころがけて下さい__。

## バグの修正方法その 3

__if 文の後__ で何も __処理を行わない__ のであれば、if 文のそれぞれの __ブロックの中__ で、__return 文__ を記述することもできます。これは、__`return` 文を実行__ すると、関数の残りの処理を行うことなく、__関数呼び出しの処理__ をその時点で __即座に終了する__ という性質を利用しています。


この場合は、下記のプログラムのように、__ローカル変数 `winner`__ が __不要__ になります。下記のようなプログラムは __実際に良く記述される__ ので、本記事でもこのプログラムを採用することにします

```python
    def judge(self):      
        # 〇 の勝利の判定
        if 〇の勝利判定を行う条件式:
            return Marubatsu.CIRCLE        
        # × の勝利の判定
        elif × の勝利判定を行う条件式:
            return Marubatsu.CROSS     
        # すべてのマスが埋まっていない事の判定
        elif すべてのマスが埋まっていない事を判定する条件式:
            return Marubatsu.DRAW
        # 上記のどれでもなければ決着がついていない
        else:
            return Marubatsu.PLAYING   
```

下記のプログラムを実行することによって、この修正方法で正しくテストが行えることが確認できます。なお、実行結果は先ほどと同様なので省略します。

```python
test_judge(testcases)
```

## if 文に関する注意点

今回記事の例からわかるように、__条件分岐__ で、__複数の条件式__ を __記述__ する際に、「__複数の if 文を記述__」する場合と、「__elif__ を使って __一つの if 文で記述__」する場合は、__異なる処理__ が行われる点に __注意__ して下さい。そこを __間違える__ と修正前の `judge` メソッドのような __バグの原因__ になります。

また、__複数の条件式__ を __記述__ する際に、__可能__ であれば __一つの if 文で記述したほうが良い__ でしょう。その __理由__ は、下記のように、__経路の組み合わせが減る__ からです。

* 修正前のフローチャートでは、__3 つの if 文が独立__ していたので、__処理の流れ__ の __組み合わせ__ が、$2 ^ 3$ = __8 通り__ ある
* 修正後のフローチャートでは、__1 つの if 文の中__ に、__3 つの条件式__ があるので、処理の流れの組み合わせは $3 + 1$ = __4 通り__ ある

上記からわかるように、__複数の if 文で記述__ する場合は、__組み合わせの数__ が、__乗算で計算__ されるため、if 文の数が多くなればなるほど、__急激に増えていく__ ことになります。一方、__1 つの if 文で記述__ する場合は、組み合わせの数が __加算で計算__ されるため、急激に増えることは __ありません__。

# MC/DC と簡易的な組み合わせ網羅のテストの併用

__簡易的な組み合わせ網羅__ のテストでは、__それぞれの if 文__ に対して、__[分岐網羅(C1)](https://qiita.com/ysgeso/items/728cee8982fe0ed9da38#%E5%88%86%E5%B2%90%E7%B6%B2%E7%BE%85decision-coverage)__ のテスト __しか行っていない__ ことになります。従って、if 文の条件式に __and 演算子__ や __or 演算子__ が __記述__ されている場合は、__MC/DC__ のテストと __併用__ したほうが良いでしょう。

実際に、先程の __簡易的な組み合わせ網羅のテスト__ で用意した 5 つのテストケースでは、__MC/DC で発見できた__、`judge` メソッドの __1 つ目と 2 つ目のバグ__ を __発見できません__。

そこで、本記事では最後に、下記のような、__MC/DC__ と __簡易的な組み合わせ網羅__ のそれぞれの条件を満たすテストケースを __集めたテストケース__ でテストを行うことにします。

```python
testcases = {
    # 決着がついていない場合のテストケース
    Marubatsu.PLAYING: [
        # ゲーム盤に一つもマークが配置されていない場合のテストケース
        "",
        # 一つだけマークが配置されていない場合のテストケース
        "C3,A2,B1,B2,C2,C1,A3,B3",
        "A1,A2,C3,B2,C2,C1,A3,B3",
        "A1,A2,B1,B2,C2,C3,A3,B3",
        "A1,C3,B1,B2,C2,C1,A3,B3",
        "A1,A2,B1,C3,C2,C1,A3,B3",
        "A1,A2,B1,B2,C3,C1,A3,B3",
        "A1,A2,B1,B2,C2,C1,C3,B3",
        "A1,A2,B1,B2,A3,C1,C2,C3",
        "A1,A2,B1,B2,C2,C1,A3,B3",
    ],   
    # 〇の勝利のテストケース
    Marubatsu.CIRCLE: [
        "A1,A2,B1,B2,C1",
        "A2,A1,B2,B1,C2",
        "A3,A1,B3,B1,C3",
        "A1,B1,A2,B2,A3",
        "B1,A1,B2,A2,B3",
        "C1,A1,C2,A2,C3",
        "A1,A2,B2,A3,C3",
        "A3,A1,B2,A2,C1",
        # 簡易的な組み合わせ網羅の 6 のテストケース
        "A1,B1,A2,B2,B3,C1,C3,C2,A3", 
    ],
    # × の勝利のテストケース
    Marubatsu.CROSS: [
        "A2,A1,B2,B1,A3,C1",
        "A1,A2,B1,B2,A3,C2",
        "A1,A3,B1,B3,A2,C3",
        "B1,A1,B2,A2,C1,A3",
        "A1,B1,A2,B2,C1,B3",
        "A1,C1,A2,C2,B1,C3",
        "A2,A1,A3,B2,B1,C3",
        "A1,C1,B1,B2,A2,A3",
    ],
    # 引き分けの場合のテストケース
    Marubatsu.DRAW: [
        "A1,A2,B1,B2,C2,C1,A3,B3,C3",
    ], 
}
```

下記のプログラムによって、MC/DC と簡易的な組み合わせ網羅の __両方のすべて__ のテストケースに対して `judge` メソッドが __期待される処理を返す__ ことが __確認__ できます。

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

## MC/DC と簡易的な組み合わせ網羅をまとめて行う方法

上記では、MC/DC のテストと、簡易的な組み合わせ網羅のテストを __別々に__ 行い、その 2 つのテストケースを __合わせて__ テストを行う方法を紹介しましたが、__MC/DC のテスト__ を行う際に、__工夫する__ ことで __簡易的な組み合わせ網羅__ のテストを __まとめて（並行して）行う__ ことができます。

今回の記事の最初のほうで、引き分けの場合の、MC/DC の 「すべてが `True` になる テストケース」の所で、以下のような説明を行いました。

「すべてのマスにマークが配置されたテストケースは、かなりの種類がありますが、MC/DC のテストでは、そのような __条件を満たす__ テストケースを __1 つだけ用意__ すれば良い」

この部分を、「__すべての経路__ に対し、そのような __条件を満たす__ テストケースを __1 つずつ用意__ する」のように修正することで、MC/DC のテストと、簡易的な組み合わせ網羅のテストを並行して行うことができるようになります。

具体的には、今回の記事では上記の場合に、「9 つのマスが埋まっている、引き分けの状態」のテストケース __のみを用意__ してテストを行いましたが、__それに加えて__、「9 つのマスが埋まっている、〇 の処理の状態」のテストケースを用意してテストを行います。

長くなるので、この方法でテストの具体例は省略しますが、興味がある方は試してみて下さい。

# 今後の記事での関数のテストの方針について

大変長くなってしまいましたが、以上で `judge` メソッドのテストは終了です。

__個人で作成__ するようなプログラムでは、__すべての関数__ に対して、このようなテストを __行う必要__ は __全くありません__ が、__ある程度以上複雑__ な関数を実装した場合は、__分岐網羅（C1）レベル__ のテストは __行ったほうが良い__ のではないかと思います。__どのレベル__ のテストを __行うか__ については、実装した __関数の複雑__ さや、__テストに費やすことが出来る時間__ などから、__自分で判断__ して下さい。

なお、本記事では、毎回 __テストを行うための関数を作成__ するようなテストを行うと、__記事が際限なく長く__ なってしまうので、基本的には __簡単なテストで済ます__ ことにしようと考えています。

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

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

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

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

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

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

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

# 次回の記事

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

[^1]:一度で正しくテストケースを記述することは難しいかもしれません。実際に、筆者は、実行結果を見た結果、間違えていることがわかったので、一度修正を行いました
[^2]:例えば、〇×ゲームの性質上、〇 の勝利と 引き分けが同時に満たされるようなテストケースは存在しません
[^3]:厳密な経路組み合わせ網羅と、簡易的な経路組み合わせ網羅を表現する用語を探したのですが見つかりませんでした。知っている方がいれば教えて頂ければ助かります