Pythonで〇×ゲームのAIを一から作成する その192 ListBoard クラスの処理速度の低下と無限ループのバグの修正

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

本記事のプログラムは Python の バージョン 3.13 で実行しています。

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

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
mbtest.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

ListBoard による処理速度の低下の改善

前回の記事で 2 次元の list でゲーム盤のデータを表現する ListBoard の定義 を行いましたが、処理速度が低下する という問題があることがわかりましたので、その原因を検証して改善を行うことにします。

処理速度の低下の原因の検証

ListBoard の導入 によって 変わった点 は、ゲーム盤のマス に対する 参照と代入処理 を list に対して直接行っていた のを、BoardList クラスの __getitem__ と __setitem__ メソッドで行うようにした点です。そこで、その処理速度の差を計測して比較 することにします。

ゲーム盤を表す 2 次元の list は ListBoard クラスのインスタンスの board 属性に代入 されています。従って、2 次元の list に対する参照と代入処理 は %timeit を利用した下記のプログラムで計測することができます。

from marubatsu import Marubatsu

mb = Marubatsu()
# list の要素の参照
%timeit mb.board.board[0][0]
# list の要素への代入
%timeit mb.board.board[0][0] = Marubatsu.CIRCLE

実行結果

40.1 ns ± 2.4 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
48.4 ns ± 1.56 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は ListBoard の __getitem__ と __setitem__ メソッドを利用する場合の計測です¹。

# ListBoard の `__getitem__` メソッドによる参照
%timeit mb.board[0][0]
# ListBoard の `__setitem__` メソッドによる代入
%timeit mb.board[0][0] = Marubatsu.CIRCLE

実行結果

255 ns ± 18.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
289 ns ± 4.54 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は実行結果をまとめた表です。桁数をあわせるために、小数点以下第一桁で四捨五入しました。下記の表から参照と代入のどちらも 5 倍以上の処理時間の差 があることがあることがわかりました。これが 処理速度が低下した原因 ではないかと思われます。

	参照（ns）	代入（ns）
2 次元の list を直接利用	40	48
ListBoard	255	289

tuple による座標の指定

ListBoard の __getitem__ では、2 つ目の添字に対応 するために ListBoardwithKey という 別のクラスのインスタンス作成 して返すという処理を行っています。インスタンスの作成 の処理には 時間がかかる ので、それが原因で処理速度が低下した可能性が高いでしょう。そのことを確認するために 別のクラスのインスタンスを作成しない、1 つの添字でゲーム盤のマスを表現 する手法について紹介し、その手法との処理時間の比較を行うことにします。

添字 には list のように 数値型 のデータと、dict のように 文字列型 のデータが 良く利用されます が、複数のデータ を要素として持つ tuple を添字に記述 することもできます。そのため、mb.board[1, 2]² のように、添字 にゲーム盤のマスの座標を表す 2 つの要素を持つ tuple を記述することで、1 つの添字で座標を指定 するという方法が考えられます。なお、list の添字は tuple に対応していないので添字に tuple を記述するとエラーが発生しますが、この手法は numpy などの有名なライブラリなどで良く利用されています。

下記はそのように ListBoard クラスの __getitem__ メソッドを修正したプログラムです。これまでの 2 つの添字の記述にも対応できるように工夫しました。

• 4、5 行目：key に代入されたデータが tuple であるかどうかは、組み込み関数 type の返り値が tuple と等しいかどうかで判定できる。key のデータ型が tuple の場合は key の 0 番と 1 番の要素に x と y 座標が代入されているとみなして self.board[key[0]][key[1]] を返すように修正する
• 6、7 行目：そうでなければこれまでと同じ処理を行う

1  from marubatsu import ListBoard, ListBoardwithFirstkey
2
3  def __getitem__(self, key):
4      if type(key) == tuple:
5          return self.board[key[0]][key[1]]
6      else:
7          return ListBoardwithFirstkey(self.board, key)
8  
9  ListBoard.__getitem__ = __getitem__

行番号のないプログラム

from marubatsu import ListBoard, ListBoardwithFirstkey

def __getitem__(self, key):
    if type(key) == tuple:
        return self.board[key[0]][key[1]]
    else:
        return ListBoardwithFirstkey(self.board, key)

ListBoard.__getitem__ = __getitem__

修正箇所

from marubatsu import ListBoard, ListBoardwithFirstkey

def __getitem__(self, key):
-   return ListBoardwithFirstkey(self.board, key)
+   if type(key) == tuple:
+       return self.board[key[0]][key[1]]
+   else:
+       return ListBoardwithFirstkey(self.board, key)

ListBoard.__getitem__ = __getitem__

下記は ListBoard の __setitem__ メソッドの定義です。__getitem__ の場合と考え方は同じで key の値が tuple の場合 に self.board[key[0]][key[1]] に value を代入 します。

def __setitem__(self, key, value):
    if type(key) == tuple:
        self.board[key[0]][key[1]] = value

ListBoard.__setitem__ = __setitem__

下記は board[0][0] と board[0, 1] でそれぞれ (0, 0) と (0, 1) のマスの 代入と参照 を行うプログラムで、実行結果から正しく代入と参照が行われることが確認できます。

mb = Marubatsu()
mb.board[0][0] = Marubatsu.CIRCLE
mb.board[0, 1] = Marubatsu.CROSS
print(mb.board[0][0])
print(mb.board[0, 1])
print(mb)

実行結果

o
x
Turn o
o..
x..
...

下記は 添字に [0, 0] を記述 して 参照と代入の処理時間を計測 するプログラムです。

# ListBoard の `__getitem__` メソッドによる参照
%timeit mb.board[0, 0]
# ListBoard の `__setitem__` メソッドによる代入
%timeit mb.board[0, 0] = Marubatsu.CIRCLE

