Enigmatic Code

Programming Enigma Puzzles

Puzzle #27: The goblin game

From New Scientist #3253, 26th October 2019 [link] [link]

Annie and Beth are about to play “Goblin”. Like snakes and ladders, it is a game played on a 10 × 10 grid of squares numbered from one to 100. Players start with their counter off the board (next to square one) and take it in turns to roll a single die, aiming to be the first to get to square 100.

However, instead of snakes or ladders, there is just one hazard: a goblin. Each player gets one goblin and is allowed to place it on any square they want (apart from square 100) before the game starts.

If you land on your opponent’s goblin, you lose, and the same goes for your opponent. If a player lands on their own goblin, they are safe. If neither player lands on a goblin, the first to get to 100 wins (an exact final roll isn’t required, just getting to the 100 square is enough).

Annie, who has never played before, decides to place her goblin on square 31, because that is her lucky number.

Where should Beth place her goblin to have the maximum chance of winning?

[puzzle#27]

4 responses to “Puzzle #27: The goblin game

  1. Jim Randell 26 October 2019 at 8:48 am

    If we just look at the probability of landing on a particular square:

    For square 1, you can only land on it in your first move. And then only if you throw a 1. So the probability is 1/6 (about 16.7%)

    For square 2, you can land on it by throwing (2) or (1, 1). So the probability is 1/6 + 1/36 (about 19.4%), which is a bit better.

    For square 3, you can land on it by throwing (3), (1, 2), (2, 1), (1, 1, 1). The probability is 1/6 + 2/36 + 1/216 (about 22.7%).

    For square 4, we get: 1/6 + 3/36 + 3/216 + 1/1296 (about 26.5%).

    For square 5, we get: 1/6 + 4/36 + 6/216 + 4/1296 + 1/7776 (about 30.9%).

    For square 6, we get: 1/6 + 5/36 + 10/216 + 10/1296 + 5/7776 + 1/46656 (about 36.0%).

    For square 7 it is not possible to throw 7 with a single dice so we get: 0/6 + 6/36 + 15/216 + 20/1296 + 15/7776 + 6/46656 + 1/279936 (about 25.4%).

    The probabilities start increasing slightly, but we can’t make up for the loss of the 1/6 component.

    Here is a graph showing the probabilities on landing on each square from 1 to 99. The graph settles down to a value of around 28.6% chance of landing on any particular square once we get past square 20.

    So it would seem that B’s best bet is to put her goblin on square 6.

    To see the outcomes of actually playing the game as described I wrote a program to play the game with random dice throws and played 1 million games for each square, and indeed square 6 is the best bet with B winning around 59.4% of the time.

    Run: [ @repl.it ]

    from random import randint
    from enigma import irange, Accumulator, fdiv, printf
    
    # play the game
    # return: 0 = win for A, 1 = win for B
    def play(gA, gB, go=0, A=0, B=0):
    
      while True:
        if go == 0:
          # A to play
          A += randint(1, 6)
          if A > 99: return 0 # A wins
          if A == gB: return 1 # B wins
        elif go == 1:
          # B to play
          B += randint(1, 6)
          if B > 99: return 1 # B wins
          if B == gA: return 0 # A wins
        # otherwise carry on
        go ^= 1
    
    # number of trials to run
    N = 1000000
    
    # look for the largest number of wins
    r = Accumulator(fn=max)
    
    # position of A's goblin
    gA = 31
    
    # choose a position for B's goblin
    for gB in irange(1, 99):
      if gB == gA: continue
    
      # run random trials and count the wins for B
      n = sum(play(gA, gB, n % 2) for n in irange(1, N))
      printf("{gB} -> {n} ({f:.2%})", f=fdiv(n, N))
      r.accumulate_data(n, gB)
    
    # output solution
    printf("best = {r.data} ({f:.2%})", f=fdiv(r.value, N))
    

    Solution: Beth should place her goblin on square 6.

    Here is a plot of the computed percentage wins for B from a typical run of the program. Anywhere between 3 and A’s goblin gives B a better than 50% chance of winning, but square 6 is clearly the best option.

  2. Robert Brown 26 October 2019 at 12:15 pm

    The only thing to add to this is that A & B throw the dice alternately. But as we’re not told who starts, I took that as another equal chance, so it makes no difference to the conclusion.

    • Jim Randell 26 October 2019 at 12:31 pm

      @Robert: In my program I alternated who goes first in each game, as the behaviour wasn’t specified in the puzzle text.

      • Robert Brown 29 October 2019 at 4:57 pm

        OK for 1million throws, but we need to know chance of a B being the first win if A or B makes the first throw. It does affect the chances – for B Goblin at 5,6,7 I got (A first) 58.5, 61.8, 54.7% or (B first) 53.0, 56.8, 48.8 %, so 6 is always the best option.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: