0
0

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を一から作成する　その223　一つのビット列で表現されたゲーム盤の合法手の一覧の計算と反転・転置処理

0
Last updated at Posted at 2026-04-12

目次と前回の記事

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

TwoBitBoard3x3 クラスの calc_legal_moves の定義

今回の記事では前回の記事で定義を開始した TwoBitBoard3x3 クラスの 残りのメソッドの定義 を行います。

最初に ai2 VS ai2 の対戦を行う際に必要となる、合法手の一覧を計算 する calc_legal_moves メソッドの定義を行います。どのように合法手の一覧を計算すればよいかについて少し考えてみて下さい。

マークが配置されているマスを表すビット列の計算

以前の記事で説明したように、BitBoard クラスでは 〇 と × の ビットボード の OR 演算 を行うことで、マークが配置されているマス を表す ビットボードを計算 しました。

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = self.board[0] | self.board[1]
略

TwoBitBoard3x3 クラスでは 同じマス を表す 〇 と × のビットが並んで配置 されているので、以下の手順で 上記と同様の計算 を行うことができます。

  1. self.board を 右シフト演算 で 1 ビット右にずらした self.board >> 1 を計算するこで、× のビット が 同じマス の 〇 の ビットの位置に移動 した ビット列が計算 される
  2. 上記で計算した値と self.board との OR 演算 を行う self.board | (self.board >> 1) を計算することで、〇 のマスを表すビット にそのマスに マークが配置されている場合は 1 が、配置されていない場合は 0 が計算される
  3. × のマスを表すビット には 必要のない値が計算 されているので 〇 を表すマスのビットだけが 1 である 0b010101010101010101 との AND 演算 を行うことで、× のマスを表すビット に 0 が、〇 のマスを表すビット にそのマスに マークが配置されているかどうか を表す ビット列が計算 される

下図は 上記の手順で計算 を行う場合の 具体例 を表します。図の マスの色 は以下の表のような意味を持ちます。

色 意味
水色 〇 のマスを表すビット
黄色 × のマスを表すビット
緑色 マスにマークが存在することを表すビット
灰色 最終的な計算結果に影響を与えないビット
紫色 〇 のマスを表すビットが 1 となるビットマスクの 1 となるビット
白色 必ず 0 となるビット

手順 1 では図の最上部のビット列を 1 ビット右シフト演算 することで、黄色 の × のマスを表すビット が同じマスの 〇 を表すビットの位置にずれます。

手順 2 では上部の 2 つのビット列の OR 演算 を行うことで、緑色のビット にそのマスに マークが存在する場合に 1、存在しない場合に 0 が計算されます。また、それ以外の白と灰色 のビットに計算された値は 最終的な計算結果に影響を及ぼしません。

手順 3 では 緑色と同じ場所 のビットだけが 1 となるビットマスク との AND 演算 を行うことで、× を表すビットに 0 が、〇 を表すビット にそのマスに マークが存在するかどうか を表す ビット列が計算 されます。

マークが配置されていないマスを表すビット列の計算手順

合法手 は マークが配置されていないマスの一覧 なので、上記で計算したビット列から マークが配置されていないマスを表すビット列を計算 する必要があります。BitBoard クラスの場合は下記のプログラムのように すべてのマスのビットを 1 としたビット列から 上記のビット列を引き算1 することで その値を求めました。

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = self.board[0] | self.board[1]
    # 空のマスのビットが 1 になるビットボードを計算する
    board = 0b111111111 - board
略

TwoBitBoard3x3 クラスの場合は 〇 を表すビット にそのマスに マークが存在するかどうか を表す ビット列が計算 されるので、下図のように 〇 を表すマスのビットが 1 である 0b010101010101010101 から 引き算 を行うことで、〇 を表すオレンジ色のマスのビット に マークが配置されていない場合は 1 が、配置されている場合は 0 となる ビット列が計算 されます。

前回の記事で説明したように、TwoBitBoard3x3 の座標 は同じマスであっても 〇 の手番と × の手番で異なります。そのため、合法手を計算する場合 は 〇 の手番の場合 は 上図のビット列を元に計算 すれば良いのですが、× の手番の場合 は上図で計算されたビット列を 1 ビット左シフト演算 してずらす必要があります。

上記で計算したビット列から 合法手を一つずつ計算する方法 は、以前の記事で説明した BitBoard クラスの場合と同じ なので忘れた方は復習して下さい。

calc_legal_moves の定義

