Invasion Game - Artificial Intelligence

Alice and Bob are playing a game with the following setting and rules: There is an N*M grid which represents a kingdom which is being invaded by the players. Each cell of the grid is either 1 or 0 where 1 denotes that there is land on this cell, while 0 denotes water. In one turn, a player can capture a cell which has land, given that the cell has not been captured before. If this cell shares a side with other uncaptured cells of land, the player can take these in the same turn as well. A cell once captured by a player cannot be captured again by another player. The game ends when all cells having land have been captured. The player who has the most number of land cells wins. If Alice plays the first turn, and both players play optimally, find the maximum number of cells of land that Bob can capture. Example: Input: 4 4 #N,M 1001 0110 0110 1001 Output: 2 Note: The code will be tested against multiple inputs for marking. Hence, write a clean function to read the input format and display the output. Though Adverserial search is the best fit for this problem, instead design the next best suited uninformed search technique for this. 1. Explain the environment of the player agent in the game [20% weightage] 2. Explain the algorithm you will use for the solution and argue its correctness [20% weightage] 3. Implement the solution using traversal/search to make the best choice for each player at each stage [30% weightage] 4. Using pseudocode notation for your solution, outline the space and time complexity of the solution with appropriate explanation [15% weightage] 5. Code’s correctness with other unseen test cases (during correction) [15% weightage] Please note that marks will be deducted for not writing code which takes in the input in a specific format (given in the adjoining notebook) properly and displays the required output. Submission guidelines: ● You are provided with the python notebook template which stipulates the structure of code and documentation. Use well indented python code. ● The implementation code must be completely original and executable. ● Please keep your work (code, documentation) confidential. If your code is found to be plagiarized, you will be penalized severely. Parties involved in the copy will be considered equal partners and will be penalized severely Topics 1. Uninformed search 2. Informed Search 3. Local search justification of algorithms word document: This should have justification towards the choices of algorithm/data structures/heuristic/fitness function wherever appropriate written in your own words. A screenshot of the output should be appended in the document and the code execution too.