Pythonで〇×ゲームのAIを一から作成する その190 他の Marubatsu クラスの処理速度の改善の試み

目次と前回の記事

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

他の Marubatsu クラスの処理速度の高速化の手法

今回の記事では前回の記事に引き続き Marubatsu クラスの処理速度の高速化の手法 についていくつか紹介します。その手法について少し考えてみて下さい。

合法手の一覧の計算の改善

Marubatsu クラスには 合法手の一覧を計算 する、下記のプログラムで定義された calc_legal_moves というメソッドが定義されています。

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[x][y] == Marubatsu.EMPTY]
    return legal_moves

ai2s や ai14s などの 静的評価関数 によって最善手を計算する関数では 合法手の中から最善手を計算 するために calc_legal_moves を 1 度 呼び出します。ai_abs_dls などの ゲーム木の探索 によって最善手を計算する関数では、ノードの評価値を計算する際に 子ノードの一覧を計算する必要 があり、計算したノードの数だけ何度も calc_legal_moves を呼び出す ので、この処理を高速化 することで 全体の処理速度を改善できる可能性 があります。

そこで calc_legal_moves の処理速度の改善 を試み、その 処理速度を比較 してみることにします。処理速度の改善方法について少し考えてみて下さい。

修正前の処理時間の計測

修正による 処理速度を比較 するために、下記のベンチマークを設定することにします。

• 前回の記事と同様に ai2s VS ai2s の 10000 回の対戦を行う
• ゲーム開始時の局面 に対して ai_abs_dls を用いて αβ 法 で評価値の計算を行う。その際に 置換表を利用する場合 と 利用しない場合 の両方で計測を行う

ai_match で ai_abs_dls のどうしの対戦を行わない理由は、後述のノートの実行結果からわかるように ai_abs_dls の処理時間 が ai2s と比較して 約千倍も長い ので、10000 回の対戦 を行うと数十分以上間以上もの 長い時間がかかる ためです。

下記は修正前のそれぞれのベンチマークを実行するプログラムです。

from ai import ai_match, ai2s

ai_match(ai=[ai2s, ai2s], match_num=5000)

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:01<00:00, 2870.59it/s]
count     win    lose    draw
o        2949    1427     624
x        1425    2917     658
total    4374    4344    1282

ratio     win    lose    draw
o       59.0%   28.5%   12.5%
x       28.5%   58.3%   13.2%
total   43.7%   43.4%   12.8%

下記は ai_abs_dls のベンチマークの設定 で以前の記事のベンチマークと同じです。

from ai import ai14s, ai_abs_dls
from marubatsu import Marubatsu

mb = Marubatsu()
eval_params = {"minimax": True}

下記は 置換表を利用する 場合の ai_abs_dls のベンチマークです。

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8)

実行結果

14.9 ms ± 304 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

下記は 置換表を利用しない 場合の ai_abs_dls のベンチマークです。

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8)

実行結果

179 ms ± 2.25 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

下記は上記のベンチマークの結果をまとめた表です。

	結果
ai2s VS ai2s	2870.59 回/秒
置換表ありの αβ 法	14.9 ms
置換表なしの αβ 法	179.0 ms

ゲーム開始時の局面に対する ai2s の処理速度は下記のプログラムのように約 20 μs = 0.02 ms で、上記の 15.2 ms の約 1000 倍であることがわかります

%%timeit

ai2s(mb)

実行結果

19.9 μs ± 933 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

合法手の一覧の計算を行う別のアルゴリズム

下記の 現状の calc_legal_moves は、呼び出されるたびに すべてのマスを調べて合法手の一覧を表す list を作成する という処理を行っていますが、毎回すべてのマスを調べるのは無駄ではないか と思った人はいないでしょうか？

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[x][y] == Marubatsu.EMPTY]
    return legal_moves

〇× ゲーム では、合法手の一覧 は 着手を行うたび に下記のように 変化します。

• ゲーム開始時の局面 では すべてのマスが合法手 である
• 着手を行うたび に合法手の一覧から 着手を行った合法手がなくなる

そのため、下記のアルゴリズムで合法手の一覧を計算することができます。

• 合法手の一覧 を legal_moves という属性に代入 することにする
• ゲームの開始時 に呼び出される restart メソッド内で、legal_moves 属性に すべてのマスの座標を要素とする list を代入 して初期化する
• move メソッドで 着手を行う際 に legal_moves 属性から 着手したマスの要素を削除 する
• unmove メソッドで 着手取り消す際 に legal_moves 属性に 取り消された着手を追加 する
• calc_legal_moves メソッドでは legal_moves 属性を 返り値として返す

上記の中の unmove メソッドでの処理は忘れやすい ので注意して下さい。

上記のアルゴリズムとこれまでの アルゴリズムの違い は以下の通りです。

メソッド	従来のアルゴリズム	合法手の一覧を記録するアルゴリズム
restart		legal_moves の初期化
move		legal_moves 属性の要素の削除
unmove		legal_moves 属性への要素の追加
calc_legal_moves	合法手の一覧を計算する	legal_moves 属性を返す

合法手の一覧を記録 するアルゴリズムでは、restart、move、unmove メソッドで 処理が追加 されていますが、calc_legal_moves で行われる処理は 計算済の legal_moves 属性を返すだけ なので、従来のアルゴリズム で合法手の一覧を計算する処理よりも 明らかに処理時間が短く なります。その処理時間の短縮 が 追加された処理時間よりも短ければ、合法手の一覧を記録するアルゴリズムのほうが 全体の処理時間が短く なります。