実行結果

111 ns ± 4.44 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
167 ns ± 3.44 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記はこれまでの実行結果をまとめた表です。添字が 1 つ の場合は ListBoardwithFirstkey の インスタンスを作成しない ため 処理時間が短くなる ことが確認できますが、2 次元の list を直接利用する場合 と比較するとまだ 約 3 倍の処理時間 がかかることが確認できます。

	参照（ns）	代入（ns）
2 次元の list を直接利用	40	48
2 つの添字	255	289
tuple による 1 つの添字	111	167

なお、tuple による 1 つの添字 でゲーム盤のマスを記述する方法を 採用する場合 は、Marubatsu クラスなどで記述されている self.board[x][y] のように 2 つの添え字で記述されたプログラムを すべて self.board[x, y] のように 修正する必要 があります。

メソッドの定義による参照と代入

__getitem__ と __setitem__ メソッドによる 添字の処理 に 時間がかかっている可能性がある ので、(x, y) のマス の 参照と代入 を行う getmark と setmark というメソッドを ListBoard クラスに定義 して 処理時間を計測 してみることにします。下記はそれらの関数の定義です。特に難しい点はないと思いますので説明は省略します。

def getmark(self, x, y):
    return self.board[x][y]

ListBoard.getmark = getmark

def setmark(self, x, y, mark):
    self.board[x][y] = mark
    
ListBoard.setmark = setmark

下記は、get_mark と set_mark で (0, 0) のマスの 代入と参照 を行うプログラムで、実行結果から正しく代入と参照が行われることが確認できます。

mb = Marubatsu()
mb.board.setmark(0, 0, Marubatsu.CIRCLE)
print(mb.board.getmark(0, 0))
print(mb)

実行結果

o
Turn o
o..
...
...

下記は getmark と setmark でマスの 参照と代入 の 処理時間を計測 するプログラムです。

mb = Marubatsu()
# ListBoard の `getmark` メソッドによる参照
%timeit mb.board.getmark(0, 0)
# ListBoard の `setmark` メソッドによる代入
%timeit mb.board.setmark(0, 0, Marubatsu.CIRCLE)

実行結果

78.1 ns ± 1.14 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
91.8 ns ± 2.46 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記はそれぞれの場合の処理速度をまとめた表で、2 次元の list を直接利用 する場合よりも 処理時間が長い 点は変わりませんが、__getitem__ と __setitem__ メソッドを定義して添字を記述するよりも 処理時間が減った ことが確認できます。

	参照（ns）	代入（ns）
2 次元の list を直接利用	40	48
2 つの添字	255	289
tuple による 1 つの添字	111	167
getmark と setmark	78	92

修正方法の方針の決定

__getitem__ と __setitem__ を定義することで、list や dict のように 添字を利用 して特定のデータの 参照や代入処理 を行えるようになり、プログラムが わかりやすく記述できる という利点が得られます。一方で上記で検証したように 同様の処理を行うメソッド を 自分で定義した場合より も 処理時間が長くなる という欠点があります。

ただし、上記の検証結果からわかるように、その 処理時間の差 は 数十 ns に過ぎません。ns は 10 億分の一秒 なので、その 参照と代入処理が全体の処理の大部分を占める という、ボトルネックになっている場合を除けば その差を 人間が体感することはほとんどない でしょう。そのため、処理速度の差が体感できない場合 は 添字によってプログラムがわかりやすく記述できる __getitem__ と __setitem__ を利用することをお勧めします。

AI の関数 の場合は、前回の記事で示したように実際に __getitem__ と __setitem__ を利用した 添字によるマスの参照と代入 を行うように修正したことで 処理速度が大きく減ったことが確認できた ので、本記事では __getitem__ と __setitem__ を不採用 とし、getmark と setmark というメソッドを定義するように 方針を変更 することにします。

Board と ListBoard クラスの修正

ゲーム盤を表すクラスが 必要とするメソッドが変わった ので、ListBoard クラスの 基底クラス である Board クラスの 抽象メソッド を下記のプログラムのように 変更 することにします。具体的には __getitem__ と __setitem__ メソッドの定義を削除し、getmark と setmark を抽象メソッドとして定義しています。

from abc import ABCMeta, abstractmethod

class Board(metaclass=ABCMeta):
    @abstractmethod
    def getmark(self, x, y):
        pass

    @abstractmethod
    def setmark(self, x, y, mark):
        pass

次に、ListBoard クラスを下記のプログラムのように 定義し直します。__init__ メソッドの内容に 変更はありません。getmark と setmark メソッドの定義は 先ほどと同じ で、__getitem__ メソッドと __setitem__ メソッドは必要がなくなったので削除しました。ListBoardwithKey クラスに関する 処理が無くなった ので、プログラムが かなりわかりやすくなった のではないかと思います。

class ListBoard(Board):
    def __init__(self, board_size=3):
        self.BOARD_SIZE = board_size
        self.board = [[Marubatsu.EMPTY] * self.BOARD_SIZE for y in range(self.BOARD_SIZE)]
 
    def getmark(self, x, y):
        return self.board[x][y]

    def setmark(self, x, y, mark):
        self.board[x][y] = mark

Marubatsu クラスの修正

次に、Marubatsu クラス の中で self.board に 2 つの添字を記述 してゲーム盤のマスの 参照と代入を行う部分 を getmark と setmark を利用 して参照と代入を行うように 修正する必要 があります。修正するメソッドは place_mark、remove_mark、is_same、calc_legal_moves、count_marks、__str__ です。また、ListBoardwithKey クラスの定義は必要が無くなったので 削除する ことにします。

