V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
SakuraSa
V2EX  ›  问与答

关于麻将的算法问题

  •  
  •   SakuraSa · 2014-08-14 21:23:30 +08:00 · 10003 次点击
    这是一个创建于 3514 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1.麻将基本
    (1. 麻将是一种将手中的牌(14张)通过交换变成特定形式从而获胜的游戏
    (2. 当手牌变成 (AA)*2 + (AAA | ABC)*4 的形式时获胜。其中AA表示一对相同的牌,AAA表示3张相同的牌,ABC表示3张牌面数字相邻的不同的牌。
    (3. 当最少只要交换1次就可以获胜时,叫做“听牌”
    (4. 当最少只要交换n次就可以“听牌”时,叫做“n向听”

    2.问题
    通过牌面,计算出当前牌是“x向听”(可记“听牌”为“0项听”;获胜为“-1项听”

    3.当前思路
    http://stackoverflow.com/questions/4239028/how-do-i-calculate-the-shanten-number-in-mahjong
    基本是按照上面搜索到的方法来做的

    4.需求
    希望能在1s内完成1k个手牌的项听数计算,当前我的python实现的算法需要1min才能完成1k次计算。

    5.碎碎念,可以略过……
    我是一名日麻爱好者,可惜实力实在是没法看,以至于在小伙伴里抬不起头……
    于是,就想着通过分析牌谱,找出自己的缺点,找出高手们的技术特点,来改进自己。
    其中,这个向听数计算,就是分析每一步是不是最优的必要算法(评价函数)。
    可惜,想了很久也没有实现快捷的算法。
    现在我手里已经收集了大约1w个牌谱(通过自己的网站,从大家那里收集)。
    如果以现在的算法速度,全分析完成大约要几个月……
    所以现在只能玩一盘,就用电脑跑10min左右的分析……
    想想,自己花在这上面(包括做网站)都快追上打麻将的时间了,可惜麻将水平毫无长进……
    真不知道自己是怎么想的。
    28 条回复    2014-08-15 21:04:01 +08:00
    Cassandra
        1
    Cassandra  
       2014-08-14 21:25:27 +08:00
    玩个麻将这么累,你没救了
    lrz0lrz
        2
    lrz0lrz  
       2014-08-14 21:30:04 +08:00
    @Cassandra 这才是认真的玩麻将嘛。
    Cassandra
        3
    Cassandra  
       2014-08-14 21:33:00 +08:00
    @lrz0lrz 一个游戏这么认真,累不累得慌
    GtDzx
        4
    GtDzx  
       2014-08-14 21:35:16 +08:00   ❤️ 1
    提供一个思路:
    1) 既然你不考虑什么"十三不靠"等诡异胡法,不同的"花色"(条、万、饼)需要的张数是可以分开计算的
    2) 对于每一个"花色",总共有不超过5^9(大约2×10^6)种组合(每个数字可能有0-4张牌),你完全可以预先计算出来每种组合需要的张数,存在内存里
    3) 最后拿到一副牌,分离"花色",对每个花色查表得到需要的张数,然后求和
    4) 可能需要最"风牌"特殊处理一下,不过这个计算量不大
    Automan
        5
    Automan  
       2014-08-14 21:35:30 +08:00
    @Cassandra 享受的是解决问题的过程。
    13k
        6
    13k  
       2014-08-14 21:37:24 +08:00 via iPad
    就要支持这样认真的。
    Cassandra
        7
    Cassandra  
       2014-08-14 21:39:44 +08:00
    @Automan 享受的是玩耍的过程
    SakuraSa
        8
    SakuraSa  
    OP
       2014-08-14 21:46:15 +08:00
    @GtDzx
    1)实际上“十三不靠”、“国士无双”之类的特殊牌型,通过相应的算法是可以以非常低的运算量判断的。比较困难的还是一般型的4~7向听
    2)似乎是个不错的办法~今晚我就去试试
    3)现在我的算法,实际上是搜索出所有牌面可能解释成 AAA, ABC, AA, AB, AC, A 的形式,然后再通过事先计算好的表格得出向听数。中间用了少许剪枝,但似乎没有明显效果。
    aheadlead
        9
    aheadlead  
       2014-08-14 21:46:38 +08:00
    LZ是原村和流的

    天才麻将少女里面那么多诡异的打法...LZ你造吗
    SakuraSa
        10
    SakuraSa  
    OP
       2014-08-14 21:50:06 +08:00
    @Cassandra
    一开始我只是想提高水平啦,后来发现花了很多精力以后,就越来越不想收手了……
    Ansen
        11
    Ansen  
       2014-08-14 22:08:06 +08:00
    七对?
    SakuraSa
        12
    SakuraSa  
    OP
       2014-08-14 22:12:34 +08:00
    @aheadlead
    数据流大概还能学一学,开挂流完全没法学嘛 ฅ۶ó ﹏ò
    Cassandra
        13
    Cassandra  
       2014-08-14 23:08:00 +08:00
    @SakuraSa 简直没救
    aheadlead
        14
    aheadlead  
       2014-08-14 23:16:08 +08:00
    @SakuraSa
    赤宝牌5饼岭上开花,以清一色+对对和+三暗刻+三杠子+赤宝牌1张+岭上开花的13番累计役满
    @saki
    Daniel65536
        15
    Daniel65536  
       2014-08-15 01:06:05 +08:00
    @SakuraSa @aheadlead

    青天井規則:字一色・三暗刻・四槓子・役牌4・嶺上開花・寶牌72
    得點:90,865,195,024,359,483,499,283,685,761,351,700(約為9 × 10^34)點;
    合計140符105飜。
    @小泉純一郎 《渣和无用改革》 第七回 天地創世(Beginning of the Cosmos)

    /* 论渣和是如何吊(kai)着(gua)打(cao)天麻的,PS,小泉的手牌是利用手指摩擦牌面而制造出的白板18张*/
    aheadlead
        16
    aheadlead  
       2014-08-15 01:34:54 +08:00
    @Daniel65536
    saki打出那手牌的时候还只是县内选拔呢...
    msg7086
        17
    msg7086  
       2014-08-15 02:32:16 +08:00 via iPhone
    这种只靠运气的垃圾游戏…
    aheadlead
        18
    aheadlead  
       2014-08-15 02:44:08 +08:00 via iPhone
    @msg7086 你觉得你会不会被喷...
    msg7086
        19
    msg7086  
       2014-08-15 06:28:00 +08:00 via iPhone
    @aheadlead 前天一波好调冲上二段了昨天一路吃翔快跌回初段了,这游戏能玩?

    打啥来啥,起手一向听到死,立直被追立还能点一发,亲家大波立随便切了一张点了个一发七对,再加上牌姬满满的恶意,不是垃圾游戏是啥
    msg7086
        20
    msg7086  
       2014-08-15 06:33:14 +08:00 via iPhone
    顺便to op:

    只分析向听数意义不大,还要考虑进章面,场况,手牌的打点,等等。另外牌姬也是个很大的因素,没牌运,怎么打都是死,牌运好,起手一向,二巡立了一发自摸还能中里什么的…
    jianghu52
        21
    jianghu52  
       2014-08-15 09:19:50 +08:00   ❤️ 1
    我觉得楼主可能有点走偏了。据我所知,目前对于数据应用最强调的还是德州扑克,但是那个应用很多时候也是在针对的是人,而不是出牌策略。
    事实上,楼主做这个策略本身就有问题。你的这个胡牌策略应该是基于河里已经出的牌,来判断剩下的牌哪些更多,然后来做胡。
    但是问题在于,如果是这样的话,你会频繁的换张,从而导致你的下家更快的胡牌。通常来说,我们觉得风牌比较不重要,而万筒条这样的权重相对较高,而万筒条里面的1 9的权重又比较低,如果你引入了权重的概念,那么计算程度恐怕会上好几个数量级。
    再接下来还有上下家的条件,比如上家一个劲的出条子,或者下家一个劲的吃万。那么我们的换张策略也应该跟着变。甚至在危险的牌面下,宁可黄牌也不让其他人胡牌等等。这些都是牌技的一部分,但是如果用算法实现的话,我觉得会很困难。
    SakuraSa
        22
    SakuraSa  
    OP
       2014-08-15 09:36:56 +08:00
    @msg7086
    的确,麻将是个运气成分非常高的游戏
    所以才需要非常多盘的统计,才能将运气成分削减到可以看到真实水平的地步
    现在的网络麻将有着良好的记录系统,
    在加上相应的算法的话,
    我想应该就能更好的辅助选手提高水平

    但是,我自己是水平几乎没有提高,真是很伤心的结果……
    SakuraSa
        23
    SakuraSa  
    OP
       2014-08-15 09:57:34 +08:00
    @jianghu52
    1) “向听数”只是评价函数的一部分。我现在的思路是:

    评价函数 = 向听数 - 下一次摸牌使得向听数减少的概率 + 1

    这样,字牌和19牌的权重自然会小(并且,会根据牌面和打出的牌而不同)
    自认为,这还是一个比较科学的评价手牌好坏的方法(虽然实现似乎很麻烦

    2) 手牌好坏的判断,只是出牌策略的一部分(基础部分)。
    真正游戏中,还要加上 局势判断 ,才能决定是进攻还是防守。
    局势判断,我实在是没什么思路,而且基础部分还没有实现……

    3) 由于我现在希望作的是牌谱分析的系统,而不是麻将AI
    所以一下部分只是想想(而且这部分比上面的要复杂太多了……

    局势判断,我现在的想法是,用选手的 出牌、摸切、副露 为输入,
    训练一个神经网络来估计对手的 手牌进度、手牌大小、是否在进攻 之类的参数
    最后根据这些参数与自己手牌进度、手牌大小,判断如何进攻、防守
    jianghu52
        24
    jianghu52  
       2014-08-15 11:49:56 +08:00
    另外,建议还要再加一个番数的输赢赔率问题。这个在德州里面已经很成熟了。可以借鉴。
    简单来说,就是如果对手是高番数的听牌,那么你应该倾向于快速胡牌,番数的权重降低。反之,可以适当提高番数的权重。同时,这个对于你要打出去的牌也很有影响。
    经常是你为了胡牌而放炮。
    imn1
        25
    imn1  
       2014-08-15 12:51:26 +08:00
    如果你是查表的,1k/min绝对是慢得可以了
    麻将花色不超过6种,每种花色不同的牌不超过10种,所以很适合16进制高低位,多用位运算能加速
    msg7086
        26
    msg7086  
       2014-08-15 13:34:36 +08:00
    另外,推荐看看天凤十段所著的麻将理论书,我觉得说得很专业了。

    http://www.amazon.co.jp/麻雀-魔神の読み-マイナビ麻雀BOOKS-渋川-難波/dp/4839944466 (也有kindle版)
    http://tieba.baidu.com/p/3220055762
    Sunyanzi
        27
    Sunyanzi  
       2014-08-15 20:44:31 +08:00
    http://www.v2ex.com/t/126619#reply17

    供你参考 ... 算法什么的我就不重复说了 ...

    我只想问你为何你的统计只考虑向听数而不考虑避铳 ..?
    SakuraSa
        28
    SakuraSa  
    OP
       2014-08-15 21:04:01 +08:00
    @Sunyanzi
    因为我想不清楚,防御时应该运用的策略的细节……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4669 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 05:35 · PVG 13:35 · LAX 22:35 · JFK 01:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.