1. 简介
最近，我们研究了解决游戏2048的算法，我们从理论的角度讨论了这个问题，并没有提供任何实际的代码。
这里我们将用Java编写一个实现，它将同时扮演人类和计算机玩家，展示更优化的游戏体验。
2. 初始设置
我们首先需要的是一个可以玩游戏并查看进展情况的设置。
这将提供我们玩游戏所需的所有构造，并完全实现计算机玩家-它只会放置随机方块，这为我们实现“人类”玩家玩游戏提供了空间。
2.1 游戏板
首先，我们需要一个游戏板，游戏板是一个由单元格组成的网格，可以在其中放置数字。
为了让一些事情更容易处理，让我们从一个简单的单元格位置表示开始，这实际上只是一对坐标的包装：
public class Cell {
private final int x;
private final int y;
// constructor, getters, and toString
}
现在我们可以编写一个类来表示棋盘本身，它将把值存储在一个简单的二维数组中，但允许我们通过上面的Cell类访问它们：
public class Board {
private final int[][] board;
private final int score;
public Board(int size) {
this.board = new int[size][];
this.score = 0;
for (int x = 0; x < size; ++x) {
this.board[x] = new int[size];
for (int y = 0; y < size; ++y) {
board[x][y] = 0;
}
}
}
public int getSize() {
return board.length;
}
public int getScore() {
return score;
}
public int getCell(Cell cell) {
return board[cell.getX()][cell.getY()];
}
public boolean isEmpty(Cell cell) {
return getCell(cell) == 0;
}
public List<Cell> emptyCells() {
List<Cell> result = new ArrayList<>();
for (int x = 0; x < board.length; ++x) {
for (int y = 0; y < board[x].length; ++y) {
Cell cell = new Cell(x, y);
if (isEmpty(cell)) {
result.add(cell);
}
}
}
return result;
}
}
这是一个不可变的类，代表棋盘，让我们可以查询棋盘的当前状态。它还会跟踪当前分数，稍后我们会讲到。
2.2 电脑玩家和放置棋子
现在我们有了游戏板，我们希望能够使用它来玩游戏。我们首先需要的是电脑玩家，因为这是一个纯粹的随机玩家，稍后会用到。
电脑玩家只需将图块放入单元格即可，因此我们需要某种方式在棋盘上实现这一点。我们希望保持图块的不可变性，因此放置图块将生成一个处于新状态的全新棋盘。
首先，我们需要一个构造函数来获取实际的棋盘状态，而不是像我们之前那样只构造一个空白棋盘：
private Board(int[][] board, int score) {
this.score = score;
this.board = new int[board.length][];
for (int x = 0; x < board.length; ++x) {
this.board[x] = Arrays.copyOf(board[x], board[x].length);
}
}
这是私有的，因此只能由同一类中的其他方法使用，这有助于我们对棋盘进行封装。
接下来，我们将添加一个方法来放置图块，这将返回一个全新的棋盘，该棋盘与当前棋盘完全相同，只是在给定的单元格中具有给定的数字：
public Board placeTile(Cell cell, int number) {
if (!isEmpty(cell)) {
throw new IllegalArgumentException("That cell is not empty");
}
Board result = new Board(this.board, this.score);
result.board[cell.getX()][cell.getY()] = number;
return result;
}
最后，我们将编写一个代表计算机玩家的新类，它将包含一个方法，该方法接收当前棋盘并返回新的棋盘：
public class Computer {
private final SecureRandom rng = new SecureRandom();
public Board makeMove(Board input) {
List<Cell> emptyCells = input.emptyCells();
double numberToPlace = rng.nextDouble();
int indexToPlace = rng.nextInt(emptyCells.size());
Cell cellToPlace = emptyCells.get(indexToPlace);
return input.placeTile(cellToPlace, numberToPlace >= 0.9 ? 4 : 2);
}
}
这段代码会获取棋盘上所有空格的列表，随机选择一个，然后在其中填入一个数字。我们会随机决定在10%的情况下将“4”填入格子，在其余90%的情况下将“2”填入格子。
2.2 “人类”玩家和移动牌
接下来我们需要的是“人类”玩家，这并非最终目标，而是一个纯粹随机的玩家，每次移动棋子时都会随机选择一个方向，这将作为我们构建最佳玩家的基础。
首先，我们需要定义一个可以采取的行动的枚举：
public enum Move {
UP,
DOWN,
LEFT,
RIGHT
}
接下来，我们需要扩充Board类，使其支持通过向某个方向移动棋子来进行移动。为了降低这里的复杂度，我们希望旋转棋盘，使棋子始终沿同一方向移动。
这意味着我们需要一种既能转置又能反转棋盘的方法：
private static int[][] transpose(int[][] input) {
int[][] result = new int[input.length][];
for (int x = 0; x < input.length; ++x) {
result[x] = new int[input[0].length];
for (int y = 0; y < input[0].length; ++y) {
result[x][y] = input[y][x];
}
}
return result;
}
private static int[][] reverse(int[][] input) {
int[][] result = new int[input.length][];
for (int x = 0; x < input.length; ++x) {
result[x] = new int[input[0].length];
for (int y = 0; y < input[0].length; ++y) {
result[x][y] = input[x][input.length - y - 1];
}
}
return result;
}
转置棋盘会交换所有行和列，这样上边缘就变成了左边缘。反转棋盘只是将其镜像，这样左边缘就变成了右边缘。
接下来，我们为Board添加一个方法，让它按照给定的方向移动，并返回新状态下的新Board。
我们首先复制一份棋盘状态，然后就可以使用：
public Board move(Move move) {
int newScore = 0;
// Clone the board
int[][] tiles = new int[this.board.length][];
for (int x = 0; x < this.board.length; ++x) {
tiles[x] = Arrays.copyOf(this.board[x], this.board[x].length);
}
接下来，我们对副本进行操作，以便始终将图块向上移动：
if (move == Move.LEFT || move == Move.RIGHT) {
tiles = transpose(tiles);
}
if (move == Move.DOWN || move == Move.RIGHT) {
tiles = reverse(tiles);
}
我们还需要另一个图块数组(这次我们将在其中构建最终结果)以及用于跟踪此移动获得的新分数的跟踪器：
int[][] result = new int[tiles.length][];
int newScore = 0;
现在我们已经准备好开始移动棋子，并且我们已经操纵了事物以便我们始终朝着同一个方向努力，我们就可以开始了。
我们可以独立移动每一列，我们只需要遍历所有列并重复，从构建我们要移动的图块的另一个副本开始。
这次我们将它们构建到LinkedList中，因为我们希望能够轻松地从中弹出值，我们还只添加具有数字的实际图块并跳过空图块。
这样就实现了图块的移动，但还没有实现图块的合并：
for (int x = 0; x < tiles.length; ++x) {
LinkedList<Integer> thisRow = new LinkedList<>();
for (int y = 0; y < tiles[0].length; ++y) {
if (tiles[x][y] > 0) {
thisRow.add(tiles[x][y]);
}
}
接下来，我们需要合并图块。我们需要将合并操作与上述操作分开进行；否则，可能会出现多次合并同一图块的风险。
这是通过构建上面的图块的另一个LinkedList来实现的，但这次我们会进行合并：
LinkedList<Integer> newRow = new LinkedList<>();
while (thisRow.size() >= 2) {
int first = thisRow.pop();
int second = thisRow.peek();
if (second == first) {
int newNumber = first * 2;
newRow.add(newNumber);
newScore += newNumber;
thisRow.pop();
} else {
newRow.add(first);
}
}
newRow.addAll(thisRow);
这里我们还会计算这次移动的新分数，这是合并后产生的方块的总和。
现在我们可以将其构建到结果数组中，一旦列表中的图块用完，其余图块将填充值“0”，以指示它们是空白的：
result[x] = new int[tiles[0].length];
for (int y = 0; y < tiles[0].length; ++y) {
if (newRow.isEmpty()) {
result[x][y] = 0;
} else {
result[x][y] = newRow.pop();
}
}
}
一旦我们完成了图块的移动，我们需要再次操纵它们回到正确的旋转位置，这与我们之前所做的正好相反：
if (move == Move.DOWN || move == Move.RIGHT) {
result = reverse(result);
}
if (move == Move.LEFT || move == Move.RIGHT) {
result = transpose(result);
}
最后，我们可以用这组新的牌和新计算的分数构建并返回一个新棋盘：
return new Board(result, this.score + newScore);
}
现在我们可以编写随机“人类”玩家了，这只不过是生成一个随机动作并调用上述方法来完成这个动作：
public class Human {
private SecureRandom rng = new SecureRandom();
public Board makeMove(Board input) {
Move move = Move.values()[rng.nextInt(4)];
return input.move(move);
}
}
2.3 玩游戏
虽然还不是很成功，但我们拥有足够的组件来运行游戏。不过，我们很快就会改进人类职业的玩法，这样就能更容易地发现差异。
首先，我们需要一种方法来打印出游戏板。
在这个例子中，我们只是要打印到控制台，所以System.out.print就足够了。对于真正的游戏，可能需要更好的GUI界面：
private static void printBoard(Board board) {
StringBuilder topLines = new StringBuilder();
StringBuilder midLines = new StringBuilder();
for (int x = 0; x < board.getSize(); ++x) {
topLines.append("+--------");
midLines.append("| ");
}
topLines.append("+");
midLines.append("|");
for (int y = 0; y < board.getSize(); ++y) {
System.out.println(topLines);
System.out.println(midLines);
for (int x = 0; x < board.getSize(); ++x) {
Cell cell = new Cell(x, y);
System.out.print("|");
if (board.isEmpty(cell)) {
System.out.print(" ");
} else {
StringBuilder output = new StringBuilder(Integer.toString(board.getCell(cell)));
while (output.length() < 8) {
output.append(" ");
if (output.length() < 8) {
output.insert(0, " ");
}
}
System.out.print(output);
}
}
System.out.println("|");
System.out.println(midLines);
}
System.out.println(topLines);
System.out.println("Score: " + board.getScore());
}
我们还需要设置一下，这意味着创建棋盘、两名玩家，并让计算机进行两次初始移动-即在棋盘上放置两个随机数：
Board board = new Board(4);
Computer computer = new Computer();
Human human = new Human();
for (int i = 0; i < 2; ++i) {
board = computer.makeMove(board);
}
现在我们有了真正的游戏循环，这将是人类和计算机玩家轮流进行的循环，只有当没有空单元格时才会停止：
printBoard(board);
do {
System.out.println("Human move");
System.out.println("==========");
board = human.makeMove(board);
printBoard(board);
System.out.println("Computer move");
System.out.println("=============");
board = computer.makeMove(board);
printBoard(board);
} while (!board.emptyCells().isEmpty());
System.out.println("Final Score: " + board.getScore());
此时，如果我们运行该程序，我们将看到正在进行的随机2048游戏。
3. 实现2048玩家
一旦我们有了游戏的基础，我们就可以开始实现“人类”玩家，并且玩得比仅仅选择随机方向更好。
3.1 模拟移动
我们这里实现的算法基于Expectimax算法，因此，该算法的核心是模拟每一种可能的走法，为每个走法分配一个分数，然后选择表现最佳的走法。
我们将大量使用Java 8 Stream来帮助构建此代码，原因我们稍后会看到。
我们首先从Human类内部重写makeMove()方法：
public Board makeMove(Board input) {
return Arrays.stream(Move.values())
.map(input::move)
.max(Comparator.comparingInt(board -> generateScore(board, 0)))
.orElse(input);
}
对于我们可以移动的每个可能方向，我们都会生成新的棋盘，然后启动得分算法-传递这个棋盘和0的深度，然后我们选择得分最高的移动。
然后，我们的generateScore()方法模拟每一种可能的计算机移动-即将“2”或“4”放入每个空单元格，然后观察接下来会发生什么：
private int generateScore(Board board, int depth) {
if (depth >= 3) {
return calculateFinalScore(board);
}
return board.emptyCells().stream()
.flatMap(cell -> Stream.of(new Pair<>(cell, 2), new Pair<>(cell, 4)))
.mapToInt(move -> {
Board newBoard = board.placeTile(move.getFirst(), move.getSecond());
int boardScore = calculateScore(newBoard, depth + 1);
return (int) (boardScore * (move.getSecond() == 2 ? 0.9 : 0.1));
})
.sum();
}
如果我们已经达到深度限制，那么我们将立即停止并计算该板的最终得分；否则，我们继续模拟。
我们的calculateScore()方法是模拟的延续，运行等式中的人类移动侧。
这与上面的makeMove()方法非常相似，但我们返回的是当前得分而不是实际棋盘：
private int calculateScore(Board board, int depth) {
return Arrays.stream(Move.values())
.map(board::move)
.mapToInt(newBoard -> generateScore(newBoard, depth))
.max()
.orElse(0);
}
3.2 最终板面得分
现在，我们可以模拟人类和计算机玩家来回移动，模拟足够多的走棋后就停止。我们需要能够为每个模拟分支生成最终棋盘的分数，这样我们才能知道哪个分支才是我们想要继续的。
我们的得分是多种因素的组合，我们将每个因素应用于棋盘上的每行和每列，所有因素加在一起，返回总分。
因此，我们需要生成一个行和列的列表来评分：
List<List<Integer>> rowsToScore = new ArrayList<>();
for (int i = 0; i < board.getSize(); ++i) {
List<Integer> row = new ArrayList<>();
List<Integer> col = new ArrayList<>();
for (int j = 0; j < board.getSize(); ++j) {
row.add(board.getCell(new Cell(i, j)));
col.add(board.getCell(new Cell(j, i)));
}
rowsToScore.add(row);
rowsToScore.add(col);
}
然后拿出我们构建的列表，对每个列表进行评分，并将分数相加；这是我们即将填写的占位符：
return rowsToScore.stream()
.mapToInt(row -> {
int score = 0;
return score;
})
.sum();
最后，我们需要真正地生成分数，这包含在上面的Lambda中，其中包含几个不同的因素，它们都会产生影响：
- 每行固定分数
- 该行中每个数字的总和
- 行内所有可能的合并
- 行中的每个空单元格
- 行的单调性，这表示行按升序排列的程度
在计算分数之前，我们需要建立一些额外的数据。
首先，我们需要一个删除了空白单元格的数字列表：
List<Integer> preMerged = row.stream()
.filter(value -> value != 0)
.collect(Collectors.toList());
然后，我们可以从这个新列表中进行一些计数，给出具有相同数字的相邻单元格的数量，其中数字严格按升序排列，数字严格按降序排列：
int numMerges = 0;
int monotonicityLeft = 0;
int monotonicityRight = 0;
for (int i = 0; i < preMerged.size() - 1; ++i) {
Integer first = preMerged.get(i);
Integer second = preMerged.get(i + 1);
if (first.equals(second)) {
++numMerges;
} else if (first > second) {
monotonicityLeft += first - second;
} else {
monotonicityRight += second - first;
}
}
现在我们可以计算这一行的分数：
int score = 1000;
score += 250 * row.stream().filter(value -> value == 0).count();
score += 750 * numMerges;
score -= 10 * row.stream().mapToInt(value -> value).sum();
score -= 50 * Math.min(monotonicityLeft, monotonicityRight);
return score;
这里选择的数字相对随意，不同的数字会对游戏的玩法产生影响，从而优先考虑不同的游戏因素。
4. 算法的改进
目前为止，我们的系统运行良好，运行效果也不错，但速度有点慢。人类每走一步大约需要1分钟，我们可以做得更好。
4.1 并行处理
显而易见，我们可以并行处理，这是使用Java Stream的一大优势-我们只需在每个流中添加一条语句即可实现并行化。
仅这一改变就使我们每步动作的时间缩短到20秒左右。
4.2 修剪不可玩的分支
我们接下来要做的是删除任何无法下棋的分支，也就是说，任何人类的举动都会导致棋盘发生变化。这些分支几乎肯定会导致更糟糕的结果，它们实际上是给了计算机一次自由落子的机会，但处理这些分支会耗费我们的处理时间。
为了实现这一点，我们需要在Board上实现一个equals方法，以便我们可以比较它们：
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Board board1 = (Board) o;
return Arrays.deepEquals(board, board1.board);
}
然后，我们可以向流管道添加一些过滤器，以停止处理任何未改变的内容。
return Arrays.stream(Move.values())
.parallel()
.map(board::move)
.filter(moved -> !moved.equals(board))
........
这对游戏初期的影响微乎其微-当填充的单元格很少时，可以调整的步数也很少。然而，到了后期，这种调整的影响就会大得多，将步数缩短到只有几秒钟。
5. 总结
这里我们构建了一个用于玩2048游戏的框架，然后，我们编写了一个求解器，以便更好地进行游戏。
Post Directory
