有一个 2 人游戏,你有一个数字序列,例如:2 -6 12
. 可以说它们写在卡片上。
游戏需要时间轮流。每个回合玩家有义务从序列的开始或结束处拿走一张牌(不可跳过)。取完最后一张牌后游戏结束。目的是以尽可能高的正分数结束游戏(分数是玩家所拿卡上所有数字的总和)。我们也知道两个玩家都使用最优策略(最大化他们的收益)。我们必须说他们最终会达到什么分数。
知道最优策略是什么样子的吗?
到目前为止我的研究:
1-3 cards is trivial
{a}, no choice take a;
{a,b} take max(a,b) reduces to problem {a}
{a,b,c} take max(a,c) reduces to problem {a,b}
4 cards : {a,b,c,d}
if (a + max(c, min(b,d)) > d + max(b, min(a,c)))
take a;
else
take d;
如果我决定拿a
,我的对手拿 max(b,d) 就像 3 张牌策略说的那样,所以我要做的就是拿最大的c
(在对手转牌时是“安全的”),从b
,中取较小的d
牌,因为对手会需要更大的一个。双胞胎的情况d
。但我不知道如何扩展(如果可能的话)n-cards 案例。
有什么线索吗?