「波波攒」游戏有最优解或者混合策略、纳什均衡的解吗，如何计算？

你要的编程方法, 先定义一些辅助函数:

formatSolve[e__] := Association@Simplify@Flatten@Solve[e];
formatNSolve[e__] := Association@Chop@Flatten@NSolve[e];
V[i_, i_] := 1 / 2;
Q[i_, j_] := Block[
	{var = If[j == 0, {Energy, Defend}, {Energy, Attack, Defend}]},
	{Equal @@ Append[var.U[i, j], V[i, j]], Tr[var] == 1}
];
EQ[i_, j_] := Block[
	{var = If[j == 0, {Energy, Defend}, {Energy, Attack, Defend}]},
	Sequence @@ {Eliminate[Q[i, j], var], V[i, j] > 0}
];

$V_{i,j}$ 表示我方气为 $i$ , 敌方气为 $j$ 时的局面评估.

规定必胜时为 $1$ , 必败时为 $0$ , 公平局面为 $\frac{1}{2}$ .

$U$ 表示给定 $V$ 时的支付矩阵, $Q$ 是该支付的代价方程组, $EQ$ 是对应方程组的约化关系.

当 $k=3$ 时, 任何一方的气累积到 $3$ 必须出杀, 因为出杀就赢了, 而且如果对面也是 $3$ 气, 对买出杀你不出不就 GG 了…

因此我们只需要考虑气不足 $3$ 时的子博弈.

竖向表示敌方的气, 横向表示我方的气.

$\begin{array}{c|lll} & 0 & 1 & 2 \\ \hline 0 &1/2&1-V_{1,0}&1-V_{2,0} \\ 1 &V_{1,0}&1/2&1-V_{2,1}\\ 2 &V_{2,0}&V_{2,1}&1/2\\ \end{array}$

因为游戏是完全对称的, 我方有多少优势, 敌方就有多少劣势.

所以只要考虑我方策略即可, 形势反过来的话策略直接对调.

显然 $V_{2,0}$ 是一个必胜态, 在这个状态对面只能等死.

然后我们考虑 $V_{1,0}$ 这个局势, 列出所有策略组:

$\begin{array}{c|cc} V_{1,0}& 气 & 防 \\ \hline 气 &<2,1>&<2,0>\\ 攻 &1&<1,1>\\ \end{array}$

对面没有气不能攻, 那我也不需要防.

$V_{1,1}=\frac{1}{2}$ 是个公平局面, $V_{2,0}=1$ 分析过了, 是必胜态.

所以此时的支付矩阵 $U_{1,0}=\begin{bmatrix} V_{2,1}&1\\ 1&1/2 \end{bmatrix}$

对应的方程组和约化形式如图所示.

现在唯一要分析的就是 $V_{2,1}$ 这个局势了

$\begin{array}{c|ccc} V_{2,1}& 气 & 攻 & 防 \\ \hline 气 &<3,2>&0&<3,1> \\ 攻 &1&<1,0>&<1,1>\\ 防 &<2,2>&<2,0>&<2,1>\\ \end{array}$

同样的可以列出支付矩阵 $U_{2,1}=\begin{bmatrix} 1&0&1\\ 1&V_{1,0}&1/2\\ 1/2&1&V_{2,1} \end{bmatrix}$

此时的代价方程组和等价形式如下所示:

两个方程解两个未知数, 搞定.

$\begin{cases} V_{1,0} \left(2 V_{2,1}-3\right)=V_{2,1}-2 \\ V_{1,0} \left(4 V_{2,1}^2-6 V_{2,1}+2\right)=2-3 V_{2,1} \\ \end{cases}$

U[1, 0] = {
	{V[2, 1], 1},
	{1, 1 / 2}
};
U[2, 1] = {
	{1, 0, 1},
	{1, V[1, 0], 1 / 2},
	{1 / 2, 1, V[2, 1]}
};
sol = formatSolve[
	{EQ[1, 0], EQ[2, 1]},
	{V[1, 0], V[2, 1]}
]

我们求出了 $V_{1,0}$ 的局面评估是 82.7%, $V_{2,1}$ 的评估是 73.5%.

这个评估事实上也等价于预期胜率.

然后各个局面采用的策略也相应可求:

当然你得先手动定义支付矩阵 $U$ 之后才能进行其他计算.

你要加其他技能比如什么反弹之类的也能写进去.

我这个代码就是不能自动推导支付矩阵的不好, 其他求解全都自动化了.

来源：知乎 www.zhihu.com

作者：酱紫君

【知乎日报】千万用户的选择，做朋友圈里的新鲜事分享大牛。
点击下载

此问题还有 7 个回答，查看全部。