V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
simonlu9
V2EX  ›  程序员

有人讨论下麻将胡牌,出牌算法吗,求思路

  •  
  •   simonlu9 · 2019-06-04 15:15:57 +08:00 · 7451 次点击
    这是一个创建于 1760 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前段时间学会了打麻将,觉得老祖宗的智慧真的博大精深,很好玩,食胡的时候真兴奋啊,于是空余时间就想自己写个麻将游戏出来,模仿欢乐麻将那种,数学差,想了两个礼拜才想出一个胡牌算法,前段时间学会了打麻将。

    觉得老祖宗的智慧真的博大精深,很好玩,食胡的时候真兴奋啊,于是空余时间就想自己写个麻将游戏出来,模仿欢乐麻将那种,数学差,想了两个礼拜才想出一个胡牌算法,

    源码 https://github.com/simonlu9/majiang/blob/master/tests/HuTest.php

    大概思路是这样的 比如你手中的牌是这样的 m 代表是万子的意思

    ['m1','m1','m1','m2','m2','m2','m2','m3','m3','m3','m4','m4','m4','m4'];

    • 1、我们首先找出可成为对子的牌有 m1,m2,m3,m4
    • 2、初始化每一张牌的可能路线,比如 m1 可与其他牌组合成顺子,也可以自己当成刻子,m2 可以与其他牌成为顺子,可以自己变成刻子,可以自己变成杠,但当其作为对子的话就只有一个可能,与其他牌成为顺子

    如上所述,我们可以得出 ,当 m1 为对子的时候,所有牌的可能性

    • m1 = [顺]
    • m2 = [顺,刻,杠]
    • m3 = [顺,刻]
    • m4 = [顺,刻,杠]

    那么可能的路线有

    • 顺 顺 顺 顺
    • 顺 顺 顺 刻
    • 顺 顺 顺 杠

    等等,相当于一个排列算法,这里就有 132*3 = 12 种可能性,若到最后每种牌剩余数都为 0,则胡牌,当 m1 作对子不成立时候,依次尝试 m2,m3,m4 作对子,重复以上的步骤,都不行的话就不能胡了 不知道有没有 bug

    第二个就是出牌的算法,目前只想到把自己手中的牌计分,分低的优先出牌,比如一些孤张,边张的,还有一些牌效重复的比如 134 679 一般都会舍去 1 和 9,还有一些就是要算打出的牌失张和进张的比例,感觉很复杂,没有一个完整的思路。

    求大家指导!

    60 条回复    2019-06-05 14:59:13 +08:00
    lkan
        1
    lkan  
       2019-06-04 15:17:20 +08:00 via iPhone
    老哥有斗地主的算法吗
    binux
        2
    binux  
       2019-06-04 15:21:27 +08:00
    胡牌规则就那么几种,扫一遍就完了。
    msg7086
        3
    msg7086  
       2019-06-04 15:24:39 +08:00 via Android
    看和牌算法效率的话可以测一下九莲这种极端情况。
    至于 AI 的话就复杂了,最基础就是算搭子,再高级点的话还要看役种期望值,再往上还有场况分析和防守等等,无聊的话可以买一些研究类书籍读一下。AI 的算法其实就是数码派的理论依据转化成代码的结果了。
    hhhsuan
        4
    hhhsuan  
       2019-06-04 15:25:33 +08:00
    网上搜一下,论文很多
    rogwan
        5
    rogwan  
       2019-06-04 15:25:44 +08:00 via Android
    麻将的精髓就是把人的不确定性,加在程序执行的过程中了,所以没有准确的方法可以预判啦。
    OxQMask
        6
    OxQMask  
       2019-06-04 15:31:08 +08:00
    我们那有一种玩法还有赖子,如果加上这个应该会复杂很多吧😂
    cway
        7
    cway  
       2019-06-04 15:39:58 +08:00
    如果单纯胡牌那不是很复杂,
    x86
        8
    x86  
       2019-06-04 15:42:00 +08:00
    麻将说起来就那么点,实战去打的时候就知道了
    winterfell30
        9
    winterfell30  
       2019-06-04 15:42:14 +08:00
    uvaoj 上有道题就是判断麻将胡牌的,刘汝佳的大白书上还讲了
    zsc8917zsc
        10
    zsc8917zsc  
       2019-06-04 15:45:49 +08:00
    n*AAA+m*ABC+DD,mn 可以等于 0
    Beeethoven
        11
    Beeethoven  
       2019-06-04 15:52:06 +08:00   ❤️ 1
    github 上搜麻将 /mahjong 一大把
    newtype0092
        12
    newtype0092  
       2019-06-04 15:52:23 +08:00
    写过个简单的递归算法:
    0.所有牌按 id 排序,这步可以在发牌时就做插入排序,这样手牌始终是有序的
    1.取最左边一张牌,依次检查所有成副的牌型[对、刻、杠、顺]
    2.不成副或超过两副对(全是对有的地方有七对的胡法)说明不成胡,继续检查下一副牌型
    3.成副则用除去这副的剩下的牌继续取最左边一张从第 1 步递归
    4.所有牌都成副就是胡了
    Narwhal
        13
    Narwhal  
       2019-06-04 15:52:37 +08:00
    AI 雀士爆打が天鳳 9 段という衝撃の事実が知れる麻雀本 | 麻雀グッズ研究所
    玩天凤的都知道天凤有个 AI 帐号 稳定高分段
    antonia0912
        14
    antonia0912  
       2019-06-04 15:59:57 +08:00
    算法不太懂,但是你要让我打麻将,我可是一个相当厉害的牌友哦
    c4f36e5766583218
        15
    c4f36e5766583218  
       2019-06-04 16:45:17 +08:00
    我觉得还行。(这个三角函数我不会
    murmur
        16
    murmur  
       2019-06-04 16:51:28 +08:00
    日麻算法不是黑鸡儿复杂,还要算役的
    dallaslu
        18
    dallaslu  
       2019-06-04 17:24:07 +08:00
    一个角度叼钻的思路:
    https://dallaslu.com/mahjong-regex/
    unknowncheater
        19
    unknowncheater  
       2019-06-04 17:35:35 +08:00
    這思路牛皮嗷,假裝自己會麻將
    luob
        20
    luob  
       2019-06-04 18:22:30 +08:00
    如果有胡牌算法,那我可以提供一个非常暴力的出牌算法:遍历一下出哪张牌能让剩下的牌向听数减少就行了,至于向听数,也用暴力计算,用胡牌算法遍历 27 种牌
    已知随机 14 张牌的向听数期望约等于 3,所以此出牌算法的复杂度是胡牌算法的 27*27*27*14 ≈ 3x10^5 倍 ……(逃
    godoway
        21
    godoway  
       2019-06-04 18:30:28 +08:00 via Android
    @murmur 算役还好,写算符才蛋疼,当你写好算符的时候差不多就是写了半个游戏逻辑了。
    bzq2810
        22
    bzq2810  
       2019-06-04 18:30:55 +08:00
    考不考虑国士无双和九莲宝灯这类牌型?
    sardine
        23
    sardine  
       2019-06-04 18:35:00 +08:00
    带惠么?
    simonlu9
        24
    simonlu9  
    OP
       2019-06-04 18:42:41 +08:00
    @bzq2810 九宝莲灯也可以啊
    @sardine 不带鬼
    simonlu9
        25
    simonlu9  
    OP
       2019-06-04 18:43:06 +08:00
    @lkan 斗地主还没想过呢,不过应该没麻将难
    simonlu9
        26
    simonlu9  
    OP
       2019-06-04 18:43:49 +08:00
    @msg7086 在 github 上看过,不过没看懂思路
    simonlu9
        27
    simonlu9  
    OP
       2019-06-04 18:44:43 +08:00
    @dallaslu 确实 6,用正则实现
    simonlu9
        28
    simonlu9  
    OP
       2019-06-04 18:46:41 +08:00
    @newtype0092 可以啊,有源码参考一下吗,现在还有一个问题是,胡牌写出来,如果效率可以的话我觉得听牌的效率也会提高,听牌的思路不知道是不是遍历每一张牌去判断
    simonlu9
        29
    simonlu9  
    OP
       2019-06-04 18:47:17 +08:00
    @rogwan 确实,麻将这种太复杂
    simonlu9
        30
    simonlu9  
    OP
       2019-06-04 18:48:09 +08:00
    @Narwhal 哈哈,我之前也是看日麻学麻将的,因为老是输,所以看看有没有一些技巧和套路,日麻研究麻将确实是有一套
    simonlu9
        31
    simonlu9  
    OP
       2019-06-04 18:49:04 +08:00
    @luob 问题有一个,没胡之前怎么判断那一张牌出呢
    simonlu9
        32
    simonlu9  
    OP
       2019-06-04 18:50:12 +08:00
    @zsc8917zsc 可以,变成七对子啦,不过这个算法不考虑,特殊胡牌型可以单独处理
    icekingcy
        33
    icekingcy  
       2019-06-04 18:52:21 +08:00 via iPhone
    还要考虑一些癞子玩法,嘿嘿嘿…

    最佳做法只能查表
    simonlu9
        34
    simonlu9  
    OP
       2019-06-04 18:56:14 +08:00
    @jsun 这个好像没有自动出牌的功能
    simonlu9
        35
    simonlu9  
    OP
       2019-06-04 18:57:40 +08:00
    @icekingcy 查表的思路是不是把胡牌的所有可能牌型整理成一个表,然后去查,是不是这样
    wploey
        36
    wploey  
       2019-06-04 19:00:19 +08:00 via iPhone
    想做成小程序之类的,但是实力不允许🤣
    kevinlm
        37
    kevinlm  
       2019-06-04 19:00:56 +08:00 via iPhone
    哈夫曼算法呀…
    ejq
        38
    ejq  
       2019-06-04 19:31:21 +08:00 via Android
    NOI 2014 团体对抗赛(
    duan602728596
        39
    duan602728596  
       2019-06-04 19:38:04 +08:00 via iPhone
    还有 huì儿、十三幺、七对的胡牌呢
    BiteTheDust
        40
    BiteTheDust  
       2019-06-04 20:07:18 +08:00
    搞估价函数那套吧
    garzon
        41
    garzon  
       2019-06-04 21:20:46 +08:00
    lyshine
        42
    lyshine  
       2019-06-04 21:27:30 +08:00
    v 站真是出人才. 我到现在还没体验到牌和麻将里面的智慧
    garzon
        43
    garzon  
       2019-06-04 21:28:35 +08:00
    再附送讨论最优实现算法的论文一篇 https://arxiv.org/pdf/1903.03294.pdf
    icekingcy
        44
    icekingcy  
       2019-06-04 22:15:17 +08:00 via iPhone
    @simonlu9 Bingo !
    msg7086
        45
    msg7086  
       2019-06-04 22:19:39 +08:00 via Android
    @simonlu9 #24 虽然汉字顺序不影响阅读,但那是九莲宝灯。
    newtype0092
        46
    newtype0092  
       2019-06-05 08:06:06 +08:00
    #28
    源码没了,太早了。。。
    停牌的思路和前面说的混、癞子、万能牌的算法是一样的。
    假如一开始手里有 n 张万能牌,检查牌是否成副时,如果当前最左边的是 1 万,检查的是 123 万,这时如果 n>1 要多检查两种情况 12x 和 1x3,如果成牌的话 n-1,然后继续往下走。
    如果允许两张万能牌的话还要检查 1xx,成牌的话 n-2,然后继续往下走。

    听牌的算法就是当你打出 1 张后手上剩 13 张,这时假设手里多 1 张万能牌,然后用胡牌算法算一下,有多少种胡法,就是听多少张。
    w274189159
        47
    w274189159  
       2019-06-05 08:34:57 +08:00
    @OxQMask #6 我怀疑你和我同一个地方。。我玩过很多地方的麻将。只有我那边有赖子
    turi
        48
    turi  
       2019-06-05 09:15:38 +08:00
    贪心
    pricesong
        49
    pricesong  
       2019-06-05 09:48:40 +08:00
    hh,经验早就有总结了,遇到运气都是扯淡。

    你吃别家碰
    你立别家胡
    你听就出铳
    不铳就弃胡。


    @simonlu9
    mk0114
        50
    mk0114  
       2019-06-05 09:49:00 +08:00
    我写了一个自动打雀魂的机器人,用 opencv 搜索图片识别,简单的只考虑了在为了向听数下降而打那张牌,牌效率练习

    没有考虑防守、点数、吃碰杠。目前只打到了雀杰。。。https://github.com/mk014/mahjong
    Eugene1024
        51
    Eugene1024  
       2019-06-05 09:52:24 +08:00
    麻将的精髓在于变化,每一局都不一样
    mk0114
        52
    mk0114  
       2019-06-05 10:13:08 +08:00
    发现了一个更牛的,但是我不懂 go
    https://github.com/EndlessCheng/mahjong-helper
    HanMeiM
        53
    HanMeiM  
       2019-06-05 11:01:17 +08:00
    这个还是要考虑怎么出牌的吧。
    有的人不打生章,有的人喜欢把生章打出去。。。。
    z960112559
        54
    z960112559  
       2019-06-05 11:07:01 +08:00
    只要找对那对将牌就比较好判断了,反正胡牌必有一对将,剩下手里牌按三个一组移除,移除完就能胡牌了(普通胡),七对那些另算
    z960112559
        55
    z960112559  
       2019-06-05 11:09:00 +08:00
    游戏地方麻将有癞子,有幸做过一次宜宾麻将,最多 11 个癞子,还得根据癞子算最大番,搞死人
    winglight2016
        56
    winglight2016  
       2019-06-05 13:21:31 +08:00
    枚举全部的胡牌可能组合,放到 hashmap 里,这样更容易适配不同规则
    coderluan
        57
    coderluan  
       2019-06-05 14:13:43 +08:00
    重点:麻将是竞技游戏,不是单机,只算自己牌不算对手牌,基本只能输死。
    slime7
        58
    slime7  
       2019-06-05 14:35:10 +08:00
    出牌算法熟悉一下某个流派,然后按这个流派的出牌优先级就可以了,进攻和防守都会涉及;比如人脑费力的饼流,反正计算机不会累。
    jabari
        59
    jabari  
       2019-06-05 14:56:27 +08:00
    10.1007/s11042-019-7682-5
    jimliang
        60
    jimliang  
       2019-06-05 14:59:13 +08:00
    光看牌效没有用,还有各种防守、副露策略,每一把都要根据情况作出对策,什么时候防什么时候攻,该弃就弃不要头铁。这些都是不简单的算法可以实现的。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5223 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 07:22 · PVG 15:22 · LAX 00:22 · JFK 03:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.