每日算法 — 使用java实现囚徒困境：重复博弈演化稳定策略与Tit-for-Tat分析

游戏简介与算法核心

囚徒困境是博弈论中最经典的模型之一。两名嫌疑人被分别审讯，各自面临”合作”（保持沉默）或”背叛”（揭发对方）的选择。单次博弈中，背叛是纳什均衡；但在重复博弈中，合作可能通过策略互动而涌现。本文用Java实现重复囚徒困境的演化模拟，讲解收益矩阵计算、策略对抗评估与复制动态过程。

收益矩阵与博弈规则

经典囚徒困境的收益结构（T > R > P > S）：

其中：T（诱惑）= 5，R（奖励）= 3，P（惩罚）= 1，S（ sucker）= 0。满足 T > R > P > S 且 2R > T + S。

import java.util.*;

/**
 * 行动枚举
 */
enum Action {
    COOPERATE('C'), DEFECT('D');

    private final char symbol;
    Action(char symbol) { this.symbol = symbol; }
    public char getSymbol() { return symbol; }
}

/**
 * 回合结果记录
 */
class RoundResult {
    final Action actionA;
    final Action actionB;
    final int payoffA;
    final int payoffB;

    RoundResult(Action actionA, Action actionB, int payoffA, int payoffB) {
        this.actionA = actionA;
        this.actionB = actionB;
        this.payoffA = payoffA;
        this.payoffB = payoffB;
    }

    @Override
    public String toString() {
        return String.format("A:%s(%d) vs B:%s(%d)", 
            actionA.getSymbol(), payoffA, actionB.getSymbol(), payoffB);
    }
}

/**
 * 收益矩阵
 */
class PayoffMatrix {
    private static final int T = 5; // Temptation
    private static final int R = 3; // Reward
    private static final int P = 1; // Punishment
    private static final int S = 0; // Sucker

    /**
     * 获取收益 (player1, player2)
     */
    public static int[] getPayoffs(Action a1, Action a2) {
        if (a1 == Action.COOPERATE && a2 == Action.COOPERATE) return new int[]{R, R};
        if (a1 == Action.COOPERATE && a2 == Action.DEFECT) return new int[]{S, T};
        if (a1 == Action.DEFECT && a2 == Action.COOPERATE) return new int[]{T, S};
        return new int[]{P, P}; // both defect
    }

    public static int getT() { return T; }
    public static int getR() { return R; }
    public static int getP() { return P; }
    public static int getS() { return S; }
}

策略接口与经典策略实现

/**
 * 策略接口：每轮根据历史记录决定行动
 */
interface Strategy {
    String getName();
    Action chooseAction(List<RoundResult> history, boolean isPlayerA);
    Strategy cloneStrategy();
}

/**
 * 始终合作策略
 */
class AlwaysCooperate implements Strategy {
    public String getName() { return "AlwaysCooperate"; }
    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        return Action.COOPERATE;
    }
    public Strategy cloneStrategy() { return new AlwaysCooperate(); }
}

/**
 * 始终背叛策略
 */
class AlwaysDefect implements Strategy {
    public String getName() { return "AlwaysDefect"; }
    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        return Action.DEFECT;
    }
    public Strategy cloneStrategy() { return new AlwaysDefect(); }
}

/**
 * 随机策略
 */
class RandomStrategy implements Strategy {
    private final Random random = new Random();
    private final double cooperateProb;

    public RandomStrategy(double cooperateProb) {
        this.cooperateProb = cooperateProb;
    }

    public String getName() { 
        return "Random(" + cooperateProb + ")"; 
    }

    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        return random.nextDouble() < cooperateProb ? Action.COOPERATE : Action.DEFECT;
    }

    public Strategy cloneStrategy() { 
        return new RandomStrategy(cooperateProb); 
    }
}

/**
 * Tit-for-Tat策略：第一轮合作，之后模仿对方上一步行动
 * 这是Robert Axelrod tournament的冠军策略
 */
class TitForTat implements Strategy {
    public String getName() { return "TitForTat"; }

    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        if (history.isEmpty()) return Action.COOPERATE;

        // 模仿对方上一步的行动
        RoundResult last = history.get(history.size() - 1);
        Action opponentLastAction = isPlayerA ? last.actionB : last.actionA;
        return opponentLastAction;
    }

    public Strategy cloneStrategy() { return new TitForTat(); }
}

