Простая реализация игры 2048 в Java

Автор оригинала: Graham Cox.

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 emptyCells() {
        List 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);
    }
}

Это private , так что он может использоваться только другими методами в том же классе. Это помогает нам инкапсулировать плату.

Затем мы добавим метод для размещения плитки. Это возвращает совершенно новую плату, которая идентична текущей, за исключением того, что она имеет заданный номер в данной ячейке:

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 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;
}

Транспонирование доски приведет к замене всех строк и столбцов таким образом, что верхний край станет левым краем. Реверсирование доски просто отражает ее таким образом, что левый край становится правым краем.

Затем мы добавим метод в Доска сделать ход в заданном направлении и вернуть новый Доска в новом государстве.

Мы начинаем с создания копии состояния доски, с которой затем можем работать:

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 thisRow = new LinkedList<>();
    for (int y = 0; y < tiles[0].length; ++y) {
        if (tiles[x][y] > 0) {
            thisRow.add(tiles[x][y]);
        }
    }

Далее нам нужно объединить плитки. Нам нужно сделать это отдельно от вышеперечисленного; в противном случае мы рискуем объединить одну и ту же плитку несколько раз.

Это достигается путем создания еще одного Связанного списка плиток из приведенного выше, но на этот раз слияния по ходу работы:

LinkedList 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, чтобы помочь структурировать этот код, по причинам, которые мы увидим позже.

Мы начнем с переписывания метода 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> rowsToScore = new ArrayList<>();
for (int i = 0; i < board.getSize(); ++i) {
    List row = new ArrayList<>();
    List 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 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 – мы можем сделать эту работу параллельной, просто добавив один оператор в каждый поток.

Одно только это изменение сокращает время до 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 .

Почему бы не попробовать изменить правила, чтобы увидеть, как они влияют на игровой процесс.