所以

与去年一样，我的名字叫安德烈·里巴尔卡（Andrei Rybalka），今年才33岁。而且，由于我进入了前十名，我决定再次分享为2018年俄罗斯AI杯赛编写游戏机器人的方法。

这次的任务是足球。 这项任务本身有点让人想起2014年曲棍球比赛时的RAIC，但是解决方案却完全不同。

这次世界是三维的，并且这个三维完全被使用了。 游戏本身最让人联想到火箭联盟 。

我不会介绍这部分内容，因为它看起来比较容易。 您可以在网站或视频上观看游戏：

为了让生活看起来对我们来说不太甜蜜，开发人员除了游戏世界的不确定性之外，还将游戏滴答声分成了100个低音炮，这最初使大多数参与者都无法进行准确的仿真，对我而言更是如此，他们打算用慢速Java编写机器人。

另外，我必须说，冠军分为几轮，这可能更适合打轮。

简要介绍比赛系统

对于初学者，需要2周的开发时间。 然后第一轮过去。 它的300最好走得更远。

一轮比赛后，比赛规则发生变化（特别是将硝基添加到比赛中），并给出了另外2周的时间，此后第二轮比赛结束。

然后规则又变得复杂了（增加了第三个玩家），又给了一个星期，我们进入了决赛。

但这还不是终点。 决赛之后还有另外一个星期，在这个星期结束时，沙盒只会停下来，而且其中的6个最好的沙盒（不包括决赛得主）也将获得奖励。 沙盒决赛和冠军决赛之间的根本区别在于，在沙盒中，游戏是以随机格式创建的，而不仅仅是以当前回合的格式创建的。

参与故事

技术部分将更低。 对于那些对历史没兴趣的人，您可以向下滚动直到其变好。

第一轮

与大多数人一样，他从一个星期的测试版开始。 花了很多时间，每晚4个小时以上。
在填写第一个版本之前，它需要进行多次迭代
我们进行编码，直到我们开始击败上一个版本为止-我们收集-我们考虑上一个版本的当前版本-我们重复进行 。

我并不急于进行第一轮补给，这发生在回合前几天。 而且，由于到目前为止，我的机器人还没有和任何人玩过游戏，所以我不知道自己处于什么样的世界，以及该排名中的哪个位置。 当我看到自己已经连续赢得超过100场比赛而没有任何损失时，我冷静了下来。

总的来说，我的第一个输球似乎是在时限上排在第12位，而且连续输掉的第一场比赛已经进入前10名。

简而言之，我意识到我有机会进入第二轮，进入前300名。
因此，我没有追逐它的位置，也没有在本回合中淹没其他任何东西，而是继续工作。

当时，我看到不连接硝基的情况下仍有很多改进空间（在第一轮之后出现），因此我专注于该策略的主要部分，意识到在第二轮之前会有超过2周或更长时间，并且我将有时间固定硝基。

第二轮

第一周，我正在积极编程，但仍然没有连接硝基。 我想在第二个星期这样做。 但是结果却有所不同，因为在第一周结束时，我患了肺炎。 我当时无法编程，所以我只上传了当时的内容，可以说，在这里我对冠军的积极参与已经结束。

在锦标赛结束之前的接下来的3周中，我制定了一项可能需要20个小时的策略。

结果，在第二轮中，我的机器人从原理上讲并不知道游戏中存在硝基，但仍然以第16位的优势占据了上风。

决赛

在决赛中，增加了第三名球员。

我用Java而不是C ++编写缓慢的代码，因为8人中有7人的评分高于我，而在此之前，我的机器人经常陷入超时状态，因此随着第三个玩家的出现，它开始在100％的游戏中跌落。 幸运的是，沙盒中的游戏是以随机格式创建的，所以我自动
每三局仅输掉一次，因此飞入的速度并不过分。 它似乎已跌至第18位。

除了编程，编辑评估函数中的系数并运行测试之外，在疾病发作之后，我第一次在决赛前一天的晚上坐在机器人上。 他添加了一个非常简单的硝基指向严格向上的方向，这样，两个攻击者将停止在同一点上奔跑并在此处相互碰撞，并从渲染深度开始以仿真精度结束，以减少3x3游戏的所有可能，从而只有僵尸程序没有因超时而死亡。
以这种形式，它播放了结局。

