用硬幣遊戲的算法

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硬幣贏得比賽的策略。