0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その209　スライス表記を利用した List1dBoard クラスの改良

0
Last updated at Posted at 2025-12-29

目次と前回の記事

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

スライス表記を利用した List1dBoard クラスの改良

numpy を利用してゲーム盤を表現する記事を記述している際に、スライス表記 を利用することで count_linemark が False の場合の List1dBoard クラスの 処理速度を改善する方法 を思いつきましたので、今回の記事ではその方法について説明します。

確認のためのゲーム盤のデータの作成

プログラムが 正しく動作するかどうかを確認 するための ゲーム盤のデータ を下記のプログラムで作成します。このプログラムは以前の記事とほぼ同じですが、今回の記事で修正する List1dBoard クラスを利用している点が異なります。

from marubatsu import List1dBoard, Marubatsu

mb = Marubatsu(boardclass=List1dBoard)
mb.cmove(0, 0)
mb.cmove(1, 0)
mb.cmove(0, 1)
mb.cmove(2, 0)
mb.cmove(1, 2)
mb.cmove(1, 1)
mb.cmove(0, 2)
print(mb)

実行結果

winner o
oxx
ox.
Oo.

List1dBoard クラスの benchmark の実行

今回の記事ではこれまでの記事でプログラムを実行してきたパソコンが筆者の都合で利用できないので、別のパソコンでプログラムを実行 しました。そのため、最初に 今回の記事のプログラムを実行するパソコン で下記の List1dBoard クラスの benchmark を実行し、その計測結果と 今回の記事で修正した List1dBoard の benchmark の計測結果と比較 することにします。なお、いつも記事のプログラムを実行する際に使っているパソコンが使えるようになった時点で、この部分は差し替える予定です。

from util import benchmark

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

実行結果

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

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

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

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

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

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

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

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

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

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

スライス表記を利用した勝敗判定の処理の改良

はじめに スライス表記 で 勝敗判定 の 処理速度を改善 する方法について説明します。

is_winner メソッドの処理のおさらい

現状の List1dBoard では count_linemark が False の場合に (x, y) のマスに着手を行った際の 勝敗判定の処理 を is_winner メソッド内の下記のプログラムで行っています。is_winner メソッドについて忘れた方は以前の記事1を復習して下さい。

    # 行と列の判定
    if self.is_same(player, x=0, y=y, dx=1, dy=0) or \
       self.is_same(player, x=x, y=0, dx=0, dy=1):
        return True
    # 左上から右下方向の判定
    if x == y and self.is_same(player, x=0, y=0, dx=1, dy=1):
        return True
    # 右上から左下方向の判定
    if x + y == self.BOARD_SIZE - 1 and \
        self.is_same(player, x=self.BOARD_SIZE - 1, y=0, dx=-1, dy=1):
        return True

上記のプログラムでは (x, y) のマスに着手を行った際の 行、列、対角線方向の直線上 に player のマークが並んでいるか どうかを下記の is_same というメソッドで計算しています。is_same について忘れた方は 以前の記事 と 以前の記事1 を復習して下さい。

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

上記の is_same の 仮引数 は以下の意味を持ちます。

仮引数 意味
x と y 直線の始点の座標
dx と dy 直線上の次のマスの座標との差分

直線上のマークの一覧の計算の性質

is_same メソッドでは、下記の list 内包表記 を利用して、仮引数 x、y、dx、dy で指定 された 直線上のマークを要素として持つ list を計算 しています。

[self.board[y + i * dy + (x + i * dx) * self.BOARD_SIZE] 
            for i in range(self.BOARD_SIZE)]

上記の list 内包表記では、i を 0 から self.BOARD_SIZE - 1 まで 1 つずつ増やしながら、1 次元の list で表現された self.board の y + i * dy + (x + i * dx) * self.BOARD_SIZE のインデックスの 要素を順番に取り出す という処理を行います。

下記は is_winner 内で y 行、x 列、対角線 1 と 22 の直線上に player のマークが並んでいるかどうかを 判定する際 に is_same の 仮引数 x、y、dx と dy に代入する値 と、list 内包表記内の y + i * dy + (x + i * dx) * self.BOARD_SIZE にそれらの 仮引数の値を代入した場合の式 の表です。なお、self.BOARD_SIZE は長いので以後は BSIZE と表記します。

x y dx dy y + i * dy + (x + i * dx) * BSIZE
y 行 0 y 1 0 y + i * BSIZE
x 列 x 0 0 1 i + x * BSIZE
対角線 1 0 0 1 1 i + i * BSIZE
対角線 2 BSIZE - 1 0 -1 1 i + (BSIZE - 1 - i) * BSIZE

下記は上記の list 内包表記内の式 を i を含む部分 と 含まない部分 に分けた表です。

