How to represent a board?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

How to represent a board?

Rafael Almeida
Hello,

There are many examples of games which use boards: chess, checkers, go, etc. Many people starting out at programming and/or game programming are very much tempted to code a board game. It looks like such a game would be easy to build at first sight.

Even more sophisticated games sometimes use a grid system, which looks a lot like boards as well. In a grid system the movements of a given agent are bound do discrete positions. Although the user may not see the board underneath pretty graphics, it is a board game.

Having in mind the sort of operations such games have to make on boards, I ask: what are the best representations for a board in Haskell?

In many languages a NxN array seems like a good pick. In Haskell, most would translate that into lists of lists. I know I have. However, traversing those lists to get a position, calculate where a piece or agent could go, etc., feels awkward and unefficient. Beside the point already made, we have no type safe guarantee that our 64x64 won't become a 63x63 + 65x1 board due to some misbehaving function.

It strikes me that list of lists is not a great board representation. I think STArrays are a better pick; from the perspective of translating an NxN array into Haskell, at least. However, maybe there is an even more elegant way to deal with a board in Haskell. I hope you can help me out figuring it out.

[]'s
Rafael

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Alexander Vieth
> In many languages a NxN array seems like a good pick. In Haskell, most would translate that into lists of lists. I know I have. However, traversing those lists to get a position, calculate where a piece or agent could go, etc., feels awkward and unefficient. Beside the point already made, we have no type safe guarantee that our 64x64 won't become a 63x63 + 65x1 board due to some misbehaving function.

Perhaps choosing a zipper-like representation, in which all adjacent places on your board can be found without any traversal, would make the usage less awkward and more efficient. As for the size, you can get a guarantee that it won't change, so long as you make a new type for your board and verify that no function on that type will produce a board of bogus size.

Alex

On 2014-06-20, at 11:24 AM, Rafael Almeida wrote:

> Hello,
>
> There are many examples of games which use boards: chess, checkers, go, etc. Many people starting out at programming and/or game programming are very much tempted to code a board game. It looks like such a game would be easy to build at first sight.
>
> Even more sophisticated games sometimes use a grid system, which looks a lot like boards as well. In a grid system the movements of a given agent are bound do discrete positions. Although the user may not see the board underneath pretty graphics, it is a board game.
>
> Having in mind the sort of operations such games have to make on boards, I ask: what are the best representations for a board in Haskell?
>
> In many languages a NxN array seems like a good pick. In Haskell, most would translate that into lists of lists. I know I have. However, traversing those lists to get a position, calculate where a piece or agent could go, etc., feels awkward and unefficient. Beside the point already made, we have no type safe guarantee that our 64x64 won't become a 63x63 + 65x1 board due to some misbehaving function.
>
> It strikes me that list of lists is not a great board representation. I think STArrays are a better pick; from the perspective of translating an NxN array into Haskell, at least. However, maybe there is an even more elegant way to deal with a board in Haskell. I hope you can help me out figuring it out.
>
> []'s
> Rafael
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Bob Ippolito
In reply to this post by Rafael Almeida
I've used Data.Array or Data.Vector when trying to solve these sorts of problems. The size of the board is not encoded in the type with either library, but that's not something that's easy to do or commonly implemented in Haskell.

Data.Vector has better functionality, but the index is always an Int, so Array can be more convenient in many cases as it can be indexed by any instance of Ix.

STArray, MVector, etc. are all options as well, but I prefer to write functional solutions when possible.


On Fri, Jun 20, 2014 at 8:24 AM, Rafael Almeida <[hidden email]> wrote:
Hello,

There are many examples of games which use boards: chess, checkers, go, etc. Many people starting out at programming and/or game programming are very much tempted to code a board game. It looks like such a game would be easy to build at first sight.

Even more sophisticated games sometimes use a grid system, which looks a lot like boards as well. In a grid system the movements of a given agent are bound do discrete positions. Although the user may not see the board underneath pretty graphics, it is a board game.

Having in mind the sort of operations such games have to make on boards, I ask: what are the best representations for a board in Haskell?

In many languages a NxN array seems like a good pick. In Haskell, most would translate that into lists of lists. I know I have. However, traversing those lists to get a position, calculate where a piece or agent could go, etc., feels awkward and unefficient. Beside the point already made, we have no type safe guarantee that our 64x64 won't become a 63x63 + 65x1 board due to some misbehaving function.

It strikes me that list of lists is not a great board representation. I think STArrays are a better pick; from the perspective of translating an NxN array into Haskell, at least. However, maybe there is an even more elegant way to deal with a board in Haskell. I hope you can help me out figuring it out.

[]'s
Rafael

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Corentin Dupont
Instead of encoding the board, I would encode the position of the pieces: there is usually much less pieces than squares.


On Fri, Jun 20, 2014 at 5:33 PM, Bob Ippolito <[hidden email]> wrote:
I've used Data.Array or Data.Vector when trying to solve these sorts of problems. The size of the board is not encoded in the type with either library, but that's not something that's easy to do or commonly implemented in Haskell.

Data.Vector has better functionality, but the index is always an Int, so Array can be more convenient in many cases as it can be indexed by any instance of Ix.

STArray, MVector, etc. are all options as well, but I prefer to write functional solutions when possible.