在决赛的两半之间，我再次坐在机器人上呆了好几个小时，其中大部分变化涉及系数的动态选择，遗传学的早期中断等。 总的来说，我一直在寻找准确度与错误计算深度和速度之间的平衡。
除了与速度作斗争外，他还进行了其他一些更改：

• 将远距离（相对于球）的攻击者发送到球与对手球门之间的中间点
• 我将硝基固定了一点（说明将在技术部分中）。 它仍然非常简单，但是变得更加高效。

总计，运行了测试并且看到了395：254与以前版本的比分，我对此保持了冷静。 这使我在决赛中获得第9名。

沙盒大结局

我继续受到伤害，并且在整个星期的大部分时间里都没有在机器人上工作。 结束的前一天，我看到几个人上传了新的版本，这些版本经常对我不利，并且可能使沙盒失去奖品。 所以我花了几个小时。

唯一的重大变化是，我三周前在Git挖了支行，使用简化算法模拟了敌人的行动。 当时效果不佳，但我想到了，进行了测试，看到了
胜过以前的版本，几乎翻了一番。 总计，在停止时，我在总体表中排名第十，与沙盒决赛的第四名相对应。

一切运作方式（技术部分）

如果术语不正确，我预先表示歉意。 另外，我从内存中写入数据，因此有可能在某个地方我不会描述最终版本。

因此，遗传算法是核心。 染色体由几个基因组成：

• -PI..PI范围内的小数，指定运动方向
• 0..10范围内的整数，指定此操作的重复次数
• 从0到1的小数。如果该值大于某个阈值，则进行跳转

基因型可以包含不同数量的染色体，但以这种方式进行的总数为40（包括重复）。

最初，我创建几十个随机基因型。 我向他们添加：

• 球上的轨迹
• 各个方向的直接轨迹，仅10个，偏移36度
• 一个根本不做任何事情的基因型（没有它，机器人总是在某个地方运行，即使它已经处于最佳位置）
• 先前tick虫的最佳基因型

然后将其全部模拟并通过评估功能运行。 N个最佳基因型可以“存活”，并被克隆M次并带有突变。 突变后，每个基因在给定范围内发生变化的可能性为10％。 好吧，这已经重复了好几代了。
没有交叉，在这个问题上我看不出任何意义。

总计，每个足球运动员每个刻度的最大可能轨迹数约为800，但实际上，在大多数情况下，该数量要少得多，因为 在某些情况下（例如，在不久的将来我们肯定无法碰球时），球员的动作被简单的启发式方法所取代。 另外，N，M和世代数取决于现场情况。 首先，从远处传球。 此外，如果找到了可接受的估计轨迹，则会提前中断错误计算（但不要早于第五代）。

巨集

守门员跑到球门中心的前方。 我的测试表明，对我来说，最好站在球门前而不是像大多数顶级球员那样坐在球门​​内。

该点的位置偏离中心的位置取决于几个因素：球飞行的位置和方向，球击中我的目标的点，如果计划了目标，最近的进攻对手的位置等。

如果球在对方身边并且朝他的目标飞去，我们可以选择硝基。

如果我的守门员可以比攻击者更早地击球（还有一些其他条件），那么攻击者将忽略该球并跑到球与对手球门中间的一个点。 我经历了很多选择，完全由他来执行。 就我而言，这是效果最好的。

否则，如果球太远，攻击者会沿直线一直运动到球与地板的最近接触点，在该点他可以拦截球（如果我们没有时间接触第一个接触点，请检查下一个接触点，等等）。

否则（当球到达时），进攻者跑到评估功能告诉他的地方。 是的，而且，如果硝基附近存在，我们可以捡起来，我们选择它。

在3x3游戏中，第二个进攻者更有可能瞄准球，而向前奔跑的机会更少，期望门将传球。 但是，如果仍然运行，则会选择另一个点-靠近中心线。

同样，每个刻度都模拟了100个微球（带有缓存）将球向前100个刻度。

该轨迹已在许多地方使用。 例如：

• 确定球与地板的接触点
• 找出球是否威胁到我的进球以及门将是否需要切换到模拟模式

在模拟球员的轨迹时使用了相同的精确轨迹，以免每次都计球。 但仅在球与任何足球运动员第一次碰撞之前。

