달무티 CPU 플레이어 만들기 Part 3: 수 평가와 전략적 패스

이 글은 Claude Opus 5 를 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.

재료에서 결정으로#

Part 1에서 공정성 경계와 결정적 easy 봇을 만들었고, Part 2에서 hard 봇의 정보 모델을 세웠습니다. 지금까지 확보한 재료는 셋입니다.

• Ledger — 공개 정보만으로 만든 오차 0의 카운팅 장부, 그리고 패스를 확정 배제가 아닌 확률적 증거로 다루는 좌석 모델
• StructurallySafe 와 SeatBeatRisk — 어떤 수가 받힐 수 있는지에 대한 구조적 참/거짓 판정과 확률 추정
• BestPlan — 손패를 최소 몇 번에 털 수 있는지, 광대 두 장을 어느 묶음에 붙일지의 플랜

Part 3 에서는 이 재료로 실제 결정 을 내립니다. 후보를 점수로 환산하고, 낼 수 있어도 참는 판단을 구현하고, 세금과 혁명을 기대값으로 계산한 뒤, 만든 봇이 정말 세졌는지 재는 방법까지 다룹니다.

앞의 두 편과 마찬가지로 이 글은 설계안이고 코드는 논지를 보이기 위한 발췌입니다. 룰셋 전제는 Part 1 의 전제표를 그대로 따르는데, 이 편에서 결정적인 한 가지만 다시 적어 두겠습니다.

달무티에서 패스는 트릭 포기가 아닙니다. 패스해도 자기 차례가 다시 오면 낼 수 있고, 살아 있는 전원이 연속으로 패스해야 트릭이 끝납니다.

“한 번 패스하면 그 트릭에서 빠진다"는 감각을 그대로 들고 오면 아래의 리드권 계산이 통째로 틀어집니다. 여기서 다루는 거의 모든 판단이 이 한 줄 위에 서 있습니다.

1. 수 평가 함수#

이제 재료가 모였습니다. 후보 하나를 점수로 환산합니다.

type HardPolicy struct {
	W Weights
}

type Weights struct {
	Plan     float64 // 손패 구조 개선도
	Control  float64 // 리드권 확보 가치
	Tempo    float64 // 상대 진행 위험
	InfoLeak float64 // 혁명 선언의 정보 노출 비용
	Rivalry  float64 // 누적 점수 경쟁 가중치
}

// score 는 후보 c 를 냈을 때의 점수다. c 가 nil 이면 패스를 뜻한다.
func (p *HardPolicy) score(v GameView, l *Ledger, c *Candidate) float64 {
	planGain := 0.0
	if c != nil {
		before := BestPlan(v.Hand, l)
		after := BestPlan(removeCards(v.Hand, c.Cards), l)
		planGain = float64(before.MinPlays-after.MinPlays) +
			0.5*(after.SafeLead-before.SafeLead) -
			float64(after.Orphans-before.Orphans)
	}

	// 제출은 이 트릭을 즉시 가져오는 가치, 패스는 나중에 다시 낄 선택권의 가치.
	control := p.continuationValue(v, l)
	if c != nil {
		control = p.controlProb(v, l, c) * p.controlValue(v, l, c)
	}
	tempo := p.tempoRiskAfter(v, l, c)

	return p.W.Plan*planGain + p.W.Control*control - p.W.Tempo*tempo
}

패스를 c == nil 로 같은 함수에 태운 것이 핵심입니다. 이렇게 하면 “제출과 패스를 어떻게 비교할 것인가"라는 문제가 사라집니다. 점수를 이루는 항은 플랜 개선도·리드권·템포 세 개인데, 리드권 항이 제출과 패스에서 다르게 계산되므로 이어지는 네 절에 나누어 보겠습니다.

리드권은 “전원 연속 패스"로만 돌아온다#

여기가 “패스=탈락” 감각을 그대로 옮기면 안 되는 지점입니다. 패스한 사람이 그 트릭에서 빠지는 변형 룰이라면 “내 뒤 순번이 전부 패스하면 리드권"이므로, 마지막 순번에서 낸 수는 그대로 리드권이 됩니다. 공식 룰은 다릅니다. 패스한 사람도 다시 낼 수 있으므로, 리드권은 살아 있는 전원이 연속으로 패스해야 돌아옵니다. 이미 패스한 좌석을 계산에서 빼면 안 됩니다.

// controlProb 는 이 행동 이후 트릭이 나에게 돌아올 확률이다.
// 달무티는 패스한 좌석도 다시 낼 수 있으므로, 이번 트릭에서 이미 패스했는지와
// 무관하게 "아직 손패가 남은 모든 상대" 를 대상으로 계산해야 한다.
func (p *HardPolicy) controlProb(v GameView, l *Ledger, c *Candidate) float64 {
	if c == nil {
		// 패스는 이 트릭을 "즉시" 가져오지 못한다.
		// 다시 낄 선택권의 가치는 continuationValue 에서 따로 센다.
		return 0
	}
	bar := Play{Rank: c.Rank, Count: v.Table.Count}

	prob := 1.0
	for _, s := range l.ActiveOpponents() {
		canBeat := l.SeatBeatRisk(s, bar.Rank, bar.Count)
		// 받을 수 있어도 참을 수 있다. 참을 확률만큼은 나에게 유리하다.
		willBeat := canBeat * (1 - l.holdPropensity(s))
		prob *= 1 - willBeat
	}
	return prob
}

이 룰의 실전적 함의가 큽니다.

• 자리 순서는 리드권 확보 확률을 거의 바꾸지 않습니다. 어차피 전원이 한 번씩 더 기회를 갖기 때문입니다. 늦은 순번의 이점은 리드권이 아니라 정보 입니다. 그 트릭에서 남들이 어떻게 행동했는지를 보고 두게 됩니다.
• 리드권 회수가 어려운 만큼 확실승수의 값어치가 큽니다. StructurallySafe 가 true 인 수만이 리드권을 확실히 보장합니다. 나머지는 전부 확률 곱셈이고, 좌석이 여덟이면 곱셈 항이 일곱 개라 값이 빠르게 0에 가까워집니다.
• 패스가 싼 게임입니다. 패스해도 이번 트릭에서 완전히 빠지는 것이 아니므로, 참는 선택의 기회비용이 낮습니다. 뒤의 전략적 패스가 자주 정답이 되는 구조적 이유입니다.

