Java Tic Tac Toe Minimax Ошибка

Пробовал отлаживать мой код MiniMax, но не нашел здесь проблемы. Основной метод — evalGame(), который возвращает 1 при победе, -1 при проигрыше и 0 при ничьей. Есть ли очевидные ошибки, которые я допустил в алгоритме MiniMax?

package tictactoe;

import static tictactoe.Player.*;

import java.util.Arrays;

public class MinimaxTTT {

    private Player[] board = new Player[9];
    private static Player player = X;

    public MinimaxTTT() {
        Arrays.fill(board, E);
        player = X;
    }

    public MinimaxTTT(Player[] b, Player p) {
        for(int i = 0; i < 9; i++) {
            board[i] = b[i];
        }
        player = p;
    }

    public static boolean checkWin(Player[] b, Player p) {
        if((b[0]==p&&b[1]==p&&b[2]==p) 
            || (b[0]==p&&b[3]==p&&b[6]==p)
            || (b[0]==p&&b[4]==p&&b[8]==p)
            || (b[0]==p&&b[1]==p&&b[2]==p)
            || (b[1]==p&&b[4]==p&&b[7]==p)
            || (b[0]==p&&b[1]==p&&b[2]==p)
            || (b[2]==p&&b[4]==p&&b[6]==p)
            || (b[2]==p&&b[5]==p&&b[8]==p)
            || (b[0]==p&&b[3]==p&&b[6]==p)
            || (b[3]==p&&b[4]==p&&b[5]==p)
            || (b[0]==p&&b[4]==p&&b[8]==p)
            || (b[2]==p&&b[4]==p&&b[6]==p)
            || (b[3]==p&&b[4]==p&&b[5]==p)
            || (b[1]==p&&b[4]==p&&b[7]==p)
            || (b[2]==p&&b[5]==p&&b[8]==p) 
            || (b[3]==p&&b[4]==p&&b[5]==p)
            || (b[0]==p&&b[3]==p&&b[6]==p)
            || (b[2]==p&&b[4]==p&&b[6]==p)
            || (b[6]==p&&b[7]==p&&b[8]==p)
            || (b[6]==p&&b[7]==p&&b[8]==p)
            || (b[1]==p&&b[4]==p&&b[7]==p)
            || (b[2]==p&&b[5]==p&&b[8]==p)
            || (b[6]==p&&b[7]==p&&b[8]==p)
            || (b[0]==p&&b[4]==p&&b[8]==p)) {
            return true;
        }
        return false;
    }

    private static boolean checkTie(Player[] b) {
        for(int i = 0; i < 9; i++) {
            if(b[i] == E) {
                return false;
            }
        }
        return true;
    }

    private static boolean gameOver(Player[] b) {
        return checkTie(b) || checkWin(b, X) || checkWin(b, O);
    }

    private static int maxOfArray(int[] a) {
        int max = a[0];
        for (int i : a)
            if (max < i)
                max = i;
        return max;
    }

    private static int minOfArray(int[] a) {
        int min = a[0];
        for (int i : a)
            if (min > i)
                min = i;
        return min;
    }

    private static int getEmptyNumber(Player[] b) {
        int spaces = 0;
        for(int i = 0; i < 9; i++) {
            if(b[i] == E)
                spaces++;
        }
        return spaces;
    }

    private static int evalGame(Player[] b, Player p, Player currentP) {
        if(gameOver(b)) {
            if(checkWin(b, p)) {
                return 1;
            } else if(checkWin(b, p == X ? O : X)) {
                return -1;
            } else {
                return 0;
            }
        } else {
            int[] arrayEval = new int[getEmptyNumber(b)];
            for(int i = 0; i < getEmptyNumber(b); i++) {
                arrayEval[i] = evalGame(possibleBoards(b, currentP)[i], p, currentP == X ? O : X);
            }
            if(currentP == p) {
                return maxOfArray(arrayEval);
            } else {
                return minOfArray(arrayEval);
            }
        }
    }

    public static Player[][] possibleBoards(Player[] b, Player p) {
        Player[][] toReturn = new Player[getEmptyNumber(b)][9];
        int spaces = 0;
        for(int i = 0; i < 9; i++) {
            if(b[i] == E) {
                for(int j = 0; j < 9; j++) {
                    toReturn[spaces][j] = b[j];
                }
                toReturn[spaces][i] = p;
                spaces++;
            }
        }
        return toReturn;
    }

    public static void main(String[] args) {
        Player[] p = new Player[9];
        Arrays.fill(p, E);
        p[1] = X;
        System.out.println(evalGame(p, O, O));
    }

}

