如何計算一局三國殺所進行的回合數的數學期望？

以下最簡情形：

一副牌只含30張「殺」與15張「閃」的（標準包卡牌只留殺閃） 1v1對局 雙方武將均為五血白板 玩家皆理性且出牌策略相同（優先留閃） 每當雙方各出完一次牌後計一回合 當任意一方死亡時遊戲結束 該遊戲進行一局所進行的回合數的數學期望是多少？

附加題 若在以上的一副牌中加入8張「桃」 其期望又是多少？

=============================================================================

關於出牌策略

理性：玩家不會做出有殺時不出殺 有閃時不出閃的行為

策略：且不論優先留殺和優先留閃的優劣 這裡只是要保證雙方策略相同且全局一致 目前預設雙方都優先留閃

---

希望我的程序沒有bug了。。。

對於只有殺和閃的情況，期望回合數是24.6221

對於還有桃子的情況，有環，我明天嘗試用馬爾科夫過程搞搞。

思考題: 對於兩種情況，先手的勝率分別是多少?

第一問code

#include &
#include &
#include &

using namespace std;

const int kTotalAtt = 30;
const int kTotalDef = 15;
double C[100][100];

struct Player {
int hp;
int att;
int def;

// 響應殺
void TryDefense() {
if (def &> 0) {
--def;
} else {
--hp;
}
}

// 棄牌
void Discard() {
if (def &> hp) {
def = hp;
att = 0;
} else if (def + att &> hp) {
att = hp - def;
}
}

int64_t Hash() const {
return (hp * 10 + att) * 10 + def;
}
};

struct Status {
Player p1;
Player p2;
int att; //牌堆殺的數目
int def; //牌堆閃的數目

void Play1() {
if (p1.att &> 0) {
p1.att--;
p2.TryDefense();
}
p1.Discard();
swap(p1, p2);
}

int64_t Hash() const {
return ((p1.Hash() * 1000 + p2.Hash()) * 100LL + att) * 100LL + def;
}
};

map& g_table;

double f(Status s) {
if (0 == s.p1.hp || 0 == s.p2.hp) {
return 0;
}

int64_t h = s.Hash();
cout &<&< h &<&< endl; auto iter = g_table.find(h); if (iter != g_table.end()) { return iter-&>second;
}

double result = 1;

int starting_att = 0;
int starting_def = 0;
if (s.att + s.def &<= 1) { // 需要洗牌的情況 starting_att = s.att; starting_def = s.def; s.att = kTotalAtt - s.p1.att - s.p2.att; s.def = kTotalDef - s.p1.def - s.p2.def; } double tot_p = 0; for (int att = 0; att &<= 2; ++att) { int def = 2 - att; if (att &< starting_att || def &< starting_def) { continue; } double prob = (C[s.att][att] * C[s.def][def]) / C[s.att+s.def][2]; if (starting_att + starting_def &> 0) {
prob = (C[s.att - starting_att][att - starting_att] *
C[s.def - starting_def][def - starting_def]) /
C[s.att + s.def - starting_att - starting_def][2 - starting_att - starting_def];
}
if (s.att &>= att s.def &>= def) {
tot_p += prob;
Status t{s};
t.att -= att;
t.def -= def;
t.p1.att += att;
t.p1.def += def;
t.Play1();
result += f(t) * prob;
}
}

if (fabs(tot_p - 1) &> 1e-9) {
cerr &<&< "ERROR: " &<&< tot_p &<&< endl; exit(1); } g_table[h] = result; return result; } int main() { for (int i = 0; i &< 100; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j &< i; ++j) { C[i][j] = C[i-1][j-1] + C[i-1][j]; } } double tot_p = 0; double tot_result = 0; for (int att1 = 0; att1 &<= 4; ++att1) { int def1 = 4 - att1; Player p1{5, att1, def1}; for (int att2 = 0; att2 &<= 4; ++att2) { int def2 = 4 - att2; Player p2{5, att2, def2}; double p = (C[kTotalAtt][att1+att2] * C[att1+att2][att1] * C[kTotalDef][def1+def2] * C[def1+def2][def1]) / (C[kTotalAtt+kTotalDef][8] * C[8][4]); Status s{p1, p2, kTotalAtt - att1 - att2, kTotalDef - def1 - def2}; double result = f(s); tot_p += p; tot_result += p * result; } } cout &<&< "tot_p = " &<&< tot_p &<&< endl; cout &<&< "tot_result = " &<&< tot_result &<&< endl; }

