EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games

Alistair Benford, Per Kristian Lehre

Algorithmica · 2026-06 · 88 (3)

DOI: 10.1007/s00453-026-01397-1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 04.06.2026. Verfasst von Alistair Benford und 1 weiteren Autor:innen. Beteiligte Einrichtung: School of Informatics, University of Edinburgh, Edinburgh, UK. Die Arbeit nennt 78 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Engineering and Physical Sciences Research Council.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Due to their complex dynamics, combinatorial games are a key test case and application for algorithms that train game playing agents. Among those algorithms that train using self-play are coevolutionary algorithms (CoEAs). However, the successful application of CoEAs for game playing is difficult due to pathological behaviours such as cycling, an issue especially critical for games with intransitive payoff landscapes. Insight into how to design CoEAs to avoid such behaviours can be provided by runtime analysis. In this paper, we push the scope of runtime analysis for CoEAs to combinatorial games, proving a general upper bound for the number of simulated games needed for a simple estimation of distribution algorithm to discover (with high probability) an optimal strategy. This result applies to any impartial combinatorial game, and for many games the implied bound is polynomial or quasipolynomial as a function of the number of game positions. After proving the main result, we provide several applications to simple well-known games: Nim, Chomp, Silver Dollar, and Turning Turtles. As the first runtime analysis for CoEAs on combinatorial games, this result is a critical step towards a comprehensive theoretical framework for coevolution.

Schlagwörter

Stichwörter der Autor:innen

CoevolutionCombinatorial gamesRuntime analysis

Autor:innen und Institutionen

  • School of Informatics, University of Edinburgh, Edinburgh, UK.
  • School of Computer Science, University of Birmingham, Birmingham, UK.

Förderung

  • Engineering and Physical Sciences Research Council

Zitieren

APA

Benford, A., & Lehre, P. K. (2026). A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games. Algorithmica, 88(3). https://doi.org/10.1007/s00453-026-01397-1

Vancouver

Benford A, Lehre PK. A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games. Algorithmica. 2026;88(3). doi:10.1007/s00453-026-01397-1

BibTeX
@article{Benford2026,
  author = {Benford, Alistair and Lehre, Per Kristian},
  title = {A General Upper Bound for the Runtime of a Coevolutionary Algorithm on Impartial Combinatorial Games},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {3},
  doi = {10.1007/s00453-026-01397-1}
}
Kostenlos starten →