なお、修正は self.board[x][y] の参照を self.board.getmark(x, y)、self.board[x][y] = mark による代入処理を self.board.setmark(x, y, mark) のように修正するというものなので、説明と修正箇所は省略します。また、長いのでプログラムは折りたたみました。

修正したプログラム

def place_mark(self, x, y, mark):
    if self.check_coord:
        if 0 <= x < self.BOARD_SIZE and 0 <= y < self.BOARD_SIZE:
            if self.board.getmark(x, y) == Marubatsu.EMPTY:
                self.board.setmark(x, y, mark)
                return True
            else:
                print("(", x, ",", y, ") のマスにはマークが配置済です")
                return False
        else:
            print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
            return False   
    else:       
        self.board.setmark(x, y, mark)
        return True 
    
Marubatsu.place_mark = place_mark

def remove_mark(self, x, y):
    if self.check_coord:
        if 0 <= x < self.BOARD_SIZE and 0 <= y < self.BOARD_SIZE:
            if self.board.getmark(x, y) != Marubatsu.EMPTY:
                self.board.setmark(x, y, Marubatsu.EMPTY)
                return True
            else:
                print("(", x, ",", y, ") のマスにはマークがありません")
                return False
        else:
            print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
            return False
    else:
        self.board.setmark(x, y, Marubatsu.EMPTY)
        return True   

Marubatsu.remove_mark = remove_mark

def is_same(self, mark, coord, dx, dy):
    x, y = coord
    text_list = [self.board.getmark(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

def calc_legal_moves(self):
    if self.status != Marubatsu.PLAYING:
        return []
    legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
                        for x in range(self.BOARD_SIZE)
                        if self.board.getmark(x, y) == Marubatsu.EMPTY]
    return legal_moves

Marubatsu.calc_legal_moves = calc_legal_moves

def count_marks(self, coord, dx, dy, datatype="dict"):
    x, y = coord   
    count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
        count[self.board.getmark(x, y)] += 1
        x += dx
        y += dy

    if datatype == "dict":
        return count
    else:
        return Markpat(count[self.last_turn], count[self.turn], count[Marubatsu.EMPTY])  
    
Marubatsu.count_marks = count_marks

def __str__(self):
    # ゲームの決着がついていない場合は、手番を表示する
    if self.status == Marubatsu.PLAYING:
        text = "Turn " + self.turn + "\n"
    # 決着がついていれば勝者を表示する
    else:
        text = "winner " + self.status + "\n"
    for y in range(self.BOARD_SIZE):
        for x in range(self.BOARD_SIZE):
            lastx, lasty = self.last_move
            if x == lastx and y == lasty:
                text += self.board.getmark(x, y).upper()
            else:
                text += self.board.getmark(x, y)
        text += "\n"
    return text

Marubatsu.__str__ = __str__

上記の修正後に下記のプログラムで ai2s VS ai2s の対戦を 10000 回 行います。修正後の ListBoard を利用した対戦を行う ためには mbparams={"boardclass": ListBoard} を記述する必要がある点に注意が必要です。その理由についてはノートで後述します。

from ai import ai_match, ai2s

ai_match(ai=[ai2s, ai2s], match_num=5000, mbparams={"boardclass": ListBoard})

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:02<00:00, 2438.01it/s]
count     win    lose    draw
o        2863    1504     633
x        1416    2929     655
total    4279    4433    1288

ratio     win    lose    draw
o       57.3%   30.1%   12.7%
x       28.3%   58.6%   13.1%
total   42.8%   44.3%   12.9%

ゲーム盤のデータ構造を表すクラスを代入する Marubatsu クラスの __init__ メソッドの仮引数 boardclass は、ListBoard クラスをデフォルト値とする デフォルト引数 です。以前の記事で説明したように、デフォルト引数の デフォルト値 はその関数を 定義した時点での値が利用 され続けます。先ほどのプログラムの修正で __init__ メソッドの再定義は行っていない ので、仮引数 boardclass の デフォルト値 は今回の記事で 修正を行う前の ListBoard クラスのまま です。

実際に下記のプログラムのように boardclass=ListBoard を記述せずに Marubatsu クラスのインスタンスを作成して board 属性に 1 つの添字を記述して参照すると、下記のプログラムの実行結果のように参照した値が ListBoardwithKey クラスのインスタンスになることから、修正前の ListBoard が利用されていることが確認できます。

mb = Marubatsu()
print(mb.board[0])

実行結果

<marubatsu.ListBoardwithFirstkey object at 0x000002AF1A03F7D0>

一方、下記のプログラムのように boardclass=ListBoard を記述して Marubatsu クラスのインスタンスを作成して board 属性に 1 つの添字を記述して参照すると、修正した ListBoard クラスには __getitem__ メソッドが定義されていないので実行結果のようなエラーが発生します。

mb = Marubatsu(boardclass=ListBoard)

print(mb.board[0])

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[15], line 3
      1 mb = Marubatsu(boardclass=ListBoard)
----> 3 print(mb.board[0])

TypeError: 'ListBoard' object is not subscriptable

なお、marubatsu.py を今回の記事の内容で修正し、VSCode の再起動を行った後で Marubatsu クラスをインポートした場合は修正後の ListBoard が利用されるようになるので、次回以降の記事でこの記述を行う必要はありません。

下記は、前回の記事 で 同じプログラムを実行 した場合の実行結果を加えてまとめた表です。2 次元の list を直接利用 する場合よりは 処理回数が若干少ない ですが、2 つの添字 で参照と代入を行う場合 よりも処理回数が大幅に増加 していることが確認できます。

	処理回数の平均
2 次元の list を直接利用	2812.18 回/秒
2 つの添字	1645.19 回/秒
getmark と setmark	2438.01 回/秒

