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

目次と前回の記事

前回までのおさらい

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

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

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

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

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

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

前回までのおさらい

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

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

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

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

is_full の定義

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

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

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

from marubatsu import Marubatsu

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

Marubatsu.is_full = is_full

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

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

Marubatsu.judge = judge

修正箇所

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

Marubatsu.judge = judge

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

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

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

この処理は、前回の記事で定義した最初の is_same の 処理と同様 なので、下記のプログラムのように 同じアルゴリズム で記述することができます。

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

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

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

行番号のないプログラム

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

Marubatsu.is_full = is_full

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

test_judge()

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

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

Marubatsu.is_full = is_full

修正箇所

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

Marubatsu.is_full = is_full

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

test_judge()

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

〇×ゲームのマスの中に、空のマスが存在するかどうか は、以前の記事 で説明した、in 演算子 を利用して調べることができます。in 演算子は、文字列型や list などの、反復可能オブジェクト の 要素 に、指定したデータ が 存在しているかどうか を 調べる という処理を行うメソッドで、指定したデータ が 存在する 場合は 計算結果 が True に、存在しない 場合は False になります。

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

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

Marubatsu.is_full = is_full

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

test_judge()

実行結果

Start
test winner = playing

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

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

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

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

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

mb = Marubatsu()
print(mb.board)

実行結果

[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]

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

print(Marubatsu.EMPTY in mb.board)

実行結果

False

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

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

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

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

print(Marubatsu.EMPTY in mb.board[0])

実行結果

True

in 演算子 は、指定した値が、反復可能オブジェクトの 1 つ目のインデックス に 対応する要素 に 代入されているかどうか を 判定 するという処理を行う。

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

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

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

行番号のないプログラム

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

    return True

Marubatsu.is_full = is_full

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

test_judge()

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

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

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

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

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

• 2 行目：self.board を 平坦化した list を 代入 する text_list を 空の list で 初期化 する
• 3 行目：ゲーム盤の 各列 に対する 繰り返し処理 を、列のデータ を col に代入 しながら行う
• 4 行目：+= 演算子 を使って、text_list に col の それぞれの要素 を順番に 追加 して 拡張 する。+= 演算子 による list の拡張 については、以前の記事 を参照すること
• 6 行目：is_full は、空のマス が 存在する 場合は False、そうでない 場合は True を返す 関数なので、in ではなく、not in 演算子 を使って、text_list の 要素の中 に Marubatsu.EMPTY が 存在する 場合は False、存在しない 場合は True を 返す

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

行番号のないプログラム

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

    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full

修正箇所

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

-   return True
+   return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full

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

test_judge()

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

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

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

    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full

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

test_judge()

実行結果

Start
test winner = playing

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

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

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

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

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

    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full

修正箇所

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

    return Marubatsu.EMPTY not in text_list

Marubatsu.is_full = is_full

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

test_judge()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Marubatsu.is_full = is_full

修正箇所

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

Marubatsu.is_full = is_full

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

test_judge()

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

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

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

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

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

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

• 下記のプログラムでは、self.board から 順番に 取り出した値 を col に代入 し、その col から 順番に 取り出した値 を cell に代入 するという、繰り返しの処理 が行われる。

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

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

[col for col in self.board]

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

[cell for cell in col]

• 上記の 2 つを 組み合わせる と以下のように記述できる。

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

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

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

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

Marubatsu.is_full = is_full

test_judge()

実行結果

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

NameError: name 'col' is not defined

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

• NameError
  名前（name）に関するエラー
• name 'col' is not defined
  col という名前（name）は定義（define）されていない（is not）

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

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

sum を使うアルゴリズム

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

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

前回の記事 では、start を 考慮しない sum の 疑似的な定義 を紹介しましたが、start を考慮に入れた場合 の sum 関数の 定義 は、おそらく 下記のようなプログラムになっていると 推測されます。

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

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

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

print(sum([[1, 2], [3, 4], [5, 6]], start=[]))

実行結果

[1, 2, 3, 4, 5, 6]

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

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

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

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

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

Marubatsu.is_full = is_full

修正箇所（+= を使ったアルゴリズムからの修正です）

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

Marubatsu.is_full = is_full

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

test_judge()

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

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

sum と pseudo_sum の違いの補足

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

print(pseudo_sum("123", start=""))

実行結果

123

一方、sum の場合は、下記のプログラムのように、同じ実引数 を記述して呼び出すと エラーが発生 します。先ほど紹介した sum の公式ドキュメントには、「start の値は文字列であってはなりません」と記述されているので、このエラーの 原因 は、sum が そのように定義 されているからです。

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

print(sum("123", start=""))

実行結果

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

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

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

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

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

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

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

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

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

実行結果から、以下のことが確認できます。

• 1 行目：各列 の マスの文字列 を 連結 した 要素 を持つ list が col_text_list に 代入 されている
• 2 用目：ゲーム盤の すべてのマス の文字列を 連結した文字列 が board_text に 代入 されている
• 3 行目：ゲーム盤のマスに 空のマスが存在する ことを表わす True が計算されている

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

行番号のないプログラム

mb = Marubatsu()
col_text_list = []
for col in mb.board:
    col_text_list.append("".join(col))
print(col_text_list)
board_text = "".join(col_text_list)
print(board_text)
print(Marubatsu.EMPTY in board_text)

実行結果

['...', '...', '...']
.........
True

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

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

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

行番号のないプログラム

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

Marubatsu.is_full = is_full

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

test_judge()

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

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

Marubatsu.is_full = is_full

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

test_judge()

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

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

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

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

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

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

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

修正箇所

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

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

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

修正箇所

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

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

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

Marubatsu.is_full = is_full

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

test_judge()

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

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

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

本記事のまとめ

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

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

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

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

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

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

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

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

次回の記事