跳棋游戏棋盘:存储对象引用或字符值？

Question

这只是一个一般性的问题。我有一个与alphabeta-search aigame的跳棋游戏，总体上运行得很好。我想知道是否建议将对象引用存储在板数组中并拥有干净的代码，或者更好地使用char-value数组并使用switch()语句来分支到不同的部分。我猜这取决于内存(在)对象数组中的效率以及它的克隆……

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

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

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

每个方块都是一个来自类层次结构的对象，如下所示：

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

AI在alpha-beta-tree递归中寻找最佳走法，该递归为每次递归克隆游戏板，例如：

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

其中doMove返回一个全新的Board对象和一个带有克隆游戏棋子的新board-array，所以我必须做大量的对象创建工作。它工作得很好，代码也很干净。就性能而言，我只是不确定这是不是一个好的方法。典型的最佳移动搜索涉及大约50000-500000个节点，这相当于游戏棋盘的完整副本和这些节点中大约一半的所有引用的游戏棋子对象(所有的叶子只需要评估，不需要进一步克隆棋盘)。它使用大约800MB的RAM。

我也可以使用一个存储字符的棋盘数组，或者尝试一种更紧凑的方式来存储所有的游戏棋子……有没有经验知道这会有多大的不同？牺牲更好的代码和对getPossibleMoves()的变形调用值得吗？如果我存储char值，我将不得不根据游戏棋子进行分支，并调用不同的子例程来获得可能的移动。我认为从OOP原则的角度来看，这是一个糟糕的方法，但我怀疑我的方法在性能原则方面是糟糕的。到底有多糟，我不知道...

Answer 1

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

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

但是现在你也可以很便宜地存储巨大的转换表。这将使最终游戏变得非常好。

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