顺便说一句，写《足球先生》很懒惰，“球员”，“机器人”这两个词是战略保留的，
所以我的包装器类简称为Dude :)

模拟

在大多数情况下，它带有一个微透镜，但是在某些情况下，它切换到具有大量微透镜的精确模式（开始时为100，然后在2x2的游戏中减小为50，因为测试表明结果的差异在误差范围内，而误差为10） （3x3），因为否则会超时。

在精确模式下，我在弹跳时切换，或者离球太近以至于在下一个滴答声中可能会发生碰撞。 此外，还有大量的小拐杖，小技巧，优化，我本人不会理解。

例如，仍然用1个Mikrotik模拟了飞行球，但是如果在下一个Mikrotik之后我发现有碰撞，他会回滚到先前的位置并以更高的精度再次进行模拟。

另外，我也假装是其他球员（包括我自己和其他人），如果他们在空中（因此他们的轨迹更容易预测）或接近球。 对于对手而言，最终版本使用了我自己的决策策略的简化版本，该策略每5秒钟发布一次（更多情况下它不允许速度）。

在模拟每个角色时，我算了一下自己，球和其他足球运动员提前40个滴答声（我对基因型动作次数的限制），然后仅对一个球模拟了相同的滴答声。

硝基

简单到不雅。

在最终版本中，硝基始终处于打开状态，如果玩家处于空中状态，并且在最后几个刻中没有击中球，则始终打开。

刚开始时，我总是直接将硝基指向上方，但是后来我尝试进行实验，并且将球精确定位到球中心的选择效果最好。 我还尝试了选择方法，以便由遗传学选择硝基的方向。

它工作得更糟。 可能是由于缺乏搜索深度。

评分功能

每个刻度的分数总和，每个刻度衰减2％。

当然，最大的重量是有目标的。 有几件事影响了他的体重：

• 进球时球到敌方守门员的距离（越远越好）
• 球的Y坐标（因为在球门的顶部很难击中）
• 球沿Z轴的速度（指向敌人的目标）

攻击我时，一切都完全相同，只是符号相反。

此外，对于攻击者而言，总体得分取决于：

• 球员到球的距离（这样即使他无法击打他也能跑到球上）
• 跳高的罚分（仅在带来很多分以至于超过该罚分时才跳高）
• 模拟的下一个滴答声从球到对手的距离
• Y球坐标（越高，敌人拦截它的机会越少）
• 球的方向与敌方目标中心之间的角度的余弦值
• 如果我碰到球则举报
• 旗帜，敌人是否碰到球
• 选择硝基的奖金

而且，击中敌方玩家也会获得少量奖励。 虽然实际上已经发生了，但是很少。

对于门将：

• 距离球的奖励，Z处的球速，Y处的球位置
• 跳罚
• 在我的球门前方区域找到球的处罚
• 考虑到到敌人和我的攻击者的距离（以便球会飞离敌人，但如果可能的话，会飞得更近我的攻击者）
• 还有一些小东西。

机器学习

作为实验，它仅在git的一个分支中占一小部分。 但无论如何我看来还是值得一提。 我没有想到（我不确定什么才有意义）。

通常，我试图在他的帮助下根据敌人和球的位置和速度来预测敌人是否可以拦截球。 我计划在评估功能中使用它。 惩罚可能拦截的轨迹。

但是我立即明白，我不仅买不起神经网络，也买不起任何严肃的东西，因为每条轨迹必须做80次。 好吧，即使是40或20，也算不上每个刻度，但无论如何，我根本没有任何时间储备，因此我什至没有考虑这些选项。

这是我所做的：

我用改良的机器人跑了几场比赛，在其中寻找轨迹时，我保存了关于自己和球的数据以及一个标志，以及是否找到了在其中我拦截球的轨迹。

我考虑了所有与足球运动员有关的坐标。 即 我一直将它放在坐标[0,0,0]中，所以我只保留了10个字段：球的相对位置，球的速度矢量，足球运动员的速度矢量，二进制拦截标志。 我仅将数据集保存为字段的中心部分，因为 我意识到，简单的算法还无法解决问题。

然后，我用max_depth = 7将此数据集DecisionTreeClassifier馈入。据我所记得，经过训练的树给出了大约90％的准确性。

