1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
package de.hysky.skyblocker.utils.tictactoe;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class TicTacToeUtils {
public static int getBestMove(char[][] board) {
HashMap<Integer, Integer> moves = new HashMap<>();
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[row].length; col++) {
if (board[row][col] != '\0') continue;
board[row][col] = 'O';
int score = alphabeta(board, Integer.MIN_VALUE, Integer.MAX_VALUE, false, 0);
board[row][col] = '\0';
moves.put(row * 3 + col + 1, score);
}
}
return Collections.max(moves.entrySet(), Map.Entry.comparingByValue()).getKey();
}
private static boolean hasMovesLeft(char[][] board) {
for (char[] rows : board) {
for (char col : rows) {
if (col == '\0') return true;
}
}
return false;
}
private static int getBoardScore(char[][] board) {
for (int row = 0; row < 3; row++) {
if (board[row][0] == board[row][1] && board[row][0] == board[row][2]) {
if (board[row][0] == 'X') {
return -10;
} else if (board[row][0] == 'O') {
return 10;
}
}
}
for (int col = 0; col < 3; col++) {
if (board[0][col] == board[1][col] && board[0][col] == board[2][col]) {
if (board[0][col] == 'X') {
return -10;
} else if (board[0][col] == 'O') {
return 10;
}
}
}
if (board[0][0] == board[1][1] && board[0][0] == board[2][2]) {
if (board[0][0] == 'X') {
return -10;
} else if (board[0][0] == 'O') {
return 10;
}
} else if (board[0][2] == board[1][1] && board[0][2] == board[2][0]) {
if (board[0][2] == 'X') {
return -10;
} else if (board[0][2] == 'O') {
return 10;
}
}
return 0;
}
private static int alphabeta(char[][] board, int alpha, int beta, boolean max, int depth) {
int score = getBoardScore(board);
if (score == 10 || score == -10) return score;
if (!hasMovesLeft(board)) return 0;
if (max) {
int bestScore = Integer.MIN_VALUE;
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
if (board[row][col] == '\0') {
board[row][col] = 'O';
bestScore = Math.max(bestScore, alphabeta(board, alpha, beta, false, depth + 1));
board[row][col] = '\0';
alpha = Math.max(alpha, bestScore);
if (beta <= alpha) break; // Pruning
}
}
}
return bestScore - depth;
} else {
int bestScore = Integer.MAX_VALUE;
for (int row = 0; row < 3; row++) {
for (int col = 0; col < 3; col++) {
if (board[row][col] == '\0') {
board[row][col] = 'X';
bestScore = Math.min(bestScore, alphabeta(board, alpha, beta, true, depth + 1));
board[row][col] = '\0';
beta = Math.min(beta, bestScore);
if (beta <= alpha) break; // Pruning
}
}
}
return bestScore + depth;
}
}
}
|
