今天要來介紹容易被大家忽略的資料結構,棋盤資料結構的設計其實也很有多要注意的,有好的演算法也要搭配好的資料結構才能讓你的AI完美發揮阿!
最常見的莫過於Array了,比如我們前面用二維陣列來表示棋盤。
board = [
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "X", ".", "."],
[".", ".", ".", ".", ".", "X", "O", "X", "."],
[".", ".", ".", ".", ".", ".", "O", "X", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."]
]
不止是棋類遊戲,像是撲克牌類也很輕鬆可以用4x13的二維陣列表達,當然也可以轉成一維陣列的方式,如下圖。
將二維陣列給拉平,0~51分別代表了52張撲克牌。
Mailbox是棋盤類遊戲常用的資料結構,通過在棋盤外加上無效區域,來避免重複的邊界判斷。
程式中的分支條件越多,性能就會越低,比如前面寫圍棋的數氣與數棋串的功能,會用is_in_bounds
來檢查邊界,這個函式會很常被使用到。
# 檢查四個方向
for dx, dy in DIRECTIONS:
nx, ny = x + dx, y + dy
# 檢查是否在邊界內
if is_in_bounds(nx, ny):
if board[nx][ny] == '.':
# 如果是空點,記錄為氣
liberties.add((nx, ny))
elif board[nx][ny] == color:
# 如果是同顏色的棋子,繼續搜尋
dfs(nx, ny)
只要在棋盤外圍加一圈無效區域(標示為 -
的位置),這樣就不用特別判斷是否超出邊界。
a b c d e
1 . . . . .
2 . . . . .
3 . . . . .
4 . . . . .
5 . . . . .
a b c d e
- - - - - - -
1 - . . . . . -
2 - . . . . . -
3 - . . . . . -
4 - . . . . . -
5 - . . . . . -
- - - - - - -
# 檢查四個方向
for dx, dy in DIRECTIONS:
nx, ny = x + dx, y + dy
if board[nx][ny] == '.':
# 如果是空點,記錄為氣
liberties.add((nx, ny))
elif board[nx][ny] == color:
# 如果是同顏色的棋子,繼續搜尋
dfs(nx, ny)
Bitboard 是一種利用位元運算來表示和操作棋盤狀態的資料結構,用0和1來表示該棋子是否在棋盤上,這種資料結構可以使用各種位元運算來快速更新棋盤狀態。
例如西洋棋的棋盤就可以用一個64位元的無號整數來表達:
圖片擷取自維基百科
a7~h7這排小兵在棋盤上就可以表示為:
00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000
為了方便觀看我們通常會轉成16進位表示:0x000000000000FF00
或是直接表示成0xFF00
position = 1 << n // 檢查第n個位置,將1左移n個bit
bitboard & position
position = 1 << n
bitboard |= position
bitboard ^= position
position = 1 << n
bitboard & ~position
bitboard ^= position
Bitboard的效能比起使用Array實在是快得太多,不只效能好,有時候還能做狀態壓縮,這邊先介紹基礎操作,後面會再慢慢介紹到更多功能,通常會用到Bitboard也代表我們很在意效能,就不會用python來實作了。
這邊分享一個圍棋的資料結構設計。
棋串可以被視為棋盤中的一個子圖(sub-graph),每個棋串都是由棋子組成的節點循環圖。以下是這個結構的詳細說明:
這種設計不僅能夠方便管理和操作棋串,還能有效地追蹤每個棋串的氣數和棋子數等資訊,而不必每次進行重新計算。
board position
a b c d e
1| . . . . .
2| . x x x .
3| . . . . .
4| . x x . .
5| . . . . .
vertex position
a b c d e
1| 8 9 10 11 12
2| 15 16 17 18 19
3| 22 23 24 25 26
4| 29 30 31 32 33
5| 36 37 38 39 40
string identity
a b c d e
1| . . . . .
2| . 16 16 16 .
3| . . . . .
4| . 30 30 . .
5| . . . . .
next position
a b c d e
1| . . . . .
2| . 17 18 16 .
3| . . . . .
4| . 31 30 . .
5| . . . . .
當兩個棋串合併時,我們只需要在它們的接觸點處交換 next position,並更新 string identity、string stones以及 string liberty set。
board position
a b c d e
1| . . . . .
2| . x x x .
3| . [x] . . .
4| . x . . .
5| . . . . .
Merge two strings...
string identity
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . 16 16 16 . 2| . 16 16 16 .
3| . 30 . . . >> 3| . 16 . . .
4| . 30 . . . 4| . 16 . . .
5| . . . . . 5| . . . . .
next position
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . 17 18 16 . 2| . 30 18 16 .
3| . 30 . . . >> 3| . 17 . . .
4| . 23 . . . 4| . 23 . . .
5| . . . . . 5| . . . . .
string stones
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . 3 . . . 2| . 5 . . .
3| . . . . . >> 3| . . . . .
4| . 2 . . . 4| . . . . .
5| . . . . . 5| . . . . .
string liberty set
a b c d e a b c d e
1| . . . . . 1| . . . . .
2| . A . . . 2| . C . . .
3| . . . . . >> 3| . . . . . # set C = set A + set B
4| . B . . . 4| . . . . .
5| . . . . . 5| . . . . .
這邊使用Disjoint Set來實作,這樣在合併上速度會快不少。
class GoBoard:
EMPTY = 0 # 空位的標誌
def __init__(self, board_size):
self.board_size = board_size + 2 # 加上一圈無效區域
self.board = [-1] * (self.board_size * self.board_size) # 用-1表示無效區域
# 每個位置的父節點,初始化為自己
self.parent = list(range(self.board_size * self.board_size))
self.rank = {}
self.string_stones = {} # 每個棋串的棋子數
self.string_liberty_set = {} # 每個棋串的氣集合
self.string_identity = {} # 每個位置對應的棋串ID
self.next_position = {} # 每個位置的下一個節點
self.root_vertex = {} # 每個棋串的根節點位置
for x in range(1, board_size + 1):
for y in range(1, board_size + 1):
self.board[self.index(x, y)] = GoBoard.EMPTY
def index(self, x, y):
return x * self.board_size + y
def directions(self, pos):
return [
pos - self.board_size, # 上
pos + self.board_size, # 下
pos - 1, # 左
pos + 1 # 右
]
def find(self, pos):
if self.parent[pos] != pos:
self.parent[pos] = self.find(self.parent[pos])
return self.parent[pos]
def union(self, pos1, pos2):
root1 = self.find(pos1)
root2 = self.find(pos2)
if root1 != root2:
if self.rank[root1] > self.rank[root2]:
self.parent[root2] = root1
self.string_stones[root1] += self.string_stones[root2]
self.string_liberty_set[root1].update(
self.string_liberty_set[root2])
elif self.rank[root1] < self.rank[root2]:
self.parent[root1] = root2
self.string_stones[root2] += self.string_stones[root1]
self.string_liberty_set[root2].update(
self.string_liberty_set[root1])
else:
self.parent[root2] = root1
self.string_stones[root1] += self.string_stones[root2]
self.string_liberty_set[root1].update(
self.string_liberty_set[root2])
self.rank[root1] += 1
def count_liberty(self, vertex):
# 獲取該vertex所屬的棋串的起點
start_pos = self.string_identity[vertex]
next_pos = start_pos
liberty_set = set()
while True:
# 找附近的氣加入liberty set
for direction in self.directions(next_pos):
if self.board[direction] == GoBoard.EMPTY:
liberty_set.add(direction)
# 移動到下一個節點
next_pos = self.next_position[next_pos]
# 回到了起始位置則停止
if next_pos == start_pos:
break
# 更新棋串的氣集合
self.string_liberty_set[start_pos] = liberty_set
return len(liberty_set)
def merge_string(self, pos1, pos2):
self.union(pos1, pos2)
除了演算法之外,資料結構也會大幅影響程式的效率,光是Mailbox簡單加上個無效區域就能幫程式提速了,這邊分享了以圖論來實作圍棋的資料結構,比起前面用Array的方式,處理棋串與數氣等圍棋規則效率會高上不少,大家可以根據不同的遊戲設計不同的資料結構,Bitboard的實作就留到後面再詳細介紹。