좌석별 확률을 곱한 것은 독립 가정 근사 이고, 여기에는 서로 반대 방향으로 작용하는 오차가 두 개 들어 있습니다.

첫째, 좌석 사이의 음의 상관을 무시합니다. 상대들은 같은 덱을 나눠 가지므로, 한 좌석이 강한 카드를 몰아 쥐었다면 다른 좌석은 그만큼 약합니다. 이 상관을 무시하면 “아무도 못 받을 확률”, 즉 리드권 확보 확률을 과대평가 합니다. 실제 딜을 돌려 재어 보면 이렇습니다.

6명 게임의 4장 리드는 실제보다 거의 두 배로 낙관하게 됩니다. 확률이 0이나 1에 가까울수록 오차가 줄고, 중간 구간에서 가장 커집니다.

둘째, 좌석 하나의 위험 자체가 이미 과대평가되어 있습니다. Part 2 의 SeatBeatRisk 는 rank 별 확률을 Boole 상한으로 단순 합산하므로 실제보다 큰 값이 나옵니다. 그만큼 1 - willBeat 가 작아지고, 리드권 확률은 반대로 과소평가 됩니다.

두 오차가 서로 반대로 작용하므로 최종 편향의 방향은 일반적으로 보장되지 않습니다. holdPropensity 까지 곱해지면 더 그렇습니다. 후보 간 순서를 정하는 용도로는 견딜 만하지만, 이 값을 절대 확률로 취급하거나 사용자에게 그대로 표시하는 용도로 재활용해서는 안 됩니다. 정확한 값이 필요하다면 좌석과 rank 의 배타성을 함께 반영한 다변량 초기하로 가거나, 아예 결정화 시뮬레이션으로 추정해야 합니다.

리드권의 가치는 내 플랜에 달려 있다#

// controlValue 는 리드권을 잡았을 때 열 수 있는 최선의 묶음 가치다.
func (p *HardPolicy) controlValue(v GameView, l *Ledger, c *Candidate) float64 {
	hand := v.Hand
	if c != nil {
		hand = removeCards(hand, c.Cards)
	}
	best := 0.0
	for _, g := range BestPlan(hand, l).Groups {
		safety := 1 - l.BeatRisk(g.Rank, g.Count())
		// 장수가 클수록, 안전할수록 값지다.
		if val := safety * float64(g.Count()); val > best {
			best = val
		}
	}
	return best
}

지난 글에서 “리드권은 조합을 강제하는 권리"라고 정리했는데, 그 문장이 코드로는 이렇게 나타납니다. 리드권의 가치는 절대값이 아니라 내 손패 구조에 대한 함수 입니다. 12를 여섯 장 쥔 봇에게 리드권은 판을 끝낼 열쇠지만, 손패가 rank 별로 한 장씩 흩어진 봇에게는 별 값어치가 없습니다. 그래서 흩어진 손패의 봇은 리드권을 사기 위해 강한 카드를 소모하지 않는 것이 옳고, 이 함수가 그 판단을 자동으로 만들어 냅니다.

c 를 제거한 뒤의 손패로 계산한다는 점도 중요합니다. 리드권을 잡으려고 정작 열고 싶었던 묶음을 써 버리면 아무 의미가 없습니다.

패스에도 가치가 있다: 다시 낄 선택권#

“패스로는 트릭을 가져올 수 없으니 리드권 항은 0"이라고 두기 쉽지만, 이 시리즈가 내내 강조한 룰을 생각하면 그렇지 않습니다.

달무티는 패스한 뒤에도 자기 차례가 다시 오면 낼 수 있습니다.

즉 패스는 트릭을 포기하는 것이 아니라 “이번 차례는 거르고, 상황이 바뀌면 다시 끼겠다"는 선택권을 사는 것 입니다. 내가 패스한 뒤 누군가 기준선을 올리면, 그 올라간 기준선을 내가 다시 받아 리드권을 가져갈 수 있습니다. 이 선택권의 값어치는 0이 아닙니다.

이 항을 0으로 두면 봇은 “지금 못 먹으면 영영 못 먹는다"고 착각 하고, 그 착각 때문에 지금 카드를 태우는 쪽으로 기웁니다. 전략적 패스를 하라고 만든 봇이 정작 패스를 과소평가하게 됩니다.

// continuationValue 는 패스한 뒤에도 이번 트릭에 다시 낄 수 있는 선택권의 가치다.
// 달무티는 패스 후 재참여를 허용하므로 이 값은 0 이 아니다.
//
// 한 수 앞만 보는 근사다. "누군가 기준선을 올린다 → 올라간 기준선을 내가 받는다"
// 까지만 세고, 그 뒤로 트릭이 몇 바퀴 더 도는지는 계산하지 않는다.
func (p *HardPolicy) continuationValue(v GameView, l *Ledger) float64 {
	// 아무도 기준선을 올리지 않으면 트릭은 그대로 끝나고 선택권도 함께 사라진다.
	quiet := 1.0
	for _, s := range l.ActiveOpponents() {
		quiet *= 1 - l.SeatBeatRisk(s, v.Table.Rank, v.Table.Count)
	}
	pRaise := 1 - quiet

	// raiseToGivenRaise 는 "누군가 올렸다" 는 조건 아래의 분포이므로
	// r 에 대한 합이 1 이다. 여기에 pRaise 를 곱해야 무조건부 기대값이 된다.
	reentry := 0.0
	for r := RankHighest; r < v.Table.Rank; r++ {
		bar := Play{Rank: r, Count: v.Table.Count}
		cands := LegalFollows(v.Hand, bar)
		if len(cands) == 0 {
			continue // 그 기준선에서는 내가 다시 낄 수 없다
		}
		// Part 1 과 같은 결정적 순서로 정렬한 뒤 최선의 후보를 고른다.
		sort.Slice(cands, func(i, j int) bool { return easyLess(cands[i], cands[j]) })

		best := 0.0
		for i := range cands {
			// 다시 껴서 낸 수도 또 받힐 수 있다. 리드권 확보 확률까지 곱한다.
			val := p.controlProb(withTable(v, bar), l, &cands[i]) *
				p.controlValue(v, l, &cands[i])
			if val > best {
				best = val
			}
		}
		reentry += l.raiseToGivenRaise(r, v.Table.Count) * best
	}
	return pRaise * reentry
}

확률을 두 번 곱하지 않도록 주의해야 합니다. 가중치를 “기준선이 r 로 올라갈 확률"이라는 무조건부 확률로 두면 Σ 자체가 이미 pRaise 이므로, 거기에 pRaise 를 또 곱하면 패스 가치가 그만큼 과소평가됩니다. 그래서 raiseToGivenRaise 는 “누군가 올렸다"는 조건 아래의 분포(r 에 대한 합이 1)로 정의하고, pRaise 는 밖에서 한 번만 곱합니다. 무조건부 분포로 두고 pRaise 를 곱하지 않아도 값은 같지만, 이쪽이 “아무도 안 올리면 선택권이 소멸한다” 는 의미를 코드에 남겨 줍니다. 어느 쪽이든 함수의 정의와 곱셈 구조가 일치해야 합니다.

후보를 고를 때 Part 1 의 순서로 정렬한 뒤 최댓값을 취하는 것도 중요합니다. LegalFollows 가 돌려주는 순서를 그대로 쓰면 map 순회 순서에 의존해 결정성이 깨집니다. 그리고 재진입해서 낸 수도 다시 받힐 수 있으므로, controlValue 만이 아니라 그 시점의 controlProb 까지 곱해야 “리드권 가치"라는 이름과 계산이 맞습니다.

이 값은 필요할 때 알아서 작아집니다. 기준선이 높이 올라갈수록 LegalFollows 가 빈 슬라이스를 돌려주므로 그 항이 빠지고, 아무도 올릴 것 같지 않으면 pRaise 가 0에 가까워집니다. “어차피 이대로 끝날 트릭"에서는 선택권 가치가 저절로 사라지는 셈 이고, 상한도 controlValue 의 최댓값을 넘지 않으므로 폭주하지 않습니다.

한계는 둘입니다. 한 수 앞만 봅니다. 실제로는 기준선이 두 번 세 번 올라가는 동안 계속 개입 기회가 오지만 그 꼬리는 세지 않습니다. 그리고 “내가 참는 동안 상대들이 카드를 태운다"는 이득을 넣지 않았습니다. 좌석별 손패 감소를 추정해야 해서 계산이 무거워지는 것에 비해 순서를 바꿀 만큼 크지 않다고 보고 뺐습니다. 둘 다 패스를 보수적으로 평가하는 방향이라 봇이 과하게 참는 쪽으로 무너지지는 않습니다. 계산 비용은 후보 하나를 평가할 때보다 무겁지만, 패스 후보는 턴당 하나뿐 이라 후보 수만큼 반복되지는 않습니다.

템포 위험은 행동에 따라 달라져야 한다#

“상대가 곧 손패를 털 위험"을 재는 항인데, 여기에는 조용히 무력화되기 쉬운 함정이 있습니다. 좌석별 남은 장수만 보고 위험을 계산하면 그 값은 후보가 무엇이든 똑같습니다. 그런데 점수 함수는 후보들 사이의 최댓값을 고르는 데 쓰이므로, 모든 후보에서 같은 값을 빼는 항은 선택에 아무 영향을 주지 못하고 완전히 상쇄됩니다. 패스 점수에서도 똑같이 빼면 제출과 패스의 비교에서도 사라집니다. 그런 항은 W.Tempo 를 아무리 튜닝해도 봇의 행동을 한 톨도 바꾸지 못하면서, 가중치가 있으니 뭔가 하고 있다는 착각만 줍니다.

그러므로 템포 위험은 그 행동을 한 다음의 위험 이어야 합니다.

// tempoRiskAfter 는 이 행동을 하고 난 뒤 남는 위험이다.
// c 가 nil 이면 패스이므로 테이블의 기준선이 그대로 유지된다.
func (p *HardPolicy) tempoRiskAfter(v GameView, l *Ledger, c *Candidate) float64 {
	bar := *v.Table
	if c != nil {
		bar = Play{Rank: c.Rank, Count: v.Table.Count} // 내가 기준선을 올린다
	}

	risk := 0.0
	for _, s := range l.ActiveOpponents() {
		risk += 2.0 * l.finishRisk(s, bar)     // 이번 트릭에 나갈 위험
		risk += 1.0 * l.oneShotOutRisk(s, bar) // 리드권을 잡고 다음에 털 위험
	}
	return risk
}

// finishRisk 는 좌석 s 가 이번 트릭에서 손패를 다 털 위험이다.
// 손패 장수가 트릭 장수와 정확히 같을 때만 이번 트릭에 나갈 수 있다.
// 적으면 응수 자체가 불가능하고, 많으면 이번 트릭엔 못 나간다.
func (l *Ledger) finishRisk(s SeatModel, bar Play) float64 {
	if s.HandCount != bar.Count {
		return 0
	}
	return l.SeatBeatRisk(s, bar.Rank, bar.Count)
}

기준선을 올리면 SeatBeatRisk 가 떨어지므로 finishRisk 도 떨어집니다. 이제 이 항이 후보에 따라 달라지고, 가중치가 실제로 작동합니다.

oneShotOutRisk 는 한 단계 뒤의 위험입니다. 어떤 좌석이 리드권을 잡았을 때 남은 카드가 전부 같은 rank 라면 한 번에 다 털고 나갑니다. 손패 내용은 모르지만 장부로 확률을 추정할 수 있습니다. 손패가 1장이면 확률 1이고, 2장이면 “미공개 카드에서 같은 rank 두 장을 뽑을 확률"입니다. 장수가 적은 좌석일수록 이 값이 가파르게 올라갑니다.

2. 전략적 패스: 낼 수 있어도 참는다#

