[note] JP_MJ Programming Techniques (1)

看板MJ_JP (日本麻將 - 日麻)作者QHsin (Q馨)時間14年前 (2011/01/31 18:07)推噓17(17推 0噓 2→)

留言19則, 12人參與討論串1/2 (看更多)

其實我是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]。 (待續？) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.195.220.99

推

littlecut

01/31 18:45, , 1^F

01/31 18:45, 1^F

→

xtxml

01/31 19:30, , 2^F

01/31 19:30, 2^F

※ 編輯: QHsin 來自: 123.195.220.99 (01/31 20:23)

推

enfis

01/31 20:23, , 3^F