每日算法 — 使用java实现海战棋：概率密度推理与贪心最优射击策略

海战棋（Battleship）是一款经典的双人对战策略游戏。玩家各自在隐蔽的棋盘上部署战舰，然后轮流射击对方棋盘上的坐标，目标是率先击沉对方所有战舰。对于AI玩家而言，如何在信息不完全的情况下做出最优射击决策，是一个极具挑战的算法问题。本文将用Java实现一个带AI的海战棋系统，核心算法包括概率密度分布计算、贪心最优射击策略，以及命中后的定向搜索追击。

一、游戏规则与数据建模

海战棋通常在10×10的棋盘上进行。标准舰队包含5艘战舰，分别为：航空母舰（5格）、战列舰（4格）、巡洋舰（3格）、潜艇（3格）和驱逐舰（2格）。战舰只能水平或垂直放置，且不能重叠。

1.1 核心数据结构

我们用枚举类型表示棋盘格子的状态，用二维数组存储整个棋盘：

/**
 * 棋盘格子状态枚举
 */
enum CellState {
    EMPTY,      // 空白水域
    SHIP,       // 有战舰（对敌方隐藏）
    MISS,       // 射击未命中
    HIT,        // 射击命中
    SUNK        // 战舰被击沉
}

/**
 * 战舰类型定义
 */
enum ShipType {
    CARRIER(5, "航空母舰"),
    BATTLESHIP(4, "战列舰"),
    CRUISER(3, "巡洋舰"),
    SUBMARINE(3, "潜艇"),
    DESTROYER(2, "驱逐舰");

    final int length;
    final String name;

    ShipType(int length, String name) {
        this.length = length;
        this.name = name;
    }
}

/**
 * 战舰实体类，记录位置和状态
 */
class Ship {
    final ShipType type;
    final int startRow, startCol;
    final boolean horizontal; // true为水平，false为垂直
    final boolean[] hits;     // 记录各部位是否被击中

    Ship(ShipType type, int startRow, int startCol, boolean horizontal) {
        this.type = type;
        this.startRow = startRow;
        this.startCol = startCol;
        this.horizontal = horizontal;
        this.hits = new boolean[type.length];
    }

    /**
     * 判断坐标是否属于本战舰
     */
    boolean contains(int row, int col) {
        if (horizontal) {
            return row == startRow && col >= startCol && col < startCol + type.length;
        } else {
            return col == startCol && row >= startRow && row < startRow + type.length;
        }
    }

    /**
     * 标记命中，返回是否击沉
     */
    boolean hit(int row, int col) {
        int index = horizontal ? (col - startCol) : (row - startRow);
        hits[index] = true;
        return isSunk();
    }

    /**
     * 检查战舰是否已完全击沉
     */
    boolean isSunk() {
        for (boolean h : hits) {
            if (!h) return false;
        }
        return true;
    }
}

1.2 棋盘类设计

/**
 * 海战棋棋盘，管理格子状态和战舰部署
 */
class Board {
    static final int SIZE = 10;
    private final CellState[][] grid;
    private final List<Ship> ships;

    Board() {
        grid = new CellState[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            Arrays.fill(grid[i], CellState.EMPTY);
        }
        ships = new ArrayList<>();
    }

    /**
     * 尝试在指定位置放置战舰，检查边界和碰撞
     */
    boolean placeShip(ShipType type, int row, int col, boolean horizontal) {
        // 边界检查
        if (horizontal) {
            if (col + type.length > SIZE) return false;
        } else {
            if (row + type.length > SIZE) return false;
        }

        // 碰撞检测（包括相邻格子的缓冲检查，确保战舰不接触）
        for (int i = 0; i < type.length; i++) {
            int r = horizontal ? row : row + i;
            int c = horizontal ? col + i : col;
            if (!canPlaceAt(r, c)) return false;
        }

        // 实际放置
        Ship ship = new Ship(type, row, col, horizontal);
        ships.add(ship);
        for (int i = 0; i < type.length; i++) {
            int r = horizontal ? row : row + i;
            int c = horizontal ? col + i : col;
            grid[r][c] = CellState.SHIP;
        }
        return true;
    }