i を含まない式 i を含む式
y 行 y i * BSIZE
x 列 x * BSIZE i * 1
対角線 1 0 i * (1 + BSIZE)
対角線 2 (BSIZE - 1) * BSIZE i * (1 - BSIZE)

上記の表では i を含む式 を i * 値 という 形式で揃えました。そうすることで、i を含む式が すべて i に特定の値を乗算した式 になり、下記の性質を持つ ことがわかります。

  • i が 0 の場合は i を含む式の値は 0 になる
  • i が 1 増える と、i を含む式の値は i に 乗算した値だけ増える

i は 0 から BSIZE - 1 まで 1 ずつ増える ので以下の事がわかります。

  • 最初に計算 される self.board のインデックスは i を含まない式の値 になる
  • 次に計算 するインデックスとの 差分 は i を含む式の中の i に乗算する値 になる
  • 最後に計算 するインデックスは i に BSIZE - 1 を代入した式 の値になる

下記はそのことを表す表です。

最初のインデックス 差分 最後のインデックス
y 行 y BSIZE y + (BSIZE - 1) * BSIZE
x 列 x * BSIZE 1 (x + 1) * BSIZE - 1
対角線 1 0 1 + BSIZE (BSIZE - 1) * (1 + BSIZE)
対角線 2 (BSIZE - 1) * BSIZE 1 - BSIZE BSIZE - 1

なお、対角線 2 の 最後のインデックス は下記の式で計算されます。

(BSIZE - 1) * BSIZE + (BSIZE - 1) * (1 - BSIZE)
= (BSIZE - 1) * (BSIZE + 1 - BSIZE)3
= BSIZE - 1

上記から いずれの直線 の場合も、その直線上のマスを表す self.board のインデックス は、上記の表の 差分の値 で 等間隔に並ぶ ことがわかります。

対角線 2 の計算の順番の変更

List1dBoard クラスでは 仮引数 board_size に代入した 大きさのゲーム盤が作成 されますが、〇× ゲーム のゲーム盤の サイズが 1 の場合 は 1 マスしか存在しない ので 〇 が 着手を行うとゲームが終了してしまい ゲームが成立しません。そこで、以後は ゲーム盤のサイズ を表す BSIZE が 2 以上 であるものとして話を進めます。

ゲーム盤のサイズを表す BSIZE が 2 以上 の場合は y 行、x 列、対角線 1 の 差分 はいずれも明らかに 正の値 になります。一方、対角線 2 の 差分 である 1 - BSIZE は 負の値 になります。この後の話をわかりやすくするため に 対角線 2 の 差分を正の値に変換 して すべての場合の差分 を 正の値に統一 することにします。具体的には以下のように変更することで 対角線 2 のマスの順番 を右上から左下方向から 逆の左下方向から右上方向に変更 します。

  • 最初 のインデックスと 最後 のインデックスを 入れ替える
  • 差分 に -1 を乗算 して 正の値にする

例えば 10 から 0 まで -2 ずつ減らす という 順番をひっくり返す と、0 から 10 まで 2 ずつ増やす という処理になります。直線上に同じマークが並んでいるかどうかの判定 は、直線上のマークの一覧の 順番を逆順にひっくり返しても結果はかわりません。従って、このような処理を行っても 正しい判定を行う ことができます。

下記はそのように上記の表を修正した表で、ゲーム盤のサイズである BSIZE が 2 以上 の場合は すべての差分が正の値 になります。

最初のインデックス 差分 最後のインデックス
y 行 y BSIZE y + (BSIZE - 1) * BSIZE
x 列 x * BSIZE 1 (x + 1) * BSIZE - 1
対角線 1 0 1 + BSIZE (BSIZE - 1) * (1 + BSIZE)
対角線 2 BSIZE - 1 BSIZE - 1 (BSIZE - 1) * BSIZE

スライス表記による直線上の要素を持つ list の計算

以前の記事で説明したように、start のインデックスから end 未満 のインデックスまで step の間隔 で 要素を取り出した新しい list を計算 するという処理は、[start:end:step] という スライス表記で記述 することができます。

ただし、これは step が正の値の場合 で、step が負の値の場合 は start から end より大きいインデックスまで となります。いずれの場合にせよ end が表す要素 は 取り出す要素には含まれません。なお、先程 差分をすべて正の値なるようにした理由 は step を正の値で統一する ことで 行う処理がわかりやすくなる ためです。

先ほど y 行、x 列、対角線 1、2 の要素はいずれも 等間隔で並んだインデックス で表現されることがわかりましたので、それらの要素を取り出した list は スライス表記で計算 することができます。

