COMP 144 Programming Language Concepts
Spring 2004

Assignment 6:
Connect-4 in Prolog

Due Date: Monday April 19

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://members.aol.com/shadows125/connect4.htm

You have to implement a basic program for a B grade:

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
```
For an "A" grade 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.
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/

Submission

This assignment is due on Monday April 19th at class time. Late assignments get 1% off each hour they are late (i.e. they will receive no credit after 100 hours). There will be no extension this time, so plan ahead! Your submission will be electronic. Your electronic submission will be an e-mail sent to luebke@cs.unc.edu with the subject

COMP 144 Assignment 6 Submission

and a 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.0.1.

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.