是星期三，有一次普通的无聊会议在工作。 设计师在他的耳朵后方挠了一下，测试人员将自己埋在电话里。 车窗外开了车，我接到电话信-
2018年俄罗斯AI杯开始了。 几乎没有人怀疑任何事情，那时我已经完全知道下一个半月我会做什么。
大家好，我叫
Andrey Tokarev ，我想分享我参加
2018年俄罗斯AI杯的经历。
这是什么
俄罗斯AI杯是自2012年以来每年举行的一次人工智能竞赛。 在这里，您需要编写一种控制某人或某物的算法，这些人或某物彼此竞争。 今年，有必要控制踢足球的机器人。
我已经有参加此类比赛的经验。 特别是，我参加了2016年俄罗斯AI杯（无奖）和2018年Mini AI杯（第2名）。
走吧
首先，我创建了游戏世界的类，对象，并从过去的比赛中提取了二维和三维矢量，并将其全部上传到Git存储库。 当然，您可以使用语言包中的对象，但是没有矢量，无法修改它们，并且使用自己的类确实更加方便。 我没有重写的是竞技场类，它很适合我，因此无需更改。
模拟
在这里，我们有一个游戏世界，我们该怎么办？
但这没有任何结果，直到我们可以模拟游戏世界，甚至无法确定球是否飞入空网。 因此，我们正在注销模拟。 模拟代码不是语言包的一部分，它以我不知道的语言提供。 但是它的C语法相似，因此复制粘贴+定义必要的功能，并且sim卡已经准备好90％。 在需要统治我的手的地方，我尝试仔细地做这件事，因为那样的话，错误可能会很昂贵，而抓住它们却不容易。 我仍然犯了一些错误，但这花了我一点血。
立刻变得很清楚，如果您使用诚实模拟（100个微滴答），那还不够，与一个100个微滴答的期权相比，用一个微滴答计算100个期权的利润要高得多。 我仍然留下2个微透镜，这样差异不会太大。
策略基础
这样我们就有了一个游戏世界，我们可以模拟它的变化。 那接下来呢？
有不同的方法。 当可能的动作很少并且深度不是很大时，您可以用蛮力进行：对所有动作进行排序，甚至对手的回程动作，他们也有自己的动作…… 极小值 例如，当有很多移动时，您可以人为地限制它们，您可以采取15度倍数的方向，每10个跳动跳一次，并使用相同的minimax。 但是，在结果对动作的微小变化不太敏感的情况下，这种方法对我来说似乎是合适的，此处在机器人方向上的一度偏差将导致碰撞后的大偏差。
当我们在没有详尽搜索的情况下采取行动时，另一个极端是某种启发。 这种方法可能是可行的，但要创建具有纯粹试探法的强大足球运动员非常困难。
但是，两种方法的组合看起来很有希望：您可以先向随机方向移动，然后以启发式方法完成游戏，该方法可以跑到球上并在正确的时间跳动。 相同的启发式组合可以用来预测对手的移动。 早些时候，我已经在比赛中使用了类似的方法，这种方法或多或少并没有被证明是不好的。
因此，我们编写了启发式算法（使用RAIK-ovsky术语聪明的人，或者只是聪明的人）！
由于我想尽快看到结果，因此smartgay匆忙编写，结果却显得很愚蠢（即使代码很可耻）。 我只是根据球的当前速度和机器人的最大速度计算了机器人抓到球的时间，然后跑到那个时候球将要碰到的点（不考虑碰撞）。 他不知道如何跳球，甚至不考虑球的高度，他很容易在球下奔跑，如果球移得太快，他通常会朝相反的方向奔跑。 由于聪明人无法跳球，因此我首先让他在距球一定距离处跳球，然后过一会儿就选择跳球时刻，这是随机的！ 事实证明，缺乏合理的跳伞选择是一个很大的缺点，但稍后会更多。 但是总的来说，一个干净的聪明人看上去并不坏，尽管他们自己也有进球，但有时甚至可以进球。
接下来，我们需要一个评估函数（OF）。
初始OF如下所示：（1000-滴答）*球门+ ball.z +机器人和球的相对位置的某些功能，即使它无法到达球，它也可以运行到球上。 在此，目标可以是-1,0,1，具体取决于是否存在目标以及目标对象，而“ tick”是从发生目标的模拟开始的滴答声。 最后是机器人不会不断推迟目标。
现在，我们使机器人在随机方向上运行随机的滴答声，然后将控制权转移到智能球，后者将其引导到球上，并在随机时刻跳跃并
击中未
击中的球 。 而且，最好不要跑到球的中心，而是随机移动一小段距离，以便机器人可以以一定角度击球。
模拟持续了2秒的固定时间，最后调用了OF。 每个机器人都会重复进行多次这种情况，并根据等级选择最佳方案。
到目前为止，该策略有一个严重的缺点：它没有内存-一切都是在每个刻度上从头开始计算的，这意味着该策略可以在一个刻度上看到目标，而在下一个刻度上找不到目标。 并非如此，您需要对其进行修复-我们保存为每个机器人找到的最佳选项，并在下一个刻度中重新使用它。 同样，现在机器人也了解彼此的事务，例如，如果第一个机器人要击球，那么第二个机器人就不会追球，而是尝试传球。
守门员
我们需要一个守门员。 我的守门员与攻击者基本不同，在于当球接近球门一定距离时它才启动，否则它将简单地返回其基点。
总结
现在，我们有一个很好的基本策略，可以执行所有必要的事情，并且可以在将来建立。
也许上面描述的所有内容看起来都很简单和合乎逻辑，但是老实说，在比赛开始时，并没有清晰地看到该策略接近尾声的情况，实施此过程花费了两周时间，占比赛的1/3。
关于测试的一点
随着时间的流逝，使游戏能力加倍的Grails将会越来越少地出现，我们必须选择能够使目标增加10-20％的变化。 然后事实证明，如此小的收益并不是那么容易识别。 为了获得全面的结果，您需要打入数百个进球，而每分钟一次的目标频率是很多小时的比赛时间。 因此，我几乎没有在服务器上测试策略，而是对以前的版本进行了长时间的本地测试。 但是，即使本地测试任何更改半天也不会很方便。 因此，我应用了一些“技巧”-测试了删节策略。 例如，如果在服务器上，每个机器人我选择了50多个选项，然后在本地仅选择了10个，那么这允许我在可容忍的时间内运行测试。
增强功能
接下来，我将以以下形式描述主要的改进及其评估：新版本的目标得分要比旧版本高出多少百分比。 即 例如，如果一个新人以120：100的成绩击败旧人，则得分为+ 20％，如果得分是2倍，则得分为+ 100％。
-您的门将必须击败目标。 如果他没有成功，请给他更多时间，将选项数量增加到x10。 + 15％
-有时，当守门员将球击中时，他会自由飞行，而他有时间返回自己的位置时，他们已经进球。 击球后，我们立即尝试将其放回原处，并以较小的负系数将其返回的价格变动添加到评估中。 + 20％
-在对方球门前再踢一球会增加球门的机会，为此，我们将在OF中给予加分。 + 60％
-尝试硝基！ 距离第一轮比赛还有几天，但我决定提前测试硝基。 凭直觉，在我看来，硝基会极大地影响游戏玩法，因为在一辆坦克上，您可以跳到天花板上或飞越整个领域。 首先，我教过如何仅对攻击者使用硝基，甚至在空中也只能对硝基使用，但是我还没有收集到这些软件包。 在飞行过程中，现在沿现在随机的3维方向使用了硝基。 坦率地说，结果是，我的压缩力不超过20％，并且在地面上使用硝基并没有带来任何效果。 因此暂时解决了硝基问题，尽管从这一刻起我尝试在硝基打开的情况下进行测试。
-太多随机性！ 随机是一件好事，当然，他有时会给出您甚至无法想到的技巧，但另一方面，当他太多时，一切都会重合的可能性很小。 我受够了。 我决定尝试将跳跃的瞬间转移到分析基础上。 由于空气中没有水平加速度（忘记硝基），因此很容易计算机器人和球相遇的力矩（t1）以及该时刻的球高（h1）。 现在，我们计算出时间（t2），之后机器人将处于h1的高度，现在跳转。 在这里我们得到一个二次方程，如果它没有解或t2 <t1，则提早跳动，否则跳。
结果让我有些震惊，将正确的跳向前锋和守门员都拧了一下，测试显示为+ 200％，即 新版本的目标击败了旧版本3次，真正的Grail！ 是在1月17日，将策略上传到服务器后，它在20场连胜中赢得了200多个评分，并在沙盒中领先了一段时间。
-我们教守门员比赛。 在我的门将被激活之前，他像支柱一样站立。 轻松的人行道：x = ball.x / 4略有增加。
-不能预测对手，而应该假设对手！ 在比赛中，我注意到在守门员将球击中对手后，我经常得到一个进球，而他在飞行中为我进球。 要绕过对手击球，首先需要确定他在第n个勾上的位置。 当然，我们不会考虑硝基。 我仍然可以解析地确定机器人的速度，似乎有两个圆的交点。 但是他无法应付这个容易接近的领域。 好吧，和他在一起，我们是程序员（不是受过教育），让机器为我们服务。 将平面划分为n个方向，在每个方向上移动机器人，端点将是多边形的顶点，而顶点决定了范围。
如何使用？ 我加了一个勾号，使对手可以第一次触球，并且OF系数很高。 由于现在还没有具体的行动方案，而是考虑了一种针对对手的可触及范围的云，一旦敌人的机器人与地面接触，我便立即将其移除。
结果+ 40％。 此外，这种方法有两个明显的优势：第一个方法是移除敌方机器人，从而加快了仿真速度;反过来，这又使我们有可能对更多的选项进行分类;第二个方法，我们不必打扰对手的控制。 结论：获利！
-愚蠢的错误，但是没有错误。 官方模拟器中有两行：
if abs(ball.position.z) > arena.depth / 2 + ball.radius: goal_scored()
我不知道是谁，但是我却保持了abs（）函数的原样，但徒劳无功。 abs-line（）（不要与std :: abs（）混淆）采用整数值，这意味着小数点将被截断。 在实践中，这意味着我仅在球已经在球门线后方一米处才记录球门。 用fabs（）替换abs（）！ 这不是Abs（）第一次使我失败。
-硝基。 第二轮即将到来，没有地方推迟正常使用硝基。 他优化了它的用法，考虑了跳跃的定义，允许使用守门员，并且也开始由守门员故意收集包裹。
-让我们回到模拟。 我已经说过，一种带有microtik的100期权比一种带有100 microtic的期权更有利可图。 的确如此，但这并不意味着有了一个Mikrotik，一切都很好，如果不采取其他措施，差异会非常严重，这将阻止足球专业水平的发展。 为了提高模拟的准确性，我应用了以下方法：
- 在跳跃过程中，增加了两个Mikrotik。
- 当我们结合许多微技术时，在移动时使用平均速度而不是最终速度更为正确。
- 使用二进制搜索，我们找到发生碰撞的滴答声，然后执行两种子策略：一种在碰撞之前，另一种在碰撞之后。 （我没有考虑到球与平坦表面的碰撞，那里的差异对我来说似乎微不足道。）
- 沿着曲面运行仍然会导致较大的差异，有时守门员会因此而错过。 因此，当我的守门员在弯曲的表面上时，我使用了10个微镜。
平均而言，每个刻度获得约1.4个mikrotik，准确度接近理想水平。 当然，我不是一次搞砸这些优化，而是逐步解决。 我不知道他们对游戏的影响力有多大，但是我认为这非常重要。
我们有什么
由于大量的重大改进，该策略的排名稳步增长，在第二轮之前，它几乎达到了历史里程碑-5000 Elo评分，自信地名列第一。
有时，您甚至都不敢相信哪些组合会随机出现。 感谢善良的社区匿名提供的发现。上周
在获得如此高的利润的同时，我不允许自己追求小的改进，而是寻求更具全局性的东西，尤其是在3x3游戏方面。 然而，针对更多团队游戏的实验，或向第三位球员灌输特殊角色，或教导守门员在失败期间外出的实验均以失败告终。 整个星期几乎没有用。 尽管如此，距离决赛还有几天，我仍然在排名中处于领先地位。
而现在进入决赛的最后一天，我开始输给一个，然后是另一个，甚至是第三个竞争对手。 如果您不添加，则可以不加奖赏。 整周什么都没发生，最后一天该怎么办？ 心情是-至少放弃了。
复活
看了几场失败的比赛后，我注意到每个人都
像山羊一样跳上硝基，在空中传递球，但我的球却不能。 我尝试了可能导致这种行为的最简单方法-在撞击时我用OF中的固定系数增加了球的高度。 结果+ 50％，哇！ 受到结果的启发，我开始强烈地扭曲参数（我在整个比赛中都忽略了这一点），添加了新的搜索选项，最后增加了时间控制，这使我可以最大程度地利用时间而不会冒生命危险。 到一天结束时，结果变成+ 150-200％，即 新版本在目标上几乎击败了前一个版本！ 是的，是的，在决赛前将近一周的比赛中排名第一，并在锦标赛历史上达到了前所未有的5000+评分。 在服务器上，该策略已在最终测试之前的两个小时成功进行了测试。 之后，我为最终启动做好了准备：禁用断言，将除法检查添加为零，再次将其上传到服务器，然后将自己切换为待机模式。
最后一部分
决赛的第一部分在晚上举行。 我一直跟踪结果，直到睡着了，一大早起来。 进行了3次
挥杆 （每次演奏一波），我对阵
TonyK只输了一场比赛，由于安东有时仍然输给其他玩家，所以我以7分的优势领先（2分获胜）。 3个波的间隙相当严重，但不足以放松。
当然，在最后一天，我不打算做任何严肃的事情，基本上是在扭曲参数。 进行了几处更改，但是由于所有内容都经过匆忙测试，因此我什至不能完全确定效果是肯定的。 通常，增长为0-20％。 但是安东明显增加了，至少起了比我还差的表现。
什么也没做，我不得不寄出什么，希望运气和积分供应。
第二部分
幸运的是，对比赛进行了分类，以便起初领导者之间相互比赛，因此无需担心，第一场比赛是对阵TonyK。 运气在我的身边，我赢得了第一场比赛，也赢得了这一波中的所有其他比赛，而TonyK又失去了一点。 到最后两波之间的差距为10分几乎是不可能的，现在可以放松。
最终结果：352胜2负（均来自安东），以12分的优势排名第一。
谢谢和其他垃圾
总的来说，我真的很喜欢今年的任务，那是“对我来说”（模拟是我的，而且三维并不吓我），比赛非常壮观，我认为不仅观看参与者，还很有趣。
我要感谢组织者的精彩比赛。
我还要感谢所有参与者，特别是决赛选手的Anton Kozlovsky（
TonyK ），沙盒比赛的Ivan Tyamgin（
tyamgin ）和Alexey Dichkovsky（
Commandos ）避免参加比赛并因此增加了获胜的机会，我也要感谢他们。
在下一个RAIK中祝大家好运！