Try   HackMD

圍棋征子邏輯

tags: coding

Marsgoat Dec 19, 2021

來分享點有趣的題目，征子對下圍棋的人來說是個非常基礎的吃子技巧，那要將征子給實作出來呢？其實征子意外的有很多小細節，包含提子等特別的判斷，非常的有趣，感覺可以當一題Leetcode的題目來玩了，難度大概是medium吧。

征子

征子是圍棋的一種吃子技巧，如下圖此時黑棋只要下在A位，無論白棋如何掙扎都是無法逃脫的。


征子會讓對方棋子始終保持在1~2氣的狀態，從1氣被叫吃，跑一手後仍只有2氣，只要進攻方注意到緊氣的位置，就能以這種方式把對方給吃掉。

實作過程

以下的code有做一點小修正，主要是可讀性問題，可以看一下程式碼可讀性這篇，原本寫不好的地方我就保留當個紀念，其中還有一個小錯誤，有興趣的人可以找找看
Marsgoat Feb 6, 2022

資料結構

最簡單的就是使用二維陣列來表示盤面狀態，這邊以9路棋盤為例：黑棋為X、白棋為O、空為.
例：

const boardArray = [
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", "X", ".", "."],
  [".", ".", ".", ".", ".", "X", "O", "X", "."],
  [".", ".", ".", ".", ".", ".", "O", "X", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
  [".", ".", ".", ".", ".", ".", ".", ".", "."],
];

判斷同塊棋與氣

首先要先判斷哪些棋子是連接在一起的，只要是相連的棋就視為同一塊，還要紀錄氣的位置，簡單說就是同一塊棋旁邊的空位就是這塊棋的氣。
想法上就是用遞迴去解，從目標棋子開始，往上下左右四個方向找，如果也是自己的棋，就把這顆子加入棋塊，然後再對這顆子的上下左右去找，為了避免回頭重複找，所以要記錄找過的地方。

getStones

boardArray盤面
target為目標棋子座標，格式為{x,y}
visit為紀錄拜訪過的點的二維陣列
isInBounds用來檢查是否超出邊界，這樣寫很硬要，我只是想要練習js的箭頭函式，但顯然很拙劣
directions定義上下左右四個方向























function getStones(boardArray, target, visit) {
  const stones = [target];
  const color = boardArray[target.y][target.x];
  visit[target.y][target.x] = 1;
  const isInBounds = (point, length) =>
    point.x < length && point.x >= 0 && point.y < length && point.y >= 0;
  const directions = [
    { x: target.x, y: target.y + 1 },
    { x: target.x, y: target.y - 1 },
    { x: target.x + 1, y: target.y },
    { x: target.x - 1, y: target.y },
  ];
  for (const dir of directions) {
    if (!isInBounds(dir, boardArray.length)) {
      continue;
    }
    if (boardArray[target.y][target.x] === color && visit[dir.y][dir.x] === 0) {
      stones = stones.concat(getStones(boardArray, dir, visit));
    }
  }
  return stones;
}

getLiberties

氣的部分，因為已經有了整塊棋了，所以就直接for迴圈去找每顆棋的四周，看有沒有空點。
getLiberties用來取得氣的位置的function
liberties氣的英文好像都是翻成liberty，我也不知道為什麼，以前我都直接取叫air































function getLiberties(boardArray, stones) {
  const liberties = [];
  const isInBounds = (point, length) =>
    point.x < length && point.x >= 0 && point.y < length && point.y >= 0;
  const visit = [];
  for (let i = 0; i < boardArray.length; i++) {
    visit[i] = [];
    for (let j = 0; j < boardArray[i].length; j++) {
      visit[i][j] = 0;
    }
  }
  for (const stone of stones) {
    const directions = [
      { x: stone.x, y: stone.y + 1 },
      { x: stone.x, y: stone.y - 1 },
      { x: stone.x + 1, y: stone.y },
      { x: stone.x - 1, y: stone.y },
    ];
    for (const dir of directions) {
      if (!isInBounds(dir, boardArray.length)) {
        continue;
      }
      if (boardArray[dir.y][dir.x] === "." && visit[dir.y][dir.x] === 0) {
        liberties.push(dir);
        visit[dir.y][dir.x] = 1;
      }
    }
  }
  return liberties;
}

其實數氣這個是研究所時我指導教授開的課的其中一次作業的一個小題，好像就是要把棋子換成氣吧，我之前是用 C++ 寫的，半年前因為工作需要又用python寫了一遍，不過這篇是我要練習js所以才用js重寫了一遍。
當時(半年前用python)我寫到這正準備測試有沒有問題的時候，突然就發現，欸？！等等，這兩件事不是可以同時做的嗎?我寫成兩個function然後讓它找兩遍是在？？？
這邊照慣例分享一下我耍笨的過程，只是我用js還原一下當時的心路歷程，我真是佩服我自己…大腦是個好東西，希望我也能有。

getStonesAndLiberties

參考了子期的非遞迴寫法改成了下面這個版本，這邊要感謝子期教我js，包含前面箭頭函式的用法，感恩子期讚嘆子期。
這邊用一個queue存放目前的棋子，然後就是檢查四個方向的連接棋塊與氣，如果有連接著的棋子就push進queue中等待檢查。







































function getStonesAndLiberties(boardArray, target) {
  const stones = [target];
  const liberties = [];
  const queue = [target];
  const color = boardArray[target.y][target.x];
  const isInBounds = (point, length) =>
    point.x < length && point.x >= 0 && point.y < length && point.y >= 0;
  const visit = [];
  for (let i = 0; i < boardArray.length; i++) {
    visit[i] = [];
    for (let j = 0; j < boardArray[i].length; j++) {
      visit[i][j] = 0;
    }
  }
  while (queue.length > 0) {
    const { x, y } = queue.pop();
    visit[y][x] = 1;
    const directions = [
      { x, y: y + 1 },
      { x, y: y - 1 },
      { x: x + 1, y },
      { x: x - 1, y },
    ];
    for (const dir of directions) {
      if (isInBounds(dir, boardArray.length) && visit[dir.y][dir.x] === 0) {
        if (boardArray[dir.y][dir.x] === color) {
          queue.push(dir);
          stones.push(dir);
        }
        if (boardArray[dir.y][dir.x] === ".") {
          liberties.push(dir);
          visit[dir.y][dir.x] = 1;
        }
      }
    }
  }
  return { liberties, stones };
}

判斷征子

接下來終於進入到征子最重要的部分了，一方要進攻一方要逃跑，其實又是個minimax的概念了，對這部分有興趣的可以去刷Leetcode中的StoneGame系列，還可以練習怎麼用DP(dynamic programming)優化，不過那個石頭是愈拿愈少，但圍棋是愈下愈多，在征子這邊沒辦法用一樣的方式優化就是了。
進攻方嘗試緊氣去吃掉對方，防守方要逃跑增加氣，所以要先標註出氣的位置，這就會利用到前面寫的getStonesAndLiberties了，進攻方把所有能緊氣的地方都試下看看，由於征子的特性，進攻方在進攻時讓目標棋子的氣大於2氣則為失敗，目標棋子只剩1氣時，因為輪到進攻方下，此時就可以直接將對方吃掉，就是征子成功，目標棋子為0氣那就更不用說了當然就是已經吃掉了。

target為目標棋子，如果是一塊棋那給其中一顆棋子的座標即可
color為先手方顏色，O或X
targetColor為目標棋子顏色
oppColor對方棋子顏色

如果先手方顏色與目標顏色不同，那先手方則為進攻方，顏色相同就當然是逃跑方了~































function isLadder(boardArray, target, color) {
  const targetColor = boardArray[target.y][target.x];
  const oppColor = color === "X" ? "O" : "X";
  const { stones, liberties } = getStonesAndLiberties(boardArray, target);
  // 進攻方
  if (color !== targetColor) {
    if (liberties.length > 2) return 0; // 目標大於2氣 失敗
    if (liberties.length <= 1) return 1; // 目標小於等於1氣 成功
    let score = -10;
    for (const move of liberties) {
      boardArray[move.y][move.x] = color;
      score = Math.max(isLadder(boardArray, target, oppColor), score);
      boardArray[move.y][move.x] = ".";
      if (score === 1) break;
    }
    return score;
  }
  // 防守方
  if (color === targetColor) {
    if (liberties.length >= 2) return 0;
    let score = 10;
    for (const move of liberties) {
      boardArray[move.y][move.x] = color;
      score = Math.min(isLadder(boardArray, target, oppColor), score);
      boardArray[move.y][move.x] = ".";
      if (score === 0) break;
    }
    return score;
  }
}

放上test給大家測試，如果能吃掉會回傳1，吃不掉會回傳0





















 describe("isLadder", () => {
    describe("測試盤面：征子", () => {
      it("應回傳1", () => {
        const boardArray = [
          [".", ".", ".", ".", ".", ".", ".", "X", "."],
          [".", ".", ".", ".", ".", ".", "X", "O", "X"],
          [".", ".", ".", ".", ".", ".", ".", "O", "X"],
          [".", ".", ".", ".", ".", ".", ".", ".", "."],
          [".", ".", ".", ".", ".", ".", ".", ".", "."],
          [".", ".", ".", ".", ".", ".", ".", ".", "."],
          [".", ".", ".", ".", ".", ".", ".", ".", "."],
          [".", ".", ".", ".", ".", ".", ".", ".", "."],
          [".", ".", ".", ".", ".", ".", ".", ".", "."],
        ];
        const result = isLadder(boardArray, { x: 7, y: 2 }, "X");
        const expected = 1;
        assert.strictEqual(result, expected);
      });
    });
  });

特殊情況

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


此時白並不需要繼續逃跑，而是可以在A位吃掉黑棋，也能將自己的氣變多，所以其實在防守方的走步要增加一個提子的選項，這時候stones就能發揮作用了，不然其實上面根本沒用到這個，要判斷自身周遭包圍自己的對方棋子有沒有只剩下1氣的，就可以將其吃掉。
這時又會在衍生出一個問題，如果有棋子被對方吃掉還能夠繼續征子嗎？
以上面的情況當然是不能，但如果是下圖的情況…

就算白於A位提子…

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

阿不過這篇我就不展開特殊情況的處理了，有興趣的人可以自己研究研究，或是等待遙遙無期的下一篇XDD

心得

最一開始就連最頂級的圍棋AI如LeelaZero與絕藝等，都會有征子的bug(犯跑征子的低級失誤)，在KataGo出現後，將一些圍棋技巧的特徵加入訓練，詳細可見KataGo論文中的 4.2 Game-specific Features，才將此狀況改善，詳細code在nninnputs.cpp中iterLadders，有興趣可以研究一下，可見其實征子也是很有學問的吧?!
而且我看了一下好像連katago都沒有處理比較特別的征子情況，不過可能也是因為並不需要的關係吧。

筆記新登場人物：子期大大！
全端工程師、公司的技術主管？！(其實我不知道詳細職稱XD)，我會進公司也是透過子期，不知道他現在發現我code寫成這樣有沒有很後悔推薦我。
認識子期快要8年了，想當初一起住在維哥家然後一起去比賽圍棋，真是令人懷念，恭喜子期與胡老大也在最近結婚了~
我的筆記系列現在有個新目標，就是要把我身旁的大佬們一一吹捧介紹過一輪。

回小羊筆記首頁

Last changed by 
 
Marsgoat
0
419
Published on HackMD