Rock–paper–scissors game in less than 10 lines of code

By: Mosè Giordano

Re-posted from: https://giordano.github.io/blog/2017-11-03-rock-paper-scissors/

Rock–paper–scissors is
a popular hand game. However, some nerds may prefer playing this game on their
computer rather than actually moving their hands.

Rock–paper–scissors rules

Image credit: Enzoklop, Wikimedia Commons, CC-BY-SA 3.0

We can write this game in less than 10 lines of code in
the Julia programming language. This implementation
will offer the opportunity to have a closer look to one of Julia’s main
features:
multiple dispatch.

The game

Here we go:

1
2
3
4
5
6
7
8
9
abstract type Shape end
struct Rock     <: Shape end
struct Paper    <: Shape end
struct Scissors <: Shape end
play(::Type{Paper}, ::Type{Rock})     = "Paper wins"
play(::Type{Paper}, ::Type{Scissors}) = "Scissors wins"
play(::Type{Rock},  ::Type{Scissors}) = "Rock wins"
play(::Type{T},     ::Type{T}) where {T<: Shape} = "Tie, try again"
play(a::Type{<:Shape}, b::Type{<:Shape}) = play(b, a) # Commutativity

That’s all. Nine lines of code, as promised. This is considerably shorter,
simpler, and easier to understand than any other implementation in all languages
over at Rosetta Code.

Explanation

Let’s dissect the code.

abstract type Shape end

defines Shape as
an
abstract type.
This will be the parent of the concrete types Rock, Paper and Scissors
that represent the characters of the game. To be fair, it’s not necessary to
create the Shape abstract type (so they would be eight lines in total!), but
this allows us to define methods for the play function only with Shape
subtypes as arguments, so that one can extended that function to other games
without clashing with our definitions.

struct Rock     <: Shape end
struct Paper    <: Shape end
struct Scissors <: Shape end

Here the concrete shapes are defined
as
composite types,
subtypes of Shape (indicated by the <: sign). They don’t actually contain
anything, but that’s OK, we just want to define the elements of the game as
types in order to take advantage of Julia’s type system.

play(::Type{Paper}, ::Type{Rock})     = "Paper wins"
play(::Type{Paper}, ::Type{Scissors}) = "Scissors wins"
play(::Type{Rock},  ::Type{Scissors}) = "Rock wins"

These are the basic rules of the game. We’ve defined
three
methods for
the play function, which return a string indicating the winning shape. The
two arguments of these methods are two shapes, for instance Rock and
Scissors. If you look carefully to the definitions, we omitted the names of
the arguments (they should come right before the :: in the list of elements),
because they’re not used in the body of the function and we don’t need them.
Instead, what’s important here is the type of both arguments.

play(::Type{T}, ::Type{T}) where {T<: Shape} = "Tie, try again"

With this single line we’ve defined the tie for all shapes. The arguments of
this method are two equal shapes, they have the same type T subtype of
Shape, whatever T is. T doesn’t even need to be defined at this point,
because in Julia, dispatch is dynamic on all arguments (in in C++/Java you can
achieve dynamic dispatch on first argument, but it’ll be static for the others).

So far we’ve seen the rules, for example, for the arguments Paper and Rock,
in this order, but there is no rule for the same arguments in the reversed
order. Here comes the magic:

play(a::Type{<:Shape}, b::Type{<:Shape}) = play(b, a)

Recall that multiple dispatch
is the ability to define function behavior across many combinations of argument
types. What’s crucial here is that the type of all arguments matters, not just
the first one as in object-oriented programming languages. If none of the
previous methods applies (PaperRock, PaperScissors, RockScissors
and all the combinations of arguments with equal types), this method will be
used, which simply swaps the two arguments so that one of the above methods can
be called.

Besides letting us save four definitions, multiple dispatch makes the program
very efficient. The appropriate method is quickly selected based on the type of
all the arguments. Without multiple dispatch we’d have to write explicitly a
sequence of at least seven if ... elseif ... end,
but branching comes
at a performance cost. Of course this isn’t a big deal in a simple game like
this, but think about your CPU-intensive application.

