目次と前回の記事

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

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

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

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

勝敗判定の処理の高速化

前回までの記事では、AI の関数 の ボトルネックを改善 することで AI が着手を選択する処理の高速化 を行いましたが、AI の関数の処理 は AI どうしが〇× ゲームの 対戦を行う際の処理の一部 にすぎません。AI どうしの対戦で行われる処理の中に 他にもボトルネックとなる処理 があれば、それを改善することで 処理の高速化 を行うことができます。

AI どうしの対戦で行われる処理の検証

ボトルネックとなる処理 の 見当をつける ためには、AI どうしの対戦で 行われる処理を検証 する必要があります。下記は、Marubatsu クラス のインスタンスを作成し、play メソッドを呼び出すことで行われる AI どうしの対戦の処理の手順 です。なお、下記の処理は GUI を使わずに行う場合の処理です。具体的な処理の内容は play メソッドとその中から呼び出される play_loop のプログラムを確認して下さい。

restart メソッドを呼び出してゲームの初期化を行う
ゲームの決着がつくまで下記の処理を繰り返す
1. 現在の局目の手番を担当する AI の関数を呼び出して着手を計算する
2. move メソッドを呼び出して計算した着手を行う
ゲームの勝敗の結果を返り値として返す

上記の 手順 1 の restart メソッドの処理は、ゲームの開始時の状態になるように 様々な属性の値を初期化 する処理で、改善の余地はほとんどなさそう です。

手順 2-1 の処理は 前回の記事で改善済み、手順 3 の処理は 返り値を返すだけ なので 改善の余地はありません。従って、改善の可能性がある のは、手順 2-2 の着手を行う move メソッドの処理だけ であることがわかります。そこで、move メソッド で (x, y) のマスに着手を行う処理を 検証する ことにします。なお、ほとんどの方は Marubatsu クラスで行われる処理を忘れてると思いますので、プログラムを示しながら説明することにます。

`move` メソッドで行われる処理

下記は move メソッドの定義と (x, y) のマスに着手を行う 際の処理の説明です。

2 行目：(x, y) のマスが埋まっているかどうかを判定し、埋まっていない場合に 3 ~ 12 行目で (x, y) の着手に応じた属性の値を更新する
3 行目：last_turn 属性に現在の手番を代入する
4 行目：turn 属性の手番を〇と × で入れ替える
5 行目：move_count 属性の値に 1 を足す
6 行目：ゲームの状態を表す status 属性に、勝敗判定を行う judge メソッドを呼び出してその返り値を代入する
7 行目：last_move 属性に行った着手を代入する
8、9 行目：records 属性に代入された list に last_move の要素を追加する
10 ~ 12 行目：この部分の処理は GUI でリプレイを表示中に着手を行った場合に行われる処理なので、AI どうしの対戦では実行されない。リプレイ機能について忘れた方は以前の記事を復習して下さい

 1  def move(self, x, y):
 2      if self.place_mark(x, y, self.turn):
 3          self.last_turn = self.turn
 4          self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
 5          self.move_count += 1
 6          self.status = self.judge()
 7          self.last_move = x, y
 8          if len(self.records) <= self.move_count:            
 9              self.records.append(self.last_move)
10          else:
11              self.records[self.move_count] = self.last_move
12              self.records = self.records[0:self.move_count + 1]

上記の 6 行目以外の処理 は、変数に値を代入する処理と、list に要素を通過する処理だけなので 改善の余地はほとんどない でしょう。6 行目の処理 は勝敗判定を行う judge メソッドを呼び出す処理なので、次に judge メソッドで行われる処理を検証することにします。

`judge` メソッドで行われる処理

下記は judge メソッドの定義とその処理の説明です。

3、4 行目：is_winner メソッドで〇が勝利しているかどうかを判定し、勝利している場合は Marubatsu.CIRCLE を返り値として返す
6、7行目：is_winner メソッドで × が勝利しているかどうかを判定し、勝利している場合は Marubatsu.CROSS を返り値として返す
9、10 行目： is_full メソッドですべてのマスが埋まっているかどうかを判定し、埋まっている場合は引き分けを表す Marubatsu.DRAW を返り値として返す
12、13 行目：上記のどれでもない場合はゲーム中であることを表す Marubatsu.PLAYING を返り値として返す

 1  def judge(self):
 2      # 〇 の勝利の判定
 3      if self.is_winner(Marubatsu.CIRCLE):
 4          return Marubatsu.CIRCLE
 5      # × の勝利の判定
 6      elif self.is_winner(Marubatsu.CROSS):
 7          return Marubatsu.CROSS   
 8      # 引き分けの判定
 9      elif self.is_full():
10          return Marubatsu.DRAW
11      # 上記のどれでもなければ決着がついていない
12      else:
13          return Marubatsu.PLAYING

judge メソッドの処理では is_winner メソッドと is_full メソッドが呼び出されているのでそれらの処理を検証することにします。

`is_full` メソッドで行われる処理

先に 簡単な処理を行う 下記の is_full メソッドから検証します。下記のプログラムのように、is_full メソッドでは 手数がゲーム盤のマスの数と同じ場合 は すべてのマスが埋まっている ので True を、そうでなければ False を返す処理を行っています。この処理には 改善の余地はほとんどない でしょう。

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

`is_winner` メソッドで行われる処理

下記は is_winner メソッドの定義とその処理の説明です。

3 ~ 6 行目：繰り返し処理で、縦 3 列、横 3 行のそれぞれの直線上のマスに対して is_same メソッドを呼び出すことで指定されたマークが並んでいるかどうかを判定し、並んでいる場合は True を返す
8、9 行目：左上から右下方向の斜め 3 マスに対して is_same メソッドを呼び出すことで指定されたマークが並んでいるかどうかを判定し、並んでいる場合は True を返す
11、12 行目：右上から左下方向の斜め 3 マスに対して is_same メソッドを呼び出すことで指定されたマークが並んでいるかどうかを判定し、並んでいる場合は True を返す
15 行目：上記のどれでもない場合は指定したマークが並んでいないので False を返す

 1  def is_winner(self, player:str):
 2      # 横方向と縦方向の判定
 3      for i in range(self.BOARD_SIZE):
 4          if self.is_same(player, coord=[0, i], dx=1, dy=0) or \
 5             self.is_same(player, coord=[i, 0], dx=0, dy=1):
 6              return True
 7      # 左上から右下方向の判定
 8      if self.is_same(player, coord=[0, 0], dx=1, dy=1):
 9          return True
10      # 右上から左下方向の判定
11      if self.is_same(player, coord=[self.BOARD_SIZE - 1, 0], dx=-1, dy=1):
12          return True
13  
14      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
15      return False

is_winner メソッドの処理では is_same メソッドが呼び出されているのでそれらの処理を検証することにします。

`is_same` メソッドで行われる処理

下記は is_same メソッドの定義とその処理の説明です。下記の処理について忘れた方は以前の記事を復習して下さい。

3、4 行目：仮引数で指定した直線上の並びのマスのマークを要素とする list を計算する
5 行目：上記で計算した list の要素を結合した文字列を計算する
6 行目：上記で計算した文字列と、指定したマークをゲーム盤の大きさの数だけ結合した文字列が等しい場合は、その直線上に指定したマークが並んでいることになるので True を、そうでない場合は False を返す

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

上記の検証結果から、move メソッドが行う処理の中で 勝敗判定を行う judge メソッド の処理が ボトルネックになっている可能性がある ことがわかりました。

ここまでで検証した 勝敗判定の処理 は、わかりやすさを重視して実装 したものなので 無駄な処理が多数行われており、それらの処理を 効率化することで処理の高速化 を行うことができます。どのような効率化を行うことができるかについて少し考えてみて下さい。

ベンチマークの設定

処理の高速化を行う前に、処理速度の比較 のための ベンチークを設定 します。ただし、move メソッドの処理を行うと 局面の状況が変化 してしまうため、move メソッドの処理時間だけ を 繰り返し何度も計測することは困難 です。そこで、move の処理が何度も行われる AI どうしの対戦の処理時間 をベンチマークとすることにします。

move の処理では 勝敗判定を行う ので、その 処理時間 は 局面によって変わります。そのため できるだけ多くの種類の局面 での move の処理時間を計測 するようなベンチマークを設定したほうが良いでしょう。以前の記事で説明したように、ランダムな着手を行う AI どうし の対戦では、〇× ゲームの すべての局面が生じる可能性 があります。そのため、ランダムな AI どうしの 対戦を数多く行う ことで、ほぼすべての種類の局面が生じる ことになります。そこで、ランダムな着手を行う ai2s どうしの対戦 を複数回行った際の処理時間の合計をベンチマークとすることにします。具体的には下記のプログラムで ai_match を利用して ai2s VS ai2s の対戦を 10000 回 行います。なお、match_num=5000 としたのは、ai_match は macth_num 回の対戦を 先手と後手を入れ替えて行う ためです。

from ai import ai_match, ai2s

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:15<00:00, 323.25it/s]
count     win    lose    draw
o        2969    1426     605
x        1477    2897     626
total    4446    4323    1231

ratio     win    lose    draw
o       59.4%   28.5%   12.1%
x       29.5%   57.9%   12.5%
total   44.5%   43.2%   12.3%

実行結果から、修正を行う前の ai2s VS ai2s の 10000 回の対戦の 処理時間が約 15 秒 であることが確認できました。なお、この 15 秒という数値は 精度が低いという問題 があります。そこで、より精度が高い 右に表示される 323.25it/s という 1 秒間 に 平均で 323.25 回の繰り返し （iteration）が行われたことを表す数値も ベンチマークとする ことにします。

この 323.25 回の繰り返し処理は、先手と後手を入れ替えた場合を含む 2 回の対戦が行われた回数なので、実際に 1 秒間に対戦が行われた回数 は 倍の 626.50 回 です。

勝敗判定の処理の高速化の実装

現状のプログラムでは 〇と × の勝利の判定 を、〇と × が 縦 3 通り、横 3 通り、斜め 2 通り の 直線に並んでいるか を判定するという方法で行っていますが、〇× ゲームの性質を考える ことで、この判定を より効率的に行う ことができます。

なお、引き分けの判定 を行う is_full メソッドは先程検証したように 改善の余地はほとんどない と思いますので修正は行わないことにします。

4 手目以下の判定の修正

〇× ゲームは 以下のいずれかの場合 に ゲームの決着 がつきます。

〇が 3 つ直線上に並ぶ（〇の勝利）
× が 3 つ直線上に並ぶ（× の勝利）
9 マスすべてが埋まっており、どちらも勝利していない（引き分け）

〇× ゲームはゲーム開始時はマークが一つも配置されておらず、〇と × が交互に着手を行うので、上記の 決着がつく最短の手数 は以下の表のようになります。

状況	最短手数
〇の勝利	5
× の勝利	6
引き分け	9

上記の表から、手数が 5 未満 の場合は絶対にゲームの 決着がついていない ことがわかりますが、現状の judge メソッドは 手数が 5 未満の場合も 決着がついているかどうかの 判定を行っている点が無駄 です。

なお、Marubatsu クラスは ゲーム盤のサイズを 3 以外の値 にすることができます。ゲーム盤のサイズが $\boldsymbol{s}$ の場合の 決着がつく最短の手数 は以下の表のようになります。ゲーム盤のサイズが 2 以上の場合は $s × 2 ≦ s × s$ なので、表の 最短手数の最小値 は $\boldsymbol{s × 2 - 1}$ です。従って、手数が $\boldsymbol{s × 2 - 1}$ 未満の場合は 決着がついていない ことになります。

状況	最短手数
〇の勝利	$s × 2 - 1$
× の勝利	$s × 2$
引き分け	$s × s$

ゲーム盤のサイズは BOARD_SIZE 属性に代入されているので、下記のプログラムの 4、5 行目のように 手数が self.BOARD_SIZE * 2 - 1 未満の場合 はゲーム中であることを表す Marubatsu.PLAYING を返す ことで、その後の 決着がついているかどうかの 判定を行わない ように judge メソッドを修正することができます。

 1  from marubatsu import Marubatsu
 2  
 3  def judge(self):
 4      if self.move_count < self.BOARD_SIZE * 2 - 1:
 5          return Marubatsu.PLAYING
 6      # 〇 の勝利の判定
 7      if self.is_winner(Marubatsu.CIRCLE):
 8          return Marubatsu.CIRCLE
 9      # × の勝利の判定
