291Snakes and Ladders

Author: Dr Heinz M. KabutzDate: 2021-07-20Java Version: 17Category: Tips and Tricks

Abstract: "Would you like to play with me?" - Summer holidays are a good time to relax and whip out a board game or two. In this newsletter we explore a children's favourite - snakes and ladders, with a simulation written in Java.

Welcome to the 291th edition of The Java(tm) Specialists' Newsletter. Half a mile from our house there lies a small fresh-water lake, roughly three acres in size. "Fresh-water" might be overselling this prime piece of real estate; every time I run past, I half expect an enormous green ogre to jump out from the reeds shouting "stay away". Lake Maherida (not to be confused with Maherida Beach) usually dries up completely by the end of August. If all the water disappears by the end of July, we will have water shortages. This year, by the end of June, almost all the water had evaporated.

I took this photo at the end of June during my daily run. In the middle you see a small brackish puddle and just above a flock of swimming enthusiasts wondering whether the gym lockdown applies to them as well. Maybe they will join my "run every day" club?

Enough about the weather, let's have some Java fun!

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Snakes and Ladders

"Would you like to play with me?" the last day of grade 2 is a wrap and our youngest proudly shows me her graduation gift from her kind teacher Mrs Dimitra. It is a magnetic snakes and ladders game. I close my laptop and reply in the only reasonable manner: "Sure, what are we playing?"

"Youngest starts", she pipes up and throws the dice. As the dice stops rolling, I wonder how much of an advantage starting gives her? It has to be more than zero. My turn and I throw a six. I move from 1 to 7. "You can throw again". Ah, the six. I throw again. Another six. "Can I throw again?" "Sure". I feel unstoppable. Next a 4, which lands me on the head of a snakes and I slide back down to position 6. I am lucky throughout the game, except for two long slides down from position 64 to 18. Eventually I have only 3 more squares. I throw a 5. "What happens now?" "You bounce back two steps"

