State
├─ 4 個盤面 bitboard
├─ 2 個 claims bitmask
├─ turn
├─ emptyCount
└─ 增量 evaluation

Node
├─ move
├─ visits
├─ value
├─ prior
├─ children
├─ unexpanded index
└─ solved status

<script id="mcts-worker-source" type="javascript/worker">
  'use strict';

  /*
   * ============================================================
   * 基本常數
   * ============================================================
   */

  const BOARD_SIZE = 49;
  const MAX_MOVES = 588;
  const MAX_DEPTH = 49;

  /*
   * 剩餘空格不超過此值時，嘗試使用精確 W/D/L 求解器。
   *
   * 如果較慢的手機出現明顯超時，可以改成 6。
   * 如果桌面瀏覽器效能很好，可以測試 8。
   */
  const EXACT_EMPTY_THRESHOLD = 7;
  const EXACT_ABORT = 2;
  const EXACT_TT_MAX_SIZE = 300000;

  const LINES = [
    [0, 1, 4],
    [0, 2, 6],
    [4, 5, 6],
    [0, 3, 5],
    [1, 3, 6],
    [2, 3, 4],
    [1, 2, 5]
  ];

  const LINE_MASKS = LINES.map(line => (1 << line[0]) | (1 << line[1]) | (1 << line[2]));

  /*
   * 每個棋位可以移至：
   * 1. 同一島的另外六個位置；
   * 2. 其他六個島上的相同位置。
   *
   * 因此每格恰好有 12 個幾何候選目的地。
   */
  const DESTINATIONS = Array.from({ length: BOARD_SIZE }, (_, from) => {
    const result = [];
    const island = (from / 7) | 0;
    const point = from % 7;
    const base = island * 7;

    for (let p = 0; p < 7; p++) {
      if (p !== point) result.push(base + p);
    }

    for (let i = 0; i < 7; i++) {
      if (i !== island) result.push(i * 7 + point);
    }

    return Uint8Array.from(result);
  });

  /*
   * ============================================================
   * 小型查表
   * ============================================================
   *
   * 一個島只有七個位置。
   *
   * key 的低七位表示火方棋子；
   * key 的高七位表示冰方棋子。
   *
   * key = fireMask | (iceMask << 7)
   */

  const POPCOUNT = new Uint8Array(128);
  const HAS_LINE = new Uint8Array(128);

  const TABLE_SIZE = 1 << 14;
  const ISLAND_OWNER = new Int8Array(TABLE_SIZE);
  const LOCAL_EVAL = new Float32Array(TABLE_SIZE);
  const META_EVAL = new Float32Array(TABLE_SIZE);

  for (let mask = 0; mask < 128; mask++) {
    let count = 0;
    let value = mask;

    while (value) {
      value &= value - 1;
      count++;
    }

    POPCOUNT[mask] = count;

    for (const lineMask of LINE_MASKS) {
      if ((mask & lineMask) === lineMask) {
        HAS_LINE[mask] = 1;
        break;
      }
    }
  }

  /*
   * 島內評估：
   * - 一子活線：0.8
   * - 二子活線：6
   * - 三子線：20
   *
   * 這個分數是固定的火方視角：
   * 正值對火有利，負值對冰有利。
   */
  const LOCAL_LINE_SCORE = [0, 0.8, 6, 20];

  /*
   * Meta 評估比局部島嶼評估權重大。
   */
  const META_LINE_SCORE = [0, 5, 35, 1000];

  for (let fireMask = 0; fireMask < 128; fireMask++) {
    for (let iceMask = 0; iceMask < 128; iceMask++) {
      if (fireMask & iceMask) continue;

      const key = fireMask | (iceMask << 7);
      const fireHasLine = HAS_LINE[fireMask] !== 0;
      const iceHasLine = HAS_LINE[iceMask] !== 0;

      if (fireHasLine && !iceHasLine) {
        ISLAND_OWNER[key] = 1;
      } else if (iceHasLine && !fireHasLine) {
        ISLAND_OWNER[key] = -1;
      } else {
        ISLAND_OWNER[key] = 0;
      }

      let localScore = 0;
      let metaScore = (POPCOUNT[fireMask] - POPCOUNT[iceMask]) * 45;

      for (const lineMask of LINE_MASKS) {
        const fireCount = POPCOUNT[fireMask & lineMask];
        const iceCount = POPCOUNT[iceMask & lineMask];

        if (iceCount === 0) {
          localScore += LOCAL_LINE_SCORE[fireCount];
          metaScore += META_LINE_SCORE[fireCount];
        }

        if (fireCount === 0) {
          localScore -= LOCAL_LINE_SCORE[iceCount];
          metaScore -= META_LINE_SCORE[iceCount];
        }
      }

      LOCAL_EVAL[key] = localScore;
      META_EVAL[key] = metaScore;
    }
  }

  /*
   * ============================================================
   * 快速偽隨機數
   * ============================================================
   *
   * 使用 xorshift32，避免 Math.random() 成為 rollout 熱點，
   * 同時讓同一 seed 較容易重現。
   */

  let rngState = 0x9e3779b9;

  function seedRandom(token, state) {
    rngState =
      (Number(token) ^
        state.fireLo ^
        Math.imul(state.fireHi, 0x9e3779b1) ^
        Math.imul(state.iceLo, 0x85ebca6b) ^
        Math.imul(state.iceHi, 0xc2b2ae35) ^
        (state.turn === 1 ? 0x27d4eb2d : 0x165667b1)) >>>
      0;

    if (rngState === 0) rngState = 0x9e3779b9;
  }

  function random() {
    let x = rngState;

    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;

    rngState = x >>> 0;
    return rngState / 4294967296;
  }

  function randomIndex(length) {
    return (random() * length) | 0;
  }

  /*
   * ============================================================
   * Bitboard 狀態
   * ============================================================
   *
   * 索引 0～27：Lo，對應島 0～3。
   * 索引 28～48：Hi，對應島 4～6。
   *
   * 這樣每一個七格島都不會跨越兩個 32-bit word。
   */

  function addPiece(state, index, player) {
    if (index < 28) {
      const bit = 1 << index;

      if (player === 1) {
        state.fireLo = (state.fireLo | bit) >>> 0;
      } else {
        state.iceLo = (state.iceLo | bit) >>> 0;
      }
    } else {
      const bit = 1 << (index - 28);

      if (player === 1) {
        state.fireHi = (state.fireHi | bit) >>> 0;
      } else {
        state.iceHi = (state.iceHi | bit) >>> 0;
      }
    }
  }

  function removePiece(state, index, player) {
    if (index < 28) {
      const bit = 1 << index;

      if (player === 1) {
        state.fireLo = (state.fireLo & ~bit) >>> 0;
      } else {
        state.iceLo = (state.iceLo & ~bit) >>> 0;
      }
    } else {
      const bit = 1 << (index - 28);

      if (player === 1) {
        state.fireHi = (state.fireHi & ~bit) >>> 0;
      } else {
        state.iceHi = (state.iceHi & ~bit) >>> 0;
      }
    }
  }

  function isEmpty(state, index) {
    if (index < 28) {
      const bit = 1 << index;
      return (((state.fireLo | state.iceLo) & bit) >>> 0) === 0;
    }

    const bit = 1 << (index - 28);
    return (((state.fireHi | state.iceHi) & bit) >>> 0) === 0;
  }

  function islandKey(state, island) {
    let shift;
    let fireMask;
    let iceMask;

    if (island < 4) {
      shift = island * 7;
      fireMask = (state.fireLo >>> shift) & 127;
      iceMask = (state.iceLo >>> shift) & 127;
    } else {
      shift = (island - 4) * 7;
      fireMask = (state.fireHi >>> shift) & 127;
      iceMask = (state.iceHi >>> shift) & 127;
    }

    return fireMask | (iceMask << 7);
  }

  function islandEvaluation(state, island) {
    return LOCAL_EVAL[islandKey(state, island)];
  }

  function refreshIslandClaim(state, island) {
    const bit = 1 << island;
    const owner = ISLAND_OWNER[islandKey(state, island)];

    state.fireClaims &= ~bit;
    state.iceClaims &= ~bit;

    if (owner === 1) {
      state.fireClaims |= bit;
    } else if (owner === -1) {
      state.iceClaims |= bit;
    }
  }

  function recomputeDerivedState(state) {
    state.fireClaims = 0;
    state.iceClaims = 0;
    state.localEval = 0;

    for (let island = 0; island < 7; island++) {
      refreshIslandClaim(state, island);
      state.localEval += islandEvaluation(state, island);
    }

    state.metaEval = META_EVAL[state.fireClaims | (state.iceClaims << 7)];
  }

  function createCompactState(source) {
    const state = {
      fireLo: 0,
      fireHi: 0,
      iceLo: 0,
      iceHi: 0,
      fireClaims: 0,
      iceClaims: 0,
      turn: Number(source.turn) === -1 ? -1 : 1,
      winner: Number(source.winner) || 0,
      ply: Number(source.ply) || 0,
      emptyCount: 49,
      localEval: 0,
      metaEval: 0
    };

    let occupied = 0;

    for (let index = 0; index < BOARD_SIZE; index++) {
      const player = Number(source.board[index]) || 0;

      if (player === 1 || player === -1) {
        addPiece(state, index, player);
        occupied++;
      }
    }

    state.emptyCount = BOARD_SIZE - occupied;
    recomputeDerivedState(state);

    return state;
  }

  /*
   * key 用於：
   * 1. worker 內的 tree reuse；
   * 2. 尾局 transposition table。
   *
   * claims 可以由棋盤唯一推導，因此不必放入 key。
   */
  function stateKey(state) {
    return (
      state.fireLo.toString(36) +
      '.' +
      state.fireHi.toString(36) +
      '.' +
      state.iceLo.toString(36) +
      '.' +
      state.iceHi.toString(36) +
      '.' +
      (state.turn === 1 ? 'f' : 'i')
    );
  }

  function positionEvaluation(state) {
    return state.localEval + state.metaEval;
  }

  /*
   * ============================================================
   * Packed move
   * ============================================================
   *
   * from、to 都只需要六個 bits：
   *
   * move = (from << 6) | to
   */

  function encodeMove(from, to) {
    return (from << 6) | to;
  }

  function moveFrom(move) {
    return move >>> 6;
  }

  function moveTo(move) {
    return move & 63;
  }

  function exportMove(move) {
    return {
      from: moveFrom(move),
      to: moveTo(move)
    };
  }

  /*
   * ============================================================
   * Make / unmake
   * ============================================================
   *
   * makeMove() 回傳父狀態的 localEval。
   * unmakeMove() 使用它精確恢復，避免大量 make/unmake 後產生浮點漂移。
   */

  function makeMove(state, move) {
    const from = moveFrom(move);
    const to = moveTo(move);
    const player = state.turn;

    const originIsland = (from / 7) | 0;
    const destinationIsland = (to / 7) | 0;

    const oldLocalEval = state.localEval;

    let beforeLocal = islandEvaluation(state, originIsland);

    if (destinationIsland !== originIsland) {
      beforeLocal += islandEvaluation(state, destinationIsland);
    }

    /*
     * 目的格：放入移動方棋子。
     * 起點：原棋子消失，生成對方棋子。
     */
    removePiece(state, from, player);
    addPiece(state, from, -player);
    addPiece(state, to, player);

    let afterLocal = islandEvaluation(state, originIsland);

    if (destinationIsland !== originIsland) {
      afterLocal += islandEvaluation(state, destinationIsland);
    }

    state.localEval += afterLocal - beforeLocal;

    refreshIslandClaim(state, originIsland);

    if (destinationIsland !== originIsland) {
      refreshIslandClaim(state, destinationIsland);
    }

    state.metaEval = META_EVAL[state.fireClaims | (state.iceClaims << 7)];

    state.emptyCount--;
    state.ply++;
    state.turn = -player;

    /*
     * 保持原程式的勝負優先順序：
     * 先檢查行動方，再檢查對方。
     */
    const playerClaims = player === 1 ? state.fireClaims : state.iceClaims;
    const opponentClaims = player === 1 ? state.iceClaims : state.fireClaims;

    if (HAS_LINE[playerClaims]) {
      state.winner = player;
    } else if (HAS_LINE[opponentClaims]) {
      state.winner = -player;
    } else {
      state.winner = 0;
    }

    return oldLocalEval;
  }

  function unmakeMove(state, move, oldLocalEval) {
    const from = moveFrom(move);
    const to = moveTo(move);

    /*
     * makeMove 後 turn 已經切換，
     * 因此前一個行動者是 -state.turn。
     */
    const player = -state.turn;

    const originIsland = (from / 7) | 0;
    const destinationIsland = (to / 7) | 0;

    removePiece(state, to, player);
    removePiece(state, from, -player);
    addPiece(state, from, player);

    refreshIslandClaim(state, originIsland);

    if (destinationIsland !== originIsland) {
      refreshIslandClaim(state, destinationIsland);
    }

    state.localEval = oldLocalEval;
    state.metaEval = META_EVAL[state.fireClaims | (state.iceClaims << 7)];

    state.emptyCount++;
    state.ply--;
    state.turn = player;
    state.winner = 0;
  }

  /*
   * ============================================================
   * 合法步生成
   * ============================================================
   */

  const NODE_GENERATION_BUFFER = new Uint16Array(MAX_MOVES);
  const ROLLOUT_MOVE_BUFFER = new Uint16Array(MAX_MOVES);
  const ROLLOUT_PATH = new Uint16Array(MAX_DEPTH);
  const ROLLOUT_UNDO = new Float64Array(MAX_DEPTH);

  const SOLVER_MOVE_BUFFERS = Array.from(
    { length: MAX_DEPTH },
    () => new Uint16Array(MAX_MOVES)
  );

  function appendMovesForPiece(state, from, output, count) {
    const destinations = DESTINATIONS[from];

    for (let i = 0; i < destinations.length; i++) {
      const to = destinations[i];

      if (isEmpty(state, to)) {
        output[count++] = encodeMove(from, to);
      }
    }

    return count;
  }

  function generateMovesToBuffer(state, output) {
    let count = 0;

    let lowBits = state.turn === 1 ? state.fireLo : state.iceLo;

    while (lowBits) {
      const leastBit = (lowBits & -lowBits) >>> 0;
      const bitIndex = 31 - Math.clz32(leastBit);

      count = appendMovesForPiece(state, bitIndex, output, count);
      lowBits = (lowBits ^ leastBit) >>> 0;
    }

    let highBits = state.turn === 1 ? state.fireHi : state.iceHi;

    while (highBits) {
      const leastBit = (highBits & -highBits) >>> 0;
      const bitIndex = 31 - Math.clz32(leastBit);
      const from = 28 + bitIndex;

      count = appendMovesForPiece(state, from, output, count);
      highBits = (highBits ^ leastBit) >>> 0;
    }

    return count;
  }

  function generateMoveArray(state) {
    const count = generateMovesToBuffer(state, NODE_GENERATION_BUFFER);
    const result = new Array(count);

    for (let i = 0; i < count; i++) {
      result[i] = NODE_GENERATION_BUFFER[i];
    }

    return result;
  }

  /*
   * ============================================================
   * 走法啟發式
   * ============================================================
   */

  function quickMoveScore(state, move, player, beforeEvaluation) {
    const oldLocalEval = makeMove(state, move);

    let score;

    if (state.winner === player) {
      score = 1000000;
    } else if (state.winner === -player) {
      score = -1000000;
    } else {
      const delta = positionEvaluation(state) - beforeEvaluation;

      /*
       * positionEvaluation 是火方視角。
       * 冰方行動時要反轉符號。
       */
      score = player * delta;
    }

    unmakeMove(state, move, oldLocalEval);
    return score;
  }

  function chooseRolloutMove(state, buffer, count, strength) {
    if (count === 1) return buffer[0];

    /*
     * 弱 AI 保留更多隨機性。
     */
    if (random() > strength) {
      return buffer[randomIndex(count)];
    }

    /*
     * 無放回抽樣。
     *
     * 原版可能在一次 rolloutChoice 中重複抽到同一走法。
     * 這裡用局部 Fisher-Yates shuffle 保證不重複。
     */
    const sampleCount = Math.min(
      count,
      2 + Math.floor(strength * 8)
    );

    const player = state.turn;
    const beforeEvaluation = positionEvaluation(state);

    let bestMove = buffer[0];
    let bestScore = -Infinity;

    for (let sample = 0; sample < sampleCount; sample++) {
      const selectedIndex =
        sample + randomIndex(count - sample);

      const temporary = buffer[sample];
      buffer[sample] = buffer[selectedIndex];
      buffer[selectedIndex] = temporary;

      const move = buffer[sample];
      const score =
        quickMoveScore(
          state,
          move,
          player,
          beforeEvaluation
        ) +
        random() * 0.001;

      if (score > bestScore) {
        bestScore = score;
        bestMove = move;
      }
    }

    return bestMove;
  }

  /*
   * ============================================================
   * 精確尾局求解器
   * ============================================================
   *
   * 回傳值是相對於 state.turn：
   *
   *  1 = 輪到的一方可以強制勝利
   *  0 = 最佳結果是和局
   * -1 = 輪到的一方必敗
   *  2 = 因 deadline 中止
   */

  const EXACT_TT = new Map();
  let solverChecks = 0;

  function exactOutcome(state, deadline, depth = 0) {
    if (state.winner === 2) return 0;

    if (state.winner === 1 || state.winner === -1) {
      return state.winner === state.turn ? 1 : -1;
    }

    if (
      (solverChecks++ & 63) === 0 &&
      performance.now() >= deadline - 0.5
    ) {
      return EXACT_ABORT;
    }

    const key = stateKey(state);
    const cached = EXACT_TT.get(key);

    if (cached !== undefined) {
      return cached;
    }

    const buffer = SOLVER_MOVE_BUFFERS[depth];
    const count = generateMovesToBuffer(state, buffer);

    if (count === 0) {
      EXACT_TT.set(key, 0);
      return 0;
    }

    const player = state.turn;
    let best = -1;

    for (let i = 0; i < count; i++) {
      const move = buffer[i];
      const oldLocalEval = makeMove(state, move);

      let result;

      if (state.winner === 2) {
        result = 0;
      } else if (state.winner === player) {
        result = 1;
      } else if (state.winner === -player) {
        result = -1;
      } else {
        const childResult = exactOutcome(
          state,
          deadline,
          depth + 1
        );

        if (childResult === EXACT_ABORT) {
          unmakeMove(state, move, oldLocalEval);
          return EXACT_ABORT;
        }

        result = -childResult;
      }

      unmakeMove(state, move, oldLocalEval);

      if (result === 1) {
        EXACT_TT.set(key, 1);
        return 1;
      }

      if (result === 0) {
        best = 0;
      }
    }

    EXACT_TT.set(key, best);
    return best;
  }

  /*
   * ============================================================
   * Rollout
   * ============================================================
   */

  function terminalFireReward(state) {
    if (state.winner === 1) return 1;
    if (state.winner === -1) return 0;
    if (state.winner === 2) return 0.5;
    return -1;
  }

  function staticFireReward(state) {
    const terminal = terminalFireReward(state);

    if (terminal >= 0) return terminal;

    /*
     * 將啟發式分數映射到約 0.02～0.98。
     * 只在搜尋 deadline 即將耗盡時使用。
     */
    return (
      0.5 +
      0.48 * Math.tanh(positionEvaluation(state) / 120)
    );
  }

  function exactOutcomeToFireReward(state, outcome) {
    if (outcome === 0) return 0.5;

    if (outcome === 1) {
      return state.turn === 1 ? 1 : 0;
    }

    return state.turn === 1 ? 0 : 1;
  }

  function rolloutFire(state, strength, deadline) {
    let madeCount = 0;
    let reward = 0.5;

    while (madeCount < MAX_DEPTH) {
      const terminal = terminalFireReward(state);

      if (terminal >= 0) {
        reward = terminal;
        break;
      }

      /*
       * 在尾局嘗試精確求解。
       */
      if (
        state.emptyCount <= EXACT_EMPTY_THRESHOLD &&
        performance.now() < deadline - 1
      ) {
        const exact = exactOutcome(state, deadline, 0);

        if (exact !== EXACT_ABORT) {
          reward = exactOutcomeToFireReward(state, exact);
          break;
        }
      }

      /*
       * 避免一個過長 rollout 讓搜尋大幅超過時間限制。
       */
      if (
        (madeCount & 3) === 0 &&
        performance.now() >= deadline - 0.5
      ) {
        reward = staticFireReward(state);
        break;
      }

      const count = generateMovesToBuffer(
        state,
        ROLLOUT_MOVE_BUFFER
      );

      if (count === 0) {
        reward = 0.5;
        break;
      }

      const move = chooseRolloutMove(
        state,
        ROLLOUT_MOVE_BUFFER,
        count,
        strength
      );

      ROLLOUT_PATH[madeCount] = move;
      ROLLOUT_UNDO[madeCount] = makeMove(state, move);
      madeCount++;
    }

    /*
     * 恢復到 rollout 開始前的狀態。
     */
    for (let i = madeCount - 1; i >= 0; i--) {
      unmakeMove(
        state,
        ROLLOUT_PATH[i],
        ROLLOUT_UNDO[i]
      );
    }

    return reward;
  }

  /*
   * ============================================================
   * MCTS Tree
   * ============================================================
   *
   * valueFire 固定為火方視角：
   *
   * 火勝 = 1
   * 和局 = 0.5
   * 冰勝 = 0
   *
   * 因此換 root 或換行動方後，舊統計仍然有效。
   */

  class Node {
    constructor(move = 0, key = '', prior = 0) {
      this.move = move;
      this.key = key;
      this.prior = prior;

      this.children = [];
      this.untried = null;

      this.visits = 0;
      this.valueFire = 0;
      this.fireWins = 0;
      this.iceWins = 0;
    }
  }

  function selectChild(node, player, exploration) {
    const logarithm = Math.log(node.visits + 1);

    let best = null;
    let bestScore = -Infinity;

    for (const child of node.children) {
      const fireMean =
        child.visits > 0
          ? child.valueFire / child.visits
          : 0.5;

      const exploitation =
        player === 1 ? fireMean : 1 - fireMean;

      const explorationTerm =
        exploration *
        Math.sqrt(logarithm / Math.max(1, child.visits));

      /*
       * Progressive bias：
       * 初期讓有領域先驗的走法稍微優先；
       * visits 增加後影響逐漸消失。
       */
      const normalizedPrior = Math.tanh(child.prior / 25);
      const priorTerm =
        (0.18 * normalizedPrior) /
        (1 + child.visits * 0.15);

      const score =
        exploitation +
        explorationTerm +
        priorTerm +
        random() * 1e-9;

      if (score > bestScore) {
        bestScore = score;
        best = child;
      }
    }

    return best;
  }

  let lastExpansionPrior = 0;

  function takeExpansionMove(node, state, strength) {
    const moves = node.untried;
    const length = moves.length;

    const sampleCount = Math.min(
      length,
      3 + Math.floor(strength * 7)
    );

    const player = state.turn;
    const beforeEvaluation = positionEvaluation(state);

    let bestSlot = 0;
    let bestScore = -Infinity;

    /*
     * 從尚未展開的走法中無放回抽樣，
     * 用輕量評估決定本次優先展開哪一步。
     */
    for (let sample = 0; sample < sampleCount; sample++) {
      const selectedIndex =
        sample + randomIndex(length - sample);

      const temporary = moves[sample];
      moves[sample] = moves[selectedIndex];
      moves[selectedIndex] = temporary;

      const score =
        quickMoveScore(
          state,
          moves[sample],
          player,
          beforeEvaluation
        ) +
        random() * 0.001;

      if (score > bestScore) {
        bestScore = score;
        bestSlot = sample;
      }
    }

    const move = moves[bestSlot];
    const lastIndex = moves.length - 1;

    moves[bestSlot] = moves[lastIndex];
    moves.pop();

    lastExpansionPrior = bestScore;
    return move;
  }

  const TREE_NODE_PATH = new Array(MAX_DEPTH + 1);
  const TREE_MOVE_PATH = new Uint16Array(MAX_DEPTH);
  const TREE_UNDO_PATH = new Float64Array(MAX_DEPTH);

  function runIteration(
    root,
    state,
    exploration,
    strength,
    deadline
  ) {
    let node = root;
    let nodeCount = 1;
    let moveCount = 0;

    TREE_NODE_PATH[0] = root;

    /*
     * Selection + Expansion
     */
    while (!state.winner) {
      if (node.untried === null) {
        node.untried = generateMoveArray(state);
      }

      if (node.untried.length > 0) {
        const move = takeExpansionMove(
          node,
          state,
          strength
        );

        TREE_MOVE_PATH[moveCount] = move;
        TREE_UNDO_PATH[moveCount] = makeMove(state, move);
        moveCount++;

        const child = new Node(
          move,
          stateKey(state),
          lastExpansionPrior
        );

        node.children.push(child);
        node = child;

        TREE_NODE_PATH[nodeCount++] = child;
        break;
      }

      if (node.children.length === 0) {
        break;
      }

      const child = selectChild(
        node,
        state.turn,
        exploration
      );

      const move = child.move;

      TREE_MOVE_PATH[moveCount] = move;
      TREE_UNDO_PATH[moveCount] = makeMove(state, move);
      moveCount++;

      node = child;
      TREE_NODE_PATH[nodeCount++] = child;
    }

    /*
     * Simulation
     */
    const rewardFire = rolloutFire(
      state,
      strength,
      deadline
    );

    /*
     * Backpropagation
     */
    for (let i = 0; i < nodeCount; i++) {
      const current = TREE_NODE_PATH[i];

      current.visits++;
      current.valueFire += rewardFire;

      if (rewardFire === 1) {
        current.fireWins++;
      } else if (rewardFire === 0) {
        current.iceWins++;
      }
    }

    /*
     * 恢復 root state。
     */
    for (let i = moveCount - 1; i >= 0; i--) {
      unmakeMove(
        state,
        TREE_MOVE_PATH[i],
        TREE_UNDO_PATH[i]
      );
    }
  }

  /*
   * ============================================================
   * 直接勝利檢查
   * ============================================================
   */

  function findImmediateWinningMove(state, moves) {
    const player = state.turn;

    for (let i = 0; i < moves.length; i++) {
      const move = moves[i];
      const oldLocalEval = makeMove(state, move);
      const wins = state.winner === player;

      unmakeMove(state, move, oldLocalEval);

      if (wins) return move;
    }

    return 0;
  }

  /*
   * ============================================================
   * Tree reuse
   * ============================================================
   */

  let persistentRoot = null;

  function findReusableRoot(key) {
    if (!persistentRoot) return null;

    if (persistentRoot.key === key) {
      return persistentRoot;
    }

    /*
     * 正常情況：
     * - AI 對 AI：下一次 state 就是 persistentRoot；
     * - 人類對 AI：人類走一步後，state 是它的一個 child。
     *
     * 額外搜尋到 grandchildren，處理少數排程或介面狀況。
     */
    for (const child of persistentRoot.children) {
      if (child.key === key) {
        return child;
      }
    }

    for (const child of persistentRoot.children) {
      for (const grandchild of child.children) {
        if (grandchild.key === key) {
          return grandchild;
        }
      }
    }

    return null;
  }

  function rootExpectedValue(child, rootPlayer) {
    if (!child || child.visits === 0) return 0.5;

    const fireMean = child.valueFire / child.visits;
    return rootPlayer === 1 ? fireMean : 1 - fireMean;
  }

  function rootWinRate(child, rootPlayer) {
    if (!child || child.visits === 0) return 0;

    return rootPlayer === 1
      ? child.fireWins / child.visits
      : child.iceWins / child.visits;
  }

  function selectBestRootChild(root, rootPlayer) {
    let best = null;

    for (const child of root.children) {
      if (!best) {
        best = child;
        continue;
      }

      if (child.visits > best.visits) {
        best = child;
        continue;
      }

      if (
        child.visits === best.visits &&
        rootExpectedValue(child, rootPlayer) >
          rootExpectedValue(best, rootPlayer)
      ) {
        best = child;
      }
    }

    return best;
  }

  /*
   * ============================================================
   * Worker 入口
   * ============================================================
   */

  self.onmessage = function (event) {
    const data = event.data;

    if (!data || data.type !== 'start') return;

    const state = createCompactState(data.state);
    const token = data.token;

    const limit = Math.max(
      50,
      Number(data.limitMs) || 6000
    );

    const exploration = Math.max(
      0.1,
      Number(data.exploration) || 1.4
    );

    const strength =
      {
        easy: 0.12,
        hard: 0.42,
        expert: 0.72,
        custom: 0.9
      }[data.level] || 0.3;

    seedRandom(token, state);

    if (EXACT_TT.size > EXACT_TT_MAX_SIZE) {
      EXACT_TT.clear();
    }

    solverChecks = 0;

    const rootPlayer = state.turn;
    const incomingKey = stateKey(state);

    let root = findReusableRoot(incomingKey);

    if (!root) {
      root = new Node(0, incomingKey, 0);
    }

    /*
     * 先生成 root 合法步，用於：
     * 1. 無合法步判斷；
     * 2. 直接勝利檢查。
     */
    const rootMoves = generateMoveArray(state);

    const start = performance.now();
    const deadline = start + limit;

    if (rootMoves.length === 0) {
      persistentRoot = root;

      self.postMessage({
        type: 'done',
        token,
        elapsed: performance.now() - start,
        iterations: 0,
        move: null,
        expected: 0.5,
        winRate: 0
      });

      return;
    }

    /*
     * 如果有直接勝利步，立即落子，不再浪費剩餘時間。
     */
    const immediateWin = findImmediateWinningMove(
      state,
      rootMoves
    );

    if (immediateWin) {
      const oldLocalEval = makeMove(state, immediateWin);
      const childKey = stateKey(state);

      let winningChild = null;

      for (const child of root.children) {
        if (child.key === childKey) {
          winningChild = child;
          break;
        }
      }

      if (!winningChild) {
        winningChild = new Node(
          immediateWin,
          childKey,
          1000000
        );

        root.children.push(winningChild);
      }

      if (winningChild.visits === 0) {
        winningChild.visits = 1;

        if (rootPlayer === 1) {
          winningChild.valueFire = 1;
          winningChild.fireWins = 1;
        } else {
          winningChild.valueFire = 0;
          winningChild.iceWins = 1;
        }
      }

      unmakeMove(state, immediateWin, oldLocalEval);

      /*
       * 預先把實際將落子的子節點保留下來。
       */
      persistentRoot = winningChild;

      self.postMessage({
        type: 'done',
        token,
        elapsed: performance.now() - start,
        iterations: 1,
        move: exportMove(immediateWin),
        expected: 1,
        winRate: 1
      });

      return;
    }

    if (root.untried === null) {
      root.untried = rootMoves.slice();
    }

    let iterations = 0;
    let nextProgressTime = start + 100;

    /*
     * 至少執行一次 iteration。
     */
    while (
      iterations === 0 ||
      performance.now() < deadline
    ) {
      runIteration(
        root,
        state,
        exploration,
        strength,
        deadline
      );

      iterations++;

      /*
       * 每四次 iteration 檢查時間，
       * rollout 本身也會檢查 deadline。
       */
      if ((iterations & 3) === 0) {
        const now = performance.now();

        if (now >= nextProgressTime) {
          self.postMessage({
            type: 'progress',
            token,
            elapsed: now - start,
            iterations
          });

          nextProgressTime += 100;

          if (nextProgressTime < now) {
            nextProgressTime =
              Math.floor(now / 100) * 100 + 100;
          }
        }

        if (now >= deadline) break;
      }
    }

    const best = selectBestRootChild(
      root,
      rootPlayer
    );

    const elapsed = performance.now() - start;
    const expected = rootExpectedValue(
      best,
      rootPlayer
    );

    const winRate = rootWinRate(
      best,
      rootPlayer
    );

    /*
     * 丟棄 root 的其他分支，只保留預計實際落子的子樹。
     *
     * 如果主執行緒最終沒有採用此走法，
     * 下一次 state key 不匹配時會自動重建。
     */
    persistentRoot = best || root;

    self.postMessage({
      type: 'done',
      token,
      elapsed,
      iterations,
      move: best ? exportMove(best.move) : null,
      expected,
      winRate
    });
  };