スライス表記では end の要素は計算されない ので、step が正の場合 は end の部分 には 最後のインデックスよりも大きな整数 を記述する必要があります。具体的には 最後のインデックス に 1 以上、差分以下 の値を 加算した値 を記述します。

end に最後のインデックスに差分より大きな値を加算した値を記述すると、余計な要素が取り出されてしまうことになります。例えば最初のインデックスが 0、最後のインデックスが 10、差分が 5 の場合は end には 10 + 1 = 11 以上、10 + 5 = 15 以下の整数を記述することができます。

下記は end に 10 ~ 16 までの値を記述した場合の表です。表から end に 11 以上 15 以下の整数を記述しなければならないことが確認できます。

スライス表記 取り出される要素
[0:10:5] 0、5
[0:11:5] 0、5、10
[0:12:5] 0、5、10
[0:13:5] 0、5、10
[0:14:5] 0、5、10
[0:15:5] 0、5、10
[0:16:5] 0、5、10、15

end には 最後のインデックスに 1 を加算した値 を記述すれば良いと思う人が多いかもしれませんが、この後で説明する理由から 最後のインデックスに差分を加算した値 を記述することを 考えたほうが良い でしょう。その理由を説明します。

下記は最後のインデックスに 1 を加算 した場合と 差分を加算 した場合の表です。

1 を加算した式 差分を加算した式
y 行 y + (BSIZE - 1) * BSIZE + 1 y + BSIZE * BSIZE
x 列 (x + 1) * BSIZE (x + 1) * BSIZE
対角線 1 BSIZE * BSIZE BSIZE * (BSIZE + 1)
対角線 2 (BSIZE - 1) * BSIZE + 1 (BSIZE - 1) * (BSIZE + 1)

どちらの場合の式も複雑さはあまり変わらないように見えるかもしれませんが、以下の スライス表記の性質 を利用することで、差分を加算した式を利用 したほうが スライス表記をより簡潔に記述 できます。

  • end を省略した場合 は以下のようになる
    • step が正の場合 は 最後の要素まで を表す
    • step が負の場合 は 先頭の要素まで を表す
  • start や end に 負の値である -i を記述した場合 は 最後の要素から先頭の要素に向かって数えた i - 1 番目の要素 を表す。例えば最後の要素は -1 で、その前の要素は -2 で指定できる。別の言葉で説明すると、要素の数が len の場合は len - i のインデックスの要素を -i を記述することで 指定できる

ゲーム盤のマスの数 は BSIZE * BSIZE なので、ゲーム盤を表す 1 次元の list の 要素の数も BSIZE * BSIZE となります。従って、end の部分 は 差分を加算した式の値 によって 以下のように記述 することができます。

  • BSIZE * BSIZE 以上 の場合は 実際には存在しない 最後の要素よりも後のインデックスを表すので end を省略 して最後の要素までを指定しても 同じ計算が行われる
  • BSIZE * BSIZE - i のように記述できる場合は -i を記述 できる

具体的には y 行 と 対角線 1、2 の 差分を加算した式 は以下の表のような性質を持つので end には 下記の表のように簡潔に記述 することができます。なお、x 列 の場合は 差分を加算した式をそのまま記述すれば良い でしょう。

差分を足した式 end に記述する内容
y 行 y + BSIZE * BSIZE ≧ BSIZE * BSIZE
（y ≧ 0 なので）		 省略する
対角線 1 BSIZE * (BSIZE + 1)
= BSIZE * BSIZE + BSIZE ≧ BSIZE * BSIZE
（BSIZE ≧ 2 なので）		 省略する
対角線 2 (BSIZE - 1) * (BSIZE + 1)
= BSIZE * BSIZE - 1 		-1

上記から それぞれの直線上のマスを表す list は 以下のスライス表記で計算 できます。なお、step が 1 の場合と start が 0 の場合 は 省略できる ので省略しました。

スライス表記 補足
y 行 [y::BSIZE] end は省略した
x 列 [x * BSIZE:(x + 1) * BSIZE] step は 1 なので省略した
対角線 1 [::BSIZE + 1] end は省略した
対角線 2 [BSIZE - 1:-1:BSIZE - 1]

下記は 0 行、0 列、対角線 1、対角線 2 を表す list を上記の スライス表記で計算 するプログラムです。実行結果から 正しい計算が行われてることが確認 できます。対角線 2 は左下から右上方向 である点に注意して下さい。

print(mb)
x = 0
y = 0
print(mb.board.board[y::mb.BOARD_SIZE])
print(mb.board.board[x:(x + 1) * mb.BOARD_SIZE])
print(mb.board.board[::mb.BOARD_SIZE + 1])
print(mb.board.board[mb.BOARD_SIZE - 1:-1:mb.BOARD_SIZE - 1])

実行結果（# のコメントは筆者が追記したものです）

winner o
oxx
ox.
Oo.

['o', 'x', 'x']  # 0 行
['o', 'o', 'o']  # 0 列
['o', 'x', '.']  # 対角線 1
['o', 'x', 'x']  # 対角線 2

図での確認

式の説明だけではわかりづらい人もいるかもしれないので、図で説明 します。下図は 1 次元の list でゲーム盤を表現した場合の、各マスのインデックス を表す図です。

図から それぞれの直線上のマスのインデックスの差分 が以下の表のように、先程の検証結果と同じになる ことが確認できます。また、対角線 2 に関しては 6 の次の差分である 8 が 最後の要素になる ので、end を省略 すると 8 のマスも含まれてしまう ことになるため end に -1 を記述する必要がある ことも確認できます。

差分
行 0、3、6 のようにゲーム盤のサイズと同じ 3 ずつ増える
列 0、1、2 のように 1 ずつ増える
対角線 1 0、4、8 のように「ゲーム盤のサイズ + 1 = 4」ずつ増える
対角線 2 2、4、6 のように「ゲーム盤のサイズ - 1 = 2」ずつ増える

処理速度の違いの検証

下記のプログラムで これまでの方法 と スライス表記 で 0 列を表す list を計算 する処理の 処理時間を計測 します。なお、3 行目の print はこれまでの方法で正しく 0 列が計算されているかを 確認するための表示 です。実行結果から スライス表記 のほうが 処理速度が約 3 倍になる ことが確認できました。興味がある方は行や対角線でも計測して下さい。

dx = 0
dy = 1
print([mb.board.board[y + i * dy + (x + i * dx) * mb.BOARD_SIZE] for i in range(mb.BOARD_SIZE)])
%timeit [mb.board.board[y + i * dy + (x + i * dx) * mb.BOARD_SIZE] for i in range(mb.BOARD_SIZE)]
%timeit mb.board.board[x:(x + 1) * mb.BOARD_SIZE]

実行結果

['o', 'o', 'o']
391 ns ± 11.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
121 ns ± 1 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

is_winner メソッドの修正

下記は上記の方法で計算を行うように is_winner メソッドを修正 したプログラムです。修正前は is_same で計算を行っていましたが、その処理はスライス表記で 1 行で行える ので is_winner の中で行う ようにし、is_same メソッドは廃止 することにします。また、player が勝利した場合 に "".join で計算される文字列を最初に計算 するようにしました。

  • 6 行目：player が勝利した場合の文字列を計算する
  • 8、9、12、15、16：上記で説明した方法で各直線上のマークを表す list を計算するように修正し、"".join で計算した値と 6 行目で計算した文字列と比較するように修正した
 1  def is_winner(self, player, last_move):
 2      x, y = last_move // self.BOARD_SIZE, last_move % self.BOARD_SIZE
 3      if self.count_linemark:
 4          元と同じなので省略
 5      else:
 6          winstr = player * self.BOARD_SIZE
 7          # 行と列の判定
 8          if "".join(self.board[y::self.BOARD_SIZE]) == winstr or \
 9             "".join(self.board[x * self.BOARD_SIZE:(x + 1) * self.BOARD_SIZE]) == winstr:
10                  return True
11          # 左上から右下方向の判定
12          if x == y and "".join(self.board[::self.BOARD_SIZE + 1]) == winstr:
13              return True
14          # 左下から右上方向の判定
15          if x + y == self.BOARD_SIZE - 1 and \
16              "".join(self.board[self.BOARD_SIZE - 1:-1:self.BOARD_SIZE - 1]) == winstr:
17              return True
18  
19      # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
20      return False  
21  
22  List1dBoard.is_winner = is_winner
行番号のないプログラム 
def is_winner(self, player, last_move):
    x, y = last_move // self.BOARD_SIZE, last_move % self.BOARD_SIZE
    if self.count_linemark:
        if self.rowcount[player][y] == self.BOARD_SIZE or \
        self.colcount[player][x] == self.BOARD_SIZE:
            return True
        # 左上から右下方向の判定
        if x == y and self.diacount[player][0] == self.BOARD_SIZE:
            return True
        # 右上から左下方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            self.diacount[player][1] == self.BOARD_SIZE:
            return True
    else:
        winstr = player * self.BOARD_SIZE
        # 行と列の判定
        if "".join(self.board[y::self.BOARD_SIZE]) == winstr or \
           "".join(self.board[x * self.BOARD_SIZE:(x + 1) * self.BOARD_SIZE]) == winstr:
                return True
        # 左上から右下方向の判定
        if x == y and "".join(self.board[::self.BOARD_SIZE + 1]) == winstr:
            return True
        # 左下から右上方向の判定
        if x + y == self.BOARD_SIZE - 1 and \
            "".join(self.board[self.BOARD_SIZE - 1:-1:self.BOARD_SIZE - 1]) == winstr:
            return True
    
    # どの一直線上にも配置されていない場合は、player は勝利していないので False を返す
    return False  

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