2 次元の list を直接利用する場合 よりは 処理速度は若干遅く なりますが、ポリモーフィズムの利点が得られる点が大きい ので getmark と setmark を採用 することにします。

他のプログラムの修正

ゲーム盤のマス の 参照と代入 を行うプログラムは 他にも下記の場所に記述 されているので、それらも修正 する必要があります。それらに関する修正も同様なので本記事では修正箇所は示さず、util.py などのファイルのほうを修正することにします。修正後のファイルは marubatsu_new.py、util_new.py、ai_new.py です。

• marubatsu.py の Marubatsu_GUI クラスの draw_board メソッド
• util.py の calc_same_boardtexts
• ai.py で定義された多数の AI の関数

このように、ポリモーフィズム を利用する場合に 共通するメソッドを後から変更 すると、そのメソッドを利用するプログラムをすべて修正する必要 が生じます。そのため、できるかぎり共通するメソッドを後から変更しない ように気をつける必要があります。筆者も最初は __getitem__ と __setitem__ メソッドを定義することで他のプログラムを一切変更しないようにする予定だったのですが、思ったより処理速度が落ちる ことが判明したので やむなく getmark と setmark メソッドに変更 することにしました。

無限ループの問題の修正

前回の記事でも言及しましたが、今回の記事での 修正前の ListBoard にはこれまでに記述したプログラムを動作させるために 必要なメソッドが定義されていない というバグがあります。そのため、下記のプログラムのように play メソッドの実引数に gui=True を記述して GUI で人間同士の対戦 を行なおうとすると、実行結果のように GUI のゲーム盤が表示されない というバグが発生します。また、JupyterLab の セルの下部 には プログラムが実行中 であることを表す 回転する矢印のアニメーション が行われつづけます。これは、プログラムの中で 無限ループが発生している ことが原因です。

なお、このバグは 修正前の ListBoard クラスを利用する場合に発生するので、Marubatsu クラスのインスタンスを作成する際に 実引数に何も記述していません。

mb = Marubatsu()
mb.play(ai=[None, None], gui=True)

実行結果

Python のバージョン 3.13 の仮想環境を新しく作成した人は、上記のプログラムを実行して widgets に関するエラーが発生するかもしれません。その場合はおそらく ipympl モジュールなどがインストールされていないことが原因なので、以前の記事の手順でインストールし、JupyterLab を再起動してから実行して下さい。

バグの原因の検証

無限ループを中断 するためには、上記のプログラムの セルの左にある四角のマーク の 停止ボタンをクリック して下さい。セルの下に下記のような プログラムが強制的に中断 されたことを表す メッセージが表示 されます。

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
Cell In[16], line 2
      1 mb = Marubatsu()
----> 2 mb.play(ai=[None, None], gui=True).

略

File c:\Users\ys\ai\marubatsu\192\marubatsu.py:385, in Marubatsu.board_to_str(self)
    383 txt = ""
    384 for col in self.board:
--> 385     txt += "".join(col)
    386 return txt

KeyboardInterrupt: 

プログラムを中断 した場合は エラーが発生した場合と同様 にプログラムが 中断された場所 が メッセージで表示 されます。上記の in Marubatsu.board_to_str(self) のメッセージから Marubatsu クラスの board_to_str メソッド内でプログラムが中断したことがわかります。

KeyboardInterrupt は、キーボードからの操作によってプログラムが中断（interrupt）されたことを表します。JupterLab では停止ボタンをクリックしてプログラムを中断しますが、JupyterLab のようなプログラムを実行する環境が無かった頃は、プログラムは一般的にコンソールというアプリケーションから実行し、キーボードでコマンドを入力を入力してプログラムを中断していたことが由来です。

なお、board_to_str メソッドは ai_abs_dls などの ゲーム木の探索を行う AI の関数 で 置換表を利用 する場合でも 呼び出される ので、下記のプログラムで ai_abs_dls で置換表を利用する処理 を行うと無限ループが発生するため答えが表示されません。

from ai import ai_abs_dls, ai14s

mb = Marubatsu()
eval_params = {"minimax": True}
print(ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8))

board_to_str で行われる処理の検証

下記は board_to_str メソッドの定義で、ゲーム盤の マスの文字列を結合 することで、ゲーム盤を表す文字列（string）を 計算して返す という処理を行っています。

def board_to_str(self):
    txt = ""
    for col in self.board:
        txt += "".join(col)
    return txt

この処理の中では for col in self.board という for 文 で、ゲーム盤を表す 2 次元の list から 列（column）を表す list を取り出す という繰り返し処理を行っていますが、self.board が 2 次元の list から ListBoard クラスのインスタンスに変わった のでこの部分で 無限ループが発生 しています。なお、下記のノートで説明するように、今回の記事で行った 修正後の ListBoard が self.board に代入 されている場合はこの for 文で エラーが発生する ので、この for 文の処理に対するバグは ListBoard の修正の有無に関わらず修正する必要があります。

ListBoard に __getitem__ メソッドが定義されていない場合は、TypeError: 'ListBoard' object is not iterable のようなエラーが発生します。

今回の記事で修正した ListBoard クラスは __getitem__ メソッドが定義されていないので、下記のプログラムで修正後の ListBoard を利用して play メソッドを実行すると、上記と同様にゲーム盤が表示されないだけでなく、実行結果のように board_to_str の for 文の処理で TypeError のエラーが発生します。

mb = Marubatsu(boardclass=ListBoard)
mb.play(ai=[None, None], gui=True)

実行結果（GUI のボタンなどの表示は同じなので省略します）

略
File c:\Users\ys\ai\marubatsu\192\marubatsu.py:384, in Marubatsu.board_to_str(self)
    377 """board 属性の要素を連結した文字列を計算して返す
    378 
    379 Returns:
    380     board 属性の要素を連結した文字列
    381 """
    383 txt = ""
