對遊戲工程師來說，也可以想成是有限狀態機，只是發生的情形是採用機率來切換的。
此部分可以參考演算法筆記的文章 [1]。
馬可夫鏈曾是我搞了非常長一段時間才有所體會的東西，如今從統計學、機率論來下手去了解馬可夫鏈，一切顯得簡單了許多。
以下只做實作必要了解的簡介說明，不做深入的數學探究。
直觀馬可夫模型
從這張有向圖來看，直觀的來說，這些橘色的圖，代表著拉霸機的元素，例如大家熟知的:
777 ，櫻桃櫻桃櫻桃、蘋果蘋果蘋果，三個連在一起，就是 BIG WIN WIN!，在這裡，也就是三個元素，如果設計連線中獎，就是只有 111、222、333。
從剪刀、石頭、布來看也行，這圖的箭頭式說明，各自轉移到其他狀態的機率。
例如: 如果你現在拿到的第一個數字是 1，那你下一次拿到 1 的機率是 80% (很高)，或是拿到 2, 3 的機率都只有 10%。
仔細看，對 2, 3 的機率都是如此，這種機率的馬可夫模型，說明了這個遊戲很容易會讓數字達到連線: 111、222、333。
狀態、狀態矩陣
狀態，就是指 1, 2, 3 被稱為狀態，我們通常也會設定一個初始狀態，也就是你要從 1, 2 , 3 哪一個開始進去跑。
如圖，狀態其實只有三個， 1, 2, 3，你也可以想成剪刀石頭布，那狀態矩陣就是:
S = { 1, 2, 3 }，或是 S = { 剪刀、石頭、布 }
轉移機率、轉移機率矩陣
我們把焦點方在一個狀態上，轉移機率就是指你在 1 的時候，下一次轉移到 2 或 3 的機率是 0.1,回到自己的機率是 0.8，對於 2, 3 而言也是一樣的，這裡有個要求，每個節點轉移出去，到自己的機率加總要是 1。
例如: 圖中的 1 ，轉移到自己 + 轉移到 2 + 轉移到 3 = 1。
因為 "機率" 的總和就是 1 (對所有機率做積分為 1)。
對 1 來說，轉移機率可以列成矩陣:
[0.8, 0.1, 0.1 ]
這個矩陣的陳列方式是按照:
[ 1, 2 ,3 ] 對比 [ 0.8, 0.1, 0.1 ] ，意思是到 1 的機率是 0.8，到 2 的機率是 0.1，到 3 的機率是 0.1。
對 2, 3 也都列成矩陣，可以合併成一個大矩陣:
[ 0.8, 0.1, 0.1 ]
[ 0.1, 0.8, 0.1 ]
[ 0.1, 0.1, 0.8 ]
從這裡可以發現，對角矩陣都是回到自己的部分。
初始狀態
初始狀態，就是從不是 1, 2, 3 的元素作為起點，進入下一個人的機率，其實也是狀態轉移矩陣的一種，只是只會在進入馬可夫鏈之前被執行一次。
從設計單態、單態轉移開始
基本上，本文想要呼叫一個 markovchainProcess(times int) ，然後輸出一系列的狀態矩陣出來， times 指的是次數，也就是在馬可夫鏈上面走幾步。
我們務必從單鏈開始做，才不會頭痛:
func markovchainProcess(times int) []string {
// 定義出所有的狀態順序 (有順序)
states := []string{"Z", "O", "T"}
// 定義狀態轉移矩陣的順序 (有順序，用名稱定義)
// means Z -> Z or Z -> O of process!
transitionName := [][]string{
{"ZZ", "ZO", "ZT"},
{"TZ", "TT", "TO"},
{"OZ", "OT", "OO"},
}
// 狀態轉移矩陣 (可以對照上面)
// 舉例 [1][1] 就是 "TT"、[2][2] 就是 "OO"
// TT 意思就是 T 元素，下一個抽到 T 的機率
transitionMatrix := [][]float32{
{0.2, 0.6, 0.2}, // 此排加總為 1
{0.1, 0.6, 0.3}, // 此排加總為 1
{0.2, 0.7, 0.1}, // 此排加總為 1
}
// 請務必檢查 sum(transitionMatrix[0]) == 1
// 請務必檢查 sum(transitionMatrix[1]) == 1
// 請務必檢查 sum(transitionMatrix[2]) == 1
// 機率不能亂給，每一個父陣列的加總一定要是 1
// 定義現在的狀態
activityNowState := states[0]
fmt.Println("Now: " + activityNowState)
// 這是最後要輸出的狀態列表，就先放入初始的固定元素 states[0] == Z
// all observation sequence
activityList := []string{activityNowState}
// 按照需求走馬可夫鏈
for i := 0; i < times; i++ {
// 單狀態為 Z 的情形
if activityNowState == "Z" {
// Algorithm 是可以放機率陣列，他會隨機指定一個 index
// 此 index 對照 state 的 index
change := Algorithm(transitionMatrix[0])
fmt.Println(transitionMatrix[0])
// 顯示轉移後的狀態名稱
changeName := transitionName[0][change]
// 如果轉移狀態後是 ZZ、ZO、ZT，就把現在的狀態改變
if changeName == "ZZ" {
activityNowState = "Z"
} else if changeName == "ZO" {
activityNowState = "O"
} else if changeName == "ZT" {
activityNowState = "T"
}
}
// 把已經轉移的狀態放到輸出的狀態列表
fmt.Println(activityNowState)
activityList = append(activityList, activityNowState)
}
return activityList
}增加為多態、多態轉移
上列，我們設計完單態的情形，現在要把多態放上去:
func markovchainProcess(times int) []string {
// 定義出所有的狀態順序 (有順序)
states := []string{"Z", "O", "T"}
// 定義狀態轉移矩陣的順序 (有順序，用名稱定義)
// means Z -> Z or Z -> O of process!
transitionName := [][]string{
{"ZZ", "ZO", "ZT"},
{"TZ", "TT", "TO"},
{"OZ", "OT", "OO"},
}
// 狀態轉移矩陣 (可以對照上面)
// 舉例 [1][1] 就是 "TT"、[2][2] 就是 "OO"
// TT 意思就是 T 元素，下一個抽到 T 的機率
transitionMatrix := [][]float32{
{0.2, 0.6, 0.2}, // 此排加總為 1
{0.1, 0.6, 0.3}, // 此排加總為 1
{0.2, 0.7, 0.1}, // 此排加總為 1
}
// 請務必檢查 sum(transitionMatrix[0]) == 1
// 請務必檢查 sum(transitionMatrix[1]) == 1
// 請務必檢查 sum(transitionMatrix[2]) == 1
// 機率不能亂給，每一個父陣列的加總一定要是 1
// 定義現在的狀態
activityNowState := states[0]
fmt.Println("Now: " + activityNowState)
// 這是最後要輸出的狀態列表，就先放入初始的固定元素 states[0] == Z
// all observation sequence
activityList := []string{activityNowState}
// 按照需求走馬可夫鏈
for i := 0; i < times; i++ {
// 單狀態為 Z 的情形
if activityNowState == "Z" {
// Algorithm 是可以放機率陣列，他會隨機指定一個 index
// 此 index 對照 state 的 index
change := Algorithm(transitionMatrix[0])
fmt.Println(transitionMatrix[0])
// 顯示轉移後的狀態名稱
changeName := transitionName[0][change]
// 如果轉移狀態後是 ZZ、ZO、ZT，就把現在的狀態改變
if changeName == "ZZ" {
activityNowState = "Z"
} else if changeName == "ZO" {
activityNowState = "O"
} else if changeName == "ZT" {
activityNowState = "T"
}
// 擴增 O, T
}else if activityNowState == "O" {
change := Algorithm(transitionMatrix[0])
changeName := transitionName[2][change]
if changeName == "OZ" {
activityNowState = "Z"
} else if changeName == "OT" {
activityNowState = "T"
} else if changeName == "OO" {
activityNowState = "O"
}
} else if activityNowState == "T" {
change := Algorithm(transitionMatrix[0]
fmt.Println(transitionMatrix[1])
changeName := transitionName[1][change]
if changeName == "TZ"
activityNowState = "Z"
} else if changeName == "TT" {
activityNowState = "T"
} else if changeName == "TO" {
activityNowState = "O"
}
}
// 把已經轉移的狀態放到輸出的狀態列表
fmt.Println(activityNowState)
activityList = append(activityList, activityNowState)
}
return activityList
}附錄 - 對 Algorithm 跟 Sum 的實作:
Algorithm 是機率研究 (5) 主要探討的程式實作內容，若有需要可以回頭去研究。
func Algorithm(p []float32) int {
//盡量把 s1, r1 寫在外面，避免速度變慢
s1 := rand.NewSource(time.Now().UnixNano())
r1 := rand.New(s1)
//given
accuracy := 100
//probabilities 是整數機率空間
probabilities := []int{}
for _, _p := range p {
probabilities = append(probabilities, int(_p*float32(accuracy)))
}
var start, end int = 0, 0
rand := r1.Intn(accuracy) // 0 ~ accuracy 精確度的亂數空間
for i, probability := range probabilities {
end += probability
if start <= rand && end > rand {
return i
}
start = end
}
return -1
}
// 可以對 []float32{ 0.1, 0.8, 0.1 } 加總
func sum(xi []float32) float32 {
fmt.Printf("%T\n", xi)
var total float32 = 0
for _, v := range xi {
total += v
}
return total
}
Reference:
[1]: http://web.ntnu.edu.tw/~algo/HiddenMarkovModel.html
[2]: https://www.datacamp.com/community/tutorials/markov-chains-python-tutorial
[3]: https://dataconomy.com/2018/03/an-introduction-to-markov-chains-using-r/
[4]: https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE
沒有留言:
張貼留言