List1dBoard.is_winner = is_winner

上記の処理速度の確認などは後でまとめて行います。

スライス表記を利用した同一局面の計算の改良

同一局面のハッシュ可能な値 を計算する calc_same_hashables も スライス表記を利用 して 処理速度を向上 することができます。その方法について少し考えてみて下さい。

List1dBoard クラスの calc_same_hashables では 8 種類の同一局面 を 個別に計算 していますが、以前の記事で説明したように 同一局面の計算 は局面を 時計回りに 90 度回転 する処理と、局面を 上下に反転する処理 で行うことができます。そこで、そのような処理を行う下記の NpBoard クラスの calc_same_hashables を修正 して List1dBoard クラスの calc_same_hashables を定義 することにします。

   def calc_same_hashables(self, move=None):
        if move is None:
            hashables = set([self.board_to_hashable()])
        else:
            hashables = { self.board_to_hashable(): move }
        boardorig = self.board
        if move is not None:
            x, y = self.move_to_xy(move)
        for i in range(7):
            if i != 3:
                self.board = np.rot90(self.board)
            else:
                self.board = np.fliplr(self.board)
            hashable = self.board_to_hashable()
            if move is None:
                hashables.add(hashable)
            else:
                if i == 3:
                    y = self.BOARD_SIZE - y - 1
                else:
                    x, y = self.BOARD_SIZE - y - 1, x
                hashables[hashable] = self.xy_to_move(x, y)
        self.board = boardorig
        return hashables

上記のプログラムで 回転処理は下記の 2 行目、反転処理は下記の 4 行目 で行っているので、修正する部分はこの 2 行だけ です。なお、上記のプログラムでは 反転処理 を 2 次元の ndarry の 左右を反転する np.fliplr で行っていますが、ゲーム盤を表す 2 次元の ndarray は print で ndarray を表示した場合と異なり axis 0 が左右方向、axis 1 が上下方向 を表すので np.fliplr では 上下方向にゲーム盤が反転 する点に注意が必要です。

1           if i != 3:
2               self.board = np.rot90(self.board)
3           else:
4               self.board = np.fliplr(self.board)

スライス表記を利用した回転処理

下図は 〇× ゲームのゲーム盤を 時計回りに 90 度回転 させた場合の図で、マスの中の数値 はそのマスが記録された 回転前 の 1 次元の list の インデックス を表します。

この図から 赤枠 の 回転後の 0 列 には 回転前 の 1 次元の list の 赤枠 の 2、5、8 のインデックスの要素が順番に並ぶ ことが確認できます。これは 回転前 の 1 次元の list の 2 行のマス を表します。同様に 回転後の 1 列 には 回転前の 1 行 の、回転後の 2 列 には 回転前の 0 行 のマスが並びます。このことを一般化すると、「回転後の i 列 には 回転前の BSIZE - 1 - i 行 のマスが並ぶ」のようになります。

1 次元の list には 0 列、1 列、2 列の順 でマスのデータを記録するので、1 次元の list で表現されたゲーム盤を 時計回りに 90 度回転 する処理は 下記のプログラムで計算 できます。

なお、回転前の局面のデータを記録 し、最後に 回転前の局面に戻している のは、回転前の局面でこの後も処理を行うから です。

  • 3 行目：後で戻せるように回転前の局面のデータを deepcopy でコピーして記録しておく
  • 4 行目：正しく回転されることを確認できるように元のゲーム盤を表示する
  • 5 行目：回転後の 1 次元の list を計算する変数を空の list で初期化する
  • 6、7 行目：回転後の各列の要素を上記で説明した方法でスライス表記で計算し、+ 演算子で rotboard に連結することで回転後の list を計算する
  • 8、9 行目：mb.board.board に回転後の list を代入し、print(mb) で回転後のゲーム盤を表示する
  • 10 行目：ゲーム盤のデータを回転前の局面に戻す
 1  from copy import deepcopy
 2  
 3  boardorig = deepcopy(mb.board.board)
 4  print(mb)
 5  rotboard = []
 6  for i in range(mb.BOARD_SIZE):
 7      rotboard += mb.board.board[mb.BOARD_SIZE - 1 - i::mb.BOARD_SIZE]
 8  mb.board.board = rotboard
 9  print(mb)
10  mb.board.board = boardorig
行番号のないプログラム 
from copy import deepcopy