本当に処理時間が短くなるかを 計算だけで正確に見積もることは困難 なので、実際に 上記のアルゴリズムを実装して処理時間を比較 してみることにします。

各メソッドの修正

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

• 4 行目：legal_moves 属性に list 内包表記を利用してすべてのマスの座標を要素とする list を代入する

1  def restart(self):
元と同じなので省略
2      self.legal_moves = [(x, y) for x in range(self.BOARD_SIZE) for y in range(self.BOARD_SIZE)]
3      
4  Marubatsu.restart = restart

行番号のないプログラム

def restart(self):
    self.initialize_board()
    self.turn = Marubatsu.CIRCLE     
    self.move_count = 0
    self.status = Marubatsu.PLAYING
    self.last_move = -1, -1          
    self.last_turn = None
    self.records = [self.last_move]
    if self.count_linemark:
        self.rowcount = {
            Marubatsu.CIRCLE: [0] * self.BOARD_SIZE,
            Marubatsu.CROSS: [0] * self.BOARD_SIZE,
        }
        self.colcount = {
            Marubatsu.CIRCLE: [0] * self.BOARD_SIZE,
            Marubatsu.CROSS: [0] * self.BOARD_SIZE,
        }
        self.diacount = {
            Marubatsu.CIRCLE: [0] * 2,
            Marubatsu.CROSS: [0] * 2,
        }
    self.legal_moves = [(x, y) for x in range(self.BOARD_SIZE) for y in range(self.BOARD_SIZE)]
    
Marubatsu.restart = restart

修正箇所

def restart(self):
元と同じなので省略
+   self.legal_moves = [(x, y) for x in range(self.BOARD_SIZE) for y in range(self.BOARD_SIZE)]
    
Marubatsu.restart = restart

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

• 3 行目：list や set などから 指定した要素を削除する remove メソッド を利用して legal_moves 属性から着手した座標の要素を削除する

1  def move(self, x, y):
2      if self.place_mark(x, y, self.turn):
元と同じなので省略
3          self.legal_moves.remove((x, y))
4          
5  Marubatsu.move = move

行番号のないプログラム

def move(self, x, y):
    if self.place_mark(x, y, self.turn):
        self.last_turn = self.turn
        self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
        self.move_count += 1
        self.last_move = x, y
        if self.count_linemark:
            self.colcount[self.last_turn][x] += 1
            self.rowcount[self.last_turn][y] += 1
            if x == y:
                self.diacount[self.last_turn][0] += 1        
            if x + y == self.BOARD_SIZE - 1:
                self.diacount[self.last_turn][1] += 1        
        self.status = self.judge()
        if len(self.records) <= self.move_count:            
            self.records.append(self.last_move)
        else:
            self.records[self.move_count] = self.last_move
            self.records = self.records[0:self.move_count + 1]
        self.legal_moves.remove((x, y))
        
Marubatsu.move = move

修正箇所

def move(self, x, y):
    if self.place_mark(x, y, self.turn):
元と同じなので省略
+       self.legal_moves.remove((x, y))
        
Marubatsu.move = move

list や set などのミュータブルなシーケンス型のデータから要素を削除するメソッドには以前の記事で説明した pop メソッドがありますが、pop メソッドが インデックスを指定 して要素を削除して 削除した要素の値を返す に対し、remove メソッドは 要素の値を指定 して要素を削除して 値を返さない 点が異なります。

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

1  def unmove(self):
2      if self.move_count > 0:
元と同じなので省略  
3          self.legal_moves.append((x, y))
4          
5  Marubatsu.unmove = unmove

• 3 行目：list の append メソッドを利用して legal_moves 属性に取り消した着手の座標の要素を追加する

行番号のないプログラム

def unmove(self):
    if self.move_count > 0:
        x, y = self.last_move
        if self.count_linemark:
            self.colcount[self.last_turn][x] -= 1
            self.rowcount[self.last_turn][y] -= 1
            if x == y:
                self.diacount[self.last_turn][0] -= 1        
            if x + y == self.BOARD_SIZE - 1:
                self.diacount[self.last_turn][1] -= 1           
        if self.move_count == 0:
            self.last_move = (-1, -1)
        self.move_count -= 1
        self.turn, self.last_turn = self.last_turn, self.turn
        self.status = Marubatsu.PLAYING
        x, y = self.records.pop()
        self.remove_mark(x, y)
        self.last_move = self.records[-1]       
        self.legal_moves.append((x, y))
        
Marubatsu.unmove = unmove

修正箇所

def unmove(self):
    if self.move_count > 0:
元と同じなので省略  
+       self.legal_moves.append((x, y))
        
Marubatsu.unmove = unmove

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

• 2 行目：legal_moves を返すように修正する

def calc_legal_moves(self):
    return self.legal_moves

Marubatsu.calc_legal_moves = calc_legal_moves

修正箇所

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[x][y] == Marubatsu.EMPTY]
-   return legal_moves
+   return self.legal_moves

Marubatsu.calc_legal_moves = calc_legal_moves

ベンチマークの実行と実行結果の検証

上記の修正後に下記のプログラムで 最初のベンチマークを実行 すると、実行結果から 1 秒間の対戦回数の平均が 2730.27 回となっており、先程の 2870.59 回から若干少なくなっていることが確認できますが、下記の実行結果にはおかしな点があります。言われないと 気づきづらいのではないか と思いますが、どこがおかしいかについて少し考えてみて下さい。

ai_match(ai=[ai2s, ai2s], match_num=5000)

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:01<00:00, 2730.27it/s]
count     win    lose    draw
o        3642     963     395
x         990    3598     412
total    4632    4561     807

