Pythonで〇×ゲームのAIを一から作成する その185 着手の取り消しによる処理の高速化

目次と前回の記事

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

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

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

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

処理の高速化

将棋や囲碁などの 多くのゲームのゲーム木 は、ノードの数が多すぎて すべてのノードの計算を行うことができません。そのため深さの上限までの探索を行う 深さ制限探索 を行いますが、その際に 深さの上限が大きい程 計算される評価値の 精度が高まる ため、ゲーム木の探索の 処理の高速化が非常に重要 になります。

これまでの記事では、ミニマックス法 による ゲーム木の探索の高速化 を行うための αβ 法などの 様々なアルゴリズム を紹介しました。αβ 法は以前の記事で説明したように、ミニマックス法と比較して 最大で計算するノードの数が平方根になる ような、大きな高速化が得られます。例えば、ミニマックス法で 100 万（$= 10^6$）個のノードを計算する処理は αβ 法では最小で $\sqrt{10^6}=10^3= 1000$ 個のノードの計算処理で行うことができるので、理想的な場合は処理速度が 1000 分の 1 になります。このように、効率の良い探索アルゴリズム を考えることで、ゲーム木のノードの数が増えた場合に 大幅な処理速度の高速化 が得られます。

別の方法として、探索アルゴリズムを実装した プログラムの処理の無駄をなくす など方法ので高速化するという手法があります。この方法では一般的にノードの数とは関係なく、処理時間が一定の割合で減る という形の高速化が行われるので、ノードの数が多い場合に αβ 法ほどの高速化は得られませんが、処理が高速に行われることに変わりはないので重要です。

処理の高速化をいつ行うべきか

一般的には、高速化 を行うことで プログラムが複雑でわかりづらく になり、その結果 バグが発生しやすく なります。プログラムは 正しく動作することが重要 なので、最初は 処理の高速化を考慮せずに わかりやすくプログラムを記述する ことが重要だと思います。

人間が遅いと感じない アプリケーションに対して 高速化を無理に行う必要はありません。そのような場合はわかりやすいプログラムを記述することをお勧めします。

本記事 でも 〇× ゲームの処理を行う Marubatsu クラスや、ミニマックス法などのゲーム木の探索を行うプログラムでは、わかりやすさを重視 して あえて効率があまり良くない プログラムを記述してきました。

ここまでの記事でゲーム木の探索のアルゴリズムについての解説が終わって ひと段落がつきました ので、しばらくの間はプログラムの無駄をなくすなどの様々な方法で 処理の高速化を行う方法 について紹介したいと思います。

ベンチマーク

コンピューターのソフトウェアなどの 性能を測る指標 のことを ベンチマーク（benchmark）と呼びます。特定の計算に対する 処理速度 という 性能を比較 するベンチマークとしては、その処理を行うプログラムの 処理速度 を用いるのが一般的でしょう。また、ベンチマークを測定するプログラム のことを ベンチマークと呼ぶ 場合もあります。

本記事ではベンチマークとして、ゲーム開始時の局面 に対して ai_abs_dls によって αβ 法で計算を行った際の処理時間 を用いることにします。具体的には、最初に下記のプログラムを実行して ai_abs_dls の実引数に記述するデータを計算します。

from ai import ai_abs_dls, ai14s
from marubatsu import Marubatsu

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

その後、下記のプログラムを実行して %%timeit で処理時間の平均を計測 します。なお、深さの上限 を 〇× ゲームのゲーム木の深さと同じ 9 に設定 することで、実質的に深さの上限を設定しない αβ 法 の計算を行っています。また、静的評価関数として ai14s を利用していますが、静的評価関数はゲームの決着がついた局面に対して評価値を計算するので 他の決着がついた局面の形勢判断を正しく行える静的評価関数 を利用しても 結果は変わりません。

実行結果から、高速化を行う前 の現時点での ベンチマークの処理時間の平均 は、筆者のパソコンでは 68.1 ms であることがわかりました。

%%timeit

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

実行結果

68.1 ms ± 585 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

参考までに Wikipedia のベンチマークの記事のリンクを下記に示します。

着手の取り消しによる処理の高速化

ゲーム木の探索を行う処理では、下記のようなプログラムで 子ノードの評価値を計算する際 に 親ノードの局面 を表す mborig を deepcopy でコピー し、そのデータに対して着手を行った mb を子ノードの評価値を計算する関数の 実引数に記述 して呼び出します。

    for x, y in legal_moves:
        mb = deepcopy(mborig)
        mb.move(x, y)
        abscore = ab_search(mb, depth + 1, tt, alpha, beta)

このような 親ノードのコピー処理が必要となる理由 は、次の子ノード の評価値を計算する際に、親ノードの局面のデータから 子ノードの局面を 計算する必要がある ためです。上記の deepcopy による深いコピー を行うことで 親ノードのデータを残す という処理は 直観的にわかりやすく、記述も 1 行で済む ため本記事では採用してきましたが、deepcopy によるデータのコピーの処理には データの量に比例した時間がかかる という 欠点 があります。

別の方法 として、直前に行った着手を取り消す ことで 子ノードの局面を親ノードの局面に戻す という方法が考えられます。着手の取り消しを行う処理時間のほうが、親ノードの局面をコピーする処理時間よりも 短ければ 処理の 高速化を行うことができます。

なお、この後の実装を見ればわかると思いますが、着手の取り消し処理 はデータのコピーと比較すると 処理速度は高速化 しますが、その反面 プログラムが複雑になります。

着手の取り消しの処理の効率

直前に行った着手を取り消す という処理の 処理時間 は、ゲームの種類 によって 大きく異なります。〇× ゲーム は 着手を行うことで ゲーム盤の 9 つのマスの中の 1 つのマスだけが変化 します。そのため、ゲーム盤のデータに関して 言えば、着手したマスのマークを取り除くこと で 簡単に着手前の局面に戻す ことができます。将棋やチェス も着手を行うことで 1 つの駒の移動と、移動先に相手の駒があった場合はその駒を取るという変化しか起きない¹ので、着手の取り消しの処理は簡単に行えます。

一方、着手によって 局面の状況が大きく変化する ようなゲームでは、直前の局面をコピーする以外の方法での 着手の取り消しが容易ではない 場合があります。オセロ は着手を行う事で 多数の駒が裏返る ので、直前に行った 着手を取り消す処理 は それほど簡単ではありません。囲碁 は基本的には 〇× ゲームと同様に着手によって 1 つのマスだけが変化しますが、相手の石を取る 着手が行われた場合は 多くのマスの内容が変化する ので直前に行った 着手を取り消す処理 は 簡単ではありません。

上記で説明したように、〇× ゲーム の場合は 直前の処理を取り消す処理 を 簡単に行えそう なので、実際に実装して処理速度を比較 することにします。具体的には、〇× ゲームで 直前の着手を取り消す処理 を行う unmove² という メソッド を Marubatsu クラスに追加 することにします。どのような処理を行えば良いかについて少し考えてみて下さい。

Marubatsu クラスの属性の意味とバグの修正

ほとんどの方は忘れていると思いますので、Marubastu クラスのインスタンスの 属性とその意味 を下記の表にまとめます。

属性	意味
move_count	ゲーム開始時の局面からの手数
turn	現在の局面の手番
last_turn	直前の局面の手番。ゲーム開始時の値は None
status	現在の局面の状況
board	ゲーム盤を表す 2 次元の list
last_move	直前に行われた着手の座標 ゲーム開始時の局面の場合は直前の着手はないので (-1, -1)3とする
records	ゲーム開始時から行われた着手を表す list i 番の要素に i 手目の着手が記録される 0 手目の着手は存在しないので 0 番の要素はゲーム開始時の局面の last_move の値である (-1, -1) とする

show_progress の修正

上記の表をまとめる際に records に対して行われる処理を確認 したところ、2 つのバグがある ことが判明したのでそれらを修正することにします。

1 つ目のバグは ai.py に定義した、指定した条件の試合経過を表示する処理を行う show_progress が間違っている というものです。具体的には、以前の記事で上記の records 属性の 0 番の要素に self.last_turn を入れるように修正 した際に、show_progress の records 属性を処理する部分を修正し忘れていました。そのため、以前の記事で行った下記のプログラムを実行すると、実行結果のようなエラーが発生します。

from ai import show_progress, ai2, ai11s

show_progress(ai=[ai2, ai11s], winner=Marubatsu.CIRCLE)

実行結果

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[3], line 3
      1 from ai import show_progress, ai2, ai11s
----> 3 show_progress(ai=[ai2, ai11s], winner=Marubatsu.CIRCLE)

File c:\Users\ys\ai\marubatsu\185\ai.py:450, in show_progress(ai, winner, params)
    448 records = mb.records
    449 mb.restart()
--> 450 for x, y in records:
    451     mb.move(x, y)
    452     print(mb)

TypeError: cannot unpack non-iterable NoneType object

上記のエラーメッセージからこのエラーは for x, y in records の処理を行う際に、None を x と y に展開（unpack）しようとしたことが原因であることがわかります。また、実際に records 属性の 0 番の要素 にはこの後で説明しますが None が代入 されています。

show_progress のバグは、今回の記事の着手の取り消しとは関係がありませんが、そのまま放置するのは良くないので修正しました。

show_progress の for x, y in records の処理は、records 属性に記録された着手を順番に行う という処理ですが、行われた着手は 1 番の要素から順に記録 されるので、下記のプログラムのように修正する必要があります。

• 7 行目：record 属性の 1 番の要素から順番に繰り返し処理を行うように修正する

 1  def show_progress(ai, winner, params=[{}, {}]):
 2      mb = Marubatsu()
 3      while True:
 4          if mb.play(ai=ai, verbose=False, params=params) == winner:
 5              records = mb.records
 6              mb.restart()
 7              for x, y in records[1:]:
 8                  mb.move(x, y)
 9                  print(mb)
10              break

行番号のないプログラム

def show_progress(ai, winner, params=[{}, {}]):
    mb = Marubatsu()
    while True:
        if mb.play(ai=ai, verbose=False, params=params) == winner:
            records = mb.records
            mb.restart()
            for x, y in records[1:]:
                mb.move(x, y)
                print(mb)
            break

修正箇所

def show_progress(ai, winner, params=[{}, {}]):
    mb = Marubatsu()
    while True:
        if mb.play(ai=ai, verbose=False, params=params) == winner:
            records = mb.records
            mb.restart()
-           for x, y in records:
+           for x, y in records[1:]:
                mb.move(x, y)
                print(mb)
            break

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

show_progress(ai=[ai2, ai11s], winner=Marubatsu.CIRCLE)

実行結果

Turn x
..O
...
...

Turn o
..o
.X.
...

Turn x
..o
.x.
O..

Turn o
..o
.x.
o.X

Turn x
O.o
.x.
o.x

Turn o
oXo
.x.
o.x

winner o
oxo
Ox.
o.x

show_progress のバグは、records 属性の 0 番の要素を修正した第 80 回の記事から生じていますが、プログラムの修正が多すぎて大変すぎる点と、その記事から今回の記事までで show_progress は一度も使われていないことから、第 80 回の記事からさかのぼって show_progress を修正しないことにします。

restart メソッドの修正

2 つ目のバグは、下記のプログラムのように records 属性の値を表示した所、0 番の要素 に (-1, -1) ではなく None が間違って代入されている というものです。

mb = Marubatsu()
print(mb.records)

実行結果

[None]

その理由について調べたところ、以前の記事で records 属性の 0 番の要素に 誤って last_move の代わりに last_turn を代入するというミス を犯していたことがわかりましたので修正することにします。なお、他のプログラムを一通り確認した所、records 属性の 0 番の要素を利用する処理が存在しない ため、上記のバグが あることが これまで明るみに出ませんでした。

records 属性の 0 番の要素 は restart メソッドで代入されるので、restart メソッドを下記のプログラムのように修正します。

• 8 行目：records 属性に [self.last_move] を代入するように修正する

 1  def restart(self):
 2      self.initialize_board()
 3      self.turn = Marubatsu.CIRCLE     
 4      self.move_count = 0
 5      self.status = Marubatsu.PLAYING
 6      self.last_move = -1, -1          
 7      self.last_turn = None
 8      self.records = [self.last_move]
 9      
10  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]
    
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_turn]
+   self.records = [self.last_move]
    
