COMPSCI 383 – Fall 2020 Homework 2 Phase 1 (Minimax) due Wednesday, September 30th at 11:59pm ET Phase 2 (Evaluation & Alpha-Beta) due Wednesday, October 7th at 11:59pm ET You are encouraged to discuss the assignment in general with your classmates, and may optionally collaborate with one other student. If you choose to do so, you must indicate with whom you worked. Multiple teams (or non-partnered students) submitting the same code will be considered plagiarism. Code must be written in a reasonably current version of Python (>3.0), and be executable from a Unix command line. You are free to use Python’s standard modules for data structures and utilities, as well as the pandas, scipy, and numpy modules. Do not use any modules or libraries that implement Minimax or Alpha-Beta pruning. Greetings, Professor Falken. Shall we play a game? For this assignment, you will implement a game playing agent for a modified version of “Connect 4”, a vertical tic-tac-toe-like game. Your agent will be able to play against humans or other automated agents, and we will pit them against each other in a class-wide tournament. Classic Connect 4 In the basic game, the board is made up of six rows and seven columns, which are filled with tokens. Players take turns dropping tokens into vertical columns until one player has 4-in-a-row (vertically, horizontally, or diagonally) or the board is full. The board shown on the right illustrates a game in progress after the following five moves have been made: Player 1 to column 1 Player 2 to column 3 Player 1 to column 3 Player 2 to column 3 Player 1 to column 5 You can play an online version here.Connect 383 In our version of the game, we will not be limited to 6x7 boards. Furthermore, play will always continue until the board is completely full (even after a player has achieved 4-in-a-row), at which point scores for each player will be calculated. The player with the highest score wins. Points will be awarded as follows: for each run of length three or greater, the player will receive points equal to the square of the length of that run. For example, 3-in-a-row is worth 9 points, 4-in-a-row 16, 5-in-a-row 25, etc. For the 4x4 board on the left, Player 1 scores 18 points (one vertical and one horizontal 3-in-a-row), while Player 2 receives 25 points (one vertical 3-in-a-row and one diagonal 4-in-a-row). When calculating the value of different moves, your game-playing agent will use the scores as utility values for the terminal games states, and seek to maximize its reward. This assignment is divided into two phases, with two different due dates. For Phase 1, you will be required to program a working agent that uses the Minimax algorithm to calculate an optimal move from a given game state. In Phase 2, you will add a heuristic evaluation function to evaluate game states along with alpha-beta pruning. Phase 1 (due 9/30) Step 0: Running the Game We’ve created a Python module that will handle representing the game state and manage play called connect383.py. You do not need to change any of the code in this file, but will need to understand how it works to program your game playing agent. To play a game, you run connect383.py from a command line (or within an IDE) and supply it with arguments that determine the parameters of the game and which type of agents are playing. The required arguments are, in order: player1 – one of {‘r’, ‘h’, ‘c’, or ‘p’} specifying the agent type (see code for details) player2 – one of {‘r’, ‘h’, ‘c’, or ‘p’}rows – the number of rows in the board columns – the number of columns in the board For example, to play against a random computer agent on a 4x5 board, you would type: > python connect383.py r h 4 5 Try playing to make sure you understand the game – later, you’ll replace the r with a c if you want to play against your bot. Step 1: Implement Minimax Once you’re comfortable running the game, it’s time to implement your computer agent. The agents.py file contains code for different agent types, each defined by a class. Your task at this step is to implement the minimax() method for the MinimaxAgent class. Given a game state, minimax() should recursively traverse the game tree, eventually determining the value of that state for use in the get_move() method. The utility of the terminal states is calculated using the GameState.score() method, with positive numbers corresponding to Player 1 outscoring Player 2, and negative numbers for Player 2 winning. Note that for the time being, you can ignore the depth parameter in minimax(), as you don’t need to think about that until Phase 2. Step 2. Testing Your Minimax Code To facilitate debugging and allow you test your code for correctness, you can optionally supply a starting game state when you invoke connect383.py. To do this, you must supply an additional command line argument, using the --board flag. The value of that argument must match one of the keys of the boards dictionary defined in test_boards.py. For example, to start the game with a state labeled “awesome”: > python connect383.py c h 4 5 --board awesome Note that when you use this option, the dimensions of the board you pass in will be ignored and set to those found in the test case. Finally, assuming you don’t have a quantum supercomputer at your disposal, you will not be able to run Minimax on a full-sized (6x7) or larger board, as the game tree will be much too big (over 13 decillion game states). Instead, you should test your Minimax on much smaller boards, where you can easily calculate the value of the state by hand and verify correctness.Phase 2 (due 10/7) Step 3: Create an Evaluation Heuristic In order to be able to play on larger boards, your computer agent must be able to invoke a heuristic evaluation function when Minimax reaches a certain depth limit. The code for this should be put in HeuristicAgent.evaluation() and get called by HeuristicAgent.minimax_depth()in accordance with the depth parameter. Note that if depth is set to None, this agent should behave identically to the MinimaxAgent. The evaluation will contain the “brains” of your Connect 383 bot, and the quality of your utility estimation is what will differentiate your agent