POJ 1085 Triangle War：狀壓 DP + 記憶化搜索解決三角棋博弈

遊戲規則

三角網格 10 個點，9 個小三角形。雙方輪流畫邊，畫完某三角形第 3 條邊者佔有該三角形並獲得額外一步。給定已畫邊序列，雙方最優策略下誰贏？

狀態壓縮表示

• 18 條邊 → 18 位二進制數 state，1 表示已畫
• 9 個三角形預存三條邊的索引 tri[9][3]
• 分數差 score：先手佔有三角形數 - 後手佔有數

記憶化搜索遞歸

dfs(state, score) 返回當前玩家在狀態 state 下，分數差為 score 時的最優分數差（當前玩家視角）。

• 遍歷所有未畫邊 e
• 計算畫 e 後新增三角形數 gain
• 若 gain > 0：獲得額外回合，遞歸 dfs(newState, score + gain)，結果為 gain + 子結果
• 若 gain == 0：換對手，遞歸 dfs(newState, score)，結果為 -子結果（零和博弈）
• 取所有合法動作的最大值

核心代碼

int dp[1<<18], tri[9][3] = {...}; // 預存三角形邊索引

int dfs(int state, int score) {
    if (dp[state] != -1) return dp[state];
    int best = -INF;
    for (int e = 0; e < 18; ++e) if (!(state & (1<<e))) {
        int nstate = state | (1<<e);
        int gain = 0;
        for (int t = 0; t < 9; ++t) {
            int cnt = 0;
            for (int k = 0; k < 3; ++k) if (nstate & (1<<tri[t][k])) ++cnt;
            if (cnt == 3 && !(state & (1<<tri[t][0])) // 剛好這步完成
                && !(state & (1<<tri[t][1]))
                && !(state & (1<<tri[t][2]))) ++gain;
        }
        int val = (gain > 0) ? gain + dfs(nstate, score + gain)
                             : -dfs(nstate, score);
        best = max(best, val);
    }
    return dp[state] = best;
}

初始化與輸出

讀入已畫邊構造初始 state，計算初始 score（模擬已走步驟）。調用 dfs(state, score)，返回值 > 0 先手贏，< 0 後手贏。

複雜度與優化

• 狀態數 2¹⁸ = 262144，每狀態遍歷 ≤18 條邊，總操作 ~4.7e6，極快
• 用 dp[state] 記憶化，避免重複計算
• 預計算每條邊能完成的三角形掩碼，可進一步優化 gain 計算

關鍵細節

1. 額外回合處理：完成三角形不換手，分數直接累加
2. 零和博弈：對手視角分數取反，max 對應極大化己方優勢
3. 邊索引映射：需建立 (點對) → 邊編號 的映射表 mp[i][j]