songxu 发布的文章

语言解释器的实现

出于个人情怀和早期对语言实现的兴趣,最近业余时间写了个简化版语言解释器,性能是python的3倍左右,几乎包含语言所有的特性,下面主要讲一下核心实现,感兴趣的可以直接看golang源码:https://github.com/song2010040402102/cy

词法分析

词法分析主要对一个表达式进行分词,把各个变量和运算符拆分到一个array中,遇到()或function,把它当成子表达式递归处理即可

语法分析

语法分析相对词法分析较为复杂,首先需要把词法array中的运算符中同名不同含义的进行转化,例如,-既可以作为一元运算符负号也可以作为二元运算符减号,++要分析是先赋值还是先自增,然后根据运算符的优先级构造语法树,其中叶子节点存储变量,其它节点存储运算符,而每个子节点的数量取决于运算符的元数,对于一元运算符要根据结合方向来选择左边还是右边的表达式作为子节点。为了通用起见,可以定义运算符的优先级、结合性、元数等

语义分析

语义分析对于自然语言非常复杂,对于计算机语言可以简单理解为像c语言编译器在编译过程报的错误或警告,即处理变量类型是否可转换或运算符是否可操作当前的变量类型等等。为了通用起见,可以定义一个变量和运算符的语义表

符号表

符号表用来表示每个变量的名称和类型,在程序运行时,用于申请堆栈的大小

符号表又分为全局符号表和函数符号表,在符号查找时,优先查找函数符号表,查找失败再查找全局符号表

由于函数可能会嵌套一些条件和循环语句,所以函数符号表是个树形结构,应该沿着当前节点往树根方向查找

指令生成

程序运行时,不可能沿着语法树来执行,会大大降低执行效率,因此需要把语法树转换成线性指令,转换过程只需要深度优先遍历即可

控制语句

像if、while、continue、break、return等都可抽象成运算符来处理,if运算符逻辑决定执行哪个语句块,while运算符逻辑决定是否要循环执行语句块,continue、break、return通过改变程序计数器来控制当前执行哪个指令

以上六个部分是解释器的核心,其他像变量、函数声明,堆栈空间申请与释放,ebp、esp、eax、pc等寄存器使用都相对比较简单,不再赘述

通用数据平台搭建

数据流格式设计

数据流信息包含时间戳、用户唯一id、用户画像信息、用户行为信息,而好的数据流需要满足通用、可扩展、占用空间少等特性,可设计如下:
data-format.png

timestamp:数据流产生的时间戳,占4字节。

uid:为用户全服唯一id,占4字节,对于可能超过4亿的用户,建议用8字节。

flag:用户画像标识位,用来标示数据流中都含有哪些用户画像信息,占1字节,可最多表示8种用户画像信息,目前常用的画像信息包含性别、年龄、地域、设备、渠道等,所以1个字节基本够用。很多人会疑问,每种数据流或仅登录数据流中包含所有用户画像信息不就ok了吗,但为了全面分析不同数据流的用户画像分类结果又要剔除一些不需要所有用户画像的数据流,这是全面性和存储空间的平衡设计。譬如在登录数据流中需要尽可能包含所有用户画像信息,在付费数据流中,你可能更关注的是性别和年龄而非所有用户画像信息,这个时候就需要flag来标识。

profile:用户画像信息,性别、年龄、地域、设备取值范围可用1字节表示,渠道号各种类型都有,可用字符串表示。

action:用户行为,包括注册、登录、付费、提现、看广告、自定义界面点击等,简单应用可用1字节表示,大型应用可用2字节表示。

para:用户行为参数,对于登录,参数可为空,付费,则为充值金额,购买,则为商品信息,包括商品数量、种类等。

数据流存储与处理

传统的数据库很难对海量的数据进行存储与处理,而hadhoop的特性刚好与用户行为数据的特点不谋而合,一般都是大规模、写一次读多次,且hadoop会尽量将数据处理任务分配到离数据存储最近的节点上,可减少数据传输时间,但hadoop的使用属于程序的工作,不再赘述。

