N人決鬥問題演算法？
N個槍手命中的概率分別為0&
給定某組(P1,P2,...,PN), 如何計算每個人射擊時的對象選擇？為了方便說明，假設有10個人，他們命中的概率為1/20,3/20,5/20,...,19/20，計算出10個人都存活的時，輪到i號射擊時，他選擇的射擊對象？------------------------------------------------------------------------------------------------------N=3時這應該是一道流傳比較廣的題目吧。注意到如果某人沒有射中目標，那麼他存活的概率與他射擊的選擇無關，所以每個人只需要選擇哪個人死能最大化他存活的概率。
其實我很反感自己提問自己開一個回答補充信息。請把對問題的補充放到問題裡面。
你的答案里已經提到了問題的解法，但是我不知道你想繼續問的是你是不知道這個問題的演算法該如何實現還是你知道了演算法是什麼不知道用程序改怎麼寫？如果是第二個，你既然知道了演算法是什麼，那你描述一下你希望實現的演算法是什麼樣的，是實現哪一部分的時候遇到了困難？我先假設是前者。
這個問題是一個典型的MDP，需要用backward dynamic programming一步一步求就好了。
假設剩餘N個人的時候第一個人的存活概率是f_N(p1,p2,p3,...,pN)，那麼很顯然：1) 假如第一個人第一槍沒打中，在這個條件下第二個人的存活概率是 f_N(p2,p3,...,pN,p1)；2) 假如第一個人第一槍打第i個人打死了，那第二(或者三，如果第一槍打的是第二個人的存活概率是f_(N-1)(p2,p3,...,pi-1,pi+1,...,pN,p1)；3) 如果剩餘i-1個人的情況每個人的生存概率都求出來了，那麼對於N個人裡面任選i個人存活的情況下，每個人應該瞄準哪個人也是確定的(除非某個人瞄準兩個人存活概率相同，後面討論)，那麼i個人的存活概率可以列i個方程，這個方程組一定可以求出一組唯一的解；4) 只剩1個人的時候顯然 f_1(p)=1這個題目第一個不明確的地方是，假如第一個人殺死第二個人或者第三個人之後的存活概率相同，他該如何選擇。隨機殺一個，還是殺號碼小的？如果這個行為是依概率確定的，不管是均等概率隨機殺，還是固定殺號碼小的或者其他什麼規則，那這個問題是一個隨機馬爾可夫決策問題，一定有唯一組解。但是如果可以協商，那就變成了博弈問題，就未必有解，即使有解也未必唯一了。為了簡化起見，建議考慮均等概率隨機瞄準一個比較好，或者假定給出的條件不會出現這種情況。
------------------------------------------------------------------------------------首先，「如果剩餘i-1個人的情況每個人的生存概率都求出來了」是什麼意思，第j個人的生存概率指的是他先開槍時他的生存概率嗎？如果是，那麼這i-1個概率怎麼足夠確定i個人的時候每個人應該瞄準誰呢？其次，如果我的理解有誤，那麼假設「剩餘i-1個人的情況每個人的生存概率確定了」，且「i個人的時候每個人應該瞄準誰也確定了」，則有「那麼i個人的存活概率可以列i個方程」，你能否列出其中的一個方程？
假設有4個人a,b,c,d,命中率分別是pa,pb,pc,pd。
假設已經求出了a,b,c,d 中任意3個人存活時，輪到某一個人開槍時，每個人的存活概率。現在求剩餘4個人的情況。輪到a開槍時：
如果a瞄準b，那麼a的存活概率等於pa * (如果剩下c,d,a,輪到c開槍時a存活的概率) + (1-pa) * (如果剩下a,b,c,d,輪到b開槍時a存活的概率)如果a瞄準其他人，a的存活概率只有第一個括弧裡面的部分不一樣。所以a應該瞄準那個讓第一個括弧裡面概率最大的那個人。其他人同理。我們這裡不考慮可能有兩個最大的存活概率的情況。到這裡，我們可以求出四個人分別瞄準誰。
然後還是考慮輪到a開槍時的條件下，a的存活概率為：
(輪到a射擊時，a的存活概率) = pa * (a瞄準的人死亡，餘下的三個人輪到下一個人開槍時，a的存活概率) ＋ (1-pa) * (輪到b射擊時，a的存活概率)
(輪到b射擊時，a的存活概率) = pb * (b瞄準的人死亡，餘下的三個人輪到下一個人開槍時，a的存活概率) ＋ (1-pb) * (輪到c射擊時，a的存活概率)(輪到c射擊時，a的存活概率) = pc * (c瞄準的人死亡，餘下的三個人輪到下一個人開槍時，a的存活概率) ＋ (1-pc) * (輪到d射擊時，a的存活概率)(輪到d射擊時，a的存活概率) = pd * (d瞄準的人死亡，餘下的三個人輪到下一個人開槍時，a的存活概率) ＋ (1-pd) * (輪到a射擊時，a的存活概率)如果b,c,d中的某個人瞄準a，那麼等號後面第一個括弧裡面的值為0.然後把後面的等式往第一個等式裡面代，就能把四個概率都求出來了，然後b,c,d的存活概率同理。chao wang和劉曉的回答先入為主的引入了看似合乎直覺，但實際上是沒有根據的錯誤假設（第一名一定射擊第二名，第二名一定射擊第一名，不會攻擊比自己弱的對手，等等）
他們錯在哪？考慮四個人的情況，開槍順序為從低命中率到高命中率（反過來的情況類似，可以另行舉例）：- Case 1: 1號到4號命中概率分別為0.91，0.92，0.93，0.94. 此時3號會選擇射擊1號而不是4號. 理由：若4號死，則輪到剩餘的1號和2號射擊時他們會選擇射擊3號，3號此時存活概率小於(1-0.91)*(1-0.92)=0.72%. 若1號死，輪到4號時他會射擊3號，但若他miss, 則2號會射擊4號，這樣3號存活的概率大於(1-0.94)*0.92*0.93=5.1%.
這裡多說兩句，為什麼三號選擇射擊最差的1號而不是僅次於他的2號呢？舉個不那麼極端的例子，如果四個人的準度分別為0.6，0.7，0.85，0.9，三號該選擇射擊誰呢？在只剩三個人 p1，0.85，0.9且右邊的0.9先開槍的時候，中間那個人存活的概率隨p1的變化如下圖所示：
- Case 2: 1號到4號命中的概率分別為0.1，0.12，0.9，0.99. 此時3號會選擇射擊4號而不是2號. 分析類似上一段，略去. （直觀的說，這種情況下1號和2號的精度相比4號來說太低，因此即使兩人合在一起，對3號的威脅也遠遠小於4號一人，因此3號選擇射擊4號）
所以，射殺的對象不僅與精度的排序有關，還與具體的數值有關。
為了避免無謂的低級錯誤，可以先參考我很久前在MO上發的相同問題：game theory - Truel extended to n persons 那裡的回答者（現在已聯繫不上T_T) 計算出10人精度分別為1/20，3/20，...，19/20，按照從低到高的順序開槍時，瞄準的對象應該分別為8, 7, 5, 2, 9, 8, 3, 5, 5, 9. 即10人都存活時，第1名會射擊第2名，第2名會射擊第5名，第3名也射擊第5名，等等。方法：
Note that your probability of hitting your target doesn"t depend on who the target is, and the situation if you miss also doesn"t depend on who the target is. Thus your only concern is what happens if you hit your target. You shoot at the target whose death would give you the highest probability of being the survivor. These probabilities for all participants can be computed by "dynamic programming", starting with the case of only one surviving participant and working backwards.
他的思路無疑是正確的。遺憾的是，我不知道應該如何來定義問題的參數、變數和結構，使得它可以通過編程的方法實現。（當你嘗試用普通的遞歸來編程解決這個問題時，會發現需要specify的變數很快就會爆棚，並且結構會很複雜以至於intractable.）
當然，編程我是菜鳥，通過適當的定義，應該確實有適合的演算法來給出答案。希望高手給出思路。個人覺得會演變成捉對決鬥的問題。
從槍法最好的N開始推算，N肯定希望槍法次好的N-1儘早死亡，所以他肯定會優先射擊N-1。N-1知道N的想法，所以也會優先射擊N來儘早解除最大的威脅。這個時候N-2不會射擊他們兩個中的任何一方。為什麼？因為N和N-1互相在廝殺，不會對自己造成威脅。一旦N-2射擊他倆中任意一個成功，那麼N-2就會變槍法次好的人，馬上就會遭受此時槍法最好的人的攻擊（N或N-1）。所以N-2的最優策略是先射擊N-3，之後如果N-1和N都存活，那麼下一輪仍然對自己沒有威脅，如果其中一人死亡，那麼下一輪自己可以優先攻擊。N-3的策略就和N-1類似了，所以N-3和N-2會互相廝殺。同理可以退出所有人。
如果N為偶數，那麼所有人的最優策略都已推出。如果N為奇數，那麼槍法最差的1號將會落單。落單的1號如果射擊成功，那麼場面將會變成偶數個人，1號將會遭受槍法次差的人的攻擊，所以1號為了保證可能的威脅槍法最差，會射擊槍法好的人，長遠來看應該射擊槍法最好的N。
所以所有人的策略是，判斷自己是目前存活人中槍法排名第幾的人，假設排名為i，如果i是偶數，那麼射擊第i-1名，如果i是奇數，那麼射擊第i+1名，如果i是技術，且自己排名最後，射擊第1名。
博弈的推導並不嚴格，但直觀上來說感覺沒錯。感覺是個馬爾可夫鏈加extensive form game的問題啊 每個人開槍時的選擇只與當前活著的人的集合有關 這些集合間的轉換概率已定，那就可以用逆向遞歸找到自己的最優策略。。。其中馬爾可夫鏈的節點是剩下的人的集合和該出手的那個人的序號
槍手都最終希望剩下的對手槍法儘可能差，因此他們不會優先攻擊比自己弱的對手。設k是這一輪開搶者的槍法排位（由高到低），則他的最優選擇同k人決鬥問題一致。 k人決鬥問題，經過一定次數的射擊後總會轉化為k-n人決鬥問題（n為任意小於k的自然數）。這裡先明確一點，無論k取何值，對手的槍法越差，自己的生存概率越高。因此，槍手們會優先攻擊槍法最好的人，直到問題轉變為三人決鬥問題。這時，由於要考慮最終二人決鬥的先手，槍法最差的槍手可能會選擇放空槍。 以上推斷的概率我有空會去算一算。考慮的不太細緻，如有錯誤，歡迎指證。
推薦閱讀：