algorithm - 当速度是主要关注点时，表示跳棋盘的最佳数据结构是什么？

Question

我目前正在实现与西洋跳棋非常相似的东西。所以，我有这个桌面游戏，有白棋和黑棋。既没有白棋子也没有黑棋子的地方，你就没有棋子。

我目前正在执行 GetValidMoves() 方法，该方法将返回当前棋盘上可以执行的所有当前移动。

因此，我想知道代表董事会的最佳方式可能是什么。天真的方法是有一个包含 0、1 和 2 的矩阵(对于没有棋子、白色棋子和黑色棋子)。

其他想法是用 2 个列表(或任何其他数据结构)代替棋盘的矩阵表示:一个用于黑色棋子，另一个用于白色。

我正在实现这个游戏来测试一些 AI 算法，所以我主要关心的是速度。我基本上会让 2 名 AI 玩家互相对战，每一轮​​每个玩家都应该有一个他所有有效 Action 的列表，然后他会选择要做什么，这总是发生直到游戏结束(一些玩家赢了或者有一个领带)。

PS:我不是在问 AI 算法，我只是想知道处理棋盘的最佳数据结构是什么，这样可以很容易

1. 寻找当前玩家的所有有效 Action
2. 行动起来
3. 确认游戏没有结束(当一名玩家输掉所有棋子或一名玩家到达棋盘的另一侧时结束)。

Answer 1

考虑使用位图:两个 64 位无符号整数，一个用于白色，一个用于黑色。然后您可以将移动和棋盘位置表示为 (W x B) -> (W x B) 中的函数，其中 W、B 表示分别是可能的白色和可能的黑色位置的集合。

那么大部分棋盘位置的东西都可以用整数运算来完成，这几乎是你能得到的速度。