每日算法 — 使用java实现抽鬼牌：记忆策略与概率推理决策

一、游戏背景与规则

抽鬼牌（Old Maid）是一款经典的卡牌游戏，玩家通过记忆已出牌和推理对手手牌来避免抽到鬼牌。游戏使用一副扑克牌，去掉一张王后（Queen），剩下53张牌，其中一张王后成为”鬼牌”。玩家轮流从对方手牌中抽取一张牌，如果抽到的牌与自己手中某张牌配对（同点数），则将配对的牌打出。最终手中剩下鬼牌的玩家输。

本文将用Java实现一个带AI对手的抽鬼牌游戏，重点讲解AI如何通过记忆追踪、概率估算和最优抽牌决策来提升胜率。

二、核心算法设计

2.1 游戏状态建模

游戏的核心状态包括：
– 玩家手牌：每个玩家持有的卡牌集合
– 已打出的牌堆：所有已配对打出的牌
– 当前回合：轮到哪位玩家抽牌
– 记忆矩阵：AI记录的对手手牌概率分布

2.2 记忆追踪策略

AI需要追踪以下信息：
1. 自己手中的牌（已知）
2. 已经打出的配对牌（已知）
3. 对手曾经拥有过的牌（通过抽牌历史推断）
4. 对手当前手牌数量（已知）

2.3 概率推理决策

AI在抽牌时，需要计算对手每张牌是鬼牌的概率：
– 如果某张牌已经被看到配对打出，则概率为0
– 如果自己手中有相同点数的牌，则对手手中该牌不可能是鬼牌（因为鬼牌只有一张王后）
– 剩余未知牌中，鬼牌均匀分布

最优策略：选择鬼牌概率最低的位置抽牌。

三、完整Java实现

import java.util.*;

/**
 * 抽鬼牌游戏 - 带AI对手的完整实现
 * 包含记忆策略与概率推理决策
 */
public class OldMaidGame {

    // 卡牌类：点数 + 花色
    static class Card {
        int rank;   // 1-13 (A-K)
        String suit; // 花色
        boolean isGhost; // 是否是鬼牌

        public Card(int rank, String suit, boolean isGhost) {
            this.rank = rank;
            this.suit = suit;
            this.isGhost = isGhost;
        }

        @Override
        public String toString() {
            String rankStr;
            switch (rank) {
                case 1: rankStr = "A"; break;
                case 11: rankStr = "J"; break;
                case 12: rankStr = "Q"; break;
                case 13: rankStr = "K"; break;
                default: rankStr = String.valueOf(rank);
            }
            return isGhost ? "👻鬼牌(Q)" : rankStr + suit;
        }
    }

    // 玩家类
    static class Player {
        String name;
        List<Card> hand;
        boolean isAI;

        public Player(String name, boolean isAI) {
            this.name = name;
            this.hand = new ArrayList<>();
            this.isAI = isAI;
        }

        // 添加牌到手牌
        public void addCard(Card card) {
            hand.add(card);
        }

        // 移除指定位置的牌
        public Card removeCard(int index) {
            return hand.remove(index);
        }

        // 自动配对并打出
        public List<Card> autoMatch() {
            List<Card> matched = new ArrayList<>();
            Map<Integer, List<Integer>> rankMap = new HashMap<>();

            // 按点数分组
            for (int i = 0; i < hand.size(); i++) {
                Card c = hand.get(i);
                if (c.isGhost) continue; // 鬼牌不参与配对
                rankMap.computeIfAbsent(c.rank, k -> new ArrayList<>()).add(i);
            }

            // 找出配对的牌（每种点数有偶数张则全部配对）
            List<Integer> toRemove = new ArrayList<>();
            for (List<Integer> indices : rankMap.values()) {
                if (indices.size() >= 2) {
                    // 成对移除
                    int pairs = indices.size() / 2 * 2;
                    for (int i = 0; i < pairs; i++) {
                        toRemove.add(indices.get(i));
                        matched.add(hand.get(indices.get(i)));
                    }
                }
            }

            // 从大到小排序索引，避免删除时索引错乱
            Collections.sort(toRemove, Collections.reverseOrder());
            for (int idx : toRemove) {
                hand.remove(idx);
            }

            return matched;
        }

