java - Ataxx 游戏中的状态表示

Question

我已经在这里问过一个关于这个主题的问题：
https ://stackoverflow.com/questions/19916951/generating-a-tree-form-array-for-ataxx-game-in-java

但是让我一步一步来：

表示Ataxx 游戏状态（使用 7x7 网格板）的最佳方式（或最佳数据结构）是什么？

* 状态由博弈树的一个节点表示，但节点中有什么？一个值？一个字符串？另一个数据结构？

Answer 1

整个棋盘可以由某种整数类型（即byte[][]）的二维数组表示，或者可能是一个enum[][]. 然后0可以，例如，表示一个空单元格，1可以表示一个带有玩家 1 棋子2的单元格，并且可以表示一个带有玩家 2 棋子的单元格。

游戏树中的一个节点通常是整个棋盘（所以byte[][]or enum[][]）。

如果您正在寻找更紧凑的电路板表示，您还可以使用base-3或base-4（2 位，更易于使用）表示法来表示电路板，但这有点复杂（您可能会坚持二维数组，直到你开始遇到内存/运行时间问题——只要你将它抽象成一个类，转换应该相当简单，并且易于测试）。

Answer 2

我会使用从国际象棋和跳棋中提取的非常有效的表示形式：bitboards。这个概念是用比特来表示棋子，因此玩家的棋子集合可以用比特域来表示。我们至少需要 49 位，所以 64 位整数可以很好地工作。

这是一种内存和计算效率极高的表示，它也比其他表示更具表现力。您可以通过按位运算轻松地同时处理两个单件以及整个集合。对于建议的基于数组的表示，对于可以由具有位板（、、、、、等）的单个运算符表示的操作，byte[][]您必须循环太多。&|^<<>>>

设置位给出玩家的棋子。例如，这可能是一位玩家的位板。您将需要另一个位板供其他玩家使用。

0000000000000000000000000000000010000000001000000

在十进制中，这将是long bitboard = 65600;. 如果我们插入一些新行，它看起来像这样：

0000000
0000000
0000000
0000000
0000100
0000000
1000000

为了有效地处理这个问题，我们可以预先计算一些表。因此，对于第 32 位/正方形中心的棋子，我们可能有一个surrounding表格，当用作surrounding[square]给出时：

0000000
0000000
0000000
0001110
0001010
0001110
0000000

然后我们可以使用按位运算符找到它与对手的位板的交集&，或者将其与 并集|，或与 进行差集^等。您可以使用 将整个位板向上移动一排<< 7，或者轻松执行任意数量的复杂操作。它具有很强的表达能力，而且这些操作中的大多数只需要一个时钟周期，因此它的效率也非常高。