为了便于讲解数据流的通用处理,数据流用Flow表示,每个action对应的数据流用Fa表示。对于一个action产生的指标集为不同维度下的次数、人数、人均次数,这里次数是指广义上的次数,不仅包括狭义上的次数,还包含可累加参数值求和,对于人均次数稍后可用表达式来实现,暂不讲。若维度数量用Dn表示,Flow中用户画像字段数用Un表示,分类参数数量用Pn表示,则Dn=Un+Pn。讲到这里,绝大部分人都会懵,因为太抽象了,我给大家举个例子。

拿购买Flow来讲,通常购买Flow中会包含用户的性别和年龄信息,其action对应的para会包含购买数量、商品颜色等信息,这里的性别和年龄表面上是用户画像字段,其本质上也是分类参数,因为我们不关心用户画像的累加,而仅关心其分类,同样商品的颜色也是分类参数,但商品的数量通常我们不关心其分类,仅关心累计购买多少数量,所以其指标集包含两种情况,一种是狭义上的次数,不同性别、不同年龄段、不同商品颜色的点击购买次数、人数,另一种为广义上的次数,不同性别、不同年龄段、不同商品颜色的购买总数量、人数,两种情况下的人数含义相同,取其一即可。

因此,要想从原始Flow得到其指标集,首先确定Flow中的para哪些是分类参数,哪些是累加参数,然后把画像中的字段和分类参数一起组成维度组,最后在求得各累加参数和不含累加参数两种情况下,对维度组的所有排列结果,且每个维度组的排列都对应一个维度组的分类树。讲到这里,几乎所有人都会懵,因为比刚才还TM抽象,我再举个例子。

还拿购买Flow来讲,维度组D={sex、age、color},累加参数组Pa={num},维度组的所有排列为A(3,3)=6,即有6种可能的排列,例如D1={age、sex、color},表示年龄段为一级分类,性别为二级分类,颜色为三级分类,D2={color、sex、age},表示颜色为一级分类,性别为二级分类,年龄为三级分类,因此维度组的所有排列就是为了罗列每个维度所在分类级别的所有情况。至于分类树比较好理解,当确定了维度组D={sex、age、color}之后,性别只有男女两种情况,当然不排除第三种情况,年龄可分为(0, 20)、[20,40)、[40,-1),颜色可分为红、黄、蓝,分类树如下图:
class-tree.png

其中,分类树中的每一个节点都代表每级确定分类下的广义次数和人数。例如女性节点代表女性用户的购买总金额和人数,女性节点下的第一个子节点代表女性用户中20岁以下用户的购买总金额和人数。

由此可见,指标集个数=(累加参数数量+1)*维度组的排列数,每个指标又存在一个分类树,计算量会很大,但通常数据分析的需求不会有这么多种情况,所以可以动态的传递需求参数来获取我们想要的结果。

需求参数有4个,第一个参数用来标记para中哪些是累加参数,哪些是分类参数,第二个参数用来确定要计算的是累加参数还是非累加参数,若是累加参数,具体又是哪个累加参数,第三个参数用来确定维度组是如何排列的,第四个参数用来确定分类树中的哪个节点。

以上讲的是针对一个action的指标计算,那多个action的情况呢,例如在计算DAU时,仅需要Login这一个action的Flow,但若计算注册留存,就需要Register和Login两个action的Flow来处理,这类情况就很难通用处理,好在数据分析时这种情况不多,我们可以对多个action共同决定的指标做单独处理,但维度组和分类树的思想是不变的,只是维度组不再是确定的,根据实际需求自定义即可。

写到这里,很多人觉得数据处理应该到此结束,但很不幸的是,处理到这种程度是远远不够的,因为之前处理的都很纯粹,就是计算次数和人数,若想知道人均次数、各环节转化率、arpu等,之前计算就很难满足。为了解决这类问题,我们引入合成指标的概念,若合成指标用Ic表示,各action的指标用Ia表示,则Ic=F(Ia1, Ia2...),F为运算,包括算术与函数运算。这里算数运算可以仅实现加减乘除带括号就足够用了,函数运算可以把常用的求平均、求最值等实现即可,这里需要用到编译器相关知识,没关系交给程序就好了。除此之外,还需要对值进行修饰,譬如保留精度、转成百分比、对合成指标命名等。最后,往往我们想同时查看多个指标的对比情况,比如把DAU和arpu放一起查看,就需要把多个指标并行计算再结果合并。以上运算、修饰、合并等可设计一个通用指标表达式即可,思想比较简单,实现却很复杂。