        public int getHandSize() {
            return hand.size();
        }

        public boolean hasGhost() {
            for (Card c : hand) {
                if (c.isGhost) return true;
            }
            return false;
        }
    }

    // AI记忆系统
    static class AIMemory {
        // 已打出的牌的点数计数（用于推断剩余牌）
        Map<Integer, Integer> playedRankCount = new HashMap<>();
        // 对手曾经拥有过的牌的点数（通过历史抽牌记录）
        Set<Integer> opponentHadRanks = new HashSet<>();
        // 自己手中的牌点数
        Set<Integer> myRanks = new HashSet<>();
        // 总牌数中每种点数的初始数量（4张，Q是3张因为去掉了一张）
        Map<Integer, Integer> totalRankCount = new HashMap<>();

        public AIMemory() {
            for (int i = 1; i <= 13; i++) {
                totalRankCount.put(i, (i == 12) ? 3 : 4); // Q只有3张（一张是鬼牌）
            }
        }

        // 更新记忆：记录已打出的配对牌
        public void recordPlayedCards(List<Card> cards) {
            for (Card c : cards) {
                if (!c.isGhost) {
                    playedRankCount.merge(c.rank, 1, Integer::sum);
                }
            }
        }

        // 更新记忆：记录自己的手牌
        public void updateMyHand(List<Card> myHand) {
            myRanks.clear();
            for (Card c : myHand) {
                if (!c.isGhost) {
                    myRanks.add(c.rank);
                }
            }
        }

        // 计算对手手牌中各位置是鬼牌的概率
        // 返回：每个位置的鬼牌概率数组
        public double[] calculateGhostProbability(List<Card> opponentHand, int opponentSize) {
            double[] probs = new double[opponentSize];

            // 统计已知信息：有多少张牌肯定不是鬼牌
            int safeCards = 0;

            // 推理：对手手中的牌，如果点数在myRanks中且我有偶数张，那对手的该牌可能不是鬼牌
            // 更精确的推理：
            // 鬼牌是Q，所以非Q的牌肯定不是鬼牌
            // 但我们不知道对手的牌是什么，只能通过概率估算

            // 简化模型：估算对手手中Q的数量
            // 总Q数 = 3（其中1张是鬼牌）
            // 我手中的Q数量已知
            int myQueenCount = 0;
            boolean myHasGhost = false;
            for (Card c : opponentHand) { } // 不能看对手的牌！

            // 注意：AI不能直接访问对手手牌，只能通过记忆推断
            // 这里我们用一个更智能的模型：

            // 已知：
            // - 我手中的牌（myRanks）
            // - 已打出的牌（playedRankCount）
            // - 对手手牌数量（opponentSize）

            // 计算剩余未见过的牌中Q的数量
            int totalQueens = 3; // 总共有3张Q（含鬼牌）
            int myQueens = countRankInMyHand(12);
            int playedQueens = playedRankCount.getOrDefault(12, 0) / 2 * 2; // 配对打出的Q（偶数）
            int remainingQueens = totalQueens - myQueens - playedQueens;

            // 剩余未见过的牌总数
            int totalCards = 53;
            int myCards = myRanks.size() > 0 ? getMyTotalCards() : 0;
            int playedCards = playedRankCount.values().stream().mapToInt(Integer::intValue).sum();
            int unseenCards = totalCards - myCards - playedCards;

            // 对手每张牌是鬼牌的概率（均匀分布假设）
            // 但我们可以用历史信息优化：如果对手之前有某张牌被抽走后又出现...
            double baseProb = (remainingQueens > 0) ? 1.0 / opponentSize : 0.0;

            // 启发式：边缘位置的牌对手可能故意把鬼牌放在那里
            // 高级AI会反其道而行之，这里我们用均匀概率作为基础
            Arrays.fill(probs, baseProb);

            return probs;
        }

        private int countRankInMyHand(int rank) {
            int count = 0;
            for (int r : myRanks) {
                if (r == rank) count++;
            }
            // myRanks是Set，需要重新计算
            return 0; // 简化，实际应从hand中统计
        }

        private int getMyTotalCards() {
            return 0; // 简化
        }

        // AI决策：选择抽哪张牌
        public int chooseCardToDraw(int opponentHandSize) {
            // 策略：选择中间位置的牌（人类玩家常把鬼牌放在边缘）
            // 更高级的策略可以基于历史数据学习
            if (opponentHandSize <= 1) return 0;

            // 随机策略 vs 智能策略
            // 这里使用"避开边缘"的启发式策略
            // 因为人类玩家倾向于把重要的牌放在两端或中间
            Random rand = new Random();

            // 70%概率选择中间区域，30%概率随机
            if (rand.nextDouble() < 0.7 && opponentHandSize >= 5) {
                int mid = opponentHandSize / 2;
                int range = Math.max(1, opponentHandSize / 4);
                return mid - range + rand.nextInt(range * 2 + 1);
            } else {
                return rand.nextInt(opponentHandSize);
            }
        }
    }

    // 游戏主类
    private Player human;
    private Player ai;
    private AIMemory aiMemory;
    private List<Card> playedCards;
    private Scanner scanner;

    public OldMaidGame() {
        human = new Player("玩家", false);
        ai = new Player("AI对手", true);
        aiMemory = new AIMemory();
        playedCards = new ArrayList<>();
        scanner = new Scanner(System.in);
    }

    // 初始化牌组并发牌
    public void initDeck() {
        List<Card> deck = new ArrayList<>();
        String[] suits = {"♠", "♥", "♦", "♣"};

        // 创建52张普通牌
        for (int rank = 1; rank <= 13; rank++) {
            for (String suit : suits) {
                deck.add(new Card(rank, suit, false));
            }
        }

        // 去掉一张♠Q，将♥Q设为鬼牌
        Iterator<Card> it = deck.iterator();
        while (it.hasNext()) {
            Card c = it.next();
            if (c.rank == 12 && c.suit.equals("♠")) {
                it.remove();
                break;
            }
        }
        for (Card c : deck) {
            if (c.rank == 12 && c.suit.equals("♥")) {
                c.isGhost = true;
                break;
            }
        }

        // 洗牌
        Collections.shuffle(deck);

        // 发牌
        for (int i = 0; i < deck.size(); i++) {
            if (i % 2 == 0) {
                human.addCard(deck.get(i));
            } else {
                ai.addCard(deck.get(i));
            }
        }
    }

    // 初始配对
    public void initialMatch() {
        List<Card> humanMatched = human.autoMatch();
        List<Card> aiMatched = ai.autoMatch();
        playedCards.addAll(humanMatched);
        playedCards.addAll(aiMatched);
        aiMemory.recordPlayedCards(humanMatched);
        aiMemory.recordPlayedCards(aiMatched);

        System.out.println("=== 初始配对完成 ===");
        System.out.println("玩家打出 " + humanMatched.size() + " 张牌");
        System.out.println("AI打出 " + aiMatched.size() + " 张牌");
        System.out.println("玩家剩余 " + human.getHandSize() + " 张牌");
        System.out.println("AI剩余 " + ai.getHandSize() + " 张牌");
        System.out.println();
    }

    // 显示玩家手牌
    private void showHumanHand() {
        System.out.print("你的手牌：");
        for (int i = 0; i < human.hand.size(); i++) {
            System.out.print("[" + i + "]" + human.hand.get(i) + " ");
        }
        System.out.println();
    }

