@ysgesoPythonで〇×ゲームのAIを一から作成するその223 一つのビット列で表現されたゲーム盤の合法手の一覧の計算と反転・転置処理Python解説AI〇×ゲーム一から作る0Posted 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 クラスでは同じマスを表す〇と × のビットが並んで配置されているので、以下の手順で上記と同様の計算を行うことができます。 self.board を右シフト演算で 1 ビット右にずらした self.board >> 1 を計算するこで、× のビットが同じマスの〇のビットの位置に移動したビット列が計算される上記で計算した値と self.board との OR 演算を行う self.board | (self.board >> 1) を計算することで、〇のマスを表すビットにそのマスにマークが配置されている場合は 1 が、配置されていない場合は 0 が計算される × のマスを表すビットには必要のない値が計算されているので〇を表すマスのビットだけが 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(, {(2, 0, 1): 1, (0, 1, 2): 1, (0, 0, 3): 3, (1, 1, 1): 1, (1, 0, 2): 2}) defaultdict(, {(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. ..

ipu

📬 Get AI News Delivered

Browse by Category

Trending Topics

The Cure for GPU Shortages? Inside the Google & Intel Alliance and the Power of IPUs

Analysis

China's AI Unicorns Evolve: The Leap from 大语言模型 (LLM) to Agent Platforms

Analysis

Building Tic-Tac-Toe AI from Scratch #223: Mastering Bitboard Operations for Legal Moves

Analysis

Zhipu Accelerates Cloud API Growth, Pioneering the Path as China's Leading AI Powerhouse

Analysis

Google and Intel Deepen Partnership to Revolutionize AI Infrastructure

Analysis

Google and Intel Deepen AI Infrastructure Partnership to Power Next-Generation Cloud

Analysis

Intel and Google Forge Multi-Year Alliance to Supercharge Next-Gen AI Cloud Infrastructure

Analysis

Google and Intel Deepen Partnership with Custom Xeon 6 Chips to Boost Cloud Efficiency

Analysis

The Remarkable Rise of China's AI Leaders: Breaking Through with Massive Token Scale

Analysis

How Yizhuang is Transforming into China's Ultimate AI Powerhouse

Analysis

US AI Giants Unite to Define New Standards for Model Development and Innovation

Analysis

Zhipu AI's Revenue Soars, Eyes Token Dominance in the AI Arena!

Analysis

Zhipu AI: Charting a Bold Course in the Generative AI Landscape

Analysis

Zhipu AI's First Financial Report: A Glimpse into the Future of Chinese LLMs

Analysis

Unveiling Intelligent Manipulation: New Research from Stanford and Harvard

Analysis

New AI 'Posture Manipulation' Could Revolutionize How We Interact with Generative AI

Analysis

AI-Enhanced Image Manipulation: Spotlight on Athletes' Integrity

Analysis

GLM-5.1: Zhipu AI's LLM Matches Coding Prowess of Claude Opus 4.5!

Analysis

VTAM: AI with Touch Senses Achieves 90% Success in Complex Robotic Tasks

Analysis

AI-Powered Image Manipulation Used in Fraud: A Cautionary Tale

Analysis

Zhipu.AI Assures Open Source Future, Addressing Concerns About Closed-Source Large Language Models

Analysis

xAI's AI Tools Face Lawsuit Over Alleged Image Manipulation

Analysis

Unveiling the Best AI Image Detectors: A Practical Guide

Analysis

AI's New Frontier: The Dawn of Answer Optimization

Analysis

AI Marketing Revolution: New Strategies to Shape LLM Responses

Analysis

New Dairy and Tech Giants Eye Hong Kong Listings, Boosting Business Growth!

Analysis

Tencent's Secret AI Agent for WeChat Poised to Revolutionize Messaging

Analysis

Texterial: Sculpting Text with AI – A New Writing Paradigm

Analysis

Zhipu AI's GLM-5: Redefining AI Coding with Superior Performance

Analysis

AI Innovation Buzz: From GLM-5's Rise to Movie Magic with Seedance 2.0

Analysis

📬 Get AI News Delivered

Browse by Category

Trending Topics