ratio     win    lose    draw
o       72.8%   19.3%    7.9%
x       19.8%   72.0%    8.2%
total   46.3%   45.6%    8.1%

下記は、修正前 のベンチマークの実行結果の再掲です。上記の実行結果と見比 べると、対戦結果の 〇 が先手の場合の勝率が 72.8 % であり、下記の 59.0 % から大きく変化している ことがわかります。ai2s はランダムな着手を行う AI なので若干の変化はあってもおかしくはありませんが、勝率が約 15 % も変化するのは明らかに変 です。

ai2s VS ai2s
100%|██████████| 5000/5000 [00:01<00:00, 2870.59it/s]
count     win    lose    draw
o        2949    1427     624
x        1425    2917     658
total    4374    4344    1282

ratio     win    lose    draw
o       59.0%   28.5%   12.5%
x       28.5%   58.3%   13.2%
total   43.7%   43.4%   12.8%

従って、先程修正したプログラムにはバグがある ことがわかります。

バグの原因の検証

ai2s は ai_by_score によってデコレート される関数で、その中の 下記のプログラムで行われる処理がバグの原因 となっています。なお、バグと関係のない処理は省略しました。これまでの記事で説明してきた内容からこのバグの原因を理解することは非常に困難なので初心者の方には難しいと思いますが、どこがおかしいかについて少し考えてみて下さい。

1  legal_moves = mb_orig.calc_legal_moves()
略
2  for move in legal_moves:
3      x, y = move
4      mb_orig.move(x, y)
5      score = eval_func(mb_orig, debug, *args, **kwargs)
6      mb_orig.unmove()
略

上記のプログラムで バグの原因 となるのは、4 行目と 6 行目で呼び出されている move と unmove メソッド内 で行われる処理 です。先ほどの修正によって、1 行目で legal_moves には mb_orig.legal_moves が代入 され、2 行目で その要素に対する繰り返し処理 を行います。また、先ほどの修正で move メソッドでは同じ mb_orig.legal_moves に代入された list の要素の削除 を、unmove メソッドでは 要素の追加 を行っています。

そのことを明確にする ために、legal_moves をその中に代入された mborig.legal_moves に置き換え、move と unmove メソッドを 呼び出す処理 をその中で行われる mb_orig.legal_moves に対する処理で置き換える と下記のプログラムのようになります。

for move in mb_orig.legal_moves:
    x, y = move
    mb_orig.legal_moves.remove((x, y))
    score = eval_func(mb_orig, debug, *args, **kwargs)
    mb_orig.legal_moves.append((x, y))

さらに、上記のプログラムから mb_orig.legal_moves に対する処理だけを抜き出してまとめる と下記のプログラムのようになります。

for move in mb_orig.legal_moves:
    mb_orig.legal_moves.remove(move)
    mb_orig.legal_moves.append(move)

このプログラムは、mb_orig.legal_moves に代入された list の要素に対する繰り返しの処理の中 で、その list の要素の削除と追加 の処理を行うという処理です。このような処理を行うと、for 文 で繰り返し処理を行う 対象となるlist の内容 が 繰り返し処理の最中に変化してしまう ため、繰り返し処理を開始した時点 で mb_orig_legal_moves に代入されていた list の要素とは異なる順番 で move に値が代入されてしまう ことになります。

list に対する繰り返しの最中に list の削除と追加を行う処理の検証

言葉だけでの説明ではわかりづらいと思いますので、上記のプログラムが行う処理 を 同様のもう少しわかりやすいプログラムで示す ことにします。

下記は、[1, 2, 3, 4, 5] という list から要素を順番に取り出して print で表示するプログラムです。実行結果のように 先頭の要素から順番に表示 が行われます。

a = [1, 2, 3, 4, 5]
for data in a:
    print(data)

実行結果

1
2
3
4
5

下記のプログラムは上記のプログラムの 繰り返し処理の中 で、a の要素から data を削除 し、すぐに data を追加 する処理を行うプログラムです。この処理は 先ほどの mb_orig.legal_moves に対して行っていた処理と同様 の処理です。実行結果のように、a に最初に代入されていた list の要素の順番とは 全く異なる順番で表示 が行われます。

a = [1, 2, 3, 4, 5]
for data in a:
    print(data)
    a.remove(data)
    a.append(data)

実行結果

1
3
5
3
3

上記のプログラムが行う 処理を視覚化 するために、下記のプログラムのように remove と append の処理の結果を print で表示 してみることにします。

a = [1, 2, 3, 4, 5]
for data in a:
    print(f"data = {data}, a = {a}")
    a.remove(data)
    print(f"  remove: a = {a}")
    a.append(data)
    print(f"  append: a = {a}")

実行結果

data = 1, a = [1, 2, 3, 4, 5]
  remove: a = [2, 3, 4, 5]
  append: a = [2, 3, 4, 5, 1]
data = 3, a = [2, 3, 4, 5, 1]
  remove: a = [2, 4, 5, 1]
  append: a = [2, 4, 5, 1, 3]
data = 5, a = [2, 4, 5, 1, 3]
  remove: a = [2, 4, 1, 3]
  append: a = [2, 4, 1, 3, 5]
data = 3, a = [2, 4, 1, 3, 5]
  remove: a = [2, 4, 1, 5]
  append: a = [2, 4, 1, 5, 3]
data = 3, a = [2, 4, 1, 5, 3]
  remove: a = [2, 4, 1, 5]
  append: a = [2, 4, 1, 5, 3]

append メソッドは list の 最後の要素の後に要素を追加 するメソッドです。そのため、remove メソッドで data の要素を削除した後 で 同じ要素を append メソッドで追加 すると、実行結果のように data の要素が削除されて 以降の要素が 1 つずつ前にずれ、data は list の最後の要素に追加 されることになります。その結果 a の要素の順番が変化 します。

