使用哈希减少重复计算

[calcitem]

考虑：

根據局面得到唯一的整數，沒有求餘

int hashInt(position pos) { 
      return pos.board[0] * 2.4e7 + pos.board[1] * 1.2e7
            + pos.board[2] * 2.4e6 + pos.board[3] * 1.2e6
            + pos.board[4] * 2.4e5 + pos.board[5] * 1.2e5
            + pos.board[6] * 2.4e6 + pos.board[7] * 1.2e4
            + pos.board[8] * 2.4e3 + pos.board[9] * 1.2e3
            + pos.board[10] * 2.4e2 + pos.board[11] * 1.2e2
            + pos.player * 24 + pos.lastmove * 12;
}

是否可用？

[ejmoog]

經思考，如果用位運算的話，一個long long可以表示一個獨特局面

long long有八個字節byte，每個byte有8個bit，4個bit可表示一個12（含）以下的數字或0，則前六個字節能用來表示board。 第七個字節就表示player，第八個字節就是lastmove。

lastmove只記錄run（1到12）。如果是落子，不管落哪一個，不管是誰落，都記成15。如果是對方上一步放棄行動，則記成14。如果是初始局面則是0。

[calcitem]

非常好，就是这样，如果实现了，一定快到飞起！

[calcitem]

甚至局面的哈希用每2个字节异或出来就行。

[ejmoog]

非常好，就是这样，如果实现了，一定快到飞起！

不過好像第一種方法也不是很差？因為第一種方法好像也能得到一個唯一的int（4字節），而剛才我想的方法是long long（8字節）。

並且longlong的方法，把每個棋子的數字轉到2進制再位運算<<，感覺也挺複雜？

第一種方法的「2.4」應改成「19」，「1.2」應改成「17」，都要是質數且不等於1~12。

[calcitem]

不是“转换”成2进制计算，是全程都用2进制来存储，只有最后算出结果呈现给玩家的最后时刻才转。

移位运算，异或等位运算是非常快的，只要CPU一个指令就搞定。

[calcitem]

加法和乘法指令比位运算指令慢，因为加法和乘法需要更多的时钟周期来执行。具体效率差距取决于具体的处理器和实现细节，但一般来说，加法和乘法指令可能需要数个时钟周期来执行，而位运算指令可能只需要一个时钟周期或者少于一个时钟周期来执行。

这种效率差距的原因是因为加法和乘法需要更多的操作，例如进位和乘法的积累，而位运算只需要在位级别上移动和操作二进制位。因此，当需要高性能的操作时，位运算指令通常比加法和乘法指令更受欢迎。

[ejmoog]

加法和乘法指令比位运算指令慢，因为加法和乘法需要更多的时钟周期来执行。具体效率差距取决于具体的处理器和实现细节，但一般来说，加法和乘法指令可能需要数个时钟周期来执行，而位运算指令可能只需要一个时钟周期或者少于一个时钟周期来执行。

这种效率差距的原因是因为加法和乘法需要更多的操作，例如进位和乘法的积累，而位运算只需要在位级别上移动和操作二进制位。因此，当需要高性能的操作时，位运算指令通常比加法和乘法指令更受欢迎。

那就盡可能多的採用二進制。

現在是在弄picees，當前方案是 把 vector stick[2] = {}; 做成 int8_t stick2[2][7] = {{0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}};

是否也乾脆使用uint64_t？直接這樣： uint64_t stick = 0;

[calcitem]

从数字电路的角度来看，加法和乘法指令与位运算指令之间的效率差异可以归结为以下几个因素：

逻辑门数：加法和乘法指令需要使用更多的逻辑门来实现，因为它们需要执行更复杂的运算。相比之下，位运算指令只需要相对简单的逻辑门来实现。

时钟周期：加法和乘法指令需要多个时钟周期来完成，因为它们需要执行多个逻辑操作。相比之下，位运算指令通常只需要一个时钟周期来完成。

电路延迟：由于加法和乘法指令需要使用更多的逻辑门和时钟周期，它们的电路延迟更高。相比之下，位运算指令的电路延迟较低。

总的来说，加法和乘法指令相对于位运算指令来说更复杂，需要更多的逻辑门和时钟周期，因此其电路延迟更高。这使得加法和乘法指令的执行速度更慢。相比之下，位运算指令由于使用较少的逻辑门和时钟周期，其电路延迟较低，从而实现了更高的执行速度。