이제 hard 봇을 easy 봇과 가장 다르게 보이게 만드는 부분입니다. 앞에서 패스를 c == nil 후보로 만들어 뒀으므로, 구현은 최댓값 선택 한 줄로 끝납니다.

func (p *HardPolicy) SelectPlay(v GameView) Decision {
	l := NewLedger(v)

	if v.Table == nil {
		return p.selectLead(v, l)
	}
	if cards, ok := p.mustBlock(v, l); ok {
		return Decision{Cards: cards} // 차단 의무는 점수 계산보다 우선한다
	}

	cands := LegalFollows(v.Hand, *v.Table)
	// Part 1 의 결정적 순서를 그대로 적용한다.
	// 이 정렬이 없으면 map 순회 순서에 따라 동점 후보의 선택이 달라져
	// 재현이 불가능해진다.
	sort.Slice(cands, func(i, j int) bool { return easyLess(cands[i], cands[j]) })

	best := p.score(v, l, nil) // 패스를 기준선으로 삼는다
	var choice *Candidate

	for i := range cands {
		// 부등호가 > 이므로 동점이면 정렬상 앞선 후보가 이긴다.
		if s := p.score(v, l, &cands[i]); s > best {
			best, choice = s, &cands[i]
		}
	}
	if choice == nil {
		return Decision{Pass: true} // 어떤 수도 패스보다 낫지 않다
	}
	return Decision{Cards: choice.Cards}
}

sort.Slice 한 줄과 > 부등호가 Part 1 에서 확보한 결정성 을 hard 봇까지 이어 줍니다. 이게 없으면 LegalFollows 의 map 순회 순서에 따라 동점 후보 중 아무거나 뽑히고, 같은 상황을 재현할 수 없는 봇이 됩니다. 봇의 이상한 수를 나중에 디버깅해야 하는 사람은 결국 우리 자신입니다.

차단 의무는 조건을 정확히 써야 한다#

“상대가 곧 나갈 것 같으면 막는다"를 코드로 옮길 때 조건을 대충 쓰면 틀립니다. 정확한 조건은 이렇습니다.

• 손패가 트릭 장수 보다 적으면 그 좌석은 이번 트릭에 응수 자체를 못 합니다. 막을 필요가 없습니다.
• 손패가 트릭 장수 보다 많으면 이번 트릭에 나갈 수 없습니다. 급하지 않습니다.
• 손패가 트릭 장수와 정확히 같고 현재 테이블을 이길 수 있을 때만, 그 좌석은 자기 차례에 나갑니다.

그리고 한 명이 나가도 게임이 끝나는 것은 아닙니다. 공식 룰북 Going Out 절이 “After a player goes out, play continues clockwise as usual” 이라고 명시합니다. 막아야 하는 이유는 판이 끝나서가 아니라, 그 좌석이 좋은 등수를 가져가서 점수와 다음 판 계급을 챙기기 때문입니다.

// mustBlock 은 이번 트릭에 나갈 수 있는 좌석을 실제로 막을 수 있을 때만
// 그 수를 리턴한다. 막을 수 없다면 굳이 카드를 태우지 않는다.
func (p *HardPolicy) mustBlock(v GameView, l *Ledger) ([]Card, bool) {
	threats := []SeatModel{}
	for _, s := range l.ActiveOpponents() {
		if s.HandCount == v.Table.Count &&
			l.SeatBeatRisk(s, v.Table.Rank, v.Table.Count) > p.blockThreshold {
			threats = append(threats, s)
		}
	}
	if len(threats) == 0 {
		return nil, false
	}

	cands := LegalFollows(v.Hand, *v.Table)
	sort.Slice(cands, func(i, j int) bool { return easyLess(cands[i], cands[j]) })

	// 위협을 전부 봉쇄하는 후보 중 가장 싼 것을 고른다.
	for i := range cands {
		blocked := true
		for _, s := range threats {
			if l.SeatBeatRisk(s, cands[i].Rank, v.Table.Count) > p.blockThreshold {
				blocked = false
				break
			}
		}
		if blocked {
			return cands[i].Cards, true
		}
	}
	return nil, false // 어떤 수로도 못 막는다면 점수 계산에 맡긴다
}

마지막 return nil, false 가 중요합니다. 막을 수 없는 위협 때문에 카드를 태우는 것은 순손실입니다. 오버라이드는 “막을 수 있을 때만” 발동해야 합니다.

패스가 이기는 여섯 가지 상황#

점수 계산이 실제로 패스를 선택하게 되는 상황은 다음과 같이 정리됩니다. 각각이 사람 고수의 판단과 대응됩니다.

4번을 구체적인 손패로 보겠습니다. 내 손패가 11 x 2, 10 x 1, 9 x 1 이고 테이블에는 4 x 2 가 놓여 있다고 해봅시다. 이걸 받으려면 3 이나 그보다 강한 rank 를 2장 만들어야 하는데, 마침 강한 카드 한 장에 광대를 붙여야 겨우 됩니다.

받으면 무슨 일이 생기는지 계산해 보면 이렇습니다. 운 좋게 리드권을 잡아도 내가 열 수 있는 최선은 11 x 2 이고, 이건 거의 확실히 받힙니다. 즉 최강급 카드 한 장과 광대 한 장을 태워서 얻는 것이 “거의 확실히 받힐 트릭을 한 번 여는 권리” 뿐입니다. controlValue 가 0에 가까우니 control 항 전체가 0에 가깝고, planGain 은 오히려 음수(광대가 빠져 다른 묶음의 안전도가 떨어짐)입니다. 패스가 이깁니다.

반대로 같은 상황에서 내 손패가 12 x 6 을 포함하고 있었다면 계산이 뒤집힙니다. 리드권만 잡으면 12 x 6 으로 판을 열 수 있고, 8명 게임에서 그 묶음을 받을 수 있는 사람이 존재할 확률은 2%입니다. 이때는 강한 카드를 태워서라도 리드권을 사는 것이 맞습니다. 같은 카드, 같은 테이블인데 손패 구조에 따라 정답이 정반대가 됩니다.