また、list に対する for 文 による繰り返し処理では、繰り返しが開始された時点での list の内容に対して処理が行われると勘違いしている人がいるかもしれませんが、実際には 繰り返しの処理が行われるたび に その時点での list の内容に対して 処理が行われます。

従って、上記のプログラムでは下記のような処理が行われます。

1 回目の繰り返し処理

• 1 回目の繰り返し処理が行われる前の a の値は [1, 2, 3, 4, 5] である
• 0 番の要素である 1 が取り出されて data に代入される
• 1 の削除と追加によって a の値が [2, 3, 4, 5, 1] に変化する

2 回目の繰り返し処理

• 2 回目の繰り返し処理が行われる前の a の値は [2, 3, 4, 5, 1] である
• 1 番の要素である 3 が取り出されて data に代入される
• 3 の削除と追加によって a の値が [2, 4, 5, 1, 3] に変化する

3 回目の繰り返し処理

• 3 回目の繰り返し処理が行われる前の a の値は [2, 4, 5, 1, 3] である
• 2 番の要素である 5 が取り出されて data に代入される
• 5 の削除と追加によって a の値が [2, 4, 1, 3, 5] に変化する

4 回目の繰り返し処理

• 4 回目の繰り返し処理が行われる前の a の値は [2, 4, 1, 3, 5] である
• 3 番の要素である 3 が取り出されて data に代入される
• 3 の削除と追加によって a の値が [2, 4, 1, 5, 3] に変化する

5 回目の繰り返し処理

• 5 回目の繰り返し処理が行われる前の a の値は [2, 4, 1, 5, 3] である
• 4 番の要素である 3 が取り出されて data に代入される
• 3 の削除と追加によって a の値が [2, 4, 1, 5, 3] になる

これと 同様の処理 が先程の mb_orig.legal_moves に対して行われる ことを示します。下記は legal_moves の要素を 先頭から順番に取り出して表示 するプログラムです。ai_by_score では この順番で処理が行われることが想定 されています。

mb_orig = Marubatsu()
for move in mb_orig.legal_moves:
    print(move)

実行結果

(0, 0)
(0, 1)
(0, 2)
(1, 0)
(1, 1)
(1, 2)
(2, 0)
(2, 1)
(2, 2)

一方、実際には下記のプログラムのような処理 が行われ、実行結果 から 想定とは全く異なる合法手が順番に取り出される ことが確認できます。また、順番が異なるだけでなく、同じ合法手が複数回取り出される ため、一部の合法手が取り出されなくなる ことも確認できます。これが ai2s VS ai2s の対戦成績が変化してしまった理由 です。

興味がある方は print で remove と append の直後の mb_orig.legal_moves の内容を表示して下記のような実行結果になる理由を確認してみて下さい。

mb_orig = Marubatsu()
for move in mb_orig.legal_moves:
    print(move)
    mb_orig.legal_moves.remove(move)
    mb_orig.legal_moves.append(move)

実行結果

(0, 0)
(0, 2)
(1, 1)
(2, 0)
(2, 2)
(0, 2)
(2, 0)
(0, 2)
(0, 2)

繰り返し処理の中 で 繰り返しの対象となる list などの要素を削除、追加 するという処理は、上記のような バグの原因 となりますが、一見すると正しい処理を行っているように見えるため 気づきづらい ので 注意が必要 です。筆者も最初はこのバグに気づかずに記事を書き進めてしまい、後で記事を読み直した際に気づきました。

バグの原因がわかりましたので、その修正方法について少し考えてみて下さい。

dict の場合は、途中でキーとキーの値を削除して追加する処理を行っても取り出される順番は変わらないようです。下記のプログラムはそのことを検証するプログラムです。なお、dict には remove メソッドは存在せず、pop メソッドの実引数にキーを記述することでキーとその値を削除することができます。

実行結果のように print でのキーとキーの値の表示の順番は変化しますが、最初の dict と同じ a、b、c の順でキーとキーの値が取り出されています。

a = {"a":1, "b":2, "c": 3}
for key, value in a.items():
    print(key, value, a)
    a.pop(key)
    a[key] = value

実行結果

a 1 {'a': 1, 'b': 2, 'c': 3}
b 2 {'b': 2, 'c': 3, 'a': 1}
c 3 {'c': 3, 'a': 1, 'b': 2}

また、理由はよくわかりませんが、上記の実行後に a を print で表示するとキーの表示の順番が元の順番に戻るようです。

print(a)

実行結果

{'a': 1, 'b': 2, 'c': 3}

このように、データ型の種類によって繰り返しの途中で要素の削除や追加を行った際の挙動は異なる ようです。どのような処理が行われるかについては、その データ型のドキュメントで確認 するか、実際にプログラムを実行して確認 する必要があります。ただし、繰り返しの途中で要素の削除や追加の処理は通常は行うべきではないので、そのような処理を行う必要が生じなければ気にする必要はない と思います。

なお、dict に対する繰り返し処理の中でキーとキーの値の削除だけを行うと下記のプログラムのようにエラーが発生します。また、実行結果は示しませんが list の場合はこのようなエラーは発生しないようです。

a = {"a":1, "b":2, "c": 3}
for key, value in a.items():
    print(key, value, a)
    a.pop(key)

実行結果

---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
Cell In[19], line 2
      1 a = {"a":1, "b":2, "c": 3}
----> 2 for key, value in a.items():
      3     print(key, value, a)
      4     a.pop(key)

RuntimeError: dictionary changed size during iteration

