algorithm - 换位表？

Question

我正在使用 Minimax 使计算机播放连接 6。我还使用 Alpha-Beta 修剪来加速算法。

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

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

我熟悉哈希表。

我发现了什么:

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

该链接很好地解释了换位表，但完全专注于国际象棋，因此很难弄清楚换位表如何独立于国际象棋工作。

Answer 1

首先，如果天真地应用极小极大算法，则必须为您将来可能遇到的每个棋盘位置计算最佳玩法(在极小极大意义上)。 Alpha beta-pruning 有助于减少不必要的计算，因为如果您知道自己永远不会下某个 Action ，那么您就不需要计算下该 Action 的值(value)。

对于某些游戏，特定棋盘上的最佳玩法完全取决于棋盘当时的状态。国际象棋如此，围棋也是如此，其他一些游戏也是如此。关键的认识是，一旦您到达特定游戏状态，您如何到达特定游戏状态并不重要(从极小极大的角度来看)。

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

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

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

如果连接6 is this game也许一个例子会很好:

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

X 0 
0 X

有不止一组 Action 可以让你到达(位置 B):

X 0 0 0
0 X X X
0 X

假设有 n 种从位置 A 到位置 B 的方法，如果您天真地进行这种操作，您可能必须测试以在位置 B 找到最佳移动最多 n 次(取决于树的哪些分支 alpha-beta 修剪掉) .但如果我们不必对 B 板位置进行多次完全相同的计算，那真的会很棒，一次就足够了!

为了利用这个想法，您需要做的是找到一种表示连接 6 板位置的方法。我们可以代表董事会的一种方式就是拥有一个 N by N数组 where N是棋盘尺寸，只为每个单元格存储一个枚举值，如果它为空，则对应于 X在它或有一个 0在里面。然而，这种幼稚的方法并没有很好的查找位置的特性，因为我们总是会绕过这些讨厌的 N by N数组。更不用说必须总是存储很多这些 N by N数组会占用大量内存。

所以如果我们可以定义一个散列函数，它接受 N by N board 并将其映射到一个几乎唯一的整数，而无需大量处理开销，然后我们可以简化这个过程。散列一个板并查看它是否在表中应该希望以这种方式更快。

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

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