Implementierung eines 2048 Solvers in Java

1. Einleitung

Kürzlich haben wir uns einen Algorithmus zur Lösung des Spiels 2048 angesehen. Wir haben dies unter theoretischen Gesichtspunkten diskutiert und nicht mit echtem Code dahinter.

Hier schreiben wir eine Implementierung in Java. Dies wird sowohl als Mensch als auch als Computer gespielt und zeigt, wie gut ein optimaleres Spiel gespielt werden kann.

2. Ersteinrichtung

Das erste, was wir brauchen, ist ein Setup, in dem wir das Spiel spielen und sehen können, wie der Fortschritt verläuft.

Dies gibt uns alle Konstrukte, die wir zum Spielen des Spiels benötigen, und implementiert den Computerspieler vollständig - der ohnehin nur zufällige Kacheln platziert. Dies gibt uns dann die Möglichkeit, einen „menschlichen“ Spieler zum Spielen des Spiels zu implementieren.

2.1. Spielbrett

Vor allem brauchen wir ein Spielbrett. Dies ist ein Gitter von Zellen, in die Zahlen eingefügt werden können.

Beginnen wir mit einer einfachen Darstellung eines Zellenstandorts , um die Arbeit mit einigen Dingen zu vereinfachen . Dies ist buchstäblich nur ein Wrapper um ein Koordinatenpaar:

