10Mar2009
Filed under: haskell
Author: osfameron
(This isn't a full blog post, but a note of a few things about implementing game grids in Haskell).
- A [[Cell]] structure seems to make sense for a lot of boards. In fact, even the problems I'm looking at might be approached simply indexing into row then col each time you want to access a list. However it feels inelegant, and some of the things I want to do (looking at lines of game pieces in a given direction N/S/E/W) would be more elegant if I can simply traverse the grid in an arbitrary direction.
- morrow remembered there had been a discussion on haskell-cafe about grids (+ +) recently. It seems to be mainly about infinite grids, but has lots of interesting stuff to absorb.
- paolino remembered that comonads were useful in grid representation. I don't understand what they are but google finds http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html which looks interesting.
- I think I want a zipper, but didn't know how it would work on [[Cell]]. Saizan clarified: "if Zipper [] a is the zipper for [a], then the one for [[a]] is Zipper [] (Zipper [] a), and depending on which layer you use the next/previous operations you move in one dimension or the other". This isn't quite true though, as when you move up/down by rows, you have to somehow remember the columnwise index.
- (Saizan referred to fmap'ing operations to keep the columns in sync, which is, I think, a more higher-order way of doing the same thing :-)
- dolio posted an ADT representation of a grid. I don't understand that at all yet, but it is pretty... He also wrote a Traversable instance (this would appear to be a generic way to expose functions to move around in your arbitrary datastructure)
- I decided to try to fold a [[Cell]] into a Cell { value=x, down=d, right=r }. This took me several hours last night, during which I cursed my feeble brain, and the fact that mutable references would have made the task trivial in other languages. (However, mutable references would make the grid useless for many useful things, like keeping intermediate copies of grid state). My no-doubt crappy code is on github (I'll come back to it in more detail later)
- While I'm whining about haskell being "too hard" I should mention that I've got bogged down in representing grids (for games or spreadsheet) in Java, Perl, and Javascript too, so I think it may be more a case of my brain being feeble. That or I'm just overcomplicating things...
- (As I remember it, the OO representation of grids is simpler to get started with but then I get bogged down with issues of multiple inheritance etc.)
Comments and suggestions welcome, I should write a full post on this soon.
chessguy
March 10th, 2009 at 1:38 pm
Here are two interesting articles about representing chess boards in imperative languages: http://www.cis.uab.edu/hyatt/boardrep.html http://www.cis.uab.edu/hyatt/bitmaps.html
Dan P
March 10th, 2009 at 6:57 pm
At first, the lack of mutability can seem annoying in Haskell. But if you're writing a game AI there's actually a big advantage. When you're searching a game tree you often find that you have many representations of boards in memory at one time, and that you're often copying boards so that you can modify the position of something or other without destroying the original board.
When you use non-mutable boards, and you use some kind of tree structure to represent them, whenever you make a new board you reuse subtrees of the old board in the new one. The result is that you get lots of sharing between boards in memory and you also don't have to copy entire boards.
banbh
March 11th, 2009 at 3:10 am
You may find the following post interesting:
http://banbh.blogspot.com/2007/08/pascals-triangle.html
It defines Pascal's triangle. If there were done naively you would end up with a (exponentially growing) tree. Done right (as in the post above) you end up with essentially a grid.
Colin Adams
March 11th, 2009 at 9:34 am
I'm using an Array of Arrays.
One reason is that I'd like to try exploiting DPH. I don't think that's possible right now (I seem to recall the types permitted are very restricted), but that might change in the future.
In any case, I could see the advantage of using a list of lists.
Dmitry Tsygankov
March 11th, 2009 at 10:36 am
Can it be done with the Data.Map thing? A map from (int, int) to Piece or something. Without any empty cells present in the map.
Edward Kmett
March 11th, 2009 at 4:12 pm
If your grid size is regular you can always fall back on something like an array and an index into the array rather than a zipper.
Dan Piponi used something similar to that for "comonadic arrays"
Most of the actions you'll want to perform on the grid won't be comonadic, but the structure itself is simple enough to work with.
http://blog.sigfpe.com/2008/03/comonadic-arrays.html