博弈論完全指南 — Nim 遊戲、Sprague-Grundy 定理與組合賽局分析 | 資料結構與演算法

// ─── Nim 遊戲：勝負判定 ─────────────────────────────────

// 單堆 Nim（每次取 1~3 顆，LeetCode 292）
function canWinNim(n: number): boolean {
  // 定理：n % 4 === 0 時先手必輸
  // 1~3 必勝（直接取完）；4 必輸（取 k 顆，對手取 4-k 顆）
  return n % 4 !== 0;
}

// 一般多堆 Nim：XOR 所有堆
function canWinNimGeneral(piles: number[]): boolean {
  let xor = 0;
  for (const pile of piles) {
    xor ^= pile;
  }
  return xor !== 0; // XOR ≠ 0 → 先手必勝
}

// 測試
console.log(canWinNim(4));   // 輸出：false（4 % 4 = 0，先手必輸）
console.log(canWinNim(7));   // 輸出：true
console.log(canWinNimGeneral([3, 5, 7])); // 輸出：true（XOR = 1 ≠ 0）
console.log(canWinNimGeneral([1, 2, 3])); // 輸出：false（XOR = 0）

// ─── Nim 必勝策略：找出使 XOR 歸零的移動 ────────────────

function nimStrategy(piles: number[]): { pileIndex: number; newSize: number } | null {
  const xor = piles.reduce((acc, p) => acc ^ p, 0);
  if (xor === 0) return null; // 當前為 P-position，無必勝策略

  for (let i = 0; i < piles.length; i++) {
    const target = piles[i] ^ xor; // 使整體 XOR 歸零所需的值
    if (target < piles[i]) {       // 只能減少，不能增加
      return { pileIndex: i, newSize: target };
    }
  }
  return null; // 理論上不會到這裡（XOR ≠ 0 時一定存在解）
}

// 測試
const strategy = nimStrategy([3, 5, 7]);
console.log(strategy);
// 輸出：{ pileIndex: 1, newSize: 4 }（將堆 B 從 5 減到 4）

// 驗證：[3, 4, 7] → XOR = 011 ^ 100 ^ 111 = 000 ✓
console.log(canWinNimGeneral([3, 4, 7])); // 輸出：false（對手面臨 P-position）

// ─── Sprague-Grundy：計算 Grundy 值 ────────────────────

// mex 函數：集合中不包含的最小非負整數
function mex(set: Set<number>): number {
  let val = 0;
  while (set.has(val)) val++;
  return val;
}

// Subtraction Game：每次可取 subtractSet 中的任意數量
function computeGrundy(maxN: number, subtractSet: number[]): number[] {
  const G = new Array(maxN + 1).fill(0);
  // G[0] = 0（終局狀態，無法移動，P-position）

  for (let n = 1; n <= maxN; n++) {
    const reachable = new Set<number>();
    for (const s of subtractSet) {
      if (n - s >= 0) {
        reachable.add(G[n - s]); // 收集可達狀態的 Grundy 值
      }
    }
    G[n] = mex(reachable);
  }
  return G;
}

// 測試：每次可取 1 或 2 顆
const grundy = computeGrundy(12, [1, 2]);
console.log(grundy);
// 輸出：[0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0]
// 週期 3：n % 3 === 0 時為 P-position

// 測試：每次可取 1、3 或 4 顆
const grundy2 = computeGrundy(15, [1, 3, 4]);
console.log(grundy2);
// 輸出：[0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, 0, 1]
// 週期 7（從 index 1 開始）

// ─── 複合賽局：多個獨立遊戲的 XOR 合併 ─────────────────

function compositeGameResult(grundyValues: number[]): {
  canWin: boolean;
  totalGrundy: number;
} {
  const totalGrundy = grundyValues.reduce((acc, g) => acc ^ g, 0);
  return {
    canWin: totalGrundy !== 0,
    totalGrundy,
  };
}

