目次と前回の記事

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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

処理速度の変化の検証

前回の記事では座標を表すデータ構造を修正しましたが、その結果ベンチマークの 処理速度 が下記の表のように変化しました。上段の数値が前回の記事の修正前の結果 で、下段の数値が修正後の結果 を表します。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	12391.16 回/秒 11848.56 回/秒	969.45 回/秒 829.88 回/秒	17.4 ms 22.7 ms
ListBoard	`True`	12340.74 回/秒 15077.96 回/秒	1882.32 回/秒 1951.29 回/秒	17.6 ms 20.6 ms
List1dBoard	`False`	11801.20 回/秒 9059.91 回/秒	956.38 回/秒 681.72 回/秒	17.6 ms 31.7 ms
List1dBoard	`True`	12300.84 回/秒 10490.45 回/秒	1875.35 回/秒 1528.86 回/秒	18.6 ms 30.2 ms

今回の記事では 処理速度の変化 の原因の 検証と改善 を行うことにします。その際に ListBoard クラスと List1dBoard クラスでは行われる処理が異なるので、別々に検証することにします。

ListBoard クラスの処理の検証と修正

上記の表から、ListBoard クラスを利用した場合は 処理速度が以下のように変化 することがわかります。

count_linemark が False の場合は ai2 VS ai2、a14s VS ai2 の処理速度が低下する
count_linemark が True の場合は ai2 VS ai2、a14s VS ai2 の処理速度が速くなる
いずれの場合も ai_abs_dls の処理速度が低下する

修正前と修正後の処理の違い

処理速度の 変化の原因を検証 するために、前回の記事の修正によって ListBoard 関連の処理の変化 を検証することにします。具体的には以下の処理が変化しました。

`getmark` の処理の違い

getmark の処理が以下のように変化しました。下記では、修正後の getmark で呼び出される xy_to_move と getmark_by_move の定義も表記しました。

# 修正前
def getmark(self, x, y):
    return self.board[x][y]   

# 修正後
def getmark(self, x, y):
    return self.getmark_by_move(self.xy_to_move(x, y))

def xy_to_move(self, x, y):
    return (x, y)    

def getmark_by_move(self, move):
    x, y = move
    return self.board[x][y]

上記の修正を行った理由は、ゲーム盤を表すクラス に 共通するメソッド として xy_to_move と getmark_by_move を定義することで、ゲーム盤を表す クラスの種類に関わらず、同じ getmark メソッドの定義 で (x, y) のマスのマークを参照 できるようにするためです。

実際に getmark と setmark は ゲーム盤を表すクラス の 基底クラス である Board クラスのメソッドとして定義し、ListBoard や List1dBoard クラスではそれらをそのまま 継承して利用 しています。

ただし、修正前と修正後のプログラムを比較すると、明らかに 修正後の getmark の方が 多くの処理を行う ため、処理速度が低下 します。

`setmark` の違い

プログラムは省略しますが、setmark も上記と同様の理由で 処理速度が低下 します。

`getmark_by_move` と `setmark_by_move` の定義

ゲーム盤のクラスの座標¹を仮引数としてマークの 参照と配置 を行う getmark_by_move と setmark_by_move を定義 しました。getmark_by_move と setmark_by_move が行う処理は 修正前の setmark と getmark とほぼ同じ ですが、下記のプログラムのように x, y = move によって move から x と y の座標を計算 する処理が 増えた分だけ処理速度が低下 します。

# 修正前
def getmark(self, x, y):
    return self.board[x][y]  

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

# 修正後
def getmark_by_move(self, move):
    x, y = move
    return self.board[x][y]  

def setmark_by_move(self, move, mark):
    x, y = move
略
    self.board[x][y] = mark

`calc_legal_moves` の違い

合法手の一覧を計算する calc_legal_moves の中で、 (x, y) のマスを参照する処理を getmark メソッドの呼び出しから、getmark メソッドの返り値である self.board[x][y] を直接記述 するように修正しました。この修正によって getmark メソッドを 9 回分呼び出さなくて済むようになった分だけ 処理速度が向上 します。

# 修正前
def calc_legal_moves(self):
    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

# 修正後
def calc_legal_moves(self):
    legal_moves = [(x, y) for y in range(self.BOARD_SIZE) 
                        for x in range(self.BOARD_SIZE)
                        if self.board[x][y] == Marubatsu.EMPTY]
    return legal_moves

`move` の違い

move メソッドの座標を代入する 仮引数を x, y から ゲーム盤のクラスの座標を代入する move に、マークを配置する処理を setmark_by_move で呼び出すように修正した。仮引数の数が 1 つ少なくなる分だけ処理速度が遅くなるはず ですが、代入処理は非常に短い処理時間で行えるので、ベンチマークの数値として 目に見えるほどの影響はない と思います。

# 修正前
def move(self, x, y, check_coord=False):
略
        self.board.setmark(x, y, self.turn)
略

# 修正後
def move(self, move, check_coord=False):
略
        self.board.setmark_by_move(move, self.turn)
略

`move` メソッドを呼び出す際の展開処理の違い

上記のように move メソッドの仮引数が変化 した結果、ai14s や ai_abs_dls などで move メソッドを呼び出す 際に実行する下記のようなプログラムで x, y = move という展開処理を行わなくて済む ようになり、その分だけ 処理速度が向上 します。

# 修正前
    legal_moves = mb_orig.calc_legal_moves()
略
    for move in legal_moves:
        x, y = move
        mb_orig.move(x, y)
略

# 修正前（下記は ai_by_mmscore 内の処理です）
    legal_moves = mb_orig.calc_legal_moves()
略
    for move in legal_moves:
        mb_orig.move(move)
略

ただし、上記で move メソッドを呼び出す前 に行われていた x, y = move の展開処理 は、先程説明したように move メソッドから呼び出される setmark_by_move メソッド内で行われます。そのため、修正前と修正後で x, y = move の展開処理が行われる数は変化しない ので 全体の処理時間はほぼ変わらない と考えて良いでしょう。

処理の違いによる処理速度の影響の考察

上記から、前回の記事の修正 によって 処理時間が以下のように変化する 事がわかります。

getmark と setmark メソッドの 処理時間が増える
calc_legal_moves メソッドの 処理時間が減る
それ以外の処理時間はほぼ変わらない

処理時間に影響を及ぼすメソッドの呼び出し回数の検証

getmark、setmark、calc_legal_moves の呼び出しが 処理時間に影響する ことがわかったので、ベンチマークで実行する ai2 VS ai2、ai14s VS ai2、ai_abs_dls の処理を行う際に それらのメソッドが呼び出される回数を検証 することにします。

`getmark` が呼び出される状況

ai2 VS ai2、ai14s VS ai2、ai_abs_dls の処理を行う際に getmark が呼び出される状況 は、VSCode の Ctrl + F で呼び出される 検索機能 で ai.py などのプログラムが記述された モジュールのファイルを検索する ことで調べることができます。調べた結果、下記の状況で getmark が呼び出されることが確認できました。

ai14s 内で、「斜め方向に〇×〇が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合」を調べる下記のプログラムで 最大 9 回 呼び出される。また、ai14s を呼び出すと 合法手の数だけ 下記のプログラムが呼び出される

最大 9 回としたのは、以前の記事で説明したように、and と or 演算子 には 短絡評価 によって すべての条件式が計算されない場合がある からです。

# 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
if mb.board.getmark(1, 1) == Marubatsu.CROSS and \
    (mb.board.getmark(0, 0) == mb.board.getmark(2, 2) == Marubatsu.CIRCLE or \
    mb.board.getmark(2, 0) == mb.board.getmark(0, 2) == Marubatsu.CIRCLE) and \
    (mb.board.getmark(1, 0) == Marubatsu.CROSS or \
    mb.board.getmark(0, 1) == Marubatsu.CROSS or \
    mb.board.getmark(2, 1) == Marubatsu.CROSS or \
    mb.board.getmark(1, 2) == Marubatsu.CROSS) and \
    mb.move_count == 4:
    return score_special

特定の直線上のマークが同じであるかを判定する ListBoard クラスの is_same メソッドの下記のプログラムで 3 回 呼び出される。また、is_same メソッドは 着手を行った後の 勝敗判定 を行う際に呼び出されるメソッドで、手数が 5 以上 で count_linemark が False の場合に is_winner メソッドから 2 ~ 4 回 呼び出される。従って、着手の処理が行われる と getmark は以下の回数が呼び出される
- 手数が 5 以下 の場合は 呼び出されない
- count_linemark が True の場合は 呼び出されない
- 手数が 5 以上 で count_linemark が False の場合は最大 3 × 4 = 12 回 呼び出される

text_list = [self.getmark(x + i * dx, y + i * dy) 
             for i in range(self.BOARD_SIZE)]

