Минимаксный алгоритм TicTacToe возвращает неожиданные результаты в играх 4x4

Я не уверен, что здесь есть ошибка - если O играет в одной из более ранних позиций, она разветвляется, тогда как, если она играет в центре, она вызывает ничью. Предположительно, в игре 4x4 выиграть/проиграть еще сложнее, поэтому компьютер безразлично выбирает первую открытую клетку.

Ниже 1 обозначает принудительный ответ с помощью O, 2 обозначает разветвление с помощью X, а ? обозначает возможное место выигрыша.

X|O|
-+-+-
2|X|?
-+-+-
?| |1

X| |O
-+-+-
X|2|?
-+-+-
1| |?

X|2|?
-+-+-
O|X|
-+-+-
 |?|1

Я бросил попытки разобраться в коде — в комнате стало слишком шумно для моих коллег.

Однако я собрал свое собственное решение, которое, по моему мнению, стоит опубликовать. Он не предназначен для того, чтобы быть особенно эффективным - на самом деле я все еще жду, когда он сделает свой первый ход в тесте 4X4, но, похоже, он делает правильные вещи в тесте 3X3 (т.е. ничья против самого себя и победа над глупой стратегией). .

Он должен быть в состоянии обрабатывать доски неодинаковых размеров. Диагональ - это любая линия квадратов, идущая от одной стороны доски к другой с использованием диагональных шагов.

Как только он закончит пробег 4X4, я опубликую его ходы для сравнения.

public class TicTacToe {

    /**
     * Strategies for players.
     */
    interface Strategy {

        /**
         * Think up a place to move.
         *
         * @param board - The current board position.
         * @return Where to move.
         */
        Optional<Board.Square> think(Board board, Player player);
    }

    /**
     * Stupid strategy just finds the first empty square and plays it.
     */
    static final Strategy stupid = (Board board, Player player) -> {
        List<Board.Square> empty = board.getEmpties();
        if (empty.size() > 0) {
            return Optional.of(empty.get(0));
        }
        return Optional.empty();
    };

    /**
     * Minimax strategy.
     */
    static final Strategy minimax = new Strategy() {
        // Divide by this at each depth step.
        private static final double FACTOR = 3;

        // Memoize each discovered best move.
        Map<Player, Map<String, Board.Place>> best = new HashMap<>();

        {
            // One map for each player.
            for (Player p : Player.values()) {
                best.put(p, new HashMap<>());
            }
        }

        @Override
        public Optional<Board.Square> think(Board board, Player player) {
            Optional<Board.Square> win = Optional.empty();
            // Seen this one before?
            Board.Place seen = best.get(player).get(board.toString());
            if (seen == null) {
                double winValue = Double.NEGATIVE_INFINITY;
                for (Board.Square play : board.getEmpties()) {
                    double value = value(board, player, play, 1);
                    if (value > winValue) {
                        win = Optional.of(play);
                        winValue = value;
                    }
                }
                if (win.isPresent()) {
                    // Record my result.
                    best.get(player).put(board.toString(), win.get().place);
                } else {
                    System.out.println("No best found for " + board);
                }
            } else {
                // Reuse it.
                win = Optional.of(board.square(seen));
            }
            return win;
        }

        private double value(Board board, Player player, Board.Square move, double scale) {
            // My value.
            double value = 0;
            // Make the move.
            board.mark(player, move);
            try {
                // A win?
                if (!board.win()) {
                    // Remaining empties.
                    List<Board.Square> empties = board.getEmpties();
                    if (!empties.isEmpty()) {
                        // Record it's value.
                        double[] values = new double[empties.size()];
                        for (int i = 0; i < values.length; i++) {
                            // Try each further move negating and downscaling at each level.
                            values[i] = value(board, player.next(), empties.get(i), (scale / FACTOR) * -1);
                        }
                        // Add them up.
                        value += DoubleStream.of(values).sum();
                    }
                } else {
                    // Somebody already won.
                    value = scale;
                }
            } finally {
                //System.out.println("Value of " + board + " to player " + player + " = " + value);
                // Unroll the move.
                board.unmark(player, move);
            }
            return value;
        }
    };

    /**
     * There are exactly two players.
     */
    enum Player {

        O, X;

        /**
         * Each player has a strategy.
         *
         * Defaults to stupid.
         */
        private Strategy strategy = stupid;

        /**
         * What mark they make on the board.
         *
         * @return String representing the mark they make.
         */
        public char mark() {
            // The mark they make is the first character of their name.
            return name().charAt(0);
        }

        /**
         * Who is the next player.
         *
         * @return The other player.
         */
        public Player next() {
            return other(this);
        }

        /**
         * Who is the other player.
         *
         * @return The other player.
         */
        static Player other(Player it) {
            return it == O ? X : O;
        }

        public Strategy getStrategy() {
            return strategy;
        }

        public Player setStrategy(Strategy strategy) {
            this.strategy = strategy;
            return this;
        }
    }

    /**
     * The board.
     */
    static class Board {