We play two games, which I both win, even though I try my level best not to (dad's can relate). A few times I count wrong to put myself in a worse position, but nothing gets past our 8 year old and she corrects me. Looking at the board, I begin to wonder: Imagine if we reverse the direction of the ladders and the snakes? Would this change our chances of winning? In other words, we climb up a snake and we slide down a ladder. There is a ladder from 80 to 99, right near the end. The bouncing around at the end, as we try to get the perfect number to win, is not an issue when the ladder goes in the normal direction. However, if the ladder makes us slide down, then every time the dice falls on 99, we go down to 80 again. There are 9 snakes versus 8 ladders, however, the ladders are longer. Even though I am not sure, I feel fairly confident that reversing the direction of the snakes and ladders will decrease my chances of winning.

"OK, let's play again", I tell her, "but this time, whenever I get onto the tail of a snake I climb up, and when I get to the top of a ladder, I slide down. "I also want to do that." Great, my plan to give her a sizeable advantage is foiled. We play and I win again. We both get bored and head for the Playmobil.

Afterwards, I got to thinking about our game. One way to determine the probabilities it to construct a complicated mathematical model of the game. A lazier approach is to play the game ten million times as a simulation. A simulation is not good at finding the outliers. For example, what is the least turns that we need to win? And what could potentially be the most turns in a single game? Our simulation will not answer those outlier questions, but it will give us a good approximation of the odds of winning, plus the average number of turns to complete the game. To begin, we create a Dice:

public interface Dice {
  int roll();
}

We will start with just one implementation, the DiceFair, taking a random number generator, by default the trusty ThreadLocalRandom. Our DiceFair is not thread-safe, each thread would need its own instance. However, we will not be using threads for running the simulation.

import java.util.*;
import java.util.concurrent.*;

public class DiceFair implements Dice {
  private final Random random;

  public DiceFair() {
    this(ThreadLocalRandom.current());
  }

  public DiceFair(Random random) {
    this.random = random;
  }

  public int roll() {
    return random.nextInt(1, 7);
  }
}

Even though it is not truly random, the numbers seem evenly distributed between the six numbers. We will expand on this a bit more later.

We will also need a Board to play on, but before we create that, we want to be able to observe the game and collect information about it. For example, we might want to know how many turns were thrown or what the sequence was that needed the least turns. The observer would be for a single game played on the board.

public interface GameObserver {
  default void turn() { }
  default void roll(int roll) { }
  default void jump(int from, int to) { }
  default void finished() { }
}

The GameObserverSummary only stores how many turns were needed to finish.

public class GameObserverSummary implements GameObserver {
  private int turns;

  public void turn() {
    turns++;
  }

  public int turns() {
    return turns;
  }
}

The more detailed GameObserverDetailed expands on that and also stores all the rolls of the dice, in addition to the total distance that we climbed and slid.

import java.util.*;

public class GameObserverDetailed extends GameObserverSummary {
  private final List<Integer> rollHistory = new ArrayList<>();
  private int climbs, slides;

  public List<Integer> rollHistory() {
    return List.copyOf(rollHistory);
  }

  public void roll(int roll) {
    rollHistory.add(roll);
  }

  public void jump(int from, int to) {
    if (from < to) climbs += to - from;
    else slides += from - to;
  }

  public int climbs() {
    return climbs;
  }

  public int slides() {
    return slides;
  }
}

To debug the game, we can also write a GameObserverPrinter that prints what is happening, as it is happening.

public class GameObserverPrinter extends GameObserverSummary {
  private int rolls = 0;

  public void turn() {
    super.turn();
    System.out.println("Turn " + turns() + ":");
  }

  public void roll(int roll) {
    rolls++;
    System.out.println("Rolled a " + roll);
  }

  public void jump(int from, int to) {
    System.out.println("Jumped from " + from + " to " + to);
  }

  public void finished() {
    System.out.println("That took " + turns() + " turns and " +
        rolls + " rolls");
  }
}

We are ready to create our game board. In my first version, I stored the jump tables for the snakes and ladders inside a Map. Not surprisingly, the hash lookups were the biggest bottleneck in my simulation. I thus changed the internal structure to instead contain jump tables in arrays of size 101 each. Even though I use int[]s internally, Maps are more convenient, thus our constructor still takes those as parameters. Furthermore, I have added a convenience method reverse() to reverse the direction of the snakes and the ladders. Lastly we have the play() method, which takes a GameObserver and optionally a Dice to use for the game. I follow the rules that my daughter taught me: We start at position 1. If we roll 6, we roll again. If we land on a snake, we slide down, and if on a ladder, we climb up. We need an exact number to win and if we have more, we bounce back again. Youngest starts, although that is hard to code into the game.

import java.util.*;
import java.util.stream.*;

public class Board {
  private final int[] snakes, ladders;

  // Internal helper methods

  /**
   * Flatten a Map<Integer, Integer> to an int[101]
   */
  private static int[] flatten(Map<Integer, Integer> map) {
    int[] result = new int[101];
    map.forEach((from, to) -> result[from] = to);
    return result;
  }

  /**
   * Expand an int[101] back into a Map<Integer, Integer>
   */
  private static Map<Integer, Integer> expand(int[] matrix) {
    Map<Integer, Integer> result = new HashMap<>();
    for (int from = 1; from < matrix.length; from++) {
      int to = matrix[from];
      if (to != 0) result.put(from, to);
    }
    return Map.copyOf(result);
  }

  /**
   * Reverse a Map so each jump goes in the opposite direction.
   */
  private static Map<Integer, Integer> reverse(
      Map<Integer, Integer> map) {
    return map.entrySet().stream().collect(Collectors.toMap(
        Map.Entry::getValue,
        Map.Entry::getKey
    ));
  }

  /**
   * Create a game board with map of snakes (sliding down) and
   * ladders (climbing up).
   */
  public Board(Map<Integer, Integer> snakes,
               Map<Integer, Integer> ladders) {
    this.snakes = flatten(snakes);
    this.ladders = flatten(ladders);
  }

  /**
   * Create a new game board with the direction of snakes and
   * ladders reversed.
   */
  public Board reverse() {
    return new Board(reverse(expand(ladders)),
        reverse(expand(snakes)));
  }

  public void play(GameObserver observer) {
    play(observer, new DiceFair());
  }

  public void play(GameObserver observer, Dice dice) {
    int position = 1; // we start on position 1
    do {
      observer.turn();
      int roll;
      do {
        roll = dice.roll();
        observer.roll(roll);
        position = next(observer, position, roll);
      } while (roll == 6 && position != 100); // 6 rolls again
    } while (position != 100);
    observer.finished();
  }

  private int next(GameObserver observer, int pos, int count) {
    int next = pos + count;
    if (next > 100) next = 100 - (next % 100); // bounce off end
    int jump;
    if ((jump = snakes[next]) != 0 ||
        (jump = ladders[next]) != 0) {
      observer.jump(next, jump);
      next = jump;
    }
    return next;
  }
}

Here is the specific board that we will use:

import java.util.*;

public class EfiBoard extends Board {
  public EfiBoard() {
    super(
        Map.of(
            17, 6,
            48, 25,
            51, 30,
            59, 40,
            64, 18,
            79, 62,
            83, 75,
            89, 68,
            94, 88),
        Map.of(
            9, 31,
            19, 38,
            21, 42,
            28, 84,
            36, 57,
            52, 67,
            70, 91,
            80, 99
        ));
  }
}

In this SimpleGame, a single player is trying to finish the game:

public class SimpleGame {
  public static void main(String... args) {
    Board board = new EfiBoard();
    board.play(new GameObserverPrinter());
  }
}

Output could be for example:

Turn 1:
Rolled a 4
Turn 2:
Rolled a 6
Rolled a 2
Turn 3:
Rolled a 5
Turn 4:
Rolled a 1
Jumped from 19 to 38
Turn 5:
Rolled a 5
Turn 6:
Rolled a 5
Jumped from 48 to 25
Turn 7:
Rolled a 4
Turn 8:
Rolled a 2
Turn 9:
Rolled a 5
Jumped from 36 to 57
Turn 10:
Rolled a 4
Turn 11:
Rolled a 6
Rolled a 6
Rolled a 3
Turn 12:
Rolled a 5
Turn 13:
Rolled a 3
Turn 14:
Rolled a 3
Turn 15:
Rolled a 3
Turn 16:
Rolled a 3
Turn 17:
Rolled a 3
Turn 18:
Rolled a 3
Turn 19:
Rolled a 1
That took 19 turns and 22 rolls

The first question I had was: how many turns do we need on average to get to position 100? To answer this, I created a TournamentObserver that collects more statistics about the number of turns per game, how much we climbed and slid, and also a list of the dice rolls that made us complete the game in the least turns:

import java.util.*;

public class TournamentObserver {
  private final List<Integer> turns = new ArrayList<>();
  private final List<Integer> climbs = new ArrayList<>();
  private final List<Integer> slides = new ArrayList<>();
  private int bestTurns = Integer.MAX_VALUE;
  private Collection<Integer> bestGame;

  public void play(Board board, Dice dice) {
    board.play(new GameObserverDetailed() {
      public void finished() {
        int turns = turns();
        if (turns < bestTurns) {
          bestTurns = turns;
          bestGame = rollHistory();
        }
        TournamentObserver.this.turns.add(turns);
        TournamentObserver.this.climbs.add(climbs());
        TournamentObserver.this.slides.add(slides());
      }
    }, dice);
  }

  public String toString() {
    IntSummaryStatistics turnsStats = turns.stream()
        .mapToInt(Integer::intValue)
        .summaryStatistics();
    double climbsAverage = climbs.stream()
        .mapToInt(Integer::intValue)
        .average().orElse(0.0);
    double slidesAverage = slides.stream()
        .mapToInt(Integer::intValue)
        .average().orElse(0.0);
    return String.format(Locale.US,
        "games={count=%,d, min=%d, average=%.1f, max=%d}, " +
            "climbsAverage=%.1f, " +
            "slidesAverage=%.1f, " +
            "bestTurns=%d, bestGame=%s",
        turnsStats.getCount(),
        turnsStats.getMin(),
        turnsStats.getAverage(),
        turnsStats.getMax(),
        climbsAverage,
        slidesAverage,
        bestTurns,
        bestGame);
  }
}

We play this game 10 million times:

public class Game {
  public static void main(String... args) {
    Board board = new EfiBoard();
    Dice dice = new DiceFair();
    var tournamentObserver = new TournamentObserver();
    for (int i = 0; i < 10_000_000; i++) {
      tournamentObserver.play(board, dice);
    }
    System.out.println(tournamentObserver);
  }
}

The output is going to be similar to the following:

games={count=10,000,000, min=2, average=26.9, max=194},
    climbsAverage=55.7, slidesAverage=51.6, bestTurns=2,
    bestGame=[3, 6, 6, 6, 6, 6, 6, 6, 6, 4]

Before we analyze the results, let's ask a second question: Will we need more turns on average if we reverse the board? I would imagine so, but let's reverse the board and try again:

public class GameReversed {
  public static void main(String... args) {
    Board board = new EfiBoard().reverse();
    Dice dice = new DiceFair();
    var tournamentObserver = new TournamentObserver();
    for (int i = 0; i < 10_000_000; i++) {
      tournamentObserver.play(board, dice);
    }
    System.out.println(tournamentObserver);
  }
}

The output changes substantially:

games={count=10,000,000, min=2, average=46.1, max=752},
    climbsAverage=91.3, slidesAverage=176.2, bestTurns=2,
    bestGame=[6, 6, 5, 6, 6, 6, 6, 6]

The results are interesting. With the normal board, we have slightly more ladder climbs than snake slides. With the reversed board, we have about twice as many slides as climbs. The average number of turns is about 27 with the normal board and 46 with the reversed board. I was right, this would have given dad a disadvantage, if I had managed to convince my 8 year old. The minimum and maximum in both cases are not correct. Minimum is actually 1 turn for both boards (for the normal board 10 sixes followed by a 1, and for the reversed board it is 18 sixes followed by a 5). For both boards, the maximum number is infinite. For example, imagine if we only ever threw a 1. With the normal board we would get into an endless loop sliding down the snake from 94 to 88. With the reversed board, we would keep on sliding down the ladder from 99 to 80. In order to demonstrate the best cases, I created a DiceOptimized, where we specify the number of sixes and the last number:

import java.util.*;
import java.util.stream.*;

public class DiceOptimized implements Dice {
  private final PrimitiveIterator.OfInt sequence;

  public DiceOptimized(int numberOfSixes, int last) {
    this.sequence = IntStream.concat(
        IntStream.generate(() -> 6).limit(numberOfSixes),
        IntStream.of(last)).iterator();
  }

  public int roll() {
    return sequence.next();
  }
}

For example, here is the GameOptimized:

public class GameOptimized {
  public static void main(String... args) {
    var tournamentObserver1 = new TournamentObserver();
    tournamentObserver1.play(
        new EfiBoard(),
        new DiceOptimized(10, 1));
    System.out.println(tournamentObserver1);

    System.out.println();

    var tournamentObserver2 = new TournamentObserver();
    tournamentObserver2.play(
        new EfiBoard().reverse(),
        new DiceOptimized(18, 5));
    System.out.println(tournamentObserver2);
  }
}

And the output is:

games={count=1, min=1, average=1.0, max=1},
climbsAverage=38.0, slidesAverage=0.0, bestTurns=1,
bestGame=[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 1]

games={count=1, min=1, average=1.0, max=1},
climbsAverage=42.0, slidesAverage=56.0, bestTurns=1,
bestGame=[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5]

It did take a bit of time to generate all these random numbers and I was wondering if there was a faster way. In Java Concurrency in Practice, Goetz shows an algorithm for pseudorandom that was based on some research. I tried the algorithm, but it did not give as good a discrete uniform distribution as I wanted for my simulation. The paper that he referenced in the book gave me some hints and thus I created this pseudorandom number generator:

import java.util.concurrent.*;

public class DiceFast implements Dice {
  private int x = ThreadLocalRandom.current().nextInt();
  private int y = ThreadLocalRandom.current().nextInt();
  private int z = ThreadLocalRandom.current().nextInt();
  private int w = ThreadLocalRandom.current().nextInt();

  // https://www.jstatsoft.org/article/view/v008i14
  public int roll() {
    int tmp = (x ^ (x << 15));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 21)) ^ (tmp ^ (tmp >> 4));
    return mod(w, 6) + 1;
  }

  protected int mod(int x, int div) {
    int result = x % div;
    if (result < 0) return -result;
    return result;
  }
}

