抓石子争单双博弈题

yq_118

写了个程序，确实是先手必胜，第一步可以在B里取3个。

yq_118

这个问题规模很小，只有27^3=19683。用递归轻松搞定。 调用 s(27, 27, 27, 0) 返回的是 (27, 24, 27)，表示第一步在B里取3个，以后根据对手的决策反复调用s就行了。

1. #!/usr/bin/python3 -i
   
2. 
   
3. 
   
4. def solver(a_max, b_max, c_max):
   
5.     mem = {(0, 0, 0, 0): 'win',
   
6.            (0, 0, 0, 1): 'lose'}
   
7. 
   
8.     def adj(a, b, c):
   
9.         return ([(i, b, c) for i in range(max(0, a - a_max), a)] +
   
10.                 [(a, i, c) for i in range(max(0, b - b_max), b)] +
    
11.                 [(a, b, i) for i in range(max(0, c - c_max), c)])
    
12. 
    
13.     def rec(x):
    
14.         if x not in mem:
    
15.             p = ((sum(x) + 1) % 2,)
    
16.             for y in adj(*x[:3]):
    
17.                 if rec(y + p) == 'lose':
    
18.                     mem[x] = y
    
19.                     break
    
20.             else:
    
21.                 mem[x] = 'lose'
    
22.         return mem[x]
    
23. 
    
24.     return lambda a, b, c, p: rec((a, b, c, p))
    
25. 
    
26. 
    
27. s = solver(3, 4, 5)
    
28. print(s(27, 27, 27, 0))

复制代码

[ 本帖最后由 yq_118 于 2011-9-11 20:40 编辑 ]

yq_118

这个是Python写的，用C的话要考虑太多与问题无关的东西。

yq_118

稍加修改就能推广到一般的情况。
根据题目的要求调用solver，返回一个求解器。
调用求解器，第一个参数为一个向量，表示各堆的石子数，第二个参数表示奇偶性，0为偶，1为奇。
返回'lose'表示输了，否则返回一个向量表示决策。

1. #!/usr/bin/python3 -i
   
2. 
   
3. 
   
4. def solver(*m):
   
5.     n = len(m)
   
6.     mem = {((0,) * n, 0): 'win',
   
7.            ((0,) * n, 1): 'lose'}
   
8. 
   
9.     def adj(x):
   
10.         for i in range(n):
    
11.             y = list(x)
    
12.             for y[i] in range(max(0, x[i] - m[i]), x[i]):
    
13.                 yield tuple(y)
    
14. 
    
15.     def rec(x, parity):
    
16.         if (x, parity) not in mem:
    
17.             q = (sum(x) + parity + 1) % 2
    
18.             for y in adj(x):
    
19.                 if rec(y, q) == 'lose':
    
20.                     mem[(x, parity)] = y
    
21.                     break
    
22.             else:
    
23.                 mem[(x, parity)] = 'lose'
    
24.         return mem[(x, parity)]
    
25. 
    
26.     return rec
    
27. 
    
28. 
    
29. s = solver(3, 4, 5)
    
30. print(s((27, 27, 27), 0))

复制代码

[ 本帖最后由 yq_118 于 2011-9-12 13:14 编辑 ]