Programming Assignment #3:  Connect-4 in Prolog
Due Date: Tuesday April 24 (Class)

Instructions:
This assignment consists of designing and implementing a Prolog program that plays Connect 4. Your solution should follow the techniques presented in the section 11.3.1 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 implementation on the web. For instance
http://www.thisiswalsall.co.uk/games/connect4.htm
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 10 bonus points, you must implements 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 10 bonus points. If you are really going strong, and want to make your program even harder to beat, 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.psy.uva.nl/projects/SWI-Prolog/Manual/Contents.html
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 single .zip file attached to it. This file should have the following content:
• Full source code.
• A clear description of the process I should follow to run the program.
• 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,...).
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.33.
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.