每日算法 — 使用java实现记忆翻牌：信息熵驱动的最优翻牌策略与概率匹配算法

记忆翻牌（Memory/Concentration）是一款经典的益智小游戏：将若干对相同图案的卡牌背面朝上排列，玩家每次翻开两张，若图案相同则消除，不同则重新翻回。看似简单的规则背后，隐藏着丰富的概率计算与信息论思想。本文将用Java实现一个带AI策略的记忆翻牌游戏，核心在于如何利用信息熵量化不确定性，指导AI做出最优翻牌决策。

一、游戏规则与状态建模

1.1 基本规则

• 棋盘为 N×M 的格子，共放置 (N×M)/2 种图案，每种图案恰好两张
• 每次操作翻开两张卡牌：
• 若图案相同，两张卡牌永久消除
• 若不同，两张卡牌重新翻回背面
• 游戏目标：以最少翻牌次数消除全部卡牌

1.2 状态表示

用三个集合描述AI已知信息：

• knownPairs：已确认位置的配对（如知道位置3和位置7都是”苹果”）
• knownSingles：只见过一张但未知配对的卡牌（如知道位置5是”香蕉”，但不知道另一张在哪）
• unknown：从未被翻开的卡牌

enum CardState {
    UNKNOWN,      // 从未翻开
    KNOWN_SINGLE, // 已知一张，配对未知
    MATCHED       // 已配对消除
}

class Card {
    int id;           // 图案编号
    CardState state;
    boolean isFaceUp; // 当前是否朝上
}

二、核心算法：信息熵驱动决策

2.1 信息熵建模

信息熵（Shannon Entropy）度量系统的不确定性。在记忆翻牌中，我们关心”翻开某张未知卡牌后，能获得多少信息量”。

假设当前有 U 张未知卡牌，S 张已知单张卡牌。若选择翻开一张未知卡牌，其结果等价于：从 U 张牌中随机抽取一张，其图案可能是：

• 与某张已知单张配对（概率为 S / (U-1)，因为每张已知单张的配对都在未知牌中）
• 打开一个全新的图案（概率为 (U - S) / (U-1)，但这需要更精确计算）

实际上更精确的建模：设总共有 P 种图案，其中 p_known 种已有已知单张，p_matched 种已配对消除，p_unknown 种完全未知。则 p_unknown = P - p_known - p_matched。

翻开一张未知牌后：
– 若该图案对应某已知单张（概率 p_known / p_unknown，当该图案的配对完全在未知牌中时），则立即形成配对，信息量最大
– 若该图案是全新的（概率 (p_unknown - p_known) / p_unknown），则新增一张已知单张

2.2 最优策略决策树

AI每回合的决策优先级如下：

1. 立即配对：若有两张已知单张属于同一图案，直接翻开它们（确定性收益）
2. 安全翻牌：若已知单张的配对位置可以确定，翻开它
3. 熵最小化翻牌：在未知牌中选择”期望信息量”最小的位置，降低未来不确定性

第3步的核心计算：对于每张未知卡牌，计算翻开它的期望信息增益，选择信息增益最大的（或等价地，选择”翻开后最有可能立即配对”的）。

/**
 * 计算翻开某张未知卡牌后的期望信息增益
 * 信息增益 = -Σ p(x) * log2(p(x))
 * 其中x为可能翻到的图案类别
 */
double calculateExpectedInfoGain(int position, Board board) {
    // 统计各图案在当前未知牌中的分布
    Map<Integer, Integer> patternCount = board.getUnknownPatternDistribution();

    int totalUnknown = board.unknownCount();
    double entropy = 0.0;

    for (Map.Entry<Integer, Integer> entry : patternCount.entrySet()) {
        int pattern = entry.getKey();
        int count = entry.getValue(); // 该图案在未知牌中的数量
        double p = (double) count / totalUnknown;
        entropy -= p * Math.log(p) / Math.log(2);
    }

    return entropy;
}

2.3 概率匹配算法

当没有确定性配对可用时，AI需要估算”翻哪两张未知牌最可能配对成功”。

设棋盘上有 U 张未知牌，其中有 K 种图案各出现2次（完全未知），S 种图案各出现1次（因为另1张是已知单张）。

翻开两张未知牌配对的概率：
– 从 U 张中选2张，总方案数 C(U,2)
– 成功配对的方案数：K（每种完全未知的图案贡献1对）
– 因此单次随机翻两张的配对概率为 K / C(U,2)

AI的优化策略：优先翻”已知单张的配对牌”。若某图案已知单张数量为1，其配对牌在未知牌中恰好1张，翻开这张的”配对成功率”为 1 / U（作为第二张时），虽然不高，但翻开后能消除一对。

更聪明的策略是：先翻开未知牌探索信息，一旦获得足够信息（找到配对）立即执行配对。

/**
 * 计算选择两张未知牌的成功配对概率
 */
double pairSuccessProbability(Board board) {
    int u = board.unknownCount();
    int k = board.fullyUnknownPatternCount(); // 完全未知的图案对数

    if (u < 2) return 0.0;
    int totalPairs = u * (u - 1) / 2;
    return (double) k / totalPairs;
}