至此,数据处理结束,除了很少见的多个action共同参与的指标计算外,其它指标的计算在数据处理层都是通用的,没有特殊逻辑,每个指标的定义都是通过action的Flow定义、四个输入参数、指标表达式来决定,分类树节点参数可选,这样就可以构建一个参数串到常用指标的关联,便于快速查询。

结果展示

若提供分类树,结果为一个二维表结构,横向为指标,纵向为时间,若不提供分类树,结果为一个N维表结构,若分类树深度为D,则N=D+2,N维表结构需要二维化到平面才能显示,可采用表格嵌套来实现,如下图所示:
video-statistic.png

多维表格用html实现比较简单,若导出至excel,就需要由内而外计算每层表格所占单元格的长宽,然后进行单元格合并,这个过程也是相当复杂,目前还没见过哪个数据平台能导出多维表格,感兴趣的读者可留言。

虽说多维表格是一个很通用的数据展示方式,但不够形象直观,对于比较常用或重要的数据可接入AntV来显示各种统计图。

还有一些需要实时显示的指标,例如用户增长、付费增长、同时在线人数等,可每隔一段时间自动请求处理并显示。

至此,结果展示结束,很多大公司的数据平台基本都是如此。但从通用性的角度来讲,以上提到的很多抽象的概念和思想,目前商用的数据平台基本都不具备。

通用数据平台的搭建,到此讲解完毕,本篇可能太注重思想,缺乏一些实际的项目来实践,导致看完后会觉得晦涩难懂,但仔细思考后就会有豁然开朗的感觉,思想高度会有很大的提升!项目地址:https://github.com/song2010040402102/log_track

golang调试

golang程序调试工具有gdb、godebug、delve等,gdb原生支持c/c++程序,对golang语法支持比较差,godebug专为golang调试开发,目前功能尚不完善,不支持attach等,delve工具可以说是golang的gdb,支持golang在调试模式下运行、attach、调试core等,所以目前采用delve工具调试golang是最佳选择

  • delve安装

delve项目地址:github.com/go-delve/delve/,克隆到GOPATH目录下,然后执行make install,最后把dlv所在目录加到PATH路径即可

由于delve对golang的版本有要求,我的golang版本是1.8.3,编译最新的delve出错,所以尝试几个老版本,亲测devle的1.2.0版本可正常安装,所以需要checkout到1.2.0,然后再编译安装

  • delve使用

delve的帮助与gdb类似,dlv --help 可查看delve有哪些子命令,具体子命令用法例如debug,可输入dlv debug --help
dlv debug 可直接调试golang源文件
dlv exec 调试golang二进制程序
dlv attach 可对正在运行的程序截取快照进行调试
dlv core 可调试崩溃文件

  • golang崩溃

go程序在崩溃时,其崩溃所在的goroutine会执行每个栈帧对应的defer函数,若执行recover函数获取panic信息,可避免进程异常退出,仅仅其所在的goroutine退出,但通常情况下程序出现异常是需要进程退出,否则会出现未知逻辑错误

在程序异常退出时,若在defer函数中采用runtime.Stack()获取栈信息,则需要在每个goroutine中都要加defer函数,比较麻烦,若截获SIGSEGV等异常信号,golang又不像c语言那样可设定每个信号的handler,一旦异常信号出现采用golang的notify机制却捕获不到,即使采用defer或者c语言的handler方式,采集到的栈信息已经不在崩溃点,所以异常信息只能采用coredump来解决,而golang在崩溃时,默认仅产生当前goroutine的崩溃信息,并没有产生core文件,因此需要修改其运行时环境,让其产生core文件

  • GOTRACEBACK

GOTRACEBACK是golang运行时环境变量之一,用于控制go程序崩溃时的处理,有以下几种取值

GOTRACEBACK=none,仅产生panic信息,不产生栈信息
GOTRACEBACK=single,在none基础上,产生当前goroutine的栈信息
GOTRACEBACK=all,在none基础上,产生所有goroutine的栈信息
GOTRACEBACK=system,在all基础上,产生包括runtime的栈信息
GOTRACEBACK=core,在system基础上,产生core dump文件

