Gomoku董事会代表

Question

我正在一个Gomoku游戏，我需要一个高效的数据结构来存储板状态， 我想过把它存储在一个二维数组中，但我相信有更多高效的方式。 谢谢

Answer 1

在时间效率方面，因为我相信你会主要做索引查找，所以一个数组几乎是最好的选择 - 它支持持续时间的这种查找，具有低常数因子。

在空间效率方面：

每个正方形可以是空的，或由播放器填充。所以最多有3种可能性。为了获得最大的空间利用效率，我们可以将我们的整个电路板存储为3进制表示形式，但是，由于计算机工作在二进制模式，因此我们需要处理整个电路板以确定给定平方的值（因此只需索引查找就可以了需要时间与董事会的大小成正比 - 如果时间真的不是一个问题，你可以考虑这一点）。相反，我建议使用每平方2位，这将允许我们指出4种可能性中的一种（第4种未被使用）。

许多语言都有某种bitset的实现，允许你使用一系列位，这对于上述是完美的。

你也只想要一个位集（而不是2D），因为在处理二维结构时通常会涉及一些内存开销。从2D到1D的转换很简单 - 我们可以用x*height + y或y*width + x将2D索引转换为1D。尽管我会推荐首先确定你需要执行这种优化 - 我相信Gomoku主板通常很小，所以即使是笨重的表示也能完美工作（尽管一些AI技术可以制作很多副本，所以，如果你这样做，最小的表示将是有意义的）。