hwang’s rift strategy

Rift contest is over. It was a great experience with plenty of emotions : excitement, frustration, satisfaction, deception and thankfulness . I hesitated to share my strategy because I was not ranked high enough to give the most convincing words. Nevertheless, I still made up my mind to write something down, on one hand to capitalize this rich experience and on the other hand to hear and learn from you.

In this article, I’ll explain the important decisions made in my solution without diving too deeply into implementation details. I started with the 1v1 matches and then based on it, I developed the 1v2 and 1v3 strategy.

Initial purchase

Intuitively, pods should be purchased on the richest zone because that will make money more efficiently. However, a rich zone very far far away from all others is not necessarily the best choice because it would take too much time for pods spawned there to come back to the remaining game.

Therefore, a neutral zone should not be rated solely on its own richness. Other reachable zones should also be taken into account. This idea led me naturally to build a score system where the zone having the highest score should be purchased in priority.

Then it came the most essential question :

For a given zone, how much should other reachable zones be weighted in its score ?

It’s like how our nose works. The closer a great wine is to us, the stronger we’ll smell it. Therefore, the contribution of other zones should be in function of distance. For a given zone x, its score is calculated as follows :

score(x) = sourceOf(x) + constant * sumOfSmeltSourcesBy(x)

where the source of a reachable zone y smelt by x runs as :

smeltSource(x, y) = Math.pow(0.5, distance(x, y)) * sourceOf(y)

As shown, source of a reachable zone is reduced by half every time it’s one step farther.

To build this system, I need a matrix to memorize the distance between all pairs of zones in a connected graph. This matrix is obtained thanks to Floyd–Warshall algorithm. This score system allows me to make purchases with high profitability.

Move

Given that a player can only purchase pods on a neutral or his already-owned zone, the very first idea I got is to separate my pods into two groups :

  • Pods at the frontier which are exposed to enemies or neutral zones
  • Pods in safe zones. A zone turns safe when both itself and all its neighbors are captured by the same player.

Pods at the frontier are involved in conquering new zones or in defending owned ones whereas safe pods should move to the frontier to engage again in fights. Pods stop moving when the entire continent is captured.

Safe Pods

Pods become safe after closing a frontier. Once mission accomplished, they should move toward other exposed zones. Two problems should be resolved in order to make a perfect move :

  • Identify a destination
  • Find a path toward the destination

Pods at the frontier

In absence of enemies, a pod at the frontier should make moves allowing to gain as many sources as possible. Since it’s only allowed to make one step move. A pod at the frontier should only focus on its neighbors. However, given it can have multiple neighbors it must choose the right direction. It should head for zones following the guide of the smell system. In the same way, this avoids moving to an isolated rich zone.

Given that zones already captured should not be targeted again, my score system is re-evaluated on each round by excluding my already owned zones.  In other words, zones belonging to me are no longer smell-able.

Resources are limited. Confronting with enemies is inevitable. When enemy pods are detected, I keep my pods moving as if no enemy were detected. I prefer to be agile rather than motionless because staying still is more likely to miss opportunities to take control of extra zones. For example, I captured the green zone and one enemy pod is detected at the red zone. If I stayed still, the red one would probably take the neutral zone and I would remain immobile.
However, being agile is not always the best choice neither. In the above scenario, when I leave my zone, enemy pod could make an invasion and then occupy my zone. It would be stupid If I trade a rich zone with a poor one.

Defense Purchase

Before conquering the whole continent, frontier always exists. In other words, the exposed zones can be in danger. Therefore I always have an eye on the frontier. When enemy pods are spawned beside my exposed zones, I try to put the same number of pods there to prepare the possible invasion. On the contrary, if no enemy is detected, I do nothing.

Since the number of pods that I can purchase is limited each round, I always defend the richest zone in priority.

Most of time, a pod spawned at the frontier vanished together with the enemy. In case enemy doesn’t attack, my spawned pods turns into pods at the frontier and thus they’ll follow the strategy explained above.

to be continued…

Codingame Rift 归来

Rift,这是我既Pokerchips之后,参加的第二个codingame组织的比赛,淋漓尽致的释放了我对编程的热爱的同时,收获颇丰。

除了获得了,在1028名来自世界各地的参赛者中,名列前2%的成绩之外,这次参赛经历,首先使我对Scala有了更加实际的应用,加深了对这个语言的了解,也体会到了面相函数式编程在人工智能方面的优势。

其次,更加意识到,单元测试,特别是行为驱动开发(BDD),在软件开发中所发挥的巨大作用。再然后,就是大大培养了对人工智能游戏开发的兴趣,也慢慢开始开窍了。