// 範例：三場獨立的 Subtraction Game（每次取 1~2），堆大小分別為 4, 5, 7
const G = computeGrundy(10, [1, 2]);
const games = [G[4], G[5], G[7]]; // [1, 2, 1]
const result = compositeGameResult(games);
console.log(result);
// 輸出：{ canWin: true, totalGrundy: 2 }
// 解釋：1 XOR 2 XOR 1 = 2 ≠ 0 → 先手必勝

// ─── Wythoff 遊戲 ──────────────────────────────────────

// Wythoff 定理：(a, b) 為 P-position 若且唯若
// a = floor(k * φ), b = floor(k * φ²)（或反過來）
// 其中 φ = (1 + √5) / 2（黃金比例）

function isWythoffPPosition(a: number, b: number): boolean {
  // 確保 a <= b
  if (a > b) [a, b] = [b, a];

  const phi = (1 + Math.sqrt(5)) / 2;
  const k = b - a; // 差值
  const expectedA = Math.floor(k * phi);

  return a === expectedA;
}

// 必勝判定
function canWinWythoff(a: number, b: number): boolean {
  return !isWythoffPPosition(a, b);
}

// 測試：前幾組 P-position（冷局面）
// (0,0), (1,2), (3,5), (4,7), (6,10), (8,13), ...
console.log(isWythoffPPosition(0, 0));   // 輸出：true（P-position）
console.log(isWythoffPPosition(1, 2));   // 輸出：true
console.log(isWythoffPPosition(3, 5));   // 輸出：true
console.log(isWythoffPPosition(4, 7));   // 輸出：true
console.log(isWythoffPPosition(2, 3));   // 輸出：false（N-position）
console.log(canWinWythoff(2, 3));        // 輸出：true（先手必勝）

// ─── Green Hackenbush（簡化版：樹上的遊戲）───────────────
// 在樹上的 Green Hackenbush 中，每條從地面出發的鏈
// 的 Grundy 值等於其長度（邊數）

// 對於一般樹結構，使用 Colon Principle：
// 將每個節點的所有子樹的 Grundy 值 XOR 起來，
// 替換為一條等長的鏈

function hackenbushTreeGrundy(
  adj: number[][],     // 鄰接表
  root: number,        // 地面連接的根節點
): number {
  const visited = new Set<number>();

  function dfs(node: number): number {
    visited.add(node);
    let grundy = 0;
    for (const neighbor of adj[node]) {
      if (!visited.has(neighbor)) {
        // 子邊的 Grundy 值 = 子樹 Grundy 值 + 1（這條邊本身）
        grundy ^= (dfs(neighbor) + 1);
      }
    }
    return grundy;
  }

  return dfs(root);
}

// 測試：一棵簡單的樹
//     0（地面）
//    / \
//   1   2
//  /
// 3
const adj = [[1, 2], [0, 3], [0], [1]];
const g = hackenbushTreeGrundy(adj, 0);
console.log(g);
// 輸出：1
// 解釋：
//   節點 3 → G=0，邊 1-3 → G=0+1=1
//   節點 1 → 子樹 G=1，邊 0-1 → G=1+1=2
//   節點 2 → G=0，邊 0-2 → G=0+1=1
//   根節點 0 → G = 2 XOR 1 = 3... 等等，
//   但 root 是地面，所以 Grundy = 2 XOR 1 = 3?
//   不，Colon Principle 從葉子往上 XOR：
//   dfs(3)=0, dfs(1)=0^(0+1)=1, dfs(2)=0, dfs(0)=(1+1)^(0+1)=2^1=3
//   G = 3 ≠ 0 → 先手必勝
console.log(g !== 0 ? "先手必勝" : "先手必輸");
// 輸出：先手必勝

// ─── Minimax + Alpha-Beta 剪枝（Tic-Tac-Toe AI）────────

type Board = number[][]; // 0 = 空, 1 = X(MAX), -1 = O(MIN)

