换位表？

Question

我正在使用Minimax使计算机播放connect 6。我也在使用Alpha Beta修剪来加速算法。

我想添加一个换位表，使算法更快。我对他们完全没有经验。

有人能解释一下换位表的基本原理吗，以及它们如何应用到像Connect 6这样的游戏中？一个有用资源的链接就可以了。

我熟悉哈希表。

我发现：

1)https://www.chessprogramming.org/Transposition_Table

这个链接很好地解释了换位表，但是完全集中在国际象棋上，所以很难弄清楚换位表是如何独立于国际象棋工作的。

Answer 1

这篇平庸的国际象棋文章详细解释了换位表。Zobrist算法创建转置表非常简单。

用两个词来形容zobrist系统:

< li >为每对[可能的块，可能的单元](对于井字游戏是2*9)生成一个随机数(假设32位)，并将它们存储在一个数组中。 < li >从hash=0开始，将hash与每对[播放棋子，播放棋子的位置]存储的数字进行XOR运算 < li >您获得了您的Zobrist密钥！

这是一个非常好的系统，允许删除一块！你只需要再次异或相同的数字。这对于negamax/alpha-beta算法非常有用，因为我们必须多次改变/恢复状态。保持Zobrist密钥最新是很容易的。

换位表的系统是：

>

对于某个游戏位置，您使用Zobrist算法生成一个哈希，这是游戏位置的签名，然后您获得一个整数（例如32位或64位）

这个“zobrist键”可以直接用于在换位表中存储给定位置的最佳移动和得分

但是你可能不想存储2^32或2^64个条目，所以你需要一个Zobrist键的“散列”来限制转位表的条目，比方说，16位代表2^16个游戏位置（实际上可能是

转置表索引=zobrist_key

你得到一个介于0和2^16-1之间的整数，这是你在转置表中的索引！当然，我们可能会遇到冲突，所以我们可以在转置表中存储完整的zobrist密钥。

让我们总结一下：

1. 对于给定的位置，计算 zobrist 键，然后计算 zobrist 键的哈希值，这将是您在转置表中的索引。让我们在此表条目中存储重要数据：得分，best_move，zobrist_key，标志，深度。
2. 当您需要在转置表中查找时，计算给定游戏位置的 zobrist 键，然后计算它的哈希值，并获取相应的条目。然后检查条目的zobrist密钥是否与您的密钥相等，以避免“误报”的冲突问题。

因此，对于Connect 6，您有2种石头颜色，假设有59x59的位置，因此您必须创建一个59x59x2 = 6962个随机数的数组。要在 Zobrist 键中对游戏位置进行编码，请取每颗石头，对于它的颜色和位置，取您生成的数字并将它们异或在一起。将 Zobrist 密钥减少为索引（哈希、二进制“and”、...），并将此索引中的数据存储在转置表中。

Answer 2

首先，极大极小算法(如果天真地应用的话)必须为你将来可能遇到的每个棋盘位置计算最好的打法(在极大极小的意义上)。Alpha beta修剪有助于减少不必要的计算，因为如果你知道你永远不会走某一步，那么你就不需要计算走这一步的价值。

对于某些游戏，给定棋盘上的最佳打法可以完全由当时棋盘的状态决定。国际象棋是这样，围棋是这样，其他几个游戏也是这样。关键的认识是，一旦你到达了那个状态，你如何到达一个特定的游戏状态并不重要(从极小极大的观点来看)。

具体来说，国际象棋意义上的换位是当您采取 2 条不同的移动路径从起始位置到结束位置时会发生什么。

换位表只是让你在遇到不同的游戏导致棋盘处于相同结束状态的情况下优化计算最佳移动。本质上，一旦你到达一个特定的棋盘位置，你只需将极小值计算的结果存储在换位表中的那个位置。这意味着稍后如果其他一些不同的移动列表到达同一个棋盘，那么突然之间你不需要在那个棋盘上完全重新计算极小值，因为你已经这样做了，你可以从换位表中查找它。

因此，如果玩家可以通过多种方式到达同一个棋盘位置，如果你能够以某种方式保存计算结果，你就不需要重复查看游戏树的分支多次。为了有效地做到这一点，你需要能够有效地表示棋盘位置，然后有一些数据结构，允许你在换位表中快速查找棋盘位置。找到正确的表示将在很大程度上取决于你正在分析的游戏。

如果connect6是这个游戏，也许举个例子会比较好:

假设董事会像这样开始（位置 A）：

X 0 
0 X

有不止一组动作可以让你达到（位置 B）：

X 0 0 0
0 X X X
0 X

假设从A位置到B位置有n种方法，如果你天真地这样做，你可能需要测试在B位置找到最多n次的最佳移动（取决于树的α-β分支修剪掉）。但是如果我们不必为B板位置多次进行完全相同的计算，那就太好了，希望一次就足够了！

要利用这个想法，您必须找到一种表示连接 6 板位置的方法。我们可以表示电路板的一种方法是拥有一个 N x N 数组，其中 N 是电路板尺寸，并且只需为每个单元格存储一个枚举值，该值对应于它是否为空、包含 X 或包含 0。然而，这种幼稚的方法对于查找位置没有很好的属性，因为我们总是会传递这些讨厌的 N x N 数组。更不用说必须始终存储大量这些 N x N 数组会占用大量内存。

因此，如果我们可以定义一个哈希函数，它将N乘Nboard映射为几乎唯一的整数，而不需要大量的处理开销，那么我们可以简化这个过程。用这种方法打散一块木板，看看它是否在桌子上，希望会更快。

这就是为什么人们试图为他们正在分析的特定游戏制作散列函数。对于连接6，我不知道最好的散列函数是什么，这是你必须解决的问题。

从这样的东西中获得最佳性能需要大量的修改，但希望这篇文章能给你一些启发。如果你想让我详述什么，请发表意见。