10      elif self.is_winner(Marubatsu.CROSS):
11          return Marubatsu.CROSS   
12      # 引き分けの判定
13      elif self.is_full():
14          return Marubatsu.DRAW
15      # 上記のどれでもなければ決着がついていない
16      else:
17          return Marubatsu.PLAYING      
18      
19  Marubatsu.judge = judge

行番号のないプログラム

from marubatsu import Marubatsu

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

修正箇所

from marubatsu import Marubatsu

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

上記の修正後に下記のプログラムで judge メソッドが正しい かどうかを判定する test_judge を実行すると、実行結果から 正しいことが確認 できました。

from test import test_judge

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

次に、下記のベンチマークを実行すると実行結果のように 処理時間 が約 15 秒から 約 5 秒に短縮 され、1 秒あたりの回数 が 323.25 回から 876.84 回に増えた ことが確認できます。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:05<00:00, 876.84it/s] 
count     win    lose    draw
o        2942    1423     635
x        1436    2907     657
total    4378    4330    1292

ratio     win    lose    draw
o       58.8%   28.5%   12.7%
x       28.7%   58.1%   13.1%
total   43.8%   43.3%   12.9%

判定を行う必要がない手番の判定の修正

〇× ゲームで 〇が勝利する のは 〇が着手した直後だけ、× が勝利する のは × が着手した直後だけ ですが、それにも関わらず現状の judge メソッドは 常に〇と × の両方 が勝利しているかどうかの 判定を行っている点が無駄 です。

そこで、下記のプログラムのように 勝利した可能性がある手番 の 勝利判定のみを行う ように judge メソッドを修正することができます。

5、6 行目：勝利する可能性がある のは 直前に着手を行ったプレイヤー なので、直前の手番 を表す last_turn の勝利判定だけ を行い、勝利していた場合は last_turn を返り値として返すように修正した

 1  def judge(self):
 2      if self.move_count < self.BOARD_SIZE * 2 - 1:
 3          return Marubatsu.PLAYING
 4      # 直前に着手を行ったプレイヤーの勝利の判定
 5      if self.is_winner(self.last_turn):
 6          return self.last_turn
 7      # 引き分けの判定
 8      elif self.is_full():
 9          return Marubatsu.DRAW
10      # 上記のどれでもなければ決着がついていない
11      else:
12          return Marubatsu.PLAYING      
13      
14  Marubatsu.judge = judge

行番号のないプログラム

def judge(self):
    if self.move_count < self.BOARD_SIZE * 2 - 1:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    if self.is_winner(self.last_turn):
        return self.last_turn
    # 引き分けの判定
    elif self.is_full():
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING      
    
Marubatsu.judge = judge

修正箇所

def judge(self):
    if self.move_count < self.BOARD_SIZE * 2 - 1:
        return Marubatsu.PLAYING
-   # 〇 の勝利の判定
-   if self.is_winner(Marubatsu.CIRCLE):
-       return Marubatsu.CIRCLE
-   # × の勝利の判定
-   elif self.is_winner(Marubatsu.CROSS):
-       return Marubatsu.CROSS 
+   # 直前に着手を行ったプレイヤーの勝利の判定
+   if self.is_winner(self.last_turn):
+       return self.last_turn
    # 引き分けの判定
    elif self.is_full():
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING      
    
Marubatsu.judge = judge

上記の修正後に下記のプログラムで judge メソッドが正しいか どうかを判定する test_judge を実行すると、実行結果から 正しいことが確認 できました。実行結果は先ほどと同じなので折りたたみます。

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

次に、下記のベンチマークを実行すると実行結果のように 処理時間 が約 5 秒から 約 4 秒に短縮 され、1 秒あたりの回数 が 876.84 回から 1242.03 回に増えた ことが確認できます。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:04<00:00, 1242.03it/s]
count     win    lose    draw
o        2976    1395     629
x        1419    2961     620
total    4395    4356    1249

ratio     win    lose    draw
o       59.5%   27.9%   12.6%
x       28.4%   59.2%   12.4%
total   44.0%   43.6%   12.5%

必要のない直線の判定の修正

〇× ゲームで 勝利した場合 は、着手を行ったマスを含む直線 が 同じマーク になります。例えば (x, y) のマスに着手を行って 勝利した場合 は下記のいずれかの場合が考えられます。

x 行 に同じマークが並んだ
y 列 に同じマークが並んだ
(0, 0)、(1, 1)、(2, 2) のいずれかのマスに着手を行った場合に 左上から右下方向 に同じマークが並んだ
(2, 0)、(1, 1)、(0, 2) のいずれかのマスに着手を行った場合に 右上から左下方向 に同じマークが並んだ

下記は、着手したマス と 判定を行う必要がある直線の数 を表した表で、最小で 2 回、最大で 4 回 判定を行えば良いことがわかります。それにも関わらず 現状の judge メソッドは 常に 8 種類の直線 に対してマークが並んでいるかどうかを判定している点が無駄です。

着手したマス	直線の数
真ん中	4
隅	3
辺	2

そこで、必要な直線だけ判定を行う ように修正することにします。

`move` メソッドの修正

必要な直線だけ を判定するためには 直前に行われた着手の座標が必要 となります。ただし、現状では下記のプログラムのように move メソッドの中で 勝敗判定を行う judge メソッドを 呼び出した後 で 直前に行われた着手の座標を表す last_turn 属性に 値を代入 しているので、勝敗判定の処理で 直前に行われた座標を利用できない という問題があります。

    self.status = self.judge()
    self.last_move = x, y

そこで、下記のプログラムの 6、7 行目のように上記の 処理の順番を変える ように move メソッドを修正する必要があります。

 1  def move(self, x, y):
 2      if self.place_mark(x, y, self.turn):
 3          self.last_turn = self.turn
 4          self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
 5          self.move_count += 1
 6          self.last_move = x, y
 7          self.status = self.judge()
 8          if len(self.records) <= self.move_count:            
 9              self.records.append(self.last_move)
10          else:
11              self.records[self.move_count] = self.last_move
12              self.records = self.records[0:self.move_count + 1]
13              
14  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
        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]
            
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.status = self.judge()
        self.last_move = x, y
+       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]
            
Marubatsu.move = move

`is_winner` メソッドの修正

次に、下記のプログラムのように is_winner メソッドが 必要な直線のみを判定 するように修正します。

