我叫伊戈尔·沃尔科夫（Igor Volkov）。 我在一家咨询公司工作，担任Java开发人员，架构师，团队负责人，技术经理。 根据项目的当前需求，可以扮演不同的角色。 长期以来，他一直吸引来自mail.ru的竞赛，但事实证明，该竞赛仅在Paper IO上积极参与。
这次，组织者提议根据流行游戏实施机器人管理策略。 在此处阅读有关规则的更多信息。 我的策略代码可以在这里找到，以及锦标赛网站上的游戏示例。
在我看来，比赛一开始，最常见的弹出式实现想法是使用MCTS 。 因此，我花了一些时间尝试这种算法。 从来没有想过如何有效地使用它来解决问题，所以我决定首先生成许多矩形路线（先进行两次，再进行三转），然后进行后续评估。
策略算法
该策略的高级算法可以由以下6点表示：
- 阅读世界状况
- 将消息对象转换为工作对象
- 形成一组矩形路线
- 为每个生成的路线评分
- 选择最佳路线
- 派队
该算法在比赛期间没有改变。 仅修改了机器人路径的形成方法及其评估。
SimpleStrategy类包含策略的初始版本，而BestStrategy类是改进版本，在竞争中排名第二。
阅读世界状况
世界的状态通过STDIN作为JSON对象传输。 我在pom.xml中看到可以使用Gson库，并且读取世界状况的任务已大大简化。 使用Gson库，将从标准输入流中读取的JSON字符串反序列化为Message类的实例。 该代码在Main.java中（第44-49行） 。
创建工作对象
在主程序代码中使用传输对象通常不是很方便并且在结构上是错误的。 例如，组织者出于某种原因可以更改邮件的格式。 因此，有必要将运输对象转换为工作人员，这将在主程序代码中使用。 Player和PlayerState类保留机器人的状态，而实用程序类MessagePlayer2PlayerConverter则根据传输消息中的数据来帮助创建这些类。 Bonus类包含有关游戏环境中单元格的奖励的信息。 用于创建工作对象的代码位于Main.java中（第61-74行） 。
在该策略的第一个版本（ SimpleStrategy ）中，使用MovePlanWithScore和Move类设置路径。 Move设置了移动的方向以及机器人应沿该方向移动多少个单元格， MovePlanWithScore包含由Move数组指定的路线以及该路线的估计值。 一个数组可以包含一到四个Move对象。 尽管只考虑了不超过三匝的矩形路线，但实际上机器人的路线是以虚线的形式获得的。 这是通过在每个转弯处选择新的最佳矩形路线来实现的。 实现为嵌套循环的路由生成功能从MovePlanWithScore形成列表以进行进一步评估。
就后续评估的执行而言，这种机器人轨迹的形成不是很有效，因为有必要多次计算相同的轨迹，但是对于理解游戏的机制非常有用。
在该策略的更高版本中， BestStrategy开始使用路由树。 MoveNode类反映此树的节点。 该树在策略开始时就完全形成了。 注意MoveNode类的init方法。 这与从SimpleStrategy类生成路由非常相似。 从根本上讲，所讨论的路由与第一个版本没有太大不同。
我认为，可以通过增加另一种方式来进一步改善路线的形成。 但是没有足够的时间进行优化。
路线等级
无论机器人位于何处，总是会为他选择以其领土为终点的最佳路线。 为了评估路线，我引入了两个指标：得分和风险。 分数-大致反映路径的每个刻度线所得分的点数，风险-不足以完成路径的刻度线数（例如，由于对手可以抓住尾巴的事实）。 风险并未立即显现。 在第一个版本中，如果漫游器突然在路径中间发现它没有时间完成路径，则它“发疯了”，因为所有危险路径都同样有害。 在所有考虑的路径中，选择最“安全”的路径，并以该路径的每个刻度线的最大点数为准。
为了评估路线的安全性，我计算了可达性矩阵：对于运动场的每个单元，我都会找到一个勾号，对手的机器人可以在该勾号上出现。 首先，只有一个刻度，然后添加了一条尾巴长度计算。 该策略的第一个版本中也没有考虑到可以沿途获得的奖金。 TimeMatrixBuilder类计算竞争对手机器人的刻度和尾巴长度矩阵。 然后将这些矩阵用于评估风险。 如果我的机器人在计算下一步动作时处于其领土上-将最大风险级别分配给危险路线，如果该机器人已经在异国或中立领土上，则该风险被评估为路径完成时（机器人到达其领土）的滴答声与可以完成时的滴答声之间的差威胁危险（例如，其他人的机器人可以踩到尾巴）。
在该策略的第一个版本中，仅根据所占领的领土来考虑得分，并且略微考虑了奖金。 为了找到捕获的单元格，我使用了递归算法 。 许多参赛者抱怨Local Runner组织者使用的算法的怪异和计算复杂性。 我将假定这样做是有意进行的，以便不为比赛的参与者提供现成的解决方案。
奇怪，但尽管该策略的第一个版本很原始，但它表现得很好：在沙箱中排名第十。 没错，在预赛中他开始迅速失败：其他参与者改进了他们的策略。
我的机器人经常死亡。 首先，由于正在建立通往竞争对手机器人捕获的领土的路线。 路径意外延长，我的机器人被尾巴抓住了。 通常是由于对尾巴的长度和对手的机器人的速度的预测不正确而死亡。 例如，对手的机器人慢下来是危险的，因为在近似计算中，该策略假定他应该已经离开了牢房，并且仍然在那儿。 为了解决这些问题，我开始为运动场的每个单元格计算大量指标（类AnalyticsBuilder和CellDetails ）。
计算运动场的细胞
- 对手的机器人可以占据笼子的刻度线（尾部的刻度线）
- 勾选对手的机器人可以进入该单元的位置
- 进入笼子时的尾巴长度
- 勾号，对手的机器人可以退出笼子
- 离开笼子时的尾巴长度
- 勾选，可以被对手的机器人捕获细胞
- 选中该单元格可能是捕获区域的目标
- 可以用锯子敲打电池的刻度
分析的深度仅限于10个动作。 我认为可以通过拒绝计算单个竞争对手或引入浮动深度来获得更大的深度，但是没有足够的时间进行优化。 除了AnalyticsBuilder之外，如果AnalyticsBuilder的呈现深度不足，他便开始使用SimpleTickMatrixBuilder 。 BestStrategy使用分析结果。
评分功能也有所改善：
- 我开始考虑奖金：获得减速奖金的罚款以及获得加速和看到奖金的奖金。 结果，该机器人开始成功地避免了不良奖励，并在此过程中获得了良好的奖励。
- 他开始考虑元首的冲突。 为胜利冲突增加了一些要点。 可能发生的碰撞越远，得分就越少。
- 为了减少环境的可能性，他添加了一些要点来获取对手的边界格。
- 减少边界处空单元格的值：离中心越远，值越低。 看着总决赛的战斗，我得出的结论是，对于捕获一个空单元这一事实，根本不需要累积积分。 空单元格的值应取决于敌方单元大群集的接近程度。 不幸的是，最终无法编辑策略。
- 增加了围绕对手机器人头部的点数。 不知道这是否有所帮助。 也许采用最简单的策略。
- 他甚至为徒劳地抓住尾巴而添加了分数（对手的机器人在我的机器人踩到尾巴的那一刻就设法捕获了领土）。 我绝对不确定，但是我认为这会阻止对手的机器人抢占别人的领土，而他们通常不得不返回自己的领土。
- 如果发现被俘的可能死亡，将大大增加对手领土边界牢房的成本。
策略调试
该策略的第一个版本包含大量错别字和错误：显然是夜间编程的结果。 例如，在Cell类中，索引被错误地考虑： this.index = x * Game.sizeY + y this.index = x * Game.width + y 。 最初，我试图仅依靠测试，但是我的直觉表明，如果不进行可视化处理且不玩以前玩过的比赛，将很难在代码中发现错误并分析做出错误决定的原因。 结果， 出现了DebugWindow可视化工具，您可以在其中逐步查看以前玩过的游戏，以及在所需的刻度上开始调试。 代码不是很漂亮，草率编写，但是在调试时对我有很大帮助。 例如，由于单元格索引的计算不正确，立即检测到错误。 许多参赛者在控制台中显示了调试信息，但是在我看来这还不够。
最佳化
为了不浪费时间创建对象和运行GC，我尝试提前创建一些对象。 这些是运动场中的单元（ 单元类）。 另外，为每个小区标识邻居。 预先创建了可能路径的树（ MoveNode类）。
我认为必须模拟许多场景，并且在此过程中，当前状态会恶化，并且每次都必须恢复。 因此，为了保护世界的状况，我尝试使用尽可能多的打包结构。 存储占用的领土-BitSet （ PlayerTerritory类）。 比赛场地的每个单元格都有编号，并且单元格编号对应于BitSet中的位数。 为了存储尾巴，我将BitSet与ArrayDeque（类PlayerTail ）一起使用。
没错，由于时间不足，我没有玩各种场景。 由于计算路径的主要功能是递归的，并且整个状态都可以存储在堆栈中，所以最新的优化对我来说不是很有用。
未实现的想法
在评估机器人路径的风险时，我独立考虑了每个对手。 实际上，每个竞争对手都不敢死。 因此，值得在风险评估中考虑这一点。 至少，在最后一场比赛中绝对必须考虑到这一点。
考虑到对手未来的死亡。 有时，机器人捕获了对手的领土，而对手意外死亡。 很遗憾，因为这样一来，您只能捕获空单元格。
考虑将在不久的将来捕获的空单元格作为评估功能。
建议和感谢
我建议所有开发人员积极参加AI Cups竞赛。 这会发展思维，并有助于在游戏中学习新算法。 正如我的经验所表明的那样，只要有一点热情就可以占据奖杯的位置，即使是简单但不是很理想的代码也可以带来结果。
非常感谢组织者。 尽管存在一些技术问题，但比赛仍很有趣。 我期待下一个！