エラーメッセージから、繰り返し（iteration）の最中（duration）に dict のサイズが変化するとエラーが発生するようです。そのことは下記の本家のドキュメントのリンク先で下記のように説明されていました。

「辞書の項目の追加や削除中にビューをイテレートすると、 RuntimeError を送出したり、すべての項目に渡ってイテレートできなかったりします」

バグの修正方法

このバグは 繰り返し処理の最中 に mb_orig.legal_moves の内容が変化 することが原因なので、mb_orig.legal_moves をコピーした list に対して 繰り返し処理を行う ことで修正することができます。list などのミュータブルなシーケンス型のデータには 浅いコピー を行うための copy メソッド があるので、下記のプログラムの 2 行目のように calc_legal_moves メソッドが legal_moves 属性のコピーを返す ように修正します。

なお、legal_moves の要素 には、その内容を後から変更することができない疑似的な複製¹が行われる イミュータブルなデータ型である tuple が代入 されています。そのような場合は 浅いコピー でコピーを行っても 以前の記事で説明したような 問題は発生しません。

def calc_legal_moves(self):
    return self.legal_moves.copy()

Marubatsu.calc_legal_moves = calc_legal_moves

修正箇所

def calc_legal_moves(self):
-   return self.legal_moves
+   return self.legal_moves.copy()

Marubatsu.calc_legal_moves = calc_legal_moves

下記のプログラムは先程の間違った順番で要素が取り出される繰り返し処理を行うプログラムに対して、legal_moves に mb_orig.legal_moves のコピーを代入 して繰り返しを行うように修正したプログラムです。その結果 legal_moves に対する繰り返し処理 の中で mb_orig.legal_moves の要素の削除や追加 を行っても legal_moves の内容は変化しなくなります。実際に実行結果から繰り返し処理で 想定通りの順番で合法手が取り出されるようになった ことが確認できます。

mb_orig = Marubatsu()
legal_moves = mb_orig.calc_legal_moves()
for move in legal_moves:
    print(move)
    mb_orig.legal_moves.remove(move)
    mb_orig.legal_moves.append(move)

修正箇所

mb_orig = Marubatsu()
+legal_moves = mb_orig.calc_legal_moves()
-for move in mb_orig.legal_moves:
+for move in legal_moves:
    print(move)
    mb_orig.legal_moves.remove(move)
    mb_orig.legal_moves.append(move)

実行結果

(0, 0)
(0, 1)
(0, 2)
(1, 0)
(1, 1)
(1, 2)
(2, 0)
(2, 1)
(2, 2)

list などのミュータブルなシーケンス型の copy メソッドの詳細については下記のリンク先を参照して下さい。

ベンチマークの実行と検証

バグが修正されたので改めて下記のベンチマークを実行すると、対戦成績が修正前とほぼ同じ 結果になっていることからも バグが修正 されたことが確認できます。

ai_match(ai=[ai2s, ai2s], match_num=5000)

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:01<00:00, 2696.27it/s]
count     win    lose    draw
o        2913    1455     632
x        1464    2941     595
total    4377    4396    1227

ratio     win    lose    draw
o       58.3%   29.1%   12.6%
x       29.3%   58.8%   11.9%
total   43.8%   44.0%   12.3%

下記は残りのベンチマークとその実行結果です。

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8)

実行結果

18.7 ms ± 360 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8)

実行結果

148 ms ± 2.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は修正前と修正後のベンチマークをまとめた表です。ai2s VS ai2s は 1 秒間の対戦回数の平均、ai_abs_dls は平均の処理時間を表します。

	修正前	修正後
ai2s VS ai2s	2870.59 回/秒	2696.27 回/秒
置換表ありの αβ 法	14.9 ms	18.7 ms
置換表なしの αβ 法	179.0 ms	148.0 ms

上記の表から、ai2s VS ai2s の処理回数は 約 10 % 減り、置換表ありの αβ 法 は処理時間が 約 25 % 増えた、置換表なしの αβ 法は処理時間が 約 20 % 減った ことが確認できます。このようなバラバラの結果になった原因について少し考えてみて下さい。

ベンチマークの結果の検証

ai2s VS ai2s のベンチマークの結果、処理回数は 約 10 % 減っています が、対戦回数が 10000 回と少ない のでこれは 誤差の範囲 であり、ほとんど変わらない と考えることができます。その理由は ai2s は 1 回の処理で calc_legal_moves を 1 回、move と unmove を子ノードの数の回数 だけしか呼び出さないからです。そのため、calc_legal_moves に関連する処理時間の合計が多少変化 しても 全体の処理時間にはほとんど影響は与えません。

αβ 法 ではノード $N$ の評価値を下記の手順で計算します。

1. $N$ がリーフノードの場合は静的評価関数で $N$ の評価値を計算する
2. 置換表を利用する場合で、置換表に評価値が登録されている場合は登録された評価値を $N$ の評価値とする
3. そうでなければ下記の手順で $N$ の評価値を計算する
   1. calc_legal_moves を呼び出して合法手の一覧を計算する
   2. それぞれの合法手に対して下記の計算を行う
      1. move メソッドを呼び出して着手を行う
      2. 着手を行った局面に対する評価値を再帰呼び出しで手順 1 から計算する
      3. unmove メソッドを呼び出して着手を取り消す
      4. 計算した子ノード評価値の値によって $N$ のノードの評価値を更新したり、残りの子ノードの枝狩りを行う
   3. 置換表を利用する場合は

上記から ルートノード以外のノード は 手順 3-2-2 から手順 1 が呼び出されて計算される のでその前後で必ず move メソッドと unmove メソッドが 呼び出される ことがわかります。

