换位表？

Question

我正在使用Minimax使计算机连接6.我也在使用Alpha-Beta修剪来加速算法.

我想添加一个转置表来使算法更快.我绝对没有经验.

有人可以解释换位表的基础知识,以及它们如何应用于Connect 6这样的游戏？指向有用资源的链接没问题.

我熟悉哈希表.

我找到了什么:

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

该链接给出了转置表的一个很好的解释,但完全集中在国际象棋上,因此难以弄清楚换位表如何独立于国际象棋.

Answer 1

首先是minimax算法,如果天真应用,必须为将来可能遇到的每个棋盘位置计算最佳游戏(在极小极大的意义上).Alpha beta-pruning有助于减少不必要的计算,因为如果您知道自己永远不会进行某种移动,那么您就不需要计算播放该移动的价值.

对于某些游戏,特定棋盘上的最佳游戏可以完全由该时刻的棋盘状态决定.国际象棋是这样的,所以去,其他一些游戏也是如此.关键的实现是,一旦你到达那个状态,你如何进入一个特定的游戏状态并不重要(从极小的角度来看).

具体地说,在棋的这种意义上的换位就是当你采取两种不同的移动路径从起始位置到终止位置时会发生什么.

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

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

如果connect6 是这个游戏也许一个例子会很好:

假设电路板像这样开始(位置A):

X 0 
0 X

有多个动作可以让你到达(位置B):

X 0 0 0
0 X X X
0 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,我不知道最好的散列函数是什么,这是你必须解决的问题.

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

Answer 2

这篇MediocreChess文章详细介绍了转置表.该佐布里斯特算法是非常简单的创建换位表.

该佐布里斯特系统中的两句话:

1. 为每一对[可能的片段,可能的单元格]生成一个随机数(比如32位)(对于tic-tac-toe它是2*9)并将它们存储在一个数组中.
2. 从hash = 0开始,并且对每一对[播放的片段,播放片段的位置]存储的数字进行散列XOR
3. 你获得了Zobrist钥匙!

这是一个非常好的系统,可以删除一块!你只需要再次对同一个号码进行异或.它对于negamax/alpha-beta算法非常有用,因为我们必须多次更改/恢复状态.保持Zobrist键是最新的很容易.

换位表系统是:

• 对于某个游戏位置,您使用Zobrist算法生成一个哈希值,这是游戏位置的签名,您将获得一个整数(例如32位或64位).
• 这个"zobrist键"可以直接用于存储转置表中给定位置的最佳移动和得分.

• 但是你可能不希望存储2 ^ 32或2 ^ 64个条目,所以你采用Zobrist键的"哈希"来限制转置表的条目,比如16比特用于2 ^ 16个游戏位置(实际上它可能> = 2 ^ 20).要获得此哈希,一个简单的方法是"模数"zobrist键,或执行"二进制和":

  转置表索引= zobrist_key和0xFFFF

您获得0到2 ^ 16-1之间的整数,这是转置表中的索引!当然,我们可以遇到碰撞,因此我们可以将完整的zobrist密钥存储在转置表中.

让我们总结一下:

1. 对于给定的位置,计算zobrist键,然后计算zobrist键的哈希值,它将是您的换位表中的索引.让我们在这个表条目中存储重要数据:score,best_move,zobrist_key,flag,depth.
2. 当你需要在转置表中查找时,计算给定游戏位置的zobrist键,然后计算它的哈希值,并获得相应的条目.然后检查条目的zobrist键是否与你的相同,以避免"误报"的碰撞问题.

所以对于Connect 6,你有2种石头色,让我们说59x59位置,所以你必须创建一个59x59x2 = 6962个随机数的数组.要对Zobrist键中的游戏位置进行编码,请取出每块石头,并根据其颜色和位置,取出您生成的数字并将它们混合在一起.将Zobrist密钥减少为索引(哈希,二进制"和",......),并将数据存储在转置表中的此索引处.