person Fraser Price    schedule 18.12.2014    source источник
comment
Я не вижу никаких ошибок. Как определяются X и O (какой тип данных) в вызовах checkWin и т.п.? Я предполагаю, что это константы, объявления которых вы не публиковали?   -  person mbomb007    schedule 18.12.2014
comment
@mbomb007 И E в getEmptyNumber()   -  person Charlie    schedule 18.12.2014
comment
@hfontanez В методе evalGame(): if(checkWin(b, p)) { return 1; } else if(checkWin(b, p == X ? O : X)) { return -1; } else { return 0; } Я думаю, что return 0 означает ничью.   -  person Charlie    schedule 18.12.2014
comment
Помимо всего этого, как это вообще работает? Где ходы? Как мы можем отладить это самостоятельно?   -  person Charlie    schedule 18.12.2014
comment
Какую ошибку выдает программа или почему игра работает не так, как ожидалось?   -  person mbomb007    schedule 18.12.2014
comment
Как определяется checkWin?   -  person Max Meijer    schedule 18.12.2014
comment
@mbomb007 X, O и E — константы в перечислении Player. E представляет собой пустой квадрат.   -  person Fraser Price    schedule 18.12.2014
comment
Вижу проблему: gameOver() должен проверить, есть ли в матрице незаполненные квадраты. Не следует проверять, кто победит. Кроме того, вы проверяете ничью, и если это возвращает false, есть победитель, вам не нужны два вызова checkWin(). Этот метод может возвращать (например) false, если X выигрывает, и true в противном случае. Имеет ли это смысл?   -  person hfontanez    schedule 18.12.2014
comment
@ mbomb007 Нет никаких исключений, только кажущиеся случайными неожиданные результаты. Отредактирую и опубликую весь класс, дайте мне секунду   -  person Fraser Price    schedule 18.12.2014
comment
@hfontanez gameOver() — это логическое значение, которое возвращает true, если кто-то выиграл или если это ничья (т. е. не осталось квадратов). На самом деле это не большая проблема, о которой я беспокоюсь, это сделает небольшую вещь, сохранив при этом, возможно, 2 строки кода.   -  person Fraser Price    schedule 18.12.2014
comment
Вы так и не сказали нам, в чем ваша проблема.   -  person Tom    schedule 18.12.2014
comment
Вот как я бы это сделал: инициализируйте свой 2D-массив нулевым символом. Ваш метод gameOver возвращает значение true, если ни один элемент массива не содержит нулевой символ. Для проверки win arr[?][0], arr[?][0] и arr[?][0] должны иметь один и тот же символ, ИЛИ arr[0][?], arr[1][?], и arr[2][?] должны иметь один и тот же символ, ИЛИ arr[0][0], arr[1][1], и arr[2][2] должны иметь один и тот же символ, ИЛИ arr[0] [2], arr[1][1] и arr[2][0] должны иметь один и тот же символ. Что-то такое...   -  person hfontanez    schedule 18.12.2014
comment
Это ничего не должно исправить, но ваш метод checkWin() проверил много повторяющихся строк игрового поля. Обратите внимание, что есть только 8 возможных выигрышных 3-в-рядов: 3 по горизонтали, 3 по вертикали и 2 по диагонали.   -  person mbomb007    schedule 18.12.2014
comment
@ mbomb007, согласны ли вы с тем, что метод gameOver() должен проверять только пустые квадраты? Я думаю, что мое объяснение выше заключается в том, как должны быть построены методы.   -  person hfontanez    schedule 18.12.2014
comment
@hfontanez хорошо, спасибо за вклад, но не совсем в чем был вопрос. Не беспокойтесь об эффективности банкомата   -  person Fraser Price    schedule 18.12.2014
comment
Ага. Возможно, if(gameOver(b)) { можно было бы даже удалить. Он выполняет одну и ту же проверку 4 или более раз. Хотя не думаю, что это корень проблемы. Программу было бы легче понять, если бы вместо этого у игрока было свойство, которое было установлено либо на X, либо на O, тогда вы передаете как доску, так и игрока, чтобы проверить наличие пустых квадратов или выигрыш. Затем при проверке выигрыша вы можете использовать p.letter или что-то еще.   -  person mbomb007    schedule 18.12.2014
comment
@FraserPrice, дело не столько в эффективности. У вас проблемы с отладкой собственного кода. Я предлагаю сначала упростить его, а затем исправить. Ваша главная проблема заключается в том, что ваше решение не соблюдает принцип единой ответственности.   -  person hfontanez    schedule 18.12.2014


Ответы (1)


С тех пор я просмотрел свой код и понял, что допустил ошибку при отладке. Рабочий, отредактированный код ниже для всех, кто заинтересован

package tictactoe;

import static tictactoe.Player.*;

import java.util.Arrays;

public class MinimaxTTT {

    private Player[] board = new Player[9];
    private Player player = X;

    public MinimaxTTT() {
        Arrays.fill(board, E);
        player = X;
    }

    public MinimaxTTT(Player[] b, Player p) {
        for(int i = 0; i < 9; i++) {
            board[i] = b[i];
        }
        player = p;
    }

    public Player[] getBoard() {
        return board;
    }

    public void setBoard(Player[] b) {
        for(int i = 0; i < 9; i++) {
            board[i] = b[i];
        }
    }

    public void setSquare(int i, Player p) {
        board[i] = p;
    }

    public Player getPlayer() {
        return player;
    }

    public void setPlayer(Player p) {
        player = p;
    }

    public void switchPlayers() {
        player = player == X ? O : X;
    }

    public boolean checkWin(Player[] b, Player p) {
        if(b[0] == p && b[1] == p && b[2] == p 
            || b[3] == p && b[4] == p && b[5] == p
            || b[6] == p && b[7] == p && b[8] == p
            || b[0] == p && b[3] == p && b[6] == p
            || b[1] == p && b[4] == p && b[7] == p
            || b[2] == p && b[5] == p && b[8] == p
            || b[0] == p && b[4] == p && b[8] == p
            || b[2] == p && b[4] == p && b[6] == p) {
            return true;
        }
        return false;
    }

    public boolean checkTie(Player[] b) {
        for(int i = 0; i < 9; i++) {
            if(b[i] == E) {
                return false;
            }
        }
        return true;
    }

    public boolean gameOver(Player[] b) {
        return checkTie(b) || checkWin(b, X) || checkWin(b, O);
    }

    private int maxOfArray(int[] a) {
        int max = a[0];
        for (int i : a)
            if (max < i)
                max = i;
        return max;
    }

    private int minOfArray(int[] a) {
        int min = a[0];
        for (int i : a)
            if (min > i)
                min = i;
        return min;
    }

    private int getEmptyNumber(Player[] b) {
        int spaces = 0;
        for(int i = 0; i < 9; i++) {
            if(b[i] == E)
                spaces++;
        }
        return spaces;
    }

    private int findIndex(int[] is, int n) {
        for(int i = 0; i < is.length; i++) {
            if(is[i] == n)
                return i;
        }
        return 0;
    }

    private int[] evalGame(Player[] b, Player p, Player currentP, int depth) {
        int[] toReturn = new int[2];
        if(gameOver(b)) {
            if(checkWin(b, p)) {
                toReturn[1] = 10 + depth;
                return toReturn;
            } else if(checkWin(b, p == X ? O : X)) {
                toReturn[1] = depth - 10;
                return toReturn;
            } else {
                toReturn[1] = 0;
                return toReturn;
            }
        } else {
            depth += 1;
            int[] arrayEval = new int[getEmptyNumber(b)];
            for(int i = 0; i < getEmptyNumber(b); i++) {
                arrayEval[i] = evalGame(possibleBoards(b, currentP)[i], p, currentP == X ? O : X, depth)[1];
            }
            if(currentP == p) {
                int position = findIndex(arrayEval, maxOfArray(arrayEval));
                int base = 0;
                for(int i = 0; i < 9; i++) {
                    if(b[i] == E) {
                        if(base == position) {
                            toReturn[0] = i;
                            break;
                        } else {
                            base++;
                        }
                    }
                }
                toReturn[1] = maxOfArray(arrayEval);
                return toReturn;
            } else {
                toReturn[1] = minOfArray(arrayEval);
                return toReturn;
            }
        }
    }

    public Player[][] possibleBoards(Player[] b, Player p) {
        Player[][] toReturn = new Player[getEmptyNumber(b)][9];
        int spaces = 0;
        for(int i = 0; i < 9; i++) {
            if(b[i] == E) {
                for(int j = 0; j < 9; j++) {
                    toReturn[spaces][j] = b[j];
                }
                toReturn[spaces][i] = p;
                spaces++;
            }
        }
        return toReturn;
    }

    public Player[] move() {
        if(!gameOver(board)) {
            board[evalGame(board, player, player, 0)[0]] = player;
        }
        return board;
    }
}
person Fraser Price    schedule 18.12.2014