硬幣遊戲的最優策略

考慮一行n個值爲v1，v2 .......，vn的硬幣。我們通過輪流對抗對手進行比賽。在每一回閤中，玩家從行中選擇第一枚硬幣或最後一枚硬幣，永久移除它，並接收硬幣的價值。如果我們先行動，確定可能贏得的最大可能的金額。硬幣遊戲的最優策略

我的解決方案

既然我們先走了，我們既可以選擇V1和V2，然後我們的對手可以從一開始或從一開始就挑。因此可能出現四個子問題。

（1,1），（1,2），（2,1），（2,2）

其中（1,1）是指，我是從開始挑[即1]並且對手也從開始選擇[即1]。（1,2）表示我從開始選擇，但對手選擇最後一個。

因此，如果M(i,j)是我可以選擇的最大值（i，j），則表示（i，j）爲遞歸函數。

M(i,j) = Max{ Max{ M(i+2,j), M(i+1,j-1) } + vi, Max{ M(i+1,j-1), M(i,j-2) } + vj }

說明：當我有i..j元件，那麼我可以選擇第一個第[i + 1]，並且是，我的對手可以選擇或者第一第[i + 2]或最後一個[j-1]，並且我希望在下次挑選時擁有最大數量，因此是外部最大值內的第一項。

第二個與上面類似，即如果我選擇最後一個[j-1]，對手選擇第一個[i + 1]或者最後一個[j-2]，我下次將其最大化。

現在，我在書裏看到了遞歸作爲

M(i,j) = Max{ Min{ Same } + vi, Min{ Same } + vj }

現在，爲什麼我在這裏降到最低。這不等於說我第一次選擇最大化，但是我必須選擇第二次選擇最小化。

我在做什麼錯？謝謝。

來源

2013-08-01 Kraken

如果要計算，你可以肯定取勝，你必須假設你的對手是試圖最大限度地發揮他/她自己的結果，這相當於減少你（因爲總和的金額你的收益總是等於v1 + ... + vn）。你的公式計算的是如果你的對手總是從他/她的角度來看錯誤的話，你會贏得什麼。

來源

2013-08-01 08:45:51 Virgile

所以基本上我在計算的是什麼是我可以贏得的最大。但我需要找到我能贏的最低最高點。對？ – Kraken

是的，這就是要點。 – Virgile

如果硬幣的編號爲n是偶數，第一個玩家可以保證自己最大的v1 + v3 + ... + v（n-1）和v2 + v4 + ... + vn。找出哪個最大，然後採取v1或vn。此後，只需將原來分別位於奇數位置或偶數位置的硬幣取出。這是可能的，因爲無論第二位球員做什麼，當第一位球員再次移動時，奇數位置和偶數位置的硬幣都會暴露。

這是最好的第一個球員能做的嗎？首先玩家可以在任何移動中從「賠率」切換到「平均值」，具體取決於「新賠率」的總和是大於還是小於「新賠率」的總和。第二個球員的策略應該是保持儘可能低的轉換動機，即選擇最大的硬幣（第一個或最後一個位置）。由此產生的位置仍然誘惑第一位玩家轉換？是的，我們通過下面的遊戲中看到：

1 3 19 6 8 20

第一個球員加上1 + 19 + 8 = 28和3 + 6 + 20 = 29，他可以通過挑選找齊保證至少29的總得分， 20.結果是

1 3 19 6 8

爲了減少第一玩家的誘惑從找齊切換到賠率和做甚至比29的總成績，第二玩家需要8.

1 3 19 6

然而，誘惑依然存在。事實上，賠率位置的總和是1 + 19 = 20，平均值總和只有3 + 6 = 9，所以第一名玩家現在可以通過切換賠率做得更好，並且取1，儘管6更大。

3 19 6

最好第二玩家所能做的是挑選6，第一玩家得到19，第二玩家得到3.總得分：第一玩家20 + 1 + 19 = 40，第二玩家8 + 6 + 3 = 17

看起來第一個玩家總是能以這種方式獲得比第二個玩家更多的東西。但是，我們仍然不知道這是否是第一位球員的最佳策略。

在另一方面，如果硬幣的數目n是奇數，第一玩家和上述分析第二玩家的角色基本上相反。

現在問題變成了，上面列出的貪婪策略是否真的是最優？我們可以通過檢查二元決策樹來檢查特定情況，其中第一個玩家取第一個或最後一個硬幣，然後第二個玩家取第一個或最後一個剩下的硬幣等等。樹中會有2^n樹葉;可以計算每個葉子的得分，然後從葉子到根的工作，每個較高節點的值可以計算爲兩個孩子的最大值或兩個孩子的最小值，具體取決於它們是誰。

而是明確構建樹，可以隱含遞歸函數調用，這將節省所需的總內存，但不會節省時間建成。

如果有人分析這樣的比賽，並與我的不同的優化策略來了，我很希望看到它。

來源

2015-04-27 05:21:42

http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/

本頁面給出了問題的一個非常明確的解釋，也是解決方案。它的結論是：

 
F(i, j) represents the maximum value the user can collect from 
     i'th coin to j'th coin. 

    F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1)), 
        Vj + min(F(i+1, j-1), F(i, j-2))) 
Base Cases 
    F(i, j) = Vi   If j == i 
    F(i, j) = max(Vi, Vj) If j == i+1

來源

2016-06-18 03:50:54 WZL

的「最小化」那裏，因爲每個人都希望儘量減少硬幣的對手的總價值發生。所以，你應該假設你的組件已經採取哪些最小化後的總價值，當輪到你來選擇下一個硬幣的策略。 – WZL

硬幣遊戲的最優策略

回答

相關問題