转换表？

Question

我正在使用Minimax让计算机运行connect 6。我还使用了Alpha-Beta剪枝来加速算法。

我想添加一个转置表，以使算法更快。我完全没有使用它们的经验。

谁能解释一下转置表的基础知识，以及它们如何应用到像Connect 6这样的游戏中？一个有用资源的链接就可以了。

我对哈希表很熟悉。

我发现：

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

该链接很好地解释了转置表，但完全集中在国际象棋上，因此很难弄清楚转置表是如何独立于国际象棋工作的。

Answer 1

首先，minimax算法，如果简单地应用，必须计算未来可能遇到的每个棋盘位置的最佳发挥(在minimax意义上)。Alpha beta-pruning有助于减少不必要的计算，因为如果你知道你永远不会玩某个棋子，那么你就不需要计算玩那个棋子的价值。

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

具体地说，在国际象棋意义上的换位是指当你采取两种不同的移动路径从开始位置到结束位置时发生的事情。

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

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

如果是connect6 is this game，举个例子就好了：

假设棋盘是这样开始的(位置A)：

X 0 
0 X

有不止一套动作可以让你达到(位置B)：

X 0 0 0
0 X X X
0 X

假设从位置A到位置B有n种方法，如果你很天真地去做这件事，你可能不得不测试找出在位置B的最佳移动n次(取决于树的α-beta修剪掉了哪些分支)。但如果我们不需要对B板的位置进行多次完全相同的计算，那就太好了，一次就足够了！

要利用这个想法，您必须找到一种表示连接6板位置的方法。我们可以表示电路板的一种方法是，只需要有一个N by N数组，其中N是电路板的尺寸，并且只存储每个单元格的枚举值，如果它为空，其中有一个X，或者有一个0。然而，这种简单的方法在查找位置方面没有很好的属性，因为我们总是在传递这些讨厌的N by N数组。更不用说必须总是存储大量这样的N by N数组，这将占用大量内存。

因此，如果我们可以定义一个哈希函数，将N by N板映射到一个几乎唯一的整数，而不需要大量的处理开销，那么我们就可以简化这个过程。散列一个棋盘，看看它是否在表中，希望这样会更快。

因此，这就是为什么人们试图为他们正在分析的特定游戏创建哈希函数。对于connect 6，我不知道最好的散列函数是什么，这是你必须解决的问题。

要想从这样的事情中获得最好的性能，需要一大堆的修补工作，但希望这篇文章能给你一些想法。如果您希望我对任何内容进行扩展，请发表评论。

Answer 2

This MediocreChess文章详细解释了转置表。Zobrist algorithm创建转换表非常简单。

zobrist system用两个词表示：

1. 为每一对possible piece, possible cell生成一个随机数(假设32位)，并将它们存储在一个数组中。
2. 从hash=0开始，然后将散列与存储的每对已播放棋子的数字进行异或运算，已播放棋子的位置
3. 您将获得Zobrist密钥!

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

转置表系统为：

• 对于某个游戏位置，您使用Zobrist算法生成一个散列，这是游戏位置的签名，并获得一个整数(例如32位或64位)。
• 这个"zobrist key“可以直接用来在转置表中存储给定位置的最佳移动和得分。
• 但是你可能不想存储2^32或2^64个条目，所以你使用Zobrist键的”散列“来限制转置表的条目，假设2^16个游戏位置的16位(实际上它可能是>=2^20)。要获得这个散列，一个简单的方法是对zobrist密钥进行“模运算”，或者执行“二进制and”：

转置表索引= zobrist_key & 0xFFFF

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

让我们总结一下：

1. 对于给定的位置，计算zobrist键，然后计算zobrist键的散列，这将是转置表中的索引。让我们将重要的数据存储在这个表项中: score，best_move，zobrist_key，flag，depth。
2. 当你需要在转置表中查找时，计算给定游戏位置的zobrist键，然后计算它的散列，并获得相应的项。然后检查entry的zobrist key是否与您的相同，以避免“误报”的冲突问题。

因此，对于Connect6，您有2个石色，假设59x59个位置，因此您必须创建一个59x59x2 = 6962个随机数组。要在Zobrist键中编码一个游戏位置，取每一块石头，对于它的颜色和位置，取你生成的数字并将它们一起异或。将您的Zobrist键减少为一个索引(hash，二进制" and "，...)，并将您的数据存储在转置表中的此索引中。