/**
 * Tit-for-Two-Tats：更宽容的版本，只有对方连续背叛两次才报复
 */
class TitForTwoTats implements Strategy {
    public String getName() { return "TitForTwoTats"; }

    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        if (history.size() < 2) return Action.COOPERATE;

        RoundResult last1 = history.get(history.size() - 1);
        RoundResult last2 = history.get(history.size() - 2);

        Action opp1 = isPlayerA ? last1.actionB : last1.actionA;
        Action opp2 = isPlayerA ? last2.actionB : last2.actionA;

        if (opp1 == Action.DEFECT && opp2 == Action.DEFECT) {
            return Action.DEFECT;
        }
        return Action.COOPERATE;
    }

    public Strategy cloneStrategy() { return new TitForTwoTats(); }
}

/**
 * Grudger（记仇者）：一直合作直到对方背叛，之后永远背叛
 */
class Grudger implements Strategy {
    private boolean grudge = false;

    public String getName() { return "Grudger"; }

    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        if (!history.isEmpty()) {
            RoundResult last = history.get(history.size() - 1);
            Action opponentLast = isPlayerA ? last.actionB : last.actionA;
            if (opponentLast == Action.DEFECT) grudge = true;
        }
        return grudge ? Action.DEFECT : Action.COOPERATE;
    }

    public Strategy cloneStrategy() { return new Grudger(); }
}

/**
 * Pavlov（胜留败走）：如果上一轮收益高则重复行动，否则改变行动
 */
class Pavlov implements Strategy {
    public String getName() { return "Pavlov"; }

    public Action chooseAction(List<RoundResult> history, boolean isPlayerA) {
        if (history.isEmpty()) return Action.COOPERATE;

        RoundResult last = history.get(history.size() - 1);
        int myPayoff = isPlayerA ? last.payoffA : last.payoffB;
        Action myLastAction = isPlayerA ? last.actionA : last.actionB;

        // R=3, T=5 是高收益；P=1, S=0 是低收益
        boolean highPayoff = (myPayoff == PayoffMatrix.getR() || 
                              myPayoff == PayoffMatrix.getT());

        return highPayoff ? myLastAction : 
            (myLastAction == Action.COOPERATE ? Action.DEFECT : Action.COOPERATE);
    }

    public Strategy cloneStrategy() { return new Pavlov(); }
}

重复博弈对战引擎

/**
 * 重复博弈引擎
 */
class RepeatedGame {

    /**
     * 执行一轮单次囚徒困境
     */
    public RoundResult playRound(Strategy s1, Strategy s2, 
                                  List<RoundResult> history1, 
                                  List<RoundResult> history2) {
        Action a1 = s1.chooseAction(history1, true);
        Action a2 = s2.chooseAction(history2, false);
        int[] payoffs = PayoffMatrix.getPayoffs(a1, a2);
        return new RoundResult(a1, a2, payoffs[0], payoffs[1]);
    }

    /**
     * 执行多轮重复博弈，返回双方总收益
     */
    public int[] playRepeatedGame(Strategy s1, Strategy s2, int rounds) {
        List<RoundResult> history1 = new ArrayList<>();
        List<RoundResult> history2 = new ArrayList<>();
        int total1 = 0, total2 = 0;

        for (int i = 0; i < rounds; i++) {
            RoundResult result = playRound(s1, s2, history1, history2);
            history1.add(result);
            history2.add(result);
            total1 += result.payoffA;
            total2 += result.payoffB;
        }

        return new int[]{total1, total2};
    }

    /**
     * 执行带有终止概率的重复博弈（模拟无限重复）
     */
    public int[] playIteratedGame(Strategy s1, Strategy s2, double continuationProb) {
        List<RoundResult> history1 = new ArrayList<>();
        List<RoundResult> history2 = new ArrayList<>();
        int total1 = 0, total2 = 0;
        Random random = new Random();

        while (random.nextDouble() < continuationProb) {
            RoundResult result = playRound(s1, s2, history1, history2);
            history1.add(result);
            history2.add(result);
            total1 += result.payoffA;
            total2 += result.payoffB;
        }

        return new int[]{total1, total2};
    }
}

演化博弈与复制动态

/**
 * 策略种群中的个体
 */
class Agent {
    Strategy strategy;
    int score;
    int population;

    Agent(Strategy strategy, int population) {
        this.strategy = strategy;
        this.population = population;
        this.score = 0;
    }
}

/**
 * 演化模拟器：模拟策略种群的竞争与演化
 */
class EvolutionSimulator {
    private final List<Agent> population = new ArrayList<>();
    private final RepeatedGame game = new RepeatedGame();
    private final int roundsPerEncounter;

    public EvolutionSimulator(int roundsPerEncounter) {
        this.roundsPerEncounter = roundsPerEncounter;
    }

    public void addStrategy(Strategy strategy, int initialPop) {
        population.add(new Agent(strategy, initialPop));
    }

    /**
     * 执行一代演化：所有个体两两对战，计算适应度，然后按适应度比例复制
     */
    public void evolveGeneration() {
        int totalPop = population.stream().mapToInt(a -> a.population).sum();

        // 计算每个策略的平均得分
        for (Agent agent : population) {
            agent.score = 0;
        }

        for (int i = 0; i < population.size(); i++) {
            for (int j = 0; j < population.size(); j++) {
                Agent a1 = population.get(i);
                Agent a2 = population.get(j);

                // 克隆策略以保持状态独立
                Strategy s1 = a1.strategy.cloneStrategy();
                Strategy s2 = a2.strategy.cloneStrategy();

                int[] result = game.playRepeatedGame(s1, s2, roundsPerEncounter);

                // 加权平均（考虑种群比例）
                a1.score += result[0] * a2.population;
            }
            // 归一化
            if (totalPop > 0) {
                agent.score /= totalPop;
            }
        }

        // 复制动态：按相对适应度更新种群比例
        int avgScore = population.stream().mapToInt(a -> a.score).sum() / population.size();

        for (Agent agent : population) {
            if (avgScore > 0) {
                double fitness = (double) agent.score / avgScore;
                agent.population = (int) (agent.population * fitness);
                agent.population = Math.max(1, agent.population); // 保证不灭绝
            }
        }
    }

    /**
     * 运行多代演化
     */
    public void runSimulation(int generations) {
        System.out.println("=== 囚徒困境演化模拟 ===");
        System.out.println("每代对战轮数: " + roundsPerEncounter);
        System.out.println();

        // 打印初始状态
        printPopulation(0);

        for (int gen = 1; gen <= generations; gen++) {
            evolveGeneration();
            if (gen % 10 == 0 || gen == 1) {
                printPopulation(gen);
            }
        }
    }

    private void printPopulation(int generation) {
        System.out.println("第 " + generation + " 代:");
        int total = population.stream().mapToInt(a -> a.population).sum();
        for (Agent agent : population) {
            double pct = total > 0 ? (double) agent.population / total * 100 : 0;
            System.out.printf("  %-20s: %4d (%.1f%%)  平均得分: %d%n",
                agent.strategy.getName(), agent.population, pct, agent.score);
        }
        System.out.println();
    }

    public List<Agent> getPopulation() { return population; }
}

策略锦标赛与评估

/**
 * 策略锦标赛：Round-Robin循环赛
 */
class Tournament {
    private final RepeatedGame game = new RepeatedGame();
    private final int rounds;

    public Tournament(int rounds) {
        this.rounds = rounds;
    }

    /**
     * 运行循环赛并打印结果矩阵
     */
    public void runRoundRobin(List<Strategy> strategies) {
        int n = strategies.size();
        int[][] scores = new int[n][n];

        System.out.println("=== 策略循环赛结果 ===");
        System.out.println("每轮对战 " + rounds + " 回合\n");

        // 表头
        System.out.printf("%-20s", "策略");
        for (int i = 0; i < n; i++) {
            System.out.printf("%12s", strategies.get(i).getName().substring(0, 
                Math.min(12, strategies.get(i).getName().length())));
        }
        System.out.printf("%12s%n", "总分");

        for (int i = 0; i < n; i++) {
            System.out.printf("%-20s", strategies.get(i).getName());
            int total = 0;
            for (int j = 0; j < n; j++) {
                Strategy s1 = strategies.get(i).cloneStrategy();
                Strategy s2 = strategies.get(j).cloneStrategy();
                int[] result = game.playRepeatedGame(s1, s2, rounds);
                scores[i][j] = result[0];
                total += result[0];
                System.out.printf("%12d", result[0]);
            }
            System.out.printf("%12d%n", total);
        }

        // 打印排名
        System.out.println("\n=== 排名 ===");
        List<int[]> rankings = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int total = 0;
            for (int j = 0; j < n; j++) total += scores[i][j];
            rankings.add(new int[]{i, total});
        }
        rankings.sort((a, b) -> b[1] - a[1]);