This did speed up the dice rolling a little bit (results to follow). However, I wanted it to be even faster. Since I have some spare cores in my machine, I decided to have some fun using VarHandles and a thread that fills an array with random values [1..6] in the background. The roll() iterates over that array, which I have sized to fit inside my L2 cache:

import java.lang.invoke.*;
import java.util.concurrent.*;

public class DiceVeryFast implements Dice {
  // fits in L2 cache at 512k
  private static final byte[] rolls = new byte[512 * 1024];

  private int pos = ThreadLocalRandom.current()
      .nextInt(0, rolls.length);
  private static final int MASK = rolls.length - 1;

  public int roll() {
    return (byte) ROLLS.getOpaque(rolls, (pos++ & MASK));
  }

  private static final VarHandle ROLLS =
      MethodHandles.arrayElementVarHandle(byte[].class);

  static {
    fillWithRandom();
    Thread shuffler = new Thread(() -> {
      while (true) {
        fillWithRandom();
      }
    }, "DiceVeryFast-Shuffler");
    shuffler.setDaemon(true);
    shuffler.start();
  }

  private static void fillWithRandom() {
    int size = rolls.length;
    var rnd = ThreadLocalRandom.current();
    for (int i = size - 1; i >= 0; i--) {
      ROLLS.setOpaque(rolls, i, (byte) rnd.nextInt(1, 7));
    }
  }
}

