Learning Haskell with Chess

This page is about learning Haskell using the board game Chess as a running example. The complete code can be found at http://www.steffen-mazanek.de/dateien/projekte/hsChess.zip.

@German Haskellers: You may also have a look at the tex-files used for our student exercises, http://www.steffen-mazanek.de/dateien/projekte/hsChess-teaching-german.zip.

Exercise 1 - data types

Learning targets

• recapitulate Haskell types (keywords type and data, product and sum types)
  • Helium: equality and show functions (pattern matching)
  • Haskell: type classes (Show, Eq, deriving)
• list handling (boards will be represented by lists of lists)

Tasks

• Define data types that represent boards (Board), squares (Square), positions (Pos), pieces (Piece, supported by PieceColor and PieceType) and game states (State).
  • Helium: Implement suited eq and show functions.
  • Haskell: Define/derive instances of Show and Eq
• Implement a function prettyBoard::Board->String, that transforms a board into a clearly arranged string representation (human readable :-)). Support this function with auxiliary functions that pretty print pieces, squares, ...
• Define the initial board (initialBoard::Board), test prettyBoard with initialBoard.
• Implement a simple evaluation function evalBoard::Board->Int as the difference of material on board, for this purpose define a function valuePiece that maps pieces to their values (pawn->1, knight and bishop->3, queen->9, rook->5, king->"infinity"=1000).

Exercise 2 - move generator

Learning targets

• list comprehension
• stepwise refinement

Exercise 3 - gametree generation and minimax algorithm

Learning targets

• break code in modules
• complexity
• recursive data structures -> recursive algorithms

Tasks

• Define a data type that represents a game tree (GameTree).
• Roughly estimate the number of nodes of the gametree with depth 4.
• Define a function play::Gametree->Int, that computes the value of a given game tree using the minimax Algorithm.
• Implement the function doMove::State->State, that choses the (best) next state.