默认是single,所以仅需要执行 env GOTRACEBACK=core ./xxx.exe,即可产生core文件,若采用sudo方式运行程序,由于sudoer账户在运行程序前会重置当前用户环境变量,所以需要修改/etc/sudoers文件,注释掉Defaults env_reset,添加Defaults !env_reset
更多运行时环境变量可参考https://dave.cheney.net/2015/11/29/a-whirlwind-tour-of-gos-runtime-environment-variables

系统默认产生core文件大小限制为0,即禁止产生core文件,需执行ulimit -c unlimited,若需要修改core文件名称为程序名.core.pid,则需要修改/etc/sysctl.conf文件,在文件后追加kernel.core_pattern =%e.core.%p
kernel.core_uses_pid = 0
然后执行sysctl -p生效

TLS证书校验

TLS证书校验:对称加密、非对称加密、数字签名、单向校验、双向校验、自签证书、受信任证书

  • 对称加密

用秘钥对信息加密后,可用相同的秘钥进行解密,常用的有DES和RC等系列算法,优点是加密算法执行效率高,缺点是秘钥易泄露,不利于开源,所以常用于本地文件的加密

  • 非对称加密

用公钥对信息加密后,只能用对应的私钥进行解密,或者用私钥对信息加密后,也只能用对应的公钥进行解密,用私钥可生成相应的公钥,用公钥生成不了对应的私钥,使用最广泛的是RSA算法,优点是秘钥管理简单,私钥保留在本地,公钥可随意公布,缺点是非对称加密算法执行效率低,不利于对大量信息进行加解密

  • 数字签名

对任意长度的信息可采用信息摘要算法生成几乎唯一的大整数,所谓几乎就是冲突的概率极低到忽略不计,常用的有MD和SHA等系列算法,数字签名就像指纹一样可唯一标记一个个体,信息一旦被篡改,其摘要也会变

  • 单向校验

TLS是针对基于TCP的应用层协议加密技术,例如FTPS、HTTPS,而基于UDP的应用层协议加密技术由于TLS未处理丢包情况,所以采用基于TLS的DTLS,由于DTLS应用较少,所以暂不研究。
以HTTPS为例,为了充分利用对称加密和非对称加密的优势,通常在秘钥协商阶段采用非对称加密,确定秘钥之后接下来的通信都采用对称加密,而非对称加密过程表面看起来能保证秘钥的安全,但若是客户端和服务器之间通信被黑客劫持,架设一个中间代理,很容易导致正在传输的信息被非法篡改而无法感知,篡改过程如下图所示:tls_fake.png

只有让客户端收到的公钥和服务端发送的公钥一致才能保证信息不被篡改,所以一般会采用第三方的信任机构(CA)签发的证书来保证公钥的一致性,证书主要包含公钥、数字签名、颁发者等信息,证书的校验主要针对数字签名的校验,而数字签名的生成是先对证书中除去签名部分采用SHA算法生成摘要,然后用CA的私钥对其加密,而校验过程则采用CA证书中的公钥对数字签名解密再与SHA算法生成的摘要做对比,以W/S为例,浏览器通常在出厂时,会内置很多第三方根信任证书,chrome和IE则直接用系统的证书管理器,而firefox则采用开源的NAS证书管理,当然也可以采用自签证书来验证,因为自签证书不被信任,所以自签证书需要手动添加到浏览器的证书管理器中,否则浏览器就会告警此网站证书不被信任,试了很多次,导入自签证书后,IE和firefox均未告警,而chrome依然告警,可能是chrome有更严格的验证机制。单向校验的完整过程如下:one_verify.png

  • 双向校验

通常仅校验服务端证书即可,有时需要指定客户端访问就需要双向校验,即服务器与客户端相互校验对方证书,校验过程如下:two_verify.png

  • 自签证书

用个人生成的证书来签发客户端和服务器证书,优点是免费,可用openssl库生成,缺点是自签证书无法内置到浏览器,去除告警只能手动添加

  • 受信任证书