flowchart TD
    A["후공 차례"] --> B{"합법 수가 있는가?"}
    B -- 아니오 --> PASS["패스"]
    B -- 예 --> C{"이번 트릭에 나갈 수 있는<br/>좌석이 있고, 막을 수 있는가?"}
    C -- 예 --> BLOCK["가장 싼 봉쇄 수 제출<br/>(점수 계산 생략)"]
    C -- 아니오 --> D["결정적 순서로 정렬 후<br/>후보별 점수 계산"]
    D --> E["플랜 개선도<br/>(묶음 파괴 · 고아 증감)"]
    D --> F["제출: 리드권 확보 확률<br/>(살아 있는 전원이 연속 패스)<br/>패스: 다시 낄 선택권 가치"]
    D --> G["리드권 가치<br/>(제출 후 손패의 최선 묶음)"]
    D --> H["행동 후 템포 위험<br/>(기준선을 올린 뒤의 위험)"]
    E --> I["최고 점수 후보"]
    F --> I
    G --> I
    H --> I
    I --> J{"패스 점수보다 높은가?<br/>(패스에도 선택권 가치가 있다)"}
    J -- 예 --> PLAY["제출"]
    J -- 아니오 --> PASS
    style A fill:#FFD700,color:#000000
    style BLOCK fill:#FF7F50,color:#000000
    style PLAY fill:#90EE90,color:#000000
    style PASS fill:#87CEEB,color:#000000

리드 선택도 같은 계산이다#

선공일 때는 후보가 “내 손패의 각 묶음 x 쪼갤 장수"가 됩니다. easy 봇처럼 가장 약한 묶음을 통째로 내는 대신, hard 봇은 세 가지를 저울질합니다.

• 어차피 받힐 묶음을 리드권이 있을 때 흘려보낼 것인가. 이쪽이 정석에 가깝습니다. 받힐 묶음은 리드권을 쥐고 있을 때 버리는 것이 가장 쌉니다.
• 가장 안전한 묶음으로 열 것인가. 리드권이 어차피 유지될 묶음을 먼저 소모하는 것은 낭비일 수 있습니다. 다만 판 후반에 상대 손패가 얇아지면, 확실승수 묶음으로 연달아 털어 그대로 나가는 것이 정답이 됩니다.
• 묶음을 쪼갤 것인가. 7장 묶음을 6장만 내고 1장을 남기면 고아 카드가 생겨 MinPlays 가 그대로인 채 Orphans 만 늘어납니다. 반대로 6장 묶음을 3+3 으로 쪼개면 제출 횟수가 하나 늘지만, 3장 판이 도는 흐름에서 응수 유연성이 생깁니다.

정리하면 “어차피 받힐 묶음을 리드권이 있을 때 버리고, 안전한 묶음은 마무리용으로 아낀다” 가 리드 정책의 뼈대입니다. easy 봇이 우연히 비슷하게 행동하는 부분이기도 한데(가장 약한 묶음을 냄), hard 봇은 그것이 “약해서"가 아니라 “어차피 받힐 것이라서” 라는 이유로 냅니다. 그래서 상대가 낮은 rank 를 다 소진해 12 묶음이 갑자기 안전해진 상황에서는 반대로 행동합니다.

3. 세금과 혁명의 기대값 계산#

목적 함수부터 정한다#

이 절에 들어가기 전에 확정해야 할 것이 있습니다. 봇이 무엇을 최대화하는가 입니다. 선택지에 따라 정답이 달라집니다.

이 글은 세 번째, 공식 점수 규칙(나갈 때마다 아직 남아 있는 인원수만큼 획득, 20판)에서의 누적 우승 을 목적 함수로 잡습니다. Part 1 에서 GameView 에 Score 와 HandsLeft 를 넣어 둔 이유가 이것입니다. 그리고 이 선택이 아래 혁명 판단에 직접 영향을 줍니다.

내려줄 카드 고르기: 상대의 묶음을 키우지 않는다#

세금은 주는 쪽(농노)에게는 선택권이 없습니다. 룰이 “가장 강한 카드"를 강제하기 때문입니다. 의사결정은 오직 받는 쪽(달무티)의 반환 카드 선택에서만 일어납니다.

easy 봇은 “가장 약한 카드부터"였습니다. hard 봇은 두 가지를 더 봅니다.

1. 내 플랜의 고아 카드를 우선 내보냅니다. 12를 다섯 장 쥐고 있다면 12는 소중한 묶음이지 버릴 카드가 아닙니다. 반면 11이 딱 한 장 있다면 그것이 최우선 반환 대상입니다. 약한 카드가 아니라 쓸모없는 카드 를 골라야 합니다.

2. 그 카드가 상대의 묶음을 얼마나 키우는지 계산합니다. 이것이 카운팅의 세금 단계 응용입니다. 여기서 흔히 쓰는 어림값이 함정입니다. “상대가 그 rank 를 몇 장 갖고 있을지 기댓값을 구한 뒤 거기에 한 장 더한 가치"는 한계 비용이 아닙니다. 가치 함수가 비선형이면 f(E[K] + 1) 과 E[f(K+1)] 은 다른 값입니다(옌센 부등식). 필요한 것은 한 장을 더했을 때의 가치 증가분의 기대값 입니다.

// groupValue 는 rank r 을 n 장 쥔 묶음의 가치다.
// 장수가 커질수록 응수 가능한 사람이 있을 확률이 급락하므로 가치는 비선형으로 오른다.
func (l *Ledger) groupValue(r Rank, n int) float64 {
	if n == 0 {
		return 0
	}
	return float64(n) * (1 - l.BeatRisk(r, n))
}

// giveAwayCost 는 rank r 카드 add 장을 넘길 때 상대 묶음의 가치가
// 얼마나 오르는지의 기대값이다. E[f(K+add) - f(K)] 형태여야 한다.
func (l *Ledger) giveAwayCost(r Rank, add int, targetHandSize int) float64 {
	total := l.TotalUnseen()
	cost := 0.0
	for k := 0; k <= l.unseen[r]; k++ {
		pk := hyperPMF(l.unseen[r], total, targetHandSize, k)
		cost += pk * (l.groupValue(r, k+add) - l.groupValue(r, k))
	}
	return cost
}

