目次と前回の記事

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

一つのビット列でゲーム盤を扱うクラスの定義

前回の記事でビットボードでゲーム盤を表現するクラスの定義を一通り終えたつもりだったのですが、別の方法を思いついたので説明することにします。

これまでの記事で定義したビットボードは 〇と × のビットボード を 別々のビット列で表現 していたため、ビットボードの反転や転置処理 を 2 つのビット列に対して行う必要 があります。そこで、この問題を解決する方法として、ゲーム盤を一つのビット列で表現 する方法を紹介することにします。その方法について少し考えてみて下さい。

なお、今回の記事では 3 x 3 のサイズのゲーム盤に限定 した説明を行います。任意のサイズのゲーム盤でも同様の方法で実装できるので、興味がある方は実装してみて下さい。

一つのビット列でゲーム盤を表現するデータ構造

ゲーム盤を一つのビット列で扱うデータ構造 の一つは実は既に紹介済です。そのデータ構造は 〇のビットボード の値を 0 ~ 8 番 のビット、× のビットボード の値を 9 ~ 17 番 の ビットに並べる というもので、以前の記事で説明した board_to_hashable メソッドでその処理を行っています。下図はその時に示した図で、図の一番下のビット列 の 水色の部分 が 〇のゲーム盤 を、黄色の部分 が × のゲーム盤 を表します。

別のデータ構造として 〇と × のマスを表すビット を 交互に並べて表現する というものがあります。具体的には 0 番と 1 番 のビットに (0, 0) の〇と × のマス を、2 番と 3 番 のビットに (0, 1) の〇と × のマス を対応させます。残りのマスも同様です。

例えば 下図の上の局面 の場合は、下図の下部のビット列で表現 します。ビット列 の 水色の部分が〇のマーク を、黄色の部分が × のマーク を表すビットで、〇と × を表すビットが交互に並び ます。

下記はマスに 配置されたマーク と、そのマスに対応する 2 つのビット を表す表です。表からわかるように 2 つのビットが 11 になることはありません。

	2 つのビット
空のマス	`00`
〇のマス	`01`
× のマス	`10`

2 つのビットを並べて 1 つのマスを表現 するので本記事ではこのデータ構造でゲーム盤を表現するビット列を 2 ビットボード と呼ぶことにします。また、この後で定義する 2 ビットボード で 3 x 3 のサイズのゲーム盤を表現するクラス の名前を TwoBitBoard3x3¹ と命名することにします。

1 つのマス に対して 2 つのビットが並ぶ ので ビット長 は 3 × 3 × 2 = 18 となり、(x, y) のマスの 〇と × のマスに対応するビットの番号 は下記の表のようになります。比較できるように BitBoard3x3 クラスの場合も載せました。表からわかるように 〇のマスのビットの番号 は BitBoard3x3 の場合の 2 倍 に、× マスのビットの番号 は 2 倍 + 1 になります。

	TwoBitBoard3x3	BitBoard3x3
〇のマス	`x * 2 + y * 6`	`x + y * 3`
× のマス	`x * 2 + y * 6 + 1`	`x + y * 3`

上記で紹介したどちらの方法でも ビット長が 18 のビット列 でゲーム盤を表現することができますが、本記事では後者の方法を採用 することにします。前者の方法はビットの並びがこれまでの方法と大きくは変わらないので実装はそれほど難しくはないと思いますので、興味がある方は前者の方法で実装してみて下さい。また、他にももっと良いデータ構造があるかもしれませんので、思いついた方は実装してみると良いでしょう。

なお、BitBoard3x3 クラスの場合は ビット長が 9 の 2 つビット列 でゲーム盤を表現するので、ゲーム盤のデータサイズは同じ です。

TwoBitBoard3x3 クラスの定義

上記のデータ構造 で 3 x 3 のサイズのゲーム盤を表現 する TwoBitBoard3x3 クラスを定義することにします。下記は TwoBitBoard3x3 クラスの定義 です

3 行目：ゲーム盤を表すクラスの基底クラスである Borad クラスを継承して定義する
4 ~ 6 行目：BitBoard クラスと異なり 空のマス を表す クラス属性 EMPTY を 0、〇と × を表す CIRCLE と CROSS を 1 と 2 とする。その理由については後述する
7 ~ 12 行目：MARK_TABLE 属性 は BitBoard クラスと同じ だが、EMPTY などの クラス属性の値が異なるので記述する必要 がある。なお、ptable などの参照テーブルを代入するクラス属性の値は BitBoard クラスと異なるので必要になった時点で定義することにする
14 ~ 45 行目：Board クラスの抽象メソッドを何も行わないメソッドとして定義する。それぞれのメソッドの具体的な処理はこの後で順番に定義する

 1  from marubatsu import Board, Marubatsu
 2  
 3  class TwoBitBoard3x3(Board):
 4      EMPTY = 0
 5      CIRCLE = 1
 6      CROSS = 2
 7      MARK_TABLE = {
 8          EMPTY: Marubatsu.EMPTY_STR,
 9          CIRCLE: Marubatsu.CIRCLE_STR,
10          CROSS: Marubatsu.CROSS_STR,
11          Marubatsu.DRAW: Marubatsu.DRAW,        
12      }       
13  
14      def initialize(self):
15          pass    
16  
17      def getmark_by_move(self, move):
18          pass
19  
20      def setmark_by_move(self, move, mark):
21          pass
22  
23      def xy_to_move(self, x, y):
24          pass
25  
26      def move_to_xy(self, move):
27          pass
28  
29      def calc_legal_moves(self):
30          pass
31  
32      def board_to_str(self):
33          pass
34  
35      def board_to_hashable(self):
36          pass    
37  
38      def judge(self, last_turn, last_move, move_count):
39          pass
40  
41      def count_markpats(self, turn, last_turn):
42          pass
43  
44      def calc_same_hashables(self, move=None):
45          pass

行番号のないプログラム

from marubatsu import Board, Marubatsu

class TwoBitBoard3x3(Board):
    EMPTY = 0
    CIRCLE = 1
    CROSS = 2
    MARK_TABLE = {
        EMPTY: Marubatsu.EMPTY_STR,
        CIRCLE: Marubatsu.CIRCLE_STR,
        CROSS: Marubatsu.CROSS_STR,
        Marubatsu.DRAW: Marubatsu.DRAW,        
    }       
    
    def initialize(self):
        pass    
    
    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 calc_legal_moves(self):
        pass
    
    def board_to_str(self):
        pass
    
    def board_to_hashable(self):
        pass    
    
    def judge(self, last_turn, last_move, move_count):
        pass
    
    def count_markpats(self, turn, last_turn):
        pass

    def calc_same_hashables(self, move=None):
        pass

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

