1

Тема: Створення непереможного бота у грі хрестики-нулики

Добрий вечір! Прошу вашої допомоги зі з'ясуванням неправильності алгоритму.
Почнемо із задуму гри. Спочатку гравець вводить через пробіл три команди, а саме: start, user/easy/medium/hard, user/easy/medium/hard. Після цього виводиться початковий стан гри(я його можу змінювати) і починаєть гра. В залежності від вибору команд ви можете грати з іншою людиною, або дивитися як борються боти різної чи однакової складності. Також програма має перевіряти введені дані користувача( користувач вводить номер рядка і стовпця, де хоче зробити хід). Все це було зроблено і не було значних труднощів, допоки я не дойшов до важкого бота. Боти побудовані так, що я передаю їм поле гри, вони роблять свій хід(замість пропуску в масиві ставлять свій символ). До речі, кожен бот і гравець наслідують клас User, який має конструктор, що приймає силвол гравця('X' або 'O'), зберігаю його в змінну і за нею вже визначає силвол супротивника. Важкого бота хочу створити за допомого Minimax алгоритму. Користувався цими джерелами інформації: https://www.youtube.com/watch?v=l-hh51ncgDI, https://www.geeksforgeeks.org/minimax-a … roduction/, https://www.geeksforgeeks.org/minimax-a … -function/, https://www.geeksforgeeks.org/minimax-a … imal-move/. Намагався написати програму в IntelliJ IDEA.
Ось код.

package tictactoe.Game.User;

import java.util.ArrayList;

public class HardBot extends User {
    public HardBot(char symbol) {
        super(symbol);
    }

    @Override
    public void makeMove(char[][] table) {
        int test = minimax(table, true, 0);
        System.out.println(test);
//        int i_best = Integer.MIN_VALUE, j_best = Integer.MIN_VALUE, best_score = Integer.MIN_VALUE;
//        for (int i = 0; i < table.length; i++) {
//            for (int j = 0; j < table[i].length; j++) {
//                if (table[i][j] == ' ') {
//                    char[][] position = the_same_as(table);
//                    position[i][j] = symbol;
//                    int score = minimax(position, true, 0);
//                    if (score > best_score) {
//                        best_score = score;
//                        i_best = i;
//                        j_best = j;
//                    }
//                }
//            }
//        }
//        table[i_best][j_best] = symbol;
    }
    private int minimax(char[][] position, boolean maximizingPlayer, int depth) {
        if (game_ended(position)) {
            return  maximizingPlayer ? evaluate(position) - depth : evaluate(position) + depth ;
        } else {
            if (evaluate(position) != 0) return maximizingPlayer ? evaluate(position) - depth : evaluate(position) + depth;
        }

        if (maximizingPlayer) {
            int maxEvaluation = Integer.MIN_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, false, depth + 1);
                return Math.max(eval, maxEvaluation);
            }
        } else {
            int minEvaluation = Integer.MAX_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, true, depth + 1);
                return Math.min(eval, minEvaluation);
            }
        }
        //IDE сворилося, бо функція повинна шось видавати
        return Short.MIN_VALUE;
    }
    private int evaluate(char[][] table) {
        if (maximizing_won(table)) return 10;
        if (minimizing_won(table)) return -10;
        return 0;
    }
    private ArrayList<char[][]> childPositions(char[][] table, boolean maximizingPlayer){
        ArrayList<char[][]> child = new ArrayList<>();
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] == ' ') {
                    char[][] new_position = the_same_as(table);
                    new_position[i][j] = maximizingPlayer ? symbol : opponent_symbol;
                    child.add(new_position);
                }
            }
        }
        return child;
    }
    private char[][] the_same_as(char[][] inp) {
        char[][] result = new char[3][3];
        for (int i = 0; i < inp.length; i++) {
            for (int j = 0; j < inp[i].length; j++) {
                result[i][j] = inp[i][j];
            }
        }
        return result;
    }
    private boolean maximizing_won(char[][] table){
        for (char[] row:
                table) {
            if (row[0] == row[1] && row[1] == row[2] && row[2] == symbol) return true;
        }
        for (int j = 0; j < 3; j++)
            if (table[0][j] == table[1][j] && table[1][j] == table[2][j] && table[2][j] == symbol) return true;
        if (table[0][0] == table[1][1] && table[1][1] == table[2][2] && table[2][2] == symbol) return true;
        if (table[0][2] == table[1][1] && table[1][1] == table[2][0] && table[2][0] == symbol) return true;
        return false;
    }
    private boolean minimizing_won(char[][] table){
        for (char[] row:
                table) {
            if (row[0] == row[1] && row[1] == row[2] && row[2] == opponent_symbol) return true;
        }
        for (int j = 0; j < 3; j++)
            if (table[0][j] == table[1][j] && table[1][j] == table[2][j] && table[2][j] == opponent_symbol) return true;
        if (table[0][0] == table[1][1] && table[1][1] == table[2][2] && table[2][2] == opponent_symbol) return true;
        if (table[0][2] == table[1][1] && table[1][1] == table[2][0] && table[2][0] == opponent_symbol) return true;
        return false;
    }
    private boolean game_ended(char[][] table) {
        for (char[] row:
                table) {
            for (char i:
                    row) {
                if (i == ' ') return false;
            }
        }
        return true;
    }
}

