Simple Chess Program for Learning FP
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. 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). I'm not sure what the natural functional equivalent would be, seeing as how arrays are immutable. Tips appreciated! Thanks, J
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
Daniel Fischer wrote:
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. There are also mutable arrays,
A chess board is only 8x8, so depending on your algorithms, a simple 2 dimensional list might be the fastest: [[Maybe Piece]] That also allows you to write simple, beautiful functional code, using the wide selection of list functions available in the Prelude and Data.List. If you choose a map from positions to pieces, it might turn out to be just about as fast to use a simple association list [(Int, Int), Maybe Piece] instead of all the machinery of Data.Map.Map (Int, Int) (Maybe Piece) A chess board has only 64 locations. Regards, Yitz Regards, Yitz
On 6/1/10, Yitzchak Gale
Daniel Fischer wrote:
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. There are also mutable arrays,
A chess board is only 8x8, so depending on your algorithms, a simple 2 dimensional list might be the fastest:
[[Maybe Piece]]
That also allows you to write simple, beautiful functional code, using the wide selection of list functions available in the Prelude and Data.List.
If you choose a map from positions to pieces, it might turn out to be just about as fast to use a simple association list
[(Int, Int), Maybe Piece]
instead of all the machinery of Data.Map.Map (Int, Int) (Maybe Piece) A chess board has only 64 locations.
Regards, Yitz
Regards, Yitz _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
Thank you, Daniel and Yitzchak! I think that will be enough to get me started. As a general question, at what number of elements does it become impractical to use Lists?
On Tue, Jun 01, 2010 at 01:54:38PM -0700, Jordan Cooper wrote:
Thank you, Daniel and Yitzchak! I think that will be enough to get me started. As a general question, at what number of elements does it become impractical to use Lists?
It's really not a question of number of elements, but of how you use the lists. If you are doing stream-processing sorts of things, you can even idiomatically and efficiently use lists that are infinitely long! What lists are not good for is things where you need to do lots of indexing, since indexing into a list requires first traversing the beginning of the list. However for small lists like 8-element lists, it really doesn't make much of a difference. You might now ask: well, suppose I need to do indexing; at what number of elements does it become impractical to use lists? The answer is: it depends, probably somewhere between 10 and 1 million. Use lists, and if it's too slow, you can switch later. -Brent
On Tuesday 01 June 2010 22:54:38, Jordan Cooper wrote:
Thank you, Daniel and Yitzchak! I think that will be enough to get me started. As a general question, at what number of elements does it become impractical to use Lists?
That utterly depends on what you're doing and how important performance is. If performance is *very* important, you can write faster code already to replace very short lists. That code will be far far longer and far far uglier than list-using code, though. We have a great number of very nice functions for manipulating lists, that makes writing list-using code nice easy and fast. If you use other data structures (where lists are a natural choice), the code and coding tends to be less pleasant. And most of the time, not so very much faster. Haskell implementations (well, certainly GHC and hugs, haven't tried others much) are pretty good with lists. If you consume your lists in the order they are produced, lists of several million elements can have nice performance. If your use-pattern isn't so good, lists of a few hundred elements can give really stinking performance. If your code contains many (!!), you are doing something wrong. If your code contains "length list == 0" (or "== 1", "== 2"), you are doing something horribly wrong.
Yitzchak Gale wrote:
A chess board is only 8x8, so depending on your algorithms, a simple 2 dimensional list might be the fastest:
[[Maybe Piece]]
That also allows you to write simple, beautiful functional code, using the wide selection of list functions available in the Prelude and Data.List.
If you choose a map from positions to pieces, it might turn out to be just about as fast to use a simple association list
[(Int, Int), Maybe Piece]
instead of all the machinery of Data.Map.Map (Int, Int) (Maybe Piece) A chess board has only 64 locations.
Ironically, it appears to me that Data.Map is *easier* to use than an association list [(a,b)] , mainly because there aren't many functions in the Prelude for working with association lists. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
Yitzchak Gale schrieb: [...]
If you choose a map from positions to pieces, it might turn out to be just about as fast to use a simple association list
[(Int, Int), Maybe Piece]
instead of all the machinery of Data.Map.Map (Int, Int) (Maybe Piece) A chess board has only 64 locations.
if you associate positions to pieces, you can omit "Maybe" and simple delete positions without pieces from the Map. So your Map will only have 32 entries or fewer. Furthermore, you could code your row and column positions (r, c) as a single Int p and use Data.IntMap.IntMap Piece. p = 8 * r + c c = mod p 8 r = div p 8 Have fun Christian
if you associate positions to pieces, you can omit "Maybe" and simple delete positions without pieces from the Map. So your Map will only have 32 entries or fewer.
Yep, good point. The same is true for Data.Map, too.
Furthermore, you could code your row and column positions (r, c) as a single Int p and use Data.IntMap.IntMap Piece.
Also true. I think that would really be overkill for a chessboard, though. Unless perhaps you're trying to build "Big Blue" in Haskell. Regards, Yitz
participants (6)
-
Brent Yorgey -
Christian Maeder -
Daniel Fischer -
Heinrich Apfelmus -
Jordan Cooper -
Yitzchak Gale