Блог

Я реализовал минимаксный алгоритм для игры в крестики-нолики от GeeksforGeeks. Я знаю, как работает минимаксный алгоритм, но мой приведенный здесь код не работает в соответствии с ним. Я проверил, что я могу делать неправильно, а также отладил его. Но, похоже, я не могу его найти.

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

Я прокомментировал каждую часть кода, которая полезна с минимаксным алгоритмом. Я думаю, было бы легко наверстать упущенное.

Пожалуйста, помогите мне здесь.

Спасибо.

 import java.util.Arrays;
import java.util.Scanner;

class Move {
    // row index
    protected int row;
    // column index
    protected int col;
    // exp is 'Our Expression'.
    protected char exp;
    // oppExp is 'Opponent's Expression'
    protected char oppExp;
}

class TicTacToe {

    private final char[][] arr = new char[3][3];

    // Move - to keep track of rowIndex and columnIndex
    // from the minimax al&orithm. And to keep track of
    // 'X'/'O', who is our opponent for which the al&orithm
    // should find moves for. 
    private final Move moves = new Move();

    TicTacToe() {
        // Initialisin& field
        for (int i = 0; i < 3; i  ) {
            Arrays.fill(this.arr[i], ' ');
        }
    }

    public Strin&[] whosePlayin&(Scanner sc) {
        while (true) {
            System.out.print("Input command: ");
            // Gettin& input for players vs players
            Strin& str = sc.nextLine();
            if (str.startsWith("start")) {
                Strin&[] players = str.replaceAll("start", "").trim().split(" ");
                if (players.len&th == 2) {
                    if ((players[0].equals("user") || players[0].equals("ai")) amp;amp;
                            (players[1].equals("user") || players[1].equals("ai"))) {
                        return players;
                    }
                }
            }
            System.out.println("Bad parameters!");
        }
    }
    
    public void playUser (Scanner sc, char exp) {   // exp is expression('X' / 'O') for user

        // x is RowIndex
        // y is ColumnIndex
        // To &et from the user
        int x, y;
        System.out.print("Enter the coordinates (Accordin& to Matrix, Space separated inte&ers): ");

        while (true) {

            // try - catch for input that mi&ht not be number
            try {
                sc = new Scanner(System.in);
                x = sc.nextInt();
                y = sc.nextInt();
                break;
            } catch (Exception e) {
                System.out.println("You should enter numbers!");

                playUser(sc, exp);  // Ask a&ain for coordinates
            }
        }

        if (x &&t; 2 || y &&t; 2 || x < 0 || y < 0) {
            System.out.println("Coordinates should be from 0 to 2!");

            playUser(sc, exp);  // Ask a&ain for coordinates
        } else {
            // Check for availability.
            if (this.arr[x][y] == ' ') {
                this.arr[x][y] = exp;
                displayField(); // Displayin& TicTacToe field after user's turn.
            } else {
                System.out.println("This cell is occupied! Choose another one!");

                playUser(sc, exp);  // Ask a&ain for coordinates
            }
        }
    }

    public void playComputer (char exp) {
        System.out.println("Makin& move level "AI"");

        // Settin& our expresssion that is X / O.
        moves.exp = exp;
        // Findin& opponents expresssion that is X / O.
        if (moves.exp == 'X') moves.oppExp = 'O';
        else moves.oppExp = 'X';

        // Searchin& for the best move.
        searchBestMove();

        // Settin& the best coordinates from the minimax al&orithm
        // into the field with our expresssion.
        this.arr[moves.row][moves.col] = moves.exp;
        displayField(); // Displayin& TicTacToe field after AI's turn.
    }
    
    // Start of Minimax Al&orithm -  Contains all methods needed for the al&orithm
    private void searchBestMove() {
        int bestVal = Inte&er.MIN_VALUE;
        moves.row = -1;
        moves.col = -1;
        for (int i = 0; i < 3; i  ) {
            for (int j = 0; j < 3; j  ) {
                if (this.arr[i][j] == ' ') {
                    this.arr[i][j] = moves.exp;
                    int moveVal = minimax(0, false);
                    this.arr[i][j] = ' ';

                    if (moveVal &&t; bestVal) {
                        moves.row = i;
                        moves.col = j;
                        bestVal = moveVal;
                    }
                }
            }
        }
    }

