目次と前回の記事
前回までのおさらい
〇×ゲームの仕様と進捗状況
正方形で区切られた 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]))
実行結果
6
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 に修正しました |