特定の直線上のマークの数を数える ListBoard クラスの count_marks メソッドの下記のプログラムで 3 回 呼び出される。count_marks メソッドは count_markpats メソッドが呼び出された際に呼び出されるメソッドで、count_linemark が False の場合に is_winner メソッドから 8 回 呼び出される。また、count_markpats メソッドは ai14s から合法手の数 だけ呼び出される。従って、ai14s を実行するたびに 3 × 8 × 合法手の数 = 24 × 合法手の数 回呼び出される

for _ in range(self.BOARD_SIZE):
    count[self.getmark(x, y)] += 1
    x += dx
    y += dy

同一局面を計算する util.py の calc_same_boardtexts の下記のプログラムで呼び出される。data に代入される list には 7 つの要素 があるので 7 × 3 × 3 = 63 回 呼び出される。calc_same_boardtexts は、ai_abs_dls 内でノードの評価値を 置換表に登録する際 に下記のプログラムで呼び出される

# calc_same_boardtexts のプログラム
for xa, xb, xc, ya, yb, yc, xa2, xb2, xc2, ya2, yb2, yc2 in data:
    txt = ""
    for x in range(mb.BOARD_SIZE):
        for y in range(mb.BOARD_SIZE):
            txt += mb.board.getmark(xa * 2 + xb * x + xc * y, ya * 2 + yb * x + yc * y)

# ai_abs_dls のプログラム
if use_tt:
    boardtxtlist = calc_same_boardtexts(mborig, bestmove)

下記は getmark メソッドが呼び出される状況と回数をまとめた表になります。

状況	回数
`ai14s` を呼び出す `count_linemark` が `False` の場合 `count_linemark` が `True` の場合	最大 9 + 24 = 33 × 合法手の数最大 9 × 合法手の数
手数が 5 以上、`count_linemark` が `False` で着手を行った場合	最大 12 回
`ai_abs_dls` を呼び出す	63 × 置換表に評価値を登録したノードの数以上

合法手の数 は 9 - 手数 なので、ai14s VS ai2 の対戦で ai14s が先手の場合 は 合法手の数が 9, 7, 5, 3, 1 の場合で ai14s が呼び出されます。従って、ai14s が先手の場合 で ai14s が呼び出された場合の 合法手数の合計 は 9 + 7 + 5 + 3 + 1 = 25 となります。ai14s が後手 の場合は 8 + 6 + 4 + 2 = 20 なので、先手の方が合法手の数の合計は多く なります。

ai2 は合法手の中からランダムに選択する処理を行うだけなので、ai2 の処理の中で 着手の処理は行われません。そのため、ai2 VS ai2 では 1 試合で行われる 手数が 5 以上の着手の処理の回数は最大で 5² です。一方 ai14s は 子ノードの評価値を計算 する際に 着手の処理 を行います。子ノードの数は合法手の数と同じなので、ai14s が先手 で手数が 5 以上の場合は 最大で 5 + 5 + 3 + 1 = 14 回の着手の処理 が行われます。

上記から以下のことがわかります。

ai2 VS ai2 の対戦で getmark が呼び出される回数
- count_linemark が False の場合は 1 試合 で最大 12 × 5 = 60 回
- count_linemark が True の場合は 呼び出されない
ai14s VS ai2 の対戦で getmark が呼び出される回数
- count_linemark が False の場合は最大で 33 × 25 + 12 × 14 = 993 回 呼び出される
- count_linemark が True の場合は最大で 9 × 25 = 225 回 呼び出される
ai_abs_dls の計算では、下記の状況で getmark が呼び出される
- 置換表にノードの評価値を登録 する処理を行う際
- リーフノード に対して ai14s が評価値を計算する際
- 子ノードの局面を計算 するために 着手を行う 際
  上記の中で、置換表にノードの評価値を登録 する処理で getmark が呼び出される回数は、置換表に登録された局面の数から類推³ することができる。ベンチマークで ai_abs_dls が計算を行う ゲーム開始時の局面 に対して ai_abs_dls を呼び出した際に 置換表に登録された局面の数 は、下記のプログラムのように analyze=True を実引数に記述した場合の 返り値の置換表を表す tt 属性の要素の数を数える ことで計算できる。実行結果からその数は 3219 なので 63 × 3219 = 202797 という、20 万回以上 もの呼び出しが行われることが確認できる

from ai import ai14s, ai_abs_dls
from marubatsu import Marubatsu

mb = Marubatsu()
eval_params = {"minimax": True}
result = ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, 
                    use_tt=True, maxdepth=8, analyze=True)
print(len(result["tt"]))

実行結果

下記は上記をまとめた表です。

処理	`count_linemark`	1 試合での `getmark` の回数
`ai2` VS `ai2`	`False`	最大 60 回
`ai2` VS `ai2`	`True`	0 回
`ai14s` VS `ai2`	`False`	最大 993 回
`ai14s` VS `ai2`	`True`	最大 225 回
`ai_abs_dls`		20 万回以上

上記から以下の事が推測されます。

count_linemark が False の場合の ai2 VS ai14s では 約 1000 回 getmark が呼び出されるため処理速度が遅くなった
ai_abs_dls は 20 万回以上 もの getmark が呼び出されるため 処理速度が遅くなった
それ以外の場合 はそれほど 多くの回数の getmark は呼び出されない ので、getmark による 処理速度の低下の影響はあまりない

また、下記の 処理速度の違い から 上記の推測がおそらく正しい ことが裏付けられます。なお、count_linemark が True の場合の ai2 VS ai2 の 処理速度が大きく向上 している理由は、この後で説明するように calc_legal_moves の修正の影響 によるものです。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	12391.16 回/秒 11848.56 回/秒	969.45 回/秒 829.88 回/秒	17.4 ms 22.7 ms
ListBoard	`True`	12340.74 回/秒 15077.96 回/秒	1882.32 回/秒 1951.29 回/秒	17.6 ms 20.6 ms

`setmark` が呼び出される状況

setmark が呼び出される状況を調べたところ、Marubatsu クラスの place_mark メソッドからのみ呼び出されていることが確認できました。place_mark は人間が着手を行う場合に利用する、座標のチェックを伴う着手を行うメソッドで、AI どうしの対戦で呼び出されることはありません。従って setmark の修正による ベンチマークの処理速度の変更はありません。

`calc_legal_moves` が呼び出される状況

calc_legal_moves はベンチマークでは下記の状況で呼び出されます

ai2 と ai14s が最善手を計算する際に 1 回 呼び出される
ai_abs_dls が リーフノード以外のノード の評価値を計算する際に 1 回 呼び出される

従って、ai2 VS ai2 と ai14s VS ai2 では、いずれの場合も 1 回の対戦で行われた 手数の数だけ calc_legal_moves が呼び出されるので、1 試合あたりの回数は 5 ~ 9 回 となります。先ほど説明したように 1 回の calc_legal_moves メソッドの呼び出しで 9 回分の getmark の呼び出し処理を行わずに済む ようになるので、1 回の対戦で 45 ~ 81 回分 の処理時間の短縮が行われます。このことから、calc_legal_moves の修正によって ai2 VS ai2 と ai14s VS ai2 の処理速度はいずれも向上することがわかります。先ほど検証した getmark による処理速度の低下と、calc_legal_moves による処理速度の向上をあわせたものが、下記の表の結果に表れることになります。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	12391.16 回/秒 11848.56 回/秒	969.45 回/秒 829.88 回/秒	17.4 ms 22.7 ms
ListBoard	`True`	12340.74 回/秒 15077.96 回/秒	1882.32 回/秒 1951.29 回/秒	17.6 ms 20.6 ms

count_linemark が True の場合に ai2 VS ai2 の 処理速度が向上した理由 は、その場合は getmark の呼び出しが行われない ため、cal_legal_moves による 処理速度の向上の影響だけが現れた ためでしょう。

ai_abs_dls では getmark の呼び出し回数が 20 万回以上と多い ため、calc_legal_moves による処理速度の向上があっても、全体として処理速度が低下 するという結果になります。

処理速度の改善

上記の検証から、Board クラスに定義した getmark の処理は、ListBoard クラスの getmark の処理 として利用するには 無駄が多い ため 処理速度が低下 したことが確認できました。そこで、下記のプログラムのように ListBoard に適した getmark メソッドを定義 して オーバーライド することで ListBoard クラスの処理速度を向上 することができます。

なお、プログラムに難しい所はないと思いますので説明と修正箇所は省略します。

from marubatsu import ListBoard

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

ListBoard.getmark = getmark

なお、先程説明したように AI どうしの対戦では setmark は呼び出されない ので、setmark は修正せずに、Board クラスで定義されたものをそのまま利用 することにします。

`is_winner`、`is_same`、`count_marks`、`count_markpats` の修正

ListBoard クラスの メソッドの外からマスの値を参照 する場合は、ポリモーフィズムの仕組みから getmark メソッドを利用する必要 がありますが、ListBoard クラスの メソッド内でマスの値を参照 する場合は calc_legal_moves メソッドのように 直接 board 属性の値を参照 したほうが 処理が速く なります。そのような処理は is_same と count_marks メソッドで行われているので、その処理を修正することにします。

