Gomoku董事会代表

Question

我正在开发一款Gomoku游戏，我需要一个高效的数据结构来存储棋盘状态，我已经考虑过将其存储在2D数组中，但我相信有一种更有效的方法。谢谢

Answer 1

就时间效率而言，由于我相信您将主要进行索引查找，因此数组将是最好的选择-它支持在恒定时间内进行这种查找，具有较低的恒定因子。

在空间效率方面：

每个方块可以是空的，也可以由任一玩家填充。所以最多有3种可能性。为了获得最大的空间效率，我们可以以基数3表示存储整个电路板，但是，由于计算机以二进制方式工作，我们需要处理整个电路板来确定某个给定正方形的值(因此，简单的索引查找将花费与电路板大小成比例的时间-如果时间真的不是问题，你可以考虑这一点)。相反，我建议使用每平方2位，这将允许我们指示4种可能性中的一种(第四种是未使用的)。

许多语言都有某种类型的位集实现，允许您处理位数组，这将是上述工作的完美选择。

您也可能只需要一个位集(而不是2D)，因为在处理2D结构时通常会涉及到一些内存开销。从2D到1D的转换很简单-我们可以使用x*height + y或y*width + x将2D索引转换为1D。

虽然我建议首先确定你需要执行这种优化-我认为Gomoku板通常很小，所以即使是一个庞大的表示也可以完美地工作(尽管一些AI技术可以复制很多个板，所以，如果你这样做，最小的表示将是有意义的)。