Pythonで〇×ゲームのAIを一から作成する　その233　プレイアウトの処理の高速化

Posted at 2026-06-21

目次と前回の記事

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

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

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

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

現状の `playout` の処理の問題点

前回の記事では下記の原始モンテカルロ法のアルゴリズムで必要となるプレイアウトの実装を行いました。

現在の局面から合法手を着手したすべての局面に対して下記の計算を行う
1. ゲームの決着がつくまで乱数を利用してランダムな着手を行い続け、その結果を記録する。この作業をプレイアウトと呼ぶ
2. あらかじめ決めておいた回数または、あらかじめ決めておいた時間になるまでプレイアウトを繰り返し、その勝率を計算する
最も高い勝率が計算された局面になる合法手を最善手とする

前回の記事で実際に確認したように、原始モンテカルロ法は大数の法則から、プレイアウトを行った回数が多いほうが精度が高まります。そのため、プレイアウトの処理速度が高速であることが非常に重要となります。以前の記事で複数回の記事にわたって Marubatsu クラスの様々な処理の高速化を行った理由の一つはこのためです。他の理由としては今後の記事で紹介する他の様々な機械学習の手法でも、処理の高速化が非常に重要となるためです。

現状のプレイアウトの処理速度の計測

前回の記事で実装した複数回のプレイアウトの結果の集計を行う playout は制限時間を設定することができるので、現状の playout が 1 秒間で何回プレイアウトを行うことができるかを計測してみることにします。また、その際にこれまでに作成した様々なゲーム盤を表すクラスごとに計測を行うことにします。

参考までにこれまでに作成したゲーム盤を表すクラスを下記の表にまとめます。クラス名のリンクはそのクラスを定義した記事へのリンクです。

ゲーム盤のクラス	ゲーム盤のデータ型	マスのデータ型
ListBoard	2 次元の list	str
List1dBoard	1 次元の list	str
ArrayBoard	array	str
NpBoard	2 次元の ndarray	str
NpIntBoard	2 次元の ndarray	int
NpBoolBoard	2 次元の ndarray	bool
BitBoard	2 つの int 型のビットボードを要素とする list	1 ビットのデータ
BitBoard3x3	3 x 3 のサイズのゲーム盤に特化した BitBoard	1 ビットのデータ
TwoBitBoard3x3	〇と × のビットボードを一つにまとめた int	1 ビットのデータ

下記はその処理を行うプログラムです。

4 ~ 7 行目：それぞれのゲーム盤を表すクラスに対して count_linemark が True と False の場合の繰り返し処理を行う。なお、BitBoard3x3 と TwoBitBoard3x3 クラスはマークの数を数える処理を行わないのでキーワード引数 count_linemark を記述しても行う処理は変わらない。そこで、この 2 つのクラスは count_linemark が False の場合のみ処理を行うようにした
8 行目：利用するゲーム盤のクラスの名前と count_linemark の値を表示する
9 ~ 10 行目：boardclass に代入されたゲーム盤を表すクラスと count_linemark を実引数に記述して Marubatsu クラスのインスタンスを作成し、制限時間を 1 秒に設定して playout を呼び出す。なおプレイアウトの回数を表す pnum には 1 秒間で絶対に処理が終わらない 1 億回を設定した
11 行目：playout の返り値の中から実際にプレイアウトが行われた回数を表示する

 1  from marubatsu import Marubatsu, ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3
 2  from util import playout
 3  
 4  for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
 5      for count_linemark in [False, True]:
 6          if boardclass in [BitBoard3x3, TwoBitBoard3x3] and count_linemark == True:
 7              continue
 8          print(f"boardclass = {boardclass.__name__} count_linemark = {count_linemark}")
 9          mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
10          retval = playout(mb, pnum=100000000, timelimit=1)
11          print(f"playout count = {retval['count']}")

行番号のないプログラム

from marubatsu import Marubatsu, ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3
from util import playout

for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
    for count_linemark in [False, True]:
        if boardclass in [BitBoard3x3, TwoBitBoard3x3] and count_linemark == True:
            continue
        print(f"boardclass = {boardclass.__name__} count_linemark = {count_linemark}")
        mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
        retval = playout(mb, pnum=100000000, timelimit=1)
        print(f"playout count = {retval['count']}")

実行結果

boardclass = ListBoard count_linemark = False
playout count = 16625
boardclass = ListBoard count_linemark = True
playout count = 13843
boardclass = List1dBoard count_linemark = False
playout count = 22207
boardclass = List1dBoard count_linemark = True
playout count = 15236
boardclass = ArrayBoard count_linemark = False
playout count = 21743
boardclass = ArrayBoard count_linemark = True
playout count = 15985
boardclass = NpBoard count_linemark = False
playout count = 10221
boardclass = NpBoard count_linemark = True
playout count = 10634
boardclass = NpIntBoard count_linemark = False
playout count = 12227
boardclass = NpIntBoard count_linemark = True
playout count = 12647
boardclass = NpBoolBoard count_linemark = False
playout count = 12390
boardclass = NpBoolBoard count_linemark = True
playout count = 10252
boardclass = BitBoard count_linemark = False
playout count = 13613
boardclass = BitBoard count_linemark = True
playout count = 10664
boardclass = BitBoard3x3 count_linemark = False
playout count = 24684
boardclass = TwoBitBoard3x3 count_linemark = False
playout count = 23125

下記は上記の実行結果をまとめた表です。表から BitBoard3x3 がプレイアウトの処理速度が最も高速であることが確認できました。また、多くの場合で count_linemark が True の場合のほうが処理速度が遅くなることが確認できました。

ゲーム盤のクラス	`count_linemark`	プレイアウトの回数
ListBoard	`False`	16625
ListBoard	`True`	13843
List1dBoard	`False`	22207
List1dBoard	`True`	15236
ArrayBoard	`False`	21743
ArrayBoard	`True`	15985
NpBoard	`False`	10221
NpBoard	`True`	10634
NpIntBoard	`False`	12227
NpIntBoard	`True`	12647
NpBoolBoard	`False`	12390
NpBoolBoard	`True`	10252
BitBoard	`False`	13613
BitBoard	`True`	10664
BitBoard3x3		24684
TwoBitBoard3x3		23125

プレイアウトで行う処理では count_markpats や calc_same_hashables メソッドは呼び出されないので、それらのメソッドを利用する AI の関数の処理速度を比較すると上記の表とは異なる結果になります。それらを利用した場合の処理速度の検証については過去の記事を参照して下さい。

1 万回のプレイアウトの結果の確認

この後で playout を改良しますが、その際に改良した playout の処理が正しいことを確認できるように、乱数の種を 0 としてゲーム開始時の局面での 1 万回のプレイアウトを行い、プレイアウトで最初に (0, 0) を着手した場合の結果を表示することにします。乱数の種を特定の値に設定することで同じパターンの乱数が発生します。従って、この後で改良した playout が正しく実装されていれば、下記と同じ処理を行った場合に同じ結果になるので、そのことを確認することで正しい処理が行われていることを確認することができます。

なお、結果をすべて表示して確認してもかまいませんが、確認作業が大変なので (0, 0) に着手した場合の結果だけを確認することにしました。気になる人は playout の返り値のすべてが同じになるかどうかを確認してみて下さい。

3 行目：random.seed(0) で乱数の種を 0 に設定する
5 ~ 8 行目：プレイアウトを 1 万回行い、最初に (0, 0) を着手した場合の結果を表示する

1  import random
2  
3  random.seed(0)
4  mb = Marubatsu()
5  retval = playout(mb, 10000)
6  move = mb.board.xy_to_move(0, 0)
7  data = retval["result"][move]
8  print(f"(0, 0) o {data[mb.CIRCLE]} x {data[mb.CROSS]} draw {data[mb.DRAW]}")