また、is_same の処理を修正する際に、無駄な処理が行われていることが判明 したので修正します。is_same メソッドは下記のプログラムのように定義されていますが、is_same メソッドの仮引数 coord に代入される値は下記のプログラムのように is_winner メソッドに記述された is_same メソッドの呼び出しによって [x, y] のような list が代入 されます。

def is_same(self, mark, coord, dx, dy):
    x, y = coord
略

def is_winner(self, player, last_move):
略
    if self.is_same(player, coord=[0, y], dx=1, dy=0)
略

ただし、is_same メソッド内の処理で 必要となる座標 は x, y 座標だけ であり、仮引数 coord の値が直接利用されることはありません。そのため、is_same の 座標を表す仮引数 に list を代入し、それを is_same で x, y 座標に展開 するのは 無駄な処理 です。

そこで、下記のプログラムのように、is_same の 座標を代入する仮引数を x と y に修正 し、is_winner メソッドの 座標を表す実引数 を下記のプログラムのように x, y 座標に分けて記述 することで、無駄な展開処理を行わない ようにすることができます。

def is_same(self, mark, x, y, dx, dy):
略

def is_winner(self, player, last_move):
略
    if self.is_same(player, x=0, y=y, dx=1, dy=0)
略

また、同様の理由 で count_marks メソッドの 座標を代入する仮引数を x と y に修正 することにします。

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

8、11、14 行目：is_same の実引数に x 座標と y 座標を記述するように修正した
22、52 行目：座標を代入する仮引数を coord から x と y に修正した
22 行目と 52 行目の後にあった x, y = coord を削除した
23、55 行目：getmark の代わりに board 属性からマスの値を参照するように修正した
37、39、42、45 行目：count_marks の実引数に x, y 座標を記述するように修正した
45 行目：元の x 座標の値は 2 であったが、これはゲーム盤のサイズ - 1 としたほうが良いことに気づいたので x = self.BOARD_SIZE - 1 に修正した

 1  from marubatsu import Markpat
 2  from collections import defaultdict
 3  
 4  def is_winner(self, player, last_move):
 5      x, y = last_move
 6      if self.count_linemark:
元と同じなので省略
 7      else:
 8          if self.is_same(player, x=0, y=y, dx=1, dy=0) or self.is_same(player, x=x, y=0, dx=0, dy=1):
 9              return True
10          # 左上から右下方向の判定
11          if x == y and self.is_same(player, x=0, y=0, dx=1, dy=1):
12              return True
13          # 右上から左下方向の判定
14          if x + y == self.BOARD_SIZE - 1 and self.is_same(player, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1):
15              return True
16      
17      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
18      return False
19  
20  ListBoard.is_winner = is_winner
21  
22  def is_same(self, mark, x, y, dx, dy):
23      text_list = [self.board[x + i * dx][y + i * dy]  
24                   for i in range(self.BOARD_SIZE)]
25      line_text = "".join(text_list)
26      return line_text == mark * self.BOARD_SIZE
27  
28  ListBoard.is_same = is_same
29  
30  def count_markpats(self, turn, last_turn):
31      markpats = defaultdict(int)
32      
33      if self.count_linemark:
元と同じなので省略
34      else:
35          # 横方向と縦方向の判定
36          for i in range(self.BOARD_SIZE):
37              count = self.count_marks(turn, last_turn, x=0, y=i, dx=1, dy=0, datatype="tuple")
38              markpats[count] += 1
39              count = self.count_marks(turn, last_turn, x=i, y=0, dx=0, dy=1, datatype="tuple")
40              markpats[count] += 1
41          # 左上から右下方向の判定
42          count = self.count_marks(turn, last_turn, x=0, y=0, dx=1, dy=1, datatype="tuple")
43          markpats[count] += 1
44          # 右上から左下方向の判定
45          count = self.count_marks(turn, last_turn, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1, datatype="tuple")
46          markpats[count] += 1
47  
48      return markpats  
49  
50  ListBoard.count_markpats = count_markpats
51  
52  def count_marks(self, turn, last_turn, x, y, dx, dy, datatype="dict"):  
53      count = defaultdict(int)
54      for _ in range(self.BOARD_SIZE):
55          count[self.board[x][y]] += 1
元と同じなので省略
56      
57  ListBoard.count_marks = count_marks

行番号のないプログラム

from marubatsu import Markpat
from collections import defaultdict

def is_winner(self, player, last_move):
    x, y = last_move
    if self.count_linemark:
        if self.rowcount[player][y] == self.BOARD_SIZE or \
        self.colcount[player][x] == self.BOARD_SIZE:
            return True
        # 左上から右下方向の判定
        if x == y and self.diacount[player][0] == self.BOARD_SIZE:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.diacount[player][1] == self.BOARD_SIZE:
            return True
    else:
        if self.is_same(player, x=0, y=y, dx=1, dy=0) or \
        self.is_same(player, x=x, y=0, dx=0, dy=1):
            return True
        # 左上から右下方向の判定
        if x == y and self.is_same(player, x=0, y=0, dx=1, dy=1):
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.is_same(player, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1):
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

ListBoard.is_winner = is_winner

def is_same(self, mark, x, y, dx, 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

ListBoard.is_same = is_same

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)
    
    if self.count_linemark:
        for countdict in [self.rowcount, self.colcount, self.diacount]:
            for circlecount, crosscount in zip(countdict[Marubatsu.CIRCLE], countdict[Marubatsu.CROSS]):
                emptycount = self.BOARD_SIZE - circlecount - crosscount
                if last_turn == Marubatsu.CIRCLE:
                    markpats[(circlecount, crosscount, emptycount)] += 1
                else:
                    markpats[(crosscount, circlecount, emptycount)] += 1
    else:
        # 横方向と縦方向の判定
        for i in range(self.BOARD_SIZE):
            count = self.count_marks(turn, last_turn, x=0, y=i, dx=1, dy=0, datatype="tuple")
            markpats[count] += 1
            count = self.count_marks(turn, last_turn, x=i, y=0, dx=0, dy=1, datatype="tuple")
            markpats[count] += 1
        # 左上から右下方向の判定
        count = self.count_marks(turn, last_turn, x=0, y=0, dx=1, dy=1, datatype="tuple")
        markpats[count] += 1
        # 右上から左下方向の判定
        count = self.count_marks(turn, last_turn, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1, datatype="tuple")
        markpats[count] += 1

    return markpats  

ListBoard.count_markpats = count_markpats

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

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

修正箇所

from marubatsu import Markpat
from collections import defaultdict

def is_winner(self, player, last_move):
    x, y = last_move
    if self.count_linemark:
元と同じなので省略
    else:
-       if self.is_same(player, coord=[0, y], dx=1, dy=0) or \
+       if self.is_same(player, x=0, y=y, dx=1, dy=0) or \
-       self.is_same(player, coord=[x, 0], dx=0, dy=1):
+       self.is_same(player, x=x, y=0, dx=0, dy=1):
            return True
        # 左上から右下方向の判定
-       if x == y and self.is_same(player, coord=[0, 0], dx=1, dy=1):
+       if x == y and self.is_same(player, x=0, y=0, dx=1, dy=1):
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
-           self.is_same(player, coord=[self.BOARD_SIZE - 1, 0], dx=-1, dy=1):
+           self.is_same(player, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1):
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

ListBoard.is_winner = is_winner

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

ListBoard.is_same = is_same

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)
    
    if self.count_linemark:
元と同じなので省略
    else:
        # 横方向と縦方向の判定
        for i in range(self.BOARD_SIZE):
-           count = self.count_marks(turn, last_turn, coord=[0, i], dx=1, dy=0, datatype="tuple")
+           count = self.count_marks(turn, last_turn, x=0, y=i, dx=1, dy=0, datatype="tuple")
            markpats[count] += 1
-           count = self.count_marks(turn, last_turn, coord=[i, 0], dx=0, dy=1, datatype="tuple")
+           count = self.count_marks(turn, last_turn, x=i, y=0, dx=0, dy=1, datatype="tuple")
            markpats[count] += 1
        # 左上から右下方向の判定
-       count = self.count_marks(turn, last_turn, coord=[0, 0], dx=1, dy=1, datatype="tuple")
+       count = self.count_marks(turn, last_turn, x=0, y=0, dx=1, dy=1, datatype="tuple")
        markpats[count] += 1
        # 右上から左下方向の判定
-       count = self.count_marks(turn, last_turn, coord=[2, 0], dx=-1, dy=1, datatype="tuple")
+       count = self.count_marks(turn, last_turn, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1, datatype="tuple")
        markpats[count] += 1

    return markpats  

ListBoard.count_markpats = count_markpats