public class Cell { private final int x; private final int y; // constructor, getters, and toString }

Wir können jetzt eine Klasse schreiben, um das Board selbst darzustellen . Dadurch werden die Werte in einem einfachen zweidimensionalen Array gespeichert, aber wir können über die obige Cell- Klasse auf sie zugreifen :

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

Dies ist eine unveränderliche Klasse, die eine Tafel darstellt und die wir abfragen können, um den aktuellen Status herauszufinden. Es verfolgt auch eine aktuelle Punktzahl, auf die wir später noch eingehen werden.

2.2. Ein Computer-Player und das Platzieren von Kacheln

Jetzt, wo wir ein Spielbrett haben, wollen wir damit spielen können. Das erste, was wir wollen, ist der Computer-Player, da dies ein rein zufälliger Player ist und später genau so sein wird, wie er später benötigt wird.

Der Computer-Player legt lediglich eine Kachel in eine Zelle. Wir brauchen also einen Weg, um dies auf unserem Brett zu erreichen. Wir möchten, dass dies unveränderlich bleibt. Wenn Sie also eine Kachel platzieren, wird ein brandneues Brett im neuen Zustand erstellt.

Erstens möchten wir einen Konstruktor, der den tatsächlichen Board-Status annimmt , im Gegensatz zu unserem früheren, der gerade ein leeres Board erstellt hat:

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

Dies ist privat, sodass es immer nur von anderen Methoden innerhalb derselben Klasse verwendet werden kann. Dies hilft bei unserer Kapselung der Platine.

Als nächstes fügen wir eine Methode zum Platzieren einer Kachel hinzu. Dies gibt eine brandneue Karte zurück, die mit der aktuellen identisch ist, außer dass sie die angegebene Nummer in der angegebenen Zelle hat:

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

Schließlich werden wir eine neue Klasse schreiben, die einen Computerspieler darstellt. Dies wird eine einzige Methode haben, die das aktuelle Board nimmt und das neue zurückgibt:

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

Dadurch wird die Liste aller leeren Zellen von der Tafel abgerufen, eine zufällige ausgewählt und anschließend eine Zahl eingefügt. Wir werden zufällig entscheiden, 10% der Zeit eine „4“ in die Zelle zu setzen und die anderen 90% eine „2“.

2.2. Ein "menschlicher" Spieler und wechselnde Kacheln

Das nächste, was wir brauchen, ist ein „menschlicher“ Spieler. Dies wird nicht das Endziel sein, sondern ein rein zufälliger Spieler, der eine zufällige Richtung wählt, um die Kacheln bei jedem Zug zu verschieben. Dies wird dann als ein Ort dienen, auf dem wir aufbauen können, um unseren optimalen Spieler zu machen.

Zunächst müssen wir eine Aufzählung der möglichen Bewegungen definieren, die ausgeführt werden können:

public enum Move { UP, DOWN, LEFT, RIGHT }

Als nächstes müssen wir die Board- Klasse erweitern, um Bewegungen zu unterstützen, indem wir die Kacheln in eine dieser Richtungen verschieben. Um die Komplexität hier zu verringern, möchten wir das Brett so drehen, dass wir die Kacheln immer in die gleiche Richtung verschieben.

Dies bedeutet, dass wir ein Mittel benötigen, um das Board zu transponieren und umzukehren:

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

Durch das Transponieren der Platine werden alle Zeilen und Spalten vertauscht, sodass die Oberkante zur linken Kante wird. Durch Umkehren der Platine wird diese einfach so gespiegelt, dass die linke Kante zur rechten Kante wird.

Als nächstes fügen wir dem Board eine Methode hinzu, um einen Schritt in eine bestimmte Richtung zu machen und ein neues Board in den neuen Zustand zurückzugeben.

Wir erstellen zunächst eine Kopie des Board-Status, mit dem wir dann arbeiten können:

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

Als nächstes manipulieren wir unsere Kopie so, dass wir immer die Kacheln nach oben verschieben:

if (move == Move.LEFT || move == Move.RIGHT) { tiles = transpose(tiles); } if (move == Move.DOWN || move == Move.RIGHT) { tiles = reverse(tiles); }

Wir brauchen noch eine Reihe von Kacheln - diesmal die, in die wir das Endergebnis einbauen werden - und einen Tracker für die neue Punktzahl, die für diesen Zug erzielt wurde:

int[][] result = new int[tiles.length][]; int newScore = 0;

Jetzt, da wir bereit sind, Kacheln zu verschieben und die Dinge so manipuliert haben, dass wir immer in die gleiche Richtung arbeiten, können wir beginnen.

Wir können jede Spalte unabhängig von den anderen verschieben. Wir müssen nur die Spalten durchlaufen und wiederholen, beginnend mit dem Erstellen einer weiteren Kopie der Kacheln, die wir verschieben.

Dieses Mal bauen wir sie in eine LinkedList ein, weil wir in der Lage sein möchten, Werte einfach daraus zu entfernen . Wir fügen auch nur die tatsächlichen Kacheln mit Zahlen hinzu und überspringen leere Kacheln.

Dies erreicht unsere Verschiebung, aber noch nicht das Zusammenführen von Fliesen:

for (int x = 0; x < tiles.length; ++x) { LinkedList thisRow = new LinkedList(); for (int y = 0; y  0) { thisRow.add(tiles[x][y]); } }

Als nächstes müssen wir Kacheln zusammenführen. Wir müssen dies getrennt von den oben genannten tun; Andernfalls besteht die Gefahr, dass dieselbe Kachel mehrmals zusammengeführt wird.

Dies wird erreicht, indem eine weitere LinkedList der Kacheln aus den oben genannten erstellt wird. Diesmal wird sie jedoch zusammengeführt :

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

Here we're also calculating the new score for this move. This is the sum of the tiles created as a result of merges.

We can now build this into the result array. Once we've run out of tiles from our list, the rest get populated with the value “0” to indicate that they are blank:

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

Once we've finished shifting tiles, we need to manipulate them again back to the correct rotation. This is the exact opposite that we did earlier:

if (move == Move.DOWN || move == Move.RIGHT) { result = reverse(result); } if (move == Move.LEFT || move == Move.RIGHT) { result = transpose(result); }

And finally, we can build and return a new board with this new set of tiles and the newly calculated score:

 return new Board(result, this.score + newScore); }

We're now in a position where we can write our random “human” player. This does nothing more than generate a random move and call the above method to play that move:

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. Playing the Game

We have enough components to play the game, albeit not very successfully. However, soon we will be improving the way that the Human class plays, and this will allow us to see the differences easily.

First, we need a way to print out the game board.

For this example, we're just going to print to the console, so System.out.print is good enough. For a real game we would want to do better graphics:

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("|"); 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()); }

We're nearly ready to go. We just need to set things up.

This means creating the board, the two players, and having the computer make two initial moves – that is, placing two random numbers on the board:

Board board = new Board(4); Computer computer = new Computer(); Human human = new Human(); for (int i = 0; i < 2; ++i) { board = computer.makeMove(board); }

And now we have the actual game loop. This is going to be a repetition of the human and computer players taking turns, and stopping only when there are no empty cells left:

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());

At this point, if we were to run the program, we would see a random game of 2048 being played.

3. Implementing the 2048 Player

Once we have a base from which to play the game, we can start implementing the “human” player and play a better game than just picking a random direction.