We could also create a hybrid of our last two Dice implementations. The single most expensive operation in our DiceFast is the remainder (%). We could avoid this by creating a 64k array with numbers 0..5 and then finding an offset into that array using our random number, masked with 65535. Let's try that out:

import java.util.stream.*;

public class DiceFastFixedMod extends DiceFast {
  private static final int[] rolls = IntStream.iterate(0,
      i -> (i + 1) % 6).limit(65536).toArray();
  private static final int MASK = rolls.length - 1;

  protected int mod(int x, int ignored) {
    return rolls[x & MASK];
  }
}

In DiceMeasurer we measure the efficacy and performance of the dices. The slowest at 85 seconds is our DiceFair with SecureRandom, but that also gives the most uniform distribution of values. DiceFair with the default ThreadLocalRandom completes in 1433 ms, DiceFast in 1001 ms and DiceVeryFast in 372 ms. Our hybrid DiceFastFixedMod manages in 690 ms. Shows how expensive the remainder operator % is!

import java.security.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class DiceMeasurer {
  private static final int RUNS = 600_000_000;

  private static final LongAccumulator best =
      new LongAccumulator(Long::min, Long.MAX_VALUE);

  public static void main(String... args) {
    for (int i = 0; i < 20; i++) {
      test();
    }
    System.out.printf("best time = %dms%n",
        (best.longValue() / 1_000_000));
  }

  private static void test() {
    long time = System.nanoTime();
    try {
      // Dice dice = new DiceFair(); // 1433 ms
      // Dice dice = new DiceFair(new SecureRandom()); // 85495 ms
      // Dice dice = new DiceFast(); // 1001 ms
      Dice dice = new DiceFastFixedMod(); // 690 ms
      // Dice dice = new DiceVeryFast(); // 372 ms
      int[] results = new int[6];
      for (int i = 0; i < RUNS; i++) {
        results[dice.roll() - 1]++;
      }
      System.out.println("results = " + Arrays.toString(results));
      int[] diffs = new int[6];
      for (int i = 0; i < diffs.length; i++) {
        diffs[i] = results[i] - RUNS / 6;
      }
      System.out.println("diffs = " + Arrays.toString(diffs));
    } finally {
      time = System.nanoTime() - time;
      best.accumulate(time);
      System.out.printf("time = %dms%n", (time / 1_000_000));
    }
  }
}