行番号のないプログラム

import random

random.seed(0)
mb = Marubatsu()
retval = playout(mb, 10000)
move = mb.board.xy_to_move(0, 0)
data = retval["result"][move]
print(f"(0, 0) o {data[mb.CIRCLE]} x {data[mb.CROSS]} draw {data[mb.DRAW]}")

実行結果

(0, 0) o 710 x 298 draw 156

`playout` のボトルネック

playout の処理には以前の記事で説明した、処理の効率を悪化する原因となるボトルネックがあります。ボトルネックが何であるかについて少し考えてみて下さい。

playout のボトルネックは以前の記事でボトルネックという用語を説明した場合の例と同様で、プレイアウトのたびに deepcopy で Marubatsu クラスのインスタンスの深いコピーを行っているという点です。

下記は playout で 100 回のプレイアウトを行った場合の処理時間と、100 回の Marubatsu クラスのインスタンスの深いコピーを行う場合の処理時間を計測するプログラムです。なお、実引数を記述せずに Marubatsu クラスのインスタンスを作成したので利用するゲーム盤を表すクラスは BitBoard3x3 となります。

from copy import deepcopy

mb = Marubatsu()
%timeit playout(mb, 100)

実行結果

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

%%timeit
for _ in range(100):
    deepcopy(mb)

実行結果

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

実行結果から playout の 3.85 ms の約半分の 2.12 ms が deepcopy の処理時間であることが確認できました。deepcopy の処理を別の処理に置き換えることで高速化することができれば playout の処理速度を約 2 倍に高速化することができます。その高速化の方法について少し考えてみて下さい。

`playout` での deepcopy の代替処理

最初に、以前の記事で行った deepcopy の代替処理による ai_abs_dls という AI の関数の処理の高速化についておさらいし、playout の場合は同様の方法をとることができないことを説明します。

`ai_abs_dls` の処理の高速化の手法のおさらい

修正前の ai_abs_dls が deepcopy で深いコピーを行っていた理由は以下の通りです。

ai_abs_dls では現在の局面に対してそれぞれの合法手を着手した局面の評価値を計算する必要がある
合法手を着手した局面を計算する際は、毎回現在の局面に対して合法手を着手する必要があるが、現在の局面を表すデータに対して直接合法手を着手してしまうと局面が変わってしまうという問題がある
現在の局面を表す Marubatsu クラスのインスタンスに対して deepcopy で深いコピーを行い、コピーした局面に対して合法手を着手することでその問題を解決する

以前の記事では着手の取り消しを行う unmove というメソッドを実装し、深いコピーを行う代わりに合法手を着手して評価値を計算した後で unmove メソッドを一回だけ呼び出して現在の局面に戻すという対処を行いました。

一方、プレイアウトではゲームの決着がつくまで着手を行い続けるため、unmove を利用して元の局面まで戻すためにはゲームの決着がつくまでに行った着手の回数だけ unmove メソッドを呼び出す必要があります。そのため残念ながらプレイアウトの場合は unmove で元の局面に戻すという方法は効率が悪く、有効な方法でありません。そのため、別の deepcopy の代替方法を考える必要があります。

`playout` で必要となる処理とその実現方法

playout で必要となる処理は、プレイアウトを行った後の mb をプレイアウトを行う前の局面に戻すという処理です。そのような処理は、プレイアウトを行った後の mb の属性の値をプレイアウトを行う前の値に戻すことで実現することができます。具体的にはプレイアウトによって値が変化する mb の属性に対して下記の処理を行います。

プレイアウトを行う前に、mb の属性の値を別の変数にコピーして記録しておく
プレイアウトを行った後で、mb の属性の値を記録しておいた変数をコピーして復元する

deepcopy は mb のすべての属性をコピーして復元しますが、上記の処理ではプレイアウトで変化する属性だけをコピーして復元する点で効率が良くなります。

プレイアウトによって変化する `mb` の属性の検証

上記の処理を行うために、プレイアウトによって変化するmb の属性を検証することにします。下記は前回の記事で定義した playout の中のプレイアウトを繰り返し行う処理の中でmb に関する処理だけを抜粋したプログラムです。

def playout(mborig, pnum, timelimit=None):
略
    for _ in range(pnum):
略
        mb = deepcopy(mborig)
略
        while mb.status == mb.PLAYING:
            move = random.choice(mb.calc_legal_moves())
略
            mb.move(move)
略

上記から playout の中のプレイアウトを行う処理では mb の calc_legal_moves と move メソッドだけが呼び出されていることがわかります。

calc_legal_moves メソッドは合法手の一覧を計算するメソッドなので局面の状況は変化しません。そのためこのメソッドを呼び出しても mb の属性の値は変化しません。気になる方は calc_legal_moves メソッドのプログラムを見て確認してみて下さい。

下記は Marubatsu クラスの move メソッドの定義です。

 1  def move(self, move, placedFalse):
 2      if not placed:
 3          self.board.setmark_by_move(move, self.turn)
 4  
 5      self.last_turn = self.turn
 6      self.turn = self.CROSS if self.turn == self.CIRCLE else self.CIRCLE  
 7      self.move_count += 1
 8      self.last_move = move
 9      self.status = self.board.judge(self.last_turn, self.last_move, self.move_count)
10      if len(self.records) <= self.move_count:            
11          self.records.append(self.last_move)
12      else:
13          self.records[self.move_count] = self.last_move
14          self.records = self.records[0:self.move_count + 1]

上記から下記の属性が変化することがわかります。

3 行目：self.board.setmark_by_move によってゲーム盤への合法手の着手を行い、board 属性が変化する
5 行目：last_turn 属性が変化する
6 行目：turn 属性が変化する
7 行目：move_count 属性が変化する
8 行目：last_move 属性が変化する
9 行目：self.board.judge を呼び出すことで勝敗判定を行い、status 属性が変化する
10 ~ 14 行目：records 属性が変化する

9 行目で呼び出される judge メソッドは勝敗判定を計算して返り値として返す処理を行うメソッドで、その処理を行う際に mb の属性の値は変化しません。気になる方は judge メソッドのプログラムを見て確認してみて下さい。

10 ~ 14 行目で変化する records 属性は決着がつくまでに行った棋譜（着手の一覧）を記録（record）する属性です。棋譜の情報は unmove メソッドで着手を取り消す処理や、以前の記事で実装した GUI で〇× ゲームの対戦を行う Marubatsu_GUI クラスの中で、対局を後から振り返ることができるリプレイ機能の処理で必要となりますが、プレイアウトで必要となるのは対局の勝敗結果だけなので棋譜を記録する必要はありません。そのため、プレイアウトの処理では records 属性を更新する処理を省略することができ、省略することで処理速度を改善することができます。

従って、records 属性の更新処理を行わずにプレイアウトを行う場合に記録する必要がある属性は board、last_turn、turn、move_count、last_move、status であることがわかりました。

Marubatsu クラスの `playout` メソッドの定義

プレイアウトの処理で Marubatsu クラスの move メソッドを利用すると、上記で説明したプレイアウトの処理で更新する必要のない records 属性を更新してしまうという問題があるので move メソッドをそのまま利用することはできません。また、Marubatsu クラスの属性の情報を記録して後で戻すという処理は playout のような関数ではなく Marubatsu クラスのメソッドとして実装したほうが良いでしょう。そこで Marubatsu クラスにその処理を行う playout というメソッドを定義することにします。

プレイアウトの処理で更新される board 属性の値はゲーム盤を表すクラスのインスタンスなので、以前の記事で説明したように変数への代入処理ではデータがコピーではなく共有されてしまいます。そのため最初は board 属性のみ deepcopy で深いコピーを行って変数に記録するという方法で実装することにします。深いコピーは処理速度が遅いという問題があるため、後で深いコピーを利用しない効率の良い処理を行うように修正します。

