Тема: Створення непереможного бота у грі хрестики-нулики
Добрий вечір! Прошу вашої допомоги зі з'ясуванням неправильності алгоритму.
Почнемо із задуму гри. Спочатку гравець вводить через пробіл три команди, а саме: 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 оцінинити коден хід і знайти найкращий.
Щиро дякую за витрачений час!
