Programming Assignment #3:  Connect-4 in Prolog
Due Date: Thursday, April 23 at 12PM

Instructions:
This assignment consists of designing and implementing a Prolog program that plays Connect 4. Your solution should follow the techniques presented in the sections 11.2.5, 11.2.7 of the textbook (i.e. the tic-tac-toe example). The game is described at:
http://www.ce.unipr.it/~gbe/cn4rules.html
You can gain a better understanding of the game by playing against one of the many Java implementations on the web. For instance
http://www.mathsisfun.com/games/connect4.html
You have to implement a basic program:
1. A naive interactive program with a simple strategy: block any winning move and win whenever possible. Your program should be interactive (i.e. implement a main goal play). The user should be able to choose its color (e.g. yellow (O), that starts first, or red (X) to go second). The program must also print the board in text-mode after each move (use X for red and O for yellow). For instance
A B C D E F G
6 - - - - - - -
5 - - - - - - -
4 - - - X - - -
3 - - - O O - -
2 - - - X X O -
1 - - O X O X X
2. For 5 bonus points, implement the minimax algorithm (see the hints section for more details). This program (play2) must also be interactive, and the user should be allowed to set the depth parameter that measures the strength of the computer play.
3. For an additional 5 bonus points. If you are really going strong, and want to make your program even better, try extending the minimax algorithm with alpha-beta pruning (see Hints section).
Hints and Additional Reference
The SWI-Prolog's reference manual is an excellent resource that documents every available feature. You can find it at:
http://www.swi-prolog.org/pldoc/refman/
The minimax algorithm and the alpha-beta pruning technique are described at:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic11/
FAQ from Spring 2002 offering of this course:
http://www.cs.unc.edu/Courses/comp144-s02/assignments/4/faq.html

Submission
You should email me your programs as a single zip file attached to it. Title the email "COMP524 Program3". The zip file should have the following content:
• Full source code, well-commented.
• A short overview of your solution that describes the design of the programs and the extend to what you have solved each section. Important: You should motivate your design in order to get full credit (e.g., board representation, scoring function for minimax if doing bonus,...).
I will compile the program using SWI-Prolog (see http://www.swi-prolog.org) only. You can develop you program with any Prolog programming environment, but you must make sure it compiles and runs under SWI-Prolog 5.6.64.
Grading
I will grade both the quality of the source code (design and documentation) and the output. Collaboration is encouraged, but you cannot share source code. Honor Code applies to this program. Please read
http://www.cs.unc.edu/Admin/Courses/HonorCode.html
for more details.