        for (int rank = 0; rank < rankings.size(); rank++) {
            int idx = rankings.get(rank)[0];
            int score = rankings.get(rank)[1];
            System.out.printf("%d. %-20s 总分: %d%n", 
                rank + 1, strategies.get(idx).getName(), score);
        }
    }
}

主程序与演示

public class PrisonersDilemmaMain {
    public static void main(String[] args) {
        // 1. 演示单次博弈
        System.out.println("=== 单次囚徒困境 ===");
        RepeatedGame game = new RepeatedGame();
        Strategy cooperate = new AlwaysCooperate();
        Strategy defect = new AlwaysDefect();

        int[] singleResult = game.playRepeatedGame(cooperate, defect, 1);
        System.out.println("AlwaysCooperate vs AlwaysDefect: " + 
            singleResult[0] + " vs " + singleResult[1]);
        System.out.println("纳什均衡: 双方都选择背叛，各得 " + PayoffMatrix.getP() + "\n");

        // 2. 演示重复博弈中Tit-for-Tat的优势
        System.out.println("=== 重复博弈 (100轮) ===");
        Strategy tft = new TitForTat();
        int[] repeatResult = game.playRepeatedGame(tft, cooperate, 100);
        System.out.println("TitForTat vs AlwaysCooperate: " + 
            repeatResult[0] + " vs " + repeatResult[1]);

        int[] repeatResult2 = game.playRepeatedGame(tft, defect, 100);
        System.out.println("TitForTat vs AlwaysDefect: " + 
            repeatResult2[0] + " vs " + repeatResult2[1]);

        int[] repeatResult3 = game.playRepeatedGame(tft, tft, 100);
        System.out.println("TitForTat vs TitForTat: " + 
            repeatResult3[0] + " vs " + repeatResult3[1] + "\n");

        // 3. 策略锦标赛
        System.out.println("=== 策略锦标赛 ===");
        List<Strategy> strategies = Arrays.asList(
            new AlwaysCooperate(),
            new AlwaysDefect(),
            new TitForTat(),
            new TitForTwoTats(),
            new Grudger(),
            new Pavlov(),
            new RandomStrategy(0.5)
        );

        Tournament tournament = new Tournament(200);
        tournament.runRoundRobin(strategies);

        // 4. 演化模拟
        System.out.println("\n=== 演化博弈模拟 ===");
        EvolutionSimulator simulator = new EvolutionSimulator(100);
        simulator.addStrategy(new AlwaysCooperate(), 20);
        simulator.addStrategy(new AlwaysDefect(), 20);
        simulator.addStrategy(new TitForTat(), 20);
        simulator.addStrategy(new Grudger(), 20);
        simulator.addStrategy(new Pavlov(), 20);
        simulator.runSimulation(50);
    }
}

算法复杂度分析

其中K=策略种类数，N=每轮对战的回合数，P=种群规模。

总结

本文实现了重复囚徒困境的完整模拟框架，核心算法包括：

1. 收益矩阵：形式化囚徒困境的收益结构，R > P > S 且 T > R 的条件确保单次博弈中背叛是均衡
2. 策略设计：实现了AlwaysCooperate、AlwaysDefect、Tit-for-Tat、Grudger、Pavlov等经典策略
3. 重复博弈：通过多轮交互历史让策略可以”学习”和”报复”，合作在重复博弈中成为可能
4. 复制动态：模拟自然选择过程，适应度高的策略种群比例增加，观察合作策略是否能演化稳定

Tit-for-Tat策略的成功揭示了合作的演化条件：善良（不首先背叛）、报复（对背叛予以回击）、宽容（背叛后愿意恢复合作）、清晰（策略简单易懂）。这四个特性使其在Axelrod的计算机锦标赛中两次夺冠。