Problem Description

A game called ``Connect 4'' is played by two players, each with a collection of coloured marbles. The goal of the game for each player is to build a line of four of the player's marbles while trying to stop the opponent player from building his/her own. A line can be horizontal, vertical or diagonal.

The game board consists of seven columns and six rows. To make a move, a player needs to select a column. The player's marble will be dropped into the topmost empty row of that column.

The game is won when one of the two players manages to line up four of his/her marbles horizontally, vertically or diagonally. If the board fills up without a win, the game ends in a draw.

Your Tasks:

Develop an AI player to play the Connect 4 game, with a human player, another AI player or even a RANPlayer who simply drops its marbles randomly to the board.

Here is a main program that illustrates how two RANPlayers are playing the game together. You can modify the main function so that your AI player can play against a RANPlayer.

It would be nice if your AI player implements the following interface:

class Player {
    public:
        // get information of the board and the goal number
        Player( int rows = 6, int columns = 7, int goal = 4);

        // return your next move, which column to drop your marble.
        // otherPlayersLastMove will be -1 if you are to move first
        // and this is your first move.
        int move( int otherPlayersLastMove);

        // return your name or what ever you want to call that player
        string getName();
};

Winning the game, while playing against the random player, is only a minor goal you want to achieve. For the game domain knowledge, give your own player's winning state a really high evaluation score, and give your opponent player's winning state a really low evaluation score.

The purpose of the assignment is for you to understand and implement the Minimax algorithm and Alpha-Beta Pruning algorithm in your AI agent to solve this adversarial search problem.

You should implement your AI agent program in such a way that the maximum search depth can be changed easily. While testing, set the search depth to be 3 moves (6-ply).

Provide a Makefile to automate the compilation of your program.

Provide an assignment report (a .txt or .pdf file) that includes at least the following information:

• How to compile and execute your program? If your source code files need to be placed into subfolders in order to use the makefile, explain how the files should be organized.
• Identify the sections of your code that implement the Minimax algorithm and Alpha-Beta Pruning algorithm respectively.
• Explain how your Evaluation function is designed and why.
• Any known bugs;
• Any comment you would like the marker to know.

What and How to Submit

You need to submit the following files for this assignment:

• source code file(s) -- I assume that they are written in C/C++, with the extension name .cpp and .h. And .rs is added already. If you use any other programming language in implementing your program, let me know the extension name(s) of these files before you attempt submitting. And make sure that your program can be compiled and executed on otter. Thanks.
• makefile, if there is one
• assignment report -- it should be either a text file (.txt) or a PDF file (.pdf).

Put all the files you want to submit in one folder on otter, submit them using the following command:
~liuh/bin/submit 485 A3 .

To check what file(s) you have submitted for this assignment, use the following command on otter:
~liuh/bin/checksubmit 485 A3

Alternatively, upload all the files you'd like to submit to VIU Learn, under the CSCI 485/Assessment/Assignment/A3 tab.