代码： 全选
這是一次非常核心且強大的重構。我們將針對您的三個要求，將精確計算與「5軸SAT（分離軸定理）過濾」結合，大幅降低幾何碰撞判定的計算量（O(N²) 的複雜度會被 O(1) 的純浮點數投影比對先行攔截）。同時，修正 MCTS 的 UCB 公式與 Minimax 搜尋樹的傳遞邏輯，並讓 AI 完美理解「單接時第二子可跨目標」的例外規則。
請在原始碼中尋找對應的函式並**完整替換**。
### 第一部分：加入 SAT 核心算法與替換原有的重疊判定
在程式碼的 `shapesOverlap` 函式**上方**，插入 SAT 相關的輔助函式，並直接替換掉 `shapesOverlap`、`ghostConflictsWithPiece`、`isValidGhost`、`twoGhostsCompatible`、`formsTriGolden` 以及計分模擬迴圈的寫法。
```javascript
// =============================================================================
// SAT 5軸快速碰撞檢測 (浮點投影過濾)
// =============================================================================
function getNumericPt(p) {
const PI5 = Math.PI / 5;
const [a, b, c, d] = p;
const x = a + b * Math.cos(PI5) + c * Math.cos(2 * PI5) + d * Math.cos(3 * PI5);
const y = b * Math.sin(PI5) + c * Math.sin(2 * PI5) + d * Math.sin(3 * PI5);
return { x, y };
}
function calculateSAT(vertices) {
const PI5 = Math.PI / 5;
let bounds = [];
for (let k = 0; k < 5; k++) {
let ax = -Math.sin(k * PI5), ay = Math.cos(k * PI5);
let min = Infinity, max = -Infinity;
for (let v of vertices) {
let pt = getNumericPt(v);
let proj = pt.x * ax + pt.y * ay;
if (proj < min) min = proj;
if (proj > max) max = proj;
}
bounds.push({ min, max });
}
return bounds;
}
function getSAT(p) {
if (!p.satBounds) p.satBounds = calculateSAT(p.vertices);
return p.satBounds;
}
function checkSATCollision(satA, satB) {
if (!satA || !satB) return 'touch'; // 保險機制
let touch = false;
for (let i = 0; i < 5; i++) {
let a = satA[i], b = satB[i];
if (a.max < b.min - 1e-5 || b.max < a.min - 1e-5) return 'separated';
if (Math.abs(a.max - b.min) <= 1e-5 || Math.abs(b.max - a.min) <= 1e-5) touch = true;
}
return touch ? 'touch' : 'overlap';
}
// 以 SAT 取代原本極慢的面重疊演算法
function shapesOverlap(shapeA, shapeB) {
return checkSATCollision(getSAT(shapeA), getSAT(shapeB)) === 'overlap';
}
// 用 SAT 優化 isValidGhost 邊與頂點的精確檢查
function isValidGhost(gp, existingPieces) {
let edgeOverlapCount = 0;
let perfectMatchCount = 0;
let attachedVertices = [];
let gpSat = getSAT(gp);
for (let exist of existingPieces) {
let col = checkSATCollision(gpSat, getSAT(exist));
if (col === 'separated') continue;
if (col === 'overlap') return false; // 面重疊
for (let ei = 0; ei < 4; ei++) {
for (let ej = 0; ej < 4; ej++) {
if (segmentsOverlapAsEdges(gp.vertices[ei], gp.vertices[(ei + 1) % 4], exist.vertices[ej], exist.vertices[(ej + 1) % 4])) {
edgeOverlapCount++;
if (segmentsPerfectlyMatch(gp.vertices[ei], gp.vertices[(ei + 1) % 4], exist.vertices[ej], exist.vertices[(ej + 1) % 4])) {
perfectMatchCount++;
attachedVertices.push(ei, (ei + 1) % 4);
}
}
}
}
}
if (edgeOverlapCount !== 1 || perfectMatchCount !== 1) return false;
for (let vi = 0; vi < 4; vi++) {
if (attachedVertices.includes(vi)) continue;
for (let exist of existingPieces) {
if (checkSATCollision(gpSat, getSAT(exist)) === 'separated') continue;
for (let vj = 0; vj < 4; vj++) {
if (pointsEqual(gp.vertices[vi], exist.vertices[vj])) return false;
}
}
}
return true;
}
function ghostConflictsWithPiece(g, piece) {
let col = checkSATCollision(getSAT(g), getSAT(piece));
if (col === 'separated') return false;
if (col === 'overlap') return true;
for (let ei = 0; ei < 4; ei++) {
for (let ej = 0; ej < 4; ej++) {
if (segmentsOverlapAsEdges(g.vertices[ei], g.vertices[(ei + 1) % 4], piece.vertices[ej], piece.vertices[(ej + 1) % 4])) return true;
}
}
for (let vi = 0; vi < 4; vi++) {
for (let vj = 0; vj < 4; vj++) {
if (pointsEqual(g.vertices[vi], piece.vertices[vj])) return true;
}
}
return false;
}
function twoGhostsCompatible(g1, g2) {
let col = checkSATCollision(getSAT(g1), getSAT(g2));
if (col === 'separated') return true;
if (col === 'overlap') return false;
for (let ei = 0; ei < 4; ei++) {
for (let ej = 0; ej < 4; ej++) {
if (segmentsOverlapAsEdges(g1.vertices[ei], g1.vertices[(ei + 1) % 4], g2.vertices[ej], g2.vertices[(ej + 1) % 4])) return false;
}
}
for (let vi = 0; vi < 4; vi++) {
for (let vj = 0; vj < 4; vj++) {
if (pointsEqual(g1.vertices[vi], g2.vertices[vj])) return false;
}
}
return true;
}
function formsTriGolden(A, B) {
if (checkSATCollision(getSAT(A), getSAT(B)) === 'separated') return false;
for (let v of A.vertices) {
for (let e = 0; e < 4; e++) {
if (pointOnOpenSegment(v, B.vertices[e], B.vertices[(e + 1) % 4])) return true;
}
}
for (let v of B.vertices) {
for (let e = 0; e < 4; e++) {
if (pointOnOpenSegment(v, A.vertices[e], A.vertices[(e + 1) % 4])) return true;
}
}
return false;
}
```
同時，將 `simulateScoreGain` 與 `simulateScoringTriGolden` 函式內的雙迴圈起頭加上 SAT 攔截，以節省遍歷點的成本：
找到對應函式內的 `if (A.id === B.id) continue;`，在其下方加入一行：
```javascript
if (checkSATCollision(getSAT(A), getSAT(B)) === 'separated') continue;
```
*(注意：`simulateScoreGain` 與 `simulateScoringTriGolden` 都有這個迴圈)*
### 第二部分：修正 AI 無法跨目標落子 (Exception Rule) 的問題
原本 AI 用來生產候選池的 `getAllValidMoves` 只尋找同一個目標棋子。現在我們將跨棋子落子的例外條件完美融合進此函式中，讓 Minimax/MCTS 能看見這些「神仙下法」。
完整替換 `getAllValidMoves` 函式：
```javascript
function getAllValidMoves(player) {
let validPairs = [];
let myTiles = [0, 1, 2].map(x => 'tile' + (player === 1 ? x : x + 3));
let counts = {};
myTiles.forEach(t => (counts[t] = piecesCount[t] + tempPieces.filter(p => p.svgId === t).length));
let availTypes = myTiles.filter(t => counts[t] > 0);
let oppPieces = pieces.filter(p => p.owner !== player);
let validGhosts = [];
for (let opp of oppPieces) {
for (let t of availTypes) {
for (let flip of [false, true]) {
for (let i = 0; i < 4; i++) {
for (let j = 0; j < 4; j++) {
let res = attachByEdge(SHAPE_MAP[t], flip, j, opp.vertices[i], opp.vertices[(i + 1) % 4], !!opp.isFlipped);
if (res) {
let gp = {
vertices: res.vertices, type: SHAPE_MAP[t], owner: player, svgId: t, isFlipped: flip,
edgeOnOpp: i, targetId: opp.id, myEdge: j, targetEdge: i, parentId: opp.id, level: (opp.level !== undefined ? opp.level : 0) + 1
};
if (isValidGhost(gp, pieces)) validGhosts.push(gp);
}
}
}
}
}
}
for (let i = 0; i < validGhosts.length; i++) {
for (let j = i + 1; j < validGhosts.length; j++) {
let g1 = validGhosts[i], g2 = validGhosts[j];
if (g1.svgId === g2.svgId && counts[g1.svgId] < 2) continue;
if (!twoGhostsCompatible(g1, g2)) continue;
if (g1.targetId === g2.targetId) {
if (g1.edgeOnOpp !== g2.edgeOnOpp) validPairs.push([g1, g2, g1.targetId]);
} else {
// 例外規則：跨目標時，若任一子能得分，或兩子互相形成頂鑫結構，即為合規
let g1Scores = simulateScoreGain([g1])[player] > 0;
let g2Scores = simulateScoreGain([g2])[player] > 0;
if (g1Scores || g2Scores || formsTriGolden(g1, g2)) {
validPairs.push([g1, g2, g1.targetId]);
}
}
}
}
return validPairs;
}
```
接著，替換 `buildCandidateMovesForNode` 內部針對單接提取候選的邏輯 (這確保深層搜尋時的過濾器支援跨目標)。
在 `buildCandidateMovesForNode` 函式中，找到 `let sameGhostPlacement = ...` 這行，將其**修改**為：
```javascript
let sameGhostPlacement = (g1, g2) => g1.targetId === g2.targetId && g1.edgeOnOpp === g2.edgeOnOpp && g1.myEdge === g2.myEdge && g1.svgId === g2.svgId && g1.isFlipped === g2.isFlipped;
```
再找到該函式內的 `let pairs = validMoves.filter(...)` 那一段，**替換**為：
```javascript
let pairs = validMoves.filter(
mv => sameGhostPlacement(mv[0], g) || sameGhostPlacement(mv[1], g)
);
```
### 第三部分：修復 MCTS UCB 計算錯誤與改寫 Minimax 為真正的 Alpha-Beta (解決送分/卡頓)
AI 原本之所以會「隨便送分給對方」，有兩個嚴重的核心邏輯漏洞：
1. 原本的 Minimax 是用 Breadth-First 寫的「Maximax」（只取路徑最高分，假設對手配合你得分）。
2. MCTS 的 `ucbSelectChild` 永遠選 `valueSum` 最高的，導致當輪到「對手節點」時，MCTS 會幫對手尋找「能讓 AI 贏的最高分下法」，這完全違背了對抗樹的原則。
請至 `startAI` 內部，將 `if (useMinimax) {` 到 `} else { // ===== MCTS =====` 之間的**搜尋邏輯** (即 `let maxDepth = turnsLeft;` 開頭到 `expectedValue = ...` 的整段迴圈) **完全替換**為真正的 Alpha-Beta 剪枝：
```javascript
if (skipSearchWithRandomMove) {
bestMove = candidateMoves[0];
expectedValue = 0;
} else {
let maxDepth = turnsLeft;
let alphaBetaTimeLimit = timeLimit;
// 真正的 Alpha-Beta Minimax 搜尋
function alphaBeta(depth, alpha, beta, isMaximizer, hypPieces, mover) {
if (cancelAi || performance.now() - searchStartTime > alphaBetaTimeLimit) return 0;
if (depth === 0) {
let gain = simulateScoreGain(hypPieces);
return gain[currentPlayer] - gain[oppPlayerNum];
}
let validMvs = buildCandidateMovesForNode(mover, hypPieces);
if (validMvs.length === 0) {
let gain = simulateScoreGain(hypPieces);
return gain[currentPlayer] - gain[oppPlayerNum];
}
// 限制分支係數以防超時
validMvs = validMvs.slice(0, 6);
let nextMover = mover === 1 ? 2 : 1;
if (isMaximizer) {
let maxEval = -Infinity;
for (let mv of validMvs) {
let eval = alphaBeta(depth - 1, alpha, beta, false, hypPieces.concat([mv[0], mv[1]]), nextMover);
maxEval = Math.max(maxEval, eval);
alpha = Math.max(alpha, eval);
if (beta <= alpha) break;
}
return maxEval;
} else {
let minEval = Infinity;
for (let mv of validMvs) {
let eval = alphaBeta(depth - 1, alpha, beta, true, hypPieces.concat([mv[0], mv[1]]), nextMover);
minEval = Math.min(minEval, eval);
beta = Math.min(beta, eval);
if (beta <= alpha) break;
}
return minEval;
}
}
bestMove = candidateMoves[0];
expectedValue = -Infinity;
// 迭代加深 (Iterative Deepening) 保證超時前有最好結果
for (let depth = 1; depth <= maxDepth; depth++) {
let currentBestScore = -Infinity;
let currentBestMove = candidateMoves[0];
let alpha = -Infinity;
let beta = Infinity;
for (let mv of candidateMoves) {
if (cancelAi || performance.now() - searchStartTime > alphaBetaTimeLimit) break;
let nextMover = currentPlayer === 1 ? 2 : 1;
let eval = alphaBeta(depth - 1, alpha, beta, false, [mv[0], mv[1]], nextMover);
if (eval > currentBestScore) {
currentBestScore = eval;
currentBestMove = mv;
}
alpha = Math.max(alpha, eval);
}
if (cancelAi || performance.now() - searchStartTime > alphaBetaTimeLimit) break;
bestMove = currentBestMove;
expectedValue = currentBestScore;
showMessage(t('ai-minimax-progress', { depth: depth, time: ((performance.now() - searchStartTime) / 1000).toFixed(1) }), 0, true);
await new Promise(r => setTimeout(r, 0));
}
if (expectedValue === -Infinity) expectedValue = 0;
}
```
最後，在 `startAI` 內部找到 MCTS 區塊的 `function ucbSelectChild(node) {`，並將其替換為支援零和博弈對抗的寫法：
```javascript
function ucbSelectChild(node) {
let bestUcb = -Infinity, best = null;
let isRootPlayer = (node.mover === currentPlayer); // 判斷此節點輪到誰選
node.children.forEach(child => {
let exploit = child.valueSum / child.visits;
// 核心修復：如果輪到對手選擇分支，對手希望 AI 分數(simVal)越低越好，所以將評價反轉！
if (!isRootPlayer) exploit = 1 - exploit;
let ucb = child.visits === 0 ? Infinity : exploit + cValue * Math.sqrt(Math.log(node.visits) / child.visits);
if (ucb > bestUcb) {
bestUcb = ucb;
best = child;
}
});
return best;
}
```
完成以上修改後，AI 尋找「頂鑫跨連結構」的能力將大幅覺醒，並且運算速度將因為 SAT 數學優化而有質的飛躍。