І те, що він вивів.(Я перервав виконання програми).

Input command: > start user hard
---------
| X O O |
| X X O |
|       |
---------
Enter the coordinates: > 3 2
---------
| X O O |
| X X O |
|   X   |
---------
Making move level "hard"
-12
---------
| X O O |
| X X O |
|   X   |
---------
Enter the coordinates: > 
Process finished with exit code -1

Початкове поле задав і зробив хід, тепер поле дуже просте і Minimax алгоритм мав би виввести якесь додатне число, бо за один хід бот може перемогти. Я закоментував частину коду, де бот ставить силвол(О), але він постав у позиції 3 1(лівий нижній кут). Я з'ясував, що функція minimax неправильно видає результат.
Задум метода make_move перебрати всі можливі позиція, де можна зробити хід i за допомогою Minimax оцінинити коден хід і знайти найкращий.
Щиро дякую за витрачений час!

Подякували: koala1

2

Re: Створення непереможного бота у грі хрестики-нулики

            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, false, depth + 1);
                return Math.max(eval, maxEvaluation);
            }

Цей цикл виконається рівно 1 раз. Вам, схоже, треба зробити

                maxEvaluation = Math.max(eval, maxEvaluation);
            }
            return maxEvaluation;

І зверніть увагу на повторення коду. Наприклад, maximizing_won та minimizing_won легко об'єднуються в одну функцію з другим параметром - символом

private boolean player_won(char[][] table, char player)
//приклад виклику
if(player_won(table, opponent_symbol))...

Так само можна об'єднати гілки з minimax:

            int maxEvaluation = Integer.MIN_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, !maximizingPlayer, depth + 1);
                maxEvaluation = Math.max(maximizingPlayer?eval:-eval, maxEvaluation);
            }
            return maximizingPlayer?maxEvaluation:-maxEvaluation;
Подякували: zxzpogoncuk1

3

Re: Створення непереможного бота у грі хрестики-нулики

І взагалі, використовуйте мемоїзацію. Всього можливих розташувань 3**9=19683, а можливих з них лише 4 з чимось тисяч. Зберігайте оцінки позицій в геш-таблиці.

Подякували: zxzpogoncuk1

4

Re: Створення непереможного бота у грі хрестики-нулики

Дякую за слушні поради! Поки що не скористався вашою порадою про об'єднання гілки з minimax -- так мені легше розуміти код.

package tictactoe.Game.User;

import java.util.ArrayList;

public class HardBot extends User {
    public HardBot(char symbol) {
        super(symbol);
    }

