Games Between Programs: The Ruliology of Competition
3 days ago
- #Computational Competition
- #Ruliology
- #Game Theory
- Models of competition involve two agents repeatedly taking actions and receiving payoffs based on a game theory setup.
- Strategies are fixed procedures determining actions based on past sequences, and exploring all possible strategies using ruliological methods reveals complex behaviors.
- The match-or-not (matching pennies) game is used as a baseline, with payoffs favoring matches for one agent and mismatches for the other.
- Finite state machines (FSMs) are analyzed as strategies, with 2-state and 3-state machines competing to determine winners based on average mean payoffs.
- Competitions between FSMs of different sizes show that machines with more states can often outmaneuver simpler ones, but complexity does not always correlate with winning.
- Adaptive evolution of FSMs through mutations can converge on winning strategies, sometimes achieving universal success against all opponents of a certain size.
- The prisoner's dilemma game is examined, with strategies like 'grim trigger' outperforming others like 'tit-for-tat' in systematic evaluations.
- Cellular automaton strategies are introduced, where rules determine actions from opponent histories, with competitions showing both simple and complex behaviors.
- Turing machine strategies are explored, adding computational depth and highlighting issues like non-halting computations in competitive settings.
- Across all program types, computational irreducibility means outcomes often require simulation, and winning strategies may exploit pockets of reducibility.
- Historical context notes early game theory and later computational approaches, with personal insights from the author's work on ruliological investigations.