それ以外のプレイアウトで値が変化する属性の値はいずれも int 型や str 型などのイミュータブルなデータなので、変数への代入処理でデータを実質的にコピー¹することができます。

先程の説明ではプレイアウトの前に mb の属性の値を変数に代入して記録し、プレイアウトの後で復元すると説明しましたが、下記のアルゴリズムで処理を行うことで mb の属性の値を変更せずにプレイアウトの処理を行うことができます。ただし、board 属性は除きます。こちらのほうが mb の属性を復元するという処理を記述しなくても良い分だけプログラムを少しだけ簡潔に記述できるので、本記事では下記のアルゴリズムで実装することにします。

プレイアウトの処理を行う前に、プレイアウトの処理に必要となる mb の属性の値をローカルな変数に代入する
プレイアウトの処理では mb の属性を利用せずに、プレイアウトの処理に必要となる mb の属性の値を代入したローカルな変数を用いて処理を行うようにする

下記はそのように Marubatsu クラスの playout メソッドを定義したプログラムです。説明と修正箇所は前回の記事で定義した playout 関数からの修正です。

4、9 ~ 14 行目：mborig を self に修正する
16 行目：ゲーム盤を表す board 属性の値を deepcopy で深いコピーを行い、ローカル変数 board に記録する
20 ~ 22 行目：turn、move_count、status 属性の値をローカル変数に代入する
24、25 行目：mb を self に修正する
28 ~ 32 行目：Marubatsu クラスの move メソッドと同様の処理をローカル変数だけを利用して行うように修正する
29 行目：元のプログラムで last_turn 属性に代入していた値をローカル変数に代入する
32 行目：元の move メソッドでは 31 行目の後で move を last_move 属性に代入していたが、その値は次の 32 行目でそのまま利用するだけなのでローカル変数 last_move に move を代入するという処理は行わずに、32 行目ではローカル変数 move をそのまま記述することにした
33 行目：プレイアウトの処理が終わったので、ローカル変数 board に記録しておいた元の局面を表すデータの深いコピーを行って board 属性に代入して復元する
34 行目：mb.status を status に修正する

 1  from time import perf_counter
 2  from copy import deepcopy
 3  
 4  def playout(self, pnum, timelimit=None):
 5      if timelimit is not None:   
 6          starttime = perf_counter()
 7          timelimit_pc = starttime + timelimit        
 8      result = {}
 9      for move in self.calc_legal_moves():
10          result[move] = {
11              self.CIRCLE: 0,
12              self.CROSS: 0,
13              self.DRAW: 0,
14          }
15      count = 0
16      board = deepcopy(self.board)
17      for _ in range(pnum):
18          if timelimit is not None and perf_counter() > timelimit_pc:
19              break
20          turn = self.turn
21          move_count = self.move_count
22          status = self.status
23          firstmove = None
24          while status == self.PLAYING:
25              move = random.choice(self.calc_legal_moves())
26              if firstmove is None:
27                  firstmove = move
28              self.board.setmark_by_move(move, turn)
29              last_turn = turn
30              turn = self.CROSS if turn == self.CIRCLE else self.CIRCLE
31              move_count += 1
32              status = self.board.judge(last_turn, move, move_count)
33          self.board = deepcopy(board)
34          result[firstmove][status] += 1
35          count += 1
36      return {
37          "result": result,
38          "count": count,
39      }
40  
41  Marubatsu.playout = playout

行番号のないプログラム

from time import perf_counter
from copy import deepcopy

def playout(self, pnum, timelimit=None):
    if timelimit is not None:   
        starttime = perf_counter()
        timelimit_pc = starttime + timelimit        
    result = {}
    for move in self.calc_legal_moves():
        result[move] = {
            self.CIRCLE: 0,
            self.CROSS: 0,
            self.DRAW: 0,
        }
    count = 0
    board = deepcopy(self.board)
    for _ in range(pnum):
        if timelimit is not None and perf_counter() > timelimit_pc:
            break
        turn = self.turn
        move_count = self.move_count
        status = self.status
        firstmove = None
        while status == self.PLAYING:
            move = random.choice(self.calc_legal_moves())
            if firstmove is None:
                firstmove = move
            self.board.setmark_by_move(move, turn)
            last_turn = turn
            turn = self.CROSS if turn == self.CIRCLE else self.CIRCLE
            move_count += 1
            status = self.board.judge(last_turn, move, move_count)
        self.board = deepcopy(board)
        result[firstmove][status] += 1
        count += 1
    return {
        "result": result,
        "count": count,
    }
    
Marubatsu.playout = playout

修正箇所

from time import perf_counter
from copy import deepcopy

-def playout(mborig, pnum, timelimit=None):
+def playout(self, pnum, timelimit=None):
    if timelimit is not None:   
        starttime = perf_counter()
        timelimit_pc = starttime + timelimit        
    result = {}
-   for move in mborig.calc_legal_moves():
+   for move in self.calc_legal_moves():
        result[move] = {
-           mborig.CIRCLE: 0,
-           mborig.CROSS: 0,
-           mborig.DRAW: 0,
+           self.CIRCLE: 0,
+           self.CROSS: 0,
+           self.DRAW: 0,
        }
    count = 0
+   board = deepcopy(self.board)
    for _ in range(pnum):
        if timelimit is not None and perf_counter() > timelimit_pc:
            break
-       mb = deepcopy(mborig)
+       turn = self.turn
+       move_count = self.move_count
+       status = self.status
        firstmove = None
-       while status == mb.PLAYING:
+       while status == self.PLAYING:
-           move = random.choice(mb.calc_legal_moves())
+           move = random.choice(self.calc_legal_moves())
            if firstmove is None:
                firstmove = move
-           mb.move(move)
+           self.board.setmark_by_move(move, turn)
+           last_turn = turn
+           turn = self.CROSS if turn == self.CIRCLE else self.CIRCLE
+           move_count += 1
+           status = self.board.judge(last_turn, move, move_count)
+       self.board = deepcopy(board)
-       result[firstmove][mb.status] += 1
+       result[firstmove][status] += 1
        count += 1
    return {
        "result": result,
        "count": count,
    }
    
Marubatsu.playout = playout

下記は上記で定義した playout メソッドで乱数の種を 0 として 1 万回のプレイアウトを行うプログラムです。先ほどと同じ結果が表示されることから正しい処理が行われることが確認できました。

random.seed(0)
retval = mb.playout(10000)
move = mb.board.xy_to_move(0, 0)
data = retval["result"][move]
print(f"(0, 0) o {data[mb.CIRCLE]} x {data[mb.CROSS]} draw {data[mb.DRAW]}")

実行結果

(0, 0) o 710 x 298 draw 156

処理速度の確認

下記の先程と同様のプログラムで上記で定義した playout メソッドの処理速度を確認することにします。先ほどのプログラムとの違いは playout(mb, pnum=100000000, timelimit=1) を mb.playout(pnum=100000000, timelimit=1) に修正した点です。

for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
    for count_linemark in [False, True]:
        if boardclass in [BitBoard3x3, TwoBitBoard3x3] and count_linemark == True:
            continue
        print(f"boardclass = {boardclass.__name__} count_linemark = {count_linemark}")
        mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
        retval = mb.playout(pnum=100000000, timelimit=1)
        print(f"playout count = {retval['count']}")

修正箇所

for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
    for count_linemark in [False, True]:
        if boardclass in [BitBoard3x3, TwoBitBoard3x3] and count_linemark == True:
            continue
        print(f"boardclass = {boardclass.__name__} count_linemark = {count_linemark}")
        mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
