Question

I'm working on a Gomoku game and I need an efficient data structure to store the boards state, I've thought about storing it in a 2D array, but I'm sure that there is a more efficient way. Thanks

No correct solution

OTHER TIPS

In terms of time efficiency, since I believe you'll mainly be doing index lookups, an array would be pretty much the best choice - it supports this lookup in constant time, with a low constant factor.

In terms of space efficiency:

Each square can be either empty, or populated by either player. So there are a maximum of 3 possibilities. For maximum space efficiency, we could store our entire board in base-3 representation, but, since a computer works in binary, we'd need to process the entire board to determine the value of some given square (thus a simply index lookup will take time proportional to the size of the board - if time really isn't a problem, you could consider this). Instead, I'd recommend using 2 bits per square, which would allow us to indicate one of 4 possibilities (the 4th being unused).

Many languages have some sort of bitset implementation, allowing you to work with an array of bits, which would be perfect for the above.

You'd also just want a single bitset (not 2D) as there's usually a bit of memory overhead involved in working with 2D structures. The conversion from 2D to 1D is simple - we could convert the 2D index to 1D with either x*height + y or y*width + x.

Although I'd recommend first being sure that you need to perform this optimization - I believe Gomoku boards are typically small, so even a bulky representation would work perfectly (although some AI techniques make many copies of the board, so, if you're doing that, a minimal representation would make sense).

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top