最后,从学习方发方式来讲,更加深信不疑,一个好的学习习惯可以帮助一个人以最快的速度获取事物的本质和他们的内在联系,进而抓住解决问题的突破口。


Scala

从上一年接触了Scala之后,就一直想练练手。只是苦于一直没有找到能吸引我的项目。这次经历,通过实战运用,使我对这个语言有了更加深入的认识。

相对于Java来说,Scala有几个让我爱不释手的特点。

宣告式编程(Declarative programming)

宣告式编程,是一种编程方式。它给解释计算机想解决什么问题,而不是简单的给计算发送一条又一条的控制指令,告诉它如何解决问题。宣告式编程的最大好处,就是它帮助写一些没有副作用的优美函数,这对程序的确定性及可预见性有特别大的帮助。这个我可以另开一帖专门讨论。

不可变性 (Immutability)

不可变性,说的是一旦一个物体被创建了,他就不会再变了。这样做的好处是你把一个创建的对象,放在哪里,不管你把它给了谁,也不管你多长时间之后再来看它,它都会像你创建时的那样,纹丝不动。

简洁

Scala去除了一切不必要的冗繁的代码。我们可以把更多的精力放在问题本身,而不是语言本身。就像case class, type infer 等种种功能。


单元测试

有人说Codingame应该开发一个调试的功能,我觉得是完全没有必要的。反而是不应该受到鼓励的。正确的方法是写测试,写测试有很多好处,特别是在Codingame比赛的这个环境下,更应该写单元测试。

高效的反馈

为了验证程序设计的正确与否,很多人都是把它跑起来,然后看看结果对不对。这样以来,就大大延长了反馈的时间,比赛的长短先不说,从把代码粘贴过去,到跑起来,再到最后得到结果,也得花近一分钟的时间。而单元测试,则是实时的。特别是Scala的SBT工具,测试是持续在跑的,只要发现代码变化,测试就会重新跑一遍。

回归测试

单元测试的另外一个好处,就是有了它,你可以毫无后顾之忧的搞重构。重构是为了,优化代码的结构,使得它更灵活的朝更有利的方向发展,既不加新功能,也不能破坏已有的行为。不破坏已有的行为,是单元测试来保证的。

除了重构之外,无法避免的就要加新的行为,一个新的行为加入,是要保证回归测试的,不能拾个芝麻,留个西瓜。

不论是重构,还是要加新功能,我们关注的都是对已有行为的保护,所以这就要求测试要以测试行为为主。测试行为,不仅可以从行为的层面清晰的阐明问题的需求,又可以避免受到细节的变化对测试的影响。

具体结合Rift本身来讲,比赛进展到中程的时候,地图变了,游戏的策略也必须与时俱进。之前只关注1v1的竞赛着,之后就必须考虑1v2和1v3了。如此一来,就会有重构,有新行为的添加,但又得保证之前的1v1策略不受影响。测试就发挥的巨大的作用。


人工智能

两个比赛比完之后,我对人工智能产生了浓厚的兴趣。之前我之所以很痴迷于电脑游戏,是因为在游戏里我可以发挥我的创造性,自由的尝试我的各种想法。人工智能,有同样的魅力,并且有更大的空间去发挥想象力,去尝试和探索不同的策略,就像玩游戏一样。不同的是,人工智能的策略,不是玩出来的,是自己用手和大脑,一行一行,编出来的,就像你在开发一个机器人,机器人会完全服从你,执行你的想法。

同样,我想在写一篇文章来谈我对制定人工智能游戏策略的体会。


学习方式方法

这是我体会最为深刻的一点。又让我想起了之前的一些困惑,上大学的时候,我总是在问学那么多课,做那么多将来都用不上的光学试验,究竟是为了什么。现在我开始慢慢明白了,那是为了锻炼我们学习的方式方法,锻炼我门的观察能力,锻炼我门发现问题的能力,提高我门推断事物内部联系的能力,进而找到问题的关键点。

编好Rift这种多人人工智能对战游戏,就必须有这些能力。知己知彼,百战不怠。了解别人,要从观察它门的行为开始,之后要对他们的行为进行分析,进而推敲出来他们的战法和策略。好的策略,要学来自己用,不好的要抓住他们的弱点,一举拿下。

结语

收获和体会是多方面的,有很多都需要做更详细的解释。接下来,我会分享我在这个对战游戏里,所用的策略,以及如何更加高效的参加Codingame的比赛。最后,能顺利的参加完这个比赛,特别需要感谢小微的大力支持,小微,谢谢你。

