2018年俄罗斯AI杯第二名历史：CodeBall

大家好！

我是三年级的学生，在大学学习之初，我就了解了俄罗斯人工智能杯 ，以及后来的人工智能人工智能竞赛迷你人工智能杯 ，并开始积极参与其中，并取得了良好的成绩。 这次，RAIC参加了会议，所以没有什么可以阻止我的:)今天我想告诉大家我如何取得第二名。

竞赛规则可以在竞赛网站上找到，也可以在本文中找到 。 链接到我的个人资料： russianaicup.ru/profile/TonyK 。

一方面，今年的任务与过去几年的任务相似，而且似乎意识形态的解决方案与以前的任务（Agar IO和Mad Cars）非常相似。 大约一个星期后，我会感到无聊，并且厌倦了参与。

另一方面，我了解到我在以前的物理比赛中学到了很多东西，现在我可以运用这种经验，而不是踩老耙子，最后表现出更好的结果。

至于可视化，我决定在不同的轴上有足够的投影，或者以一定的角度显示。 但是我很误会，如果不是因为Local Runner内置的魔术可视化工具（组织者后来又添加了），我将不得不从那些经过beta测试阶段编写并投入公共领域的参与者那里借用3D可视化工具。

这次可以使用模拟器的伪代码，这等于使那些懂得如何逆转物理学并编写出色的机器人的人，那些不能逆转物理学但也可以编写强大的机器人的人具有同等的可能性。 我认为这是组织者的明智决定。

我做的第一件事是从C ++文档中重写模拟器代码，然后在我的旧计算机和服务器上测量了模拟器的时间。 在第二种情况下，结果是原来的两倍，尽管这是预期的。 我弄清楚了我可以模拟多少次和达到什么深度。 立刻变得很清楚，我们将不得不忘记对100个微技术进行诚实的模拟（在服务器上将一tick物理学分成100个“微技术”），因此有必要以necessary回的方式解决精度问题。

由于外壳的排列方式使得每个刻度上分别调用每个机器人的动作请求，因此我实现了一个简单的逻辑：在第一个机器人被要求执行动作的那一刻，程序会找到所有机器人的动作，并记住并给出第一个动作，当其他机器人要求该动作时，它会返回它记住的内容。

我不耐烦地将机器人送上战场。 我决定生成随机轨迹并选择最佳轨迹。 同时，他希望生成的布景能够执行一些复杂的动作，例如，从右侧绕球然后击球。

轨迹是行动计划。 最初的轨迹是这样的：

• 将动作设置为任意角度；
• 在轨迹的随机刻度上，将角度更改为另一个随机角度；
• 跳入轨迹的随机刻度。

这样的轨迹空间非常适合随机搜索，因为我（可能还有当时的每个人）可以从文档中获得原始仿真器提供的仿真数量。 经常会猜测出良好的轨迹，并且由于保留了前一滴答声的最佳轨迹，因此搜索被拖延了时间。

所有物体都放置在模拟器中：我的机器人，对手的机器人和球。 评估是最简单的：在轨迹的所有点上，从球到敌方目标的距离与目标到某人的大数值之和。 模拟深度200滴答声。 敌人以其最后的速度被预测。



我立即为第二个机器人添加了一个单独的动作，并强行取消了跳跃，如果在飞行过程中没有与球接触，则不会徒劳地跳跃。 同时，我的机器人获得了一半以上的时间，并且知道彼此的最佳轨迹。 现在，强大的对手已经有了第一个进球，他们已经有了门将和一些更复杂的逻辑。

事实证明，我没有考虑到敌方大门的距离，而是考虑到战场中心一侧的距离（ x和z混合），但这并没有影响该策略。 改正后，情况没有变好，这很好。 这通常在您编写机器人时发生。

然后他通过改变比分增加了守门员：他对我一半的射门得分以及对我的进球施加了罚款，并估计了守门员到我进球的距离。 现在，守门员站在球门处，将球击出。 一个重要的优化是，如果球不在我的一半视野内，则90％的时间分配给攻击者，10％的守门员，否则50％。

将机器人在每个点的轨迹评估乘以0.9 ^深度，我像整体得分一样凭经验得出该系数。 系数的值在很长时间内都没有改变，只要“能做就可以”。