2 行目：直前の着手の座標を x と y に代入する
3 ~ 5 行目：y 行と x 列のみの判定を行うように修正する
7 ~ 12 行目：斜めの直線上のマスに着手した場合のみ斜めの判定を行うように修正する。左上から右下の直線のマス は x 座標と y 座標が同じ であることと、右上から左下の直線のマス は x 座標と y 座標の合計がゲーム盤の大きさ - 1 であることを利用して判定を行っている

 1  def is_winner(self, player):
 2      x, y = self.last_move
 3      if self.is_same(player, coord=[0, y], dx=1, dy=0) or \
 4         self.is_same(player, coord=[x, 0], dx=0, dy=1):
 5          return True
 6      # 左上から右下方向の判定
 7      if x == y and self.is_same(player, coord=[0, 0], dx=1, dy=1):
 8          return True
 9      # 右上から左下方向の判定
10      if x + y == self.BOARD_SIZE - 1 and \
11          self.is_same(player, coord=[self.BOARD_SIZE - 1, 0], dx=-1, dy=1):
12          return True
13  
14      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
15      return False
16  
17  Marubatsu.is_winner = is_winner

行番号のないプログラム

def is_winner(self, player):
    x, y = self.last_move
    if self.is_same(player, coord=[0, y], dx=1, dy=0) or \
       self.is_same(player, coord=[x, 0], dx=0, dy=1):
        return True
    # 左上から右下方向の判定
    if x == y and self.is_same(player, coord=[0, 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):
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner

修正箇所

def is_winner(self, player):
+   x, y = self.last_move
-   # 横方向と縦方向の判定
-   for i in range(self.BOARD_SIZE):
-       if self.is_same(player, coord=[0, i], dx=1, dy=0) or \
-          self.is_same(player, coord=[i, 0], dx=0, dy=1):
-           return True
+   if self.is_same(player, coord=[0, y], dx=1, dy=0) or \
+      self.is_same(player, coord=[x, 0], dx=0, dy=1):
+       return True
    # 左上から右下方向の判定
-   if self.is_same(player, coord=[0, 0], dx=1, dy=1):
+   if x == y and self.is_same(player, coord=[0, 0], dx=1, dy=1):
        return True
    # 右上から左下方向の判定
-   if self.is_same(player, coord=[self.BOARD_SIZE - 1, 0], dx=-1, dy=1):
+   if x + y == self.BOARD_SIZE - 1 and \
+       self.is_same(player, coord=[self.BOARD_SIZE - 1, 0], dx=-1, dy=1):
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner

上記の修正後に下記のプログラムで judge メソッドが正しいか どうかを判定する test_judge を実行すると、実行結果から 正しいことが確認 できました。

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

次に、下記のベンチマークを実行すると実行結果のように 処理時間 が約 4 秒から 約 2 秒に短縮 され、1 秒あたりの回数 が 1242.03 回から 1891.24 回に増えた ことが確認できます。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:02<00:00, 1891.24it/s]
count     win    lose    draw
o        2969    1468     563
x        1468    2911     621
total    4437    4379    1184

ratio     win    lose    draw
o       59.4%   29.4%   11.3%
x       29.4%   58.2%   12.4%
total   44.4%   43.8%   11.8%

各直線上のマークの数を記録する修正方法

下記は指定した直線上に 同じマークが並んでいるかどうかを判定 する is_same メソッドのプログラムと行われる処理の再掲です。この処理は、list を作成し、join メソッドでその要素を結合するという処理を行っていますが、この処理を毎回行う のはあまり 効率が良いとは言えません。もっと効率の良い方法はないでしょうか？

3、4 行目：仮引数で指定した直線上の並びのマスのマークを要素とする list を計算する
5 行目：上記で計算した list の要素を結合した文字列を計算する
6 行目：上記で計算した文字列と、指定したマークをゲーム盤の大きさの数だけ結合した文字列が等しい場合は、その直線上に指定したマークが並んでいることになるので True を、そうでない場合は False を返す

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

下記は、上記とは別の判定のアルゴリズムです。

ゲーム開始時 に縦 3 列、横 3 行、斜め 2 つの 8 種類のそれぞれの直線上 に 〇と × がいくつ並んでいるかを記録する変数を用意 してそれぞれを 0 で初期化 する
着手を行うたび に、上記の変数の中で 対応する変数に 1 を足す
上記で 1 を足した結果 ゲーム盤のサイズと同じ数 になった場合は、直線状に 同じマークが並んだ ことになる

上記の 手順 1 は、8 種類の直線に対応する〇と × が並んだ数を表す変数に 0 を代入する処理なので、8 × 2 = 16 個の変数に 0 を代入 する処理です。

手順 2 は着手したマスを含む直線に 対応する変数に 1 を足す という処理です。なお、斜めの直線に関してはその直線上のマスに着手したかどうかの判定の処理が加わります

手順 3 は その値が特定の値であるかを判定 するという処理です

また、手順 2 と 3 は is_same と同様に 着手が行われるたびに 2 ~ 4 回行われる処理 です。

下記は、これまでのアルゴリズムと上記のアルゴリズムの処理の 違いを表す表 で、行われる処理の処理時間の差の合計 が 全体の処理時間の差 となります。

	これまでのアルゴリズム	上記のアルゴリズム
ゲーム開始時		手順 1
`move` メソッド	`is_same`	手順 2、3

そこで、それぞれの処理が 1 回のゲームで何回行われるか を数えることにします。

ゲーム開始時に行われる処理は明らかに 1 回なので、手順 1 の処理は 1 回だけ 行われます。

一方 ai2s どうしの対戦 では move メソッドは 下記の場合 に呼び出されます。

ai2s は ai_by_score の中で 合法手を着手した局面の評価値を計算する際 に move メソッドを呼び出すので、ai2s が呼び出されるたび にその局面の 合法手の数だけ move メソッドが呼び出される
ai2s が計算した最善手を着手する際に move メソッドが呼び出される

下記は、着手を行った際に呼び出される move メソッドの回数 を表します。

手数	回数	合計
1	10	10
2	9	19
3	8	27
4	7	34
5	6	40
6	5	45
7	4	49
8	3	52
9	2	54

〇× ゲームは 5 ~ 9 回の手数で決着がつく ゲームなので、上記の表から 1 回のゲームで 40 ~ 54 回 move メソッドが 呼び出される ことがわかります。

