const SAT5_AXES = Array.from({ length: 5 }, (_, k) => {
  const angle = (k * Math.PI) / 5;
  return { x: -Math.sin(angle), y: Math.cos(angle) };
});

// 計算五條固定 SAT 軸上的投影區間。
// 軸是全域固定的，因此每顆棋子只需要保存五組 min / max，不必重複保存軸向量。
function calculateSAT(vertices) {
  const numericVertices = vertices.map(getNumericPt);

  return SAT5_AXES.map(axis => {
    let min = Infinity;
    let max = -Infinity;

    for (const pt of numericVertices) {
      const projection = pt.x * axis.x + pt.y * axis.y;
      if (projection < min) min = projection;
      if (projection > max) max = projection;
    }

    return { min, max };
  });
}

// 棋子頂點在本程式中建立後不會再被原地修改；因此 satBounds 可安全快取。
// 所有正式棋子、暫存棋子、活法 ghost、MCTS 假設棋子都應經此函式進入搜尋／合法性流程。
function preparePieceSAT(piece) {
  if (!piece || !piece.vertices) return piece;
  if (!piece.satBounds) piece.satBounds = calculateSAT(piece.vertices);
  return piece;
}

function getSAT(piece) {
  return preparePieceSAT(piece).satBounds;
}

// 在「指定盤面」上生成 player 的所有合法單子。
// boardPieces 可包含 minimax / MCTS 路徑中的假設棋子；extraHypPieces 用於正確扣除搜尋路徑已消耗的棋子數。
function getAllValidSingleMovesOnBoard(player, boardPieces, extraHypPieces = []) {
  const candidates = [];
  const counts = getRemainingCounts(player, extraHypPieces);

  const myTiles = [0, 1, 2].map(x => 'tile' + (player === 1 ? x : x + 3));
  const availTypes = myTiles.filter(tileId => counts[tileId] > 0);
  const opponentPieces = boardPieces.filter(piece => piece.owner !== player);

  for (const opponentPiece of opponentPieces) {
    for (const tileId of availTypes) {
      for (const flip of [false, true]) {
        for (let targetEdge = 0; targetEdge < 4; targetEdge++) {
          for (let myEdge = 0; myEdge < 4; myEdge++) {
            const result = attachByEdge(
              SHAPE_MAP[tileId],
              flip,
              myEdge,
              opponentPiece.vertices[targetEdge],
              opponentPiece.vertices[(targetEdge + 1) % 4],
              !!opponentPiece.isFlipped
            );

            if (!result) continue;

            const ghost = {
              id: allocateHypothesisPieceId(),
              vertices: result.vertices,
              type: SHAPE_MAP[tileId],
              owner: player,
              svgId: tileId,
              isFlipped: flip,
              edgeOnOpp: targetEdge,
              targetId: opponentPiece.id,
              myEdge,
              targetEdge,
              parentId: opponentPiece.id,
              level: (opponentPiece.level !== undefined ? opponentPiece.level : 0) + 1
            };

            preparePieceSAT(ghost);

            if (isValidGhost(ghost, boardPieces)) {
              candidates.push(ghost);
            }
          }
        }
      }
    }
  }

  return candidates;
}

// 真實盤面使用的相容包裝；保留既有呼叫方式。
function getAllValidSingleMoves(player) {
  return getAllValidSingleMovesOnBoard(player, pieces, []);
}

function buildCandidateMovesForNode(mover, extraHypPieces, quick) {
  // 搜尋樹內若該方只剩最後一子，必須生成單子候選。
  // 用 [ghost] 統一包裝，讓 minimax / MCTS 的「一個回合一個 move 陣列」模型保持一致。
  if (getRemainingPieceTotal(mover, extraHypPieces) === 1) {
    const boardPieces = pieces.concat(extraHypPieces);
    return getAllValidSingleMovesOnBoard(mover, boardPieces, extraHypPieces).map(ghost => [ghost]);
  }

  const ghosts = collectLiveGhostsForPlayer(mover, extraHypPieces);
  return buildCandidateMovesFromGhosts(mover, extraHypPieces, ghosts, quick);
}

const opponent = player === 1 ? 2 : 1;

const evaluatedMoves = moves.map(move => {
  const gain = simulateScoreGain([move]);

  return {
    move,
    // 與 minimax 的葉節點一致：以己方淨得分判斷。
    value: gain[player] - gain[opponent]
  };
});

const bestValue = Math.max(...evaluatedMoves.map(item => item.value));
const bestMoves = evaluatedMoves.filter(item => item.value === bestValue);

// 同分時保留隨機性；不同分時一定選擇最佳單接。
const move = bestMoves[Math.floor(Math.random() * bestMoves.length)].move;

function edgeGhostKey(ghost) {
  return edgeKey(ghost.targetId, ghost.targetEdge);
}