boardorig = deepcopy(mb.board.board)
print(mb)
rotboard = []
for i in range(mb.BOARD_SIZE):
    rotboard += mb.board.board[mb.BOARD_SIZE - 1 - i::mb.BOARD_SIZE]
mb.board.board = rotboard
print(mb)
mb.board.board = boardorig

実行結果

winner o
oxx
ox.
Oo.

winner o
ooo
oxx
..x

上記の実行結果から 正しく回転できていることが確認 できます。

スライス表記を利用した上下の反転処理

上下の反転処理 の場合は、反転後の i 列 には 反転前の i 列の順番を逆 にしたものになります。なお、特に難しい点はないと思いましたので図は省略します。

i 列の要素の順番を逆 にするという処理は start に i 列の最後のインデックス、end に i 列の最初のインデックス - 1、step に -1 を記述した スライス表記で計算 することができ、i 列 の 最初のインデックス と 最後のインデックス は下記の表の式で計算できます。

なお、step が負の場合も end に記述されたインデックスの 要素は計算されない ので、差分を表す 1 を引く必要がある 点に注意が必要です。

最初のインデックス 最後のインデックス
i * BSIZE (i + 1) * BSIZE - 1

従って、各列の順番を逆にした list は下記のプログラムで計算できるはずですが、実行結果のように 1 列と 2 列は正しい計算 が行われますが、0 列だけは空の list が計算されてしまう という問題が発生します。

print(mb)
for i in range(mb.BOARD_SIZE):
    print(mb.board.board[(i + 1) * mb.BOARD_SIZE - 1:i * mb.BOARD_SIZE - 1:-1])

実行結果

winner o
oxx
ox.
Oo.

[]
['o', 'x', 'x']
['.', '.', 'x']

このようなことが起きる原因は、0 列の場合の end が 0 * mb.BOARD_SIZE - 1 = -1 のように 負の値が計算 されてしまうためです。具体的には 0 列の場合 は [2:-1:-1] というスライス表記で計算が行われますが、end の -1 はインデックスが 8 の最後の要素 を表すので、[2:8:-1] というスライス表記の計算が行われます。2 から 8 まで -1 ずつ インデックスを加算しながら 要素を取り出すことはできない ので、結果として 空の list が計算 されます。

end の値を省略せず に 先頭の要素までを指定 する場合は end に None を記述 します。下記は 0 列のみ end に None を指定 するように修正したプログラムで、実行結果から 0 列でも正しく計算が行われることが確認 できます。

  • 3 行目：start を計算する
  • 4 行目：i が 0 の場合は None を計算するように end を計算する。end は start から BSIZE を引いた値なので、そのように計算した
  • 5 行目：上記で計算した start と end を利用して i 列の逆順の list を計算する
1  print(mb)
2  for i in range(mb.BOARD_SIZE):
3      start = (i + 1) * mb.BOARD_SIZE - 1
4      end = start - mb.BOARD_SIZE if i > 0 else None
5      print(mb.board.board[start:end:-1])
行番号のないプログラム 
print(mb)
for i in range(mb.BOARD_SIZE):
    start = (i + 1) * mb.BOARD_SIZE - 1
    end = start - mb.BOARD_SIZE if i > 0 else None
    print(mb.board.board[start:end:-1])
修正箇所 
print(mb)
for i in range(mb.BOARD_SIZE):
+   start = (i + 1) * mb.BOARD_SIZE - 1
+   end = start - mb.BOARD_SIZE if i > 0 else None
-   print(mb.board.board[(i + 1) * mb.BOARD_SIZE - 1:i * mb.BOARD_SIZE - 1:-1])
+   print(mb.board.board[start:end:-1])

実行結果

winner o
oxx
ox.
Oo.

['o', 'o', 'o']
['o', 'x', 'x']
['.', '.', 'x']

下記は上記の手順で mb の局面の上下を反転 するプログラムで、実行結果から 正しく上下が反転することが確認 できます。行う処理は回転の場合と同様なので説明は省略します。

boardorig = deepcopy(mb.board.board)
print(mb)
flipboard = []
for i in range(mb.BOARD_SIZE):
    start = (i + 1) * mb.BOARD_SIZE - 1
    end = start - mb.BOARD_SIZE if i > 0 else None    
    flipboard += mb.board.board[start:end:-1]
mb.board.board = flipboard
print(mb)
mb.board.board = boardorig

実行結果

winner o
oxx
ox.
Oo.

winner o
oo.
ox.
Oxx

詳細は省略しますが、list などの列挙可能なオブジェクトの要素の順番を逆にしたイテレータを返す reversed という組み込み関数を利用するという方法もあります。ただし、reversed が返す値は list ではなくイテレータと呼ばれるものなので、逆順の list を計算するためには下記のプログラムのように list の実引数に記述する必要があります。

