引言
Threes! 是2014年发布的极简数字合并游戏，玩家在4×4棋盘上滑动数字方块，将相同数字（或1与2）合并为更大数字。与2048不同，Threes的合并规则更精细（1+2=3，3+3=6，6+6=12…），且新方块从边缘生成。本文用Java完整实现Threes游戏引擎，重点讲解两个算法：一是基于贪心策略的AI决策系统，二是利用启发式状态评估函数（单调性+空格数+大数字位置）指导滑动方向选择。
核心算法设计
1. 游戏规则与合并逻辑
- 棋盘为4×4网格，每格为空或含1/2/3/6/12/24/48/96/192/384/768/1536/3072/6144
- 滑动方向时，所有方块向该方向靠拢
- 合并规则：1+2=3，其他相同数字合并翻倍（3+3=6，6+6=12…）
- 每次有效移动后，在滑动方向的反方向边缘随机生成新方块（1/2/3的概率分别为40%/40%/20%）
- 当棋盘满且无法合并时游戏结束
2. 启发式评估函数
AI评估棋盘状态的综合得分：
– 空格数权重：空格越多，未来操作空间越大
– 单调性权重：大数字集中在角落，形成单调递减序列（如2048的蛇形策略）
– 大数字位置权重：最大数字放在角落得分最高
– 平滑度权重：相邻数字差值越小越好，便于后续合并
3. 贪心决策 + 期望最大化
对每个方向模拟执行，计算移动后的期望评估值（考虑新方块生成的概率分布），选择期望值最高的方向。更高级的变体可采用Minimax或Expectimax搜索多层。
完整Java实现
import java.util.*;
/**
* Threes! 游戏引擎：贪心策略 + 启发式状态评估
*/
public class ThreesGame {
static final int SIZE = 4;
static final int EMPTY = 0;
Random rand = new Random(42);
int[][] board;
int score;
boolean gameOver;
// 评估权重（可调的启发式参数）
static final double W_EMPTY = 270.0;
static final double W_MONO = 47.0;
static final double W_SMOOTH = 11.0;
static final double W_MAX_CORNER = 100.0;
static final double W_MERGE = 70.0;
public ThreesGame() {
board = new int[SIZE][SIZE];
spawnTile(); spawnTile(); // 初始两格
}
/**
* 核心合并逻辑：向指定方向滑动
* 返回是否发生了有效移动
*/
boolean move(int dir) {
// dir: 0=上, 1=下, 2=左, 3=右
int[][] prev = copyBoard();
boolean moved = false;
if (dir == 0) moved = moveUp();
else if (dir == 1) moved = moveDown();
else if (dir == 2) moved = moveLeft();
else if (dir == 3) moved = moveRight();
if (moved) {
spawnTileAtEdge(dir);
score += calculateMergeScore(prev, board);
}
gameOver = !hasValidMove();
return moved;
}
boolean moveLeft() {
boolean moved = false;
for (int r=0; r<SIZE; r++) {
int[] row = new int[SIZE];
int idx = 0;
for (int c=0; c<SIZE; c++) if (board[r][c] != EMPTY) row[idx++] = board[r][c];
int[] merged = mergeLine(Arrays.copyOf(row, idx));
Arrays.fill(board[r], EMPTY);
for (int i=0; i<merged.length; i++) board[r][i] = merged[i];
if (merged.length != idx || !Arrays.equals(merged, Arrays.copyOf(row, idx))) moved = true;
}
return moved;
}
boolean moveRight() {
reverseBoardHorizontally();
boolean moved = moveLeft();
reverseBoardHorizontally();
return moved;
}
boolean moveUp() {
transpose();
boolean moved = moveLeft();
transpose();
return moved;
}
boolean moveDown() {
transpose();
boolean moved = moveRight();
transpose();
return moved;
}
/**
* 单行合并逻辑（从左到右）
* Threes规则：1+2=3，相同数字(>=3)合并翻倍
*/
int[] mergeLine(int[] line) {
List<Integer> result = new ArrayList<>();
boolean[] merged = new boolean[line.length];
for (int i=0; i<line.length; i++) {
if (merged[i]) continue;
if (i+1 < line.length && !merged[i+1]) {
// 检查是否可以合并
int a = line[i], b = line[i+1];
if ((a==1 && b==2) || (a==2 && b==1)) {
result.add(3); merged[i]=merged[i+1]=true; continue;
}
if (a >= 3 && a == b) {
result.add(a*2); merged[i]=merged[i+1]=true; continue;
}
}
result.add(line[i]);
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
/** 在滑动方向的反方向边缘生成新方块 */
void spawnTileAtEdge(int dir) {
List<int[]> candidates = new ArrayList<>();
if (dir == 0) { // 上滑 -> 底部生成
for (int c=0; c<SIZE; c++) if (board[SIZE-1][c]==EMPTY) candidates.add(new int[]{SIZE-1,c});
} else if (dir == 1) { // 下滑 -> 顶部生成
for (int c=0; c<SIZE; c++) if (board[0][c]==EMPTY) candidates.add(new int[]{0,c});
} else if (dir == 2) { // 左滑 -> 右侧生成
for (int r=0; r<SIZE; r++) if (board[r][SIZE-1]==EMPTY) candidates.add(new int[]{r,SIZE-1});
} else if (dir == 3) { // 右滑 -> 左侧生成
for (int r=0; r<SIZE; r++) if (board[r][0]==EMPTY) candidates.add(new int[]{r,0});
}
if (candidates.isEmpty()) return;
int[] pos = candidates.get(rand.nextInt(candidates.size()));
double p = rand.nextDouble();
board[pos[0]][pos[1]] = p < 0.4 ? 1 : (p < 0.8 ? 2 : 3);
}
/** 随机生成初始方块 */
void spawnTile() {
List<int[]> empty = new ArrayList<>();
for (int r=0; r<SIZE; r++) for (int c=0; c<SIZE; c++) if (board[r][c]==EMPTY) empty.add(new int[]{r,c});
if (empty.isEmpty()) return;
int[] pos = empty.get(rand.nextInt(empty.size()));
board[pos[0]][pos[1]] = rand.nextDouble() < 0.7 ? 1 : 2;
}
/**
* 启发式状态评估函数
*/
double evaluateBoard(int[][] b) {
double score = 0;
// 1. 空格数奖励
int emptyCount = countEmpty(b);
score += W_EMPTY * emptyCount;
// 2. 单调性（Snake Pattern）：大数字在角落形成单调序列
score += W_MONO * calculateMonotonicity(b);
// 3. 平滑度：相邻格子差值倒数和
score += W_SMOOTH * calculateSmoothness(b);
// 4. 最大数字在角落奖励
score += W_MAX_CORNER * maxInCorner(b);
// 5. 可合并对数奖励
score += W_MERGE * countMergeable(b);
return score;
}
int countEmpty(int[][] b) {
int cnt = 0;
for (int[] row : b) for (int v : row) if (v == EMPTY) cnt++;
return cnt;
}
/**
* 计算单调性：分别评估四个方向的单调性，取最大值
* 目标是大数字集中在某一角落，形成递减序列
*/
double calculateMonotonicity(int[][] b) {
double[] totals = new double[4]; // 左->右, 右->左, 上->下, 下->上
// 行方向
for (int r=0; r<SIZE; r++) {
int current = 0;
while (current < SIZE-1 && b[r][current] != EMPTY) {
int next = current + 1;
while (next < SIZE && b[r][next] == EMPTY) next++;
if (next >= SIZE) break;
if (b[r][current] >= b[r][next]) totals[0] += Math.log(b[r][next]+1) / Math.log(2);
else totals[1] += Math.log(b[r][current]+1) / Math.log(2);
current = next;
}
}
// 列方向
for (int c=0; c<SIZE; c++) {
int current = 0;
while (current < SIZE-1 && b[current][c] != EMPTY) {
int next = current + 1;
while (next < SIZE && b[next][c] == EMPTY) next++;
if (next >= SIZE) break;
if (b[current][c] >= b[next][c]) totals[2] += Math.log(b[next][c]+1) / Math.log(2);
else totals[3] += Math.log(b[current][c]+1) / Math.log(2);
current = next;
}
}
return Math.max(totals[0], totals[1]) + Math.max(totals[2], totals[3]);
}
double calculateSmoothness(int[][] b) {
double smooth = 0;
for (int r=0; r<SIZE; r++) {
for (int c=0; c<SIZE-1; c++) {
if (b[r][c] != EMPTY && b[r][c+1] != EMPTY)
smooth -= Math.abs(valueLog(b[r][c]) - valueLog(b[r][c+1]));
}
}
for (int r=0; r<SIZE-1; r++) {
for (int c=0; c<SIZE; c++) {
if (b[r][c] != EMPTY && b[r+1][c] != EMPTY)
smooth -= Math.abs(valueLog(b[r][c]) - valueLog(b[r+1][c]));
}
}
return smooth;
}
double valueLog(int v) {
if (v <= 2) return v;
return Math.log(v/3.0) / Math.log(2) + 1;
}
double maxInCorner(int[][] b) {
int max = 0;
for (int[] row : b) for (int v : row) max = Math.max(max, v);
if (b[0][0] == max || b[0][SIZE-1] == max || b[SIZE-1][0] == max || b[SIZE-1][SIZE-1] == max)
return 1.0;
return 0.0;
}
int countMergeable(int[][] b) {
int count = 0;
for (int r=0; r<SIZE; r++) {
for (int c=0; c<SIZE; c++) {
if (b[r][c] == EMPTY) continue;
if (c+1<SIZE && canMerge(b[r][c], b[r][c+1])) count++;
if (r+1<SIZE && canMerge(b[r][c], b[r+1][c])) count++;
}
}
return count;
}
boolean canMerge(int a, int b) {
if (a == EMPTY || b == EMPTY) return false;
if ((a==1 && b==2) || (a==2 && b==1)) return true;
return a >= 3 && a == b;
}
/**
* AI决策：对四个方向计算期望评估值，选择最优
*/
int getBestMove() {
double bestScore = Double.NEGATIVE_INFINITY;
int bestDir = -1;
for (int dir=0; dir<4; dir++) {
int[][] sim = simulateMove(board, dir);
if (sim == null) continue; // 无效移动
// 计算该方向的期望评估值（考虑不同新方块的概率）
double expectedScore = evaluateBoard(sim);
if (expectedScore > bestScore) {
bestScore = expectedScore;
bestDir = dir;
}
}
return bestDir;
}
/** 模拟执行某方向移动，不实际修改board */
int[][] simulateMove(int[][] src, int dir) {
ThreesGame temp = new ThreesGame();
temp.board = copyBoard(src);
boolean moved = temp.move(dir);
return moved ? temp.board : null;
}
boolean hasValidMove() {
for (int dir=0; dir<4; dir++) {
ThreesGame temp = new ThreesGame();
temp.board = copyBoard(board);
if (temp.move(dir)) return true;
}
return false;
}
int calculateMergeScore(int[][] before, int[][] after) {
int sumBefore = 0, sumAfter = 0;
for (int r=0; r<SIZE; r++) {
for (int c=0; c<SIZE; c++) {
sumBefore += before[r][c];
sumAfter += after[r][c];
}
}
return sumAfter - sumBefore;
}
int[][] copyBoard(int[][] src) {
int[][] dst = new int[SIZE][SIZE];
for (int i=0; i<SIZE; i++) System.arraycopy(src[i], 0, dst[i], 0, SIZE);
return dst;
}
int[][] copyBoard() { return copyBoard(board); }
void transpose() {
for (int r=0; r<SIZE; r++)
for (int c=r+1; c<SIZE; c++) {
int t = board[r][c]; board[r][c] = board[c][r]; board[c][r] = t;
}
}
void reverseBoardHorizontally() {
for (int r=0; r<SIZE; r++)
for (int c=0; c<SIZE/2; c++) {
int t = board[r][c]; board[r][c] = board[r][SIZE-1-c]; board[r][SIZE-1-c] = t;
}
}
void printBoard() {
System.out.println("Score: " + score);
for (int[] row : board) {
for (int v : row) System.out.printf(v==0?" . ":"%4d ", v);
System.out.println();
}
System.out.println();
}
void runAI(int maxMoves) {
System.out.println("=== Threes! AI 开始 ===");
printBoard();
for (int i=0; i<maxMoves && !gameOver; i++) {
int dir = getBestMove();
if (dir < 0) break;
String[] names = {"上","下","左","右"};
System.out.println("第"+(i+1)+"步: " + names[dir]);
move(dir);
printBoard();
}
System.out.println("Game Over! Final Score: " + score);
}
public static void main(String[] args) {
new ThreesGame().runAI(1000);
}
}
复杂度分析
- 单次移动：遍历4行/列，每行合并
O(SIZE)，总时间O(SIZE²) = O(16)，空间O(SIZE)。 - 启发式评估：计算单调性、平滑度等需遍历整个棋盘，时间
O(SIZE²)，空间O(1)。 - AI决策：需模拟4个方向，每个方向一次评估
O(SIZE²)，总时间O(4×SIZE²) = O(64)，每步可在微秒级完成。若扩展为两层Expectimax搜索，复杂度变为O(4² × SIZE²)。
总结
本文实现了Threes!的完整游戏引擎与AI决策系统：独特的1+2=3合并规则、边缘生成机制、以及基于空格数+单调性+平滑度+角落最大值的启发式评估。该AI采用贪心策略每步选择评估值最高的方向，在Threes中可达到较高分数。读者可进一步实现Expectimax多层搜索，或引入神经网络学习更优的评估函数权重。