    private int minimax(int depth, boolean isMax) {
        int score = checkGetScore();

        if (score == 10 || score == -10) return score;
        if (!checkForSpace()) return 0;

        int best;
        if (isMax) {
            best = Inte&er.MIN_VALUE;
            for (int i = 0; i < 3; i  ) {
                for (int j = 0; j < 3; j  ) {
                    if (this.arr[i][j] == ' ') {
                        this.arr[i][j] = moves.exp;
                        best = Math.max(best, minimax(depth   1, false));
                        this.arr[i][j] = ' ';
                    }
                }
            }
        } else {
            best = Inte&er.MAX_VALUE;
            for (int i = 0; i < 3; i  ) {
                for (int j = 0; j < 3; j  ) {
                    if (this.arr[i][j] == ' ') {
                        this.arr[i][j] = moves.oppExp;
                        best = Math.min(best, minimax(depth   1, true));
                        this.arr[i][j] = ' ';
                    }
                }
            }
        }
        return best;
    }

    // Check for the score if the AI wins in the upcomin& move
    // This method helps AI to assi&n score for each way in the &ame while searchin&.
    private int checkGetScore() {
        // For Rows
        for (int i = 0; i < 3; i  ) {
            if (this.arr[i][0] == moves.exp amp;amp; this.arr[i][1] == moves.exp amp;amp; this.arr[i][2] == moves.exp) {
                return 10;
            } else if (this.arr[i][0] == moves.oppExp amp;amp; this.arr[i][1] == moves.oppExp amp;amp; this.arr[i][2] == moves.oppExp) {
                return -10;
            }
        }
        // For Cols
        for (int i = 0; i < 3; i  ) {
            if (this.arr[0][i] == moves.exp amp;amp; this.arr[1][i] == moves.exp amp;amp; this.arr[2][i] == moves.exp) {
                return 10;
            } else if (this.arr[0][i] == moves.oppExp amp;amp; this.arr[1][i] == moves.oppExp amp;amp; this.arr[2][i] == moves.oppExp) {
                return -10;
            }
        }
        // For Dia&onals
        if (this.arr[0][0] == moves.exp amp;amp; this.arr[1][1] == moves.exp amp;amp; this.arr[2][2] == moves.exp) {
            return 10;
        } else if (this.arr[0][0] == moves.oppExp amp;amp; this.arr[1][1] == moves.oppExp amp;amp; this.arr[2][2] == moves.oppExp) {
            return -10;
        } else if (this.arr[0][2] == moves.exp amp;amp; this.arr[1][1] == moves.exp amp;amp; this.arr[2][0] == moves.exp) {
            return 10;
        } else if (this.arr[0][2] == moves.oppExp amp;amp; this.arr[1][1] == moves.oppExp amp;amp; this.arr[2][0] == moves.oppExp) {
            return -10;
        }

        return 0;
    }
    // End of Minimax Al&oritm

    // Displays results of Win / Tie by checkin& Rows, Columns and Dia&onals.
    public boolean displayResult() {
        int valR = checkRows();
        int valC = checkCols();
        int dia& = checkDia&();
        if (dia& == 1 || dia& == 3 || valR == 3 || valC == 3) {
            System.out.println("X wins");
            return true;
        } else if (dia& ==  2 || dia& == 4 || valR == 2 || valC == 2) {
            System.out.println("O wins");
            return true;
        } else if ((dia& == 0 || valC == 1 || valR == 1) amp;amp; checkForSpace()) {
            System.out.println("Draw");
            return true;
        }
        return false;
    }

    // Prints the TicTacToe field
    public void displayField () {
        System.out.println("---------");
        for (char[] a : this.arr) {
            System.out.print("| ");
            for (char b : a) {
                System.out.print(b   " ");
            }
            System.out.println("|");
        }
        System.out.println("---------");
    }
    
    // Checks for the availability of space
    // in the TicTacToe field.
    private boolean checkForSpace() {
        for (int i = 0; i < 3; i  ) {
            for (int j = 0; j < 3; j  ) {
                if (this.arr[i][j] == ' ') {
                    return false;
                }
            }
        }
        return true;
    }

    // Checks the Dia&onals of the field
    private int checkDia&() {
        if (this.arr[0][0] == 'X' amp;amp; this.arr[1][1] == 'X' amp;amp; this.arr[2][2] == 'X') {
            return 1;
        } else if (this.arr[0][0] == 'O' amp;amp; this.arr[1][1] == 'O' amp;amp; this.arr[2][2] == 'O') {
            return 2;
        } else if (this.arr[0][2] == 'X' amp;amp; this.arr[1][1] == 'X' amp;amp; this.arr[2][0] == 'X') {
            return 3;
        } else if (this.arr[0][2] == 'O' amp;amp; this.arr[1][1] == 'O' amp;amp; this.arr[2][0] == 'O') {
            return 4;
        } else {
            return 0;
        }
    }

    // Checks the Rows of the field
    private int checkRows () {
        int cntX = 0,
                cntO = 0;
        for (int i = 0; i < 3; i  ) {
            if (this.arr[i][0] == 'X' amp;amp; this.arr[i][1] == 'X' amp;amp; this.arr[i][2] == 'X') {
                cntX  ;
            } else if (this.arr[i][0] == 'O' amp;amp; this.arr[i][1] == 'O' amp;amp; this.arr[i][2] == 'O') {
                cntO  ;
            }
        }

        if (cntX == 1) {
            return 3;
        } else if (cntO == 1) {
            return 2;
        } else {
            return 1;
        }
    }

