摘要：棋類游戲一般需要行數(shù)列數(shù)狀態(tài)數(shù)個(gè)狀態(tài)，以華容道為例，需要為個(gè)狀態(tài)分配編碼值。對(duì)于華容道游戲來(lái)說(shuō)，這種左右鏡像的情況對(duì)于滑動(dòng)棋子尋求結(jié)果的影響是一樣的。

此為《算法的樂(lè)趣》讀書筆記，我用javascript（ES6）重新實(shí)現(xiàn)算法。

華容道游戲看似簡(jiǎn)單，但求解需要設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜，還牽涉到棋類游戲的棋局判斷，所以整個(gè)過(guò)程還是挺費(fèi)勁的。我盡量用面向?qū)ο蟮乃枷雭?lái)進(jìn)行封裝，整個(gè)過(guò)程將分成幾個(gè)部分記錄下來(lái)，今天是第二部分，棋局處理Zobrist算法原理及實(shí)現(xiàn)。

Zobrist哈希算法是一種適用于棋類游戲的棋局編碼方式，通過(guò)建立一個(gè)特殊的轉(zhuǎn)換表，對(duì)棋盤上每一個(gè)位置的所有可能狀態(tài)賦予一個(gè)絕不重復(fù)的隨機(jī)編碼，通過(guò)對(duì)不同位置上的隨機(jī)編碼進(jìn)行異或計(jì)算，實(shí)現(xiàn)在極低沖突率的前提下將復(fù)雜的棋局編碼為一個(gè)整數(shù)類型哈希值的功能。

識(shí)別出棋局的最小單位（格子或交叉點(diǎn)），確定每個(gè)最小單位上的所有可能的狀態(tài)數(shù)。以華容道的棋局為例，最小單位就是20個(gè)小格子，每個(gè)格子有五種狀態(tài)，分別是空狀態(tài)、被橫長(zhǎng)方形占據(jù)、被堅(jiān)長(zhǎng)方形占據(jù)、被小方格占據(jù)和被大方格占據(jù)。

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

對(duì)指定的棋局，對(duì)每個(gè)單位上的狀態(tài)用對(duì)應(yīng)的編碼值（隨機(jī)數(shù)）做異或運(yùn)算，最后得到一個(gè)哈希值。

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

棋局發(fā)生變化時(shí)，不必對(duì)整個(gè)棋局重新計(jì)算哈希值，只需要計(jì)算發(fā)生變化的那些最小單元的狀態(tài)變化即可。

編碼表定義為一個(gè)三維數(shù)組。

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))      //對(duì)16位隨機(jī)整數(shù)值
                    }while(!tmp)                                    //跳過(guò)零值
                    this.zobHash[i][j].push(tmp)
                }
            }
        }
    }
    get(i,j,k){                                                   //get接口
        return this.zobHash[i][j][k]
    }
}

對(duì)棋盤的格子逐個(gè)處理，根據(jù)棋盤格子的武將信息獲取武將的類型，從而獲取該類型對(duì)應(yīng)的編碼值，用此編碼值參與哈希值進(jìn)行異或運(yùn)算。

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;                    //取得格子上武將序號(hào)
            let type = (index >= 0 && index < heroes.length) ? heroes[index].type : 0;                                           //數(shù)組索引值超出范圍，定為零
            hash ^= zobHash.get(i - 1,j - 1,type);                //異或計(jì)算
            // console.log(index+"--"+type+"--"+zobHash[i - 1][j - 1][type]+"<=>"+hash)
        }
    }
    return hash;
}

棋盤狀態(tài)左右鏡像問(wèn)題：兩個(gè)棋局雖然武將的位置不一樣，但是如果忽略武將的名字信息，單純從形狀上看是左右對(duì)稱的鏡像結(jié)構(gòu)。對(duì)于華容道游戲來(lái)說(shuō)，這種左右鏡像的情況對(duì)于滑動(dòng)棋子尋求結(jié)果的影響是一樣的。

鏡像即左右對(duì)稱，進(jìn)行一個(gè)坐標(biāo)變換即可得到。

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))       坐標(biāo)變換
            hash ^= zobHash.get(i - 1,HRD_GAME_COL - j,type);
        }
    }
    return hash;
}

設(shè)計(jì)了三個(gè)棋局，測(cè)試目標(biāo)：同一個(gè)棋局的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))    //兩值相等

代碼托管在開(kāi)源中國(guó)，其中的hyd.js即華容道解法。

https://gitee.com/zhoutk/test

盡量使用面向?qū)ο蟮乃枷雭?lái)解決問(wèn)題，讓數(shù)據(jù)和操作綁定在一起，努力使代碼容易看懂。