就这个场景而言，对运算速度的需求是远远大于内存占用的需求的。而且，当存到哈希表时，可以将8个字节通过异或的方式缩短到2个字节来显著减少这种影响。

[calcitem]

直接用 uint64_t。

[calcitem]

具体可以参考：https://github.com/calcitem/chaosclock/blob/dev/src/bitboard.h

[ejmoog]

8个字节通过异或的方式缩短到2个字节来显著减少这种影响。

異或仍能夠保證無重嗎？

[calcitem]

8个字节通过异或的方式缩短到2个字节来显著减少这种影响。

異或仍能夠保證無重嗎？

问题问得好，要保险起见，可以移位后再异或减少重复，或者用Zobrist算法是随机性很强最保险，但是比特棋盘还是一定得有，和哈希两者结合起来运用。

[ejmoog]

8个字节通过异或的方式缩短到2个字节来显著减少这种影响。

異或仍能夠保證無重嗎？

问题问得好，要保险起见，可以移位后再异或减少重复，或者用Zobrist算法是随机性很强最保险，但是比特棋盘还是一定得有，和哈希两者结合起来运用。

是否一定要縮短到4字節或2字節？如果8字節本身是無重的話，是否可以考慮直接使用8字節？

[calcitem]

可以这样，将完整的8字节数据存储到2字节对应的内存地址里，哈希匹配的时候，从内存地址中取数据后，检查一下取到的完整8字节是否相等，如果是，就认为真正碰撞了，如果没有就算是有重复了，就不用哈希表拿到的数据，而是重新计算评估值。直棋现在就是用这个方法。

[calcitem]

8字节只能用于计算但不能作为存储地址，用8字节直接当内存地址的话，可以算下2的64次方是多大内存，天文数字。

[ejmoog]

如何圈定一個內存區域來做哈希排重？

本機某個值的地址是：0x7ffeb93f609c

我只用到前七個F，則還有五個bype可以規劃。

c++能否找到一塊0x????? 0000000~0x????? FFFFFFF 是專門給我保存局面用的地址？

[ejmoog]

圈定內存區域

Model: Default

admin@openai.com 如何圈定一個內存區域來做哈希排重？

c++能否找到一塊0x????? 0000000~0x????? FFFFFFF 是專門給我保存局面用的地址？

要圈定一個內存區域來做哈希排重，可以使用C++中的指針來實現。首先，可以使用new運算符來動態分配一塊內存區域，然後使用指針變量來保存該內存區域的起始地址。例如，下面的代碼動態分配了一塊大小為1000字節的內存區域，並使用指針變量ptr保存了該區域的起始地址：

char* ptr = new char[1000];

然後，可以在這個內存區域中實現哈希排重算法。需要注意的是，由於哈希排重算法需要頻繁地訪問內存，因此在實現哈希排重算法時需要關注內存的性能和效率。

至於問題中提到的能否找到一塊0x????? 0000000~0x????? FFFFFFF是專門給你保存局面用的地址，需要更多的上下文信息來確定。如果這是一個固定的內存區域，可以使用指針變量來保存其起始地址，就像上面的例子一樣。如果這是一個動態分配的內存區域，則需要確定其分配方式和內存管理方式，以確定如何訪問該內存區域。

[calcitem]

AI回答偏了。这个需要问得更细一些才能拿到准确的回答。

[calcitem]

不过AI回答大体上也没问题，只是不够细。总体而言就是new一块内存比如1GB大小，因为内存大小有限，所以0x7ffeb93f609c需要转换为一个更小的内存地址值，比如舍弃掉高N位，保留低N位，要舍弃多少需要计算一下，取决于1GB能存多少组数据，每组数据占用的字节数需要算下。

[ejmoog]

8字節一個局面。

char* ptr = new char[1024]; //1kb

1k的內存就有128個局面。

1m的內存就有128*1024=131072個局面。

申請個100M？

[ejmoog]

0x7ffe b000 0000 ~ 0x7ffe bfff ffff 這個要申請多大的空間？

[calcitem]

十六进制地址范围0x7ffeb0000000到0x7ffebfffffff所代表的内存区域大小为16GB（Gigabytes），换算成十进制为140,737,488,391,168字节。

[ejmoog]

我聲明了一個指針： uint8_t *ptr;

我有一個內存地址的值： 0x7f2a81cce011;

我現在希望ptr指向這個內存地址。可否做到？

[calcitem]

不可以。绝对内存地址是操作系统管理的，用户无权任意写入。只能从操作系统中申请一块指定大小的内存，拿到这块内存的首地址，然后首地址加上指定的偏移量（不允许越界访问），把数据存到这个地方。

