java - 跳棋游戏板 : store object refs or char values?

Question

只是一个一般性问题。我有一个带有字母搜索 aigame 的西洋跳棋游戏，整体效果非常好。我想知道是否建议将对象引用存储在板数组中并拥有干净的代码，或者更好地使用字符值数组并使用 switch() 语句来分支不同的部分。我想这取决于对象数组及其克隆的内存效率(低效率)......

我将游戏位置存储在 board[][] 数组中，该数组引用实现棋子所有特征的游戏棋子对象，特别是查找可能移动的例程。

我的主要 getmoves 循环看起来像这样:

for(sq:Squares) {
    allmoves.addAll(sq.getPossiblemoves());
}

每个方 block 都是来自类层次结构的一个对象，例如:

interface GamePiece {...}
class EmptySquare implements GamePiece {...}
class Pawn extends EmptySquare implements GamePiece {...}
class Queen extends EmptySquare implements GamePiece {...}

AI 在 alpha-beta-tree 递归中寻找最佳 Action ，为每个递归克隆游戏板，例如:

int alphabeta(Board b....) {
    for(mv:b.possibleMoves) {
      score = -alphabeta(b.doMove(mv),...)
    }
}

其中 doMove 返回一个全新的 Board 对象，其中包含带有克隆游戏片段的新棋盘数组，因此我必须创建大量对象。它运行良好并且代码非常干净。我只是不确定这在性能方面是否是一个好方法。典型的最佳移动搜索涉及大约 50000-500000 个节点，这相当于游戏板的完整副本以及大约一半节点的所有引用的游戏棋子对象(所有叶子都只是被评估，不需要进一步克隆董事会)。它使用大约 800MB 的 RAM。

我还可以使用 board[][] 数组来存储字符，或者尝试一种更紧凑的方式来存储所有游戏片段...有什么经验可以说明这会产生多大的差异吗？是否值得通过对 getPossibleMoves() 的多态调用来牺牲更好的代码？如果我存储字符值，我将必须根据游戏片段进行分支并调用不同的子例程以获得可能的移动。我认为从 OOP 原则的角度来看，这将是一个糟糕的方法，但我怀疑我的方法在性能原则方面是不好的。到底有多糟糕，我不知道......

Answer 1

我很惊讶你没有考虑使用“位板”，例如，一个 64 位整数，其中 N 位告诉你一个棋子位于 N 方格上。对于跳棋，你需要两个位板，一个用于黑色，红色。

移动生成可能可以通过位运算来完成。如果没有，您仍然可以轻松枚举棋盘位置 0..63，检查棋子类型等；它不会改变其余代码的基本逻辑。

但现在您还可以便宜地存储巨大的换位表。这将使残局发挥得非常好。

您可能希望从访问信息的抽象操作开始。为了让你的游戏玩得好，你需要对其进行调整以允许更深入的搜索。在这种情况下，您可能会发现干净的抽象与高性能不一致。我建议你先把它做好，然后当你想调整代码时，用它们的实现替换抽象函数。