下記は、先程の表に回数を加えた表です。

	これまでのアルゴリズム	上記のアルゴリズム	回数
ゲーム開始時		手順 1	1
`move` メソッド	`is_same`	手順 2、3	40 ~ 54

上記から、各直線上のマークの数を記録するアルゴリズムの方が 処理時間が短くなること を、1 回の対戦での処理時間の差を見積もる ことで示します。なお、厳密な見積もり を行っても、実際の処理時間の差とは異なる可能性が高い ため 大雑把に見積もる ことにし、実際の処理時間の差 は ベンチマークで確認 することにします。

上記の表のから move メソッドが実行される回数には幅がありますが、その 間を取って 50 回 として見積もることにします。move メソッドが実行されると is_same または手順 2、3 が 2 ~ 4 回実行 されるので、こちらも 間を取って 3 回 として見積もることにします。

上記から、1 回の対戦 で is_same または手順 2、3 が 50 × 3 = 150 回 行われるものとして 処理速度の差を大雑把に見積もる と以下の式のようになります。

(is_same の処理時間 - 手順 2、3 の処理時間) × 150 - 手順 1 の処理時間

最初は筆者は上記の見積もりが正しいと思っていたのですが、上記の見積もりが実は間違っている ことが後で判明しました。何が間違っているかについてはこの後で説明 しますが、それまでは 上記の見積もりが正しいものとして説明を続けます。

手順 1 の主な処理は 16 回の代入処理、手順 2 と 3 の主な処理は 代入処理と判定処理 ですが、手順 2 と 3 は約 150 回 も行われるので 手順 1 の処理時間は全体でみれば 非常に小さな割合 となるので 無視する ことにします。

is_same で行われる処理は list の作成 と join メソッドによる文字列の結合 ですが、この処理は明らかに 手順 2、3 の処理と比べる と 複雑で処理時間が長くなりそう です。従って、上記のアルゴリズムによって 処理速度が高速化することが期待 できます。そのことを確認するために、上記のアルゴリズムで判定を行うように プログラムを修正 し、ベンチマークを実行して 処理時間を比較 することにします。

この修正方法は、これまでになかったデータ を Marubatsu クラスに 記録する必要がある ので、Marubatsu クラスのインスタンスの データ量が増えるという欠点 があります。そのため、下記のような 問題が発生する可能性がある 点に注意が必要です。

Marubatsu クラスのインスタンスを大量に作成して変数に代入する場合に、コンピューターの メモリが足りなくなる 可能性がある
Marubatsu クラスのインスタンスを大量にファイルに保存する場合に、コンピューターのハードディスクなどの 容量が足りなくなる 可能性がある
deepcopy でコピー する必要がある場合は 処理時間が長くなる

なお、現状では前者の 2 つの処理は行っていない点と、以前の記事で deepcopy でコピーすることはなくなったので、上記の欠点は大きな問題にはならない でしょう。

並んでいる数を表すデータ構造の設定

最初に、縦 3 列、横 3 列、斜め 2 つのそれぞれに〇と × がいくつ並んでいるかを どのように記録するか を決める必要があります。様々な方法が考えられると思いますが、本記事では下記のデータ構造でそのデータを記録することにします。もっと良い別のデータ構造を思いついた方はその方法で実装し、本記事の場合と処理速度を比較してみて下さい。

列（column）に〇と × 並んでいる数を colcount 属性に下記のデータ構造で記録する
- 〇が並んでいる数を Marubatsu.CIRLCE のキーの値、× が並んでいる数を Marubatsu.CROSS のキーの値 に記録する dict で表現 する
- 〇が並んでいる数 を インデックスが列の番号 を表す list で記録 する
- 例えば 〇が 2 列 に並んでいる数は self.colcount[Maurbatsu.CIRCLE][2] に記録する
- × の場合も同様のデータ構造で記録する
行（row）に〇と × が並んでいる数を rowcount 属性に 同様のデータ構造 で記録する
斜め（対角線（diagonal））に〇と × が並んでいる数を diacount という属性に 同様のデータ構造 で記録する。ただし、〇や × がいくつ並んでいるかを表す list は 0 番の要素に左上から右下の方向 の数を、1 番の要素に右上から左下方向の数 を記録する

`restart` メソッドの修正

手順 1 で ゲーム開始時に上記のデータを初期化 する必要があるので、下記のプログラムの 2 ~ 13 行目のように restart メソッドに上記のデータを記録 するように修正します。列や行の数 は ゲーム盤のサイズに等しい ので [0] * self.BOARD_SIZE でゲーム盤のサイズの数だけ 0 を要素を持つ list を作成 することができます。斜め方向の直線は 2 種類 なので [0] * 2 と記述していますが、わかりづらいと思った方は [0, 0] と記述してもかまいません。

 1  def restart(self):
元と同じなので省略
 2      self.rowcount = {
 3          Marubatsu.CIRCLE: [0] * self.BOARD_SIZE,
 4          Marubatsu.CROSS: [0] * self.BOARD_SIZE,
 5      }
 6      self.colcount = {
 7          Marubatsu.CIRCLE: [0] * self.BOARD_SIZE,
 8          Marubatsu.CROSS: [0] * self.BOARD_SIZE,
 9      }
10      self.diacount = {
11          Marubatsu.CIRCLE: [0] * 2,
12          Marubatsu.CROSS: [0] * 2,
13      }
14      
15  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]
    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,
    }
    
Marubatsu.restart = restart

修正箇所

def restart(self):
元と同じなので省略
+   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,
+   }
    
Marubatsu.restart = restart

`move` メソッドの修正

次に、下記のプログラムのように 手順 2 の 着手を行った際に対応する変数に 1 を足す 処理を行うように move メソッドを修正します。

7、8 行目：x 列と y 列のマークの数を加算する
9 ~ 12 行目：条件を満たす場合に斜め方向のマークの数を加算する

 1  def move(self, x, y):
 2      if self.place_mark(x, y, self.turn):
 3          self.last_turn = self.turn
 4          self.turn = Marubatsu.CROSS if self.turn == Marubatsu.CIRCLE else Marubatsu.CIRCLE  
 5          self.move_count += 1
 6          self.last_move = x, y
 7          self.colcount[self.last_turn][x] += 1
 8          self.rowcount[self.last_turn][y] += 1
 9          if x == y:
