data-structures - 五子棋局代表

Question

我正在开发五子棋游戏，我需要一个有效的数据结构来存储棋盘状态，我曾考虑将其存储在二维数组中，但我确信有一种更有效的方法。谢谢

Answer 1

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

在空间效率方面：

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

许多语言都有某种位集实现，允许您使用位数组，这对于上述情况来说是完美的。

您还只需要一个位集（不是 2D），因为使用 2D 结构通常会产生一些内存开销。从 2D 到 1D 的转换很简单 - 我们可以使用x*height + y或将 2D 索引转换为 1D y*width + x。

尽管我建议您首先确定您需要执行此优化 - 我相信 Gomoku 板通常很小，因此即使是庞大的表示也可以完美地工作（尽管一些 AI 技术会制作许多板的副本，所以，如果你是这样做，最小的表示是有意义的）。