第二問code (stack over flow)

#include &
#include & #include &

using namespace std;

const int kTotalAtt = 30;
const int kTotalDef = 15;
const int kTotalPeach = 8;
const int kMaxHp = 5;
double C[100][100];

struct Player {
int hp;
int att;
int def;
int peach;

// 吃桃子
void TryRecover() {
while (peach &> 0 hp &< kMaxHp) { --peach; ++hp; } } // 響應殺 void TryDefense() { if (def &> 0) {
--def;
} else {
--hp;
}
}

// 棄牌
void Discard() {
if (peach &> hp) {
peach = hp;
att = def = 0;
} else if (peach + def &> hp) {
def = hp - peach;
att = 0;
} else if (peach + def + att &> hp) {
att = hp - peach - def;
}
}

int64_t Hash() const {
return ((hp * 10 + att) * 10 + def) * 10 + peach;
}
};

struct Status {
Player p1;
Player p2;
int att; //牌堆殺的數目
int def; //牌堆閃的數目
int peach; //牌堆桃的數目

void Play1() {
p1.TryRecover();
if (p1.att &> 0) {
p1.att--;
p2.TryDefense();
}
p1.Discard();
swap(p1, p2);
}

int64_t Hash() const {
return (((p1.Hash() * 10000 + p2.Hash()) * 100LL + att) * 100LL + def) * 10 + peach;
}
};

map& g_table;

static int dep = 0;

double f(Status s) {
++dep;
int64_t h = s.Hash();
cout &<&< dep &<&< " " &<&< h &<&< endl; if (s.p1.att + s.p2.att + s.att &> kTotalAtt || s.p1.def + s.p2.def + s.def &> kTotalDef || s.p1.peach + s.p2.peach + s.peach &> kTotalPeach) {
cerr &<&< "ERROR" &<&< endl; exit(1); } if (0 == s.p1.hp || 0 == s.p2.hp) { return 0; } auto iter = g_table.find(h); if (iter != g_table.end()) { return iter-&>second;
}

double result = 1;

int starting_att = 0;
int starting_def = 0;
int starting_peach = 0;

if (s.att + s.def + s.peach &<= 1) { starting_att += s.att; starting_def += s.def; starting_peach += s.peach; s.att += kTotalAtt - s.p1.att - s.p2.att; s.def += kTotalDef - s.p1.def - s.p2.def; s.peach += kTotalPeach - s.p1.peach - s.p2.peach; } double tot_p{0}; for (int att = starting_att; att &<= 2; ++att) { for (int def = starting_def; def &<= 2; ++def) { int peach = 2 - att - def; if (peach &< starting_peach) { continue; } double prob = (C[s.att][att] * C[s.def][def] * C[s.peach][peach]) / C[s.att + s.def + s.peach][2]; if (starting_att + starting_def + starting_peach &> 0) {
prob = (C[s.att - starting_att][att - starting_att] *
C[s.def - starting_def][def - starting_def] *
C[s.peach - starting_peach][peach - starting_peach]) /
C[s.att + s.def + s.peach - starting_att - starting_def - starting_peach]
[2 - starting_att - starting_def - starting_peach];
}

if (s.att &>= att s.def &>= def s.peach &>= peach) {
tot_p += prob;
Status t{s};
t.att -= att;
t.def -= def;
t.peach -= peach;
t.p1.att += att;
t.p1.def += def;
t.p1.peach += peach;
t.Play1();
result += f(t) * prob;
}
}
}

if (fabs(tot_p - 1) &> 1e-9) {
cerr &<&< "ERROR: " &<&< tot_p &<&< endl; exit(1); } g_table[h] = result; --dep; return result; } int main() { for (int i = 0; i &< 100; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j &< i; ++j) { C[i][j] = C[i-1][j-1] + C[i-1][j]; } } double tot_p = 0; double tot_result = 0; for (int att1 = 0; att1 &<= 4; ++att1) { for (int def1 = 0; att1 + def1 &<= 4; ++def1) { int peach1 = 4 - att1 - def1; Player p1{5, att1, def1, peach1}; for (int att2 = 0; att2 &<= 4; ++att2) { for (int def2 = 0; att2 + def2 &<= 4; ++def2) { int peach2 = 4 - att2 - def2; Player p2{5, att2, def2, peach2}; double p = (C[kTotalAtt][att1+att2] * C[att1+att2][att1] * C[kTotalDef][def1+def2] * C[def1+def2][def1] * C[kTotalPeach][peach1+peach2] * C[peach1+peach2][peach1]) / (C[kTotalAtt+kTotalDef+kTotalPeach][8] * C[8][4]); Status s{p1, p2, kTotalAtt - att1 - att2, kTotalDef - def1 - def2, kTotalPeach - peach1 - peach2}; double result = f(s); tot_p += p; tot_result += p * result; } } } } cout &<&< "tot_p = " &<&< tot_p &<&< endl; cout &<&< "tot_result = " &<&< tot_result &<&< endl; }

