Amplifying human performance in combinatorial competitive programming
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917852104097792 |
|---|---|
| author | Veličković, Petar Vitvitskyi, Alex Markeeva, Larisa Ibarz, Borja Buesing, Lars Balog, Matej Novikov, Alexander |
| author_facet | Veličković, Petar Vitvitskyi, Alex Markeeva, Larisa Ibarz, Borja Buesing, Lars Balog, Matej Novikov, Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Amplifying human performance in combinatorial competitive programming Veličković, Petar Vitvitskyi, Alex Markeeva, Larisa Ibarz, Borja Buesing, Lars Balog, Matej Novikov, Alexander Machine Learning Artificial Intelligence Neural and Evolutionary Computing Programming Languages 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. |
| title | Amplifying human performance in combinatorial competitive programming |
| topic | Machine Learning Artificial Intelligence Neural and Evolutionary Computing Programming Languages |
| url | https://arxiv.org/abs/2411.19744 |