[calcitem]

可参考 https://github.com/calcitem/Sanmill/blob/master/src/hashmap.h

[calcitem]

准确而言，ptr指向这个地址 0x7f2a81cce011 是可以做的，赋值就行。但是大概率不能直接往里面写数据，会因非法访问内存而导致程序崩溃。而且 0x7f2a81cce011 这个值非常大，为127TB，远远大于PC的内存大小（估计你笔记本就4G-8G大小吧？），所以肯定是写不进去的。

所以，如前面帖子所提到的，必须作截断，比如只保留高N位或低N位，或者作异或，具体需要根据数据的特征以及申请的buffer大小而定，注意地址要尽量随机化，缩小地址值后，写入就不会越界了。写入的地址必须是申请的内存块的首地址加上这个偏移量。

[ejmoog]

我已經申請到了0x7f2a81cce011~0x7f2a91cce011的空間，在我的內存裏，大小為24M。

則可直接用內存地址偏移量來存取唯一局面。

[ejmoog]

只是不知道這麼大的數字的加法，會不會耗費很大？

[calcitem]

不会，在相同位数的情况下，加法的效率和数字大小没关系，只取决于调用了几次加法。这里只有一次。

之所以拿到这么大的地址值，超过物理内存大小，是因为操作系统分配出的内存的地址是虚拟内存地址，不是物理内存地址，虚拟内存地址是可能会超过物理内存大小的。比方说，如果操作系统约定堆地址都从0x7f开头，那么这个值就是肯定很大了，操作系统内部处理时会映射成物理地址。

[calcitem]

以上是假定都是相同位数的计算的比较。

从硬件底层的角度看，大数字的加法通常需要更多的处理器时间和更大的内存来完成计算，因此可能会影响性能。

在现代计算机中，加法操作通常是通过硬件电路完成的，这些电路可以在非常短的时间内执行加法操作。但是，当数字的位数增加时，计算机必须执行更多的操作，以便在电路中正确地执行加法操作。

因此，对于数字大的加法操作，可能需要更长的时间来完成计算，这可能会导致性能下降。不过，现代计算机的处理速度和内存容量已经足够强大，可以轻松处理大数字的加法操作，所以在实际应用中，这种性能差异很少会被感知到。

但是，在规定所有数字都是64位计算的情况下，对于小数字和大数字的加法操作，从硬件底层的角度来看，性能差异将会非常小甚至可以忽略不计。

这是因为现代计算机的处理器和内存都已经非常快和高效，可以轻松处理64位数字的加法操作。此外，计算机硬件还针对不同的数字大小优化了不同的算法和电路设计，以确保在任何数字大小情况下都能提供高效的加法操作。

因此，当所有数字都是64位计算时，从硬件底层的角度来看，小数字和大数字的加法操作将非常接近，性能差异可以忽略不计。

如果将数字缩减到32位或16位，从硬件底层的角度来看，加法计算的效率可能会提高，因为缩短数字的位数会减少计算机执行加法操作所需的处理器时间和内存开销。

在处理32位或16位数字的加法操作时，计算机需要执行的操作数量比处理64位数字的加法操作要少得多，这将导致加法操作的执行速度更快。此外，缩短数字的位数还可以减少内存占用，因为32位和16位数字占用的内存比64位数字少得多。

不过，缩减数字位数也会降低数字的精度和表示范围，可能会导致数字溢出或精度丢失等问题。因此，需要在计算效率和数字精度之间进行权衡，选择最适合特定应用场景的数字位数。

[ejmoog]

我也不是特別關心地址的序，我只關心有沒有足夠的量。

0x7f2a81cce011這個只是它某次分配給我的一個地址。每一次都是不同的地址。

24M內存還是給得起的，並且每次我用完都會delete。

請問即使不delete，程序停止時也是會自動釋放內存的吧？

[calcitem]

在这片申请的大内存中存数据，直接赋值就行，不用在内部new和delete，需要做的就是指针偏移到指定位置，写入就行。

只需要在程序开头初始化这片内存，应该不需要反复new，否则会显著影响效率。因为new操作的开销非常大，操作系统内部会进行非常复杂的操作才能new出来给用户用。

最后退出程序前，需要delete这一大块new出来的内存。

[calcitem]

如果感兴趣，后面可以阅读这篇

https://zhuanlan.zhihu.com/p/367386292

