javascript - 在 Javascript 中实现 Zobrist 哈希

Question

我需要在 Javascript 中为国际象棋引擎实现 Zobrist 哈希，我想知道实现此目的的最佳方法是什么。现在，我不是计算机科学家，也从未上过正式的算法和数据结构类(class)，所以如果我在这方面有点偏离，我很抱歉......

据我了解，我需要一个 64 位哈希函数来编码低于该位置的位置，从而引发太多冲突。现在在 javascript 中我只能访问 32 位数字。另外，还有一个问题是我如何实现哈希表，以及节点中的 V8 引擎如何“在幕后”实现它。

我可以将它作为长度为 TABLESIZE 的 javascript 数组，并执行以下操作:

var table = new Array();

table[hashCodeLo % TABLESIZE] = {
    hashCodeLo: hashCodeLo,
    hashCodeHi: hashCodeHi,
    someProperty: someValue
};

其中 hashCodeLo 和 hashCodeHi 表示代码的高 32 位和低 32 位，并且 TABLESIZE < 2^32。我存储这些是为了检测执行 % TABLESIZE 位时发生的冲突。现在我猜测，由于 TABLESIZE 很大，而且我分配的元素不连续，V8 无论如何都会将其踢入“字典模式”，所以我也可能不费心将其设为由最大 TABLESIZE 的整数索引的数组，而是执行类似的操作:

var table = {};

table[hashCode] = {
    someProperty: someValue
}

这里的 hashCode 只是我的 64 位 hashCode 的字符串表示形式。由于我不确定“词典模式”在幕后是如何工作的，所以我不确定哪个更好。另外，我不知道使用“1983981918391”等键与使用更紧凑的表示(如:

)是否使用了更多内存

hashCode = String.fromCharCode(FIRST_16BITS, SECOND_16BITS, THIRD_16BITS, FOURTH_16BITS)

我什至不确定这是否按照我的预期工作......

由于这是引擎的关键部分，我希望从中获得尽可能多的性能，因此非常感谢您的帮助。

Answer 1

From what I understand I need a 64 bit hashfunction to encode a position as lower than that originates too many collisions.

不适用于 transposition table至少 - 它的大小几乎不会达到 2⁶⁴。

如果您要实现此功能来对位置本身进行编码(并通过比较 64 位哈希来检测一些冲突)，那么是的，您可以使用 64 位，如果这是文献建议的(尽管您可能想尝试)也是 52 位)。

Now in javascript I only have access to 32 bits numbers.

没有。 JavaScript 中的数字是 64 位 float ，最多可以精确存储 52 位整数。只有按位运算符仅限于 32 位整数(如有必要，数字将转换为整数)。

但是，数组本身的长度限制为 2³²；但即使这样也应该足够了。

Also there is an issue with how I implement the hash table and how it gets implemented "behind the scenes" by the V8 engine in node.

只需将其实现为数组即可。尝试用 null 值填充它以进行初始化，并查看非稀疏数组是否表现更好。如果您关心性能，请测试它。

hashCodeLo and hashCodeHi denote the higher and lower 32 bits of the code and TABLESIZE < 2^32. I store these to detect collisions

我会使用Uint32Array而不是对象数组。根据 someProperty 和 someValue 的内容，您可能只想将对象的索引存储在普通数组中，或者标量本身(可能使用 DataView ) 。代码可能如下所示:

var zobrist = new Uint32Array(13 * 2 * 64 * 2) // pieces * colors * fields * 64/32
for (var i=0; i<zobrist.length; i++)
    zobrist[i] = Math.random() * 4294967296;

var table = new Uint32Array(3 * tablesize);

function hash(hi, lo, piece, color, field) {
    hi ^= zobrist[piece * 128 + color * 64 + field];
    lo ^= zobrist[piece * 128 + color * 64 + field + 1];

    var i = lo % tablesize;
    if (table[i] == hi && table[i+1] == lo) {
        // collision
    } else {
        table[i] = hi; table[i+1] = lo;
        // do what you want with table[i+2]
    }
}