JP_MJ Programming Techniques (1) - 日本麻將

其實我是xtxml，被迫用老妹帳號發文( ′_>`)

好久沒發文，來發一些可能很冷僻的研究用文章，
主要是一些大二的時候做的筆記，整理了部分先貼出來。

這個主題我沒有辦法詳細的講完，因為這真的要詳細講，
大概可以寫個一兩百頁，我認為對於電資方面有所研究的對象，
點出關鍵大概也已經可以理解主要概念，剩下的問題實作時不難自己解決。

(請以空白鍵或換頁鍵瀏覽)


=============================================================================
前言


1.主要為數學及演算法討論，對數學跟程設有一些基礎比較能看懂。

2.因為是筆記整理出來的，所以細節省略很多，但這些細節並不相當困難，
很跳針，不要認真看，看個大概就好，真正想理解絕對是要自己親手寫才知道，
我挑出幾個概念性的關鍵問題來討論，這些關鍵問題可以省下很多嘗試錯誤的時間。

3.這類程式有什麼用？
簡單的用途，了解部分概念即可以寫寫麻將的小遊戲，
複雜一點，做各種機率運算，以及統計分析，肯定得對這些演算法有相當的理解。

ex.我很好奇，南三對TOP差距10900，我這手早和可以追8000，做大牌可以追12000
做大牌 跟 早和8000下一局追回3000，何者機率上較高？
做大牌的和了機率應該高於多少，我才該去賭？
這問題涉及到其他兩家的精算，但依舊可以用程式去做統計及運算。

麻將的自由度相較其他遊戲而言並不高，許多高端戰局的精算判斷，
用電腦來達成意外地相當容易，我們可以藉由這樣的特性，由電腦輔助分析牌面，
來得到部分我們所關切的問題的答案。






4.這類演算法都是基於某個條件，做出某個結論，
以下討論的機率，目前全部都是門前自摸和的機率。
這結論不代表正解手，如何解讀或詮釋在於每個人的看法，
然而，他提供一個客觀的機率條件，做為一個追究問題時的參考，是相當重要的。


5.保持適度的懷疑態度以及科學的精神，任何人說的都不一定是對的。


p.s.以下都以一般和了型做為討論的主題。
七對、國士可獨立判斷，並且其演算法相當簡單，故不在討論的範圍內。





=============================================================================


牌譜表達數位化






做為開頭，先來討論這個問題：如何以數碼的方式記錄牌譜？

這是看起來一個小問題，一開始隨便決定其實也沒差。

然而為什麼要提這個問題？
因為後續開始複雜的演算之後，
記錄方式的好壞就會大幅影響程式的效能和資源的使用，
甚至影響後續的擴充性。


因此，這邊提一下程式裡面可能用到的幾種記錄法。


我們定義這樣的先後順序，做為記錄的依據：

123456789m123456789p12345789s東南西北白發中

範例牌型：
123m 456p 78999s 白白


方法一.
將136張牌，依照先後順序，編為1-136號，每張都視為『不相同』的牌，
1-4號：1m 5-8號：2m .......

表示法：1,6,10,52,53,58,99,101,105,107,108,126,128


方法二.
將34種牌，依照先後順序，編為1-34號，同種牌編號相同，
1號：1m 2號：2m .......

表示法：1,2,3,13,14,15,25,26,27,27,27,32,32


方法三.
將4色牌，依照種類分開編號。

表示法：
{(1,2,3),
(4,5,6),
(7,8,9,9,9),
(5,5)}



方法四.

記數法。

表示法：
{(1,1,1,0,0,0,0,0,0),
(0,0,0,1,1,1,0,0,0),
(0,0,0,0,0,0,1,1,3),
(0,0,0,0,2,0,0,X,X)} X為不使用之空間。


方法一：
優點：佔用空間小，資訊保存最詳細，擴張性高(支援赤牌、白鑽等等)
缺點：牌面運算時換算較複雜，資訊難以閱讀。
用途：配牌用、牌譜相關記錄用。

方法二：
優點：佔用空間小，稍作轉換就能讀懂的資訊，牌面運算時換算較簡單。
缺點：每項特色都不是最好。
用途：資料轉換及交換時使用。

方法三：
優點：佔用空間小，最容易看的資訊，可以直接顯示。
缺點：2維的儲存方式，不能一單一數字代表一張牌，連洗牌都不好洗。
用途：顯示用。


方法四：
優點：做各類運算時效率極高，運算時的基本表達方式。
缺點：佔用固定空間大。
用途：程式運算用。




延伸問題：如何有效率，省空間，又利於運算的記錄『和了拆解型』？


=============================================================================

聽牌的定義：(不考慮役種)

1.廣義聽牌：一切滿足4面子+1單騎、或3面子+1對子+1搭(對)子的牌型。

2.形聽：手牌非空聽的牌型。
Ex.1111234444m456p 不算聽牌

3.狹義形聽：手牌含副露區非空聽的牌型。
Ex.222444m4468p 暗槓[7777p] 不算聽牌

4.有效聽牌：所有可視牌非空聽的牌型。








一般型廣義聽牌『上聽數+1』公式：(意味著最少幾手可以和了)


拆解型中，計算面子及搭(對)子之數目，以下述公式計算。

有對子時：8 - 面子數*2 - 搭(對)子數
無對子時：8 - 面子數*2 - 搭(對)子數 + 1


其中，若 (搭(對)子數 > 5-面子數)，則以 (5-面子數) 計算







=============================================================================

1.如何確定聽牌？
2.如何拆解出可能的聽牌牌型？
3.如何找出所有和了牌以及所有餘剩牌？
4.如何確定上聽數？
5.如何找出所有(上聽)有效牌以及所有餘剩牌？



對戰平台：至少得達到1.2.3.
AI用：1.2.3.必須達到，隨AI的強弱而定，4.5.很可能需要用到。
分析用：1~5皆須達到










How To 拆解？

1.暗刻優先、順子其次，最後取對子及搭子。

例一：11123456m+456789p

照這種拆法會拆成111+234+456+789+56 => 4面子無對子，判定為聽牌
但事實上這是11+123+456+456+789的和了型。

2.順子優先、暗刻其次，最後取對子及搭子。

例二：111234m+456789p+北北

照這種拆法會拆成123+456+789+11+北北+4 => 3面子2對子，判定為聽牌
但事實上這是111+234+456+789+北北的和了型。


3.先取雀頭

明顯地，需要嚐試不同的雀頭，取完之後還可能依舊會碰上上述問題。





由上面的例子，我們至少知道一個事實，
要找到一套簡易的通解，一次就得到最低上聽樹的拆解型是困難的。
好在上聽數的問題，因為現在的電腦速度夠快，即使用暴力法都可以高速地算出。


不管是暗刻優先、還是順子優先，我們建立一套FILO的堆疊(或用遞迴)系統，
建立所有可能的拆解型，最後找出最低上聽數的型。


例如上面的例二，我們依舊用『順子優先、暗刻其次，最後取對子及搭子』的方式。

1.我們第一次依序取 1.123m 2.456p 3.789p 4.11 5.北北 取出第一個拆解型。
2.接著面子堆疊pop出789p嘗試尋找新的拆解型
3.接著面子堆疊pop出456p嘗試尋找新的拆解型
4.最後面子堆疊pop出123m，找到了最佳的拆解型 234+456+789+111+北北










上述演算法的概念，依照顏色分開處理較為容易，
最後再依各種組合方式去拼湊最低上聽數，細節部分就不多做說明。


雖然這不是一套好的演算法，佔用的資源也不小，但以現在的電腦而言，
速度上大多的牌型都在2~10ms左右，一色牌型可能到100~200ms，
若不是對速度或效能吹毛求疵，以一個容易寫的程式嗎來說，是可以考慮看看的。








=============================================================================

和了機率、期望值計算


先定義幾個名詞：

1.(上聽)有效牌：以直接減少上聽數為目的的有效牌。
2.廣義有效牌：在某個目的下提升手牌價值的進張。


1.最短和了路徑：最少自摸數達成和了的路徑 (ShAP)
2.直線和了路徑：除了上聽有效牌外全部打掉，僅限以最短和了路徑為目標 (StAP)
3.無退後的和了路徑：在不增加上聽數的前提下，允許改善牌面。 (NBAP)
4.包含退後的和了路徑：允許增加上聽數來改善牌面。 (BAP)

ShAP ⊂ StAP⊂ NBAP ⊂ BAP







判斷上聽數，上述的演算法為我們達到基礎的需求。
然而當開始確定有效牌時，難題就會緊接而來。

一個3上聽的牌，如何找出他所有的上聽有效牌的？
我們要知道所有的有效牌，必然得知道可能的最短和了型

依照上面暴力的基礎，我們可以選擇更暴力的方法，
曾經做過的方式便是，去分析歸類每種拆解型，
依照面子數、對子數、搭子數來推估可能的和了型，最後找出有效牌。

僅僅是計算『形聽』的話，這個方法還是有一定程度的可行性，
但如果是計算真正的『有效聽牌』(得考慮是否還有有效牌)，
光是雀頭的形成就可以分好幾類，面子的形成又好幾類，每類有不同的判定法，
一弄就是幾千行，而且程式碼亂七八糟。
這我奮鬥過，用相當複雜的方式解析有效牌，很有成就感，
但我希望不要有人再踏到這上面來搞這無聊事。

正著走不行我們就退著走，既然難以用現在的牌型去找和了型，
那不如用所有的和了來連結現在的牌型。


『和了型非常多』，有多少，有11498658這麼多。
想當然耳，我們不可能每次拿一千多萬筆資料來比。

直接觀察和了型太不實際了，接著我們是試著分花色來看，
以單一花色做考量的話，至少數字上會小很多。令人滿意地，我們得到下面的結果。

牌數0張：1種
牌數1張：9種
牌數2張：45種
牌數3張：165種
牌數4張：495種
牌數5張：1278種
牌數6張：2922種
牌數7張：6030種
牌數8張：11385種
牌數9張：19855種
牌數10張：32211種
牌數11張：48879種
牌數12張：69675種
牌數13張：93600種
牌數14張：118800種


此處的種數並非和了可能的種數，而是所有可能的牌面組合。
14張牌也只有大約10萬種左右，這讓搜尋的可行性大幅的增加，
而我們繼續算出可能湊成和了型的種類數，如下。
(單一顏色3a+1的張數，必不可能是和了型，故為0種)

牌數0張：1種
牌數1張：0種
牌數2張：9種
牌數3張：16種
牌數4張：0種
牌數5張：135種
牌數6張：127種
牌數7張：0種
牌數8張：996種
牌數9張：627種
牌數10張：0種
牌數11張：4475種
牌數12張：2098種
牌數13張：0種
牌數14張：13259種

到這邊，我們便得知了，最最最差的8上聽狀況下，也只會比對大約6萬多次，
而在這裡，最開始提到的牌譜表示法方法四：記數法對於這樣的牌型運算，
遠比其他表示法還優秀，因此深入去計算牌型資訊時，這樣的表示法及其重要。

我們再度的耍流氓：

現代的電腦，消耗個50MB的記憶體也是不痛不癢的，這麼多種類的組合列成表格如何？

我們可以在表格中為各種組合添加描述，來表達形式上的許多特徵，
以及牌型變化的關連性，
這種強烈的連結力，是前面重視單一狀態的即時拆解法難以做到的。

牌型的變化簡而言之必定帶有某一花色的張數的改變，
我們可以針對這樣的現象來『搭橋』。

例如：單一花色0張變成1張，有9種可能，我就把牌數0張的那筆資料，
分別搭上九條橋連接到牌數1張的9種組合上面，反之亦然。

我們建構了這無數條管線之後，牌型的變化就很好掌控了，
我根本不用去管現在幾搭幾對，我只要知道某一個牌型離和了型還有幾座橋，
橋數便是『上聽數+1』，途中經過的節點通通是有效牌。

在此，我們能得到的不只是有效牌是哪些，
而是目前狀況通往和了的所有最短和了路徑的分支圖。


有效牌1' 和了型1
/ 和了型2
/ 和了型3
__ 有效牌1 有效牌2' 和了型4
/ ╳ ...
目前--- 有效牌2 有效牌3' ...... ...
\__ ╳
有效牌3 有效牌4'
\
\ 有效牌5'


以上僅為示意圖，實質上兩次有效牌中間還參雜了『這手該捨哪張？』的分歧。
這張圖是由和了型倒著畫回去的，至於如何避免重複連線，則需要一點小判斷。

參考圖：http://i.imgur.com/1qfTs.jpg




以三上聽而言，直線和了型大多在150種以內，，不過中間的節點就可能有幾千種，
少數的『特例三上聽』在畫這張圖時可能要畫個一兩秒，例如：256679m 114p 23458s。
四上聽以上要畫這種圖就不切實際了，因為分歧太多，耗時太久，
然而四上聽以上的牌，大致也還用不著精確的期望值計算，所以這點並不嚴重。


有了這樣的分支圖，有有效牌的牌數資訊，我們自然可以開始對每條路徑來求其期望值。
這些期望值，也可以幫助我們決定，來什麼牌該打什麼牌。
基於期望打點或者基於和了率，我們也可能得到不同的最佳路徑。



這個表示法，兩年後(我大四那年)，再度在麻雀一人研究所裡面看到這個做法，
當時真是油然而生一種惺惺相惜之情:)，正所謂殊途同歸便是這麼一回事吧。





=============================================================================






點數計算


這裡只提一個部分，役種及點數的計算，可以寫一個函數來做所有和了型的拆解，
再針對這些拆解型去算飜符。

飜符的計算上，平和跟三暗刻最後算，
因為這兩個這兩個會牽扯和了牌是哪張而影響是否達成。







=============================================================================

單一分支和了機率


有了上面的分支圖，我們可以開始算跑到每個和了型的機率，
這個分支機率有兩種：

1.一種是若先滿足其他分支，則會放棄該分支。
2.就算滿足其他分支，也不管他，只決打這一分支。

這兩個計算上其實可以相當簡單的切換，所以倒不是太大的問題，
只是說明以下的計算，我們是建立在1.的狀況下。
分支機率上： 2 >= 1，但整體和了率上通常是 1 >= 2。
(後者我沒有提出過證明，所以我只說『通常是』)


這部分要算得精確，而我反覆地想尋找更簡單的方式來計算，
結論是沒有太多的絕竅，算是上沒什麼能約分或者合併的部分，
該成該除就只能用排列組合的公式去硬算。





前提：

配牌完牌型：223788m + 23478p + 55s
最短和了路徑(之一)：摸1m打2m => 摸9m打8m => 摸9p

不可視牌數：UV = 122 (136 - 13張手牌 - dora表示牌 = 122)
上聽數：ST = 2
第i層該總有效牌：AEPi i=1 to ST +1 依序為{30,20,8}
第i層該路徑有效牌：EPi i=1 to ST +1 依序為{4,4,4}

路徑有效牌連乘積：PA = 4*4*4
(這個條件下，若是決打的話，條件改成AEPi = EPi = {4,4,4})









不可視牌有UV張，所以我第一手能摸到有效牌的機率是AEP1 / UV，
我摸的有效牌恰好是這個條路線的機率是(AEP1 / UV) * (EP1 / AEP1)，
等於EP1 / UV。

單以一手來看，決不決打對這條線地成功率來說一樣的，
因為目前第一手摸有效牌的機率與AEPi毫無關係。

然而我這手摸不到有效牌的機率是(UV-AEP1) / UV，
這手摸不到，下一手摸到此路線的有效牌之機率為：

(UV-AEP1) / UV * EP1 / (UV-1)

這時候這條路線的機率就有差了，因為AEP1進入了機率公式裡面。
而這時的AEP1越小，其機率越大，
一般狀況AEP1 >= EP1，若是決打的話AEP1 = EP1，
故決打對這條線的機率來說確實是比一般高的，
當然這件事算是基本常識，只是我們用例子說明這兩個機率算法的不同。




依照上面的算法，我們繼續類推整理如下。
(注意，剛剛算的是機率，以下只先算組合數)

公式 實際數值

ST+1巡和了組合數： 1 * PA 1 * 4*4*4

ST+2巡和了組合數： (UV-AEP1) * PA + (122-30)*4*4*4
(UV-1-AEP2) * PA + 4*(122-1-20)*4*4
(UV-2-AEP3) * PA 4*4*(122-2-8)*4


ST+3巡和了組合數：

(UV-AEP1) * (UV-1-AEP1) * PA + (122-30)*(122-1-30)*4*4*4
(UV-AEP1) * (UV-2-AEP2) * PA + (122-30)*4*(122-2-20)*4*4
(UV-AEP1) * (UV-3-AEP3) * PA + (122-30)*4*4*(122-3-8)*4
(UV-1-AEP2) * (UV-2-AEP2) * PA + 4*(122-1-30)*(122-2-30)*4*4
(UV-1-AEP2) * (UV-3-AEP3) * PA + 4*(122-1-30)*4*(122-3-20)*4
(UV-2-AEP3) * (UV-3-AEP3) * PA 4*4*(122-2-30)*(122-3-8)*4






公式是列出來了，但是這怎麼看都不是一個親切的形式，巡數越多項數越多，
寫出程式來列式計算終究還是不難，因為還是有規則在，
只是這樣的方式達成歸達成，不一定真的合用。



這時，跳脫一下排列組合的公式，我們改用圖像式的分解來思考，
下圖就是一個例子。











有效牌：k k = 1,2,3,.....
無效牌：N

摸牌次數： 1 2 3 4 5 6 7 8 9 10 11 12 13
狀況1 N N N 1 N N N N 2 3 -- -- --
狀況2 1 N N N N N N N 2 N N N 3
狀況3 1 N N N N N N N 2 N N N N


狀況1：第10次摸牌和了
狀況2：第13次摸牌和了
狀況3：(未和了)


機率表示式：

狀況1：P{ [N N N 1] ^ [N N N N 2] ^ [3] }
狀況2：P{ [1] ^ [N N N N N N N 2] ^ [N N N 3] }
狀況3：(未和了)








我們可以將摸牌的行為，解析成 -----| ------| --|這樣的區段的交集，
區段必然是ST+1個(小於 ST+1 則代表未和了的機率)，
每個區段前面由0 ~ X個無效摸牌加上1個有效摸牌，代表一個階段，
也就是分支圖上經歷一個有效牌節點的模擬。

我們如果能找到一個公式，讓三個區段乘起來便是和了率，
那就等於擺脫了前面那樣項數不固定的討厭形式。









ProbFromTo(i,a,b)：在第i+1階段下，第a次摸牌進入該狀態，
第b次摸到該狀態有效牌之機率。

簡寫：PFT(i,a,b)
PFT(i,a,b) = PERMUT(UV - AEP(i+1) - a , UV - AEP(i+1) - b + 1) /
PERMUT(UV - a,UV - b)

PERMUT(a,b) = a! / (a-b)!


假設 殘餘摸牌巡數 = 6


令Ai為1*n之矩陣，令Bi為n*n之矩陣，令Ci為1*n之矩陣。
其中 n = 殘餘摸牌巡數(6) - 上聽數ST(2)，i=0 to ST。


Ai為第i ~ n-ST+i-1 次摸牌進入i+1階段之機率
Bi為轉移矩陣
Ci為第i+1 ~ n-ST+i 次摸牌離開i+1階段之機率



A0 = [1,0,0,0] for i = 0
(最開始就是A0階段，故第零次摸牌進入A0階段之機率為1，其餘為0)
Ai = C(i-1) for i > 0




Bi： PFT(i,i,i+1) , PFT(i,i,i+2) , PFT(i,i,i+3) , PFT(i,i,i+4)
0 , PFT(i,i+1,i+2) , PFT(i,i+1,i+3) , PFT(i,i+1,i+4)
0 , 0 , PFT(i,i+2,i+3) , PFT(i,i+2,i+4)
0 , 0 , 0 , PFT(i,i+3,i+4)

1.Bi必為upper triangular matrix (可以從PFT這個函數的意義得知)
2.(當EPi皆不為零時) Bi對角線上的元素皆非零
3.由1.2.可之，存在Bi(-1)，並且可以簡單的求值。


Ci = Ai X Bi








令該路徑和了率P為1*n之矩陣。

P = {p1,p2,p3,p4}
pi為恰好第 ST+i 次摸牌和了之機率


P = PA(路徑有效牌連乘積) * A0 X B0 X B1 X B2

反之，P X B2(-1) X B1(-1) X B0(-1) = [PA,0,0,0]。






(待續？)

--