其实我是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 ※ 编辑: QHsin 来自: 123.195.220.99 (01/31 20:23)