---

用動態規劃的思想，定義期望E(甲殺,甲閃,乙殺,乙閃,現在是甲還是乙的回合,棄牌堆殺,棄牌堆閃)。依剩餘牌可求得摸到殺和閃的概率，進而寫出轉移方程。發現轉移方程無拓撲序，需要解方程。發現方程是稀疏的，可以迭代解。

---

這個我很久以前還真寫過一個小程序來驗證過。結果和 @管清文 不太一樣，結果是30個殺，15個閃，12個回合左右就可以分出勝負。

------

更新，我們的結論是相似的，只是計算回合的方法不一樣。

代碼分為兩個文件，libsoldier.py 如下：

import random

class CardDeck:
def __init__(self):
self.cards = ["D"] * 15 + ["K"] * 30
self.used_cards = []

def shuffle(self):
self.used_cards.extend(self.cards)
random.shuffle(self.used_cards)
self.cards = self.used_cards
self.used_cards = []

def issue_cards(self, number):
if len(self.cards) &< number: self.shuffle() issued_cards = self.cards[:number] self.cards = self.cards[number:] return issued_cards def to_used(self, card): self.used_cards.append(card) class Soldier: def __init__(self, name, card_deck): self.hand_cards = [] self.name = name self.deck = card_deck self.blood = 5 self.attack_flag = 0 self.defend_flag = 0 self.death_flag = 0 def draw(self, cards): self.hand_cards.extend(cards) def attack(self): # 攻擊，有殺出殺！ self.attack_flag = 0 if "K" in self.hand_cards: self.play("K") self.attack_flag = 1 # print(self.name + " kill") return self.attack_flag def defend(self): #防禦，有閃出閃！ self.defend_flag = 0 if "D" in self.hand_cards: self.play("D") self.defend_flag = 1 # print(self.name + " dash") return self.defend_flag def discard(self): #棄牌 if len(self.hand_cards) &<= self.blood: pass else: while len(self.hand_cards) &> self.blood:
if "K" in self.hand_cards: #先丟殺
self.play("K")
# print(self.name + " discard K")
continue
elif "D" in self.hand_cards: #再丟閃
self.play("D")
# print(self.name + " discard D")
continue

def action(self): # 回合
self.draw(self.deck.issue_cards(2))
# print(self.name + " hand cards are " + str(self.hand_cards))
self.attack()
self.discard()
# print(self.name + "huihe ends")
return self.attack_flag

def take_initial_cards(self):
self.draw(self.deck.issue_cards(4))

def play(self, card): #出牌
self.hand_cards.remove(card)
self.deck.to_used(card)