a = [1, 2, 3]
print(reversed(a))
print(list(reversed(a)))

実行結果

<list_reverseiterator object at 0x000002694DBBB3A0>
[3, 2, 1]

また、list にはその要素を逆順にする reverse というメソッドがあります。ただし、下記のプログラムの実行結果のように reverse メソッドの返り値は None になる点に注意して下さい。

print(a)
print(a.reverse())
print(a)

実行結果

[1, 2, 3]
None
[3, 2, 1]

興味と余裕がある方は reversed や reverse メソッドを利用した上下の反転処理を実装してみて下さい。

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

calc_same_hashables2 の定義

下記は上記の手順で計算を行うように calc_same_hashabls2 を定義 するプログラムです。これまでの calc_same_hashables の実行結果と比較することで プログラムが正しく計算できることを確認する ために calc_same_hashabls2 という名前で定義し、正しい計算が行われることを確認できた後 で calc_same_hashabls という名前で定義し直す ことにします。

  • 3 ~ 14 行目：上記の方法で回転と反転処理を行うように修正した
 1  def calc_same_hashables2(self, move=None):
元と同じなので省略
 2      for i in range(7):
 3          if i != 3:
 4              rotboard = []
 5              for i in range(self.BOARD_SIZE):
 6                  rotboard += self.board[self.BOARD_SIZE - 1 - i::self.BOARD_SIZE]
 7              self.board = rotboard
 8          else:
 9              flipboard = []
10              for i in range(self.BOARD_SIZE):
11                  start = (i + 1) * self.BOARD_SIZE - 1
12                  end = start - self.BOARD_SIZE if i > 0 else None  
13                  flipboard += self.board[start:end:-1]
14              self.board = flipboard
元と同じなので省略
15  
16  List1dBoard.calc_same_hashables2 = calc_same_hashables2
行番号のないプログラム 
def calc_same_hashables2(self, move=None):
    if move is None:
        hashables = set([self.board_to_hashable()])
    else:
        hashables = { self.board_to_hashable(): move }
    boardorig = self.board
    if move is not None:
        x, y = self.move_to_xy(move)
    for i in range(7):
        if i != 3:
            rotboard = []
            for i in range(self.BOARD_SIZE):
                rotboard += self.board[self.BOARD_SIZE - 1 - i::self.BOARD_SIZE]
            self.board = rotboard
        else:
            flipboard = []
            for i in range(self.BOARD_SIZE):
                start = (i + 1) * self.BOARD_SIZE - 1
                end = start - self.BOARD_SIZE if i > 0 else None  
                flipboard += self.board[start:end:-1]
            self.board = flipboard
        hashable = self.board_to_hashable()
        if move is None:
            hashables.add(hashable)
        else:
            if i == 3:
                y = self.BOARD_SIZE - y - 1
            else:
                x, y = self.BOARD_SIZE - y - 1, x
            hashables[hashable] = self.xy_to_move(x, y)
    self.board = boardorig
    return hashables

List1dBoard.calc_same_hashables2 = calc_same_hashables2
修正箇所 
def calc_same_hashables2(self, move=None):
元と同じなので省略
    for i in range(7):
        if i != 3:
-           self.board = np.rot90(self.board)
+           rotboard = []
+           for i in range(self.BOARD_SIZE):
+               rotboard += self.board[self.BOARD_SIZE - 1 - i::self.BOARD_SIZE]
+           self.board = rotboard
        else:
-           self.board = np.fliplr(self.board)
+           flipboard = []
+           for i in range(self.BOARD_SIZE):
+               start = (i + 1) * self.BOARD_SIZE - 1
+               end = None if i == 0 else start - self.BOARD_SIZE
+               flipboard += self.board[start:end:-1]
+           self.board = flipboard
元と同じなので省略

List1dBoard.calc_same_hashables2 = calc_same_hashables2

上記の修正後に、下記のプログラムで mb の局面 に対して 元の calc_same_hashables と上記の calc_same_hashables2 が同じ処理を行うことを確認 します。仮引数 move には (0, 0) の座標を代入 しました。また、dict が同じキーとキーの値を持つこと は == 演算子の結果が True であるかどうかで 判定する ことができます。実行結果から == 演算子の結果が True になる ことから 同一のデータが計算されていることが確認 できます。

from pprint import pprint

move = mb.board.xy_to_move(0, 0)
h1 = mb.board.calc_same_hashables(move)
h2 = mb.board.calc_same_hashables2(move)
print(h1)
print(h2)
print(h1 == h2)

実行結果