    /**
     * 检查某个格子及其八邻域是否可以放置新战舰
     */
    private boolean canPlaceAt(int row, int col) {
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                int nr = row + dr, nc = col + dc;
                if (nr >= 0 && nr < SIZE && nc >= 0 && nc < SIZE) {
                    if (grid[nr][nc] == CellState.SHIP) return false;
                }
            }
        }
        return true;
    }

    /**
     * 对指定坐标进行射击
     */
    ShotResult shoot(int row, int col) {
        if (grid[row][col] == CellState.SHIP) {
            grid[row][col] = CellState.HIT;
            for (Ship ship : ships) {
                if (ship.contains(row, col)) {
                    boolean sunk = ship.hit(row, col);
                    if (sunk) {
                        markSunk(ship);
                        return new ShotResult(true, true, ship.type);
                    }
                    return new ShotResult(true, false, null);
                }
            }
        }
        grid[row][col] = CellState.MISS;
        return new ShotResult(false, false, null);
    }

    /**
     * 战舰被击沉后，将其所有格子标记为SUNK
     */
    private void markSunk(Ship ship) {
        for (int i = 0; i < ship.type.length; i++) {
            int r = ship.horizontal ? ship.startRow : ship.startRow + i;
            int c = ship.horizontal ? ship.startCol + i : ship.startCol;
            grid[r][c] = CellState.SUNK;
        }
    }

    boolean allShipsSunk() {
        return ships.stream().allMatch(Ship::isSunk);
    }

    CellState getCell(int row, int col) {
        return grid[row][col];
    }

    List<Ship> getShips() {
        return ships;
    }
}

/**
 * 射击结果记录
 */
class ShotResult {
    final boolean hit;
    final boolean sunk;
    final ShipType sunkShip;

    ShotResult(boolean hit, boolean sunk, ShipType sunkShip) {
        this.hit = hit;
        this.sunk = sunk;
        this.sunkShip = sunkShip;
    }
}

二、AI核心算法：概率密度推理

当AI没有任何命中信息时，最佳策略是计算每个格子被战舰覆盖的概率。概率越高的格子，射击价值越大。

2.1 概率密度计算原理

核心思想：枚举所有可能的战舰放置方式，统计每个格子被多少种放置方式覆盖。覆盖次数越多，该格子有战舰的概率就越高。

具体步骤：
1. 对于每一种尚未被击沉的战舰类型，枚举它在当前棋盘上的所有合法放置位置
2. 每种放置位置必须满足：不覆盖已知的MISS格子，不覆盖已被击沉战舰的格子
3. 如果某格已经是HIT（命中但未沉），则只统计覆盖该格的放置方式（用于定向搜索阶段）
4. 累加每个格子的覆盖次数，得到概率密度图

/**
 * 概率密度计算器
 */
class ProbabilityDensityCalculator {
    private final Board enemyBoard; // AI视角的对手棋盘（仅知道MISS和HIT）
    private final int[][] density;
    private final Set<ShipType> remainingShips;

    ProbabilityDensityCalculator(Board enemyBoard, Set<ShipType> remainingShips) {
        this.enemyBoard = enemyBoard;
        this.remainingShips = remainingShips;
        this.density = new int[Board.SIZE][Board.SIZE];
    }

    /**
     * 计算当前棋盘的概率密度图
     */
    int[][] calculate() {
        // 清空密度图
        for (int[] row : density) {
            Arrays.fill(row, 0);
        }

        // 对每种剩余的战舰，枚举所有合法放置
        for (ShipType ship : remainingShips) {
            enumeratePlacements(ship);
        }

        return density;
    }

