农心杯世界围棋团体锦标赛是由韩国日刊体育社主办，农心集团赞助的一项围棋国际大赛，是世界上水平最高的围棋团体赛。每届由中国、日本和韩国各派出5名棋手，采用擂台赛的方式，三国棋手轮番上阵，最后留在擂台上的队伍获得冠军。
中日韩三国擂台赛，各派出五名选手。首先每方各派出一位选手比赛，其中一国棋手首轮轮空。假设每两人之间的胜率均为50%，则首轮轮空一方胜率为多少？
这是一道动态规划问题。
定义状态为（中方人数，日方人数，韩方人数，当前对局甲方，当前对局乙方），状态函数为f，f（当前状态）=（中方获胜概率，日方获胜概率，韩方获胜概率）。
其实状态也可以描述为（中方人数，日方人数，韩方人数，观战方），这样用4个数字就解决了。
状态空间中的结点数远远小于5×5×5×3，实际上只有363种状态。
import numpy as np
a = dict() # 备忘录方法
def get(x):
if tuple(x) not in a:
# 如果已经有两个国家没人了，游戏就可以结束了
if x[0] == 0 and x[1] == 0:
return [0, 0, 1]
elif x[0] == 0 and x[2] == 0:
return [0, 1, 0]
elif x[1] == 0 and x[2] == 0:
return [1, 0, 0]
one = x[3] # 对战的一方
two = x[4] # 对战的另一方
three = 3 - one - two # 观战的一方
# 如果人数不够，那就让观战的一方上场
if x[one] == 0:
x[3] = three
return get(x)
if x[two] == 0:
x[4] = three
return get(x)
# 如果two胜利
ne = x[:]
ne[one] -= 1
ans = np.array([0.0, 0.0, 0.0])
ne[3] = two
ne[4] = three
ans += 0.5 * np.array(get(ne))
# 如果one胜利
ne = x[:]
ne[two] -= 1
ne[3] = one
ne[4] = three
ans += 0.5 * np.array(get(ne))
a[tuple(x)] = ans
return a[tuple(x)]
print(get([5, 5, 5, 0, 1]))