在初秋时节，编写机器人迷你AI杯＃3 （aka Mad Cars）的比赛已经结束，参赛者必须在汽车上进行比赛。 与会者就什么将起作用，什么将不起作用进行了很多争论，从简单的if到训练神经网络都表达并测试了想法，但最高的位置是那些被称为“模拟”的家伙。 让我们尝试理解它的含义，比较第一，第三和第四名的解决方案，并讨论其他可能解决方案的主题。
免责声明
这篇文章是与Alexei Dichkovsky（Commandos）和Vladimir Kiselev（Valdemar）合作编写的。
对于那些只想了解获奖者决定的人，我建议您立即从“模拟”一词开始。
问题陈述
这次，世界的机制非常类似于Drive Ahead手机游戏：为玩家提供了一个带有按钮的汽车； 任务是比敌人更快地按下敌人的按钮。 如果没有人在600个游戏节拍中获胜，该卡就会开始陷入一堆垃圾中，也可以按下一个按钮。 换句话说，您需要保护按钮免受敌人，周围世界和大量垃圾的侵害（当然，是的）。 每位玩家有5条生命，游戏从5轮转为9轮，而有人没有结束生命。 每个回合都在随机地图和汽车上举行，两个参与者都一样。 总共有6种不同的卡和3种类型的汽车-共有18种不同的组合。
每个回合都被打断。 象棋一样，in是一招。 唯一的区别是两个玩家都同时走。 在有些比赛中，每个人都轮流参加，或者每隔几步就只能做一个动作，然后选择单位作为框架 。
机器人的每一个滴答声都会进入和平状态，并有机会执行3个动作：
更完整的规则可以在这里找到。 并在这里查看决赛。
通用解决方案说明
大多数机器人写作比赛都非常相似：滴答声是有限的（一个回合最多有1,500个），可能的动作是有限的，您需要选择一个动作序列以胜于对手。 稍后，我们将回到更好的意义上，但是现在，我们将弄清楚如何解决主要问题-众多选择：一开始我们只有一个初始状态，那么每台机器可以以三种不同的方式移动，给了我们两辆车的9种不同组合，到第1500步时，将是9 ^ 1500种不同组合...这比我们想要在宇宙存在期间设法设法将它们进行分类的结果要多。
这里我们来谈谈模拟是什么。 这不是某种算法，而只是具有足够或完全准确性的游戏规则的重新创建，以便可以对解决方案进行分类。 当然，我们不会仅解决部分解决方案。 搜索算法将用于此目的-在游戏状态树中，我们正在寻找最适合自己的。 有很多算法（从minimax到MCTS），每种算法都有自己的细微差别。 最好使自己熟悉过去AI竞赛的参赛者所做的决定。 这将提供对算法在什么条件下工作以及在哪些情况下不工作的基本了解。 在特殊的存储库中有许多与此相关的链接。
选择算法时，应考虑：
- 1滴答的时间限制（我今年错算了很多，但能够留在第三位）；
- 玩家人数。 例如，如果有三个玩家，将很难使用minimax；
- 仿真精度 这可能允许重用旧的计算；
- 状态树的“分支”（是否可以计算所有可能的状态至少向前移动10个）；
- 常识-如果比赛持续4个小时，请勿开始撰写MCTS。
在本次比赛中，1滴答答响了大约10-13毫秒（整个比赛2分钟）。 在这段时间内，机器人必须读取数据，做出决定并发送命令以进行移动。 这足以刺激大约500-1000次移动。 遍历所有状态。 最简单的搜索算法可能看起来像是三个运动选项的比较：“向左移动50个滴答声”，“向右移动50个滴答声”，“单击停止的50个滴答声”。 而且，无论听起来多么简单，离获胜者的决定都不远。
因为 我们只算出50步，这在大多数情况下直到比赛结束才算在内，那么我们需要一个评估函数来说明世界状况对我们的好坏。 大多数情况下，它建立在试探法上，并理解什么对胜利至关重要。 例如，在2014年俄罗斯AI杯比赛中有比赛，但是如果您获得最后的积分，您可以获得更多的积分，那么您就可以赢得比赛。 因此，评分功能应在沿高速公路快速移动的同时刺激点的收集。 只能针对模拟的最后状态（50个滴答声之后）或作为中间状态的估计值之和来计算分数。 通常，估计会随时间“消失”，以便更早地发生状态。 因为 我们不能肯定地预测敌人，那么未来的选择就不太可能发生，我们不会严重依赖他们。 同样，这种技术使机器人能够更快地完成其任务，并且不会推迟一切。 但是值得注意的是，该机器人为了以后的利益而将承担更少的风险。
由于我们将根据自己的行动预测世界状况，因此我们需要以某种方式对敌人的行为进行建模。 没有什么复杂的，有两种常见的选择：
- 存根或启发式
一种简单的行为逻辑被写成，敌人只是什么都不做，或者根据简单的试探法来选择行动（例如，您可以使用该策略的第一个版本，或者只是重复对手的先前举动）。 - 使用与自己相同的算法
首先，我们尝试为敌人找到最佳行动（针对最后一步中的最佳行动，或者针对存根），然后我们利用敌人发现的行为为自己寻找最佳行动。 在这里，机器人将尝试抵抗棘手的敌人。 在比赛开始时，这种逻辑无法很好地发挥作用，因为 许多机器人仍然非常虚弱，您对它们的决定将过于谨慎。 - 其他
相同的极小值可同时遍历玩家的所有举动，而他根本不需要启发法。
如果执行了上述所有步骤，则很可能会得到一个非常好的机器人，尤其是如果您可以选择一个好的评分功能。 但是，通过他的战斗，您会发现他在某些情况下的举止很奇怪。 在这些情况下，校正评估函数可能会很困难，否则很有可能破坏其他逻辑。 在这里拐杖和Ifs来营救。 是的，比赛的最后几天通常归结为拐杖和假设，以纠正任何特定条件下的缺陷。 就我个人而言，我真的不喜欢这部分，但我已经不止一次地注意到决赛中的拐杖会影响前十名中的位置排列，这意味着未成文的if可能会浪费您的奖金（当我写下这些话时，我的心会痛，我也喜欢漂亮的算法和解决方案）。
问：有可能根本不用仿真吗？
答：是的，您可以对启发式方法使用解决方案（决策树，大量ifs等）。 关于启发式的AI体系结构，有一篇很好的文章 。
问：模拟的使用要比启发式方法好多少？
答：这完全取决于任务。 例如，这里的一些纸牌和汽车组合可以用ifs进行硬编码，并始终获胜（或平局）。 但是，仿真通常会找到难以为自己考虑或难以实施启发式方法的解决方案。 在本次比赛中，当您翻转另一台机器时，模拟决策会将您的轮子放在敌人的轮子上，这会关闭“空中”的标志，这意味着敌人无法施加身体的旋转并重新转动轮子。 但是这个决定没有考虑到这个含义，它只是找到了让敌人更快落在屋顶上并按下他的按钮的选择。
问：神经网络和RL？
答：不管它有多受欢迎，在机器人竞赛中，这种解决方案都很少能很好地表现出来。 尽管神经网络不需要仿真，因为 他们只需根据当前状态的输入参数发出一个动作，他们仍然需要学习一些知识，为此，他们通常必须编写一个模拟器来在本地驱动数千个游戏。 我个人认为他们有潜力。 也许他们可以解决部分问题，或者在响应时间非常有限的情况下使用它。
注意事项
关于有限数量的可能动作，值得澄清的是，有时允许“平稳地”调整某些参数。 例如，不仅要前进，而且要有一定比例的动力。 在这种情况下，可以简单地通过使用多个值（例如0％，25％，50％，75％和100％）轻松得出结论数量的“有限性”。 通常，只有两个就足够了：“完全打开”和“完全关闭”。
模拟
在这场比赛中，我们使用了现成的花栗鼠物理引擎。 组织者的期望是，他很老，经过时间考验，并且有很多包装纸，这样每个人都可以将其包括在自己的决定中...
在严酷的现实中，引擎每次都会产生不同的值，这使得很难重新启动引擎以计算移动选项。 该问题已“直接解决”了-用C语言编写了一个内存分配器，并且完全复制了具有世界状态的内存。 这样的分配器结束了用非C ++语言编写解决方案的能力（事实上，这是可行的，但是非常费力，分配器仍必须用C编写）。 此外，预测的准确性还受向游戏世界添加元素的顺序的影响，这需要组织者用来计算游戏的代码的非常精确的副本。 但是他已经在使用Python。 其他编程语言的棺材中的最后一个亮点是，该引擎已经过时，并且包含许多无法在竞赛中准确地重新创建自己的物理模拟版本的优化。
结果，原本应该为所有参与者提供模拟运动的平等条件的引擎成为了最困难的障碍。 超过10个人能够克服这一挑战，排行榜上的前7名仅由进行精确模拟的家伙占据，这可以证明它在此类比赛中的重要性。
除了几个能够进入花栗鼠内部并优化复制其状态的参与者外，其余参与者都具有近似相同性能的模拟（这使比赛更加有趣，因为您知道这是为决策算法而奋斗，而不是“谁更看重移动”）。
搜索和预测对手的算法
从这一点开始，对解决方案进行单独描述。 算法将代表其作者进行描述。
弗拉基米尔·基谢列夫（瓦尔德马尔）第四名
使用随机搜索（蒙特卡洛）搜索解空间。 算法如下：
- 我们初始化基因组-60个滴答的动作序列（左，右，停止）-随机数据。
- 收集发现的最佳基因组
- 随机更改动作之一
- 使用评估函数，我们得到一个数字-指示新基因组的质量的指标
- 如果您有更好的解决方案，请更新最佳解决方案。
- 从步骤2再次重复
我的模拟器在1秒钟内对世界进行了约100k的模拟，考虑到平均每刻约12ms，我们每刻可得到1200次动作。 也就是说，在1个滴答声中，我们设法完成了整个周期约20次。
为了找到最佳解决方案，此迭代次数显然不够。 因此，实现了“伸展”动作的想法：代替60个动作的基因组，我们将使用12个“伸展”动作的链进行操作-我们相信每个动作连续持续5个滴答声。
加：通过减少基因组的长度来提高突变的质量，该模拟还可以每5个滴答运行一次，并检查100个基因组而不是20个基因组（以避免跌落时限，最终在70个点停止）。
更少：拉伸动作可能不会导致最佳解决方案（例如，在保险杠上摇摆，而不是稳定的机架）
应当指出，显着提高了算法质量的技术：
- 我们仅在第一个刻度上执行随机初始化，其余时间我们重复使用以1步偏移找到的最佳解决方案（第二个刻度上的动作移至第一个，依此类推，最后添加一个随机动作）。 这极大地提高了搜索的质量，因为否则该算法会“忘记”在最后一个滴答声中要执行的操作，并在不同方向产生无意义的抽搐。
- 在课程开始时，我们进行了更深入的更改（我们将基因组更改了2到3次而不是一次），希望突破局部最大值（模拟退火方法中的温度相似性）。
强度是手动选择的：前30次迭代进行3个突变，接下来的10次进行2次突变，然后进行1次突变。 - 预测敌人行动非常重要。 为了减少寻找自己解决方案的时间，我们使用了对手的最佳举动信息，从对手方进行了20次迭代，然后自己进行了50次随机搜索。
对手的最佳决定也将在偏移的情况下重新使用下一步。 同时，当寻找对敌人的解决方案时，最后一步的基因组被用作我的预期行动。
在比赛中，他积极使用了用于本地开发的工具，这使得可以快速发现错误并专注于该策略的弱点：
- 本地竞技场-与以前的版本进行了许多比赛；
- 用于调试行为的可视化工具；
- 一个脚本，用于从站点收集有关比赛的统计信息-使您能够了解失败最常发生在哪些地图和机器上。
mortido：
每5个滴答声计数一次是有风险的，尤其是当敌人远离您预测的选项时。 另一方面，在这个游戏世界中，只有5个滴答声，没有发生太多事情。
另外，在我的决定中，尽管如此，我还是在每个滴答声中添加了随机组合，但是我绝对不会说这对决定的影响。
突击队：
用如此大量的模拟来更改几个动作似乎没有什么意义，因为一个动作几乎没有发生任何变化。 但是，当您将一个动作扩展到5个滴答声时，它似乎会变得更多。
我也不太喜欢这个主意-我们会采用最佳组合，并在一开始尝试对其进行编辑。 改变第一个刻度线将使后续的刻度线至少相对足够似乎是不合逻辑的。
亚历山大·基谢列夫（mortido）第三名
有了其他竞赛优胜者的文章，我决定使用遗传算法。 然而，事实证明，这类似于随机搜索甚至是对退火的模仿，但后来更多。
我们用40个数字组成的数组对解决方案进行编码，其中-1、0和1对应于
在每个回合开始时，我计算了整场比赛已经花了多少时间，根据还剩下多少回合来计算新的时限，我假设每个回合为1200滴答。 T.O. 最初，我尝试每转花的时间不超过11毫秒，但是如果前一轮的速度快于1200滴答声，我可以在最后“四处走动”。
Valdemar：
有趣的是，这种筹码对我来说使比赛恶化了。 事实证明，总要花20-30毫秒比先花11毫秒，然后花60毫秒更好
在这段时间的三分之一中，我一直在寻找敌人的最佳行动，其余的则用于计算自己的决定。 在寻找敌人的举动时，我的行为被建模为从最后一招起的最佳行为，移动了1滴答。 即 好像我继续按照最后一刻制定的计划行事，而他正试图抵抗我。
本身和对手对解决方案本身的搜索都是相同的：
- 我们从最后一步开始做出决定，并将其移动1步（我们已经完成了）
- 我们向随机解决方案群体证明，直到我们将其全部填满为止
- 我们模拟所有决策并使用评估功能设置适用性。 我们记得最好的。
- 虽然有时间进行计算
- 提示，请始终向总体中添加当前最佳解决方案的1个变异，如果更好，请记住
- 只要新人口中有一个地方并且没有超过计算时间（您可以在人口稠密的楼层）
- 我们带两个不同的人，以最适合自己的身体离开-妈妈
- 我们带两个不同的人，以最适合自己的身体离开-爸爸（不应该和妈妈在一起）
- 越过他们
- 如果
RND < 则RND < - 我们模拟解决方案并记住它，如果它是最好的
结果，我们将返回被认为是最佳的动作序列。 它的第一步是作为机器人动作发送的。 不幸的是，我的计划存在严重缺陷，因为 可以在一秒钟内完成的模拟次数非常少（包括由于具有很长的评估功能），然后在竞赛服务器上仅进行了1次4分，而对敌人则完全没有进行。 这使算法更像是随机搜索或模拟退火（因为我们设法从最后一步开始对解决方案进行了1次变异）。 改变某些东西已经为时已晚，我们设法保持第三名。
重要的是实现用于交叉，变异和生成初始随机解的算法，因为 它取决于将要测试的决策，而完全随机的决策看起来并不像乍看起来那样好（它可以工作，但是需要更多选择）。
在最终版本中，细分市场中产生了随机决策，其中一处排除了“抽搐”解决方案：
- 随机选择球队
- 对于解决方案的整个长度（40个移动）
- 我们在单元格中写入当前命令
- 我们有10％的可能性将现有团队更改为随机
根据类似的技术，也发生了突变-解决方案的随机部分被替换为随机命令。 交叉是通过选择从1个父级到第二个父级的决策点来进行的。
我喜欢我们尽可能地利用所有时间来找到最佳解决方案。 如果解决方案不是最好的，那也没什么大不了的-我们可以在下一个步骤改进它，因为 优化结果在时间上“模糊”。 , . , - , . ,
Valdemar:
1 , , .
Commandos:
— - .
— , . , … , . " ”. -.
(Commandos) 1
( ), n m . 3^2=9 . m + n 40 .
:
|----------- n -----------|---------- m --------| | ... | ... |
: , , . ( ).
n m , . , .
:
- , ( , ):
- , , , .
- , , . . . , , , .
- . ; ( ).
- n m . , .1, , . - ( ) , — , ;
- . , — . , ( ).
Valdemar:
, 2 . . , .
mortido:
! , . . , 2 , 40-60 . , 3 .
n + m == const ?
. n + m != const , . , . - .
(Valdemar) 4
, . , ( , , ..) [0..1].
. : , .
, , : , .
, :
- — 70 180 ( : ).
, . - 0..500
- — [2pi, pi/4] [0, 1]
- — , ( ), ( , , )
- — , , , .
, , . - — . .
- Y — .
, 2 , .
.
:
mortido:
, .. , .
Commandos:
, . -
(mortido) 3
, chipmunk. . , , , , . .
3
, ( , , ):
- . , , ( , );
- , — , ; , 1 ;
- ;
- ( , );
- ( “+”, “-”);
- ( “+”, “-”); , , , ;
30 , , ( ); - , .
, , (, , )
Valdemar:
. , “ , , ” , ( ..) .
, , . .
Commandos:
, , “”… ? , “” .
(Commandos) 1
SquaredWheelsBuggy , .. , . Buggy , , ( /).
:
- ;
- ; — , , 1 0; .. ;
- . ; 10 ( );
- ( , );
- (, );
- — - , ;
- / ; , — ; .
1-5 , . 2 “ ”.
Valdemar:
, . , .
mortido:
, 10 .
IF'
(Valdemar) 4
, if'. 3 , , . , , -.
: , “” — , - , ( , ) — .
:
- . , .
- — , .
- . “ ” .
, , .
, , .
, : . , , if' .
mortido:
, . .
Commandos:
if'. , , … , , .
(mortido) 3
- .
3 . . . “”, . , , .
, “” . . , , , - . . , , .. .
, , , , , . … . - — , ( , ).
Valdemar:
, . . “” , if'. , — .
, + . , .
Commandos:
… , - — , , . , , .
(Commandos) 1
. (, , ). ( ) /.
pill carcass map , , ( ). island map, , .
island hole buggy. / , , ( ). — . , , . SquaredWheelBuggy . , , , . , … , , .
(Pill map, Bus) , ( / 100% ).
pill hubble map. , ( ), . .
— , ...
, . , . ( ).
Valdemar:
, — . , .
mortido:
, “” .
Valdemar:
. , . ( ) .
. “”, , , , :)
, mailru , .
mortido:
: , … , , ( ). , 3 , , … .
Commandos:
- , . , , , . … . — , .
— ++. . , . 1
, . , . , , .
Mail.Ru Group .
Valdemar
mortido