快速哈希化二维数组

Question

我正在使用标准的alpha beta剪枝搜索算法构建一个翻转棋玩家。我试图添加一个翻译表来存储搜索树中先前计算过的节点。因此，我需要对代表游戏板（即状态）的二维数组进行哈希，并为其存储一个值。

我只好使用双重循环迭代我的数组，并将所有值相加并乘以偏移量以获得唯一的哈希值。

@Override
public int hashCode() {
    if (dirtyHash) {
        int hash = 0;
        for (int i = 0; i < Board.SIZEX; i++)
            for (int j = 0; j < Board.SIZEY; j++)
                hash += board[i][j] * (i + Board.SIZEY * j);

        hashValue = hash;
        dirtyHash = false;
    }

    return hashValue;
}

我怀疑有更聪明的方法来完成这个任务？有人有什么想法吗？

- Johan Norén

---

board[i][j] 可能的值有哪些？Board.SIZEX 和 Board.SIZEY 有多大？ - Whatang

黑白棋盘非常适合使用64位整数进行表示 - 只是这么说一下。 - Sam Dufel

好观点，Sam。由于每个位置可以是空的/黑色的/白色的，我需要不止一个64位长整型，但也许需要两个长整型来表示占用情况，再加上一个表示颜色的长整型。Whatang：尺寸通常为8x8，但我希望能够普遍适用。但基本问题仍然存在（如果不涉及应用程序），如何高效地对数组进行哈希？ - Johan Norén

即使是一个8x8的黑白棋盘也无法用64位来表示，因为它们有三种状态：黑、白和空。你至少需要102位来完整描述这个系统。 - paradigmatic

将板子视为一个64位的三进制数。 - rossum

Sam怎么会在明显是虚假陈述的情况下得到三个赞成票？ - Fantius

Answer 1

作为第一次尝试，我会使用Java标准库：

int hash = java.util.Arrays.deepHashCode( board );

一旦一切正常运作，对整个应用程序进行性能剖析，以检查哈希码计算是否真的是性能瓶颈。

- paradigmatic

Answer 2

如果您想自己处理这个问题，以下是一种方法。

棋盘上每个单元格都有三个取值：空、黑、白。这意味着您可以在每个单元格上使用两个位。由于棋盘是 8x8 或者 64 个单元格，您可以使用两个 long 原语来编码棋盘。也许其中一个告诉您某个特定的单元格是否为空，如果不是，则另一个告诉您它的颜色。

您甚至不需要将此表示转换为二维数组。您可以直接在方法中对长整型数执行按位操作以处理棋盘。

哈希值可以是两个 long 的异或，或类似的东西。

- wberry

Answer 3

你应该使用Zobrist哈希来处理这个问题。它非常适用于棋盘游戏，并且可以在棋盘发生变化时进行增量更新，而不是每次都从头开始重新计算。这使得它非常高效。 http://en.wikipedia.org/wiki/Zobrist_hashing

- Fantius

Answer 4

我建议按照以下步骤操作：

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < Board.SIZEX; i++)
        for (int j = 0; j < Board.SIZEY; j++)
            hash = (hash) ^ ( (Math.pow(p,i)+Math.pow(p,j))* board[i][j]
    return hashValue;
}

对于大于32位的p和q素数，为什么会更快？

这个算法对于一个棋盘的计算是非常容易的：新棋局可以从旧的棋局中通过计算得到hash值=(hash) ^ ( (Math.pow(p,i)+Math.pow(p,j))* board[i][j]。而且不需要迭代整个棋盘，只需迭代改变过的棋子即可（如果您在棋盘上添加了一个黑棋子，则使用该黑色棋子的hash值，如果您将其从黑色变为白色，则将其从hash值中删除黑色棋子，然后再次添加白色棋子）。

- Fritz

---

如果p是32位质数且x >= 2，那么Math.pow(p, x)会填入int中吗？还是会溢出呢？ - ignis