并发与并行的区别

并发(concurrency)和并行(parallelism)是两个完全不同的概念。

并发,从它的英语本意来看是竞争的意思。这是理解它的关键。没有竞争,并发就无从谈起。为什么会有竞争,那是因为资源是有限的。资源是一方面是有限的,一方面还要满足不同主体的需求,这就会遇到资源的共享。这样以来,就要指定一些规则,让大家有效,并且安全的利用这些资源。这里的并字,强调的是一种秩序。

并行,和竞争没有半毛钱的关系。并行指的是一个任务的属性,看它能不能被化分成相互独立,可以同时完成的小任务。比如说,有一个任务,是要数一本书一共有多少字,那么这个任务就可以被分成很多份,让小明数十页,小微数另外十页。此处的并字,侧重点是指任务能不能可分,能不能同时进行,来达到加速的目的。

两者,不是一个概念,不对立存在。不同的用法是为了达到不同的目的。一个很好的例子,就是JVM中不同的垃圾回收算法,有的是并发的,有的是并行的。

时间去哪了

春晚,一首时间去哪了,一组父女的照片,让人禁不住悲上心头。确实,我们伤怀,因为我们最爱的人在慢慢老去,不知不觉的,无法阻挡的。

可与其说举手无措的哀叹时间去哪了,倒不如享受身边这摸不到,嗅不着的时间。时间,积淀了我们的心智,不仅是照片中的晚辈,还有长辈。

活在不同阶段,看不同世界。一生的风景,从开始到结尾,从艳阳到风雨,洒脱的体会,便不再在乎时间去哪了。其实,它那里也没去,就在你身旁,也一直会在你身旁。

Scala io

这周四周五两天参加了在巴黎举办的第一期 scala.io, 写点东西留作纪念。

开始关注scala其实是上一年的事了,经常看网上的新闻,发现它很火,才开始看的。学习scala的最初原因就是因为好奇,稀罕函数式编程。今年夏天,和公司里其他的scala爱好者一起上了coursera的在线课程,初步掌握了scala,果然和之前学过所有语言都不一样,很强大。兴趣依然盎然,才参加了这个io。

说实在的,我工作中也不用scala,io上好多主题也实在看的是似懂非懂。但目的就是为了去长见识,看看高手是怎么玩的。会上看到了 akka的victor klang,play的sadek,等很多大牛,惊叹于他们在盒子之外的思维,敢于挑战的勇气,看问题的深度,和对自己工作的执着与热情。

整场会下来,收获最大的真的就是视野。见识到了,同样的问题,在函数是编程的世界里是怎么解决的,是怎么改进的。保持一颗开放,好奇,天天向上的心。

Maven中的传递依赖

说有模块A,B,C。A依赖B和C,B依赖C。在A的POM中,可以只声明对B的依赖,而省略C。

有人说了,这样做不好,如果有一天B不依赖C了,而A仍然需要C,A就傻逼了,因为他躺着中了一枪。所以有人说,A一定要明确的声明对C的依赖,而不是靠B做一个传递依赖。

我觉得,任何事的对与错都不是绝对的,得看。

如果真的不好,与其保留这种名不正言不顺的做法,不如让Maven直接给它删了,何必模棱两可呢。避免许多口舌。

软件测试的级别

这里所说的级别是指一个测试所覆盖的系统的范围的大小。一个测试所覆盖的系统越多,它的级别也就应当越高。之所以想谈软件的级别,是因为对测试级别的不合理划分会引发更多的开发成本,降低开发效率。

在软件开发的整个生命周期中,在它的交付阶段,一个必不可少的步骤便是验收测试。验收测试的目的在于证明软件可以满足客户的所有需求。这个测试是软件测试中的最高级别的测试。它的特点有,系统覆盖范围最为全面,从用户界面,到算法逻辑,到数据存储,全部囊括其中。其次,测试必须基于用户的真实使用环境,一切都是真枪实弹,不能参杂任何的仿真的元素。最后,这种测试往往不能被完全自动化,它的执行会牵连到测试人员的直接参与。

从以上特点我们可以总结出来,一个测试的级别越高,它的执行成本就会越高。其中包括,资源环境的配置,人员的直接干预。这也就必然决定了测试的反馈时间延长(比如说配置环境需要半天,测试人员到位需要提前预约)。其次,由于大的覆盖范围,分析问题,鉴定问题的难度也会增加。因此,一个测试的级别越高,它被执行的次数就应该越少,它被执行的时间段就因该越晚。

我并不反对写高级别的测试,但我反对把一个验收测试当作单元测试用。