Tic Tac Toe Rewrite/Refactor

3 files changed, 124 insertions, 103 deletions

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