Program To Solve 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

program to solve a game search problem in java

program to solve a game search problem in java 1

program to solve a game search problem in java 2

program to solve a game search problem in java 3

program to solve a game search problem in java 4

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");
 }
 }
}

Create A Game Search Problem in Java Assignment Solution.

Instructions

Requirements and Specifications