Я работаю над реализацией минимакса в настольной игре, но у меня возникают проблемы при поиске дерева состояний. Я вполне уверен, что это либо
- моя реализация минимакса, которая неверна, либо
- способ построения моего следующего состояния, в котором минимакс будет выполнять поиск, или
- комбинация 1 и 2
Я сидел, сочиняя код для игры наилучшим образом, насколько мог. Это в первую очередь для практики, но также для того, чтобы попытаться отделить вещи как можно лучше. Но это решение возможно стало чем-то вроде препятствия для моего прогресса в минимаксе, потому что код самой игры стал немного запутанным. Это сделало состояние отладки в игре немного сложным. Тем не менее, благодаря тщательной отладке я чувствую уверенность в том, что состояние игры поддерживается на хорошем уровне, когда я играю в игру, в которой я чередуюсь между двумя игроками-людьми, то есть я не делаю минимаксного поиска по состоянию игры. Но как только я запускаю минимаксный поиск, игровое состояние начинает довольно быстро распадаться, как если бы я неправильно выполнял свою минимаксную рекурсию или строил свое следующее состояние.
Перед тем, как показать свою работу Сделано в отношении минимакса. Сначала я расскажу, как моделируется игра, чтобы убедиться, что вы располагаете необходимой информацией. После этого я покажу пример вывода игры, в которой запущен минимакс. Я попытался прокомментировать вывод, чтобы вы могли видеть, что происходит неправильно .
Давайте доберемся до этого.
Игра представляет собой настольную игру из 3 х 4 клетки вот так:
+---+---+---+
| | | | 0 <- Starting row of Black player
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| | | | 3 <- Starting row of Red player
+---+---+---+
0 1 2
Я представлю классы, которые я построил сейчас. Я опущу обобщенный c код, подобный конструкторам и методам get / set, и выделю только важные методы, которые изменяют состояние экземпляра класса.
Класс Board моделируется следующим образом:
public class Board
{
public static final int ROWS = 4;
public static final int COLUMNS = 3;
private Cell[][] cells;
public Board()
{
initialize();
}
private void initialize()
{
cells = new Cell[ROWS][COLUMNS];
for (int row = 0; row < ROWS; row++)
{
for (int column = 0; column < COLUMNS; column++)
{
cells[row][column] = new Cell(row, column);
}
}
}
public Board getDeepCopy(State state)
{
Board boardCopy = new Board();
for (int row = 0; row < ROWS; row++)
for (int column = 0; column < COLUMNS; column++)
boardCopy.cells[row][column] = cells[row][column].getDeepCopy(state);
return boardCopy;
}
//Other generic logic
...
}
Я создал метод getDeepCopy(State state) в паре классов, которые я использую для создания копии текущего состояния игры, в котором минимакс будет выполнять поиск, чтобы не изменять реальное состояние игры. Так что этот метод будет повторяться в других классах, как вы увидите.
Класс Cell выглядит следующим образом
public class Cell
{
private String content;
private Piece piece;
private int row;
private int column;
public Cell getDeepCopy(State state)
{
Cell c = new Cell(row, column);
c.content = content;
c.piece = piece != null ? piece.getDeepCopy(state) : null;
return c;
}
//Other generic logic
...
}
Класс Piece определен как
public class Piece
{
private Point point;
private String symbol;
public Piece getDeepCopy(State state)
{
return state.getBoard().getCells()[this.getPoint().getY()][this.getPoint().getX()].getPiece();
}
//Other generic logic
...
}
В игре 2 игрока, красный и черный игрок. У каждого из них есть по 4 штуки
Класс Player выглядит следующим образом:
public class Player
{
private Color color;
private int score;
private Stack<Piece> pieces;
private ArrayList<Piece> placedPieces;
public static final int MAX_PIECES = 4;
private void initializePieces()
{
pieces = new Stack<>();
placedPieces = new ArrayList<>();
for (int i = 0; i < MAX_PIECES; i++)
{
pieces.push(new Piece(color.getSymbol()));
}
}
public Piece getAvailablePiece()
{
return pieces.empty() ? null : pieces.pop();
}
public void returnPiece(Piece piece)
{
if (pieces.size() != MAX_PIECES)
{
pieces.push(piece);
}
}
public void updatePlacedPieces(Piece piece)
{
if (!placedPieces.contains(piece))
placedPieces.add(piece);
else
for (Piece match : placedPieces)
if (piece.equals(match))
match.setPoint(piece.getPoint());
}
//Other generic logic
...
}
Теперь перейдем к более тяжелым частям игры, состоянию игры и алгоритму минимакса. Все игровое состояние представлено в классе State, как показано ниже (обратите внимание на метод getDeepCopy(), который, я подозреваю, является одним из главных виновников)
public class State
{
private int points;
private Board board;
private Player turn;
private Player opponent;
private Player redPlayer;
private Player blackPlayer;
private Move move;
private State parent;
private ArrayList<Move> availableMoves;
private int depth;
// Root state (s_0)
public State(int points)
{
this.points = points;
redPlayer = new Player(Color.Red);
blackPlayer = new Player(Color.Black);
turn = redPlayer;
opponent = blackPlayer;
depth = 0;
board = new Board();
parent = null;
}
// Child states from root state (s_1, s_2, ... s_n)
public State(State parent, Move move)
{
this.parent = parent;
this.move = move;
redPlayer = parent.getRedPlayer();
blackPlayer = parent.getBlackPlayer();
depth = parent.depth + 1;
points = parent.getPoints();
board = parent.getBoard();
passTurn(parent.getTurn());
availableMoves = Logic.getAllMoves(this);
}
public void passTurn(Player lastTurn)
{
if (lastTurn.equals(redPlayer))
{
turn = blackPlayer;
opponent = redPlayer;
}
else
{
turn = redPlayer;
opponent = blackPlayer;
}
System.out.println(String.format("\nTurn: %s", turn.toString()));
}
public State getDeepCopy(State state, Move move)
{
State stateCopy = new State();
stateCopy.move = move;
stateCopy.parent = state.getParent();
stateCopy.points = state.getPoints();
stateCopy.redPlayer = state.getRedPlayer();
stateCopy.blackPlayer = state.getBlackPlayer();
stateCopy.turn = state.getTurn();
stateCopy.opponent = state.getOpponent();
stateCopy.depth = state.getDepth();
stateCopy.board = state.getBoard().getDeepCopy(state); // Here the deep copy begins
stateCopy.availableMoves = state.getAvailableMoves();
return stateCopy;
}
//Other generic logic
}
Игра выполняется в основном классе называется Game, где я чередую движение человека и движения ИИ. Все игровые логики c обрабатываются в классе Logic, с использованием только static методов. Этот класс реализует правила игры, например, если игрок хочет вставить фигуру, и ему помогает класс BoardManager (также только с методами static), который выполняет операции на доске (размещение фигуры, удаление кусок, и т. д. c.). Таким образом, класс Logic не содержит состояния, равно как и класс BoardManager, они только изменяют текущее состояние в зависимости от экземпляра состояния игры.
Вот класс Game с выделенными наиболее важными методами
public class Game
{
private State state;
private boolean playing;
public void play() throws IOException
{
drawBoard();
System.out.println(String.format("First player to make a move is %s", state.getTurn().toString()));
playing = true;
while (!isGameOver() && playing)
if (isHumanPlayer())
doHumanMove();
else
doAIMove();
}
private void doHumanMove() throws IOException
{
Choice choice = getChoice();
boolean isMoveOk = false;
Move move = null;
switch (choice)
{
case INSERT:
System.out.print("Enter cell to insert on: ");
Point to = getPointFromUser();
move = new Move(to, state.getRedPlayer(), Move.Type.Insert);
isMoveOk = Logic.doMove(move, state);
break;
case ...
}
if (isMoveOk)
{
drawBoard();
state = new State(state, move);
}
}
private void doAIMove()
{
Move move = MiniMax.search(0, state, false);
state = new State(state, move);
drawBoard();
}
}
Теперь перейдем к самой мелкой части, минимаксному классу. Я вызываю минимакс с помощью метода search(), как видно выше в методе play() Game. Затем я звоню miniMax() на depth, текущем State и о том, является ли текущий игрок maximizer. Я надеюсь, что это самоочевидно, посмотрев на код
public class MiniMax
{
private static final int maxDepth = 2;
public static Move search(int depth, State state, boolean isPlayerMaximizer)
{
System.out.println("Starting MiniMax search...");
Value v = miniMax(depth, state, isPlayerMaximizer);
return v.getMove();
}
private static Value miniMax(int depth, State state, boolean isPlayerMaximizer)
{
state.getBoard().draw();
if (depth == maxDepth || state.getTurn().getScore() == state.getPoints())
return getScore(state);
if (isPlayerMaximizer)
return getMax(depth, state);
else
return getMin(depth, state);
}
private static Value getMax(int depth, State state)
{
int bestScore = Integer.MIN_VALUE;
Move bestMove = null;
state.setAvailableMoves(Logic.getAllMoves(state)); // Is this wrong?
for (Move move : state.getAvailableMoves())
{
State nextState = state.getDeepCopy(state, move); // Copy of state to work on
Logic.doMove(move, nextState);
nextState.passTurn(nextState.getTurn());
Value val = miniMax(depth + 1, nextState, false);
if (val.getValue() >= bestScore)
{
bestScore = val.getValue();
bestMove = move;
}
}
if (bestMove != null)
Logic.doMove(bestMove, state);
return new Value(bestScore, bestMove);
}
private static Value getMin(int depth, State state)
{
int bestScore = Integer.MAX_VALUE;
Move bestMove = null;
state.setAvailableMoves(Logic.getAllMoves(state));
for (Move move : state.getAvailableMoves())
{
State nextState = state.getDeepCopy(state, move);
Logic.doMove(move, nextState);
state.passTurn(nextState.getTurn());
Value val = miniMax(depth + 1, nextState, true);
if (val.getValue() <= bestScore)
{
bestScore = val.getValue();
bestMove = move;
}
}
if (bestMove != null)
Logic.doMove(bestMove, state);
return new Value(bestScore, bestMove);
}
private static Value getScore(State state)
{
Player maximizer = state.getRedPlayer();
Player minimizer = state.getBlackPlayer();
if (state.getTurn() == maximizer && maximizer.getScore() == state.getPoints())
return new Value(10, state.getMove());
else if (state.getTurn() == minimizer && minimizer.getScore() == state.getPoints())
return new Value(-10, state.getMove());
else
return new Value(0, state.getMove());
}
private static class Value {
int value;
Move move;
public Value(int value, Move move) {
this.value = value;
this.move = move;
}
public Move getMove() {
return move;
}
public int getValue()
{
return value;
}
}
}
Вот пример игры, в которой я вызываю минимакс
Welcome!
// Initial state (human player makes a move)
+---+---+---+
| | | | 0
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| | | | 3
+---+---+---+
0 1 2
First player to make a move is Red
Choose an option:
1. Insert
2. Diagonal move
3. Attack
4. Jump
5. Exit
Input: 1
Enter cell to insert on: 0,3
Red is trying to do a Insert move...
Red placed a piece on the board at (0, 3).
// So far so good
+---+---+---+
| | | | 0
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| R | | | 3
+---+---+---+
0 1 2
Turn: Black
Starting MiniMax search... // OK, time for the AI to make a move
+---+---+---+
| | | | 0
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| R | | | 3
+---+---+---+
0 1 2
Black is trying to do a Insert move...
Black placed a piece on the board at (0, 0).
Turn: Red
// So far so good
+---+---+---+
| B | | | 0
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| R | | | 3
+---+---+---+
0 1 2
Black is trying to do a Insert move...
Black placed a piece on the board at (1, 0).
Turn: Red
// Black just did two moves in a row, looks like the turn is not passed on properly?
// Looks like after just 1 move with minimax the state of the game becomes wrong?
+---+---+---+
| B | B | | 0
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| R | | | 3
+---+---+---+
0 1 2
Black is trying to do a Insert move...
Black placed a piece on the board at (2, 0).
Turn: Red
// Take note that the piece inserted by black at (1, 0) no longer exists on the board below
// Does getDeepCopy() not work properly?
+---+---+---+
| B | | B | 0
+---+---+---+
| | | | 1
+---+---+---+
| | | | 2
+---+---+---+
| R | | | 3
+---+---+---+
0 1 2
Black is trying to do a Diagonal move...
Black moved diagonally from (0, 0) to (1, 1)
Turn: Red
// Same thing here, now the piece at (2, 0) is gone
// But the piece which was moved from (0, 0) to (1, 1) is still there
+---+---+---+
| | | | 0
+---+---+---+
| | B | | 1
+---+---+---+
| | | | 2
+---+---+---+
| R | | | 3
+---+---+---+
0 1 2
// Console output is duplicated because the move now happened on the actual game state
Black is trying to do a Diagonal move...
Black moved diagonally from (0, 0) to (1, 1)
// Red is trying to INSERT on a row which does not belong to Red
// Looks like the turn was not updated properly?
Red is trying to do a Insert move...
Invalid move: not starting row of Red.
Turn: Black
Спасибо за чтение этого довольно длинного поста. Я надеюсь, что смогу получить представление о том, что я делаю неправильно, поэтому я могу заставить этот минимаксный поиск работать правильно!