用根证书颁发机构来签发客户端和服务器证书,优点是浏览器内置,缺点是费用较高,腾讯云有免费1年的,但是加了文件验证之后还TM提示我验证失败,巨坑!

  • 实战

以https的双向校验为例,采用openssl生成秘钥及证书,golang实现其验证过程

  1. 首先生成自己的CA秘钥及证书
    openssl genrsa -out ca.key 2048
    openssl req -x509 -new -nodes -key ca.key -subj "/CN=songxu" -days 5000 -out ca.crt
  2. 生成服务端秘钥及用CA来签发其证书
    openssl genrsa -out server.key 2048
    openssl req -new -key server.key -subj "/CN=localhost" -out server.csr
    openssl x509 -req -in server.csr -CA ca.crt -CAkey ca.key -CAcreateserial -out server.crt -days 5000
  3. 生成客户端秘钥及用CA来签发其证书
    openssl genrsa -out client.key 2048
    openssl req -new -key client.key -subj "/CN=localhost" -out client.csr
    openssl x509 -req -in client.csr -CA ca.crt -CAkey ca.key -CAcreateserial -out client.crt -days 5000
  4. 服务端代码
    tls_server.png
  5. 客户端代码
    tls_client.png

完整代码可参考我的github

麻将AI - 向听搜索

麻将AI主要包含:胡牌算法、听牌算法、N向听牌算法、出牌算法、叫牌算法

  • 胡牌算法

胡牌即满足3n+2,3为刻或顺,2为将,所以判断一副牌是否胡牌仅需抽出一对将,看剩下的牌是否全是刻或顺即可

在遍历一副牌时有两种方式,一种是按优先级线性遍历,即先取出一对将牌,接下来按刻>顺>对>连>单的优先级取牌;另一种采用平级树状遍历,即亦取出一对将牌后,接下来把每层的可能性递归展开

以{1万1万2万2万2万2万3万4万}为例,采用优先级线性遍历结果为{[1万1万]、[2万2万2万]、[2万3万4万]},采用平级树状遍历结果分别为{[1万1万]、[2万2万2万]、[2万3万4万]}、{[1万1万]、[2万3万4万]、[2万2万2万]},看似两种方式都可以判断是否胡牌且第二种方式反而麻烦,事实上这仅是众多牌型中非常简单且不含癞子牌情况,然而很多地方麻将规则都有癞子牌,数量通常在3、4、7张不等,甚至有些规则癞子牌不止一种,在这种情况下采用优先级线性遍历就无法判断是否胡牌,仅能采用平级树状遍历。以{1万1万2万2万3万4万5万2筒2筒3筒4筒5筒癞癞}为例,采用优先级线性遍历结果为{[1万1万]、[2万3万4万]、[2万癞癞]}...,且判断其未胡牌,而采用平级树状遍历结果为{[1万1万]、[2万3万4万]、[2万癞癞]}、{[1万1万]、[2万2万癞]、[3万4万5万]、[2筒2筒癞]、[3筒4筒5筒]}...,且判断为胡牌,所以两种方式各有优缺点

优先级线性遍历:优点算法简单、执行效率高,缺点不适用一般性地方麻将,且获取不了所有的分组情况
平级树状遍历:优点可适用一般性地方麻将,可获取所有分组情况,缺点算法复杂、执行效率稍慢。因为听牌等算法都依赖于平级树状遍历,所以接下来详细介绍其算法

平级树状遍历第一层节点为一副牌中所有可能的将牌,分三种情况:牌数大于等于2、牌数等于1、牌数等于0,例如有3个1万,可取出2个1万作将,有1个2万,可取出一个2万并凑1个癞子作将,牌数等于0只能凑两个癞子作将,第二层到最后一层则依次取出所有可能的刻和顺,分五种情况:不需要癞子的刻、不需要癞子的顺子、需要一张癞子的对、需要一张癞子的连、需要两张癞子的单,如下图所示hu.png

若将牌的可能性为k,树的深度为d,则遍历的时间复杂度为k×5^(d-1),以14张手牌为例,树的深度为5,k取值范围[1,13],取平均为7,则时间复杂度为4375,但通常情况下,那五种情况越靠后,越不太可能胡牌,即分支被截断的可能性越大,其实际时间复杂度会比理论值小得多,但若不考虑靠后的情况,则会忽略一些极端情况下的胡牌,而且一般情况下除去吃碰杠后的牌,实际手牌可能是10张、7张等,少三张就意味着树的深度减1,其时间复杂度会成指数级下降,所以此算法放到服务端也是可行的

