Games between Programs: The Ruliology of Competition—Stephen Wolfram Writings

Recent |

Categories

Artificial Intelligence<br>Big Picture<br>Biology<br>Companies & Business<br>Computational Science<br>Computational Thinking<br>Data Science<br>Education<br>Future Perspectives<br>Historical Perspectives<br>Language & Communication<br>Life & Times<br>Life Science<br>Mathematica<br>Mathematics<br>Multicomputation<br>New Kind of Science<br>New Technology<br>Personal Analytics<br>Philosophy<br>Physics<br>Ruliology<br>Software Design<br>Wolfram|Alpha<br>Wolfram Language<br>Other

&times;

Contents

Top

The Basic Setup

Strategies from Finite State Machines

The Space of Possible Finite State Machines

The Complexity of Winning

Competitions between Machines of Different Sizes

Adaptive Evolution of Finite State Machines

What About Prisoner’s Dilemma?

The Space of All Possible Games

Cellular Automaton Strategies

Cellular Automata vs. Finite State Machines

Adaptive Evolution of Cellular Automaton Strategies

Turing Machine Strategies

Discussion

Historical & Personal Notes

Thanks

Games between Programs: The Ruliology of Competition

Games between Programs: The Ruliology of Competition

June 4, 2026

The Basic Setup

Whether one’s dealing with biology, economics, politics or a host of other fields, it’s common to encounter situations that can be modeled as involving two agents that repeatedly compete with each other. One imagines that at each step each agent can take one of a certain set of actions, and that then—in a classic game theory way—each agent (or “player”) gets a certain fixed “payoff” based on the action they and their opponent take. But how do the agents decide what action to take? We imagine that each agent has a certain fixed procedure—or “strategy”—for making its decisions. And we imagine that the input to each of those decisions is the sequence of past actions that the agent and its opponent have taken.

There’s been lots of work done over the course of nearly a century on particular choices of strategies. But something I’ve long been curious about is what happens if one systematically considers all possible strategies. And if we think of strategies as programs this becomes a question to which we can immediately apply ruliological methods. Which is what I’m going to do here.

To be more specific about the setup, let’s assume that at each step, each agent takes one of two possible actions, indicated by and . And for now let’s take the payoffs to be the ones for the classic "match-or-not" ("matching pennies") game—in which player 1 has the bigger payoff when there’s a match, and player 2 has the bigger payoff when there isn’t a match:

So what happens when agents repeatedly play this game? Well, it depends on their strategies. Here are a few examples for several different choices of each agent’s strategy:

Plotting the cumulative payoffs for the two agents (represented by and ) in each of these cases we get:

Often we’ll consider the “winning agent” to be the one that has the numerically largest cumulative payoff (i.e. is eventually on top in these plots) after a certain number of steps. And with a criterion like this, we’ll be able to rank different programs against each other—and in general explore the ruliology of competition.

With the basic setup we’re using, we can represent all possible sequences of actions by a multiway graph:

For any given sequence of actions, there is then a cumulative payoff for each agent for our match-or-not game:

If each agent adopts a particular strategy, this will define a particular path through the multiway graph. For the strategies used in the examples above, the paths are:

What does it take to have a winning strategy? In what follows, we’ll consider strategies based on several different types of programs. But one basic question we can always ask is whether what turn out to be the winning strategies tend to be based on programs that are more complicated, or less so—or to show behavior that is more complicated, or less so.

In other words, if you want to win, should you typically be trying to build up something complicated? Or should you instead expect to be able to find a “simple hack” that will “crack the game” and—at least usually—let you win? In effect, we’re asking whether competition tends to lead to complexity, or simplicity.

I’ve recently looked at minimal models of both biological evolution and machine learning, in which one is adaptively evolving programs in order to maximize some externally imposed fitness function. And what I’ve found is that even when the fitness function one uses is simple, the behavior of the programs that maximize it is normally quite complex. In other words, adaptive evolution will tend to make even a simple, fixed objective be achieved in a complicated way.

So what if instead of having a fixed, externally imposed objective, our goal is just broadly to win against other agents? Does such—potentially open-ended—competition lead us to more complex behavior (or more complex programs), or not?...