他开始赢得冠军，并迅速在排名中上升。 Beta阶段结束了。

长期以来，我对这个策略(MAX_HIT_E - MIN_HIT_E) / 2 ，这些版本(MAX_HIT_E - MIN_HIT_E) / 2较小的编辑，错误修复（值得注意的是，我认为平均反弹强度为(MAX_HIT_E - MIN_HIT_E) / 2 ）时就(MAX_HIT_E - MIN_HIT_E) / 2 ，并且还优化了模拟器。 我设法在每个刻度上整理出的轨迹数量发挥了重要作用，因此我专注于优化。 去除鼻窦和平方根。 在更改角度之前或之后，在轨迹上添加了不太可能的零速度。 得分略有变化。

16版本一直排在榜首，但在beta测试结束一周之后，正如预期的那样，许多版本开始获胜 。

我尝试用从敌人到球的最接近距离之和来细化轨迹，并且得到了非常有趣的行为。 我的机器人在无法赚钱的情况下，经常开始封锁敌人，破坏他们的轨迹并阻止他们跑到球上，有时结果是非常成功和阴险的。

接下来，我固定了跳跃时的准确性。 如果有人跳到当前刻度线，那么我们先做两次，两次，然后再做其余的98次，我还尝试通过启发式系数来补偿某些微型机达到最大速度时精度的损失。 改进极大地帮助了您，并且命中率更高，更准确。

同样在这个时候，我开始在站点上的调试信息中显示我设法完成的迭代次数。 在200个滴答声中有250个，在每个滴答声分配给我的策略期间，我总共模拟了50,000个滴答声。

然后我打开了突变轨迹。 这大大改善了策略。 在大约所有迭代的一半中，不是使用新的轨迹，而是使用了略有变化的最佳轨迹，从而可以收敛到某个地方，例如，达到局部最大值。 事实证明那是一个强大的策略，我决定离开，直到第一轮，尽管它离整整还有两个星期。 但是几天后，她不再继续统治最高职位。

我花了一些时间来摆脱完全随机性，例如，我尝试进行三元搜索以找到机器人击球需要加速的角度。 但这并不总是可行，而且我也没有弄清楚如何进一步发展这个想法。

我的机器人知道每条轨迹只跳一次，但是当他们在地面上想跳起来然后将球击中空中时，他们不知道当您触摸球时可以跳第二次，从而使球重击，并且不只是推动它。

这是固定的，现在是模拟器，当他注意到有人可以在当前滴答声中将球击中时，后退一个滴答声并迫使机器人以最大的力跳动。 现在，机器人站在地面上，知道它将推离地面，而不仅仅是推动，而是第二次跳球。

我了解到，当添加硝基和另一个机器人时，由于缺少迭代，一切都会弯曲。 同样在不同的地方，我在准确性方面也遇到了很大的问题，我不知道该如何解决。 我没有看到任何分析解决方案或任何明智的管理方式 。

我需要一个全新的策略，或者一个将准确性和速度相结合的魔术模拟器，并且在最后阶段将为我提供足够的轨迹进行迭代。 我没有提出新的策略（令人惊讶的是），而是开始研究模拟器。

“智能模拟器”

我想处理的第一件事是准确性。

我一次模拟了100个Mikrotik，尽管在这100个Mikrotik中的一个发生了碰撞-或其他事件。 如果您忽略这一点，则对象的碰撞要比实际发生的碰撞晚（始终在第100个微透镜上），因此反弹的方式有所不同。 在轨迹的尽头，这个小错误可能会变成很大的错误。 例如，我们认为球击中了敌人的球门，但实际上它将从后门反弹到我们的球门中。

不难发现，在第i个微透镜上发生碰撞的情况下，无需计数全部100个微透镜，而是一次计数第一个i - 1微透镜就足够了（实际上，物理步骤被考虑了一定的时间dt ，现在这一次是t * (i - 1) ，其中t是对应于一个Mikrotik的时间）。 现在，您需要模拟1个微米（ dt = t ）和其余的100 - i微米。 我们只用三个模拟就得到了完全相同的结果，而不是一百个。 唯一的问题是，我们不知道碰撞将在哪个微透镜上发生。