-def count_marks(self, turn, last_turn, coord, dx, dy, datatype="dict"):  
+def count_marks(self, turn, last_turn, x, y, dx, dy, datatype="dict"):  
-   x, y = coord
    count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
-       count[self.getmark(x, y)] += 1
+       count[self.board[x][y]] += 1
元と同じなので省略
    
ListBoard.count_marks = count_marks

ベンチマークの実行

上記の修正後に、下記のプログラムで ListBoard に対する ベンチマークを実行 します。

from util import benchmark

boardclass = ListBoard
for count_linemark in [False, True]:
    print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
    benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})
    print()

実行結果

boardclass: ListBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 14579.71it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

ai14s VS ai2
100%|██████████| 50000/50000 [00:44<00:00, 1113.82it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.1%    0.0%   11.9%
total   93.5%    0.0%    6.5%

ai_abs_dls
 18.0 ms ±   1.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

boardclass: ListBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 15309.97it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

ai14s VS ai2
100%|██████████| 50000/50000 [00:25<00:00, 1984.76it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.1%    0.0%   11.9%
total   93.5%    0.0%    6.5%

ai_abs_dls
 17.4 ms ±   0.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は上記の結果を先程の表に加えたものです。下段が上記の実行結果 です。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	12391.16 回/秒 11848.56 回/秒 14579.71 回/秒	969.45 回/秒 829.88 回/秒 1113.82 回/秒	17.4 ms 22.7 ms 18.0 ms
ListBoard	`True`	12340.74 回/秒 15077.96 回/秒 15309.97 回/秒	1882.32 回/秒 1951.29 回/秒 1984.76 回/秒	17.6 ms 20.6 ms 17.4 ms

上記から、AI どうしの対戦 では count_linemark が False の場合の処理速度が、上段の前回の記事の修正前 よりも速くなる ことが確認できます。なお、AI どうしの対戦 では count_linemark が True の場合は getmark がほとんど呼び出されていないため処理速度は 中段とほとんど変わりません。

また、ai_abs_dls の処理速度が 上段とほぼ同じ になることが確認できます。ai_abs_dls の処理速度が 上段とほとんど変わらない理由 は、おそらく処理速度の向上につながる calc_legal_moves の処理時間が、全体の処理時間の中で 小さな割合 だからだと思います。興味があるかたは実際に検証してみて下さい。

List1dBoard クラスの処理の検証と修正

次に、List1dBoard クラスの処理の検証と修正を行いますが、その前に List1dBoard クラスに下記のメソッドを定義する必要があります。

`is_same` と `is_winner` メソッドの定義

List1dBoard クラスは ListBoard クラスを継承して定義 しているので、オーバーライドしていない is_same と is_winner メソッドは ListBoard クラスの メソッドがそのまま呼び出されます。先ほど is_same と is_winner で行われていた getmark メソッドの呼び出しを、board 属性から直接参照 するように修正したので、is_same メソッドと is_winner メソッドを下記のプログラムのように 定義してオーバーライド する必要があります。

4、14 行目：board 属性のインデックスに数値座標を計算するように修正する

 1  from marubatsu import List1dBoard
 2  
 3  def is_same(self, mark, x, y, dx, dy):
 4      text_list = [self.board[y + i * dy + (x + i * dx) * self.BOARD_SIZE]
 5                   for i in range(self.BOARD_SIZE)]
 6      line_text = "".join(text_list)
 7      return line_text == mark * self.BOARD_SIZE
 8  
 9  List1dBoard.is_same = is_same
10  
11  def count_marks(self, turn, last_turn, x, y, dx, dy, datatype="dict"):    
12      count = defaultdict(int)
13      for _ in range(self.BOARD_SIZE):
14          count[self.board[y + x * self.BOARD_SIZE]] += 1
元と同じなので省略
15      
16  List1dBoard.count_marks = count_marks

行番号のないプログラム

from marubatsu import List1dBoard

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

List1dBoard.is_same = is_same

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

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

修正箇所

from marubatsu import List1dBoard

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

List1dBoard.is_same = is_same

def count_marks(self, turn, last_turn, x, y, dx, dy, datatype="dict"):    
    count = defaultdict(int)
    for _ in range(self.BOARD_SIZE):
-       count[self.board[x][y] += 1
+       count[self.board[y + x * self.BOARD_SIZE]] += 1
元と同じなので省略
    
List1dBoard.count_marks = count_marks

`getmark` メソッドの修正

ListBoard で行った検証と同様の理由から、List1dBoard クラスの getmark を下記のプログラムのように修正することで、処理速度の向上が見込めるはず です。

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

List1dBoard.getmark = getmark

ベンチマークの実行

上記の修正後に下記のプログラムで List1dBoard に対する ベンチマークを実行 します。

boardclass = List1dBoard
for count_linemark in [False, True]:
    print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
    benchmark(mbparams={"boardclass": boardclass, "count_linemark": count_linemark})
    print()

実行結果

boardclass: List1dBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:04<00:00, 11818.58it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

ai14s VS ai2
100%|██████████| 50000/50000 [00:47<00:00, 1050.48it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.1%    0.0%   11.9%
total   93.5%    0.0%    6.5%

ai_abs_dls
 20.9 ms ±   1.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

boardclass: List1dBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:04<00:00, 10430.42it/s]
count     win    lose    draw
o       29454   14352    6194
x       14208   29592    6200
total   43662   43944   12394

ratio     win    lose    draw
o       58.9%   28.7%   12.4%
x       28.4%   59.2%   12.4%
total   43.7%   43.9%   12.4%

ai14s VS ai2
100%|██████████| 50000/50000 [00:31<00:00, 1591.74it/s]
count     win    lose    draw
o       49446       0     554
x       44043       0    5957
total   93489       0    6511

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.1%    0.0%   11.9%
total   93.5%    0.0%    6.5%

ai_abs_dls
 24.3 ms ±   2.9 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は上記の結果を先程の表に加えたものです。下段が上記の実行結果です。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
List1dBoard	`False`	11801.20 回/秒 9059.91 回/秒 11818.58 回/秒	956.38 回/秒 681.72 回/秒 1050.48 回/秒	17.6 ms 31.7 ms 20.9 ms
List1dBoard	`True`	12300.84 回/秒 10490.45 回/秒 10430.42 回/秒	1875.35 回/秒 1528.86 回/秒 1591.74 回/秒	18.6 ms 30.2 ms 24.3 ms

上記から、すべての場合で 上記の修正前 の中段の結果よりも 処理速度が向上 していますが、前回の記事の修正前 の上段の結果と比べて ほとんど変わらない か 処理速度が遅い という結果になります。このことから、前回の記事で修正した List1dBoard クラスの処理には getmark 以外 にも 処理速度が低下する原因がある ことがわかります。その原因について少し考えてみて下さい。

Move クラスによる処理速度の低下

前回の記事では、List1dBoard クラスの座標を 最初は 数値座標を表す 数値型のデータ とし、合法手を計算する calc_legal_moves を下記のプログラムのように定義しました。

def calc_legal_moves(self):
    legal_moves = [move for move in range(self.BOARD_SIZE ** 2)]
    return legal_moves

上記のように List1dBoard クラスの座標を 数値型のデータで表現 すると、x, y = move のような 展開処理を行えない ため、marubatsu.py や ai.py などで 座標の展開処理 を行うプログラムを 修正する必要が生じます。そこで、List1dBoard クラスの座標を表す下記のプログラムのような __getitem__ メソッドが定義された Move クラス を定義し、calc_legal_moves メソッドでは List1dBoard クラスの 合法手 を Move クラスのインスタンス で表現するという、ポリモーフィズム の仕組みを利用することでその問題を解決しました。

class List1dBoard(ListBoard):
    class Move:
        def __init__(self, move, board_size):
            self.move = move
            self.board_size = board_size
    
        def __getitem__(self, key):
            if key == 0:
                return self.move // self.board_size
            elif key == 1:
                return self.move % self.board_size
            else:
                raise IndexError

    def calc_legal_moves(self):
        legal_moves = [self.Move(move, self.BOARD_SIZE) for move in range(self.BOARD_SIZE ** 2) 
                            if self.board[move] == Marubatsu.EMPTY]
        return legal_moves

略

上記の Move クラスを定義して利用することで、x, y = move のような 座標の展開処理 を 修正する必要がなくなる という利点が生じますが、List1dBoard クラスの 座標を数値型のデータで記述 する処理と比較して、self.Move(move, self.BOARD_SIZE) のように Move クラスの インスタンスを作成する ほうが 処理時間が長くなります。

また、以前の記事で説明したように、__getitem__ メソッドによる 添字の処理 は 処理速度の低下の原因 となる場合があります。そのことを実際に比較してみることにします。

下記は List1dBoard の Move クラスを定義 し、5 という 数値座標のインスタンスを作成 してその 展開処理の処理時間を計測 するプログラムです。実行結果から展開処理で (1, 2) という座標が正しく計算され、その 処理時間の平均が 615 ns であることが確認できます。

class Move:
    def __init__(self, move, board_size):
        self.move = move
        self.board_size = board_size

    def __getitem__(self, key):
        if key == 0:
            return self.move // self.board_size
        elif key == 1:
            return self.move % self.board_size
        else:
            raise IndexError
        
move = Move(5, 3)
x, y = move
print(x, y)
%timeit x, y = move

実行結果

1 2
615 ns ± 6.13 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は整数の数値座標から x, y 座標を計算して返す 処理を行う move_to_xy という関数を定義し、その関数を利用して 5 という数値座標から x, y 座標を計算 する処理の 処理時間を計測 するプログラムです。実行結果から move_to_xy で (1, 2) という座標が正しく計算され、その 処理時間の平均が 106 ns という、Move クラスを利用した場合の 約 1/6 の処理時間であることが確認できます。

def move_to_xy(move):
    return move // 3, move % 3

move = 5
x, y = move_to_xy(move)
print(x, y)
%timeit x, y = move_to_xy(move)

実行結果

1 2
106 ns ± 3.07 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

一般的 には Move クラスを利用した座標データのほうが x, y 座標の計算処理 を x, y = move のように 直観的に分かりやすく記述できる のでそちらのほうがよいと思いますが、AI の関数の処理などの 処理速度が極めて重要な場合 は上記のように 数値座標として整数 を利用し、x, y 座標の計算を行う関数を定義 したほうが 処理速度が速くなる ので本記事でもそのようにプログラムを修正することにします。

なお、__getitem__ メソッドを持つ Move クラスを定義して 展開処理で x, y 座標を計算 するのと、x, y 座標を計算するメソッドを定義 するのは、どちらも特定のメソッドを持つようにゲーム盤のクラスを定義するので、ポリモーフィズムの仕組みを利用 していることに変わりはありません。

List1dBoard クラスの修正

まず、List1dBoard クラスのメソッドの修正を行います。

`calc_legal_moves` の修正

下記は calc_legal_moves メソッドを修正したプログラムです。

2 行目：座標を表すデータを整数型の move に修正する

1  def calc_legal_moves(self):
2      legal_moves = [move for move in range(self.BOARD_SIZE ** 2) 
3                          if self.board[move] == Marubatsu.EMPTY]
4      return legal_moves
5   
6  List1dBoard.calc_legal_moves = calc_legal_moves

行番号のないプログラム

def calc_legal_moves(self):
    legal_moves = [move for move in range(self.BOARD_SIZE ** 2) 
                        if self.board[move] == Marubatsu.EMPTY]
    return legal_moves
 
List1dBoard.calc_legal_moves = calc_legal_moves

修正箇所

def calc_legal_moves(self):
-   legal_moves = [self.Move(move, self.BOARD_SIZE) for move in range(self.BOARD_SIZE ** 2) 
+   legal_moves = [move for move in range(self.BOARD_SIZE ** 2) 
                        if self.board[move] == Marubatsu.EMPTY]
    return legal_moves
 
List1dBoard.calc_legal_moves = calc_legal_moves

`getmark_by_move` と `setmark_by_move` の修正

下記は getmark_by_move と setmark_by_move メソッドを修正したプログラムです。

2、9、11 行目：move.move を move に修正する
8 行目：move が整数になったため x, y = move による展開処理を記述できなくなったので、x, y 座標を計算する処理に修正する必要がある

 1  def getmark_by_move(self, move):
 2      return self.board[move]    
 3  
 4  List1dBoard.getmark_by_move = getmark_by_move
 5  
 6  def setmark_by_move(self, move, mark):
 7     if self.count_linemark:
 8         x, y = move // self.BOARD_SIZE, move % self.BOARD_SIZE
元と同じなので省略
 9              changedmark = self.board[move]
元と同じなので省略
10      self.board[move] = mark
11      
12  List1dBoard.setmark_by_move = setmark_by_move

行番号のないプログラム

def getmark_by_move(self, move):
    return self.board[move]    

List1dBoard.getmark_by_move = getmark_by_move

def setmark_by_move(self, move, mark):
    if self.count_linemark:
        x, y = move // self.BOARD_SIZE, move % self.BOARD_SIZE
        if mark != Marubatsu.EMPTY:
            diff = 1
            changedmark = mark
        else:
            diff = -1
            changedmark = self.board[move]
        self.colcount[changedmark][x] += diff
        self.rowcount[changedmark][y] += diff
        if x == y:
            self.diacount[changedmark][0] += diff
        if x + y == self.BOARD_SIZE - 1:
            self.diacount[changedmark][1] += diff
    self.board[move] = mark
    
List1dBoard.setmark_by_move = setmark_by_move

修正箇所

def getmark_by_move(self, move):
-   return self.board[move.move]    
+   return self.board[move]    

List1dBoard.getmark_by_move = getmark_by_move

def setmark_by_move(self, move, mark):
    if self.count_linemark:
-       x, y = move
+       x, y = move // self.BOARD_SIZE, move % self.BOARD_SIZE
元と同じなので省略
-           changedmark = self.board[move.move]
+           changedmark = self.board[move]
元と同じなので省略
-   self.board[move.move] = mark
+   self.board[move] = mark
    
List1dBoard.setmark_by_move = setmark_by_move

`xy_to_move` の修正と `move_to_xy` の定義

下記は xy_to_move を修正したプログラムと、move_to_xy の定義です。move_to_xy は ListBoard でも定義する必要がある 点に注意が必要です。

2 行目：整数の数値座標を返すように修正した
6 ~ 9、11 ~ 12 行目：ゲーム盤のクラスの座標から x, y 座標を表す tuple を返すように List1dBoard と ListBoard の move_to_xy メソッドを定義する。ListBoard の move は x, y 座標を表す tuple なので move をそのまま返している

 1  def xy_to_move(self, x, y):
 2      return y + x * self.BOARD_SIZE
 3  
 4  List1dBoard.xy_to_move = xy_to_move
 5  
 6  def move_to_xy(self, move):
 7      return move // self.BOARD_SIZE, move % self.BOARD_SIZE
 8  
 9  List1dBoard.move_to_xy = move_to_xy
10  
11  def move_to_xy(self, move):
12      return move
13  
14  ListBoard.move_to_xy = move_to_xy

行番号のないプログラム

def xy_to_move(self, x, y):
    return y + x * self.BOARD_SIZE

List1dBoard.xy_to_move = xy_to_move

def move_to_xy(self, move):
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE

List1dBoard.move_to_xy = move_to_xy

def move_to_xy(self, move):
    return move

ListBoard.move_to_xy = move_to_xy

修正箇所

def xy_to_move(self, x, y):
-   return Move(y + x * self.BOARD_SIZE, self.BOARD_SIZE)
+   return y + x * self.BOARD_SIZE

List1dBoard.xy_to_move = xy_to_move

+def move_to_xy(self, move):
+   return move // self.BOARD_SIZE, move % self.BOARD_SIZE

List1dBoard.move_to_xy = move_to_xy

+def move_to_xy(self, move):
+   return move

ListBoard.move_to_xy = move_to_xy

`is_winner` の修正

List1dBoard クラスの中で x, y = move のような 展開処理 を行っている is_winner メソッドを下記のプログラムのように修正する必要があります。

2 行目：展開処理を、数値座標から x, y 座標を計算する処理に修正した

1  def is_winner(self, player, last_move):
2      x, y = last_move // self.BOARD_SIZE, last_move % self.BOARD_SIZE
元と同じなので省略
3  
4  List1dBoard.is_winner = is_winner

行番号のないプログラム

def is_winner(self, player, last_move):
    x, y = last_move // self.BOARD_SIZE, last_move % self.BOARD_SIZE
    if self.count_linemark:
        if self.rowcount[player][y] == self.BOARD_SIZE or \
        self.colcount[player][x] == self.BOARD_SIZE:
            return True
        # 左上から右下方向の判定
        if x == y and self.diacount[player][0] == self.BOARD_SIZE:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.diacount[player][1] == self.BOARD_SIZE:
            return True
    else:
        if self.is_same(player, x=0, y=y, dx=1, dy=0) or \
        self.is_same(player, x=x, y=0, dx=0, dy=1):
            return True
        # 左上から右下方向の判定
        if x == y and self.is_same(player, x=0, y=0, dx=1, dy=1):
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.is_same(player, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1):
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

List1dBoard.is_winner = is_winner

修正箇所

def is_winner(self, player, last_move):
-   x, y = last_move
+   x, y = last_move // self.BOARD_SIZE, last_move % self.BOARD_SIZE
元と同じなので省略

List1dBoard.is_winner = is_winner

展開処理の修正

上記の修正によって List1dBoard クラスの座標の 展開処理が行えなくなった ので、その処理を move_to_xy に修正 する必要があります。修正する必要がある箇所は以下の通りです。修正箇所を探す際は x, y を検索 すると良いでしょう。なお、ListBoard クラスの座標は tuple のままなので、ListBoard クラス内の x, y = move は修正する必要はありません。また、前回の記事で x, y = move のような展開処理を大量に削除したので、修正する必要がある場所はそれほど多くはありません。

marubatsu.py の Marubatsu クラスの __str__
marubatsu.py の Marubatsu_GUI クラスの update_gui
util.py の calc_same_boardtexts
ai.py の ai1s、ai4s

また、プログラム内で 座標を表す (x, y) や (1, 1) の tuple を xy_to_move に修正 する必要があります。修正する必要がある箇所は以下の通りです。

marubatsu.py の Marubatsu_GUI クラスの draw_board
util.py の calc_same_boardtexts
tree.py の Mbtree_GUI クラスの create_event_handler
ai.py の ai3、ai3s、ai4、ai4s、ai7、ai7s、ai8s、ai9s、ai10s

下記は、上記の中で ベンチマークの処理に関連 する util.py の calc_same_boardtexts の修正を行ったプログラムで、他のプログラムに関しては今回の記事の ai_new.py などのファイルに反映させることにします。

5 行目：展開処理を move_to_xy メソッドで行うように修正した
7 行目：(x, y) の座標を代入する処理を xy_to_move メソッドの返り値を代入するように修正した

1  def calc_same_boardtexts(mb, move=None):
元と同じなので省略
2          if move is None:
3              boardtexts.add(txt)
4          else:
5              x, y = mb.board.move_to_xy(move)
6              x, y = xa2 * 2 + xb2 * x + xc2 * y, ya2 * 2 + yb2 * x + yc2 * y
7              boardtexts[txt] = mb.board.xy_to_move(x, y)
8      return boardtexts

行番号のないプログラム

def calc_same_boardtexts(mb, move=None):
    data = [ [ 0,  0,  1, 1, -1,  0,  1,  0, -1, 0,  1,  0],
             [ 1, -1,  0, 1,  0, -1] * 2,
             [ 1,  0, -1, 0,  1,  0,  0,  0,  1, 1, -1,  0],
             [ 1, -1,  0, 0,  0,  1] * 2,
             [ 0,  1,  0, 1,  0, -1] * 2,
             [ 1,  0, -1, 1, -1,  0] * 2,
             [ 0,  0,  1, 0,  1,  0] * 2, ]
    if move is None:
        boardtexts = set([mb.board_to_str()])
    else:
        boardtexts = { mb.board_to_str(): move }
    for xa, xb, xc, ya, yb, yc, xa2, xb2, xc2, ya2, yb2, yc2 in data:
        txt = ""
        for x in range(mb.BOARD_SIZE):
            for y in range(mb.BOARD_SIZE):
                txt += mb.board.getmark(xa * 2 + xb * x + xc * y, ya * 2 + yb * x + yc * y)
        if move is None:
            boardtexts.add(txt)
        else:
            x, y = mb.board.move_to_xy(move)
            x, y = xa2 * 2 + xb2 * x + xc2 * y, ya2 * 2 + yb2 * x + yc2 * y
            boardtexts[txt] = mb.board.xy_to_move(x, y)
    return boardtexts

修正箇所

def calc_same_boardtexts(mb, move=None):
元と同じなので省略
        if move is None:
            boardtexts.add(txt)
        else:
-           x, y = move
+           x, y = mb.board.move_to_xy(move)
            x, y = xa2 * 2 + xb2 * x + xc2 * y, ya2 * 2 + yb2 * x + yc2 * y
-           boardtexts[txt] = (x, y)
+           boardtexts[txt] = mb.board.xy_to_move(x, y)
    return boardtexts

ベンチマークの実行

ai_abs_dls の定義では util.py から calc_same_boardtexts をローカルにインポート しているので、上記で 修正した calc_same_boardtexts を ai_abs_dls が利用するため には下記のプログラムのように ai_abs_dls を再定義 する必要があります。下記のプログラムは from util import calc_same_boardtexts のローカルなインポート処理をコメントにして 削除しているだけ なので説明は省略して折りたたみます。

ai_abs_dls の再定義

from ai import ai_by_mmscore, dprint
from time import perf_counter

@ai_by_mmscore
def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1,
               eval_func=None, eval_params={}, use_tt=False,
               tt=None, tt_for_mo=None):
    count = 0
    def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
        nonlocal count
        if timelimit_pc is not None and perf_counter() >= timelimit_pc:
            raise RuntimeError("time out")
        
        count += 1
        if mborig.status != Marubatsu.PLAYING or depth == maxdepth:
            return eval_func(mborig, calc_score=True, **eval_params)
        
        if use_tt:
            boardtxt = mborig.board_to_str()
            if boardtxt in tt:
                lower_bound, upper_bound, _ = tt[boardtxt]
                if lower_bound == upper_bound:
                    return lower_bound
                elif upper_bound <= alpha:
                    return upper_bound
                elif beta <= lower_bound:
                    return lower_bound
                else:
                    alpha = max(alpha, lower_bound)
                    beta = min(beta, upper_bound)
            else:
                lower_bound = min_score
                upper_bound = max_score
        
        alphaorig = alpha
        betaorig = beta

        legal_moves = mborig.calc_legal_moves()
        if tt_for_mo is not None:
            if not use_tt:            
                boardtxt = mborig.board_to_str()
            if boardtxt in tt_for_mo:
                _, _, bestmove = tt_for_mo[boardtxt]
                index = legal_moves.index(bestmove)
                legal_moves[0], legal_moves[index] = legal_moves[index], legal_moves[0]        
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for move in legal_moves:
                mborig.move(move)
                abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
                mborig.unmove()
                if abscore > score:
                    bestmove = move
                score = max(score, abscore)
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for move in legal_moves:
                mborig.move(move)
                abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
                mborig.unmove()
                if abscore < score:
                    bestmove = move
                score = min(score, abscore)
                if score <= alpha:
                    break
                beta = min(beta, score)   
            
#        from util import calc_same_boardtexts

        if use_tt:
            boardtxtlist = calc_same_boardtexts(mborig, bestmove)
            if score <= alphaorig:
                upper_bound = score
            elif score < betaorig:
                lower_bound = score
                upper_bound = score
            else:
                lower_bound = score
            for boardtxt, move in boardtxtlist.items():
                tt[boardtxt] = (lower_bound, upper_bound, move)
        return score
                
    min_score = float("-inf")
    max_score = float("inf")
    
    if tt is None:
        tt = {}
    score = ab_search(mb, depth=0, tt=tt, alpha=min_score, beta=max_score)
    dprint(debug, "count =", count)
    return score, count

また、benchmark では ai_abs_dls をローカルにインポート しているので、util.py からインポートした benchmark を利用すると上記の再定義を行った ai_abs_dls が利用されません。%timeit で処理時間を計測する場合は ローカルなインポートは必要がない ので、下記のプログラムで benchmark の処理を記述 して %timeit で処理時間を計測 することにします。

from ai import ai_match, ai2, ai14s

match_num = 50000
for boardclass in [ListBoard, List1dBoard]:
    for count_linemark in [False, True]:
        print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
        mbparams={"boardclass": boardclass, "count_linemark": count_linemark}
        ai_match(ai=[ai2, ai2], match_num=match_num, mbparams=mbparams)   
        ai_match(ai=[ai14s, ai2], match_num=match_num, mbparams=mbparams)

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

実行結果

boardclass: ListBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 13986.04it/s]
count     win    lose    draw
o       29297   14378    6325
x       14635   29094    6271
total   43932   43472   12596

ratio     win    lose    draw
o       58.6%   28.8%   12.7%
x       29.3%   58.2%   12.5%
total   43.9%   43.5%   12.6%

ai14s VS ai2
100%|██████████| 50000/50000 [00:45<00:00, 1108.16it/s]
count     win    lose    draw
o       49491       0     509
x       44164       0    5836
total   93655       0    6345

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.3%    0.0%   11.7%
total   93.7%    0.0%    6.3%

ai_abs_dls
17.3 ms ± 867 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

boardclass: ListBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 14665.56it/s]
count     win    lose    draw
o       29434   14299    6267
x       14384   29131    6485
total   43818   43430   12752

ratio     win    lose    draw
o       58.9%   28.6%   12.5%
x       28.8%   58.3%   13.0%
total   43.8%   43.4%   12.8%

ai14s VS ai2
100%|██████████| 50000/50000 [00:25<00:00, 1989.96it/s]
count     win    lose    draw
o       49457       0     543
x       44133       0    5867
total   93590       0    6410

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.3%    0.0%   11.7%
total   93.6%    0.0%    6.4%

ai_abs_dls
17.6 ms ± 251 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

boardclass: List1dBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 17289.04it/s]
count     win    lose    draw
o       29346   14300    6354
x       14392   29228    6380
total   43738   43528   12734

