一尘不染

当速度是首要考虑因素时,代表棋盘的最佳数据结构是什么?

algorithm

我目前正在实施与检查程序非常相似的方法。因此,我有这款桌上游戏,有白色和黑色两块。在没有白色或黑色碎片的地方,您没有碎片。

我目前正在执行GetValidMoves()一种方法,该方法将返回当前板可以执行的所有当前动作。

因此,我想知道代表董事会的最佳方法是什么。天真的方法是使用一个矩阵,该矩阵具有0的1和2(无片,白片和黑片)。

另一种想法是代替木板的矩阵表示,而是有2个列表(或任何其他数据结构):一个用于黑色,另一个用于白色。

我正在实施此游戏以测试某些AI算法,因此我主要关心的是速度。我基本上将让2个AI玩家互相玩游戏,每回合每个玩家都应拥有其所有有效举动的列表,然后他将选择要采取的举动,直到游戏结束时这种情况一直发生(某些玩家获胜或有一个获胜者领带)。

PS:我不是在问AI算法,我只是想知道什么是处理电路板的最佳数据结构,因此它很容易实现

  1. 寻找当前玩家的所有有效举动
  2. 做个动作
  3. 验证游戏还没有结束(一个玩家失去所有棋子或一个玩家到达棋盘的另一端时结束)。

阅读 243

收藏
2020-07-28

共1个答案

一尘不染

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

然后,大多数板位的工作都可以用整数算术完成,这与您获得的速度差不多。

2020-07-28