Personal tools

Learning Haskell with Chess

From HaskellWiki

Revision as of 08:39, 19 March 2007 by Smazanek (Talk | contribs)

Jump to: navigation, search

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.

Contents

1 Exercise 1 - data types

1.1 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)

1.2 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).

2 Exercise 2 - move generator

2.1 Learning targets

  • list comprehension
  • stepwise refinement

2.2 Tasks

3 Exercise 3 - gametree generation and minimax algorithm

3.1 Learning targets

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

3.2 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.