ratio     win    lose    draw
o       58.7%   28.6%   12.7%
x       28.8%   58.5%   12.8%
total   43.7%   43.5%   12.7%

ai14s VS ai2
100%|██████████| 50000/50000 [00:46<00:00, 1078.35it/s]
count     win    lose    draw
o       49486       0     514
x       44141       0    5859
total   93627       0    6373

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.3%    0.0%   11.7%
total   93.6%    0.0%    6.4%

ai_abs_dls
17.2 ms ± 258 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

boardclass: List1dBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 17326.73it/s]
count     win    lose    draw
o       29330   14288    6382
x       14224   29385    6391
total   43554   43673   12773

ratio     win    lose    draw
o       58.7%   28.6%   12.8%
x       28.4%   58.8%   12.8%
total   43.6%   43.7%   12.8%

ai14s VS ai2
100%|██████████| 50000/50000 [00:24<00:00, 2029.60it/s]
count     win    lose    draw
o       49470       0     530
x       44279       0    5721
total   93749       0    6251

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.6%    0.0%   11.4%
total   93.7%    0.0%    6.3%

ai_abs_dls
19.2 ms ± 1.77 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は上記の結果をまとめた表です。最下段が上記の実行結果 です。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	12391.16 回/秒 11848.56 回/秒 14579.71 回/秒 13986.04 回/秒	969.45 回/秒 829.88 回/秒 1113.82 回/秒 1108.16 回/秒	17.4 ms 22.7 ms 18.0 ms 17.3 ms
ListBoard	`True`	12340.74 回/秒 15077.96 回/秒 15309.97 回/秒 14665.56 回/秒	1882.32 回/秒 1951.29 回/秒 1984.76 回/秒 1989.96 回/秒	17.6 ms 20.6 ms 17.4 ms 17.6 ms
List1dBoard	`False`	11801.20 回/秒 9059.91 回/秒 11818.58 回/秒 17289.04 回/秒	956.38 回/秒 681.72 回/秒 1050.48 回/秒 1078.35 回/秒	17.6 ms 31.7 ms 20.9 ms 17.2 ms
List1dBoard	`True`	12300.84 回/秒 10490.45 回/秒 10430.42 回/秒 17326.73 回/秒	1875.35 回/秒 1528.86 回/秒 1591.74 回/秒 2029.60 回/秒	18.6 ms 30.2 ms 24.3 ms 19.2 ms