-       retval = playout(mb, pnum=100000000, timelimit=1)
+       retval = mb.playout(pnum=100000000, timelimit=1)
        print(f"playout count = {retval['count']}")

実行結果

boardclass = ListBoard count_linemark = False
playout count = 28327
boardclass = ListBoard count_linemark = True
playout count = 20445
boardclass = List1dBoard count_linemark = False
playout count = 39620
boardclass = List1dBoard count_linemark = True
playout count = 23251
boardclass = ArrayBoard count_linemark = False
playout count = 41177
boardclass = ArrayBoard count_linemark = True
playout count = 23935
boardclass = NpBoard count_linemark = False
playout count = 14189
boardclass = NpBoard count_linemark = True
playout count = 14417
boardclass = NpIntBoard count_linemark = False
playout count = 18041
boardclass = NpIntBoard count_linemark = True
playout count = 18303
boardclass = NpBoolBoard count_linemark = False
playout count = 18656
boardclass = NpBoolBoard count_linemark = True
playout count = 13625
boardclass = BitBoard count_linemark = False
playout count = 19077
boardclass = BitBoard count_linemark = True
playout count = 13415
boardclass = BitBoard3x3 count_linemark = False
playout count = 51124
boardclass = TwoBitBoard3x3 count_linemark = False
playout count = 45061

下記は先ほどの結果に上記の実行結果を加えた表です。表から増え方の割合に差はありますが、いずれの場合もプレイアウトの回数が増えており、最も高速な BitBoard3x3 クラスの場合は 2 倍以上も処理速度が高速化することが確認できます。

ゲーム盤のクラス	`count_linemark`	プレイアウトの回数	修正後の回数
ListBoard	`False`	16625	28327
ListBoard	`True`	13843	20445
List1dBoard	`False`	22207	39620
List1dBoard	`True`	15236	23251
ArrayBoard	`False`	21743	41177
ArrayBoard	`True`	15985	23935
NpBoard	`False`	10221	14189
NpBoard	`True`	10634	14417
NpIntBoard	`False`	12227	18041
NpIntBoard	`True`	12647	18303
NpBoolBoard	`False`	12390	18656
NpBoolBoard	`True`	10252	13625
BitBoard	`False`	13613	19077
BitBoard	`True`	10664	13415
BitBoard3x3		24684	51124
TwoBitBoard3x3		23125	45061

ゲーム盤を表すクラスの改良

上記の修正では deepcopy でゲーム盤を表す board 属性の深いコピーを行うという点が効率が悪いので、次はこの問題を解決します。

deepcopy の代替方法の考え方は先程と同様で、プレイアウトを行う前にゲーム盤を表す mb.board の中でプレイアウトによって変化する属性の値を記録しておき、プレイアウトの後で元に戻すというものです。なお、先程は mb の属性を直接変更しないアルゴリズムでプログラムを記述することができましたが、今回は mb.board の属性を変更しないようにプログラムを記述することは困難なのでその方法は採用しません。

また、Marubatsu クラスのメソッドの中でゲーム盤を表すクラスの属性を直接変更することは望ましくないので、ゲーム盤を表すクラスに下記の 2 つのメソッドを追加することにします。行う処理はゲームのデータのセーブとロードに似ているので save と load という名前にしました。

メソッド	処理
`save`	ゲーム盤のクラスの属性の中で、値が変化する属性をコピーしたデータを返り値として返す
`load`	`save` メソッドの返り値を代入する仮引数 `data` を持ち、ゲーム盤の状態を `save` を実行した時点の状態に復元する

なお、ゲーム盤を表すクラスごとにその属性のデータ構造が異なるので、それぞれのクラスごとにこの 2 つのメソッドを実装る必要があります。

Board クラスの修正

save と load メソッドはすべてのゲーム盤を表すクラスに実装する必要があるので、下記のプログラムのようにゲーム盤を表すクラスの基底クラスである Board クラスの抽象メソッドとして定義することにします。

from marubatsu import Board
from abc import ABCMeta, abstractmethod

@abstractmethod
def save(self):
    pass

Board.save = save

@abstractmethod
def load(self, data):
    pass

Board.load = load

値が変化する属性の一覧

ゲーム盤を表すクラスの属性にはゲーム盤のサイズを表す BOARD_SIZE 属性など、__init__ メソッドで初期化を行った後で値が変化することがない属性と、ゲーム盤を表す board 属性のように着手を行うと変化する属性がありますが、変化しない属性はコピーや復元を行う必要はありません。

下記は値が変化する属性の一覧で、これらの属性の値のコピーと復元処理を行う必要があります。その方法について少し考えてみて下さい。

属性	意味
`board`	ゲーム盤を表すデータ。データ構造はゲーム盤のクラスによって異なる
`rowcount`	各行のマークの数を表すデータ
`colcount`	各列のマークの数を表すデータ
`diacount`	各対角線のマークの数を表すデータ
`cross_turn`	× の手番であるかどうかを表す int 型のデータ。TwoBitBoard3x3 クラスのみ存在する

値が変化する属性のデータ型

下記は board 属性のデータ構造を表す表です。

ゲーム盤のクラス	データ型
ListBoard	str 型を要素の値とする 2 次元の list
List1dBoard	str 型を要素の値とする 1 次元の list
ArrayBoard	str 型を要素とする array
NpBoard	str 型を要素の値とする 2 次元の ndarray
NpIntBoard	int 型を要素の値とする 2 次元の ndarray
NpBoolBoard	bool 型を要素の値とする 2 次元の ndarray
BitBoard	〇と × の int 型のビットボードを要素とする 1 次元の list
BitBoard3x3	3 x 3 のゲーム盤のサイズに特化した BitBoard
TwoBitBoard3x3	〇と × をまとめて一つのビットボードで表す int 型のデータ

rowcountのデータ構造は下記の表のような、dict のキーの値に list を代入したデータ構造です。colcount、diacount のデータ構造も同様です。

キー	キーの値
`self.CIRCLE`	各行の〇の数を表す int 型を要素とする 1 次元の list
`self.CROSS`	各行の × の数を表す int 型を要素とする 1 次元の list

上記の表から、値が変化する属性のデータ構造は下記のように分類されることがわかります。なお、list や ndarray の要素のデータ型が int、str、bool の場合は、いずれの場合であってもコピーと復元の処理の方法は変わらないので下記では要素のデータ型は省略しました。

2 次元の list
1 次元の list
array
2 次元の ndarray
int 型
1 次元の list をキーの値とする dict

様々なデータの効率的なコピーと復元処理

上記の中のイミュータブルな int 型は変数への代入処理でコピーと復元を行うことができるので、それ以外のデータ構造の効率的なコピーと復元の方法ついて説明します。

1 次元の list のコピーと復元

List1dBoard の board 属性にはイミュータブルな str 型のデータを要素とする 1 次元の list が代入されます。以前の記事で説明したように、すべての要素の値がイミュータブルな 1 次元の list のコピーは、浅いコピーによって行うことができます。また、コピーしたデータからの復元も同様に浅いコピーで行うことができます。

1 次元の list の浅いコピーを行う主な方法は以下の通りです。

list の copy メソッド
list の [:] によるスライス表記
copy モジュールで定義された copy 関数

下記は上記の方法で〇× ゲームのマスの数と同じ 9 つの str 型の要素を持つ 1 次元の list の浅いコピーを行うプログラムで、実行結果からいずれの場合も正しくコピーを行うことができていることが確認できます。厳密に確認したい人は、コピーしたデータの特定の要素に値を代入して、コピー元のデータと共有が行われていないことも確認してみて下さい。

from copy import copy

a = ["o", "x", ".", ".", "x", "o", "o", ".", "x"]
print("list の copy メソッドによるコピー")
print(a.copy())
print("スライス表記 [:] によるコピー")
print(a[:])
print("copy モジュールの copy による浅いコピー")
print(copy(a))