通常在麻将结算时都需要获取其分组信息,实际上分组信息就是所有满足深度为d的分支,小于d的都是未胡牌分支,由于树状结构的分支的各节点间存在排列不同但组合相同的情况,所以在最终处理分组结果时,注意对相同组合不同排列的分支除重

  • 听牌算法

听牌即满足来1张牌即可胡牌,所以听牌算法本质就是胡牌算法,由于麻将牌种类有34张,依次带入会很影响性能,所以采用带入一张牌,若带入一张特殊牌,特殊牌的id和所有普通牌的id间隔均大于2,若胡牌,则听任意牌,若带入一张癞子牌后胡牌,则听有限牌

在获取听有限牌时,需分析满足胡牌的分组信息,分组信息实际是上文的树状结构转化后含所有分支的二维数组,数组中的元素实际是树状节点,而听牌信息都保存在含癞子的节点,分为1癞子将、1癞子对、1癞子连、2癞子单四种情况

1癞子将:听节点第一张牌,例如节点[1万癞],则听1万
1癞子对:听节点第一张牌,例如节点[1条1条癞],则听1条
1癞子连:若节点前两张间隔为1,则听两边,例如节点[5万6万癞],则听4万、7万;若间隔为2,则听中间,例如节点[5条7条癞],则听6条
2癞子单:听节点第一张牌及其前后各两张牌,例如节点[5万癞癞],则听3万、4万、5万、6万、7万

在遍历完所有节点并取出其听牌后,由于各节点的听牌可能存在交集,所以需要对听牌结果进行除重

  • N向听牌算法

若来一张牌即可胡牌,定义为听牌,来一张牌打出一张牌即可听牌,定义为1向听牌,来一张牌打出一张牌即可1向听牌,定义为2向听牌,则N向听牌可递归定义为来一张牌打出一张牌即可N-1向听牌,而上文中的听牌算法实际是N=0时的N向听牌算法,因此听牌算法也是N向听牌算法的基础

若手牌数为M,按上文定义并依次递推,则N向听牌可理解为从M张手牌中选出N张牌打出,并来N张牌,若听牌,则为N向听牌,其中选出N张牌打出并来N张牌,可转化为把选出的N张牌替换为癞子牌,因此N向听牌的时间复杂度为组合数C{M,N}*Ot,Ot为检查听牌的时间复杂度

由于N是定值,而Ot又依赖听牌算法,所以仅能通过减小M来优化此算法。由于在选出的N张牌中,不太可能出现两张一样的牌,因此可把M张牌进行除重以此来减小M值,但存在一种可能,当手牌中对子数大于等于5时,需要选出一对牌,否则会影响向听结果,也可以提前去除手牌中独立的刻、顺(前后都没有相关牌)来减少M值,当然还有一些尚待研究的方法来减少M值

在选牌算法上,有两种遍历方式,一种是递归深度优先遍历(RDT),一种是循环广度优先遍历(CBT),如下图所示NTing_group.png

图中是从1万2万3万4万中选择1张、2张、3张的情形,在判断是否为三上一听的时,除了要选择3张之外,还需要选择1张、2张的原因是有可能一副牌为一上一听或两上一听,所以在遍历时,一旦出现选2张、1张就能听牌的情形,就无需考虑3张、2张的情形,如图所示,CBT满足此特性,而RDT不满足此特性,但是可通过剪枝来尽量满足此特性,图中绿色分支表示选2张和1张牌就能听牌,红色分支为被剪部分,很明显如果能把第一层节点中的2万和1万对换,剪枝效率会大大提高,因此可通过对每层节点预排序来提高剪枝效率,而排序的标准就是出牌的优先级,但出牌的算法又依赖向听算法,只能采用按权重出牌来对节点排序,权重算法属于出牌算法的一种,放到下文分析