</script>

function startAI() {
  if (
    !gameStarted ||
    state.winner ||
    controllers[state.turn] === 'human'
  ) {
    return;
  }

  const moves = getLegalMoves(state);

  if (!moves.length) {
    state.winner = 2;
    history[historyIndex].state = cloneState(state);
    renderAll();
    return;
  }

  const level = controllers[state.turn];
  const config = AI_LEVELS[level];

  if (!config) return;

  selectedCell = -1;
  lastAIStats = null;
  thinking = true;
  aiProgress = {
    elapsed: 0,
    iterations: 0
  };

  renderAll();

  const token = ++aiToken;
  const started = performance.now();

  /*
   * 關鍵修改：
   * worker 不再每次思考都重新建立。
   *
   * 搜尋正常完成後會保留 worker，
   * 從而允許下一回合重用 MCTS 子樹。
   */
  try {
    if (!aiWorker) {
      aiWorker = new Worker(getWorkerURL());
    }
  } catch (error) {
    aiWorker = null;
    runFallbackAI(token, started);
    return;
  }

  aiWorker.onmessage = event => {
    const message = event.data;

    if (
      !message ||
      message.token !== aiToken ||
      message.token !== token
    ) {
      return;
    }

    if (message.type === 'progress') {
      aiProgress = {
        elapsed: message.elapsed,
        iterations: message.iterations
      };

      renderStatus();
      return;
    }

    if (message.type === 'done') {
      /*
       * 不要在這裡 terminate worker。
       *
       * 舊版：
       *
       * aiWorker?.terminate();
       * aiWorker = null;
       *
       * 必須刪除，否則 tree reuse 無法工作。
       */

      thinking = false;

      const stats = {
        elapsed: message.elapsed,
        iterations: message.iterations,
        expected: message.expected,
        winRate: message.winRate,
        level
      };

      if (message.move) {
        commitMove(
          message.move,
          'ai',
          stats
        );
      } else {
        state.winner = 2;
        lastAIStats = stats;
        history[historyIndex].state =
          cloneState(state);

        renderAll();
      }
    }
  };

  aiWorker.onerror = () => {
    if (token !== aiToken) return;

    aiWorker?.terminate();
    aiWorker = null;

    runFallbackAI(token, started);
  };

  const exploration =
    level === 'custom'
      ? preferences.exploration
      : config.exploration;

  const limitMs =
    level === 'custom'
      ? preferences.customTimeSeconds * 1000
      : config.ms;

  try {
    aiWorker.postMessage({
      type: 'start',
      token,
      state: {
        board: Array.from(state.board),
        claims: Array.from(state.claims),
        turn: state.turn,
        winner: state.winner,
        ply: state.ply
      },
      level,
      limitMs,
      exploration
    });
  } catch (error) {
    aiWorker?.terminate();
    aiWorker = null;

    runFallbackAI(token, started);
  }
}

function cancelAI() {
  clearTimeout(aiStartTimer);
  aiStartTimer = null;
  aiToken++;

  if (aiWorker) {
    aiWorker.terminate();
    aiWorker = null;
  }

  thinking = false;
  aiProgress = {
    elapsed: 0,
    iterations: 0
  };
}

const AI_LEVELS = {
  easy: {
    ms: DEFAULT_AI_SECONDS.easy * 1000,
    exploration: 1.55
  },

  hard: {
    ms: DEFAULT_AI_SECONDS.hard * 1000,
    exploration: 1.28
  },

  expert: {
    ms: DEFAULT_AI_SECONDS.expert * 1000,
    exploration: 1.08
  },

  custom: {
    ms: DEFAULT_AI_SECONDS.custom * 1000,
    exploration: 1.25
  }
};