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:

CHOICES = (1,2,5,9) #(1,2,3) ist langweilig
INITSTATE = 24

def subtraction_game(s):
    '''Game loop.'''
    while True:
        s -= user_action(s)
        if (s == 0):
            print('Congratulations! You won!')
            break
        s -= computer_action(s)
        if (s == 0):
            print('You lost! Better luck next time!')
            break

def nim_strategy(s):
	if s in CHOICES: return s
	for i in CHOICES:
		if s > i and not nim_strategy(s-i): return i
	return False

def user_action(s):
    '''User's action selection (by console input).'''
    print('%d matches are on the table. How many do you want to take?' % s)
    amount = 0
    while int(amount) not in CHOICES or int(amount) > s:
        amount = input('> ')
    return int(amount)


def computer_action(s):
    '''Computer's action selection.'''
    amount = nim_strategy(s)
    if not amount:
        from random import choice
        amount = choice(tuple(filter(lambda x: x <= s, CHOICES)))
    print('Computer takes %d matches.' % amount)
    return amount


if __name__ == '__main__':
	for i in range(1,30): print str(i) + ': ' + str(nim_strategy(i))
	subtraction_game(INITSTATE)