--> 384 for col in self.board:
    385     txt += "".join(col)
    386 return txt

TypeError: 'ListBoard' object is not iterable

無限ループが発生する原因

実は 無限ループが発生する原因 はこの問題を解決するために 必要な知識ではありません が、せっかくなのでこの処理で 無限ループが発生する原因について説明 します。興味がない方はこの部分は飛ばしても構いません。

実際に 無限ループが発生していること は、下記のプログラムで board_to_str で行っているものと 同じ for 文 を実行し、col を print で表示 すると、実行結果のように 無限ループが発生 して ListBoardwithFirstkey クラスの インスタンスが無限に取り出されて表示 されることから確認することができます。放っておくとメッセージが無限に表示されるので 停止ボタンをクリックしてプログラムを中断 して下さい。

mb = Marubatsu()
for col in mb.board:
    print(col)

実行結果（中断時のメッセージは省略します）

<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749BB0>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749E50>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749BB0>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749E50>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749BB0>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749E50>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749BB0>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749E50>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749BB0>
<marubatsu.ListBoardwithFirstkey object at 0x000001F1C3749E50>
・・・以下放っておくと無限に続く

前回の記事でも説明しましたが、for 文による繰り返し処理 では ポリモーフィズムの仕組みが利用 されおり、for 文による繰り返し処理を行うことができる 反復可能オブジェクト は 以下のいずれかのメソッドが定義 されている必要があります。

• for 文による繰り返し処理の際に、次の要素を取り出すために呼び出される __iter__ メソッド。このメソッドについては今後の記事で紹介する予定です
• シーケンスとして定義 された __getitem__ メソッド。シーケンスの用語の意味については後で説明する

修正前の ListBoard クラス には __iter__ メソッドは 定義されていません が、__getitem__ は定義されている ので for 文による繰り返し処理 に記述しても エラーは発生しません。エラーは発生しないが、無限ループが発生する原因を理解するためには __iter__ メソッドが定義されておらず、__getitem__ メソッドが定義 されたクラスのインスタンスを for 文に記述 した場合に 行われる処理 について理解する必要があります。

なお、今回の記事では説明しませんが、__iter__ メソッドが定義 されている場合は、下記の説明とは 全く異なる処理 が行われます。

下記のプログラムは仮引数 key の値を返す、__getitem__ メソッドのみが定義 された クラス A を定義 するプログラムです。

class A:
    def __getitem__(self, key):
        return key

下記のプログラムで A のインスタンスを作成 して for 文で繰り返し処理を行う と 無限ループが発生 し、下記のような実行結果が表示されます。放っておくとメッセージが無限に表示されるので中断ボタンをクリックしてプログラムを停止して下さい。

a = A()
for value in a:
    print(value)

実行結果（中断時のメッセージは省略します）

0
1
2
3
4
5
6
7
8
9
10
・・・以下放っておくと無限に続く

A の __getitem__ メソッドは 添字の値をそのまま返す処理 を行うので、実行結果から for 文 の繰り返し処理では a[0]、a[1]、a[2] ・・・ のように 添字を 0 から 1 ずつ増やしながら その値を value に代入する という処理が行わることが確認できます。また、無限ループが発生 していることから、添字の数値の上限が設定されていない ことがわかります。

Python の __getitem__ のドキュメント には下記のように for 文の 繰り返し処理 が __getitem__ メソッドで IndexError の 例外 を発生 させることで終了することが記述されています。なお、シーケンス（sequence）とは list などのような ひと続きのデータ を表し、シーケンスの 終端 とはその 最後のデータ を表し、IndexError が発生 することで一続きのデータの 列挙が終了したことを判定 するという意味です。

「for ループでは、シーケンスの終端を正しく検出できるようにするために、不正なインデクスに対して IndexError が送出されるものと期待しています」

シーケンス（sequence）の用語の詳細については下記のリンク先を参照して下さい。

従って、無限ループにならない ようにするためには、__getitem__ メソッドが key が特定の値を超えた場合 に IndexError を発生 させる必要があります。例えば下記のプログラムでは添字の値を表す key が 5 以上 になった場合に raise 文 で IndexError を発生 させるように修正しました。

class A:
    def __getitem__(self, key):
        if key < 5:
            return key
        else:
            raise IndexError

上記の修正後に先程と同じ下記のプログラムを実行すると、実行結果のように for 文 の繰り返し処理によって a[0]、a[1]、・・・、a[4] の値が表示 され、a[5] を d に代入しようとした際に __getitem__ メソッドで IndexError が発生 して 繰り返し処理が終了する という処理が行われます。

a = A()
for d in a:
    print(d)

実行結果

0
1
2
3
4

__getitem__ メソッドで発生した IndexError は for 文の繰り返し処理の 終了の判定に利用 されますが、それによってプログラムが エラーで終了することはありません。その仕組みは以前の記事で説明した例外処理で実現されています。上記のプログラムの処理では、下記のようなプログラムが実行されると考えると良いでしょう。

• 1、2、8 行目：index を 0 から 1 ずつ無限に増やす繰り返し処理を行う。range の実引数に無限大を表す数値を記述することはできないのでこのように記述した
• 3 ~ 6 行目：try 文で a[index] の計算を試み、5 行目の except IndexError: で IndexError が発生した場合はエラーでプログラムを終了せずに、6 行目の break 文を実行して繰り返し処理を終了する

1  index = 0
2  while True:
3      try:
4          d = a[index]
5      except IndexError:
6          break
7      print(d)
8      index += 1

行番号のないプログラム

index = 0
while True:
    try:
        d = a[index]
    except IndexError:
        break
    print(d)
    index += 1

実行結果

0
1
2
3
4

上記をまとめると以下のようになります。

