Pythonで〇×ゲームのAIを一から作成する その210 ビットボードによるゲーム盤の表現方法と論理演算とシフト演算によるマークの参照と配置処理の実装

目次と前回の記事

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

ビットボードによるゲーム盤の表現

以前の記事で ゲーム盤のマスに 〇 と × が存在するかどうか を 3 次元の np.bool の ndarray で表現する NpBoolBoard クラスの定義を行いました。

NpBoolBoard クラスでは、以前の記事で説明したように、マークを表す数値、x 座標、y 座標 の順で 3 つの axis を持つ 3 次元 の np.bool の ndarray に対して、マークが存在する場合 は対応する要素に True、存在しない場合 は False を記録しました。

np.bool は 1 バイト で表現された 2 進数の 0 を True、1 を False とみなしてデータを記録しますが、1 バイトのデータ は 0 ~ 255 の 256 種類のデータを区別して表現 することができるので、残りの 2 ~ 255 のデータは利用されない という 無駄が生じます。

True と False の 2 種類のデータ を 無駄なく表現する方法 として、2 進数 1 桁分 のデータである 1 ビットのデータで表現 するという方法があります。具体的には、整数型 のデータを 2 進数で表記した際の、それぞれのビット（桁）¹が 0 か 1 であるか で 複数の True と False を まとめて無駄なく表現 することができます。例えば 2 進数 8 桁 の 1 バイト のデータで 8 つの True と False をまとめて表現 することができます。

言葉だけでの説明ではわかりづらいと思いますので具体例を挙げます。8 人 の人物が 20 歳以上であるか どうかを以下の方法で 1 バイトのデータで表現 することができます。

• 8 ビットの 2 進数 の それぞれのビット を 8 人にわりあてる
• 各ビット に対して 対応する人物が 20 歳以上 の場合は 1 に、そうでない場合は 0 にする

下記は 8 ビットの 2 進数 で 8 人の年齢 を表した場合の一例です。1 のビットが 5 つ 存在するので 5 人が 20 歳以上、3 人が 20 歳未満 であることを表します。

10011011

3 × 3 の 〇× ゲームのゲーム盤 には 9 つのマス があるので、〇 が存在するか を表す 9 ビットの 2 進数 と、× が存在するか を表す 9 ビットの 2 進数 でゲーム盤を表現できます。

このような、ゲーム盤（board）の 各マスの情報 を 2 進数の 1 ビットのデータに対応 させて表現したデータの事を ビットボード（bit board）と呼びます。

画像を色のついた点の集まりで表現したデータをビットマップ画像と呼びますが、元は白黒画像が 1 つの点を白または黒を表す 1 ビットのデータで表現していたことが由来だと言われています。

ビットボード は 1 つの整数型のデータ で 複数のマスをまとめて表現 することができるので、データサイズが小さくて済む という 利点 があります。例えば 3 × 3 の 〇× ゲームのゲーム盤 の場合は、NpBoolBoard では 9 つの各マス について 〇 と × がそれぞれ存在するかどうかを 1 バイトの np.bool で表現 するので、ゲーム盤を表すデータの データサイズ は 9 * 2 = 18 バイト になります。一方、ビットボード で表現する場合は 〇 と × のビットボード に対してそれぞれ 9 ビット のデータが必要になるので、9 × 2 = 18 ビット = 2.25 バイト という 1/8 のデータで表現 することができます。

なお、実際にはデータを 2.25 バイト のような 中途半端なサイズ で扱うことは 一般的に行われません。Python では int 型のデータ を 基本的には 4 バイト で表現²するので 9 ビット で表現できる整数 のデータは実際には 4 バイトで表現されます。そのため、ビットボード で表現されたゲーム盤のデータは 4 × 2 = 8 バイト になりますが、それでも ndarray で表現する場合の 18 バイト よりもデータサイズは小さく なります。

上記のデータサイズはゲーム盤を表現するデータのサイズです。Python ではすべてのデータをオブジェクトで扱い、オブジェクトにはオブジェクトが管理するデータ以外にもいくつかのデータが記録されるので、上記の ndarray や int 型のデータのデータサイズは上記で説明したサイズよりも大きくなります。

他のビットボードの利点として、複数の True と False を表すデータを後述する ビット演算 という手法で まとめて行うことができる ため、ビット演算をうまく組み合わせて処理を行う ことで 高速に処理を行う ことができる場合があるという利点があります。

一方、ビット演算 を利用する処理は 複雑になる場合が多い ため、プログラムがわかりづらくなりやすい という 欠点 があります。後で示すように、一見すると何を行っているかがわからない ような処理や、説明されても意味が理解しづらい ようなものもあります。データサイズ や 処理速度 が 重要でない場合 は 無理にビットボードをしないほうが良い でしょう。

今回の記事では Int 型のデータ である ビットボード でゲーム盤を表現する BitBoard クラスの定義を開始します。

ビットに関する用語

本記事で用いる、ビットに関するいくつかの用語 を説明します。

2 進数 で表記された、複数のビットが並んだデータ の事を ビット列 と呼びます。

整数の 2 進数 を表す ビット列 の中で、最も小さな値を表すビット のことを LSB と呼びます。LSB は least significant bit の略で、日本語では 最下位ビット と呼びます。逆に 最も大きな値を表すビット のことを MSB（most significant bit。最上位ビット）と呼びます。

ビット列の ビット は一般的に 番号で区別 します。下図のように LSB に 0 を割り当て、LSB から MSB に 向かって 1 つずつ増やしながら 番号を割り当てます。一般的な数字の並べ方と異なり、右から左に番号が増える 点に注意して下さい。本記事では以後は ビット列のビット をこの番号を使って 0 番のビット のように 表記 することにします。

下図の 正方形の中の数字 がビット列の ビットの値、上の数字 が ビットの番号 を表します。

あるビットより も 番号が大きいビット のことをそのビットの 上位のビット、番号が小さいビット の事を 下位のビット と呼びます。

MSB は、特定のサイズで表現 されたデータの中で 最も大きな値を表すビット の事なので、上図のように MSB が 0 になることがあります。先ほどの 8 人の年齢を表現する場合で、人物を 0 番のビットから順番に対応させた場合は、MSB は 最後の人の年齢 が 20 歳未満であるかどうかを表します。

ただし、1 である最も大きな番号のビット（上図では 6 番の ビット）という意味で MSB が使われる場合もある ので、MSB の意味は文脈から判断する必要があります。

LSB と MSB が最下位または最上位のバイト（byte）を表す場合もあります。

参考までに LSB と MSB の Wikipedia のリンクを下記に示します。

Python の 2 進数のリテラルと 2 進数としての int 型の表示

以前の記事で説明したように、プログラムの中に直接記述されたデータ の事を リテラル と呼びます。

2 進数のリテラル

Python では int 型 のデータを 2 進数の形式で記述 することができ、そのリテラルは 先頭 に 2 進数（binary）であることを表す 0b を記述 し、その後に 2 進数の値を記述 します。例えば 2 進数の 1010（= 10 進数の 10）は下記のプログラムのように 0b1010 というリテラルで記述します。なお、整数 は 2 進数と 10 進数 の どちらのリテラルでも記述 でき、それぞれが 同じ値を表します。例えば 2 進数の 0b1010 と 10 進数の 10 は 同じ数値 を表し、下記のプログラムのように == 演算子で 等しいかどうかを計算 すると True になります。

a = 0b1010
b = 10
print(a == b)

実行結果

True

Python の 整数のリテラル についての詳細については下記のリンク先を参照して下さい。

2 進数としての int 型の表示

下記のプログラムのように int 型 のデータを print で表示 すると、そのデータが元は 2 進数のリテラルで記述 されていても実行結果のように 10 進数で表示 が行われます。

print(a)
print(b)

実行結果

10
10

Python では組み込み関数 bin を利用することで、下記のプログラムのように int 型 のデータを 2 進数（binary）のリテラルの文字列に変換 することができます。

print(bin(a))

実行結果

0b1010

組み込み関数 bin の詳細については下記のリンク先を参照して下さい。

数値を 2 進数として表示 する別の方法として、以前の記事で説明した フォーマット済文字列リテラル（f 文字列） の 表現型に b を記述 するという方法があります。組み込み関数 bin との違い は以下の通りです。

• bin と異なり 先頭に 0b は表示されない
• bin の場合はその整数を表す 最低限の長さ の 2 進数のリテラルの文字列に変換されるが、f 文字列 の場合は 5b のように表現型の b の前に文字幅を指定 できる

下記は 10 進数の 10 を bin と f 文字列 の両方で表示するプログラムです。実行結果から下記の事が確認できます。

• f 文字列 の場合は 先頭に 0b が表示されない
• f 文字列 で 文字幅を指定しない 場合は bin と同様に 最も短い文字列 で表示する
• 文字幅と表現型 に 8b を記述することで、8 文字の 2 進数 が表示される。なお、    1010 の 先頭の 4 文字 には 空白文字が表示 されている
• 文字幅と表現型 に 08b を記述することで、空白文字の代わりに 0 が記述 された 8 文字の 2 進数 が表示される
• f 文字列 で 先頭に 0b を表示 したい場合は、下記のプログラムの 5 行目のように 2 進数として表示する {} の直前に 0b を記述 すれば良い

print(bin(a))
print(f"{a:b}")
print(f"{a:8b}")
print(f"{a:08b}")
print(f"0b{a:08b}")

実行結果

0b1010
1010
    1010
00001010
0b00001010

2 進数を 文字幅と表現型 に 08b のように記述した f 文字列で表示 することで、そのデータが 特定のビット数の 2 進数 であることが 明確になる ので、本記事では以後は その方法で 2 進数を表記 することにします。また、2 進数であることを明確にする ために 先頭に 0b を表示することにします。

組み込み関数 bin の詳細については下記のリンク先を参照して下さい。

Python では 8 進数（octal）のリテラルは先頭に 0o を、16 進数（hexadecimal）のリテラルは先頭に 0x を記述します。

f 文字列で 8 進数と 16 進数を表示する場合は表現型に o と x を記述します。

整数を 8 進数や 16 進数のリテラルの文字列に変換する組み込み関数 oct と hex があります。興味がある方は下記のリンク先を参照して下さい。

ゲーム盤のマスとビットの対応

〇× ゲームの ゲーム盤をビットボードで表現 するためには、ゲーム盤の マスと 2 進数のビット をどのように 対応づけるかを決める 必要があります。ゲーム盤のマスとビットが 1 対 1 に対応 していれば どのように対応づけてもかまいません が、本記事では下図の 数値座標とビットの番号を対応 させることにします。このように 対応づけした理由 は、この対応づけ がゲーム盤の マス と List1dBoard の list のインデックスの対応と同じ なので、List1dBoard のプログラムの一部を BitBoard の定義の参考にする ことができるからです。

下図の下部は 上部の局面 を表す ビットボードのデータ で、対応するマスのビット が 1 の場合にマークが存在する ことを表します。対応がわかりやすくなるように、対応するマス と ビットボードのビット を 同じ色で塗りつぶしました。

また、List1dBoard と同様 に 〇 と × のそれぞれのマーク に対してマスにマークが存在するかどうかを 別々のデータで表現 しています。図ではビットボードを 2 進数で表現していますが、ビットボードは整数を表す int 型のデータ である点に注意して下さい。

BitBoard クラスの定義

ビットボード で 〇× ゲームの ゲーム盤を表現 する BitBoard クラスを定義します。具体的には下記のような BitBoard クラスを定義 し、各メソッドをその後で順番に定義 します。

• ListBoard クラスと同様に Board クラスを継承 して定義する
• 必要なクラス属性 を定義する
• Board クラスの 抽象メソッド を 何の処理も行わないメソッドとして定義 しする

下記は継承する Board クラスの 抽象メソッドの一覧 です。

抽象メソッド	処理
getmark_by_move(move)	move のマスのマークを返す
setmark_by_move(move, mark)	move のマスに mark を代入する
xy_to_move(x, y)	(x, y) のマスのゲーム盤のクラスの座標を返す
move_to_xy(move)	move のマスの x, y の座標を返す
judge(last_turn, last_move, move_count)	勝敗判定を計算して返す
count_markpats(turn, last_turn)	局面のマークのパターンを返す
calc_legal_moves()	合法手の一覧を表す、ゲーム盤のクラスの座標を要素とする list を返す
calc_same_hashables(move)	同一局面のハッシュ可能な値の一覧と move の同一局面に対応する座標を計算する
board_to_str()	ゲーム盤を表す文字列を返す
board_to_hashable()	ゲーム盤を表すハッシュ可能な値を返す

〇、×、空のマス を表す クラス属性 は下記のように定義することにします。その理由は 〇 と × のビットボード を list の 0 番と 1 番の要素に記録 するためです。空のマスを表すビットボードは存在しない のでクラス属性 EMPTY は -1 としました。この考え方は以前の記事で説明した NpBoolBoard クラスと同じです。なお、クラス属性 MARK_TABLE は他のゲーム盤を表すクラスと同じ です。

クラス属性	値
EMPTY	-1
CIRCLE	0
CROSS	1

下記はそのように BitBoard クラスを定義したプログラムです。

from marubatsu import Board, Marubatsu

class BitBoard(Board):
    EMPTY = -1
    CIRCLE = 0
    CROSS = 1
    MARK_TABLE = {
        EMPTY: Marubatsu.EMPTY_STR,
        CIRCLE: Marubatsu.CIRCLE_STR,
        CROSS: Marubatsu.CROSS_STR,
        Marubatsu.DRAW: Marubatsu.DRAW,        
    }    
    
    def getmark_by_move(self, move):
        pass

    def setmark_by_move(self, move, mark):
        pass
        
    def xy_to_move(self, x, y):
        pass
        
    def move_to_xy(self, move):
        pass
    
    def judge(self, last_turn, last_move, move_count):
        pass    
    
    def count_markpats(self, turn, last_turn):
        pass    

    def calc_legal_moves(self):
        pass
    
    def calc_same_hashables(self, move=None):
        pass    
    
    def board_to_str(self):
        pass
    
    def board_to_hashable(self):
        pass        

__init__ メソッドの定義

最初に __init__ メソッドを下記のプログラムのように定義します。

他のゲーム盤を表現するクラス の __init__ メソッドとの 違い は 4 行目だけ で、ゲーム開始時の局面 を表す ビットボード を [0, 0] という list で表現 します。

0 は すべてのビットが 0 となる 2 進数 なので、すべてのマスにマークが存在しない ことを表します。〇 のビットボード を表す list の 0 番の要素 と × のビットボード を表す list の 1 番の要素 に 0 を代入 することで、マークが配置されていないゲーム開始時の局面 のゲーム盤を表現したことになります。

 1  def __init__(self, board_size:int=3, count_linemark:bool=False):
 2      self.BOARD_SIZE = board_size
 3      self.count_linemark = count_linemark
 4      self.board = [0, 0]
 5      if self.count_linemark:
 6          self.rowcount = {
 7              self.CIRCLE: [0] * self.BOARD_SIZE,
 8              self.CROSS: [0] * self.BOARD_SIZE,
 9          }
10          self.colcount = {
11              self.CIRCLE: [0] * self.BOARD_SIZE,
12              self.CROSS: [0] * self.BOARD_SIZE,
13          }
14          self.diacount = {
15              self.CIRCLE: [0] * 2,
16              self.CROSS: [0] * 2,
17          }
18  
19  BitBoard.__init__ = __init__

行番号のないプログラム

def __init__(self, board_size:int=3, count_linemark:bool=False):
    self.BOARD_SIZE = board_size
    self.count_linemark = count_linemark
    self.board = [0, 0]
    if self.count_linemark:
        self.rowcount = {
            self.CIRCLE: [0] * self.BOARD_SIZE,
            self.CROSS: [0] * self.BOARD_SIZE,
        }
        self.colcount = {
            self.CIRCLE: [0] * self.BOARD_SIZE,
            self.CROSS: [0] * self.BOARD_SIZE,
        }
        self.diacount = {
            self.CIRCLE: [0] * 2,
            self.CROSS: [0] * 2,
        }
        
BitBoard.__init__ = __init__

ゲーム盤の サイズが 3 × 3 以外 の場合でもゲーム開始時には マークが存在しないことに変わりはない ので、[0, 0] がゲーム開始時の局面を表す ことになります。

ビット演算

他のメソッドを定義する際に必要 となるいくつかの ビット演算 について説明します。

良く使われるビット演算 には 論理演算 と シフト演算 があります。
論理演算には AND、OR、XOR、NOT があり、2 進数の 各ビット に対して 独立した演算を行う 点が特徴です。

シフト演算 は 2 進数の 各ビットを左右にずらす（shift）するという演算です。

参考までに下記に 論理演算 と シフト演算 の Wikipedia のリンクを記します。

論理演算（AND、OR、XOR）

論理演算のうち AND、OR、XOR は 2 つの 2 進数 のデータの それぞれのビット に対して 下記の表の演算 を行います。日本語名の列 はそれぞれの 演算の日本語名 を表します。また、Python では 下記の表の演算子 を使って 論理演算を行う ことができます。

論理演算	日本語名	演算子	行う処理
AND 演算	論理積	&	両方とも 1 の場合に 1 を、 それ以外の場合は 0 を計算する
OR 演算	論理和	|3	どちらかに 1 があれば 1 を、 それ以外の場合は 0 を計算する
XOR 演算	排他的論理和	^4	異なる値の場合は 1 を、 同じ値の場合は 0 を計算する

AND 演算と OR 演算は 1 を True、0 を False に対応させた場合の bool 型のデータに対する and と or 演算子と同様の計算を行います。

下記はそれぞれの論理演算を表で表したものです。

AND	0	1
0	0	0
1	0	1

OR	0	1
0	0	1
1	1	1

XOR	0	1
0	0	1
1	1	0

XOR は exclusive or の略で、ex は x と同じ発音になるので x で略すことが良くあります。exclusive は 排他的 という意味の英単語で、排他的とは 特定の人々やグループだけ が参加または 利用できる状況 を指します。XOR は上図のように 両方が 1 以外 の場合は OR と同じ計算 を行いますが、両方が 1 の場合は 0 になる点が 全員が利用できない という意味で 排他的 なので 排他的論理和 と名付けられたようです。

下記は 2 進数 の 0b1010 と 0b1100 に対して AND、OR、XOR の演算を行うプログラムで、4 つのビットのそれぞれ に対して 上記の表の演算が行われる ことが確認できます。

a = 0b1010
b = 0b1100

print(f"a       = 0b{a:04b}")
print(f"b       = 0b{b:04b}")
print(f"a AND b = 0b{a & b:04b}")
print()
print(f"a       = 0b{a:04b}")
print(f"b       = 0b{b:04b}")
print(f"a OR b  = 0b{a | b:04b}")
print()
print(f"a       = 0b{a:04b}")
print(f"b       = 0b{b:04b}")
print(f"a XOR b = 0b{a ^ b:04b}")

実行結果

a       = 0b1010
b       = 0b1100
a AND b = 0b1000

a       = 0b1010
b       = 0b1100
a OR b  = 0b1110

a       = 0b1010
b       = 0b1100
a XOR b = 0b0110

上記のプログラムを下記のように bin で表示 すると 3 桁の 2 進数 として表示されてしまい 上下のビットが揃わなくなる ため、f 文字列 と b:04 で表示しました。

print(f"a       = {bin(a)}")
print(f"b       = {bin(b)}")
print(f"a XOR b = {bin(a ^ b)}")

実行結果

a       = 0b1010
b       = 0b1100
a XOR b = 0b110

&、|、^ 演算子の詳細については下記のリンク先を参照して下さい。

論理演算 は +、-、*、/ などの 算術演算と異なり、それぞれのビット に対して 独立した計算が行われる ので、あるビットで行われた計算の結果 が、他のビットに影響を及ぼすことがない という 重要な性質 があります。実際にこの後で紹介する マークの配置と削除の処理 は その性質を利用 して行います。

一方、+ や - などの 算術演算 では あるビットの演算結果 によって 繰上がりなど が生じて 他のビットの演算結果に影響を及ぼす ことがあります。

論理演算（NOT）

NOT 演算 は日本語では 否定 または 論理否定 と呼ばれる演算で、一つの 2 進数 のデータの すべてのビットの 0 と 1 を置き換える という演算を行います。Python では ~（チルダ）⁵ という記号を int 型のデータの直前に記述 することで NOT 演算を行うことができます。

論理演算の NOT 演算 は 1 を True、0 を False に対応させた場合の bool 型のデータに対する not と同様の計算 を行います。

正の 10 進数 は、0 以外の（最も左の）最上位の桁よりも左の桁 に 0 が無限に並んでいる と考えることができます。例えば 10 進数の 123 は ・・・000123（・・・の部分には 0 が無限に続く）のように、その左に 0 が無限に続く数値と同じ です。ただし、0 を無限に記述することは不可能 なので、一般的にはそれらの 0 を省略して記述 します。

これは 正の 2 進数の場合も同様 で、最上位の 1 のビットよりも上位のビット に 0 が無限に並んでいる と考えることができます。例えば 2 進数の 1010 は ・・・0001010（・・・の部分には 0 が無限に続く）と同じであると考えることができます。

従って 正の 2 進数 に対して NOT 演算 を行うと、元の 2 進数の 最上位の 1 のビットよりも上位のビット が すべて 0 から 1 に変換される ため 左に 1 が無限に並んだ 2 進数 に変換されます。例えば 1010 という 2 進数に対して NOT 演算 を行うと、1010 の 0 と 1 を入れ替えた 0101 の 左に 1 が無限に続く ・・・1110101 という 2 進数のデータを計算 します。

実際には 1 が無限に続く ような数値を実際にコンピュータの データとして記録することは不可能 なので、Python では 1 が無限に続くということを表す、実際には 1 が無限に続かない 有限のサイズのデータが記録 されます。

なお、実際には有限のサイズのデータですが、無限に 1 が続くデータが記録された場合と同じ計算が正しく行われる ので問題はありません。

~ 演算子の詳細については下記のリンク先を参照して下さい。

Python では int 型のデータが表現できる数値の範囲に制限はありませんが、他の 多くのプログラム言語 では 整数型 のデータは データサイズが決まっています。その場合の NOT 演算 はその データの中のすべてのビットの 0 と 1 を入れ替える という処理が行われます。例えば 64 ビットで整数を表現 する場合は、その整数を表す 64 ビット分の 0 と 1 が入れ替えられます。

負の整数に関する補足

下記の内容 は 今回の記事では利用しません。論理演算の中でもわかりづらいものの一つなので 意味がわからない と思った方は無理に理解しようとはせずに 飛ばしてください。

Python では 左に 1 が無限に続く 2 進数 のデータを 負の整数とみなす ため、x という 整数 に NOT 演算 を行うと下記のプログラムのように -(x + 1) という 整数が計算 されます。下記では 10 に対して NOT 演算を行った結果、-(10 + 1) = -11 が計算 されます。

print(~10)

実行結果

-11

上記のような計算が行われる理由 は、コンピュータでは 一般的に負の整数 を 2 の補数 と呼ばれる方法で表現するからです。その仕組みや 2 の補数が使われる理由について説明すると長くなるので今回の記事では説明しませんが、詳細について知りたい方は下記の Wikipedia のリンク先を参照して下さい。

なお、今回の記事が扱う範囲では上記の計算が行われる理由や 2 の補数について理解する必要はありませんが、負の整数に対する論理演算 は、2 の補数を理解しないと直観と反する計算が行われるように見える ので、そのような計算を行う場合は勉強する必要があります。

下記のプログラムのように負の整数を bin や f 文字列で 2 進数として表示すると、負の記号の後にその値の絶対値の 2 進数が表示されますが、実際に記録されるデータは上記で説明したように左に無限に 1 が続くことを表す 2 進数のデータです。

print(bin(-10))
print(f"{-10:b}")

実行結果

-0b1010
-1010

例えば -10 = -(9 + 1) = ~9 なので、9 を表す 2 進数である 1001 の 0 と 1 を入れ替えた 0110 の左に 1 が無限に続く ・・・1110110 を表すデータが記録されます。

シフト演算

シフト演算 は 2 進数のすべてのビット を 指定した数だけ左右にずらす（shift）処理を行う演算で、左にずらす 場合を 左シフト、右にずらす 場合を 右シフト と呼びます。Python では << 演算子が 左シフト を、>> 演算子が 右シフト を表し、<< の場合は 左に記述した数値 の各ビットを 右に記述した数値 の分だけ 左にずらします。>> の場合も同様 です。

左シフト を行った場合は、ずらした結果生じた 隙間のビット はすべて 0 で埋められます。例えば 0b1010 << 3 は 0b1010 を 左に 3 ビットずらして 0b1010XXX とし、空いた隙間の 下位 3 ビットの X を 0 で埋めた 結果 0b1010000 が計算 されます。下記はそのことを確認するプログラムです。

print(f"a      = 0b{a:07b}")
print(f"a << 3 = 0b{a << 3:7b}")

実行結果

a      = 0b0001010
a << 3 = 0b1010000

2 進数 の各 ビットが表す値 は ビットの番号が 0 から順番 に 1、2、4、・・・のように ビットの番号が 1 つ増える とその値が 2 倍 になるので x ビットの左シフト は値を $\boldsymbol{2 ^ x}$ 倍するのと同じ 計算が行われます。例えば $2 ^ 3 = 8$ なので、3 ビットの左シフト は下記のプログラムのように 数値を 8 倍する という計算を行います。8 倍になることが明確になる ように print では 10 進数を表示 しました。

print(10)
print(10 << 3)
print(10 * (2 ** 3))

実行結果

10
80
80

x ビットの右シフト を行った場合は、下位 x ビット のデータは すべて捨てられます。例えば 0b1001 >> 2 は下記のプログラムのように 0b1001 を 右に 2 ビットずらした結果、元の 下位 2 ビットの 01 が捨てられて 0b10 が計算 されます。ずれたことが明確になる ように 2 進数を表す先頭の 0b の表示は省略 し、先頭の 0 を空白にした 4 文字で表示 しました。

a = 0b1001
print(f"a      = {a:4b}")
print(f"a >> 2 = {a >> 2:4b}")

実行結果

a      = 1001
a >> 2 =   10

2 進数 では ビットの番号が 1 つ減る とその値が 1/2 倍 になるので x ビットの右シフト は 値を $\boldsymbol{\frac{1}{2 ^ {x}}}$ 倍 するのと同じ計算が行われます。例えば $\boldsymbol{\frac{1}{2 ^ {2}} = \frac{1}{4}}$ なので、2 ビットの右シフト は下記のプログラムのように 数値を 4 で除算する という計算を行います。ただし、x ビットの右シフトでは 下位 x ビットのデータが捨てられる ので、計算結果は 小数点以下が切り捨て られた 整数である商 が計算されます。10 ÷ 4 = 2 余り 2 なので 10 >> 2 の計算結果は 2 となるので、3 行目の計算では 商を計算する // 演算子 で計算を行っています。

print(10)
print(10 >> 2)
print(10 // (2 ** 2))

実行結果

10
2
2

シフト演算 の詳細については下記のリンク先を参照して下さい。

Python では int 型のデータが表現できる数値の範囲に制限はありませんが、他の多くのプログラム言語では整数型のデータはデータサイズが決まっており、左シフトを行った場合はデータサイズを超えた部分のビットは捨てられます。

また、詳細は省略しますがシフト演算には、算術シフト、論理シフト、循環シフトなどの種類の演算があり、Python のシフト演算は論理シフトです。

詳細は下記のシフト演算の Wikipedia を参照して下さい。

コンピューターの CPU は上記で紹介した以外にも様々なビット演算を行う命令が用意されています。また、Python ではその中のいくつかのビット演算を利用することができ、必要があれば今後の記事でいくつか紹介する予定です。

CPU が用意するビット演算を利用することで高速な処理を行うことができる場合がありますが、Python では残念ながら本記事で紹介するものを含めた基本的な CPU のビット演算しか利用することはできません。それらのビット演算を Python で行いたい場合は、別のプログラム言語を利用するか、そのようなビット演算を行うことができるモジュールをインポートする必要があります。

マスの座標のデータ構造と xy_to_move の定義

これまでは マスの座標を表すデータ を (0, 1) のような tuple または 0 のような 数値座標で表現 してきましたが、BitBoard ではそれらとは 別のデータ構造で座標を表現 します。以後はこの座標を BitBoard の座標と表記 することにします。

マスの座標のデータ構造とその計算方法

具体的には、マスに対応 する 2 進数の ビットの値 で BitBoard の座標を表現 します。そのように表現する理由についてはこの後で説明します。

2 進数のビットの値 は 最下位 のビットである LSB が $2^0 =$ 1 で、左に一つずれるたびに 2 倍 になります。そのため、x 番のビットの値 は下図のように $\boldsymbol{2^x}$ になります。

$\boldsymbol{2^x}$ は ** 演算子 を利用して計算することもできますが、左シフト を利用して 1 << x でも計算 することができます。これは 0 ビットの左シフト である 1 << 0 が 値をずらさない ので 元の値である 1 を計算 するからです。よくある間違いですが、2 << x と間違えないようにして下さい。下記は 5 番のビットの値 である $2^5 = 32$ を 両方の方法で計算 するプログラムで、実行結果からどちらも 正しい値が計算される ことが確認できます。

print(2 ** 5)
print(1 << 5)

実行結果

32
32

上記から、数値座標が x の BitBoard の座標 は 2 ** x または 1 << x で計算 することができることがわかりました。

処理速度の違いの検証

上記のどちらの方法でも同じ値が計算されますが、処理速度には違いがあります。下記は $2^3$、$2^{10}$、$2^{100}$ をそれぞれの方法で計算した場合の 処理速度を計測 するプログラムです。

%timeit 2 ** 3
%timeit 1 << 3
%timeit 2 ** 10
%timeit 1 << 10
%timeit 2 ** 100
%timeit 1 << 100

実行結果

11 ns ± 0.18 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
9.76 ns ± 0.143 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
9.79 ns ± 0.208 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
9.76 ns ± 0.142 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
149 ns ± 5.33 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
9.77 ns ± 0.142 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

実行結果から x が小さい場合 は処理速度に ほとんど差はありません が、x が大きい場合 は << による 左シフトの方が処理速度がかなり高速になる ことが確認できました。これは ビットをずらすだけ の シフト演算 のほうが べき乗の計算よりも単純な計算 であるためです。そこで、本記事では << 演算子を利用して計算を行う ことにします。

xy_to_move の定義

2026/01/07 修正：y + self.BOARD_SIZE * x を間違えて x + self.BOARD_SIZE * y と記述していたのを修正しました。

下記は xy_to_move を定義するプログラムです。(x, y) のマスに 対応するビット は 数値座標の番号のビット なので、下記のプログラムでは 数値座標を扱う List1dBoard クラスでの 数値座標の計算と同様 に y + self.BOARD_SIZE * x で (x, y) の 数値座標を計算 し、左シフト を利用して (x, y) のマスの BitBoard の 座標を計算 して返しています。

def xy_to_move(self, x, y):
    return 1 << (y + self.BOARD_SIZE * x)

BitBoard.xy_to_move = xy_to_move

下記は 数値座標が 0 である (0, 0) のマス と 数値座標 が 2 + 3 * 2 = 8 である (2, 2) のマス の BitBoard クラスでの座標を計算 するプログラムで、実行結果から $2^0 = 1$ と $2^8=256$ が 正しく計算されていることが確認 できます。

bb = BitBoard()
print(bb.xy_to_move(0, 0))
print(bb.xy_to_move(2, 2))

実行結果

1
256

なお、BitBoard の座標から (x, y) の座標を計算 する move_to_xy は今回の記事で説明した内容だけでは 簡単には実装できない ので 次回の記事で実装する予定 です。

getmark_by_move の定義

次に、BitBoard の座標 のマスの マークを計算 する getmark_by_move の定義 を行います。そのためには、ビットボード の 指定した座標を表すビット が 1 であるかどうかを判定 する処理を行う必要がありますが、その処理は AND 演算 を利用することで簡単に行うことができます。その方法について少し考えてみて下さい。

特定のビットが 1 であるかどうかの判定方法

その方法は ビットボード と 調べたいビットのみを 1 とした数値 に対して AND 演算 を行うというものです。AND 演算は以下の性質があります。

• 0 & 0 = 0、0 & 1 = 0 なので 片方が 0 であればもう片方の値に関わらず 0 が計算 される
• 1 & 0 = 0、1 & 1 = 1 なので 片方が 1 であれば もう片方の値と同じ値が計算 される

そのため、調べたいビットのみを 1、残りのすべてのビットを 0 とした数値と AND 演算 を行うと、以下のような計算結果 になります。

• 調べたいビット以外 のビットは すべて 0 が計算 される
• 調べたいビット に対しては、そのビットが 1 の場合は 1 が、0 の場合 は 0 が計算 される

下図は ビットボード と 5 番のビットのみが 1 の数値との AND 演算 で計算した結果を表す図です。ビットボードの緑色の 5 番以外 のビットに対しては 白色の 0 と AND 演算 が行われるので計算結果は すべて 0 となります。一方、5 番のビット は 黄色の 1 と AND 演算 が行われます。図ではビットボードの 5 番のビットが 1 となっていますが、計算結果の 5 番のビット は ビットボードの 5 番のビットと常に同じ になります⁶。

x 番のビットだけが 1 である数値は 1 << x で計算できるので、ビットボードの x 番のビットが 1 であるか どうかは、下記の 2 行目の条件式 で判定を行うことができます。

bit = 1 << x
board & bit == bit

下記は 上記の図のビットボード の 各ビットが 1 であるかどうかを判定 するプログラムで、実行結果から 正しい計算が行われることが確認 できます。

bb = 0b000100111
for num in range(9):
    bit = 1 << num
    print(f"{num} 番のビットが 1 であるかの判定 {bb & bit == bit}")

実行結果

0 番のビットが 1 であるかの判定 True
1 番のビットが 1 であるかの判定 True
2 番のビットが 1 であるかの判定 True
3 番のビットが 1 であるかの判定 False
4 番のビットが 1 であるかの判定 False
5 番のビットが 1 であるかの判定 True
6 番のビットが 1 であるかの判定 False
7 番のビットが 1 であるかの判定 False
8 番のビットが 1 であるかの判定 False

なお、if 文 では 条件式の計算結果が 0 の場合は False、0 以外の数値 の場合は True とみなして計算 が行われます。bb & (1 << num) は bb の num 番ビットが 0 の場合は 0 が、1 の場合 は 正の整数が計算 されるので、下記のプログラムのように if 文の条件式に bb & bit だけを記述して判定を行う こともできます。そのため、実行結果は上記と同じ になります。なお、3 行目の print では end="" を記述することで改行しないようにしました。

bb = 0b000100111
for num in range(9):
    print(f"{num} 番のビットが 1 であるかの判定 ", end="")
    if bb & (1 << num):
        print(True)
    else:
        print(False)

実行結果

0 番のビットが 1 であるかの判定 True
1 番のビットが 1 であるかの判定 True
2 番のビットが 1 であるかの判定 True
3 番のビットが 1 であるかの判定 False
4 番のビットが 1 であるかの判定 False
5 番のビットが 1 であるかの判定 True
6 番のビットが 1 であるかの判定 False
7 番のビットが 1 であるかの判定 False
8 番のビットが 1 であるかの判定 False

上記をまとめると以下のようになります。

2 進数 b の x 番のビットが 1 であるか どうかは 以下の式で判定 できる。

b & (1 << x)

<< 演算子 は & 演算子よりも優先順位が高い ので 上記の () は必要ありません が、使い慣れない演算子の優先順位はわかりづらく、下記のように記述 すると & 演算子が先に計算されるように誤解される 可能性があります。そこで、上記のように () を記述して計算の順序が明確になる ようにしました。

b & 1 << x

下記は両者が同じ計算を行うことを確認するプログラムです。

print(bb & (1 << 5))
print(bb & 1 << 5)

実行結果

32
32

Python の 演算子の優先順位 の詳細については下記のリンク先を参照して下さい。

getmark_by_move の定義

先程 BitBoard の座標 を マスに対応するビットのみが 1 となる数値で表現 することにしたので、BitBoard の座標 のマスに マークが配置されているか どうかは、ビットボードと BitBoard の座標との AND 演算の計算で判定 することができます。これが BitBoard の座標を先程説明したように定義した理由 です。

従って、getmark_by_move は下記のプログラムのように定義することができます。

• 2、4 行目：〇 のビットボードと BitBoard の座標が代入された move の AND 演算を行うことで、move に対応するマスに 〇 があるかどうかを判定する。4 行目の場合も同様

1  def getmark_by_move(self, move):
2      if self.board[0] & move:
3          return self.CIRCLE
4      elif self.board[1] & move:
5          return self.CROSS
6      else:
7          return self.EMPTY
8  
9  BitBoard.getmark_by_move = getmark_by_move

行番号のないプログラム

def getmark_by_move(self, move):
    if self.board[0] & move:
        return self.CIRCLE
    elif self.board[1] & move:
        return self.CROSS
    else:
        return self.EMPTY

BitBoard.getmark_by_move = getmark_by_move

上記の定義後に、先程の 下図の局面 に対して (0, 0)、(1, 1)、(2, 2) のマスのマークを getmark_by_move メソッドで計算 することにします。

なお、BitBoard クラスが継承する Board クラスの get_mark は下記のプログラムのようにその中で xy_to_move で (x, y) の座標を変換 して getmark_by_move を呼び出しています。

def getmark(self, x, y):
    return self.getmark_by_move(self.xy_to_move(x, y))

そこで、下記のプログラムでは get_mark を呼び出すことで (0, 0)、(1, 1)、(2, 2) のマスのマークを getmark_by_move メソッドで計算 する処理を行うことにします。実行結果から 〇 を表す 0、× を表す 1、空のマスを表す -1 が 正しく計算されることが確認 できます。

• 1 行目：BitBoard クラスのインスタンスを作成する
• 2、3 行目：setmark_by_move メソッドはまだ作成していない ので、board[0] と board[1] に直接上図の 2 進数の値を代入して上図の局面にする
• 4 ~ 6 行目：getmark でそれぞれの座標のマスを計算して表示する

1  bb = BitBoard()
2  bb.board[0] = 0b000100111
3  bb.board[1] = 0b001011000
4  print(bb.getmark(0, 0))
5  print(bb.getmark(1, 1))
6  print(bb.getmark(2, 2))

行番号のないプログラム

bb = BitBoard()
bb.board[0] = 0b000100111
bb.board[1] = 0b001011000
print(bb.getmark(0, 0))
print(bb.getmark(1, 1))
print(bb.getmark(2, 2))

実行結果

0
1
-1

setmark_by_move メソッドの定義

setmark_by_move は 仮引数 mark に self.CIRCLE または self.CROSS が代入されている場合は mark に代入された マークを配置 し、self.EMPTY が代入されている場合は マークを削除 するという処理を行います。

マークを配置 する処理は、その マークのビットマップ の 対応する BitBoard の座標のビットを 1 にする という処理ですが、その処理は OR 演算 を利用することで簡単に行うことができます。その方法について少し考えてみて下さい。

特定のビットを 1 にする方法

その方法は ビットボード と、ビットボードの 1 にしたいビットのみを 1 とした数値 に対して OR 演算 を行うというものです。OR 演算は以下の性質があります。

• 0 | 0 = 0、0 | 1 = 1 なので 片方が 0 であれば もう片方の値と同じ値が計算 される
• 1 | 0 = 1、1 | 1 = 1 なので 片方が 1 であればもう片方の値に関わらず 1 が計算 される

そのため、1 にしたいビットのみを 1、残りのすべてのビットを 0 とした数値と OR 演算 を行うと、以下のような計算結果 になります。

• 1 にしたいビット以外 のビットは 元のビットの値 が計算される
• 1 にしたいビット に対しては 必ず 1 が計算 される。これは 元のビットが 0 と 1 のどちらの場合であっても 変わらない

下図は ビットボード と 5 番のビットのみが 1 の数値 との OR 演算 で計算した結果を表す図です。ビットボードの 緑色の 5 番以外のビット に対しては 白色の 0 と OR 演算 が行われるので計算結果は すべて元のビットと同じ になります。一方、5 番のビット は 黄色の 1 と OR 演算 が行われます。図ではビットボードの 5 番のビットが 0 となっていますが、計算結果の 5 番のビット はビットボードの 5 番のビットの値に関わらず 必ず 1 になります。

上記をまとめると以下のようになります

以下のプログラムで 2 進数 b の x 番のビットを 1 にする ことができる。

b = b | (1 << x)

なお、+ などの他の演算子と同様に、上記の式は |= 演算子を利用 して 下記のように記述 することができる。

b |= 1 << x

元の 2 進数の x 番のビットが 0 の場合は下記のプログラムのように + 演算子による加算でも x 番のビットを 1 にすることができます。

print(f"0b{0b001000111 + (1 << 5):09b}")
print(f"0b{0b001000111 | (1 << 5):09b}")

実行結果

0b001100111
0b001100111

ただし、元の 2 進数の x 番のビットが 1 の場合 は繰上りが起きて 異なる計算結果になる 点に注意が必要です。

なお、下記のプログラムのように Python では 加算と OR 演算 は 処理時間はほとんど変わらない ようです。

%timeit 0b001000111 + (1 << 5)
%timeit 0b001000111 | (1 << 5)

実行結果

10.2 ns ± 0.368 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
9.52 ns ± 0.0512 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

特定のビットを 0 にする方法

マークを削除 する処理は、その マークのビットマップ の 対応する BitBoard の座標のビットを 0 にする という処理ですが、その処理は AND 演算 を利用することで行うことができます。その方法について少し考えてみて下さい。

その方法は ビットボード と、ビットボードの 0 にしたいビットのみを 0、他のすべてのビットを 1 とした数値に対して AND 演算 を行うというものです。下記は先ほど説明した AND 演算の性質です。

• 0 & 0 = 0、0 & 1 = 0 なので 片方が 0 であればもう片方の値に関わらず 0 が計算 される
• 1 & 0 = 0、1 & 1 = 1 なので 片方が 1 であれば もう片方の値と同じ値が計算 される

そのため、0 にしたいビットのみを 0、他のすべてのビットを 1 とした数値と AND 演算 を行うと、以下のような計算結果になります。

• 0 にしたいビット以外 のビットは 元のビットの値が計算 される
• 0 にしたいビット に対しては 必ず 0 が計算 される。これは 元のビットが 0 と 1 のどちらの場合であっても 変わらない

下図は ビットボード と 5 番のビットのみが 0 の数値との AND 演算 で計算した結果を表す図です。ビットボード の 緑色の 5 番以外 のビットに対しては 白色の 1 と AND 演算 が行われるので計算結果は すべて元のビットと同じ になります。一方、5 番のビット は 紫の 0 と AND 演算 が行われます。図ではビットボードの 5 番のビットが 1 となっていますが、計算結果 の 5 番のビット はビットボードの 5 番のビットの値に関わらず 必ず 0 になります。

なお、図では省略 しましたが、9 番以降のビット は ビットボード は すべて 0、5 番のみビットが 0 となる数値 は すべて 1 となります。0 と 1 の AND 演算 の結果は 0 となるので 計算結果 の 9 番以降のビット は すべて 0 になります。これが省略した理由です。

上記のような計算を行うためには x 番のビットのみを 0、他のすべてのビットを 1 とする数値を 計算する必要 がありますが、その計算は 下記の方法で行う ことができます。

2026/04/03：何かを勘違いしていたため、かなり回りくどい方法で計算する方法を紹介していたので修正しました。ただし、処理速度は修正前のプログラムで計測 している点と、元の方法でも正しい計算が行われる ので、プログラムそのものはこのことに気づいた 222 回目の記事まで元のまま修正しない ことにしました。

• x 番のビットのみを 1 とするビット列を 1 << x で計算する
• NOT 演算子 ~ を利用した ~(1 << x) を計算することで x 番のビットのみを 0、他のすべてのビットを 1 とする数値が計算される。

上記をまとめると以下のようになります。

以下のプログラムで 2 進数 b の x 番のビットを 0 にする ことができる。

b = b & (~(1 << x))

なお、+ などの他の演算子と同様に、上記の式は &= を利用 して 下記のように記述 することができる。

b &= ~(1 << x)

2026/04/03：下記は修正前の記事です。上記と比べて回りくどいことを行っていることが分かるのではないかと思います。

• 整数の 0 は すべてのビットが 0 の 2 進数 で表現される
• ~ 演算子によって すべてのビットの 0 と 1 を入れ替えた値 が計算されるので、~0 によって すべてのビットが 1 の 2 進数が計算 される⁷
• 「~0」 と 「x 番のビットのみが 1 となる 1 << x」 を XOR 演算⁸ することで、x 番以外 のビットは 1 ^ 0 = 1 が計算され、x 番 のビットは 1 ^ 1 = 0 が計算されるため、x 番のビットのみが 0 となる 2 進数が計算 される

上記をまとめると以下のようになります。

以下のプログラムで 2 進数 b の x 番のビットを 0 にする ことができる。

b = b & (~0 ^ (1 << x))

なお、+ などの他の演算子と同様に、上記の式は &= を利用 して 下記のように記述 することができる。

b &= ~0 ^ (1 << x)

今回の記事の最初で説明しましたが、ビット演算 は上記の式のように 見た目から何を行っているかが非常にわかりにくい プログラムに なることがある ため、バグが発生しやすい という 欠点 があります。繰り返しになりますが、データサイズや処理速度が重要でない場合 は 無理にビット演算を利用しないほうが良いで しょう。

setmark_by_move メソッドの定義

下記は上記の方法で setmark_by_move メソッドを定義したプログラムです。なお、count_linemark が True の場合は 3 行目で move_to_xy メソッドを利用する必要 がありますが、move_to_xy メソッドはまだ定義していない ので count_linemark が True の場合 は setmark_by_move メソッドを実行すると エラーが発生 します。move_to_xy メソッドについては 次回の記事で実装 します。

• 3 ~ 15 行目：count_linemark が True の場合は move_to_xy メソッドを利用して (x, y) の座標を計算する。現時点では move_to_xy メソッドを定義していないが、定義すれば正しく動作するようになる。4 ~ 15 行目の処理は他のゲーム盤を表すクラスの処理と同じ
• 16 行目：マークを削除する場合は、先程説明した方法を利用して 〇 と × のビットボード の 両方から move のマスのビットを 0 にしてマークを削除する。なお、mark のマークが配置されている ビットボードだけ に対して処理を行ったほうが 良いと思うかもしれないが、その場合は それぞれのビットボードにマークが配置されているか どうかを if 文で判定する必要 があるため、両方のビットマップ の move のマスのビットを 0 にする プログラムの方が記述が短く、処理時間も若干速くなる。また、マークが配置されていないビットマップ に対してこの処理を行っても 内容は変化しない ので問題は発生しない
• 19、20 行目：mark のビットマップに先程説明した方法でマークを配置する

 1  def setmark_by_move(self, move, mark):
 2      if self.count_linemark:
 3          x, y = self.move_to_xy(move)
 4          if mark != self.EMPTY:
 5              diff = 1
 6              changedmark = mark
 7          else:
 8              diff = -1
 9              changedmark = self.board[move]
10          self.colcount[changedmark][x] += diff
11          self.rowcount[changedmark][y] += diff
12          if x == y:
13              self.diacount[changedmark][0] += diff
14          if x + y == self.BOARD_SIZE - 1:
15              self.diacount[changedmark][1] += diff
16      if mark == self.EMPTY:
17          self.board[self.CIRCLE] &= ~0 ^ move
18          self.board[self.CROSS] &= ~0 ^ move
19      else:
20          self.board[mark] |= move
21  
22  BitBoard.setmark_by_move = setmark_by_move

行番号のないプログラム

def setmark_by_move(self, move, mark):
    if self.count_linemark:
        x, y = self.move_to_xy(move)
        if mark != self.EMPTY:
            diff = 1
            changedmark = mark
        else:
            diff = -1
            changedmark = self.board[move]
        self.colcount[changedmark][x] += diff
        self.rowcount[changedmark][y] += diff
        if x == y:
            self.diacount[changedmark][0] += diff
        if x + y == self.BOARD_SIZE - 1:
            self.diacount[changedmark][1] += diff
    if mark == self.EMPTY:
        self.board[self.CIRCLE] &= ~0 ^ move
        self.board[self.CROSS] &= ~0 ^ move
    else:
        self.board[mark] |= move
    
BitBoard.setmark_by_move = setmark_by_move

上記の定義を行った後で下記の処理を行うプログラムで 〇 と × のマークの配置 と、マークの削除 の処理を行い 正しい動作が行われるかを確認 します。実行結果から 正しい処理が行われることが確認 できました。

なお、getmark と同様に継承した Board クラスの setmark もその中で setmark_by_move を呼び出している ので下記の処理で setmark_by_move の処理を確認することができます。

• ゲーム開始時の局面 に対して getmark で (0, 0) のマークを計算する。実行結果は 空のマークを表す -1 になる
• setmark で (0, 0) に 〇 のマークを配置し、getmark でそのマスのマークを計算する。実行結果は 〇 のマークを表す 0 になる
• setmark で (1, 1) に × のマークを配置し、getmark でそのマスのマークを計算する。実行結果は × のマークを表す 1 になる
• setmark で (1, 1) からマークを削除 し、getmark でそのマスのマークを計算する。実行結果は 空のマークを表す -1 になる

bb = BitBoard()
print(bb.getmark(0, 0))
bb.setmark(0, 0, bb.CIRCLE)
print(bb.getmark(0, 0))
bb.setmark(1, 1, bb.CROSS)
print(bb.getmark(1, 1))
bb.setmark(1, 1, bb.EMPTY)
print(bb.getmark(1, 1))

実行結果

-1
0
1
-1

処理速度の計測と比較

今回の記事で実装した setmark_by_move と getmark_by_move のそれぞれについて 処理速度を計測 することにします。具体的には BitBoard クラスとこれまでに 最も処理速度が速かった List1dBoard クラスに対して計測を行い、その 比較を行います。

• getmark_by_move の計測
  (0, 0) に 〇、(1, 0) に × を着手した局面に対して下記に比較を行う
  • (0, 0) のマスのマークを計算することで、〇 のマークの計算 の処理速度を計測する
  • (1, 0) のマスのマークを計算することで、× のマークの計算 の処理速度を計測する
  • (2, 0) のマスのマークを計算することで、空 のマークの計算 の処理速度を計測する
• getmark_by_move の比較
  • (0, 0) のマスに 〇 を配置することで、〇 のマークの配置 の処理速度を計測する
  • (1, 0) のマスに × を配置することで、× のマークの配置 の処理速度を計測する
  • (2, 0) のマスからマークを削除することで、マークの削除 の処理速度を計測する

下記はその処理を行うプログラムです。なお、getmark はその中で xy_to_move を呼び出す 処理を行っている分だけ getmark_by_move よりも処理時間が長く なります。そのため、下記のプログラムでは getmark_by_move だけの処理速度を計測 するために、あらかじめ xy_to_move で座標を計算してから getmark_by_move の処理速度を計測しました。setmark_by_move も同様です。

from marubatsu import List1dBoard

lb = List1dBoard()
lb.setmark(0, 0, lb.CIRCLE)
lb.setmark(1, 0, lb.CROSS)
bb = BitBoard()
bb.setmark(0, 0, bb.CIRCLE)
bb.setmark(1, 0, bb.CROSS)

lmove1 = lb.xy_to_move(0, 0)
lmove2 = lb.xy_to_move(1, 0)
lmove3 = lb.xy_to_move(2, 0)
bmove1 = bb.xy_to_move(0, 0)
bmove2 = bb.xy_to_move(1, 0)
bmove3 = bb.xy_to_move(2, 0)

print("getmark_by_move")
print("List1dBoard")
%timeit lb.getmark_by_move(lmove1)
%timeit lb.getmark_by_move(lmove2)
%timeit lb.getmark_by_move(lmove2)
print("BitBoard")
%timeit bb.getmark_by_move(bmove1)
%timeit bb.getmark_by_move(bmove2)
%timeit bb.getmark_by_move(bmove2)
print()
print("setmark_by_move")
print("List1dBoard")
%timeit lb.setmark_by_move(lmove1, lb.CIRCLE)
%timeit lb.setmark_by_move(lmove2, lb.CROSS)
%timeit lb.setmark_by_move(lmove3, lb.EMPTY)
print("BitBoard")
%timeit bb.setmark_by_move(bmove1, bb.CIRCLE)
%timeit bb.setmark_by_move(bmove2, bb.CROSS)
%timeit bb.setmark_by_move(bmove2, bb.EMPTY)

実行結果

getmark_by_move
List1dBoard
59.4 ns ± 0.84 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
58.7 ns ± 0.624 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
70.7 ns ± 13.1 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
BitBoard
91.8 ns ± 0.552 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
122 ns ± 4.71 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
132 ns ± 6.53 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

setmark_by_move
List1dBoard
90.8 ns ± 2.8 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
90.1 ns ± 3.49 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
90.5 ns ± 3.64 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
BitBoard
141 ns ± 4.01 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
143 ns ± 4.08 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
250 ns ± 4.65 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

下記は上記の 実行結果をまとめた表 です。単位は ns で小数点以下第 1 桁で四捨五入しました。また、上段が List1dBoard、下段が BitBoard の 処理速度 を表します。

マーク	getmark_by_move	setmark_by_move
〇	60 92	91 141
×	59 122	90 143
空	71 132	91 250

実行結果から下記の事がわかります。下記ではその 理由 についても 考察 しました。

• List1dBoard クラスの方が BitBoard クラスよりも 処理速度が速い。その理由は後述する
• BitBoard クラスの getmark_by_move では 〇 のマークの判定を行った後 で × のマーク の判定と 空のマークの判定 を行うので、× や 空のマークが配置 されていると 処理速度が遅くなる
• BitBoard クラスの setmark_by_move は マークを削除 する処理で 〇 と × の両方のビットマップに対する処理 を行うので、マークを 配置する処理よりも処理時間が約 2 倍 になる

List1dBoard クラスの方が 処理速度が速い のは、マークの参照と配置 で行われる処理が list の1 つの要素の参照または代入処理だけ だからです。それに対して BitBoard クラスの場合は AND や OR などの 演算処理 を int 型 のビットボードのデータ に対して行う必要がある ため 処理速度が遅く なります。

このことからビットボードの方が処理速度が遅くなると思う人がいるかもしれませんが、ビットボード を利用した場合は 勝敗判定の処理など の、他の処理を 効率よく高速に行う ことができます。そのことについては次回の記事で説明します。

今回の記事のまとめ

今回の記事では ゲーム盤 を ビットボードで表現 する BitBoard クラスの 定義を開始 しました。最初に BitBoard の座標を定義 して xy_to_move メソッドを定義しました。次に マークの参照と配置 を行う getmark_by_move と setmark_by_move メソッドを定義しました。

マークの参照と配置 の処理に関しては ビットボードの処理速度 は List1dBoard クラスの場合と比べて 遅くなってしまいます が、今後の記事で説明する 勝敗判定などの処理 では 処理速度が高速 になります。

ビットボードの他の利点 としては、データサイズを小さくできる ことが挙げられます。ただし、ビットボードの処理 を行う ビット演算を利用 したプログラムは わかりにくい場合が多い という 欠点がある ため、データサイズや処理速度が重要でない場合 は 無理に利用しないほうが良い でしょう。

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

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

次回の記事

更新日時	更新内容
2026/01/07	xy_to_move の定義で y + self.BOARD_SIZE * x を間違えて x + self.BOARD_SIZE * y と記述していたのを修正しました。
2026/04/03	特定のビットを 0 にする方法の計算方法の説明を修正しました

1. ビットがわかりづらいと思った方は 2 進数の 1 桁のことだと思ってください ↩

2. Python の int 型のデータは数値の大きさに制限はないので、4 バイトで表現できない大きさの整数のデータサイズは 4 バイトより大きくなります ↩

3. Windows の日本語のキーボードでは BackSpace キーの左のキーを Shift キーを押しながら押すことで入力します ↩

4. Windows の日本語のキーボードでは BackSpace キーの 2 つ左のキーで入力します ↩

5. Windows の日本語のキーボードでは BackSpace キーの 2 つ左のキーを Shift キーを押しながら押すことで入力します ↩

6. ビットボードの 5 番のビットと計算結果の 5 番のビットを同じ水色で塗りつぶしているのは、それらが同じ値になることを表しています ↩

7. 先ほど説明したように、~0 = -(0 + 1) = -1 なので、Python では -1 はすべてのビットが 1 となる 2 進数で表現されます ↩

8. ~0 はすべてのビットが 1 なので、引き算による ~0 - (1 << x) でも同じ計算を行うことができます。わかりやすいと思ったほうで計算するとよいでしょう ↩