また、calc_legal_moves メソッドは、リーフノード と 置換用に評価値が登録 されている場合を 除いた場合 に手順 3 で 呼び出される ことがわかります。

従って、αβ 法 で計算した ノードの数を $\boldsymbol{n}$、計算した リーフノードの数を $\boldsymbol{l}$、置換表に登録されていたノードの数 を $\boldsymbol{t}$ とすると、move、unmove、calc_legal_moves が呼び出される回数は以下の表のようになります。

メソッド	回数
move	$n - 1$
unmove	$n - 1$
calc_legal_moves	$n - l - t$

下記は、2 つのアルゴリズムで行われる処理の違い の表の修正版です。calc_legal_moves の処理を 「legal_moves 属性を返す」から、「legal_moves の コピーを返す」に 修正 しました。この中で restart メソッドは常にゲームの開始時に 1 回だけ実行 されます。

メソッド	従来のアルゴリズム	合法手の一覧を記録するアルゴリズム
restart		legal_moves の初期化
move		legal_moves 属性の要素の削除
unmove		legal_moves 属性への要素の追加
calc_legal_moves	合法手の一覧を計算する	legal_moves 属性のコピーを返す

2 つの表をあわせると、合法手の一覧を記録するアルゴリズムが 余計に行う処理 は以下のようになるため、下記の処理時間の分だけ 余分に処理時間がかかる ことになります。このうちの legal_moves の初期化 の処理は 1 回だけ しか行われないので 無視する ことにします。

• legal_moves の初期化を 1 回
• legal_moves 属性の要素の削除と追加をそれぞれ $n - 1$ 回

一方、合法手の一覧を記録するアルゴリズムによって 短縮される処理時間 は以下の式で計算できます。なお、先程のバグの修正によって legal_moves のコピーを作成する処理が必要となった ので 最初に想定していたより も処理時間の 短縮の量は減りそう です。

• (legal_moves のコピーを返す処理時間 - 合法手の一覧を計算する処理時間) × ($n - l - t$)

上記の $\boldsymbol{t}$ は 置換表を利用しない場合は 0 になります。そのため、余分にかかる時間 は置換表の利用の有無に関わらず 同じ式で計算 されますが、短縮される時間 は 置換表を利用する場合のほうが 利用しない場合と比較して $t > 0$ である分だけ 小さくなります。別の言葉で説明すると、置換表を利用する場合 は、置換表に 登録されていたノードを計算する際 に処理時間の 短縮の効果が得られる legal_moves が呼び出されない ので、その分だけ置換表を利用しない場合よりも 処理時間の短縮の効果が少なくなる ということです。

その結果、置換表を利用しない 場合は「短縮される処理時間 > 余分にかかる処理時間」となるため 全体の処理時間が短く なりますが、置換表を利用する 場合は「短縮される処理時間 < 余分にかかる処理時間」となるため 全体の処理時間が長く なります。

上記から、合法手の一覧を記録するアルゴリズム は 静的評価関数 を利用した AI では 処理時間がほとんどか変わらず、αβ 法 を利用した AI では 置換表の利用の有無 によって 効果が正反対になる ことがわかりました。

αβ 法 では 置換表を利用するのが一般的 だと思いますので、上記の検証の結果残念ながら本記事では このアルゴリズムを採用しない ことにします。

このように、思いついたアルゴリズム が実際には うまく働かないことはよくある ことです。また、逆にあまり 有望に思えなかったアルゴリズム が実際には うまく働くこともある ので、思いついたアルゴリズムを 実際に実装して試してみることは重要 だと思います。

また、余分に行う「legal_moves 属性の要素の削除と追加」の 処理をもっと速く行うことができれば 置換表を利用する場合でも、このアルゴリズムのほうが 処理速度が速くなることが考えられます。別のゲームの場合 ではこのアルゴリズムのような考え方が 有効に働くこともある と思いますので、このアルゴリズムの考え方を学ぶのは無駄ではないと思います。

細かい話になりますが、legal_moves の要素の順番が変化 することでミニマックス法や αβ 法で行われる ノードの探索の順番が変わる ことになります。その結果、αβ 法 で 計算されるノードの数が変化 して 処理時間が若干変化 する場合が生じますが、計算される 評価値は変化しません。

AI どうしの対戦で必要のない処理の削除

Marubatsu クラスの メソッド は、これまで 人間どうしが対戦を行う ことを 想定して実装 してきました。そのため、AI どうしの対戦では必要のない処理 がいくつか行われています。そのような処理を行わない ようにすることで 処理速度を改善 することができます。どのような処理が AI どうしの対戦で必要がないかについて少し考えてみて下さい。

place_mark と remove_mark メソッドの修正

指定した座標に指定したマークを配置 する処理を行う place_mark は、下記のプログラムのように 指定した座標がゲーム盤の外にある場合 と 既にマークが配置されている場合 は着手が行えなかったことを表す False を返す という処理を行います。指定した座標からマークを削除 する remove_mark も同様 です。

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

この処理は、人間 がキーボードやマウスなどで 着手するマスを指定する場合 のように、間違った座標や着手できないマス に着手を行おうとする 可能性がある場合 は 必要となる処理 ですが、合法手の中から着手を選択 する AI どうしの対戦 では 必ず合法手が計算されるので不要 な処理です。また、合法手が着手 された場合は、0 <= x、x < self.BOARD_SIZE、0 <= y、y < self.BOARD_SIZE、self.board[x][y] == Marubatsu.EMPTY の 5 つの True が計算される条件式 を計算する必要があるため、それらの処理を行わない ようにすることで それなりの処理時間を短縮 できる可能性があります。