def check_health(self): # 扣血
if self.defend_flag == 0:
self.blood -= 1
else:
pass

def death_check(self): # 檢查是否死亡
self.death_flag = 0
if self.blood == 0:
self.death_flag = 1
return self.death_flag


然後是遊戲環節, play.py

from libsoldier import CardDeck
from libsoldier import Soldier

def game():
winner = ""
huihe_number = 0
new_deck = CardDeck()
new_deck.shuffle()
simayi = Soldier("simayi", new_deck)
zhugeliang = Soldier("zhugeliang", new_deck)
simayi.take_initial_cards()
zhugeliang.take_initial_cards()
while True:
if zhugeliang.action():
simayi.defend()
simayi.check_health()
huihe_number += 1
if simayi.death_check():
winner = "zhugeliang"
break
if simayi.action():
zhugeliang.defend()
zhugeliang.check_health()
huihe_number += 1
if zhugeliang.death_check():
winner = "simayi"
break
return winner, huihe_number / 2

sum = 0
win_rate = 0
for _ in range(1000):
winner, number = game()
sum += number
if winner == "zhugeliang":
win_rate += 1

print(sum/1000.0, win_rate/1000.0)


最後的結果是12.1305. 基本上是 @管清文 答案的一半左右，是不是我們對回合的定義不一樣？我是按照題主說的，兩個人都動一次，算一個回合。

先手優勢挺大，基本上是6:4開。

我當時測試的比樓主的還要複雜一些，因為我還測試了英姿 vs 閉月 vs 制衡 等等。總之其實只要沒有錦囊，出殺出閃都挺機械的，不太需要涉及到AI。

話說如果持續不斷的回答三國殺問題，會不會成為「三國殺話題的優秀回答者」 ？^_^

---

我對假設的一點小小疑問是不同的留牌策略是否會產生不同的結果？

---

先試試一個更簡單的問題：如何計算一盤國際象棋所進行的回合數的數學期望值？國際象棋里「理性出牌」可能更好定義一些，三國殺里「理性」就不是那麼容易界定了。

---

不知道有沒有多項式複雜度的解法。首先考慮暴力解法。假設牌只有30張殺，15張閃，出牌策略固定。牌局在哪一回合結束完全由殺和閃排列順序決定。洗牌相當於從45個位置中任意選出15個位置放閃，是一個組合問題，也就是說洗牌結果一共有C(45,15)種情況。寫程序將這些情況枚舉出來，算一下每種情況在哪一回合結束，取平均值即可。。。

可以對暴力解法進行剪枝。從第1個位置依次往後枚舉，當枚舉到某個位置n時，發現牌局可以在第m回合結束（直覺認為，n-2m &<= 2），那麼剩下的就不用枚舉了。可以根據還剩多少張殺和閃的數量算出當前情況對應多少種洗牌情況: C(45-n, 閃). 將所有的 m*C(45-n, 閃)/C(45,15) 相加就是回合數的期望。剪枝解法比暴力解法節省了一些枚舉的步驟數。

C(45,15)的規模64位計算機還能hold住。如果想對更大規模的問題進行求解，就增加機器，並行求解。

----------------------------------------------------------------

感謝評論 @卜奕 提醒，原答案沒有考慮抓完牌堆重新洗牌的問題，求出的實際是在45張牌之內能夠結束戰鬥的條件下的期望。現在考慮45張牌內不能結束戰鬥的情況。

設45張牌內能結束的概率是p, 結束時已經用掉的牌數為M (約等於回合數*2)，這兩個值都可以在第一輪模擬內求得。這裡規定，必須把手牌出完、且牌堆抓完後，才重新洗牌。那麼，第二輪45張牌的牌局分布情況跟第一輪45張牌的情況是一樣的。那麼如果戰鬥在第二輪結束，用掉的牌數期望是45+M。以此類推，總的用掉的牌數期望是：

最終求得

---

