@mearnest/

# Three player takeaway game

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

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