«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<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);Это достигается созданием еще одного LinkedList плиток из вышеприведенного, но на этот раз путем слияния:
Здесь мы также вычисляем новый счет для этого хода. Это сумма тайлов, созданных в результате слияний.
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();
}
}
}Теперь мы можем встроить это в массив результатов. Как только плитки из нашего списка заканчиваются, остальные заполняются значением «0», чтобы указать, что они пусты:
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, и это позволит нам легко увидеть различия.
Во-первых, нам нужен способ распечатать игровое поле.
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());
}В этом примере мы просто собираемся печатать на консоль, поэтому System.out.print достаточно. Для настоящей игры мы хотели бы улучшить графику:
Мы почти готовы к работе. Нам просто нужно все уладить.
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 для структурирования этого кода по причинам, которые мы увидим позже.
public Board makeMove(Board input) {
return Arrays.stream(Move.values())
.map(input::move)
.max(Comparator.comparingInt(board -> generateScore(board, 0)))
.orElse(input);
}Мы начнем с того, что перепишем метод makeMove() внутри нашего класса Human:
Для каждого возможного направления, в котором мы можем двигаться, мы создаем новую доску, а затем запускаем алгоритм подсчета очков — «Переход на этой доске и глубина 0. Затем мы выбираем ход, который имеет лучший результат.
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();
}Затем наш метод generateScore() имитирует каждое возможное перемещение компьютера, то есть размещение «2» или «4» в каждой пустой ячейке, а затем смотрит, что может произойти дальше: ~~ ~
Если мы достигли предела глубины, то мы немедленно остановимся и подсчитаем окончательный балл того, насколько хороша эта доска; в противном случае мы продолжаем нашу симуляцию.
Наш метод calculateScore() является продолжением нашей симуляции, выполняющей часть уравнения, связанную с движением человека.
private int calculateScore(Board board, int depth) {
return Arrays.stream(Move.values())
.map(board::move)
.mapToInt(newBoard -> generateScore(newBoard, depth))
.max()
.orElse(0);
}«Это очень похоже на описанный выше метод makeMove(), но мы возвращаем текущий счет вместо реальной доски:
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. Удаление неиграбельных ветвей
Следующее, что мы можем сделать, это удалить все неиграбельные ветки. То есть каждый раз, когда ход человека приводит к неизменной доске. Почти наверняка это ответвления, которые приведут к худшим результатам — они фактически дают компьютеру свободу действий, — но они требуют от нас времени обработки для их выполнения.
@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);
}Для этого нам нужно реализовать метод equals на нашей плате, чтобы мы могли сравнивать их:
return Arrays.stream(Move.values())
.parallel()
.map(board::move)
.filter(moved -> !moved.equals(board))
........Затем мы можем добавить несколько фильтров к нашим потоковым конвейерам, чтобы остановить обработку всего, что не изменилось.
Это оказывает минимальное влияние на начальные этапы игры — когда заполненных ячеек очень мало, очень мало ходов, которые можно обрезать. Однако позже это начинает оказывать гораздо большее влияние, сокращая время перемещения до нескольких секунд.
5. Резюме
Здесь мы построили фреймворк для игры 2048. Затем мы вписали в него решатель, чтобы играть лучше. Все приведенные здесь примеры можно найти на GitHub.