每日算法 — 使用java实现钓鱼纸牌：不完全信息博弈与记忆策略最优决策

一、钓鱼纸牌规则与博弈特征

钓鱼纸牌（Go Fish）是全球流行的经典纸牌游戏，核心规则如下：

1. 一副牌（不含大小王）均分给所有玩家，剩余为”鱼塘”
2. 玩家轮流向其他玩家索要特定点数的牌（如”给我所有的7″）
3. 如果对方有该点数的牌，必须全部交出；否则说”去钓鱼”，索要者从鱼塘抽一张
4. 当玩家集齐4张同点数时，组成一套并亮出计分
5. 手牌用完者从鱼塘补牌，鱼塘空时游戏结束，套数最多者获胜

钓鱼纸牌是典型的不完全信息博弈：
– 每位玩家只能看到自己的手牌和已亮出的套
– 需要通过对手的行为推断其手牌分布
– 记忆能力直接决定胜率

二、不完全信息博弈建模

2.1 信息集定义

在钓鱼纸牌中，玩家 i 的信息集包含：
– 私有信息：自己的手牌
– 公共信息：已亮出的所有套、每位玩家索要/交出的历史
– 推断信息：对手手牌的概率分布（通过贝叶斯更新）

2.2 贝叶斯信念更新

当玩家A向玩家B索要点数 r 时：
– B交出k张：确认B手中该点数剩余为0，更新信念
– B说”去钓鱼”：确认B手中没有该点数，A从鱼塘抽一张（所有人看到A抽牌但不知道是什么）

三、核心算法实现

3.1 增强版卡牌与套管理

import java.util.*;

public class GoFishCard {
    public enum Suit { HEARTS, DIAMONDS, CLUBS, SPADES }
    private final Suit suit;
    private final int rank; // 1-13

    public GoFishCard(Suit suit, int rank) {
        this.suit = suit;
        this.rank = rank;
    }
    public int getRank() { return rank; }
    public Suit getSuit() { return suit; }

    @Override
    public String toString() {
        String[] r = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
        return r[rank-1] + suit.toString().charAt(0);
    }
}

public class CardDeck {
    private List<GoFishCard> cards;
    private Random rand;

    public CardDeck() {
        cards = new ArrayList<>();
        rand = new Random();
        for (GoFishCard.Suit s : GoFishCard.Suit.values()) {
            for (int r = 1; r <= 13; r++) cards.add(new GoFishCard(s, r));
        }
    }
    public void shuffle() { Collections.shuffle(cards, rand); }
    public GoFishCard draw() { return cards.isEmpty() ? null : cards.remove(cards.size()-1); }
    public boolean isEmpty() { return cards.isEmpty(); }
    public int size() { return cards.size(); }
}

3.2 记忆模型：对手手牌信念追踪

public class BeliefModel {
    // beliefs[rank][player] = 该玩家持有该点数的期望张数
    private double[][] beliefs;
    private int numPlayers;
    private int numRanks = 13;
    private Random random;

    public BeliefModel(int numPlayers) {
        this.numPlayers = numPlayers;
        this.beliefs = new double[numRanks][numPlayers];
        this.random = new Random();

        // 初始均匀分布：每人每张点数期望 4/numPlayers
        for (int r = 0; r < numRanks; r++) {
            for (int p = 0; p < numPlayers; p++) {
                beliefs[r][p] = 4.0 / numPlayers;
            }
        }
    }

    /**
     * 更新信念：玩家p交出了k张rank点数的牌给asker
     */
    public void updateGiven(int rank, int player, int countGiven, int asker) {
        int r = rank - 1;
        // 确认player手中该点数剩余极少
        beliefs[r][player] = Math.max(0, beliefs[r][player] - countGiven);
        // asker获得了牌，期望值增加
        beliefs[r][asker] += countGiven;

        normalize(r);
    }

    /**
     * 更新信念：player被索要rank但说"Go Fish"
     * 确认player没有该点数
     */
    public void updateGoFish(int rank, int player) {
        int r = rank - 1;
        beliefs[r][player] = 0;
        normalize(r);
    }

    /**
     * 玩家亮出一套（4张），清空所有玩家对该点数的信念
     */
    public void updateCompleteSet(int rank) {
        int r = rank - 1;
        for (int p = 0; p < numPlayers; p++) {
            beliefs[r][p] = 0;
        }
    }

    private void normalize(int r) {
        double sum = 0;
        for (int p = 0; p < numPlayers; p++) sum += beliefs[r][p];
        if (sum > 0) {
            for (int p = 0; p < numPlayers; p++) {
                beliefs[r][p] = Math.min(4, beliefs[r][p] * (4.0 / sum));
            }
        }
    }

    /**
     * 获取某玩家持有某点数的期望张数
     */
    public double getExpectedCount(int rank, int player) {
        return beliefs[rank-1][player];
    }