10              self.diacount[self.last_turn][0] += 1        
11          if x + y == self.BOARD_SIZE - 1:
12              self.diacount[self.last_turn][1] += 1        
13          self.status = self.judge()
14          if len(self.records) <= self.move_count:            
15              self.records.append(self.last_move)
16          else:
17              self.records[self.move_count] = self.last_move
18              self.records = self.records[0:self.move_count + 1]
19              
20  Marubatsu.move = move
21  Marubatsu.restart = restart

行番号のないプログラム

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
        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]
            
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
+       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]
            
Marubatsu.move = move

`unmove` メソッドの修正

筆者も最初は忘れていたのですが、move メソッドの 逆の処理を行う unmove に対して直線上に並んだ マークの数を減らす 処理を行うように修正する必要があります。ai2s などの ai_by_score や ai_by_mmscore で デコレートする AI の関数 では unmove の処理が行わる ため、その修正を行わないと直線上の マークの数が間違った数 になり 正しい勝敗判定を行えなくなる からです。実際に筆者は unmove の修正をし忘れた ため、ai_match の対戦結果がすべて引き分けになる という バグを発生 させてしまいました。興味がある方は下記の unmove 以外の修正を行った状態で ai_match のベンチマークを実行してみて下さい

先程の検証では unmove の処理を考慮していなかった 点が 不正確 でしたが、unmove で行われる処理は 手順 2 の逆の処理 を行うというもので、その処理は 1 回の代入処理にすぎません。そのため、unmove で行わわれる処理を考慮にいれても is_same の処理時間のほうが長い ことに変わりはないでしょう。

先程の見積もりが間違っている述べましたが、その理由は unmove ではありません。

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

3 ~ 9 行目：unmove の元の処理を行う前に、move とは逆に直前の着手を行った直線上のマークの数を 1 減らす処理を行う

 1  def unmove(self):
 2      if self.move_count > 0:
 3          x, y = self.last_move
 4          self.colcount[self.last_turn][x] -= 1
 5          self.rowcount[self.last_turn][y] -= 1
 6          if x == y:
 7              self.diacount[self.last_turn][0] -= 1        
 8          if x + y == self.BOARD_SIZE - 1:
 9              self.diacount[self.last_turn][1] -= 1           
10          if self.move_count == 0:
11              self.last_move = (-1, -1)
12          self.move_count -= 1
13          self.turn, self.last_turn = self.last_turn, self.turn
14          self.status = Marubatsu.PLAYING
15          x, y = self.records.pop()
16          self.remove_mark(x, y)
17          
18          self.last_move = self.records[-1]  
19          
20  Marubatsu.unmove = unmove

行番号のないプログラム

def unmove(self):
    if self.move_count > 0:
        x, y = self.last_move
        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]  
        
Marubatsu.unmove = unmove

修正箇所

def unmove(self):
    if self.move_count > 0:
+       x, y = self.last_move
+       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]  
        
Marubatsu.unmove = unmove

`is_winner` メソッドの修正

最後に、下記のプログラムのように 直線上のマークの数で判定を行う ように is_winner メソッドを修正 します。なお、それぞれの判定は 2 行で記述できる ので、is_same メソッドの呼び出しをやめて、判定処理を judge メソッドの中に記述 することにしました。

3 ~ 12 行目：列、行、斜め直線の判定をマークの数を利用して判定するように修正する

 1  def is_winner(self, player):
 2      x, y = self.last_move
 3      if self.rowcount[player][y] == self.BOARD_SIZE or \
 4         self.colcount[player][x] == self.BOARD_SIZE:
 5              return True
 6      # 左上から右下方向の判定
 7      if x == y and self.diacount[player][0] == self.BOARD_SIZE:
 8          return True
 9      # 右上から左下方向の判定
10      if x + y == self.BOARD_SIZE - 1 and \
11          self.diacount[player][1] == self.BOARD_SIZE:
12          return True
13  
14      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
15      return False
16  
17  Marubatsu.is_winner = is_winner

行番号のないプログラム

def is_winner(self, player):
    x, y = self.last_move
    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

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner

修正箇所

def is_winner(self, player):
    x, y = self.last_move
-   if self.is_same(player, coord=[0, y], dx=1, dy=0) or \
-      self.is_same(player, coord=[x, 0], dx=0, dy=1):
+   if self.rowcount[player][y] == self.BOARD_SIZE or \
+      self.colcount[player][x] == self.BOARD_SIZE:
            return True
    # 左上から右下方向の判定
-   if x == y and self.is_same(player, coord=[0, 0], dx=1, dy=1):
+   if x == y and self.diacount[player][0] == self.BOARD_SIZE:
        return True
    # 右上から左下方向の判定
-   if x + y == self.BOARD_SIZE - 1 and \
-       self.is_same(player, coord=[self.BOARD_SIZE - 1, 0], dx=-1, dy=1):    
+   if x + y == self.BOARD_SIZE - 1 and \
+       self.diacount[player][1] == self.BOARD_SIZE:
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner

上記の修正後に下記のプログラムで judge メソッドが正しいか どうかを判定する test_judge を実行すると、実行結果から 正しいことが確認 できました。

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

次に、下記のベンチマークを実行すると実行結果のように 処理時間 が約 2 秒のままほとんど変化していません。また、1 秒あたりの回数 も 1891.24 回から 1992.20 回 のように約 5 % しか増えておらず、これまでに行った改良と比較して ほとんど変化しない ことが確認できます。手順 2、3 と is_same の処理時間の差が大きそうであることを考えるとこの結果がおかしいのではないかと思う人がいるかもしれませんが、このような結果になる理由は 先程行った見積もりに間違いがあったから です。その理由について少し考えてみて下さい。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:02<00:00, 1992.20it/s]
count     win    lose    draw
o        2944    1419     637
x        1457    2917     626
total    4401    4336    1263

ratio     win    lose    draw
o       58.9%   28.4%   12.7%
x       29.1%   58.3%   12.5%
total   44.0%   43.4%   12.6%

処理時間がほとんど変わらない理由

下記は各直線上のマークの数を記録するアルゴリズムの再掲です。ただし、手順 2 に unmove の処理を加えました。