    /**
     * 枚举指定战舰的所有合法放置并累加密度
     */
    private void enumeratePlacements(ShipType ship) {
        // 水平放置
        for (int row = 0; row < Board.SIZE; row++) {
            for (int col = 0; col <= Board.SIZE - ship.length; col++) {
                if (isValidPlacement(row, col, ship.length, true)) {
                    addDensity(row, col, ship.length, true);
                }
            }
        }
        // 垂直放置
        for (int row = 0; row <= Board.SIZE - ship.length; row++) {
            for (int col = 0; col < Board.SIZE; col++) {
                if (isValidPlacement(row, col, ship.length, false)) {
                    addDensity(row, col, ship.length, false);
                }
            }
        }
    }

    /**
     * 检查某放置是否合法
     * 合法条件：不覆盖MISS、不覆盖SUNK、覆盖所有已知的HIT（定向搜索时）
     */
    private boolean isValidPlacement(int row, int col, int length, boolean horizontal) {
        for (int i = 0; i < length; i++) {
            int r = horizontal ? row : row + i;
            int c = horizontal ? col + i : col;
            CellState state = enemyBoard.getCell(r, c);

            // 不能覆盖已知的MISS和SUNK
            if (state == CellState.MISS || state == CellState.SUNK) {
                return false;
            }
        }
        return true;
    }

    /**
     * 将某放置覆盖的格子密度加1
     */
    private void addDensity(int row, int col, int length, boolean horizontal) {
        for (int i = 0; i < length; i++) {
            int r = horizontal ? row : row + i;
            int c = horizontal ? col + i : col;
            density[r][c]++;
        }
    }
}

2.2 带约束的定向搜索概率

当AI命中某格但战舰尚未击沉时，需要进入”定向搜索”模式。此时概率计算应增加约束：只统计覆盖已知HIT格子的放置方式。这样AI会优先射击与已知HIT在同一直线上的格子。

    /**
     * 定向搜索模式：只统计覆盖所有已知HIT的放置方式
     */
    int[][] calculateWithHits(List<int[]> knownHits) {
        for (int[] row : density) {
            Arrays.fill(row, 0);
        }

        for (ShipType ship : remainingShips) {
            enumerateConstrainedPlacements(ship, knownHits);
        }

        return density;
    }

    private void enumerateConstrainedPlacements(ShipType ship, List<int[]> knownHits) {
        // 水平放置
        for (int row = 0; row < Board.SIZE; row++) {
            for (int col = 0; col <= Board.SIZE - ship.length; col++) {
                if (isValidPlacement(row, col, ship.length, true)
                        && coversHits(row, col, ship.length, true, knownHits)) {
                    addDensity(row, col, ship.length, true);
                }
            }
        }
        // 垂直放置
        for (int row = 0; row <= Board.SIZE - ship.length; row++) {
            for (int col = 0; col < Board.SIZE; col++) {
                if (isValidPlacement(row, col, ship.length, false)
                        && coversHits(row, col, ship.length, false, knownHits)) {
                    addDensity(row, col, ship.length, false);
                }
            }
        }
    }

    /**
     * 检查放置是否覆盖所有已知的HIT坐标
     */
    private boolean coversHits(int row, int col, int length, boolean horizontal, List<int[]> knownHits) {
        for (int[] hit : knownHits) {
            boolean covered = false;
            for (int i = 0; i < length; i++) {
                int r = horizontal ? row : row + i;
                int c = horizontal ? col + i : col;
                if (r == hit[0] && c == hit[1]) {
                    covered = true;
                    break;
                }
            }
            if (!covered) return false;
        }
        return true;
    }

三、AI射击决策引擎

AI的决策分为两个阶段：探索阶段和定向追击阶段。

3.1 决策状态机

/**
 * AI射击决策引擎
 */
class AIPlayer {
    private final Board enemyBoard; // AI视角的对手棋盘
    private final Set<ShipType> remainingShips; // 对手尚未沉没的战舰类型
    private final List<int[]> pendingHits; // 已命中但未沉的坐标
    private boolean huntingMode; // 是否处于定向追击模式

    AIPlayer() {
        this.enemyBoard = new Board();
        this.remainingShips = new LinkedHashSet<>(Arrays.asList(ShipType.values()));
        this.pendingHits = new ArrayList<>();
        this.huntingMode = false;
    }