        /**
         * Top left corner is 0,0. Access is [y][x].
         */
        final Square[][] board;
        // The board as columns.
        final List<List<Square>> columns;
        // The dagonals.
        final List<List<Square>> diagonals;
        // For sense checking.
        final int width;
        final int height;
        // Counts for each player - useful optimisation.
        final int[] counts = new int[Player.values().length];

        // A clear square.
        private static final char Clear = ' ';

        public Board(int width, int height) {
            this.width = width;
            this.height = height;
            board = new Square[height][];
            for (int y = 0; y < height; y++) {
                board[y] = new Square[width];
                // Fill it.
                for (int x = 0; x < width; x++) {
                    board[y][x] = new Square(x, y);
                }
            }
            // Build my columns lists.
            columns = new ArrayList<>();
            for (int x = 0; x < width; x++) {
                List<Square> column = new ArrayList<>();
                for (int y = 0; y < height; y++) {
                    column.add(board[y][x]);
                }
                columns.add(column);
            }
            // And the diagonals.
            diagonals = new ArrayList<>();
            for (int y = 0; y <= height - width; y++) {
                List<Square> diagonal = new ArrayList<>();
                // Left to right.
                for (int x = 0; x < width; x++) {
                    diagonal.add(board[y + x][x]);
                }
                diagonals.add(diagonal);
                // Right to left.
                diagonal = new ArrayList<>();
                for (int x = 0; x < width; x++) {
                    diagonal.add(board[y + x][width - 1 - x]);
                }
                diagonals.add(diagonal);
            }
        }

        public Board(int size) {
            this(size, size);
        }

        private Stream<List<Square>> asRows() {
            // Map each row to a list.
            return Arrays.stream(board).map(r -> Arrays.asList(r));
        }

        private Stream<List<Square>> asCols() {
            // Walk the columns.
            return columns.stream();
        }

        private Stream<List<Square>> asDiagonals() {
            // Walk the diagonals.
            return diagonals.stream();
        }

        private boolean winning(List<Square> row) {
            //System.out.println("winner(" + row + ")");
            if (row.isEmpty()) {
                return false;
            }
            Optional<Player> owner = row.get(0).owner;
            // First square owned.
            if (!owner.isPresent()) {
                return false;
            }
            return !row.stream()
                    //.peek(s -> System.out.println(s))
                    .anyMatch((s) -> (!s.owner.isPresent() || s.owner.get() != owner.get()));
        }

        public Square square(Place place) {
            return board[place.y][place.x];
        }

        private Optional<Player> getWinner() {
            Optional<Player> winner = Optional.empty();
            // Must be at least enough plays by one player to reach across/down the board.
            OptionalInt min = IntStream.of(counts).min();
            if (!min.isPresent() || min.getAsInt() < Math.min(width, height)) {
                // Nobody can posibly have won.
                return winner;
            }
            List<List<Square>> winners = asRows()
                    .filter(r -> winning(r))
                    .collect(Collectors.toList());
            if (winners.isEmpty()) {
                winners = asCols()
                        .filter(r -> winning(r))
                        .collect(Collectors.toList());
            }
            if (winners.isEmpty()) {
                winners = asDiagonals()
                        .filter(r -> winning(r))
                        .collect(Collectors.toList());
            }
            if (!winners.isEmpty()) {
                winner = winners.get(0).get(0).owner;
            }
            return winner;
        }

        private boolean isDrawn() {
            // All square occupied - counts add up to width*height.
            return IntStream.of(counts).sum() == width * height;
        }

        private boolean win() {
            return getWinner().isPresent();
        }

        /**
         * One square of the board.
         *
         * Remember that a Square is ON a board - i.e. it is a sub-object of a Board. Do not attempt to memoize Squares as they will hold a reference to their parent board.
         */
        class Square {

            // The owner of it.
            Optional<Player> owner = Optional.empty();
            // where it is on the board.
            final Place place;

            public Square(Place place) {
                this.place = place;
            }

            public Square(int x, int y) {
                this(new Place(x, y));
            }

            public char getMark() {
                return owner.isPresent() ? owner.get().mark() : Clear;
            }

            public boolean isTaken() {
                return owner.isPresent();
            }

            @Override
            public String toString() {
                return place + "(" + (owner.isPresent() ? owner.get().toString() : "") + ")";
            }

            private void take(Player player) {
                if (!isTaken()) {
                    owner = Optional.of(player);
                    // Keep track of the counts.
                    counts[player.ordinal()] += 1;
                } else {
                    throw new IllegalStateException("Attempt to take taken square!"
                            + " Square=" + this
                            + " Player=" + player
                            + " board=" + Board.this.toString()
                    );
                }
            }

            private void release(Player player) {
                if (isTaken()) {
                    if (owner.get() == player) {
                        owner = Optional.empty();
                        // Keep track of the counts.
                        counts[player.ordinal()] -= 1;
                    } else {
                        throw new IllegalStateException("Attempt to release other player's square!"
                                + " Square=" + this
                                + " Player=" + player
                                + " board=" + Board.this.toString()
                        );
                    }
                } else {
                    throw new IllegalStateException("Attempt to release untaken square!"
                            + " Square=" + this
                            + " Player=" + player
                            + " board=" + Board.this.toString()
                    );
                }
            }

        }

