分类目录归档:互联网

简评围棋世纪大战

W020160309499767463096AlphaGo与李世石的世纪大战在3月15日落下了帷幕,李世石终于不敌AlphaGo,最后战成了1:4。其中可圈可点的第四盘,AlphaGo走出奇臭无比的黑79手,并没有像很多IT专家开赛前预测的横扫李世石,把无数“专家”们的脸都打肿了。

甚至有很多国内“专家”开始鼓吹人工智能已经战胜人类,甚至人类将要被人工智能统治等无知言论,让人实在看不下去。做为围棋爱好者和一个普通挨踢工作者,这里可以简单说一下AlphaGo的原理和机制。

AlphaGo是一个通用型人工智能程序?这个恐怕是今年最大的误解。

让我们看看背后的英国团队DeepMind的Aja Huang(黄士杰),从2003年硕士论文开始研究围棋打劫程序,到2011年博士论文研究围棋MCTS算法,一直是各大围棋程序研究的中坚力量,其本人也有业余6段水平。DeepMind的创始人Demis还是一个国际象棋13岁的天才大师。DeepMind团队中其他懂围棋的也不在少数,团队更是从去年就开始请欧洲冠军樊麾做他们的全职围棋顾问。

其所使用的算法,主要可以分为三大块:蒙特卡洛搜索(MCTS),快速走子,和深度神经网络。MCTS是目前非常针对围棋的博弈类搜索算法,快速走子是充分利用围棋定式和规则的在极短时间内下子的算法,深度神经网络是一个获取统计知识的训练学习模型。可以看到,只有深度神经网络勉强算作通用性算法,其余都是相当针对围棋这一课题的专业性特殊算法。

最近深度神经网络炒作的火热,甚至有人认为从深度神经网络就可以发展出真正的智能来了。深度神经网络是统计知识的学习算法,它并不具备逻辑知识,从目前应用来看,可以解决一些图像识别问题,但是离真正的人工智能还有十万八千里。

从对弈结果来看,我们也发现了AlphaGo极大的不足:大局观优秀,计算力不行。一个很尴尬的问题就是,为什么计算机还会计算力不行?这实际上还是因为围棋的棋盘太庞大,如果采用全盘搜索,即使深度再深,对于局部来说也搜不到几步。AlphaGo并不像其它围棋程序一样,在局部战斗的时候会临时缩小搜索范围,产生局部最大化的计算力,因此AlphaGo的局部往往会亏损,反而没有职业棋手算的清楚。

计算力不足导致的另一个严重问题是,一旦涉及到复杂的劫争,就会立刻陷入被动,导致崩盘。从对弈过程来看,AlphaGo有意的避免打劫的出现,是有目共睹的。实际上,大局观和局部计算力是任何一个围棋程序难以取舍的两个难点。要大局观,必须全盘搜索,使得局部计算力有一定缺陷。要计算力,必须在局部问题上加以限制,因此往往不会脱先去争别处的好点。

另一个问题是,自我训练(self-train)可以显著提高水平么?这一点在之前被专家们鼓吹的很凶猛,号称一直训练下去可以得到围棋上帝。实际上自己和自己下得到的谱,一般来说是有瓶颈存在的。在两个估价函数相同的程序看来,因为搜索深度和宽度局限,看不到的棋局依然看不到。随便举个例子,两个6岁小孩对下10000局可以提高到职业9段?只有和比你更厉害的高手对弈才可以显著提高水平。这也是AlphaGo团队请了樊麾去做围棋顾问,特训了几个月的原因所在。

Alp470e92b60339250b849feaf4802f0891haGo解决了围棋问题了么?AlphaGo就是围棋上帝?其实远远没有解决。人类研究围棋算法已有超过百年历史,最近十几年MCTS算法也给围棋程序注入了一股新鲜的活力,极大的提高了围棋程序的水平。然而,围棋由于状态空间的庞大,注定是需要更多更长时间来优化的。甚至如果说要完全“解决”围棋问题,搜索完全部的围棋状态空间,恐怕未来50年都看不到任何希望。

从世界范围来看,AlphaGo的算法改进创新上不见得很优秀,在我看来更像是利用了Google庞大的计算资源(相比之下其它围棋程序的可分配计算资源简直少的可怜)而取得的成果。本次对弈尽管从结果上来看非常的出色,机器程序有史以来第一次战胜了人类职业9段,但在我看来依然有着浓重的商业营销味。

围棋是个大问题,棋盘太大,可能性太大,职业棋手确实有时候都无法评价一步棋的好坏。未来几年,也许发展过后的围棋程序可以帮助职业棋手提高水平增强实力,不过如果要把围棋程序和人工智能生扯在一起,我觉得从目前来看依然是远远不够的。

到目前为止,没有任何迹象表明,深度神经网络对统计知识的学习可以表征人类智能,恰恰相反,深度神经网络其局限性也越来越多的被人了解。智能是非常复杂的统计知识的表征么?智能是什么,其实到现在依然是个谜。

 

浅谈部落冲突的协议设计

部落冲突(Clash of Clans)是一款风靡全世界的手机游戏。部落冲突的忽然流行造就了又一家神奇的芬兰公司Supercell,同时也带来了很多关于游戏成功秘诀的讨论。在这里我们暂且不论部落冲突为啥会吸引那么多玩家这个话题,简单来看看部落冲突里的底层协议设计。