从上文分析可知,在算法效率上,RDT在剪枝效率达到极限情况下,才能和CBT一样,为何还要介绍RDT呢,原因在于上文提到的拆对子情况,当需要选出一对牌时,CBT难以实现,而RDT可在倒数第三层的节点上针对拆一对牌进行特殊处理,况且经过预排序加剪枝后的RDT和CBT的效率相差并不大,所以在追求准确、牺牲一点效率的情况下可采用RDT,在追求效率、牺牲极端错误结果的情况下可采用CBT

  • 出牌算法

对于业余的机器人可采用按权重出牌,有三个权重因子,牌数量、关联度、位置,牌数量即单、对、刻、杠,按杠>刻>对>单的优先级来出牌,关联度即与前后两张牌的距离,例如3万4万和3条5条,会优先打3条,位置即牌与5的距离,越靠近中间位置越好,5最好,1、9最差,因此三个权重因子的优先级为牌数量>=关联度>>位置,当遇到对和连时,此时牌数量和关联度优先级相等,例如4万4万和5条6条,打四万也行打6条也行,由于位置因子一般情况下可忽略,只有在前两个因子相等时,才会考虑位置因子,所以前两个因子都远大于位置因子。把每张牌按三个权重因子计算一个综合系数后按从小到大排序后,打出第一张牌即可,因此权重只是出牌的简单策略,对于一些复杂结构的牌型,权重策略难以实现最优解,因此上文的RDT采用此算法进行预排序只能提高剪枝效率,不能保证最高剪枝效率

对于专业的机器人可采用按向听出牌,首先按权重依次尝试打牌,然后看打牌后的向听数及听牌数量,向听数越少、听牌数量越多,越优先出牌,按权重依次尝试的目的是尽可能先出差牌,得到较低的向听数,然后取当前最低的向听数来作为向听算法的输入向听数,可大大提高效率。初始输入向听数,可根据当前手牌数和癞子数来确定,理论上可取手牌数/3-癞子数

  • 叫牌算法

业余级机器人可按照简单的杠>碰>吃的优先级来处理,但对于专业的机器人,需要区分在叫牌前后向听数的变化来决定是否叫牌

首先获取叫牌前手牌的向听数,对于有摸牌情况,即暗杠和补杠,需要把摸牌加到手牌中,然后用向听算法打出一张牌,再判断此时手牌的向听数,假设为N0,接着获取叫牌后手牌的向听数,因为可能同时存在多种叫牌,所以需要依次尝试

暗杠,即把暗杠相应的四张牌从手牌中移除,判断此时的向听数,假设为N1
补杠,即把摸牌移除,判断此时的向听数,假设为N2
明杠,即把明杠相应的三张牌从手牌中移除,判断此时的向听数,假设为N3
碰吃,即把要参与碰吃的两张牌从手牌中移除,然后用向听算法打出一张牌,若出现碰吃的牌和打牌相等,可忽略此碰吃,接着再判断此时的向听数,假设为N4

若N4>N0,可选择碰吃,否则忽略;对于N1、N2、N3,因为不可能大于N0,且杠牌后还可以摸牌,所以只要不小于N0,即可杠牌

由于在叫牌时,手牌中可能有很多单张,此时的向听数会很大,算法非常耗时,可先获取手牌中所有的无关联单张,然后移除3的整数倍的单张,保留3的余数的单张,由于可能存在1张或2张单张,所以尝试的最大向听数Nm为手牌数/3,一般情况下实际向听数Nr<=Nm,若出现Nr>Nm,出于性能考虑,只能忽略极少数情况,暂时没想到对于存在多个单张的情况下,判断主牌的向听数的完美解决方案,还有待研究

  • 项目源码

以上思想的源码实现可参考https://github.com/song2010040402102/mahjong

  • 性能测试

运行源码目录下的script/test.sh,获取测试结果如下:
mahjong_perf_test.png

  • 后续

以上算法在不影响服务端运行效率的前提下,可以根据不同水平玩家匹配相应的机器人,且可适配几乎所有地方性麻将,但是算法针对的仅是自己的手牌,属于完备信息博弈,而真实玩家在打麻将过程中,会根据其它玩家打牌和叫牌等行为来分析其它玩家可能的手牌并给出相应的策略,所以麻将属于非完备信息博弈,最好能通过深度学习来解决,有待于研究......