下記は上記の手順で 合法手の一覧を計算 する calc_legal_moves メソッドの定義です。なお、修正箇所は BitBoard3x3 クラスからの修正です。

  • 5 ~ 9 行目：上記で説明した方法でマークが配置されていないマスを表すビット列を計算する。× の手番の場合は 8、9 行目で 1 ビット左にずらす
  • 10 行目以降の処理は BitBoard クラスの処理と同じ
 1  from marubatsu import TwoBitBoard3x3
 2  
 3  def calc_legal_moves(self):
 4      # マークが配置されているマスのビットが 1 になるビットボードを計算する
 5      board = 0b010101010101010101 & (self.board | (self.board >> 1))
 6      # 空のマスのビットが 1 になるビットボードを計算する   
 7      board = 0b010101010101010101 - board
 8      if self.crossturn:
 9          board <<= 1
10      legal_moves = []
11      # board が 0 になるまで繰り返し処理を行う
12      while board:
13          # 次の合法手である LOB を計算する
14          move = board & (-board)
15          legal_moves.append(move)
16          # board の RSB を 0 にして move のデータを削除する
17          board -= move
18  
19      return legal_moves
20  
21  TwoBitBoard3x3.calc_legal_moves = calc_legal_moves
行番号のないプログラム 
from marubatsu import TwoBitBoard3x3

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
    board = 0b010101010101010101 & (self.board | (self.board >> 1))
    # 空のマスのビットが 1 になるビットボードを計算する   
    board = 0b010101010101010101 - board
    if self.crossturn:
        board <<= 1
    legal_moves = []
    # board が 0 になるまで繰り返し処理を行う
    while board:
        # 次の合法手である LOB を計算する
        move = board & (-board)
        legal_moves.append(move)
        # board の RSB を 0 にして move のデータを削除する
        board -= move

    return legal_moves

TwoBitBoard3x3.calc_legal_moves = calc_legal_moves
修正箇所 
from marubatsu import TwoBitBoard3x3

def calc_legal_moves(self):
    # マークが配置されているマスのビットが 1 になるビットボードを計算する
-   board = self.board[0] | self.board[1]
+   board = 0b010101010101010101 & (self.board | (self.board >> 1))
    # 空のマスのビットが 1 になるビットボードを計算する
-   board = 0b111111111 - board
-   board = 0b010101010101010101 - board
+   if self.crossturn:
+       board <<= 1
    legal_moves = []
    # board が 0 になるまで繰り返し処理を行う
    while board:
        # 次の合法手である LOB を計算する
        move = board & (-board)
        legal_moves.append(move)
        # board の RSB を 0 にして move のデータを削除する
        board -= move

    return legal_moves

TwoBitBoard3x3.calc_legal_moves = calc_legal_moves

上記の定義後に、下記のプログラムで 〇 の手番 である ゲーム開始時の局面 と、× の手番 である (0, 0) にマークを配置 した場合の局面の 合法手の一覧 を calc_legal_moves メソッドで計算すると、実行結果から正しい処理が行われることが確認 できました。

from marubatsu import Marubatsu

mb = Marubatsu(boardclass = TwoBitBoard3x3)
print(mb)
for move in mb.calc_legal_moves():
    print(mb.board.move_to_xy(move))
print()
mb.cmove(0, 0)
print(mb)
for move in mb.calc_legal_moves():
    print(mb.board.move_to_xy(move))

実行結果

Turn o
...
...
...

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

Turn x
O..
...
...

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

処理時間の比較

下記のプログラムで 0 ~ 8 回の着手 を行った それぞれの局面 に対して BitBoard3x3 と TwoBitBoard3x3 クラスの calc_legal_moves の 処理時間を計測して比較 します。

from marubatsu import BitBoard3x3

mb1 = Marubatsu(boardclass=BitBoard3x3)
mb2 = Marubatsu(boardclass=TwoBitBoard3x3)
print(mb1)
%timeit mb1.calc_legal_moves()
%timeit mb2.calc_legal_moves()
for x, y in [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 1), (2, 0)]:
    mb1.cmove(x, y)
    mb2.cmove(x, y)
    print(mb1)
    %timeit mb1.calc_legal_moves()
    %timeit mb2.calc_legal_moves()

実行結果

Turn o
...
...
...

955 ns ± 17.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.06 μs ± 4.85 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn x
O..
...
...

858 ns ± 4.01 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.05 μs ± 6.37 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn o
o..
X..
...

781 ns ± 5.11 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
880 ns ± 14.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn x
o..
x..
O..

692 ns ± 4.27 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
882 ns ± 4.34 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn o
oX.
x..
o..

624 ns ± 5.46 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
736 ns ± 6.73 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn x
ox.
xO.
o..

524 ns ± 2.01 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
720 ns ± 7.34 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn o
ox.
xo.
oX.

437 ns ± 2.21 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
597 ns ± 8.48 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn x
ox.
xoO
ox.

361 ns ± 2.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
550 ns ± 1.85 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
Turn o
oxX
xoo
ox.

