每日算法 — 使用java实现真心话大冒险：轮盘选择算法与概率决策

引言

真心话大冒险是聚会中经典的社交游戏，参与者通过旋转 bottle 或抽取卡片决定由谁来回答问题或接受挑战。本文将用 Java 实现一个智能化的真心话大冒险系统，核心讲解轮盘选择算法（Roulette Wheel Selection）与概率决策模型，让读者在熟悉的游戏场景中理解遗传算法中的经典选择策略与概率编程思想。

核心算法思路

轮盘选择算法

轮盘选择是遗传算法中的经典操作，其核心思想是：
– 为每个选项分配一个概率权重
– 计算累积概率分布
– 生成随机数，根据累积概率选择对应选项

时间复杂度：O(n) 基础版本，可优化至 O(log n) 使用二分查找。

加权随机抽样

对于真心话与大冒险两种题目类型，我们可以：
– 根据玩家历史选择动态调整权重
– 使用指数加权移动平均（EWMA）追踪偏好
– 实现自适应难度调整

完整 Java 实现

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 真心话大冒险智能决策系统
 * 核心算法：轮盘选择 + 加权随机抽样 + 自适应概率调整
 */
public class TruthOrDareGame {

    // 题目类型枚举
    enum QuestionType { TRUTH, DARE }

    // 题目实体类
    static class Question {
        String content;
        QuestionType type;
        int difficulty;      // 难度 1-10
        double weight;       // 当前权重
        int selectedCount;   // 被选中次数

        Question(String content, QuestionType type, int difficulty) {
            this.content = content;
            this.type = type;
            this.difficulty = difficulty;
            this.weight = 1.0;
            this.selectedCount = 0;
        }
    }

    // 玩家状态
    static class Player {
        String name;
        int truthCount;
        int dareCount;
        double preference;   // 偏好值：>0 偏向 truth, <0 偏向 dare

        Player(String name) {
            this.name = name;
        }
    }

    private final List<Question> truths = new ArrayList<>();
    private final List<Question> dares = new ArrayList<>();
    private final List<Player> players = new ArrayList<>();
    private final Random random = ThreadLocalRandom.current();

    // 初始化题库
    public void initQuestions() {
        truths.add(new Question("你最尴尬的一次经历是什么？", QuestionType.TRUTH, 3));
        truths.add(new Question("如果有时光机，你最想回到哪个时刻？", QuestionType.TRUTH, 4));
        truths.add(new Question("你偷偷做过但没人知道的事？", QuestionType.TRUTH, 6));
        truths.add(new Question("你最害怕失去什么？", QuestionType.TRUTH, 5));
        truths.add(new Question("如果可以匿名发一条消息给任何人，你会发给谁说什么？", QuestionType.TRUTH, 7));

        dares.add(new Question("模仿一种动物叫声持续10秒", QuestionType.DARE, 2));
        dares.add(new Question("用屁股写自己的名字", QuestionType.DARE, 4));
        dares.add(new Question("给通讯录第5个人发一条搞笑消息", QuestionType.DARE, 6));
        dares.add(new Question("单脚站立唱一首歌", QuestionType.DARE, 5));
        dares.add(new Question("做一个最丑的鬼脸保持5秒", QuestionType.DARE, 3));
    }

    /**
     * 轮盘选择算法核心实现
     * 根据权重数组选择索引，权重越高被选概率越大
     */
    public int rouletteWheelSelection(double[] weights) {
        double totalWeight = 0.0;
        for (double w : weights) {
            totalWeight += w;
        }

        // 生成 [0, totalWeight) 的随机数
        double rand = random.nextDouble() * totalWeight;
        double cumulative = 0.0;

        for (int i = 0; i < weights.length; i++) {
            cumulative += weights[i];
            if (rand < cumulative) {
                return i;
            }
        }
        return weights.length - 1; // 兜底
    }