add 를 인자로 둔 이유가 있습니다. 대달무티는 2장 을 내려줘야 하는데, 같은 rank 두 장을 주는 것은 한계 비용을 두 번 더한 값과 다릅니다. k → k+2 는 묶음을 5장에서 7장으로 밀어 올릴 수 있고, 그 구간의 가치 증가는 두 번의 한 장 증가보다 큽니다. 그러므로 반환 카드 2장은 개별 최소가 아니라 조합 최소로 골라야 합니다.

// SelectTaxCards (ReturnAny) 는 반환 카드 조합을 완전탐색한다.
// 손패에서 2장을 고르는 경우의 수는 최대 수백 개라 전수 비교가 싸다.
func (p *HardPolicy) selectReturn(v GameView, l *Ledger, duty TaxDuty) []Card {
	plan := BestPlan(v.Hand, l)
	target := v.SeatOf(duty.To).HandCount

	bestCost := math.Inf(1)
	var best []Card
	for _, combo := range combinations(v.Hand, duty.Count) {
		if containsJester(combo) {
			continue // 광대는 반환 후보에서 아예 제외한다
		}
		cost := 0.0
		for r, add := range countByRank(combo) {
			cost += l.giveAwayCost(r, add, target)
		}
		cost += planDamage(plan, combo) // 내 묶음을 깨는 손해
		if cost < bestCost {
			bestCost, best = cost, combo
		}
	}
	return best
}

직관에 반하는 결론이 나옵니다. rank 12 는 판 초반에 반환 카드로 나쁩니다. 12는 세상에 12장이나 있어 대농노도 여러 장 쥐고 있을 가능성이 높고, 한 장을 더해 주면 그 묶음이 5장에서 6장이 될 수 있습니다. Part 2 의 확률표대로라면 그 순간 대농노는 거의 무적인 리드 카드 를 손에 넣습니다. 최강 카드 2장을 뺏어 오고 그 대신 판을 뒤집을 열쇠를 쥐여 준 셈입니다.

다만 이것은 조건부 주장 이라는 점을 분명히 해 두겠습니다. 위험한 것은 “12"라는 숫자 자체가 아니라 상대가 이미 그 rank 를 많이 모았을 가능성 입니다. 12가 이미 여러 장 소진되어 unseen[12] 가 작아졌다면 같은 12도 안전한 반환 카드가 됩니다. 그래서 이 판단은 상수가 아니라 giveAwayCost 로 매번 다시 계산해야 합니다. 일반화하면 이렇습니다. 미공개 장수가 많이 남은 rank 일수록 반환 카드로 위험하고, 이미 많이 소진된 중간 rank 의 고아 카드가 가장 안전합니다.

광대를 주지 않는 진짜 이유#

Part 1 의 weakerFirst 가 광대를 예외 처리한 근거를 여기서 정량화할 수 있습니다. 광대를 지켜야 하는 이유는 혁명과는 무관합니다. 혁명 판정은 딜 직후 세금 징수보다 먼저 끝나고 카드는 매 판 다시 딜되므로, 세금으로 넘긴 광대가 그 판의 혁명 재료가 되는 일은 없습니다. 이유는 순수하게 플레이 가치 입니다. 광대는 어떤 묶음에든 붙어 장수를 늘리는 유일한 카드이고, 위 giveAwayCost 로 계산하면 모든 rank 에 대해 동시에 비용이 발생하는 유일한 카드이기도 합니다. 상대가 어떤 rank 를 몇 장 쥐고 있든 그 묶음을 한 장 키워 주기 때문입니다. 5장을 6장으로 만드는 그 한 장이 “응수 가능한 사람이 있을 확률 19%“를 “2%“로 바꿉니다.

혁명: 이득과 정보 노출 비용#

혁명이 취소하는 것은 판 전체의 세금 입니다. 내 세금만 취소되는 것이 아니라는 점이 중요합니다. 그래서 기대값을 네 항으로 나눠야 합니다.

EV(혁명) = 내 손패의 세금 변화
         + 상대 손패 강화 방지
         - 정보 노출 비용
         + 누적 점수 경쟁 효과

내 손패의 세금 변화 는 계급에서 바로 나옵니다. 대농노는 최강 2장을 잃고 아무 2장을 받으므로 순손실이 크고, 취소하면 그만큼을 지킵니다. 대달무티는 정확히 반대라 취소가 순손실입니다. 상인은 이 항이 0입니다.

정보 노출 비용 은 구체적으로 계산할 수 있습니다. 혁명을 선언하면 전원이 두 가지를 알게 됩니다.

• 내 손에 광대 2장이 있다 → 내가 큰 묶음을 리드해도 광대로 부풀린 것일 수 있다 는 경계를 삽니다.
• 다른 모든 사람은 광대가 0장이다 → 상대들의 StructurallySafe 판정이 즉시 정확해집니다. Part 2 의 구조적 판정표에서 “내가 광대 2장을 쥐었을 때” 열이 그대로 상대에게 적용되어, 상대는 자기 큰 묶음 리드를 훨씬 자신 있게 던집니다.

두 번째가 더 아픕니다. 내가 혁명을 선언하는 순간, 판 전체의 불확실성이 줄어들고 그 이득은 나 말고 전원이 나눠 갖습니다.

상대 손패 강화 방지 는 두 가지 이유로 오해하기 쉬운 항입니다.

첫째, 단판 1등이 목적이어도 상대가 강해지는 것은 손해입니다. 등수는 상대적이라, 나와 1등을 다투는 대달무티의 손패가 최강 카드 2장만큼 좋아지면 내 1등 확률이 그대로 내려갑니다. 내 손패가 그대로여도 그렇습니다.

둘째, 이 항은 상인 전용이 아닙니다. 혁명은 두 달무티가 받을 세금을 모두 막으므로, 대농노와 소농노도 자기 세금 손실을 피하는 것과 별개로 이 이득을 함께 얻습니다. 농노에게는 이 항이 앞의 항에 가려 잘 보이지 않을 뿐입니다. 상인은 앞의 항이 0이라 이 항만 혼자 남아 눈에 띄고, 그래서 “상인 전용"처럼 착각하기 쉽습니다.

계급별로 정리하면 이렇습니다.

누적 점수 경쟁 효과 만이 목적 함수에 따라 켜지고 꺼지는 항입니다. 단판 1등이 목적이면 이 항은 0이고, 20판 누적 우승이 목적이면 “점수 선두가 누구인가"와 “몇 판 남았는가"가 값을 좌우합니다. leaderThreat 같은 함수로 이 항만 계급·상황 조건부로 두는 것은 타당하지만, 바로 위의 상대 손패 강화 방지 항까지 상인 전용으로 묶으면 안 됩니다.

func (p *HardPolicy) DeclareRevolution(v GameView) bool {
	if countJesters(v.Hand) < 2 {
		return false
	}
	me := v.SeatOf(v.Me)

	if me.Title == GreaterPeon {
		return true // 대혁명. 좌석 전복의 가치가 다른 모든 항을 압도한다
	}
	if v.Round == 1 {
		return false // 전제표대로 첫 판에는 세금이 없다. 취소할 것이 없다
	}

	// ① 내 손패의 세금 변화. 대농노 2, 소농노 1, 달무티는 음수, 상인은 0.
	gain := taxLossIfNotCancelled(me.Title)
	// ② 상대 손패 강화 방지. 계급과 무관하게 항상 있다.
	gain += p.W.Control * p.blockedTribute(v, me.Title)
	// ③ 정보 노출 비용.
	cost := p.W.InfoLeak * float64(len(v.Seats)-1)
	// ④ 누적 점수 경쟁 효과. 단판이 목적이면 0 이다.
	if v.HandsLeft > 0 {
		// 남은 판수가 적고 점수 선두가 달무티 자리일수록 막을 값어치가 크다.
		gain += p.W.Rivalry * p.leaderThreat(v)
	}
	return gain > cost
}

easy 봇의 룩업 테이블과 결과는 대체로 같지만, 상인일 때 조건부로 선언한다 는 차이가 생깁니다. 상인의 gain 은 ①이 0이어도 ②가 항상 양수이므로, 정보 노출 비용을 넘기만 하면 선언합니다. 20판 중 18판째이고 점수 선두가 달무티 자리에 앉아 있다면 ④까지 더해져 확실히 선언 쪽으로 기웁니다. Part 1 의 easy 봇 혁명표에서 “상인은 안 함"이라고 단순화했던 자리가 바로 여기입니다. 사람이 실제로 하는 판단이고, 봇에게서 이런 수가 나오면 상대는 “이 봇 뭔가 생각하고 있다"고 느낍니다.

첫 판 분기에서 GreaterPeon 검사가 Round == 1 검사보다 먼저 온다는 점은 Part 1 과 동일합니다. 공식 선택 규칙이 첫 판에도 대혁명은 허용하기 때문입니다.

4. 전체 파이프라인#

flowchart TD
    subgraph K["① 지식: 공개 정보만"]
        K1["Ledger 구축<br/>rank 별 미공개 장수 카운팅"]
        K2["좌석 모델<br/>남은 장수 + 패스 관측(확률적 증거)"]
    end
    subgraph P["② 계획: 내 손패"]
        P1["rank 별 묶음 분해"]
        P2["광대 배치 완전탐색"]
        P3["최소 제출 횟수 · 안전 리드 수 · 고아 수"]
    end
    subgraph C["③ 후보"]
        C1["합법 수 생성 후 결정적 정렬"]
        C2["패스를 nil 후보로 추가"]
    end
    subgraph E["④ 평가"]
        E1["플랜 개선도"]
        E2["제출: 리드권 확보 확률 x 가치<br/>패스: 다시 낄 선택권 가치"]
        E3["행동 후 템포 위험"]
    end
    K1 --> P1
    K2 --> E2
    P1 --> P2 --> P3
    P3 --> E1
    C1 --> O{"이번 트릭에 나갈 좌석이 있고<br/>막을 수 있는가?"}
    O -- 예 --> B["오버라이드: 가장 싼 봉쇄 수<br/>(점수 계산 없이 즉시 제출)"]
    O -- 아니오 --> E1
    C2 --> E1
    E1 --> D["점수 최댓값 선택<br/>(동점은 정렬 순서로)"]
    E2 --> D
    E3 --> D
    D --> R["제출 또는 패스"]
    style K fill:#87CEEB,color:#000000
    style P fill:#90EE90,color:#000000
    style C fill:#F5DEB3,color:#000000
    style E fill:#DDA0DD,color:#000000
    style B fill:#FF7F50,color:#000000
    style R fill:#FFD700,color:#000000

계산량을 짚어 두겠습니다. 후보 수는 rank 수 x 광대 사용량 이라 최대 수십 개, 광대 배치는 100가지 미만, BeatRisk 는 rank 12개 x 좌석 7개의 초기하 계산입니다. 전부 곱해도 한 턴의 판단은 수천 회 수준의 초기하 계산 으로 끝나고, 재귀도 탐색도 없습니다. 상태 공간이 이만큼 작으면 실시간 턴 예산 안에 충분히 들어올 것으로 예상합니다.

다만 여기서 실행 시간을 숫자로 단정하지는 않겠습니다. 이 글의 코드는 발췌이고 벤치마크를 돌린 적이 없으므로, 구체적인 수치는 실제 구현 후 벤치마크로 확인해야 합니다. 특히 BestPlan 을 매 후보마다 다시 부르는 부분은 계산이 중복되므로, 실측해 보고 필요하면 캐싱을 넣어야 할 지점입니다.

어쨌든 요지는 이것입니다. 달무티는 탐색 없이 순수 계산만으로 상당한 수준에 도달할 수 있는 게임 입니다. 결정화 몬테카를로 트리 탐색 같은 무거운 장치는 이 계산을 다 짜고 나서도 부족할 때 꺼내는 것이 순서입니다.

5. 튜닝과 검증#

봇을 만드는 것보다 봇이 정말 세졌는지 재는 것 이 더 어렵습니다. 카드게임은 분산이 커서 100판을 돌려도 우연에 묻히기 때문입니다.

