Course:CPSC312-2021/Tic-Tac-Toe
Authors: Chris Knee, Alex Caceres-Wright, Peiyan Yang
What is the problem?
We will create a set of rules to model the popular game Tic Tac Toe, where opposing players place their pieces to get three pieces in a row on a 3x3 board. As a logic programming language, Prolog seems suitable for board games such as Tic-Tac-Toe as the idea of such games is to win given a set of rules. Our first goal is to investigate whether this hypothesis is true using this basic game. Next, we will see whether game-tree searching is suitable for Prolog using the environment and rule setup done in the first part.
What is the something extra?
We have implemented a Minimax search algorithm in Prolog that searches ahead until it reaches a terminal state, making it able to play perfectly given any board state. More specifically, we have implemented Negamax, which was partially inspired by the Haskell example shown in class. Alongside this, we have also created a simple user interface that allows others to play against the computer going as X or O.
What did we learn from doing this?
In the end, we were successful in implementing both the Tic-Tac-Toe game and the Minimax algorithm. The nature of Prolog made constructing the game environment trivial as all that was necessary were how a move can get to the next state and at which states the game would end. Most of the difficulty in this project came from the computer player and the UI.
Minimax
Recursion is much less intuitive in Prolog than in other languages like Haskell, which made the argmax function much harder to implement. Fortunately, debugging in Prolog is just as simple given that a complex algorithm can be separated into many smaller functions which can all be individually tested. In the end, we found the process to be very similar to how Minimax is implemented in Haskell, as the core functionality of each helper function is basically the same. Prolog does suffer in generalizability when compared to Haskell, as there would need to have changes to a some of the core functions if another game were to be modelled. While Prolog is definitely weaker that Haskell in some aspects, our algorithm demonstrates a proof of concept idea that tree search algorithms are definitely still viable in Prolog.
UI
As in Haskell, it is apparent that Prolog is not very suited for I/O operations, especially for live environments. Creating a robust input system that would anticipate every possible input is much more difficult than in other languages, and so we had to utilize conditional statements in order to accomplish much of our goal. Most of our code is dependant on the Prolog 'read/1' function, which requires a period after an input. These restrictions makes our interface feel very unnatural and hard to navigate at times. It seems that Prolog is more of a back end language that can be connected with Javascript or another equivalent language to produce a much more robust and intuitive interface.