実行結果

list の copy メソッドによるコピー
['o', 'x', '.', '.', 'x', 'o', 'o', '.', 'x']
スライス表記 [:] によるコピー
['o', 'x', '.', '.', 'x', 'o', 'o', '.', 'x']
copy モジュールの copy による浅いコピー
['o', 'x', '.', '.', 'x', 'o', 'o', '.', 'x']

下記は上記のそれぞれの場合の処理時間を計測するプログラムです。実行結果から list の copy メソッドを利用する方法が最も高速であることが確認できました。

print("list の copy メソッドによるコピー")
%timeit a.copy()
print("スライス表記 [:] によるコピー")
%timeit a[:]
print("copy モジュールの copy による浅いコピー")
%timeit copy(a)

実行結果

list の copy メソッドによるコピー
64.4 ns ± 0.377 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
スライス表記 [:] によるコピー
83.4 ns ± 1.13 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
copy モジュールの copy による浅いコピー
149 ns ± 1.01 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

Python のバージョン、list の要素数、要素のデータ型によっては上記と異なる結果になる場合があるかもしれません。

2 次元の list のコピーと復元

2 次元の list のコピーを浅いコピーで行うと要素が共有されてしまうため、copy モジュールの deepcopy を利用した深いコピーでコピーを行う必要があります。

2 次元の list のコピーと復元を行う他の方法としては、list とは異なる別のデータに変換してコピーし、それを元の 2 次元の list に戻すという方法が考えられます。具体的には numpy や pickle モジュールを利用してコピーと復元を行うことができます。なお、他にも同様の処理を行うこができるもっと高速なモジュールがあるかもしれませんので、ご存じの方はコメントなどで教えて頂ければ助かります。

numpy を利用する場合は 2 次元の list を 2 次元の ndarray に変換するという方法でデータのコピーを行い、ndarray の tolist メソッドを利用して 2 次元の list に復元します。

以前の記事では pickle モジュールで定義された dump と load を利用して Python のオブジェクトをファイルに保存する方法とファイルから読み込む方法を紹介しましたが、pickle には Python のオブジェクトを以前の記事で説明した bytes 型のデータのオブジェクトに変換する dumps と、dumps で変換した bytes 型のデータを元の Python のオブジェクトに戻す loads メソッドがあるのでそれを利用します。

下記は ListBoard を利用したゲーム盤に対していくつかのマスに着手を行った局面のデータを、それぞれの方法でコピーと復元を行うプログラムです。実行結果からいずれの場合も元の局面が表示されるので、正しくコピーと復元を行えていることが確認できます。

4 ~ 8 行目：ListBoard クラスを利用した Marubatsu クラスのインスタンスを作成し、いくつかのマスに着手を行った後でゲーム盤を表示する
10、11 行目：deepcopy で mb.board の深いコピーを行い、それを再び deepcopy でコピーしたものを mb.board に代入することで復元する
13、14 行目：np.array で mb.board に代入された 2 次元の list を 2 次元の ndarray に変換してコピーし、tolist メソッドで 2 次元の list に復元して mb.board に代入する
18、19 行目：pickle.dumps で mb.board に代入された 2 次元の list を bytes 型のデータに変換し、pickle.loads で 2 次元の list に復元して mb.board に代入する

 1  import numpy as np
 2  import pickle
 3  
 4  mb = Marubatsu(boardclass=ListBoard)
 5  mb.cmove(0, 0)
 6  mb.cmove(1, 0)
 7  mb.cmove(2, 1)
 8  print(mb)
 9  print("deepcopy")
10  board = deepcopy(mb.board)
11  mb.board = deepcopy(board)
12  print(mb)
13  print("ndarray")
14  board = np.array(mb.board)
15  mb.board = board.tolist()
16  print(mb)
17  print("pickle")
18  board = pickle.dumps(mb.board)
19  mb.board = pickle.loads(board)
20  print(mb)

行番号のないプログラム

import numpy as np
import pickle

mb = Marubatsu(boardclass=ListBoard)
mb.cmove(0, 0)
mb.cmove(1, 0)
mb.cmove(2, 1)
print(mb)
print("deepcopy")
board = deepcopy(mb.board)
mb.board = deepcopy(board)
print(mb)
print("ndarray")
board = np.array(mb.board)
mb.board = board.tolist()
print(mb)
print("pickle")
board = pickle.dumps(mb.board)
mb.board = pickle.loads(board)
print(mb)

実行結果

Turn x
ox.
..O
...

deepcopy
Turn x
ox.
..O
...

ndarray
Turn x
ox.
..O
...

pickle
Turn x
ox.
..O
...

下記は上記のそれぞれの処理速度を計測するプログラムです。

print("deepcopy")
%timeit deepcopy(mb.board)
board = deepcopy(mb.board)
%timeit deepcopy(board)
print("ndarray")
%timeit np.array(mb.board)
board = np.array(mb.board)
%timeit board.tolist()
print("pickle")
%timeit pickle.dumps(mb.board)
board = pickle.dumps(mb.board)
%timeit mb.board = pickle.loads(board)

実行結果

deepcopy
11.1 μs ± 71.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
11 μs ± 63.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
ndarray
373 ns ± 2.09 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
50.6 ns ± 0.379 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
pickle
2.88 μs ± 12.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.36 μs ± 30 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

下記は上記の実行結果をまとめた表です。単位は ns で統一しました。実行結果から ndarray を利用した方法がコピーと復元のいずれの場合でも圧倒的に高速であることが確認できたので、本記事ではその方法を利用することにします。

	コピー	復元
deepcopy	11,100 ns	11,000 ns
ndarray	373 ns	51 ns
pickle	28,800 ns	23,600 ns

2026/06/14 日頃に Google の AI に deepcopy と ndarray 以外で 2 次元の list を高速にコピーして復元する方法について尋ねたところ pickle が最も速いという回答が得られましたが、上記のように実際に実行してみたところ pickle が一番遅いという残念な結果になりました。生成 AI の答えを鵜呑みにせずに実際に確認することが重要な例の一つだと思いましたので紹介しました。

1 次元の list に対しても ndarray と pickle を利用してコピーと復元を行うこともできますが、下記のプログラムの実行結果のように list copy メソッドの方が処理速度が高速になるようです。

print("list の copy メソッドによるコピー")
%timeit a.copy()
print("スライス表記 [:] によるコピー")
%timeit a[:]
print("copy モジュールの copy による浅いコピー")
%timeit copy(a)
print("ndarray に変換後 tolist メソッドによる変換")
%timeit np.array(a)
b = np.array(a)
%timeit b.tolist()
print("pickle による変換と復元")
%timeit pickle.dumps(a)
c = pickle.dumps(a)
%timeit pickle.loads(c)

実行結果

list の copy メソッドによるコピー
64.4 ns ± 0.708 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
スライス表記 [:] によるコピー
82.3 ns ± 0.127 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
copy モジュールの copy による浅いコピー
148 ns ± 0.716 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
ndarray に変換後 tolist メソッドによる変換
1.69 μs ± 10 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
160 ns ± 2.08 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
pickle による変換と復元
1.15 μs ± 5.36 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
505 ns ± 3.76 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

pickle モジュールの dumps と loads の詳細については下記のリンク先を参照して下しさい。

array のコピーと復元

array には copy メソッドは用意されていないので、下記のいずれかの方法でコピーを行う必要があります。np.array や pickle を利用することもできますが、1 次元の list の場合のように処理速度は下記と比較して速くないので省略します。興味がある方は計測してみて下さい。

array の [:] によるスライス表記
copy モジュールで定義された copy 関数

下記は上記の方法で〇× ゲームのマスの数と同じ 9 つの要素を持つ array の浅いコピーを行うプログラムで、実行結果からいずれの場合も正しくコピーを行うことができていることが確認できます。

