Best data type to represent a game board

[Tobias Pfeiffer]

Hey everyone,

I'm thinking about doing my (fourth...) Go(-game) AI implementation in
Elixir for fun, learning and profit. It needs to be as fast as possible
to be good, and one of the cornerstones of course is the game
board/state and many simulations will be run.

A game board is special because...

* has a set size (19x19 for instance), which can also be "unfolded" to
be one dimensional (just 361 fields)
* needs random access (you often check a field and its surrounding
fields, or many of them)
* is usually updated less than read (you move/set one piece but usually
do more checks before that)
* for Go specifically each board field can only have 3 different values
(empty, black, white)

Lists are out due to the random access/update change. Now it seems like
my choices sort of boil down to...

* Tuples
* Binaries
* Maps?

Does anyone have any recommendations/experience/tips which data type
might be best suited to what I'm describing or what data type I might be
missing or ignoring.

Cheers + thanks in advance!
Tobi
--
http://www.pragtob.info/

[José Valim]

On top of my head I would try either tuples with tuples or a flat map where you would use the row+col to compute the map key. Ideally you would abstract all of the board operations on its own module so if later you need to change its internal representation, the rest of the code would be fine.

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Director of R&D

--
http://www.pragtob.info/

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-talk+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-talk/cb55a6c4-f6c0-7ce7-7d0f-a654ebe4f855%40gmail.com.
For more options, visit https://groups.google.com/d/optout.

[OvermindDL1]

If you want it fast then you'd probably want a port with C++/rust or so for the math part, but since you are doing it for fun, learning, and profit, then I'd use binaries.  ^.^

Specifically, I'd use bitstrings, every 3 bits would represent two squares.  This is the tightest packing that you can get and it is easy to store in ETS or so along with possible links to other states that you could build a tree out of.  Then a weighting min/max (or better, AI?  There are a few AI modules with genetic algo's for elixir) to calculate a score for each, store that with the board state and links, then you can walk the tree to find the best paths.  That would be the simple/naive way that I'd whip it up anyway.

[Tobias Pfeiffer]

Thanks for the input (both of you!),

it'll definitely live in its own module with all important access
methods (neighbous_of for instance) so that it'd be easy to exchange.
When I do it I'll probably start with tuples and then once the basic
monte carlo tree search runs exchange the underlying data type,
benchmark and share :)

Tobi

On 09/09/2016 04:11 PM, José Valim wrote:
> On top of my head I would try either tuples with tuples or a flat
> map where you would use the row+col to compute the map key. Ideally you
> would abstract all of the board operations on its own module so if later
> you need to change its internal representation, the rest of the code
> would be fine.
>
>
>
>

> *José Valim*
> www.plataformatec.com.br <http://www.plataformatec.com.br/>

> send an email to elixir-lang-ta...@googlegroups.com
> <mailto:elixir-lang-talk%2Bunsu...@googlegroups.com>.

> To view this discussion on the web visit
> https://groups.google.com/d/msgid/elixir-lang-talk/cb55a6c4-f6c0-7ce7-7d0f-a654ebe4f855%40gmail.com

> <https://groups.google.com/d/msgid/elixir-lang-talk/cb55a6c4-f6c0-7ce7-7d0f-a654ebe4f855%40gmail.com>.

> For more options, visit https://groups.google.com/d/optout

> <https://groups.google.com/d/optout>.

>
>
> --
> You received this message because you are subscribed to the Google
> Groups "elixir-lang-talk" group.
> To unsubscribe from this group and stop receiving emails from it, send

> an email to elixir-lang-ta...@googlegroups.com
> <mailto:elixir-lang-ta...@googlegroups.com>.

> To view this discussion on the web visit

> https://groups.google.com/d/msgid/elixir-lang-talk/CAGnRm4%2BZp53jLnCYz5csGU_%3D%2BCfmtWFg7YKSP_jOqnptW%2Bpnfg%40mail.gmail.com
> <https://groups.google.com/d/msgid/elixir-lang-talk/CAGnRm4%2BZp53jLnCYz5csGU_%3D%2BCfmtWFg7YKSP_jOqnptW%2Bpnfg%40mail.gmail.com?utm_medium=email&utm_source=footer>.

> For more options, visit https://groups.google.com/d/optout.

--
http://www.pragtob.info/