280 ns ± 1.22 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
393 ns ± 1.16 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は 上記の実行結果をまとめた表 です。実行結果から いずれの場合 も 着手回数が増えると合法手の数が少なくなる ので 処理時間が短くなる ことが確認できます。また、BitBoard3x3 クラスの方が 処理速度が若干速い ことが確認できます。これは、マークが配置されていないことを表すビット列の計算 が BitBoard3x3 クラスの方が単純 であることと、TwoBitBoard3x3 クラスのほうが計算する際の ビット列の長さが長いことが原因 です。

着手回数 BitBoard3x3 TwoBitBoard3x3
0 955 ns 1060 ns
1 858 ns 1050 ns
2 781 ns 880 ns
3 692 ns 882 ns
4 624 ns 736 ns
5 524 ns 720 ns
6 437 ns 597 ns
7 361 ns 550 ns
8 280 ns 393 ns

ai2 VS ai2 の対戦による確認

calc_legal_moves が 正しい処理を行うこと を、下記のプログラムで ai2 VS ai2 の対戦を行うことで確認 することにします2。なお、ai14s の処理に必要 となる count_markpats はまだ実装していない ので、ai14s VS ai2 の対戦を行う benchmark はまだ利用することはできません。対戦成績 が 以前の記事 と 同じになる ことから、calc_legal_moves が 正しい処理を行うことが確認 できました。

from ai import ai_match, ai2
import random

random.seed(0)
ai_match(ai=[ai2, ai2], mbparams={"boardclass": TwoBitBoard3x3}, match_num=50000)

実行結果

ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21945.68it/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%

下記は 上記の実行結果 と BitBoard3x3 の ai2 VS ai2 の処理時間 をまとめた表です。下記から TwoBitBoard3x3 クラスの方が処理速度が約 10 % 程遅い ことが確認できました。これは先ほど確認したように calc_legal_moves の処理が TwoBitBoard3x3 クラスの方が遅い ことが主な原因ではないかと思われます。

ai2 VS ai2
BitBoard3x3 24220.47 回/秒
TwoBitBoard3x3 21945.68 回/秒

count_markpats メソッドの定義

次に、ai14s の処理で必要となる count_markpats メソッドを定義します。

BitBoard3x3 クラスでは masklist という クラス属性 に 各直線上のマスのビットを 1 とする ビットマスクの一覧 と、ptable という クラス属性 に ビット長が 9 まで の ビット列の popcount3 をあらかじめ計算した 参照テーブルを利用 してその計算を行いました。

TwoBitBoard3x3 クラスでも 同様の方法 で count_markpats の計算を行うことができますが、下記の点が異なります。

  • 〇 と × の手番 によって計算に必要となる ビットマスクの一覧が異なる
  • ptable に記録する 参照テーブル に ビット長が 18 まで のビット列の popcount を計算する点が異なる

なお、ビット長が 18 まで の ビット列の種類 は $\boldsymbol{2 ^ {18}}$ です。1 メガ = $\boldsymbol{2 ^ {20}}$ なので、ビット長が 18 までのビット列の popcount を ptable に記録する 参照テーブルのデータサイズ は数 メガバイト程度 にしかならないので、参照テーブルの データサイズの問題は発生しません。

参照テーブルの計算

下記は masklist と ptable を計算 するプログラムです。ptable は 0 以上 $\boldsymbol{2 ^ {18}}$ 未満 のビット列に対する popcount を計算するように修正 しました。

masklist の各要素 には 〇 の手番 を表す CIRCLE = 1 番の要素 に 〇 のビットマスク を、× の手番 を表す CROSS = 2 番の要素 に × のビットマスク を記録した list を記録 しました。なお、0 番の要素は利用しない ので 0 を記録 しました。

TwoBitBoard3x3.ptable = [i.bit_count() for i in range(1 << 18)]
TwoBitBoard3x3.masklist = [
    [0, 0b000000000000010101, 0b000000000000101010], # 0 列のビットマスク
    [0, 0b000000010101000000, 0b000000101010000000], # 1 列のビットマスク
    [0, 0b010101000000000000, 0b101010000000000000], # 2 列のビットマスク
    [0, 0b000001000001000001, 0b000010000010000010], # 0 行のビットマスク
    [0, 0b000100000100000100, 0b001000001000001000], # 1 行のビットマスク
    [0, 0b010000010000010000, 0b100000100000100000], # 2 行のビットマスク
    [0, 0b010000000100000001, 0b100000001000000010], # 対角線 1 のビットマスク
    [0, 0b000001000100010000, 0b000010001000100000], # 対角線 2 のビットマスク
]

count_markpats メソッドの定義

