第11名方案(NN+MCTS)

恭喜获奖者。感谢团队成员 ( @iiyamaiiyama @kibuna ) 以及 Kaggle 团队举办了一场精彩的比赛。
我们的解决方案结合了神经网络 (NN) 和搜索策略 (MCTS)。我将详细分享我们的解决方案。

摘要

• 模型 + MCTS

模型

我们使用了3个阶段的训练。

1. 使用分数在1230以上的数据进行模仿学习。
2. 微调 HandyRL（自我对弈训练）。
3. 再次使用分数在1230以上的数据进行模仿学习（重训练）。

训练参数

• 模型架构：ResNeSt
• 优化器：SAM(Adam)
• 特征
  • 每个玩家的头/尾/身体。
  • t-1, t+1, t+2 时刻的尾巴位置
  • 食物位置
  • 到食物的距离
• 数据增强
  • 玩家打乱增强
    • 索引1-3被打乱，索引0是自己的玩家，不能被打乱。
  • 水平/垂直翻转

推理速度

使用 Torch Script 编译训练好的模型以加速推理，但模型量化比原始模型更慢。

MCTS

使用解耦 UCT(UCB1) 的蒙特卡洛树搜索

• UCB1
  我们使用了带有 UCB1 的简单解耦 UCT。在典型的 MCTS 中，模拟会一直进行直到游戏结束，但我们将其限制在最多10步。这是因为模拟直到游戏结束非常耗时，而且随机因素太大，无法正确评估。
  我们不像 AlphaZero 那样在 MCTS 期间运行 CNN。那也非常耗时。

• 奖励
  如果游戏结束，很容易计算用于 UCB 的奖励。然而，如上所述，许多模拟在游戏中间就终止了。因此，我们决定按以下方式给予奖励：
  

  • 如果游戏结束：根据最终排名给予分数。（例如 第1名=1.0, ..., 第4名=0.0）
  • 如果游戏未结束：
    • 如果智能体死亡：给予 0
    • 否则：
      • 如果其他一个或两个智能体死亡：给予 0.7
      • 否则：给予 0.5
  • 杂项奖励：
    吃到食物：+0.01
    追逐自己的尾巴：+ 0.002（每回合）

• 模拟期间的 Crazy-Move
  模拟的质量在 MCTS 中是非常重要的因素，模拟中的随机移动不会产生正确的结果。
  当然，随着模拟次数的增加，UCB值预计会逐渐收敛到最优移动。但是博弈树的终端节点没有足够的模拟机会。因此，当 MCTS 访问一个它以前从未见过的棋盘状态时，它根据 crazy-goose agent 选择移动。
  当棋盘状态被第二次或之后访问时，MCTS 根据 UCB1 选择移动。

• 反公开智能体
  LB（排行榜）上有许多公开内核克隆（复制）智能体。只要它是确定性工作的，就很容易发现它是否是克隆。如果我们知道它是克隆智能体，我们可以100%预测智能体的下一步移动并加以利用。
  然而，由于1秒的时间限制，不可能推断模拟期间访问的每个棋盘的克隆智能体的移动。
  因此，我们仅在 MCTS 开始的第一个棋盘（根节点）预测克隆智能体的移动。
  虽然在白银-黄金区域很少有克隆智能体，但利用它们可以稳定提交后前10场比赛的胜率。这加速了 LB 的收敛，使我们更容易选择更强的智能体。
  此外，我们预计在最终评估周，我们会匹配到那些因为 sigma 增加而碰巧赢得很多比赛的克隆智能体。但是，这次比赛中 sigma 的增加非常轻微，所以这方面的贡献很小。

• C++ 实现
  我们