每日算法 — 使用java实现三国杀：蒙特卡洛模拟与贪心最优出牌决策

引言

三国杀是一款风靡全国的策略卡牌游戏，玩家扮演三国时期武将，通过使用手牌、发动技能来击败对手。游戏中的决策充满不确定性：抽到的手牌随机、对手行为未知，如何在信息不完全的情况下做出最优决策？本文将用Java实现一个简化版三国杀的AI核心，讲解蒙特卡洛模拟（Monte Carlo Simulation）在概率决策中的应用，以及贪心策略在手牌管理中的优化思路。

算法原理

蒙特卡洛模拟

蒙特卡洛方法通过大量随机采样来估计期望收益。在三国杀中，AI可以模拟多种可能的对手手牌和后续牌堆分布，对每种候选出牌方案进行 thousands 次对局模拟，选择胜率最高的方案。

贪心手牌评估

每次出牌前，AI需要快速评估当前手牌组合的价值。定义每张牌的即时价值函数：杀牌的价值取决于目标敌方剩余血量，闪牌的价值取决于受到攻击的概率，桃牌的价值与自身血量负相关。贪心策略选择当前价值最高的合法行动。

Java实现

import java.util.*;

/**
 * 简化版三国杀AI核心：蒙特卡洛模拟 + 贪心最优出牌
 */
public class SanguoshaAI {

    // 牌类型
    enum CardType { SHA, SHAN, TAO, JUEDOU, WUZHONG, SHUNSHOU }
    // 身份
    enum Role { ZHU, ZHONG, FAN, NEI }

    static class Card {
        CardType type;
        Card(CardType t) { this.type = t; }
    }

    static class Player {
        int hp = 4, maxHp = 4;
        List<Card> hand = new ArrayList<>();
        Role role;
        boolean alive = true;
        Player(Role r) { this.role = r; }

        int handValue(Player[] all, int selfIdx) {
            int val = 0;
            for (Card c : hand) {
                val += cardValue(c, all, selfIdx);
            }
            return val;
        }
    }

    /**
     * 评估单张牌对当前玩家的即时价值
     */
    static int cardValue(Card c, Player[] all, int selfIdx) {
        Player self = all[selfIdx];
        switch (c.type) {
            case SHA: // 杀：目标为血量最少的敌人时价值最高
                int minEnemyHp = 10;
                for (int i = 0; i < all.length; i++) {
                    if (i == selfIdx || !all[i].alive) continue;
                    if (isEnemy(self, all[i])) minEnemyHp = Math.min(minEnemyHp, all[i].hp);
                }
                return Math.max(0, 6 - minEnemyHp);
            case SHAN: // 闪：自身血量越低价值越高
                return Math.max(1, 5 - self.hp);
            case TAO: // 桃：自身血量越低价值越高
                return self.hp <= 2 ? 8 : 3;
            case JUEDOU: // 决斗：对血量少且手牌少的敌人使用
                return 4;
            case WUZHONG: // 无中生有：稳定价值
                return 5;
            case SHUNSHOU: // 顺手牵羊：敌方手牌多时价值高
                return 4;
            default: return 1;
        }
    }

    static boolean isEnemy(Player a, Player b) {
        if (a.role == Role.ZHU) return b.role == Role.FAN || b.role == Role.NEI;
        if (a.role == Role.FAN) return b.role == Role.ZHU || b.role == Role.ZHONG;
        return true; // 内奸视所有人为敌人（简化）
    }

    /**
     * 贪心策略选择最优行动
     * @return 行动描述字符串，null表示跳过出牌
     */
    static String greedyAction(Player[] all, int selfIdx) {
        Player self = all[selfIdx];
        int bestVal = -1;
        String bestAction = null;
        int bestCardIdx = -1;

        for (int i = 0; i < self.hand.size(); i++) {
            Card c = self.hand.get(i);
            int val = cardValue(c, all, selfIdx);
            String action = null;
            int target = -1;

            switch (c.type) {
                case SHA:
                    target = findBestTarget(all, selfIdx, c.type);
                    if (target >= 0) action = "SHA->P" + target;
                    break;
                case TAO:
                    if (self.hp < self.maxHp) action = "TAO->SELF";
                    break;
                case WUZHONG:
                    action = "WUZHONG";
                    break;
                case JUEDOU:
                    target = findBestTarget(all, selfIdx, c.type);
                    if (target >= 0) action = "JUEDOU->P" + target;
                    break;
                case SHUNSHOU:
                    target = findRichestEnemy(all, selfIdx);
                    if (target >= 0) action = "SHUNSHOU->P" + target;
                    break;
                default:
                    break;
            }

            if (action != null && val > bestVal) {
                bestVal = val;
                bestAction = action;
                bestCardIdx = i;
            }
        }

        if (bestAction != null) {
            self.hand.remove(bestCardIdx);
        }
        return bestAction;
    }

    static int findBestTarget(Player[] all, int selfIdx, CardType type) {
        Player self = all[selfIdx];
        int best = -1, minHp = 10;
        for (int i = 0; i < all.length; i++) {
            if (i == selfIdx || !all[i].alive) continue;
            if (!isEnemy(self, all[i])) continue;
            if (all[i].hp < minHp) {
                minHp = all[i].hp;
                best = i;
            }
        }
        return best;
    }

