Rock Paper Scissors magma by Mark Seemann
The Rock Paper Scissors game forms a magma. An example for object-oriented programmers.
This article is part of a larger series about monoids, semigroups, and other group-like algebraic structures. In this article, you'll see an example of a magma, which is a binary operation without additional constraints.
Rock Paper Scissors #
When my first child was born, my wife and I quickly settled on a first name, but we couldn't agree on the surname, since we don't share the same surname. She wanted our daughter to have her surname, and I wanted her to have mine. We couldn't think of any rational arguments for one or the other, so we decided to settle the matter with a game of Rock Paper Scissors. I lost, so my daughter has my wife's surname.
Despite that outcome, I still find that Rock Paper Scissors is a great way to pick between two equally valid alternatives. You could also flip a coin, or throw a die, but most people have their hands handy, so to speak.
In C#, you can model the three shapes of rock, paper, and scissors like this:
public abstract class Rps { public readonly static Rps Rock = new R(); public readonly static Rps Paper = new P(); public readonly static Rps Scissors = new S(); private Rps() { } private class R : Rps { } private class P : Rps { } private class S : Rps { } // More members... }
I've seen more than one example where people use an enum to model the three shapes, but I believe that this is wrong, because enums have an order to them, including a maximum and a minimum value (by default, enum is implemented with a 32-bit integer). That's not how Rock Paper Scissors work, so instead, I chose a different model where Rock, Paper, and Scissors are Singletons.
This design works for the example, although I'm not entirely happy with it. The problem is that Rock, Paper, and Scissors should be a finite set, but by making Rps abstract, another developer could, conceivably, create additional derived classes. A finite sum type would have been better, but this isn't easily done in C#. In a language with algebraic data types, you can make a prettier implementation, like this Haskell example. F# would be another good language option.
Binary operation #
When playing the game of Rock Paper Scissors, each round is a throw that compares two shapes. You can model a throw as a binary operation that returns the winning shape:
public static Rps Throw(Rps x, Rps y) { if (x == Rock && y == Rock) return Rock; if (x == Rock && y == Paper) return Paper; if (x == Rock && y == Scissors) return Rock; if (x == Paper && y == Paper) return Paper; if (x == Paper && y == Scissors) return Scissors; if (x == Paper && y == Rock) return Paper; if (x == Scissors && y == Scissors) return Scissors; if (x == Scissors && y == Rock) return Rock; return Scissors; }
To a C# programmer, perhaps the method name Throw is bewildering, because you might expect the method to throw an exception, but I chose to use the domain language of the game.
Because this method takes two Rps values as input and returns an Rps value as output, it's a binary operation. Thus, you already know it's a magma, but could it, also, be another, stricter binary operations, such as a semigroup or quasigroup?
Lack of associativity #
In order to be a semigroup, the binary operation must be associative. You can easily demonstrate that Throw isn't associative by use of a counter-example:
[Fact] public void ThrowIsNotAssociative() { // Counter-example Assert.NotEqual( Rps.Throw(Rps.Throw(Rps.Paper, Rps.Rock), Rps.Scissors), Rps.Throw(Rps.Paper, Rps.Throw(Rps.Rock, Rps.Scissors))); }
This xUnit.net unit test passes, thereby demonstrating that Throw is not associative. The result of paper versus rock is paper, which, pitted against scissors yields scissors. On the other hand, paper versus the result of rock versus scissors is paper, because rock versus scissors is rock, and rock versus paper is paper.
Since Throw isn't associative, it's not a semigroup (and, by extension, not a monoid). Could it be a quasigroup?
Lack of invertibility #
A binary operation must be invertible in order to be a quasigroup. This means that for any two elements a and b, there must exist two other elements x and y that turns a into b.
This property must hold for all values involved in the binary operation - in this case Rock, Paper, and Scissors. A single counter-example is enough to show that Throw is not invertible:
[Fact] public void ThrowIsNotInvertible() { // Counter-example var a = Rps.Rock; var b = Rps.Scissors; Assert.False(Rps.All.Any(x => Rps.Throw(a, x) == b)); Assert.False(Rps.All.Any(y => Rps.Throw(y, a) == b)); }
This (passing) unit test utilises an All property on Rps:
public static IReadOnlyCollection<Rps> All { get { return new[] { Rock, Paper, Scissors }; } }
For a counter-example, pick Rock as a and Scissors as b. There's no value in All that satisfies the invertibility property. Therefore, Throw is not a quasigroup, either.
Lack of identity #
Since Throw is neither associative nor invertible, it's not really any named algebraic construct, other than a magma. It's neither group, semigroup, quasigroup, monoid, loop, groupoid, etc. Does it have any properties at all, apart from being a binary operation?
It doesn't have identity either, which you can illustrate with another counter-example:
[Fact] public void ThrowHasNoIdentity() { // Find all identity candidates for Rock var rockIdentities = from e in Rps.All where Rps.Throw(e, Rps.Rock) == Rps.Rock && Rps.Throw(Rps.Rock, e) == Rps.Rock select e; // Narrow for Paper var paperIdentities = from e in rockIdentities where Rps.Throw(e, Rps.Paper) == Rps.Paper && Rps.Throw(Rps.Paper, e) == Rps.Paper select e; // None of those candidates are the identity for Scissors var scissorIdentities = from e in paperIdentities where Rps.Throw(e, Rps.Scissors) == Rps.Scissors && Rps.Throw(Rps.Scissors, e) == Rps.Scissors select e; Assert.Empty(scissorIdentities); }
First, you use Rps.All to find all the values that behave as an identity element for Rps.Rock. Recall that the identity is an element that doesn't change the input. In other words it's a value that when combined with Rps.Rock in Throw still returns Rps.Rock. There are two values that fulfil that property: Rps.Rock and Rps.Scissors. Those are the two values contained in rockIdentities.
In order to be an identity, the value must behave as a neutral element for all possible values, so next, filter rockIdentities to find those elements that also behave as identities for Rps.Paper. Between Rps.Rock and Rps.Scissors, only Rps.Rock behaves like an identity for Rps.Paper, so paperIdentities is a collection containing only the single value Rps.Rock.
Is Rps.Rock an identity for Rps.Scissors, then? It's not. scissorIdentities is empty. There's no element in Rps.All that acts an identity for all values in Rps.All. Therefore, by brute force, the test ThrowHasNoIdentity demonstrates (as it says on the tin) that throw has no identity.
Commutativity #
While Throw is neither associative, invertible, nor has identity, it does have at least one property: it's commutative. This means that the order of the input values doesn't matter. In other words, for any two Rps values x and y, this assertion always passes:
Assert.Equal( Rps.Throw(x, y), Rps.Throw(y, x));
Since Rps.Throw(x, y) is equal to Rps.Throw(y, x), Throw is commutative.
Summary #
The Rock Paper Scissors Throw operation is a commutative magma, but while, for example, we call an associative magma a semigroup, there's no fancy word for a commutative magma.
Next: Colour-mixing magma.
