Description
Introduction
In this assignment you will be implementing two versions of the board game Conne t Four.
The Two Versions of Conne t Four
Conne t Four is a well-known, simple two-player board game, widely marketed for hildren.
The players take turns dropping disks of their assigned olor from the top of a grid. The goal
of game is to onne t four of your own disks horizontally, verti ally or diagonally. A graphi al
illustration of the game is shown in Figure 1. Here the players have the olors yellow and red.
The yellow player is one move away from winning.
The game is played on a variably-sized board (usually 7-by-6, whi h is the value you should
use in this assignment), where, during a player’s turn, he or she may pla e a pie e at the top
and it falls to the bottom, the lowest uno upied square. Alternately, he or she may remove a
disk from the bottom. Removing a disk from the bottom shifts every disk above it down one
position. This hanges the possibilities for a onne tion for both players. A player an only
remove a disk from the bottom if the disk has his or her own olor. The rst player to onstru t
a line of four pie es in a row (either verti al, horizontal, or diagonal) is onsidered to have won
the game. An informative animation of how the game is played, for those who are unfamiliar
with it, is lo ated at its Wikipedia page: https://en.wikipedia.org/wiki/Conne t_Four.
Your task is to implement both versions of the game. In the rst version, the player is not
allowed to remove disks from the bottom. In the se ond version, the player is allowed the
removal option. At the start of the game, the user must be allowed to hoose whi h option the
omputer is required to play!
Figure 1: The board asso iated with Conne t Four.
2
Assignment Ob je tives
Implement MiniMax sear h with Alpha-Beta pruning for Conne t Four.
Implement both the play options.
Ea h option must be implemented with two dierent heuristi s. These heuristi s
may be the same for both the options.
Enable a omputer vs omputer play of the game, where one player uses a heuristi .
While this player uses the heuristi , the other one plays random moves.
Provide a way to bound the depth of the sear h.
Code your assignment in su h a way as to be able to show every move being made in both
of the games.
Questions
During the demo you should be prepared to dis uss the following questions:
Explain the heuristi s you used for the game(s).
Does one player always win?
Tips
Don’t spend too mu h time on the graphi s. Command-line based graphi s is ne.
Bonus
Can you think of a way to improve the number of nodes pruned with Alpha-Beta pruning in
Conne t Four?
3