    /**
     * 使用二分查找优化轮盘选择，O(log n)
     */
    public int rouletteWheelSelectionBinary(double[] weights) {
        double totalWeight = 0.0;
        double[] prefixSum = new double[weights.length];
        for (int i = 0; i < weights.length; i++) {
            totalWeight += weights[i];
            prefixSum[i] = totalWeight;
        }

        double rand = random.nextDouble() * totalWeight;
        // 二分查找第一个 >= rand 的累积概率
        int left = 0, right = prefixSum.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (prefixSum[mid] < rand) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 自适应权重更新
     * 使用指数加权移动平均，让热门题目逐渐降温
     */
    public void updateWeight(Question q, double alpha) {
        q.selectedCount++;
        // 选中后权重衰减，避免重复选中同一题
        q.weight *= (1 - alpha);
        // 但保留基础权重，确保长期仍有机会被选中
        q.weight = Math.max(q.weight, 0.1);
    }

    /**
     * 根据玩家偏好选择 truth 或 dare
     */
    public QuestionType selectType(Player player) {
        double truthBias = 0.5 + player.preference * 0.3; // 基础50% + 偏好调整
        truthBias = Math.max(0.2, Math.min(0.8, truthBias)); // 限制在20%-80%
        return random.nextDouble() < truthBias ? QuestionType.TRUTH : QuestionType.DARE;
    }

    /**
     * 从指定类型题库中轮盘选择一题
     */
    public Question selectQuestion(List<Question> pool) {
        double[] weights = new double[pool.size()];
        for (int i = 0; i < pool.size(); i++) {
            // 权重 = 基础权重 / (选中次数 + 1)，实现轮询效果
            weights[i] = pool.get(i).weight / (pool.get(i).selectedCount + 1.0);
        }
        int idx = rouletteWheelSelection(weights);
        return pool.get(idx);
    }

    /**
     * 选择本轮受罚玩家
     * 使用轮盘选择，近期未被选中的玩家权重更高
     */
    public Player selectPlayer() {
        double[] weights = new double[players.size()];
        for (int i = 0; i < players.size(); i++) {
            // 假设有记录每位玩家上次被选中轮次，此处简化为随机
            weights[i] = 1.0;
        }
        int idx = rouletteWheelSelection(weights);
        return players.get(idx);
    }

    /**
     * 主游戏循环
     */
    public void playRound() {
        if (players.isEmpty()) {
            System.out.println("请先添加玩家！");
            return;
        }

        Player victim = selectPlayer();
        QuestionType type = selectType(victim);
        List<Question> pool = type == QuestionType.TRUTH ? truths : dares;
        Question q = selectQuestion(pool);

        updateWeight(q, 0.3);
        if (type == QuestionType.TRUTH) {
            victim.truthCount++;
            victim.preference -= 0.05; // 选过truth后更倾向dare
        } else {
            victim.dareCount++;
            victim.preference += 0.05;
        }

        System.out.printf("【%s】选中玩家: %s | 类型: %s | 难度: %d%n",
                type == QuestionType.TRUTH ? "真心话" : "大冒险",
                victim.name, type, q.difficulty);
        System.out.println("题目: " + q.content);
        System.out.println("---");
    }

    public void addPlayer(String name) {
        players.add(new Player(name));
    }

    public static void main(String[] args) {
        TruthOrDareGame game = new TruthOrDareGame();
        game.initQuestions();
        game.addPlayer("Alice");
        game.addPlayer("Bob");
        game.addPlayer("Charlie");

        System.out.println("=== 真心话大冒险开始 ===");
        for (int i = 0; i < 10; i++) {
            game.playRound();
        }
    }
}

算法复杂度分析

扩展思考

1. 带约束的轮盘选择：如果某些题目不能连续出现，可引入禁忌搜索（Tabu Search）机制，将近期选中的题目加入禁忌表。
2. 多目标优化：同时考虑难度、趣味性、玩家偏好，可使用NSGA-II多目标遗传算法进行题目组合优化。
3. 冷启动问题：新题目初始权重低，可用汤普森采样（Thompson Sampling）平衡探索与利用。

总结

本文通过真心话大冒险游戏，实现了轮盘选择算法、加权随机抽样与自适应权重更新。这些技术广泛应用于遗传算法、推荐系统、AB测试等领域。掌握轮盘选择的本质——按概率比例分配选择机会——是理解概率算法的重要一步。