    static int findRichestEnemy(Player[] all, int selfIdx) {
        Player self = all[selfIdx];
        int best = -1, maxHand = -1;
        for (int i = 0; i < all.length; i++) {
            if (i == selfIdx || !all[i].alive) continue;
            if (!isEnemy(self, all[i])) continue;
            if (all[i].hand.size() > maxHand) {
                maxHand = all[i].hand.size();
                best = i;
            }
        }
        return best;
    }

    /**
     * 蒙特卡洛模拟：评估当前状态下某行动的期望胜率
     * @param simCount 模拟次数
     */
    static double monteCarloEval(Player[] current, int selfIdx, String action, int simCount) {
        int wins = 0;
        Random rand = new Random();
        for (int s = 0; s < simCount; s++) {
            // 复制当前状态并随机化未知信息
            Player[] sim = copyPlayers(current);
            // 简化模拟：执行行动后随机进行10轮对局
            applyAction(sim, selfIdx, action);
            for (int round = 0; round < 10; round++) {
                for (int i = 0; i < sim.length; i++) {
                    if (!sim[i].alive) continue;
                    String act = greedyAction(sim, i);
                    applyAction(sim, i, act);
                }
            }
            if (sim[selfIdx].alive && isWinning(sim, selfIdx)) wins++;
        }
        return (double) wins / simCount;
    }

    static Player[] copyPlayers(Player[] src) {
        Player[] dst = new Player[src.length];
        for (int i = 0; i < src.length; i++) {
            dst[i] = new Player(src[i].role);
            dst[i].hp = src[i].hp;
            dst[i].maxHp = src[i].maxHp;
            dst[i].alive = src[i].alive;
            for (Card c : src[i].hand) dst[i].hand.add(new Card(c.type));
        }
        return dst;
    }

    static void applyAction(Player[] all, int actorIdx, String action) {
        if (action == null) return;
        Player actor = all[actorIdx];
        if (action.startsWith("SHA->")) {
            int target = Integer.parseInt(action.substring(5));
            // 目标尝试出闪
            boolean dodged = false;
            for (int i = 0; i < all[target].hand.size(); i++) {
                if (all[target].hand.get(i).type == CardType.SHAN) {
                    all[target].hand.remove(i);
                    dodged = true;
                    break;
                }
            }
            if (!dodged) all[target].hp--;
        } else if (action.startsWith("TAO->")) {
            actor.hp = Math.min(actor.maxHp, actor.hp + 1);
        } else if (action.startsWith("JUEDOU->")) {
            int target = Integer.parseInt(action.substring(8));
            // 简化：双方各扣1血
            actor.hp--; all[target].hp--;
        } else if (action.equals("WUZHONG")) {
            // 摸两张牌（简化）
            actor.hand.add(new Card(CardType.SHA));
            actor.hand.add(new Card(CardType.SHAN));
        }
        // 清理死亡角色
        for (Player p : all) if (p.hp <= 0) p.alive = false;
    }

    static boolean isWinning(Player[] all, int selfIdx) {
        // 简化胜利条件：主公存活且反贼全灭
        boolean zhuAlive = false;
        int fanAlive = 0;
        for (Player p : all) {
            if (!p.alive) continue;
            if (p.role == Role.ZHU) zhuAlive = true;
            if (p.role == Role.FAN) fanAlive++;
        }
        return zhuAlive && fanAlive == 0;
    }

    public static void main(String[] args) {
        Player[] players = new Player[4];
        players[0] = new Player(Role.ZHU);
        players[1] = new Player(Role.ZHONG);
        players[2] = new Player(Role.FAN);
        players[3] = new Player(Role.FAN);

        // 初始手牌
        players[0].hand.add(new Card(CardType.SHA));
        players[0].hand.add(new Card(CardType.TAO));
        players[0].hand.add(new Card(CardType.SHAN));
        players[2].hand.add(new Card(CardType.SHA));
        players[2].hand.add(new Card(CardType.SHAN));

        String action = greedyAction(players, 0);
        System.out.println("主公贪心最优行动: " + action);

        if (action != null) {
            double winRate = monteCarloEval(players, 0, action, 1000);
            System.out.println("蒙特卡洛模拟胜率: " + String.format("%.2f%%", winRate * 100));
        }
    }
}

复杂度分析

• 贪心行动选择：$O(H \times N)$，$H$ 为手牌数，$N$ 为玩家数。
• 蒙特卡洛模拟：$O(S \times R \times N \times H)$，$S$ 为模拟次数，$R$ 为每轮模拟回合数。

总结

本文实现了简化版三国杀AI的核心决策模块：贪心策略用于快速评估手牌价值并选择即时最优行动，蒙特卡洛模拟则通过大量随机对局估计长期胜率。实际游戏中还可引入更复杂的因素，如武将技能联动、身份推测、牌堆记忆等，使AI策略更加贴近人类高手。