摘要：棋類游戲一般需要行數列數狀態數個狀態，以華容道為例，需要為個狀態分配編碼值。對于華容道游戲來說，這種左右鏡像的情況對于滑動棋子尋求結果的影響是一樣的。

此為《算法的樂趣》讀書筆記，我用javascript（ES6）重新實現算法。

華容道游戲看似簡單，但求解需要設計的數據結構比較復雜，還牽涉到棋類游戲的棋局判斷，所以整個過程還是挺費勁的。我盡量用面向對象的思想來進行封裝，整個過程將分成幾個部分記錄下來，今天是第二部分，棋局處理Zobrist算法原理及實現。

Zobrist哈希算法是一種適用于棋類游戲的棋局編碼方式，通過建立一個特殊的轉換表，對棋盤上每一個位置的所有可能狀態賦予一個絕不重復的隨機編碼，通過對不同位置上的隨機編碼進行異或計算，實現在極低沖突率的前提下將復雜的棋局編碼為一個整數類型哈希值的功能。

識別出棋局的最小單位（格子或交叉點），確定每個最小單位上的所有可能的狀態數。以華容道的棋局為例，最小單位就是20個小格子，每個格子有五種狀態，分別是空狀態、被橫長方形占據、被堅長方形占據、被小方格占據和被大方格占據。

為每個單位上的所有狀態都分配一個隨機的編碼值。棋類游戲一般需要“行數×列數×狀態數”個狀態，以華容道為例，需要為5×4×5=100個狀態分配編碼值。

對指定的棋局，對每個單位上的狀態用對應的編碼值（隨機數）做異或運算，最后得到一個哈希值。

沖突概率小，只要隨機編碼值的范圍夠大，棋局哈希沖突的概率非常小，實際應用中基本上不考慮沖突的情況。

棋局發生變化時，不必對整個棋局重新計算哈希值，只需要計算發生變化的那些最小單元的狀態變化即可。

編碼表定義為一個三維數組。

class Zobrist{
    constructor(){                                                    //三維表屬性
        this.zobHash = []
        for(let i = 0; i < HRD_GAME_ROW; i++)                        //初始化
        {
            this.zobHash.push([])
            for(let j = 0; j < HRD_GAME_COL; j++)
            {
                this.zobHash[i].push([])
                for(let k = 0; k < MAX_WARRIOR_TYPE; k++)
                {
                    do{
                        var tmp = Math.random()
                        tmp = Math.floor(tmp * Math.pow(2,15))      //對16位隨機整數值
                    }while(!tmp)                                    //跳過零值
                    this.zobHash[i][j].push(tmp)
                }
            }
        }
    }
    get(i,j,k){                                                   //get接口
        return this.zobHash[i][j][k]
    }
}

對棋盤的格子逐個處理，根據棋盤格子的武將信息獲取武將的類型，從而獲取該類型對應的編碼值，用此編碼值參與哈希值進行異或運算。

function getZobristHash(zobHash, state)
{
    let hash = 0;
    let heroes = state.heroes;
    for(let i = 1; i <= HRD_GAME_ROW; i++) 
    {
        for(let j = 1; j <= HRD_GAME_COL; j++) 
        {
            let index = state.board[i][j] - 1;                    //取得格子上武將序號
            let type = (index >= 0 && index < heroes.length) ? heroes[index].type : 0;                                           //數組索引值超出范圍，定為零
            hash ^= zobHash.get(i - 1,j - 1,type);                //異或計算
            // console.log(index+"--"+type+"--"+zobHash[i - 1][j - 1][type]+"<=>"+hash)
        }
    }
    return hash;
}

棋盤狀態左右鏡像問題：兩個棋局雖然武將的位置不一樣，但是如果忽略武將的名字信息，單純從形狀上看是左右對稱的鏡像結構。對于華容道游戲來說，這種左右鏡像的情況對于滑動棋子尋求結果的影響是一樣的。

鏡像即左右對稱，進行一個坐標變換即可得到。

function getMirrorZobristHash(zobHash, state)
{
    let hash = 0;
    let heroes = state.heroes;
    for(let i = 1; i <= HRD_GAME_ROW; i++) 
    {
        for(let j = 1; j <= HRD_GAME_COL; j++) 
        {
            let index = state.board[i][j] - 1;
            let type = (index >= 0 && index < heroes.length) ? heroes[index].type : 0;
            //(HRD_GAME_COL - 1) - (j - 1))       坐標變換
            hash ^= zobHash.get(i - 1,HRD_GAME_COL - j,type);
        }
    }
    return hash;
}

設計了三個棋局，測試目標：同一個棋局的Zobrist哈希與鏡像哈希相等，鏡像棋局的Zobrist哈希與其鏡像哈希相等。

var zobHash = new Zobrist()
var gameState = new HrdGameState()
var gameStateL = new HrdGameState()
var gameStateR = new HrdGameState()
var hs = [new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),
          new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,2),
          new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,2),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)
]
var hsl = [ new Warrior(WARRIOR_TYPE.HT_BOX,0,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,2,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
            new Warrior(WARRIOR_TYPE.HT_HBAR,0,2),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,2,2),
            new Warrior(WARRIOR_TYPE.HT_VBAR,3,2),
            new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,1,4),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,3,4)
]
var hsr = [ new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,1,0),
            new Warrior(WARRIOR_TYPE.HT_BOX,2,0),
            new Warrior(WARRIOR_TYPE.HT_VBAR,0,2),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,1,2),
            new Warrior(WARRIOR_TYPE.HT_HBAR,2,2),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
            new Warrior(WARRIOR_TYPE.HT_VBAR,3,3),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,0,4),
            new Warrior(WARRIOR_TYPE.HT_BLOCK,2,4)
]
gameState.initState(hs)
gameStateL.initState(hsl)
gameStateR.initState(hsr)
console.dir(getZobristHash(zobHash,gameStateL) + "--" + getMirrorZobristHash(zobHash,gameStateR))    //兩值相等

代碼托管在開源中國，其中的hyd.js即華容道解法。

https://gitee.com/zhoutk/test

盡量使用面向對象的思想來解決問題，讓數據和操作綁定在一起，努力使代碼容易看懂。