大家好，我叫Olya。 两周前，另一场比赛在CodinGame结束，一场比赛是针对该游戏的编程机器人。 我进入了世界排行榜的前300名，所以我想告诉你为什么比赛很酷并且分享我的秘密。 进入同一比赛前100名的伊万· 史密斯 （Ivan spaceorc ）也将分享秘密。
您将学习如何在游戏AI编程竞赛中成功竞争。
什么是CodinGame？
codingame.com是面向所有年龄和培训水平的开发人员的教育平台。 您可以用26种语言编写：从C＃和Python到Bash和Haskell。 最酷的事情是，那里的任务不是无聊而难以理解的，而是具有良好GUI的真实游戏：
竞赛是每两个月举行一次的为期10天的竞赛。 任何人都可以参加，不必成为ACM ICPC的决赛入围者。 当然，要想达到最高境界，您至少需要了解游戏人工智能的典型算法。
但是，为了有兴趣地度过几个晚上，最基本的知识就足够了。 每个竞赛中都有一个现成的代码，用于读取输入数据。 仍然只有阅读规则，写朴实的if-else-并投入战斗！
库图鲁代码
“克苏鲁密码”是最后一场比赛，比赛于6月15日至25日举行。 要找出情节和目的，只需进行描述即可：
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
永远说谎的东西根本没有死。 死亡死于一个神秘的永恒世代。
您和您的研究人员团队已发现克苏鲁之墓。 这是您一生中最糟糕的决定，因为他还没有准备好醒来，现在却饿死了您。 但是地下室是一个真正的迷宫，您不记得出口在哪里……如果仍然在那儿！
哦……看来克苏鲁并不孤单，现在他正在为你派遣深渊者。
尝试保持最长的生命，但请记住，一个人不会持续很长时间...
规则
我将立即说，您可以观看Tinsane上的规则和基本策略分析视频，而无需阅读规则的文本描述：
否则，请继续阅读。
地图
在游戏中，四个玩家在生成的地图上行走-更准确地说，是相互连接的单元格图。 地图上还有更多正在运行的敌方小兵，其目标是赶上并吓players玩家。
性格
- 研究人员是参与者之一。 在一个单元格上向任何方向移动。 它具有超级大国，但稍后会更多。
- 范德勒是一个绿色的怪物。 从先前已知的点每5圈出现在地图上。 它产生3–6步，搜索最近的玩家并开始追逐。 每转仅走一平方。 如果他没有在N步之内抓到任何人，他将从地图上消失。
- 砍刀-类似于带镰刀的死亡。 出现，代替健康值低于200点的玩家，并保留在地图上直到游戏结束。 如果他们之间没有墙，则“看到”一个球员。 如果在2步中目标没有失明，则下一步跳到玩家最后一次见到的地方。
生存
如果游荡者或砍杀者随玩家一起进入牢房，则玩家会失去20点生命。 而且，玩家每回合都会无缘无故地失去一定的生命值。 但是，如果在两个细胞的半径范围内有活着的研究人员，那么损失的健康就会少一些。
研究人员超级大国
- 计划-5回合内使生命值提高2点。 如果其他研究人员落在了行动半径之内，那么效果会扩展到他们身上，并且效果的创建者每人获得+2生命值。 每个游戏可以使用2次。
- YELL-吓到下一个单元格中的玩家。 计划在下一回合中执行的动作将变为WAIT（玩家将静止不动）。 如果流浪者追赶敌人，并且您想替代他，这将很有用。
- LIGHT-照亮半径为5的单元，每个游戏可以使用3次。 帮助吓跑流浪者：当他们计算到最近目标的路径时，每个照亮的细胞数为4。
游戏结束
如果玩家的生命值降至零，则该玩家死亡。 经过200次移动后，幸存的玩家开始更快地失去健康，游戏几乎立即结束。
竞赛开发者将规则提供给选手，但是成功的选手会去Github并阅读裁判代码 。
战术
我必须马上说我不是从零开始。 6月16日，Kontur 在七个城市举行了编码中心-那些希望讨论比赛并在宜人的环境中玩乐的人的会议（ 照片 ）。
我在大学通过了考试，但没有到达叶卡捷琳堡的中枢，但我利用了主办方提供的奖金-入门套件。 它有两种语言可供使用-C＃和TypeScript ，并且它已经实现了整个基础结构：每次读取游戏状态的逻辑，以及表征游戏本身的类（例如状态和可能的动作），以及一些辅助类（例如自定义计时器）。 。 我能够立即开始写出最有趣的东西-我的大脑 机器人 研究员。
叶卡捷琳堡枢纽的领导人之一是Vanya Dashkevich（ spaceorc ）。 他已经在CodinGame上坐了一年多，参加了七场比赛，其中有五场达到了世界前100名：
我从Vanya那里找到了决定的细节，这使他在世界排行榜中排名第64位，并将他的决定与我的决定进行了比较。
[1]来到中心：在那里您可以获取入门工具包的链接，讨论规则，提出策略并结识有趣的人。
比赛开始时，比赛结束时，选择下一步动作的算法看起来是一样的：
- 生成机器人可用的所有操作；
- 将它们应用于当前状态；
- 评估这些举动的结果；
- 选择最好的一个。
产生可用动作
奥尔利斯特卡（Ollisteka） ：在这一步，我开始应用启发式方法-我以为自己代替了研究人员，并决定了什么是好的，什么不是。 我可以去下一个空闲单元吗？ 添加这样的举动。 我还有一个未使用的计划，附近没有流浪者或砍伐者，下一回合会攻击我吗？ 添加。
根据相同的方案，LIGHT和YELL属于可能采取的措施，但是它们的使用只会使我在排行榜中的排名降低。 因此，我仍然将它们从最终实现中删除。
[2]不要害怕包含幻想：对于初学者来说，简单的试探法和几个条件运算符就足够了。
中风应用
将移动应用于游戏状态的过程称为模拟。 通过模拟，您可以使用高级AI编程技术： minimax ， 遗传算法 ， 蒙特卡洛树搜索等。
Ollisteka ：这是与我的“模拟不足”相关的步骤。 “ Nedo”-因为在我离开之后，其他玩家应该离开，敌人应该离开或重生。 但是，我懒得对四个玩家和大量具有平凡逻辑的敌人进行完整的模拟。 因此，我只是根据自己是一个人还是一群人来改变自己的健康状况，这个回合没有遇到流浪者。
spaceorc ：最近我通常的方法有两个步骤：
- 当组织者打开所有规则并将“裁判”的来源放到Github上时，您将以任何方式进入舞台；
- 你带裁判，看着他，写一个模拟。
模拟已完成，具有所有细微差别，但效果不佳。 我通常会打赌搜索的速度和深度。但是完整的模拟可以让您在本地进行许多比赛并比较不同的策略。 我使用CodinGame测试了完整的模拟-我预测了各小兵的位置，知道了对手的下落（即下一步行动），并找出了差异。 当完整的仿真准备就绪时，我开始编写一个快速的仿真-简单地做一个工作即可。
[3]想登顶吗？ 您必须弄清楚规则并编写模拟。
模拟对手
spaceorc ：编写了蒙特卡洛树搜索法，但由于没有太多时间进行整理，因此效果较差。 通常，这种方法或多或少仅在Ultimate Tic-Tac-Toe中出现 。 对手的打法相同-每步加得分模拟，我的举动-MCTS直到最后。 以这种方式可以在50毫秒内模拟大约50场比赛。 对于MCTS而言，这还不够，因此我将其删除并返回到最初的想法。
结果，快速仿真变得不完整：
- 停止考虑流浪者，距离我不超过8个牢房；
- 停止产生流浪者，因为它们已经以5个动作产生了，这大约是我的搜索深度。
因此，搜索的深度增加了。 我还尝试模拟对手的动作（没有黄，光，计划），但结果却更糟。
评估功能
评估功能有助于选择所有可用动作中的最佳动作。 它在进入时获取游戏的状态，而在输出时给出带有估计的数字-数值越大，当前玩家的游戏状态越好。
Ollisteka ：我的评估中包括哪些参数：
- 我的研究员的健康状况；
- 流浪者：
- 如果他有可能下一步行动，那将是一个坏举动；
- 如果我与他同在一条线，那么离他越远越好；
- 如果他还捕食我，那么距离就更重要。
- 周围的自由细胞，以免陷入死胡同；
- 其他研究人员，最好与他们保持联系；
- 当前计划：如果我的健康状况降至230以下，那么治疗是个好主意。
在某些时候，我试图评估这些削减器，但是当我删除它们时，我在排行榜中被提升到几十个地方。 如果我更好地弄清楚他们的逻辑，那么也许他们会做得更好。
结果，我的评估可能会更小，但正如他们所说，它的确可行-别碰。
spaceorc ：我尝试使用评估功能，但是效果并不理想。。。总的来说，在排行榜中比我高很多的人并没有做太多的事情，但是提出了很好的评估功能。 我没有应付。 我的最终评估功能包括：
- 点数（死亡的行程+健康）；
- 乌鸦 ;
- 与外国研究人员的距离。
[4]实验：更改评估函数参数的系数，添加新参数并删除旧参数。
选择最好的举动
我们按降序对移动进行排序，采用第一个，然后使用它。
最佳化
争夺前100名的位置还不足以拥有良好的评估功能和完整的模拟。 机器人运行得越快，在一个时间片中将模拟出更多的游戏。 游戏越多，当前举动越有可能达到最佳状态。 移动越优化，在排行榜中的位置就越高。
Ollisteka ：我利用了地图可以以图形形式表示的事实-我预先计算了从一个单元到另一个单元的所有路径的长度，并且没有每次都花时间。
spaceorc ：在CodinGame上，仿真工作很快，在50毫秒内完成了数万次移动。 由于以下原因：
- 位掩码和不安全代码。
- 资源管理器-整数，流浪者-整数，斜杠-整数。
- 所有可变状态都适合128字节，因此一切操作都非常迅速。
- 坐标为字节，因为最大的映射具有222个空闲单元。
- 队列必须为-var queue = stackalloc字节[255]。
- 预先计算路径，距离和其他事物。
我最近一直在做，非常好。 顺便说一句，我总是为这种模拟编写许多测试，否则，它们将无法调试。
[5]想要竞争前100名的位置-摆脱低效的代码。
它导致了什么
Ollisteka ：在整个比赛中，我的机器人一直稳居前300名。 在某个时候，我甚至排在世界排行榜的第84位，但是后来我提交了一个新版本，但没有回来。\ （ツ） /¯在第290位排名结束时，我很高兴，原因有以下三个：
- 这是我参加的第一场比赛，因为过去我忙于学习。
- 我喜欢游戏本身-很清楚如何玩以及如何赢得比赛。
- 世界前15％-听起来很酷:)
很明显，要想达到顶峰，就需要进行完整而快速的仿真。 但是我不想这样做，所以我只是将参数添加到评估函数中并更改了魔术常数。
spaceorc ：我对结果非常满意，我进入了前100名...但是我仍然必须在评估功能上做更多的工作，结果证明对模拟有很大的偏见。 最后我有点累，我的想象力还不够...
总结
看看CodinGame并尝试一下！ 他们在7月承诺进行新的竞赛-来到中心，我们将一起对机器人进行编码。
有用的链接：
UPD 感谢dbf的评论：Kutulu的代码已上传到multiplayer 。 因此，您可以将本文中获得的知识付诸实践！ :)