function checkWinner(board: Board): number {
  const lines = [
    [[0,0],[0,1],[0,2]], [[1,0],[1,1],[1,2]], [[2,0],[2,1],[2,2]], // 橫
    [[0,0],[1,0],[2,0]], [[0,1],[1,1],[2,1]], [[0,2],[1,2],[2,2]], // 縱
    [[0,0],[1,1],[2,2]], [[0,2],[1,1],[2,0]],                      // 斜
  ];
  for (const line of lines) {
    const sum = line.reduce((s, [r, c]) => s + board[r][c], 0);
    if (sum === 3) return 1;   // X 勝
    if (sum === -3) return -1; // O 勝
  }
  return 0; // 平局或未結束
}

function isFull(board: Board): boolean {
  return board.every(row => row.every(cell => cell !== 0));
}

// Alpha-Beta 剪枝的 Minimax
function minimax(
  board: Board,
  depth: number,
  isMaximizing: boolean,
  alpha: number,
  beta: number
): number {
  const winner = checkWinner(board);
  if (winner !== 0) return winner * (10 - depth); // 越快贏分數越高
  if (isFull(board)) return 0;                    // 平局

  if (isMaximizing) {
    let best = -Infinity;
    for (let r = 0; r < 3; r++) {
      for (let c = 0; c < 3; c++) {
        if (board[r][c] === 0) {
          board[r][c] = 1; // X 落子
          best = Math.max(best, minimax(board, depth + 1, false, alpha, beta));
          board[r][c] = 0; // 還原
          alpha = Math.max(alpha, best);
          if (beta <= alpha) return best; // Beta 剪枝
        }
      }
    }
    return best;
  } else {
    let best = Infinity;
    for (let r = 0; r < 3; r++) {
      for (let c = 0; c < 3; c++) {
        if (board[r][c] === 0) {
          board[r][c] = -1; // O 落子
          best = Math.min(best, minimax(board, depth + 1, true, alpha, beta));
          board[r][c] = 0;  // 還原
          beta = Math.min(beta, best);
          if (beta <= alpha) return best; // Alpha 剪枝
        }
      }
    }
    return best;
  }
}

// 找出 X（MAX 玩家）的最佳落子位置
function bestMove(board: Board): [number, number] {
  let bestScore = -Infinity;
  let move: [number, number] = [-1, -1];

  for (let r = 0; r < 3; r++) {
    for (let c = 0; c < 3; c++) {
      if (board[r][c] === 0) {
        board[r][c] = 1;
        const score = minimax(board, 0, false, -Infinity, Infinity);
        board[r][c] = 0;
        if (score > bestScore) {
          bestScore = score;
          move = [r, c];
        }
      }
    }
  }
  return move;
}

// 測試
const board: Board = [
  [ 0,  0, -1],
  [ 0,  1,  0],
  [ 0,  0,  0],
];
console.log("最佳落子：", bestMove(board));
// 輸出：最佳落子： [0, 0]（或其他最優位置）

#include <vector>
#include <iostream>
using namespace std;

// 單堆 Nim（每次取 1~3）
bool canWinNim(int n) {
    return n % 4 != 0;
}

// 多堆 Nim
bool canWinNimGeneral(vector<int>& piles) {
    int xorSum = 0;
    for (int p : piles) xorSum ^= p;
    return xorSum != 0;
}

// 必勝策略
pair<int, int> nimStrategy(vector<int>& piles) {
    // 回傳 {堆 index, 移除後的目標數量}，{-1, -1} 表示必輸
    int xorSum = 0;
    for (int p : piles) xorSum ^= p;
    if (xorSum == 0) return {-1, -1};

    for (int i = 0; i < (int)piles.size(); i++) {
        int target = piles[i] ^ xorSum;
        if (target < piles[i]) {
            return {i, target};
        }
    }
    return {-1, -1};
}

