玩转系统：解谜玩家能教我们如何解决难题吗？

文献标题

Playing the System: Can Puzzle Players Teach us How to Solve Hard Problems?

文献信息

• 主题领域: 游戏化科学与多序列比对 (Multiple Sequence Alignment, MSA)
• 关键词: 多序列比对, 视频游戏, 行为克隆, 强化学习, 转换器模型, 全卷积网络

研究背景与问题

• 发现的问题或挑战:

  • 游戏化科学游戏（Science Discovery Games, SDGs）可以借助玩家解决复杂的科学问题。然而，如何将玩家的解题经验用到经典计算难题如 NP-hard 问题中一直是难点。
  • 多序列比对 (MSA) 是一种生物信息学中的典型 NP-hard 问题，涉及复杂的序列排列和优化，没有现成的最佳方案，且传统算法受参数敏感性和效率限制。
  • 人类可以通过直觉解决某些计算问题，但缺乏对这些直觉背后策略的深入结构化研究。

• 研究重要性:

  • 多序列比对广泛用于生物学、医学等领域，其优化解法具有重要的科学价值。
  • 探索玩家如何通过解谜游戏（如 Borderlands Science）贡献于科学问题，可以为生物信息学建模方法提供全新视角。

• 研究动机与相关工作:

  • 先前的类似项目如 Phylo 显示人类玩家能够改进一些计算生成的多序列比对，但玩家群体的战略仍缺乏深入挖掘。
  • 强化学习 (Reinforcement Learning, RL) 和行为克隆 (Behavioral Cloning, BC) 等技术展示了从人类决策中提取有效策略的潜力，这也是本研究的重要基石。

解决方案

• 提出的方法或解决方案:

  • 通过游戏 Borderlands Science 收集数百万玩家的解密数据，并提炼这些数据以理解人类解决多序列比对问题的策略。
  • 使用机器学习（ML）框架，包括全卷积网络 (Fully Convolutional Network, FCN) 和基于转移学习的 Transformers 模型，从玩家解题数据中学习有效策略。
  • 提出三个关键假设 (H1, H2, H3)：
    1. 玩家使用的策略并非简单的启发式规则。
    2. 人类解的性能至少与标准 MSA 算法媲美。
    3. 玩家策略可以通过行为克隆实现高效模仿。

• 创新之处:

  • 与传统优化算法相比，利用玩家在解谜时的直觉和集体策略来实现序列比对。
  • 创建了一个可扩展的基于玩家数据的学习框架，并展示了该框架在构建高效 MSA 算法中的潜力。
  • 成功训练出行为克隆代理模型，其解题性能接近或优于玩家。

• 实施步骤与关键技术:

  1. 数据收集与过滤: 从 Borderlands Science 收集玩家解法，构建游戏内的“Pareto 前沿”用作标杆，用于识别接近最优方案的玩家解决方案。
  2. 多序列比对定义与算法比较:
     • 比较主流 MSA 方法（如 Needleman-Wunsch, PASTA, HMMER）与玩家方案的异同，采用多种尺度进行评估，包括相似度计算（Cosine 相似度、Hamming 距离）。
  3. 机器学习框架搭建:
     • 分别实现图像到图像 (image2image) 任务和序列到序列 (seq2seq) 任务的模型，根据 FCN 和 Transformers 的框架设计网络。
  4. 评估与对比:
     • 使用多种指标衡量模型解决方案与玩家解方案的距离，确保机器学习模型尽可能模仿玩家策略。

研究成果

• 具体成果:

  • 玩家策略（尤其是博弈解）与简单算法（如 Greedy 算法）相比，明显更复杂且更高效。
  • 尽管 Needleman-Wunsch 算法在小规模问题上优于玩家，在更复杂问题上玩家表现更佳。
  • 基于 Transformer 的模型更精准地模仿了玩家策略，实现了较高的解决方案质量。
  • 从玩家数据和模型解中提取了一种“缺口效率”的策略（gap-efficient strategy），对多序列比对有重要意义。

• 与现有解决方案的比较优势:

  • 玩家解法在更高复杂度任务上超越传统算法，如 Needleman-Wunsch 和 PASTA。
  • 模型学习的解法在部分场景下能生成比玩家解更高效的对齐策略，尤其在减少不必要缺口方面。
  • 对于无法明确定义奖励函数的复杂问题，行为克隆提供了鲁棒性解决方案。

• 实验与评估结果:

  • FCN 和 Transform 网络在多种评估指标（如 Cosine 相似度, Hamming 距离）上均表现出与玩家解法的高一致性。
  • Transformer 基于 seq2seq 任务配置，在评估中稍胜一筹。

• 局限性与未来方向:

  • 本研究主要聚焦微生物序列的多序列比对，尚未验证对于其他类型数据的泛化性。
  • 玩家游戏行为可能存在某些限制作答行为的偏差，未来需对这些交互模式进行更多控制或优化。
  • 未来研究可以进一步提升基于玩家策略的模型对其它 NP-hard 问题的适应能力，或者探索与强化学习、逆向强化学习的模型结合。