    /**
     * 选择索要目标：找期望值最高的对手和点数
     */
    public int[] chooseBestAsk(int myId, List<Integer> myRanks) {
        double bestScore = -1;
        int bestRank = -1;
        int bestTarget = -1;

        for (int rank : myRanks) {
            for (int p = 0; p < numPlayers; p++) {
                if (p == myId) continue;
                double expected = beliefs[rank-1][p];
                // 综合期望张数和完成套的概率
                double score = expected * (1 + expected / 4.0);
                if (score > bestScore) {
                    bestScore = score;
                    bestRank = rank;
                    bestTarget = p;
                }
            }
        }
        return new int[]{bestRank, bestTarget};
    }
}

3.3 AI玩家：记忆策略实现

public class GoFishAI {
    private String name;
    private List<GoFishCard> hand;
    private int score; // 完成的套数
    private BeliefModel belief;
    private int id;
    private Random random;

    // 精确记忆：记录已知在谁手中的牌
    private Map<Integer, Set<Integer>> knownCards; // rank -> set of player ids

    public GoFishAI(String name, int id, int numPlayers) {
        this.name = name;
        this.id = id;
        this.hand = new ArrayList<>();
        this.score = 0;
        this.belief = new BeliefModel(numPlayers);
        this.random = new Random();
        this.knownCards = new HashMap<>();
        for (int r = 1; r <= 13; r++) knownCards.put(r, new HashSet<>());
    }

    public String getName() { return name; }
    public int getId() { return id; }
    public int getScore() { return score; }
    public int getHandSize() { return hand.size(); }
    public boolean isHandEmpty() { return hand.isEmpty(); }

    public void receiveCard(GoFishCard card) {
        if (card != null) hand.add(card);
    }

    public void receiveCards(List<GoFishCard> cards) {
        hand.addAll(cards);
    }

    /**
     * 检查是否能组成套并亮出
     */
    public List<Integer> checkCompleteSets() {
        Map<Integer, List<GoFishCard>> byRank = new HashMap<>();
        for (GoFishCard c : hand) {
            byRank.computeIfAbsent(c.getRank(), k -> new ArrayList<>()).add(c);
        }

        List<Integer> completed = new ArrayList<>();
        for (Map.Entry<Integer, List<GoFishCard>> entry : byRank.entrySet()) {
            if (entry.getValue().size() >= 4) {
                completed.add(entry.getKey());
                // 移除这4张牌
                hand.removeAll(entry.getValue().subList(0, 4));
                score++;
                belief.updateCompleteSet(entry.getKey());
            }
        }
        return completed;
    }

    /**
     * 核心决策：向谁索要什么点数的牌
     */
    public AskDecision makeDecision() {
        // 策略1：优先向已知有该点数的玩家索要（精确记忆）
        Set<Integer> myRanks = new HashSet<>();
        for (GoFishCard c : hand) myRanks.add(c.getRank());

        for (int rank : myRanks) {
            Set<Integer> knownHolders = knownCards.get(rank);
            for (int holder : knownHolders) {
                if (holder != id && belief.getExpectedCount(rank, holder) > 0.5) {
                    return new AskDecision(rank, holder, "known_memory");
                }
            }
        }

        // 策略2：使用信念模型选择最优期望目标
        int[] best = belief.chooseBestAsk(id, new ArrayList<>(myRanks));
        if (best[0] > 0) {
            return new AskDecision(best[0], best[1], "belief_model");
        }

        // 策略3：随机选择（保底）
        int rank = new ArrayList<>(myRanks).get(random.nextInt(myRanks.size()));
        int target;
        do { target = random.nextInt(belief.numPlayers); } while (target == id);
        return new AskDecision(rank, target, "random");
    }

    /**
     * 记录观察到的行为
     */
    public void observeAsk(int asker, int target, int rank, boolean success, int count) {
        if (success) {
            belief.updateGiven(rank, target, count, asker);
            knownCards.get(rank).add(target);
            // 目标交出了牌，asker现在肯定有该点数
            knownCards.get(rank).add(asker);
        } else {
            belief.updateGoFish(rank, target);
            // 目标没有该点数
            knownCards.get(rank).remove(target);
        }
    }

    /**
     * 给出指定点数的所有牌
     */
    public List<GoFishCard> giveCards(int rank) {
        List<GoFishCard> toGive = new ArrayList<>();
        Iterator<GoFishCard> it = hand.iterator();
        while (it.hasNext()) {
            GoFishCard c = it.next();
            if (c.getRank() == rank) {
                toGive.add(c);
                it.remove();
            }
        }
        return toGive;
    }

    public boolean hasRank(int rank) {
        return hand.stream().anyMatch(c -> c.getRank() == rank);
    }

    @Override
    public String toString() {
        return String.format("%s[套:%d 手牌:%d]", name, score, hand.size());
    }
}

class AskDecision {
    int rank;
    int target;
    String strategy;

    AskDecision(int rank, int target, String strategy) {
        this.rank = rank;
        this.target = target;
        this.strategy = strategy;
    }
}

