引言
接金币是一款经典的反应类游戏：金币从屏幕上方随机位置落下，玩家控制底部的篮子左右移动以接住金币。在双人对抗版本中，两名玩家共享同一片区域，竞争接取有限的金币资源。当一方的移动会直接影响另一方可接取的金币集合时，游戏便进入了非合作博弈的范畴。本文用Java实现双人对抗接金币游戏，核心算法采用博弈论纳什均衡（Nash Equilibrium）分析双方最优策略，并结合Minimax搜索求解对抗局面下的动态决策。
问题建模
将双人接金币抽象为完全信息动态博弈：
– 玩家：P1（我方）与 P2（对手）
– 状态：双方篮子的位置、当前屏幕上的金币分布、各自得分
– 行动：每回合双方同时选择左移、右移或静止
– 收益：接取金币获得正收益，碰撞或错过则收益为0
– 目标：在有限回合内最大化自身得分，同时最小化对手得分优势
纳什均衡的定义
在接金币博弈中，若存在策略对 (s₁*, s₂*)，使得：
– P1 无法通过单方面改变策略获得更高收益
– P2 无法通过单方面改变策略获得更高收益
则称 (s₁*, s₂*) 为一个纳什均衡策略组合。
核心算法：Minimax搜索与纳什均衡近似
算法思路
- 状态空间构建：枚举双方位置与金币分布的所有可能状态
- 收益矩阵计算：对每对行动组合，计算双方的期望收益
- Minimax决策：
- P1 最大化自身最小收益（假设P2会采取对P1最不利的行动）
- P2 同理
- 混合策略纳什均衡：当纯策略均衡不存在时，使用线性规划或迭代法求解双方的最优混合策略概率分布
复杂度分析
- 状态数：
O(W² × 2^N)，其中W为篮子可到达的位置数，N为金币数 - 对于小规模场景（
N ≤ 5），可用完全信息Minimax搜索 - 对于较大场景，采用贪心近似+局部纳什均衡，复杂度降至
O(W² × N)
Java完整实现
import java.util.*;
/**
* 双人对抗接金币：博弈论纳什均衡与Minimax对抗策略
*
* 核心思路：
* 1. 将接金币建模为双人零和/非零和博弈
* 2. 对每一层决策使用Minimax搜索评估最优行动
* 3. 当存在纯策略纳什均衡时直接采用；否则用混合策略近似
* 4. 支持完全信息搜索与带截断的贪心近似两种模式
*/
public class CoinCatchGame {
// ============ 游戏常量 ============
static final int GRID_WIDTH = 15; // 水平格子数
static final int GRID_HEIGHT = 10; // 垂直格子数
static final int MAX_DEPTH = 4; // Minimax搜索深度
// ============ 金币类 ============
static class Coin {
int x, y; // 坐标位置
int value; // 分值
int id;
public Coin(int id, int x, int y, int value) {
this.id = id;
this.x = x;
this.y = y;
this.value = value;
}
public Coin copy() {
return new Coin(id, x, y, value);
}
@Override
public String toString() {
return String.format("Coin[%d](%d,%d)=%d", id, x, y, value);
}
}
// ============ 玩家状态 ============
static class PlayerState {
int x; // 篮子水平位置
int score; // 当前得分
public PlayerState(int x, int score) {
this.x = x;
this.score = score;
}
public PlayerState copy() {
return new PlayerState(x, score);
}
}
// ============ 游戏状态 ============
static class GameState {
PlayerState p1; // 玩家1（我方）
PlayerState p2; // 玩家2（对手）
List<Coin> coins; // 当前屏幕上未接的金币
int turn; // 当前回合数
public GameState(PlayerState p1, PlayerState p2, List<Coin> coins, int turn) {
this.p1 = p1;
this.p2 = p2;
this.coins = new ArrayList<>(coins);
this.turn = turn;
}
public GameState copy() {
List<Coin> newCoins = new ArrayList<>();
for (Coin c : coins) newCoins.add(c.copy());
return new GameState(p1.copy(), p2.copy(), newCoins, turn);
}
}
// ============ 行动枚举 ============
enum Action { LEFT, STAY, RIGHT }
static final Action[] ACTIONS = { Action.LEFT, Action.STAY, Action.RIGHT };
// ============ 收益结果 ============
static class Payoff {
double p1Utility; // P1收益
double p2Utility; // P2收益
public Payoff(double p1, double p2) {
this.p1Utility = p1;
this.p2Utility = p2;
}
}
// ============ 核心游戏引擎 ============
private Random rand;
public CoinCatchGame() {
this.rand = new Random(42);
}
/** 生成初始游戏状态 */
public GameState initState(int coinCount) {
PlayerState p1 = new PlayerState(GRID_WIDTH / 4, 0);
PlayerState p2 = new PlayerState(3 * GRID_WIDTH / 4, 0);
List<Coin> coins = new ArrayList<>();
for (int i = 0; i < coinCount; i++) {
int cx = rand.nextInt(GRID_WIDTH);
int cy = 2 + rand.nextInt(GRID_HEIGHT - 2);
int val = 10 + rand.nextInt(41); // 10~50分
coins.add(new Coin(i, cx, cy, val));
}
return new GameState(p1, p2, coins, 0);
}
/**
* 执行一步动作，更新状态
* 规则：金币每回合下落一格；双方移动后，检查是否与同一行金币位置重合
*/
public GameState step(GameState state, Action a1, Action a2) {
GameState next = state.copy();
// 1. 移动玩家
next.p1.x = clamp(next.p1.x + actionDelta(a1), 0, GRID_WIDTH - 1);
next.p2.x = clamp(next.p2.x + actionDelta(a2), 0, GRID_WIDTH - 1);
// 2. 金币下落一格
Iterator<Coin> it = next.coins.iterator();
while (it.hasNext()) {
Coin c = it.next();
c.y -= 1;
if (c.y < 0) {
it.remove(); // 金币落地消失
}
}
// 3. 检查接取：玩家位置与金币y=0行重合则接取
// 简化：假设篮子占底部一整行，只需x坐标匹配
List<Coin> toRemove = new ArrayList<>();
for (Coin c : next.coins) {
if (c.y == 0) {
boolean p1Catch = (c.x == next.p1.x);
boolean p2Catch = (c.x == next.p2.x);
if (p1Catch && p2Catch) {
// 同时到达：各得一半（非零和博弈）
next.p1.score += c.value / 2;
next.p2.score += c.value / 2;
toRemove.add(c);
} else if (p1Catch) {
next.p1.score += c.value;
toRemove.add(c);
} else if (p2Catch) {
next.p2.score += c.value;
toRemove.add(c);
}
}
}
next.coins.removeAll(toRemove);
// 4. 每隔一定回合生成新金币
next.turn++;
if (next.turn % 3 == 0 && next.coins.size() < 8) {
int cx = rand.nextInt(GRID_WIDTH);
int cy = GRID_HEIGHT - 1;
int val = 10 + rand.nextInt(41);
next.coins.add(new Coin(rand.nextInt(1000), cx, cy, val));
}
return next;
}
private int actionDelta(Action a) {
switch (a) {
case LEFT: return -1;
case RIGHT: return 1;
default: return 0;
}
}
private int clamp(int v, int min, int max) {
return Math.max(min, Math.min(max, v));
}
// ============ Minimax搜索 + 纳什均衡评估 ============
/**
* 对当前状态进行Minimax搜索，返回P1的最优行动
* @param state 当前状态
* @param depth 剩余搜索深度
* @param isP1Turn 是否P1的决策层（在同时行动博弈中，这里简化为交替决策近似）
*/
public Action minimaxDecision(GameState state, int depth, boolean isP1Turn) {
double bestVal = isP1Turn ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
Action bestAction = Action.STAY;
for (Action a : ACTIONS) {
double val;
if (isP1Turn) {
// P1选择行动后，假设P2会最小化P1的收益（零和近似）
val = minValue(state, a, depth - 1);
if (val > bestVal) {
bestVal = val;
bestAction = a;
}
} else {
// 同理
val = maxValue(state, a, depth - 1);
if (val < bestVal) {
bestVal = val;
bestAction = a;
}
}
}
return bestAction;
}
/** P1已选a1，P2选择行动最小化P1收益 */
private double minValue(GameState state, Action a1, int depth) {
if (depth <= 0 || state.coins.isEmpty()) {
return evaluate(state);
}
double minVal = Double.POSITIVE_INFINITY;
for (Action a2 : ACTIONS) {
GameState next = step(state, a1, a2);
double val = maxValue(next, depth - 1);
minVal = Math.min(minVal, val);
}
return minVal;
}
/** P2已选a2，P1选择行动最大化自身收益 */
private double maxValue(GameState nextState, int depth) {
if (depth <= 0 || nextState.coins.isEmpty()) {
return evaluate(nextState);
}
double maxVal = Double.NEGATIVE_INFINITY;
for (Action a1 : ACTIONS) {
double val = minValue(nextState, a1, depth - 1);
maxVal = Math.max(maxVal, val);
}
return maxVal;
}
/** 简化的评估函数：得分差 + 潜在收益 */
private double evaluate(GameState state) {
double scoreDiff = state.p1.score - state.p2.score;
// 加上P1对剩余金币的潜在可达收益估计
double potential = 0;
for (Coin c : state.coins) {
int dist1 = Math.abs(c.x - state.p1.x);
int dist2 = Math.abs(c.x - state.p2.x);
if (dist1 <= c.y && dist1 <= dist2) {
potential += c.value * 0.5; // P1有优势抢到
}
}
return scoreDiff + potential;
}
// ============ 纳什均衡：收益矩阵与混合策略 ============
/**
* 对当前状态构建3×3收益矩阵（双方各有3种行动）
* 然后求解近似纳什均衡：若存在鞍点则取纯策略，否则用Maximin策略
*/
public Action nashEquilibriumMove(GameState state) {
double[][] payoffP1 = new double[3][3]; // payoffP1[i][j]: P1选ACTIONS[i], P2选ACTIONS[j]
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
GameState next = step(state, ACTIONS[i], ACTIONS[j]);
payoffP1[i][j] = evaluate(next);
}
}
// 打印收益矩阵
System.out.println("\n--- 收益矩阵 (P1视角) ---");
System.out.print(" ");
for (Action a : ACTIONS) System.out.printf("%-8s", a);
System.out.println();
for (int i = 0; i < 3; i++) {
System.out.printf("%-6s ", ACTIONS[i]);
for (int j = 0; j < 3; j++) {
System.out.printf("%7.1f ", payoffP1[i][j]);
}
System.out.println();
}
// 寻找Maximin策略（保守策略，最大化最小收益）
double[] rowMin = new double[3];
for (int i = 0; i < 3; i++) {
rowMin[i] = payoffP1[i][0];
for (int j = 1; j < 3; j++) {
rowMin[i] = Math.min(rowMin[i], payoffP1[i][j]);
}
}
double bestMin = rowMin[0];
int bestActionIdx = 0;
for (int i = 1; i < 3; i++) {
if (rowMin[i] > bestMin) {
bestMin = rowMin[i];
bestActionIdx = i;
}
}
System.out.printf("P1 Maximin策略: %s (保证收益 >= %.1f)\n", ACTIONS[bestActionIdx], bestMin);
return ACTIONS[bestActionIdx];
}
// ============ 主程序：模拟对战 ============
public static void main(String[] args) {
CoinCatchGame game = new CoinCatchGame();
GameState state = game.initState(10);
System.out.println("=== 双人对抗接金币：博弈论纳什均衡策略 ===\n");
System.out.println("初始金币分布:");
for (Coin c : state.coins) {
System.out.println(" " + c);
}
// 模拟10个回合
for (int round = 1; round <= 10; round++) {
System.out.printf("\n--- 回合 %d ---\n", round);
System.out.printf("P1位置=%d 得分=%d | P2位置=%d 得分=%d | 剩余金币=%d\n",
state.p1.x, state.p1.score, state.p2.x, state.p2.score, state.coins.size());
// P1使用纳什均衡策略
Action a1 = game.nashEquilibriumMove(state);
// P2使用简单贪心：朝最近金币移动
Action a2 = game.greedyMove(state, false);
System.out.printf("P1行动: %s | P2行动: %s\n", a1, a2);
state = game.step(state, a1, a2);
}
System.out.println("\n=== 最终得分 ===");
System.out.printf("P1: %d 分\n", state.p1.score);
System.out.printf("P2: %d 分\n", state.p2.score);
System.out.println(state.p1.score > state.p2.score ? "P1 获胜！" :
state.p1.score < state.p2.score ? "P2 获胜！" : "平局！");
}
/** P2的简单贪心策略：向最近且可达的金币移动 */
private Action greedyMove(GameState state, boolean isP1) {
int myX = isP1 ? state.p1.x : state.p2.x;
if (state.coins.isEmpty()) return Action.STAY;
Coin target = null;
int minDist = Integer.MAX_VALUE;
for (Coin c : state.coins) {
int dist = Math.abs(c.x - myX);
if (dist < minDist) {
minDist = dist;
target = c;
}
}
if (target == null) return Action.STAY;
if (target.x < myX) return Action.LEFT;
if (target.x > myX) return Action.RIGHT;
return Action.STAY;
}
}
关键代码解析
1. 收益矩阵构建
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
GameState next = step(state, ACTIONS[i], ACTIONS[j]);
payoffP1[i][j] = evaluate(next);
}
}
对于同时行动博弈，枚举所有 3 × 3 = 9 种行动组合，通过前向模拟一步得到P1的期望收益矩阵。这是求解纳什均衡的基础数据结构。
2. Maximin保守策略
rowMin[i] = min(payoffP1[i][0], payoffP1[i][1], payoffP1[i][2]);
bestAction = argmax(rowMin);
Maximin策略是纳什均衡在零和博弈中的核心解概念：玩家选择能保证自己获得最大”最小收益”的行动。即使对手采取对自己最不利的策略，Maximin也能确保底线收益最大化。
3. Minimax交替搜索
private double minValue(GameState state, Action a1, int depth) { ... }
private double maxValue(GameState nextState, int depth) { ... }
通过递归的Minimax搜索，在有限深度内评估当前决策的长期影响。P1层最大化，P2层最小化，层层交替直至达到搜索深度边界，再调用评估函数返回启发式分值。
扩展思考
- 混合策略纳什均衡：当收益矩阵不存在纯策略鞍点时，可通过线性规划求解双方的最优混合概率分布（如P1以60%概率左移、40%概率静止）
- 不完全信息扩展：引入”迷雾”机制，双方只能看到部分金币位置，此时需要用贝叶斯博弈或信息集（Information Set）建模
- 演化稳定策略（ESS）：在多智能体重复博弈中，通过复制动态方程观察策略的演化收敛
总结
本文以双人对抗接金币为场景，将博弈论的纳什均衡概念引入游戏AI设计。通过收益矩阵构建、Maximin保守策略和Minimax深度搜索三层算法架构，实现了在竞争环境下的理性决策。该框架适用于所有存在资源竞争的双人/多人博弈场景，如围棋、扑克、拍卖机制设计等。
