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。欢迎大家使用。
结语
这段难忘的比赛经历，让我学到了很多东西。细想起来，主要是我真真正正的投入了进去，这就是竞技编程的魅力。