repl.it
@mearnest/

Three player takeaway game

Python 2.7

Three players take turns removing between 1 and 5 coins from a pile of 40. Which player has the best chance of winning?

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from fractions import Fraction
from functools import wraps

def main():
  print ' n        P1       P2       P3'
  for n in range(1,41):
    if n < 10: 
      print '',
    print n,' ', '  '.join(map(show_frac,outcome(n)))


def outcome(n):
  if n == 1: 
    return (Fraction(1),0,0)
  options = [outcome(n-i) for i in range(1,min(6,n))]
  # Among all options, choose the ones for which the 
  # probability of P3 losing is minimal (because P1
  # becomes P3 after one turn)
  best_prob = min(options,key=lambda x:x[2])[2]
  good_opts = [t for t in options if t[2]==best_prob]
  # Remove duplicate options, then
  good_opts = list(set(good_opts))
  # randomly choose one of them.
  result = average_vec(good_opts)
  # Rotate the probabilities, since after one 
  # turn the players' roles have shifted
  return (result[2],result[0],result[1])


# Given a list of lists, returns a list 
# whose i^th entry is the average of the i^th
# entry of each input list.
def average_vec(Ls):
  return map(lambda L:sum(L)/len(L),zip(*Ls))


# This is just for making the numbers look pretty
def show_frac(x):
  if x.denominator == 1:
    s = str(x.numerator)
  else:
    s = str(x.numerator)+'/'+str(x.denominator)
  while len(s) < 7:
    s = ' ' + s
  return s

def show_frac2(x):
  return str(round(float(x),2))

# This makes the computation of outcome much faster
def memoize(f):
	cache = f.cache = dict()
	@wraps(f)
	def f_memoized(*args):
		if args not in cache:
			cache[args] = f(*args)
		return cache[args]
	return f_memoized

outcome = memoize(outcome)

main()
Fetching token
?