ゲーム開始時 に縦 3 列、横 3 行、斜め 2 つの 8 種類のそれぞれの直線上 に 〇と × がいくつ並んでいるかを記録する変数を用意 してそれぞれを 0 で初期化 する
着手を行うたび に、上記の変数の中で 対応する変数に 1 を足す。着手を取り消すたび に上記の変数の中で 対応する変数から 1 を引く
上記で 1 を足した結果 ゲーム盤のサイズと同じ数 になった場合は、直線状に 同じマークが並んだ ことになる

先程は下記の表を元に 2 つのアルゴリズムの処理時間の差を見積りましたが、この表に間違いがあります。なお、下記の表には unmove が入っていないという間違いがありますが、それよりもっと重要な間違いがあります。どこが間違っているかを少し考えてみて下さい。

	これまでのアルゴリズム	上記のアルゴリズム	回数
ゲーム開始時		手順 1	1
`move` メソッド	`is_same`	手順 2、3	40 ~ 54

上記の表が間違っている理由は、最初の高速化の修正で行った 手数が 4 以下の場合 に judge メソッドから is_winner を呼び出す処理を行わない ようにしたことにあります。上記の表 は 手数に関わらず is_winner を呼び出す場合 のものです。

下記は、着手を行った際に呼び出される move メソッドの回数 の表の再掲です。

手数	回数	合計
1	10	10
2	9	19
3	8	27
4	7	34
5	6	40
6	5	45
7	4	49
8	3	52
9	2	54

上記の表から、is_winner が呼び出されない 1 ~ 4 手目で move メソッドが呼び出される 回数は 34 回 であることがわかります。そのため、1 回の ai2s どうしの対戦で is_winner または手順 3 の処理が 実際に呼び出される回数 は 40 ~ 54 から 34 を引いた 6 ~ 20 回 になります。なお、手順 2 の処理は move と unmove メソッドを呼び出した際に 必ず実行される ので 40 ~ 54 回実行されるという点は変わりません。

下記は先ほどの表を修正した表で、unmove メソッドも考慮に入れました。

	これまでのアルゴリズム	上記のアルゴリズム	回数
ゲーム開始時		手順 1	1
`move` メソッド `unmove` メソッド		手順 2	40 ~ 54¹
`is_winner` メソッド	`is_same`	手順 3	6 ~ 20

上記の表から、is_same または手順 3 が実行される回数 を先程と同様の方法で 見積もる ことにします。回数を中間の 12 とし、先程と同様に move メソッドが実行されるたびに 3 回実行されるとすると、その回数は 12 × 3 = 36 回と見積もる ことができます。

先程の 間違った表からの見積もりが 150 回 であったことから、その値は 約 4 倍もの差がある ことがわかります。また、表からわかるように各直線上のマークの数を記録するアルゴリズムでは、元のアルゴリズムと比べて 手順 2 の処理が 150 回ほど余分に行われる ので、その分だけ処理時間がかかる ことになります。

各直線上のマークの数を記録するアルゴリズムによって 処理時間がほとんど変化しない理由 は 手順 2 を行うことで 余分にかかる処理時間 と is_same の代わりに手順 3 を行うことで 短縮される処理時間 が ほぼ同じ だからです。

各直線上のマークの数を記録するアルゴリズムの検証

上記の結果から、各直線上のマークの数を記録 するアルゴリズムは高速化がほとんど行われない 意味のないアルゴリズム だと 思った方がいるかもしれません が、is_same と 手順 2、3 の処理時間に差がある ことを利用するという 考え方そのものは間違っていません。〇× ゲームでは たまたま 4 手目以下の局面では決着がつかない という性質を持つため、このアルゴリズムが 有効に働きませんでした が、そうでないゲーム であればこのアルゴリズムで 大きな高速化を得ることができるはず です。

そのことを 手数に関わらず is_winner を呼び出す場合 の 処理時間を比較 することで確認することにします。具体的には、move メソッドが呼び出された場合に 手数に関わらず is_same または手順 2、3 が実行される ように修正することで、先程勘違いしていた下記の表の処理 が行われた場合の 処理時間を比較 することにします。

	これまでのアルゴリズム	上記のアルゴリズム	回数
ゲーム開始時		手順 1	1
`move` メソッド	`is_same`	手順 2、3	40 ~ 54

各直線上のマークの数を記録するプログラムの修正

先に 修正箇所が少ない、各直線上のマークの数を記録するプリグラム の処理の修正を行うことにします。修正は下記のプログラムのように judge メソッドの修正だけです。

2 行目：手数が 0 の場合のみ Marubatsu.PLAYING を返す ように修正した。なお、この if 文を削除すると、手数が 0 の場合 は last_turn 属性に None が代入されている ため、5 行目の is_winner の呼び出し処理の中で エラーが発生 してしまう点に注意が必要である²。なお、手数が 0 の場合は 直前の着手がない ので、直前の着手が行われたマスを元に計算を行う is_winner を呼び出さないのは正しい処理 である

1  def judge(self):
2      if self.move_count == 0:
3          return Marubatsu.PLAYING
4      # 直前に着手を行ったプレイヤーの勝利の判定
5      if self.is_winner(self.last_turn):
元と同じなので省略
6      
7  Marubatsu.judge = judge

行番号のないプログラム

def judge(self):
    if self.move_count == 0:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    if self.is_winner(self.last_turn):
        return self.last_turn
    # 引き分けの判定
    elif self.is_full():
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING      
    
Marubatsu.judge = judge

修正箇所

def judge(self):
-   if self.move_count < self.BOARD_SIZE * 2 - 1:
+   if self.move_count == 0:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    if self.is_winner(self.last_turn):
元と同じなので省略
    
Marubatsu.judge = judge

上記の修正後に下記のプログラムで judge メソッドが正しいか どうかを判定する test_judge を実行すると、実行結果から 正しいことが確認 できました。

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

次に、下記のベンチマークを実行します。実行結果から 処理時間は約 3 秒、1 秒あたりの回数は 1661.86 回 であることがわかりました。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:03<00:00, 1661.86it/s]
count     win    lose    draw
o        2916    1439     645
x        1489    2903     608
total    4405    4342    1253

ratio     win    lose    draw
o       58.3%   28.8%   12.9%
x       29.8%   58.1%   12.2%
total   44.0%   43.4%   12.5%

