在解决石头剪子布这个问题的过程中,我们会用到一个 maxmin 函数,先来看看这个函数的理论基础。
首先,Minimax 也叫做鞍点,是人工智能,决策理论,博弈论,统计和哲学等领域中基础的决策规则,用于将最坏情况(最大损失)的损失降到最低。
而 maximmin与 minimax 有所不同:
Minimax 用于 zero-sum 的游戏,表示让对手的最大收益最小化,就相当于使自己的最大损失最小化,并使自己的最小收益最大化。
而 Maximin 是 non-zero-sum 游戏的常用术语,用来描述使自己的最小收益最大化的策略,这与让对手的最大收益最小化不同,与纳什均衡策略也不相同。
下面是代码实现:
def maxmin(A):
num_vars = len(A)
# minimize matrix c
c = [-1] + [0 for i in range(num_vars)]
c = np.array(c, dtype="float")
c = matrix(c)
# constraints G*x <= h
G = np.matrix(A, dtype="float").T # reformat each variable is in a row
# G before inverse sign to get the standard form
print("G matrix:", G)
G *= -1 # minimization constraint
G = np.vstack([G, np.eye(num_vars) * -1]) # > 0 constraint for all vars
new_col = [1 for i in range(num_vars)] + [0 for i in range(num_vars)]
G = np.insert(G, 0, new_col, axis=1) # insert utility column for simplex tableau
G = matrix(G)
h = ([0 for i in range(num_vars)] +
[0 for i in range(num_vars)])
h = np.array(h, dtype="float")
h = matrix(h)
# contraints Ax = b, sum of pi_rock, pi_paper, pi_scissors equal 1
A = [0] + [1 for i in range(num_vars)]
A = np.matrix(A, dtype="float")
A = matrix(A)
b = np.matrix(1, dtype="float")
b = matrix(b)
print("c matrix:", c)
print("G matrix:", G)
print("h matrix:", h)
print("A matrix:", A)
print("b matrix:", b)
sol = solvers.lp(c=c, G=G, h=h, A=A, b=b)
return sol
学习资料:
https://en.wikipedia.org/wiki/Minimax#Maximin
https://medium.com/@excitedAtom/linear-programming-in-python-cvxopt-and-game-theory-8626a143d428