Assignment 2
Due Date: Thursday, October 13
Adversarial Search for the Dots and Boxes Game
In this assignment you will implement the minimax and alpha-beta pruning algorihtms to play the Dots and Boxes game against an agent.
Dots and Boxes is a pencil-and-paper game for two players (sometimes more). Starting with an empty grid of dots, two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. The player who completes the fourth side of a 1×1 box claims that box and earns one point, then takes another turn. (A point is typically recorded by placing a mark that identifies the player in the box, such as an initial.) The game ends when no more lines can be placed. The winner is the player with the most points. The board may be of any size.
For more details on the game please be sure to review the PowerPoint Slides for Assignment 2.
Description
The game you implement will be slightly different than the traditional dots-and-boxes.
-
A player will **not** move again after completing a box. Instead the players take turns.
-
When the game board is generated each box will be given a random value between 1 and 5. When a player completes a box, her score will increase by the value of the box.
-
A player’s final score will be the sum of the values of the boxes claimed.
The AI will rely on the minimax algorithm to choose which dots to connect at each step.
-
When the game starts the human player will specify:
- The size of the board;
- How many plys the AI will search (i.e., the horizon for the minimax). -
Use the following scoring function to evaluate the leaves of the tree:
score(AI) – score(Human) -
Use alpha-beta pruning to allow the AI to search deeper into the tree by pruning unnecessary branches.
What to Submit:
- Code [60 points]
- 5 Minute Video [20 points]
- Write up [20 points]
For more details on specific deliverables and additional notes about the assignment, please carefully review the PowerPoint Slides for Assignment 2.