連接四個哈希函數：映射關閉元素以關閉哈希鍵

Question

我正在編寫一個Connect Four遊戲引擎。目前，我使用Zobrist hashing爲不同的Connect Four板位置生成散列鍵（爲了不再做同樣的事情，評估板位置存儲在散列表中）。評估板位置（最小最大樹中的節點）總是彼此接近。不幸的是，關閉的棋盤位置被映射到統一分佈的散列鍵，導致大量的cpu緩存未命中。

是否有可能建立一個散列函數來映射關閉板位置以關閉散列鍵？

一個玩家A板位置由以下結構的棋盤表示：

. . . . . . . TOP 
5 12 19 26 33 40 47 
4 11 18 25 32 39 46 
3 10 17 24 31 38 45 
2 9 16 23 30 37 44 
1 8 15 22 29 36 43 
0 7 14 21 28 35 42 

我不知道，如果它甚至有可能。 感謝您的幫助！

Answer 1

我不認爲這是可能的。一個好的散列鍵（如zobrist散列用於棋盤遊戲）很可能具有僞隨機屬性，以實現轉置表中鍵的均勻分佈。在表中，「關閉」位置的鍵彼此接近，這與此相矛盾。考慮到這一點：即使您將棋盤位置一對一地映射到（2^7-1）^ 7位置的表格，您也無法將「關閉」棋盤位置映射到關閉存儲位置：如果一個低指數的產品會發生變化，倉位將會接近，但是每個指數獲得的倉位差距會增加一倍，而高倉位將會有很多TB的差距;-)

作爲國際象棋引擎我知道這個問題。 AFAIK沒有人解決這個問題，每個人都使用zobrist哈希，也許稍做修改。

無論如何，祝你好運解決連接-4 ......我知道這之前已經完成，但它是更理想的做自我;-)

Answer 2

下面是如何修改想必幾乎均勻隨機哈希功能可以以類似的電路板位置有可能在附近的哈希中發生的方式對其進行偏置。

讓hash（gamestate）成爲你現有的函數。我們將創建一個newhash（gamestate），該hash用於隨機行爲使用散列，但對於密切相關的遊戲狀態而言，產生彼此靠近的散列的概率相當高。

讓棋盤狀態的'顏色'成爲下一個要移動的玩家。如果想找到白色播放器的散列鍵，使用newhash（board）= hash（board）。如果您想查找黑色位置的散列，請根據您的訂單查找最大數量的黑色碎片，比如在位置i。從遊戲狀態中移除我，並調用修改狀態probableparent然後使用newhash（board）= hash（probableparent）+ i。如果您按照可能的安排順序排列職位（更高的事情會晚一些作爲第一順序標準，也許中間位置會更早地作爲第二條標準？我真的不知道connect4的好策略），那麼有點可能在黑色轉彎之前的白色轉彎處於可能的狀態，因此在你的緩存中很好，因此我就在附近。此外，8種可能的黑色移動可能會共享相同的prev_board狀態，因此在哈希位置附近。

您可以擴展此想法，一次回滾多個層。說如果當前轉向％3 == 2，在板位置i和j上移除最大的兩個移動，然後使用newhash（board）= hash（board-two-removals-ago）+ i * 48 + j。