游戏简介与算法核心
拼字游戏（Scrabble-like）是经典的文字棋盘游戏，玩家在网格上放置字母牌组成单词以获得分数。本文用Java实现一个拼字游戏AI，讲解Trie树（前缀树）在快速单词验证中的应用，以及贪心策略结合锚点分析来计算每一轮的最优落子。
游戏规则与计分系统
游戏在15×15的棋盘上进行，玩家持有7个字母牌。每回合可以在棋盘上横向或纵向放置一个有效单词，新放置的字母必须与已有字母相连（第一回合除外）。单词的得分是各字母分值之和，加上特殊格子的倍数奖励。
import java.util.*;
/**
* 字母分值表（标准Scrabble分值）
*/
class LetterScores {
private static final Map<Character, Integer> SCORES = new HashMap<>();
static {
"AEIOULNRST".chars().forEach(c -> SCORES.put((char)c, 1));
"DG".chars().forEach(c -> SCORES.put((char)c, 2));
"BCMP".chars().forEach(c -> SCORES.put((char)c, 3));
"FHVWY".chars().forEach(c -> SCORES.put((char)c, 4));
SCORES.put('K', 5);
"JX".chars().forEach(c -> SCORES.put((char)c, 8));
"QZ".chars().forEach(c -> SCORES.put((char)c, 10));
}
public static int getScore(char letter) {
return SCORES.getOrDefault(Character.toUpperCase(letter), 0);
}
}
/**
* 棋盘特殊格子类型
*/
enum SpecialTile {
NORMAL, DOUBLE_LETTER, TRIPLE_LETTER, DOUBLE_WORD, TRIPLE_WORD, CENTER
}
/**
* 棋盘格子
*/
class BoardCell {
char letter = '\0'; // '\0'表示空
SpecialTile special = SpecialTile.NORMAL;
boolean isEmpty() { return letter == '\0'; }
}
/**
* 15×15 拼字游戏棋盘
*/
class ScrabbleBoard {
private static final int SIZE = 15;
private final BoardCell[][] grid = new BoardCell[SIZE][SIZE];
public ScrabbleBoard() {
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
grid[r][c] = new BoardCell();
}
}
setupSpecialTiles();
}
private void setupSpecialTiles() {
// 三重单词分
int[][] tw = {{0,0},{0,7},{0,14},{7,0},{7,14},{14,0},{14,7},{14,14}};
for (int[] p : tw) grid[p[0]][p[1]].special = SpecialTile.TRIPLE_WORD;
// 双重单词分
int[][] dw = {{1,1},{2,2},{3,3},{4,4},{7,7},{10,10},{11,11},{12,12},{13,13},
{1,13},{2,12},{3,11},{4,10},{10,4},{11,3},{12,2},{13,1}};
for (int[] p : dw) grid[p[0]][p[1]].special = SpecialTile.DOUBLE_WORD;
// 三重字母分
int[][] tl = {{1,5},{1,9},{5,1},{5,5},{5,9},{5,13},{9,1},{9,5},{9,9},{9,13},{13,5},{13,9}};
for (int[] p : tl) grid[p[0]][p[1]].special = SpecialTile.TRIPLE_LETTER;
// 双重字母分
int[][] dl = {{0,3},{0,11},{2,6},{2,8},{3,0},{3,7},{3,14},{6,2},{6,6},{6,8},{6,12},
{7,3},{7,11},{8,2},{8,6},{8,8},{8,12},{11,0},{11,7},{11,14},{12,6},{12,8},{14,3},{14,11}};
for (int[] p : dl) grid[p[0]][p[1]].special = SpecialTile.DOUBLE_LETTER;
grid[7][7].special = SpecialTile.CENTER;
}
public boolean isValid(int r, int c) { return r >= 0 && r < SIZE && c >= 0 && c < SIZE; }
public char getLetter(int r, int c) { return grid[r][c].letter; }
public void setLetter(int r, int c, char ch) { grid[r][c].letter = ch; }
public boolean isEmpty(int r, int c) { return grid[r][c].isEmpty(); }
public SpecialTile getSpecial(int r, int c) { return grid[r][c].special; }
public int getSize() { return SIZE; }
/**
* 检查棋盘是否为空（第一回合）
*/
public boolean isEmpty() {
for (int r = 0; r < SIZE; r++)
for (int c = 0; c < SIZE; c++)
if (!grid[r][c].isEmpty()) return false;
return true;
}
}
Trie树词典构建
/**
* Trie树节点
*/
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isWord = false;
String word = null; // 存储完整单词，便于检索
}
/**
* Trie树词典，支持前缀查询和完整单词验证
*/
class WordDictionary {
private final TrieNode root = new TrieNode();
private final Set<String> allWords = new HashSet<>();
/**
* 从单词列表构建词典
*/
public void buildDictionary(List<String> words) {
for (String word : words) {
String upper = word.toUpperCase();
allWords.add(upper);
TrieNode node = root;
for (char ch : upper.toCharArray()) {
node = node.children.computeIfAbsent(ch, k -> new TrieNode());
}
node.isWord = true;
node.word = upper;
}
}
/**
* 检查是否为有效单词
*/
public boolean isValidWord(String word) {
return allWords.contains(word.toUpperCase());
}
/**
* 检查是否为有效前缀（可用于剪枝搜索）
*/
public boolean isValidPrefix(String prefix) {
TrieNode node = root;
for (char ch : prefix.toUpperCase().toCharArray()) {
node = node.children.get(ch);
if (node == null) return false;
}
return true;
}
/**
* 获取以某前缀开头的所有单词（用于高级AI）
*/
public List<String> getWordsWithPrefix(String prefix) {
List<String> results = new ArrayList<>();
TrieNode node = root;
for (char ch : prefix.toUpperCase().toCharArray()) {
node = node.children.get(ch);
if (node == null) return results;
}
collectWords(node, results);
return results;
}
private void collectWords(TrieNode node, List<String> results) {
if (node == null) return;
if (node.isWord) results.add(node.word);
for (TrieNode child : node.children.values()) {
collectWords(child, results);
}
}
}
锚点分析与单词生成
/**
* 锚点：棋盘上可以与新单词交叉的位置
*/
class Anchor {
int row, col;
boolean horizontal; // true=横向放置, false=纵向放置
Anchor(int row, int col, boolean horizontal) {
this.row = row; this.col = col; this.horizontal = horizontal;
}
}
/**
* 单词放置方案
*/
class Move {
String word;
int startRow, startCol;
boolean horizontal;
int score;
Map<Cell, Character> placements = new HashMap<>(); // 实际需要放置的字母
static class Cell {
int r, c;
Cell(int r, int c) { this.r = r; this.c = c; }
@Override public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Cell)) return false;
Cell cell = (Cell) o;
return r == cell.r && c == cell.c;
}
@Override public int hashCode() { return Objects.hash(r, c); }
}
}
/**
* 拼字游戏AI，使用锚点分析和Trie树搜索最优落子
*/
class ScrabbleAI {
private final ScrabbleBoard board;
private final WordDictionary dictionary;
public ScrabbleAI(ScrabbleBoard board, WordDictionary dictionary) {
this.board = board;
this.dictionary = dictionary;
}
/**
* 找到棋盘上所有有效锚点
*/
public List<Anchor> findAnchors() {
List<Anchor> anchors = new ArrayList<>();
if (board.isEmpty()) {
// 第一回合，中心格是唯一的锚点
anchors.add(new Anchor(7, 7, true));
return anchors;
}
for (int r = 0; r < board.getSize(); r++) {
for (int c = 0; c < board.getSize(); c++) {
if (board.isEmpty(r, c)) {
// 如果上下有字母，可以作为纵向单词的一部分
boolean hasVerticalNeighbor =
(board.isValid(r-1, c) && !board.isEmpty(r-1, c)) ||
(board.isValid(r+1, c) && !board.isEmpty(r+1, c));
// 如果左右有字母，可以作为横向单词的一部分
boolean hasHorizontalNeighbor =
(board.isValid(r, c-1) && !board.isEmpty(r, c-1)) ||
(board.isValid(r, c+1) && !board.isEmpty(r, c+1));
if (hasHorizontalNeighbor) anchors.add(new Anchor(r, c, true));
if (hasVerticalNeighbor) anchors.add(new Anchor(r, c, false));
}
}
}
return anchors;
}
/**
* 搜索最优落子
*/
public Move findBestMove(List<Character> rack) {
List<Anchor> anchors = findAnchors();
Move bestMove = null;
for (Anchor anchor : anchors) {
List<Move> moves = generateMovesAtAnchor(anchor, rack);
for (Move move : moves) {
if (isValidMove(move)) {
move.score = calculateScore(move);
if (bestMove == null || move.score > bestMove.score) {
bestMove = move;
}
}
}
}
return bestMove;
}
/**
* 在特定锚点生成所有可能的单词放置
*/
private List<Move> generateMovesAtAnchor(Anchor anchor, List<Character> rack) {
List<Move> moves = new ArrayList<>();
// 贪心策略：尝试使用尽可能多的字母（优先使用全部7个字母获得50分奖励）
for (int len = 2; len <= 7; len++) {
// 向左/向上扩展生成前缀，向右/向下生成后缀
// 简化实现：枚举所有字母排列组合
generatePermutations(anchor, rack, new ArrayList<>(), moves, len);
}
return moves;
}
private void generatePermutations(Anchor anchor, List<Character> rack,
List<Character> current, List<Move> moves, int targetLen) {
if (current.size() == targetLen) {
String word = buildWordFromPlacement(anchor, current);
if (word != null && dictionary.isValidWord(word)) {
Move move = createMove(anchor, word, current);
if (move != null) moves.add(move);
}
return;
}
for (int i = 0; i < rack.size(); i++) {
char ch = rack.get(i);
current.add(ch);
// 前缀剪枝：如果当前前缀不在词典中，提前终止
String partial = buildPartialWord(anchor, current);
if (partial == null || dictionary.isValidPrefix(partial)) {
generatePermutations(anchor, rack, current, moves, targetLen);
}
current.remove(current.size() - 1);
}
}
/**
* 从放置方案构建单词（考虑棋盘上已有的字母）
*/
private String buildWordFromPlacement(Anchor anchor, List<Character> letters) {
StringBuilder sb = new StringBuilder();
int idx = 0;
if (anchor.horizontal) {
for (int c = anchor.col; c < board.getSize() && idx < letters.size(); c++) {
if (board.isEmpty(anchor.row, c)) {
sb.append(letters.get(idx++));
} else {
sb.append(board.getLetter(anchor.row, c));
}
}
} else {
for (int r = anchor.row; r < board.getSize() && idx < letters.size(); r++) {
if (board.isEmpty(r, anchor.col)) {
sb.append(letters.get(idx++));
} else {
sb.append(board.getLetter(r, anchor.col));
}
}
}
return sb.toString();
}
private String buildPartialWord(Anchor anchor, List<Character> letters) {
// 类似buildWordFromPlacement，但只构建到当前已放置的部分
return buildWordFromPlacement(anchor, letters);
}
private Move createMove(Anchor anchor, String word, List<Character> letters) {
Move move = new Move();
move.word = word;
move.startRow = anchor.row;
move.startCol = anchor.col;
move.horizontal = anchor.horizontal;
int idx = 0;
if (anchor.horizontal) {
for (int c = anchor.col; c < board.getSize() && idx < letters.size(); c++) {
if (board.isEmpty(anchor.row, c)) {
move.placements.put(new Move.Cell(anchor.row, c), letters.get(idx++));
}
}
} else {
for (int r = anchor.row; r < board.getSize() && idx < letters.size(); r++) {
if (board.isEmpty(r, anchor.col)) {
move.placements.put(new Move.Cell(r, anchor.col), letters.get(idx++));
}
}
}
return move;
}
/**
* 验证落子是否符合规则（与已有字母连接、不覆盖已有字母等）
*/
private boolean isValidMove(Move move) {
// 检查是否与已有字母交叉（第一回合除外）
if (!board.isEmpty()) {
boolean connects = false;
for (Move.Cell cell : move.placements.keySet()) {
if (hasAdjacentLetter(cell.r, cell.c)) {
connects = true;
break;
}
}
if (!connects) return false;
}
// 检查形成的所有交叉单词是否有效
for (Move.Cell cell : move.placements.keySet()) {
String crossWord = extractCrossWord(cell.r, cell.c, move.horizontal);
if (crossWord.length() > 1 && !dictionary.isValidWord(crossWord)) {
return false;
}
}
return true;
}
private boolean hasAdjacentLetter(int r, int c) {
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (board.isValid(nr, nc) && !board.isEmpty(nr, nc)) return true;
}
return false;
}
private String extractCrossWord(int r, int c, boolean mainHorizontal) {
// 提取与主单词垂直方向的交叉单词
StringBuilder sb = new StringBuilder();
if (mainHorizontal) {
// 垂直方向提取
int sr = r;
while (board.isValid(sr-1, c) && !board.isEmpty(sr-1, c)) sr--;
for (int i = sr; board.isValid(i, c) && !board.isEmpty(i, c); i++) {
sb.append(board.getLetter(i, c));
}
} else {
// 水平方向提取
int sc = c;
while (board.isValid(r, sc-1) && !board.isEmpty(r, sc-1)) sc--;
for (int j = sc; board.isValid(r, j) && !board.isEmpty(r, j); j++) {
sb.append(board.getLetter(r, j));
}
}
return sb.toString();
}
/**
* 计算落子得分
*/
private int calculateScore(Move move) {
int wordScore = 0;
int wordMultiplier = 1;
// 主单词得分
for (Map.Entry<Move.Cell, Character> entry : move.placements.entrySet()) {
Move.Cell cell = entry.getKey();
char letter = entry.getValue();
int letterScore = LetterScores.getScore(letter);
SpecialTile special = board.getSpecial(cell.r, cell.c);
switch (special) {
case DOUBLE_LETTER: letterScore *= 2; break;
case TRIPLE_LETTER: letterScore *= 3; break;
case DOUBLE_WORD: wordMultiplier *= 2; break;
case TRIPLE_WORD: wordMultiplier *= 3; break;
case CENTER: wordMultiplier *= 2; break;
default: break;
}
wordScore += letterScore;
}
// 加上棋盘上已有字母的分值（这些字母不享受格子倍数）
for (char ch : move.word.toCharArray()) {
// 简化：假设所有字母都已计入
}
int totalScore = wordScore * wordMultiplier;
// 使用全部7个字母的奖励
if (move.placements.size() == 7) totalScore += 50;
return totalScore;
}
}
主程序与演示
public class ScrabbleMain {
public static void main(String[] args) {
// 构建词典（实际应用中应加载完整词典文件）
List<String> words = Arrays.asList(
"HELLO", "WORLD", "JAVA", "ALGORITHM", "TREE", "TRIE",
"WORD", "GAME", "PLAY", "SCORE", "BOARD", "TILE",
"SEARCH", "MATCH", "POINT", "LETTER", "PREFIX", "GREEDY",
"OPTIMAL", "STRATEGY", "PUZZLE", "LETTER", "PHRASE",
"SPELL", "CROSS", "GRID", "NODE", "PATH", "ROOT",
"CHILD", "LEVEL", "DEPTH", "BREADTH", "QUEUE", "STACK"
);
WordDictionary dictionary = new WordDictionary();
dictionary.buildDictionary(words);
ScrabbleBoard board = new ScrabbleBoard();
ScrabbleAI ai = new ScrabbleAI(board, dictionary);
System.out.println("=== 拼字游戏AI演示 ===\n");
// 第一回合：在中心放置HELLO
List<Character> rack1 = Arrays.asList('H', 'E', 'L', 'L', 'O', 'A', 'T');
Move move1 = ai.findBestMove(rack1);
if (move1 != null) {
System.out.println("第一回合最优落子: " + move1.word);
System.out.println("得分: " + move1.score);
System.out.println("放置位置: (" + move1.startRow + "," + move1.startCol + ")");
System.out.println("方向: " + (move1.horizontal ? "横向" : "纵向"));
}
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| Trie树构建 | O(总字母数) | O(总字母数) |
| 单词验证 | O(单词长度) | O(1) |
| 前缀查询 | O(前缀长度) | O(1) |
| 锚点查找 | O(棋盘大小) | O(锚点数) |
| 最优落子搜索 | O(锚点数 × 排列数 × 验证) | O(递归深度) |
| 得分计算 | O(单词长度) | O(1) |
总结
本文实现了一个拼字游戏AI，核心算法包括：
- Trie树：以前缀树结构存储词典，实现O(L)时间的单词验证和前缀查询，支持高效的搜索剪枝
- 锚点分析：识别棋盘上所有可与新单词连接的位置，将搜索空间从整个棋盘缩小到有效锚点
- 贪心最优落子：枚举手牌字母的排列组合，结合Trie树前缀剪枝，快速找到高分单词
- 交叉验证：确保主单词和垂直方向形成的交叉单词均为有效词典单词
Trie树是拼字游戏AI的核心数据结构——其前缀匹配能力使得在搜索过程中可以大幅剪枝无效分支，将指数级复杂度降为可接受的搜索范围。
