# Learning Haskell with Chess

### From HaskellWiki

(Difference between revisions)

GetcoGetla (Talk | contribs) (ouletorelc) |
|||

(12 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

− | 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]. |
+ | olodom |

+ | [[Category:Education]] |
||

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

− | <h1>Exercise 1 - Data Types</h1> |
+ | @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. |

− | <h2>Learning Targets</h2> |
+ | ==Exercise 1 - data types== |

− | <ul> |
||

− | <li>recapitulate Haskell types (keywords type and data, product and sum types)</li> |
||

− | <li>Helium: define equality functions (pattern matching)</li> |
||

− | <li>pretty printing</li> |
||

− | </ul> |
||

− | <h2>Tasks</h2> |
+ | ===Learning targets=== |

− | <ul> |
+ | *recapitulate Haskell types (keywords <hask>type</hask> and <hask>data</hask>, product and sum types) |

− | <li>Define data types that represent boards (Board), squares (Square), positions (Pos), pieces (Piece) and game states (State).</li> |
+ | **Helium: equality and show functions (pattern matching) |

− | <li>Helium: Implement suited eq-functions.</li> |
+ | **Haskell: type classes (<hask>Show</hask>, <hask>Eq</hask>, <hask>deriving</hask>) |

− | <li>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, ...</li> |
+ | *list handling (boards will be represented by lists of lists) |

− | <li>Define the initial board (initialBoard::Board), test prettyBoard with initialBoard.</li> |
+ | *special character <hask>'\n'</hask>, <hask>putStr::String->IO ()</hask> |

− | <li>Implement a simple evaluation function evalBoard::Board->Int as the difference of material on board (values: Pawn->1, Knight and Bishop->3, Queen->9, Rook->6, King->"infinity"=1000).</li> |
||

− | </ul> |
||

− | <h1>Exercise 2 - Move Generator</h1> |
+ | ===Tasks=== |

− | <h2>Learning Targets</h2> |
+ | *Define data types that represent boards (<hask>Board</hask>), squares (<hask>Square</hask>), positions (<hask>Pos</hask>), pieces (<hask>Piece</hask>, supported by <hask>PieceColor</hask> and <hask>PieceType</hask>) and game states (<hask>State</hask>). |

− | <ul> |
+ | **Helium: Implement suited eq and show functions. |

− | <li>list comprehension</li> |
+ | **Haskell: Define/derive instances of <hask>Show</hask> and <hask>Eq</hask> |

− | <li>stepwise refinement</li> |
+ | *Implement a function <hask>prettyBoard::Board->String</hask>, that transforms a board into a clearly arranged string representation (human readable :-)). Support this function with auxiliary functions that pretty print pieces, squares, ... |

− | </ul> |
+ | *Define the initial board (<hask>initialBoard::Board</hask>), test <hask>prettyBoard</hask> with <hask>initialBoard</hask>. |

− | <h2>Tasks</h2> |
+ | *Implement a simple evaluation function <hask>evalBoard::Board->Int</hask> as the difference of material on board, for this purpose define a function <hask>valuePiece</hask> that maps pieces to their values (pawn->1, knight and bishop->3, queen->9, rook->5, king->"infinity"=1000). |

− | <h1>Exercise 3 - Gametree Generation and Minimax Algorithm</h1> |
+ | ==Exercise 2 - move generator== |

− | <h2>Learning Targets</h2> |
+ | ===Learning targets=== |

− | <ul> |
+ | *list comprehension |

− | <li>break code in modules</li> |
+ | *stepwise refinement |

− | <li>complexity</li> |
+ | ===Tasks=== |

− | <li>recursive data structures -> recursive algorithms</li> |
+ | *Define a function <hask>movePos::Pos->Pos->Board->Board</hask> such that <hask>movePos p1 p2 b</hask> moves the piece at p1 to p2 (overwrite the square at p2 with the square at p1 and delete p1). Do not check whether the move is valid at this stage. Hint: Define a function <hask>updateBoard</hask> first. On top of this further define a function <hask>deleteSquare</hask>. Its much simpler to have these functions at hand. |

− | </ul> |
+ | *Implement a function <hask>colorPos::PieceColor->Board->[Pos]</hask> whose result is the list of the positions of the pieces of a certain color. |

