用硬币游戏的算法

Question

让我们玩一个游戏：

连续有n堆硬币。第i个堆栈由d_i个硬币组成。两个玩家：玩家1，玩家2交替移动。轮到他的玩家只能拿第一个筹码或者最后一个筹码或者两个筹码。当没有硬币时，游戏结束。每个玩家最后都希望拥有尽可能多的硬币。玩家1开始。

我想知道算法（听起来像贪婪算法）来计算每个玩家在游戏结束时有多少硬币，当两个玩家都玩最佳。

我不知道如何处理这样的算法。只是猜测战略还是有一些方法来推断它？或者，实现一个算法可能太奇怪了？

实例（硬币堆叠从第一至第n）：

1，100，1 - 玩家有2枚至100个硬币分别（不幸的是第一玩家只能采取第一和最后一叠 - 第二玩家始终将用100个硬币堆栈）

1,1,100,1,1,5 - 玩家分别有8和101个硬币（我认为这是在最佳游戏之后 - 先取5和1，然后再取1来防止玩家1从100个硬币中获得堆叠，如果玩家1在第一步中获得的硬币少于6个，他将总是少于8个硬币）。

我希望我指出了足够的问题。你是否同意这很有趣？ :)任何人都可以帮忙吗？

Answer 1

如果仅存在范围a到b-1中的堆栈，则可以通过解决最佳策略的子问题，通过O（n^2）中的动态编程来解决此问题。

Python代码：

A=[1, 1, 100, 1, 1, 5] 
#A=[1, 100, 1] 

cache={} 
def go(a,b): 
    """Find greatest difference between player 1 coins and player 2 coins when choosing from A[a:b]""" 
    if a==b: return 0 # no stacks left 
    if a==b-1: return A[a] # only one stack left 
    key=a,b 
    if key in cache: 
     return cache[key] 

    v=A[a]-go(a+1,b) # taking first stack 
    v=max(v,A[b-1]-go(a,b-1)) # taking last stack 
    v=max(v,A[a]+A[b-1]-go(a+1,b-1)) # taking both stacks 

    cache[key]=v 
    return v 

v = go(0,len(A)) 
n=sum(A) 
print (n+v)/2,(n-v)/2 

这表示你的第二个情况下，最佳的游戏实际上是第一人采取只最左边1.从那时起，他可以保证，他将捕获100，所以他赢了。

（播放机1获得102，播放器2胜7）

有为O（n^2）子博弈所以这个算法需要时间为O（n^2）

的子博弈（和最佳的第一玩家/第二个玩家金币）是：

[1, 5] 6 0 
[1, 1] 2 0 
[1, 100] 101 0 
[100, 1] 101 0 
[1, 1] 2 0 
[1, 100, 1] 2 100 
[1, 1, 5] 6 1 
[100, 1, 1] 101 1 
[1, 1, 100] 101 1 
[100, 1, 1, 5] 105 2 
[1, 100, 1, 1] 101 2 
[1, 1, 100, 1] 101 2 
[1, 100, 1, 1, 5] 7 101 
[1, 1, 100, 1, 1] 102 2 
[1, 1, 100, 1, 1, 5] 102 7 

因此，举例来说，假设我们已经找到所有最佳剧本的小游戏，希望找到[1,1,100,1,1,5最好的发挥]。

我们所要做的是依次考虑每一个举动：

1. 拿第一栈，这会为我们赢得1，和离开游戏[1,100,1,1,5]这是我们从我们的子问题会知道赢得我们101共102.
2. 拿上一叠，这将赢得我们5，并离开游戏[1,1,100,1,1]这将只赢得了额外的2总共7。
3. 以两个堆栈，这会为我们赢得6，和离开游戏[1,100,1,1]这又只会让我们赢得了2个玩家，如果播放2最佳，共8

所以最好的举措是只采取第一个堆栈。

Answer 2

添加到@彼得动态规划的解决方案：

我觉得复发看起来有点像以下：

考虑硬币堆从A[i,..j]
令，dp[i, j]代表了最高分数PLAYER1都不可能得到。然后，

dp[i, j] = MAX { 
       MIN(dp[i+2, j], dp[i+1, j-1], dp[i+2, j-1]) + A[i], //Case when Player2 will try to make the most of it if Player1 picks ith coin. 
       MIN(dp[i+1, j-1], dp[i, j-2], dp[i+1, j-2]) + A[j], //Case when Player2 will try to make the most of it if Player1 picks the jth coin. 
       MIN(dp[i+2, j-1], dp[i+1, j-2], dp[i+2, j-2]) + A[i] + A[j] // Case when Player2 will try to make the most of it when Player1 picks both the ith and jth coins. 
       } 

由于只有N^2个可能的游戏状态。它可以通过填充大小为N^2的dp表来实现。

对于C++球迷：

#include<iostream> 
using namespace std; 
int Solve(int A[], int N, int **dp, int i, int j){ 
     if(dp[i][j] != -1) 
       return dp[i][j]; 
     if(j<i) 
       return 0; 
     else if(j==i) 
       return A[i]; 
     else if((j-i) == 1) 
       return (A[i] + A[j]); 
     else{ 
       int opt1 = min(Solve(A, N, dp, i+2, j), Solve(A, N, dp, i+1, j-1)); 
       opt1 = min(opt1, Solve(A, N, dp, i+2, j-1)); 
       int opt2 = min(Solve(A, N, dp, i+1, j-1), Solve(A, N, dp, i, j-2)); 
       opt2 = min(opt2, Solve(A, N, dp, i+1, j-2)); 
       int opt3 = min(Solve(A, N, dp, i+2, j-1), Solve(A, N, dp, i+1, j-2)); 
       opt3 = min(opt3, Solve(A, N, dp, i+2, j-2)); 
       int res = max(opt1+A[i], opt2+A[j]); 
       res = max(res, opt3+A[i]+A[j]); 
       dp[i][j] = res; 
       return res; 

     } 
} 
int main(){ 
     int N; 
     int A[N]; 
     cin >> N; 
     for(int i=0; i<N; ++i) 
       cin >> A[i]; 
     int **dp; 
     dp = new int* [N]; 
     for(int i=0; i<N; ++i) 
       dp[i] = new int[N]; 
     for(int i=0; i<N; ++i) 
       for(int j=0; j<N; ++j) 
         dp[i][j] = -1; 
     Solve(A, N, dp, 0, N-1); 
     cout << dp[0][N-1] << endl; 
     for(int i=0; i<N; ++i) 
       delete [] dp[i]; 
     delete []dp; 
     return 0; 
} 

此外，作为@Peter指出你的分析第二个例子是错误的。玩家1实际上有一个通过得分102硬币赢得比赛的策略。