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);
}
}
Это получает список каждой пустой ячейки с доски, выбирает случайную, а затем помещает в нее число. Мы случайным образом решим поставить «4» в ячейку в 10% случаев, а «2» — в остальных 90%.
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. Игра в игру
У нас достаточно компонентов, чтобы играть в игру, пусть и не очень успешно. Однако вскоре мы улучшим способ игры класса Human , и это позволит нам легко увидеть различия.
Во-первых, нам нужен способ распечатать игровое поле.
В этом примере мы просто собираемся печатать на консоль, поэтому System.out.print достаточно. Для реальной игры мы хотели бы улучшить графику:
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 Streams для структурирования этого кода по причинам, которые мы увидим позже.
Начнем с того, что перепишем метод makeMove() внутри нашего класса Human :
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();
Наконец, нам нужно фактически сгенерировать наши оценки. Это происходит внутри приведенной выше лямбды и представляет собой несколько различных факторов, которые вносят свой вклад :
- Фиксированная оценка для каждой строки
- Сумма каждого числа в строке
- Каждое возможное слияние в строке
- Каждая пустая ячейка в строке
- Монотонность ряда. Это представляет количество, которое строка организована в возрастающем числовом порядке.
Прежде чем мы сможем рассчитать баллы, нам нужно создать некоторые дополнительные данные.
Во-первых, нам нужен список чисел с удаленными пустыми ячейками:
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 Streams — мы можем сделать эту работу параллельной, просто добавив один оператор в каждый поток.
Одно только это изменение позволяет нам сократить примерно до 20 секунд на ход.
4.2. Обрезка неиграбельных ветвей
Следующее, что мы можем сделать, это удалить все неиграбельные ветки. То есть каждый раз, когда ход человека приводит к неизменной доске. Это почти наверняка ответвления, которые приведут к худшим результатам — они фактически дают компьютеру свободу действий — но они требуют времени обработки для их выполнения.
Для этого нам нужно реализовать на нашей плате метод 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. Затем мы написали в него решатель, чтобы мы могли играть в лучшую игру. Все приведенные здесь примеры можно найти на GitHub .
Почему бы не попробовать изменить правила, чтобы посмотреть, как они повлияют на игровой процесс.