使用 Stacks 而不是 piles 的加权 Nim，每个玩家从相反的边挑选
Weighted Nim with Stacks instead of piles and each player picks from opposite sides
有n叠硬币。每个堆栈包含 k_i 个硬币，特定堆栈中的硬币具有不同的值。在每一轮中，您可以从任何一叠的顶部挑选一枚硬币，您的对手可以从任何一叠的底部挑选一枚硬币。硬币价值最高的人获胜。
这场比赛的最佳策略是什么？
我认为这应该是某种贪婪算法结合对手的反应，也许将每个堆栈分成两半来比较值？
偶数堆叠的价值
作为一个特例，考虑是否所有的栈都是偶数。
第二个玩家可以复制第一个玩家以获得等于所有下半部分筹码的价值。这表明第二个玩家的游戏价值至少是底部 - 顶部（即第一个玩家的游戏价值最多是顶部 - 底部）。
同样，第一个玩家可以从任何一叠中取出，然后复制第二个玩家以获得等于所有上半部分堆栈的值。 （如果第二个玩家从奇数筹码开始游戏，第一个玩家可以再次自由地从任何筹码中取走。）这个策略保证第一个玩家获得等于筹码的所有上半部分的价值。这说明游戏对第一个玩家的价值至少是top-bottom。
因此，这款游戏的价值恰好是上下，并且至少有一个玩家的最佳策略是这种复制方法。当然，如果球员打得不是最佳状态，也许可以做得更好，但这是双方最佳发挥的理论最佳值。
对于奇数大小的堆栈，需要更加注意每个堆栈的中心值。
通用堆栈的值
一般来说，一组堆栈的值是通过将您一侧的值相加，减去另一侧的值，然后轮流 add/subtract 任何中心值（按大小递减顺序）得出的). （如果轮到你了，就加第一个值，否则减去第一个值。）
在Python中，可以写成：
def compute_value(stacks):
t=0
middle=[]
for S in stacks:
n=len(S)
n2,r = divmod(n,2)
t += sum(S[:n2]) - sum(S[n2+r:])
if r:
middle.append(S[n2])
middle.sort(reverse=True)
for i,m in enumerate(middle):
if i%2==0:
t += m
else:
t -= m
return t
最优策略
这导致了一个有效的最优策略。简单地考虑从每一堆中取出一枚硬币，计算得到的堆的价值（从对手的角度来看），然后选择给你最高分的选项（分数=硬币的价值+得到的堆的价值）。
请注意，这是高效的，因为您只需要考虑前面的一步，而不需要探索一整棵树。
（这也可以进一步优化，因为堆栈中的所有值都可以忽略，除了本轮可以拿走的硬币、中心硬币和可能成为中心硬币的硬币。）
首先，让我们尝试找出如果两位玩家都表现最佳，将采取哪些 gems。
我们假设 gem 不是堆叠，而是假设 gem 排列成一行，玩家在他们选择的 gem 旁边做一个标记。
引理 5.1：
首先让我们证明，如果任何玩家选择，他们可以强制尽可能平均地分配所有筹码。为此，玩家只需模仿对手的动作，所有的筹码最终都会尽可能平均地分配。
基于直觉的假设是，如果两名球员都表现最佳，那么他们最终只会从自己的半场挑选 gem。我们只比较所有堆栈中的两个堆栈。所以我们会得到 3 个案例：
案例一：偶数和偶数
让我们使用 $2m$ 和 $2n$ gems 的两个堆栈，让 gems 编号为 $a_1,a_2。 ..,a_{2m} $和$b_1,b_2,...,b_{2n}$分别从左到右，玩家1从左边选择，玩家2从右边选择.
凭直觉，我们希望玩家能够完美平均地分配每一堆。所以让我们假设相反，最后，玩家 1 选择了 gems $a_1,a_2,...,a_m,...,a_{ m+k}$ 和 $b_1,b_2,...,b_{n-k}$ 并且玩家 2 选择了这两个堆栈中剩余的 gems。
从引理 5.1 中，我们知道任何玩家都可以强制拆分，但由于他们没有这样做，我们可以假设 gems 的值的总和来自 $a_{m+1 },...,a_{m+k}$ 和来自 $b_{n-k+1},...,b_n$ 是相等的，因为否则，这将意味着玩家没有最佳发挥。有可能数值是相等的，但是我们在玩的时候，为了简单起见，可以选择平分。
案例二：奇数奇数
让我们做与之前完全相同的事情，但两个堆栈有 $2m+1$ 和 $2n+1$ gems。所以最中心的 gem 是 $a_{m+1}$ 和 $b_{n+1}$。
让我们再次假设最后，玩家 1 选择了 gems $a_1,a_2,...,a_{m+1},... ,a_{m+1+k}$ 和 $b_1,b_2,...,b_{n+1-k}$ 并且玩家 2 选择剩余的 gems这两个堆栈。与前面的情况类似，$a_{m+2},...,a_{m+1+k}$ 和 $b_{n+1-k 中 gems 的值之和+1},...,b_{n+1}$ 必须相等，因为假设两个玩家都玩得最好。唯一的区别是在这种情况下，先走的玩家可以选择 $a_{m+1}$ 和 $b_{n+1}$ 之间的 gems 中较大的一个。因此，我们可以平分堆栈，只需要比较中心 gems.
案例 3：偶数和奇数
让我们做与之前完全相同的事情，但两个堆栈有 2m 和 2n+1 gems。所以堆栈 B 的中心 gem 是 b_(n+1)。假设玩家 1 首先选择。
假设玩家 1 最后选择了 gems $a_1,a_2,...,a_m,...,a_ {m+k}$ 和 $b_1,b_2,...,b_{n+1-k}$ 并且玩家 2 选择了这两个堆栈中剩余的 gems。与前面的情况类似，gems 来自 $a_{m+1},...,a_{m+k}$ 和来自 $b_{n+1-k+1 的值之和},...,b_{n+1}$ 必须相等。
同理，如果最终玩家1选择了gems $a_1,a_2,...,a_{m-k}$和$b_1,b_2,...,b_{n+1},...,b_{n+1+k}$，玩家2选择剩余的gems，然后gems 的值来自 $a_{m-k+1},...,a_m$ 和来自 $b_{n+2},...,b_{n+1+k }$ 必须相等。
所以为了简单起见，我们可以将每个堆栈分成两半。
因此，最佳策略（对双方玩家而言）是将 gem 的偶数堆分成两半，然后将所有 gem 的奇数堆排序s 根据其中心 gems 的值递减，然后第一个堆栈将被拆分，这样玩家 1（假设玩家 1 开始）获得中心 gem，第二个堆栈将是拆分使得玩家 2 获得中心 gem，并且奇数 gem 的第 $(2n-1)th$ 堆栈将与玩家 1 获得中心 gem 拆分, 奇数个 gem 的第 (2n)$ 个堆栈将分裂，玩家 2 获得中心 gem.
因此，如果我们先走，我们必须选择奇数个 gems 和最有价值的中心 gem 的堆栈，我们可以简单地镜像机器人的移动直到堆栈被删除，因为我们假设机器人也在最佳状态下运行。如果在你的回合中没有部分空的筹码，你应该选择一个奇数 gem 的筹码，当前最有价值的中心 gem.
让我们根据它们的中心 gem，从 1 到 $k$ 对所有具有奇数 gem 的堆栈进行降序排序和编号。
根据这个策略，如果两个玩家都玩得最好，假设玩家 1 先走，从顶部选择，
玩家1的分数=所有gem上半部分的所有gem的值之和，偶数gem+所有gem的值之和]s 位于奇数 gems 的堆栈的上半部分 { 如果堆栈编号为奇数，则包括中心 gem，如果堆栈编号为奇数，则不包括中心 gem堆栈编号为偶数}
玩家 2 的分数 = 剩余 gems
的值之和
我认为这就是双方都采用（我认为的）最佳策略进行游戏的结果。
有n叠硬币。每个堆栈包含 k_i 个硬币，特定堆栈中的硬币具有不同的值。在每一轮中，您可以从任何一叠的顶部挑选一枚硬币，您的对手可以从任何一叠的底部挑选一枚硬币。硬币价值最高的人获胜。
这场比赛的最佳策略是什么？
我认为这应该是某种贪婪算法结合对手的反应，也许将每个堆栈分成两半来比较值？
偶数堆叠的价值
作为一个特例，考虑是否所有的栈都是偶数。
第二个玩家可以复制第一个玩家以获得等于所有下半部分筹码的价值。这表明第二个玩家的游戏价值至少是底部 - 顶部（即第一个玩家的游戏价值最多是顶部 - 底部）。
同样，第一个玩家可以从任何一叠中取出，然后复制第二个玩家以获得等于所有上半部分堆栈的值。 （如果第二个玩家从奇数筹码开始游戏，第一个玩家可以再次自由地从任何筹码中取走。）这个策略保证第一个玩家获得等于筹码的所有上半部分的价值。这说明游戏对第一个玩家的价值至少是top-bottom。
因此，这款游戏的价值恰好是上下，并且至少有一个玩家的最佳策略是这种复制方法。当然，如果球员打得不是最佳状态，也许可以做得更好，但这是双方最佳发挥的理论最佳值。
对于奇数大小的堆栈，需要更加注意每个堆栈的中心值。
通用堆栈的值
一般来说，一组堆栈的值是通过将您一侧的值相加，减去另一侧的值，然后轮流 add/subtract 任何中心值（按大小递减顺序）得出的). （如果轮到你了，就加第一个值，否则减去第一个值。）
在Python中，可以写成：
def compute_value(stacks):
t=0
middle=[]
for S in stacks:
n=len(S)
n2,r = divmod(n,2)
t += sum(S[:n2]) - sum(S[n2+r:])
if r:
middle.append(S[n2])
middle.sort(reverse=True)
for i,m in enumerate(middle):
if i%2==0:
t += m
else:
t -= m
return t
最优策略
这导致了一个有效的最优策略。简单地考虑从每一堆中取出一枚硬币，计算得到的堆的价值（从对手的角度来看），然后选择给你最高分的选项（分数=硬币的价值+得到的堆的价值）。
请注意，这是高效的，因为您只需要考虑前面的一步，而不需要探索一整棵树。
（这也可以进一步优化，因为堆栈中的所有值都可以忽略，除了本轮可以拿走的硬币、中心硬币和可能成为中心硬币的硬币。）
首先，让我们尝试找出如果两位玩家都表现最佳，将采取哪些 gems。 我们假设 gem 不是堆叠，而是假设 gem 排列成一行，玩家在他们选择的 gem 旁边做一个标记。
引理 5.1： 首先让我们证明，如果任何玩家选择，他们可以强制尽可能平均地分配所有筹码。为此，玩家只需模仿对手的动作，所有的筹码最终都会尽可能平均地分配。
基于直觉的假设是，如果两名球员都表现最佳，那么他们最终只会从自己的半场挑选 gem。我们只比较所有堆栈中的两个堆栈。所以我们会得到 3 个案例：
案例一：偶数和偶数
让我们使用 $2m$ 和 $2n$ gems 的两个堆栈，让 gems 编号为 $a_1,a_2。 ..,a_{2m} $和$b_1,b_2,...,b_{2n}$分别从左到右，玩家1从左边选择，玩家2从右边选择.
凭直觉，我们希望玩家能够完美平均地分配每一堆。所以让我们假设相反，最后，玩家 1 选择了 gems $a_1,a_2,...,a_m,...,a_{ m+k}$ 和 $b_1,b_2,...,b_{n-k}$ 并且玩家 2 选择了这两个堆栈中剩余的 gems。
从引理 5.1 中，我们知道任何玩家都可以强制拆分，但由于他们没有这样做，我们可以假设 gems 的值的总和来自 $a_{m+1 },...,a_{m+k}$ 和来自 $b_{n-k+1},...,b_n$ 是相等的，因为否则，这将意味着玩家没有最佳发挥。有可能数值是相等的，但是我们在玩的时候，为了简单起见，可以选择平分。
案例二：奇数奇数
让我们做与之前完全相同的事情，但两个堆栈有 $2m+1$ 和 $2n+1$ gems。所以最中心的 gem 是 $a_{m+1}$ 和 $b_{n+1}$。
让我们再次假设最后，玩家 1 选择了 gems $a_1,a_2,...,a_{m+1},... ,a_{m+1+k}$ 和 $b_1,b_2,...,b_{n+1-k}$ 并且玩家 2 选择剩余的 gems这两个堆栈。与前面的情况类似，$a_{m+2},...,a_{m+1+k}$ 和 $b_{n+1-k 中 gems 的值之和+1},...,b_{n+1}$ 必须相等，因为假设两个玩家都玩得最好。唯一的区别是在这种情况下，先走的玩家可以选择 $a_{m+1}$ 和 $b_{n+1}$ 之间的 gems 中较大的一个。因此，我们可以平分堆栈，只需要比较中心 gems.
案例 3：偶数和奇数
让我们做与之前完全相同的事情，但两个堆栈有 2m 和 2n+1 gems。所以堆栈 B 的中心 gem 是 b_(n+1)。假设玩家 1 首先选择。
假设玩家 1 最后选择了 gems $a_1,a_2,...,a_m,...,a_ {m+k}$ 和 $b_1,b_2,...,b_{n+1-k}$ 并且玩家 2 选择了这两个堆栈中剩余的 gems。与前面的情况类似，gems 来自 $a_{m+1},...,a_{m+k}$ 和来自 $b_{n+1-k+1 的值之和},...,b_{n+1}$ 必须相等。
同理，如果最终玩家1选择了gems $a_1,a_2,...,a_{m-k}$和$b_1,b_2,...,b_{n+1},...,b_{n+1+k}$，玩家2选择剩余的gems，然后gems 的值来自 $a_{m-k+1},...,a_m$ 和来自 $b_{n+2},...,b_{n+1+k }$ 必须相等。 所以为了简单起见，我们可以将每个堆栈分成两半。
因此，最佳策略（对双方玩家而言）是将 gem 的偶数堆分成两半，然后将所有 gem 的奇数堆排序s 根据其中心 gems 的值递减，然后第一个堆栈将被拆分，这样玩家 1（假设玩家 1 开始）获得中心 gem，第二个堆栈将是拆分使得玩家 2 获得中心 gem，并且奇数 gem 的第 $(2n-1)th$ 堆栈将与玩家 1 获得中心 gem 拆分, 奇数个 gem 的第 (2n)$ 个堆栈将分裂，玩家 2 获得中心 gem.
因此，如果我们先走，我们必须选择奇数个 gems 和最有价值的中心 gem 的堆栈，我们可以简单地镜像机器人的移动直到堆栈被删除，因为我们假设机器人也在最佳状态下运行。如果在你的回合中没有部分空的筹码，你应该选择一个奇数 gem 的筹码，当前最有价值的中心 gem.
让我们根据它们的中心 gem，从 1 到 $k$ 对所有具有奇数 gem 的堆栈进行降序排序和编号。
根据这个策略，如果两个玩家都玩得最好，假设玩家 1 先走，从顶部选择，
玩家1的分数=所有gem上半部分的所有gem的值之和，偶数gem+所有gem的值之和]s 位于奇数 gems 的堆栈的上半部分 { 如果堆栈编号为奇数，则包括中心 gem，如果堆栈编号为奇数，则不包括中心 gem堆栈编号为偶数}
玩家 2 的分数 = 剩余 gems
的值之和我认为这就是双方都采用（我认为的）最佳策略进行游戏的结果。