from array import array

a = array("w", ["o", "x", ".", ".", "x", "o", "o", ".", "x"])
print(a)
print("スライス表記 [:] によるコピー")
print(a[:])
print("copy モジュールの copy による浅いコピー")
print(copy(a))

実行結果

array('w', 'ox..xoo.x')
スライス表記 [:] によるコピー
array('w', 'ox..xoo.x')
copy モジュールの copy による浅いコピー
array('w', 'ox..xoo.x')

下記は上記のそれぞれの場合の処理時間を計測するプログラムです。実行結果からスライス表記を利用する方法が最も高速であることが確認できました。

print("スライス表記 [:] によるコピー")
%timeit a[:]
print("copy モジュールの copy による浅いコピー")
%timeit copy(a)

実行結果

スライス表記 [:] によるコピー
91.1 ns ± 0.175 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
copy モジュールの copy による浅いコピー
234 ns ± 3.08 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

2 次元の ndarray のコピー

2 次元の ndarray のコピーは下記の方法で行うことができます。

ndarray の copy メソッド
copy モジュールで定義された copy 関数

下記は上記の方法で〇× ゲームのマスの数と同じ 9 つの str 型の要素を持つ 2 次元の list のコピーを行うプログラムで、実行結果からいずれの場合も正しくコピーを行うことができていることが確認できます。

a = np.array([["o", "x", "."], [".", "x", "o"], ["o", ".", "x"]])
print("ndarray の copy メソッドによるコピー")
print(a.copy())
print("copy モジュールの copy によるコピー")
print(copy(a))

実行結果

ndarray の copy メソッドによるコピー
[['o' 'x' '.']
 ['.' 'x' 'o']
 ['o' '.' 'x']]
copy モジュールの copy によるコピー
[['o' 'x' '.']
 ['.' 'x' 'o']
 ['o' '.' 'x']]

下記は上記のそれぞれの場合の処理時間を計測するプログラムです。実行結果から ndarray の copy メソッドを利用したほうが高速になることが確認できました。

print("ndarray の copy メソッドによるコピー")
%timeit a.copy()
print("copy モジュールの copy によるコピー")
%timeit copy(a)

実行結果

ndarray の copy メソッドによるコピー
318 ns ± 4.67 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
copy モジュールの copy によるコピー
495 ns ± 5.27 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

なお、ndarray は何次元のデータであっても copy メソッドや copy モジュールの copy で完全なコピーを行うことができますが、いずれの場合でも ndarray の copy メソッドのほうが処理が高速になります。興味がある方は確認してみて下さい。

ndarray は list とは異なる方法でデータを記録しているため、多次元の list の場合と異なり、多次元の ndarray であっても浅いコピーを行う copy モジュールで完全なコピーを行うことができます。実際に下記のプログラムのように copy でコピーした 2 次元の ndarray の特定の要素を変更してもコピー元のデータは変化しません。

print(a[0][0])
b = copy(a)
b[0][0] = "x"
print(a[0][0])
print(b[0][0])

実行結果

o
o
x

ただし、処理速度の点から ndarray のコピーは ndarry の copy メソッドで行ったほうが良いでしょう。

スライス表記は list の場合は浅いコピーを行いますが、ndarray の場合はコピーではなくデータの共有が行われる点に注意が必要です。

下記のプログラムのように 1 次元の ndarray に対して [:] によるスライス表記を行うと、元の 1 次元の ndarray の浅いコピーではなく、元の ndarray の要素を共有する ndarray が作成されるため、片方の要素の値を変更すると実行結果のようにもう片方の要素の値も変化します。

a = np.array([1, 2, 3])
print(a)
b = a[:]
print(b)
b[0] = 5
print(a)
print(b)

実行結果

[1 2 3]
[1 2 3]
[5 2 3]
[5 2 3]

また、下記のプログラムのようにスライス表記を利用して元の ndarray の要素の一部を表す ndarray を計算した場合でもそれらの要素は共有されます。下記のプログラムはそのことを確認するプログラムで、a[:2,:2] で 2 次元の ndarray の一部を計算して b に代入して b の要素を変更すると、対応する a の要素も変更されます。

a = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
print(a)
b = a[:2, :2]
print(b)
b[0][0] = 5
print(a)
print(b)

実行結果

[[1 2 3]
 [4 5 6]
 [7 8 9]]
[[1 2]
 [4 5]]
[[5 2 3]
 [4 5 6]
 [7 8 9]]
[[5 2]
 [4 5]]

1 次元の list をキーの値とする dict

dict のキーの値が list のようなミュータブルなデータの場合は、dict の浅いコピーを行うとキーの値である list が共有されるため、深いコピーでコピーを行う必要があります。

深いコピーを利用しない別の方法としては、dict のキーの値をそれぞれの別々にコピーし、それらのデータから元の dict のデータを復元するという方法があります。

rowcount 属性のような「ミュータブルな要素を持つ 1 次元の list」をキーの値とする dict の場合はそれぞれのキーの値を別々に copy メソッドで浅いコピーを行い、その値から元の dict のデータを復元します。

下記はいくつかの着手を行った局面の rowcount 属性を上記の方法でコピーして復元するプログラムで、実行結果から rowcount が正しく復元されていることが確認できます。

mb = Marubatsu(boardclass=ListBoard, count_linemark=True)
mb.cmove(0, 0)
mb.cmove(1, 1)
print(mb.board.rowcount)
circlelist = mb.board.rowcount[mb.CIRCLE].copy()
crosslist = mb.board.rowcount[mb.CROSS].copy()
mb.board.rowcount = {
    mb.CIRCLE: circlelist.copy(),
    mb.CROSS: crosslist.copy(),
}
print(mb.board.rowcount)

実行結果

{'o': [1, 0, 0], 'x': [0, 1, 0]}
{'o': [1, 0, 0], 'x': [0, 1, 0]}

下記は rowcount 属性を deepcopy で深いコピーを行う場合と、上記の方法でデータのコピーと復元を行う処理の処理時間を計測するプログラムです。

%timeit deepcopy(mb.board.rowcount)

実行結果

4.74 μs ± 26.6 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%%timeit 
# データのコピー
circlelist = mb.board.rowcount[mb.CIRCLE].copy()
crosslist = mb.board.rowcount[mb.CROSS].copy()

実行結果

190 ns ± 1.95 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

%%timeit
# データの復元
mb.board.rowcount = {
    mb.CIRCLE: circlelist.copy(),
    mb.CROSS: crosslist.copy(),
}

実行結果

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

実行結果から、後者の処理時間のほうが deepcopy による深いコピーの処理時間よりも 10 倍以上も高速であることが確認できました。

rowcount、colcount、diacount のデータを下記のような 1 つの 3 次元の list にまとめ、それを 3 次元の ndarray に変換してコピーし、tolist メソッドで復元するという方法も考えられます。おそらく下記の方法のほうが上記の方法よりも処理速度が若干高速になるのではないかと思いますが、下記の方法はデータ構造が変化するためゲーム盤を表すクラスのメソッドを変更する必要が生じます。

1 つ目のインデックスが行、列、対角線を表し、行を 0、列を 1、対角線を 2 に対応させる
2 つ目のインデックスが行、列、対角線の番号を表す。行と列はゲーム盤のサイズと同じだけあり、対角線は常に 2 個なので、2 つ目のインデックスは 0 以上ゲーム盤のサイズ未満の整数とする
3 つ目のインデックスが〇と × のマークを表し、〇を 0、× を 1 に対応させる

最も高速な処理を行うことができる BitBoard3x3 クラスは rowcount、colcount、diacount 属性を持たないので本記事では上記のような修正は行わないことにします。興味がある方は実際に実装して処理速度を比較してみて下さい。