int main() {
    cout << canWinNim(4) << endl;  // 輸出：0（false）
    cout << canWinNim(7) << endl;  // 輸出：1（true）

    vector<int> piles = {3, 5, 7};
    cout << canWinNimGeneral(piles) << endl; // 輸出：1

    auto [idx, target] = nimStrategy(piles);
    cout << "堆 " << idx << " 改為 " << target << endl;
    // 輸出：堆 1 改為 4
    return 0;
}

#include <vector>
#include <set>
#include <iostream>
using namespace std;

vector<int> computeGrundy(int maxN, vector<int>& subtractSet) {
    vector<int> G(maxN + 1, 0);

    for (int n = 1; n <= maxN; n++) {
        set<int> reachable;
        for (int s : subtractSet) {
            if (n - s >= 0) reachable.insert(G[n - s]);
        }
        // 計算 mex
        int m = 0;
        while (reachable.count(m)) m++;
        G[n] = m;
    }
    return G;
}

bool compositeGame(vector<int>& grundyValues) {
    int xorSum = 0;
    for (int g : grundyValues) xorSum ^= g;
    return xorSum != 0;
}

int main() {
    vector<int> subtractSet = {1, 2};
    auto G = computeGrundy(9, subtractSet);
    for (int g : G) cout << g << " ";
    // 輸出：0 1 2 0 1 2 0 1 2 0
    cout << endl;

    vector<int> games = {G[4], G[5]}; // {1, 2}
    cout << compositeGame(games) << endl; // 輸出：1（先手必勝）
    return 0;
}

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

bool isWythoffPPosition(int a, int b) {
    if (a > b) swap(a, b);
    double phi = (1.0 + sqrt(5.0)) / 2.0;
    int k = b - a;
    int expectedA = (int)floor(k * phi);
    return a == expectedA;
}

bool canWinWythoff(int a, int b) {
    return !isWythoffPPosition(a, b);
}

int main() {
    // P-position 測試
    cout << isWythoffPPosition(0, 0) << endl;  // 輸出：1（true）
    cout << isWythoffPPosition(1, 2) << endl;  // 輸出：1
    cout << isWythoffPPosition(3, 5) << endl;  // 輸出：1
    cout << isWythoffPPosition(4, 7) << endl;  // 輸出：1
    // N-position 測試
    cout << canWinWythoff(2, 3) << endl;       // 輸出：1（先手必勝）
    return 0;
}

#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;

int checkWinner(vector<vector<int>>& board) {
    int lines[8][3][2] = {
        {{0,0},{0,1},{0,2}}, {{1,0},{1,1},{1,2}}, {{2,0},{2,1},{2,2}},
        {{0,0},{1,0},{2,0}}, {{0,1},{1,1},{2,1}}, {{0,2},{1,2},{2,2}},
        {{0,0},{1,1},{2,2}}, {{0,2},{1,1},{2,0}}
    };
    for (auto& line : lines) {
        int s = board[line[0][0]][line[0][1]]
              + board[line[1][0]][line[1][1]]
              + board[line[2][0]][line[2][1]];
        if (s == 3) return 1;
        if (s == -3) return -1;
    }
    return 0;
}

bool isFull(vector<vector<int>>& board) {
    for (auto& row : board)
        for (int cell : row)
            if (cell == 0) return false;
    return true;
}

int minimax(vector<vector<int>>& board, int depth,
            bool isMax, int alpha, int beta) {
    int w = checkWinner(board);
    if (w != 0) return w * (10 - depth);
    if (isFull(board)) return 0;

    if (isMax) {
        int best = INT_MIN;
        for (int r = 0; r < 3; r++)
            for (int c = 0; c < 3; c++)
                if (board[r][c] == 0) {
                    board[r][c] = 1;
                    best = max(best, minimax(board, depth + 1, false, alpha, beta));
                    board[r][c] = 0;
                    alpha = max(alpha, best);
                    if (beta <= alpha) return best; // Beta 剪枝
                }
        return best;
    } else {
        int best = INT_MAX;
        for (int r = 0; r < 3; r++)
            for (int c = 0; c < 3; c++)
                if (board[r][c] == 0) {
                    board[r][c] = -1;
                    best = min(best, minimax(board, depth + 1, true, alpha, beta));
                    board[r][c] = 0;
                    beta = min(beta, best);
                    if (beta <= alpha) return best; // Alpha 剪枝
                }
        return best;
    }
}

