arXiv:2411.19744cs.LGcs.AI2024-11被引 13

人机协作优化竞赛编程,突破人类极限得分

Amplifying human performance in combinatorial competitive programming

  • 人类写基础启发式代码,AI优化评分函数
  • 在多个哈希编码赛中进入前1%并超越顶尖人类团队
  • 适用于需要高质量解的组合优化场景

近年来,复杂AI系统在编程竞赛中表现日益出色,但在Codeforces等主流平台的顶尖分数仍难企及。本文聚焦组合型竞赛编程,目标是在特定输入下寻找接近最优的解,而这类问题通常计算上难以处理。我们提出一种人机协同新范式:人类程序员编写启发式算法框架,随后利用FunSearch进化评分函数以优化性能。该方法在历届Hash Code全球团队编程竞赛中应用,显著提升原始得分,成功进入所有线上初赛的前百分之一,并在多轮比赛中超越顶级人类队伍。此外,在一次未公开的AtCoder优化题中也表现出色。

原文摘要 · Abstract (English)

Recent years have seen a significant surge in complex AI systems for competitive programming, capable of performing at admirable levels against human competitors. While steady progress has been made, the highest percentiles still remain out of reach for these methods on standard competition platforms such as Codeforces. Here we instead focus on combinatorial competitive programming, where the target is to find as-good-as-possible solutions to otherwise computationally intractable problems, over specific given inputs. We hypothesise that this scenario offers a unique testbed for human-AI synergy, as human programmers can write a backbone of a heuristic solution, after which AI can be used to optimise the scoring function used by the heuristic. We deploy our approach on previous iterations of Hash Code, a global team programming competition inspired by NP-hard software engineering problems at Google, and we leverage FunSearch to evolve our scoring functions. Our evolved solutions significantly improve the attained scores from their baseline, successfully breaking into the top percentile on all previous Hash Code online qualification rounds, and outperforming the top human teams on several. Our method is also performant on an optimisation problem that featured in a recent held-out AtCoder contest.

人机协作组合优化竞赛编程进化算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。