From UBC Wiki

Authors: Kavya, Linda

What is the problem?

We'll be implementing a fully functional version of Tic-Tac-Toe, where there are two versions.

version 1: traditional two player tic tac toe. This lets user play against another user.

version 2: player vs computer. This lets a solo player go against our smart computer algorithm.

What is the something extra?

  • The "player vs computer" mode is implemented with our own version of the minimax algorithm. Our minimax algorithm pre-asses each possible move the computer can make based on the current state of the game, (and the possible successive states after an opponent has already played), and assigns an appropriate value to each potential move. It then chooses the best move based on likelihood of winning the game. With our version of minimax, the computer is guaranteed to always win or (worst case) tie with the human player.
  • Additionally, we also implemented a GUI using the gloss library for the two player version. Starting player is X (in red), second player is O (in blue), and if O wins then the board turns blue and if X wins the board turns red. If there is a tie, a single grey color is placed on the board. Clicking on the board after the game is finished restarts.

What did we learn from doing this?

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

What we learned from implementing minimax:

We learned that there are multiple ways to implement the minimax algorithm (there is no 'standard' way)! Some versions make the algorithm choose a move based on the assumption that the opponent will make the best possible move, and others asses the possibilities of the opponent making the best move and the cases where they choose the worst moves as well. Just a simple search of minimax algorithms with different games will prove this fact. Also, the fact that there were so many different ways we could implement this, with many different techniques, was challenging. We chose to implement using the latter method, since it exhausts all possible cases the opponent can make.

What we learned from implementing GUI:

The GUI was arguably the most challenging part of the entire program, even for something as simple as a tic-tac-toe board. I found that the haskell documentation + gloss library in general is not the most intuitive. There also aren't extensive resources out there available to learn GUI for Haskell. However, implementing the GUI taught me how to transform mouse click events to the an executable function, make a program more interactive, and how to render certain shapes/images with limited resources and think more creatively. For example, to implement an X image, there was nothing in the library that could render an X (there was one for O / thick circles), so we used two lines that intersected at 45 and -45 degrees.

Was functional programming suitable for the task?

Functional programming was suitable for the task, because it made abstraction and debugging a lot easier. Due to the immutable nature of functional programming languages, I knew that each variable in the program belonged to a very specific value, and if there was any error I could easily test the variables and determine whether or not there was a problem in the values. Furthermore, I encountered a lot of type errors, and the strong-typed nature of Haskell made it easy to identify these type errors and resolve them.

Links to code etc

Office Hours:
Class Schedule:
Important Course Pages
Lecture Notes
Course Discussion

[1] Click here for the github repository!