    // 玩家回合：从AI手中抽牌
    private boolean humanTurn() {
        System.out.println("\n=== 你的回合 ===");
        System.out.println("AI有 " + ai.getHandSize() + " 张牌");
        showHumanHand();
        System.out.print("请选择要抽的牌的位置 (0-" + (ai.getHandSize() - 1) + ")：");

        int choice = scanner.nextInt();
        if (choice < 0 || choice >= ai.getHandSize()) {
            System.out.println("无效位置！");
            return humanTurn();
        }

        Card drawn = ai.removeCard(choice);
        System.out.println("你抽到了：" + drawn);
        human.addCard(drawn);

        // 配对
        List<Card> matched = human.autoMatch();
        if (!matched.isEmpty()) {
            System.out.println("配对成功，打出：" + matched);
            playedCards.addAll(matched);
            aiMemory.recordPlayedCards(matched);
        }

        showHumanHand();
        return human.getHandSize() == 0;
    }

    // AI回合：从玩家手中抽牌
    private boolean aiTurn() {
        System.out.println("\n=== AI的回合 ===");
        System.out.println("AI正在思考...");

        // 更新AI记忆
        aiMemory.updateMyHand(ai.hand);

        // AI决策
        int choice = aiMemory.chooseCardToDraw(human.getHandSize());
        System.out.println("AI选择了第 " + choice + " 张牌");

        Card drawn = human.removeCard(choice);
        System.out.println("AI抽到了：" + drawn);
        ai.addCard(drawn);

        // 配对
        List<Card> matched = ai.autoMatch();
        if (!matched.isEmpty()) {
            System.out.println("AI配对成功，打出 " + matched.size() + " 张牌");
            playedCards.addAll(matched);
            aiMemory.recordPlayedCards(matched);
        }

        System.out.println("AI剩余 " + ai.getHandSize() + " 张牌");
        return ai.getHandSize() == 0;
    }

    // 游戏主循环
    public void play() {
        System.out.println("🎴 欢迎来到抽鬼牌游戏！");
        System.out.println("规则：从对方手中抽牌，配对后打出，最后拿到鬼牌的人输。\n");

        initDeck();
        initialMatch();

        boolean gameOver = false;
        boolean humanTurn = true;

        while (!gameOver) {
            if (humanTurn) {
                gameOver = humanTurn();
                if (gameOver) {
                    System.out.println("\n🎉 恭喜你赢了！AI拿到了鬼牌！");
                    break;
                }
            } else {
                gameOver = aiTurn();
                if (gameOver) {
                    System.out.println("\n😢 AI赢了！你拿到了鬼牌...");
                    break;
                }
            }
            humanTurn = !humanTurn;

            // 检查是否只剩鬼牌
            if (human.getHandSize() == 1 && human.hasGhost() && ai.getHandSize() == 0) {
                System.out.println("\n😢 你输了！鬼牌在你手中！");
                break;
            }
            if (ai.getHandSize() == 1 && ai.hasGhost() && human.getHandSize() == 0) {
                System.out.println("\n🎉 你赢了！鬼牌在AI手中！");
                break;
            }
        }

        scanner.close();
    }

    public static void main(String[] args) {
        OldMaidGame game = new OldMaidGame();
        game.play();
    }
}

四、算法复杂度分析

4.1 时间复杂度

其中n=53为常数，整体游戏每回合的时间复杂度为O(m)，m为当前手牌数。

4.2 空间复杂度

• 手牌存储：O(m)，m为玩家手牌数
• 记忆系统：O(1)，因为牌的点数只有13种，是常数空间
• 已出牌记录：O(n)，n为总牌数

五、博弈策略与拓展

5.1 高级AI策略

本文实现的AI使用了基础的启发式策略，更高级的AI可以包含：

1. 贝叶斯推理：根据对手的抽牌选择，不断更新对手手牌的概率分布
2. 心理博弈：分析对手的抽牌模式，预测其策略
3. 反向诱导：故意将鬼牌放在对手最可能抽的位置的反位置

5.2 游戏拓展方向

• 多人模式：支持3-5人游戏，鬼牌数量可配置
• 难度分级：简单/普通/困难三个难度等级
• 网络对战：支持多人在线对战
• 统计分析：记录胜率数据，分析最优策略

5.3 实际应用

抽鬼牌中的概率推理和记忆策略在实际中有广泛应用：
– 扑克AI：德州扑克等不完全信息博弈
– 网络安全：基于行为模式的入侵检测
– 推荐系统：用户偏好的概率推断