Play the game

Now that we’ve implemented the game we can play it in the
Julia
REPL:

julia> abstract type Shape end

julia> struct Rock     <: Shape end

julia> struct Paper    <: Shape end

julia> struct Scissors <: Shape end

julia> play(::Type{Paper}, ::Type{Rock})     = "Paper wins"
play (generic function with 1 method)

julia> play(::Type{Paper}, ::Type{Scissors}) = "Scissors wins"
play (generic function with 2 methods)

julia> play(::Type{Rock},  ::Type{Scissors}) = "Rock wins"
play (generic function with 3 methods)

julia> play(::Type{T},     ::Type{T}) where {T<: Shape} = "Tie, try again"
play (generic function with 4 methods)

julia> play(a::Type{<:Shape}, b::Type{<:Shape}) = play(b, a) # Commutativity
play (generic function with 5 methods)

julia> play(Paper, Scissors)
"Scissors wins"

julia> play(Rock, Rock)
"Tie, try again"

julia> play(Rock, Paper)
"Paper wins"

julia> @which play(Rock, Paper)
play(a::Type{#s1} where #s1<:Shape, b::Type{#s2} where #s2<:Shape) in Main at REPL[9]:1

There was no explicit method for the combination of arguments RockPaper,
but the commutative rule has been used here, as confirmed by the
@which
macro.

Play randomly

We can also add some randomness to the game.
The
rand
function can pick up a random element from a given collection. Luckily,
the
subtypes
function returns the array with all the subtypes of the given abstract type:

julia> subtypes(Shape)
3-element Array{Union{DataType, UnionAll},1}:
 Paper
 Rock
 Scissors

julia> rand(subtypes(Shape))
Rock

julia> rand(subtypes(Shape))
Rock

julia> rand(subtypes(Shape))
Paper

julia> rand(subtypes(Shape))
Scissors

julia> play(rand(subtypes(Shape)), rand(subtypes(Shape)))
"Scissors wins"

julia> play(rand(subtypes(Shape)), rand(subtypes(Shape)))
"Paper wins"

julia> play(rand(subtypes(Shape)), rand(subtypes(Shape)))
"Paper wins"

julia> play(rand(subtypes(Shape)), rand(subtypes(Shape)))
"Tie, try again"

julia> play(rand(subtypes(Shape)), rand(subtypes(Shape)))
"Paper wins"

Extend to four shapes

Here it is proposed an
extension of the game to a fourth shape, the well, with the following rules:

  • the well wins against rock and scissors, because both fall into it,
  • the well loses against paper, because the paper covers it.

This is a non-zero-sum game, but
this isn’t a concern for us.

We can extend the above Julia implementation to include the well.

1
2
3
4
struct Well <: Shape end
play(::Type{Well}, ::Type{Rock})     = "Well wins"
play(::Type{Well}, ::Type{Scissors}) = "Well wins"
play(::Type{Well}, ::Type{Paper})    = "Paper wins"

We accomplished the extension with just four additional lines, one to define the
new type and three for the new game rules. We don’t need to redefine the tie or
the commutativity methods, thanks to Julia’s dynamic type system.

Here you can see that multiple dispatch let us extend the game very easily,
saving us four more definitions. Out of the total necessary
definitions we had just definitions, without giving up commutativity.

Let’s see it in action in the REPL:

julia> struct Well <: Shape end

julia> play(::Type{Well}, ::Type{Rock})     = "Well wins"
play (generic function with 6 methods)

julia> play(::Type{Well}, ::Type{Scissors}) = "Well wins"
play (generic function with 7 methods)

julia> play(::Type{Well}, ::Type{Paper})    = "Paper wins"
play (generic function with 8 methods)

julia> play(Paper, Well)
"Paper wins"

julia> play(Well, Rock)
"Well wins"

julia> play(Well, Well)
"Tie, try again"