Course:CPSC312-2017-Connect Four

Connect Four

Authors: Chris, Patience

https://github.com/csatterfield/connect_four

What is the problem?

State the general problem. If applicable, tell us what information you will use, e.g., a link to some website that provides the information you used. What will you do?"

We will use Prolog to build a program that can play Connect Four against a human opponent. There are many variations of the game, but we will consider the traditional gameplay, and the rules are as follows:

Two players alternate dropping disks from the top of a vertical, 7-column by 6-row grid. The disks fall into the bottommost available space in that column. Whoever is the first to form a vertical, horizontal or diagonal line of his/her own disks wins.

Here is a description of the rules: https://en.wikipedia.org/wiki/Connect_Four

What is the something extra?

What is the in-depth aspect you will do? If the problem is related to some other group's project, tell us how they fit together. If in doubt, include the information."

We implemented a simple command-line based interface to accept user input and render the state of the game. In addition, we created a simple AI which utilizes the Negamax algorithm in order to select the best move (or close to it, as it is very computationally demanding to select the best) at each step.

What did we learn from doing this?

(This should be written after you have done the work.) What is the bottom-line? Is logic programming suitable for (part-of) the task? Make sure you include the evidence for your claims.

Logic programming is definitely suitable for making games with basic rules like connect four. Defining the rules of the game was easy, and we were able to create a playable version quickly.

However, Prolog's implementation of lists causes simple operations like replacing an element inside a matrix to become very expensive. This overhead was not noticeable in user vs user games, but became relevant when designing the AI since it must make many such operations for each turn. This forced us to limit the depth at which the AI considers possible moves, or else the game would be unplayably slow. Implementing the Negamax algorithm in Prolog proved to be a challenge due to the recursive nature of the language. This caused what could have been a few lines of code in another language to become needlessly complicated. For these reasons, we do not believe that Prolog is not an appropriate tool for creating an AI (at least for connect four).