    @Override
    public void makeMove(char[][] table) {
        int i_best = Integer.MIN_VALUE, j_best = Integer.MIN_VALUE, best_score = Integer.MIN_VALUE;
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] == ' ') {
                    char[][] position = the_same_as(table);
                    position[i][j] = symbol;
                    int score = minimax(position, true, 0);
                    if (score > best_score) {
                        best_score = score;
                        i_best = i;
                        j_best = j;
                    }
                }
            }
        }
        table[i_best][j_best] = symbol;
    }
    private int minimax(char[][] position, boolean maximizingPlayer, int depth) {
        if (game_ended(position)) {
            return  maximizingPlayer ? evaluate(position) - depth : evaluate(position) + depth ;
        } else {
            if (evaluate(position) != 0) return maximizingPlayer ? evaluate(position) - depth : evaluate(position) + depth;
        }

        if (maximizingPlayer) {
            int maxEvaluation = Integer.MIN_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, false, depth + 1);
                maxEvaluation = Math.max(eval, maxEvaluation);

            }
            return maxEvaluation;
        } else {
            int minEvaluation = Integer.MAX_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, true, depth + 1);
                minEvaluation = Math.min(eval, minEvaluation);
            }
            return minEvaluation;
        }
    }
    private int evaluate(char[][] table) {
        if (player_won(table, symbol)) return 10;
        if (player_won(table, opponent_symbol)) return -10;
        return 0;
    }
    private ArrayList<char[][]> childPositions(char[][] table, boolean maximizingPlayer){
        ArrayList<char[][]> child = new ArrayList<>();
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] == ' ') {
                    char[][] new_position = the_same_as(table);
                    new_position[i][j] = maximizingPlayer ? symbol : opponent_symbol;
                    child.add(new_position);
                }
            }
        }
        return child;
    }
    private char[][] the_same_as(char[][] inp) {
        char[][] result = new char[3][3];
        for (int i = 0; i < inp.length; i++) {
            for (int j = 0; j < inp[i].length; j++) {
                result[i][j] = inp[i][j];
            }
        }
        return result;
    }
    private boolean player_won(char[][] table, char player) {
        for (char[] row:
                table) {
            if (row[0] == row[1] && row[1] == row[2] && row[2] == player) return true;
        }
        for (int j = 0; j < 3; j++)
            if (table[0][j] == table[1][j] && table[1][j] == table[2][j] && table[2][j] == player) return true;
        if (table[0][0] == table[1][1] && table[1][1] == table[2][2] && table[2][2] == player) return true;
        if (table[0][2] == table[1][1] && table[1][1] == table[2][0] && table[2][0] == player) return true;
        return false;
    }

    private boolean game_ended(char[][] table) {
        for (char[] row:
                table) {
            for (char i:
                    row) {
                if (i == ' ') return false;
            }
        }
        return true;
    }
}

Ось результат

Input command: > start hard hard
---------
|       |
|       |
|       |
---------
Making move level "hard"
---------
| X     |
|       |
|       |
---------
Making move level "hard"
---------
| X   O |
|       |
|       |
---------
Making move level "hard"
---------
| X   O |
|   X   |
|       |
---------
Making move level "hard"
---------
| X   O |
|   X   |
| O     |
---------
Making move level "hard"
---------
| X X O |
|   X   |
| O     |
---------
Making move level "hard"
---------
| X X O |
|   X O |
| O     |
---------
Making move level "hard"
---------
| X X O |
| X X O |
| O     |
---------
Making move level "hard"
---------
| X X O |
| X X O |
| O O   |
---------
Making move level "hard"
---------
| X X O |
| X X O |
| O O X |
---------
X wins

Input command: > exit

Process finished with exit code 0

На жаль, очевидно, що боти працюють неправильно. Так виглядає ніби алгоритм навмисно намагається програти.

Але після цієї думки (бот намагається програти) я змінив параметр(з true на false) при першому виклику minimax в make_move і все запрацювало.

package tictactoe.Game.User;

import java.util.ArrayList;

public class HardBot extends User {
    public HardBot(char symbol) {
        super(symbol);
    }