ListBoard の処理は、先程行ったベンチマークと同じです。3 段目と 4 段目で若干数値が異なる部分がありますが、誤差の範囲でしょう。

上記から、List1dBoard の処理を修正 したことで 4 段目の処理 がいずれも 上記の修正前 の 3 段目の処理速度よりも 速くなる ことが確認できます。

また、ai2 VS ai2 の対戦では List1dBoard のほうが ListBoard よりも 処理速度が大幅に速くなる ことが確認できました。このことから、2 次元の list よりも 1 次元の list のほうが ai2 VS ai2 の処理速度が速くなる ことがわかります。その理由は、2 次元の list では 2 つの添字を指定 してマスの値を参照する必要があるのに対して 1 次元の list では 1 つの添字だけ でマスの値を参照できるため、その分だけ処理速度が速くなる からです。

ai14s VS ai2 と ai_abs_dls の処理速度は ListBoard クラスと あまり変わりません が、これは ai14s と ai_abs_dls から数多く呼び出される getmark の処理で行われる x, y 座標を数値座標に変換する処理 によるものではないかと思います。

Board クラスの修正

今回の記事の修正によって、Board クラスで定義する 抽象メソッドなどを下記の表のように修正 することにします。なお、下記の表の move は ゲーム盤のクラスの座標 を表します。