在模拟的某个固定滴答声中，我们可以在一个模拟中制作从1到100的任意数量的微透镜，并查看是否存在碰撞。 在这种情况下，图像将是这样的：首先没有触摸，但是从一定数量的微透镜开始，直到一百个触摸。 除了在极少数情况下，首先没有接触时，然后在微透镜的某些部分上有接触，然后再没有接触。

因此，有可能在最坏的情况下使用二进制搜索进行10次模拟来找到发生碰撞的Mikrotik。 如前所述，对于三个模拟，您可以通过100个微控制器以完美的精度获得世界状态。

实际上，除了碰撞之外，还有其他几种类型的事件，并且可能在一个刻度中发生了几种，因此只有第一个事件位于一个二分法中，然后第二个事件位于刻度二分法的剩余后缀中，依此类推。 因此，在每次计数之前，滴答被视为每次模拟中几个微透镜的分段。

因此，这些问题得以准确解决。 但是由于仿真中有5个对象，并且根据最终规则应该有7个，并且所有这些对象经常崩溃，因此平均而言，二分法调用得太频繁了，而且工作时间长得令人望而却步。 因此，我进入了模拟器开发的第二阶段-优化。

显然，当其中一个机器人的轨迹移开时，此机器人不会撞到的所有其他对象每次都会移动相同。 显然，无需使用模拟器重新计算其状态（例如，计算与竞技场的严重碰撞）。

在整理出特定机器人的轨迹之前，足以诚实地模拟并记住所有对象在所有时刻的状态，然后简单地从内存中获取这些状态就足够了。 我们将此类对象称为静态对象，将对其进行排序的机器人是动态的。

如果突然有一些动态对象与静态对象发生影响（发生碰撞），则将这个静态对象添加到动态对象中，直到模拟当前轨迹结束为止。 实际上，在存储静态对象状态的阶段，会建立一个相互影响的图表，然后将其正确地用于将静态对象转换为动态对象。 例如，一个敌方机器人击中了球，并且我们生成了一条路径，在该路径中我们将敌方机器人击中了球。 现在，球将进一步飞行，并且在模拟过程中，当将敌方机器人添加到动态对象时，需要注意的是，应稍后将球添加到动态对象，即如果我们不干扰的话，敌方机器人会击中球的滴答声。 通常情况下，这是根据影响图递归完成的。



现在，模拟器不会计算所有对象，而只会计算动态对象，并且平均而言，它是一个对象而不是七个对象，并且长二分法的使用频率大大降低。 结果很快，不再需要在决赛中忍受其他机器人-太酷了！

带有新模拟器且模拟深度从200减少到100的第26版已在第一轮中发送。 但是它包含一些错误，并且没有明显的优势。

准确性的最后一个问题仍然是：沿着竞技场的四舍五入。 在这种情况下，为了达到绝对精度，必须诚实地计数100个微透镜。 解决方案非常简单：总是从地板上跳开。 没有舍入-没问题。

此外，一段时间以来，我进行了优化，消磁，并以更智能的策略研究游戏，从而获得了新的得分常数。 它变得更好了，该策略在排名中上升了很多，第37版在决赛之前一直都在沙盒中取得了我所有策略中最好的成绩。

从那时起，我在云服务中租用了一台32核计算机，以使我的策略彼此冲突，并开始对所有事物进行连续实验。 更改了常数。 我试图用自己的策略来预测敌人的行动，但这即使在与我的策略对抗的游戏中也无济于事。

通过求解方程，他学会了计算敌人的最后行动，并开始预测他的进一步行为。 增加了对硝基的支持：选择了球体表面上的随机点作为该作用。 进行了许多次要编辑。 但是进展不大。 到第二轮开始时，我以4-5的高点稳步赢得冠军

尽管如此，我并没有感到绝望。 我计划在决赛之前实施两项改进，希望这些改进可以大大改善该策略。 我决定在沙盒按照最终规则启动之前不解决它们，而是花时间调试和优化已完成的工作，以最大程度地减少上周（每分钟都很重要）的恶意错误的机会。

决赛开始前的最后一周。