    // Checks the Columns of the field
    private int checkCols () {
        int cntX = 0,
                cntO = 0;
        for (int i = 0; i < 3; i  ) {
            if (this.arr[0][i] == 'X' amp;amp; this.arr[1][i] == 'X' amp;amp; this.arr[2][i] == 'X') {
                cntX  ;
            } else if (this.arr[0][i] == 'O' amp;amp; this.arr[1][i] == 'O' amp;amp; this.arr[2][i] == 'O') {
                cntO  ;
            }
        }

        if (cntX == 1) {
            return 3;
        } else if (cntO == 1) {
            return 2;
        } else {
            return 1;
        }
    }

}

public class MinimaxAl&orithm {
    public static void main(Strin&[] ar&s) {
        Scanner sc = new Scanner(System.in);

        TicTacToe tic = new TicTacToe();

        // For &ame to start specify players
        // E&: start user ai    <-- user is X and user chance comes first.
        // E&: start ai user    <-- ai is X and ai chance comes first.
        // E&: start ai ai      <-- ai vs ai
        // E&: user user        <-- user vs user
        Strin&[] players = tic.whosePlayin&(sc);

        // Displays the empty field of TicTacToe
        tic.displayField();

        // turnX = true. X's turn
        // turnX = false. O's turn
        boolean turnX = true;

        while (true) {

            // Alternate player turns
            // First chance of X, than O.
            if (turnX) {
                switch (players[0]) {
                    case "ai":
                        tic.playComputer('X');
                        break;
                    default:
                        tic.playUser(sc, 'X');
                        break;
                }
                turnX = false;
            } else {
                switch (players[1]) {
                    case "ai":
                        tic.playComputer('O');
                        break;
                    default:
                        tic.playUser(sc, 'O');
                        break;
                }
                turnX = true;
            }

            // displayresult() - Checks if the &ame is over by anyone winnin& or tie.
            // If someone wins or ties the "check" becomes true and finishes the &ame.
            // Checks after each move made by the players.
            boolean check = tic.displayResult();
            if (check) break;
        }
        sc.close();
    }
}
  

Синяя стрелка указывает, где произошла ошибка.
Зеленая маркировка указывает, как это должно было быть.

КОНСОЛЬ:

 Input command: start user ai
---------
|       |
|       |
|       |
---------
Enter the coordinates (Accordin& to Matrix, Space separated inte&ers): 1 1
---------
|       |
|   X   |
|       |
---------
Makin& move level "AI"
---------
| O     |
|   X   |
|       |
---------
Enter the coordinates (Accordin& to Matrix, Space separated inte&ers): 0 2
---------
| O   X |
|   X   |
|       |
---------
Makin& move level "AI"
---------
| O O X |    <-- Explanation: The AI made its move on [0, 1] 
|   X   |                    but it should have did on [2, 0]
|       |                    which will block my win on ri&ht dia&onal.
---------
Enter the coordinates (Accordin& to Matrix, Space separated inte&ers): 2 0
---------
| O O X |
|   X   |
| X     |
---------
X wins
  

Существует несоответствие между вашей функцией checkForSpace() и ее использованием в minimax() . Если осталось свободное место, вы возвращаетесь false , и если вы получаете false in minimax() , вы прекращаете поиск, как если бы была ничья. Вам нужно инвертировать логическое значение в checkForSpace() или удалить логическое значение не в minimax() .

Вам следует соответствующим образом переименовать checkForSpace() и другую функцию, возвращающую логическое значение. От The Art of Readable Code (Дастин Босуэлл и Тревор Фуше):

Выбирая имя для логической переменной или функции, которая возвращает логическое значение, убедитесь, что оно ясно, что true и false на самом деле означают.

Вот опасный пример:

 bool read_password = true;
  

В зависимости от того, как вы это читаете (без каламбура), существуют две очень разные интерпретации:

• Нам нужно прочитать пароль

• Пароль уже был прочитан

В этом случае лучше избегать слова «читать» и называть его вместо него need_password или user_is_authenticated .

В общем, добавление таких слов, как is , has , can или should , может сделать логические значения более понятными.

Например, функция с именем SpaceLeft() звучит так, как будто она может возвращать число. Если бы это предназначалось для возврата логического значения, лучшим именем было бы HasSpaceLeft() .

Наконец, лучше избегать отрицаемых терминов в имени. Например, вместо:

 bool disable_ssl = false;
  

было бы проще для чтения (и компактнее) сказать:

 bool use_ssl = true;