4個攻城車對陣一個大螺絲,都不動,求獲勝概率?

為了讓不玩爐石的也懂,說明一下……

雙方玩家ab各30血,零以下就輸。a方場上4個攻城車【效果,我方回合開始時,隨機對一個敵方單位[包括玩家]造成兩點傷害。血量:4】,b方場上一個大螺絲【效果,我方回合結束時,隨機對一個敵方單位[包括玩家]造成8點傷害。血量:8】 a方先手時a的勝率?
b方先手時a的勝率?


直接算出來準確的數字估計還是有點難度的,不過,可以使用蒙地卡羅方法。

如果條件允許,題主不妨自己寫個程序跑一跑。

早上隨手一寫的。。可能剛起床不太清醒寫錯了,望指出……
代碼:

#include&
using namespace std;
int zero(int x){
if(x&<0) return 0; else return x;} bool loseb(int b[]){return (b[0]==0)+(b[1]==0);} bool losea(int a[]){ bool s=0; for(int i=0;i&<=3;i++){s=s*(a[i]==0);} s=s+(a[4]==0); return s; } void a_attack(int a[],int b[]){ int x; for(int i=0;i&<=3;i++){if(a[i]&>0){
x=rand()%2;
b[x]=zero(b[x]-2);}
}
}
void b_attack(int a[]){
int x,m;
m=0;
int r[5]={0,0,0,0,0};
int s[5]={0,0,0,0,0};
for(int i=0;i&<=4;i++){ if(a[i]&>0) {
r[m]=a[i];
s[m]=i;
m++;
}
}
x=rand()%m;
r[x]=zero(r[x]-8);
a[s[x]]=r[x];
}
int main(){
int n=0;
cout&<&<"n="; cin&>&>n;
int awin=0;
int bwin=0;
int a[5]={4,4,4,4,30};
int b[2]={8,30};
srand((unsigned int)time(0));
for(int k=1;k&<=n;k++){ a[0]=4;a[1]=4;a[2]=4;a[3]=4;a[4]=30; b[0]=8;b[1]=30; for(int i=1;i&<=20;i++){ a_attack(a,b); if(loseb(b)){ awin++; break; } b_attack(a); if(losea(a)){ bwin++; break; } } /*for(int i=1;i&<=20;i++){ b_attack(a); if(losea(a)){ bwin++; break; } a_attack(a,b); if(loseb(b)){ awin++; break; } }*/ } cout&<&<"a wins:"&<&

a先手a勝大概93%,b先手a勝大概70%……


動態規劃:
1、定義狀態:
dp[i][j][k][l][m][n] = [31][5][31][9][30][5]
i = a方血量
j = a方剩餘車
k = b方血量
l = b方的拉格納羅斯剩餘血量
m = 已經開始了幾輪
n = a方的車子已經開始攻擊了幾次
2、狀態轉移:
羞於貼搓代碼,又懶得寫轉移過程,最後還是懶惰戰勝了羞恥心。

bint cal(int ahp, int cn, int bhp, int ln, int r, int hf = 0)
{
if (ahp &< 0)ahp = 0; if (bhp &< 0)bhp = 0; if (ahp == 0) { return dp[ahp][cn][bhp][ln][r][hf] = bint(0, 1); } if (bhp == 0) { return dp[ahp][cn][bhp][ln][r][hf] = bint(1, 1); } if (ln == 0) { return dp[ahp][cn][bhp][ln][r][hf] = bint(1, 1); } if (cn == 0) { return dp[ahp][cn][bhp][ln][r][hf] = bint(0, 1); } if(dp[ahp][cn][bhp][ln][r][hf].empty == false)return dp[ahp][cn][bhp][ln][r][hf]; if(r 1) { // b round int tn = cn + 1; bint ret = bint(0, 1); // -- hit face ret = ret + cal(ahp - 8, cn, bhp, ln, r + 1, 0) / tn; // -- hit car if (cn &> 0)
{
ret = ret + cal(ahp, cn - 1, bhp, ln, r + 1, 0) * cn / tn;
}
return dp[ahp][cn][bhp][ln][r][hf] = ret;
}
else
{
// a round
if (hf == cn)
{
return dp[ahp][cn][bhp][ln][r][hf] = cal(ahp, cn, bhp, ln, r + 1, 0);
}
bint ret = bint(0, 1);
// -- hit face
ret = ret + cal(ahp, cn, bhp - 2, ln, r, hf + 1) / 2;
// -- hit boss
ret = ret + cal(ahp, cn, bhp, ln - 2, r, hf + 1) / 2;

return dp[ahp][cn][bhp][ln][r][hf] = ret;
}
}

3、得到結果:
a先手勝率 = 1651550249 / 1769472000 ≈ 0.93335766
a後手勝率 = 4131607469 / 5898240000 ≈ 0.70048140
跟蒙地卡羅方法得到的結果很接近,八成沒錯了

PS:半年沒搞演算法了,看到這題手癢難耐,敲著敲著憶起昨日時光,不禁潸然淚下(大霧)……


python版

import random

def battle_on():
a={"own":30, "1":4, "2":4, "3":4, "4":4}
a_dmg = 2

b={"own":30, "1":8}
b_dmg = 8
for i in range(1000):
for j in range(len(a)-1):
target = random.choice(list(b.keys()))
b[target] -= a_dmg
if b["own"] &<= 0: return True if b[target] &<= 0: del b[target] for j in range(len(b)-1): target = random.choice(list(a.keys())) a[target] -= b_dmg if a["own"] &<= 0: return False if a[target] &<= 0: del a[target] cnt = 0; N = 10000 for i in range(N): if battle_on() == True: cnt +=1 print(cnt/N*100)

結果與 @王錚 相同。
如果是3個投石車還公平點,勝率分別是65%和30%


matlab版:

%4個投石車對陣大羅斯
%只考慮遠程隨機攻擊,不考慮肉搏。
N=10000;%隨機試驗的次數
result=zeros(2,2);
for krty=1:1:N%隨機試驗的次數

%a先手
a=[30,4,4,4,4];
b=[30,8];
win=0;%勝利結果
for k=1:1:1000%遊戲的回合數
%a動
for gcc=1:1:(length(a)-1)%攻城車的攻擊
pa=randi(2,1);%攻擊的目標
b(pa)=b(pa)-2;
if(min(b)&<=0)%b死了或者大羅斯死了,b都會輸 win=1;%a贏 break; end end if(win&>0)
break;
end
%b動
pb=randi(length(a),1);%攻擊目標
if(pb&>1)%死掉一個攻城車。
a=a(1:1:(length(a)-1));
else
a(1)=a(1)-8;
end
if(a(1)&<0) win=2;%b贏了 end if(win&>0)
break;
end
end
result(1,win)=result(1,win)+1;

%--------------------------
%b先手
a=[30,4,4,4,4];
b=[30,8];
win=0;%勝利結果

for k=1:1:1000%遊戲的回合數
%b動
pb=randi(length(a),1);%攻擊目標
if(pb&>1)%死掉一個攻城車。
a=a(1:1:(length(a)-1));
else
a(1)=a(1)-8;
end
if(a(1)&<0) win=2;%b贏了 end if(win&>0)
break;
end
%a動
for gcc=1:1:(length(a)-1)%攻城車的攻擊
pa=randi(2,1);%攻擊的目標
b(pa)=b(pa)-2;
if(min(b)&<=0)%b死了或者大羅斯死了,b都會輸 win=1;%a贏 break; end end if(win&>0)
break;
end

end
result(2,win)=result(2,win)+1;
end
result

結論:
a先手,a勝93.42%
b先手,a勝70.33%
關鍵在於,a只要幹掉大羅斯,a就一定勝了。而b每次只能最多幹掉一個攻城車,幹掉一個工程車不足以勝利。攻城車分散了b的火力。

如果換為3個攻城車,那麼:
a先手,a勝64.24%;b先手,a勝29.34%,b勝70.66%。


樓上各種秀代碼。。。表示我和同學試過然後投石車贏了。


投石車先手起碼可以砸四輪,總共砸的次數在10-16次,大螺絲被砸到四次輸了,概率還是很低的,而且還要考慮投石車有場攻。
粗略估計投石車先手勝率90%以上,後手勝率80%
等待高手程序蒙特卡洛模擬驗證


⊙▽⊙工程車不是每回合還能打一次么 要不要考慮3個砸中螺絲的情況


概率學的不行,但遊戲還是熟悉的。所以,對於投石車來說,贏的情況只有英雄存在的情況下打掉對面英雄或螺絲。而至少在前三輪,任何極端情況下,投石車組不可能直接GG。所以就前三輪來說,投石車總共會攻擊9到12次,其中四次攻擊到螺絲即可獲勝。具體怎麼算,這個等高手了:)


推薦閱讀:

大數定理的歷史是怎麼樣的?
怎麼看待實數系的連續性。從0到1之間任取一個實數,取到的值剛好是0.5的概率是0?
二胎政策會加重男女比例失衡嗎?
連續拋硬幣,遇到「正反反」停止和遇到「正反正」停止,兩種情況下拋硬幣的平均次數是否相同?
為什麼指數函數的值的前幾位數服從Benford"s Law?

TAG:數學 | 概率 | 概率論 | 爐石傳說Hearthstone |