On Fri, Jun 20, 2014 at 8:24 AM, Rafael Almeida <[hidden email]> wrote:
Hello,

There are many examples of games which use boards: chess, checkers, go, etc. Many people starting out at programming and/or game programming are very much tempted to code a board game. It looks like such a game would be easy to build at first sight.

Even more sophisticated games sometimes use a grid system, which looks a lot like boards as well. In a grid system the movements of a given agent are bound do discrete positions. Although the user may not see the board underneath pretty graphics, it is a board game.

Having in mind the sort of operations such games have to make on boards, I ask: what are the best representations for a board in Haskell?

In many languages a NxN array seems like a good pick. In Haskell, most would translate that into lists of lists. I know I have. However, traversing those lists to get a position, calculate where a piece or agent could go, etc., feels awkward and unefficient. Beside the point already made, we have no type safe guarantee that our 64x64 won't become a 63x63 + 65x1 board due to some misbehaving function.

It strikes me that list of lists is not a great board representation. I think STArrays are a better pick; from the perspective of translating an NxN array into Haskell, at least. However, maybe there is an even more elegant way to deal with a board in Haskell. I hope you can help me out figuring it out.

[]'s
Rafael

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Chris Warburton
In reply to this post by Alexander Vieth
Alexander Vieth <[hidden email]> writes:

>> In many languages a NxN array seems like a good pick. In Haskell,
>> most would translate that into lists of lists. I know I
>> have. However, traversing those lists to get a position, calculate
>> where a piece or agent could go, etc., feels awkward and
>> unefficient. Beside the point already made, we have no type safe
>> guarantee that our 64x64 won't become a 63x63 + 65x1 board due to
>> some misbehaving function.
>
> Perhaps choosing a zipper-like representation, in which all adjacent
> places on your board can be found without any traversal, would make
> the usage less awkward and more efficient.

I thought of zippers too, although their simplicity suffers when moving
from 1D lists to 2D lists-of-lists.

Comonads are possibly related. They're certainly useful for cellular
automata[1], which are effectively zero-player board games.

[1] http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html

Cheers,
Chris
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Chris Warburton
In reply to this post by Corentin Dupont
Corentin Dupont <[hidden email]> writes:

> Instead of encoding the board, I would encode the position of the pieces:
> there is usually much less pieces than squares.

Possibly useful: http://en.wikipedia.org/wiki/Sparse_matrix

Cheers,
Chris
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Carter Schonwald
Unless you're dealing with a board with millions of positions or more, sparse matrices don't matter. 

The array package has support for 2d arrays. 

I've my own pretty fancy multi dim array tooling in the works, but for your use case just use array package 

On Friday, June 20, 2014, Chris Warburton <[hidden email]> wrote:
Corentin Dupont <<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;corentin.dupont@gmail.com&#39;)">corentin.dupont@...> writes:

> Instead of encoding the board, I would encode the position of the pieces:
> there is usually much less pieces than squares.

Possibly useful: http://en.wikipedia.org/wiki/Sparse_matrix

Cheers,
Chris
_______________________________________________
Haskell-Cafe mailing list
<a href="javascript:;" onclick="_e(event, &#39;cvml&#39;, &#39;Haskell-Cafe@haskell.org&#39;)">Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Daniel Trstenjak-2
In reply to this post by Rafael Almeida

Hi Rafael,

> Having in mind the sort of operations such games have to make on boards, I ask:
> what are the best representations for a board in Haskell?

What works pretty nicely is using a one dimensional Data.Vector[1] to represent
your board, a tuple (x, y) to represent a position on the board and then using
a lens[2] to transform the tuple (x, y) into an index of the one dimensional Data.Vector.

You can then write code like:

   -- get board value at position (1, 2)
   board ^. atCoord (1, 2)    

   -- set board value at position (1, 2)
   board & atCoord (1, 2) .~ newValue


Having a one dimensional vector has the advantage, that's a lot nicer to e.g. map or fold over it.

In the toy example hsbot[3] I used this kind of representation.


Greetings,
Daniel

[1] https://hackage.haskell.org/package/vector
[2] https://hackage.haskell.org/package/lens
[3] https://github.com/dan-t/hsbot
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: How to represent a board?

Benjamin Edwards
There is also the grid package on hackage that has support for a number of different grid shapes.

Ben


On Fri, Jun 20, 2014 at 5:12 PM, Daniel Trstenjak <[hidden email]> wrote:


Hi Rafael,

> Having in mind the sort of operations such games have to make on boards, I ask:
> what are the best representations for a board in Haskell?

What works pretty nicely is using a one dimensional Data.Vector[1] to represent
your board, a tuple (x, y) to represent a position on the board and then using
a lens[2] to transform the tuple (x, y) into an index of the one dimensional Data.Vector.

You can then write code like:

-- get board value at position (1, 2)
board ^. atCoord (1, 2)

-- set board value at position (1, 2)
board & atCoord (1, 2) .~ newValue


Having a one dimensional vector has the advantage, that's a lot nicer to e.g. map or fold over it.

In the toy example hsbot[3] I used this kind of representation.


Greetings,
Daniel

[1] https://hackage.haskell.org/package/vector
[2] https://hackage.haskell.org/package/lens
[3] https://github.com/dan-t/hsbot
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe