Add Tic Tac Toe puzzle solver

Uses minimax to find best move

7 files changed, 224 insertions, 13 deletions

diff --git a/README.md b/README.md
index 43fc4cb..d543c23 100644
--- a/README.md
+++ b/README.md
@@ -25,7 +25,7 @@ Discord Server: https://discord.gg/QsEkNQS
 - Fishing, jerry fishing, fishing festival, spooky fishing trackers
 - Expertise kills in fishing rod lore
 - Catacombs trackers
-- Dungeons puzzle solver (Riddle, trivia, blaze, creeper, water)
+- Dungeons puzzle solver (Riddle, trivia, blaze, creeper, water, tic tac toe)
 - Catacombs F7 Stage 3 solvers (Starts with letter, select all colour, ignore arrows on sea lanterns)
 - Find correct Livid (with graphic display of HP)
 - Pet background colors based on level
@@ -41,7 +41,7 @@ Discord Server: https://discord.gg/QsEkNQS
 ## Commands
 - /dhelp - Returns this message in-game.
 - /dsm - Opens the GUI for Danker's Skyblock Mod.
-- /toggle <gparty/coords/golden/slayercount/rngesusalerts/splitfishing/chatmaddox/spiritbearalerts/aotd/lividdagger/sceptremessages/midasstaffmessages/implosionmessages/healmessages/petcolors/dungeontimer/golemalerts/expertiselore/skill50display/outlinetext/caketimer/lowhealthnotify/lividsolver/threemanpuzzle/oruopuzzle/blazepuzzle/creeperpuzzle/waterpuzzle/startswithterminal/selectallterminal/itemframeonsealanterns/list> - Toggles features. /toggle list returns values of every toggle.
+- /toggle <gparty/coords/golden/slayercount/rngesusalerts/splitfishing/chatmaddox/spiritbearalerts/aotd/lividdagger/sceptremessages/midasstaffmessages/implosionmessages/healmessages/petcolors/dungeontimer/golemalerts/expertiselore/skill50display/outlinetext/caketimer/lowhealthnotify/lividsolver/threemanpuzzle/oruopuzzle/blazepuzzle/creeperpuzzle/waterpuzzle/tictactoepuzzle/startswithterminal/selectallterminal/itemframeonsealanterns/list> - Toggles features. /toggle list returns values of every toggle.
 - /setkey <key> - Sets API key.
 - /getkey - Returns key set with /setkey and copies it to your clipboard.
 - /loot <zombie/spider/wolf/fishing/catacombs> [winter/spooky/f(1-7)/session] - Returns loot received from slayer quests or fishing stats. /loot fishing winter returns winter sea creatures instead.
diff --git a/src/main/java/me/Danker/DankersSkyblockMod.java b/src/main/java/me/Danker/DankersSkyblockMod.java
index 3cfd57c..4a1e9c7 100644
--- a/src/main/java/me/Danker/DankersSkyblockMod.java
+++ b/src/main/java/me/Danker/DankersSkyblockMod.java
@@ -4,6 +4,7 @@ import com.google.gson.JsonObject;
 import me.Danker.commands.*;
 import me.Danker.gui.*;
 import me.Danker.handlers.*;
+import me.Danker.utils.TicTacToeUtils;
 import me.Danker.utils.Utils;
 import net.minecraft.block.Block;
 import net.minecraft.client.Minecraft;
@@ -24,10 +25,12 @@ import net.minecraft.inventory.Container;
 import net.minecraft.inventory.ContainerChest;
 import net.minecraft.inventory.IInventory;
 import net.minecraft.inventory.Slot;
+import net.minecraft.item.ItemMap;
 import net.minecraft.item.ItemStack;
 import net.minecraft.nbt.NBTTagCompound;
 import net.minecraft.util.*;
 import net.minecraft.world.World;
+import net.minecraft.world.storage.MapData;
 import net.minecraftforge.client.ClientCommandHandler;
 import net.minecraftforge.client.GuiIngameForge;
 import net.minecraftforge.client.event.ClientChatReceivedEvent;
@@ -111,6 +114,7 @@ public class DankersSkyblockMod
 	static List<Vec3[]> creeperLines = new ArrayList<>();
 	static boolean prevInWaterRoom = false;
 	static boolean inWaterRoom = false;
+	static AxisAlignedBB correctTicTacToeButton = null;
 	
     static double dungeonStartTime = 0;
     static double bloodOpenTime = 0;
