我在使用极小化-极大化算法（Minimax）让计算机玩连接6游戏（Connect 6）。我还使用了Alpha-Beta剪枝来加速算法。

我想添加一个置换表来使算法更加快速。我对置换表完全没有经验。

能有人解释一下置换表的基础知识，以及它们如何应用于像连接6这样的游戏吗？提供一个有用的资源链接也可以。

我熟悉哈希表。

我找到的：

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

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

回答：

首先，如果简单地应用极小化-极大化算法（Minimax），它必须为将来可能遇到的每个棋盘位置计算最佳走法（在极小化-极大化意义上）。Alpha-Beta剪枝有助于减少不必要的计算，因为如果你知道你永远不会走某一步棋，那么你就不需要计算走那一步棋的值。

在一些游戏中，某个棋盘上的最佳走法完全可以由当时棋盘的状态决定。国际象棋、围棋以及其他一些游戏也是如此。关键的认识是，一旦到达某个游戏状态，如何到达那个状态并不重要（从极小化-极大化的角度来看）。

具体来说，置换这个词在国际象棋的意义上是指从起始位置到结束位置时采取的两条不同路径的移动。

置换表只是在你遇到不同走法导致棋盘处于相同结束状态的情况时，优化计算最佳走法的方式。本质上，一旦你到达一个特定的棋盘位置，你只需将该位置的极小化-极大化计算结果存储在置换表中。这意味着，如果以后其他不同的移动列表到达同一棋盘，你就不需要完全重新计算该棋盘的极小化-极大化，因为你已经做过这件事了，你可以直接从置换表中查找结果。

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

如果连接6是这个游戏，或许一个例子会很好：

假设棋盘开始时是这样的（位置A）：

X 0 0 X

有不止一种移动集可以让你到达（位置B）：

X 0 0 00 X X X0 X

假设从位置A到位置B有n种方式，如果你简单地处理这个问题，你可能需要测试在位置B找到最佳走法最多n次（取决于Alpha-Beta剪枝掉的树枝）。但实际上，如果我们不需要为B棋盘位置重复进行完全相同的计算，完成一次就足够了，这将是很棒的！

为了利用这个想法，你必须找到一种表示连接6棋盘位置的方法。我们可以表示棋盘的一种方式是使用一个N by N数组，其中N是棋盘的维度，并且为每个单元格存储一个枚举值，对应于它是空的、里面有X还是0。然而，这种简单的方法在查找位置时没有很好的属性，因为我们总是要传递这些讨厌的N by N数组。更不用说总是要存储大量这样的N by N数组会占用很多内存。

所以，如果我们可以定义一个哈希函数，它接受N by N棋盘并将其映射到一个几乎唯一的整数，而不会产生大量的处理开销，那么我们可以简化这个过程。通过这种方式，哈希一个棋盘并检查它是否在表中应该会更快。

这就是为什么人们试图为他们正在分析的特定游戏制作一个哈希函数。对于连接6，我不知道最好的哈希函数是什么，这是你需要自己解决的问题。

从这样的东西中获得最佳性能需要大量的调整，但希望这篇文章能给你一些想法。如果你希望我扩展任何内容，请评论。