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

# 目次と前回の記事

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

https://qiita.com/ysgeso/items/8468e6bc59b7595c21f0

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

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

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

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

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

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

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

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

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

## 前回までのおさらい

前回の記事では、`judge` メソッドのテストの作業を完了し、`judge` メソッドにあった 3 つのバグをすべて修正しました。これにより、〇×ゲームの __7 つの仕様__ の __実装__ がすべて __完了__ しました。

# `judge` メソッドの改良

下記のプログラムは、前回の記事までで実装した `judge` メソッドです。このプログラムは、__かなり長い__ プログラムになっていますが、__判定したいこと__ を、__そのまま記述__ しているという点で、__or__、__and__、__not 演算子__ の使い方を __学べば__、__初心者__ でも __自力で記述できる__ のではないかと思います。

```python
    def judge(self):      
        # 〇 の勝利の判定
        if self.board[0][0] == self.board[1][0] == self.board[2][0] == Marubatsu.CIRCLE or \
            self.board[0][1] == self.board[1][1] == self.board[2][1] == Marubatsu.CIRCLE or \
            self.board[0][2] == self.board[1][2] == self.board[2][2] == Marubatsu.CIRCLE or \
            self.board[0][0] == self.board[0][1] == self.board[0][2] == Marubatsu.CIRCLE or \
            self.board[1][0] == self.board[1][1] == self.board[1][2] == Marubatsu.CIRCLE or \
            self.board[2][0] == self.board[2][1] == self.board[2][2] == Marubatsu.CIRCLE or \
            self.board[0][0] == self.board[1][1] == self.board[2][2] == Marubatsu.CIRCLE or \
            self.board[2][0] == self.board[1][1] == self.board[0][2] == Marubatsu.CIRCLE:
            return Marubatsu.CIRCLE
        # × の勝利の判定
        elif self.board[0][0] == self.board[1][0] == self.board[2][0] == Marubatsu.CROSS or \
            self.board[0][1] == self.board[1][1] == self.board[2][1] == Marubatsu.CROSS or \
            self.board[0][2] == self.board[1][2] == self.board[2][2] == Marubatsu.CROSS or \
            self.board[0][0] == self.board[0][1] == self.board[0][2] == Marubatsu.CROSS or \
            self.board[1][0] == self.board[1][1] == self.board[1][2] == Marubatsu.CROSS or \
            self.board[2][0] == self.board[2][1] == self.board[2][2] == Marubatsu.CROSS or \
            self.board[0][0] == self.board[1][1] == self.board[2][2] == Marubatsu.CROSS or \
            self.board[2][0] == self.board[1][1] == self.board[0][2] == 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  
```

__正しく動作__ するプログラムを __記述__ することが __できなければ__、そもそも __先に進む__ ことは __不可能__ なので、例え __効率が悪くとも__、__最初__ は上記のようなプログラムでも __構わない__ と思います。

ただし、上記のようなプログラムには、__入力ミス__ がつきもので、__たった一つ__ のデータの __入力を間違っただけ__ で __バグが発生__ してしまうという __問題__ があります。また、〇 の勝利と × の勝利の判定で __同じような処理__ を __2 度記述__ しているため、__効率が悪い__ などの問題があります。

そこで、今回と次回の記事では、`judge` メソッドを様々なアルゴリズムで記述する方法について紹介します。

# 勝利判定を行うメソッドの定義

まず、`judge` メソッドの中で、__〇 の勝利の判定__ と、__× の勝利の判定__ を行う if 文の __条件式__ を __見比べて__、__どの部分__ が __異なっている__ かを __確認__ してください。


よく見ると、__`Marubatsu.CIRCLE`__ と __`Marubatsu.CROSS`__ の部分が __異なる__ だけで、__それ以外__ の部分は __全く同じ__ であることがわかるはずです。このような場合は、〇 の勝利の判定と、× の勝利の判定を __一つのメソッド__ で __まとめる__ ことができます。

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

* __処理__：__実引数で指定__ した __プレイヤーが勝利__ しているかどうかを __判定__ する
* __名前__：指定したプレイヤーが __勝利者である__(is winner) ことを __判定__ するので、__`is_winner`__ とする
* __入力__：__`player`__ という仮引数で、__判定するプレイヤー__ の情報を __受け取る__
* __出力__：__`player`__ のプレイヤーが __勝利__ していた場合は __`True`__ を、__そうでなければ `False`__ を返す

このメソッドは、以下のプログラムのように定義することができます。なお、具体的な条件式の記述はこの後で行います。

```python
def is_winner(self, player):
    if player が勝利していることを判定する条件式:
        return True
    else:
        return False
```

この関数を使って、__`judge` メソッド__ を以下のプログラムのように __修正__ することができます。

```python
from marubatsu import Marubatsu

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 
    
Marubatsu.judge = judge
```

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

```diff_python
from marubatsu import Marubatsu

def judge(self):      
    # 〇 の勝利の判定
-   if self.board[0][0] == self.board[1][0] == self.board[2][0] == Marubatsu.CIRCLE or \
-      self.board[0][1] == self.board[1][1] == self.board[2][1] == Marubatsu.CIRCLE or \
-      self.board[0][2] == self.board[1][2] == self.board[2][2] == Marubatsu.CIRCLE or \
-      self.board[0][0] == self.board[0][1] == self.board[0][2] == Marubatsu.CIRCLE or \
-      self.board[1][0] == self.board[1][1] == self.board[1][2] == Marubatsu.CIRCLE or \
-      self.board[2][0] == self.board[2][1] == self.board[2][2] == Marubatsu.CIRCLE or \
-      self.board[0][0] == self.board[1][1] == self.board[2][2] == Marubatsu.CIRCLE or \
-      self.board[2][0] == self.board[1][1] == self.board[0][2] == Marubatsu.CIRCLE:
+   if self.is_winner(Marubatsu.CIRCLE):
        return Marubatsu.CIRCLE
    # × の勝利の判定
-   elif self.board[0][0] == self.board[1][0] == self.board[2][0] == Marubatsu.CROSS or \
-        self.board[0][1] == self.board[1][1] == self.board[2][1] == Marubatsu.CROSS or \
-        self.board[0][2] == self.board[1][2] == self.board[2][2] == Marubatsu.CROSS or \
-        self.board[0][0] == self.board[0][1] == self.board[0][2] == Marubatsu.CROSS or \
-        self.board[1][0] == self.board[1][1] == self.board[1][2] == Marubatsu.CROSS or \
-        self.board[2][0] == self.board[2][1] == self.board[2][2] == Marubatsu.CROSS or \
-        self.board[0][0] == self.board[1][1] == self.board[2][2] == Marubatsu.CROSS or \
-        self.board[2][0] == self.board[1][1] == self.board[0][2] == Marubatsu.CROSS:
+   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 
    
Marubatsu.judge = judge
```
</details>


この修正によって、下記のような __利点__ が得られます。

* __元の `judge` メソッド__ の 〇 の勝利の判定と × の勝利の判定を行う、一見すると何を行っているかが __わかりづらい複雑な条件式__ が、__`is_winner`__ という、その __名前から__ 何を行っているかが __わかりやすい__ メソッドの呼び出しに __置き換えられている__ ので、`judge` メソッドで行われる __処理__ の __見た目__ が __わかりやすくなる__。このような、__具体的な処理の記述__ を、メソッドの名前などの、短く __わかりやすい__ 記述 __置き換える__ ことを、__抽象化__ と呼ぶ
* __同じような処理__ を行う 〇 の勝利の判定と、× の勝利の判定を行う条件式が、`is_winner` の中の __1 箇所__ に __まとめられる__ ので、プログラムの __記述が短く__ なる
* __1 箇所__ に __まとめる__ ことで、__間違っていた場合__ の __修正__ や、__条件式の改良__ を行う際に、その __1 箇所だけ__ を __修正__ すれば __済む__ ようになる

## `is_winner` の実装

次に、__`is_winner`__ の __条件式を記述__ します。__`player` が勝利__ しているかどうかを __判定__ する __条件式__ は、下記のプログラムのように、`judge` メソッドに記述されていた、__〇 の勝利の判定__ を行う __条件式__ の __`Marubatsu.CIRCLE`__ を __`player`__ に __置き換える__ ことで記述することができます。

__元の `judge` メソッド__ では、__〇 が勝利した場合__ に行う __処理__ は、__`return Marubatsu.CIRCLE`__ でしたが、__`is_winner`__ では、__`player` が勝利した場合__ は __`True` を返す__ ので __`return True` を記述__ する必要がある点に __注意__ して下さい。また、`player` が勝利 __していない__ 場合は、__`False` を返します__。

```python
def is_winner(self, player):
    # player が勝利しているかどうかを判定する
    if self.board[0][0] == self.board[1][0] == self.board[2][0] == player or \
       self.board[0][1] == self.board[1][1] == self.board[2][1] == player or \
       self.board[0][2] == self.board[1][2] == self.board[2][2] == player or \
       self.board[0][0] == self.board[0][1] == self.board[0][2] == player or \
       self.board[1][0] == self.board[1][1] == self.board[1][2] == player or \
       self.board[2][0] == self.board[2][1] == self.board[2][2] == player or \
       self.board[0][0] == self.board[1][1] == self.board[2][2] == player or \
       self.board[2][0] == self.board[1][1] == self.board[0][2] == player:
        return True
    else:
        return False

Marubatsu.is_winner = is_winner
```

<details><summary><strong>修正箇所（<code>judge</code> メソッドの 〇の勝利を判定する if 文との比較です)
</strong></summary>

