Running on Java 17-ea+27-2476 (Preview)

Home of The JavaSpecialists' Newsletter

**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.

"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:

publicinterfaceDice {introll(); }

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.

importjava.util.*;importjava.util.concurrent.*;publicclassDiceFairimplementsDice {privatefinalRandom random;publicDiceFair() {this(ThreadLocalRandom.current()); }publicDiceFair(Random random) {this.random = random; }publicintroll() {returnrandom.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.

publicinterfaceGameObserver {defaultvoidturn() { }defaultvoidroll(introll) { }defaultvoidjump(intfrom,intto) { }defaultvoidfinished() { } }

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

publicclassGameObserverSummaryimplementsGameObserver {privateintturns;publicvoidturn() { turns++; }publicintturns() {returnturns; } }

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.

importjava.util.*;publicclassGameObserverDetailedextendsGameObserverSummary {privatefinalList<Integer> rollHistory =newArrayList<>();privateintclimbs, slides;publicList<Integer> rollHistory() {returnList.copyOf(rollHistory); }publicvoidroll(introll) { rollHistory.add(roll); }publicvoidjump(intfrom,intto) {if(from < to) climbs += to - from;elseslides += from - to; }publicintclimbs() {returnclimbs; }publicintslides() {returnslides; } }

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

publicclassGameObserverPrinterextendsGameObserverSummary {privateintrolls = 0;publicvoidturn() {super.turn(); System.out.println("Turn "+ turns() +":"); }publicvoidroll(introll) { rolls++; System.out.println("Rolled a "+ roll); }publicvoidjump(intfrom,intto) { System.out.println("Jumped from "+ from +" to "+ to); }publicvoidfinished() { 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.

importjava.util.*;importjava.util.stream.*;publicclassBoard {privatefinalint[] snakes, ladders;// Internal helper methods /** * Flatten a Map<Integer, Integer> to an int[101] */privatestaticint[] flatten(Map<Integer, Integer> map) {int[] result =newint[101]; map.forEach((from, to) -> result[from] = to);returnresult; }/** * Expand an int[101] back into a Map<Integer, Integer> */privatestaticMap<Integer, Integer> expand(int[] matrix) { Map<Integer, Integer> result =newHashMap<>();for(intfrom = 1; from < matrix.length; from++) {intto = matrix[from];if(to != 0) result.put(from, to); }returnMap.copyOf(result); }/** * Reverse a Map so each jump goes in the opposite direction. */privatestaticMap<Integer, Integer> reverse( Map<Integer, Integer> map) {returnmap.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). */publicBoard(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. */publicBoard reverse() {returnnewBoard(reverse(expand(ladders)), reverse(expand(snakes))); }publicvoidplay(GameObserver observer) { play(observer,newDiceFair()); }publicvoidplay(GameObserver observer, Dice dice) {intposition = 1;// we start on position 1do{ observer.turn();introll;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(); }privateintnext(GameObserver observer,intpos,intcount) {intnext = pos + count;if(next > 100) next = 100 - (next % 100);// bounce off endintjump;if((jump = snakes[next]) != 0 || (jump = ladders[next]) != 0) { observer.jump(next, jump); next = jump; }returnnext; } }

Here is the specific board that we will use:

importjava.util.*;publicclassEfiBoardextendsBoard {publicEfiBoard() {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:

publicclassSimpleGame {publicstaticvoidmain(String... args) { Board board =newEfiBoard(); board.play(newGameObserverPrinter()); } }

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:

importjava.util.*;publicclassTournamentObserver {privatefinalList<Integer> turns =newArrayList<>();privatefinalList<Integer> climbs =newArrayList<>();privatefinalList<Integer> slides =newArrayList<>();privateintbestTurns = Integer.MAX_VALUE;privateCollection<Integer> bestGame;publicvoidplay(Board board, Dice dice) { board.play(newGameObserverDetailed() {publicvoidfinished() {intturns = turns();if(turns < bestTurns) { bestTurns = turns; bestGame = rollHistory(); } TournamentObserver.this.turns.add(turns); TournamentObserver.this.climbs.add(climbs()); TournamentObserver.this.slides.add(slides()); } }, dice); }publicString toString() { IntSummaryStatistics turnsStats = turns.stream() .mapToInt(Integer::intValue) .summaryStatistics();doubleclimbsAverage = climbs.stream() .mapToInt(Integer::intValue) .average().orElse(0.0);doubleslidesAverage = slides.stream() .mapToInt(Integer::intValue) .average().orElse(0.0);returnString.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:

publicclassGame {publicstaticvoidmain(String... args) { Board board =newEfiBoard(); Dice dice =newDiceFair();vartournamentObserver =newTournamentObserver();for(inti = 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:

publicclassGameReversed {publicstaticvoidmain(String... args) { Board board =newEfiBoard().reverse(); Dice dice =newDiceFair();vartournamentObserver =newTournamentObserver();for(inti = 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:

importjava.util.*;importjava.util.stream.*;publicclassDiceOptimizedimplementsDice {privatefinalPrimitiveIterator.OfInt sequence;publicDiceOptimized(intnumberOfSixes,intlast) {this.sequence = IntStream.concat( IntStream.generate(() -> 6).limit(numberOfSixes), IntStream.of(last)).iterator(); }publicintroll() {returnsequence.next(); } }

For example, here is the GameOptimized:

publicclassGameOptimized {publicstaticvoidmain(String... args) {vartournamentObserver1 =newTournamentObserver(); tournamentObserver1.play(newEfiBoard(),newDiceOptimized(10, 1)); System.out.println(tournamentObserver1); System.out.println();vartournamentObserver2 =newTournamentObserver(); tournamentObserver2.play(newEfiBoard().reverse(),newDiceOptimized(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:

importjava.util.concurrent.*;publicclassDiceFastimplementsDice {privateintx = ThreadLocalRandom.current().nextInt();privateinty = ThreadLocalRandom.current().nextInt();privateintz = ThreadLocalRandom.current().nextInt();privateintw = ThreadLocalRandom.current().nextInt();// https://www.jstatsoft.org/article/view/v008i14publicintroll() {inttmp = (x ^ (x << 15)); x = y; y = z; z = w; w = (w ^ (w >> 21)) ^ (tmp ^ (tmp >> 4));returnmod(w, 6) + 1; }protectedintmod(intx,intdiv) {intresult = x % div;if(result < 0)return-result;returnresult; } }

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:

importjava.lang.invoke.*;importjava.util.concurrent.*;publicclassDiceVeryFastimplementsDice {// fits in L2 cache at 512kprivatestaticfinalbyte[] rolls =newbyte[512 * 1024];privateintpos = ThreadLocalRandom.current() .nextInt(0, rolls.length);privatestaticfinalintMASK = rolls.length - 1;publicintroll() {return(byte) ROLLS.getOpaque(rolls, (pos++ & MASK)); }privatestaticfinalVarHandle ROLLS = MethodHandles.arrayElementVarHandle(byte[].class);static{ fillWithRandom(); Thread shuffler =newThread(() -> {while(true) { fillWithRandom(); } },"DiceVeryFast-Shuffler"); shuffler.setDaemon(true); shuffler.start(); }privatestaticvoidfillWithRandom() {intsize = rolls.length;varrnd = ThreadLocalRandom.current();for(inti = 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:

importjava.util.stream.*;publicclassDiceFastFixedModextendsDiceFast {privatestaticfinalint[] rolls = IntStream.iterate(0, i -> (i + 1) % 6).limit(65536).toArray();privatestaticfinalintMASK = rolls.length - 1;protectedintmod(intx,intignored) {returnrolls[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!

importjava.security.*;importjava.util.*;importjava.util.concurrent.atomic.*;publicclassDiceMeasurer {privatestaticfinalintRUNS = 600_000_000;privatestaticfinalLongAccumulator best =newLongAccumulator(Long::min, Long.MAX_VALUE);publicstaticvoidmain(String... args) {for(inti = 0; i < 20; i++) { test(); } System.out.printf("best time = %dms%n", (best.longValue() / 1_000_000)); }privatestaticvoidtest() {longtime = System.nanoTime();try{// Dice dice = new DiceFair(); // 1433 ms// Dice dice = new DiceFair(new SecureRandom()); // 85495 ms// Dice dice = new DiceFast(); // 1001 msDice dice =newDiceFastFixedMod();// 690 ms// Dice dice = new DiceVeryFast(); // 372 msint[] results =newint[6];for(inti = 0; i < RUNS; i++) { results[dice.roll() - 1]++; } System.out.println("results = "+ Arrays.toString(results));int[] diffs =newint[6];for(inti = 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.

importjava.util.*;importjava.util.function.*;importjava.util.stream.*;publicclassSimulation {publicstaticvoidplay(intplayers, IntFunction<Board> boardCreator, IntFunction<Dice> diceCreator,intgames) {int[] wins =newint[players]; Board[] boards = IntStream.range(0, players) .mapToObj(boardCreator).toArray(Board[]::new); Dice[] dice = IntStream.range(0, players) .mapToObj(diceCreator).toArray(Dice[]::new);for(inti = 0; i < games; i++) {varobs =newGameObserverSummary[wins.length]; Arrays.setAll(obs, __ -> new GameObserverSummary());intminTurns = Integer.MAX_VALUE;for(intplayer = 0; player < wins.length; player++) { boards[player].play(obs[player], dice[player]); minTurns = Math.min(minTurns, obs[player].turns()); }for(intplayer = 0; player < obs.length; player++) {// The first player that has turns == minTurns winsif(obs[player].turns() == minTurns) { wins[player]++;break; } } }for(inti = 0; i < wins.length; i++) {if(i > 0) {doublediff = (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.

publicclassGameSimulationSingleBoardSingleDice {publicstaticvoidmain(String... args) {intplayers = 2; Board board =newEfiBoard(); Dice dice =newDiceVeryFast();intgames = 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.

publicclassGameSimulationMixedBoardsSingleDice {publicstaticvoidmain(String... args) {intplayers = 2; Board[] boards = {newEfiBoard(),newEfiBoard().reverse()}; Dice dice =newDiceVeryFast();intgames = 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

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)

When you load these comments, you'll
be connected to Disqus.
Privacy Statement.

We deliver relevant courses, by top Java developers to produce more resourceful and efficient programmers within their organisations.

We can help make your Java application run faster and trouble-shoot concurrency and performance bugs...