{'..xoxxooo': 8,
 '.oo.xoxxo': 8,
 'oo.ox.oxx': 6,
 'ooooxx..x': 2,
 'oooxxox..': 0,
 'oxxox.oo.': 0,
 'x..xxoooo': 6,
 'xxo.xo.oo': 2}
{'..xoxxooo': 8,
 '.oo.xoxxo': 8,
 'oo.ox.oxx': 6,
 'ooooxx..x': 2,
 'oooxxox..': 0,
 'oxxox.oo.': 0,
 'x..xxoooo': 6,
 'xxo.xo.oo': 2}
True

下記は 両者の処理速度を計測 するプログラムです。実行結果から スライス表記 を利用したほうが 処理速度が約 3 倍 になることが確認できました。

%timeit mb.board.calc_same_hashables(move)
%timeit mb.board.calc_same_hashables2(move)

実行結果

21.1 μs ± 505 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
8.07 μs ± 32.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

正しく動作することが確認できたので、下記のプログラムで calc_same_hashables という名前で定義しなおす ことにします。プログラムは同じなので折りたたみました。

プログラム 
def calc_same_hashables(self, move=None):
    if move is None:
        hashables = set([self.board_to_hashable()])
    else:
        hashables = { self.board_to_hashable(): move }
    boardorig = self.board
    if move is not None:
        x, y = self.move_to_xy(move)
    for i in range(7):
        if i != 3:
            rotboard = []
            for i in range(self.BOARD_SIZE):
                rotboard += self.board[self.BOARD_SIZE - 1 - i::self.BOARD_SIZE]
            self.board = rotboard
        else:
            flipboard = []
            for i in range(self.BOARD_SIZE):
                start = (i + 1) * self.BOARD_SIZE - 1
                end = start - self.BOARD_SIZE if i > 0 else None  
                flipboard += self.board[start:end:-1]
            self.board = flipboard
        hashable = self.board_to_hashable()
        if move is None:
            hashables.add(hashable)
        else:
            if i == 3:
                y = self.BOARD_SIZE - y - 1
            else:
                x, y = self.BOARD_SIZE - y - 1, x
            hashables[hashable] = self.xy_to_move(x, y)
    self.board = boardorig
    return hashables

List1dBoard.calc_same_hashables = calc_same_hashables

ベンチマークの実行

下記のプログラムで List1dBoard の処理速度 を benchmark 計測 します。

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

実行結果

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

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

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

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

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

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

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

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

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

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

下記は今回の記事の最初で行った 修正前の List1dBoard クラスの benchmark の結果に上記の 修正後の実行結果を加えた表 です。

count_linemark ai2 VS ai2 ai14s VS ai2 ai_abs_dls
修正前 False 18942.59 回/秒 1664.46 回/秒 18.2 ms
修正後 False 24249.15 回/秒 1843.54 回/秒 8.7 ms
修正前 True 17171.76 回/秒 2814.81 回/秒 17.8 ms
修正後 True 18801.86 回/秒 2890.13 回/秒 10.1 ms

上記の表から以下の事が確認できます。

  • count_linemark が False の場合は いずれの場合 も 修正後のほうが処理速度が向上 する
  • count_linemark が True の場合は 今回の修正の影響を受けない ので ai2 VS ai2 と ai14s VS ai2 の処理速度は 修正前と後でほとんど変わらない
  • calc_same_hashables を多用する ai_abs_dls ではいずれの場合でも ai_abs_dls の処理速度が約 2 倍 になり、count_linemark が False の方が処理速度が速く なる
  • ai2 VS ai2 の対戦では、count_linemark が False のほう が 処理時間が大幅に高速になる が、今回の記事で修正を行っていない count_markpats を呼び出す ai14s VS ai2 の対戦では count_linemark が True のほうが 処理速度が速く なる

今回の記事のまとめ

今回の記事ではスライス表記を利用した List1dBoard クラスの改良を行いました。また、スライス表記を利用 することで実際に List1dBoard クラスの処理速度が向上 し、その結果 ai14s VS ai2 以外 の場合は count_linemark が False の方が処理速度が速くなる ことが確認できました。

今回の記事で説明した スライス表記を利用する方法 は 2 次元の list でゲーム盤を表現する場合は 利用できません。そのため、2 次元の list と 1 次元の list でゲーム盤を表現した場合を比較すると、わかりやすさの点では 2 次元の list のほうが優位になりますが、処理速度の面では 1 次元の list のほうが 優位である ことがわかります。

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

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

次回の記事

  1. 以前の記事では is_same の実引数に記述する、直線上の最初のマスの座標を tuple で記述していている点が異なりますが、行われる処理の内容は現在のプログラムと同じです ↩ ↩2

  2. 対角線 1 は左上から右下方向、対角線 2 は右上から左下方向の対角線です ↩

  3. $x × y + x × z = x × (y + z)$ という公式を当てはめました ↩

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?