Day14 圍棋征子邏輯2
===
今天來補完昨天的征子邏輯特殊情況，其實對有在下棋的人來說可能也沒有那麼特殊，想看特別的歡迎看看[珍瓏題-明皇遊月宮勢](https://youtu.be/j8oSjZhyfUw?si=9vebunaGACN3e7Oz)，從5分43秒左右開始是一個全棋盤的征子，特別有趣，講解者是我的好朋友，他的影片幹話很多，喜歡聽幹話的，歡迎訂閱邊學圍棋邊聽幹話XDD。

## 特殊情況

其實昨天看似沒問題的征子，還有一個小問題，當征子的路徑上有對方的棋子時，如下圖：



此時白並**不需要繼續逃跑，而是可以在 A 位吃掉黑棋**，也能將自己的氣變多，所以其實在防守方的走步要增加一個吃子的選項，這時候`stones`就能發揮作用了，不然昨天根本沒用到這個參數(不知道有沒有人有發現，感覺大家應該是都沒在看code的XDD)，要**判斷自身周遭包圍自己的對方棋子有沒有只剩下1氣的，就可以將其吃掉**。
所以我們要將白棋的搜索範圍加大，不只是延長自己的氣，還要判斷自身周邊的所有黑棋，有沒有1氣的黑棋可以吃掉，畢竟吃棋也是延長氣的一種方式。
(有點像是在Threat Space Search中說到的，五子棋的活三迫著，對方的回應可以是去下死四，要記得把這些對方的反迫著加入搜索。)

## 實作
### 優化
昨天的`score` 就直接不用了，直接回傳True or False就好了，這樣會更乾淨一點，這邊新增了一個`get_new_board`用來更新棋盤狀態，不要改動原始棋盤，因為我們之後還要做一些額外的處理。

def is_ladder2(board, target, color):
    if (board[target[0]][target[1]] == '.'):
        return False

    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])
    print_board(board)
    # 進攻方 (max層)
    if color != target_color:
        if len(liberties) > 2:
            return False  # 目標大於2氣 失敗
        if len(liberties) <= 1:
            return True  # 目標氣少於等於1 成功
        for liberty in liberties:
            new_board = get_new_board(board, liberty, color)
            if is_ladder2(new_board, target, opponent_color):
                return True

    # 防守方 (min層)
    if color == target_color:
        if len(liberties) >= 2:
            return False  # 防守方有2個或以上的氣，逃脫成功
        
        # TODO 找出1氣的對方棋子
        
        for liberty in liberties:
            new_board = get_new_board(board, liberty, color)
            if is_ladder2(new_board, target, opponent_color):
                return False
        return True

    return False

def get_new_board(board, move, color):
    new_board = [row.copy() for row in board]
    new_board[move[0]][move[1]] = color
    return new_board

### 找出1氣的對方棋子
要找出吃子就要檢查對方的氣，要找出所有與我方棋子相鄰的敵方棋子的氣，看有沒有剩下1氣的棋子(先不考慮打劫的問題)。

for stone in stones:
    for dx, dy in DIRECTIONS:
        nx, ny = stone[0] + dx, stone[1] + dy
        if is_in_bounds(nx, ny) and board[nx][ny] == opponent_color:
            # 找到氣數為1的敵方棋子
            _, opp_liberties = get_stones_and_liberties(board, nx, ny)
            if len(opp_liberties) == 1:
                # 如果發現有敵方棋子只有1個氣，直接返回 False
                return False

這時又會再衍生出一個問題，如果有棋子被對方吃掉還能夠繼續征子嗎？
以上面的情況當然是不能，但如果是下圖的情況...


就算白於 A 位提子...


黑棋仍然能將白棋給吃掉，但是此時要注意的是黑棋緊氣的方式，此時下圖 A 點是不能夠下的禁著點。


禁著點：
因為黑方下在A點立刻就沒有氣了，就會馬上被提起來，在大部分的規則中這樣是被禁止的。但是如果有發生吃子的行為則是允許的(不考慮打劫的情況)。

### 加入吃子走步
所以我們不能在提子後就終止搜索，必須將吃子的走步加入搜索之中。
新增一個 `move` 用來存放所有逃跑走步，包含吃子走步。