− | <h2>Tasks</h2> |
+ | *Define <hask>moves::PieceType->[(Int,Int)]</hask> that returns the base moving vectors for a particular piece (return empty list for pawns here, because their vector depends on the color). |

− | <ul> |
+ | *Implement <hask>genMoves::Board->Pos->[Board]</hask>, it takes a board b and a position p and results in the list of all boards that may follow if you move the piece at p on board b. |

− | <li>Define a data type that represents a game tree (GameTree).</li> |
+ | *Combine <hask>colorPos</hask> and <hask>genMoves</hask> to a function <hask>nextStates::State->[State]</hask> that returns all possible successor states. |

− | <li>Roughly estimate the number of nodes of the gametree with depth 4.</li> |
+ | |

− | <li>Define a function play::Gametree->Int, that computes the value of a given game tree using the minimax Algorithm.</li> |
+ | ==Exercise 3 - gametree generation and minimax algorithm== |

− | <li>Implement the function doMove::State->State, that choses the (best) next state.</li> |
+ | ===Learning targets=== |

− | </ul> |
+ | *break code in modules |

+ | *complexity |
||

+ | *recursive data structures -> recursive algorithms |
||

+ | |||

+ | ===Tasks=== |
||

+ | *Define a data type that represents a game tree (<hask>GameTree</hask>). |
||

+ | *Roughly estimate the number of nodes of the gametree with depth 4. |
||

+ | *Define a function <hask>play::Gametree->Int</hask>, that computes the value of a given game tree using the minimax Algorithm. |
||

+ | *Implement the function <hask>doMove::State->State</hask>, that choses the (best) next state. |

## Latest revision as of 22:54, 5 October 2008

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

## Contents |

## [edit] 1 Exercise 1 - data types

### [edit] 1.1 Learning targets

- recapitulate Haskell types (keywords andtype, product and sum types)data
- Helium: equality and show functions (pattern matching)
- Haskell: type classes (,Show,Eq)deriving

- list handling (boards will be represented by lists of lists)
- special character ,'\n'putStr::String->IO ()

### [edit] 1.2 Tasks

- Define data types that represent boards (), squares (Board), positions (Square), pieces (Pos, supported byPieceandPieceColor) and game states (PieceType).State
- Helium: Implement suited eq and show functions.
- Haskell: Define/derive instances of andShowEq

- Implement a function , that transforms a board into a clearly arranged string representation (human readable :-)). Support this function with auxiliary functions that pretty print pieces, squares, ...prettyBoard::Board->String
- Define the initial board (), testinitialBoard::BoardwithprettyBoard.initialBoard
- Implement a simple evaluation function as the difference of material on board, for this purpose define a functionevalBoard::Board->Intthat maps pieces to their values (pawn->1, knight and bishop->3, queen->9, rook->5, king->"infinity"=1000).valuePiece

## [edit] 2 Exercise 2 - move generator

### [edit] 2.1 Learning targets

- list comprehension
- stepwise refinement

### [edit] 2.2 Tasks

- Define a function such thatmovePos::Pos->Pos->Board->Boardmoves the piece at p1 to p2 (overwrite the square at p2 with the square at p1 and delete p1). Do not check whether the move is valid at this stage. Hint: Define a functionmovePos p1 p2 bfirst. On top of this further define a functionupdateBoard. Its much simpler to have these functions at hand.deleteSquare
- Implement a function whose result is the list of the positions of the pieces of a certain color.colorPos::PieceColor->Board->[Pos]
- Define that returns the base moving vectors for a particular piece (return empty list for pawns here, because their vector depends on the color).moves::PieceType->[(Int,Int)]
- Implement , it takes a board b and a position p and results in the list of all boards that may follow if you move the piece at p on board b.genMoves::Board->Pos->[Board]
- Combine andcolorPosto a functiongenMovesthat returns all possible successor states.nextStates::State->[State]

## [edit] 3 Exercise 3 - gametree generation and minimax algorithm

### [edit] 3.1 Learning targets

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

### [edit] 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 , that computes the value of a given game tree using the minimax Algorithm.play::Gametree->Int
- Implement the function , that choses the (best) next state.doMove::State->State