Course:CPSC312-2021/connect4prolog

From UBC Wiki

Connect 4

Authors: Vandy Liu, Eric Jang

What is the problem?

The problem we are trying to tackle is how feasible is using prolog to create games. We already tried to tackle this with Haskell and quite a bit of success, so we wanted to see how far we could take the powers of Prolog. We've decided to tackle this problem by trying to code the game connect four in Prolog. Connect four is a two player game, where both players take turns making moves and try to have four markers in a row horizontally, vertically or diagonally. The board is 7 (wide) by 6 (high). The red player goes first and the yellow player goes second. A player can place their piece in any of the 7 columns, and the marker falls down to the first available spot (usually by gravity) as long as the column is not filled up. The first player to have four markers in a row wins the game. If all the spots on the board are filled and no one has won yet, then it is a draw. More on the game can be seen here: https://en.wikipedia.org/wiki/Connect_Four.

What is the something extra?

We will be implementing various different CPU algorithms ranging in strength. We made a simple player that always plays a predetermined list of actions no matter what, a random player who plays randomly, a normally-distributed player that plays moves along a normal distribution where the mean move is column 4 (middle column). We also added more complicated algorithms: Monte-Carlo tree search algorithm and Mini-Max algorithm with alpha-beta pruning. Both of which are very strong and will give you a run for your money!

What did we learn from doing this?

Firstly, many elements of our Haskell flow and thought process helped make the programming easier because we already had practice thinking in a functional way. That is one of the most important things we learned that thinking of programming from a higher level can make implementing things a lot easier. In the beginning, it was a little difficult but once we realized the importance of accumulators, writing the functions became easier. We also learned many tricks in Prolog like the use of -> for if-then statements and \+ for negations. Back to our problem: We believe that Prolog can be suited to create games depending on the simplicity of the game. We really wanted to test out how far we could take Prolog's functionality and coding this connect4 game worked quite well. We even implemented algorithms that are strong enough to beat most human players with just a few lines of code, which really shows off Prolog's powers. It may be tougher for games with a lot of state changes and actions happening at once though. We also believe that coding games in Prolog is easier to test because you always get deterministic results from the tests and it makes it a lot easier to debug code as opposed to OOP where there may be bugs that depend on state.

Links to code, etc

https://github.com/vandyliu/connect4-prolog