我做的第一个改进就是这个。 在比赛中，通常情况下，我的大多数问题都是由对手控制，而其他任何策略都是在对手控制球的情况下出现的。 通常，他以某种方式击中了他-控制。 在这种情况下，无法预测球的轨迹并进一步计划一些有利可图的行动，在对手犯错并将球的控制权移交给我的机器人之前，仍然要做“任何事情”。 此后，您必须尽量不要执行可能导致球再次与敌人同在的事实。

换句话说，在规划轨迹时，我想考虑对手的可能位置，并尽量不要在那儿击球。 我决定使用一个四维势场（前三个维是坐标，立方体的边等于机器人的直径，第四个维是时间），我将填写它，生成随机的敌人轨迹。

后来，当评估我的机器人的轨迹时，我计算了在相应的时间点与球相交的所有多维数据集的总和，然后乘以一个比得分中所有其他值都高的系数。 也就是说，在目标之后，优先考虑了潜在领域。 如果他们不在空中（似乎没有人会在空中），它还允许在前30个滴答声之后将敌人从模拟中删除（敌人在此时只能在地面上做任何事，而这样遥远的不准确预测只会干扰）。空气以复杂的方式使用硝基来改变轨迹）。

通过为敌人生成随机轨迹，可以找出他击球所需的最短时间。 该值对于解决我的守门员过早跳出大门的问题很有用。 因为我的门将跳得很早，变得无法控制，所以我进球很多。 此后，敌人轻松地预测了我的守门员将如何飞行，并且如果可能的话，可以在我的守门员到达他之前改变球的轨迹。 现在，如果敌人可以比我的守门员计划提前击球，我取消了守门员跳伞。



事实证明，在不对策略造成重大损害的情况下，可以计算每个轨迹的轨迹，而不是每个轨迹。 通过将运行时间减半，我使平均迭代次数增加了一倍。 这里发生了一些魔术。 看来，如果我们计算每秒钟刻度的轨迹并将迭代次数加倍，则平均迭代次数将不会改变。 但是实际上，模拟器每次模拟会计数两个滴答声（200个微滴答声），而不是一个。 而且轨迹已经是50，而不是100深，这就是平均迭代次数将翻倍的原因。

在决赛前保留了几天。 尽管由于良好的控球能力，我的策略开始减少进球数，但我并没有开始得分更高。 因此，我必须在不久后为对手的进球激励她。 进球得分越快，比率越高。 而且，该系数正在极大地增长，以便超过其余的得分，并且不用担心势场，例如，在得分之前只剩下10个滴答声时。

添加了敌人向哪里发送硝基的计算。 这是通过蛮力用一定步骤完成的。 同样，在没有任何威胁我进球的情况下，守门员开始补充硝基的储备。

第二个主要改进是使用minimax。 如果在构建静态轨迹时对敌人使用不同的撞击力会影响球的飞行，则在搜索过程中会考虑两个选项，即敌人的最大和最小撞击力，并采用最小值的估计值。

在决赛中，当机器人在地面上时，我有7种轨迹选择：

• 2个角没有跳；
• 2个角跳；
• 2个角度，具有跳跃和硝基同向速度；
• 2个角度，带有跳跃和硝基补偿重力；
• 1个角跳
• 1个角度，具有跳跃和硝基同向速度；
• 1个带跳角和硝基的角可补偿重力（由于错误而未使用，在撰写本文时会发现此现象）。

和机器人悬空时的两个选项：

• 硝基至球体表面上的随机点和随机冲击力；
• 随机冲击力。

决赛前几个小时有比赛，但是我的策略显然更好。 看来一切都已完成，我睡了一天都没有超过一天，没有任何东西可以依靠我。 它留待观察。 决赛前两个小时，安德烈（Andrei）发出了新鲜出炉的圣杯，并成功获得了第一名。 他的参与历史可以在以下位置找到： habr.com/en/post/440398 。

在决赛的各个阶段之间，我添加了一个潜在的领域，将球推离我的进球，无论其他因素如何，这在我看来与安德烈（Andrei）相当。 但是已经很晚了，因为上半场我输了7分，下半场甚至3/3的胜利还不够。

RAIC是一项艰巨的比赛，奖品授予参与者非常非常困难。 当参与者坐在桌顶时，对他而言，这不仅仅是娱乐，而是一种挣扎。 编写强大的策略时，需要考虑很多小事情。 做出的每个决定都会严重影响结果。

该策略的源代码将在此处提供 。