From 115078d8ce5584fa1bae256d4a44696c6ac79b44 Mon Sep 17 00:00:00 2001
From: Aaron <51387595+AzureAaron@users.noreply.github.com>
Date: Sun, 28 Apr 2024 13:42:04 -0400
Subject: Tic Tac Toe Rewrite/Refactor
---
.../skyblock/dungeon/puzzle/TicTacToe.java | 12 +-
.../skyblocker/utils/tictactoe/BoardIndex.java | 5 +
.../skyblocker/utils/tictactoe/TicTacToeUtils.java | 210 +++++++++++----------
3 files changed, 124 insertions(+), 103 deletions(-)
create mode 100644 src/main/java/de/hysky/skyblocker/utils/tictactoe/BoardIndex.java
(limited to 'src/main/java')
diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/TicTacToe.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/TicTacToe.java
index e4c51e69..1683276e 100644
--- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/TicTacToe.java
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/TicTacToe.java
@@ -4,6 +4,7 @@ import de.hysky.skyblocker.config.SkyblockerConfigManager;
import de.hysky.skyblocker.skyblock.dungeon.secrets.DungeonManager;
import de.hysky.skyblocker.utils.Utils;
import de.hysky.skyblocker.utils.render.RenderHelper;
+import de.hysky.skyblocker.utils.tictactoe.BoardIndex;
import de.hysky.skyblocker.utils.tictactoe.TicTacToeUtils;
import net.fabricmc.fabric.api.client.rendering.v1.WorldRenderContext;
import net.minecraft.client.MinecraftClient;
@@ -49,7 +50,8 @@ public class TicTacToe extends DungeonPuzzle {
try {
//Only attempt to solve if the puzzle wasn't just completed and if its the player's turn
- if (itemFramesThatHoldMaps.size() != 9 && itemFramesThatHoldMaps.size() % 2 == 1) {
+ //The low bit will always be set to 1 on odd numbers
+ if (itemFramesThatHoldMaps.size() != 9 && (itemFramesThatHoldMaps.size() & 1) == 1) {
char[][] board = new char[3][3];
for (ItemFrameEntity itemFrame : itemFramesThatHoldMaps) {
@@ -83,7 +85,7 @@ public class TicTacToe extends DungeonPuzzle {
if (row == -1 || column == -1) continue;
//Get the color of the middle pixel of the map which determines whether its X or O
- int middleColor = mapState.colors[8256] & 255;
+ int middleColor = mapState.colors[8256] & 0xFF;
if (middleColor == 114) {
board[row][column] = 'X';
@@ -92,11 +94,11 @@ public class TicTacToe extends DungeonPuzzle {
}
}
- int bestMove = TicTacToeUtils.getBestMove(board) - 1;
+ BoardIndex bestMove = TicTacToeUtils.getBestMove(board);
double nextX = 8;
- double nextY = 72 - (double) (bestMove / 3);
- double nextZ = 17 - (bestMove % 3);
+ double nextY = 72 - bestMove.row();
+ double nextZ = 17 - bestMove.column();
BlockPos nextPos = DungeonManager.getCurrentRoom().relativeToActual(BlockPos.ofFloored(nextX, nextY, nextZ));
nextBestMoveToMake = new Box(nextPos);
diff --git a/src/main/java/de/hysky/skyblocker/utils/tictactoe/BoardIndex.java b/src/main/java/de/hysky/skyblocker/utils/tictactoe/BoardIndex.java
new file mode 100644
index 00000000..bd9200ad
--- /dev/null
+++ b/src/main/java/de/hysky/skyblocker/utils/tictactoe/BoardIndex.java
@@ -0,0 +1,5 @@
+package de.hysky.skyblocker.utils.tictactoe;
+
+public record BoardIndex(int row, int column) {
+
+}
diff --git a/src/main/java/de/hysky/skyblocker/utils/tictactoe/TicTacToeUtils.java b/src/main/java/de/hysky/skyblocker/utils/tictactoe/TicTacToeUtils.java
index fde18f27..0725b2ce 100644
--- a/src/main/java/de/hysky/skyblocker/utils/tictactoe/TicTacToeUtils.java
+++ b/src/main/java/de/hysky/skyblocker/utils/tictactoe/TicTacToeUtils.java
@@ -1,105 +1,119 @@
package de.hysky.skyblocker.utils.tictactoe;
+import java.util.Arrays;
import java.util.Collections;
-import java.util.HashMap;
-import java.util.Map;
+import java.util.Comparator;
+import java.util.stream.Stream;
+
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap;
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;
- }
- }
+ public static BoardIndex getBestMove(char[][] board) {
+ Object2IntOpenHashMap<BoardIndex> moves = new Object2IntOpenHashMap<>();
+
+ for (int row = 0; row < board.length; row++) {
+ for (int column = 0; column < board[row].length; column++) {
+ // Simulate the move as O if the square is empty to determine a solution
+ if (board[row][column] != '\0') continue;
+ board[row][column] = 'O';
+ int score = alphabeta(board, Integer.MIN_VALUE, Integer.MAX_VALUE, 0, false);
+ board[row][column] = '\0';
+
+ moves.put(new BoardIndex(row, column), score);
+ }
+ }
+
+ return Collections.max(moves.object2IntEntrySet(), Comparator.comparingInt(Object2IntMap.Entry::getIntValue)).getKey();
+ }
+
+ private static boolean hasMovesAvailable(char[][] board) {
+ return Arrays.stream(board).flatMap(row -> Stream.of(row[0], row[1], row[2])).anyMatch(c -> c == '\0');
+ }
+
+ private static int getScore(char[][] board) {
+ // Check if X or O has won horizontally
+ for (int row = 0; row < 3; row++) {
+ if (board[row][0] == board[row][1] && board[row][0] == board[row][2]) {
+ switch (board[row][0]) {
+ case 'X': return -10;
+ case 'O': return 10;
+ }
+ }
+ }
+
+ // Check if X or O has won vertically
+ for (int column = 0; column < 3; column++) {
+ if (board[0][column] == board[1][column] && board[0][column] == board[2][column]) {
+ switch (board[0][column]) {
+ case 'X': return -10;
+ case 'O': return 10;
+ }
+ }
+ }
+
+ // Check if X or O has won diagonally
+ // Top left to bottom right
+ if (board[0][0] == board[1][1] && board[0][0] == board[2][2]) {
+ switch (board[0][0]) {
+ case 'X': return -10;
+ case 'O': return 10;
+ }
+ }
+
+ // Top right to bottom left
+ if (board[0][2] == board[1][1] && board[0][2] == board[2][0]) {
+ switch (board[0][2]) {
+ case 'X': return -10;
+ case 'O': return 10;
+ }
+ }
+
+ return 0;
+ }
+
+ private static int alphabeta(char[][] board, int alpha, int beta, int depth, boolean maximizePlayer) {
+ int score = getScore(board);
+
+ if (score == 10 || score == -10) return score;
+ if (!hasMovesAvailable(board)) return 0;
+
+ if (maximizePlayer) {
+ int bestScore = Integer.MIN_VALUE;
+
+ for (int row = 0; row < 3; row++) {
+ for (int column = 0; column < 3; column++) {
+ if (board[row][column] == '\0') {
+ board[row][column] = 'O';
+ bestScore = Math.max(bestScore, alphabeta(board, alpha, beta, depth + 1, false));
+ board[row][column] = '\0';
+ alpha = Math.max(alpha, bestScore);
+
+ //Is this correct? Well the algorithm seems to solve it so I will assume it is
+ if (beta <= alpha) break; // Pruning
+ }
+ }
+ }
+
+ return bestScore - depth;
+ } else {
+ int bestScore = Integer.MAX_VALUE;
+
+ for (int row = 0; row < 3; row++) {
+ for (int column = 0; column < 3; column++) {
+ if (board[row][column] == '\0') {
+ board[row][column] = 'X';
+ bestScore = Math.min(bestScore, alphabeta(board, alpha, beta, depth + 1, true));
+ board[row][column] = '\0';
+ beta = Math.min(beta, bestScore);
+
+ if (beta <= alpha) break; // Pruning
+ }
+ }
+ }
+
+ return bestScore + depth;
+ }
+ }
}
\ No newline at end of file
--
cgit