下記は count_markpats を定義したプログラムです。

  • 6 行目：turn の手番 のゲーム盤を表す self.board[turn] を self.board に修正 し、ビットマスクを表す mask を turn の手番 を表す ビットマスクが代入 された mask[turn] に修正 した
  • 7 行目：last_turn の手番 のゲーム盤を表す self.board[last_turn] を self.board に修正 し、ビットマスクを表す mask を last_turn の手番 を表す ビットマスクが代入 された mask[last_turn] に修正 した
 1  from collections import defaultdict
 2  
 3  def count_markpats(self, turn, last_turn):
 4      markpats = defaultdict(int)
 5      for mask in self.masklist:
 6          turncount = self.ptable[self.board & mask[turn]]
 7          lastturncount = self.ptable[self.board & mask[last_turn]]
 8          emptycount = self.BOARD_SIZE - turncount - lastturncount
 9          markpats[(lastturncount, turncount, emptycount)] += 1
10  
11      return markpats  
12  
13  TwoBitBoard3x3.count_markpats = count_markpats
行番号のないプログラム 
from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)
    for mask in self.masklist:
        turncount = self.ptable[self.board & mask[turn]]
        lastturncount = self.ptable[self.board & mask[last_turn]]
        emptycount = self.BOARD_SIZE - turncount - lastturncount
        markpats[(lastturncount, turncount, emptycount)] += 1

    return markpats  

TwoBitBoard3x3.count_markpats = count_markpats
修正箇所 
from collections import defaultdict

def count_markpats(self, turn, last_turn):
    markpats = defaultdict(int)
    for mask in self.masklist:
-       turncount = self.ptable[self.board[turn] & mask]
+       turncount = self.ptable[self.board & mask[turn]]
-       lastturncount = self.ptable[self.board[last_turn] & mask]
+       lastturncount = self.ptable[self.board & mask[last_turn]]
        emptycount = self.BOARD_SIZE - turncount - lastturncount
        markpats[(lastturncount, turncount, emptycount)] += 1

    return markpats  

TwoBitBoard3x3.count_markpats = count_markpats

処理時間の比較

下記のプログラムで いくつかのマスに着手を行った局面 に対する BitBoard3x3 と TwoBitBoard3x3 クラスの calc_markpats の 結果と処理時間を計測 することにします。

mb1 = Marubatsu(boardclass=BitBoard3x3)
mb2 = Marubatsu(boardclass=TwoBitBoard3x3)
mb1.cmove(0, 0)
mb1.cmove(1, 0)
mb1.cmove(0, 1)
mb2.cmove(0, 0)
mb2.cmove(1, 0)
mb2.cmove(0, 1)
print(mb1)
print(mb1.count_markpats())
print(mb2.count_markpats())
%timeit mb1.count_markpats()
%timeit mb2.count_markpats()

実行結果

Turn x
ox.
O..
...

defaultdict(<class 'int'>, {(2, 0, 1): 1, (0, 1, 2): 1, (0, 0, 3): 3, (1, 1, 1): 1, (1, 0, 2): 2})
defaultdict(<class 'int'>, {(2, 0, 1): 1, (0, 1, 2): 1, (0, 0, 3): 3, (1, 1, 1): 1, (1, 0, 2): 2})
2.92 μs ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.84 μs ± 10.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

実行結果から、いずれも同じ結果になることが確認 できました。また、行う処理はほぼ同じ なので、処理時間もほぼ同じになる ことが確認できました。

ai14s VS ai2 の対戦による確認

calc_markpats が 正しい処理を行うこと を、下記のプログラムで ai14s VS ai2 の対戦を行うことで 確認する ことにします。なお、ai_abs_dls の処理に必要 となる calc_same_hashables など のメソッドは まだ実装していない ので、ai_abs_dls の対戦を行う benchmark はまだ利用することはできません。対戦成績 が 以前の記事 と 同じになる ことから、calc_legal_moves が正しい処理を行うことが確認 できました。

from ai import ai14s

ai_match(ai=[ai14s, ai2], mbparams={"boardclass": TwoBitBoard3x3}, match_num=50000)

実行結果