```diff_python
-   if self.board[0][0] == self.board[1][0] == self.board[2][0] == Marubatsu.CIRCLE or \
+   if self.board[0][0] == self.board[1][0] == self.board[2][0] == player or \
-      self.board[0][1] == self.board[1][1] == self.board[2][1] == Marubatsu.CIRCLE or \
+      self.board[0][1] == self.board[1][1] == self.board[2][1] == player or \
-      self.board[0][2] == self.board[1][2] == self.board[2][2] == Marubatsu.CIRCLE or \
+      self.board[0][2] == self.board[1][2] == self.board[2][2] == player or \
-      self.board[0][0] == self.board[0][1] == self.board[0][2] == Marubatsu.CIRCLE or \
+      self.board[0][0] == self.board[0][1] == self.board[0][2] == player or \
-      self.board[1][0] == self.board[1][1] == self.board[1][2] == Marubatsu.CIRCLE or \
+      self.board[1][0] == self.board[1][1] == self.board[1][2] == player or \
-      self.board[2][0] == self.board[2][1] == self.board[2][2] == Marubatsu.CIRCLE or \
+      self.board[2][0] == self.board[2][1] == self.board[2][2] == player or \
-      self.board[0][0] == self.board[1][1] == self.board[2][2] == Marubatsu.CIRCLE or \
+      self.board[0][0] == self.board[1][1] == self.board[2][2] == player or \
-      self.board[2][0] == self.board[1][1] == self.board[0][2] == Marubatsu.CIRCLE:
+      self.board[2][0] == self.board[1][1] == self.board[0][2] == player:
-       return Marubatsu.CIRCLE
+       return True
+   else:
+       return False
```
</details>


## 修正した `judge` メソッドのテスト

`judge` メソッドを __修正__ したので、__テスト__ を行う必要があります。今回の修正では、`is_winner` という __新しい関数を定義__ したので、__厳密なテスト__ を行うのであれば、__`is_winner`__  に対する __テスト__ を行う必要があるので __大変__ だと思う人がいるかもしれません。

__関数やメソッドを修正__ した結果、関数の中の __処理の流れ__ が大きく __変わったり__、__新しい関数を定義__ する事はよくあることですが、そのたびに、__新しい__ 処理の流れに対応した __テストケースを作成__ したり、__新しい関数__ に対する __テストを行う__ のは __大変__ で、__現実的に無理__ なことが __多い__ でしょう。

今回のように、`judge` メソッドに __新しい機能__ を付け __加える__ の __ではなく__、`judge` メソッドの __機能__ そのものは __全く変化しない__ ような __修正__ を行った場合は、__それまでに行ったテスト__ を __そのまま流用__ するのが __一般的__ です。__しっかりとしたテスト__ が行えていれば、処理の流れが変わったり、新しい関数を定義していても、__十分な精度__ で __テストを行う__ ことが __できる__ からです。

そこで、本記事でも、今後は __修正__ した __`judge` メソッド__ の __テスト__ は、__前回までの記事__ で __作成__ した __`test_judge`__ を __そのまま使って行う__ ことにします。ただし、前回の記事で作成した `test_judge` は、__実引数__ に __テストケースを記述__ する __必要__ がある点が __不便__ です。そこで、__`test_judge`__ を __実引数を記述せず__ に呼び出した場合は、前回の記事で作成した、__MC/DC__ と __簡易的な組み合わせ網羅__ を __組み合わせたテストケース__ で __テストを行う__ ように __修正__ します。

下記は、そのように `test_judge` を修正したプログラムです。修正点は以下の通りです。

* __`testcases`__ を __デフォルト引数値__ が __`None`__ に設定された __デフォルト引数__ にする
* 関数のブロックの __最初__ に、__`testcases`__ が __`None` の場合__ に、`testcases` に MC/DC と 簡易的な組み合わせ網羅 を 組み合わせた __テストケースのデータを代入__ する