部落冲突的底层协议可以说设计的非常的好,从技术上说,也是非常先进而且高效的。首先客户端和服务器端采用RC4进行加密。在第一次握手之后,服务器端会传回一个秘钥seed,然后客户端和服务器端把新seed扔给Scramble7算法,产生新秘钥。这个算法在客户端更新之后还经常进行变换,可见Supercell程序员的用功刻苦程度。算法握手大致描述如下:
client.rc4 = RC4(INIT_KEY)
server.rc4 = RC4(INIT_KEY)
client: login(user_id, user_pwd, client_version, device_info, client_seed)
server: login_success(user_id, user_pwd, client_version, client_bind, server_seed)
server: set_key(new_key)
prng = Scramble7(server_seed)
reset_key = prng.get_key(new_key)
client.rc4 = RC4(reset_key)
server.rc4 = RC4(reset_key)

在经过这一系列解密之后,我们才能开始看到明文,知道客户端和服务器之间到底交流了什么。

接下来让我们仔细分析一下部落冲突目前的核心玩法:部落战的协议内容:
client: attackwar(user_id)
server: attackwar_fail(user_id, reason) # If fail
server: attackwar(map_info) # If success
client: action(tick, checksum, [action1, action2, action3, ...])
action_list:
action_army: (x, y, army_id, tick)
action_ally: (x, y, ally_id, tick)
action_end: (tick)
action_spell: (x, y, spell_id, tick)
action_hero: (x, y, hero_id, tick)
action_herospell: (hero_id, tick)
action_start: (tick)
action_data: (data_content, tick)

我们先来看一个设计的非常巧妙的action指令。这个指令的头是tick和checksum,tick是以1/60秒为单位的整数(60就是第一秒,120就是第二秒),而checksum是一个客户端信息的总和。

信息的总和是如何算出来的呢?这里非常巧妙的是,客户端会把目前绝大多数数据做一个求和,再算上当前tick数,得到一个总的checksum。这个checksum非常的关键,因为服务器会校验。服务器如果不了解客户端信息,是怎么校验的呢?很简单,服务器在连接建立之后,会跑着一套和客户端同样逻辑的代码,然后对客户端发来的每一条信息进行checksum校验。

比如说,客户端说我第一秒在某处放了一条龙。客户端经过模拟后,发现第二秒龙会摧毁一个对方的建筑,这时候checksum就会有显著变化,因为一个建筑没了。这时候给服务器的checksum必须有体现,服务器也会跑一个模拟程序,检验第二秒龙摧毁了一个建筑,如果客户端发来的checksum对不上,那么服务器就会断掉连接,认为客户端非法。

所以要做一个脱机离开客户端直接向服务器发送请求的程序很难,因为必须包含客户端完整的模拟战斗逻辑。而这套逻辑是部落冲突的代码核心,每次版本更新都会大改,非常难以完整进行模拟。

在此基础上的协议基本杜绝了第三方脱机机器人的存在。大部分机器人必须依靠客户端才能进行,比如BlueStacks上运行的虚机。

然而,这样的协议之上依然存在很多漏洞。还是拿部落战举例,如果有一个Men-In-The-Middle拦截了打的不好的协议包,只传送打的好的协议包,那么其实是可以保证每一次部落战都完成三星。

在最近的一次更新中,新增了action_start和action_data两条指令,这是做什么用的呢?Supercell为了阻止日益猖獗的叉叉助手和iMod所谓沙盒模拟(就是脱机练习进行演练),将对手的一部分信息(电塔援军陷阱)进行了隐藏。在付出一次攻击代价的情况下,服务器会给客户端返回这些信息,客户端才能进行完整的游戏。大概的逻辑如下:
client: attackwar(user_id)
server: attackwar(map_without_key_info)
client: action(60, checksum_60, [action_start(0)])
server: key_info(data)
client: action(120, checksum_120, [action_data(61, data)])
client: action(180, checksum_180, [action_army(125, x, y, army_id), ...])
......

简单说就是在action_start之后,服务器才会返回关键信息,让客户端能够完整进行模拟。那么action_data的作用是什么呢?由于checksum机制的存在,服务器需要和客户端同步加入这部分关键信息,所以客户端需要在收到key_info之后,告诉服务器,我在何时(tick)把这些key_info加入到地图形成完整地图的。然后服务器收到之后,可以和客户端一起进行模拟,并且校验checksum。

那么目前版本有一个致命的bug,就是服务器对action_data返回的data并没有进行检验。导致的后果就是客户端如果发回的key_info和服务器之前传回的不一样,也能正常模拟下去。如果客户端发一个空的key_info,服务器会认为陷阱电塔援军都神奇的消失了!

当然这种bug可能并不影响普通玩家,可能只有深入研究了协议的才会发现。尽管存在很多bug,但是笔者认为部落冲突依然是一款从技术上设计非常精良的游戏。不管何时,技术上的完善都是一款游戏坚实的基石。如果外挂横行漏洞百出,不管游戏表面有多美丽,都是一摊烂泥无法流行起来。

 

浅谈 Swift 语言