__iter__ メソッドが定義されておらず、__getitem__ メソッドが定義 されているオブジェクトに対して for 文 で繰り返し処理を行うと下記の手順で処理が行われる。

• 繰り返しのたびに key の値を 0 から 1 ずつ増やしながら、オブジェクトの __getitem__(key) を呼び出し、その 返り値を for 文の変数に代入 する
• 繰り返し処理は __getitem__ メソッドの処理で IndexError の例外が発生 した時点で 終了する

このことから、__iter__ メソッドが定義されておらず、__getitem__ メソッドが定義 されたクラスのインスタンスに対して for 文で繰り返し処理を行うと、list と同様 の 0 からはじまる整数のインデックスを持つデータ構造 であることを 想定した繰り返し処理が行われる ことがわかります。

先程の board_to_str の下記の for 文で 無限ループが発生した理由 は以下の通りです。

mb = Marubatsu()
for col in mb.board:
    print(col)

1. for 文 による繰り返し処理が行われるたびに、添字を 0 から 1 ずつ増やしながら col = mb.board[添字の値] の処理が実行される
2. mb.board[添字の値] が参照 されると下記の ListBoard クラスの __getitem__ が呼び出されるが、この処理は 添字がどのような値でも実行できるの で IndexError は発生しない
3. for 文の処理 は __getitem__ メソッド内で IndexError が発生しない限り終了しない ので 無限ループが発生する

def __getitem__(self, key):
    return ListBoardwithFirstkey(self.board, key)

Python の公式の反復可能オブジェクト(iterable)の説明では、「with a __getitem__() method that implements sequence semantics」のようにシーケンスとして実装された __getitem__ メソッドを持つと説明されています。

また、シーケンス(sequence) のドキュメントには以下のように説明されています。

An iterable which supports efficient element access using integer indices via the __getitem__() special method and defines a __len__() method that returns the length of the sequence.

上記の要点を列挙すると以下のようになります。

• 整数の添字に対する値を返す __getitem__ メソッドが定義されている
• 要素の数を返り値として返す __len__ メソッドが定義されている

上記から、筆者は __getitem__ メソッドが定義されている反復可能オブジェクトを for 文で利用するためには __len__ メソッドの定義が必要だと最初は思ったのですが、実際には for 文の繰り返し処理の最中に __len__ メソッドは利用されないので __len__ メソッドの定義を行う必要はないようです。

なお、ListBoard クラスでは必要がないので実装しませんが、シーケンスとしてデータ型を実装する場合は __len__ メソッドを定義したほうが良いでしょう。

バグの修正方法

1 つ目の添字 はゲーム盤の 列を表す ので、その 添字の値 は 0 以上ゲーム盤のサイズ未満の整数 である必要があります。そのため、上記のバグの原因の説明を読んだ方は ListBoard クラスの __getitem__ メソッドの添字を表す仮引数 key の値 が self.BOARD_SIZE 以上 の場合に IndexError を発生 させればよいと思った方がいるかもしれません。確かにそのように修正すれば無限ループは発生しませんが、今回の記事の前半で __getitem__ メソッドを定義しない ことにしたので その方法を取ることはできません。

また、下記の board_to_str では for 文 による繰り返し処理で 列のデータを順番に取り出す という処理を行っていますが、そのような処理を行うことができるのは ゲーム盤のデータ を 2 次元の list で表現した場合だけ です。例えば、List1dBoard のようにゲーム盤のデータが 1 次元の list で表現されて self.board に代入されている場合に下記のプログラムを実行すると列のデータではなく、セルのデータが順番に取り出されてしまう ことになります。

def board_to_str(self):
    txt = ""
    for col in self.board:
        txt += "".join(col)
    return txt

上記の board_to_str が行う処理は、ゲーム盤のデータ構造が異なる と アルゴリズムが変化する処理 なので Marubatsu クラスの board_to_str メソッドにその処理を記述するとゲーム盤の データ構造の種類が増えるたびに Marubatsu クラスの board_to_str にその処理を追加する必要 があり、ポリモーフィズムの利点が失われ てしまします。

そのため、ポリモーフィズムの利点を活かす ためには、borad_to_str を ゲーム盤のデータ構造を表すクラスのほうで定義 する必要があります。

具体的には、下記のプログラムのように ListBoard クラスに board_to_str メソッドを定義 します。ListBoard クラスの board 属性は 2 次元の list なので Marubatsu クラスの board_to_str と 全く同じ内容 です。

def board_to_str(self):
    txt = ""
    for col in self.board:
        txt += "".join(col)
    return txt

ListBoard.board_to_str = board_to_str

次に、Marubatsu クラスの board_to_str メソッドを下記のプログラムのように ListBoard クラスの board_to_str を呼び出した返り値を返す ように修正します。

def board_to_str(self):
    return self.board.board_to_str()

Marubatsu.board_to_str = board_to_str

上記の修正後に下記のプログラムを実行して、上記で 修正した ListBoard クラスを利用 した Marubatsu クラスの board_to_str メソッドを実行すると、実行結果のように無限ループにならずに 正しく計算されることが確認 できます。

mb = Marubatsu(boardclass=ListBoard)
mb.board_to_str()

実行結果

'.........'

Board クラスの修正

board_to_str メソッドが ゲーム盤のデータ構造を表すクラス で 必要とされるメソッド になったので、下記のプログラムのように Board クラスの抽象メソッドに追加 します。

@abstractmethod
def board_to_str(self):
    pass

Board.board_to_str = board_to_str

Marubatsu クラスの board_to_str メソッドを呼び出すと、mb.board.board_to_str() が実行されるので 2 回のメソッドの呼び出し処理が行われます。そのため、現状のプログラムで mb.board_to_str() のように記述されている部分を mb.board.board_to_str() に修正することでメソッドの呼び出し処理が 1 回分減るためほんの少しですが処理時間が短くなります。