    /**
     * 根据射击结果更新AI状态
     */
    void reportShotResult(int row, int col, ShotResult result) {
        if (result.hit) {
            pendingHits.add(new int[]{row, col});
            huntingMode = true;
            if (result.sunk) {
                // 战舰被击沉，从待处理列表中移除属于该舰的命中
                remainingShips.remove(result.sunkShip);
                removeSunkHits(result.sunkShip);
                if (pendingHits.isEmpty()) {
                    huntingMode = false;
                }
            }
        }
    }

    /**
     * 从pendingHits中移除已被击沉战舰的坐标
     */
    private void removeSunkHits(ShipType sunkShip) {
        // 简化为清空所有pendingHits（假设一次只击沉一艘）
        // 更精确的做法是根据战舰长度和位置匹配
        pendingHits.clear();
    }

    /**
     * 选择下一个射击目标
     */
    int[] selectTarget() {
        ProbabilityDensityCalculator calc = new ProbabilityDensityCalculator(enemyBoard, remainingShips);
        int[][] density;

        if (huntingMode && !pendingHits.isEmpty()) {
            // 定向追击：计算覆盖所有已知HIT的概率分布
            density = calc.calculateWithHits(pendingHits);
        } else {
            // 探索阶段：计算全局概率分布
            density = calc.calculate();
        }

        // 贪心策略：选择概率密度最高的未射击格子
        int maxDensity = -1;
        int bestRow = -1, bestCol = -1;

        for (int row = 0; row < Board.SIZE; row++) {
            for (int col = 0; col < Board.SIZE; col++) {
                CellState state = enemyBoard.getCell(row, col);
                if (state == CellState.EMPTY || state == CellState.SHIP) {
                    if (density[row][col] > maxDensity) {
                        maxDensity = density[row][col];
                        bestRow = row;
                        bestCol = col;
                    }
                }
            }
        }

        return new int[]{bestRow, bestCol};
    }

    Board getEnemyBoard() {
        return enemyBoard;
    }
}

3.2 探索阶段的优化：棋盘着色策略

在没有任何命中信息的探索阶段，可以采用棋盘着色（Checkerboard）策略进一步优化。由于战舰最小长度为2，相邻的格子不可能同时属于同一艘战舰的最小覆盖。因此，优先射击黑白相间的格子可以提高早期发现战舰的效率。

    /**
     * 带棋盘着色优化的目标选择
     */
    int[] selectTargetOptimized() {
        ProbabilityDensityCalculator calc = new ProbabilityDensityCalculator(enemyBoard, remainingShips);
        int[][] density;

        if (huntingMode && !pendingHits.isEmpty()) {
            density = calc.calculateWithHits(pendingHits);
        } else {
            density = calc.calculate();
        }

        int maxDensity = -1;
        int bestRow = -1, bestCol = -1;

        for (int row = 0; row < Board.SIZE; row++) {
            for (int col = 0; col < Board.SIZE; col++) {
                CellState state = enemyBoard.getCell(row, col);
                if (state != CellState.EMPTY && state != CellState.SHIP) continue;

                int d = density[row][col];
                // 探索阶段应用棋盘着色加权
                if (!huntingMode) {
                    if ((row + col) % 2 == 0) {
                        d = d * 3 / 2; // 优先射击某种颜色的格子
                    }
                }

                if (d > maxDensity) {
                    maxDensity = d;
                    bestRow = row;
                    bestCol = col;
                }
            }
        }

        return new int[]{bestRow, bestCol};
    }

四、完整可运行代码

以下是将所有模块整合后的完整海战棋游戏，包含战舰随机部署、AI对战和胜负判定：

import java.util.*;

/**
 * 海战棋主程序：概率密度AI对战演示
 */
public class BattleshipGame {

