Day13 圍棋征子邏輯
===
今天要來實作一個很有趣的題目，就是圍棋的征子，這邊會用上很多前幾天所分享到的演算法，剛好當作複習。
這邊一樣不浪費篇幅寫規則，這邊附上維基百科的傳送門：[圍棋基礎規則](https://zh.wikipedia.org/zh-tw/%E5%9B%B4%E6%A3%8B#%E8%A7%84%E5%88%99)。
這邊還有[圍棋進階規則](https://zh.wikipedia.org/zh-tw/%E5%9C%8D%E6%A3%8B%E8%A6%8F%E5%89%87%E6%AF%94%E8%BC%83)，說真的很多進階規則我自己也搞不太懂，像是假生，我也是在當圍棋替代役的時候聽棋協的秦秘書長說的。
想學圍棋的話可以報名[黑嘉嘉圍棋教室基礎課](https://www.heijiajia.com.tw/origin/#/shop/products/30k-10k-v2)，裡面很多AI功能都是我與正在UCLA讀博士的Steven大大做的，所以自行業配一波XDD。
## 征子
[征子](https://zh.wikipedia.org/wiki/%E5%BE%81%E5%AD%90)是圍棋的一種吃子技巧，如下圖此時黑棋只要下在A位，無論白棋如何掙扎都是無法逃脫的。
征子會讓對方棋子始終保持在1~2氣的狀態，從1氣被叫吃，跑一手後仍只有2氣，只要進攻方注意到緊氣的位置，就能以這種方式把對方給吃掉。
征子對下圍棋的人來說是個非常基礎的吃子技巧，但將征子給實作出來就沒那麼容易了，有很多小細節藏在裡面。
大家可以先停在這裡思考一下，回想一下前幾天所分享到的各種演算法，試著動手寫寫看再回來繼續往下看。
## 實作
### 資料結構
最簡單的就是使用二維陣列來表示盤面狀態，這邊以9路棋盤為例：黑棋為`X`、白棋為`O`、空為`.`
例：
```python=
board = [
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "X", ".", "."],
[".", ".", ".", ".", ".", "X", "O", "X", "."],
[".", ".", ".", ".", ".", ".", "O", "X", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."]
]
```
開始實作征子前要先根據圍棋的規則完成一些小功能。
### 判斷同塊棋與氣
首先要先判斷哪些棋子是連接在一起的，只要是相連的棋就視為同一塊，還要紀錄[氣](https://zh.wikipedia.org/wiki/%E6%B0%A3_(%E5%9C%8D%E6%A3%8B))的位置，簡單說就是同一塊棋旁邊的空位就是這塊棋的氣。
想法上就是用遞迴去解，從目標棋子開始，往上下左右四個方向找，如果也是自己的棋，就把這顆子加入棋塊，然後再對這顆子的上下左右去找，為了避免回頭重複找，所以要記錄找過的地方。
```python=
# 定義棋盤大小
BOARD_SIZE = 9
# 定義方向 (上下左右)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def is_in_bounds(x, y): # 檢查座標是否在棋盤內
return 0 <= x < BOARD_SIZE and 0 <= y < BOARD_SIZE
```
`board` 表示棋盤的二維陣列。
`visited` 用來存已經訪問過的點。
`stones` 儲存棋串。
`liberties` 氣的英文好像都是翻成liberty，我也不知道為什麼，這邊用set來存是因為有可能同一個氣被重複計算到，直接用set比較方便。
例如下圖，A點會被上跟左兩顆黑棋重複計算到。
```python=
def get_stones_and_liberties(board, x, y):
if board[x][y] == '.':
return [], []
visited = set() # 已訪問過的點
stones = [] # 儲存棋串中所有的棋子位置
liberties = set() # 記錄該棋串的氣
color = board[x][y] # 棋子的顏色
# 深度優先搜尋 (DFS)
def dfs(x, y):
# 避免重複訪問
if (x, y) in visited:
return
visited.add((x, y)) # 標記已訪問過
stones.append((x, y)) # 將該點加入棋串
# 檢查四個方向
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)
# 從輸入的位置開始搜尋
dfs(x, y)
return stones, liberties
```
這邊應該還蠻簡單的，很像修資料結構演算法時，老師會出的小作業。
### 判斷征子
接下來要進入到征子最重要的部分了，我們要判斷黑棋能不能吃掉白棋，如果我們單純的使用Minimax + Alpha-Beta Pruning的話，應該是非常難在有限的時間內跑出解來，畢竟光是9x9的棋盤也已經過於複雜。
但是這邊因為是要判斷征子，我們就要利用征子的特性，讓對方的棋子始終保持在1~2氣之間的狀態，所以我們就可以通過類似Threat Space Search的概念，將搜索範圍限縮在「緊氣」的點上，而白棋被「叫吃」就只能逃跑，會大幅減少搜索難度。
進攻方嘗試緊氣去吃掉對方，防守方要逃跑增加氣，所以要先標註出氣的位置，這就會利用到前面寫的`get_stones_and_liberties`了，進攻方把所有能緊氣的地方都試下看看，由於征子的特性，進攻方在進攻時讓目標棋子的氣大於2氣則為失敗，目標棋子只剩1氣時，因為輪到進攻方下，此時就可以直接將對方吃掉，就是征子成功，目標棋子為0氣那就更不用說了當然就是已經吃掉了。
`target` 為目標棋子，如果是一塊棋那給其中一顆棋子的座標即可。
`color` 為先手方顏色，O或X
`target_color` 為目標棋子顏色
`opponent_color` 對方棋子顏色
`score` 一開始min層設為10，max層設為-10，因為回傳只有1跟0(成功/失敗)所以不用真的設成無限大，設成2跟-2也可以。
如果先手方顏色與目標顏色不同，那先手方則為進攻方，顏色相同就當然是防守方了~
```python=
def is_ladder(board, target, color):
if (board[target[0]][target[1]] == '.'):
return 0
target_color = board[target[0]][target[1]] # 目標棋子顏色
opponent_color = 'X' if color == 'O' else 'O' # 對方顏色
stones, liberties = get_stones_and_liberties(board, target[0], target[1])
# 進攻方 (max層)
if color != target_color:
if len(liberties) > 2:
return 0 # 目標大於2氣 失敗
if len(liberties) <= 1:
return 1 # 目標氣少於等於1 成功
score = -10
for x, y in liberties:
board[x][y] = color
score = max(is_ladder(board, target, opponent_color), score)
board[x][y] = '.'
if score == 1: # 找到一條獲勝路徑提前剪枝
break
# 防守方 (min層)
if color == target_color:
if len(liberties) >= 2:
return 0 # 防守方有2個或以上的氣，逃脫成功
score = 10
for x, y in liberties:
board[x][y] = color
score = min(is_ladder(board, target, opponent_color), score)
board[x][y] = '.'
if score == 0: # 找到一條逃跑路徑提前剪枝
break
return score
```
如果能吃掉會回傳1，吃不掉會回傳0，最後附上一個印出棋盤的功能方便大家印出棋盤測試。
```python=
def print_board(board):
index_A = 'abcdefghijklmnopqrs'
size = len(board)
index_A = index_A[0:size]
for c in ' '+index_A:
print(c, end=' ')
print()
for i, line in enumerate(board):
print(index_A[i], end=' ')
for value in line:
print(value, end=' ')
print()
print()
```
以下是測試範例，board1應該要回傳1，board2應該要回傳0。
```
board1 = [
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "X", ".", "."],
[".", ".", ".", ".", ".", "X", "O", "X", "."],
[".", ".", ".", ".", ".", ".", "O", "X", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."]
]
board2 = [
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "X", ".", "."],
[".", ".", ".", ".", ".", "X", "O", "X", "."],
[".", ".", ".", ".", ".", ".", "O", "X", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", "O", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."]
]
```
## 總結
在實作圍棋征子邏輯的過程，我們用到了Minimax Algorithm、Alpha-Beta Pruning，利用氣來縮小搜索空間，類似於Threat Space Search的概念，希望大家在複習前面所學時，也能同時感受到圍棋的趣味。
## 特殊情況思考
這個範例其實是征子失敗的，但如果是按照上面的程式會回傳1。
這邊就留給大家思考是為什麼了，這幾天太肝了，只好拆成兩篇，明天再來解答。
```
board = [
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "X", ".", "."],
[".", ".", ".", ".", ".", "X", "O", "X", "."],
[".", ".", ".", ".", ".", ".", "O", "X", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "O", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", "."]
]
```
Sign in with Wallet
Connect another wallet