IntroductionThere are two tasks in this coursework: (i) to implement minimax, and (ii) to implement minimax with alpha-beta pruning, for tic-tac-toe (noughts-and-crosses). You should assume a 3 3 board, with two players who take turns to place an “X” or a “O” on the board. The rst player to obtain a horizontal, vertical or diagonal line of 3 “X”s or “O”s is the winner. If the board is full and no line of 3 exists the game is a draw.Task 1: Standard minimaxThe rst task is to implement standard minimax search. For each move throughout the search you should print the current player, the possible moves, the number of nodes expanded, the move chosen, and the resulting state of the board. Your output for each move should be of the following form:Current player: OPossible moves: [(1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]Nodes considered: ???Move chosen: (1,0)board:X 0 -0 - -X - -where ??? is an integer value corresponding to the number of nodes expanded. Once a player has won, or the board is full you should print the total number of nodes considered for the search. Your output should be of the form:Total nodes expanded: ???where ??? is the total number of nodes expanded. To complete this task you must use the skeleton code provided (see details below). This code provides an implementation of the board, the game state, and template methods in which you must write your solution. Some of the testing of your solution will be automated and so you must use this template code.For this task you must implement the following method:/** Make the next move, determined using minimax.* Print out information about the search progression.*/public void makeMiniMaxMove() {totalNodesExpanded += levelNodesExpanded;levelNodesExpanded = 0;// Fill in the code here to do the next move using minimax// (with no alpha-beta pruning)// You may introduce additional methods, but you must retain// makeMiniMaxMove as the only method that needs calling from// elsewhere, and you may not introduce additional classes.// You must comment your code to explain what you have done.// Print how many nodes were expanded to find this moveSystem.out.println("Nodes considered: " + levelNodesExpanded);// Print the move itself - YOU SHOULD FILL THIS IN TOOSystem.out.println("Move chosen: " );// E.g.:// System.out.println("Move chosen: " + nextState.moveMade);}You are permitted to introduce additional methods (but not classes), but makeMiniMaxMove() must remain as the method called from elsewhere.Task 2: Minimax with alpha-beta pruningThe second task is to implement minimax search with alpha-beta pruning. Your output should have the same form as for task 1. In other words, for each move throughout the search you should print the current player, the possible moves, the number of nodes expanded, the move chosen, and the resulting state of the board. You should also print the total number of nodes considered for the search.You must again use the skeleton code provided, this time using makeAlphaBetaMove() to implement your solution. As before, you may introduce additional methods (but not classes), but makeAlphaBetaMove() must remain as the method called from elsewhere.Template codeThe template code is available on the module webpage. There are a number of Java les that you should download: Coordinate.java — represents a simple 2-dimensional coordinate TicTacToeBoard.java — simple representation of the board GameState.java — represents a node (game state) for the search TicTacToe.java — the main class implementing minimax and alpha-beta pruningIn your solution the only le that you should edit is TicTacToe.java. The template code is very simply written and the important components are commented. It should be easy to follow if you understand minimax and alpha-beta pruning. Note that although the template code compiles and runs, it will run indenitely.IntroductionThere are two tasks in this coursework: (i) to implement minimax, and (ii) to implement minimax with alpha-beta pruning, for tic-tac-toe (noughts-and-crosses). You should assume a 3 3 board, with two players who take turns to place an “X” or a “O” on the board. The rst player to obtain a horizontal, vertical or diagonal line of 3 “X”s or “O”s is the winner. If the board is full and no line of 3 exists the game is a draw.Task 1: Standard minimaxThe rst task is to implement standard minimax search. For each move throughout the search you should print the current player, the possible moves, the number of nodes expanded, the move chosen, and the resulting state of the board. Your output for each move should be of the following form:Current player: OPossible moves: [(1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]Nodes considered: ???Move chosen: (1,0)board:X 0 -0 - -X - -where ??? is an integer value corresponding to the number of nodes expanded. Once a player has won, or the board is full you should print the total number of nodes considered for the search. Your output should be of the form:Total nodes expanded: ???where ??? is the total number of nodes expanded. To complete this task you must use the skeleton code provided (see details below). This code provides an implementation of the board, the game state, and template methods in which you must write your solution. Some of the testing of your solution will be automated and so you must use this template code.For this task you must implement the following method:/** Make the next move, determined using minimax.* Print out information about the search progression.*/public void makeMiniMaxMove() {totalNodesExpanded += levelNodesExpanded;levelNodesExpanded = 0;// Fill in the code here to do the next move using minimax// (with no alpha-beta pruning)// You may introduce additional methods, but you must retain// makeMiniMaxMove as the only method that needs calling from// elsewhere, and you may not introduce additional classes.// You must comment your code to explain what you have done.// Print how many nodes were expanded to find this moveSystem.out.println("Nodes considered: " + levelNodesExpanded);// Print the move itself - YOU SHOULD FILL THIS IN TOOSystem.out.println("Move chosen: " );// E.g.:// System.out.println("Move chosen: " + nextState.moveMade);}You are permitted to introduce additional methods (but not classes), but makeMiniMaxMove() must remain as the method called from elsewhere.Task 2: Minimax with alpha-beta pruningThe second task is to implement minimax search with alpha-beta pruning. Your output should have the same form as for task 1. In other words, for each move throughout the search you should print the current player, the possible moves, the number of nodes expanded, the move chosen, and the resulting state of the board. You should also print the total number of nodes considered for the search.You must again use the skeleton code provided, this time using makeAlphaBetaMove() to implement your solution. As before, you may introduce additional methods (but not classes), but makeAlphaBetaMove() must remain as the method called from elsewhere.Template codeThe template code is available on the module webpage. There are a number of Java les that you should download: Coordinate.java — represents a simple 2-dimensional coordinate TicTacToeBoard.java — simple representation of the board GameState.java — represents a node (game state) for the search TicTacToe.java — the main class implementing minimax and alpha-beta pruningIn your solution the only le that you should edit is TicTacToe.java. The template code is very simply written and the important components are commented. It should be easy to follow if you understand minimax and alpha-beta pruning. Note that although the template code compiles and runs, it will run indenitely.