3.1. Simulating Moves

The algorithm we are implementing here is based on the Expectimax algorithm. As such, the core of the algorithm is to simulate every possible move, allocate a score to each one, and select the one that does best.

We'll be making heavy use of Java 8 Streams to help structure this code, for reasons we'll see later.

We'll start by re-writing the makeMove() method from inside our Human class:

public Board makeMove(Board input) { return Arrays.stream(Move.values()) .map(input::move) .max(Comparator.comparingInt(board -> generateScore(board, 0))) .orElse(input); }

For every possible direction we can move in, we generate the new board and then start the scoring algorithm – passing in this board and a depth of 0. We then select the move that has the best score.

Our generateScore() method then simulates every possible computer move – that is, placing either a “2” or a “4” into every empty cell – and then sees what could happen next:

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

If we have reached our depth limit, then we'll immediately stop and calculate a final score for how good this board is; otherwise, we continue with our simulation.

Our calculateScore() method is then the continuation of our simulation, running the human move side of the equation.

This is very similar to the makeMove() method above, but we're returning the ongoing score instead of the actual board:

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. Scoring Final Boards

We're now in a situation where we can simulate moves back and forth by the human and computer players, stopping when we've simulated enough of them. We need to be able to generate a score for the final board in each simulation branch, so that we can see which branch is the one we want to pursue.

Our scoring is a combination of factors, each of which we are going to apply to every row and every column on the board. These all get summed together, and the total is returned.

As such, we need to generate a list of rows and columns to score against:

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

Then we take the list that we've built, score each of them, and sum the scores together. This is a placeholder that we're about to fill out:

return rowsToScore.stream() .mapToInt(row -> { int score = 0; return score; }) .sum();

Finally, we need actually to generate our scores. This goes inside the above lambda, and is several different factors that all contribute:

  • A fixed score for every row
  • The sum of every number in the row
  • Every merge possible in the row
  • Every empty cell in the row
  • The monotonicity of the row. This represents the amount the row is organized in ascending numerical order.

Before we can calculate the scores, we need to build some extra data.

First, we want a list of the numbers with blank cells removed:

List preMerged = row.stream() .filter(value -> value != 0) .collect(Collectors.toList());

We can then make some counts from this new list, giving the number of adjacent cells with the same number, with strictly ascending numbers and strictly descending numbers:

int numMerges = 0; int monotonicityLeft = 0; int monotonicityRight = 0; for (int i = 0; i  second) { monotonicityLeft += first - second; } else { monotonicityRight += second - first; } }

Now we can calculate our score for this row:

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;

The numbers selected here are relatively arbitrary. Different numbers will have an impact on how well the game plays, prioritizing different factors in how we play.

4. Improvements to the Algorithm

What we have so far works, and we can see that it plays a good game, but it's slow. It takes around 1 minute per human move. We can do better than this.

4.1. Parallel Processing

The obvious thing that we can do is to do work in parallel. This is a huge benefit of working with Java Streams – we can make this work in parallel by just adding a single statement to each stream.

This change alone gets us down to around 20 seconds per move.

4.2. Pruning Unplayable Branches

The next thing we can do is to prune out any branches that are unplayable. That is, any time that a human move results in an unchanged board. These are almost certainly branches that are going to result in worse outcomes – they are effectively giving the computer a free move – but they cost us processing time to pursue them.

To do this, we need to implement an equals method on our Board so that we can compare them:

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

We can then add some filters to our stream pipelines to stop processing anything that hasn't changed.

return Arrays.stream(Move.values()) .parallel() .map(board::move) .filter(moved -> !moved.equals(board)) ........

Dies hat nur minimale Auswirkungen auf die frühen Teile des Spiels - wenn nur sehr wenige gefüllte Zellen vorhanden sind, können nur sehr wenige Bewegungen getrimmt werden. Später wirkt sich dies jedoch viel stärker aus und reduziert die Bewegungszeiten auf nur wenige Sekunden.

5. Zusammenfassung

Hier haben wir ein Framework für das Spielen des Spiels 2048 erstellt. Dann haben wir einen Löser in dieses geschrieben, damit wir ein besseres Spiel spielen können. Alle hier gezeigten Beispiele finden Sie auf GitHub.

Warum nicht versuchen, die Regeln zu variieren, um zu sehen, wie sie sich auf das Gameplay auswirken?