@@ -2298,7 +2302,7 @@ public class DankersSkyblockMod
     			ConfigHandler.writeStringConfig("misc", "display", DisplayCommand.display);
     		}
     		
-    		if (ToggleCommand.creeperToggled && Utils.inDungeons && world != null) {
+    		if (ToggleCommand.creeperToggled && Utils.inDungeons && world != null && player != null) {
     	    	double x = player.posX;
     	    	double y = player.posY;
     	    	double z = player.posZ;
@@ -2335,7 +2339,7 @@ public class DankersSkyblockMod
     			}
     		}
     		
-    		if (ToggleCommand.waterToggled && Utils.inDungeons && world != null) {
+    		if (ToggleCommand.waterToggled && Utils.inDungeons && world != null && player != null) {
     			// multi thread block checking
     			new Thread(() -> {
     				prevInWaterRoom = inWaterRoom;
@@ -2482,6 +2486,92 @@ public class DankersSkyblockMod
     			}
     		}
     		
+    		if (ToggleCommand.ticTacToeToggled && Utils.inDungeons && world != null && player != null) {
+    			correctTicTacToeButton = null;
+    			AxisAlignedBB aabb = new AxisAlignedBB(player.posX - 6, player.posY - 6, player.posZ - 6, player.posX + 6, player.posY + 6, player.posZ + 6);
+				List<EntityItemFrame> itemFrames = world.getEntitiesWithinAABB(EntityItemFrame.class, aabb);
+				List<EntityItemFrame> itemFramesWithMaps = new ArrayList<>();
+				// Find how many item frames have maps already placed
+				for (EntityItemFrame itemFrame : itemFrames) {
+					ItemStack item = itemFrame.getDisplayedItem();
+					if (item == null || !(item.getItem() instanceof ItemMap)) continue;
+					MapData mapData = ((ItemMap) item.getItem()).getMapData(item, world);
+					if (mapData == null) continue;
+
+					itemFramesWithMaps.add(itemFrame);
+				}
+
+				// Only run when it's your turn
+				if (itemFramesWithMaps.size() != 9 && itemFramesWithMaps.size() % 2 == 1) {
+					char[][] board = new char[3][3];
+					BlockPos leftmostRow = null;
+					int sign = 1;
+					char facing = 'X';
+					for (EntityItemFrame itemFrame : itemFramesWithMaps) {
+						ItemStack map = itemFrame.getDisplayedItem();
+						MapData mapData = ((ItemMap) map.getItem()).getMapData(map, world);
+
+						// Find position on board
+						int row = 0;
+						int column;
+						sign = 1;
+
+						if (itemFrame.facingDirection == EnumFacing.SOUTH || itemFrame.facingDirection == EnumFacing.WEST) {
+							sign = -1;
+						}
+
+						BlockPos itemFramePos = new BlockPos(itemFrame.posX, Math.floor(itemFrame.posY), itemFrame.posZ);
+						for (int i = 2; i >= 0; i--) {
+							int realI = i * sign;
+							BlockPos blockPos = itemFramePos;
+							if (itemFrame.posX % 0.5 == 0) {
+								blockPos = itemFramePos.add(realI, 0, 0);
+							} else if (itemFrame.posZ % 0.5 == 0) {
+								blockPos = itemFramePos.add(0, 0, realI);
+								facing = 'Z';
+							}
+							Block block = world.getBlockState(blockPos).getBlock();
+							if (block == Blocks.air || block == Blocks.stone_button) {
+								leftmostRow = blockPos;
+								row = i;
+								break;
+							}
+						}
+
+						if (itemFrame.posY == 72.5) {
+							column = 0;
+						} else if (itemFrame.posY == 71.5) {
+							column = 1;
+						} else if (itemFrame.posY == 70.5) {
+							column = 2;
+						} else {
+							continue;
+						}
+
+						// Get colour
+						// Middle pixel = 64*128 + 64 = 8256
+						int colourInt = mapData.colors[8256] & 255;
+						if (colourInt == 114) {
+							board[column][row] = 'X';
+						} else if (colourInt == 33) {
+							board[column][row] = 'O';
+						}
+					}
+					System.out.println("Board: " + Arrays.deepToString(board));
+
+					// Draw best move
+					int bestMove = TicTacToeUtils.getBestMove(board) - 1;
+					System.out.println("Best move slot: " + bestMove);
+					if (leftmostRow != null) {
+						double drawX = facing == 'X' ? leftmostRow.getX() - sign * (bestMove % 3) : leftmostRow.getX();
+						double drawY = 72 - Math.floor(bestMove / 3);
+						double drawZ = facing == 'Z' ? leftmostRow.getZ() - sign * (bestMove % 3) : leftmostRow.getZ();
+
+						correctTicTacToeButton = new AxisAlignedBB(drawX, drawY, drawZ, drawX + 1, drawY + 1, drawZ + 1);
+					}
+				}
+    		}
+    		
     		tickAmount = 0;
     	}
     	
@@ -2594,6 +2684,9 @@ public class DankersSkyblockMod
     			Utils.draw3DLine(creeperLines.get(i)[0], creeperLines.get(i)[1], CREEPER_COLOURS[i % 10], event.partialTicks);
     		}
     	}
+    	if (ToggleCommand.ticTacToeToggled && correctTicTacToeButton != null) {
+    		Utils.draw3DBox(correctTicTacToeButton, 0x40FF40, event.partialTicks);
+		}
     }
     
     @SubscribeEvent
diff --git a/src/main/java/me/Danker/commands/DHelpCommand.java b/src/main/java/me/Danker/commands/DHelpCommand.java
index f8864cd..b65203e 100644
--- a/src/main/java/me/Danker/commands/DHelpCommand.java
+++ b/src/main/java/me/Danker/commands/DHelpCommand.java
@@ -34,7 +34,7 @@ public class DHelpCommand extends CommandBase {
 													EnumChatFormatting.GOLD + " Commands, " + EnumChatFormatting.GREEN + " Keybinds.\n" +
 													EnumChatFormatting.GOLD + " /dhelp" + EnumChatFormatting.AQUA + " - Returns this message.\n" +
 													EnumChatFormatting.GOLD + " /dsm" + EnumChatFormatting.AQUA + " - Opens the GUI for Danker's Skyblock Mod.\n" +
-													EnumChatFormatting.GOLD + " /toggle <gparty/coords/golden/slayercount/rngesusalerts/splitfishing/chatmaddox/spiritbearalerts/aotd/lividdagger/sceptremessages/midasstaffmessages/implosionmessages/healmessages/petcolors/dungeontimer/golemalerts/expertiselore/skill50display/outlinetext/caketimer/lowhealthnotify/lividsolver/threemanpuzzle/oruopuzzle/blazepuzzle/creeperpuzzle/waterpuzzle/startswithterminal/selectallterminal/itemframeonsealanterns/list>" + EnumChatFormatting.AQUA + " - Toggles features. /toggle list returns values of every toggle.\n" +
+													EnumChatFormatting.GOLD + " /toggle <gparty/coords/golden/slayercount/rngesusalerts/splitfishing/chatmaddox/spiritbearalerts/aotd/lividdagger/sceptremessages/midasstaffmessages/implosionmessages/healmessages/petcolors/dungeontimer/golemalerts/expertiselore/skill50display/outlinetext/caketimer/lowhealthnotify/lividsolver/threemanpuzzle/oruopuzzle/blazepuzzle/creeperpuzzle/waterpuzzle/tictactoepuzzle/startswithterminal/selectallterminal/itemframeonsealanterns/list>" + EnumChatFormatting.AQUA + " - Toggles features. /toggle list returns values of every toggle.\n" +
 													EnumChatFormatting.GOLD + " /setkey <key>" + EnumChatFormatting.AQUA + " - Sets API key.\n" +
 													EnumChatFormatting.GOLD + " /getkey" + EnumChatFormatting.AQUA + " - Returns key set with /setkey and copies it to your clipboard.\n" +
 													EnumChatFormatting.GOLD + " /loot <zombie/spider/wolf/fishing/catacombs/mythological/> [winter/festival/spooky/f(1-7)/session]" + EnumChatFormatting.AQUA + " - Returns loot received from slayer quests or fishing stats. /loot fishing winter returns winter sea creatures instead.\n" +
diff --git a/src/main/java/me/Danker/commands/ToggleCommand.java b/src/main/java/me/Danker/commands/ToggleCommand.java
index 5e4c136..32c7a2a 100644
--- a/src/main/java/me/Danker/commands/ToggleCommand.java
+++ b/src/main/java/me/Danker/commands/ToggleCommand.java
@@ -42,6 +42,7 @@ public class ToggleCommand extends CommandBase implements ICommand {
 	public static boolean blazeToggled;
 	public static boolean creeperToggled;
 	public static boolean waterToggled;
+	public static boolean ticTacToeToggled;
 	// Terminal Helpers
 	public static boolean startsWithToggled;
 	public static boolean selectAllToggled;
@@ -57,8 +58,8 @@ public class ToggleCommand extends CommandBase implements ICommand {
 		return "/" + getCommandName() + " <gparty/coords/golden/slayercount/rngesusalerts/splitfishing/chatmaddox/spiritbearalert/" + 
 										  "aotd/lividdagger/sceptremessages/petcolors/dungeontimer/golemalerts/expertiselore/skill50display/" + 
 										  "outlinetext/midasstaffmessages/implosionmessages/healmessages/caketimer/lowhealthnotify/" +
-										  "lividsolver/threemanpuzzle/oruopuzzle/blazepuzzle/creeperpuzzle/waterpuzzle/startswithterminal/" +
-										  "selectallterminal/itemframeonsealanterns/list>";
+										  "lividsolver/threemanpuzzle/oruopuzzle/blazepuzzle/creeperpuzzle/waterpuzzle/tictactoepuzzle/" +
+										  "startswithterminal/selectallterminal/itemframeonsealanterns/list>";
 	}
 
 	@Override
@@ -75,8 +76,8 @@ public class ToggleCommand extends CommandBase implements ICommand {
 														  "expertiselore", "skill50display", "outlinetext", "midasstaffmessages",
 														  "implosionmessages", "healmessages", "caketimer", "lowhealthnotify",
 														  "lividsolver", "threemanpuzzle", "oruopuzzle", "blazepuzzle",
-														  "creeperpuzzle", "waterpuzzle", "startswithterminal", "selectallterminal",
-														  "itemframeonsealanterns", "list");
+														  "creeperpuzzle", "waterpuzzle", "tictactoepuzzle", "startswithterminal",
+														  "selectallterminal", "itemframeonsealanterns", "list");
 		}
 		return null;
 	}
@@ -232,6 +233,11 @@ public class ToggleCommand extends CommandBase implements ICommand {
 				ConfigHandler.writeBooleanConfig("toggles", "WaterPuzzle", waterToggled);
 				player.addChatMessage(new ChatComponentText(DankersSkyblockMod.MAIN_COLOUR + "Water puzzle solver has been set to " + DankersSkyblockMod.SECONDARY_COLOUR + waterToggled + DankersSkyblockMod.MAIN_COLOUR + "."));
 				break;
+			case "tictactoepuzzle":
+				ticTacToeToggled = !ticTacToeToggled;
+				ConfigHandler.writeBooleanConfig("toggles", "TicTacToePuzzle", ticTacToeToggled);
+				player.addChatMessage(new ChatComponentText(DankersSkyblockMod.MAIN_COLOUR + "Tic tac toe puzzle solver has been set to " + DankersSkyblockMod.SECONDARY_COLOUR + ticTacToeToggled + DankersSkyblockMod.MAIN_COLOUR + "."));
+				break;
 			case "startswithterminal":
 				startsWithToggled = !startsWithToggled;
 				ConfigHandler.writeBooleanConfig("toggles", "StartsWithTerminal", startsWithToggled);
@@ -276,6 +282,7 @@ public class ToggleCommand extends CommandBase implements ICommand {
 															DankersSkyblockMod.TYPE_COLOUR + " Blaze puzzle solver: " + DankersSkyblockMod.VALUE_COLOUR + blazeToggled + "\n" +
 															DankersSkyblockMod.TYPE_COLOUR + " Creeper puzzle solver: " + DankersSkyblockMod.VALUE_COLOUR + creeperToggled + "\n" +
 															DankersSkyblockMod.TYPE_COLOUR + " Water puzzle solver: " + DankersSkyblockMod.VALUE_COLOUR + waterToggled + "\n" +
+															DankersSkyblockMod.TYPE_COLOUR + " Tic tac toe puzzle solver: " + DankersSkyblockMod.VALUE_COLOUR + ticTacToeToggled + "\n" +
 															DankersSkyblockMod.TYPE_COLOUR + " Starts with letter terminal solver: " + DankersSkyblockMod.VALUE_COLOUR + startsWithToggled + "\n" +
 															DankersSkyblockMod.TYPE_COLOUR + " Select all color items terminal solver: " + DankersSkyblockMod.VALUE_COLOUR + selectAllToggled + "\n" +
 															DankersSkyblockMod.TYPE_COLOUR + " Ignore item frames on sea lanterns: " + DankersSkyblockMod.VALUE_COLOUR + itemFrameOnSeaLanternsToggled));
diff --git a/src/main/java/me/Danker/gui/PuzzleSolversGui.java b/src/main/java/me/Danker/gui/PuzzleSolversGui.java
index 059d41d..8701563 100644
--- a/src/main/java/me/Danker/gui/PuzzleSolversGui.java
+++ b/src/main/java/me/Danker/gui/PuzzleSolversGui.java
@@ -21,6 +21,7 @@ public class PuzzleSolversGui extends GuiScreen {
 	private GuiButton blaze;
 	private GuiButton creeper;
 	private GuiButton water;
+	private GuiButton ticTacToe;
 	private GuiButton startsWith;
 	private GuiButton selectAll;
 	private GuiButton itemFrameOnSeaLanterns;
@@ -52,10 +53,11 @@ public class PuzzleSolversGui extends GuiScreen {
 		blaze = new GuiButton(0, width / 2 - 100, (int) (height * 0.3), "Blaze Solver: " + Utils.getColouredBoolean(ToggleCommand.blazeToggled));
 		creeper = new GuiButton(0, width / 2 - 100, (int) (height * 0.4), "Creeper Solver: " + Utils.getColouredBoolean(ToggleCommand.creeperToggled));
 		water = new GuiButton(0, width / 2 - 100, (int) (height * 0.5), "Water Solver: " + Utils.getColouredBoolean(ToggleCommand.waterToggled));
-		startsWith = new GuiButton(0, width / 2 - 100, (int) (height * 0.6), "Starts With Letter Terminal Solver: " + Utils.getColouredBoolean(ToggleCommand.startsWithToggled));
-		selectAll = new GuiButton(0, width / 2 - 100, (int) (height * 0.7), "Select All Color Terminal Solver: " + Utils.getColouredBoolean(ToggleCommand.selectAllToggled));
+		ticTacToe = new GuiButton(0, width / 2 - 100, (int) (height * 0.6), "Tic Tac Toe Solver: " + Utils.getColouredBoolean(ToggleCommand.ticTacToeToggled));
+		startsWith = new GuiButton(0, width / 2 - 100, (int) (height * 0.7), "Starts With Letter Terminal Solver: " + Utils.getColouredBoolean(ToggleCommand.startsWithToggled));
 		// Page 2
-		itemFrameOnSeaLanterns = new GuiButton(0, width / 2 - 100, (int) (height * 0.1), "Ignore Arrows On Sea Lanterns: " + Utils.getColouredBoolean(ToggleCommand.itemFrameOnSeaLanternsToggled));
+		selectAll = new GuiButton(0, width / 2 - 100, (int) (height * 0.1), "Select All Color Terminal Solver: " + Utils.getColouredBoolean(ToggleCommand.selectAllToggled));
+		itemFrameOnSeaLanterns = new GuiButton(0, width / 2 - 100, (int) (height * 0.2), "Ignore Arrows On Sea Lanterns: " + Utils.getColouredBoolean(ToggleCommand.itemFrameOnSeaLanternsToggled));
 		
 		switch (page) {
 			case 1:
@@ -64,11 +66,12 @@ public class PuzzleSolversGui extends GuiScreen {
 				this.buttonList.add(blaze);
 				this.buttonList.add(creeper);
 				this.buttonList.add(water);
+				this.buttonList.add(ticTacToe);
 				this.buttonList.add(startsWith);
-				this.buttonList.add(selectAll);
 				this.buttonList.add(nextPage);
 				break;
 			case 2:
+				this.buttonList.add(selectAll);
 				this.buttonList.add(itemFrameOnSeaLanterns);
 				this.buttonList.add(backPage);
 				break;
@@ -110,6 +113,10 @@ public class PuzzleSolversGui extends GuiScreen {
 			ToggleCommand.waterToggled = !ToggleCommand.waterToggled;
 			ConfigHandler.writeBooleanConfig("toggles", "WaterPuzzle", ToggleCommand.waterToggled);
 			water.displayString = "Water Solver: " + Utils.getColouredBoolean(ToggleCommand.waterToggled);
+		} else if (button == ticTacToe) {
+			ToggleCommand.ticTacToeToggled = !ToggleCommand.ticTacToeToggled;
+			ConfigHandler.writeBooleanConfig("toggles", "TicTacToePuzzle", ToggleCommand.ticTacToeToggled);
+			ticTacToe.displayString = "Tic Tac Toe Solver: " + Utils.getColouredBoolean(ToggleCommand.ticTacToeToggled);
 		} else if (button == startsWith) {
 			ToggleCommand.startsWithToggled = !ToggleCommand.startsWithToggled;
 			ConfigHandler.writeBooleanConfig("toggles", "StartsWithTerminal", ToggleCommand.startsWithToggled);
diff --git a/src/main/java/me/Danker/handlers/ConfigHandler.java b/src/main/java/me/Danker/handlers/ConfigHandler.java
index 73ff7e3..54c1258 100644
--- a/src/main/java/me/Danker/handlers/ConfigHandler.java
+++ b/src/main/java/me/Danker/handlers/ConfigHandler.java
@@ -197,6 +197,7 @@ public class ConfigHandler {
 		if (!hasKey("toggles", "BlazePuzzle")) writeBooleanConfig("toggles", "BlazePuzzle", false);
 		if (!hasKey("toggles", "CreeperPuzzle")) writeBooleanConfig("toggles", "CreeperPuzzle", false);
 		if (!hasKey("toggles", "WaterPuzzle")) writeBooleanConfig("toggles", "WaterPuzzle", false);
+		if (!hasKey("toggles", "TicTacToePuzzle")) writeBooleanConfig("toggles", "TicTacToePuzzle", false);
 		if (!hasKey("toggles", "StartsWithTerminal")) writeBooleanConfig("toggles", "StartsWithTerminal", false);
 		if (!hasKey("toggles", "SelectAllTerminal")) writeBooleanConfig("toggles", "SelectAllTerminal", false);
 		if (!hasKey("toggles", "IgnoreItemFrameOnSeaLanterns")) writeBooleanConfig("toggles", "IgnoreItemFrameOnSeaLanterns", false);
@@ -437,6 +438,7 @@ public class ConfigHandler {
 		ToggleCommand.blazeToggled = getBoolean("toggles", "BlazePuzzle");
 		ToggleCommand.creeperToggled = getBoolean("toggles", "CreeperPuzzle");
 		ToggleCommand.waterToggled = getBoolean("toggles", "WaterPuzzle");
+		ToggleCommand.ticTacToeToggled = getBoolean("toggles", "TicTacToePuzzle");
 		ToggleCommand.startsWithToggled = getBoolean("toggles", "StartsWithTerminal");
 		ToggleCommand.selectAllToggled = getBoolean("toggles", "SelectAllTerminal");
 		ToggleCommand.itemFrameOnSeaLanternsToggled = getBoolean("toggles", "IgnoreItemFrameOnSeaLanterns");
diff --git a/src/main/java/me/Danker/utils/TicTacToeUtils.java b/src/main/java/me/Danker/utils/TicTacToeUtils.java
new file mode 100644
index 0000000..ab1b853
--- /dev/null
+++ b/src/main/java/me/Danker/utils/TicTacToeUtils.java
@@ -0,0 +1,102 @@
+package me.Danker.utils;
+
+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 = minimax(board, false, 0);
+                board[row][col] = '\0';
+                moves.put(row * 3 + col + 1, score);
+            }
+        }
+        return Collections.max(moves.entrySet(), Map.Entry.comparingByValue()).getKey();
+    }
+
+    public static boolean hasMovesLeft(char[][] board) {
+        for (char[] rows : board) {
+            for (char col : rows) {
+                if (col == '\0') return true;
+            }
+        }
+        return false;
+    }
+
+    public static int getBoardRanking(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;
+    }
+
+    public static int minimax(char[][] board, boolean max, int depth) {
+        int score = getBoardRanking(board);
+        if (score == 10 || score == -10) return score;
+        if (!hasMovesLeft(board)) return 0;
+
+        if (max) {
+            int bestScore = -1000;
+            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, minimax(board, false, depth + 1));
+                        board[row][col] = '\0';
+                    }
+                }
+            }
+            return bestScore - depth;
+        } else {
+            int bestScore = 1000;
+            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, minimax(board, true, depth + 1));
+                        board[row][col] = '\0';
+                    }
+                }
+            }
+            return bestScore + depth;
+        }
+    }
+
+}