pair<int, int> bestMove(vector<vector<int>>& board) {
    int bestScore = INT_MIN;
    pair<int, int> move = {-1, -1};
    for (int r = 0; r < 3; r++)
        for (int c = 0; c < 3; c++)
            if (board[r][c] == 0) {
                board[r][c] = 1;
                int score = minimax(board, 0, false, INT_MIN, INT_MAX);
                board[r][c] = 0;
                if (score > bestScore) {
                    bestScore = score;
                    move = {r, c};
                }
            }
    return move;
}

// ─── Misere Nim ────────────────────────────────────────
// 規則：取走最後一顆石子的人「輸」

function canWinMisereNim(piles: number[]): boolean {
  const xor = piles.reduce((acc, p) => acc ^ p, 0);
  const allOnes = piles.every(p => p <= 1); // 所有堆大小都 ≤ 1

  if (allOnes) {
    // 特殊情況：所有堆都是 0 或 1
    // 奇數個 1 → 被迫取最後一顆 → 必輸
    // 偶數個 1 → 對手取最後一顆 → 必勝
    const count = piles.filter(p => p === 1).length;
    return count % 2 === 0;
  }

  // 一般情況：與標準 Nim 相同！XOR ≠ 0 先手必勝
  return xor !== 0;
}

// 測試
console.log(canWinMisereNim([1, 1, 1])); // 輸出：false（3 個 1，被迫取最後一顆）
console.log(canWinMisereNim([1, 1]));    // 輸出：true（2 個 1，對手取最後一顆）
console.log(canWinMisereNim([2, 3]));    // 輸出：true（XOR = 1 ≠ 0）
console.log(canWinMisereNim([1, 2, 3])); // 輸出：false（XOR = 0）

// ─── 圖上的博弈：DAG 上的 Grundy 值 ────────────────────

function graphGameGrundy(
  adj: number[][],  // 鄰接表（有向圖）
  n: number         // 節點數（0 ~ n-1）
): number[] {
  // 拓撲排序 + 反向計算 Grundy 值
  const grundy = new Array(n).fill(-1);

  // 找出所有出度為 0 的節點（終局狀態）
  const outDegree = new Array(n).fill(0);
  for (let u = 0; u < n; u++) {
    outDegree[u] = adj[u].length;
  }

  // DFS + 記憶化計算 Grundy 值
  function dfs(u: number): number {
    if (grundy[u] !== -1) return grundy[u];
    if (adj[u].length === 0) {
      return grundy[u] = 0; // 終局，G = 0
    }

    const reachable = new Set<number>();
    for (const v of adj[u]) {
      reachable.add(dfs(v));
    }
    let m = 0;
    while (reachable.has(m)) m++;
    return grundy[u] = m;
  }

  for (let u = 0; u < n; u++) {
    if (grundy[u] === -1) dfs(u);
  }
  return grundy;
}

// 測試：一個簡單的 DAG
// 0 → 1 → 3
// 0 → 2 → 3
// 節點 3 是終局（出度 0）
const dagAdj = [[1, 2], [3], [3], []];
const dagGrundy = graphGameGrundy(dagAdj, 4);
console.log(dagGrundy);
// 輸出：[2, 1, 1, 0]
// 節點 0 的 Grundy 值 = 2 ≠ 0 → 從節點 0 出發先手必勝

// 單堆取 1~3，先取完者勝
function canWinNim(n: number): boolean {
  return n % 4 !== 0;
}

