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

Area of Science:

• Artificial Intelligence
• Game Theory
• Computational Complexity

Background:

• Combinatorial games present complex dynamics, serving as crucial test cases for game-playing agent training algorithms.
• Coevolutionary algorithms (CoEAs) that train using self-play are powerful but susceptible to pathological behaviors like cycling, especially in games with intransitive payoff landscapes.
• Runtime analysis offers insights into designing CoEAs to mitigate these issues.

Purpose of the Study:

• To extend the scope of runtime analysis to coevolutionary algorithms applied to combinatorial games.
• To provide a theoretical framework for understanding and improving CoEA performance in game playing.

Main Methods:

• Developed a general upper bound for the number of simulated games required by a simple estimation of distribution algorithm.
• The analysis focuses on discovering optimal strategies with high probability within impartial combinatorial games.
• Applied the theoretical results to analyze well-known games such as Nim, Chomp, Silver Dollar, and Turning Turtles.

Main Results:

• Proved a general upper bound for the runtime of a specific CoEA in discovering optimal strategies for impartial combinatorial games.
• The derived bounds are polynomial or quasipolynomial for many games, offering practical implications for algorithm design.
• This work represents the first runtime analysis of CoEAs specifically for combinatorial games.

Conclusions:

• The findings provide critical theoretical insights into the behavior of CoEAs in combinatorial games.
• This research is a foundational step towards a comprehensive theoretical framework for coevolutionary approaches in game AI.
• The established bounds can guide the development of more robust and efficient game-playing agents.