# 防守方 (min層)
if color == target_color:
    if len(liberties) >= 2:
        return False  # 防守方有2個或以上的氣，逃脫成功
        
    moves = set(liberties)
    # 找出與我方相鄰的敵方棋子，並且將1個氣的敵方棋子加入
    for stone in stones:
        for dx, dy in DIRECTIONS:
            nx, ny = stone[0] + dx, stone[1] + dy
            if is_in_bounds(nx, ny) and board[nx][ny] == opponent_color:
                # 找到氣數為1的敵方棋子
                _, opp_liberties = get_stones_and_liberties(board, nx, ny)
                if len(opp_liberties) == 1:
                    moves.add(list(opp_liberties)[0])

    for move in moves:
        new_board = get_new_board(board, move, color)
        if not is_ladder2(new_board, target, opponent_color):
            return False
    return True

自此我們就成功將吃子走步也給加入搜索了，但是用昨天最後給的範例跑出來，結果還是True，顯示征子成功，這是為什麼呢?
利用昨天提供的 `print_board` 將盤面給印出來會發現以下情況。


這邊會發現死子沒有處理到，黑子被吃掉了但還是在棋盤上，導致算氣錯誤。

### 死子處理
這時前面新增的`get_new_board`這時就可以派上用場了，我們要判斷新增的走步，是否讓棋盤上有棋子沒「氣」了。
這邊還要注意到禁著點，進攻方在緊氣的時候是不能下在沒有氣且沒有吃子的地方(不考慮打劫的情況)。

def get_new_board(board, move, color):
    new_board = [row.copy() for row in board]
    new_board[move[0]][move[1]] = color
    opponent_color = 'X' if color == 'O' else 'O'
    captured = False  # 用來檢查是否有吃子

    def remove_if_no_liberties(x, y):
        nonlocal captured
        stones, liberties = get_stones_and_liberties(new_board, x, y)
        if len(liberties) == 0:
            for stone in stones:  # 將所有無氣的棋子移除
                new_board[stone[0]][stone[1]] = '.'
            captured = True  # 紀錄有吃子

    # 檢查周圍四個方向，移除沒有氣的敵方棋子
    for dx, dy in DIRECTIONS:
        nx, ny = move[0] + dx, move[1] + dy
        if is_in_bounds(nx, ny) and new_board[nx][ny] == opponent_color:
            remove_if_no_liberties(nx, ny)

    # 不考慮打劫的情況，只要有吃子就不算自殺。
    stones, liberties = get_stones_and_liberties(new_board, move[0], move[1])
    if len(liberties) == 0 and not captured:  # 如果自己沒有氣且沒有吃子，則視為自殺
        for stone in stones:
            new_board[stone[0]][stone[1]] = '.'

    return new_board

這樣修改完畢後，昨天最後的範例就可以被正確的判斷出來了，打劫的情況也加進去的話會過於複雜，都可以再寫一篇了，這樣我的主題大概會變成實作圍棋規則探討，所以還是到此為止吧。

## 結論
最一開始就連最頂級的圍棋AI如LeelaZero與絕藝等，都會有征子的bug(犯跑征子的低級失誤)，征子對人類來說是相當簡單的直線計算，但其實它的深度是非常深的，如下圖，黑棋 A 要跑到底被白棋提光都已經快50手的事情了，就很容易產生Horizon Effect，如果程式沒有做特別的判斷應該都很難算這麼深。


在KataGo出現後，將一些圍棋技巧的特徵加入訓練，詳細可見[KataGo論文](https://arxiv.org/pdf/1902.10565.pdf)中的 4.2 Game-specific Features，才將此狀況改善，詳細code在[nninnputs.cpp](https://github.com/lightvector/KataGo/blob/master/cpp/neuralnet/nninputs.cpp)中`iterLadders`，還有[board.cpp](https://github.com/lightvector/KataGo/blob/master/cpp/game/board.cpp)中的`searchIsLadderCaptured`，有興趣可以研究一下，可見其實征子也是很有學問的吧?!
而且我看了一下好像連Katago都沒有處理比較特別的征子情況，不過可能也是因為並不需要的關係吧。