[G 家 onsite 题] 探讨 Stone Game (LC877) 的扩展：3 个 player 的 Stone Game

Stone Game 大家应该很熟悉了，这里简单说一下：

有 N 堆石头排列成一排，用数组 piles[0, ..., N-1] 表示，piles 代表第 i 堆石头的个数。两个玩家轮流从 piles[] 里拿石头，每次可以拿 1、2 或 3 堆（不能不拿，且如果拿了某堆，就要把该堆石头全部拿走）。最终当 piles 被拿完时，石头总数多的一方获胜。

两个玩家时，是零和游戏，所以可以用 DP + Minmax 的方式解决。但是当三个玩家时候（其它规则不变，游戏顺序：玩家 1、玩家 2、玩家 3），应该怎么解这道题呢？

G 家 virtual onsite 时候遇到了这个题（三人），lz 没解出来。

补充内容 (2020-11-26 00:47):
补充一下：忽略一个细节，和 LC 原题不一样的是，只能从头拿：

拿 piles[0]
拿 piles[0], piles[1]
拿 piles[0], piles[1], piles[2]

愤怒的小蚯蚓 发表于 2020-11-25 11:24
我去....三个人？

补充内容 (2020-11-25 11:25):

我也是这么觉得，因为不再是零和了。

愤怒的小蚯蚓 发表于 2020-11-25 11:55
还是零和，只是 是 多方的零和博弈...

补充内容 (2020-11-25 11:56):

这么说也对，但是多方的话确实不知道应该如何下手。

三个player每人max自己的score应该就可以了吧，三维dp或者recursion with memorization

a(i,j) -> (score_a, score_b, score_c) : max score a can achieve if a starts picking a pile in the current settings
b(i,j) -> (score_a, score_b, score_c) : max score b can achieve if b starts picking a pile in the current settings
c(i,j) -> (score_a, score_b, score_c) : max score c can achieve if c starts picking a pile in the current settings

a(i,j)计算方法：
if i ==j:
    a(i,j) = (piles[i],0,0)
else:
    ah,bh,ch = b(i+1,j)
    at,bt,ct = b(i,j-1)
    if ah+piles[i] >  at+piles[j] or ah+piles[i] ==  at+piles[j] and max(bh,ch)<=max(bt,ct):
        a(i,j) = (ah+piles[i], bh,ch)
   else:
        a(i,j) = (at+piles[j], bt,ct)
把a(i,j)存一下加速计算。
要考虑break tie的情况因为现在有3个人，取头尾都一样的话应该取让除了当前player之外的最高的那个人少拿的case

补充内容 (2020-11-26 02:07):
a(i,j)意思是现在轮到a来拿，piles现在可以拿的pile是从i到j的这些piles

只能从头尾拿？

FightForLife 发表于 2020-11-26 00:34
只能从头尾拿？

抱歉忽略了这个细节，只能从头拿

- 拿 piles[0]
- 拿 piles[0], piles[1]
- 拿 piles[0], piles[1], piles[2]

wmy5 发表于 2020-11-26 00:48
抱歉忽略了这个细节，只能从头拿

- 拿 piles[0]

dp[\i][who_choose_now] => tuple<int, int, int>, 表示 who_choose_now 这个人做出最优选择之后三人的石头数。

dp[\i][0]会拿
argmax{
1. pile[\i] + get<0>(dp[i+1][1])
2. pile[\i] + pile[i + 1] + get<0>(dp[i+2][1])
3. pile[\i] + pile[i + 1] + pile[i + 2] + get<0>(dp[i+3][1])
}
个pile。

看看行不行，还能不能优化。

愤怒的小蚯蚓 发表于 2020-11-26 00:17
i, j 代表的是什么意思？

小于i的或者大于j的pile都已经被拿过了。可以接着拿的是剩下的i到j这些piles。（piles[i:j+1]）

FightForLife 发表于 2020-11-26 01:15
dp[\i][who_choose_now] => tuple, 表示 who_choose_now 这个人做出最优选择之后三人的石头数。

dp[\i ...

觉得比较靠谱，关键是 dp value 是 tuple。

有三个玩家的话，也许会出现这个情况: 玩家1的两个option的自身max石头数相同，但玩家2和玩家3的max将会不同(假设他们的max都低于玩家1)，那这时玩家1的选择是什么？会影响后续dp