[Haskell-beginners] Simple Chess Program for Learning FP

Daniel Fischer daniel.is.fischer at web.de
Tue Jun 1 15:04:21 EDT 2010


On Tuesday 01 June 2010 20:01:48, Jordan Cooper wrote:
> FP newbie here,
>
> I'd like to start learning how to program more purely. Immutability is
> something that tends to confuse me when it comes to handling state,
> and I figure the only way I'll understand is if I do it myself.

If you don't want to pass the state around explicitly (and that gets 
tiresome rather soon), you can hide it from view using a State monad. 
Depending on what you do, that could be either the simple

Control.Monad.State[.Strict].State

or, if you need the functionality of other monads,

Control.Monad.State[.Strict].StateT

Using monad transformers (generally, types ending with a capital T) is, 
however, often less than obvious to beginners, so it might be a good idea 
to not dive in at the deep end, but rather to acclimatise oneself in the 
shallower waters first.
A good way to get used to State is writing yet another parser combinator 
library (look e.g. at the API docs for parsec to see what combinators to 
implement -- you don't need to write them all, you'll learn how to use 
State before that).

>
> In the past I coded a little chess game in C, where two computers
> played each other (not well, but they made legal moves). I figured
> this might be good to try and accomplish the same thing in Haskell.
>
> Any general advice before I embark would be appreciated, though my
> main question has to do with data structures. In C I used a
> two-dimensional array to represent the board (I realize there are more
> efficient representations, but I'm aiming for understanding over
> performance).

If performance isn't important, you can also use a two-dimensional array
(Data.Array; Array (Int,Int) (Maybe Piece) for example) in Haskell.
Actually, immutable arrays in Haskell are surprisingly snappy (at least if 
you compile with optimisations).

Another option is using Data.Map and representing the gamestate as a Map 
from positions to pieces.

> I'm not sure what the natural functional equivalent
> would be, seeing as how arrays are immutable.

There are also mutable arrays,
Data.Array.ST
and
Data.Array.IO
with the common interface
Data.Array.MArray

If you use STUArrays or IOUArrays, you can get very fast code, but it's 
better to come to close terms with declarative functional programming 
before learning how to write "almost C" in Haskell (your "almost C" will 
look far less ugly then).

>
> Tips appreciated!

Hmm,

you'll probably need

-- GameState : whose turn, which piece where
-- Move : which piece, from where, to which square

evaluatePosition :: GameState -> Value
-- Value could be Int or something else as long as it's comparable
-- this is the really hard part

chooseMove :: GameState -> Move
-- for all legal moves, evaluate the position if that move were made
-- choose the most promising one
-- if you try to implement an elaborate strategy, that'll be hard too,
-- you'll need to figure out which branches to cut off early and when
-- to stop looking further
-- You'll probably want to add a pseudo-random generator to choose
-- a move when there's no clear favourite

makeMove :: Move -> GameState -> GameState
   

>
> Thanks,
> J


More information about the Beginners mailing list