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.
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 (Paper
–Rock
, Paper
–Scissors
, Rock
–Scissors
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 Rock
–Paper
,
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"