一、拱猪是一个”负分游戏”
拱猪（Black Lady / Hearts 家族）是规避型纸牌游戏：所有分牌都是负分。红桃各 −1（或在某些规则里为 0），黑桃 Q（猪）−13，方块 J（羊）+10 等。游戏目标是让总分尽量接近 0，最好为正——也就是”别吃分牌”。
这带来了和传统得分型游戏完全相反的算法特性：
- 策略目标是最小化负分，而非最大化正分。如果直接把分数取反当”收益”，会导致”宁可让对手吃 26 分”这种极端打法，而这在实际规则里往往真的成立（”收全红”变体）。所以必须显式的做零和归一化。
- 每一张牌的边际风险是可计算的。给定剩余牌，每张牌的”被吃概率”可以从已知信息推断，因此期望损失最小化是可解析的。
- 残局可完全求解。牌数少时可以用精确的零和博弈求解（Alpha-Beta 或 Minimax），这是验证启发式策略质量的最佳手段。
本文实现：期望损失模型 + 精确残局求解器 + 两者对比。
二、规则简化与建模
为了聚焦算法，本文采用拱猪的核心双人残局规则：
- 每轮两人各出一张牌，花色必须跟随（无该花色则可任意垫）。
- 领出者出牌决定花色，另一方必须跟同花色；无法跟则任意出。
- 同花色中更大者赢得本轮，赢家吃下本轮所有分牌，并领出下一轮。
- 分牌：黑桃 Q = −13；红桃每张 = −1；其余 0 分。
- 终局：所有牌出完，得分高者（负分少者）获胜。
关键约定：谁赢本轮谁吃分。这让”故意输掉本轮”成为核心策略——因为输家不吃分。
三、算法核心一：期望损失模型（中局决策）
3.1 风险的定义
对当前要出的一张牌 c，定义它的期望损失：
EV(c) = Σ_p P(本轮我赢 | 我出 c, 对手出 p) × loss(p, c)
其中 loss 是本轮所有分牌的负分总和。难点在 P(本轮我赢)：它取决于对手出什么牌，而对手的牌未知。
3.2 用”已知信息”替代”未知枚举”
与其枚举对手全部可能手牌（组合爆炸），不如利用三件事：
- 对手是否还有该花色：从已出牌记录可以精确推出（初始 13 张/花色，减去自己手里和已出的）。
- 对手手牌数：公开可见。
- 本花色的最大剩余牌：若自己出的牌是该花色当前最大，则只有对手持有更大牌时才可能输——而这个事件概率可从”未见牌”推断。
于是 EV(c) 可以写成两层决策：
EV(c) = P(对手无法跟花色) × EV(垫牌情形)
+ P(对手跟花色) × E[本轮结果 | 对手跟牌]
其中第二项用”未见大牌密度”来估：
P(我赢) = 1 − P(对手持有更大的同花色牌)
≈ 1 − (未见更大牌数 / 未见该花色总数)^对手手牌数
这个近似在牌数多时准确，牌数少时会有偏差——这正是需要精确求解器的原因。
3.3 决策规则
选择 EV(c) 最大的牌（即期望损失最小）。但有一个硬约束优先级：
1. 若手中有"绝对安全牌"（该花色已无更大牌存活），优先出它
2. 否则选 EV 最优
3. 若所有牌都会吃分，选"吃分最少"的
这个分层比纯 EV 更稳定：安全牌是确定性零损失，不该被期望值的浮点噪声影响。
四、算法核心二：残局精确求解
当剩余牌数 ≤ 8 时，可以用 Alpha-Beta 精确求解（无近似）：
- 状态 = (剩余手牌集合 A, B, 已出牌记录, 当前轮状态, 领出方)。
- 由于剩余牌少，状态空间可控（≤ 8 张牌，
C(8,4) × 4!级别）。 - 求解返回精确的终局分差，可作为评估中局启发式策略的基准。
这给出一个很有价值的实验：把”精确求得的最优决策”与”启发式决策”逐手对比，量化启发式的失误率。
五、项目结构
hearts/
├── pom.xml
└── src/main/java/com/example/hearts/
├── Suit.java 花色
├── Card.java 牌（花色 + 点数）
├── CardSet.java 牌集（位掩码）
├── Trick.java 一轮的状态
├── HeartsState.java 对局状态与转移
├── ExpectedLossAI.java 期望损失启发式
├── ExactSolver.java 残局 Alpha-Beta 精确解
└── Main.java 自对弈 + 精度对比
六、完整实现
6.1 花色与牌
package com.example.hearts;
/** 花色。索引 0..3 固定，便于做位运算。 */
public enum Suit {
CLUB(0, "梅花"), DIAMOND(1, "方块"), HEART(2, "红桃"), SPADE(3, "黑桃");
public final int idx;
public final String cn;
Suit(int idx, String cn) {
this.idx = idx;
this.cn = cn;
}
public static Suit of(int idx) {
return values()[idx];
}
}
package com.example.hearts;
/** 一张牌。rank 1..13（A=1, K=13）。 */
public final class Card implements Comparable<Card> {
public final Suit suit;
public final int rank;
public Card(Suit suit, int rank) {
this.suit = suit;
this.rank = rank;
}
/** 位编号：suit * 13 + (rank - 1)，范围 0..51。 */
public int bitIndex() {
return suit.idx * 13 + (rank - 1);
}
public long bit() {
return 1L << bitIndex();
}
public static Card fromBitIndex(int idx) {
return new Card(Suit.of(idx / 13), idx % 13 + 1);
}
/** 是否分牌。 */
public boolean isPenalty() {
return suit == Suit.HEART || (suit == Suit.SPADE && rank == 12);
}
/** 罚分（负值）。黑桃Q = -13，红桃每张 = -1。 */
public int penalty() {
if (suit == Suit.SPADE && rank == 12) return -13;
if (suit == Suit.HEART) return -1;
return 0;
}
@Override
public int compareTo(Card o) {
if (suit != o.suit) return Integer.compare(suit.idx, o.suit.idx);
return Integer.compare(rank, o.rank);
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Card c)) return false;
return c.suit == suit && c.rank == rank;
}
@Override
public int hashCode() {
return bitIndex();
}
@Override
public String toString() {
String[] r = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
return suit.cn + r[rank - 1];
}
}
6.2 牌集（位掩码）
package com.example.hearts;
import java.util.ArrayList;
import java.util.List;
/** 用 long 的 52 位表示一组牌。集合运算全部是位运算，O(1)。 */
public final class CardSet {
public static final long ALL = (1L << 52) - 1;
public static final long HEARTS = 0x1FFFL << 26; // suit 2 的 13 张
public static final long SPADE_QUEEN = 1L << (3 * 13 + 11);
private CardSet() {}
/** 某花色的全部牌位掩码。 */
public static long suitMask(Suit s) {
return 0x1FFFL << (s.idx * 13);
}
public static int size(long set) {
return Long.bitCount(set);
}
public static List<Card> toList(long set) {
List<Card> out = new ArrayList<>();
long s = set;
while (s != 0) {
int idx = Long.numberOfTrailingZeros(Long.lowestOneBit(s));
s &= s - 1;
out.add(Card.fromBitIndex(idx));
}
return out;
}
/** 某花色在集合中的牌。 */
public static long ofSuit(long set, Suit suit) {
return set & suitMask(suit);
}
/** 集合中所有分牌的罚分总和（负值）。 */
public static int penaltyOf(long set) {
int p = 0;
long s = set;
while (s != 0) {
int idx = Long.numberOfTrailingZeros(Long.lowestOneBit(s));
s &= s - 1;
p += Card.fromBitIndex(idx).penalty();
}
return p;
}
/** 集合中的最大 rank（单花色集合上用）。显式遍历，最多 13 次，成本可忽略。 */
public static int maxRank(long set) {
int best = -1;
long s = set;
while (s != 0) {
int idx = Long.numberOfTrailingZeros(Long.lowestOneBit(s));
s &= s - 1;
best = Math.max(best, Card.fromBitIndex(idx).rank);
}
return best;
}
public static String describe(long set) {
return toList(set).toString();
}
}
这里没有用”位索引取最高位”的技巧。位索引是全局 suit*13 + rank-1，跨花色时最高位对应的 rank 会被花色偏移干扰，直接算会出错。显式遍历虽然慢一点，但正确性无歧义——在这类位掩码结构里，把”跨花色的全局索引”当”花色内 rank”用，是最常见的隐性 bug 来源。
6.3 一轮与对局状态
package com.example.hearts;
import java.util.ArrayList;
import java.util.List;
/** 一轮（trick）的状态。 */
public final class Trick {
public final Suit leadSuit;
public final int leader; // 领出方 0/1
public Card firstCard = null; // 领出牌
public Card secondCard = null; // 跟随牌
public Trick(int leader) {
this.leader = leader;
this.leadSuit = null; // 花色由第一张牌决定，见 leadSuitOf
}
public boolean isComplete() {
return firstCard != null && secondCard != null;
}
public long cardsMask() {
long m = 0;
if (firstCard != null) m |= firstCard.bit();
if (secondCard != null) m |= secondCard.bit();
return m;
}
/** 本轮谁赢。 */
public int winner() {
if (!isComplete()) return -1;
Suit s = firstCard.suit;
boolean secondFollows = secondCard.suit == s;
if (secondFollows) {
return secondCard.rank > firstCard.rank ? (1 - leader) : leader;
}
// 未跟花色，领出方直接赢
return leader;
}
/** 本轮吃下的罚分（负值），由赢家承受。 */
public int penalty() {
return firstCard.penalty() + secondCard.penalty();
}
}
package com.example.hearts;
import java.util.ArrayList;
import java.util.List;
/** 对局状态：双方手牌、已完成轮次的吃分记录、当前轮。 */
public final class HeartsState {
public long[] hands = new long[2];
public int[] penalties = new int[2];
public int nextLeader = 0;
public Trick trick = null;
/** 已打出的所有牌（公开信息）。 */
public long played = 0;
public HeartsState() {}
public HeartsState copy() {
HeartsState s = new HeartsState();
s.hands[0] = hands[0];
s.hands[1] = hands[1];
s.penalties[0] = penalties[0];
s.penalties[1] = penalties[1];
s.nextLeader = nextLeader;
s.played = played;
if (trick != null) {
Trick t = new Trick(trick.leader);
t.firstCard = trick.firstCard;
t.secondCard = trick.secondCard;
s.trick = t;
}
return s;
}
/** 某方是否还有指定花色。 */
public boolean hasSuit(int player, Suit suit) {
return (hands[player] & CardSet.suitMask(suit)) != 0;
}
/**
* 某方在给定局面下的合法出牌。
* 花色跟随规则：若有领出花色则必须跟，否则任意。
*/
public List<Card> legalCards(int player) {
List<Card> out = new ArrayList<>();
long hand = hands[player];
if (hand == 0) return out;
if (trick != null && trick.firstCard != null) {
Suit lead = trick.firstCard.suit;
long follow = hand & CardSet.suitMask(lead);
if (follow != 0) return CardSet.toList(follow);
}
return CardSet.toList(hand);
}
/** 出牌并推进状态。 */
public void play(int player, Card card) {
hands[player] &= ~card.bit();
played |= card.bit();
if (trick == null) {
trick = new Trick(player);
trick.firstCard = card;
} else {
trick.secondCard = card;
int w = trick.winner();
penalties[w] += trick.penalty();
nextLeader = w;
trick = null;
}
}
public boolean isTerminal() {
return hands[0] == 0 && hands[1] == 0;
}
public int totalPenalty() {
return penalties[0] + penalties[1];
}
/** 分差：正数表示玩家 0 领先。 */
public int diff() {
return penalties[1] - penalties[0];
}
}
6.4 期望损失启发式
package com.example.hearts;
import java.util.List;
/**
* 期望损失 AI。
* 核心思想：估算每张牌的期望罚分，选最小者。
* 三层结构：安全牌优先 → 期望值决策 → 兜底最少损失。
*/
public final class ExpectedLossAI {
private final int me;
public ExpectedLossAI(int me) {
this.me = me;
}
/** 选择要出的牌。 */
public Card choose(HeartsState st) {
int opp = 1 - me;
List<Card> legal = st.legalCards(me);
if (legal.size() == 1) return legal.get(0);
// 第一层：绝对安全牌。若该牌是本花色当前最大，且更大牌已全部出现，则零风险。
for (Card c : legal) {
if (isAbsolutelySafe(st, c, opp)) return c;
}
// 第二层：期望损失最小
Card best = legal.get(0);
double bestEv = Double.NEGATIVE_INFINITY;
for (Card c : legal) {
double ev = expectedValue(st, c, opp);
if (ev > bestEv) {
bestEv = ev;
best = c;
}
}
return best;
}
/**
* 绝对安全：本花色内不存在"仍存活且比我大的牌"。
* 存活 = 不在我手里、不在已出牌里。
*/
private boolean isAbsolutelySafe(HeartsState st, Card c, int opp) {
long unknown = CardSet.ALL & ~st.hands[me] & ~st.played;
long bigger = 0;
for (long s = unknown; s != 0; ) {
int idx = Long.numberOfTrailingZeros(Long.lowestOneBit(s));
s &= s - 1;
Card u = Card.fromBitIndex(idx);
if (u.suit == c.suit && u.rank > c.rank) bigger |= u.bit();
}
if (bigger != 0) return false;
// 还要确认对手确实跟不了更大牌：若对手手里没有该花色，则必定安全
// （本实现里 bigger == 0 已足够：场上已无更大牌）
return true;
}
/**
* 期望值（越大越好，因为是负分游戏）。
*
* EV = P(对手跟不出花色) * E[情况A] + P(对手跟得出) * E[情况B]
*
* 情况A：对手垫牌，我必赢本轮，吃下本轮全部罚分 + 对手垫的分牌
* 情况B：对手跟牌，胜负取决于牌面比较
*/
private double expectedValue(HeartsState st, Card c, int opp) {
Suit lead = st.trick != null && st.trick.firstCard != null
? st.trick.firstCard.suit : c.suit;
long oppHand = st.hands[opp];
long oppSuit = oppHand & CardSet.suitMask(lead);
int oppSize = CardSet.size(oppHand);
int oppSuitCount = CardSet.size(oppSuit);
// 若我是领出方，对手必然"面对"我的花色
boolean iLead = (st.trick == null || st.trick.firstCard == null);
double pFollow = oppSize == 0 ? 0 : (double) oppSuitCount / oppSize;
if (iLead && oppSuitCount > 0) pFollow = 1.0; // 有该花色就必须跟
// 计算两种情形下的罚分承受
int myPenaltyIfWin = c.penalty();
int oppPenaltyIfWin = 0;
// 对手的牌未知，用"未见牌"的平均罚分估计
long unknown = CardSet.ALL & ~st.hands[0] & ~st.hands[1] & ~st.played;
double avgUnknownPenalty = unknown == 0 ? 0
: (double) CardSet.penaltyOf(unknown) / CardSet.size(unknown);
// 情况 B：对手跟牌。我赢的概率取决于是否有更大的同花色牌
double pIWin;
if (iLead) {
// 我领出 c，对手若跟则必然有同花色牌，比较大小
long biggerInOpp = oppSuit & biggerMask(c);
double pOppHasBigger = oppSuitCount == 0 ? 0
: Math.min(1.0, (double) CardSet.size(biggerInOpp) / oppSuitCount);
pIWin = 1.0 - pOppHasBigger;
} else {
// 我跟牌（或垫牌），当前领出牌为 trick.firstCard
Card leadCard = st.trick.firstCard;
if (c.suit != leadCard.suit) {
pIWin = 0.0; // 垫牌必输
} else {
pIWin = c.rank > leadCard.rank ? 1.0 : 0.0;
}
}
double lossIfIWin = myPenaltyIfWin + avgUnknownPenalty;
double lossIfILose = c.penalty() * 0.0; // 我不吃分
double evWin = -lossIfIWin;
double evLose = 0.0;
double evFollow = pIWin * evWin + (1 - pIWin) * evLose;
// 对手跟不出：我只能赢（领出方）或必然输（跟牌方垫牌）
double evNoFollow = iLead ? evWin : evLose;
return pFollow * evFollow + (1 - pFollow) * evNoFollow;
}
private long biggerMask(Card c) {
long m = 0;
for (int r = c.rank + 1; r <= 13; r++) {
m |= new Card(c.suit, r).bit();
}
return m;
}
}
6.5 残局精确求解
package com.example.hearts;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 残局精确求解器（Alpha-Beta）。
* 状态空间小（剩余牌 ≤ 8），可完全求解，用作启发式的基准。
* 返回的是"从 me 视角的精确终局分差"。
*/
public final class ExactSolver {
private final int me;
private long nodes = 0;
private final Map<Long, Integer> tt = new HashMap<>();
public ExactSolver(int me) {
this.me = me;
}
public long nodes() { return nodes; }
public int solve(HeartsState st) {
return search(st, Integer.MIN_VALUE + 1, Integer.MAX_VALUE - 1);
}
/** 返回分差（玩家0 视角），内部用玩家0 最大化。 */
private int search(HeartsState st, int alpha, int beta) {
nodes++;
if (st.isTerminal()) {
return st.penalties[1] - st.penalties[0];
}
long key = hashKey(st);
Integer cached = tt.get(key);
if (cached != null) return cached;
int player = st.trick == null || st.trick.firstCard == null
? st.nextLeader
: 1 - st.trick.leader;
List<Card> legal = st.legalCards(player);
int best = player == 0 ? Integer.MIN_VALUE + 1 : Integer.MAX_VALUE - 1;
for (Card c : legal) {
HeartsState next = st.copy();
next.play(player, c);
int value = search(next, alpha, beta);
if (player == 0) {
if (value > best) best = value;
if (value > alpha) alpha = value;
} else {
if (value < best) best = value;
if (value < beta) beta = value;
}
if (alpha >= beta) break;
}
tt.put(key, best);
return best;
}
/**
* 状态键：双手牌 + 已出牌 + 当前轮的两张牌 + 领出方。
* 用一个 long 拼接（手牌各 52 位放不下，故用哈希组合）。
*/
private long hashKey(HeartsState st) {
long h = st.hands[0] * 0x9E3779B97F4A7C15L;
h ^= Long.rotateLeft(st.hands[1], 17) * 0xC2B2AE3D27D4EB4FL;
h ^= Long.rotateLeft(st.played, 31);
if (st.trick != null) {
h ^= st.trick.leader * 0x85EBCA6BL;
if (st.trick.firstCard != null) h ^= st.trick.firstCard.bit() * 0x27D4EB2FL;
if (st.trick.secondCard != null) h ^= st.trick.secondCard.bit() * 0x165667B1L;
} else {
h ^= st.nextLeader * 0xA24BAED4963EE407L;
}
return h;
}
}
6.6 入口：启发式 vs 精确解
package com.example.hearts;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class Main {
/** 从全副牌中随机发 2×n 张，构成一个残局。 */
static HeartsState randomEndgame(int cardsPerPlayer, long seed) {
Random rnd = new Random(seed);
List<Card> all = CardSet.toList(CardSet.ALL);
Collections.shuffle(all, rnd);
HeartsState st = new HeartsState();
for (int i = 0; i < cardsPerPlayer; i++) {
st.hands[0] |= all.get(i * 2).bit();
st.hands[1] |= all.get(i * 2 + 1).bit();
}
st.nextLeader = rnd.nextInt(2);
return st;
}
public static void main(String[] args) {
int cardsPerPlayer = 6; // 12 张牌的残局，规模够小，可精确求解
int trials = 200;
int heuristicDiffSum = 0;
int exactDiffSum = 0;
long totalNodes = 0;
int agree = 0;
for (int t = 0; t < trials; t++) {
HeartsState base = randomEndgame(cardsPerPlayer, t);
// 1) 启发式对局：双方都用期望损失 AI
HeartsState h = base.copy();
ExpectedLossAI ai0 = new ExpectedLossAI(0);
ExpectedLossAI ai1 = new ExpectedLossAI(1);
while (!h.isTerminal()) {
int player = h.trick == null ? h.nextLeader : 1 - h.trick.leader;
Card c = (player == 0 ? ai0 : ai1).choose(h);
h.play(player, c);
}
heuristicDiffSum += h.diff();
// 2) 精确求解同一初始局面
ExactSolver solver = new ExactSolver(0);
exactDiffSum += solver.solve(base);
totalNodes += solver.nodes();
// 3) 比较首手决策是否一致
int firstPlayer = base.trick == null ? base.nextLeader : 1 - base.trick.leader;
Card heurPick = (firstPlayer == 0 ? ai0 : ai1).choose(base);
Card exactPick = bestBySolver(base, solver, firstPlayer);
if (heurPick.equals(exactPick)) agree++;
}
System.out.println("=== 残局实验：" + cardsPerPlayer + " 张/人，共 " + trials + " 局 ===");
System.out.printf("启发式平均分差（玩家0视角）: %.2f%n", heuristicDiffSum * 1.0 / trials);
System.out.printf("精确解平均分差（玩家0视角）: %.2f%n", exactDiffSum * 1.0 / trials);
System.out.printf("首手决策一致率: %.1f%%%n", agree * 100.0 / trials);
System.out.printf("精确求解平均节点数: %.0f%n", totalNodes * 1.0 / trials);
}
/**
* 用求解器遍历首手合法牌，选出对当前玩家最优的那张。
*
* 注意视角不变量：solver.solve() 永远返回"玩家 0 视角的分差"。
* 因此玩家 0 要挑"分差最大"，玩家 1 要挑"分差最小"——两个方向必须相反。
* 若写成同向，AI 会稳定地选错牌，而且不会抛任何异常，极难排查。
*/
static Card bestBySolver(HeartsState st, ExactSolver solver, int player) {
List<Card> legal = st.legalCards(player);
Card best = legal.get(0);
int bestVal = player == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
for (Card c : legal) {
HeartsState next = st.copy();
next.play(player, c);
int v = solver.solve(next); // 始终是"玩家0 视角"的分差
if (player == 0) {
if (v > bestVal) { bestVal = v; best = c; } // 玩家0 最大化分差
} else {
if (v < bestVal) { bestVal = v; best = c; } // 玩家1 最小化分差
}
}
return best;
}
}
七、复杂度分析
- 期望损失决策：对每张合法牌（≤ 13）计算一次 EV，每次 EV 需要扫一遍未见牌（≤ 52）。总计
O(13 × 52) = O(1)常数级。 - 精确求解：状态数上界约为
C(2n, n) × 2^n（n为每人手牌数），n=6时约924 × 64 ≈ 6 万，配合 Alpha-Beta 与置换表实测平均节点数在数千量级。 - 牌集运算：所有集合操作（取花色、求罚分、取最高牌）都是 64 位位运算，单次
O(1)；位掩码让”是否还有某花色”的判定从遍历变成一次&。 - 空间：状态仅 2 个
long手牌 + 若干整数，置换表为HashMap<Long,Integer>，n=6时不超过几万条目。
八、小结
拱猪的算法价值在于它把”负面目标”处理得极为干净：
- 零和归一是必须的。负分游戏里直接取反做最大化，会让 AI 追求”对手灾难”而不是”自己安全”，这类偏差在训练或对弈中很难被发现。
- 分层决策比纯期望更稳。安全牌是确定性零损失，不该被浮点期望的噪声左右；先判安全、再算期望，是工程上更可靠的顺序。
- 残局求解器是最好的验证工具。它给你一个精确基准，让”启发式的失误率”变成可量化的数字，而不是靠手感判断好坏。
