# PCRedive 從接龍小遊戲到動態規劃
###### tags: `技術文`
以`一ㄚ`起頭為例，有效的對(單字,起頭,結尾)為
單字|亞瑟|夏天風情|家具| 甲殼類|鴨子|啞鈴|霞|亞里莎|嘉夜
---|---|---|---|---|---|---|---|---|---
起頭注音|ㄧㄚ|ㄧㄚ|ㄧㄚ|ㄧㄚ|ㄧㄚ|ㄧㄚ|ㄧㄚ|ㄧㄚ|ㄧㄚ
結尾注音| ㄜ|ㄧㄥ| ㄩ| ㄟ| ㄗ|ㄧㄥ|ㄧㄚ| ㄚ|ㄧㄝ
每個對(起頭,結尾)與其他對重複也是算一個對(pair)，查表時可以看出圖片和對"可能是"one-to-one關係。
:::info
**Axiom**
(1) 九宮格至少要出現1個有效的對給玩家選擇，最多出現9個對，前提是對有多達9個以上，例如`ㄩㄣ`起頭就只有一個對。
:::
實際上即使韻母對應的有效對有多達9個以上，台面上也僅僅出現最多6個(我遇到最多6個啦)，如果有效對只有2個，台面上出現的對最多也就2個。
:::info
韻母 -> pair的注音起頭
:::
# 100% 圖鑑條件
蒐集475個不同的"解釋"，遊戲內顯示有480個，應該有5個是重複的。
# 台面分析(A)
台面上出現的9個圖示(icon)都不一樣，從[龍的探索者們 小遊戲單字表-icons.png](https://hanshino.nctu.me/online/icons.png)得知共有142個圖示，九宮格就是從142個圖示內隨機挑選9個。回憶高中數學[Binomial coefficient](https://en.wikipedia.org/wiki/Binomial_coefficient)定義為$\binom{n}{k} = \frac{n!}{k!(n-k)!}$，意思是n個元素的集合內取k個元素的組合。
韻母出現時，假設
- 九宮格內圖示(icon)和對(pair)的關係是one-to-one
- 其他沒選到的圖示也是one-to-one。
> - 如果對應到多個(1-to-many)，那選到正確圖示的時候要給你Normal還是Great?
> - 如果多個圖示只對應到一個對(many-to-one)，你在跟我開玩笑嗎？
所以選圖示=選對。
再來不考慮格子內的排序，算給定注音開頭出現結特定注音結尾的組合數
- 給定韻母`一ㄚ`出現`ㄧㄝ`的組合數=${141\choose 8}$
- 給定韻母`ㄩㄣ`出現`ㄧㄥ`的組合數
- 出現`ㄧㄥ`對的有兩個，換個角度想就是`所有組合-不出現"一ㄥ"的組合`
- 組合數=${9\choose 142}-{9\choose 140}$
- 要算機率分母放${9\choose 142}$
### 一般化成函式
目標：在對方給定注音開頭(head)，算出九宮格上出現注音結尾(tail)圖示的機率
```python
# https://stackoverflow.com/questions/26560726/python-binomial-coefficient
''' Calculate binomial coefficient xCy = x! / (y! (x-y)!)
'''
from math import factorial as fac
def binomial(x, y):
try:
binom = fac(x) // fac(y) // fac(x - y)
except ValueError:
binom = 0
return binom
icon_count = 142
icon_all_combs = binomial(142,9)
def find(head,tail):
# tail_dup = ['ㄥ','ㄥ','ㄛ']
tail_dup = [ pair["tail"] for pair in findHead(head)]
# tail_dup = ['ㄥ','ㄛ']
tail_undup = set(tail_dup)
# If tail='ㄥ', count = 2
count = len(list(filter(lambda x: x==tail, tail_dup)))
# caculate probability
return (icon_all_combs - binomial(icon_count-count, 9))/icon_all_combs
```
實驗了一下，`find('ㄩㄣ','ㄧㄢ')`得到6.33%的機率，這與(1)矛盾
# 台面分析(B)
既然用算的行不通，擷取幾張遊戲畫面的九宮格統計一下
韻母|Normal|Great|Puricone|該韻母總對數
---|---|---|---|---|---|---
ㄧ|2|3|1|38
ㄨ|2|3|1|39
一ㄠ|2|3|1|24
ㄚ|2|3|1|17
ㄨ|2|3|1|39
ㄥ|2|3|1|15
ㄗ|2|3|1|19
ㄧㄥ|2|3|1|23
ㄠ|2|3|1|25
ㄧ|2|3|1|38
ㄞ|2|3|1|18
ㄧㄝ|2|3|1|10
ㄧㄣ|2|3|1|8
發現Normal/Great/Puricone固定在2/3/1。再對Normal/Great/Puricone沒有達到至少2/3/1的韻母對進行分析，寫個小程式就能抓出來。
韻母|總對數
---|---
ㄡ|10
ㄣ|12
ㄦ|2
ㄨㄚ|4
ㄨㄛ|5
ㄨㄣ|6
ㄨㄤ|6
ㄩㄝ|5
ㄩㄢ|6
ㄩㄣ|1
擷取遊戲畫面進行分析
韻母|Normal|Great|Puricone|韻母總對數
---|---|---|---|---|---|---
ㄩㄝ|2|2|1|5
ㄨㄛ|1|2|1|5
到這邊做一個猜想，會不會九宮格上出現的Normal/Great/Puricone會等同：
:::success
(2)
normal = MIN(2, 韻母對["normal"])
great = MIN(3, 韻母對["great"])
puricone = MIN(1, 韻母對["puricone"])
:::
又找了ㄦ/ㄨㄚ的九宮格畫面來分析，發現都符合 (2)
韻母|Normal|Great|Puricone|韻母總對數
---|---|---|---|---|---|---
ㄦ|1|1|0|2
ㄨㄚ|1|2|1|5
那剩下的ㄡ/ㄣ/ㄨㄣ/ㄨㄤ/ㄩㄢ/ㄩㄣ應該也符合 (2)
### 一般化成函式
給個注音開頭(head)返回出現對應解釋(info)的機率和注音結尾(tail)
```python
def findPair(head, info):
# find all pairs
pairs = findHead(head)
# seperate pairs into different groups: normal, great, puricone
n = list(filter(lambda x: x["property"]=="normal",pairs))
p= list(filter(lambda x: x["property"]=="puricone",pairs))
g = list((filter(lambda x: x["property"]=="great",pairs)))
n_count = min(2,n)
g_count = min(3,n)
p_count = min(1,n)
```
寫到這卡住了，回想一下高中數學題目：
有A,B,C三箱各裝有不同顏色的球：A箱有3黑11黃，B箱有5黑13藍，C箱有7黑17綠。
自A,B,C這3箱各取x,y,z個球，試問：
大概就是這樣的感覺，完成剩下的部份。
(3)
```python
''' Calculate binomial coefficient xCy = x! / (y! (x-y)!)
'''
def binomial(x, y):
try:
binom = fac(x) // fac(y) // fac(x - y)
except ValueError:
binom = 0
return binom
def findPair(head, info):
# find all pairs
pairs = findHead(head)
tail = None
if len(list(filter(lambda x: x["info"] == info, pairs))) > 0:
tail = list(filter(lambda x: x["info"] == info, pairs))[0]["tail"]
# seperate pairs into different groups: normal, great, puricone
n = list(filter(lambda x: x["property"] == "normal", pairs))
g = list((filter(lambda x: x["property"] == "great", pairs)))
p = list(filter(lambda x: x["property"] == "puricone", pairs))
n_count = len(n)
g_count = len(g)
p_count = len(p)
n_tail_count = len(list(filter(lambda x: x["info"] == info, n)))
g_tail_count = len(list(filter(lambda x: x["info"] == info, g)))
p_tail_count = len(list(filter(lambda x: x["info"] == info, p)))
n_x_count = min(2, len(n))
g_x_count = min(3, len(g))
p_x_count = min(1, len(p))
probability = 1 - \
(binomial(n_count-n_tail_count, n_x_count)/binomial(n_count, n_x_count)) * \
(binomial(g_count-g_tail_count, g_x_count)/binomial(g_count, g_x_count)) * \
(binomial(p_count-p_tail_count, p_x_count)/binomial(p_count, p_x_count))
return (probability, tail)
p, t = findPair('ㄦ', '放在公園裡的遊戲道具。')
print(p, t) # 1.0 ㄕ
p, t = findPair('ㄦ', '看到隆起來的手臂肌肉了嗎？那就是二頭肌。')
print(p, t) # 1.0 ㄧ
p, t = findPair('ㄦ', '紅色又酸酸甜甜的水果。')
print(p, t) # 0.0 None
p, t = findPair('ㄩ', '主要是避雨用的傘。')
print(p, t) # 0.5 ㄢ
```
# 預測出現機率
:::info
**Axiom**
(3) 自己選或嘉夜選的解釋都會出現在圖鑑內
:::
:::info
假設玩家和嘉夜在**Hard模式下**九宮格出現Normal/Great/Puricone的機率一樣
> 實測看來好像嘉夜能選擇的更少(汗)
:::
既然已經從(3)知道給定出現**注音開頭**後九宮格出現指定**解釋**的機率，接下來討論九宮格出現後想要得到某**解釋**，九宮格要選哪一個
- 狀況一：九宮格內已有出現對應解釋
- 狀況二：九宮格內沒有出現對應解釋，選擇會讓接下來n回合(無論玩家或嘉夜)內出現對應解釋的解釋 (n=未知)
狀況二是這樣子的
如果嘉夜台面上出現(A,B)對，又輪到嘉夜作答，你想要嘉夜選(A,B)給你往下接，但嘉夜不一定會選你想要的，但他一定會選正解，當然就是從台面上x個解答中選一個，選到你想要的機率是`1/x`，在此新增一個函數`coff_pc`就是來算`1/x`
```python
def coff_pc(head):
# find all pairs
pairs = findHead(head)
# seperate pairs into different groups: normal, great, puricone
n = list(filter(lambda x: x["property"] == "normal", pairs))
g = list((filter(lambda x: x["property"] == "great", pairs)))
p = list(filter(lambda x: x["property"] == "puricone", pairs))
n_count = len(n)
g_count = len(g)
p_count = len(p)
n_x_count = min(2, len(n))
g_x_count = min(3, len(g))
p_x_count = min(1, len(p))
return 1/(n_x_count+g_x_count+p_x_count)
print(coff_pc('ㄦ')) # 0.5
```
通往`(info3,c,d)`的路不只一條，如果有兩條:
- 路徑1: (info1,a,b)->(info2,b,c)->(info3,c,d)
- 路徑2: (info1,a,b)->(info5,b,x)->(info6,x,y)->(info2,y,c)->(info3,c,d)
當然會選機率大的路徑2啊(假設路徑2機率最大)
再來是路徑長度。
Round|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|Rush
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
玩家||O||O||O||O||O||O||O||O||
嘉夜|O||O||O||O||O||O||O||O||
:::warning
Round最多到15，因為接下來進Rush。這邊視遇到Rush為結束，要把Rush也考慮來會讓狀況複雜化
:::
然後再用上Dynamic Programming
```python
# Create lookup table for function findPairInRound
findPairInRoundTableKeys = set([l["info"] for l in mapping_list])
findPairInRoundTable = {}
for b in bopomopo_character_set:
findPairInRoundTable[b] = {}
for k in findPairInRoundTableKeys:
findPairInRoundTable[b][k] = {}
for r in range(16):
findPairInRoundTable[b][k][r] = None
# 如果對方丟個head進來，九宮格還沒出現，有多大機率出現info，而且如果是嘉夜的回合，嘉夜剛好選到info
def findPairInRound(head, target_info, round):
# 如果對方丟個head進來，九宮格還沒出現，有多大機率出現info，而且如果是嘉夜的回合，嘉夜剛好選到info
# lookup table
tmp = findPairInRoundTable[head][target_info][str(round)]
if tmp is not None:
return tmp
# final round
if round == 15:
findPairInRoundTable[head][target_info]['15'] = findPair(
head, target_info) # save
return findPair(head, target_info)
matching_pairs = findHead(head, target_info)
if len(list(filter(lambda x: x["info"] == target_info, matching_pairs))) == 0:
# The info not in the current round
p = 0
t = None
for pair in matching_pairs:
# Find the maximum possibility
# In this case, pair["tail"] = t1, we call this function to get possibility
p1, t1 = findPair(pair["head"], pair["info"])
p2, t2 = findPairInRound(t1, target_info, round + 1)
p_ = p1*p2
t_ = t2
if round % 2 == 0:
# カヤ
p_ = p_ * coff_pc(pair["head"])
if p_ > p:
p = p_
t = t_
findPairInRoundTable[head][target_info][str(round)] = (p, t) # save
return p, t
else:
# The info is in the current round
p, t = findPair(head, target_info)
if round % 2 == 0:
# カヤ
p = p * coff_pc(head)
findPairInRoundTable[head][target_info][str(round)] = (p, t) # save
return (p, t)
t = time.time()
possibility, _ = findPairInRound('ㄓ', '一旦試過就再也無法放手。', 1)
print("%.1f%% %.3f sec"%(possibility*100,time.time()-t,)) # 7.5 % 1.170 sec
```
# 實作
### 資料庫
小小的json檔，用來存475個解釋
DB.json
```
{
"以管狀造型為主，多以吹奏等空氣流動方式產生樂音的樂器。": True,
"生長在溫暖地區，黃色且味道酸甜的水果。": False
}
```
### 流程
用前一板的影像辨識為基礎
1. 辨識九宮格和下注音開頭
2. 從資料庫讀取未完成解釋
3. 對每個有效圖示(通常是6個)列出達成率前3的解釋
- 圖示本身就是未完成解釋=100%
4. 玩家按下圖示，標記該解釋完成
5. `go to 1`
即便用了動態規劃，配備是i5-6200，從Round1隨便查一個解釋的出現機率在table是空的情況下也要0.955s。
```python
t = time.time()
possibility, _ = tools.findPairInRound('ㄓ', '海軍使用的軍用船隻。', 1)
print("%.1f %% %.3f sec"%(possibility*100,time.time()-t,)) # 12.5 % 0.955 sec
```
只得先建表了。用i7-6700花了369.855 sec建出`findPairInRoundTable.json`
```python
with open("findPairInRoundTable.json") as f:
tools.findPairInRoundTable = json.load(f)
t = time.time()
possibility, _ = tools.findPairInRound('ㄓ', '海軍使用的軍用船隻。', 1)
print("%.1f %% %.3f sec"%(possibility*100,time.time()-t,)) # 12.5 % 0.000 sec
```
### 加強影像辨識
在上一版，是以特定像素的白色區塊總和作為九宮格出現的依據，但過場動畫容易被誤判。讀進來的icon有白邊造成template Matching誤認。
### 回合數判斷
每輪遊戲回合數有限，當下的剩餘的回合數會影響字詞出現的機率，因此當右上方血條滿格時即重設`Round=1`
陰影難以肉眼辨識，二值化時影響很大，只得用取上半部份的血條+eroding後判斷
此外，不再從九宮格判斷回合起始，而以大張的字卡為主，這樣也能蒐集到雙方出現過的字詞
最後用pyscreenshot擷取螢幕上的scrcpy視窗當作圖片來源
# 結論
抽不到露娜！！！退坑
# Reference
- [龍的探索者們 小遊戲單字表](https://hanshino.nctu.me/online/KyaruMiniGame)
- [Python Binomial Coefficient](https://stackoverflow.com/questions/26560726/python-binomial-coefficient)
Sign in with Wallet
Connect another wallet