Matching pennies is a non-cooperative game studied in game theory. It is played between two players, Even and Odd. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously. If the pennies match (both heads or both tails), then Even wins and keeps both pennies. If the pennies do not match (one heads and one tails), then Odd wins and keeps both pennies.[0] This project looks into how introducing strategy to this usually basic game affects how we can analyze it.
Introduction
Introduction
Matching pennies is generally a non-cooperative (a game where the moves of the players are independent of each other), zero-sum game (a game where one player’s gain is offset by the other players loss) and is a classic example of game theory principles since each round is independent of the previous rounds. However, if we add strategy based on memory to it, it becomes a deterministic game. With the introduction of memory and strategy, we can look at how different methods of to determine the best one affects our findings - including adding randomness to the tournaments. During the game, two players play against each other. They each have two possible moves: red or green. Player 1 wins if both players play the same color, and follows their strategy exactly. Player two wins if both players play different colors, and follows the inverse of their strategy (if they would have played green in a situation, they will actually play red)
Interpretation of a graph, given a set of moves
Interpretation of a graph, given a set of moves
In[]:=
exampleGraph=EdgeTaggedGraph[{gg,gr,rg,rr},vertices,rc,EdgeStyle->{ggr,grg,rgg,rrr}]
Out[]=
The game is represented by a set of length four (or less), which consists of the colors green and red and is predetermined by the opponent' s strategy. The "starting position" or first move is shown by the larger vertex in the graph. For every round, go from the starting position and follow the edges which correspond to the colors in the set in order. Take {green, red, green, red} with the above graph for example. For your first move, start at the red vertex (the larger vertex), follow the green edge to end at the green vertex. Then, you take the green vertex to be your initial position for your next move.
In[]:=
ListAnimate[Table[EdgeTaggedGraph[{gg,gr,rg,rr},vertices,rc,EdgeStyle->{ggr,grg,rgg,rrr,i[[1]]->{i[[2]],Thick}}],{i,{{rr,Red},{rg,Green},{gg,Red},{gr,Green},{rr,Red},{rg,Green},{gr,Green}}}]]
Out[]=
The above graph follows the list of moves {Green, Red, Green, Red, Green, Green}.
Initialization of the vertices and edges
Initialization of the vertices and edges
I decided to save the components of the graph in variables to make them easier to use.
Defined directed edge (starting vertex, ending vertex):
In[]:=
rr="red""red";rg="red""green";gr="green""red";gg="green""green";
Defined colored directed edge (starting vertex, ending vertex, color of the edge):
In[]:=
rrr="red""red"->Red;rrg="red""red"->Green;rgr="red""green"->Red;rgg="red""green"->Green;grr="green""red"->Red;grg="green""red"->Green;ggr="green""green"->Red;ggg="green""green"->Green;
Initializing the vertices colors:
In[]:=
vertices=VertexStyle->{"red"->Red,"green"->Green};
Defining the current vertex:
In[]:=
rc=VertexSize->{"red"->0.055,"green"->0.04};gc=VertexSize{"red"0.04,"green"0.055};
Making a graph with the above variables:
In[]:=
graphtest1=EdgeTaggedGraph[{rg,rr,gr,gg},vertices,gc,EdgeStyle->{rgr,rrg,grr,ggg}]
Out[]=
Making graphs from strategies:
Making graphs from strategies:
I first tried using the graph of a strategy as the input for the general strategy function. This was inefficient since it required a lot of list manipulation instead of working on the colors in the graphs directly. After some more trial and error I reached my final general function to apply a strategy which uses a list of numerical values(0 for green and 1 for red) to output a graph given a strategy.
Below is a list of lists where each list represents a strategy and its position represents its strategy number.
Below is a list of lists where each list represents a strategy and its position represents its strategy number.
Each list follows the following format: {starting position, green vertex green edge, green vertex red edge, red vertex green edge, red vertex red edge}
In[]:=
strategies=Tuples[{0,1},5]
Out[]=
{{0,0,0,0,0},{0,0,0,0,1},{0,0,0,1,0},{0,0,0,1,1},{0,0,1,0,0},{0,0,1,0,1},{0,0,1,1,0},{0,0,1,1,1},{0,1,0,0,0},{0,1,0,0,1},{0,1,0,1,0},{0,1,0,1,1},{0,1,1,0,0},{0,1,1,0,1},{0,1,1,1,0},{0,1,1,1,1},{1,0,0,0,0},{1,0,0,0,1},{1,0,0,1,0},{1,0,0,1,1},{1,0,1,0,0},{1,0,1,0,1},{1,0,1,1,0},{1,0,1,1,1},{1,1,0,0,0},{1,1,0,0,1},{1,1,0,1,0},{1,1,0,1,1},{1,1,1,0,0},{1,1,1,0,1},{1,1,1,1,0},{1,1,1,1,1}}
So, the list of the strategy for the initial example graph would be {1,1,0,0,1}. I then created a function to create the graphs. It converts strategy numbers into separate parts of the graphs and joins them together at the end to produce a graph.
Define a function that creates a directed edge graph for a given strategy:
graphMaker[stratNo_]:=Module[{strat=strategies[[stratNo]],m1Color,m1NoColor,first,second,c,m2Color,m2NoColor,m3Color,m3NoColor,m4Color,m4NoColor},If[strat[[1]]==0, c=gc, c=rc];If[strat[[2]]==0, m1NoColor=gg; m1Color=ggg; first="green", m1NoColor=gr; m1Color=grg; first="red"];Which[strat[[3]]==strat[[2]], m2NoColor=m1NoColor; m2Color=(DirectedEdge["green",first,2]->Red),strat[[3]]==0, m2NoColor=gg; m2Color=ggr, True, m2NoColor=gr; m2Color=grr];If[strat[[4]]==0, m3NoColor=rg; m3Color=rgg; second="green", m3NoColor=rr; m3Color=rrg; second="red"];Which[strat[[4]]==strat[[5]], m4NoColor=m3NoColor; m4Color=(DirectedEdge["red",second,2]->Red),strat[[5]]==0, m4NoColor=rg; m4Color=rgr,True, m4NoColor=rr; m4Color=rrr];EdgeTaggedGraph[{m1NoColor, m2NoColor, m3NoColor, m4NoColor}, vertices, c, EdgeStyle->{m1Color, m2Color, m3Color, m4Color}]]
In[]:=
TableForm[Partition[Table[Labeled[graphMaker[i],i],{i,32}],6]]
Out[]//TableForm=
|
|
|
|
|
| ||||||||||||
|
|
|
|
|
| ||||||||||||
|
|
|
|
|
| ||||||||||||
|
|
|
|
|
| ||||||||||||
|
|
|
|
|
|
Functions to make moves after being inputted the opponent’s previous move(s)
Functions to make moves after being inputted the opponent’s previous move(s)
For last move
For last move
I then moved on to creating a function that makes each move for the agent so it could be implemented in the bigger functions.
Define a function to make a move for a given strategy:
For a max of 4 moves
For a max of 4 moves
I decided to represent the second player changing only their last move by finding the opposite of its current position after following its usual process. This allows the player to simply return the opposite of what they would otherwise play at the end.
Define a function to output the opposite value of the parity of a given number:
Next, I moved on to creating a function to follow the strategy of a given agent. Since, by definition, they all start at the starting point, there is no need to input that in this function. Since the game that I am looking at only has a history of 4, outputting a set larger than 4 would be unnecessary as it would have no value. Instead, I decided to output only the last 4 elements of the produced list of moves. For the moves after the first move, the previous position is updated since where they end is where the position for the new move starts .
Define a function to output the list of the 4 previous moves for a given strategy and list of moves:
Defining a function that does the same thing as the previous one but inverses the latest move.
For a round between 2 players
For a round between 2 players
Once I had the function for both players to make their moves given a set of moves played by their opponent, I moved on to making a function to run a round between 2 players. Since all players have a memory of only 4, when a list reaches length greater than or equal to 4, it drops the first element in the list.
Defining a function to run the previous 2 functions over each other’s outputs:
Period length of a round
Period length of a round
Since each player’s next move only depends on their opponent’s previous 4 moves, those are the only moves that matter. Therefore, the current state of any round can be described using the previous 4 moves of player 1 and of player 2. Hence, once a set of 4 moves is repeated, the game will only be a repeat of what happened before. This implies that there are only finitely many possible states. Since play must continue indefinitely, the game must eventually revisit a state that had been previously encountered. Since I am testing all possible strategies, there is also the case where a bot ends up playing one color forever. In this case, the first set of 4 moves never repeats because it ends up playing the same color forever. To ensure that the function doesn’t just search for a match even when there isn’t one, I decided to move the reference list to the next set of 4.
Defining a function to output the length of a period:
Determining a winner for all the rounds
Determining a winner for all the rounds
Since I took all possible strategies into account, I needed to find a way to differentiate the payoffs for the strategies that end up playing the same color forever versus if they always just played the same color forever. I chose to do this to differentiate an agent that ends up playing the same color forever and an agent that just plays that color forever. I decided to do this by considering a number of rounds equal to the length of the period plus the number of moves it took to end up repeating forever (all moves before it starts to repeat). Since this is a zero sum game, if the score of one player is increased by one, the score of the other must be reduced by one as well.
Defining a function to find the winner of a round:
Normal tournament without any randomness included
Normal tournament without any randomness included
Before I looked at the best strategies in random tournaments, I decided to find the best strategies in a basic tournament to see the impact randomness has when determining the best strategies.
From the above list it’s clear that 15, 25 are the best strategies as player 1 in this tournament.
From the above list it's clear that 14, 21 are the best strategies as player 2 in this tournament .
Tournaments with randomness included including results and analysis
Tournaments with randomness included including results and analysis
Defining 2 functions to find the ratio of points to rounds player:
Since there are many ways to include randomness into tournaments, I decided to try out three different ways, all of which start with equal weightages for all players.
The first of which is having one pool of player 1 and player 2 each, and randomly selecting one player from each of the pools for every round. Then, the winner of the game gets a boost to their “fitness” (probability of showing up again) by an amount determined by its win ratio while the loser of the game gets a penalty determined by its loss ratio. I’ve implemented this by doing (2+ratio of points)/2. Since the ratio of points for a loser will always be greater than -1 and negative, this fraction returns <1 and >0 for losers. Similarly, since the ratio of winners will always be lesser than 1 and positive, this fraction returns >1 and <2 for winners. If the game between the 2 agents was a draw, this fraction returns 1 which means it doesn’t change the fitness of the agent.
The first of which is having one pool of player 1 and player 2 each, and randomly selecting one player from each of the pools for every round. Then, the winner of the game gets a boost to their “fitness” (probability of showing up again) by an amount determined by its win ratio while the loser of the game gets a penalty determined by its loss ratio. I’ve implemented this by doing (2+ratio of points)/2. Since the ratio of points for a loser will always be greater than -1 and negative, this fraction returns <1 and >0 for losers. Similarly, since the ratio of winners will always be lesser than 1 and positive, this fraction returns >1 and <2 for winners. If the game between the 2 agents was a draw, this fraction returns 1 which means it doesn’t change the fitness of the agent.
Define a function to simulate the above described random tournament:
My second simulation of a random tournament is similar to my first one since it still has one pool for player 1 and player 2 each, however, it does not use the ratio by which each strategy wins or loses in each round to determine the change in strength, but instead uses a set value (in this case I’ve chose +10% for winning, -10% for losing and no change for drawing). I have chosen random values, so results will vary depending on the change in fitness for winning and losing. This game rewards strategies that win more even if it’s by a little over strategies that win less but by a greater amount.
Define a function to simulate the above described random tournament:
My third simulation of a random tournament has one player 1, chosen randomly, set for each round and then player 2 is chose randomly based on its weightage in the pool for that player 1. This is different from the previous tournaments since it ensures every strategy gets a chance to player as player 1, compared to the others where they all have equal probability of being chosen but no guarantee. Because of this uniformity, this model is a more accurate way of finding out which strategy wins the most.
Define a function to simulate the above described random tournament:
To find the best strategy, I chose to input a list of the best 3 strategies after running each simulation around 200 times and doing that 20 times. I chose to do this since it would account for the randomness of a strategy coming first by luck since this is a random setup. I chose to have the maximum possible strength of any strategy after rounds to be 10 so that, even if it simply gets lucky and ends up repeating a lot in just one simulation, that won’t mean it ends up as one of the best strategies overall. I added an upper bound of 10 to ensure that randomness doesn’t impact the final output as much.
Define a function that, given a list of best 3 strategies after running a tournament a few times gives the overall best 3 strategies:
After running this function on players 1 and 2 for all random tournaments, the following were my findings (After running it again the results may change since this includes randomness):
From the above outcomes, it can be seen that strategy numbers 5, 6 and 21 are the ones that win the most in tournament 1 as player 1, which means that these strategies win a lot as well as by a lot.
From the above outcomes, it can be seen that strategy numbers 6, 14 and 21 are the ones that win the most in tournament 1 as player 2, which means that these strategies win a lot as well as by a lot.
Therefore, in tournament 1, the overall best strategies would be 14 and 21.
From the above outcomes, it can be seen that strategy numbers 14, 21 and 22 are the ones that win the most in tournament 2 as player 1, which means that these strategies win a lot.
From the above outcomes, it can be seen that strategy numbers 6, 14, 21 and 30 are the ones that win the most in tournament 2 as player 2, which means that these strategies win a lot.
Therefore, in tournament 2, the overall best strategies would be 14 and 21.
From the above outcomes, it can be seen that strategy numbers 1, 8 and 17 are the ones that win the most in tournament 3 for any player, which means that these strategies win a lot.
Conclusion
Conclusion
In this project, I analyzed how adding randomness to the methods of determining the best strategy in a deterministic game can add uncertainty. I created functions to follow strategies with a memory of 4. Hopefully, in the future, I could increase the memory to 5 or even 6 as well as find the optimal strategy in those cases, as well as for different kinds of tournaments. I would also like to include tournaments that consider strategies that end up playing the same color forever to be the same.
References
References
[0] - Wikipedia contributors. (2026, June 26). Matching pennies. Wikipedia. https://en.wikipedia.org/wiki/Matching_pennies
Wolfram, S. (2026, June 4). Games between Programs: The Ruliology of Competition—Stephen Wolfram Writings. https://writings.stephenwolfram.com/2026/06/games-between-programs-the-ruliology-of-competition/
Fundenberg, D., & Maskin, E. (1990). Evolution and Cooperation in Noisy Repeated Games. The American Economic Review, 80(2), 274–279. http://www.jstor.org/stable/2006583
Acknowledgements
Acknowledgements
I would like to thank Stephen Wolfram for making this program possible, along with Cyrus, Eryn, Megan and Rory for running it. Thank you to my TA and Mentor groups for all of their support - Ava, Ellie, Gracelyn, Morgan, Shaivi, Shrika and Sophia. Lastly, thank you to my mentor Anoushka, advocate Adam and TA Kaavya for helping every step of the way in my project.
Additional thanks to Stephen Wolfram for suggesting this project.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Games between programs: determining the best strategy
by Nupur Layak
Wolfram Community, STAFF PICKS, July 9, 2026
https://community.wolfram.com/groups/-/m/t/3751741
by Nupur Layak
Wolfram Community, STAFF PICKS, July 9, 2026
https://community.wolfram.com/groups/-/m/t/3751741