一個猜牌遊戲，是否有必勝策略？

01-03

有11張牌，上面分別寫著1~11。發給甲5張、乙5張，剩下的1張反蓋在桌上。雙方只知道自己有什麼牌。
由甲開始甲乙輪流進行下面操作之一：

宣稱一個數（若對方有該牌則要亮出）；

猜測桌上牌的數並翻開該牌（若對了則贏，否則輸，無論如何遊戲結束）。

問：誰有必勝策略？若無必勝策略，雙方的最優策略是什麼？在最優策略下，雙方獲勝概率是分別是多少？

占坑。。感覺是cf原題。。

來自Codeforces Beta Round #78 div1 E題：Problem - E - Codeforces

是把原問題強化一下變成 $n+m+1$ 張牌的情況。無必勝策略，但可以依據方法提高勝率。

設 $F[n][m]$ 為：自己手上還有n 張牌未公開，對手手上還有m 張牌未公開時的勝率。

若選擇直接猜答案：勝率為 $frac{1}{m+1}$

若選擇猜對手的牌： $frac{m}{m+1}$ 概率局面變為 $(n,m-1)$ ； $frac{1}{m}$ 概率沒有猜中，於是對手下一回合獲勝。因此綜合勝率為 $frac{m}{m+1} (1-F[m-1][n])$

於是有如下轉移方程： $F[n][m]=maxleft{ frac{1}{m+1},frac{m}{m+1}(1-F[m-1][n]) ight}$

這樣只考慮了無欺騙的情況。//我有這麼天真嗎？

可以斷言自己的某張牌是對方的，誘使對手下一回合猜錯輸掉；當然對手也會考慮到被欺騙的可能性。

當選擇第二種斷言時，自己有兩種策略：

策略a：斷言自己的某張牌是對方的

策略b：從 $m+1$ 張牌中隨機選一張

對手也有兩種策略：

策略1：相信對方挑的牌不在對方手上

策略2：除非對方挑的牌在自己手上，相信對方挑的牌就在對方手上

於是有四種情況：

情況a1：對方下回合直接輸掉，本方勝率為1。

情況a2：對方成功排除掉一張本方的牌，本方勝率為 $1-F[m][n-1]$ 。

情況b1：和之前的分析一樣，本方勝率為 $frac{m}{m+1} (1-F[m-1][n])$ 。

情況b2：有 $frac{m}{m+1}$ 概率猜中對方的牌，因此接下來的勝率仍然為 $1-F[m-1][n]$ ；有 $frac{1}{m}$ 的概率對方以為猜的牌是本方手牌，因此對方下回合一定無法取勝，於是再下回合本方取勝。本方綜合勝率為 $1-frac{m}{m+1}F[m-1][n]$ 。

既然是一個零和博弈的話，設對方相信的概率為 $p$ ，四種情況勝率為 $p_{a1} =1$ , $p_{a2} =1-F[m][n-1]$ , $p_{b1} =frac{m}{m+1} (1-F[m-1][n])$ , $p_{b2} =1-frac{m}{m+1}F[m-1][n]$ ，則根據納什均衡解方程，當 $p_{a1} imes p+p_{a2} imes(1-p)=p_{b1} imes p+p_{b2} imes(1-p)$ 時本方勝率最大，則 $F[m][n]=p_{a1} imes p+p_{a2} imes(1-p)$ 。//update 2015.8.6

我覺得這真是個鬥智斗勇的遊戲啊。

我只能分析前幾層，無法給出定量的分析。

對於遊戲的任意一方，他的目標是，確定不在自己手裡的6張牌中哪一張是底牌。為了縮小範圍，他可以進行的操作就是報一張不在自己手裡的牌。如果這張牌在對方手中，就縮小了範圍；如果這張牌不在對方手中，那麼他就知道這張牌是底牌，下一回合就是可以揭底牌了。
但是，如果對方知道自己採用這種策略，那麼一旦自己報的牌不在對方手中，對方就可以搶先知道報的牌是底牌了。
為了避免這種情況，就需要在適當的時候「虛晃一槍」，報一張自己手中的牌。如果對方沒有想到你會報自己的手牌，就會立即猜測這張牌是底牌，從而輸掉。
現在假設對方也想到了你可能報自己的手牌，所以你報的牌如果不在對方手中，那麼就是沒有信息量的。但報自己的手牌也不能為自己縮小範圍，屬於「損人不利己」的行為，應當少做。
所以正確的策略應該是以報手中沒有的牌為主，偶爾報一張手中有的牌。但對方就也可以通過觀測來估計你做出兩種行為的概率，如果能以比較大的概率確定底牌，就可以放手搏一把。
……