function groupGhostsByEdge(ghosts) {
  const result = new Map();

  for (const ghost of ghosts) {
    const key = edgeGhostKey(ghost);

    if (!result.has(key)) result.set(key, []);
    result.get(key).push(ghost);
  }

  return result;
}

function flattenEdgeGhosts(edgeGhostMap) {
  const result = [];

  for (const ghosts of edgeGhostMap.values()) {
    result.push(...ghosts);
  }

  return result;
}

// 對父節點每條邊的活法做增量失效檢查。
// 完全未受影響的邊直接共用原 ghosts 陣列；只有受影響的邊才新建陣列。
function filterEdgeGhostMapByNewPieces(parentEdgeGhostMap, newPieces) {
  const result = new Map();

  for (const [key, ghosts] of parentEdgeGhostMap) {
    const survivors = ghosts.filter(ghost => survivesHypotheticalPieces(ghost, newPieces));

    if (survivors.length === 0) continue;

    result.set(key, survivors.length === ghosts.length ? ghosts : survivors);
  }

  return result;
}

function appendGhostToEdgeMap(edgeGhostMap, ghost) {
  const key = edgeGhostKey(ghost);
  const oldList = edgeGhostMap.get(key) || [];

  // 不修改父節點共享的舊陣列。
  edgeGhostMap.set(key, oldList.concat([ghost]));
}

function deriveIncrementalEdgeGhosts(parentEdgeGhostsByPlayer, mover, newPieces, boardPieces) {
  const opponent = mover === 1 ? 2 : 1;

  // 新棋對雙方既有活法都可能造成失效。
  const moverEdgeGhosts = filterEdgeGhostMapByNewPieces(parentEdgeGhostsByPlayer[mover], newPieces);
  const opponentEdgeGhosts = filterEdgeGhostMapByNewPieces(parentEdgeGhostsByPlayer[opponent], newPieces);

  // mover 新落下的棋子四邊，會產生 opponent 的新活法。
  for (const newPiece of newPieces) {
    for (let edgeIndex = 0; edgeIndex < 4; edgeIndex++) {
      const newGhosts = enumerateEdgeMethods(newPiece, edgeIndex, boardPieces);

      for (const ghost of newGhosts) {
        preparePieceSAT(ghost);
        appendGhostToEdgeMap(opponentEdgeGhosts, ghost);
      }
    }
  }

  return {
    [mover]: moverEdgeGhosts,
    [opponent]: opponentEdgeGhosts
  };
}

function makeMCTSNode(mover, extraHypPieces, edgeGhostsByPlayer) {
  return {
    mover,
    extraHypPieces,

    // 每位玩家：Map<targetPieceId_targetEdge, ghost[]>
    // 每條邊只保存目前仍存活的活法；未改變的邊可與父節點結構共享。
    edgeGhostsByPlayer,

    children: [],
    visits: 0,
    valueSum: 0,
    untriedMoves: null,
    isTerminal: false,
    move: null,

    // 本節點由父節點落下的棋子；可為一子或兩子。
    lastPlaced: []
  };
}

let gc1 = Object.assign({}, mv[0], { id: fakeIdCounter-- });
let gc2 = Object.assign({}, mv[1], { id: fakeIdCounter-- });
let childExtra = node.extraHypPieces.concat([gc1, gc2]);
let childMover = node.mover === 1 ? 2 : 1;

let childGhostsByPlayer = deriveIncrementalGhosts(
  node.ghostsByPlayer,
  node.mover,
  gc1,
  gc2,
  pieces.concat(childExtra)
);

let child = makeMCTSNode(childMover, childExtra, childGhostsByPlayer);

const placedPieces = getMovePieces(mv).map(ghost =>
  preparePieceSAT(
    Object.assign({}, ghost, {
      id: fakeIdCounter--
    })
  )
);

const childExtra = node.extraHypPieces.concat(placedPieces);
const childMover = node.mover === 1 ? 2 : 1;

const childEdgeGhostsByPlayer = deriveIncrementalEdgeGhosts(
  node.edgeGhostsByPlayer,
  node.mover,
  placedPieces,
  pieces.concat(childExtra)
);

const child = makeMCTSNode(childMover, childExtra, childEdgeGhostsByPlayer);
child.lastPlaced = placedPieces;

let nextCandidates;

if (getRemainingPieceTotal(childMover, childExtra) === 1) {
  nextCandidates = getAllValidSingleMovesOnBoard(
    childMover,
    pieces.concat(childExtra),
    childExtra
  ).map(ghost => [ghost]);
} else {
  nextCandidates = buildCandidateMovesFromGhosts(
    childMover,
    childExtra,
    flattenEdgeGhosts(child.edgeGhostsByPlayer[childMover]),
    true
  );
}