收集積分遊戲

Question

有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，我的對手取最大值（B，d）爲3卡戰略說，所以我要做的就是採取最大的c（這在對手轉牌期間是「安全的」），並且從b，d卡變小，因爲對手會拿更大的一張。與d孿生情況。但我不知道如何擴展（如果可能）n卡的情況。

任何線索？

Answer 1

//globals 
int[N] cards; 
int[N][N] v; //initialized to 0 
int[N][N] sum; // precomputed such that sum(i,j)=cards[i]+...+cards[j] 

void updateValue(int i,int j){ 
    int left=cards[i]+sum(i+1,j)-v(i+1,j); 
    int right=cards[j]+sum(i,j-1)-v(i,j-1); 
    v[i,j]=max(left,right); 
} 

void do(){ 
    for (int d=1;d<N;d++) 
     for (int i=0;i<N-d;i++) 
      updateValue(i,i+d); 
} 

答案將在[0，N-1]

人們可以通過該注意到以下提高內存的使用情況：如果我們看一下V作爲一個大方桌，我們填補其上三角形的一半。對於外部循環中的每個d值，我們填充從[0，d]到[N-d，N-1]的對角線。現在請注意，在填充此對角線時，我們只使用最後一個對角線的值，因此我們並不需要將所有以前的值保存在內存中。

Answer 2

乍一看，我記得我的Knackpack問題，但後來我意識到這是一個遞歸問題。你熟悉OCaml嗎？思考這個問題的方法是根據一組「功能」。

你需要從基本情況開始，並定義的基本功能：

e.g. f1(a) -> a 
    f2(x, y) -> max(x,y) 
    f3(x, y, z) -> max(f(x,y),z) 

然後你需要定義像下面的更復雜的情況：

if (a + max(c, min(b,d)) > d + max(b, min(a,c))) 
    take a; 
else 
    take d; 

這看起來像一個4輸入功能，您可以使用之前定義的最大值和最小值。 事情是這樣的：

f2 (a, b,c, d) -> if (a + max(c, min(b,d)) > d + max(b, min(a,c))) then true, else false 
f3(a, b,c, d) -> if(f2(a,b,c,d) then a else d 

你需要的，如果你需要定義你的「基本」功能F2，F3等，然後與其他功能的輸出替換輸入值。

我明白這不是一個解決方案，但希望是一個足夠好的提示，以遞歸的方式開始推理。

Answer 3

我認爲像這樣將工作：

int[] cards; 

int low = 0; 
int high = cards.length - 1; 

int bestScore(int low, int high) 
{ 
    if (low > high) 
    return 0; 

    // our best score is our immediate score minus the opponents best response 
    int lowScore = cards[low] - bestScore(low + 1, high); 
    int highScore = cards[high] - bestScore(low, high - 1); 

    if (lowScore >= highScore) 
    return lowScore; 
    else 
    return highScore; 
} 

int bestMove(int low, int high) 
{ 
    int lowScore = cards[low] - bestScore(low + 1, high); 
    int highScore = cards[high] - bestScore(low, high - 1); 

    if (lowScore >= highScore) 
    return low; 
    else 
    return high; 
} 

Answer 4

答案的情況下，該序列的長度爲偶數：

的第一個球員總是有一個戰略，不鬆動。關鍵的觀察是，如果第一個玩家願意，他可以在偶數地方收集所有數字，如果他願意，他可以收集奇數地方的所有數字。所以，他只需要事先檢查其總和更大：

如果序列{X_1，X_2，...，x_n}其中n = 2K

計算：A = X_1 + X_3 _... x_2k -1和B = x_2 + x_4 + ...+ x_2k

如果A> = B，則選擇x_2k開始，無論對手做什麼，第一個玩家總是可以爲某個i選擇x_2i。如果A < B，從挑選x_1開始並且無論對手做什麼，第一個玩家總是可以爲某個我選擇x_2i + 1。