Алгоритм MiniMax не умный после добавленной глубины

Question

Игра в крестики-нолики, класс ИИ недостаточно умен, чтобы быть непобедимым.

Класс ИИ должен рассчитывать наилучшее место с учетом крестики-нолики. Метод 'getBestSpot' вызывает min-max до конца игры. Класс gameState используется для проверки статуса игры и определения победителя.

Доска клонируется с помощью конструктора копирования, поэтому фактические свойства платы не изменяются. Затем он получает доступные места на скопированной доске и играет на каждом из них. Он продолжает делать это до тех пор, пока игра не закончится, а затем он оценивает игровое место с учетом «глубины» и результата:

Оценка по делу:

• победа = 1 - глубина
• потерять = -1 - глубина
• связь = 0 - глубина

'Object []' используется для передачи обоих значений: int bestSpot, String bestSpot между min-max. Вместо этого будет изменено использование int [].

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

В этом случае токен оппонента равен O, и ИИ (X) должен играть на месте 0, чтобы минимизировать / предотвратить победу противника (O), спот 0 должен получить наивысший счет потому что, если ИИ (X) не будет играть там, оппонент (O) будет играть, и это сделает другие доступные места меньшими, потому что getScore () вернет -1 - depth, когда противник выиграет. Неудачный тест:

@Test
public void testMinimizedSpotCaseLosing() {
    newGrid = new String[]{"0", "O", "X",
                           "O", "X", "5",
                           "O", "7", "8"};
    board.setGrid(newGrid);
    assertEquals( "0", miniMax.minimizedSpot(board, 0)[0] );
}


Test output:

    junit.framework.AssertionFailedError: 
    Expected :0
    Actual   :5

Вот класс ИИ:

public class AI {

    private String token;
    private GameState gameState;
    private String opponentToken;

    AI(String token) {
        this.token = token;
        gameState = new GameState();
        opponentToken = null;

        setOpponentToken();
    }


    public String getToken() {
        return token;
    }

    public String getOpponentToken() {
        return opponentToken;
    }

    public void setOpponentToken() {
        if(token.equals("X")) {
            opponentToken = "O";
        } else {
            opponentToken = "X";
        }
    }

    public int getBestSpot(Board board) {
        String[] grid = board.getGrid();
        if( !grid[4].equals("X") && !grid[4].equals("O")) {
            return 4;
        } else {
            return Integer.parseInt((String) maximizedSpot(board, 0)[0]);
        }
    }

    public Object[] maximizedSpot(Board board, int depth) {
        Board boardClone = new Board(board);

        int bestScore = 0;
        String bestSpot = null;
        int score;

        String[] availableSpots = boardClone.getAvailableSpots();

        for(String availableSpot: availableSpots) {
            int spot = Integer.parseInt(availableSpot);
            boardClone.setSpot(spot, token);
            depth += 1;

            if( gameState.finished(boardClone) ) {
                score = getScore(boardClone, depth);
            } else {
                Object[] minimizedSpot = minimizedSpot(boardClone, depth);
                score = (int) minimizedSpot[1];
            }
            boardClone.setGrid(board.getGrid());

            if( bestScore == 0 || score > bestScore ) {
                bestScore = score;
                bestSpot = availableSpot;
            }

        }
        return new Object[]{bestSpot, bestScore};
    }

    public Object[] minimizedSpot(Board board, int depth) {
        Board boardClone = new Board(board);

        int bestScore = 0;
        String bestSpot = null;
        int score;


        String[] availableSpots = boardClone.getAvailableSpots();

        for(String availableSpot: availableSpots) {
            int spot = Integer.parseInt(availableSpot);
            boardClone.setSpot(spot, opponentToken);
            depth += 1;

            if ( gameState.finished(boardClone) ) {
                score = getScore(boardClone, depth);
            } else {
                Object[] maximizedSpot = maximizedSpot(boardClone, depth);
                score = (int) maximizedSpot[1];
            }
            boardClone.setGrid(board.getGrid());

            if (bestScore == 0 || score < bestScore) {
                bestScore = score;
                bestSpot = availableSpot;
            }
        }
        return new Object[]{bestSpot, bestScore};
    }

    public int getScore(Board board, int depth) {
        if( gameState.finished(board) && gameState.getWinnerToken() != null ) {
            String winnerToken = (gameState.getWinnerToken());
            if(winnerToken.equals(token)) {
                return 1 - depth;
            } else if (winnerToken.equals(opponentToken)) {
                return -1 - depth;
            }
        }
        return 0 - depth;
    }
}

Доска класса

public class Board {

private String[] grid;
private int[][] winCombinations;

public Board() {
    this.grid = new String[]{"0", "1", "2", "3", "4", "5", "6", "7", "8"};
    this.winCombinations = new int[][]{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7,}, {2,5,8}, {0,4,8}, {2,4,6}};
}

public Board(Board sourceBoard) {
    this();
    System.arraycopy(sourceBoard.grid, 0, this.grid, 0, sourceBoard.grid.length);

    for (int i = 0; i < winCombinations.length; i++) {
        int[] line = winCombinations[i];
        System.arraycopy(sourceBoard.winCombinations[i], 0, line, 0, line.length);
    }
}

public String[] getGrid() {
    return grid;
}

public int[][] getWinCombinations() {
    return winCombinations;
}

public String[] getAvailableSpots() {
    ArrayList<String> resultList = new ArrayList<String>();
    for (String aGrid : grid) {
        if (!aGrid.equals("X") && !aGrid.equals("O")) {
            resultList.add(aGrid);
        }
    }
    return resultList.toArray(new String[resultList.size()]);
}

public void reset() {
    grid = new String[]{"0", "1", "2", "3", "4", "5", "6", "7", "8"};
}

public void setSpot(int i, String token) {
    grid[i] = token;
}

public void setGrid(String[] grid) {
    this.grid = grid;
}

}

GameState класс:

public class GameState {

private String winner;

public GameState() {
    this.winner = null;
}

public boolean checkTie(Board board) {
    String[] availableSpots = board.getAvailableSpots();

    return availableSpots.length == 0 && !checkWin(board);
}

public boolean checkWin(Board board) {
    int[][] winCombinations = board.getWinCombinations();
    String[] grid = board.getGrid();

    for (int[] winCombination : winCombinations) {
        boolean combinationState = checkWinCombination(winCombination, board);

        if (combinationState) {
            // Get token inside winCombination and set to winner variable.
            setWinnerToken(grid[winCombination[0]]);
            return true;
        }
    }
    return false;
}

public boolean checkWinCombination(int[] combination, Board board) {
    String[] grid = board.getGrid();
    return grid[combination[0]].equals("X") && grid[combination[1]].equals("X") && grid[combination[2]].equals("X") || grid[combination[0]].equals("O") && grid[combination[1]].equals("O") && grid[combination[2]].equals("O");
}

public boolean finished(Board board) {
    return checkWin(board) || checkTie(board);
}

public String getWinnerToken() {
    return winner;
}

public void setWinnerToken(String token) {
    winner = token;
}
}