1. 序章

最近、ゲーム2048を解決するためのアルゴリズムを検討しました。これについては、実際のコードではなく、理論的な観点から説明しました。

ここでは、これの実装をJavaで記述します。これは、人間とコンピューターの両方のプレーヤーとしてプレイし、より最適なゲームをどれだけ上手くプレイできるかを示します。

2. 初期設定

最初に必要なのは、ゲームをプレイして進行状況を確認できるセットアップです。

これにより、ゲームをプレイするために必要なすべての構成が得られ、とにかくランダムなタイルのみを配置するコンピュータープレーヤーが完全に実装されます。 これにより、ゲームをプレイするための「人間」プレーヤーを実装する余地が生まれます。

2.1. ゲームボード

何よりもまず、ゲームボードが必要です。 これは、数値を配置できるセルのグリッドです。

作業を少し簡単にするために、セルの位置の簡単な表現から始めましょう。 これは文字通り、座標のペアの単なるラッパーです。

public class Cell {
    private final int x;
    private final int y;

    // constructor, getters, and toString
}

ボード自体を表すクラスを作成できるようになりました。 これにより、値が単純な2次元配列に格納されますが、上記の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);
    }
}

これは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<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 % o f時間、および「2」他の90%。

2.2. 「人間」のプレーヤーとシフトするタイル

次に必要なのは「人間」のプレイヤーです。 これは最終目標ではありませんが、移動するたびにランダムな方向を選んでタイルをシフトする純粋にランダムなプレーヤーです。これは、私たちが構築できる場所として機能します私たちの最適なプレーヤーを作るために。

まず、実行可能な移動の列挙を定義する必要があります。

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

次に、これらの方向の1つにタイルを移動することで移動をサポートするために、ボードクラスを拡張する必要があります。ここでの複雑さを軽減するために、常にタイルを移動するようにボードを回転させます。同じ方向。

これは、ボードを転置する手段と反転する手段の両方が必要であることを意味します。

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

準備はほぼ整いました。 設定する必要があります。

これは、ボードと2人のプレーヤーを作成し、コンピューターに2つの最初の動きをさせることを意味します。つまり、ボードに2つのランダムな数字を配置します。

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 を多用して、このコードの構造化を支援します。これについては、後で説明します。

まず、 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. ファイナルボードのスコアリング

現在、人間とコンピュータープレーヤーによる前後の動きをシミュレートできる状況にあり、十分にシミュレートしたときに停止します。 シミュレーションブランチごとに最終ボードのスコアを生成できる必要があります。これにより、どのブランチが追跡したいのかを確認できます。[X01X]

スコアリングは要素の組み合わせであり、それぞれがボード上のすべての行とすべての列に適用されます。 これらはすべて合計され、合計が返されます。

そのため、スコアを付けるために行と列のリストを生成する必要があります。

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ストリームを使用することの大きな利点です。各ストリームに単一のステートメントを追加するだけで、この作業を並行して行うことができます。

この変更だけでも、1回の移動で約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をプレイするためのフレームワークを構築しました。 次に、より良いゲームをプレイできるように、これにソルバーを書き込みました。 ここに見られるすべての例を見つけることができます GitHubで

ルールを変えて、ゲームプレイにどのように影響するかを確認してみませんか。