4個攻城車對陣一個大螺絲,都不動,求獲勝概率?
為了讓不玩爐石的也懂,說明一下……
雙方玩家ab各30血,零以下就輸。a方場上4個攻城車【效果,我方回合開始時,隨機對一個敵方單位[包括玩家]造成兩點傷害。血量:4】,b方場上一個大螺絲【效果,我方回合結束時,隨機對一個敵方單位[包括玩家]造成8點傷害。血量:8】 a方先手時a的勝率?
b方先手時a的勝率?
直接算出來準確的數字估計還是有點難度的,不過,可以使用蒙地卡羅方法。
如果條件允許,題主不妨自己寫個程序跑一跑。
早上隨手一寫的。。可能剛起床不太清醒寫錯了,望指出……代碼:
a先手a勝大概93%,b先手a勝大概70%…… return dp[ahp][cn][bhp][ln][r][hf] = ret;#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:"&<&
動態規劃:
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;
}
}
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 |