修正点は move_to_xy メソッドを追加 した点だけです。

抽象メソッド	処理
`getmark_by_move(move)`	`move` のマスのマークを返す
`setmark_by_move(move, mark)`	`move` のマスに `mark` を代入する
`board_to_str()`	ゲーム盤を表す文字列を返す
`judge(last_turn, last_move, move_count)`	勝敗判定を計算して返す
`count_markpats(turn, last_turn)`	局面のマークのパターンを返す
`xy_to_move(x, y)`	(x, y) のマスのゲーム盤のクラスの座標を返す
`move_to_xy(move)`	move のマスの x, y の座標を返す
`calc_legal_moves()`	合法手の一覧を表す、ゲーム盤のクラスの座標を要素とする list を返す

下記のメソッドは Board クラスでその処理を定義 していますが、より効率的な方法で getmark や setmark の定義を行える場合 はその処理をオーバーライドして定義します。

メソッド	処理
`getmark(move)`	(x, y) のマスのマークを返す
`setmark(x, y, mark)`	(x, y) のマスに `mark` を代入する

`ai14s` の改良

ai14s のプログラムを改良できることに気が付いたので 改良を行う ことにします。ai14s では先ほど示したように、下記のプログラムで「斜め方向に〇×〇が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合」を調べていますが、この if 文の条件式 では 最後に and mb.move_count=4 が記述 されていることから、4 手目であることが条件の一つ になっています。従って、この条件式では その前に記述されている複数の getmark の条件がすべて真 であっても mb.move_count=4 でない場合は偽 となります。

    # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
    if mb.board.getmark(1, 1) == Marubatsu.CROSS and \
        (mb.board.getmark(0, 0) == mb.board.getmark(2, 2) == Marubatsu.CIRCLE or \
        mb.board.getmark(2, 0) == mb.board.getmark(0, 2) == Marubatsu.CIRCLE) and \
        (mb.board.getmark(1, 0) == Marubatsu.CROSS or \
        mb.board.getmark(0, 1) == Marubatsu.CROSS or \
        mb.board.getmark(2, 1) == Marubatsu.CROSS or \
        mb.board.getmark(1, 2) == Marubatsu.CROSS) and \
        mb.move_count == 4:
        return score_special

以前の記事で説明したように、python の and 演算子 は 先頭から順番に計算 が行われ、False が計算された時点 で 残りの式の計算を省略 するという 短絡処理 が行われます。move_count は 0 ~ 9 までの場合があり、4 の場合だけこの条件式が真になる可能性がある ので、最初に mb.move_count=4 の判定 を行ったほうが 効率的な判定 を行うことができます。

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

8 行目：条件式の最後にあった mb.move_count == 4 を最初に移動した

 1  from ai import ai_by_score
 2  
 3  @ai_by_score
 4  def ai14s(mb, debug=False, score_victory=300, score_sure_victory=200, \
 5            score_defeat=-100, score_special=100, score_201=2, \
 6            score_102=0.5, score_012=-1):
元と同じなので省略
 7      # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
 8      if mb.move_count == 4 and \
 9          mb.board.getmark(1, 1) == Marubatsu.CROSS and \
10          (mb.board.getmark(0, 0) == mb.board.getmark(2, 2) == Marubatsu.CIRCLE or \
11          mb.board.getmark(2, 0) == mb.board.getmark(0, 2) == Marubatsu.CIRCLE) and \
12          (mb.board.getmark(1, 0) == Marubatsu.CROSS or \
13          mb.board.getmark(0, 1) == Marubatsu.CROSS or \
14          mb.board.getmark(2, 1) == Marubatsu.CROSS or \
15          mb.board.getmark(1, 2) == Marubatsu.CROSS):
16          return score_special    
元と同じなので省略

行番号のないプログラム

from ai import ai_by_score

@ai_by_score
def ai14s(mb, debug=False, score_victory=300, score_sure_victory=200, \
          score_defeat=-100, score_special=100, score_201=2, \
          score_102=0.5, score_012=-1):
    # 評価値の合計を計算する変数を 0 で初期化する
    score = 0        

    # 自分が勝利している場合
    if mb.status == mb.last_turn:
        return score_victory

    markpats = mb.count_markpats()
    if debug:
        pprint(markpats)
    # 相手が勝利できる場合は評価値を加算する
    if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
        score = score_defeat * markpats[Markpat(last_turn=0, turn=2, empty=1)]
    # 次の自分の手番で自分が必ず勝利できる場合
    elif markpats[Markpat(last_turn=2, turn=0, empty=1)] >= 2:
        return score_sure_victory
    
    # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
    if mb.move_count == 4 and \
        mb.board.getmark(1, 1) == Marubatsu.CROSS and \
        (mb.board.getmark(0, 0) == mb.board.getmark(2, 2) == Marubatsu.CIRCLE or \
        mb.board.getmark(2, 0) == mb.board.getmark(0, 2) == Marubatsu.CIRCLE) and \
        (mb.board.getmark(1, 0) == Marubatsu.CROSS or \
        mb.board.getmark(0, 1) == Marubatsu.CROSS or \
        mb.board.getmark(2, 1) == Marubatsu.CROSS or \
        mb.board.getmark(1, 2) == Marubatsu.CROSS):
        return score_special    

    # 次の自分の手番で自分が勝利できる場合は評価値に score_201 を加算する
    if markpats[Markpat(last_turn=2, turn=0, empty=1)] == 1:
        score += score_201
    # 「自 1 敵 0 空 2」1 つあたり score_102 だけ、評価値を加算する
    score += markpats[Markpat(last_turn=1, turn=0, empty=2)] * score_102
    # 「自 0 敵 1 空 2」1 つあたり score_201 だけ、評価値を減算する
    score += markpats[Markpat(last_turn=0, turn=1, empty=2)] * score_012
    
    # 計算した評価値を返す
    return score