        private List<Square> getEmpties() {
            // Walk all squares.
            return Arrays.stream(board)
                    // Unroll each row.
                    .flatMap(l -> Arrays.stream(l))
                    // All not taken.
                    .filter(s -> !s.isTaken())
                    // As a list.
                    .collect(Collectors.toList());
        }

        /**
         * A place on the board.
         */
        class Place {

            final int x;
            final int y;

            public Place(int x, int y) {
                // Sense check.
                if (x < 0 || x >= width) {
                    throw new IllegalArgumentException("Off board: x = " + x);
                }
                if (y < 0 || y >= height) {
                    throw new IllegalArgumentException("Off board: x = " + x);
                }
                this.x = x;
                this.y = y;
            }

            @Override
            public String toString() {
                return "{" + x + "," + y + '}';
            }

        }

        /**
         * Mark a place on the board.
         *
         * @param player
         */
        public void mark(Player player, Square square) {
            // Take the square.
            square.take(player);
        }

        /**
         * UnMark a place on the board.
         *
         * Confirms the mark first.
         */
        public void unmark(Player player, Square square) {
            square.release(player);
        }

        @Override
        public String toString() {
            return Arrays.stream(board)
                    .map(r -> Arrays.stream(r)
                            .map(s -> String.valueOf(s.getMark()))
                            .collect(Collectors.joining("", "[", "]")))
                    .collect(Collectors.joining(""));
        }

    }

    class Game {

        // The current board state.
        final Board board;

        public Game(Board board) {
            this.board = board;
        }

        public Game(int size) {
            this(new Board(size));
        }

        public Game(int width, int height) {
            this(new Board(width, height));
        }

        private void play(Player firstPlayer) {
            boolean gameFinished = false;
            Player player = firstPlayer;
            do {
                Optional<Board.Square> move = player.getStrategy().think(board, player);
                if (move.isPresent()) {
                    board.mark(player, move.get());
                    System.out.println("Moved: " + move.get() + " -> " + board);
                } else {
                    System.out.println("No move!");
                }
                // Has anyone won?
                Optional<Player> winner = board.getWinner();
                if (winner.isPresent()) {
                    System.out.println("Player " + winner.get() + " won! " + board);
                    gameFinished = true;
                } else {
                    if (board.isDrawn()) {
                        System.out.println("Draw! " + board);
                        gameFinished = true;
                    }
                }
                // Next player.
                player = player.next();
            } while (!gameFinished);

        }

    }

    private void testStupid() {
        // Both start off stupid.
        new Game(3).play(Player.X);
    }

    private void testMinimax() {
        // Test minimax strategy.
        Board testBoard = new Board(3);
        // Set it up like http://neverstopbuilding.com/minimax
        testBoard.mark(Player.O, testBoard.board[0][0]);
        testBoard.mark(Player.X, testBoard.board[0][2]);
        testBoard.mark(Player.X, testBoard.board[1][0]);
        testBoard.mark(Player.X, testBoard.board[2][0]);
        testBoard.mark(Player.O, testBoard.board[2][1]);
        testBoard.mark(Player.O, testBoard.board[2][2]);
        // What does the strategy do?
        Optional<Board.Square> play = minimax.think(testBoard, Player.X);
        System.out.println("minimax(" + testBoard + ") = " + play);
    }

    private void test3X3Game() {
        // Play a game.
        // Change strategies.
        new Game(3).play(Player.X);
    }

    private void test4X4Game() {
        // Play a game.
        new Game(4).play(Player.X);
    }

    public void test() {
        testStupid();
        testMinimax();
        System.out.println("Test minmax vs stupid");
        Player.X.setStrategy(minimax);
        test3X3Game();
        System.out.println("Test minmax vs minmax");
        Player.O.setStrategy(minimax);
        test3X3Game();
        System.out.println("Test 4 X 4");
        test4X4Game();
    }

    public static void main(String args[]) {
        try {
            new TicTacToe().test();
        } catch (Throwable t) {
            t.printStackTrace(System.err);
        }
    }

}

При игре в минимакс против самого себя он перемещается:

Moved: {1,1}(X) -> [   ][ X ][   ]
Moved: {0,0}(O) -> [O  ][ X ][   ]
Moved: {2,2}(X) -> [O  ][ X ][  X]
Moved: {0,2}(O) -> [O  ][ X ][O X]
Moved: {0,1}(X) -> [O  ][XX ][O X]
Moved: {2,1}(O) -> [O  ][XXO][O X]
Moved: {1,0}(X) -> [OX ][XXO][O X]
Moved: {1,2}(O) -> [OX ][XXO][OOX]
Moved: {2,0}(X) -> [OXX][XXO][OOX]
Draw! [OXX][XXO][OOX]

Обратите внимание, что эта ОС не публикует ходы OP, поэтому явно что-то не так с алгоритмом OP.