遊戲樹換位表（連接4）

Question

我正在爲Android創建一個Connect 4應用程序，現在我正在使用一個極小極大算法，以及葉節點的alpha-beta prunning和啓發式評估函數。我還下令進一步最大限度地修剪過程。不幸的是，採用該策略時，該算法需要7秒的時間，導致我放棄它，轉而使用換位表。

現在，我已閱讀有關轉置表的信息，並已瞭解它們的工作原理，但我不確定如何繼續使用代碼中的實際實現。我不是Java專家，所以我需要任何幫助，你可以給我。

在我的遊戲中，我使用了一個int [42]數組作爲董事會職位。我想過使用哈希映射並存儲某種數據結構對象，其中每個對象都將包含棋盤位置（數組）和一個int「分數」變量（實際上這將是給予該位置的分數，評估函數）。但是，這意味着每次我想在桌子上放置一個新的棋盤位置時，我需要執行某種檢查來查看這個位置是否已經存在（??）。如果沒有，只能插入表格中？

我很樂意爲您提供有關此主題的任何技術幫助。如果需要的話，我可以提供一些代碼示例，但這是一個普遍問題，我認爲在這一點上它們確實不是必需的。

在此先感謝。

Answer 1

您可以使用來自象棋轉位表的技術：Zobrist散列法。基本上不是存儲整個板子，而是計算一個long作爲該位置的散列鍵，並將其與相關數據一起存儲。它具有可以逐步更新的額外好處。在進行移動時，不必從頭開始生成密鑰，您可以使用單個按位XOR操作（非常快）更新密鑰。

基本上，爲每個方塊（槽？）生成一些隨機數。你需要每一方都有一個。爲了便於索引，我假設black = 0和red = 1。初始化看起來像

long[][] zobrist = new long[42][2]; 
for (int square = 0; square < zobrist.length; square++) 
    for (int side = 0; side < zobrist[i].length; side++) 
     zobrist[square][side] = RandomLong(); 

你需要找到產生了RandomLong()隨機long一個PRNG。確保它在查看位時具有良好的隨機性。我建議不要使用LCG。

要從零開始計算位置的散列鍵，您只需將所有的zobrist值異或即可。

long computeKey(int[] board) { 
    long hashKey = 0; 
    for (int square = 0; square < board.length; square++) 
     if (hasPiece(board[square])) { 
     int side = getColour(board[square]); 
     hashKey ^= zobrist[square][side]; 
     } 
} 

要遞增更新，只需XOR移動的效果。這是您想要移動並更新密鑰的時候。

long updateKey(long oldKey, int moveSquare, int moveSide) { 
    return oldKey^zobrist[moveSquare][moveSide]; 
} 

要取消移動並獲取舊密鑰，上述功能也起作用！ XOR的行爲在邏輯上與否定行爲相似，因此應用兩次可以讓您恢復原始密鑰。