棋盘对称性的处理

Question

在8X8棋盘中，我想知道如何实现棋盘的对称性。

很多位置只是、镜像、或旋转，彼此的(没有棋子或抛出功能留下的方向是无法区分的)。

通过使用板的垂直、水平和对角线镜像的组合，始终可以在a1-d1-d4三角形中固定工件的位置。

如何在棋盘上实现这些对称性？这取决于选择的板表示(Bitboard，0x88，8x8数组，等等)吗？

编辑1：目标是实现最终游戏表的生成及其压缩。

Answer 1

如果要压缩板，可以生成每个板的规范表示。@DocBrown的旧答案很好地表达了这一点：

为了提高效率，您可以使用每个板的“规范表示”，定义如下。生成给定的所有对称板，将每个板打包到一个字节数组中，在这些数组中保留一个数组，该数组被解释为一个很大的数字，具有最小值。这种填充表示是每个板的对称类的唯一标识符，可以很容易地放入字典/哈希表中，这使得测试该对称类是否已经非常有效。

这个问题指的是N皇后问题，因为每个女王都是难以区分的，所以在那里可以找到很多对称性。对于游戏终端机来说，这是(很少)的情况，所以我不知道你能节省多少钱。

Answer 2

首先，要记住，模拟这种对称性是一种优化。你不需要捕捉所有的东西，这是一种努力，复杂性和所获得的利益之间的权衡。

此外，它也无助于能够定位在a1-d1-d4三角形中的每一个单独的部分。你需要同时担心董事会上的所有部分，以及它们之间的关系。将a1和h1上的两个rooks视为实际上都位于a1上是没有意义的。

你能做的就是在对称方面“正常化”整个董事会。您需要一些算法来决定正常形式是什么。例如，您可能决定首先将白色国王转换为那个三角形，然后再执行任何其他的转换，这些转换会使白色国王保持在那里，并将黑国王移动到一个标准位置(我选择这些国王是因为他们被保证在黑板上并且是唯一的)。正如您注意到的，许多转换只有在没有剩下的棋子和抛出无效的情况下才会有效，这在很大程度上限制了可能性。

随着这种正常化，你需要跟踪你所做的操作，把董事会转换成它的正常形式，以便你可以撤销以后的转变。例如，如果您正在向用户展示一系列获胜的动作，最好是在真正的棋盘上，而不是在转换后的面板上。

然后，这种正常化与你所建立的任何现有的职位数据库结合起来是有用的。如果你知道板X的某些属性(如赢球)，而板Y规范为X板，那么你也知道板Y的属性，但前提是要取消必要的转换。当在数据库中添加位置时，您应该基于一个标准化的板来这样做。

我不认为棋盘的基本表示法对这项技术的有用性特别重要。