Re: [computer-go] Dynamic-memory in Go?

[Arend Bayer <arend.bayer@xxxxxx>]

>   Maybe there is in Go - besides breadth-first-search - another place where one needs dynamic-memory-allocation. If yes, I would be interested for which parts dynamic memory is needed.

The problem is that even for storing all relevant data for a single
position, you cannot give good bounds for the amount memory you need.

Consider blocks (directly connected strings of stones): You may want to
store it's number of liberties, whether it's attackable, defendable,
etc. A typical go position contains maybe 30 such blocks. But worst case 
on a 19x19 board is around 290. So if you do this in a static array, you
waste a lot of memory, and possibly destroy data locality.

Further, you may want to store a list of all neighboring blocks.
Maybe on average 3 per block, but of course it can be much higher.
Similarly a list of liberties, etc.

While GNU Go does all of the above in static arrays (either by using the
safe upperbounds, or by just ignoring everything that doesn't fit in the
size of the list), it would seem entirely reasonable to me to do all this
with dynamic memory. Since dynamic memory may give better data locality,
it's a priori not at all clear which approach is faster.

Arend

P.S.: Although it's a bit late now, still congratulations to Hydra's
nice victory against Shredder.

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/