国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

華容道游戲(中)

Jason / 1437人閱讀

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

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

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

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

Zobrist哈希算法步驟:

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

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

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

Zobrist哈希算法優(yōu)點(diǎn):

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

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

Zobrist算法實(shí)現(xiàn) 編碼表定義

編碼表定義為一個(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))      //對16位隨機(jī)整數(shù)值
                    }while(!tmp)                                    //跳過零值
                    this.zobHash[i][j].push(tmp)
                }
            }
        }
    }
    get(i,j,k){                                                   //get接口
        return this.zobHash[i][j][k]
    }
}
計(jì)算棋局Zobrist哈希值

對棋盤的格子逐個(gè)處理,根據(jù)棋盤格子的武將信息獲取武將的類型,從而獲取該類型對應(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;                    //取得格子上武將序號
            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;
}
取鏡像Zobrist哈希值
棋盤狀態(tài)左右鏡像問題:兩個(gè)棋局雖然武將的位置不一樣,但是如果忽略武將的名字信息,單純從形狀上看是左右對稱的鏡像結(jié)構(gòu)。對于華容道游戲來說,這種左右鏡像的情況對于滑動棋子尋求結(jié)果的影響是一樣的。

鏡像即左右對稱,進(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è)棋局,測試目標(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))    //兩值相等
完整代碼

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

https://gitee.com/zhoutk/test
小結(jié)

盡量使用面向?qū)ο蟮乃枷雭斫鉀Q問題,讓數(shù)據(jù)和操作綁定在一起,努力使代碼容易看懂。

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/79340.html

相關(guān)文章

  • 容道游戲(上)

    摘要:華容道游戲看似簡單,但求解需要設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜,還牽涉到棋類游戲的棋局判斷,所以整個(gè)過程還是挺費(fèi)勁的。華容道游戲介紹華容道游戲據(jù)說來源于三國故事諸葛亮智算華容,關(guān)云長義釋曹操。 此為《算法的樂趣》讀書筆記,我用javascript(ES6)重新實(shí)現(xiàn)算法。 華容道游戲看似簡單,但求解需要設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜,還牽涉到棋類游戲的棋局判斷,所以整個(gè)過程還是挺費(fèi)勁的。我盡量用面向?qū)ο蟮?..

    xi4oh4o 評論0 收藏0
  • 容道游戲(下)

    摘要:華容道游戲看似簡單,但求解需要設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜,還牽涉到棋類游戲的棋局判斷,所以整個(gè)過程還是挺費(fèi)勁的。 此為《算法的樂趣》讀書筆記,我用javascript(ES6)重新實(shí)現(xiàn)算法。 華容道游戲看似簡單,但求解需要設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜,還牽涉到棋類游戲的棋局判斷,所以整個(gè)過程還是挺費(fèi)勁的。我盡量用面向?qū)ο蟮乃枷雭磉M(jìn)行封裝,整個(gè)過程將分成幾個(gè)部分記錄下來,今天是最后一部分,棋局的廣...

    BicycleWarrior 評論0 收藏0
  • 用React寫一個(gè)數(shù)字容道,你需要知道的秘密

    摘要:還在上班很無聊數(shù)字華容道暢玩地址開發(fā)源碼地址這個(gè)叫前言年末了。光隨機(jī)生成一個(gè)亂序數(shù)列是不夠的,還得保證這個(gè)數(shù)列的逆序數(shù)為偶數(shù),嗦嘎。所以,我們直接將交換的次數(shù),記為數(shù)列逆序數(shù)個(gè)數(shù),就達(dá)到了想要的效果。 還在上班?很無聊?數(shù)字華容道暢玩地址 開發(fā)源碼地址 這個(gè)叫前言 年末了。哦,不,要過年了。以前只能一路站到公司的我,今早居然是坐著過來的。新的一年,總要學(xué)一個(gè)新東西來迎接新的未來吧,所以...

    Jason 評論0 收藏0
  • 一只青蛙跳下水

    這是一個(gè)關(guān)于獨(dú)立鉆石的游戲 獨(dú)立鉆石起源于法國,是一種風(fēng)靡世界的益智游戲與中國發(fā)明的華容道、匈牙利人發(fā)明的魔方, 并稱為智力游戲界的三大不可思議它類似于跳棋,但不能走步,只能跳。走棋時(shí)棋子跳過相鄰的棋子到空位上,并把跳過的棋子吃掉。棋子可以沿棋盤的格線橫跳、縱跳,但不能斜跳 了解更多 游戲截圖 showImg(https://segmentfault.com/img/bVAdq3); 游戲地址 游...

    鄒強(qiáng) 評論0 收藏0
  • 淺談你們根本不懂的區(qū)塊鏈游戲

    摘要:下面,我想用淺顯易懂的語言,簡述一下區(qū)塊鏈游戲的機(jī)會。同時(shí)這也是第一個(gè)從游戲機(jī)制到設(shè)計(jì)來說,整體完成度較高的區(qū)塊鏈游戲,其他同期的小游戲基本是在原型或者階段。 作者:Vincent, DappReview CEO編輯:米芽 復(fù)盤過去十年,站在每一個(gè)時(shí)間節(jié)點(diǎn)都有大大小小機(jī)會。而往前看,似乎卻一片迷茫。 本文以一個(gè)深度參與者的身份,用寥寥幾千字,試圖還原區(qū)塊鏈游戲在過去半年的發(fā)展,并...

    DevWiki 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<