Day21 Board Representation
===
今天要來介紹容易被大家忽略的資料結構，棋盤資料結構的設計其實也很有多要注意的，有好的演算法也要搭配好的資料結構才能讓你的AI完美發揮阿！

## Array
最常見的莫過於Array了，比如我們前面用二維陣列來表示棋盤。

board = [
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", "X", ".", "."],
    [".", ".", ".", ".", ".", "X", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", "O", "X", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."],
    [".", ".", ".", ".", ".", ".", ".", ".", "."]
]

不止是棋類遊戲，像是撲克牌類也很輕鬆可以用4x13的二維陣列表達，當然也可以轉成一維陣列的方式，如下圖。


將二維陣列給拉平，0~51分別代表了52張撲克牌。

## Mailbox
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
Bitboard 是一種利用位元運算來表示和操作棋盤狀態的資料結構，用0和1來表示該棋子是否在棋盤上，這種資料結構可以使用各種位元運算來快速更新棋盤狀態。

例如西洋棋的棋盤就可以用一個**64位元的無號整數**來表達：

圖片擷取自[維基百科](https://zh.wikipedia.org/zh-tw/%E5%9C%8B%E9%9A%9B%E8%B1%A1%E6%A3%8B)

a7~h7這排小兵在棋盤上就可以表示為：

00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000

為了方便觀看我們通常會轉成16進位表示：`0x000000000000FF00`
或是直接表示成`0xFF00`


### 基本操作

* **檢查棋子存在**
只要將棋盤與想檢查的位置做AND運算就能知道該位置有無棋子，1代表有棋子、0代表沒有。

position = 1 << n  // 檢查第n個位置，將1左移n個bit
bitboard & position

* **放置棋子**
將棋子放上去可以做OR運算，也可以用XOR，只是要先檢查本來上面是否有棋子，如果已經有棋子的話做XOR會變成把棋子給移除。

position = 1 << n
bitboard |= position

bitboard ^= position

* **移除棋子**
移除棋子則可以先對該位置取NOT接著再做AND，當然也可以用XOR。

position = 1 << n
bitboard & ~position

bitboard ^= position

Bitboard的效能比起使用Array實在是快得太多，不只效能好，有時候還能做狀態壓縮，這邊先介紹基礎操作，後面會再慢慢介紹到更多功能，通常會用到Bitboard也代表我們很在意效能，就不會用python來實作了。

## 圍棋資料結構設計
這邊分享一個圍棋的資料結構設計。
### 棋串（string）
棋串可以被視為棋盤中的一個子圖（sub-graph），每個棋串都是由棋子組成的節點循環圖。以下是這個結構的詳細說明：
* **board position**：當前的棋盤狀態。
* **vertex position**：每個棋子的座標，表示在一維陣列中的索引位置。
* **string identity**：表示棋串的 ID（identity），這個 ID 指向棋串的根節點（root vertex），這樣的設計使得所有屬於該棋串的節點都可以通過這個根節點來進行識別和操作。
* **next position**：這表示每個節點在棋串中的下一個節點位置。
這些節點之間形成了一個循環結構。例如，對於 ID 為 16 的棋串，其 next position 的鏈接可以表達為 17->18->16，這是一個無限循環的鏈接關係，這樣的設計使得我們能夠通過任意一個節點遍歷整個棋串。

這種設計不僅能夠方便管理和操作棋串，還能有效地追蹤每個棋串的氣數和棋子數等資訊，而不必每次進行重新計算。

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的實作就留到後面再詳細介紹。

## Reference
* [Bitboards](https://www.chessprogramming.org/Bitboards)
* [暗棋殘局庫的壓縮與實做](https://etds.lib.ntnu.edu.tw/thesis/detail/57e6238b5c6b71b6b7de753a3bc0c183/)
* [dlgo棋盤資料結構](https://github.com/CGLemon/pyDLGO/blob/master/docs/Methods.md)