目次と前回の記事

前回までのおさらい

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

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

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

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

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

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

前回までのおさらい

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

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

前回の記事の最後では、下記のプログラムのように、最初に一直線上のマスの座標を作成するための データを集めた list を作成し、その データを元 に 繰り返し処理 によって判定を行いました。

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

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

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

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

上記のプログラムでは、is_winner を 実行する際 に、横方向で 3 つ、縦方向で 3 つ、斜め方向で 2 つの、計 8 つ の要素を持つ judge_data_list を作成していますが、この方法では、ゲーム盤の サイズが大きくなった 際に、前回の記事で紹介したその 4 の方法ほどではありませんが、多くの要素 を持つ judge_data_list を 作成する必要 があります。

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

from marubatsu import Marubatsu

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

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

Marubatsu.is_winner = is_winner

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

from test import test_judge

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

このアルゴリズムの性質

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

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

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

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

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

プログラムの簡略化

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

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

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

Marubatsu.is_winner = is_winner

修正箇所

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

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

Marubatsu.is_winner = is_winner

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

test_judge()

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

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

下記のプログラムは、前回の記事で定義した is_same メソッドです。前回の記事ではそのように記述しませんでしたが、下記のプログラムを is_same のアルゴリズムその 1 と考えて下さい。

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

        return True

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

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

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

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

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

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

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

行番号のないプログラム

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

    return count == self.BOARD_SIZE

Marubatsu.is_same = is_same

修正箇所

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

-   return True
+   return count == self.BOARD_SIZE

Marubatsu.is_same = is_same

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

test_judge()

このアルゴリズムの性質

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

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

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

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

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

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

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

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

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

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

print(sum([1, 2, 3]))

実行結果

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

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

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

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

行番号のないプログラム

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

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same

修正箇所

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

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

Marubatsu.is_same = is_same

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

test_judge()

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

`sum` に関する注意点

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

print(sum(["1", "2", "3"]))

実行結果

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

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

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

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

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

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

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

合計を計算するためには、途中の計算結果 を記憶しておく 変数が必要 なので、上記のプログラムでは、2 行目で total という変数を 0 で初期化 し、4 行目で total に list から取り出したデータ を加算するという処理を行っています。data に ["1", "2", "3"] のようなデータが代入されていた場合は、3 行目の for 文の 最初の繰り返し で、num に "1" が代入 されるため、4 行目では、0 + "1" という、整数型と文字列型 のデータを + 演算子で演算するという処理が行われるため、上記のようなエラーが発生します。

文字列型 のデータは、反復可能オブジェクト ですが、同様の理由 で、sum の 実引数 に 文字列型のデータを記述 して呼び出すと、下記のプログラムのように エラーが発生 します。

print(sum("123"))

実行結果

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

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

三項演算子による簡略化

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

先程のプログラムの上記の部分は、以前の記事で説明した 三項演算子 を使うことで、下記のプログラムのように 1 行で記述 することができます。

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

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

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

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same

修正箇所

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

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same

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

test_judge()

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

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

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

print(True + 2)     # 1 + 2 と同じ
print(False * 3)    # 0 * 3 と同じ
print(True - False) # 1 - 0 と同じ

実行結果

3
0
1

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

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

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

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

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

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same

修正箇所

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

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same

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

test_judge()

このアルゴリズムの性質

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

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

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

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

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

以前の記事で説明したように、list 内包表記 は、下記のような for 文の ブロックの中 で append の 処理のみ を行うプログラムを、その下のプログラムのように、簡潔に記述 する表記方法です。

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

a = [式 for 変数名 in 反復可能オブジェクト]

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

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

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

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

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

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

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

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

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

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

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

Marubatsu.is_same = is_same

修正箇所

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

    return sum(same_list) == self.BOARD_SIZE

Marubatsu.is_same = is_same

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

test_judge()

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

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

Marubatsu.is_same = is_same

修正箇所

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

Marubatsu.is_same = is_same

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

test_judge()

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

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

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

Marubatsu.is_same = is_same

修正箇所

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

Marubatsu.is_same = is_same

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

test_judge()

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

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

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

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

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

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

Marubatsu.is_same = is_same

修正箇所

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

Marubatsu.is_same = is_same

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

test_judge()

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

is_same を、前回の記事で紹介した、+ 演算子 を使うアルゴリズムで実装することができます。

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

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

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

行番号のないプログラム

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

    return line_text == mark * self.BOARD_SIZE

Marubatsu.is_same = is_same

修正箇所（その 2 と比較しています）

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

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

Marubatsu.is_same = is_same

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

test_judge()

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

以前の記事で説明したように、文字列型 のデータのみを要素として持つ list の要素 を、join メソッド を使って、特定の文字列 で 間を区切って連結 することができます。その際に、空文字 に対して join メソッド を記述することで、list の要素 を 直接連結 した 文字列を計算 できます。

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

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

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

行番号のないプログラム

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

Marubatsu.is_same = is_same

修正箇所

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

    return line_text == mark * self.BOARD_SIZE

Marubatsu.is_same = is_same

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

test_judge()

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

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

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

本記事のまとめ

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

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

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

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

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

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

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

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

次回の記事

更新履歴

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

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

目次と前回の記事

前回までのおさらい

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

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

前回までのおさらい

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

このアルゴリズムの性質

プログラムの簡略化

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

このアルゴリズムの性質

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

list の作成と sum による計算

sum に関する注意点

三項演算子による簡略化

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

このアルゴリズムの性質

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

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

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

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

list と join を使った記述方法

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

本記事のまとめ

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

次回の記事

更新履歴

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

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

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

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

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

`sum` に関する注意点

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

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

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

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