I also tested the performance of Game.java with our various Dice implementations. Using DiceFair we completed in 5198 ms, with DiceFast it took 4300 ms and with DiceVeryFast we got it down to 3906 ms. This was using the EspilonGC with 30GB of memory, running the Game over and over until it crashed with an OutOfMemoryError.

Let us answer the question of whether the youngest player gets an advantage by starting, and by how much. For simplicity, we are going to deviate from the real game a little bit. Instead of taking turns throwing the dice, we are going to assume that the dice is fair and so we are simply going to let each player throw until they have reached position 100, counting the turns. To determine who the winner is, we check who had the least turns. If the turns are the same, we pick whichever player started first.

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Simulation {
  public static void play(int players,
                          IntFunction<Board> boardCreator,
                          IntFunction<Dice> diceCreator,
                          int games) {
    int[] wins = new int[players];
    Board[] boards = IntStream.range(0, players)
        .mapToObj(boardCreator).toArray(Board[]::new);
    Dice[] dice = IntStream.range(0, players)
        .mapToObj(diceCreator).toArray(Dice[]::new);

    for (int i = 0; i < games; i++) {
      var obs = new GameObserverSummary[wins.length];
      Arrays.setAll(obs, __ -> new GameObserverSummary());
      int minTurns = Integer.MAX_VALUE;
      for (int player = 0; player < wins.length; player++) {
        boards[player].play(obs[player], dice[player]);
        minTurns = Math.min(minTurns, obs[player].turns());
      }
      for (int player = 0; player < obs.length; player++) {
        // The first player that has turns == minTurns wins
        if (obs[player].turns() == minTurns) {
          wins[player]++;
          break;
        }
      }
    }
    for (int i = 0; i < wins.length; i++) {
      if (i > 0) {
        double diff = (wins[i - 1] - wins[i]) * 100.0 / games;
        System.out.printf(Locale.US, "diff = %.2f%%%n", diff);
      }
      System.out.println("player" + (i + 1) +
          " Wins = " + wins[i]);
    }
  }
}

