Create A Game Search Problem in Java Assignment Solution

Instructions

Objective

Write a java assignment program to solve a game search problem in a java programming language. This assignment challenges you to implement a solution that tackles a game search problem using Java. Your task is to create a program that can navigate through a game space, searching for a specific goal. Through this assignment, you will not only enhance your Java programming skills but also gain experience in problem-solving and algorithmic thinking within the context of game search.

Requirements and Specifications

Source Code

BOARD

import java.util.ArrayList; import java.util.Collection; import java.util.Objects; public class Board { public static final int SIZE = 6; private static final int[][] DIRS = {{-1,-1}, {-1,0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; private static final int O = 1; private static final int X = 2; private static final int COVERED = 3; private final int[][] grid = new int[SIZE][SIZE]; public Board makeMove(Location location, boolean firstPlayerToMove) { if (grid[location.row][location.col] != 0) { return null; } Board copy = new Board(); for (int i = 0; i for (int j = 0; j copy.grid[i][j] = grid[i][j]; } } copy.grid[location.row][location.col] = firstPlayerToMove ? O : X; for (int[] d : DIRS ) { if (location.row + d[0] < SIZE && location.row + d[0] >= 0 && location.col + d[1] < SIZE && location.col + d[1] >= 0) { if (copy.grid[location.row + d[0]][location.col + d[1]] == 0) { copy.grid[location.row + d[0]][location.col + d[1]] = COVERED; } } } return copy; } public int evaluate(boolean firstPlayerToMove) { if (getPossibleMoves().isEmpty()) { return firstPlayerToMove ? Integer.MIN_VALUE : Integer.MAX_VALUE; } return 0; } public Collection getPossibleMoves() { Collection result = new ArrayList<>(); for (int i = 0; i for (int j = 0; j if (grid[i][j] == 0) { result.add(new Location(i, j)); } } } return result; } public static class Location { int row; int col; Location(int row, int col) { this.row = row; this.col = col; } @Override public String toString() { return "(" + row + "," + col + ")"; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Location location = (Location) o; return row == location.row && col == location.col; } @Override public int hashCode() { return Objects.hash(row, col); } } public boolean isOver() { return getPossibleMoves().isEmpty(); } @Override public String toString() { StringBuilder builder = new StringBuilder(); for (int i = 0; i for(int j = 0; j builder.append("["); switch (grid[i][j]) { case 0: builder.append(" "); break; case 1: builder.append("O"); break; case 2: builder.append("X"); break; case 3: builder.append("/"); break; default: throw new IllegalStateException(); } builder.append("]"); } builder.append(System.lineSeparator()); } return builder.toString(); } }

SOLVER

public class Solver { private static final int DEPTH = 4; public static Board.Location findMove(Board board, boolean firstPlayerToMove, boolean pruning) { NodeResult result = minimax(board, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, firstPlayerToMove, pruning); // System.out.println(pruning ? "AB Pruning Algorithm:" : "Minimax Algorithm:"); // System.out.println("Board Size - (" + Board.SIZE + "x" + Board.SIZE + ")"); // System.out.println("Nodes Expanded - " + result.nodesExpanded); // System.out.println("Depth - " + DEPTH); return result.move; } private static NodeResult minimax(Board board, int depth, int alpha, int beta, boolean firstPlayerMove, boolean pruning) { if (board.isOver() || depth == DEPTH) { return new NodeResult(board, null, board.evaluate(firstPlayerMove), 1, 0); } if (firstPlayerMove) { int maxDepth = 0; int nodesExpanded = 1; NodeResult best = null; for (Board.Location loc : board.getPossibleMoves()) { NodeResult res = minimax(board.makeMove(loc, firstPlayerMove), depth+1, alpha, beta, false, pruning); nodesExpanded += res.nodesExpanded; maxDepth = Math.max(maxDepth, 1 + res.depthLevel); if (best == null || res.value > best.value) { best = new NodeResult(board, loc, res.value); } // updating search statistics best.nodesExpanded = nodesExpanded; best.depthLevel = maxDepth; // making pruning if necessary if (pruning) { if (best.value >= beta) { break; } alpha = Math.max(alpha, best.value); } } return best; } else { int maxDepth = 0; int nodesExpanded = 1; NodeResult best = null; for (Board.Location loc : board.getPossibleMoves()) { NodeResult res = minimax(board.makeMove(loc, firstPlayerMove), depth+1, alpha, beta, true, pruning); nodesExpanded += res.nodesExpanded; maxDepth = Math.max(maxDepth, 1 + res.depthLevel); if (best == null || res.value < best.value) { best = new NodeResult(board, loc, res.value); } // updating search statistics best.nodesExpanded = nodesExpanded; best.depthLevel = maxDepth; // making pruning if necessary if (pruning) { if (best.value <= alpha) { break; } beta = Math.min(beta, best.value); } } return best; } } private static class NodeResult { Board board; Board.Location move; int value; int nodesExpanded; int depthLevel; public NodeResult(Board board, Board.Location move, int value, int nodesExpanded, int depthLevel) { this.board = board; this.move = move; this.value = value; this.nodesExpanded = nodesExpanded; this.depthLevel = depthLevel; } public NodeResult(Board board, Board.Location move, int value) { this(board, move, value, 0, 0); } } }

TESTER

import java.io.IOException; import java.io.PrintWriter; import java.util.Scanner; public class Tester { enum SearchType { MM, AB; } private static final String OUTPUT_FILENAME = "Readme.txt"; public static void main(String[] args) { try(Scanner scanner = new Scanner(System.in)) { String[] parts = scanner.nextLine().split("\\s+"); int aiPlayer = Integer.parseInt(parts[0]); SearchType st = SearchType.valueOf(parts[1]); Board board = new Board(); int currPlayer = 1; while(!board.isOver()) { System.out.println(board); if (currPlayer == aiPlayer) { Board.Location chosen = Solver.findMove(board, currPlayer == 1, st == SearchType.AB); System.out.println("Move " + chosen + " is chosen"); board = board.makeMove(chosen, currPlayer == 1); } else { Board.Location chosen = null; while(chosen == null) { try { System.out.println("Input your move: "); String[] locs = scanner.nextLine().split("\\s+"); if (locs.length != 2) { throw new IllegalArgumentException(); } int r = Integer.parseInt(locs[0]); int c = Integer.parseInt(locs[1]); Board.Location loc = new Board.Location(r, c); if (board.getPossibleMoves().contains(loc)) { chosen = loc; } else { throw new IllegalArgumentException(); } } catch (Exception e) { System.out.println("Invalid input"); } } System.out.println("Move " + chosen + " is chosen"); board = board.makeMove(chosen, currPlayer == 1); } currPlayer = 3 - currPlayer; } System.out.println(board); System.out.println("Player " + currPlayer + " lost"); } } }