元のアルゴリズムのプログラムの修正

次に 元のアルゴリズムで判定を行う ように修正を行います。行う修正は restart、move、unmove、is_winner を 修正前の処理に戻すだけ なのでプログラムは折りたたみました。

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]
    
Marubatsu.restart = restart

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
        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]
            
Marubatsu.move = move

unmoveの修正

def unmove(self):
    if self.move_count > 0:
        self.move_count -= 1
        self.turn, self.last_turn = self.last_turn, self.turn
        if self.move_count == 0:
            self.last_move = (-1, -1)
        self.status = Marubatsu.PLAYING
        x, y = self.records.pop()
        self.remove_mark(x, y)
        self.last_move = self.records[-1]  

Marubatsu.unmove = unmove

is_winnerの修正

def is_winner(self, player):
    x, y = self.last_move
    if self.is_same(player, coord=[0, y], dx=1, dy=0) or \
       self.is_same(player, coord=[x, 0], dx=0, dy=1):
            return True
    # 左上から右下方向の判定
    if x == y and self.is_same(player, coord=[0, 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):
        return True

    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False

Marubatsu.is_winner = is_winner

上記の修正後に下記のプログラムで judge メソッドが正しいか どうかを判定する test_judge を実行すると、実行結果から 正しいことが確認 できました。

test_judge()

実行結果

Start
test winner = playing
oooooooooo
test winner = o
ooooooooo
test winner = x
oooooooo
test winner = draw
o
Finished

次に、下記のベンチマークを実行すると実行結果から 処理時間 は約 3 秒から 約 4 秒に増え、1 秒あたりの回数 は 1661.86 回から 1165.33 に大幅に減る ことがわかりました。このことから、手順 2、3 の処理時間のほうが is_same よりも短い ことが確認でき、各直線上のマークの数を記録 するという 考え方そのものは間違っていない ことがわかりました。

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

実行結果

ai2s VS ai2s
100%|██████████| 5000/5000 [00:04<00:00, 1165.33it/s]
count     win    lose    draw
o        2964    1391     645
x        1422    2938     640
total    4386    4329    1285

ratio     win    lose    draw
o       59.3%   27.8%   12.9%
x       28.4%   58.8%   12.8%
total   43.9%   43.3%   12.8%

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

下記は今回の記事で行った修正の ベンチマークの結果をまとめた表 です。最初の 4 つの列の意味 は以下の通りで、〇が記載されている行 は その修正が行われた ことを表します。

4 以下：4 手目以下の判定の修正
手番：判定を行う必要がない手番の判定の修正
直線：必要のない直線の判定の修正
記録：各直線上のマークの数を記録の修正

4 以下	手番	直線	記録	処理時間（秒）	1 秒あたりの処理回数
				15	323.25
〇				5	876.84
〇	〇			4	1242.03
〇	〇	〇		2	1891.24
〇	〇	〇	〇	2	1992.20
	〇	〇		4	1165.33
	〇	〇	〇	3	1661.86

表から、以下の事がわかります。

他の条件が同じ場合 は、「4 以下」、「手番」、「直線」の 修正を加える ことで 処理時間が短縮 される
「記録」の修正を加える場合は、「4 以下」の修正が 行われている場合 は処理時間が ほとんど変わらない が、行われていない場合は 短縮される
すべての修正を組み合わせる ことで処理速度が 約 6 倍に高速化 される

「4 以下」、「手番」、「一列」の修正によって 処理時間が短縮される理由 は、これらの修正は、それまでに行われていた 無駄な処理をなくすだけ の修正だからです。

一方、「記録」の修正は、それまでとは 異なる視点で効率の良い処理 を行うことで、一部の処理の効率を改善 しますが、一方で 修正前では行われていなかった処理が追加 されるという特徴があります。そのため、処理の効率化による短縮時間 と 追加された処理の時間 が 同じくらいの場合は処理時間がほとんど変わりません。また、追加された処理時間のほうが長い場合 は処理時間が 悪化してしまう ような場合もあります。

高速化を行う際には、最初は無駄な処理を無くすだけの修正を行うことができますが、それだけではすぐに修正できる場所が無くなってしまう ので、異なる視点での修正を行う必要 が生じます。その際には、絶対にうまくいくと思っていた改善の 効果がほとんどなかったり、逆に処理時間が 悪化するようなことが良くあります。

また、修正を 単独で行った際 には 大きな改善が得られる場合でも、複数の修正を同時に適用 する場合は、それぞれの 修正内容の相性 によっては 改善の効果が無い 場合や、逆に 悪化してしまう 場合があります。そのため、最大の高速化 を行いたい場合は、無駄な処理を無くすだけの修正を除いた すべての修正の組み合わせの処理時間を計測 する必要がありますが、組み合わせの数 は修正方法の数を $n$ とすると $\boldsymbol{2^n}$ になるので、修正方法の数が増える と すべての組み合わせ の処理時間を計測することは 現実的には不可能 です。そのため、基本的には 思いついた修正を次々に行っていき、処理時間が悪化した場合は他の修正との相性を考える という方法で修正を行うのが一般的ではないかと思います。

この現象は、病気を治す薬はそれぞれ個別の病気を治す役には立ちますが、異なる薬を同時に服用すると毒になってしまうという、薬の飲み合わせの問題に似ています。

他の例としては、単独で利用する場合は美味しくなるが、混ぜるとまずくなる調味料の例が挙げられるでしょう。

先程の表から今回の記事で行った修正をすべて組み合わせた場合が一番高速なので、marubatsu.py には すべての修正を行ったものを採用 することにします。また、is_same メソッドは必要がなくなったので削除 することにします。

今回の記事のまとめ

今回の記事では Marubatsu クラスの中で 勝敗判定 を行う処理を 高速化する様々な手法 について説明しました。また、修正の組み合わせ によっては 効率が変わらない 場合や、逆に 悪化してしまう ような場合があることを 具体例を挙げて説明 しました。

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

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

次回の記事

ai2s が計算した最善手を着手するための move に対しては unmove で着手の取り消しが行われることはないので、厳密には手順 2 の中で unmove の処理を行う回数は表の数値よりも手数の数だけ減ります。ただし、その数は全体のほんの一部なので検証では考慮に入れないことにします ↩
筆者も最初はこの if 文を削除してエラーを発生させてしまいました ↩