Marubatsu.restart = restart

上記の修正後に下記のプログラムを実行すると、実行結果のように records 属性の 0 番の要素に (-1, -1) が正しく代入 されるようになったことが確認できます。

mb = Marubatsu()
print(mb.records)

実行結果

[(-1, -1)]

こちらのバグは、放置するとこの後で定義する unmove の処理が行われた際に last_move 属性の値が None になる可能性が生じます。その場合は print によって __str__ メソッドが実行された際に行われる、直前の着手を大文字で表示するため の下記の処理で None を展開 しようとした結果 エラーが発生する ので修正する必要があります。

    lastx, lasty = self.last_move

着手の取り消しの際に行う処理

下記は、先程のMarubastu クラスのインスタンスの 属性とその意味 の再掲です。

属性	意味
move_count	ゲーム開始時の局面からの手数
turn	現在の局面の手番
last_turn	直前の局面の手番。ゲーム開始時の値は None
status	現在の局面の状況
board	ゲーム盤を表す 2 次元の list
last_move	直前に行われた着手の座標 ゲーム開始時の局面の場合は直前の着手はないので (-1, -1)とする
records	ゲーム開始時から行われた着手を表す list i 番の要素に i 手目の着手が記録される 0 手目の着手は存在しないので 0 番の要素はゲーム開始時の局面の last_move の値である (-1, -1) とする

上記の表から、着手を取り消した場合 に上記の それぞれの属性に対して行う処理 は以下の表のようになります。ただし、ゲーム開始時の局面 の場合は直前の局面は存在しないので unmove は何も行わないことにします。

属性	行う処理
move_count	1 を引く
turn	直前の局面の手番にする。具体的には last_turn を代入する
last_turn	直前の局面の前の局面は現在の局面の手番なので turn を代入する。ただし、直前の局面がゲーム開始時の局面の場合は None を代入する
status	直前の局面は決着がついていない局面なので、Marubatsu.PLAYING を代入すれば良い
board	直前の局面で行われた着手は records の最後の要素に代入されているので、そのマスを空にする
records	最後の要素を削除する
last_move	上記で最後の要素を削除した records の最後の要素が直前の局面の前の着手なのでそれを代入する

着手の取り消しを行う処理の実装

必要な処理がわかったので unmove メソッドを実装することにします。

remove_mark メソッドの定義

上記の処理の中で必要となる マスを空にする処理を行うメソッドがない ので、指定したマスのマークを空にする remove_mark というメソッドを定義することにします。なお、指定したマスにマークを配置する place_mark メソッドは 空のマスにマークを配置 する処理を行うメソッドなので、マークが配置されたマスを空にする 処理を 行うことはできません。

下記は remove_mark メソッドの定義です。行う処理は place_mark メソッドと似ているので place_mark からの修正 を説明します。

• 1 行目：メソッドの名前を remove_mark とする。また、配置するマークは存在しないので仮引数 mark を削除する
• 3、4 行目：マスが空でない場合にそのマスを空にするように修正する
• 7 行目：マスが空でない場合のメッセージを修正する

 1  def remove_mark(self, x, y):
 2      if 0 <= x < self.BOARD_SIZE and 0 <= y < self.BOARD_SIZE:
 3          if self.board[x][y] != Marubatsu.EMPTY:
 4              self.board[x][y] = Marubatsu.EMPTY
 5              return True
 6          else:
 7              print("(", x, ",", y, ") のマスにはマークがありません")
 8              return False
 9      else:
10          print("(", x, ",", y, ") はゲーム盤の範囲外の座標です")
11          return False   
12      
13  Marubatsu.remove_mark = remove_mark

行番号のないプログラム

def remove_mark(self, x, y):
    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   
    
Marubatsu.remove_mark = remove_mark

修正箇所

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

上記の定義後に下記のプログラムを実行すると、実行結果から (1, 1) に配置されたマークが削除 されたことが確認できます。なお、remove_mark は マークを削除する処理しか行わない ので、手番は × のまま変化しません。

mb = Marubatsu()
mb.move(1, 1)
print(mb)
mb.remove_mark(1, 1)
print(mb)

実行結果

Turn x
...
.O.
...

Turn x
...
...
...