3.4 游戏主引擎

public class GoFishGame {
    private List<GoFishAI> players;
    private CardDeck pond;
    private Random random;
    private int currentPlayer;

    public GoFishGame(int numPlayers) {
        this.players = new ArrayList<>();
        this.random = new Random();

        String[] names = {"记忆大师", "概率专家", "随机玩家"};
        for (int i = 0; i < numPlayers && i < names.length; i++) {
            players.add(new GoFishAI(names[i], i, numPlayers));
        }
    }

    public void initialize() {
        pond = new CardDeck();
        pond.shuffle();

        // 每人发5张牌（标准规则）
        int initialCards = 5;
        for (int i = 0; i < initialCards; i++) {
            for (GoFishAI p : players) {
                p.receiveCard(pond.draw());
            }
        }

        // 初始检查套
        for (GoFishAI p : players) p.checkCompleteSets();
        currentPlayer = 0;
    }

    public void playRound() {
        GoFishAI player = players.get(currentPlayer);
        if (player.isHandEmpty() && !pond.isEmpty()) {
            player.receiveCard(pond.draw());
            System.out.println(player.getName() + " 从鱼塘补牌");
        }

        if (player.isHandEmpty()) {
            currentPlayer = (currentPlayer + 1) % players.size();
            return;
        }

        AskDecision decision = player.makeDecision();
        GoFishAI target = players.get(decision.target);

        System.out.printf("%s -> %s: 给我所有的%s (策略:%s)\n",
            player.getName(), target.getName(), 
            rankToString(decision.rank), decision.strategy);

        boolean success = target.hasRank(decision.rank);
        List<GoFishCard> received;

        if (success) {
            received = target.giveCards(decision.rank);
            player.receiveCards(received);
            System.out.println("  成功！获得 " + received.size() + " 张");

            // 通知所有玩家观察
            for (GoFishAI p : players) {
                p.observeAsk(player.getId(), target.getId(), decision.rank, true, received.size());
            }
        } else {
            System.out.println("  " + target.getName() + ": Go Fish!");
            GoFishCard drawn = pond.draw();
            if (drawn != null) {
                player.receiveCard(drawn);
                System.out.println("  从鱼塘抽到: " + drawn);
            }

            for (GoFishAI p : players) {
                p.observeAsk(player.getId(), target.getId(), decision.rank, false, 0);
            }
            currentPlayer = (currentPlayer + 1) % players.size();
        }

        // 检查是否完成套
        List<Integer> completed = player.checkCompleteSets();
        if (!completed.isEmpty()) {
            System.out.println("  *** " + player.getName() + " 亮出套: " + completed);
        }
    }

    private String rankToString(int rank) {
        String[] r = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
        return r[rank-1];
    }

    public boolean isGameOver() {
        if (!pond.isEmpty()) return false;
        for (GoFishAI p : players) {
            if (!p.isHandEmpty()) return false;
        }
        return true;
    }

    public void play() {
        initialize();
        System.out.println("=== 钓鱼纸牌开始 ===\n");

        int rounds = 0;
        while (!isGameOver() && rounds < 200) {
            playRound();
            rounds++;
        }

        System.out.println("\n=== 最终结果 ===");
        players.sort((a, b) -> b.getScore() - a.getScore());
        for (GoFishAI p : players) {
            System.out.println(p);
        }
    }

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

四、策略对比实验

public class StrategyComparison {
    public static void main(String[] args) {
        int iterations = 1000;
        int[] wins = new int[3];

        for (int i = 0; i < iterations; i++) {
            GoFishGame game = new GoFishGame(3);
            game.initialize();
            int rounds = 0;
            while (!game.isGameOver() && rounds < 200) {
                game.playRound();
                rounds++;
            }

            // 记录胜者
            int best = 0;
            for (int j = 1; j < 3; j++) {
                if (game.players.get(j).getScore() > game.players.get(best).getScore()) {
                    best = j;
                }
            }
            wins[best]++;
        }

        System.out.println("=== 1000局统计 ===");
        String[] names = {"记忆大师", "概率专家", "随机玩家"};
        for (int i = 0; i < 3; i++) {
            System.out.printf("%s: %d胜 (%.1f%%)\n", names[i], wins[i], 100.0 * wins[i] / iterations);
        }
    }
}

五、复杂度分析

六、扩展与优化

1. 深度记忆：不仅记忆”谁有什么”，还记忆”谁索要什么”推断其手牌
2. 欺骗策略：故意索要自己没有的点数，误导对手信念
3. 联盟检测：识别两个玩家是否互相配合
4. 强化学习：使用Q-Learning训练更优的索要策略

七、总结

钓鱼纸牌是不完全信息博弈的经典范例。通过贝叶斯信念更新追踪对手手牌分布、记忆模型记录确定性信息、期望收益计算选择最优索要目标，AI玩家可以显著优于随机策略。这些技术同样适用于桥牌、德州扑克等更复杂的纸牌博弈场景。