在刚过去不久swift_taylor的万众瞩目的 WWDC 2014 上,苹果发布了 Swift 语言。注意这个和已存在很久的 Swift Parallel Language (http://swift-lang.org/) 是两个东西。这是由苹果独立开发完成的,基于 LLVM 的全新语言,是一个从头到脚都打上苹果烙印的新东西。作者于是来赶趟儿简单写写对 Swift 语言的体会和感受。

Swift 做为一个崭新的2014年才发布的语言,全身上下都透着各种狂拽酷炫吊炸天的味道。从各家语言中博采众长,非常具备时代气息。关于 Swift 从哪些语言里继承了哪些特点,各家说法都有。个人第一印象觉得 Swift 更像 Ruby 一些。

然而做为一个新生语言,Swift 也有着一些小缺点:

  • 你依然需要学Objective C。Swift的大量底层库还是Objective C写的。如果真想写个游戏的话,难免还是会涉及调用大量的Cocoa风格的API。当然,有一部分Objective C的库已经专门为Swift进行了参数简化和改写,你有时候不需要再写Objective C里的反人类的长达几十个字母的常量名了。比如:let myTableView: UITableView = UITableView(frame: CGRectZero, style: .Grouped)
  • 缺少私有属性、异常处理等机制。私有属性很多语言都没有,个人觉得没有太大关系;异常处理的话,做为新时代语言来说,缺少了还是比较不应该,虽说Objective C里也没有。
  • 类型非常诡异的复制特性。比如下面代码
    var ages = ["Peter": 23, "Wei": 35, "Anish": 65, "Katya": 19]
    var copiedAges = ages
    copiedAges["Peter"] = 24
    println(ages["Peter"])
    // 23
    var a = [1, 2, 3]
    var b = a
    a[0] = 42
    println(a[0])
    // 42
    println(b[0])
    // 42
    a.append(4)
    a[0] = 777
    println(a[0])
    // 777
    println(b[0])
    // 42

    大家可以体会一下这让人毛骨悚然的设计。简单说就是字典赋值都会复制一份出来,而数组不会。但是数组一旦长度做了更改也会立刻原地复制一份出来。这种设计模式很让人摸不到头脑,比较反常识。
  • 文档依然不是很齐全。需要较长时间来补充。
  • 无法跨平台。说到这一点确实有人要说这是勉为其难了。Apple凭啥做个能跨Android的东西来呢。然而,大概询问了几家游戏开发公司,都表示最大得导致他们不会用Swift开发游戏的原因就是没法跨平台。而现有的很多游戏引擎都做到了跨平台开发。

由于 Swift 的优点太多,网上也有很多人做了分析,这里就不一一详述了。这里只想总结说,Swift 确实是门开发效率非常高的语言。如果你只做 iOS/Mac 开发,Swift 现在是你的第一选择。

有人问 Swift 会不会是 iOS 开发的未来。我可以毋庸置疑的回答,是的。Apple的策略倾向导致,将来会有大量的资源像 Swift 倾斜。对于一个公司策略级的开发语言来说,Swift 的前途已经注定灿烂了。就像 Apple 描述 Swift 的那样:A complete replacement for both the C and Objective-C languages。

最后祝大家在 Swift 学习中能找到乐趣。

 

云服务为什么会是未来?

今天在交流时候有记者问过我,使用云服务主要还是成本的考虑吗?是的。和传统服务相比,云服务实际上没有哪一点是完全不可替代的。而成本恰恰是小团队最关心的一个问题,时间成本、人力成本、以及最直接的机时售价价格,这些问题累积在一起,才是做为初创公司选择云服务的所有理由。

 

英国经济学家杰文斯曾经在《煤矿问题》中指出一个看似互相矛盾的问题:对蒸汽机性能的改进提高了煤炭的能源转化率,用更少的煤可以产生更多的能源了,而能源的价格降低往往又导致了煤矿的消费量增加。这种现象被称为杰文斯悖论,既:对资源的利用率降低了资源的价格,最终会增加资源的使用量。在云计算领域,该悖论也非常的适用,云服务大大改进了计算资源的利用率,改进的方式包括:更简单的获取计算资源的方式,以及将闲置计算资源更好的释放出来。当开关服务器就和开关水龙头一样便捷之后,公司以及个人对服务器资源的需求会大大的增加。

举个切身体会到的例子。曾几何时,公司弄一台线上服务器是如此的困难。早先我们需要首先买一台服务器,然后找个机房托管,签完各种合同,交完押金和钱,将庞大的机器搬到机房里的某个机柜,插好各种线,终于可以接入互联网开始服务了。再然后有了服务器租赁业务,依然会比较麻烦,填完合同之后,大概需要2-3天不等,机器才能准备好。在如今云服务提供的便利之下,5分钟可以开一台服务器,用完即关。

对于传统互联网公司来说,一方面,在计算资源获取困难的时候,一个项目或者一个新计划只能压缩到有服务器的时候才能开展,而根据流量动态调节服务器响应能力变得几乎不可能。另一方面,在计算资源过剩的时候,闲置在那里的服务器资源对于能源的浪费,简直是一件令人发指的事情。有一个听来的真实的笑话是这么说的,老板发现了公司服务器CPU闲置的非常厉害,让手下想办法。某公司手下用脚本检查CPU占用率,如果没满就写一个死循环占满。另一个公司觉得这样太直白了不太好,就暗示开发把代码写的烂一点,以占用更多的CPU让数字看上去好看些。对于大型互联网公司来说,目前每年都有无数的钱财和资源浪费在了闲置服务器上。

如果将传统服务器比作每天早上下山挑水喝,那么云服务就像是自来水入户,打开水龙头,水就流了出来,不用的时候,可以随时关上水龙头。既充分利用了资源,也没有造成资源浪费,把成本降到了最低。将计算能力分割成块然后当成自来水一样出售给大众,这无疑是大势所趋。在未来,任何一个普通学生想起一个复杂的算法,都可以经过简单的操作,然后开启100台服务器进行计算,最后在验证完算法之后关闭。云服务会真正像自来水一样走进千家万户。

有感而发写一点不那么务实的东东。

 

 

用 AWS 构建高性能 Appflood 广告服务

众所周知,广告业务是对服务器的性能考验最为严峻。首先广告业务的访问量十分巨大,动辄每秒成千上万的请求,其次广告业务对于实时性的要求非常之高,在 RTB 环境下要求请求延迟不超过100毫秒,而我们对自己的要求往往是请求延迟不超过20毫秒。

重新从底层搭建所有框架对于创业型公司来说是很不现实的。Key-Value DB、Cache、LoadBalancer、TaskQueue,这一切如果都用开源框架来搭建,无异于一场灾难。从易用性到健壮性,从 Availability 到 Scalability,开源框架往往都不能完整的满足所有。幸好亚马逊提供的 AWS 服务提供了完整的全套的解决方案。我们从中也学到了很多东西。

1. Colocation -> IaaS

早先公司自购的服务器并且用的美国公司的托管服务。后来发现对于创业公司来说,繁复的服务器维护工作简直是一场灾难。在09年左右卖掉了服务器,投靠了 AWS 的怀抱,开始全部用 IaaS 做为服务器平台。

说实话初期 AWS 的虚拟 Instance 很不好用。做为第一批吃螃蟹的用户来说,体验过各种奇葩的问题,比如 Instance 失去响应,Reboot失效等等。经过询问 AWS 工程师,给出的结论一般是:Linux内核问题、底层硬件坏了,或者就是他们也不知道原因。

不过虚拟 Instance 的好处也非常明显,就是开关很便捷。如果真的坏了而且也找不到原因就再开一台吧。AWS可以靠低价的Instance数量取胜。

2. Key-Value -> DynamoDB

公司早期我们就是Key-Value的狂热热爱者。在试用过Tokyo Tyrant,MongoDB,Riak等等服务之后,最后我们还是采用了 AWS 的 DynamoDB。Key-Value看似美好,但是其背后的维护人力成本也非常之高。在数据快速增长的时候,在节点出现意外的时候,在磁盘满了需要更换节点的时候,往往都是灾难发生的时候。虽然标榜具有很高的 Availability,但是往往需要开大量的冗余节点支撑,平时在不用的时候浪费很多的钱。在个别节点崩溃之后,剩余节点的负载又往往高居不下,很难调节。

最后我们试用了 DynamoDB,到目前为止感觉良好。无需自己考虑节点问题,无需考虑存储空间不够。唯一的问题可能就是无法做 Replica。当然这一问题也有其他办法可以解决。

3. TaskQueue -> SQS

对于读写分离的线上业务来说,TaskQueue 服务一般是必不可少的。早期我们自己搭建的TaskQueue Service,后台采用 Redis 做存储,也尝试过较为成熟的 RabbitMQ 等开源方案。一个经常遇到的比较严重的问题就是,存储满了怎么办。

相信所有 TaskQueue 系统最怕的就是存储满了怎么办,无论你的存储是在很大的内存里,还是在磁盘上,如果 Worker 不工作总会有满了的时候。突发流量增加导致后端 Worker 处理不过来,或者因为 Worker 的代码异常导致处理速度过慢。一般的 TaskQueue 系统遇到这种情况往往就是崩溃掉,丢失 Queue 里的所有任务。

对于 Queue 系统还有一样需要考虑的就是并发性。如果流量增长过快,需要考虑的是要增加更多 Queue Master节点,以及更多的 Worker 来处理。这些问题都需要大量人力来维护。

随后我们还是投靠了 SQS 服务。Master 的所有问题都交给了 AWS 来解决。偶尔遇上线上故障也会有积累几千万个任务的时候,但是不需要考虑存储和Master节点的可用性,一切都很平稳,数据也没有丢失过。使用 Autoscaling 也可以很好的实时增加 Worker 数量,保证任务处理可以跟得上。

唯一的缺点就是 SQS 的时序性稍差。当然这一点也可以在应用层加以处理,避免时序错乱问题。

4. OnDemand -> Spot

AWS 的 Instance 有 OnDemand 和 Spot 两种类别。区别在于 OnDemand 比较贵,Spot很便宜但是可能随时被关掉。然而实际上给一个很好的bid price,Spot是可以开很久很久的。通过做好现成的 AMI,然后用 Spot 方式动态启动服务器,可以将各个时段不均匀的访问导致的开销降到最低。比如定时在访问量最大的时候多开几台,然后在大家睡觉的时候再关掉。不管是什么服务器能提供多好的 Availability 和 Scalability,它的最关键的分母还是 Cost。使劲花钱用最豪华的配置搭一个稳定服务,只是看上去很美,所有人都会。而 Spot 可以让我们用最好的性价比,搭出优良的在线服务来。

最后

总之,AWS 使我们从后端的海量运维工作和底层框架搭建工作中解脱了出来,让我们有更多的精力处理上层业务逻辑和算法。另外,充分利用 Spot Instance 也使得我们的服务器成本非常的低廉。目前我们有 5台c1.xlarge做为广告服务的前端处理Web请求,5台m1.xlarge做为广告服务的Worker。除掉静态请求统统走 CDN CloudFront 之外,动态请求的平均响应延迟是 13毫秒,日均访问量是亿量级。服务器负载都在 <1 以内。

 

炉石传说如何偷看对面的手牌

炉石传说是一款暴雪最新出的卡牌游戏。这里我们简单对它的协议和客户端机制做一下分析。

炉石传说的客户端是采用的Unity3D+C#制作的。画面精良,美术细腻,可以说达到了 Unity3D 引擎作品中相当高的水准。3D的卡牌效果让人惊叹,暴雪出品确实必属精品啊。(Diablo III 除外)

EX1_062_premium由于采用的是Unity3D,可以预见移植到手机和Pad上毫不费力。因为采用的是C#,可以说缺点也是很显然的。C#的反编译非常的简单(虽然C/C++的反编译也难不到哪里去),大大降低了逆向工程(Reverse Engineering)的成本。这里不得不吐槽一下暴雪对微软系列的热爱,Web Server也统统用的IIS+ASP.NET,不出意外Game Server后端也用的是Windows Server以及SQL Server。可能也与暴雪一直专心于制作Windows Game有关。

下面我们不对客户端内容做任何反编译和分析,仅仅从通讯协议层来简单看看炉石传说的客户端在游戏时都做了什么。

我们先在本地用 tcpdump 监听一下 3724和1119端口,通过看包得内容,可以判断炉石传说的游戏 TCP 链接用的是 Protobuf 协议。Protobuf 协议的标志就是开头以 08 或者 0A 开始。

16:03:32.228771 IP 192.168.1.XX.53668 > XXX.XXX.XXX.XX.battlenet: Flags [P.], seq 229:256, ack 11411, win 8192, options [nop,nop,TS val 1131484283 ecr 57022610], length 27
0x0000: 5866 baf3 8757 040c cede b078 0800 4500 Xf...W.....x..E.
0x0010: 004f 6ddf 4000 4006 be15 c0a8 0158 7271 .Om.@.@......Xrq
0x0020: da42 d1a4 0e8c 4ab6 e5de 32f4 32b5 8018 .B....J...2.2...
0x0030: 2000 f655 0000 0101 080a 4371 147b 0366 ...U......Cq.{.f
0x0040: 1892 0200 0000 1300 0000 0811 1004 1800 ................
0x0050: 20ff ffff ffff ffff ffff 0128 00 ...........(.

Protobuf 是 Google 开源的一个公开协议。然而并不是说知道用 Protobuf 就能理解传得是什么内容。Protobuf 需要有详细的 .proto 参数配置文件定义传输的细节,否则对于其它第三方来说就是一团乱码。

通过一些逆向工程,我们大概知道了这个 .proto 参数配置是怎样的。炉石传说可以说是一个瘦客户端。客户端做的计算分析工作很少。这一点很符合暴雪的特点,比如魔兽世界也是这样的一个瘦客户端,大量的3D碰撞检测计算都放在了服务器端。

炉石传说把所有的客户端需要显示的细节,都通过服务器传来数据,其中甚至包含了客户端动画展示时需要的停顿。炉石传说的服务器端维护了一个 id=1~67,并且可以动态增加的字典,其中 1 代表系统,2 和 3 代表两边的玩家,4~35 是 id=2 玩家的所有牌的编号,而 36~67 是 id=3 玩家的所有牌的编号。系统、玩家、牌,这些共用一个属性表,这大大降低了定义的复杂度。

下面是一些通讯的简单例子:

初始化:
player{ ... 玩家属性初始化 ... }
init{ id:4 name:"HERO_03" attr{HEALTH=30} attr{PUT=1} attr{OWNER=1}
init{ id:5 name:"CS2_083b" attr{COST=2} attr{PUT=1} attr{OWNER=1} attr{CASTBY=4}}
init{ id:6 name:"" attr{PUT=2} attr{OWNER=1}}
........
init{ id:35 name:"" attr{PUT=2} attr{OWNER=1}}
init{ id:36 name:"HERO_08" attr{HEALTH=30} attr{PUT=1} attr{OWNER=2}
init{ id:37 name:"CS2_034" attr{COST=2} attr{PUT=1} attr{OWNER=2} attr{CASTBY=36}}
init{ id:38 name:"" attr{PUT=2} attr{OWNER=2}}
........
init{ id:67 name:"" attr{PUT=2} attr{OWNER=2}}

从这个初始化例子我们可以很清晰的看到,服务器给每个客户端初始化了 67 张“牌”,其中 1,2,3 是系统和两边玩家,4,5是玩家A的英雄卡 HERO_03 和英雄技能 CS2_083b,被放到了战场(PUT=1),6-35是玩家A的牌库,被放到了待抽牌堆(PUT=2),相应的,对面36,37是玩家B的英雄卡 HERO_08 和英雄技能 CS2_034,38-67则是玩家B的牌。

接下来的通讯协议分析就不一一说了,总之就是服务器向客户端通过设置这些牌的属性, 让客户端达到显示牌以及动画效果的目的。

那么有人要说笔者标题党了。技术细节看了一大堆,但是如何能看到对面的牌呢?难道服务器会直接在通讯协议里告诉玩家A,玩家B手里的所有牌么?

其实不然。暴雪在技术细节上做的还是很好的。只有在玩家把牌放入战场,对方才能通过通讯协议知道牌的内容。但是其中有一个小问题,就是:

每一次比赛牌的 id 并不会随机化洗牌!

就是说,玩家A和玩家B如果两次用同一副自己组的牌对打,玩家B如果给玩家A出示过某个 id 对应什么牌的话,那么下一次比赛玩家A就会知道玩家B还在手里的牌是什么!

说通俗一点的话,就是对圣斗士来说,每一招只能用一次,第二次用同样的招数就变得很不安全!

下面是一个和同一个好友同一副牌玩第 2 把的例子:

EX1_561_premium敌方 操作 开始
第 1 回合
玩家 铁喙猫头鹰 牌库 -> 手牌
玩家 刺骨 牌库 -> 手牌
玩家 任务达人 牌库 -> 手牌
玩家 刀扇 牌库 -> 手牌
玩家 幸运币 未知 -> 手牌 施法:
敌方 寒冰护体 牌库 -> 手牌
敌方 变形术 牌库 -> 手牌
敌方 魔爆术 牌库 -> 手牌

在第一回合,我们就清楚的知道了对方先手拿得三张牌是什么!

当然,在平时天梯和竞技场里,这个问题可能不会存在,因为每次遇到的选手都是系统随机分配的,都是第一次遇到。如果是打职业线上比赛的话,就难保不会有人通过这个办法作弊咯。

当然,目前游戏还在内测阶段,相信暴雪技术团队应该会在公测前修复这个问题吧。

除此之外,目前的通讯协议上还有下面几个 BUG:

  1. 对面手牌中的”奥秘牌“会在奥秘出示之前就通过通讯协议让另一方知晓。
    就是说虽然客户端没有提示,但是实际上对面一拿到奥秘牌,你的客户端就可以知道对面的哪一张是奥秘牌,虽然不知道具体是什么奥秘。
  2. 服务器错误的把每一方思考时候的选择数目发给了另一方客户端。
    选择数是你每一步有多少种可能。这是服务器端提前算好告诉客户端,然后让客户端提示用户做选择的。比如在1费回合你没有2费牌,只能点”结束回合“,这时候的选择数就是1个。通过判断对方每回合结束的选择数,你可以大致估计对方手牌里的费的多少,以及是不是法术指向牌。
  3. 虽然是第一次遇到某玩家,但是还是可能通过牌的 id 猜到对方某些手牌的内容。
    注意,因为没有通过随机化洗牌(shuffle),所以牌的 id 实际上是玩家从牌库中选择的顺序。有些玩家喜欢从1费开始选牌,有些喜欢从高费开始,但是一般两张同样的牌都会一起选进去,所以他们拥有相邻的id。比如你看见对方出了一张id=16的炎爆术,手里还有一张id=15的未知牌,那么你就知道下回合多半又是一张炎爆打脸了。

好了,简单写了这些,其实并没有太严重到逆天的 BUG,炉石传说还是一款好游戏。希望暴雪团队继续努力,早点出移动客户端,让笔者可以早点躺着玩。

 

浅谈如何修改游戏 (1)

很多很多年前,那时 DOS 游戏界有着两大逆天神器 GameBuster 和 FPE。不管是仙剑奇侠传还是红警神马的,一旦祭出神器,那是神挡杀神佛挡杀佛,弹指间敌人灰飞烟灭。

到如今几十年的发展,游戏变得越来越网游化和移动化。大游戏动辄十几G的容量,数据都存在服务器,外挂检查严而又严。小游戏在iPhone和Android上,麻雀虽小五脏俱全,对作弊的检查也是非常严格,数据加密和校验方法层出不穷。

然而道高一尺魔高一丈,本文就尝试粗浅的介绍下现如今修改游戏可以做的一些手段。

对于 Windows 游戏修改手段来说,大概可以分为下面一些层次,按照安全性排序:

  • 对数据段的内存读
  • 通过 PostMessage 对游戏模拟键盘和鼠标操作
  • 对 D3D9 的 EndScene 或者 D3D11 的 Present 函数挂钩子,进行远程调用
  • 创建远程线程 (RemoteThread) 去调用执行函数
  • 模拟游戏发送网络底层的命令包
  • 对数据段的内存写
  • 对代码段的直接修改

对游戏的数据段的读取,是最安全最可靠的。游戏本身无法判断其它应用是否对它进行内存读的操作。然而,只靠内存读可以做的事情非常少,不过依然有可能读取到游戏里隐藏给玩家的数据。比如人物的三维坐标、朝向、行进速度、或者隐藏Buff啦,比如法术的实际释放坐标和半径,以及前进路线啦。

想要更进一步的对游戏本身进行操作,那么可以用按键精灵,或者类似的工具,模拟鼠标和键盘事件发送给游戏。但是这依然无法产生逆天的效果,实际上可以做一些机械性重复性特别高的事情。这类工具本身的可侦测性也是非常低的,比较的安全可靠。

EndScene 和 Present 实际上是游戏UI线程一般在绘制完一帧图像之后必须调用的。很多录像软件也是 Hook 的这两个函数。所以实际上这是很安全而且很合法的钩子。在 EndScene 里做操作的好处在于,很多游戏里的操作函数需要运行在游戏UI线程。如果用 RemoteThread 的方式去调用函数往往会导致线程问题然后游戏崩溃。

RemoteThread 调用实际上用于一些简单的判断函数,比如得到某个游戏对象的名称,判断某个 NPC 的敌对状态。这些执行函数不需要在主线程执行,可以用 RemoteThread 飞快的调用完成。RemoteThread 的执行速度和 EndScene Hook 相比往往要快上百倍。

而发送游戏的网络底层命令包,则需要对游戏的网络通讯协议有一定的了解。它可以跳过游戏上层逻辑对命令合法性的判断,直接用底层协议对服务器通讯。通过这个办法可能可以做一些客户端里无法完成,但是服务器却允许的操作。它的安全性也不够高,如果命令非法,也可能造成服务器拒绝继续服务,导致掉线或者客户端崩溃的结果。

对数据段的内存写,实际上是早期游戏修改的大招了。然而,现今绝大多数网络游戏都有防护措施,他们不依赖客户端数据,服务器发现客户端数据不一致,就会拒绝继续服务,导致掉线甚至封号,得不偿失。所以这种手段用到的越来越少了。

对代码段的直接修改,是跳过一些客户端条件检查判断的手段。比如跳过客户端关于法术的 Cooldown 检查,直接向服务器发送法术发送命令。这个办法比直接发送网络底层命令包简单很多,只要对上层游戏逻辑进行修改就可以了,但是它却非常不安全。现今的网络游戏往往具有自我修改的检测能力,比如暴雪的 Warden 会定期的扫描自己可执行文件的代码段,看看有没有被注入钩子或者一些跳过检查的代码。如果被发现了你的客户端在内存中被做了修改,那么就等着过几天静悄悄的被无法登录游戏吧!

想要精确的定位到函数以及变量在内存中的地址,以及数据结构,就需要一些额外的辅助工具了。这里向大家介绍两个工具:Ollydbg 和 IDA Pro。可以说,有这两个工具在手,没有不能修改的游戏。IDA Pro 是非常强大的静态反编译工具,它的插件工具也相当多。读入静态 exe,它可以比较完美的分析出函数地址、函数调用关系、数据结构等。Ollydbg 是动态的运行中反编译工具,通过它,可以对在执行过程中的游戏增加断点,单步调试,等等。这两者可以结合在一起使用。

想要熟练掌握这两个工具,你必须会一些 X86 的汇编指令,可以熟练的编写汇编代码,对 C/C++ 编译有一些了解。有了这些基础之后,就可以随心所欲的对游戏下刀了。当然,有些游戏会有反跟踪和反“反编译”手段,想要修改成功,往往还需要一些耐心和毅力,以及一些直觉和洞察力。

最后,让我们来看看破解过得游戏能做到什么地步。其实很简单,就是能做到游戏的服务器端所容忍的上限。比如游戏客户端允许你的走路速度是 7 码/秒,施法距离是 40 码,而服务器考虑到网络延迟以及客户端的计算误差,往往上限会高一些,比如是 10 码/秒和 43 码。在绕过客户端限制之下,往往可以达到服务器允许的上限。再比如客户端在短期内连续发送很多移动命令,外加计算恰当的时间戳,可以让服务器觉得客户端是出现了卡顿,因此服务器会允许一大串移动命令和一大串偏移时间戳,在服务器看来,客户端卡顿了 10 秒并且移动了 70 码,但是客户端实际只经过了很短时间,做到了瞬间移动。这样的例子需要探索性实验。

如果服务器做的足够精美足够巧妙,其实是可以杜绝任何客户端的修改。然而这需要大量的服务器运算和负载。对于海量游戏数据处理来说,这无疑是会继续增加服务器运营费用和成本。因此很多国产网游的服务器检查非常粗糙和简陋,酝酿出大量的客户端修改和外挂。而好游戏在服务器端的强制检查判断则非常的严格和精妙,从而减少了客户端修改带来的收益。

最后告诫大家,游戏修改破坏平衡性,同时损害了游戏乐趣。网络游戏修改更加破坏了运营商的利益,破坏了游戏的生态环境,要小心被跨省追捕哦。修改有风险,入行需谨慎啊!

下次我们来谈谈 iPhone/Android 修改的一般性方法。

 

谈谈Zopfli

image01

最近 Google 出了一个新的开源项目 Zopfli。Zopfli是什么呢?简单说是一个 Deflate 压缩算法的另一种实现。推出之后国内国外媒体纷纷报道转载。昨天看到国内媒体的报道 (搜狐IT)中说道:“据悉,Zopfli的压缩率比现有的Zlib高3-8倍。”当时看到了就吓了一大跳,3-8倍这是要逆天啊!赶紧去Zopfli主页看一眼,原来只是3%-8%的提升。国内IT编辑真是吓死人不偿命。

Zopfli到底表现怎么样呢?先看看 Zopfli 自己提供的数据:

测试集 样本大小 gzip -9 7-zip kzip Zopfli
Alexa-top-10k 693,108,837 128,498,665 125,599,259 125,163,521 123,755,118
Calgary 3,141,622 1,017,624 980,674 978,993 974,579
Canterbury 2,818,976 730,732 675,163 674,321 669,933
enwik8 100,000,000 36,445,248 35,102,976 35,025,767 34,955,756

大概是比标准的gzip -9要小 3.7%-8.3% 的样子。但是压缩所需要的时间非常的惊人:

压缩算法 压缩时间
gzip -9 5.60 s
7-zip -mm=Defalte -mx=9 128 s
kzip 336 s
Zopfli 454 s

可以说如果用 gzip 压缩要喝口水的时间的话,用 Zopfli 就可以出去吃个便饭了。

我们再看看这些算法的出生年份:Deflate最早诞生于1994年。7-zip最早诞生于1999年,也是一个开源项目,虽然7-zip自己默认用的格式是LZMA和LZMA2算法,但是也支持对Deflate算法的更好的压缩。KZip 是 Pngout 作者写的一个小工具,诞生于2006年,是一个把现有Zip再压缩的工具。

这里不得不提几个Zopfli文档里没有提到的其它 Deflate 兼容的压缩工具:DeflOpt,是2007年诞生的一个Zip再压缩工具。AdvZip,是一个利用7-zip Deflate的一个Zip再压缩工具。

可以从表中看出,Zopfli比1994年原版Deflate确实有3%-8%的提升,但是对比比较新的Deflate实现,提升实在是很有限,比如比KZip只提升了大概1%不到。压缩时间对比KZip也增加了相当多。

发布没多久,就有人发现,利用 KZip+DeflOpt,压缩的结果可以比Zopfli压缩的更小,甚至Zopfli的几个样本的压缩结果,依然可以用 DeflOpt 再压缩一点(1%左右)。所以说Zopfli其实并不是他在文档里所说的,“所有已知Deflate算法实现里压缩比最高的”。

当然,Zopfli的意义在于它是开源算法,而KZip+DeflOpt这俩都不开源。关于KZip,DeflOpt是如何实现的,之前还有很多人在猜测。Zopfli的出现给大家提供了很好的解答。

另一点值得探讨的是,在今天研究Deflate算法更好实现是否还有价值。Zlib的作者本人Mark Adler在听说Zopfli之后说:“这很酷,不过看上去是一个付出了很多努力,但只取得了很小提升的一个糟糕结果。也许到了给HTTP的accept-encoding加上更好算法的时候了”。是的,诞生于1994年的Deflate确实太老了。现有的解压更快、压缩比更高的开源算法有很多很多,比如 bzip2, LZMA/XZ等等。LZMA/XZ在解压速度上,以及压缩比上,都完胜Deflate。Deflate对于很多 UTF-8 3 bytes的网页压缩效果也很不理想。直到今天,支持bzip2, LZMA的浏览器还寥寥无几。也许更有前途值得关注的是HTTP/2.0协议(一部分基于Google的SPDY协议)。

重新回到Deflate算法。为何Deflate有如此多的压缩实现呢?我们得详细的看看Deflate算法的具体内容。Deflate算法其实就是LZ77算法加Huffman算法。先经过LZ77的字典找重,然后用Huffman树进行降比特。不同的Deflate压缩的实现其关键在于LZ77的搜索重复单词,以及选择分块来进行Huffman。早期算法例如7-zip对分块都不是很重视,更多的考虑的是LZ77算法的优化。而KZip另辟蹊径对分块也进行了优化,使得最终比特流长度变得更短。

LZ77算法优化是一个有向图上的最短路径的搜索问题。对于字节流每个字节建立单边节点,重复单词序列建立更短的边,形成一个有向图。LZ77算法的目的就是如何找到有向图从起点到终点的最短路径。对于边的长度确定的情况下,用动态规划找最优解是很简单的。然而LZ77在搜索时,如果要考虑下一步Huffman过滤之后的长度,则边长度就是不固定的。Zopfli采用迭代的办法,先用一次贪心法拿到第一个次好的结果,然后通过使用结果字节的熵值(就是出现频率的N-log2n)来给出下一次迭代的每条边的边长,也就是每个字母的比特长度。通过反复迭代,来逐步逼近最好结果。当然,理论上也可能跌入一个次好结果的低谷。

Huffman_tree_2.svg然后是最关键的分块问题。分块为何会影响Huffman的压缩结果?其主要问题还是因为动态Huffman算法的随机性。如果都采用对字节使用频率统计完毕之后的静态Huffman,那么不管如何分块都不会对结果有影响,反而因为分块产生额外的比特,使得结果变大。动态Huffman的树是在字节流的处理过程中动态创建的,因此其字节流的开始片段不规律性往往使得结果不优。如何分块才能更优?因为随机性太大,也很难进行判断。所以KZip和Zopfli采用的都是尽可能的穷举。KZip就号称用了“重复单词的穷举(LZ77)”和“更高效率的分块(Huffman)”来实现,可以增加分块的个数进行进一步优化。而Zopfli,是不停的在一个最大块内找9个点,穷举判断哪一个最优,然后进行反复切割的办法。

Deflate压缩算法有没有最优解?这其实是个NP问题。对于短短32字节大小的数据,都有2**31 = 2147483648 种不同的分块方案。当然绝大多数分块都没有意义而产生更差结果。分块之后依然还有需要进行迭代的边长会变化的最短路径问题需要解决。

最后,尽管 Zopfli 的结果不是很令人满意,不过确实给众多不开源的 Deflate 压缩工具树立了标杆。那些想靠着 Deflate 算法做收费 PNG 压缩的软件可以洗洗睡了。