From UBC Wiki

Chess with AI Player

Authors: Aziz Sonawalla, Yiyi Liu, Cynthia Zhou

What is the problem?

To build a Chess engine in Haskell and an efficient AI opponent so that users can play against the computer using a command-line interface. The Chess engine will setup the game between the human player and the AI, as well as enforce the rules of the game (eg. which pieces can move where). The human player will be shown an ASCII text chessboard and can make moves using algebraic notation (eg. d2 to d4).

What is the something extra?

The AI player will leverage the Min-max algorithm used by Deep Blue in 1997 (albeit a simpler version) and test how deep the AI player can traverse the game tree efficiently between moves.

What did we learn from doing this?

There are primarily two things we learnt from programming this project in Haskell:

The first is that the functional nature of Haskell makes it extremely easy to concisely represent a rules-based game like Chess in the language. For example, we were able to enforce the rules around how the King can move by simply writing them out as a series of cases. This is a far more concise way of writing the engine compared to an Object-oriented language where the King would be a subclass of the type ChessPiece and it would require several methods to achieve the same goal.

Secondly, Haskell proved to be extremely efficient (computationally) for both the Chess engine and the AI opponent. Without any caching or pruning, the AI opponent was able to build an analyze a game tree of depth 4 under 3 seconds - short enough to be able to integrate it seamlessly into the game without significant delays. For reference, Deep Blue usually searched a depth of 6-8 moves. While we aren't sure if this efficiency should be credited to the fact that Haskell compiles to low-level C/assembly or the fact that it uses lazy evaluation, it is a significant asset in designing a computationally intense project such as this.

One downside that we experienced while developing this project is that Haskell specifically has a fairly immature development environment. It is extremely tedious to setup, code and test large projects with multiple dependencies, and the GHC compiler slows down significantly as more dependencies are added. Repl servers used for code analysis and suggestions within IDEs constantly crashed and thus most of the time we were coding blind.

Links to code etc