__`testcases` に対応__ する __実引数を記述せず__ に `test_judge` を __呼び出す__ と、仮引数 __`testcases`__ にデフォルト値である __`None` が代入__ された状態で、__`test_judge`__ のブロックが __実行__ されます。その結果、__最初の if 文__ によって、__`testcases`__ に MC/DC と 簡易的な組み合わせ網羅を組み合わせた __テストケースのデータ__ が __代入__ されます。[以前の記事](https://qiita.com/ysgeso/items/ea147c436e357281f441#none-%E3%81%AE%E5%88%A4%E5%AE%9A%E3%81%A8isis-not-%E6%BC%94%E7%AE%97%E5%AD%90) で説明したように、__`None` であるか__ どうかの __判定__ は、`==` ではなく、__`is` 演算子__ で行う __必要__ がある点に __注意__ して下さい。

```python
def test_judge(testcases=None, debug=False):
    if testcases is None:
        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",
            ], 
        }

    print("Start")
    以下同じなので略
```

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

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

## `is_winner` の微修正

先程実装した、`is_winner` のように、__条件式__ が __`True`__ の場合は、__`True`__ を、__そうでない場合__ は __`False` を返す__ 関数は、条件式の __計算結果そのもの__ が、__返り値に等しい__ ので、下記のプログラムのように、__if 文を使わず__ に、__条件式__ の計算結果を __直接返す__ ように修正することができます。

```python
def is_winner(self, player):
    # player が勝利していることを表す条件式の計算結果を返す
    return self.board[0][0] == self.board[1][0] == self.board[2][0] == player or \
           self.board[0][1] == self.board[1][1] == self.board[2][1] == player or \
           self.board[0][2] == self.board[1][2] == self.board[2][2] == player or \
           self.board[0][0] == self.board[0][1] == self.board[0][2] == player or \
           self.board[1][0] == self.board[1][1] == self.board[1][2] == player or \
           self.board[2][0] == self.board[2][1] == self.board[2][2] == player or \
           self.board[0][0] == self.board[1][1] == self.board[2][2] == player or \
           self.board[2][0] == self.board[1][1] == self.board[0][2] == player

Marubatsu.is_winner = is_winner
```

下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

# `is_winner` のアルゴリズム その 1 （`+` 演算子を使う）

__勝利判定__ を行う `is_winner` を実装したので、今回の記事で紹介する、__さまざまな__ 勝利判定の __アルゴリズム__ は、__`is_winner` を修正__ することで __実装__ することにします。

`is_winner` の __条件式__ の中では、__一直線上に 3 つ並んだマス__ に配置された __マーク__ が __`winner` と等しい__ かどうかを、下記のプログラムのように、__`==` 演算子__ を __連結__ して __記述__ しました。

```python
self.board[0][0] == self.board[1][0] == self.board[2][0] == player
```

[以前の記事](https://qiita.com/ysgeso/items/1fdd19037bbf64082a42#python-%E3%81%AE%E6%AF%94%E8%BC%83%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AB%E3%82%88%E3%82%8B-and-%E6%BC%94%E7%AE%97%E5%AD%90%E3%81%AE%E7%9C%81%E7%95%A5) で説明したように、このような記述は、__Python 以外__ の __多くのプログラム言語__ では __行うことができず__[^1]、下記のように、__and 演算子__ を使って __記述する必要__ があり（長いので途中で改行しました）、その場合は __記述が長く__ なってしまいます。

```python
self.board[0][0] == self.board[1][0] and self.board[1][0] == self.board[2][0] and \
self.board[2][0] == player
```

__`+` 演算子__ を使って、__文字列を結合__ することができるプログラム言語[^2]であれば、上記の判定を行う  __条件式__ を、__別のアルゴリズム__ で記述することができるので、その方法を紹介します。

例えば、〇 が __(0, 0)、(1, 0)、(2, 0)__ の 3 つのマスに __並んでいる__ 場合、__`self.board[0][0]`__ と __`self.board[1][0]`__ と __`self.board[2][0]`__ には、__`Marubatsu.CIRCLE`__ に代入された __`"o"`__ という文字列が __代入__ されています。従って、この __3 つ__ を __`+` 演算子で結合__ すると、__`Marubatsu.CIRCLE` + `Marubatsu.CIRCLE` + `Marubatsu.CIRCLE`__、すなわち __`"ooo"`__ という __文字列が代入__ されているはずです。また、`Marubatsu.CIRCLE` を __3 つ結合__ した文字列は、__`Marubatsu.CIRCLE * 3`__ と記述できます。

上記の事から、__`player` のマーク__ が __(0, 0)、(1, 0)、(2, 0)__ の 3 つのマスに __並んでいる__ ことを __判定__ する __条件式__ は、下記のプログラムのように記述することができます。

```python
self.board[0][0] + self.board[1][0] + self.board[2][0] == player * 3
```

下記は、この方法で `is_winner` を修正したプログラムです。

```python
def is_winner(self, player):
    # player が勝利していることを表す条件式の計算結果を返す
    return self.board[0][0] + self.board[1][0] + self.board[2][0] == player * 3 or \
           self.board[0][1] + self.board[1][1] + self.board[2][1] == player * 3 or \
           self.board[0][2] + self.board[1][2] + self.board[2][2] == player * 3 or \
           self.board[0][0] + self.board[0][1] + self.board[0][2] == player * 3 or \
           self.board[1][0] + self.board[1][1] + self.board[1][2] == player * 3 or \
           self.board[2][0] + self.board[2][1] + self.board[2][2] == player * 3 or \
           self.board[0][0] + self.board[1][1] + self.board[2][2] == player * 3 or \
           self.board[2][0] + self.board[1][1] + self.board[0][2] == player * 3

Marubatsu.is_winner = is_winner
```

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

```diff_python
def is_winner(self, player):
    # player が勝利していることを表す条件式の計算結果を返す
-   return self.board[0][0] == self.board[1][0] == self.board[2][0] == player or \
+   return self.board[0][0] + self.board[1][0] + self.board[2][0] == player * 3 or \
-          self.board[0][1] == self.board[1][1] == self.board[2][1] == player or \
+          self.board[0][1] + self.board[1][1] + self.board[2][1] == player * 3 or \
-          self.board[0][2] == self.board[1][2] == self.board[2][2] == player or \
+          self.board[0][2] + self.board[1][2] + self.board[2][2] == player * 3 or \
-          self.board[0][0] == self.board[0][1] == self.board[0][2] == player or \
+          self.board[0][0] + self.board[0][1] + self.board[0][2] == player * 3 or \
-          self.board[1][0] == self.board[1][1] == self.board[1][2] == player or \
+          self.board[1][0] + self.board[1][1] + self.board[1][2] == player * 3 or \
-          self.board[2][0] == self.board[2][1] == self.board[2][2] == player or \
+          self.board[2][0] + self.board[2][1] + self.board[2][2] == player * 3 or \
-          self.board[0][0] == self.board[1][1] == self.board[2][2] == player or \
+          self.board[0][0] + self.board[1][1] + self.board[2][2] == player * 3 or \
-          self.board[2][0] == self.board[1][1] == self.board[0][2] == player
+          self.board[2][0] + self.board[1][1] + self.board[0][2] == player * 3
```
</details>


下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

:::note
条件式の中に `player * 3` を何度も記述するのは効率が悪いので、下記のプログラムのように、先に `player * 3` の計算結果を変数に代入するという方法もあります。

```python
def is_winner(self, player):
    wintext = player * 3
    # player が勝利していることを表す条件式の計算結果を返す
    return self.board[0][0] + self.board[1][0] + self.board[2][0] == wintext or \
           self.board[0][1] + self.board[1][1] + self.board[2][1] == wintext or \
           self.board[0][2] + self.board[1][2] + self.board[2][2] == wintext or \
           self.board[0][0] + self.board[0][1] + self.board[0][2] == wintext or \
           self.board[1][0] + self.board[1][1] + self.board[1][2] == wintext or \
           self.board[2][0] + self.board[2][1] + self.board[2][2] == wintext or \
           self.board[0][0] + self.board[1][1] + self.board[2][2] == wintext or \
           self.board[2][0] + self.board[1][1] + self.board[0][2] == wintext

Marubatsu.is_winner = is_winner
```

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

```diff_python
def is_winner(self, player):
+   wintext = player * 3
    # player が勝利していることを表す条件式の計算結果を返す
-   return self.board[0][0] + self.board[1][0] + self.board[2][0] == player * 3 or \
+   return self.board[0][0] + self.board[1][0] + self.board[2][0] == wintext or \
-          self.board[0][1] + self.board[1][1] + self.board[2][1] == player * 3 or \
+          self.board[0][1] + self.board[1][1] + self.board[2][1] == wintext or \
-          self.board[0][2] + self.board[1][2] + self.board[2][2] == player * 3 or \
+          self.board[0][2] + self.board[1][2] + self.board[2][2] == wintext or \
-          self.board[0][0] + self.board[0][1] + self.board[0][2] == player * 3 or \
+          self.board[0][0] + self.board[0][1] + self.board[0][2] == wintext or \
-          self.board[1][0] + self.board[1][1] + self.board[1][2] == player * 3 or \
+          self.board[1][0] + self.board[1][1] + self.board[1][2] == wintext or \
-          self.board[2][0] + self.board[2][1] + self.board[2][2] == player * 3 or \
+          self.board[2][0] + self.board[2][1] + self.board[2][2] == wintext or \
-          self.board[0][0] + self.board[1][1] + self.board[2][2] == player * 3 or \
+          self.board[0][0] + self.board[1][1] + self.board[2][2] == wintext or \
-          self.board[2][0] + self.board[1][1] + self.board[0][2] == player * 3
+          self.board[2][0] + self.board[1][1] + self.board[0][2] == wintext
           
Marubatsu.is_winner = is_winner
```
</details>

:::

# `is_winner` のアルゴリズム その 2 （データの分離と繰り返し処理）

__`is_winner`__ では、__条件式の中__ に、__マスの座標__ を表すデータを __直接記述__ していますが、__`test_judge`__ の中で __着手__ を行うための __座標データ__ を、`test_judge` の中の着手を行うプログラムから __分離__ したように、`is_winner` においても、マスの座標を表す __データ__ を __分離__ する方法が考えられます。

## 条件式からのデータの分離

__条件式__ の中から __データ__ を __分離__ するためには、どのような __データ__ が条件式に __記述__ されているかを __考える__ 必要があります。下記は、`is_winner` の中の条件式の最初の行を抜粋したものですが、この中の __データ__ は、__`self.board`__ の __インデックス__ である `0`、`0`、`1`、`0`、`2`、`0` の __6 つ__ です。

```python
self.board[0][0] == self.board[1][0] == self.board[2][0] == player
```

この 6 つのデータを __list で表現__ すると、下記のようになります

```python
[ 0, 0, 1, 0, 2, 0 ]
```

下記のプログラムは、__このデータ__ を __使って__ 上記の __条件式を記述__ したものです。1 行目は、[以前の記事](https://qiita.com/ysgeso/items/51c2eba867aa560808c6#%E5%8F%8D%E5%BE%A9%E5%8F%AF%E8%83%BD%E3%82%AA%E3%83%96%E3%82%B8%E3%82%A7%E3%82%AF%E3%83%88%E3%81%AE%E5%B1%95%E9%96%8B) で説明した、反復可能オブジェクトの __展開__ を使って、__6 つ__ の list の __要素__ を、__6 つの変数__ に __代入__ しています。2 行目では、その __変数を使って__ 条件式を __修正__ しています。

```python
x1, y1, x2, y2, x3, y3 = [ 0, 0, 1, 0, 2, 0 ]
self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player
```

:::note
6 つのデータは、__3 組__ の __座標__ を表すデータなので、下記のように、__座標__ を表す 2 つのデータを __list で表現__ することで、__全体__ を __2 次元配列__ を表す __list で表現__ することもできます。

```python
[ [0, 0], [1, 0], [2, 0] ]
```

__2 次元以上__ 配列を表すの __list の要素__ を __展開__ によって __個別の変数__ に __代入__ する場合は、下記のプログラムのように、代入文の __右辺の list__ と __同じ構造__ で代入文の __左辺を記述__ します。代入文の __左辺の中__ に記述された __変数__ に、__対応__ する __右辺の要素の値__ が __代入__ されます。

```python
[[x1, y1], [x2, y2], [x3, y3]] = [[0, 0], [1, 0], [2, 0]]
:::

__元の条件式__ には、このようなデータが __8 つ__ あるので、それを __list で表現__ すると、下記のプログラムのような __2 次元配列__ を表す __list__ になります。このデータは、勝利の __判定__（judge）を行うための __座標__（coordinates）の __リスト__（list）なので、__`judge_coords_list`__ という __変数に代入__ します。

```python
judge_coords_list = [
    [ 0, 0, 1, 0, 2, 0 ],
    [ 0, 1, 1, 1, 2, 1 ],
    [ 0, 2, 1, 2, 2, 2 ],
    [ 0, 0, 0, 1, 0, 2 ],
    [ 1, 0, 1, 1, 1, 2 ],
    [ 2, 0, 2, 1, 2, 2 ],
    [ 0, 0, 1, 1, 2, 2 ],
    [ 2, 0, 1, 1, 0, 2 ],
]
```

## for 文を使った `is_winner` の記述

このデータを使って、__`is_winner`__ を下記プログラムのように __for 文__ を使って __記述__ できます。

1 行目の for 文は、上記のデータを __順番に取り出し__ て __`x1`__ ~ __`y3`__ の __6 つの変数に代入__ し、2、3 行目の for 文のブロックの処理を実行するという __繰り返し処理__ を行います。

2 行目は、__取り出したすべてのマス__ に、__`player`__ の __マークが並んでいるか__ どうかを __判定__ します。

```python
for x1, y1, x2, y2, x3, y3 in judge_coords_list:
    if self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player:
        return True

return False
```

〇×ゲームでは、8 種類ある __いずれか__ の 1 直線上に __同じマークが並べば__、__その時点で__ そのマークのプレイヤーの __勝利が決まります__。従って、8 種類を調べる __途中__ で `player` の __勝利が決まった場合__ は、__残りを調べる__ 必要は __ありません__。__return 文__ を実行すると、関数の __ブロックの処理__ が __その時点で終了__ するので、3 行目に __`return True` を記述__ することで、1 行目の for 文の __繰り返し処理__ の __途中__ であっても、__`player` の勝利と判定__ した時点で __残り__ の __繰り返し処理__ は __行われません__。

`player` のマークが一直線上に __配置されている__ 場合は、3 行目の __return 文__ によって __関数の処理が終了__ するので、for 文の __繰り返し処理__ が __終了する__ ことは __ありません__。

逆に、`player` のマークが __一直線上__ に __配置されていない__ 場合は、1 ~ 3 行目の for 文の __繰り返しの処理__ で、__2 行目の条件式__ が __`True` になる__ ことは __ありません__。そのような場合は、3 行目の __return 文__ が __実行__ されることは __無い__ ので、for 文の __繰り返し__ が __必ず終了__ します。

このことから、__for 文の繰り返し処理の後__ に記述された __処理__ は、__`player`__ が __勝利していない__ 場合 __のみ実行__ されます。従って、__`player`__ が __勝利していない__ ことを表す __`return False`__ を __for 文の繰り返し処理の後__ の 5 行目に __記述__ しています。

下図は、このプログラムのフローチャートです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b6eeb679-a9fd-267f-c9a8-352d5fccfd2b.png" width="700">

:::note
__`is_winner` の微修正__ の場合と同様に、__2、3 行目__ を下記のプログラムのように記述すれば良いと思う人がいるかもしれませんが、そのように記述すると __バグが発生__ します。

```python
for x1, y1, x2, y2, x3, y3 in judge_coords_list:
    return self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player
```

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

```diff_python
for x1, y1, x2, y2, x3, y3 in judge_coords_list:
-   if self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player:
-       return True
+   return self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player
```
</details>

バグの原因は、上記のように記述すると、1 行目の __for 文__ の __最初__ の __繰り返し処理__ で、__必ず return 文が実行__ されるため、__2 つ目以降__ の __繰り返し処理__ が決して __行われない__ からです。

例えば、ゲーム盤の __一番上の行以外__ で `player` のマークが __一直線上に配置__ されていた場合、__最初__ の for 文の __繰り返し__ で __(0, 0)__、__(1, 0)__、__(2, 0)__ のマスに `player` のマークが __配置されていない__ ため、__その時点__ で __`False` が返され__ てしまいます。
:::

下記のプログラムが、修正後の `is_winner` です。

```python
def is_winner(self, player):
    # 一直線上のマスの座標を表すデータを集めた list
    judge_coords_list = [
        [ 0, 0, 1, 0, 2, 0 ],
        [ 0, 1, 1, 1, 2, 1 ],
        [ 0, 2, 1, 2, 2, 2 ],
        [ 0, 0, 0, 1, 0, 2 ],
        [ 1, 0, 1, 1, 1, 2 ],
        [ 2, 0, 2, 1, 2, 2 ],
        [ 0, 0, 1, 1, 2, 2 ],
        [ 2, 0, 1, 1, 0, 2 ],
    ]

    # 一直線上のマスの座標を順番に取り出す繰り返し処理
    for x1, y1, x2, y2, x3, y3 in judge_coords_list:
        # 取り出した一直線上のマスに player が配置されているかどうかを判定する
        if self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player:
            # 並んでいれば player の勝利なので True を返す
            return True

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

Marubatsu.is_winner = is_winner
```

下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

__修正前__ のプログラムでは、__`self.board[0][0]`__ のように、`self.board` のような座標データ __以外__ の __記述__ と、__座標データ__ の __記述__ が __混在__ していますが、__修正後__ のプログラムでは、__座標データ__ が __一か所__ に __まとめられている__ ので、__座標データ__ を __記述__、__修正__ する際に、__座標データ__ の事 __だけ__ に __集中__ して __効率よく__ プログラムを __記述__ することができます。

# `is_winner` のアルゴリズム その 3 （繰り返しを使った一直線上の並びの判定）

これまでの __`is_winner`__ の __条件式__ には、__その中__ に 3 つの __一直線上のマス__ を表す __`self.board` の要素__ を __直接記述__ していました。〇×ゲームのように、一直線上のマスの数が __3 つしかない__ 場合は、そのような条件式を __記述__ するのはそれほど __大変ではありません__ が、例えばもっと __大きなゲーム盤__ のゲームで、一直線上のマスの数が 9 つの場合に、その一直線上に同じマークが並ぶことを判定する __条件式__ は、下記のように `self.board` の要素を __9 つも記述__ する必要があるため、__記述が大変__ です。

```python
self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == \
self.board[x4][y4] == self.board[x5][y5] == self.board[x6][y6] == \
self.board[x7][y7] == self.board[x8][y8] == self.board[x9][y9] == player
```

__他にも__、元の条件式では、__4 * 4__ の 〇×ゲームのような、__3 つ以外__ の一直線上のマスに同じマークが並んだ場合を __判定__ することが __できない__ という __欠点__ があります。

このような欠点を解消する方法として、__特定の数__ の一直線上のマスに __同じマークが配置__ されていることを、for 文による __繰り返し処理__ で __判定__ するというアルゴリズムがあります。

## アルゴリズムの説明

具体的には以下のようなアルゴリズムで判定を行います。

1. 一直線上のマスの __座標__ を __順番に取り出す__
2. __取り出した座標のマス__ に、__`player`__ のマークが __配置されているかどうか__ を __調べる__
__配置されていなければ__ 一直線上に __並んでいない__ ことが __確定__ し、__処理を終了__ する
3. まだ __マスが残っていれば__ 手順 1 へ __戻る__
4. __一直線上__ のマスに __`player`__ のマークが __配置__ されていることが __確定__ する

__この処理__ を、`is_winner` の中に記述しても構いませんが、__関数で定義__ したほうがプログラムが __わかりやすく__ なったり、__この処理__ をプログラムの __様々な場所から利用__ できるようになるので、関数で定義する事にします。

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

* __処理__：__実引数__ で指定した __すべてのマスに__、__実引数__ で指定した __マークが配置__ されているかどうかを __調べる__
* __名前__：指定したマスに __同じ__（same）マークが配置されているかを判定するので、__`is_same`__ とする
* __入力__：__仮引数 `coords`__ で __マスの座標の list__ を、__仮引数 `mark`__ で __マークの情報__ を受け取る
* __出力__：`corrds` で指定された __すべてのマス__ に `mark` のマークが __配置されている場合__ は __`True`__ を、__そうでなければ `False`__ を __返す__

__`coords`__ には、__一直線上__ に並んだ __マスの座標__ を __代入__ する必要があるので、例えば (0, 0)、(1, 0)、(2, 0) の場合は `[[0, 0], [1, 0], [2, 0]]` という __2 次元配列の list__ を __代入__ することにします。

## `is_same` の実装

`is_same` は、先程のアルゴリズムを使って下記のプログラムのように定義することができます。

```python
1  def is_same(self, coords, mark):
2      for x, y in coords:
3          if self.board[x][y] != mark:
4              return False
5
6      return True
7
8  Marubatsu.is_same = is_same
```

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

```python
def is_same(self, coords, mark):
    for x, y in coords:
        if self.board[x][y] != mark:
            return False
    return True

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

2 行目の for 文で、__`coords`__ の先頭の要素から __順番に座標を取り出し__、__`x` と `y`__ に __代入__ するという __繰り返し処理__ を行います。

3 行目では、__(x, y)__ のマスに __`mark`__ のマークが __配置されているか__ どうかを __判定__ し、__配置されていなければ__、`coords` が指定する __一直線上__ に __配置されていない__ ことが __確定__ するので 4 行目の __return 文__ によって __`False` を返し__、__関数の処理を終了__ します。

`mark` のマークが一直線上に __配置されていない__ 場合は、__必ず__ 4 行目の __return 文 が実行__ されるので、__for 文__ の繰り返し処理の __後で記述__ された __処理__ が __実行される__ ことは決して __ありません__。

逆に、`mark` のマークが __一直線上__ に __配置されている__ 場合は、2 ~ 4 行目の for 文の __繰り返しの処理__ で、__3 行目の条件式__ が __`True` になる__ ことは __ありません__。そのような場合は、4 行目の __return 文__ が __実行__ されることは __無い__ ので、for 文の __繰り返し__ が __必ず終了__ します。

このことから、__for 文の繰り返し処理の後__ に記述された __処理__ は、`mark` のマークが一直線上に __配置されている__ 場合 __のみ実行__ されます。従って、`mark` のマークが一直線上に __配置されている__ ことを表す、__`return True`__ を __for 文の繰り返し処理の後__ の 6 行目に __記述__ しています。

下図は、このプログラムのフローチャートです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/94df66c1-aa88-4644-bfff-6a7d3de80f02.png" width="700">

上記の説明と、フローチャートを見て、先程の `is_winner` のアルゴリズム その 2 で紹介したプログラムに __似ている__ と思った方が多いのではないかと思いますが、__実際に似ています__。

その 2 のアルゴリズムは、__いずれか一つ__ の条件が __満たされている__ ことを、__繰り返し処理__ で __判定__ するアルゴリズムです。

一方、その 3 のアルゴリズムは __その逆__ で、__すべての条件__ が __満たされている__ ことを __繰り返し処理__ で __判定__ するアルゴリズムです。

従って、その 2 と その 3 のプログラムは、if 文の __条件式__ の __`==` と `!=`__、__return 文__ で返す __`True` と `False`__ が __逆__ になっている __以外__ は、__同じ構造の処理__ を行っています。

下記は、その 2 と その 3 のフローチャートを並べたものです。分かりやすいように、その 3 では、その 2 と __逆__ になっている __部分__ の __背景を水色で表記__ しましたので、__見比べて確認__ して下さい。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/b6eeb679-a9fd-267f-c9a8-352d5fccfd2b.png" width="375">

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3524802/94df66c1-aa88-4644-bfff-6a7d3de80f02.png" width="375">

## `is_same` を使った `is_winner` の記述

`is_same` を使って、`is_winner` を以下のように記述することができます。その 2 の `is_winner` から修正した部分は以下の通りです。

* __`judge_coords_list`__ の __データ構造__ を、__`is_same`__ の導入に __合わせて修正__ した
* for 文の中で、__`judge_coords_list`__ から __取り出したデータ__ を __`coords`__ という __一つの変数に代入__ するようにした
* for 文の中で記述していた __if 文の条件式__ を、__`is_same`__ メソッドを使うように修正した

```python
def is_winner(self, player):
    # 一直線上のマスの座標を表すデータを集めた list
    judge_coords_list = [
        [ [0, 0], [1, 0], [2, 0] ],
        [ [0, 1], [1, 1], [2, 1] ],
        [ [0, 2], [1, 2], [2, 2] ],
        [ [0, 0], [0, 1], [0, 2] ],
        [ [1, 0], [1, 1], [1, 2] ],
        [ [2, 0], [2, 1], [2, 2] ],
        [ [0, 0], [1, 1], [2, 2] ],
        [ [2, 0], [1, 1], [0, 2] ],
    ]

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

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

Marubatsu.is_winner = is_winner
```

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

```diff_python
def is_winner(self, player):
    # 一直線上のマスの座標を表すデータを集めた list
    judge_coords_list = [
-       [ 0, 0, 1, 0, 2, 0 ],
-       [ 0, 1, 1, 1, 2, 1 ],
-       [ 0, 2, 1, 2, 2, 2 ],
-       [ 0, 0, 0, 1, 0, 2 ],
-       [ 1, 0, 1, 1, 1, 2 ],
-       [ 2, 0, 2, 1, 2, 2 ],
-       [ 0, 0, 1, 1, 2, 2 ],
-       [ 2, 0, 1, 1, 0, 2 ],
+       [ [0, 0], [1, 0], [2, 0] ],
+       [ [0, 1], [1, 1], [2, 1] ],
+       [ [0, 2], [1, 2], [2, 2] ],
+       [ [0, 0], [0, 1], [0, 2] ],
+       [ [1, 0], [1, 1], [1, 2] ],
+       [ [2, 0], [2, 1], [2, 2] ],
+       [ [0, 0], [1, 1], [2, 2] ],
+       [ [2, 0], [1, 1], [0, 2] ],
    ]

    # 一直線上のマスの座標を順番に取り出す繰り返し処理
-   for x1, y1, x2, y2, x3, y3 in judge_coords_list:
+   for coords in judge_coords_list:
        # 取り出した一直線上のマスに player が配置されているかどうかを判定する
-       if self.board[x1][y1] == self.board[x2][y2] == self.board[x3][y3] == player:
+       if self.is_same(coords, player):
            # 並んでいれば player の勝利なので True を返す
            return True

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

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


下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

実例は示しませんが、この変更により、__ゲーム盤のサイズ__ を __4 * 4 に変更__ し、__`[[0, 0], [1, 0], [2, 0], [3, 0]]`__ のような判定を行うためのデータを用意すれば、__3 マス以外__ の一直線上に同じマークが並んだ場合に対しても __正しく判定__ を行うことが __できる__ ようになります。

:::note
`judge_coords_list` のデータを、__テストケース__で __座標を記述__ した場合と __同様__ に、下記のような __Excel 座標__ で記述することもできます。

```python
    judge_coords_list = [
        "A1,B1,C1",
        "A2,B2,C2",
        "A3,B3,C3",
        "A1,A2,A3",
        "B1,B2,B3",
        "C1,C2,C3",
        "A1,B2,C3",
        "C1,B2,A3",
    ]
```

このように記述した場合は、__`is_same`__ を下記のプログラムのように __修正__ します。

* __2 行目__：__`split` メソッド__ を使って、`coords` を __Excel 座標__ を __要素__ とする __list に変換__ する
* __3 行目__：__`excel_to_xy`__ を使って、__Excel 座標__ から、__x 座標__ と __y 座標__ を __計算__ する

```python
1  def is_same(self, coords, mark):
2      for coord in coords.split(","):
3          x, y = excel_to_xy(coord)
4          if self.board[x][y] != mark:
5              return False
6      return True
7
8  Marubatsu.is_same = is_same
```

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

```python
def is_same(self, coords, mark):
    for coord in coords.split(","):
        x, y = excel_to_xy(coord)
        if self.board[x][y] != mark:
            return False
    return True

Marubatsu.is_same = is_same

```
</details>

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

```diff_python
def is_same(self, coords, mark):
-   for coord in coords:
+   for coord in coords.split(","):
+       x, y = excel_to_xy(coord)
        if self.board[x][y] != mark:
            return False
    return True

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


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

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

# `is_winner` のアルゴリズム その 4 （データを計算で作り出す）

その 3 の方法では、__プログラムの中__ に __直接__ `judge_coords_list` のような、__判定__ を行うために __利用するデータ__ を __記述__ する __必要__ があります。このような方法では、判定を行うために利用する __データの数__ が __増えた場合__ は、__データを記述__ するのが __大変__ です。そこで、次は、判定を行うために利用する __データ__ を __プログラムで作成__ するアルゴリズムを紹介します。

判定を行うために利用する __データ__ を __プログラムで作成__ するためには、それらの __データの性質__ を __理解__ する __必要__ があります。どのような性質があるかについて __考えてみて下さい__。

## 判定を行うために利用するデータの性質

〇×ゲームでは、一直線上に並んだ座標は、下記の __3 種類に分類__ することができます。

* __横方向__ に並ぶ場合
* __縦方向__ に並ぶ場合
* __斜め方向__ に並ぶ場合

まず、__横方向__ に並ぶ場合の性質から考えます。どのような性質があるかについて考えてみて下さい。

### 横方向に並ぶ座標の性質と作成

横方向に並ぶ座標には以下のような性質があります。

1. どの座標も __y 座標__ は __すべて同じ__ である
2. 横方向に並ぶ座標の __中__ の __座標の数__ は、ゲーム盤の __列の数__ だけ存在し、それぞれの __x 座標__ は __`0`、`1`、・・・、`ゲーム盤の列の数 - 1`__ である。例えば、〇×ゲームの場合で、y 座標が 0 の場合は、(0, 0)、(1, 0)、(2, 0) となる
3. 横方向に並ぶ座標の __種類__ は、ゲーム盤の __行の数__ だけ存在し、それぞれの __y 座標__ は __`0`、`1`、・・・、`ゲーム盤の行の数 - 1`__ である。例えば 〇×ゲームの場合は、「(0, 0)、(1, 0)、(2, 0)」、「(0, 1)、(1, 1)、(2, 1)」、「(0, 2)、(1, 2)、(2, 2)」の __3 種類__ である

__2 番目の性質__ から、__y 座標が 0 の場合__ の横方向に並ぶ座標は、__for 文__ による __繰り返し処理__ を使った下記のプログラムで作成することができます。

```python
coords = []
for x in range(3):
    coords.append([x, 0])
print(coords)
```
実行結果
```
[[0, 0], [1, 0], [2, 0]]
```

また、上記のプログラムは、__[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)__ を使って下記のように __簡潔に記述__ できます。

```python
coords = [[x, 0] for x in range(3)]
print(coords)
```
実行結果
```
[[0, 0], [1, 0], [2, 0]]
```

__3 番目の性質__ から、__横方向に並ぶ座標__ は、__for 文__ による __繰り返し処理__ を使った下記のプログラムで作成することができます。

```python
judge_coords_list = []
for y in range(3):
    judge_coords_list.append([[x, y] for x in range(3)])
print(judge_coords_list)
```
実行結果
```
[[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]]]
```

:::note
上記のプログラムは、list 内包表記を使って下記のように記述できます。ただし、下記のプログラムは __わかりづらい__ 点と、__この後__ で縦方向や斜め方向に並ぶ座標を __追加する際__ に list 内包表記を __使うことはできない__ ので、採用しないことにします。

```python
judge_coords_list = [[[x, y] for x in range(3)] for y in range(3)]
print(judge_coords_list)
```
実行結果
```
[[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]]]
```
:::

### 縦方向に並ぶ座標の作成

__縦方向__ に並ぶ座標の __性質__ は、__横方向__ に並ぶ座標の __性質__ の __x 座標__ と __y 座標__ を __入れ替えた__ ものです。従って、__縦方向__ に並ぶ座標の __作成__ は、__先程__ のプログラムの __`x` と `y`__ を __入れ替える__ ことで、下記のプログラムのように記述できます。なお、__入れ替える__ のは、__for__ の __直後__ の `x` と `y` __だけ__ で、__`[x, y]`__ の `x` と `y` を __入れ替えてはいけない__ 点に注意して下さい。__分かりづらい__ と思った方は、__横方向__ に並ぶ座標の作成の説明と __同様の手順__ で、__順を追って__ プログラムを __作成__ してみて下さい。

```python
judge_coords_list = []
for x in range(3):
    judge_coords_list.append([[x, y] for y in range(3)])
print(judge_coords_list)
```

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

```diff_python
-for y in range(3):
+for x in range(3):
-   judge_coords_list.append([[x, y] for x in range(3)])
+   judge_coords_list.append([[x, y] for y in range(3)])
```
</details>

実行結果
```
[[[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]]]
```

:::note
__すべて__ の `x` と `y` を __入れ替え__ ては __いけない理由__ は、__入れ替える前__ と __全く同じ処理__ が行われてしまうからです。例えば、下記のプログラムの 1 ~ 3 行目と、4 ~ 6 行目は、__`a` と `b` を入れ替えた__ プログラムですが、3 行目と 6 行目は、どちらも __同じ計算結果__ が表示されます。

```python
1  a = 1
2  b = 2
3  print(a * 3 + b)
4  b = 1
5  a = 2
6  print(b * 3 + a)
```

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

```python
a = 1
b = 2
print(a * 3 + b)
b = 1
a = 2
print(b * 3 + a)
```
</details>

実行結果
```
5
5
```

一方、下記のプログラムのように、__式__ のほう __ではなく__、__データだけ__ を __入れ替えた__ 場合は、__異なる計算__ が行われます。

```python
a = 1
b = 2
print(a * 3 + b)
b = 1
a = 2
print(a * 3 + b)
```

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

```diff_python
a = 1
b = 2
print(a * 3 + b)
b = 1
a = 2
-print(b * 3 + a)
+print(a * 3 + b)
```
</details>

実行結果
```
5
7
```
:::

上記のプログラムは、__縦方向__ の座標 __のみ__ を作成するので、__横方向__ の座標と __合わせる__ 場合は、下記のプログラムのように __最初の行__ で、__`judge_coords_list`__ に __空の list__  を __代入__ し、その後で __横方向__ の座標と __縦方向__ の座標を __作成__ して `judge_coords_list` に __追加__ します。

```python
judge_coords_list = []
# 横方向の座標を追加する
for y in range(3):
    judge_coords_list.append([[x, y] for x in range(3)])
# 縦方向の座標を追加する
for x in range(3):
    judge_coords_list.append([[x, y] for y in range(3)])
print(judge_coords_list)
```
実行結果
```
[[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]], [[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]]]
```

### 斜め方向に並ぶ座標の作成

__斜め方向__ に並ぶ座標は、横や縦方向と __性質が異なり__ ます。その性質について考えてみて下さい。

斜め方向に並ぶ座標は、__左上から右下__ 方向と、__右上から左下__ 方向の 2 種類があります。

まず、__左上から右下__ 方向の __性質__ について考えてみます。性質が __わかりづらい__ と思った方は __座標を実際に記述__ してみることをお勧めします。〇×ゲームの左上から右下方向の場合の座標は __(0, 0)、(1, 1)、(2, 2)__ です。一見すればすぐに下記の性質がある事がわかると思います。

1. __どの座標__ も __x 座標と y 座標__ は __同じ__ である
2. __座標の数__ は、ゲーム盤の __列の数__ だけ存在し、それぞれの x 座標は `0`、`1`、・・・、`ゲーム盤の列の数 - 1` である

従って、左上から右下方向の座標は、下記のプログラムで作成することができます。

```python
coords = [[x, x] for x in range(3)]
print(coords)
```
実行結果
```
[[0, 0], [1, 1], [2, 2]]
```

:::note
上記の性質 2 は、下記のように考えることもできます。

__座標の数__ は、ゲーム盤の __行の数__ だけ存在し、それぞれの y 座標は `0`、`1`、・・・、`ゲーム盤の行の数 - 1` である

上記のように考えた場合は、左上から右下方向の座標は、下記のプログラムのように記述します。どちらでも計算結果は同じなので、分かりやすいと思ったほうを採用して下さい。

```python
coords = [[y, y] for y in range(3)]
print(coords)
```
実行結果
```
[[0, 0], [1, 1], [2, 2]]
```
:::


次に、__右上から左下__ 方向の性質について考えてみます。先程と同様に 〇×ゲームの場合の __座標を記述__ すると __(2, 0)、(1, 1)、(0, 2)__ のようになります。この場合の性質は少し __わかりづらい__ かもしれませんが、ゲーム盤の __サイズを増やすこと__ でその性質が __わかりやすくなる__ ので __記述__ してみます。ゲーム盤の __サイズが 5 * 5__ の場合は、__(4, 0)、(3, 1)、(2, 2)、(1, 3)、(0, 4)__ となります。よく見ると、__どの座標__ も、__x 座標と y 座標の合計__ が __4__ になることがわかります。この 4 が __`ゲーム盤の行の数 - 1`__ であることに __気が付く__ ことができれば、以下の性質があることがわかるようになります。

1. __どの座標__ も __x 座標と y 座標の合計__ は、__`ゲーム盤の行の数 - 1`__ である
2. __座標の数__ 、ゲーム盤の __行の数__ だけ存在し、それぞれの y 座標は `0`、`1`、・・・、`ゲーム盤の行の数 - 1` である。

〇×ゲームの場合、__`ゲーム盤の行の数 - 1`__ は __`2`__ なので、x + y = 2 になるため、__x 座標__ は x = 2 - y という __式で計算__ することができます。

従って、右上から左下方向の座標は、下記のプログラムで作成することができます。

```python
coords = [[2 - y, y] for y in range(3)]
print(coords)
```
実行結果
```
[[2, 0], [1, 1], [0, 2]]
```

:::note
__x 座標__ を __基準__ に考えた場合は、下記のようになります。この場合は、先程と異なり、__左下から右上__ 方向の、__(0, 2)、(1, 1)、(2, 0)__ の順で座標が作成されます。

```python
coords = [[x, 2 - x] for x in range(3)]
print(coords)
```
実行結果
```
[[0, 2], [1, 1], [2, 0]]
```

__x 座標__ を __基準__ に、先程と同じ __右上から左下__ 方向で座標を作成したい場合は、下記のプログラムのように、__`range`__ から __取り出される値__ を __2 から 0__ まで __1 ずつ減らす__ ように __記述__ します。この __`range` の記述方法__ については、[以前の記事](https://qiita.com/ysgeso/items/6ca248133ff4d59a81d4#range-%E3%81%AE%E4%BD%BF%E3%81%84%E6%96%B9) を参照して下さい。なお、プログラムが __わかりづらい__ ので、わざわざ下記のように記述する __必要はない__ と思います。

```python
coords = [[x, 2 - x] for x in range(2, -1, -1)]
print(coords)
```
実行結果
```
[[2, 0], [1, 1], [0, 2]]
```

:::
### すべての一直線に並ぶ座標の作成

__すべて__ の __一直線に並ぶ座標__ は、上記を __あわせた__、下記のプログラムで作成することができます。

```python
judge_coords_list = []
# 横方向の座標を追加する
for y in range(3):
    judge_coords_list.append([[x, y] for x in range(3)])
# 縦方向の座標を追加する
for x in range(3):
    judge_coords_list.append([[x, y] for y in range(3)])
# 左上から右下方向の座標を追加する
judge_coords_list.append([[x, x] for x in range(3)])
# 右上から左下方向の座標を追加する
judge_coords_list.append([[2 - y, y] for y in range(3)])
print(judge_coords_list)
```
実行結果
```
[[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]], [[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]], [[0, 0], [1, 1], [2, 2]], [[2, 0], [1, 1], [0, 2]]]
```

:::note
__`x` と `y`__ の __意味がおかしくなる__ ことを __気にしない__ のであれば、__縦方向__ と、__横方向__ の座標を下記のプログラムのように、__1 つ__ の for 文で __まとめる__ ことができます。

まとめてもあまりプログラムが短くならず、分かりにくいので本記事では採用しません。

```python
judge_coords_list = []
for y in range(3):
    # 横方向の座標を追加する
    judge_coords_list.append([[x, y] for x in range(3)])
    # 縦方向の座標を追加する
    judge_coords_list.append([[y, x] for y in range(3)])
# 左上から右下方向の座標を追加する
judge_coords_list.append([[x, x] for x in range(3)])
# 右上から左下方向の座標を追加する
judge_coords_list.append([[2 - y, y] for y in range(3)])
print(judge_coords_list)
```
実行結果
```
[[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 1], [2, 1]], [[0, 2], [1, 2], [2, 2]], [[0, 0], [0, 1], [0, 2]], [[1, 0], [1, 1], [1, 2]], [[2, 0], [2, 1], [2, 2]], [[0, 0], [1, 1], [2, 2]], [[2, 0], [1, 1], [0, 2]]]
```
:::

## `is_winner` の修正

__上記__ のプログラムを __`is_winner`__ に __組み込む__ ことにします。その際に、上記のプログラムの中で記述した __`3`__ は、__ゲーム盤のサイズ__ を表すデータで、そのデータは、`Marubatsu` クラスのインスタンスの __`BOARD_SIZE` 属性__ に __代入__ されているので、__`3`__ を __`self.BOARD_SIZE`__ に __置き換える__ ことにします。

また、__右上から左下__ 方向の座標の追加の際に記述した __`2`__ は、__`ゲーム盤のサイズ - 1`__ なので、__`self.BOARD_SIZE - 1`__ に __置き換えます__。下記のプログラムはそのように修正したプログラムです。

```python
def is_winner(self, player):
    # 一直線上のマスの座標を表すデータを集めた list を代入する変数を空の list で初期化する
    judge_coords_list = []
    # 横方向の座標を追加する
    for y in range(self.BOARD_SIZE):
        judge_coords_list.append([[x, y] for x in range(self.BOARD_SIZE)])
    # 縦方向の座標を追加する
    for x in range(self.BOARD_SIZE):
        judge_coords_list.append([[x, y] for y in range(self.BOARD_SIZE)])
    # 左上から右下方向の座標を追加する
    judge_coords_list.append([[x, x] for x in range(self.BOARD_SIZE)])
    # 右上から左下方向の座標を追加する
    judge_coords_list.append([[self.BOARD_SIZE - 1 - y, y] for y in range(self.BOARD_SIZE)])

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

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

Marubatsu.is_winner = is_winner
```

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

```diff_python
def is_winner(self, player):
-   # 一直線上のマスの座標を表すデータを集めた list
-   judge_coords_list = [
-       [ [0, 0], [1, 0], [2, 0] ],
-       [ [0, 1], [1, 1], [2, 1] ],
-       [ [0, 2], [1, 2], [2, 2] ],
-       [ [0, 0], [0, 1], [0, 2] ],
-       [ [1, 0], [1, 1], [1, 2] ],
-       [ [2, 0], [2, 1], [2, 2] ],
-       [ [0, 0], [1, 1], [2, 2] ],
-       [ [2, 0], [1, 1], [0, 2] ],
-   ]
+    # 一直線上のマスの座標を表すデータを集めた list を代入する変数を空の list で初期化する
+   judge_coords_list = []
+   # 横方向の座標を追加する
+   for y in range(self.BOARD_SIZE):
+       judge_coords_list.append([[x, y] for x in range(self.BOARD_SIZE)])
+   # 縦方向の座標を追加する
+   for x in range(self.BOARD_SIZE):
+       judge_coords_list.append([[x, y] for y in range(self.BOARD_SIZE)])
+   # 左上から右下方向の座標を追加する
+   judge_coords_list.append([[x, x] for x in range(self.BOARD_SIZE)])
+   # 右上から左下方向の座標を追加する
+   judge_coords_list.append([[self.BOARD_SIZE - 1 - y, y] for y in range(self.BOARD_SIZE)])    

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

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

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


下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

# `is_winner` のアルゴリズム その 5 （差分で座標を計算する）

その 4 までの方法では、__一直線上の座標__ を __あらかじめ__ 記述もしくは計算し、それを `is_same` メソッドの __実引数に記述__ して判定を行いました。それに対し、__一直線上の座標__ を __計算するためのデータ__ を `is_same` メソッドの __実引数に記述__ し、`is_same` メソッドの __中__ で __そのデータを使って座標を計算する__ というアルゴリズムがあります。

## アルゴリズムの考え方

例えば、__横方向__ の座標の一つに __(0, 0)、(1, 0)、(2, 0)__ というデータがありますが、このデータは、__(0, 0) から始まり__、__x 座標__ を __1 つずつ増やす__ ことで __残りのデータを計算して作成__ することができます。

この性質は、__他の横方向__ の座標にも __当てはまります__。例えば、__(0, 1)、(1, 1)、(2, 1)__ というデータは、__(0, 1) から始まり__、__x 座標__ を __1 つずつ増やす__ ことで __残りのデータを計算して作成__ できます。

つまり、__横方向__ のデータは、__最初の座標__ と、__x 座標__ を __どれだけ増やす__ かという __情報__ があれば、__残りの座標__ のデータを __計算で作り出す__ ことが __できる__ ということです。

これは、__縦方向__ と、__斜め方向__ の座標にも __あてはまり__、__必要なデータ__ を __表__ にすると以下のようになります。なお、__次のデータ__ で __x 座標や y 座標__ が __どれだけ変化するか__ を表す __データ__ の事を、__差分__ と呼ぶので、表には __x 座標の差分__ のように表記しています。

| データの種類 | 最初の座標 | ｘ 座標の差分 | y 座標の差分 |
|:-:|:-:|:-:|:-:|
| 横方向のデータ  | (0, 0)<br>(0, 1)<br>(0, 2)  | 1  | 0  |
| 縦方向のデータ  | (0, 0)<br>(1, 0)<br>(2, 0)  | 0  | 1  |
| 左上から右下方向のデータ  | (0, 0)  | 1 | 1  |
| 右上から左下方向のデータ  | (2, 0)  | -1  | 1  |

## `is_same` の修正

まず、__最初の座標__ と、__x、y 座標の差分__ を使って判定を行うように `is_same` を下記のプログラムのように修正します。修正内容は以下の通りです。

* __1 行目__：__仮引数 `coords`__ を __最初の座標__ を代入する __`coord`__ と、__x 座標と y 座標の差分__ を代入する __`dx` と `dy`__ に __修正__ する。__仮引数の名前__ の __d__ は、__差分__ を表す __英単語__ の __difference__ の __頭文字__ である。仮引数 __`mark`__ は __変更しない__ が、__先頭に移動__ する（先頭に移動する理由は後述する）
* __2 行目__：__最初の座標__ から、__x 座標__ と __y 座標__ を取り出して __`x` と `y` に代入__ する
* __3 行目__：for 文による __繰り返しの処理__ を行う。__チェックする座標の数__ は、__ゲーム盤のサイズ__ と __等しい__ ので、__繰り返しの数__ を表す __反復可能オブジェクト__ には、__`range(self.BOARD_SIZE)`__ を記述する。なお、__繰り返しの数__ を __代入__ する __変数__ は、この繰り返しの __ブロックの中__ で __利用しない__ ので、__そのような値を代入__ する __変数名__ として、__慣習的に使われる__ __`_`__ を使用している[^3]
* __4、5 行目__：__(x, y)__ に __`mark` が配置__ されているかどうかを __判定__ し、__配置されていなければ `False` を返す__。なお、この部分は元と同じで、__修正していない__
* __6、7 行目__：__`x` に `dx`__、__`y` に `dy`__ を __加算__ することで、__次の座標を計算__ する。__計算後の値__ が、__次の繰り返し__ の __4 行目で使用__ される

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

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

```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

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

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

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

    return True

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

## 座標を作成するためのデータの作成

次に、__`is_winner`__ の中の __`judge_coords_list`__ の __データ構造__ を、__座標を作成__ するために __必要__ となる、__最初の座標__ と、__x と y 座標の差分__ のデータに __修正__ する必要があります。そのようなデータを list や tuple で表現することも可能ですが、__分かりやすさを重視__ して、本記事では、それぞれのデータを、下記のような __dict で表現__ することにします。

```python
{ "coord": [0, 0], "dx": 1, "dy": 0 }
```

__横方向__ の座標の __最初の座標__ の __x 座標は `0`__ で、__x 座標の差分__ は __`1`__、__y 座標の差分__ は __`0`__ なので、__横方向__ の座標データを __作成するために必要なデータ__ は、下記のプログラムで作成することができます。

なお、このデータを __代入__ する __変数の名前__ を、__データの意味__ に __合わせて`judge_data_list`__  に __変更__ しました。また、実行結果が __わかりやすく__ なるようにするために、[以前の記事](https://qiita.com/ysgeso/items/44884dcf168aab949508#%E3%82%AF%E3%83%A9%E3%82%B9%E3%81%AE%E5%90%8D%E5%89%8D%E7%A9%BA%E9%96%93%E3%81%AE%E7%A2%BA%E8%AA%8D) で紹介した __`pprint`__ で表示を行っています。

```python
from pprint import pprint

judge_data_list = []
# 横方向の座標を作成するために必要なデータを追加する
for y in range(3):
    judge_data_list.append({ "coord": [0, y], "dx": 1, "dy": 0 })
pprint(judge_data_list)
```
実行結果
```
[{'coord': [0, 0], 'dx': 1, 'dy': 0},
 {'coord': [0, 1], 'dx': 1, 'dy': 0},
 {'coord': [0, 2], 'dx': 1, 'dy': 0}]
```

__同様の方法__ で、__縦方向__ と __斜め方向__ の座標を作成するために必要なデータを合わせたもの、下記のプログラムで作成することができます。

```python
# 縦方向の座標を作成するために必要なデータを追加する
for x in range(3):
    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 })    
pprint(judge_data_list)
```
実行結果
```
[{'coord': [0, 0], 'dx': 1, 'dy': 0},
 {'coord': [0, 1], 'dx': 1, 'dy': 0},
 {'coord': [0, 2], 'dx': 1, 'dy': 0},
 {'coord': [0, 0], 'dx': 0, 'dy': 1},
 {'coord': [1, 0], 'dx': 0, 'dy': 1},
 {'coord': [2, 0], 'dx': 0, 'dy': 1},
 {'coord': [0, 0], 'dx': 1, 'dy': 1},
 {'coord': [2, 0], 'dx': -1, 'dy': 1}]
 ```

## `is_winner` の修正

`is_winner` は以下のプログラムのように修正します。

* __3 ~ 13 行目__：上記の __`judge_data_list`__ のデータを __作成する処理__ を記述するように修正する。13 行目の __右上から左下方向__ の __先頭の座標__ は、ゲーム盤の __右上の座標__ なので、__`[self.BOARD_SIZE - 1, 0]`__ と記述することができる
* __16 行目__：__`judge_data_list`__ から順番に __取り出したデータ__ を __`judge_data` に代入__ するという __繰り返し処理__ を行うように修正する
* __18 行目__：__`is_same`__ の __実引数__ を、__`judge_data` の属性__ を使って記述するように修正する

```python
 1  def is_winner(self, player):
 2      # 一直線上のマスの座標を作成するためのデータを集めた list を代入する変数を空の list で初期化する
 3      judge_data_list = []
 4      # 横方向の座標を作成するために必要なデータを追加する
 5      for y in range(self.BOARD_SIZE):
 6          judge_data_list.append({ "coord": [0, y], "dx": 1, "dy": 0 })
 7      # 縦方向の座標を作成するために必要なデータを追加する
 8      for x in range(self.BOARD_SIZE):
 9          judge_data_list.append({ "coord": [x, 0], "dx": 0, "dy": 1 })
10      # 左上から右下方向の座標を追加する
11      judge_data_list.append({ "coord": [0, 0], "dx": 1, "dy": 1 })
12      # 右上から左下方向の座標を追加する
13      judge_data_list.append({ "coord": [self.BOARD_SIZE - 1, 0], "dx": -1, "dy": 1 })     
14
15      # 一直線上のマスの座標作成するためのデータを順番に取り出す繰り返し処理
16      for judge_coords in judge_data_list:
17          # 取り出した一直線上のマスに player が配置されているかどうかを判定する
18          if self.is_same(player, judge_coords["coord"], judge_coords["dx"], judge_coords["dy"]):
19              # 並んでいれば player の勝利なので True を返す
20              return True
21
22      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
23      return False
24
25  Marubatsu.is_winner = is_winner
```

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

```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": [self.BOARD_SIZE - 1, 0], "dx": -1, "dy": 1 })     

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

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

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

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

```diff_python
def is_winner(self, player):
-   # 一直線上のマスの座標を表すデータを集めた list を代入する変数を空の list で初期化する
-   judge_coords_list = []
-   # 横方向の座標を追加する
-   for y in range(self.BOARD_SIZE):
-       judge_coords_list.append([[x, y] for x in range(self.BOARD_SIZE)])
-   # 縦方向の座標を追加する
-   for x in range(self.BOARD_SIZE):
-       judge_coords_list.append([[x, y] for y in range(self.BOARD_SIZE)])
-   # 左上から右下方向の座標を追加する
-   judge_coords_list.append([[x, x] for x in range(self.BOARD_SIZE)])
-   # 右上から左下方向の座標を追加する
-   judge_coords_list.append([[self.BOARD_SIZE - 1 - y, y] for y in range(self.BOARD_SIZE)])
+   # 一直線上のマスの座標を作成するためのデータを集めた 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": [self.BOARD_SIZE - 1, 0], "dx": -1, "dy": 1 })     

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

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

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

下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## 実引数に記述した dict の仮引数への展開

下記は、先程のプログラムの、18 行目のプログラムですが、このプログラムの __実引数__ で、__`judge_data`__ を __3 箇所に記述__ するのが __面倒__ だと思った人はいないでしょうか。

```python
if self.is_same(mark, judge_data["coord"], judge_data["dx"], judge_data["dy"]):
```

Python では、__dict の展開__ という __記法__ を利用することで、上記のプログラムを下記のように __簡潔に記述__ することができます。

```python
if self.is_same(mark, **judge_data):
```

__関数呼び出し__ の __実引数__ に、__dict を記述__ する際に、上記の __`**judge_data`__ のように、__先頭__ に __`**` を記述__ することで、dict の __それぞれ__ の「__属性名__ を __キーワード__」、「__属性の値__ を __キーワードの値__」とする __[キーワード引数](https://qiita.com/ysgeso/items/c5dbe62b329f7936181a#%E4%BD%8D%E7%BD%AE%E5%BC%95%E6%95%B0%E3%81%A8%E3%82%AD%E3%83%BC%E3%83%AF%E3%83%BC%E3%83%89%E5%BC%95%E6%95%B0)__ を記述した場合の処理が行われます。このことを、__dict の展開__ と呼びます。

例えば、関数の実引数として __`{ "coord": [0, 0], "dx": 1, "dy": 0 }`__ の前に、__`**` を記述__ して呼び出すと、__`coord=[0, 0]`__、__`dx=1`__、__`dy=0`__ という __3 つのキーワード引数__ が記述されたことになります。

具体例として、下記の 3 行目と 4 行目は __同じ処理__ を行うプログラムです。

```python
mb = Marubatsu()
judge_data = { "coord": [0, 0], "dx": 1, "dy": 0 }
print(mb.is_same(Marubatsu.CIRCLE, **judge_data))
print(mb.is_same(Marubatsu.CIRCLE, coord=[0, 0], dx=1, dy=0))
```
実行結果
```
False
False
```

なお、__dict の展開__ が行われると、__キーワード引数__ として __実引数が記述__ されるので、[以前の記事](https://qiita.com/ysgeso/items/c5dbe62b329f7936181a#%E4%BD%8D%E7%BD%AE%E5%BC%95%E6%95%B0%E3%81%A8%E3%82%AD%E3%83%BC%E3%83%AF%E3%83%BC%E3%83%89%E5%BC%95%E6%95%B0%E3%81%AE%E4%B8%A1%E6%96%B9%E3%82%92%E4%BD%BF%E3%81%86%E5%A0%B4%E5%90%88) で説明したように、__dict の展開__ は、__必ず位置引数より前に記述__ する必要があります。例えば、下記のように __位置引数__ の __`Marubatsu.CIRCLE` より後__ に、__dict の展開を記述__ すると __エラーが発生__ します。

__`is_same`__ の仮引数 __`mark`__ を __先頭に記述__ するようにしたのは、__そのため__ です。
```python
print(mb.is_same(**judge_data, Marubatsu.CIRCLE))
```
実行結果
```
  Cell In[44], line 1
    print(mb.is_same(**judge_data, Marubatsu.CIRCLE))
                                                   ^
SyntaxError: positional argument follows keyword argument unpacking
```

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

* __SyntaxError__
構文（文法のこと）（syntax）に関するエラー
* __positional argument follows keyword argument__
位置引数（positional argument）が、キーワード引数（keyword argument）の後（follows）に記述されている
:::

:::note warn
dict の展開を利用するためには、以下の点に注意する必要があります。

* dict の __キーの名前__ と、関数の __仮引数の名前__ を __一致させる__ 必要がある
* __すべて__ の __キーワード引数__ を __dict のキーの名前__ より __前に記述__ する必要がある
:::

先程の `is_winner` のプログラムの、18 行目のプログラムを修正し、下記のプログラムを実行することで、修正した `judge` メソッドで、すべてのテストケースで期待された処理が行われることが確認できます。実行結果は先程と同じなので省略します。

```python
test_judge()
```

## その 5 の方法の利点と欠点

その 5 の方法の __利点__ は、ゲーム盤の __サイズ__ が __極端に大きくなった場合__ でも __利用できる__ 点にあります。例えば、ゲーム盤の __サイズ__ が __1 億 * 1 億__[^4] の 〇×ゲームの場合、__一直線上に並ぶ座標__ は、__縦と横__ 方向で __1 億通りずつ__、__斜め__ 方向で __2 通り__ の、計 __2 億 2 通り__ あります。__それぞれ__ に対して、__1 億__ の __座標データ__ が __記録__ されるので、__全部__ で 約 2 億 * 1 億 = __約 2 京__ もの __座標データ__ が __必要__ となりますが、__現在__ の __一般的なコンピュータ__ でも、それだけのデータを __記憶することは困難__ でしょう。


一方、この方法であれば、一直線上に並ぶ __データ 1 つ__ につき、__座標データが 1 つ__ と __差分データが 2 つ__ ですむので、__その 4__ の方法で作成するデータと __比較__ して、__約 1 億分の 1__  のデータ量で済みます。 

なお、__その 4__ の方法の __欠点__ は、ゲーム盤のサイズが 100 や __1000 程度__ では __全く問題にならない__ ので、__〇×ゲーム__、将棋、囲碁程度のサイズのゲーム盤であれば __気にする必要は全くない__ でしょう。

この方法の __欠点__ としては、アルゴリズムが、その 4 の方法と比べて __抽象的__ になるので、__分かりづらくなる__ 点が挙げられます。他にも、__その 4__ の方法の場合は、__一度作成した座標データ__ を __何度も再利用する__（本記事では再利用はしていません） ことが可能ですが、__その 5__ の方法の場合は、__毎回__ すべての __座標データ__ を __計算する必要__ があるので、__計算速度__ が __若干遅くなる__[^5] という欠点があります。

なお、__`judge`__ メソッドの __処理__ は、最近の PC であれば、__1 ミリ秒__（1/1000 秒）__以下__ で __実行__ できるので、__〇×ゲーム__ を __人間が遊ぶ__ 場合は __その差__ を __気にする必要__ は全く __ありません__。 一方、〇×ゲームの __AI を作成__ する際には、`judge` メソッドなどの __処理速度__ が __重要__ になる場合があるので、__アルゴリズムの計算速度__ については、その際に説明する予定です。


# 本記事のまとめ

本記事では、`judge` メソッドの中の、〇 と × の勝利を判定する __様々なアルゴリズムを紹介__ しました。下記の表は、それぞれのアルゴリズムの __特長を簡単にまとめた__ ものです。

| アルゴリズム | 利点 | 欠点 |
|:-:|:-:|:-:|
| 修正前  | 初心者でも記述できる  | 記述が長い<br>入力ミスをしやすい  |
| その 1<br>（`+`演算子）| Python 以外の多くの言語でも記述できる  | 記述が長い<br>入力ミスをしやすい  |
| その 2<br> (データの分離）| データを記述しやすい<br>プログラムを短く記述できる  | データの量が多いと記述が大変  |
| その 3<br>（繰り返しの利用）  | その 2 の利点に加え、データを用意すれば、3 * 3 以外のゲーム盤にも対応できる  | データの量が多いと記述が大変  |
| その 4<br>（データの作成）  | 常に 3 * 3 のゲーム盤以外にも対応できる<br>データを記述する必要がない| プログラムが複雑  |
| その 5<br>（データを差分で作成） | その 4 の利点に加えて、非常に大きなゲーム盤でも利用できる  | プログラムが複雑<br>計算速度がその 4 より若干遅い |

:::note
__アルゴリズム__ は、__データ構造__ と __密接な関係__ があるので、〇×ゲームの __ゲーム盤__ のデータを、__別のデータ構造__ で表現した場合は、上記とは __異なるアルゴリズム__ を使う必要があります。別のデータ構造で〇×ゲームのゲーム盤を表現する方法と、その場合のアルゴリズムについては、〇×ゲームの AI を作成する際に紹介する予定です。
:::

次回の記事では、他の 〇と×の勝利を判定するアルゴリズムと、ゲーム盤のマスが埋まっていることを判定する他のアルゴリズムについて紹介します。


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

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

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

以下のリンクは、今回の記事で更新した marubatsu.py です。プログラムは、その 5 のものを記述しています。

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

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

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

# 次回の記事

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

# 更新履歴

| 更新日時 | 更新内容 |
|:--|:--|
| 2023/12/11 | `is_winner` の仮引数の名前を `winner` から `player` に修正しました |
| 2024/01/28 | `is_winner` の 13 行目の `[2, 0]` を `[self.BOARD_SIZE - 1, 0]` に修正しました |

[^1]:記述そのものは可能ですが、Python の場合とは __全く異なる計算__ が行われます
[^2]:C 言語など、__`+` 演算子__ を使って文字列の __結合を行う__ ことが __できない__ 言語が存在します
[^3]:別の名前に変更してもかまいませんが、`_` は良く使われるのでその意味は覚えておいて下さい
[^4]:1 億という極端な例が非現実的だと思う人がいるかもしれませんが、実際にそのような大量のデータを扱うプログラムは存在し、そのような場合は その 5 のアルゴリズムを使うことはできません
[^5]:具体的な方法については割愛しますが、筆者の PC で比較した所、その 4 より その 5 の `judge` メソッドのほうが、若干ですが、処理に時間がかかりました