摘要：華容道游戲看似簡(jiǎn)單，但求解需要設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜，還牽涉到棋類游戲的棋局判斷，所以整個(gè)過(guò)程還是挺費(fèi)勁的。

此為《算法的樂(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)，今天是最后一部分，棋局的廣度搜索。

棋局的搜索空間是一個(gè)樹狀關(guān)系空間，廣度優(yōu)先搜索能夠首先找到最優(yōu)解，因?yàn)槭紫日业降慕馍疃仁亲顪\的。

我們對(duì)算法的要求是：給定一個(gè)華容道游戲的開局布局，可以得到這個(gè)開局的所有解決方法以及相應(yīng)的武將移動(dòng)步驟，要求算法具有能用性，能處理任何一種開局的華容道游戲。

class HrdGame{
    constructor(caoIdx, heroes){                
        this.caoIdx = caoIdx;                        //曹操在武將列表中的序號(hào)
        var startState = new HrdGameState();         //新建開局棋局
        startState.initState(heroes)                 //開局棋局初始化
        this.states = []                             //存儲(chǔ)所有棋局狀態(tài)，廣度搜索的狀態(tài)空間
        this.zhash = {}                              //棋局及其鏡像哈希，判重空間
        this.result = 0;                             //解的總數(shù)
        addNewStatePattern(this,startState)          //開局處理，相當(dāng)于游戲初始化
    }
}

游戲的求解過(guò)程就是棋局的搜索過(guò)程，每移動(dòng)一個(gè)棋子就會(huì)生成一個(gè)新的棋局，對(duì)每一個(gè)棋局我們都要生成其所有的后續(xù)棋局。結(jié)束條件：在生成每一個(gè)新棋局時(shí)，判斷是否為解，是則該狀態(tài)終止；另一方面，每一個(gè)棋局若其后續(xù)棋局?jǐn)?shù)為空，也自動(dòng)終止。

function isEscaped(game, gameState){            //曹操的位置到達(dá)（1，3）
    return (gameState.heroes[game.caoIdx -1].left == CAO_ESCAPE_LEFT) && (gameState.heroes[game.caoIdx - 1].top == CAO_ESCAPE_TOP)
}

function resolveGame(game)                                     //廣度搜索主函數(shù)
{
    let index = 0;
    while(index < game.states.length){
        gameState = game.states[index];                        //依次選定棋局狀態(tài)
        if(isEscaped(game, gameState)){                        //找到解，輸出
            game.result++;
            console.log("result:"+game.result+" step--"+gameState.step+" index:"+index)
        }
        else{
            searchNewGameStates(game, gameState);             //選定棋局搜索所有新棋局
        }
        index++;
    }
    return (game.result > 0);
}

武將移動(dòng)產(chǎn)生新棋局。

function searchNewGameStates(game, gameState)                   //搜索新棋局
{
    for(let i = 0; i < gameState.heroes.length; i++)            //遍歷武將
    {
        for(let j = 0; j < MAX_MOVE_DIRECTION; j++)             //遍歷所有方向
        {
            trySearchHeroNewState(game, gameState, i, j);       //移動(dòng)武將產(chǎn)生新棋局
        }
    }
}

根據(jù)華容道規(guī)則，對(duì)一個(gè)武將棋子連續(xù)移動(dòng)只算一步，因此在每一步移動(dòng)成功后，需要繼續(xù)對(duì)該棋子嘗試移動(dòng)，但是移動(dòng)的方向有限制，不能向原方向移動(dòng)。

function trySearchHeroNewState(game, gameState, heroIdx, dirIdx)
{
    let newState = moveHeroToNewState(gameState, heroIdx, dirIdx);    //新棋局產(chǎn)生
    if(newState) {
        if(addNewStatePattern(game, newState))                        //處理新棋局，判重，添加到狀態(tài)鏈中
        {
             /*嘗試連續(xù)移動(dòng)，根據(jù)華容道游戲規(guī)則，連續(xù)的移動(dòng)也只算一步*/
            tryHeroContinueMove(game, newState, heroIdx, dirIdx);
            return;
        }
    }
}

function moveHeroToNewState(gameState, heroIdx, dirIdx)
{
    if(canHeroMove(gameState, heroIdx, dirIdx))                //能夠移動(dòng)
    {
        var newState = new HrdGameState();                     //新建棋局
        if(newState)
        {
            copyGameState(gameState, newState);                //用父棋局初始化新棋局
            var hero = newState.heroes[heroIdx];               //取得武將
            const dir = DIRECTION[dirIdx];                     //取得方向

            clearPosition(newState, hero.type, hero.left, hero.top); //清除父棋局信息
            takePosition(newState, heroIdx, hero.type, hero.left + dir[0], hero.top + dir[1]);            //新棋局?jǐn)?shù)據(jù)生成
            hero.left = hero.left + dir[0];                    //武將新位置設(shè)定
            hero.top = hero.top + dir[1];

            newState.step = gameState.step + 1;                //移動(dòng)步數(shù)加一
            newState.parent = gameState;                       //形成因果鏈
            newState.move.heroIdx = heroIdx;                   //記錄移動(dòng)方法
            newState.move.dirIdx = dirIdx;
            return newState;                                   //返回新棋局
        }
    }
    return null;
}

function addNewStatePattern(game, gameState)
{
    var l2rHash = getZobristHash(zobHash, gameState);            //計(jì)算棋局哈希值
    if(!game.zhash[l2rHash])                                     //棋局不存在
    {
        game.zhash[l2rHash] = l2rHash;                           //棋局哈希存儲(chǔ)
        var r2lHash = getMirrorZobristHash(zobHash, gameState);
        game.zhash[r2lHash] = r2lHash;                           //棋局鏡像哈希存儲(chǔ)
        game.states.push(gameState);                             //棋局存儲(chǔ)

        return true;
    }

    return false;                                                //棋局已經(jīng)存在，忽略
}

定義：

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)
]

四個(gè)解：

result:1 step--81 index:11930
result:2 step--85 index:12123
result:3 step--98 index:12337
result:4 step--101 index:12348

定義：

var hs = [new Warrior(WARRIOR_TYPE.HT_VBAR,0,0),          //構(gòu)建武將列表，初始棋局
          new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,0),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,0,2),
          new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,3,2),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,3)
]

四個(gè)解：

result:1 step--73 index:11391
result:2 step--84 index:12207
result:3 step--86 index:12263
result:4 step--89 index:12306

定義：

var hs = [new Warrior(WARRIOR_TYPE.HT_BLOCK,0,0),          //構(gòu)建武將列表，初始棋局
          new Warrior(WARRIOR_TYPE.HT_BOX,1,0),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,3,0),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,1),
          new Warrior(WARRIOR_TYPE.HT_HBAR,1,2),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,1),
          new Warrior(WARRIOR_TYPE.HT_VBAR,0,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,1,3),
          new Warrior(WARRIOR_TYPE.HT_BLOCK,2,3),
          new Warrior(WARRIOR_TYPE.HT_VBAR,3,3)
]

四個(gè)解：

result:1 step--74 index:7767
result:2 step--80 index:9212
result:3 step--94 index:10921
result:4 step--97 index:11157

文中是主要代碼分析，完整代碼托管在開源中國(guó)，其中的hyd.js即華容道解法。

https://gitee.com/zhoutk/test

終于完成了，其中遇到一個(gè)坑，就是zobrist的空間問(wèn)題，《算法的樂(lè)趣》書中是說(shuō)用32位整數(shù)，但其提供的源碼是左移15位，我覺(jué)得也應(yīng)該夠，就用了15位整數(shù)。結(jié)果搜索不到解，各種調(diào)試、跟蹤，感覺(jué)哪哪都是對(duì)的，曹操就是下不來(lái)，郁悶一晚。突然想到會(huì)不會(huì)是zobrist空間太小，若空間太小，新的棋局會(huì)與舊棋局沖突，這樣應(yīng)該會(huì)導(dǎo)致很多狀態(tài)被忽略。清晨起床一試，爽！