おそらくそのような修正を行っても全体の処理時間はほとんど減らないと思いますので本記事ではそのような修正は行いません。興味がある方は修正してみてください。

List1dBoard クラスの修正

前回の記事で定義した 1 次元の list でゲーム盤を表現する List1dBoard クラスを今回の記事に合わせて下記のプログラムのように修正します。

• 2 ~ 4 行目：__init__ メソッドは元のプログラムと同じ
• 6 ~ 10 行目：getmark と setmark メソッドは、List1dBoardwithKey の __getitem__ と __setitem__ の self.key を x に、key を y に置き換えるという修正を行う
• 12、13 行目：board_to_str メソッドは すべてのマスのマーク を表す 文字列を連結 するという処理を行う。その処理はゲーム盤のデータが 1 次元の list になったので self.board の要素を join で連結 することで計算できる

 1  class List1dBoard(Board):
 2      def __init__(self, board_size=3):
 3          self.BOARD_SIZE = board_size
 4          self.board = [Marubatsu.EMPTY] * (self.BOARD_SIZE ** 2)
 5          
 6      def getmark(self, x, y):
 7          return self.board[x + y * self.BOARD_SIZE]
 8      
 9      def setmark(self, x, y, value):
10          self.board[x + y * self.BOARD_SIZE] = value
11  
12      def board_to_str(self):
13          return "".join(self.board)

行番号のないプログラム

class List1dBoard(Board):
    def __init__(self, board_size=3):
        self.BOARD_SIZE = board_size
        self.board = [Marubatsu.EMPTY] * (self.BOARD_SIZE ** 2)
        
    def getmark(self, x, y):
        return self.board[x + y * self.BOARD_SIZE]
    
    def setmark(self, x, y, value):
        self.board[x + y * self.BOARD_SIZE] = value

    def board_to_str(self):
        return "".join(self.board)

修正箇所（getmark と setmark は List1dBoardwithKey からの修正です）

class List1dBoard(Board):
    def __init__(self, board_size=3):
        self.BOARD_SIZE = board_size
        self.board = [Marubatsu.EMPTY] * (self.BOARD_SIZE ** 2)
        
-   def __getitem__(self, key):   
+   def getmark(self, x, y):
-       return self.board[self.key + key * self.BOARD_SIZE]
+       return self.board[x + y * self.BOARD_SIZE]
    
-   def __setitem__(self, key, value):
+   def setmark(self, x, y, value):
-       self.board[self.key + key * self.BOARD_SIZE] = value
+       self.board[x + y * self.BOARD_SIZE] = value

+   def board_to_str(self):
+       return "".join(self.board)

上記の実行後に下記のプログラムを実行すると、実行結果から List1dBoard を利用 した場合でも board_to_str の処理が 正しく行われたように見えます が、実は board_to_str には バグがあります。初心者には気づきにくいと思いますが、どのようなバグがあるかについて少し考えてみて下さい。

mb = Marubatsu(boardclass=List1dBoard)
mb.board_to_str()

実行結果

'.........'

board_to_str のバグの検証

board_to_str のバグは、下記のプログラムで ListBoard と List1dBoard のそれぞれのインスタンスに対して (0, 0) と (1, 0) にマークを配置 した場合の board_to_str() の返り値の表示 を行うことで確認できます。実行結果からどちらも 同じゲーム盤 であるにも関わらず 異なる文字列が計算 されて表示されることが確認できます。

mb = Marubatsu(boardclass=ListBoard)
mb.move(0, 0)
mb.move(1, 0)
print(mb)
print(mb.board_to_str())
print()
mb1d = Marubatsu(boardclass=List1dBoard)
mb1d.move(0, 0)
mb1d.move(1, 0)
print(mb1d)
print(mb1d.board_to_str())

実行結果

Turn o
oX.
...
...

o..x.....

Turn o
oX.
...
...

ox.......

このようなことが起きる原因は、ListBoard と List1dBoard の board_to_str が 異なる処理を行う からです。どのように異なるかについて少し考えてみて下さい。

下記は ListBoard の board_to_str の定義です。この処理では、for 文 でそれぞれの 列を順番に取り出し て結合することで、列ごとに結合 した文字列を 結合 しています。

def board_to_str(self):
    txt = ""
    for col in self.board:
        txt += "".join(col)
    return txt

例えば先程の mb の 下記のゲーム盤 に対しては 縦方向 の 0 列目の o..、1 列目の x..、2 列目の ... が計算されて 結合されて o..x..... が計算 されます。

Turn o
oX.
...
...

一方、List1dBoard では、以前の記事で説明した下図の 数値座標の順番 で 1 次元の list の要素にマークが記録されるので、それを結合すると ox....... という文字列が計算されます。

従って、この問題を解決するためには 数値座標 を上図の横方向の行ごとに数えるのではなく、縦方向の列ごとに数える ように修正する必要があります。下記はそのように List1dBoard の getmark と setmark メソッドを修正するプログラムです。具体的には計算式の x と y を入れ替える ことで数値座標が 縦方向に増えながら数える ようになります。

def getmark(self, x, y):
    return self.board[y + x * self.BOARD_SIZE]

List1dBoard.getmark = getmark

def setmark(self, x, y, value):
    self.board[y + x * self.BOARD_SIZE] = value
    
List1dBoard.setmark = setmark 

修正箇所

def getmark(self, x, y):
-   return self.board[x + y * self.BOARD_SIZE]
+   return self.board[y + x * self.BOARD_SIZE]

List1dBoard.getmark = getmark

def setmark(self, x, y, value):
-   self.board[x + y * self.BOARD_SIZE] = value
+   self.board[y + x * self.BOARD_SIZE] = value
    