そこで、前回の記事で各直線上のマークの数を記録するかどうかの切り替えを行えるようにしたのと同様の下記の方法で、Marubatsu クラスの place_mark と remove_mark でそれらの 確認を行うかどうかの切り替え を行えるようにします。

• Marubatsu クラスに check_coord という、place_mark と remove_mark での 座標（coordinate）などの確認（check）の処理を行うかどうか を表す 属性を追加 する
• Marubatsu クラスの __init__ メソッドに デフォルト値を True とする仮引数 check_coord を追加 し、その値を check_coord 属性に代入 する

ベンチマークの実行

先程行った 合法手の一覧を記録するアルゴリズム は 採用しない ことにしたので JupyterLab を再起動 し、下記のプログラムで 修正前の Marubatsu クラスを改めてインポートし直す 必要があります。

# JupyterLab を再起動する
from marubatsu import Marubatsu

mb = Marubatsu()

次に、比較を行うために下記のプログラムで修正前の place_mark と remove_mark を呼び出す処理を ベンチマーク としてその 処理時間を計測 します。place_mark だけでは局面の状況が変化するので何度も繰り返し処理を行うことはできませんが、同じマスに対して着手と取り除く処理 を行うことで 元の局面に戻る ため、下記の処理を %%timeit で 何度でも繰り返して処理を行う ことができます。どのマスを指定 した場合でも 計算される条件式は同じ なのでゲーム開始時に (1, 1) に 〇 を着手して取り除いた場合の処理を行いました。

%%timeit
mb.place_mark(1, 1, Marubatsu.CIRCLE)
mb.remove_mark(1, 1)

実行結果

453 ns ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

各メソッドの修正

次に各メソッドの修正を行います。

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

• 3 行目：デフォルト値を True とした仮引数 check_coord を追加する
• 7 行目：check_coord 属性に仮引数 check_coord を代入する

 1  def __init__(self, board_size=3, count_linemark=False, check_coord=True):
 2      # ゲーム盤の縦横のサイズ
 3      self.BOARD_SIZE = board_size
 4      # 各直線上のマークの数を数えるかどうか
 5      self.count_linemark = count_linemark
 6      # place_mark と remove_mark メソッドで座標などのチェックを行うかどうか
 7      self.check_coord = check_coord
 8      # 〇×ゲーム盤を再起動するメソッドを呼び出す
 9      self.restart()
10  
11  Marubatsu.__init__ = __init__

行番号のないプログラム

def __init__(self, board_size=3, count_linemark=False, check_coord=True):
    # ゲーム盤の縦横のサイズ
    self.BOARD_SIZE = board_size
    # 各直線上のマークの数を数えるかどうか
    self.count_linemark = count_linemark
    # place_mark と remove_mark メソッドで座標などのチェックを行うかどうか
    self.check_coord = check_coord
    # 〇×ゲーム盤を再起動するメソッドを呼び出す
    self.restart()

Marubatsu.__init__ = __init__

修正箇所

-def __init__(self, board_size=3, count_linemark=False):
+def __init__(self, board_size=3, count_linemark=False, check_coord=True):
    # ゲーム盤の縦横のサイズ
    self.BOARD_SIZE = board_size
    # 各直線上のマークの数を数えるかどうか
    self.count_linemark = count_linemark
    # place_mark と remove_mark メソッドで座標などのチェックを行うかどうか
+   self.check_coord = check_coord
    # 〇×ゲーム盤を再起動するメソッドを呼び出す
    self.restart()

Marubatsu.__init__ = __init__

下記は place_mark と remove_mark メソッドを修正したプログラムです。行う修正は self.check_coord が True の場合はどちらも これまで通りの処理 を、False の場合は 13 ~ 15 行目と 31 ~ 33 行目で指定した座標にマークを配置または削除 して True を返す 処理を行うというものなのでまとめて記述しました。また、修正箇所は特に必要はないと思いましたので省略しました。

 1  def place_mark(self, x, y, mark):
 2      if self.check_coord:
 3          if 0 <= x < self.BOARD_SIZE and 0 <= y < self.BOARD_SIZE:
 4              if self.board[x][y] == Marubatsu.EMPTY:
 5                  self.board[x][y] = mark
 6                  return True
 7              else:
 8                  print("(", x, ",", y, ") のマスにはマークが配置済です")
 9                  return False
10          else:
11              print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
12              return False   
13      else:       
14          self.board[x][y] = mark
15          return True
16  
17  Marubatsu.place_mark = place_mark
18  
19  def remove_mark(self, x, y):
20      if self.check_coord:
21          if 0 <= x < self.BOARD_SIZE and 0 <= y < self.BOARD_SIZE:
22              if self.board[x][y] != Marubatsu.EMPTY:
23                  self.board[x][y] = Marubatsu.EMPTY
24                  return True
25              else:
26                  print("(", x, ",", y, ") のマスにはマークがありません")
27                  return False
28          else:
29              print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
30              return False
31      else:
32          self.board[x][y] = Marubatsu.EMPTY
33          return True
34  
35  Marubatsu.remove_mark = remove_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[x][y] == Marubatsu.EMPTY:
                self.board[x][y] = mark
                return True
            else:
                print("(", x, ",", y, ") のマスにはマークが配置済です")
                return False
        else:
            print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
            return False   
    else:       
        self.board[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[x][y] != Marubatsu.EMPTY:
                self.board[x][y] = Marubatsu.EMPTY
                return True
            else:
                print("(", x, ",", y, ") のマスにはマークがありません")
                return False
        else:
            print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
            return False
    else:
        self.board[x][y] = Marubatsu.EMPTY
        return True

Marubatsu.remove_mark = remove_mark

修正後のベンチマークの実行

上記の修正後に下記のプログラムで 実引数に何も記述しない ことで これまで通り座標のチェックを行う Marubatsu クラスのインスタンスを作成して 先程のベンチマーク を実行します。実行結果については後でまとめて考察します。

mb = Marubatsu()

%%timeit
mb.move(1, 1)
mb.unmove()

実行結果

466 ns ± 9.53 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

次に、今回の記事の最初で行った 3 種類のベンチマークを実行します。

from ai import ai_match, ai2s

ai_match(ai=[ai2s, ai2s], match_num=5000)

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:01<00:00, 2812.18it/s]
count     win    lose    draw
o        2923    1410     667
x        1444    2942     614
total    4367    4352    1281

