COMP 4106代做、代写Intelligen e留学生、代做python，Java，c/c++编程语言

日期：2019-03-02 09:56

COMP 4106 - Artifi

ial Intelligen

e

Winter 2019

Assignment #2

Due date: Mar

h 12, 2019

Game Playing with MiniMax

Introdu

tion

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: http://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 different 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?