ゲーム盤を表すクラスの修正

次に、それぞれのゲーム盤を表すクラスに save と load メソッドを実装します。

ListBoard クラスの `save_count` と `load_count` メソッドの定義

rowcount、colcount、diacount のデータ構造は全てのクラスで共通なので、それらのデータのコピーと復元処理を行う save_count と load_count というメソッドを定義することにします。また、これらの属性を持つゲーム盤のクラスは BitBoard クラス以外は ListBoard クラスを継承して定義しているので、ListBoard クラスにこれらのメソッドを定義することで BitBoard 以外のクラスでもこれらの関数を利用することができます。

下記は save_count と load_count メソッドを定義するプログラムです。`

save_count は rowcount、colcount、diacount の 2 つのキーの値である list をそれぞれコピーした要素を持つ tuple を返す関数として定義しました。

load_count は save_count の返り値である tuple を代入する仮引数 data を持ち、その要素をそれぞれコピーして rowcount、colcount、diacount を復元する処理を行います。

def save_count(self):
    return (self.rowcount[self.CIRCLE].copy(), self.rowcount[self.CROSS].copy(),
            self.colcount[self.CIRCLE].copy(), self.rowcount[self.CROSS].copy(),
            self.diacount[self.CIRCLE].copy(), self.rowcount[self.CROSS].copy())
    
ListBoard.save_count = save_count

def load_count(self, data):
    self.rowcount = {
        self.CIRCLE: data[0].copy(),
        self.CROSS: data[1].copy(),
    }
    self.colcount = {
        self.CIRCLE: data[2].copy(),
        self.CROSS: data[3].copy(),
    }
    self.diacount = {
        self.CIRCLE: data[4].copy(),
        self.CROSS: data[5].copy(),
    }
    
ListBoard.load_count = load_count

ListBoard クラスの修正

下記は ListBoard クラスの save と load メソッドを定義するプログラムです。

save メソッドは下記の処理を行います。

ゲーム盤を表す 2 次元の list を 2 次元の ndarray に変換して board に代入する
count_linemark が True の場合は board と save_count の返り値を要素とする tuple を返す
count_linemark が False の場合は board だけを返り値として返す

save メソッドは下記の処理を行います。

save メソッドの返り値を代入する仮引数 data を持つ
data の中のゲーム盤を表す 2 次元の ndarray を tolist メソッドで 2 次元の list に復元して board 属性にコピーする
count_linemark が True の場合は load_count メソッドを呼び出してrowcount、colcount、diacount を復元する

def save(self):
    board = np.array(self.board)
    if self.count_linemark:
        return board, self.save_count()
    else:
        return board
    
ListBoard.save = save

def load(self, data):
    if self.count_linemark:
        self.board = data[0].tolist()
        self.load_count(data[1])
    else:
        self.board = data.tolist()
        
ListBoard.load = load

上記のプログラムの動作の確認と、処理時間の検証は後でまとめて行います。

List1dBoard クラスの修正

下記は List1dBoard クラスの save と load メソッドの定義で、board 属性に関する処理以外は ListBoard の場合と同様なので board 属性に関する処理だけを説明します。以後のゲーム盤のクラスの説明でも同様です。

ゲーム盤を表す 1 次元の list のコピーと復元は list の copy メソッドを利用して行います。

def save(self):
    board = self.board.copy()
    if self.count_linemark:
        return board, self.save_count()
    else:
        return board
    
List1dBoard.save = save

def load(self, data):
    if self.count_linemark:
        self.board = data[0].copy()
        self.load_count(data[1])
    else:
        self.board = data.copy()
        
List1dBoard.load = load

ArrayBoard クラスの修正

下記は ArrayBoard クラスの save と load メソッドの定義で、ゲーム盤を表す array のコピーと復元は [:] というスライス表記を利用して行います。

def save(self):
    board = self.board[:]
    if self.count_linemark:
        return board, self.save_count()
    else:
        return board
    
ArrayBoard.save = save

def load(self, data):
    if self.count_linemark:
        self.board = data[0][:]
        self.load_count(data[1])
    else:
        self.board = data[:]
        
ArrayBoard.load = load

NpBoard、NpIntBoard、NpBoolBoard クラスの修正

下記は NpBoard クラスの save と load メソッドの定義で、ゲーム盤を表す ndarray のコピーと復元は ndarray の copy メソッドを利用して行います。

def save(self):
    board = self.board.copy()
    if self.count_linemark:
        return board, self.save_count()
    else:
        return board
    
NpBoard.save = save

def load(self, data):
    if self.count_linemark:
        self.board = data[0].copy()
        self.load_count(data[1])
    else:
        self.board = data.copy()
        
NpBoard.load = load

NpIntBoard、NpBoolBoard クラスは NpBoard クラスを継承して定義されており、ゲーム盤を表す ndarray のコピーと復元は NpBoard と同じ方法で行うことができるので、それらのクラスに save と load メソッドを定義する必要はありません。

BitBoard クラスの修正

下記は BitBoard クラスの save と load メソッドの定義で、ゲーム盤を表す 1 次元の list のコピーと復元は list の copy メソッドを利用して行います。なお、BitBoard クラスは ListBoard クラスを継承していないので、下記のプログラムのように先程定義した save_count と load_count メソッドを定義する必要があります。

BitBoard.save_count = save_count
BitBoard.load_count = load_count

def save(self):
    board = self.board.copy()
    if self.count_linemark:
        return board, self.save_count()
    else:
        return board
    
BitBoard.save = save

def load(self, data):
    if self.count_linemark:
        self.board = data[0].copy()
        self.load_count(data[1])
    else:
        self.board = data.copy()
        
BitBoard.load = load

BitBoard3x3 クラスの修正

下記は BitBoard3x3 クラスの save と load メソッドの定義で、ゲーム盤を表す 1 次元の list のコピーと復元は list の copy メソッドを利用して行います。また、BitBoard3x3 クラスではマークの数を数えないので count_linemark に関する処理を記述する必要はありません。

def save(self):
    return self.board.copy()
    
BitBoard3x3.save = save

def load(self, data):
    self.board = data.copy()
        
BitBoard3x3.load = load

TwoBoard3x3 クラスの修正

下記は TwoBitBoard3x3 クラスの save と load メソッドの定義です。TwoBitBoard3x3 クラスにはゲーム盤を表す int 型の board 属性と手番を表す int 型の crossturn 属性があるので、save メソッドではそれらの値を要素とする tuple を返します。また、それらはイミュータブルなデータなので load メソッドではそれらをそのまま属性に代入することで復元を行うことができます。

def save(self):
    return self.board, self.crossturn
 
TwoBitBoard3x3.save = save

def load(self, data):
    self.board, self.crossturn = data
        
TwoBitBoard3x3.load = load

Marubatsu クラスの `playout` メソッドの修正

最後に下記のプログラムのように Marubatsu クラスの playout メソッドをゲーム盤の save と load メソッドを利用するように修正します。

2 行目：self.board.save() でプレイアウトを行う前のゲーム盤のデータをコピーした値を board に代入する
4 行目：self.board.load(board) でプレイアウトを行った前の状態にゲーム盤のデータを復元する

 1  def playout(self, pnum, timelimit=None):
元と同じなので省略
 2      board = self.board.save()
 3      for _ in range(pnum):
元と同じなので省略
 4          self.board.load(board)
 5          result[firstmove][status] += 1
 6          count += 1
 7      return {
 8          "result": result,
 9          "count": count,
10      }
11  
12  Marubatsu.playout = playout

行番号のないプログラム

def playout(self, pnum, timelimit=None):
    if timelimit is not None:   
        starttime = perf_counter()
        timelimit_pc = starttime + timelimit        
    result = {}
    for move in self.calc_legal_moves():
        result[move] = {
            self.CIRCLE: 0,
            self.CROSS: 0,
            self.DRAW: 0,
        }
    count = 0
    board = self.board.save()
    for _ in range(pnum):
        if timelimit is not None and perf_counter() > timelimit_pc:
            break
        turn = self.turn
        move_count = self.move_count
        status = self.status
        firstmove = None
        while status == self.PLAYING:
            move = random.choice(self.calc_legal_moves())
            if firstmove is None:
                firstmove = move
            self.board.setmark_by_move(move, turn)
            last_turn = turn
            turn = self.CROSS if turn == self.CIRCLE else self.CIRCLE
            move_count += 1
            status = self.board.judge(last_turn, move, move_count)
        self.board.load(board)
        result[firstmove][status] += 1
        count += 1
    return {
        "result": result,
        "count": count,
    }
    
Marubatsu.playout = playout

修正箇所

def playout(self, pnum, timelimit=None):
元と同じなので省略
-   board = deepcopy(self.board)
+   board = self.board.save()
    for _ in range(pnum):
元と同じなので省略
-       self.board = deepcopy(board)
+       self.board.load(board)
        result[firstmove][status] += 1
        count += 1
    return {
        "result": result,
        "count": count,
    }
    
Marubatsu.playout = playout

処理の確認と処理速度の計測

下記のプログラムで修正したプログラムの処理の確認と処理速度の計測をまとめて行うことにします。先程のプログラムとの違いは 7 ~ 11 行目で乱数の種を 0 としてゲーム開始時の局面での 10000 回のプレイアウトを行い、最初に (0, 0) に合法手を着手した場合の結果を表示する点です。実行結果からいずれのゲーム盤のクラスを利用した場合も先ほどと同じ結果が表示されるため、正しい処理が行われていることが確認できました。

 1  for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
 2      for count_linemark in [False, True]:
 3          if boardclass in [BitBoard3x3, TwoBitBoard3x3] and count_linemark == True:
 4              continue
 5          print(f"boardclass = {boardclass.__name__} count_linemark = {count_linemark}")
 6          mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
 7          random.seed(0)
 8          retval = mb.playout(10000)
 9          move = mb.board.xy_to_move(0, 0)
10          data = retval["result"][move]
11          print(f"(0, 0) o {data[mb.CIRCLE]} x {data[mb.CROSS]} draw {data[mb.DRAW]}")
12          retval = mb.playout(pnum=100000000, timelimit=1)
13          print(f"playout count = {retval['count']}")

行番号のないプログラム

for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
    for count_linemark in [False, True]:
        if boardclass in [BitBoard3x3, TwoBitBoard3x3] and count_linemark == True:
            continue
        print(f"boardclass = {boardclass.__name__} count_linemark = {count_linemark}")
        mb = Marubatsu(boardclass=boardclass, count_linemark=count_linemark)
        random.seed(0)
        retval = mb.playout(10000)
        move = mb.board.xy_to_move(0, 0)
        data = retval["result"][move]
        print(f"(0, 0) o {data[mb.CIRCLE]} x {data[mb.CROSS]} draw {data[mb.DRAW]}")
        retval = mb.playout(pnum=100000000, timelimit=1)
        print(f"playout count = {retval['count']}")

実行結果

boardclass = ListBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 47205
boardclass = ListBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 43096
boardclass = List1dBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 75128
boardclass = List1dBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 53790
boardclass = ArrayBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 59657
boardclass = ArrayBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 48865
boardclass = NpBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 17016
boardclass = NpBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 21976
boardclass = NpIntBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 22197
boardclass = NpIntBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 30375
boardclass = NpBoolBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 22650
boardclass = NpBoolBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 20084
boardclass = BitBoard count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 76938
boardclass = BitBoard count_linemark = True
(0, 0) o 710 x 298 draw 156
playout count = 49244
boardclass = BitBoard3x3 count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 90216
boardclass = TwoBitBoard3x3 count_linemark = False
(0, 0) o 710 x 298 draw 156
playout count = 77525

下記は先程の結果に上記の実行結果を加えた表です。長いので count_linemark を clmark と表記しました。表からいずれの場合も処理速度がさらに高速化し、最も高速な BitBoard3x3 クラスの場合は最初の約 3.5 倍も高速になることが確認できました。

ゲーム盤のクラス	`clmark`	最初の回数	1 回目の修正後	2 回目の修正後
ListBoard	`False`	16625	28327	47205
ListBoard	`True`	13843	20445	43096
List1dBoard	`False`	22207	39620	75128
List1dBoard	`True`	15236	23251	53790
ArrayBoard	`False`	21743	41177	59657
ArrayBoard	`True`	15985	23935	48865
NpBoard	`False`	10221	14189	17016
NpBoard	`True`	10634	14417	21976
NpIntBoard	`False`	12227	18041	22197
NpIntBoard	`True`	12647	18303	30375
NpBoolBoard	`False`	12390	18656	22650
NpBoolBoard	`True`	10252	13625	20084
BitBoard	`False`	13613	19077	76938
BitBoard	`True`	10664	13415	49244
BitBoard3x3		24684	51124	90216
TwoBitBoard3x3		23125	45061	77525

今回の記事のまとめ

今回の記事では、複数回のプレイアウトの集計処理の高速化を行い、最も処理速度が速い BitBoard3x3 クラスを利用した場合に約 3.5 倍の高速化が実現できたことが確認できました。頑張ればもっと高速化することができるかもしれませんが、それほど劇的な高速化は行えないのではないかと思いますのでプレイアウトの高速化はここまでにしたいと思います。

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

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

次回の記事

近日公開予定です

以前の記事で説明したように、Python の代入処理は例外なくオブジェクトを共有するという処理ですが、イミュータブルなデータは実質的に代入処理がデータの複製処理になります。なお、以前の記事ではこのことを疑似的な複製と表記しました ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その233 プレイアウトの処理の高速化

目次と前回の記事

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

現状の playout の処理の問題点

現状のプレイアウトの処理速度の計測

1 万回のプレイアウトの結果の確認

playout のボトルネック

playout での deepcopy の代替処理

ai_abs_dls の処理の高速化の手法のおさらい

playout で必要となる処理とその実現方法

プレイアウトによって変化する mb の属性の検証

Marubatsu クラスの playout メソッドの定義

処理速度の確認

ゲーム盤を表すクラスの改良

Board クラスの修正

値が変化する属性の一覧

値が変化する属性のデータ型

様々なデータの効率的なコピーと復元処理

1 次元の list のコピーと復元

2 次元の list のコピーと復元

array のコピーと復元

2 次元の ndarray のコピー

1 次元の list をキーの値とする dict

ゲーム盤を表すクラスの修正

ListBoard クラスの save_count と load_count メソッドの定義

ListBoard クラスの修正

List1dBoard クラスの修正

ArrayBoard クラスの修正

NpBoard、NpIntBoard、NpBoolBoard クラスの修正

BitBoard クラスの修正

BitBoard3x3 クラスの修正

TwoBoard3x3 クラスの修正

Marubatsu クラスの playout メソッドの修正

処理の確認と処理速度の計測

今回の記事のまとめ

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

次回の記事

Pythonで〇×ゲームのAIを一から作成する　その233　プレイアウトの処理の高速化

現状の `playout` の処理の問題点

`playout` のボトルネック

`playout` での deepcopy の代替処理

`ai_abs_dls` の処理の高速化の手法のおさらい

`playout` で必要となる処理とその実現方法

プレイアウトによって変化する `mb` の属性の検証

Marubatsu クラスの `playout` メソッドの定義

ListBoard クラスの `save_count` と `load_count` メソッドの定義

Marubatsu クラスの `playout` メソッドの修正