미러 매치로 분산을 죽입니다. 같은 시드로 딜한 손패를 좌석만 회전시켜 반복 실행합니다. 8명 게임이면 같은 딜을 8번 돌려 모든 봇이 모든 손패를 한 번씩 잡게 합니다. 이렇게 하면 손패와 좌석에서 오는 분산이 크게 줄어듭니다. 브리지 대회의 듀플리케이트 방식과 같은 아이디어이고, 필요한 판수를 크게 줄여 줍니다. 다만 “순수한 정책 차이만 남는다"고까지 말할 수는 없습니다. 봇들이 서로 반응하며 두는 게임이라 좌석을 돌려도 상호작용과 경로 의존성은 남고, 특히 상대 구성이 달라지면 같은 손패라도 전개가 달라집니다.

평균 등수를 지표로 씁니다. 승률(1등 비율)은 정보량이 적습니다. 달무티는 등수가 그대로 다음 판의 계급이 되고 점수도 등수에 비례하므로, 2등과 5등의 차이가 큽니다. 8명 게임에서 무작위 봇의 기대 평균 등수는 4.5 이고, hard 봇이 easy 봇 7명 사이에서 이보다 유의하게 낮은 값을 내야 개선입니다.

결과를 보고할 때는 반드시 표본 수와 오차를 함께 적습니다. “평균 등수 3.2” 같은 숫자는 그 자체로는 아무 의미가 없습니다. 몇 판을 돌렸는지, 표준오차가 얼마인지, 튜닝에 쓰지 않은 held-out 시드에서도 같은 값이 나오는지가 있어야 비로소 주장이 됩니다. 가중치를 맞추면서 같은 시드로 측정하면 그 시드에 과적합된 봇이 나옵니다.

가중치는 좌표 하강으로 맞춥니다. Weights 항이 다섯 개뿐이므로, 한 번에 하나씩 격자 탐색하며 평균 등수가 좋아지는 방향으로 옮기는 것으로 충분합니다. 항이 늘어나기 시작하면 그때 셀프플레이 학습을 고민해도 늦지 않습니다. 그리고 항을 추가할 때마다 그 항이 후보에 따라 실제로 달라지는지 확인해야 합니다. 모든 후보에서 같은 값이 되는 항은 가중치를 아무리 돌려도 행동을 바꾸지 못합니다. 가중치를 0과 큰 값으로 놓고 봇의 선택이 달라지는지 보는 간단한 ablation 으로 잡을 수 있습니다.

중간 난이도는 계산을 줄이지 말고 정보를 줄입니다. normal 봇을 만든다고 hard 봇의 계산을 대충 하게 만들면, 봇이 “약한” 게 아니라 “이상한” 수를 둡니다. 대신 Ledger 를 최근 몇 트릭만 보게 하거나, 패스 관측을 무시하게 하거나, 패스 임계값을 보수적으로 두는 식으로 정보 접근을 좁히는 편이 훨씬 자연스러운 약함을 만듭니다. 사람이 약한 이유도 계산을 못 해서가 아니라 다 기억하지 못해서입니다.

결정적 봇은 읽힙니다. hard 봇도 결정적으로 두면 사람이 몇 판 만에 패턴을 읽습니다. 상위 후보 두세 개의 점수 차가 작을 때 소프트맥스로 샘플링하면 사람다워집니다. 다만 난수 시드를 리플레이 로그에 반드시 남겨야 합니다. 그래야 “이 봇 왜 이렇게 뒀지?“를 나중에 재현할 수 있습니다.

마치며#

세 편을 관통하는 이야기를 한 줄로 줄이면 이렇습니다.

easy 봇은 한 턴 안에서 합법적인 최소 손실 을 계산하고, hard 봇은 판 전체에서 자기 손패를 몇 번에 털지 를 계산합니다.

hard 봇을 만들면서 새로 등장한 개념들은 전부 이 한 문장에서 파생됩니다. 카운팅은 “내 묶음이 안전한가"를 알기 위해 필요하고, 패 분해 플랜은 “몇 번 내야 하는가"를 세기 위해 필요하며, 전략적 패스는 “이 차례를 쓸 값어치가 있는가"를 묻기 위해 필요합니다.

그리고 이 세 가지 모두 상대 손패를 한 장도 보지 않고 만들어집니다. 봇이 강해지는 방향은 정보를 더 주는 쪽이 아니라, 모두에게 공개된 같은 정보를 더 성실하게 세는 쪽이어야 합니다. 그래야 사람이 졌을 때 “속았다"가 아니라 “다음엔 나도 세어 봐야겠다"고 생각하게 됩니다. 봇 AI 설계에서 이 감각이 알고리즘 선택보다 중요하다고 생각합니다.

마지막으로 두 가지를 덧붙이겠습니다. 첫째, Part 2 의 확률표와 손패 분포는 판 시작 시점의 무작위 딜 을 몬테카를로로 뽑은 값입니다. 실제 게임에서는 세금 교환이 손패를 편향시키고 카운팅이 쌓이면서 수치가 계속 달라지므로, 봇 가중치를 맞출 때 표의 숫자를 상수로 박지 말고 Ledger 에서 매 턴 다시 계산하시기 바랍니다. 둘째, 룰셋 전제가 하나만 달라져도 여기 나온 계산의 상당 부분이 무너집니다. 특히 패스 후 재참여 를 허용하지 않는 변형 룰을 쓴다면 리드권 계산 전체를 다시 써야 합니다. 봇을 만들기 전에 룰부터 확정하고 문서로 못 박아 두시기 바랍니다.

References#

• The Great Dalmuti Rulebook (Wizards of the Coast, PDF)
• The Great Dalmuti (BoardGameGeek)
• Jensen’s inequality (Wikipedia)
• Hypergeometric distribution (Wikipedia)
• Duplicate bridge (Wikipedia)
• 달무티 CPU 플레이어 만들기 Part 1: 규칙 기반 easy 봇
• 달무티 CPU 플레이어 만들기 Part 2: hard 봇의 정보 모델과 확실승수 판정
• 대부호부터 렉시오까지: 클라이밍 카드게임의 세계와 전략