    public static void main(String[] args) {
        // 创建玩家棋盘和AI棋盘
        Board playerBoard = createRandomBoard();
        Board aiBoard = createRandomBoard();

        AIPlayer ai = new AIPlayer();
        Random random = new Random();

        System.out.println("=== 海战棋AI对战开始 ===");
        int round = 0;

        while (!playerBoard.allShipsSunk() && !aiBoard.allShipsSunk()) {
            round++;
            System.out.println("\n--- 第 " + round + " 回合 ---");

            // AI射击
            int[] target = ai.selectTargetOptimized();
            int row = target[0], col = target[1];
            ShotResult result = aiBoard.shoot(row, col);
            ai.reportShotResult(row, col, result);

            System.out.printf("AI射击: (%d, %c) -> ", row, (char)('A' + col));
            if (result.sunk) {
                System.out.println("命中并击沉 " + result.sunkShip.name + "!");
            } else if (result.hit) {
                System.out.println("命中!");
            } else {
                System.out.println("未命中");
            }

            // 玩家随机射击（简化演示）
            int pr, pc;
            do {
                pr = random.nextInt(Board.SIZE);
                pc = random.nextInt(Board.SIZE);
            } while (playerBoard.getCell(pr, pc) == CellState.MISS
                    || playerBoard.getCell(pr, pc) == CellState.HIT
                    || playerBoard.getCell(pr, pc) == CellState.SUNK);

            ShotResult playerResult = playerBoard.shoot(pr, pc);
            System.out.printf("玩家射击: (%d, %c) -> ", pr, (char)('A' + pc));
            if (playerResult.sunk) {
                System.out.println("命中并击沉 " + playerResult.sunkShip.name + "!");
            } else if (playerResult.hit) {
                System.out.println("命中!");
            } else {
                System.out.println("未命中");
            }
        }

        System.out.println("\n=== 游戏结束 ===");
        if (aiBoard.allShipsSunk()) {
            System.out.println("AI获胜！共用了 " + round + " 回合");
        } else {
            System.out.println("玩家获胜！");
        }
    }

    /**
     * 随机生成一个合法部署的棋盘
     */
    static Board createRandomBoard() {
        Board board = new Board();
        Random rand = new Random();
        List<ShipType> types = Arrays.asList(ShipType.values());

        for (ShipType type : types) {
            boolean placed = false;
            int attempts = 0;
            while (!placed && attempts < 1000) {
                boolean horizontal = rand.nextBoolean();
                int row = rand.nextInt(Board.SIZE);
                int col = rand.nextInt(Board.SIZE);
                placed = board.placeShip(type, row, col, horizontal);
                attempts++;
            }
            if (!placed) {
                throw new RuntimeException("无法放置战舰: " + type.name);
            }
        }
        return board;
    }
}

// 将前文定义的所有枚举和类放入同一文件中即可编译运行
// （CellState, ShipType, Ship, Board, ShotResult, 
//  ProbabilityDensityCalculator, AIPlayer 等）

五、算法复杂度分析

在10×10的标准棋盘上，概率密度计算的时间开销完全可以接受。对于更大的棋盘，可以通过剪枝和缓存进一步优化：只重新计算受上次射击影响的局部区域，而非整盘概率图。

六、算法扩展与优化方向

1. 蒙特卡洛模拟：不单纯依赖概率密度，而是用蒙特卡洛方法模拟大量随机部署，统计每个格子的命中频率，在复杂约束下更准确。
2. 动态战舰长度推断：当某艘战舰被击沉后，利用剩余战舰的长度信息更新概率模型，排除不可能的放置。
3. 猎杀模式优化：命中后不仅考虑覆盖所有HIT的放置，还引入战舰长度约束，排除长度不足或方向矛盾的放置方式。
4. 对手建模：在对战中学习对手的部署偏好（如是否倾向边缘放置），调整先验概率分布。

七、总结

海战棋AI的核心在于将不完全信息博弈转化为概率推理问题。通过概率密度分布计算，AI能够在没有任何命中信息时做出最优探索决策；命中后则通过定向搜索快速锁定并击沉目标战舰。贪心策略配合棋盘着色优化，使AI在早期探索阶段也能保持高效。这种将概率统计与贪心决策相结合的思路，不仅适用于海战棋，也是许多不完全信息博弈问题的通用解法。