這個問題很有意思，結構化一下，慢慢更新：

- 討論簡化情形

- 討論boundary condition

- 通用的情形

- 猜牌的選擇

- 宣稱牌的選擇

1. 討論簡化的情形

三張的簡化情型討論比較簡單一點。假設勝利的payoff是1，輸的payoff是-1.

1. 甲選擇直接猜牌，期望payoff 是0

2. 甲選擇宣稱牌，無論宣稱自己的牌是對方的牌，乙的最佳對策是直接選擇猜牌，期望payoff也是0。

a.- 甲宣稱自己牌，乙沒有翻牌。

b.- 甲宣稱其他牌，乙翻牌。

c. - 甲宣稱其他牌，乙沒有翻牌。

乙有兩種不同的觀測。

- b情形下，乙可以獲知甲已經知道全部信息可以在下輪直接獲勝，所以乙會選擇猜牌應對，期望payoff 0。

- a,c的情形下，乙可以知道甲如果在下一輪猜牌，猜中的概率大於等於1/2 （a情形，概率=1/2，c情形，概率等於1），乙的最佳對策也應該是直接猜牌。

綜上所述，在考慮單局遊戲的情形下，甲採用任何策略，乙的最佳對策都是直接猜牌。

2. Boundary condition: 什麼時候採取直接猜牌是最好的對策

當你排除掉k張牌之後,那麼你猜中牌的概率是1/（m+n+1-k），採用前面簡化情形的假設，檔m+n-k&>1的時候，你的期望為負。但是期望為負並不是是否採用猜牌策略的決定條件。決定條件應該是比較選擇猜牌的期望收益和選擇不猜牌的其他策略的期望收益。

一個簡單的例子，當你的手牌為空，對手已經獲取了所有信息，那麼對手下一盤一定猜牌，而且必然猜中。此時你如果不選擇猜牌，你的期望收益為-1，那麼即使你直接猜牌猜中的概率小於1/2，期望為負，選擇直接猜牌依然是更好的選擇。

下面我們記遊戲為G(m,n,k),m，n為雙方（甲，乙）的手牌數量，k為公共牌數量。同樣我們先只看k=1的情形。那麼根據前一段舉得例子，我們有：

1. 甲輪，G（0，n, 1）情形，甲的最佳策略是猜牌；

2. 同樣，乙的輪次，G（m，0, 1）情形，乙的最佳策略是猜牌；

考慮單個回合裡面，雙方都有三個策略可以選擇：1.猜牌，2，宣稱自己的手牌 (B)，3，宣稱其他的牌 (V)。

因為猜牌會直接進入evaluation階段，先不討論。

其中宣稱自己的手牌和宣稱其他的牌是對手沒有辦法直接觀測出來的。

- 假設遊戲開始之前，你對對手採用宣稱自己手牌的概率有一個主觀的判斷記為p0 = p(B)，相應宣稱其他牌的概率為（1-p0）

- 每回合對手宣稱牌後，你都可以更新自己對這個概率的判斷。對手宣稱牌的時候，你會出現兩種不同的observation

- 你翻出來一張手牌，記為O（m，n，R）, m為對手當前手牌數目，n為自己當前手牌數目。相應你更新的概率為p (B|O(m,n,R)),因為你翻牌，所以你知道對手一定宣稱的不是他自己的手牌。此時雙方猜中底牌的概率是確定的：

- 己方的概率為1/（m+1）；

- 對手猜中概率為1/（n+1）；

除了之前討論的幾個情形，m，n中有一個為0，或者是m，n=1，都不會選擇直接猜牌。

- 你沒有翻出牌，記為O（m，n，U），概率更新為p1 = p（B|O(m,n,U)），這個情形下就很有意思。因為你的決定取決於你主觀的判斷。這是因為：

- 如果你判斷對手是在宣稱其他的牌，那麼他宣稱而沒有翻的牌就是公共牌，應該直接猜這張牌；

- 如果你判斷對手在宣稱自己的牌，那麼其實你也是會獲取到一些信息（基於主觀判斷的）：對手手中有這張牌。那麼你選擇繼續宣稱牌的時候可以避開這樣牌。

所以，如果p1&<1/2, 可以直接選擇猜牌。如果p1&>=1/2, 你應該繼續宣稱牌，並且宣稱他沒有宣稱的其他牌。

而此時你可以發現，這個observation其實轉移了「信息」，對手可以根據O的情形更新他的判斷, 而O（m，n，U）的觀測對宣稱者有利，因為宣稱者通過翻出來的牌獲取了有效的信息，對方卻沒有。O（m，n，R）的觀測需要基於你的track record，如果你不能很好的迷惑對手，這個情形反而是不利的。

覺得越來越像德撲了哈，所以你的策略實際上分成了兩個部分：

- call bluff：是否選擇猜牌：基於對手策略的主觀判斷；

- bluffing ：宣稱自己的牌和其他的牌的概率調整:

甲有必勝策略啊：直接宣稱一個自己有的數即可。

第一感覺是這樣：我猜的時候，從所有未翻開的牌里隨機選一個來報。這樣，如果選出來的不是我的牌，根據對方翻牌與否，我就收穫了信息。但是，不管有沒有收穫信息，我肯定沒有泄露任何信息，因為我選擇的牌是隨機的。即使對方完全清楚我的策略也沒用。

假設對方也是同樣的策略，那麼獲勝概率可以寫一個遞推公式來算。

這個策略不是最優。例如，或許可以調整隨機數生成器，讓它稍傾向於不在我手上的牌。因為不再是完全均勻的隨機，我會泄露一點信息，但有更大的概率選中外面的牌，所以更大概率獲得信息。

每輪一定機會獲得收益，自己不會露出破綻，也不會利用對方的破綻，還挺好玩的吧。

這題蠻有意思的。把情況簡化成三張牌的情況去分析。

平衡在於：

信息上有主動權的一方（比如我已經知道了底牌），在行動上卻是劣勢的（我無法翻牌，行動權在下家）。

假設甲報了一張牌，那麼下家面臨兩種情況，一是：甲知道了底牌，乙不知底牌，且乙不知甲是否知道了底牌。二是，甲不知底牌，乙也不知，且乙不知甲是否知道。

如果這個循環繼續，該甲行動的時候，他還是面臨這個問題：對手是否知道了底牌是0.5的概率。

因為如果我知道對手知道了底牌，我一定會翻牌，不能讓對手贏嘛。

推導了幾輪之後，我發現：循環在一個地方必須被打破，即：經過連續兩輪報出自己手上的牌之後，第三輪開始報牌的時候，必須報不是自己手上的兩張牌中的一張。

這時就出現了一種情況：比如這輪該甲猜了，他猜了一張不是自己手上的牌，那麼這時，甲知道了底牌是什麼，同時，乙雖然不知道底牌是什麼，但是乙知道了甲知道了底牌。所以這時候他一定會隨機翻牌。

我的結論是，最終博弈的結果就是：由於規則限制，在信息上佔有主動權的一方，在行動上並沒有主動權。所以導致最終的結果是，我即使有信息優勢（比如我知道了底牌），卻不能翻牌。而對另一方而言，雖然信息上略有劣勢（也不是完全沒有信息。只是我不知道底牌是什麼，但我知道你知道了），必須把結果弄成隨機的，即50%的概率。

回頭想想，期貨市場的博弈不也是這個樣子的嗎？一旦一個信息成為公共知識，即：不僅我知道，你知道，而且：我知道你知道，你也知道我知道。甚至：我知道你知道我知道，你也知道我知道你知道···。這時這個信息才會完全反映到價格里去。

利用規則漏洞。當對手喊出一張你沒有的手牌。輪到你的回合，喊出同一張，快速觀察有對手沒有亮牌的動作趨勢，若無，則快速打開那張牌。

如果甲使用了最優策略，而乙知道甲會使用最優策略從而基於此使用最優策略，而甲又知道乙會根據自己的最優策略來產生自己的最優策略從而甲又改進自己的最優策略，而乙又……好像找人打牌

我覺得最優策略就是讓對方摸不清自己的套路

最優就是把對方的牌在你的牌之前亮完。或者是知道，一旦有一方牌被知道，肯定下一個就能猜到底牌。而且你自己叫自己的這個方案幾乎是坑死自己的，

帶概率的問題怎麼會有必勝策略呢。。

我一次就猜對了你拿我沒辦法呀~

如果求最優解寫出零和博弈的Value矩陣然後求均衡點吧喵~

這題想過想到我可以詐騙對方的時候我就直接放棄了orz

簡化為一共三張即可…沒有必勝策略