摘要:華容道游戲看似簡單,但求解需要設(shè)計的數(shù)據(jù)結(jié)構(gòu)比較復雜,還牽涉到棋類游戲的棋局判斷,所以整個過程還是挺費勁的。
此為《算法的樂趣》讀書筆記,我用javascript(ES6)重新實現(xiàn)算法。
華容道游戲看似簡單,但求解需要設(shè)計的數(shù)據(jù)結(jié)構(gòu)比較復雜,還牽涉到棋類游戲的棋局判斷,所以整個過程還是挺費勁的。我盡量用面向?qū)ο蟮乃枷雭磉M行封裝,整個過程將分成幾個部分記錄下來,今天是最后一部分,棋局的廣度搜索。廣度搜索
棋局的搜索空間是一個樹狀關(guān)系空間,廣度優(yōu)先搜索能夠首先找到最優(yōu)解,因為首先找到的解深度是最淺的。
游戲定義我們對算法的要求是:給定一個華容道游戲的開局布局,可以得到這個開局的所有解決方法以及相應(yīng)的武將移動步驟,要求算法具有能用性,能處理任何一種開局的華容道游戲。
class HrdGame{ constructor(caoIdx, heroes){ this.caoIdx = caoIdx; //曹操在武將列表中的序號 var startState = new HrdGameState(); //新建開局棋局 startState.initState(heroes) //開局棋局初始化 this.states = [] //存儲所有棋局狀態(tài),廣度搜索的狀態(tài)空間 this.zhash = {} //棋局及其鏡像哈希,判重空間 this.result = 0; //解的總數(shù) addNewStatePattern(this,startState) //開局處理,相當于游戲初始化 } }算法思路及代碼
游戲的求解過程就是棋局的搜索過程,每移動一個棋子就會生成一個新的棋局,對每一個棋局我們都要生成其所有的后續(xù)棋局。結(jié)束條件:在生成每一個新棋局時,判斷是否為解,是則該狀態(tài)終止;另一方面,每一個棋局若其后續(xù)棋局數(shù)為空,也自動終止。
解的判定function isEscaped(game, gameState){ //曹操的位置到達(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); }搜索新棋局
武將移動產(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); //移動武將產(chǎn)生新棋局 } } }新棋局生成
根據(jù)華容道規(guī)則,對一個武將棋子連續(xù)移動只算一步,因此在每一步移動成功后,需要繼續(xù)對該棋子嘗試移動,但是移動的方向有限制,不能向原方向移動。
function trySearchHeroNewState(game, gameState, heroIdx, dirIdx) { let newState = moveHeroToNewState(gameState, heroIdx, dirIdx); //新棋局產(chǎn)生 if(newState) { if(addNewStatePattern(game, newState)) //處理新棋局,判重,添加到狀態(tài)鏈中 { /*嘗試連續(xù)移動,根據(jù)華容道游戲規(guī)則,連續(xù)的移動也只算一步*/ tryHeroContinueMove(game, newState, heroIdx, dirIdx); return; } } }移動武將
function moveHeroToNewState(gameState, heroIdx, dirIdx) { if(canHeroMove(gameState, heroIdx, dirIdx)) //能夠移動 { 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]); //新棋局數(shù)據(jù)生成 hero.left = hero.left + dir[0]; //武將新位置設(shè)定 hero.top = hero.top + dir[1]; newState.step = gameState.step + 1; //移動步數(shù)加一 newState.parent = gameState; //形成因果鏈 newState.move.heroIdx = heroIdx; //記錄移動方法 newState.move.dirIdx = dirIdx; return newState; //返回新棋局 } } return null; }處理棋局
function addNewStatePattern(game, gameState) { var l2rHash = getZobristHash(zobHash, gameState); //計算棋局哈希值 if(!game.zhash[l2rHash]) //棋局不存在 { game.zhash[l2rHash] = l2rHash; //棋局哈希存儲 var r2lHash = getMirrorZobristHash(zobHash, gameState); game.zhash[r2lHash] = r2lHash; //棋局鏡像哈希存儲 game.states.push(gameState); //棋局存儲 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) ]
四個解:
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) ]
四個解:
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) ]
四個解:
result:1 step--74 index:7767 result:2 step--80 index:9212 result:3 step--94 index:10921 result:4 step--97 index:11157完整代碼
文中是主要代碼分析,完整代碼托管在開源中國,其中的hyd.js即華容道解法。
https://gitee.com/zhoutk/test小結(jié)
終于完成了,其中遇到一個坑,就是zobrist的空間問題,《算法的樂趣》書中是說用32位整數(shù),但其提供的源碼是左移15位,我覺得也應(yīng)該夠,就用了15位整數(shù)。結(jié)果搜索不到解,各種調(diào)試、跟蹤,感覺哪哪都是對的,曹操就是下不來,郁悶一晚。突然想到會不會是zobrist空間太小,若空間太小,新的棋局會與舊棋局沖突,這樣應(yīng)該會導致很多狀態(tài)被忽略。清晨起床一試,爽!
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/79353.html
摘要:還在上班很無聊數(shù)字華容道暢玩地址開發(fā)源碼地址這個叫前言年末了。光隨機生成一個亂序數(shù)列是不夠的,還得保證這個數(shù)列的逆序數(shù)為偶數(shù),嗦嘎。所以,我們直接將交換的次數(shù),記為數(shù)列逆序數(shù)個數(shù),就達到了想要的效果。 還在上班?很無聊?數(shù)字華容道暢玩地址 開發(fā)源碼地址 這個叫前言 年末了。哦,不,要過年了。以前只能一路站到公司的我,今早居然是坐著過來的。新的一年,總要學一個新東西來迎接新的未來吧,所以...
摘要:近日,優(yōu)刻得科技股份有限公司以下簡稱聯(lián)合中國移動廣東公司中興通訊股份有限公司,以及云游戲合作伙伴北京念力科技有限公司,進行了實驗室環(huán)境下云游戲體驗測試。近日,優(yōu)刻得科技股份有限公司(以下簡稱UCloud)聯(lián)合中國移動廣東公司、中興通訊股份有限公司,以及云游戲合作伙伴北京念力科技有限公司,進行了5G實驗室環(huán)境下云游戲體驗測試。這項測試將為云游戲在5G網(wǎng)絡(luò)環(huán)境下的發(fā)展提供實驗室參考,為5G技術(shù)的...
閱讀 1876·2021-09-28 09:36
閱讀 2426·2021-09-08 09:35
閱讀 3067·2019-08-30 15:53
閱讀 1554·2019-08-30 14:08
閱讀 665·2019-08-29 18:40
閱讀 2843·2019-08-29 13:57
閱讀 2702·2019-08-29 13:55
閱讀 681·2019-08-26 13:45