For example, here is a simulation of 10 million games by two players on a single board and with one dice.

public class GameSimulationSingleBoardSingleDice {
  public static void main(String... args) {
    int players = 2;
    Board board = new EfiBoard();
    Dice dice = new DiceVeryFast();
    int games = 10_000_000;
    Simulation.play(players, __ -> board, __ -> dice, games);
  }
}

Output is:

player1 Wins = 5138231
diff = 2.76%
player2 Wins = 4861769

As expected, the player that starts does have a tiny advantage. If we played 100 times, the first player should win 51 times and the second player 49 times. But that would take too long.

If we change our game to two players where the first has the normal board, but the second has a reversed board, thus they slide down ladders and climb up snakes, the odds change substantially.

public class GameSimulationMixedBoardsSingleDice {
  public static void main(String... args) {
    int players = 2;
    Board[] boards = {new EfiBoard(), new EfiBoard().reverse()};
    Dice dice = new DiceVeryFast();
    int games = 10_000_000;
    Simulation.play(players, i -> boards[i], __ -> dice, games);
  }
}

Instead of only a 2.76% improvement in odds, it increases to 36.98%:

player1 Wins = 6849091
diff = 36.98%
player2 Wins = 3150909

All of this could be calculated mathematically with an absorbing Markov chain, but that would be a topic for a Markovian Specialists Newsletter.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive