stateDiagram-v2 [*] --> 1 1 --> 2 1 --> 3 1 --> 4 1 --> 5 1 --> 6 1 --> 7 2 --> 3 2 --> 4 2 --> 5 2 --> 6 2 --> 7 2 --> 8 3 --> 4 3 --> 5 3 --> 6 3 --> 7 3 --> 8 3 --> 9 4 --> 5 4 --> 6 4 --> 7 4 --> 8 4 --> 9 4 --> 10 5 --> 6 5 --> 7 5 --> 8 5 --> 9 5 --> 10 5 --> 11 6 --> 7 6 --> 8 6 --> 9 6 --> 10 6 --> 11 6 --> 12 7 --> 19 8 --> 9 8 --> 10 8 --> 11 8 --> 12 8 --> 13 8 --> 14 9 --> 10 9 --> 11 9 --> 12 9 --> 13 9 --> 14 9 --> 15 10 --> 3 11 --> 12 11 --> 13 11 --> 14 11 --> 15 11 --> 16 11 --> 17 12 --> 13 12 --> 14 12 --> 15 12 --> 16 12 --> 17 12 --> 18 13 --> 14 13 --> 15 13 --> 16 13 --> 17 13 --> 18 13 --> 19 14 --> 25 15 --> 16 15 --> 17 15 --> 18 15 --> 19 15 --> 20 15 --> 21 16 --> 17 16 --> 18 16 --> 19 16 --> 20 16 --> 21 16 --> 22 17 --> 18 17 --> 19 17 --> 20 17 --> 21 17 --> 22 17 --> 23 18 --> 19 18 --> 20 18 --> 21 18 --> 22 18 --> 23 18 --> 24 19 --> 20 19 --> 21 19 --> 22 19 --> 23 19 --> 24 19 --> 25 20 --> 21 20 --> 22 20 --> 23 20 --> 24 20 --> 25 20 --> 26 21 --> 22 21 --> 23 21 --> 24 21 --> 25 21 --> 26 21 --> 27 22 --> 23 22 --> 24 22 --> 25 22 --> 26 22 --> 27 22 --> 28 23 --> 29 24 --> 9 25 --> 26 25 --> 27 25 --> 28 25 --> 29 25 --> 30 26 --> 27 26 --> 28 26 --> 29 26 --> 30 27 --> 28 27 --> 29 27 --> 30 28 --> 12 29 --> 30 30 --> [*]
Background
Ciw can be used to bring discrete event simulation to games. In this post I considered a Ciw-ified version of Snakes and Ladders. There are aspects that we can faithfully and naturally represent and other aspects that we cannot.
First, let us suppose that there is a sequence of \(n\) tiles labelled \(1\) to \(n\). It has been known for decades that the classic game of Snakes and Ladders can be modelled as a Markov chain (Daykin et al 1967). Simply put, there is a collection of states in which a player’s game piece can be positioned and the probability of going to any other position only depends on the current position. This is known as the Markov property.
In the original snakes and ladders we can take time to be discrete. Each player in some order will roll a 6-sided die to decide how many steps forward in the sequence they travel on their turn. If they land on the bottom of a ladder then they instantly advance up the ladder. Similarly, if they land at the head of a snake they instantly move to the earlier position at the tip of the tail of the snake. So taking an ordinary step takes one discrete unit of time, however the jumps take no time at all. In the original Snakes and Ladders we would consider the jumps to be part of the end of a player’s turn, but using Ciw we will take these to be two separate events. A Snakes and Ladders board might look somewhat like this:
The main way that Ciw will differ in our example from the original Snakes and Ladders is the simultaneity of turns and events. Whenever events are simultaneous, Ciw randomly chooses which event happens next in order to avoid contradictions in the state.
Let’s dive into an example
Example
The following is a state diagram based on a Snakes and Ladders board I found on Google images (not the one above, sorry). We’ll use it as an example. It has a few jumps but is otherwise a contiguous sequence of states.
The first thing we can readily model is the routing from one square to another. We can do this by just creating a list of lists representing the required stochastic matrix (AKA routing matrix). The ordinary state transitions (i.e. moving the player’s piece) happen with equal probability for any of the six steps ahead of the current state. The jump spots send the piece to some other particular state with probability of one.
"""The Snakes and Ladders board and its routing matrix.
The board is a contiguous sequence of ``n_squares`` tiles labelled ``1`` to
``n_squares``. From a tile that is not the head of a snake or the foot of a
ladder, a player moves forward by an ordinary die roll: one, two, ... six
tiles. These seven tiles, plus the six jump entries, are modelled as a
stochastic (routing) matrix ``R`` where ``R[i][j]`` is the probability of
moving from tile ``i + 1`` to tile ``j + 1``.
Two details are worth calling out:
* Tiles are one-indexed for the reader but zero-indexed in ``R``; the jump
entries are written with the ``- 1`` offsets so they read like the tile
labels.
* Every ordinary row must sum to one, otherwise Ciw treats the leftover
probability as an exit from the system. Near the end of the board a die roll
can overshoot the final square, so those outcomes are *clamped* onto the
final square. Without the clamp, tiles 25 to 29 would leak probability mass,
players would leave the board early, and "reaching the end" would not be
well defined.
"""
from __future__ import annotations
jump_spots = (7, 10, 14, 23, 24, 28)
n_squares = 30
def build_routing_matrix() -> list[list[float]]:
"""Return the ``30 x 30`` routing matrix for the board.
Returns
-------
list of list of float
``R[i][j]`` is the probability of moving from tile ``i + 1`` to tile
``j + 1``. Ordinary tiles use a fair six-sided die; jump spots route
with probability one.
"""
R = [[0.0] * n_squares for _ in range(n_squares)]
for i in range(n_squares):
if i + 1 in jump_spots:
continue
if i == n_squares - 1:
continue
for step in range(1, 7):
R[i][min(i + step, n_squares - 1)] += 1 / 6
R[10 - 1][3 - 1] = 1.0
R[7 - 1][19 - 1] = 1.0
R[14 - 1][25 - 1] = 1.0
R[24 - 1][9 - 1] = 1.0
R[23 - 1][29 - 1] = 1.0
R[28 - 1][12 - 1] = 1.0
return RWe only want new arrivals to the Snakes and Ladders game to occur once at the very beginning of the simulation. Thus all the arrival distributions except the first one should be set to None, which can be quickly written as 29 * [None]. For the first square we can define a sequence of arrival times where the first time is zero and the second time is infinity. This can be given as ciw.dists.Sequential([0, float('inf')]). Here we are not really using infinity as a number with algebraic rules, but we rather assume that it is a token that entails that the second arrivals never occur.
Putting these two steps together, we can simply concatenate these two types of arrival distributions as follows:
"""Arrival distributions: all six players enter once, at time zero.
New arrivals only occur once, at the very beginning of the simulation, and all
six players enter at the first tile. Every other tile therefore has an arrival
distribution of ``None`` (written compactly as ``29 * [None]``). The first tile
uses a sequential distribution whose first arrival is at time ``0`` and whose
second arrival is at infinity, so no further arrivals ever occur.
"""
from __future__ import annotations
import ciw
from ciw_snakes_ladders.board import n_squares
n_players = 6
def build_arrival_distributions() -> list:
"""Return the per-tile arrival distributions.
Returns
-------
list
A length-``n_squares`` list whose first entry is
``ciw.dists.Sequential([0, inf])`` and whose remaining entries are
``None``.
"""
return [ciw.dists.Sequential([0, float("inf")])] + (n_squares - 1) * [None]Next we can consider the service distributions in Ciw. In this case these can be used to represent the amount of time until a player makes their next move. Whenever an ordinary move is made we can assume that it takes one discrete unit of time which can be represented by ciw.dists.Deterministic(1). However, we need to account for jumpy positions which lead to another transition instantly. These should have a zero arrival time, which we can represent as ciw.dists.Deterministic(0). Putting these together into a list we have:
"""Service distributions: one unit of time per move, zero for a jump.
In Ciw a service distribution represents the time until a player's next move.
An ordinary move takes one discrete unit of time (``Deterministic(1)``), while
a jump from a snake or ladder happens instantly (``Deterministic(0)``).
"""
from __future__ import annotations
import ciw
from ciw_snakes_ladders.board import jump_spots, n_squares
def build_service_distributions() -> list:
"""Return the per-tile service distributions.
Returns
-------
list
A length-``n_squares`` list of ``Deterministic`` distributions: zero
for jump spots and one elsewhere.
"""
return [
ciw.dists.Deterministic(0) if i in jump_spots else ciw.dists.Deterministic(1)
for i in range(n_squares)
]Now let’s consider the fact that we need some number of player pieces to enter the simulation at the start of the simulation. We already set the timing of these arrivals in the arrival distributions, but this does not specify how many pieces will arrive. For this example I have simply assumed that there are 6 players, but we could readily use any counting number of players. This is represented using ciw.dists.Deterministic(6). In a similar fashion as before for the arrival distributions, we also set None to the other 29 positions so that pieces only arrive at the starting position of the game board. Putting these distributions together we have:
"""Batching distributions: all six players arrive at the first tile together.
Batching specifies how many players enter when an arrival occurs. All six enter
at the starting tile, so the first tile has a ``Deterministic(6)`` batch
distribution and the other 29 tiles use ``None`` so that no players arrive
there.
"""
from __future__ import annotations
import ciw
from ciw_snakes_ladders.arrivals import n_players
from ciw_snakes_ladders.board import n_squares
def build_batching_distributions() -> list:
"""Return the per-tile batching distributions.
Returns
-------
list
A length-``n_squares`` list whose first entry is
``ciw.dists.Deterministic(n_players)`` and whose remaining entries are
``None``.
"""
return [ciw.dists.Deterministic(n_players)] + (n_squares - 1) * [None]We must make an assumption about the number of servers. In terms of our generalization of Snakes and Ladders this amounts to controlling how many pieces can leave a square at once. This could be changed for fun, however a natural assumption is that there is no such limit. This involves associating a float('inf') to each node for the number of servers, which can be done using multiple concatenation for all 30 squares:
"""Number of servers: unlimited, so players never block one another.
A server at a tile controls how many players can leave that tile at once.
Assigning ``float("inf")`` to every tile means there is no limit, so pieces
cannot block each other. The queueing aspect of Ciw is therefore unimportant
here, which is why the queue capacity is left at its (infinite) default.
"""
from __future__ import annotations
from ciw_snakes_ladders.board import n_squares
def build_number_of_servers() -> list:
"""Return an infinite number of servers for every tile.
Returns
-------
list
A length-``n_squares`` list of ``float('inf')``.
"""
return [float("inf")] * n_squaresAnother aspect that is tacit in the configuration is the queue capacities. The queueing aspect is completely unimportant for modelling a single square on a Snakes and Ladders board, so leaving the queue capacity at its default of infinite capacity ensures that pieces cannot block each other.
Code
Here is the complete example:
"""Assemble the Ciw network and run the Snakes and Ladders simulation.
This is the complete example from the post: it puts together the routing
matrix, the arrival, service, and batching distributions, and the number of
servers into a single :func:`ciw.create_network` call, simulates until a player
reaches the final square, and reports that player as the winner.
"""
from __future__ import annotations
import ciw
import pandas as pd
from ciw_snakes_ladders.arrivals import build_arrival_distributions
from ciw_snakes_ladders.batching import build_batching_distributions
from ciw_snakes_ladders.board import build_routing_matrix, n_squares
from ciw_snakes_ladders.servers import build_number_of_servers
from ciw_snakes_ladders.services import build_service_distributions
seed = 2018
def build_network() -> ciw.network.Network:
"""Create the Ciw network for the board.
Returns
-------
ciw.network.Network
The fully specified network, ready to be handed to
:class:`ciw.Simulation`.
"""
return ciw.create_network(
arrival_distributions=build_arrival_distributions(),
service_distributions=build_service_distributions(),
routing=build_routing_matrix(),
batching_distributions=build_batching_distributions(),
number_of_servers=build_number_of_servers(),
)
def run_simulation(random_seed: int = seed) -> ciw.Simulation:
"""Simulate until one player reaches the end of the board.
Parameters
----------
random_seed:
Seed for Ciw's random number generator, for repeatability.
Returns
-------
ciw.Simulation
The simulation, after running until a single customer has finished.
"""
ciw.seed(random_seed)
network = build_network()
simulation = ciw.Simulation(network)
simulation.simulate_until_max_customers(1, method="Finish")
return simulation
def winner(simulation: ciw.Simulation) -> int:
"""Return the id number of the player who reached the final square.
Parameters
----------
simulation:
A simulation that has been run to completion.
Returns
-------
int
The ``id_number`` of the first player routed into the final square.
"""
records = pd.DataFrame(simulation.get_all_records())
return records[records.destination == n_squares].id_number.to_numpy()[0]
def main() -> None:
"""Run the simulation and print the winner."""
simulation = run_simulation()
print(f"Player {winner(simulation)} is the winner!")
if __name__ == "__main__":
main()The above code results in Player 1 is the winner!.
Conclusions
Implementing a generalization of Snakes and Ladders was relatively easy with Ciw. The main difference is that events are allowed to happen simultaneously, however the various choices of configuration we made above should hint at how to further generalize Snakes and Ladders. If we had wanted to step even closer to simulating a classic game of Snakes and Ladders we could have simulated a separate snakes and ladders game with only one player at a time until they win. Then the results could be post-processed to find out who would have won based on the fewest steps or the least time taken (since the time is discrete 1 or 0 time steps).