修正箇所

from ai import ai_by_score

@ai_by_score
def ai14s(mb, debug=False, score_victory=300, score_sure_victory=200, \
          score_defeat=-100, score_special=100, score_201=2, \
          score_102=0.5, score_012=-1):
元と同じなので省略
    # 斜め方向に 〇×〇 が並び、いずれかの辺の 1 つのマスのみに × が配置されている場合
-   if mb.board.getmark(1, 1) == Marubatsu.CROSS and \
+   if mb.move_count == 4 and \
-       mb.board.getmark(1, 1) == Marubatsu.CROSS and \
        (mb.board.getmark(0, 0) == mb.board.getmark(2, 2) == Marubatsu.CIRCLE or \
        mb.board.getmark(2, 0) == mb.board.getmark(0, 2) == Marubatsu.CIRCLE) and \
        (mb.board.getmark(1, 0) == Marubatsu.CROSS or \
        mb.board.getmark(0, 1) == Marubatsu.CROSS or \
        mb.board.getmark(2, 1) == Marubatsu.CROSS or \
-       mb.board.getmark(1, 2) == Marubatsu.CROSS) and \
-       mb.move_count == 4:
+       mb.board.getmark(1, 2) == Marubatsu.CROSS):
        return score_special    
元と同じなので省略

上記の修正後に下記のプログラムで ベンチマークを実行 します。

for boardclass in [ListBoard, List1dBoard]:
    for count_linemark in [False, True]:
        print(f"boardclass: {boardclass.__name__}, count_linemark {count_linemark}")
        mbparams={"boardclass": boardclass, "count_linemark": count_linemark}
        ai_match(ai=[ai2, ai2], match_num=match_num, mbparams=mbparams)   
        ai_match(ai=[ai14s, ai2], match_num=match_num, mbparams=mbparams)

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

実行結果

boardclass: ListBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 14916.51it/s]
count     win    lose    draw
o       29252   14312    6436
x       14337   29339    6324
total   43589   43651   12760

ratio     win    lose    draw
o       58.5%   28.6%   12.9%
x       28.7%   58.7%   12.6%
total   43.6%   43.7%   12.8%

ai14s VS ai2
100%|██████████| 50000/50000 [00:44<00:00, 1116.53it/s]
count     win    lose    draw
o       49461       0     539
x       44217       0    5783
total   93678       0    6322

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.4%    0.0%   11.6%
total   93.7%    0.0%    6.3%

ai_abs_dls
17.4 ms ± 298 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

boardclass: ListBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:03<00:00, 15463.39it/s]
count     win    lose    draw
o       29415   14280    6305
x       14292   29293    6415
total   43707   43573   12720

ratio     win    lose    draw
o       58.8%   28.6%   12.6%
x       28.6%   58.6%   12.8%
total   43.7%   43.6%   12.7%

ai14s VS ai2
100%|██████████| 50000/50000 [00:24<00:00, 2030.27it/s]
count     win    lose    draw
o       49510       0     490
x       44192       0    5808
total   93702       0    6298

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.4%    0.0%   11.6%
total   93.7%    0.0%    6.3%

ai_abs_dls
17.4 ms ± 728 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)

boardclass: List1dBoard, count_linemark False
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 17404.27it/s]
count     win    lose    draw
o       29234   14345    6421
x       14346   29413    6241
total   43580   43758   12662

ratio     win    lose    draw
o       58.5%   28.7%   12.8%
x       28.7%   58.8%   12.5%
total   43.6%   43.8%   12.7%

ai14s VS ai2
100%|██████████| 50000/50000 [00:43<00:00, 1145.23it/s]
count     win    lose    draw
o       49473       0     527
x       44077       0    5923
total   93550       0    6450

ratio     win    lose    draw
o       98.9%    0.0%    1.1%
x       88.2%    0.0%   11.8%
total   93.5%    0.0%    6.5%

ai_abs_dls
16.7 ms ± 277 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

boardclass: List1dBoard, count_linemark True
ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 17176.56it/s]
count     win    lose    draw
o       29201   14419    6380
x       14251   29435    6314
total   43452   43854   12694

ratio     win    lose    draw
o       58.4%   28.8%   12.8%
x       28.5%   58.9%   12.6%
total   43.5%   43.9%   12.7%

ai14s VS ai2
100%|██████████| 50000/50000 [00:23<00:00, 2152.38it/s]
count     win    lose    draw
o       49476       0     524
x       44249       0    5751
total   93725       0    6275

ratio     win    lose    draw
o       99.0%    0.0%    1.0%
x       88.5%    0.0%   11.5%
total   93.7%    0.0%    6.3%

ai_abs_dls
17.3 ms ± 349 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

下記は上記の結果をまとめた表です。上段が修正前、下段が上記の実行結果 です。

boardclass	count_linemark	`ai2` VS `ai2`	`ai14s` VS `ai2`	`ai_abs_dls`
ListBoard	`False`	13986.04 回/秒 14916.51 回/秒	1108.16 回/秒 1116.53 回/秒	17.3 ms 17.4 ms
ListBoard	`True`	14665.56 回/秒 15463.39 回/秒	1989.96 回/秒 2030.27 回/秒	17.6 ms 17.4 ms
List1dBoard	`False`	17289.04 回/秒 17404.27 回/秒	1078.35 回/秒 1145.23 回/秒	17.2 ms 16.7 ms
List1dBoard	`True`	17326.73 回/秒 17176.56 回/秒	2029.60 回/秒 2152.38 回/秒	19.2 ms 17.3 ms

上記の表から ai14s が関連 する ai14s VS ai2 と ai_abs_dls の 処理速度 が一部を除いて 少し向上 したことが確認できます。

`ai6s`、`ai7s` の修正

ai6s と ai7s の中で 廃止した Marubatsu クラスの count_marks を呼び出している ため、実行すると下記のプログラムのような エラーが発生する ことが判明したので修正します。

from ai import ai6s

mb = Marubatsu()
ai6s(mb)

実行結果

略
File c:\Users\ys\ai\marubatsu\196\ai.py:787, in ai6s(mb, debug)
    784 # 相手の手番で相手が勝利できる場合は評価値として -1 を返す
    785 # 横方向と縦方向の判定
    786 for i in range(mb.BOARD_SIZE):
--> 787     count = mb.count_marks(coord=[0, i], dx=1, dy=0)
    788     if count[mb.turn] == 2 and count[Marubatsu.EMPTY] == 1:
    789         return -1

AttributeError: 'Marubatsu' object has no attribute 'count_marks'

ai6s は 相手が勝利できる場合に評価値として -1 を返す 処理を行うので、下記のプログラムのように Marubatsu クラスの廃止していない count_markpats を利用して記述できます。

@ai_by_score
def ai6s(mb, debug):
    # 自分が勝利している場合は、評価値として 1 を返す
    if mb.status == mb.last_turn:
        return 1

    markpats = mb.count_markpats()
    # 相手が勝利できる場合は評価値として -1 を返す
    if markpats[Markpat(last_turn=0, turn=2, empty=1)] > 0:
        return -1
    # それ以外の場合は評価値として 0 を返す
    else:
        return 0

上記の修正後に下記のプログラムを実行すると、実行結果のように エラーが発生しなくなった ことが確認できます。

ai6s(mb)

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

ai6s(mb)

プログラムは省略しますが、ai7s も同様の方法で修正 することができます。修正は ai_new.py に反映させます。

今回の記事のまとめ

今回の記事では前回の記事の修正による ListBoard と List1dBoard の処理の違いを検証 することで 処理速度の低下の原因を検証 し、処理速度の改善 を行いました。また、改善を行うことで 2 次元よりも 1 次元の list でゲーム盤を表現したほうが ai2 VS ai2 の処理速度が大幅に向上する ことが確認できました。

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

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

次回の記事

「ゲーム盤のデータ構造に適したデータ構造での座標」という意味です。詳細は前回の記事を参照して下さい。 ↩
手数が 5 以上の局面は 5、6、7、8、9 の 5 種類です ↩
類推と表記したのは、ai_abs_dls が既に置換表に登録済のノードの評価値を更新する処理を行う場合があるからです。そのため、置換表にノードの評価値を登録する処理を行う回数は、置換表に登録されたノードの数よりも多い可能性があります ↩