接下来，我将树导出到一组ifs（本质上是DecisionTree）。

它看起来像这样：

public static boolean predict(double dude_vel_x, double dude_vel_y, double dude_vel_z, double ball_rel_pos_x, double ball_rel_pos_y, double ball_rel_pos_z, double ball_vel_x, double ball_vel_y, double ball_vel_z) { if (ball_vel_z <= 6.4765448570251465) { if (dude_vel_y <= -6.087389945983887) { if (ball_vel_z <= -20.188323974609375) { if (dude_vel_x <= 13.032730102539062) { if (ball_rel_pos_y <= -1.1829500198364258) { return ball_vel_y <= 18.906089782714844; } else { return false; } } else { return true; } } else { // ............................ 

在这个阶段，我进行了测试，没有发现任何改善，并将试验推迟到后来，由于我的冒险，该试验从未到达。

施罗丁巴格

第一轮过后的某个地方，我在房子里抓到了这种稀有动物。

谁不知道，这是一个错误，他们只能通过阅读代码来找到，并且找到它后，开发人员想知道程序如何工作。 就我而言，她也保持在前十名。

通常，错误在于在该基因的复制函数中调用了一个构造函数，其中省略了包含该基因值的可选参数。 在没有此参数的情况下，该值是随机选择的。 因此，当试图复制一个基因而不是复制一个基因时，他创建了一个新的随机实例。

实际上，我没有进行遗传学搜索，而是进行了随机搜索，因为每个刻度都仅生成了数百条随机路径并选择了最佳路径。

更正后（在代码中添加了2个字符），游戏变得更好了约3倍。

仪式舞蹈

在某个时间点，我注意到球员有时会无缘无故地弹跳，尽管受到了点球，却远离球。

事实证明，我以100微米的精度计算了跳跃的瞬间。 有时结果是，仅在跳跃时，球与杠铃发生了碰撞。 并根据此刻精确地计算的准确性，建议的轨迹是否导致了目标。

粗略地说，球飞向对手的球门并击中门柱。 我的足球运动员在场地的另一端奔跑，模拟了没有跳跃的轨迹（有1个mikrotik），并且看到球没有击中球门。

然后出现另一条轨迹，恰好在球击中杆的那一刻跳了起来。 而且，由于我不仅对足球运动员而且对一个球都计算出一个跳动，其跳动幅度为100 Mikrotik，因此，计算出的球的跳动角度与在1 microtik的路径中获得的角度不同，并且可能会出现这种更精确的轨迹中的球落入门。

因此，将选择此轨迹，机器人将跳跃。

通常，通过弹跳进行仪式舞蹈，玩家将目标设定为:)

杀手级功能

她不是

测试中

我以8个线程（每台计算机和笔记本电脑上有4个线程）驾驶无尽的游戏。 我选择了游戏数量，以使其具有统计意义。

如果策略上有重大改进，则总共可以实现1000个目标，
进行较小的更正后，留下过夜，然后账单就成千上万了。

常数的遗传选择

我在第一轮之前尝试过。 它没有给出任何信息，原因是从遗传学上讲，您需要参加大量比赛的锦标赛。

我试图玩100,000滴答声的游戏，但这还不够。 由于强度的差异很小（通常在选择常数时确实如此），每10万次滴答声的获胜者在很大程度上取决于情况。 您需要做更多的事情才能确保获胜者。 而且我不能离开选择一天或更长的时间，所以我拒绝了这项冒险。

总结

传统的感谢组织者。 任务很有趣。 遗憾的是，我被迫错过了近一半的锦标赛冠军，而对硝基选手或三名选手却什么也没做。

结果，直到最后，我在沙盒中观看了我的策略如何在没有硝基的情况下以2x2模式获胜，以13：2的比分击败了在决赛中获得第三名的任何Mr.Smile，并且在几局后输给了他同样的12：2在3x3模式下使用硝基:)

当然，还有我专有的可视化器提供的视频：

在未来的锦标赛中，只有您可能不得不告别此可视化仪。
对于我来说，每次我都越来越相信，如果您要申请正常的名额，唯一的选择就是写信……

嗯，你明白了。

每次都厌倦了Java的缓慢性并削减了策略的强度，以满足所分配的时间。

我希望有人在我的作品中发现一些有趣或有用的东西，并带有自传特征:)