CodinGame之Ghost in the Cell赛后感

这次利用业余时间参加了CodinGame的Ghost In the Cell人工智能游戏比赛,下面记录一下比赛中所积累到的经验。一是希望下次能做的更好,二来希望能给没有参加过比赛但是有浓厚兴趣的朋友,起到个抛砖引玉的作用。

赛果

  • 传奇者联盟
  • 总排名: 59/3508
  • 语言排名Scala: 2/50

游戏概述

比赛双方各拥有一个主基地和一定数量的兵力。除了主基地之外,地图上还有待征服的其他基地。每个基地都有一定的产能,一旦拥为己有,就可以生产新的兵力。征服一个基地,需要往基地上派遣足够的兵力,谁的兵力多谁胜。一旦占领基地之后,选手可以通过牺牲十个兵力来转化为基地的永久产能。此外,每个选手还拥有两个炸弹,可以投放到基地上,摧毁在目标基地上的兵力,并且阶段性暂停兵力生产。最后谁的兵力最多谁获胜。更多细则,请参考比赛主页

策略篇

之前的比赛(比如Coder Strike Back, Great Escape),可以利用优化算法(比如基因算法,Minimax算法)对整个游戏进行模拟,无须深入挖掘游戏策略,就可以找到非常高效的方案。

Ghost in the Cell这款游戏一大特点就是巨大的搜索空间(分支因子过大),导致我们无法通过全面的模拟来实现优化的解决方案。这种情况下,我们必须要利用人脑对问题深入分析,设计一个为这款游戏量身定做的策略。这种利用人脑分析引导程序搜索解决方案的方法,叫做启发式(heuristic)算法。启发式算法,不能保证最优的解决方案,但可以在相对短的时间内,找到符合一定条件的方案。

这种方法的效率非常依赖于人们对问题的理解,因此,选择了启发式算法,就要深挖游戏中的概念和规律。接下来是我为对游戏的理解。每次理解得到升级,我的排名都会直线上升。

部队机动性

一旦一个部队从基地上被派遣出去,我们便失去了对它的控制,直至它到达目的地。所以我们要限制在路上的部队,与其让它们长途跋涉,我们应该为它们找到中转基地。这样可以增加部队的机动性,如果在到达中途基地的时候,战况和预估的有差异,我们可以给它们下达新的命令,执行新的任务。

出乎意料的是,通过中转基地的路径,会比直达路径更快。就好像,某些中转基地之间有快车道一样。计算最优路径有现成的算法:Floyd Warshall algorithm。这里是我的scala implementation

距离和产能的天然效应

即便我们可以在部队的数量上胜过对方,我们也未必能征服对方。假如基地A和基地B每轮产生等量的部队,那么基地A必须在起始兵力上拥有一定的优势,才能攻陷基地B。

举例来说,基地A和基地B,初始各有2只部队,并且每轮都生产2个新部队(产能为2),基地A和基地B相距四步。如果基地A在第一轮输送2个部队到基地B,当它们到达目的地时,基地B将坐拥2+4*2=10支部队。因此基地A的2只部队并不能撼动基地B。
基地A必须派遣至少2+4*2+1=11部队才能拿下基地B。因此,基地A的兵力优势必须达到4(路程)*2(产能)=8以上才能发起有效的进攻。因此远征难,没有十足把握,不必发动攻击,而是要利用现有的部队去做更有效的任务,比如扩大产能。

一旦理解了距离和产能的效应,我们可以计算每个基地的时间线。简单来说,就是可以通过计算基地的产能和发往基地的部队,算出基地在每个时间点的占有者和所持有的兵力。这个时间点是我进行攻防策略设计的最重要的根据。

具体来说,对每个基地我都会计算它的20轮后投入产出比,最终的兵力/所需投入的兵力。

炸弹的释放和躲避

炸弹可以摧毁对方的部队,拖延对方的产能。用好它要选择好地点和时机。炸一个没有部队没有产能的基地,没有任何效果。等到自己部队都快要被消灭殆尽的时候再释放炸弹起不了任何作用。因此好的策略,是利用炸弹阻止对方的扩张,为自己的扩张争取时间。

很多人的都选择在比赛一开始,就释放炸弹,这样炸弹会经历一段相对很长的过程才能到达目的地,这个时长增加的炸弹打击的不确定性。我所选择的方案,是在地图的中心点释放炸弹。这样我可以缩短从炸弹释放到炸弹爆炸的时长,进而降低不确定性。

选择中心点当做炮台还有一大优势。值得注意的是,炮弹不能像部队那样,可以利用中转基地缩短两点之间的距离。因此先攻占中间点在发送炸弹可以缩短炸弹爆炸的绝对总时长。

方法篇

在处理一些复杂问题的时候,我们不可能事先就制定一个完美解决方案,因为有很多概念、规律会隐藏的很深。通常,我们要通过实践去学习,边实践边发现。下面介绍一下处理复杂问题的一些方法。

千里之行,始于脚下

边实践边学习的精髓,就是要实践。千里之行,始于脚下,不要怕步子迈的小,一定要走出去。所以,不要多犹豫,开始写代码吧。

这也是我学习离散优化课程中老师大力推荐的方法。先从贪婪算法开始,有助于帮助更深刻的理解问题,发现可以优化的地方,也可以从心里上得到阶段性的成就感。接着再设计更加稳定可靠的优化算法,循序渐进的解决问题。

观察

观察能力,是非常重要的学习能力,通过观察,你可以找到内在的规律,就比如远征难的概念。CodinGame里,你可以观看排行榜上高手的比拼,从他们哪里可以观察到许多有用的策略。

放松

如果你感觉到阻塞,停滞不前了。一定要学会放松,去散步,打球,放空,好的想法说不定在你洗澡的时候就冒出来了。

实战篇

完美的计划,精妙的策略,不执行,都是纸上谈兵。选择一款好的编程语言,好的开发环境,会节省你开发的时间,进而给你更多时间去实践和学习。

Scala语言

Scala把指令时编程和函数式编程结合在了一起,并且对Immutablility有特别好的支持,基于篇幅的限制,我接下来打算专门写一篇文章,介绍面向函数式编程在人工智能对战游戏中的应用。

CodinGame

鉴于CodinGame平台的特点,只能提交一个源文件的限制,我开源了我的CodinGame工具:CodinGame Scala Kit。欢迎大家使用。

结语

这段难忘的比赛经历,让我学到了很多东西。细想起来,主要是我真真正正的投入了进去,这就是竞技编程的魅力。