在Javascript中实现Zobrist哈希 [英] Implementing Zobrist hashing in Javascript

问题描述

我需要在Javascript中为国际象棋引擎实现Zobrist哈希，我想知道实现此目标的最佳方法是什么.现在，我不是计算机科学家，也从来没有正式的算法和数据结构类，所以对不起，我对此感到抱歉...

I need to implement Zobrist hashing for a chess engine in Javascript and I'm wondering what is the best way of accomplishing this. Now, I'm not a computer scientist and never had formal algorithms and data structures classes so I'm sorry if I'm a bit off on this...

据我了解，我需要一个64位哈希函数将一个位置编码为低于该位置的位置，以免产生太多的碰撞.现在，在javascript中，我只能访问32位数字.还有一个问题是如何实现哈希表以及如何通过节点中的V8引擎在后台实现哈希表.

From what I understand I need a 64 bit hashfunction to encode a position as lower than that originates too many collisions. Now in javascript I only have access to 32 bits numbers. 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.

我可以将其作为长度为TABLESIZE的javascript数组，并执行类似的操作:

I can either have it as a javascript array of length TABLESIZE and do something like:

var table = new Array();

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

其中hashCodeLo和hashCodeHi表示代码的高32位和低32位，而TABLESIZE< 2 ^ 32.我将它们存储起来，以通过执行％TABLESIZE位来检测冲突.现在我正在猜测，因为TABLESIZE很大，并且我不连续地分配元素，V8仍将其踢入字典模式"，因此我不应该麻烦地使其成为由TABLESIZE之前的整数索引的数组，而是执行类似的操作:

where hashCodeLo and hashCodeHi denote the higher and lower 32 bits of the code and TABLESIZE < 2^32. I store these to detect collisions from doing the % TABLESIZE bit. Now I'm guessing since TABLESIZE is large and I'm assigning elements non contiguously V8 will kick this into "dictionary mode" anyways so I might as well not bother making it an array indexed by an integer up to TABLESIZE and instead do something like:

var table = {};

table[hashCode] = {
    someProperty: someValue
}

这里的hashCode只是我的64位hashCode的字符串表示形式.由于我不确定词典模式"在幕后的工作方式，因此我不确定哪个更好.而且我也不知道是否通过使用像'1983981918391'这样的键与像这样的更紧凑的表示形式来使用更多的内存:

where here hashCode is just a string representation of my 64 bits hashCode. Since I'm not sure how "dictionary mode" works behind the scenes I'm not sure which is better. Also I don't know if I'm using more memory by using keys like '1983981918391' vs a more compact representation like:

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

我什至不确定这是否可以按照我的意图工作...

I'm not even sure if this works the way I intend...

由于这是引擎的关键部分，因此我想尽可能地发挥性能，因此能提供帮助.

Since this is a critical part of the engine I want to squeeze as much performance as I can out of this so any help is appreciated.

推荐答案

据我了解，我需要一个64位哈希函数将一个位置编码为低于该位置，从而导致发生过多的碰撞.

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

至少不用于换位表-它几乎没有2 ⁶⁴ .

Not for the transposition table at least - it will hardly have a size of 2⁶⁴.

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

If you're implementing this to encode the positions themselves (and detect some of the collisions by comparing the 64-bit hash), then yes you can use 64 bits if that is what literature recommends (though you might want to try 52 bits as well).

现在在javascript中，我只能访问32位数字.

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

不. JavaScript中的数字是64位浮点数，您可以在其中精确存储最多52位整数.仅按位运算符限制为32位整数(如有必要，数字将被强制转换为整数).

No. Numbers in JavaScript are 64-bit floats, and you can store up to 52-bit integers in them precisely. Only the bitwise operators are limited to 32-bit integers (to whom the numbers will be casted if necessary).

但是，数组本身的长度限制为2 ³² ；甚至这还绰绰有余.

However, arrays themselves are limited to a length of 2³²; yet even this should be more than enough.

另外，我如何实现哈希表以及如何通过节点中的V8引擎在幕后"实现哈希表.

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值填充它以进行初始化，并查看非稀疏数组的性能是否更好.如果您关心性能，请测试.

Just implement is as an array. Try to fill it with null values for initialisation and see whether a non-sparse array performs better. If you care about performance, test it.

hashCodeLo和hashCodeHi表示代码的高32位和低32位，而TABLESIZE< 2 ^ 32.我将其存储以检测碰撞

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的不同，您可能只想将对象的索引存储在普通数组或标量本身中(可能使用

I'd use a Uint32Array instead of an array of objects. Depending on what someProperty and someValue are, you might want to just store an index of an object in a normal array, or a scalar itself (possibly using a DataView). The code might look like this:

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]
    }
}

这篇关于在Javascript中实现Zobrist哈希的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！