paper_sissors_rock.md

What is the probability of having a stalemate with 5 players in paper sissors rock?

1 player

Obviously 1/1

2 players

Obviously 1/3 (1/1 * 1/3)

3 players

Now we get two possible stalemate scenarios.

1. All players get the same value: 1/1 * 1/3 * 1/3 = 1/9
2. All players get a different value: 1/1 * 2/3 * 1/3 = 2/9

Add the two probabilities together and get: 1/9 + 2/9 = 1/3

4 players

This is where its gets interesting (or difficult).

If we try the two possible stalemate scenarios:

1. All same value: 1/1 * 1/3 * 1/3 * 1/3 = 1/27 or if n = number of players then (1/3)^n-1
2. All values chosen: 1/1 * 2/3 * (at least one of the remaining players chooses the third value) hmm Ok, it is easier to calculate that none of the players get a certain value (call that pNone) then pAtLeastOne = 1 - pNone Try again: 1/1 * 2/3 * (1 - 2/3 * 2/3) = ~0.37 or if n = number of players then 2/3 * (1 - (2/3)^n-2)

This does not actually work, it does not approach 1 as n increases because of the second scenario (2/3 * (1 - (2/3)^n-2) has that 2/3 * .. at the start

I was on a boat and a unified rule came to me: It does not matter what the first two players choose, each player after that has a 1/3 chance of picking a value that causes a stalemate.

So using the pAtLeastOne = 1 - pNone rule: 1 - (2/3)^n-2

Plug in 4: 1 - (2/3)^4-2 = 0.56

5 players

use the rule found previously (1 - (2/3)^n-2): 1 - (2/3)^5-2 = 0.70

unfortunately brute forcing the result (see below) give about 63% stalemates for 5 players

import secrets

def print_res(stalemates_all_same, stalemates_one_of_each, num_rounds, num_players):
    print('all same:')
    print(stalemates_all_same, '/', num_rounds)
    print(stalemates_all_same/num_rounds)
    print('one of each:')
    print(stalemates_one_of_each, '/', num_rounds)
    print(stalemates_one_of_each/num_rounds)
    print('total:')
    print((stalemates_all_same + stalemates_one_of_each)/num_rounds)
    print('my algo (1 - (2/3)^n-2):')
    p = 1 - (2/3)**(num_players-2)
    print(p)

def rnd(n):
  r = []
  for i in range(n):
    r.append('psr'[secrets.randbelow(3)])
  return r

def all_possibilities(n):
    rnds = []
    for i in range(3**n):
        r = []
        for j in range(n):
            h = int(i / (3**j) % 3)
            r.append(h)
        #for j in range(n):
        #    r[j] = 'psr'[r[j]]
        #print(r)
        rnds.append(r)
    return rnds

def calc(n):
    stalemates_all_same = 0
    stalemates_one_of_each = 0
    rounds = all_possibilities(n)
    num_rounds = len(rounds)
    i = 0
    for r in rounds:
        if len(set(r)) == 1:
            print(i, r, '***')
            stalemates_all_same += 1
        elif len(set(r)) >= 3:
            print(i, r, '#')
            stalemates_one_of_each += 1
        else:
            print(i, r)
        i += 1
    print_res(stalemates_all_same, stalemates_one_of_each, num_rounds, n)

calc(5)

So my friend figured it out in a few minutes.

With 5 players there are 4 different non stalemate scenarios:

1. 1 * 2/3 * 2/3 * 2/3 * 2/3 (eg P P P P S)

2. 1 * 2/3 * 2/3 * 2/3 * 1/3 (eg P P P S S)

3. 1 * 2/3 * 2/3 * 1/3 * 1/3 (eg P P S S S)

4. 1 * 2/3 * 1/3 * 1/3 * 1/3 (eg P S S S S)

1 - sum(case 1 to 4) = ~0.63

updated python script to compare brute force and updated working formula:

def print_res(stalemates_all_same, stalemates_one_of_each, num_rounds, num_players, algo_result):
    print('all same:')
    print(stalemates_all_same, '/', num_rounds)
    print(stalemates_all_same/num_rounds)
    print('one of each:')
    print(stalemates_one_of_each, '/', num_rounds)
    print(stalemates_one_of_each/num_rounds)
    print('total:')
    print((stalemates_all_same + stalemates_one_of_each)/num_rounds)
    print('algo result:')
    print(algo_result)

def all_possibilities(num_players):
    rnds = []
    for i in range(3**num_players):
        r = []
        for j in range(num_players):
            h = int(i / (3**j) % 3)
            r.append(h)
        #for j in range(num_players):
        #    r[j] = 'psr'[r[j]]
        #print(r)
        rnds.append(r)
    return rnds

def algo(num_players):
    cases = num_players - 1
    total = 0
    for i in range(cases):
        inv = cases - i
        total += (2/3)**inv * (1/3)**i
    return 1 - total

def calc(num_players):
    stalemates_all_same = 0
    stalemates_one_of_each = 0
    rounds = all_possibilities(num_players)
    num_rounds = len(rounds)
    i = 0
    for r in rounds:
        if len(set(r)) == 1:
            print(i, r, '***')
            stalemates_all_same += 1
        elif len(set(r)) >= 3:
            print(i, r, '#')
            stalemates_one_of_each += 1
        else:
            print(i, r)
        i += 1
    print_res(stalemates_all_same, stalemates_one_of_each, num_rounds, num_players, algo(num_players))

calc(5)