抽象メソッド	処理
`initialize()`	ゲーム盤のデータを初期化する
`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 の座標を返す
`calc_legal_moves()`	合法手の一覧を表す、ゲーム盤のクラスの座標を要素とする list を返す
`board_to_str()`	ゲーム盤を表す文字列を返す
`board_to_hashable()`	ゲーム盤を表すハッシュ可能な値を返す
`judge(last_turn, last_move, move_count)`	勝敗判定を計算して返す
`count_markpats(turn, last_turn)`	局面のマークのパターンを返す
`calc_same_hashables(move)`	同一局面のハッシュ可能な値の一覧と `move` の同一局面に対応する座標を計算する

`init` メソッドと `initialize` メソッドの定義

下記は __init__ メソッドと initialize メソッドの定義です。説明と修正箇所は BitBoard3x3 クラスのメソッドからのものです。以後のメソッドの説明でも同様です。

3 行目：ビットボードのビット長が 9 の 2 倍の 18 になったのでそのように修正した
9 行目：ゲーム盤を表すデータが 1 つのビット列になったので、board 属性には 1 つの int 型のデータを代入する。また、ゲーム開始時の局面ではマークが 1 つも配置されていないのでその値は 0 である

 1  def __init__(self, *args, **kwargs):
 2      self.BOARD_SIZE = 3
 3      self.bit_length = 18
 4      self.initialize()
 5  
 6  TwoBitBoard3x3.__init__ = __init__
 7  
 8  def initialize(self):
 9      self.board = 0
10  
11  TwoBitBoard3x3.initialize = initialize

行番号のないプログラム

def __init__(self, *args, **kwargs):
    self.BOARD_SIZE = 3
    self.bit_length = 18
    self.initialize()
    
TwoBitBoard3x3.__init__ = __init__

def initialize(self):
    self.board = 0

TwoBitBoard3x3.initialize = initialize

修正箇所

def __init__(self, *args, **kwargs):
    self.BOARD_SIZE = 3
-   self.bit_length = 9
+   self.bit_length = 18
    self.initialize()
    
TwoBitBoard3x3.__init__ = __init__

def initialize(self):
-   self.board = [0, 0]
+   self.board = 0

TwoBitBoard3x3.initialize = initialize

TwoBitBoard3x3 の座標のデータ構造

ゲーム盤 を表すデータの データ構造が変わった ので、TwoBitBoard3x3 の座標 の データ構造も変える必要 があります。どのようなデータ構造にすれば良いかについて少し考えてみて下さい。

BitBoard3x3 の座標 では、マスを表すビットだけを 1 とした ビット列で表現 しました。そのようにすることで、BitBoard3x3 クラスの setmark_by_move では マークの配置または削除 を下記のような処理で行うことができます。

マークの削除 は下記のプログラムの 3、4 行目のように、〇と × のそれぞれのビットボード と BitBoard3x3 の座標 を表すビット列の 1 と 0 を反転したビット列との AND 演算 で行うことができる
マークの配置 は下記のプログラムの 6 行目のように、配置するマークのビットボード と BitBoard3x3 の座標 を表すビット列との OR 演算 で行うことができる

1 def setmark_by_move(self, move, mark):
2     if mark == self.EMPTY:
3         self.board[self.CIRCLE] &= ~0 ^ move
4         self.board[self.CROSS] &= ~0 ^ move
5     else:
6         self.board[mark] |= move

同様の方法でマークの配置と削除 を行うことができるようにするために、TwoBitBoard3x3 の座標 を マークの配置または削除 を行う マスとマークに対応するビットを 1 としたビット列 で表現することにします。例えば (1, 0) のマスに 〇を着手または削除 する場合は 1 * 2 + 0 * 6 = 2 番のビットが 1 となる 0b100 となります。(1, 0) のマスに × を着手または削除 する場合は 1 * 2 + 0 * 6 + 1 = 3 番のビットが 1 となる 0b1000 となります。そうすることで、上記とほぼ同様の方法 で マークの配置と削除 を行うことができます。

`xy_to_move` メソッドの定義と `initialize` メソッドの修正

次に (x, y) の座標 から TwoBitBoard3x3 の座標を計算 する xy_to_move メソッドを定義することにします。BitBoard3x3 クラスの 場合と異なり、現在の局面の手番によって同じマスでも計算する値が異なる ので、現在の局面の手番のデータが必要 になります。BitBoard3x3 クラスは 手番のデータを記録していない ので、手番を表す属性を追加 することにしました。

TwoBitBoard3x3 の座標 は × の手番のビットの番号 は 〇の手番の場合よりも 1 つ多くなる ので、〇の手番の場合は 0 が、× の手番の場合は 1 が代入される crossturn という名前の属性を追加 することにします。属性の名前は × の手番の場合に True と同じ意味を持つ 1 が代入 されることから crossturn という名前にしました。

ゲーム開始時の局面 は 〇の手番 なので、下記のプログラムの 3 行目のように crossturn 属性に 0 を代入 するように initialize メソッドを修正します。

1  def initialize(self):
2      self.board = 0
3      self.crossturn = 0
4  
5  TwoBitBoard3x3.initialize = initialize

行番号のないプログラム

def initialize(self):
    self.board = 0
    self.crossturn = 0

TwoBitBoard3x3.initialize = initialize

修正箇所

def initialize(self):
    self.board = 0
+   self.crossturn = 0

TwoBitBoard3x3.initialize = initialize

下記は xy_to_move メソッドの定義です。2 行目では先ほどの表で説明した式で 現在の手番の (x, y) に対応するマスのビットが 1 となるビット列の計算 を行っています。

1  def xy_to_move(self, x, y):
2      return 1 << (y * 2 + x * 6 + self.crossturn)
3  
4  TwoBitBoard3x3.xy_to_move = xy_to_move

行番号のないプログラム

def xy_to_move(self, x, y):
    return 1 << (y * 2 + x * 6 + self.crossturn)

TwoBitBoard3x3.xy_to_move = xy_to_move

修正箇所

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

TwoBitBoard3x3.xy_to_move = xy_to_move

`move_to_xy` メソッドの定義

(x, y) のマスに 対応するビットの番号 は、BitBoard3x3 クラスの場合の 2 倍または 2 倍 + 1 になるので、ビットの番号を 2 で割った商 を計算した後で BitBoard3x3 クラスと同じ計算を行う ことで TwoBitBoard3x3 の座標から (x, y) の座標を計算 することができます。下記はそのように move_to_xy を定義したプログラムです。

2 行目：move のビットの番号を 2 で割った商を計算するように修正する

1  def move_to_xy(self, move):
2      move = (move.bit_length() - 1) // 2
3      return move // self.BOARD_SIZE, move % self.BOARD_SIZE   
4  
5  TwoBitBoard3x3.move_to_xy = move_to_xy

行番号のないプログラム

def move_to_xy(self, move):
    move = (move.bit_length() - 1) // 2
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE   

TwoBitBoard3x3.move_to_xy = move_to_xy

修正箇所

def move_to_xy(self, move):
-   move = move.bit_length() - 1
+   move = (move.bit_length() - 1) // 2
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE   

TwoBitBoard3x3.move_to_xy = move_to_xy

下記のプログラムで xy_to_move と move_to_xy が正しい計算を行うことを確認 します。

〇の手番と × の手番のそれぞれに対して下記の処理を行う
- xy_to_move で (0, 1) のマスに対する計算を行う
- 上記の値に対して move_to_xy を呼び出して元の座標が計算されることを確認する

bb = TwoBitBoard3x3()
# 〇 の手番
move = bb.xy_to_move(0, 1)
print(bin(move))
print(bb.move_to_xy(move))
# × の手番
bb.crossturn = 1
move = bb.xy_to_move(0, 1)
print(bin(move))
print(bb.move_to_xy(move))

実行結果

0b100
(0, 1)
0b1000
(0, 1)

1 * 2 + 0 = 2 なので、〇の手番 の場合の (0, 1) に対する xy_to_move の計算結果は 2 番のビットが 1 となる 0b100 に、× の手番 の場合は 1 * 2 + 1 = 3 番のビットが 1 となる 0b1000 になります。実行結果から 正しい計算が行われることが確認 できました。

`setmark_by_move` メソッドの定義

TwoBitBoard3x3 クラスの setmark_by_move メソッドの定義を行う前に、下記の BitBoard3x3 クラスの setmark_by_move の処理で 無駄な計算を行っていた ことに気が付きましたので その修正を先に行う ことにします。

1 def setmark_by_move(self, move, mark):
2     if mark == self.EMPTY:
3         self.board[self.CIRCLE] &= ~0 ^ move
4         self.board[self.CROSS] &= ~0 ^ move
5     else:
6         self.board[mark] |= move

上記のプログラムの 3、4 行目では以前の記事の修正前の記事で説明したように、move に代入されたビット列の 1 と 0 を反転したビット列 を ~0 ^ move という式で計算 していますが、よく考えると NOT 演算 を行う ~ 演算子はビット列の 1 と 0 を反転した値を計算 するので ~move というより簡単な式で計算 することができます。

下記はそのように BitBoard3x3 クラスの setmark_by_move を修正 したプログラムです。ここでは記載しませんが、BitBoard クラスも 同様の処理を行っている ので marubatsu.py の方で修正 しておくことにします。

5、6 行目：~0 ^ move を ~move に修正した

 1  from marubatsu import BitBoard3x3
 2  
 3  def setmark_by_move(self, move, mark):
 4      if mark == self.EMPTY:
 5          self.board[self.CIRCLE] &= ~move
 6          self.board[self.CROSS] &= ~move
 7      else:
 8          self.board[mark] |= move
 9  
10  BitBoard3x3.setmark_by_move = setmark_by_move

行番号のないプログラム

from marubatsu import BitBoard3x3

def setmark_by_move(self, move, mark):
    if mark == self.EMPTY:
        self.board[self.CIRCLE] &= ~move
        self.board[self.CROSS] &= ~move
    else:
        self.board[mark] |= move

BitBoard3x3.setmark_by_move = setmark_by_move

修正箇所

from marubatsu import BitBoard3x3

def setmark_by_move(self, move, mark):
    if mark == self.EMPTY:
-       self.board[self.CIRCLE] &= ~0 ^ move
+       self.board[self.CIRCLE] &= ~move
-       self.board[self.CROSS] &= ~0 ^ move
+       self.board[self.CROSS] &= ~move
    else:
        self.board[mark] |= move
    self.crossturn ^= 1
    
BitBoard3x3.setmark_by_move = setmark_by_move

下記は TwoBitBoard3x3 クラスの setmark_by_move メソッドの定義です。BitBoard3x3 クラスとの違い は以下の通りです。

2 行目：元のプログラムでは マークの削除 を行うことを mark == self.EMPTY によって判定 していたが、self.EMPTY の値を -1 から 0 に修正 したため、マークを配置する場合 は move に 0 以外の値が代入 されるようになった。そこで if 文の条件式に mark だけを記述 することで マークを配置することを判定 することにした。条件式の中で == 演算子による比較を行わなくて済む ようになった分だけ 処理時間が短くなる
3 行目：マークの配置 処理を board 属性に対して直接計算を行う ように修正した
5 行目：マークを削除 する処理は BitBoard3x3 クラスの場合は手番の情報がないので〇と × の両方のビットボードに対する処理を行う必要があったが、TwoBitBoard3x3 クラスの場合は board に代入されたゲーム盤を表す ビット列に対してのみ処理を行えば良い
6 行目：マークの配置や削除 を行うと 手番が入れ替わる ので crossturn 属性の値を 0 から 1 または 1 から 0 に変更 する必要がある

1  def setmark_by_move(self, move, mark):
2      if mark:
3          self.board |= move
4      else:
5          self.board &= ~move
6      self.crossturn = 0 if self.crossturn else 1
7  
8  TwoBitBoard3x3.setmark_by_move = setmark_by_move

行番号のないプログラム

def setmark_by_move(self, move, mark):
    if mark:
        self.board |= move
    else:
        self.board &= ~move
    self.crossturn = 0 if self.crossturn else 1

TwoBitBoard3x3.setmark_by_move = setmark_by_move

修正箇所

def setmark_by_move(self, move, mark):
-   if mark == self.EMPTY:
+   if mark:
-       self.board[self.CIRCLE] &= ~0 ^ move
-       self.board[self.CROSS] &= ~0 ^ move
+       self.board |= move
    else:
-       self.board[mark] |= move
+       self.board &= ~move
+   self.crossturn = 0 if self.crossturn else 1


TwoBitBoard3x3.setmark_by_move = setmark_by_move

move の値 に 配置または削除するマークの情報が記録されている ので、マークの配置や削除 を行う 3、5 行目 の処理では mark の値は利用されません。そのため、move が〇の手番を表す 座標の場合に mark に CROSS を代入 しても 〇のマークが配置される 点に注意が必要です。また、× のマークが配置 されている場合に move に〇の手番を表す座標を代入 して mark に EMPTY を代入 した場合は × のマークが削除されない点 にも注意が必要です。

なお、以下のようにすることでそのような問題は発生しないので、わざと間違った TwoBitBoard3x3 の座標を計算して利用しない限り問題は発生しないでしょう。

マークを配置する際に、TwoBitBoard3x3 の座標を xy_to_move や、今後実装する予定の calc_legal_moves で計算する
マークを削除する際に、過去に着手を行った際に利用した TwoBitBoard3x3 の座標を利用する

変数 a の値を 0 から 1、または 1 から 0 に変更 する方法は、他にも 1 との XOR 演算を行う a ^ 1 や、1 - a という式 で行うこともできます。

下記のプログラムは 3 つの方法で正しく計算されること と、それらの処理時間を計測 するプログラムです。a を 0 とした場合で 2 回ずつ計算を行う ことで、実行結果から 0 が 1 に、1 が 0 に 正しく計算されることが確認 できます。

a = 0
a ^= 1
print(a)
a ^= 1
print(a)
a = 1 - a
print(a)
a = 1 - a
print(a)
a = 0 if a else 1
print(a)
a = 0 if a else 1
print(a)
a = 0
%timeit a ^ 1
%timeit 1 - a
%timeit 0 if a else 1
a = 1
%timeit a ^ 1
%timeit 1 - a
%timeit 0 if a else 1

実行結果

1
0
1
0
1
0
29.2 ns ± 0.176 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
21.5 ns ± 0.12 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
20.5 ns ± 0.269 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
30 ns ± 0.32 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
21.5 ns ± 0.187 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
16.7 ns ± 0.0679 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

下記は上記の実行結果をまとめた表です。表から Python では 0 if a else 1 が処理速度が平均では最も速い ことが確認できます。なお、他のプログラム言語では違う結果になる場合があるのではないか と思います。

`a` の値	`a ^ 1`	`1 - a`	`0 if a else 1`
`0`	29.2 ns	20.5 ns	21.5 ns
`1`	21.5 ns	30.0 ns	16.7 ns
平均	25.4 ns	25.3 ns	19.1 ns

`getmark_by_move` メソッドの定義

BitBoard3x3 クラスの getmark_by_move の処理では、下記のプログラムのように 〇のビットボードの (x, y) のマスに マークが配置されいるかを判定 し、配置されていなければ × のビットボードの (x, y) のマスに マークが配置されているかの判定 を行う必要がありました。

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

同様の方法 で TwoBitBoard3x3 クラスの getmark_by_move の計算を行う場合は、下記のようなアルゴリズムになるでしょう。

self.board & move が 0 でない場合 は 現在の局面の手番のマークが配置 されている
現在の局面の手番が〇の場合 は、同じマスの × のマークのマス の ビットの番号 は 〇のマークのビットの番号より 1 大きい ので self.board & (move << 1) が 0 でない場合 は × のマークが配置 されている
現在の局面の手番が × の場合 は、同じマスの〇のマークのマス の ビットの番号 は × のマークのビットの番号より 1 小さい ので self.board & (move >> 1) が 0 でない場合 は 〇のマークが配置 されている
上記の どれでもなければマークは配置されていない

上記の 手順 2、3 の処理 は明らかに BitBoard3x3 クラスの getmark_by_move の処理よりも複雑 なので 処理時間が長くなる という問題があるため 別のアルゴリズムを紹介 します。

if 文を利用しないアルゴリズム

TwoBitBoard3x3 クラスでは 空のマス を表す EMPTY を 0、〇と × のマーク を表す CIRCLE と CROSS を 1、2 とすることで、if 文による条件分岐を利用しない アルゴリズムで (x, y) のマスのマークを計算 することができます。

先程説明したように、(x, y) のマスに対応する 〇と × のビットの値を右から順に並べる と 下記の表 のようになります。また、並べたビットの値を 10 進数に直す と下記の表のように 空のマス の場合は EMPTY と同じ 0 に、〇のマス の場合は CIRCLE と同じ 1 に、× のマス の場合は CROSS と同じ 2 になります。

	2 つのビット	10 進数での値
空のマス	`00`	`0`
〇のマス	`01`	`1`
× のマス	`10`	`2`

上記から、(x, y) のマスに対応する〇と × のビットの値 が 0 番と 1 番のビットの値になるビット列を計算 することで (x, y) のマスのマーク を if 文を使わずに計算できる ことがわかりました。これが、EMPTY、CIRCLE、CROSS の値を 0、1、2 に設定した理由 です。

また、そのような値は 下記のアルゴリズムで計算 することができます。

ゲーム盤を表す self.board の中 で (x, y) のマスを表すビットの番号 は y * 2 + x * 6 と y * 2 + x * 6 + 1 なので、self.board を y * 2 + x * 6 ビット右シフト した self.board >> (y * 2 + x * 6) を計算 することで、それらのビットが 0 番と 1 番のビットに移動したビット列が計算 される
手順 1 で計算したビット列の 0 番と 1 番以外のビットを 0 とするために、下記の式で 0 番と 1 番のビットだけが 1 である 0b11 との AND 演算 を行う

(self.board >> (y * 2 + x * 6)) & 0b11

下図は上記のアルゴリズムで (1, 1) のマスに対応する 〇と × のビットの値 が、0 番と 1 番のビットの値になるビット列を計算 する処理を表したものです。図の灰色のマスは 最終的な計算結果に影響を及ぼさない ビットを、白色のマスは 必ず 0 になる ビットを表します。

上図の 上部の手順 1 では 1 * 2 + 1 * 6 = 8 ビットの右シフト演算 を行うことで　(1, 1) のマスに対応する 〇と × のビットの値 が 0 番と 1 番のビットに移動 したビット列の計算を行います。図からわかるように 2 ~ 9 番のビット には 元の 10 ~ 17 番のビットの値が計算 されるので、それらのビットの値を 0 にする ために上図の 下部の手順 2 では 0b11 との AND 演算 を行います。

右シフト演算のビット数を計算するアルゴリズム

先程の 手順 1 で行う 右シフト演算のビット数 は、下記の手順で TwoBitBoard3x3 の座標 を表す move から計算 することができます。

move_to_xy メソッドで (x, y) の座標を計算 する
x * 2 + y * 6 を計算する

ただし、上記のアルゴリズムは下記の move_to_xy メソッド内の move.bitlength() - 1 で 1 となるビットの番号を計算した値を利用 して (x, y) の座標を計算する必要 がある点が 効率が悪い という問題があります。(x, y) の座標を計算しない 効率の良いアルゴリズムがあるのでその方法について少し考えてみて下さい。

def move_to_xy(self, move):
    move = (move.bit_length() - 1) // 2
    return move // self.BOARD_SIZE, move % self.BOARD_SIZE

x * 2 + y * 6 は、下記の理由から move.bit_length() - 1 の 0 番のビットを 0 にする という計算を行うことで求めることができます。

〇の手番 の局面の場合
- move.bit_length() - 1 = y * 2 + x * 6 となる
- x と y は整数 なので y * 2 + x * 6 は偶数 になる
- 偶数を表すビット列 は 1 の位 を表す 0 番のビットの値が 0 になる
- 従って move.bit_length() - 1 の 0 番のビットは元々 0 なので、move.bit_length() - 1 の 0 番のビットを 0 にした値 は y * 2 + x * 6 となる
× の手番の局面 の場合
- move.bit_length() - 1 = y * 2 + x * 6 + 1 となる
- x と y は整数 なので y * 2 + x * 6 + 1 は奇数 になる
- 奇数を表すビット列 は 1 の位 を表す 0 番のビットの値が 1 になる
- 0 番のビットが 1 の場合 に 0 番のビットを 0 にすると 値が 1 小さくなる
- 従って move.bit_length() - 1 の 0 番のビットを 0 にした値は y * 2 + x * 6 + 1 - 1 = y * 2 + x * 6 となる

ビット列 b の 0 番のビットを 0 にするアルゴリズムを 2 つ紹介します。

0 番のビットだけを 0 とした ~0b1 との AND 演算 を行う
1 ビット右シフト演算 を行った値に対して 1 ビット左シフト演算 を行う。1 ビット右シフト演算 を行うことで 0 番のビットの値がなくなり、その値に対して 1 ビット左シフト演算 を行うことで 元の値の 0 番のビットが 0 の値が計算 される

下記は 0b1001 と 0b1000 に対して上記の計算を行うプログラムです。実行結果から 正しい値が計算されることが確認 できます。なお、以前の記事で説明したように Python では ~x = -(x + 1) なので ~1 = -(1 + 1) = -2 になります。

print(bin(0b1000 & -2))
print(bin(0b1001 & -2))
print(bin(0b1000 >> 1 << 1))
print(bin(0b1001 >> 1 << 1))

実行結果

下記は 上記の処理時間を計測 するプログラムです。実行結果から 処理速度はほぼ同じ であることが確認できました。本記事では 短く記述できる前者の方法を採用 することにします。

%timeit 0b1000 & -2
%timeit 0b1001 & -2
%timeit 0b1000 >> 1 << 1
%timeit 0b1001 >> 1 << 1

実行結果

9.92 ns ± 0.0568 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
10.1 ns ± 0.167 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
9.89 ns ± 0.012 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)
10 ns ± 0.125 ns per loop (mean ± std. dev. of 7 runs, 100,000,000 loops each)

下記は上記のアルゴリズムで getmark_by_move を定義したプログラムです。

1  def getmark_by_move(self, move):
2      return (self.board >> ((move.bit_length() - 1) & -2)) & 0b11
3  
4  TwoBitBoard3x3.getmark_by_move = getmark_by_move

行番号のないプログラム

def getmark_by_move(self, move):
    return (self.board >> ((move.bit_length() - 1) & -2)) & 0b11

TwoBitBoard3x3.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
+   return (self.board >> ((move.bit_length() - 1) & -2)) & 0b11

TwoBitBoard3x3.getmark_by_move = getmark_by_move

処理の確認と処理時間の比較

下記の処理を行うことで setmark_by_move と getmark_by_move の処理が 正しく行われることを確認 することにします。

setmark_by_move で (0, 0) に〇 を、(1, 0) に × を配置 する
getmark_by_move で (0, 0)、(1, 0)、(2, 0) の マスのマーク を 〇と × のそれぞれの手番の TwoBitBoard3x3 の座標で計算 することで、〇、×、空のマスのマークを正しく計算できる ことを確認する
setmark_by_move で (0, 0) の 〇のマークを削除 する
getmark_by_move で (0, 0) の マスのマーク を 〇と × のそれぞれの手番の TwoBitBoard3x3 の座標で計算 することで、(0, 0) の マスのマークが正しく削除されたことを確認 する

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

2 ~ 4 行目：〇の手番の (0, 0)、(1, 0)、(2, 0) の TwoBitBoard3x3 の座標を計算する
5 ~ 8 行目：× の手番の (0, 0)、(1, 0)、(2, 0) の TwoBitBoard3x3 の座標を計算する
9 行目：(0, 0) のマスに 〇を着手 する。先ほど説明したように 仮引数 mark の値は利用されない ので、〇のマークを配置するため には move に〇の手番の座標を代入する必要 がある点に注意すること
10 行目：(1, 0) のマスに × を着手 する。move に × の手番の座標を代入する必要 がある点に注意すること
11 ~ 16 行目：〇と × のそれぞれの手番の座標 を利用して (0, 0)、(1, 0)、(2, 0) のマスの マークを計算 する
17 行目：(0, 0) のマスの 〇のマークを削除 する。move に〇の手番の座標を代入する必要 がある点に注意すること
18、19 行目：〇と × の手番の座標 を利用して (0, 0) のマスの マークを計算 する

 1  bb = TwoBitBoard3x3()
 2  m1 = bb.xy_to_move(0, 0)
 3  m2 = bb.xy_to_move(1, 0)
 4  m3 = bb.xy_to_move(2, 0)
 5  bb.crossturn = 1
 6  m4 = bb.xy_to_move(0, 0)
 7  m5 = bb.xy_to_move(1, 0)
 8  m6 = bb.xy_to_move(2, 0)
 9  bb.setmark_by_move(m1, bb.CIRCLE)
10  bb.setmark_by_move(m5, bb.CROSS)
11  print(bb.getmark_by_move(m1))
12  print(bb.getmark_by_move(m4))
13  print(bb.getmark_by_move(m2))
14  print(bb.getmark_by_move(m5))
15  print(bb.getmark_by_move(m3))
16  print(bb.getmark_by_move(m6))
17  bb.setmark_by_move(m1, bb.EMPTY)
18  print(bb.getmark_by_move(m1))
19  print(bb.getmark_by_move(m4))

行番号のないプログラム

bb = TwoBitBoard3x3()
m1 = bb.xy_to_move(0, 0)
m2 = bb.xy_to_move(1, 0)
m3 = bb.xy_to_move(2, 0)
bb.crossturn = 1
m4 = bb.xy_to_move(0, 0)
m5 = bb.xy_to_move(1, 0)
m6 = bb.xy_to_move(2, 0)
bb.setmark_by_move(m1, bb.CIRCLE)
bb.setmark_by_move(m5, bb.CROSS)
print(bb.getmark_by_move(m1))
print(bb.getmark_by_move(m4))
print(bb.getmark_by_move(m2))
print(bb.getmark_by_move(m5))
print(bb.getmark_by_move(m3))
print(bb.getmark_by_move(m6))
bb.setmark_by_move(m1, bb.EMPTY)
print(bb.getmark_by_move(m1))
print(bb.getmark_by_move(m4))

実行結果

EMPTY = 0、CIRCLE = 1、CROSS = 2 と 実行結果を照らし合わせる ことで 正しい値が計算されることが確認 できます。

処理時間の比較

下記は BitBoard3x3 クラスと TwoBitBoard3x3 クラスの setmark_by_move と getmark_by_move メソッドの 処理時間を計測 するプログラムです。それぞれのクラスで (0, 0) のマスに対して 〇を配置、マークを削除、× を配置 する処理と そのマスのマークを計算する処理 の 処理時間を計測 しました。TwoBitBoard3x3 クラスの場合は × を配置する際に座標を計算し直す必要がある 点に注意して下さい。

bb = BitBoard3x3()
tb = TwoBitBoard3x3()
m1 = bb.xy_to_move(0, 0)
m2 = tb.xy_to_move(0, 0)
# 〇 を配置する
print("〇 の配置")
print("setmark_by_move")
%timeit bb.setmark_by_move(m1, bb.CIRCLE)
%timeit tb.setmark_by_move(m2, tb.CIRCLE)
print("getmark_by_move")
%timeit bb.getmark_by_move(m1)
%timeit tb.getmark_by_move(m2)
# 〇 を削除する
print("〇 の削除")
print("setmark_by_move")
%timeit bb.setmark_by_move(m1, bb.EMPTY)
%timeit tb.setmark_by_move(m2, tb.EMPTY)
print("getmark_by_move")
%timeit bb.getmark_by_move(m1)
%timeit tb.getmark_by_move(m2)
# × を配置する
print("× の配置")
print("setmark_by_move")
tb.crossturn = 1
m2 = tb.xy_to_move(0, 0)
%timeit bb.setmark_by_move(m1, bb.CROSS)
%timeit tb.setmark_by_move(m2, tb.CROSS)
print("getmark_by_move")
%timeit bb.getmark_by_move(m1)
%timeit tb.getmark_by_move(m2)

実行結果

〇 の配置
setmark_by_move
125 ns ± 0.312 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
133 ns ± 2.48 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
97.6 ns ± 1.28 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
161 ns ± 2.14 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
〇 の削除
setmark_by_move
220 ns ± 20.8 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
134 ns ± 0.213 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
145 ns ± 0.512 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
155 ns ± 2.49 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
× の配置
setmark_by_move
126 ns ± 0.957 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
134 ns ± 1.73 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
getmark_by_move
128 ns ± 0.968 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
164 ns ± 2.2 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は上記の実行結果の setmark_by_move の 処理時間をまとめた表 です。〇と × の配置 の場合は BitBoard3x3 クラスの方が 処理時間が若干短く なります。これは TwoBitBoard3x3 クラスの場合は crossturn 属性の値を計算する処理を行う必要がある ためだと考えられます。マークの削除 の場合に BitBoard3x3 クラスの方が 処理時間が約 2 倍ほど長い のは BitBoard3x3 クラスでは 〇と × の両方のビットボードに対する処理を行うから です。また、平均では TwoBitBoard3x3 クラスの方が処理時間が短くなる ことがわかります。

	BitBoard3x3	TwoBitBoard3x3
〇の配置	125 ns	133 ns
× の配置	126 ns	134 ns
マークの削除	220 ns	134 ns
平均	157 ns	134 ns

下記は上記の getmark_by_move の 実行結果をまとめた表 です。BitBoard3x3 クラスの場合は 〇が配置されている場合 は 最初の if 文の条件式の計算だけで処理が終わる ので 処理時間が短く なりますが、TwoBitBoard3x3 クラスの場合は マスのマークの種類に関わらず 常に 同じ計算を行う ので 処理時間はほぼ同じ になります。また、残念ながらいずれの場合でも TwoBitBoard3x3 クラスのほうが 処理速度が遅くなる ことがわかります。

	BitBoard3x3	TwoBitBoard3x3
〇のマス	97.6 ns	161 ns
× のマス	128 ns	164 ns
空のマス	145 ns	155 ns
平均	124 ns	160 ns

参照テーブルを利用した `getmark_by_move` の改良

TwoBitBoard3x3 クラスの getmark_by_move メソッドが遅い理由 は、右シフト演算を行うビット数を計算する処理が複雑 だからです。そこで、その値をあらかじめ計算した 参照テーブル を作成し、TwoBitBoard3x3 クラスの shiftbit_table というクラス属性に代入 して利用することにします。

下記は shiftbit_table を計算 するプログラムです。なお、下記のプログラムは marubatsu.py のほうでは TwoBitBoard3x3 クラスの定義の直後に記述 することにします。

1 行目：shiftbit_table を空の dict で初期化する
2 ~ 7 行目：2 重の for 文ですべてのマスに対する繰り返し処理を行う
4 行目：(x, y) のマスに対して右シフトを行うビット数を計算する
5 行目：(x, y) の〇のマスに対する TwoBitBoard3x3 の座標を計算する
6 行目：shiftbit_table に (x, y) の〇のマスに対する TwoBitBoard3x3 の座標の右シフトを行うビット数を記録する
7 行目：× のマスに対する TwoBitBoard3x3 の座標は〇のマスに対する TwoBitBoard3x3 の座標を 1 ビット左シフトした値なので、その計算を行うことで shiftbit_table に (x, y) の × のマスに対する TwoBitBoard3x3 の座標の右シフトを行うビット数を記録する

1  shiftbit_table = {}
2  for x in range(3):
3      for y in range(3):
4          shiftbit = x * 2 + y * 6
5          move = 1 << shiftbit
6          shiftbit_table[move] = shiftbit
7          shiftbit_table[move << 1] = shiftbit
8  
9  TwoBitBoard3x3.shiftbit_table = shiftbit_table

行番号のないプログラム

shiftbit_table = {}
for x in range(3):
    for y in range(3):
        shiftbit = x * 2 + y * 6
        move = 1 << shiftbit
        shiftbit_table[move] = shiftbit
        shiftbit_table[move << 1] = shiftbit

TwoBitBoard3x3.shiftbit_table = shiftbit_table

下記は上記で計算した 参照テーブルを利用 するように getmark_by_move メソッドの 2 行目を修正 したプログラムです。

1  def getmark_by_move(self, move):
2      return (self.board >> self.shiftbit_table[move]) & 0b11
3  
4  TwoBitBoard3x3.getmark_by_move = getmark_by_move

行番号のないプログラム

def getmark_by_move(self, move):
    return (self.board >> self.shiftbit_table[move]) & 0b11

TwoBitBoard3x3.getmark_by_move = getmark_by_move

修正箇所

def getmark_by_move(self, move):
-   return (self.board >> ((move.bit_length() - 1) & -2)) & 0b11
+   return (self.board >> self.shiftbit_table[move]) & 0b11

TwoBitBoard3x3.getmark_by_move = getmark_by_move

実行結果は同じなので省略しますが、下記のプログラムを実行すると 先程と同じ実行結果 になるので getmark_by_move が正しく動作することが確認 できます。

bb = TwoBitBoard3x3()
m1 = bb.xy_to_move(0, 0)
m2 = bb.xy_to_move(1, 0)
m3 = bb.xy_to_move(2, 0)
bb.crossturn = 1
m4 = bb.xy_to_move(0, 0)
m5 = bb.xy_to_move(1, 0)
m6 = bb.xy_to_move(2, 0)
bb.setmark_by_move(m1, bb.CIRCLE)
bb.setmark_by_move(m5, bb.CROSS)
print(bb.getmark_by_move(m1))
print(bb.getmark_by_move(m4))
print(bb.getmark_by_move(m2))
print(bb.getmark_by_move(m5))
print(bb.getmark_by_move(m3))
print(bb.getmark_by_move(m6))
bb.setmark_by_move(m1, bb.EMPTY)
print(bb.getmark_by_move(m1))
print(bb.getmark_by_move(m4))

下記は先ほどのプログラムを修正して TwoBitBoard3x3 クラスの getmark_by_move の処理時間だけを計測するプログラムです。

tb = TwoBitBoard3x3()
m2 = tb.xy_to_move(0, 0)
# 〇 を配置する
print("〇 の配置")
tb.setmark_by_move(m2, tb.CIRCLE)
%timeit tb.getmark_by_move(m2)
# 〇 を削除する
print("〇 の削除")
tb.setmark_by_move(m2, tb.EMPTY)
%timeit tb.getmark_by_move(m2)
# × を配置する
print("× の配置")
tb.crossturn = 1
m2 = tb.xy_to_move(0, 0)
tb.setmark_by_move(m2, tb.CROSS)
%timeit tb.getmark_by_move(m2)

実行結果

〇 の配置
122 ns ± 1.05 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
〇 の削除
113 ns ± 0.144 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
× の配置
122 ns ± 0.948 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

下記は先ほどの表に上記の実行結果を加えた表です。TwoBitBoard3x3 の 下段が上記の実行結果 を表します。表から 処理速度が向上 し、〇のマス以外 では TwoBitBoard3x3 クラスの方が 処理速度が速くなり、平均でもほんの少し速くなる ことが確認できました。

	BitBoard3x3	TwoBitBoard3x3
〇のマス	97.6 ns	161 ns 122 ns
× のマス	128 ns	164 ns 122 ns
空のマス	145 ns	155 ns 113 ns
平均	124 ns	160 ns 119 ns

上記から、TwoBitBoard3x3 クラスの setmark_by_move と getmark_by_move の 処理速度 は平均では BitBoard3x3 クラスよりほんの少し速くなる ことがわかりました。

`judge` メソッドの定義

Marubatsu クラスの cmove メソッドで 着手を行うことができるようにする ためには、勝敗判定を行う judge メソッドが必要 になるので judge メソッドを定義 することにします。

下記は BitBoard3x3 クラスの judge メソッドの定義で、直前に行った着手 を表す last_move のマスを含む 各直線上のマスのビットを 1 とする ビットマスクの一覧 をあらかじめ計算して記録した 参照テーブル である move_to_masklist を利用して判定 を行います。

 1  def judge(self, last_turn, last_move, move_count):
 2      if move_count < 5:
 3          return Marubatsu.PLAYING
 4      # 直前に着手を行ったプレイヤーの勝利の判定
 5      board = self.board[last_turn]
 6      for bitmask in self.move_to_masklist[last_move]:
 7          if board & bitmask == bitmask:
 8              return last_turn
 9      # 引き分けの判定
10      if move_count == self.bit_length:
11          return Marubatsu.DRAW
12      # 上記のどれでもなければ決着がついていない
13      else:
14          return Marubatsu.PLAYING

TwoBitBoard3x3 クラスの場合は手番によって 各直線上のマスのビットを 1 とするビットマスクの一覧が異なる ので、move_to_masklist の 計算処理 を下記のプログラムのように 修正する必要 があります。

1 ~ 4 行目：各列、各行、各対角線 の 〇の手番 で着手した場合に対応する ビットマスク を記録するように修正する
8 行目：〇の手番 の場合の (x, y) の TwoBitBoard3x3 の座標を計算 する
9 行目：〇の手番 の場合の (x, y) に着手 した場合の x 列と y 行のビットマスク を 参照テーブルに記録 する。この部分の処理は元のプログラムと同じ
10 行目：× の手番 の場合の (x, y) に着手 した場合の x 列と y 行のビットマスク を 参照テーブルに記録 する。× の手番 のマスの ビットの番号 は 〇の手番 のマスの ビットの番号 + 1 なので、(x, y) の TwoBitBoard3x3 の座標 と x 列と y 行のビットマスク は、〇の手番の場合のビット列を 1 ビット左シフト することで計算できる
11 ~ 16 行目：2 つの対角線 の場合に対して 上記と同様の計算 を行う

 1  colmasks = [0b000000000000010101, 0b000000010101000000, 0b010101000000000000]
 2  rowmasks = [0b000001000001000001, 0b000100000100000100, 0b010000010000010000]
 3  diamask1 = 0b010000000100000001
 4  diamask2 = 0b000001000100010000
 5  move_to_masklist = {}
 6  for x in range(3):
 7      for y in range(3):
 8          move = 1 << (y * 2 + x * 6)
 9          move_to_masklist[move] = [colmasks[x], rowmasks[y]]
10          move_to_masklist[move << 1] = [colmasks[x] << 1, rowmasks[y] << 1]
11          if x == y:
12              move_to_masklist[move].append(diamask1)
13              move_to_masklist[move << 1].append(diamask1 << 1)
14          if x + y == 2:
15              move_to_masklist[move].append(diamask2)
16              move_to_masklist[move << 1].append(diamask2 << 1)
17  
18  TwoBitBoard3x3.move_to_masklist = move_to_masklist

行番号のないプログラム

colmasks = [0b000000000000010101, 0b000000010101000000, 0b010101000000000000]
rowmasks = [0b000001000001000001, 0b000100000100000100, 0b010000010000010000]
diamask1 = 0b010000000100000001
diamask2 = 0b000001000100010000
move_to_masklist = {}
for x in range(3):
    for y in range(3):
        move = 1 << (y * 2 + x * 6)
        move_to_masklist[move] = [colmasks[x], rowmasks[y]]
        move_to_masklist[move << 1] = [colmasks[x] << 1, rowmasks[y] << 1]
        if x == y:
            move_to_masklist[move].append(diamask1)
            move_to_masklist[move << 1].append(diamask1 << 1)
        if x + y == 2:
            move_to_masklist[move].append(diamask2)
            move_to_masklist[move << 1].append(diamask2 << 1)

TwoBitBoard3x3.move_to_masklist = move_to_masklist

修正箇所

-colmasks = [0b000000111, 0b000111000, 0b111000000]
+colmasks = [0b000000000000010101, 0b000000010101000000, 0b010101000000000000]
-rowmasks = [0b001001001, 0b010010010, 0b100100100]
+rowmasks = [0b000001000001000001, 0b000100000100000100, 0b010000010000010000]
-diamask1 = 0b100010001
+diamask1 = 0b010000000100000001
-diamask2 = 0b001010100
+diamask2 = 0b000001000100010000
move_to_masklist = {}
for x in range(3):
    for y in range(3):
-       move = 1 << (y + 3 * x)
+       move = 1 << (y * 2 + x * 6)
        move_to_masklist[move] = [colmasks[x], rowmasks[y]]
+       move_to_masklist[move << 1] = [colmasks[x] << 1, rowmasks[y] << 1]
        if x == y:
            move_to_masklist[move].append(diamask1)
+           move_to_masklist[move << 1].append(diamask1 << 1)
        if x + y == 2:
            move_to_masklist[move].append(diamask2)
+            move_to_masklist[move << 1].append(diamask2 << 1)

TwoBitBoard3x3.move_to_masklist = move_to_masklist

judge メソッドでは 引き分けの判定 を 手数を表す move_count が self.bit_length と等しいかどうか で判定していましたが、self.bit_length の値が 9 から 18 に変化 したので、下記のプログラムの 9 行目 のように self.bit_length を 9 に修正する必要 があります。それ以外の部分は修正する必要はありません。

 1  def judge(self, last_turn, last_move, move_count):
 2      if move_count < 5:
 3          return Marubatsu.PLAYING
 4      # 直前に着手を行ったプレイヤーの勝利の判定
 5      for bitmask in self.move_to_masklist[last_move]:
 6          if self.board & bitmask == bitmask:
 7              return last_turn
 8      # 引き分けの判定
 9      if move_count == 9:
10          return Marubatsu.DRAW
11      # 上記のどれでもなければ決着がついていない
12      else:
13          return Marubatsu.PLAYING  
14  
15  TwoBitBoard3x3.judge = judge

行番号のないプログラム

def judge(self, last_turn, last_move, move_count):
    if move_count < 5:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    for bitmask in self.move_to_masklist[last_move]:
        if self.board & bitmask == bitmask:
            return last_turn
    # 引き分けの判定
    if move_count == 9:
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING  

TwoBitBoard3x3.judge = judge

修正箇所

def judge(self, last_turn, last_move, move_count):
    if move_count < 5:
        return Marubatsu.PLAYING
    # 直前に着手を行ったプレイヤーの勝利の判定
    for bitmask in self.move_to_masklist[last_move]:
        if self.board & bitmask == bitmask:
            return last_turn
    # 引き分けの判定
-   if move_count == self.bit_length:
+   if move_count == 9:
        return Marubatsu.DRAW
    # 上記のどれでもなければ決着がついていない
    else:
        return Marubatsu.PLAYING  

TwoBitBoard3x3.judge = judge

動作の確認とバグの検証

judge メソッドが正しく判定を行うか どうかを、(0, 0), (1, 0), (0, 1), (1, 1), (0, 2) の順 で着手を行う下記のプログラムで 確認する ことにします。実行結果から 正しいマスに着手が行われる ことは確認できますが、最後の 〇が勝利している局面の上部の表示 が Turn x となっていることから 〇の勝利が正しく判定できていない ことが確認できます。

mb = Marubatsu(boardclass=TwoBitBoard3x3)
print(mb)
for x, y in [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2)]:
    mb.cmove(x, y)
    print(mb)

実行結果

Turn o
...
...
...

Turn x
O..
...
...

Turn o
oX.
...
...

Turn x
ox.
O..
...

Turn o
ox.
oX.
...

Turn x
ox.
ox.
O..

judge メソッドの判定の処理は、直前の着手 を表す last_move 属性を利用しているので、その値が間違っている可能性 があります。そこで、下記のプログラムで ゲーム開始時の局面で (0, 0) に着手を行った場合 の last_move 属性の値を表示 してみることにします。

mb = Marubatsu(boardclass=TwoBitBoard3x3)
mb.cmove(0, 0)
print(mb)
print(bin(mb.last_move))

実行結果

Turn x
O..
...
...

0b10

実行結果から 直前の着手 を表す last_move 属性の値 は 1 番のビットが 1 となる 0b10 になることが確認できました。これは (0, 0) マスの × の手番に対応 する TwoBitBoard3x3 の座標 ですが、直前の着手 では (0, 0) に〇を着手 しています。従って、last_move 属性に代入された TwoBitBoard3x3 の座標 の 手番が間違っている ことが確認できました。

バグの修正

下記は先程のプログラムで ゲーム盤に着手 を行う際に呼び出した Marubatsu クラスの cmove メソッドのプログラムです。このプログラムでは 2 行目 で Marubatsu クラスの place_mark メソッドを呼び出すことで 着手を試み、着手が行なえた場合は 3 行目 で 着手を行ったマス の ゲーム盤を表すクラスの座標を計算 しています。

1  def cmove(self, x, y):
2      if self.place_mark(x, y, self.turn):
3          move = self.board.xy_to_move(int(x), int(y))
4          self.move(move, placed=True)

TwoBitBoard3x3 以外のクラス では この処理で問題はありません が、TwoBitBoard3x3 クラスの場合は place_mark メソッド内でゲーム盤を表すクラスの setmark_by_move メソッドで 実際の着手が行われてしまう ため crossturn 属性の値が 次の手番の値に変化 してしまいます。そのため、3 行目で move を計算 すると実際に着手を行った局面の 次の手番 の TwoBitBoard3x3 の座標 が計算されてしまいます。

従って、この問題を解決するためには下記のプログラムのように move の計算処理 を place_mark を呼び出す前に移動 する必要があります。ただし、x や y に代入された値によって は int(x) や int(y) でエラーが発生する可能性がある ので、下記のプログラムでは以前の記事で説明した例外処理を利用してエラーが発生しないようにしました。

2 ~ 5 行目：move の計算処理を place_mark メソッドより前で行うように修正した。また、try 文の中で処理を行い、except 文に何も処理を行わない pass を記述することで、エラーが発生した場合に何も処理を行わないように修正した

1  def cmove(self, x, y):
2      try:
3          move = self.board.xy_to_move(int(x), int(y))
4      except:
5          pass
6      if self.place_mark(x, y, self.turn):
7          self.move(move, placed=True) 
8  
9  Marubatsu.cmove = cmove

行番号のないプログラム

def cmove(self, x, y):
    try:
        move = self.board.xy_to_move(int(x), int(y))
    except:
        pass
    if self.place_mark(x, y, self.turn):
        self.move(move, placed=True) 

Marubatsu.cmove = cmove

修正箇所

def cmove(self, x, y):
+   try:
+       move = self.board.xy_to_move(int(x), int(y))
+   except:
+       pass
    if self.place_mark(x, y, self.turn):
-       move = self.board.xy_to_move(int(x), int(y))
        self.move(move, placed=True) 

Marubatsu.cmove = cmove

上記の修正後に 先程と同じ下記のプログラム を実行すると、実行結果の 0b1 のように last_move 属性の値 が 0 番のビットが 1 となる 0b1 になることが確認できました。これは (0, 0) マスの 〇の手番に対応 する TwoBitBoard3x3 の座標 なので、正しい計算が行われる ようになったことが確認できました。

mb = Marubatsu(boardclass=TwoBitBoard3x3)
mb.cmove(0, 0)
print(mb)
print(bin(mb.last_move))

実行結果

Turn x
O..
...
...

0b1

cmove メソッドの 3 行目の計算 で エラーが発生した場合 は、place_mark メソッド内で同じ処理が行われている ので、そこでエラーメッセージが表示 されます。

下記は cmove メソッドの 仮引数 x と y に組み込み関数 int で整数に変換できない "x" と "y" を代入するプログラムで、実行結果の エラーメッセージ は place_mark メソッド内の処理で表示 されています。

mb = Marubatsu(boardclass=TwoBitBoard3x3)
mb.cmove("x", "y")

実行結果

整数の座標を入力して下さい

Marubatsu クラスの cmove メソッドを利用せずに、move メソッドで直接着手を行う場合 は TwoBitBoard3x3 クラスの setmark_by_move メソッドで 着手を行う際利用 した TwoBitBoard3x3 の座標 が そのまま last_move 属性に代入される ので上記のような 問題は発生しません。

先程と同じ下記のプログラムで judge メソッドが正しく判定を行うか どうかを確認すると、実行結果から最後の 〇が勝利している局面の上部の表示 が winner o となっていることから 〇の勝利が正しく判定できている ことが確認できます。

mb = Marubatsu(boardclass=TwoBitBoard3x3)
print(mb)
for x, y in [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2)]:
    mb.cmove(x, y)
    print(mb)

実行結果

Turn o
...
...
...

Turn x
O..
...
...

Turn o
oX.
...
...

Turn x
ox.
O..
...

Turn o
ox.
oX.
...

winner o
ox.
ox.
O..

下記は以前の記事で定義した test_judge で judge メソッドが正しく動作するかをテスト するプログラムです。実行結果から 正しい判定を行うことができることが確認 できました。

from mbtest import test_judge

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

実行結果

Start
test winner = playing
oooooooooo
test winner = 1
ooooooooo
test winner = 2
oooooooo
test winner = draw
o
Finished

なお、BitBoard3x3 クラスと TwoBitBoard3x3 クラスの judge メソッドが 行う処理は同じ なので 処理速度はほぼ変わらない と思います。興味がある方は実際に確認してみて下さい。

今回の記事のまとめ

今回の記事では 一つのビット列 でゲーム盤を扱う TwoBitBoard3x3 クラス の定義を開始し、initialize、xy_to_move、move_to_xy、getmark_by_move、setmark_by_move、judge メソッドを定義しました。次回の記事では残りのメソッドを定義します。

なお、今回の記事で AI どうしの対戦を行わなかったのは、AI どうしの対戦を行うために必要 となる calc_legal_moves メソッドをまだ実装してい ないからです。

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

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

次回の記事

クラスの名前の先頭にアラビア数字を使うことはできないので、英語の Two を先頭にしました ↩