    @Override
    public void makeMove(char[][] table) {
        int i_best = Integer.MIN_VALUE, j_best = Integer.MIN_VALUE, best_score = Integer.MIN_VALUE;
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] == ' ') {
                    char[][] position = the_same_as(table);
                    position[i][j] = symbol;
                    int score = minimax(position, false, 0);
                    if (score > best_score) {
                        best_score = score;
                        i_best = i;
                        j_best = j;
                    }
                }
            }
        }
        table[i_best][j_best] = symbol;
    }
    private int minimax(char[][] position, boolean maximizingPlayer, int depth) {
        if (game_ended(position)) {
            return  maximizingPlayer ? evaluate(position) - depth : evaluate(position) + depth ;
        } else {
            if (evaluate(position) != 0) return maximizingPlayer ? evaluate(position) - depth : evaluate(position) + depth;
        }

        if (maximizingPlayer) {
            int maxEvaluation = Integer.MIN_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, false, depth + 1);
                maxEvaluation = Math.max(eval, maxEvaluation);

            }
            return maxEvaluation;
        } else {
            int minEvaluation = Integer.MAX_VALUE;
            for (char[][] child:
                    childPositions(position, maximizingPlayer)) {
                int eval = minimax(child, true, depth + 1);
                minEvaluation = Math.min(eval, minEvaluation);
            }
            return minEvaluation;
        }
    }
    private int evaluate(char[][] table) {
        if (player_won(table, symbol)) return 10;
        if (player_won(table, opponent_symbol)) return -10;
        return 0;
    }
    private ArrayList<char[][]> childPositions(char[][] table, boolean maximizingPlayer){
        ArrayList<char[][]> child = new ArrayList<>();
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[i].length; j++) {
                if (table[i][j] == ' ') {
                    char[][] new_position = the_same_as(table);
                    new_position[i][j] = maximizingPlayer ? symbol : opponent_symbol;
                    child.add(new_position);
                }
            }
        }
        return child;
    }
    private char[][] the_same_as(char[][] inp) {
        char[][] result = new char[3][3];
        for (int i = 0; i < inp.length; i++) {
            for (int j = 0; j < inp[i].length; j++) {
                result[i][j] = inp[i][j];
            }
        }
        return result;
    }
    private boolean player_won(char[][] table, char player) {
        for (char[] row:
                table) {
            if (row[0] == row[1] && row[1] == row[2] && row[2] == player) return true;
        }
        for (int j = 0; j < 3; j++)
            if (table[0][j] == table[1][j] && table[1][j] == table[2][j] && table[2][j] == player) return true;
        if (table[0][0] == table[1][1] && table[1][1] == table[2][2] && table[2][2] == player) return true;
        if (table[0][2] == table[1][1] && table[1][1] == table[2][0] && table[2][0] == player) return true;
        return false;
    }

    private boolean game_ended(char[][] table) {
        for (char[] row:
                table) {
            for (char i:
                    row) {
                if (i == ' ') return false;
            }
        }
        return true;
    }
}
Input command: > start hard hard
---------
|       |
|       |
|       |
---------
Making move level "hard"
---------
| X     |
|       |
|       |
---------
Making move level "hard"
---------
| X     |
|   O   |
|       |
---------
Making move level "hard"
---------
| X X   |
|   O   |
|       |
---------
Making move level "hard"
---------
| X X O |
|   O   |
|       |
---------
Making move level "hard"
---------
| X X O |
|   O   |
| X     |
---------
Making move level "hard"
---------
| X X O |
| O O   |
| X     |
---------
Making move level "hard"
---------
| X X O |
| O O X |
| X     |
---------
Making move level "hard"
---------
| X X O |
| O O X |
| X O   |
---------
Making move level "hard"
---------
| X X O |
| O O X |
| X O X |
---------
Draw

Input command: > start hard user
---------
|       |
|       |
|       |
---------
Making move level "hard"
---------
| X     |
|       |
|       |
---------
Enter the coordinates: > 3 3
---------
| X     |
|       |
|     O |
---------
Making move level "hard"
---------
| X   X |
|       |
|     O |
---------
Enter the coordinates: > 1 2
---------
| X O X |
|       |
|     O |
---------
Making move level "hard"
---------
| X O X |
|       |
| X   O |
---------
Enter the coordinates: > 2 2
---------
| X O X |
|   O   |
| X   O |
---------
Making move level "hard"
---------
| X O X |
| X O   |
| X   O |
---------
X wins

Input command: > start user hard
---------
|       |
|       |
|       |
---------
Enter the coordinates: > 1 1
---------
| X     |
|       |
|       |
---------
Making move level "hard"
---------
| X     |
|   O   |
|       |
---------
Enter the coordinates: > 3 3
---------
| X     |
|   O   |
|     X |
---------
Making move level "hard"
---------
| X O   |
|   O   |
|     X |
---------
Enter the coordinates: > 3 2
---------
| X O   |
|   O   |
|   X X |
---------
Making move level "hard"
---------
| X O   |
|   O   |
| O X X |
---------
Enter the coordinates: > 1 3
---------
| X O X |
|   O   |
| O X X |
---------
Making move level "hard"
---------
| X O X |
|   O O |
| O X X |
---------
Enter the coordinates: > 2 1
---------
| X O X |
| X O O |
| O X X |
---------
Draw

Input command: > exit

Process finished with exit code 0

Вже завтра буду думати чому так. Щиро дякую, пане koala!

5

Re: Створення непереможного бота у грі хрестики-нулики

Не побачив ваше друге повідомлення. У майбутньому оптимізую алгоритм. Дякую за ще одну пораду!

6

Re: Створення непереможного бота у грі хрестики-нулики

Hru zavgdy mogna zvesty do nitcyjy, prytcomu duge lehko. Osj tut dectco moge dopomohty.

Подякували: zxzpogoncuk1