一直在學C++, 對三國殺也感興趣, 正好看到此題, 覺得有趣也試著寫了個程序來回答, 先說一下規則, 一個玩家從摸牌到棄牌算一回合, 因為如果兩個玩家各出完一次牌算一回合不能覆蓋一方在出牌階段把對方殺死的情況(理由是遊戲至此結束, 對方已經沒法出牌), 起手雙方先各摸4張牌, 不算入回合. 接著先手再摸2張牌, 進入對決, 此步算入回合. 利用蒙特卡羅模擬100000次, 取平均值, 算得回合期望為21.25次. 代碼如下:

#include &

using namespace std;

class Random {
public:
unsigned long long operator()()
{
liuting = liuting * (unsigned long long)25214903917 + 11;
return liuting;
}
private:
static unsigned long long liuting;
};
unsigned long long Random::liuting = 111;

Random amur_tiger;
int round_count = 0;

struct Card {
Card(int a, int d) : attack_size(a), defend_size(d) {}

int attack_size;//在場牌堆里的殺
int defend_size;//在場牌堆里的閃
int discard_att_size = 0;//棄牌堆里的殺
int discard_def_size = 0;//棄牌堆里的閃

int GetaCard();
};
int Card::GetaCard()
{
if (!(attack_size + defend_size)) {//場上牌堆沒牌後重置
attack_size = discard_att_size;
defend_size = discard_def_size;
discard_att_size = discard_def_size = 0;
}
if (amur_tiger() % (attack_size + defend_size) &< attack_size) { --attack_size; return 1;//1表示殺 } else { --defend_size; return 0;//0表示閃 } } class Player { public: Player(int h) : hit_point(h) {} void GetCard(Card card, int i);//i為取牌數量 void DisCard(Card card);//棄牌 bool Attack(); void Defend(); int hit_point;//血量 private: int att_size = 0;//手牌殺數量 int def_size = 0;//手牌閃數量 }; void Player::GetCard(Card card, int i) { while (i-- &> 0) {
if (card.GetaCard()) ++att_size;
else ++def_size;
}
}
void Player::DisCard(Card card)
{
if (att_size + def_size &> hit_point) {
if (def_size &> hit_point) {
card.discard_att_size += att_size;
card.discard_def_size += def_size - hit_point;
att_size = 0;
def_size = hit_point;
}
else {
card.discard_att_size += att_size + def_size - hit_point;
att_size = hit_point - def_size;
}
}
}
bool Player::Attack()
{
if (att_size) {
--att_size;
return 1;
}
return 0;
}
void Player::Defend()
{
if (def_size) --def_size;
else --hit_point;
}

bool Judge(Player player)
{
++round_count;
return player.hit_point;
}

void fight_round(Card card, Player att_player, Player def_player)
{
att_player.GetCard(card, 2);
if(att_player.Attack())
def_player.Defend();
att_player.DisCard(card);
}

int main()
{
int total_size = 0, test_size = 100000;
for (int i = 0; i &< test_size; ++i) { round_count = 0; Card card(30, 15); Player first(5), second(5); first.GetCard(card, 4); second.GetCard(card, 4); while (1) { fight_round(card, first, second); if (!Judge(second)) break; fight_round(card, second, first); if (!Judge(first)) break; } total_size += round_count; } cout &<&< (total_size * 1.0) / test_size &<&< endl; return EXIT_SUCCESS; }

---

已加入 探囊取物和釜底抽薪

代碼地址：Clovertjp/KillersOfThreeKingdom

求不要吐槽命名以及代碼太爛~~~~

(只有殺閃 棄牌規則是：殺 閃 )

每組樣本個數是10萬，結果和上面的一樣，順便統計了一下先手和後手的輸的次數

可以看出來先手有明顯優勢。

(只有殺閃 棄牌規則是： 閃 殺)

這是加入8個桃後的結果，棄牌規則是：殺 閃 桃

棄牌規則是：殺 桃 閃

棄牌規則是： 閃 桃 殺

棄牌規則是： 閃 殺 桃 代碼後面我上傳 github Java寫的，想要什麼人物，卡牌你們自己加，或者給我說，我加

---

推薦閱讀：