三、完整Java实现

import java.util.*;

/**
 * 记忆翻牌游戏 - 信息熵驱动AI策略
 */
public class MemoryGame {

    private final int rows;
    private final int cols;
    private final Card[][] board;
    private final Random random = new Random();
    private int remainingPairs;
    private int moveCount;

    // AI记忆：图案ID -> 已知位置列表
    private final Map<Integer, List<int[]>> aiMemory = new HashMap<>();
    private final Set<String> eliminatedPositions = new HashSet<>();

    public MemoryGame(int rows, int cols) {
        if ((rows * cols) % 2 != 0) {
            throw new IllegalArgumentException("总格子数必须是偶数");
        }
        this.rows = rows;
        this.cols = cols;
        this.board = new Card[rows][cols];
        this.remainingPairs = (rows * cols) / 2;
        initializeBoard();
    }

    private void initializeBoard() {
        int totalCards = rows * cols;
        int pairCount = totalCards / 2;

        // 生成图案编号列表，每种图案两张
        List<Integer> patterns = new ArrayList<>();
        for (int i = 0; i < pairCount; i++) {
            patterns.add(i);
            patterns.add(i);
        }
        Collections.shuffle(patterns, random);

        // 填充棋盘
        int idx = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                board[r][c] = new Card(patterns.get(idx++), r, c);
            }
        }
    }

    /**
     * AI执行一步决策
     */
    public void aiPlay() {
        moveCount++;
        System.out.println("\n=== AI第" + moveCount + "步 ===");

        // 步骤1：检查是否有已知配对可直接消除
        List<int[]> knownPair = findKnownPair();
        if (knownPair != null) {
            System.out.println("策略：执行已知配对");
            flipAndMatch(knownPair.get(0), knownPair.get(1));
            return;
        }

        // 步骤2：信息熵驱动选择
        // 先翻开一张"期望信息增益最大"的牌
        int[] first = selectBestUnknownCard();
        if (first == null) {
            System.out.println("游戏结束");
            return;
        }

        Card firstCard = flip(first);
        System.out.println("翻开第一张: [" + first[0] + "," + first[1] + "] = 图案" + firstCard.patternId);

        // 检查翻开的这张是否可以和已知单张配对
        int[] matchingKnown = findMatchingKnown(firstCard.patternId, first);
        if (matchingKnown != null) {
            System.out.println("策略：与已知单张配对");
            flipAndMatch(first, matchingKnown);
            return;
        }

        // 步骤3：第二张牌的选择
        // 优先：是否有另一张已知单张属于同一新图案？（不可能，因为上面已检查）
        // 次优：选择"与第一张最可能配对"的牌
        int[] second = selectSecondCard(first, firstCard.patternId);
        Card secondCard = flip(second);
        System.out.println("翻开第二张: [" + second[0] + "," + second[1] + "] = 图案" + secondCard.patternId);

        if (firstCard.patternId == secondCard.patternId) {
            System.out.println("匹配成功！消除图案" + firstCard.patternId);
            eliminate(first, second);
        } else {
            System.out.println("不匹配，翻回");
            // AI记住这两张牌的信息
            rememberCard(first, firstCard.patternId);
            rememberCard(second, secondCard.patternId);
            firstCard.isFaceUp = false;
            secondCard.isFaceUp = false;
        }
    }

    /**
     * 寻找AI记忆中已知的可配对两张牌
     */
    private List<int[]> findKnownPair() {
        for (Map.Entry<Integer, List<int[]>> entry : aiMemory.entrySet()) {
            List<int[]> positions = entry.getValue();
            // 过滤已消除的位置
            List<int[]> available = new ArrayList<>();
            for (int[] pos : positions) {
                if (!eliminatedPositions.contains(pos[0] + "," + pos[1]) && !board[pos[0]][pos[1]].isFaceUp) {
                    available.add(pos);
                }
            }
            if (available.size() >= 2) {
                return Arrays.asList(available.get(0), available.get(1));
            }
        }
        return null;
    }

    /**
     * 寻找与指定图案匹配的已知单张（排除当前位置）
     */
    private int[] findMatchingKnown(int patternId, int[] exclude) {
        List<int[]> known = aiMemory.get(patternId);
        if (known == null) return null;
        for (int[] pos : known) {
            if (!posEquals(pos, exclude) && !eliminatedPositions.contains(pos[0] + "," + pos[1])
                    && !board[pos[0]][pos[1]].isFaceUp) {
                return pos;
            }
        }
        return null;
    }

    /**
     * 信息熵驱动：选择最佳未知卡牌
     * 优先选择"其配对已知"的位置（高确定性）
     * 否则选择信息价值最大的未知位置
     */
    private int[] selectBestUnknownCard() {
        List<int[]> unknowns = getAllUnknownCards();
        if (unknowns.isEmpty()) return null;

        // 策略A：如果某张未知牌的配对是已知单张，优先翻它
        for (int[] pos : unknowns) {
            Card card = board[pos[0]][pos[1]];
            List<int[]> known = aiMemory.get(card.patternId);
            if (known != null && !known.isEmpty()) {
                boolean hasValidKnown = known.stream()
                    .anyMatch(k -> !posEquals(k, pos) && !eliminatedPositions.contains(k[0] + "," + k[1])
                            && !board[k[0]][k[1]].isFaceUp);
                if (hasValidKnown) {
                    return pos;
                }
            }
        }

        // 策略B：选择信息熵最大的位置（探索价值最高）
        // 简化为：优先翻完全未知的区域，随机选择
        return unknowns.get(random.nextInt(unknowns.size()));
    }

    /**
     * 选择第二张牌
     * 若第一张是新图案，第二张选择"最可能配对"的未知牌
     */
    private int[] selectSecondCard(int[] firstPos, int firstPattern) {
        List<int[]> unknowns = getAllUnknownCards();
        // 排除第一张
        unknowns.removeIf(pos -> posEquals(pos, firstPos));

        if (unknowns.isEmpty()) return null;

        // 检查是否有已知单张与新翻开的牌配对
        int[] matching = findMatchingKnown(firstPattern, firstPos);
        if (matching != null) {
            return matching;
        }

        // 计算每张候选牌与第一张牌配对的概率
        // 如果第一张是新图案，其配对在剩余未知牌中恰好有1张
        // 均匀随机选择
        return unknowns.get(random.nextInt(unknowns.size()));
    }

    private List<int[]> getAllUnknownCards() {
        List<int[]> result = new ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (!board[r][c].isFaceUp && !eliminatedPositions.contains(r + "," + c)) {
                    result.add(new int[]{r, c});
                }
            }
        }
        return result;
    }

    private Card flip(int[] pos) {
        board[pos[0]][pos[1]].isFaceUp = true;
        return board[pos[0]][pos[1]];
    }

    private void flipAndMatch(int[] pos1, int[] pos2) {
        Card c1 = flip(pos1);
        Card c2 = flip(pos2);
        System.out.println("配对: [" + pos1[0] + "," + pos1[1] + "] & [" + pos2[0] + "," + pos2[1] + "] = 图案" + c1.patternId);
        eliminate(pos1, pos2);
    }

    private void eliminate(int[] pos1, int[] pos2) {
        eliminatedPositions.add(pos1[0] + "," + pos1[1]);
        eliminatedPositions.add(pos2[0] + "," + pos2[1]);
        remainingPairs--;
    }

    private void rememberCard(int[] pos, int patternId) {
        aiMemory.computeIfAbsent(patternId, k -> new ArrayList<>()).add(pos);
    }

    private boolean posEquals(int[] a, int[] b) {
        return a[0] == b[0] && a[1] == b[1];
    }

    public boolean isGameOver() {
        return remainingPairs == 0;
    }

    public int getMoveCount() {
        return moveCount;
    }

    public void printBoard() {
        System.out.println("\n当前棋盘状态：");
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (eliminatedPositions.contains(r + "," + c)) {
                    System.out.print("[XX] ");
                } else if (board[r][c].isFaceUp) {
                    System.out.printf("[%2d] ", board[r][c].patternId);
                } else {
                    System.out.print("[??] ");
                }
            }
            System.out.println();
        }
    }

    static class Card {
        int patternId;
        int row, col;
        boolean isFaceUp;

        Card(int patternId, int row, int col) {
            this.patternId = patternId;
            this.row = row;
            this.col = col;
        }
    }

    public static void main(String[] args) {
        // 4x4棋盘，8对图案
        MemoryGame game = new MemoryGame(4, 4);
        System.out.println("记忆翻牌游戏开始！4x4棋盘，共8对图案");

        while (!game.isGameOver()) {
            game.printBoard();
            game.aiPlay();
        }

        game.printBoard();
        System.out.println("\n游戏结束！AI总共用了 " + game.getMoveCount() + " 步完成全部配对");
        System.out.println("理论最优步数（每次配对成功）：8步");
        System.out.println("实际步数越接近理论值，说明AI策略越高效");
    }
}

四、算法复杂度分析

五、策略优化方向

1. 贝叶斯更新：每次翻牌后更新各位置的后验概率分布，不依赖均匀分布假设
2. 对手建模：双人对战时，需考虑对手的记忆能力，引入博弈论思想
3. 蒙特卡洛模拟：通过大量随机模拟评估不同翻牌策略的期望收益
4. 完美信息策略：若允许AI拥有过目不忘的完美记忆，问题退化为确定性搜索，最优解可通过动态规划求得

六、总结

记忆翻牌游戏虽然规则极简，却蕴含了信息论、概率统计与搜索算法的核心思想。通过信息熵量化未知状态的不确定性，AI能够做出”最有价值”的探索决策。这种”探索-利用”（Exploration-Exploitation）的权衡也是强化学习、推荐系统等领域的基础问题。希望本文的Java实现能帮助读者理解信息熵在实际决策中的威力。