List1dBoard.setmark = setmark 

上記の修正後に先程と同じ下記のプログラムを実行すると、実行結果から どちらも同じ o..x..... を計算 するようになったことが確認できます。

mb = Marubatsu(boardclass=ListBoard)
mb.move(0, 0)
mb.move(1, 0)
print(mb)
print(mb.board_to_str())
print()
mb1d = Marubatsu(boardclass=List1dBoard)
mb1d.move(0, 0)
mb1d.move(1, 0)
print(mb1d)
print(mb1d.board_to_str())

実行結果

Turn o
oX.
...
...

o..x.....

Turn o
oX.
...
...

o..x.....

gui_play の修正

上記で修正した ListBoard と List1dBoard を利用した Marubatsu クラスのインスタンスを利用した GUI の対戦を行うことができるか どうかを gui_play で確認 することにします。

ただし、現状の gui_play は Marubatsu クラスのインスタンスを mb = Marubatsu() で作成しているので、異なるゲーム盤のデータ型を切り替えることができません。そこで、以前の記事 での ai_match の場合の修正と同様 に下記のプログラムのように 仮引数に mbparams を追加 するという修正を行うことにします。修正方法は同じなので説明は省略します。

1  from util import load_bestmoves
2  
3  def gui_play(ai=None, params=None, ai_dict=None, mbparams={}, seed=None):
元と同じなので省略
4      mb = Marubatsu(**mbparams)
5      mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)

行番号のないプログラム

from util import load_bestmoves

def gui_play(ai=None, params=None, ai_dict=None, mbparams={}, seed=None):
    # ai が None の場合は、人間どうしの対戦を行う
    if ai is None:
        ai = [None, None]
    if params is None:
        params = [{}, {}]
    # ai_dict が None の場合は、ai1s ~ ai14s の Dropdown を作成するためのデータを計算する
    if ai_dict is None:
        ai_dict = { "人間": ( None, {} ) }
        for i in range(1, 15):
            ai_name = f"ai{i}s"  
            ai_dict[ai_name] = (getattr(ai_module, ai_name), {})
        bestmoves_and_score_by_board = load_bestmoves("../data/bestmoves_and_score_by_board.dat")
        ai_dict["ai_gt7"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board})
        bestmoves_and_score_by_board_sv = load_bestmoves("../data/bestmoves_and_score_by_board_shortest_victory.dat")
        ai_dict["ai_gtsv"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_sv})
        bestmoves_and_score_by_board_svrd = load_bestmoves("../data/bestmoves_and_score_by_board_sv_rd.dat")
        ai_dict["ai_gtsvrd"] = (ai_gt7, {"bestmoves_and_score_by_board": bestmoves_and_score_by_board_svrd})

    mb = Marubatsu(**mbparams)
    mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)

修正箇所

from util import load_bestmoves

-def gui_play(ai=None, params=None, ai_dict=None, seed=None):
+def gui_play(ai=None, params=None, ai_dict=None, mbparams={}, seed=None):
元と同じなので省略
-   mb = Marubatsu()
+   mb = Marubatsu(**mbparams)
    mb.play(ai=ai, params=params, ai_dict=ai_dict, seed=seed, gui=True)

修正した gui_play の実行

今回の記事で 様々なプログラムを修正 したので、そのすべての修正を反映したプログラムをインポート して gui_play を実行しないと エラーが発生 します。そこで、今回の記事の修正をすべて反映 させた 〇〇_new.py を作成し、下記のプログラムのように util_new.py から gui_play をインポート して実行することにします。なお、それらのファイル内で モジュールをインポートする際 に モジュールの名前を 〇〇_new に変更する必要 があります。修正したファイルについては、本記事で入力したプログラムを参照して下さい。

from util_new import gui_play

gui_play()

実行結果は省略しますが、GUI で対戦を行うことができるようになった ことを確認して下さい。また、今回の記事で修正した ai14s などさまざまなの AI を選択して AI と対戦を行うことができることも確認してみて下さい。

board_to_str を修正した結果、先程無限ループが発生した下記の ai_abs_dls で置換表を利用する プログラムを実行すると、ListBoard クラスと List1dBoard クラスの どちらを利用した場合でも 無限ループが発生せずに 最善手が計算されることが確認 できます。

from ai_new import ai_abs_dls, ai14s

mb = Marubatsu(boardclass=ListBoard)
print(ai_abs_dls(mb, eval_func=ai14s, use_tt=True, maxdepth=8))
mb1d = Marubatsu(boardclass=List1dBoard)
print(ai_abs_dls(mb1d, eval_func=ai14s, use_tt=True, maxdepth=8))

実行結果（実行結果はランダムなので下記と異なる場合があります）

(0, 0)
(2, 1)

今回の記事のまとめ

今回の記事では ListBoard による 処理速度の低下の原因を検証 し、処理速度がほとんど低下しないように修正 しました。また、修正前の ListBoard を利用した場合に発生する 無限ループの原因を検証し、その バグが発生しないように修正 しました。

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

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル
marubatsu.py	本記事で更新した marubatsu_new.py
ai.py	本記事で更新した ai_new.py
tree.py	本記事で更新した tree_new.py
util.py	本記事で更新した util_new.py

次回の記事

1. 正確には一つ目の添字は ListBoard の __getitem__ メソッド、二つ目の添字は ListBoardwithKey の __getitem__ メソッドが呼び出されていますが、冗長なので以後も ListBoard の __getitem__ を呼び出すと表記することにします ↩

2. () が省略されているのでそう見えないかもしれませんが、board[1, 2] は (1, 2) という tuple の添字の () を省略したもので、省略しない場合は board[(1, 2)] と記述します ↩