当速度是主要关注点时,代表跳棋板的最佳数据结构是什么？

Question

我目前正在实现与跳棋非常相似的东西.所以,我有这个桌面游戏,有白色和黑色的片断.如果没有白色或黑色的碎片,你就没有碎片.

我现在正在做的GetValidMoves()方法是返回当前电路板可以做的所有当前动作.

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

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

我正在实现这个游戏来测试一些AI算法,所以我主要关心的是速度.我基本上会让2个AI玩家互相玩,每回合每个玩家应该有一个他所有有效动作的列表,然后他会选择要做的动作,这一直发生直到比赛结束(某些玩家获胜或者有一个领带).

PS:我不是在询问AI算法,我只想知道处理电路板的最佳数据结构是什么,这样就可以轻松实现

1. 查找当前玩家的所有有效动作
2. 采取行动
3. 验证游戏未结束(当一名玩家丢失所有棋子或一名玩家到达棋盘的另一侧时,游戏结束).

Answer 1

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

然后大多数电路板位置的东西都可以用整数运算来完成,这个速度大约是你能得到的.

Answer 2

一种常见的方法是使用long每个玩家的类型二进制表示.
(因为棋盘上有64个方格)..正如查理已经说过的......
这是一篇非常好的(但是一般的)维基文章.

用法很简单 - 例如,如果你想检查所有棋子是否可以向上和向右移动,将玩家的棋子重新移位7位向左移动,并检查那里是否有对手棋子,然后再将它们向左移7位并检查这些方块是否清晰......
我曾在Reversi竞赛中使用过一次,可以说实施并不太难.
HTH.