pop メソッドの説明

先程の表から、board と records に対して下記の処理を行う必要があります。この処理では records から最後の要素を取り出し、その後で records の 最後の要素を削除 する処理が必要になりますが、その処理は list の pop メソッドを利用することで 1 行で記述 できます。

属性	行う処理
board	直前の局面で行われた着手は、records の最後の要素に代入されているので、それのマスを空にする
records	最後の要素を削除する

pop メソッドについては以前の記事で説明しましたが、忘れた方が多いと思いますので改めて説明します。また、ノートに以前の記事で説明しなかった補足説明も行います。

list の pop メソッドは、下記のプログラムの実行結果のように、list の最後の要素を返り値として返し、最後の要素を削除 するという処理を行います。

a = [1, 2, 3]
b = a.pop()
print(a)
print(b)

実行結果

[1, 2]
3

このノートと次のノートは以前の記事で説明しなかった内容です。pop メソッドの実引数に数値を記述することで、下記のプログラムのように記述したインデックスの要素を返り値として返し、その要素を削除するという処理が行われます。

a = [1, 2, 3]
b = a.pop(1)
print(a)
print(b)

実行結果

[1, 3]
2

pop メソッドは dict などの ミュータブルなシーケンス型 に対して利用できるメソッドです。下記は dict の "y" というキーの値を返して削除する処理を行うプログラムです。なお、dict の場合は pop メソッドの実引数を省略することはできません。

a = {
    "x": 1,
    "y": 2,
    "z": 3,
}
b = a.pop("z")
print(a)
print(b)

実行結果

{'x': 1, 'y': 2}
3

pop メソッドの詳細については下記のリンク先の表を参照して下さい。

unmove メソッドの定義

下記は、先程の表で説明した処理を行う unmove メソッドの定義です。

• 2 行目：ゲーム開始時の局面の場合は何も行わないようにする
• 3 ~ 10 行目：先程の表の処理を順番に行う

 1  def unmove(self):
 2      if self.move_count > 0:
 3          self.move_count -= 1
 4          self.turn, self.last_turn = self.last_turn, self.turn
 5          if self.move_count == 0:
 6              self.last_move = (-1, -1)
 7          self.status = Marubatsu.PLAYING
 8          x, y = self.records.pop()
 9          self.remove_mark(x, y)
10          self.last_move = self.records[-1]
11              
12  Marubatsu.unmove = 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

上記の定義後に、下記のプログラムで ゲーム開始時の局面 から (0, 0)、(1, 0)、(2, 0)、(0, 1)、(1, 1) の 5 回の着手 を行った局面から 5 回 unmove を行った局面をそれぞれ表示すると、実行結果のように unmove が正しく行われている ことがわかります。また、それぞれの局面で 直前の着手が行われたマスが正しく大文字で表示 されていることが確認できます。

mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
mb.move(2, 0)
mb.move(0, 1)
mb.move(1, 1)
for _ in range(5):
    mb.unmove()
    print(mb)

実行結果

Turn o
oxo
X..
...

Turn x
oxO
...
...

Turn o
oX.
...
...

Turn x
O..
...
...

Turn o
...
...
...

ai_abs_dls の修正

下記のプログラムは unmove を利用 するように ai_abs_dls を修正 したプログラムです。なお、親ノードの局面のデータを取っておく必要がなくなったので、仮引数 mborig の名前を mb という名前に変更してもかまいませんが、本記事では変更しないことにします。

• 11 行目の下にあった mborig を deepcopy でコピーする処理を削除する
• 12、13 行目：mborig に対して着手を行い、ab_search で mborig の評価値を計算するように修正する。なお、呼び出した ab_search の中でも mborig に対して直接着手が行われる が、必ずその着手の取り消しがセットで行われる ので、ab_search の 処理が終了した時点での mborig の局面 は、呼び出す前の局面と一致 する
• 14 行目：unmove メソッドを呼び出して、12 行目で行った着手を unmove で取り消して親ノードの局面に戻す
• 16 ~ 20 行目：min ノードに対して上記と同じ修正を行う

 1  from ai import ai_by_mmscore, dprint
 2  from time import perf_counter
 3  
 4  @ai_by_mmscore
 5  def ai_abs_dls(mb, debug=False, timelimit_pc=None, maxdepth=1, eval_func=None,
 6                 eval_params={}, use_tt=False, tt=None, tt_for_mo=None):               
 7      count = 0
 8      def ab_search(mborig, depth, tt, alpha=float("-inf"), beta=float("inf")):
元と同じなので省略
 9          if mborig.turn == Marubatsu.CIRCLE:
10              score = float("-inf")
11              for x, y in legal_moves:
12                  mborig.move(x, y)
13                  abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
14                  mborig.unmove()
元と同じなので省略
15          else:
16              score = float("inf")
17              for x, y in legal_moves:
18                  mborig.move(x, y)
19                  abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
20                  mborig.unmove()
元と同じなので省略

行番号のないプログラム

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 x, y in legal_moves:
                mborig.move(x, y)
                abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
                mborig.unmove()
                if abscore > score:
                    bestmove = (x, y)
                score = max(score, abscore)
                if score >= beta:
                    break
                alpha = max(alpha, score)
        else:
            score = float("inf")
            for x, y in legal_moves:
                mborig.move(x, y)
                abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
                mborig.unmove()
                if abscore < score:
                    bestmove = (x, y)
                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

修正箇所

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")):
元と同じなので省略
        if mborig.turn == Marubatsu.CIRCLE:
            score = float("-inf")
            for x, y in legal_moves:
-               mb = deepcopy(mborig)
-               mb.move(x, y)
+               mborig.move(x, y)
-               abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+               abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
                mborig.unmove()
元と同じなので省略
        else:
            score = float("inf")
            for x, y in legal_moves:
-               mb = deepcopy(mborig)
-               mb.move(x, y)
+               mborig.move(x, y)
-               abscore = ab_search(mb, depth + 1, tt, alpha, beta)
+               abscore = ab_search(mborig, depth + 1, tt, alpha, beta)
                mborig.unmove()
元と同じなので省略

上記の修正後に下記のプログラムで ベンチマークのプログラムの処理時間を計測 すると、実行結果のように 処理時間が 68.1 ms から 36.8 ms のように 大幅に短くなった ことが確認できます。このことから、〇× ゲーム では局面のデータのコピーの処理よりも、着手の取り消しの処理の方 が 短い時間で処理を行うことができる ことが確認できました。

%%timeit

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

実行結果

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

なお、先程の修正によって バグが発生している可能性 があります。上記の実引数に対して ai_abs_dls が行う処理は αβ 法で評価値を計算 するので 強解決の AI になるはず なので、そのことを下記のプログラムで確認した所、強解決の AI であることが確認 できました。

from util import Check_solved

params = {
    "eval_func": ai14s,
    "eval_params": eval_params,
    "use_tt": True,
    "maxdepth": 9
}

Check_solved.is_strongly_solved(ai_abs_dls, params=params)

実行結果

100%|██████████| 431/431 [00:01<00:00, 308.63it/s]
431/431 100.00%

ベンチマークのまとめ

今回の記事で行った ai_abs_dls によるベンチマークの結果を下記の表にまとめます。

	処理時間の平均
修正前	68.1 ms
着手の取り消しの適用	36.8 ms

今回の記事のまとめ

今回の記事では 着手の取り消しによる処理の高速化 の手法を紹介し、ai_abs_dls に対してその手法を適用して 実際に高速化が行われる ことを示しました。〇× ゲーム、チェス、将棋 のような 着手の取り消しが容易なゲーム では、この手法は有効なので 実際に良く使われている のではないかと思います。一方、着手の取り消しが容易ではないゲームの場合は、局面のコピーが使われる場合があると思います。

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

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

次回の記事

1. チェスの場合はキャスリングという特殊な着手の例外がありますが、その場合も 2 つの駒を移動するだけなので着手の取り消しは容易です ↩

2. コンピューターでは操作の取り消しを undo と呼ぶので、それに倣って着手（move）の取り消しを行うメソッドを unmove と命名しました。一般的に着手の取り消しを英語で unmove と呼ぶかどうかについてはよくわかりません ↩

3. (-1, -1) とした理由については、以前の記事を参照して下さい ↩