// 1~3：直接取完 → 必勝
// 4：取 k，對手取 4-k → 必輸
// 歸納：n % 4 === 0 → 必輸，否則必勝

function canIWin(maxChoosableInt: number, desiredTotal: number): boolean {
  // 邊界：所有數字總和不夠
  const totalSum = (maxChoosableInt * (maxChoosableInt + 1)) / 2;
  if (totalSum < desiredTotal) return false;
  if (desiredTotal <= 0) return true;

  const memo = new Map<number, boolean>();

  function dp(usedMask: number, currentTotal: number): boolean {
    if (memo.has(usedMask)) return memo.get(usedMask)!;

    for (let i = 1; i <= maxChoosableInt; i++) {
      const bit = 1 << (i - 1);
      if (usedMask & bit) continue; // 已使用

      // 取 i 後直接達標，或對手處於必輸狀態
      if (currentTotal + i >= desiredTotal ||
          !dp(usedMask | bit, currentTotal + i)) {
        memo.set(usedMask, true);
        return true;
      }
    }

    memo.set(usedMask, false);
    return false;
  }

  return dp(0, 0);
}

// 測試
console.log(canIWin(10, 11)); // 輸出：false
console.log(canIWin(10, 0));  // 輸出：true

// 解法一：數學觀察 — O(1)
// 堆數為偶數，先手可以選擇全取奇數位或全取偶數位
// 兩組和不同，先手永遠能選較大組 → 必勝
function stoneGame(piles: number[]): boolean {
  return true;
}

// 解法二：區間 DP — 通用解（適用於無此數學結論的變體）
function stoneGameDP(piles: number[]): boolean {
  const n = piles.length;
  // dp[i][j]：先手在 piles[i..j] 能比後手多得的石子數
  const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let i = 0; i < n; i++) dp[i][i] = piles[i];

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(
        piles[i] - dp[i + 1][j],  // 取左端
        piles[j] - dp[i][j - 1]   // 取右端
      );
    }
  }

  return dp[0][n - 1] > 0;
}

// 測試
console.log(stoneGameDP([5, 3, 4, 5])); // 輸出：true
console.log(stoneGameDP([3, 7, 2, 3])); // 輸出：true

function predictTheWinner(nums: number[]): boolean {
  const n = nums.length;
  const dp: number[][] = Array.from({ length: n }, (_, i) => {
    const row = new Array(n).fill(0);
    row[i] = nums[i]; // 初始化對角線
    return row;
  });

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(
        nums[i] - dp[i + 1][j],
        nums[j] - dp[i][j - 1]
      );
    }
  }

  return dp[0][n - 1] >= 0; // >= 0 包含平局（題目定義先手平局算贏）
}

// 測試
console.log(predictTheWinner([1, 5, 2]));    // 輸出：false
console.log(predictTheWinner([1, 5, 233, 7])); // 輸出：true

function divisorGame(n: number): boolean {
  // 觀察：n 為偶數 → 先手必勝，n 為奇數 → 先手必輸
  // 原因：偶數時先手取 1（1 必整除任何數），留奇數給對手
  //       奇數的因子都是奇數，奇數 - 奇數 = 偶數，又留偶數給先手
  //       最終 n = 1 時無法行動 → 此時輪到的人必輸
  return n % 2 === 0;
}

// 驗證型 DP 解法
function divisorGameDP(n: number): boolean {
  const dp = new Array(n + 1).fill(false);
  // dp[0] = false, dp[1] = false（無法行動）

  for (let i = 2; i <= n; i++) {
    for (let x = 1; x < i; x++) {
      if (i % x === 0 && !dp[i - x]) {
        dp[i] = true; // 存在一步使對手必輸
        break;
      }
    }
  }
  return dp[n];
}

// 測試
console.log(divisorGame(2));  // 輸出：true（取 1，留 1 給對手）
console.log(divisorGame(3));  // 輸出：false（只能取 1，留 2 給對手）
console.log(divisorGame(4));  // 輸出：true