用通俗有趣的风格讲解了为什么 new 内存的开销如此之大。

[ejmoog]

我將一個uint64_t的bit打印如下： 0000000000001000000000000010000001111100101001011011000100110100

方陣如下：pos.board 00000000 00001000 00000000 00100000 01111100 10100101 10110001 00110100

我以為它不會大於七個f

但現在我發現我好像搞錯了！

每一行相當於兩個f，就一共有14個f！

那就不止24M這麼少了…

[ejmoog]

要想一個離散性能好的哈希函數才行…

[ejmoog]

暫時想到，把uint64_t的一半跟另一半異或，如果已存有值則加1。

[calcitem]

看来 Zobrist 算法应该是必须的。

[calcitem]

暫時想到，把uint64_t的一半跟另一半異或，如果已存有值則加1。

不用加1。加1后就乱套了。已有值就直接更新掉它。

[ejmoog]

看来 Zobrist 算法应该是必须的。

對於混亂時鐘的zobrist如何弄？

[ejmoog]

用12*12個質數，不同數字出現在不同地方，都加上一個特別的質數。

不過仍不能保證不會重合，比如：

2+5+7=3+11=14

看來「質數」也不是相加了不重合的保證。

仍在思考中…

[calcitem]

不要用加法，用Zobrist基本只需要位运算即可。参考 https://www.xqbase.com/computer/struct_zobrist.htm

[ejmoog]

不要用加法，用Zobrist基本只需要位运算即可。参考 https://www.xqbase.com/computer/struct_zobrist.htm

用zobrist算法，通過異或得到一個60位的隨機數，那是否應截斷至32位，然後把value保存到一個空間大小為0xffffffff的數組中？

[calcitem]

32位还是64位，决定了随机性也就是碰撞的概率。对这个游戏应该都关系不大，32位的随机性也很好了。直棋用的是32位因为局面数比较少，国际象棋程序用的肯定是要64位。

另外，为啥是得到60位的随机数？

[calcitem]

你算下2的32次方是多大内存？512MB，还不止，因为要乘以每个单元的内存大小，就是4GB！

所以数组空间大小肯定要继续截断！截断后每个单元存的不止是局面，还要存32位或64位的哈希值用于判断局面是否真的匹配！所以基于此再算算需要多大内存，决定要截取多少位！

[ejmoog]

你算下2的32次方是多大内存？512MB，还不止，因为要乘以每个单元的内存大小，就是4GB！

所以数组空间大小肯定要继续截断！截断后每个单元存的不止是局面，还要存32位或64位的哈希值用于判断局面是否真的匹配！所以基于此再算算需要多大内存，决定要截取多少位！

是否考慮暫時先不判斷匹配？

如果要判斷的話，那局面本身就是一個uint64，因此，感覺截斷到24位都可以？

60位隨機數是你給的那篇文章說的。

[calcitem]

可以，先不判断匹配，看下效果。

话说 https://www.xqbase.com/computer/struct_zobrist.htm 哪里提到60位呀？不是64位吗？

生成60位反而不如64位快，因为还需要作截断。

[ejmoog]

可以，先不判断匹配，看下效果。

话说 https://www.xqbase.com/computer/struct_zobrist.htm 哪里提到60位呀？不是64位吗？

生成60位反而不如64位快，因为还需要作截断。

是64位，我後來發現它把五個隨意數合並，原以為只有四個，如果有四個，就是60位。

據我個人實驗，rand()産生的是32位的隨機數，也有可能有時是31位（可能最高位是0）。

這篇文章說rand() 産生的是15位的隨機數，我懷疑它是時代的産物（32位機？）。

[calcitem]

我後來發現它把五個隨意數合並，原以為只有四個，如果有四個，就是60位。

没懂...😂

據我個人實驗，rand()産生的是32位的隨機數，也有可能有時是31位（可能最高位是0）。

本质上是64位。整数数据类型位数只可能是2的n次幂。

這篇文章說rand() 産生的是15位的隨機數，我懷疑它是時代的産物（32位機？）。

可能吧。你的本意是指16位机？我不记得 现在的rand是多少位了。好像是32。

[ejmoog]

在C语言中，“rand()”函数返回一个15位的值(0~32767)，所以要得到64位的随机数还需要再加工一下。实际上我已经为你做好了，这个64位随机数的函数是： 　 U64 rand64(void) { 　return rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^ ((U64)rand() << 45) ^ ((U64)rand() << 60); }

[calcitem]

那么很可能当时是16位机器。