ai14s VS ai2
100%|██████████| 50000/50000 [00:16<00:00, 3117.85it/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%

下記は先ほどの表に、上記の実行結果 と BitBoard3x3 の ai14s VS ai2 の 処理時間を加えた 表です。こちらも TwoBitBoard3x3 クラスの方が 処理速度がほんの少しだけ遅くなる ことが確認できました。ただし、その差はほとんどないので 処理速度はほぼ同じと考えても良い でしょう。

ai2 VS ai2 ai14s VS ai2
BitBoard3x3 24220.47 回/秒 3238.18 回/秒
TwoBitBoard3x3 21945.68 回/秒 3117.85 回/秒

board_to_hashable メソッドの定義

ゲーム盤のデータ を ハッシュ可能な値に変換 する board_to_hashable は、BitBoard3x3 クラスでは 〇 と × のビットボード を 一つのビット列に直した値を計算 していましたが、TwoBitBoard3x3 クラスでは ゲーム盤のデータ が 元々一つのビット列 なので、下記のプログラムのように self.board をそのまま返すことで定義 できます。

def board_to_hashable(self):
    return self.board

TwoBitBoard3x3.board_to_hashable = board_to_hashable
修正箇所 
def board_to_hashable(self):
-   return self.board[0] | (self.board[1] << (self.bit_length)) 
+   return self.board

TwoBitBoard3x3.board_to_hashable = board_to_hashable

処理速度の比較

下記のプログラムで いくつかのマスに着手を行った先程と同じ局面 に対する BitBoard3x3 と TwoBitBoard3x3 クラスの board_to_hashable の 処理時間を計測 することにします。

%timeit mb1.board_to_hashable()
%timeit mb2.board_to_hashable()

実行結果

195 ns ± 2.67 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
90.3 ns ± 0.142 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

BitBoard3x3 クラスの方が 明らかに処理が複雑 なので、TwoBitBoard3x3 クラスの方が 処理時間が約 2 倍ほど高速になる ことが確認できました。

board_to_str メソッドの定義

ゲーム盤のデータ を 文字列に変換 する board_to_str は AI の関数では利用しない ので、処理速度は重要ではありません。そこで、下記のプログラムのように BitBoard クラスと同じ処理を行う ように定義することにします。

def board_to_str(self):
    txt = ""
    for x in range(self.BOARD_SIZE):
        for y in range(self.BOARD_SIZE):
            txt += self.MARK_TABLE[self.getmark(x, y)]
    return txt

TwoBitBoard3x3.board_to_str = board_to_str

下記のプログラムで いくつかのマスに着手を行った先程と同じ局面 に対して BitBoard3x3 と TwoBitBoard3x3 クラスの board_to_str を実行 すると、どちらも同じ結果になる ことが確認できました。処理速度は重要ではないので処理時間の計測は省略します。

print(mb1.board_to_str())
print(mb2.board_to_str())

実行結果

oo.x.....
oo.x.....

calc_same_hashables メソッドの定義

同一局面のハッシュ可能な値の一覧 を計算する calc_same_hashabels は、BitBoard3x3 クラスでは 〇 と × の それぞれのビットボード に対して 反転と転置処理 を行う必要がありましたが、TwoBitBoard3x3 クラスでは 1 つのビット列でゲーム盤を表現 するので 1 回の反転と転置処理 を行うだけで済みます。

下図は TwoBitBoard3x3 クラスの ゲーム盤の各マスに対応するビットの番号 を表す図です。水色のマス の中の数字が 〇 のビットの番号 を、黄色のマス の中の数字が × のビットの番号 を表します。

上図からゲーム盤の 左右の反転処理 は 0 ~ 5 番 と 12 ~ 17 番 の ビットを交換する処理 であることがわかります。また、交換するそれぞれの ビットの間隔 は 12 - 0 = 12 なので、0 ~ 5 番 のビットを 1 とした ビットマスク と delta を 12 とした delta swap でその計算を行うことができます。

また、転置処理 は上図から 下記のビットを交換 する処理であることがわかるので、2 回の delta swap でその計算を行うことができます。

交換するビット ビットの間隔
2、3、10、11 番と 6、7、14、15 番 6 - 2 = 4
4、5 番と 12、13 番 12 - 4 = 8

calc_same_hashables の定義

  • 8 行目：TwoBitBoard3x3 クラスではゲーム盤を表すデータが 1 つのビット列なので board という変数にその値を代入するように修正した
  • 11 ~ 12 行目：上記で説明した delta swap で左右の反転処理を行うように修正した
  • 14、17、25、28 行目：TwoBitBoard3x3 クラスのゲーム盤の ハッシュ可能な値 は board に等しい ので hashable を board に修正 した
  • 20 ~ 23 行目：上記で説明した delta swap で転置処理を行うように修正した

下記は calc_same_hashables を定義するプログラムです。

 1  def calc_same_hashables(self, move=None):
 2      if move is None:
 3          hashables = set()
 4      else:
 5          hashables = {}
 6      if move is not None:
 7          x, y = self.move_to_xy(move)
 8      board = self.board
 9      for _ in range(4):
10          # 左右の反転処理
11          c = (board ^ (board >> 12)) & 0b111111
12          board = c ^ (c << 12) ^ board
13          if move is None:
14              hashables.add(board)
15          else:
16              x = self.BOARD_SIZE - x - 1
17              hashables[board] = self.xy_to_move(x, y)
18  
19          # 転置処理
20          c = (board ^ (board >> 4)) & 0b110000001100
21          board = c ^ (c << 4) ^ board 
22          c = (board ^ (board >> 8)) & 0b110000
23          board = c ^ (c << 8) ^ board 
24          if move is None:
25              hashables.add(board)
26          else:
27              x, y = y, x
28              hashables[board] = self.xy_to_move(x, y)
29      return hashables   
30  
31  TwoBitBoard3x3.calc_same_hashables = calc_same_hashables
行番号のないプログラム 
def calc_same_hashables(self, move=None):
    if move is None:
        hashables = set()
    else:
        hashables = {}
    if move is not None:
        x, y = self.move_to_xy(move)
    board = self.board
    for _ in range(4):
        # 左右の反転処理
        c = (board ^ (board >> 12)) & 0b111111
        board = c ^ (c << 12) ^ board
        if move is None:
            hashables.add(board)
        else:
            x = self.BOARD_SIZE - x - 1
            hashables[board] = self.xy_to_move(x, y)
            
        # 転置処理
        c = (board ^ (board >> 4)) & 0b110000001100
        board = c ^ (c << 4) ^ board 
        c = (board ^ (board >> 8)) & 0b110000
        board = c ^ (c << 8) ^ board 
        if move is None:
            hashables.add(board)
        else:
            x, y = y, x
            hashables[board] = self.xy_to_move(x, y)
    return hashables   

TwoBitBoard3x3.calc_same_hashables = calc_same_hashables
修正箇所 
def calc_same_hashables(self, move=None):
    if move is None:
        hashables = set()
    else:
        hashables = {}
    if move is not None:
        x, y = self.move_to_xy(move)
-   circlebb = self.board[0]
-   crossbb = self.board[1]
+   board = self.board
    for _ in range(4):
        # 左右の反転処理
-       c = (circlebb ^ (circlebb >> 6)) & 0b111
-       circlebb = c ^ (c << 6) ^ circlebb        
-       c = (crossbb ^ (crossbb >> 6)) & 0b111
-       crossbb = c ^ (c << 6) ^ crossbb        
-       hashable = circlebb | (crossbb << self.bit_length) 
+       c = (board ^ (board >> 12)) & 0b111111
+       board = c ^ (c << 12) ^ board
        if move is None:
-           hashables.add(hashable)
+           hashables.add(board)
        else:
            x = self.BOARD_SIZE - x - 1
-           hashables[hashable] = self.xy_to_move(x, y)
+           hashables[board] = self.xy_to_move(x, y)
            
        # 転置処理
 -      c = (circlebb ^ (circlebb >> 2)) & 0b100010
 -      circlebb = c ^ (c << 2) ^ circlebb 
 -      c = (circlebb ^ (circlebb >> 4)) & 0b100
 -      circlebb = c ^ (c << 4) ^ circlebb 
 -      c = (crossbb ^ (crossbb >> 2)) & 0b100010
 -      crossbb = c ^ (c << 2) ^ crossbb 
 -      c = (crossbb ^ (crossbb >> 4)) & 0b100
 -      crossbb = c ^ (c << 4) ^ crossbb 
 -      hashable = circlebb | (crossbb << self.bit_length)         
 +      c = (board ^ (board >> 4)) & 0b110000001100
 +      board = c ^ (c << 4) ^ board 
 +      c = (board ^ (board >> 8)) & 0b110000
 +      board = c ^ (c << 8) ^ board 
        if move is None:
-           hashables.add(hashable)
+           hashables.add(board)
        else:
            x, y = y, x
-           hashables[hashable] = self.xy_to_move(x, y)
+           hashables[board] = self.xy_to_move(x, y)
    return hashables   

TwoBitBoard3x3.calc_same_hashables = calc_same_hashables

下記は 以前の記事 で説明した calc_same_hashables の動作を確認 するプログラムです。ただし、TwoBitBoard3x3 クラスでは ゲーム盤を表すデータ と ハッシュ可能な値が等しい ので 8 行目 では hashable を mb.board.board に代入する ように修正しました。

実行結果が以前の記事と同じ であることから 正しく動作することが確認 できました。

 1  mb = Marubatsu(boardclass=TwoBitBoard3x3)
 2  mb.cmove(1, 1)
 3  mb.cmove(0, 0)
 4  mb.cmove(1, 0)
 5  move = mb.board.xy_to_move(1, 0)
 6  hashables = mb.board.calc_same_hashables(move)
 7  for hashable, move in hashables.items():
 8      mb.board.board = hashable
 9      print(mb.board.move_to_xy(move))
10      print(mb)
11      print()
行番号のないプログラム 
mb = Marubatsu(boardclass=TwoBitBoard3x3)
mb.cmove(1, 1)
mb.cmove(0, 0)
mb.cmove(1, 0)
move = mb.board.xy_to_move(1, 0)
hashables = mb.board.calc_same_hashables(move)
for hashable, move in hashables.items():
    mb.board.board = hashable
    print(mb.board.move_to_xy(move))
    print(mb)
    print()
修正箇所 
mb = Marubatsu(boardclass=BitBoard)
mb.cmove(1, 1)
mb.cmove(0, 0)
mb.cmove(1, 0)
move = mb.board.xy_to_move(1, 0)
hashables = mb.board.calc_same_hashables(move)
for hashable, move in hashables.items():
-   mb.board.board[0] = hashable & mb.board.fullmask
-   mb.board.board[1] = hashable >> mb.board.bit_length
+   mb.board.board = hashable
    print(mb.board.move_to_xy(move))
    print(mb)
    print()

実行結果

(1, 0)
Turn x
.Ox
.o.
...


(0, 1)
Turn x
...
oo.
x..


(2, 1)
Turn x
...
.oo
..x


(1, 2)
Turn x
...
.o.
.ox


(1, 2)
Turn x
...
.o.
xo.


(2, 1)
Turn x
..x
.oo
...


(0, 1)
Turn x
x..
oo.
...


(1, 0)
Turn x
xO.
.o.
...

処理時間の比較

下記のプログラムで いくつかのマスに着手を行った先程と同じ局面 に対する BitBoard3x3 と TwoBitBoard3x3 クラスの calc_same_hashables の処理時間を計測 することにします。

%timeit mb1.board.calc_same_hashables()
%timeit mb2.board.calc_same_hashables()

実行結果

4.26 μs ± 15.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.65 μs ± 13.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

BitBoard クラスでは 2 つのビット列 に対する反転と転置処理を行う必要があるのに対し、TwoBitBoard3x3 クラスでは 1 つのビット列 に対する反転と転置処理しか行う必要がないので、TwoBitBoard3x3 クラスの方が 処理時間が高速になる ことが確認できました。

benchmark の比較

TwoBitBoard3x3 クラスの すべてのメソッドの定義が完了 したので、下記のプログラムで benchmark を実行して calc_same_hashables を利用 する ai_abs_dls の処理時間を計測 することにします。

from util import benchmark

benchmark(mbparams={"boardclass":TwoBitBoard3x3})

実行結果

ai2 VS ai2
100%|██████████| 50000/50000 [00:02<00:00, 21774.56it/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:15<00:00, 3197.78it/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
  6.4 ms ±   0.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

下記は先ほどの表に、上記の実行結果 と BitBoard3x3 の ai_abs_dls の処理時間を加えた表 です。ai2 VS ai2 と ai14s VS ai2 の結果は 先ほどとほぼ同じ なので、上記ではなく 先程の結果のまま としました。

ai2 VS ai2 ai14s VS ai2 ai_abs_dls
BitBoard3x3 24220.47 回/秒 3238.18 回/秒 7.9 ms
TwoBitBoard3x3 21945.68 回/秒 3117.85 回/秒 6.4 ms

実行結果から TwoBitBoard3x3 クラスの方が ai_abs_dls の 処理速度が高速になった ことが確認できました。

BitBoard3x3 と TwoBitBoard3x3 クラスの性能の比較

上記から、TwoBitBoard3x3 クラスと BitBoard3x3 クラスの 性能の違い は下記のようになることがわかりました。

  • 合法手の一覧を計算 する calc_legal_moves は BitBoard3x3 クラスの方が少し速い
  • ハッシュ可能な値を計算 する board_to_hashable と、同一局面のハッシュ可能な値の一覧を計算 する calc_same_hashables は TwoBitBoard3x3 クラスの方がかなり速い
  • それ以外のメソッド の 処理速度はほぼ同じ である
  • ai2 VS ai2 の処理速度は BitBoard3x3 クラスの方が若干速い
  • ai14s VS ai2 の処理速度は ほぼ同じである
  • ai_abs_dls の処理速度は TwoBitBoard3x3 クラスの方が若干速い

上記は ゲーム盤のサイズが 3 x 3 の場合の性質 です。ゲーム盤の サイズが大きくなる と 上記とは異なる性質になる可能性がある 点に注意が必要です。

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

上記から BitBoard3x3 と TwoBitBoard3x3 クラスは 状況によって性能の優劣が異なる ことが確認できましたので、以後の記事 では この 2 つのクラスを使い分ける ことにします。また、これらのクラスは 他の ListBoard などのクラスと比較 して 処理速度が高速 なので、Marubatsu クラスの __init__ メソッドの 3 行目 を 下記のプログラムのように修正 して、ゲーム盤を表すクラスを指定しない場合 は BitBoard3x3 クラスを利用する ように修正することにします。

1  def __init__(self, boardclass=None, board_size=3, *args, **kwargs):
2      if boardclass is None:
3          boardclass = BitBoard3x3
元と同じなので省略
4  
5  Marubatsu.__init__ = __init__
行番号のないプログラム 
def __init__(self, boardclass=None, board_size=3, *args, **kwargs):
    if boardclass is None:
        boardclass = BitBoard3x3
    # ゲーム盤のデータ構造を定義するクラス
    self.boardclass = boardclass
    # ゲーム盤の縦横のサイズ
    self.BOARD_SIZE = board_size
    # boardclass のパラメータ
    self.args = args
    self.kwargs = kwargs
    self.board = self.boardclass(self.BOARD_SIZE, *self.args, **self.kwargs)
    self.EMPTY = self.board.EMPTY
    self.CIRCLE = self.board.CIRCLE
    self.CROSS = self.board.CROSS
    # 〇×ゲーム盤を再起動するメソッドを呼び出す
    self.restart()
    
Marubatsu.__init__ = __init__
修正箇所 
def __init__(self, boardclass=None, board_size=3, *args, **kwargs):
    if boardclass is None:
-       boardclass = ListBoard
+       boardclass = BitBoard3x3
元と同じなので省略
    
Marubatsu.__init__ = __init__

処理の高速化に関する補足

以上でゲーム盤を表すクラスの高速化に関する記事は終了です。他にも改良の余地はいくつもある と思いますが、おそらく処理速度はほとんど変わらない のではないかと思います。

また、筆者が思いつかなかったもっと高速なデータ構造があるかもしれませんので、思いついた方はコメントで指摘して頂けると助かります。

他のプログラム言語での実装

本記事 は Python で 〇× ゲームの AI を一から 作成することが目的 なので詳しくは説明しませんが、他のプログラム言語での実装 について 簡単に補足 します。

Python は インタープリタ言語 と呼ばれる種類の言語であり、一般的 には インタープリタ言語 は コンパイル言語 と呼ばれる種類の言語よりも 処理時間がかなり遅く なります。例えば、行う処理によって異なりますが、Python はコンパイル言語である C++ よりも 処理速度が数百倍以上も遅くなる事が多い ようです。

そのため、もっと大幅な高速化 を行いたい場合は Python 以外 の もっと高速なプログラム言語で実装 することを検討したほうが良いでしょう。候補としては C++、C#、Java、Go、Rust などの コンパイル言語 があり、それらのプログラム言語で ビットボードを利用したアルゴリズムで実装を行う ことで、おそらく数百倍以上 の処理速度の向上が得られるのではないかと思います。ただし、それらのプログラム言語は 初心者には難く、本当の意味での最速を目指す 場合は、キャッシュ などの CPU の仕組み など、コンピューター と プログラム言語の仕組み についても 深く理解する必要 があります。

参考までに Wikipedia のインタープリタとコンパイラのリンクを下記に記します。

また、いくつかの言語の処理速度を比較した記事 を下記に記します。他にも様々な条件で処理速度を比較した記事が簡単に見つかると思いますので興味がある方は調べてみて下さい。

処理速度が遅い Python で 多くの AI のプログラムが開発されている理由 は、AI の処理 の中で 処理時間の大部分を占める処理 を 高速な C++ などで実装されたモジュールを利用 して行うことができるからです。そのようなモジュールの一つが以前の記事で紹介した numpy で、他にも数多くの同様のモジュールがあります。

他のプログラム言語の知識が必要となるので本記事では行いませんが、〇× ゲームの処理を行うモジュール を C++ 等の言語を利用して実装 することで 〇× ゲームの処理速度を大幅に向上 させることができるのではないかと思います。

Python の高速化

本記事では利用しませんが Python を高速化する方法 がいくつかあります。それらには利点と欠点がある ので 欠点に注意して利用する必要 があります。下記に Python の高速化の手法を紹介する記事の一つを紹介します。ただし、いずれれの方法でも残念ながら基本的には コンパイラ言語に匹敵するほと処理速度が向上することはない ようです。

今回の記事のまとめ

今回の記事では TwoBitBoard3x3 クラスの定義を完了しました。なお、これまで処理の高速化を行ってきたのは次回からの記事で説明する AI の手法では処理の高速化が重要だからです。

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

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

次回の記事

  1. XOR 演算でも同じ計算が行われますが、以前の記事で検証したように Python では引き算のほうが XOR 演算よりも若干高速なので引き算で計算を行いました ↩

  2. random.seed(0) は benchmark と同じ結果になるようにするための乱数の種の初期化です ↩

  3. ビット列の 1 のビットの数を数える計算のことです。忘れた方は以前の記事を復習して下さい ↩

0
0
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
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?