ratio     win    lose    draw
o       58.5%   28.2%   13.3%
x       28.9%   58.8%   12.3%
total   43.7%   43.5%   12.8%

JupyterLab を再起動したので ai_abs_dls の設定 を行う下記のプログラムを実行します。

from ai import ai14s, ai_abs_dls

eval_params = {"minimax": True}

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8)

実行結果

14.9 ms ± 231 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8)

実行結果

174 ms ± 2.38 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

次に 実引数に check_coord=False を記述することで 座標のチェックを行わない Marubatsu クラスのインスタンスを作成して 上記と同じベンチマーク を実行します。

mb = Marubatsu(check_coord=False)

%%timeit
mb.move(1, 1)
mb.unmove()

実行結果

215 ns ± 11 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

ai2s VS ai2s の対戦を ai_match で行う際には、mbparams={"check_coord": False} を実引数に記述 して 座標のチェックを行わないようにする 必要があります。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:01<00:00, 2915.41it/s]
count     win    lose    draw
o        2875    1458     667
x        1424    2929     647
total    4299    4387    1314

ratio     win    lose    draw
o       57.5%   29.2%   13.3%
x       28.5%   58.6%   12.9%
total   43.0%   43.9%   13.1%

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, use_tt=True, maxdepth=8)

実行結果

14.4 ms ± 122 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit

ai_abs_dls(mb, eval_func=ai14s, eval_params=eval_params, maxdepth=8)

実行結果

166 ms ± 3.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

ベンチマークのまとめと考察

下記は 修正前 、修正後で座標のチェックを行う場合 と 修正後で座標のチェックを行わない場合 のベンチマークをまとめた表です。

	修正前	チェックあり	チェックなし
place_mark と remove_mark	453 ns	466 ns	215 ns
ai2s VS ai2s	2870.59 回/秒	2812.18 回/秒	2915.41 回/秒
置換表ありの αβ 法	14.9 ms	14.9 ms	14.4 ms
置換表なしの αβ 法	179.0 ms	174.0 ms	166.0 ms

修正後で 座標のチェックを行う場合 の place_mark と remove_mark の処理時間 が修正前よりも ほんの少しだけ増えている のは、place_mark と remove_mark の 最初で check_coord が True であるか どうかを判定する if 文の処理が増えた からです。ただし、処理時間はほとんど変わらない ので ai2s VS ai2s や αβ 法 の処理時間はいずれも ほとんど変化しません。そのため、この程度の処理速度の増加は 気にする必要はない でしょう。

一方、修正後で 座標のチェックを行わない場合 の place_mark と remove_mark の処理時間 は半分以下になっているので 処理速度が 2 倍以上に改善 しています。ただし、その差は約 250 ns = 0.25 μs にすぎません。そのため、place_mark と remove_mark が呼び出される move と unmove メソッドが 数回しか呼び出されない ai2s VS ai2s の対戦の 処理速度はほとんど変わりません。一方、計算したノードの数だけ大量に move と unmove が呼び出される 置換表を利用しない αβ 法 の場合は、処理時間が若干減少している ことが確認できます。

1 回の処理での処理時間の改善 が 非常に短い ためこの手法による 処理速度の改善は大きくはありません でしたが、αβ 法 の場合は ベンチマークの結果で実感できるくらいの速度の改善 が見られたので、本記事では この手法を採用 することにします。

他の改善方法について

他にも play メソッドの中で AI どうしの対戦で必要となる処理だけを行う 下記の ai_play というメソッドを定義するなど、いくつかの処理の改善を試みてみたのですが、いずれも 処理速度の改善が小さすぎて ベンチマークの結果から 実感できる改善は得られなかった ので採用しないことにします。

def ai_play(self, ai, params):
    self.restart()
    while self.status == Marubatsu.PLAYING:
        index = 0 if self.turn == Marubatsu.CIRCLE else 1
        x, y = ai[index](self, **params[index])
        self.move(x, y)
    return self.status

Marubatsu.ai_play = ai_play

もしかすると良い改善の方法があるかもしれませんので、良いアイディアを思いついた方は実際に実装してみて処理速度の違いを計測してみて下さい。

今回の記事のまとめ

今回の記事ではいくつかの方法で Marubatsu クラスの処理速度の改善を試みました。残念ながら 合法手の一覧を記録 するアルゴリズムは 処理速度が悪化する場合がある ことが判明したので採用には至りませんでしたが、AI どうしの対戦に必要がない処理を行わない ようにする方法では 若干の処理速度の改善 が見られました。

また、繰り返し処理の中 で 繰り返しの対象となる list などの要素を削除、追加 するという処理が バグの原因 になりやすいことを説明しました。

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

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

次回の記事

1. この用語は本記事独自の用語です。Python の一般的な用語ではない点に注意して下さい。詳細は以前の記事を復習して下さい ↩