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

「대부호 CPU 플레이어 만들기」의 마지막 편은 그 시험으로 말할 수 없는 것을 적으며 끝났습니다. 그 가운데 한 줄이 이랬습니다. “다른 설계의 봇, 예컨대 몬테카를로로 상대 손패를 뽑아 끝까지 두어 보는 봇과 견준 것이 아닙니다.” 열아흐레 뒤인 10월 24일, 바로 그런 봇이 운영 봇이 됐습니다. 블로그에는 아직 적지 않은 일입니다.

다시 읽어 보니 시리즈에는 몬테카를로가 처음부터 들어 있었습니다. 봇의 성적을 잰 시뮬레이터가 몬테카를로였고, 장부의 위험 점수는 몬테카를로로 검산할 수 있는 근사였는데 큰 판에서는 검산하지 않은 채 남아 있었습니다. 그 검산을 이번에 해 봤고, 운영 봇의 탐색도 같은 방법으로 들여다봤습니다. Part 1 에서 다룬 표본 평균과 √n 오차를 그대로 씁니다.

성적표부터 몬테카를로였습니다#

Part 6 과 Part 7 의 Δ 는 “판당 평균 순위의 차이” 였습니다. 판마다 덱을 무작위로 섞어 봇을 앉히고, 끝난 순위를 세어 평균을 냈습니다. 몬티 홀에서 바꿔서 이긴 판을 센 것과 같은 일을 카드 54장과 봇 네~여섯 명으로 한 것입니다.

그래서 신뢰구간의 폭도 Part 1 의 공식을 따릅니다. 첫 파일럿은 seed 16개로 Δ −0.579 [−0.624, −0.535] 였고, held-out 시험은 seed 128개로 −0.746 [−0.761, −0.731] 이었습니다. 정책은 다르지만 구간의 반폭이 0.045 에서 0.015 로 세 배쯤 좁아졌습니다. seed 를 8배 늘렸으니 √8 ≈ 2.8 배를 기대한 그대로입니다. 구간을 판이 아니라 seed 단위로 센 것도 같은 이유였습니다. 한 seed 에서 나온 아홉 칸은 같은 seed 로 덱을 만들기 때문에 서로 독립이라고 볼 수 없고, 독립이 아닌 것을 독립으로 세면 n 이 부풀어 구간이 실제보다 좁게 나옵니다.

시뮬레이터에는 몬테카를로의 오래된 기법 하나가 이름 없이 들어 있었습니다. 같은 seed 의 같은 딜에 후보 봇과 기준 봇을 자리를 바꿔 가며 앉힌 것입니다. 두 봇을 서로 다른 무작위 딜로 재면, 두 평균의 차이에는 봇의 실력 차이와 딜의 운이 함께 섞입니다. 같은 딜로 재면 딜의 운이 양쪽에 똑같이 들어가 차이에서 상당 부분 지워집니다. 시뮬레이션 교과서는 이것을 공통 난수(common random numbers)라고 부릅니다. 이 기법은 뒤에서 운영 봇의 탐색에도 다시 나옵니다.

정답지가 없는 큰 판#

Part 3 의 장부는 “이 수를 내면 자격 있는 상대 가운데 누군가가 받을 수 있는가” 를 0 과 1 사이의 점수로 셉니다. 싱글은 초기하 분포로 정확히 세지만, 같은 숫자 묶음을 여러 자리가 받을 수 있는지는 자리끼리를 조건부로 독립처럼 합치는 근사입니다. 시리즈는 미확인 카드 6~8장짜리 작은 상태 450개에서 가능한 배분을 전부 세어 이 근사를 검산했고, 같은 숫자 “누군가” 의 안전한 쪽 오차가 최대 0.089 라고 적은 뒤 이렇게 덧붙였습니다. “큰 상태에서는 작아질 것으로 보지만 검증하지 않았습니다.”

검증하지 않은 이유는 Part 1 의 끝에 적은 숫자입니다. 미확인 38장을 세 자리와 블라인드로 나누는 경우는 2.4 × 10¹⁸ 가지라 전부 셀 수 없습니다. 몬테카를로로는 잴 수 있습니다. 장부가 가정하는 손패 모형은 “제약을 지키는 모든 배분이 똑같이 그럴듯하다” 이고, 그 모형에서 배분을 무작위로 뽑는 가장 단순한 방법은 섞어서 칸 크기대로 자르고 제약을 어긴 것은 버리는 것입니다. 아래는 실험 코드를 읽기 쉽게 줄인 것입니다.

// 미확인 카드를 섞어 칸(자리·블라인드·나락) 크기대로 자르고, 제약을 어긴 배분은 버린다.
// 남은 배분은 제약을 지키는 모든 배분 위에서 균등하다.
for accepted < samples {
	rng.Shuffle(len(deck), func(i, j int) { deck[i], deck[j] = deck[j], deck[i] })
	ok, offset := true, 0
	for _, b := range bins {
		part := deck[offset : offset+b.capacity]
		offset += b.capacity
		for _, card := range part {
			if (b.seat == 0 && card.IsJoker()) || (b.bound > 0 && ExchangeStrength(card) > b.bound) {
				ok = false // 블라인드의 조커, 조공 상한을 넘는 카드
			}
		}
		if b.seat > 0 {
			hands[b.seat] = part
		}
	}
	if !ok {
		continue
	}
	accepted++
	// 받을 수 있는지는 장부의 근사식이 아니라 엔진의 판정(CanAnyBeat)으로 센다.
	for _, seat := range responders {
		if model.CanAnyBeat(append(slices.Clone(known[seat]), hands[seat]...), field, revolution) {
			hits++
			break
		}
	}
}

봇 저장소를 복사한 사본에 이 함수를 붙여 돌렸습니다. 원본 코드는 건드리지 않았습니다. 먼저 자를 쟀습니다. 시리즈의 작은 상태 생성기로 180개 상태를 만들어 2만 개씩 뽑은 값과 전수 열거 정답을 견주니, 가장 크게 어긋난 것이 표준오차의 2.27배였습니다. 180번 재면 그 정도는 나옵니다.

어떻게 수렴하는지도 하나 보겠습니다. 정답이 0.6000 이고 장부의 근사가 0.6400 인 작은 상태입니다. 같은 상태를 씨만 바꿔 세 번씩 쟀습니다.

n=100      0.5400  0.5600  0.6100    (표준오차 0.049)
n=1000     0.6030  0.5810  0.5970    (0.015)
n=10000    0.6004  0.6006  0.6084    (0.0049)
n=100000   0.6017  0.5985  0.6005    (0.0015)
n=1000000  0.6001  0.5991  0.5997    (0.0005)

백 개로는 0.60 과 0.64 를 가릴 수 없습니다. 만 개면 근사가 0.04 높게 봤다는 것이 보입니다.

그다음이 큰 판입니다. 4인 매치 40개(판 4개씩)를 운영 hard 봇 넷으로 돌리면서, 한 자리의 차례가 올 때마다 낼 수 있는 수 가운데 셋을 무작위로 골라 장부의 위험 점수와 몬테카를로 2만 개의 값을 함께 쟀습니다. 필드를 바로 정리하는 수와 받을 자격이 있는 상대가 없는 수는 봇이 위험을 세지 않으므로 뺐습니다. 모두 3,479개 평가였고, 미확인 카드는 3장에서 41장까지였습니다. 몬테카를로 쪽 표준오차는 어느 평가에서도 0.0035 를 넘지 않습니다.

수의 종류평가평균 오차최대 오차근사가 위험을 낮게 본 최대
싱글2,2780.00040.0090.008
같은 숫자, 응수자 하나1990.00090.0080.008
같은 숫자, 응수자 둘~셋8380.0180.1960.196
계단1640.0150.1200.058

싱글과 응수자가 하나인 같은 숫자는 설계에 적힌 대로 정확합니다. 싱글의 최대 오차 0.009 도 몬테카를로 쪽 표준오차의 2.9배라, 2,000번 넘게 재다 보면 나오는 흔들림입니다. 확정 안전도 그대로였습니다. 장부가 0 이라고 한 705개 평가에서 몬테카를로도 2만 번 중 한 번도 받히지 않았고, 몬테카를로가 0 인데 장부가 0 이 아닌 평가도 없었습니다.

달라진 것은 응수자가 둘 이상인 같은 숫자입니다. 838개 가운데 절반(426개)에서 장부는 몬테카를로의 흔들림보다 크게 위험을 낮게 봤고, 높게 본 것은 10개뿐이었습니다. 평균으로 0.017 낮았고, 13% 에서는 0.05 넘게, 44개에서는 0.1 넘게 낮았습니다. 가장 큰 차이는 0.196 으로 작은 상태의 0.089 의 두 배가 넘습니다. 큰 상태에서는 작아질 것이라는 예상과 반대입니다.

가장 크게 틀린 국면은 손으로도 셀 수 있습니다. 판 첫 바퀴에 내가 K 쌍으로 받으려는 자리입니다. 안 나온 카드 가운데 K 쌍을 이길 수 있는 것은 2 석 장뿐입니다. A 와 조커는 모두 내 손에 있거나 이미 나왔습니다. 그런데 상대 하나는 조공으로 가장 센 카드를 내준 자리라 조공 상한 때문에 2 를 들 수 없습니다. 그러면 2 석 장은 13칸짜리 자리, 11칸짜리 자리, 블라인드 2칸, 모두 26칸 가운데 어딘가에 고르게 흩어집니다. 자리마다 따로 보면 2 를 두 장 이상 쥘 확률이 0.500 과 0.381 이고, 장부는 이것을 독립처럼 합쳐 0.690 이라고 셉니다. 그런데 석 장을 26칸에 놓는 2,600가지 가운데 아무도 두 장을 못 쥐는 경우는 310가지뿐입니다. 한 자리가 2 를 적게 쥘수록 나머지 자리가 많이 쥐게 되는 비둘기집 효과입니다. 정답은 1 − 310/2,600 = 0.881 이고, 몬테카를로는 0.886 을 냈습니다. 장부는 열 번에 세 번 버틴다고 본 K 쌍이, 실제로는 열 번에 아홉 번 받힙니다.

이 효과는 운영 쪽에서도 이미 한 번 잡혔습니다. 11월에 3인 대부호를 열면서 응수자가 둘뿐인 3인 판에서 같은 과소평가가 0.23 까지 나왔고, 그 경우만은 두 자리의 결합 분포를 정확히 세도록 고쳐 지금의 hard-6 이 됐습니다. 4인 이상의 판은 응수자가 둘이든 셋이든 여전히 근사입니다. 이 차이가 봇의 성적을 얼마나 바꾸는지는 이번 실험으로 알 수 없습니다. 위험 점수는 점수 층의 통제 항과 드물게 발동하는 위협 차단에만 들어가는데, Part 6 에서 통제 항은 끄나 켜나 성적이 거의 같았습니다. 봇이 이 숫자를 확률이라 부르지 않고 주로 후보 사이의 순서로 쓰기로 한 것이 여기서 보험 노릇을 합니다.

열여섯 번 굴려 보고 고릅니다#

10월 24일에 운영 봇이 된 hard-4 는 손패가 다섯 장 이하로 줄면 수를 고르기 전에 한 단계를 더 거칩니다. 후보는 hard-3 의 점수 층이 고른 수, easy 가 낼 수, 받기라면 패스, 그리고 점수 상위 두 수입니다. 장부와 맞는 상대 손패를 열여섯 번 뽑고(결정화라고 부릅니다), 후보마다 그 열여섯 개 손패로 판을 끝까지 두어 봅니다. 이어지는 내 수는 탐색 없는 hard-3 이 두고, 상대들은 easy 가 둡니다. 평균 순위가 가장 낮은 후보를 냅니다.

// Hard4Search 는 hard-4 의 동결 탐색 설정이다: 표본 16, 점수 상위 후보 2, 손패 5장 이하에서만, 바꾸는 문턱 0, 롤아웃에서
// 나는 hard-3·상대는 Easy.
func Hard4Search() SearchConfig {
	return SearchConfig{Samples: 16, Candidates: 2, MaxHand: 5, Rollout: RolloutSelf}
}

열여섯 개 손패는 모든 후보가 같이 씁니다. 시뮬레이터가 같은 딜에 두 봇을 앉힌 것과 같은 공통 난수입니다. 난수의 씨는 시야의 해시라서, 같은 시야를 받으면 같은 열여섯 개를 뽑고 같은 수를 냅니다. 봇이 결정적이어야 한다는 시리즈의 계약이 탐색이 들어온 뒤에도 그대로 남았습니다.

처음부터 이 모양은 아니었습니다. 같은 날 아침에 먼저 해 본 시도는 판 끝까지 굴리는 동안 나도 상대도 모두 easy 로 두었는데, 어떤 설정으로 돌려도 탐색 없는 hard-3 보다 약했습니다. 손패 다섯 장 이하에서만 탐색해도 평균 순위가 0.030 나빠졌고, 늘 탐색하게 하면 0.306 나빠졌습니다. 표본을 늘려도 그대로였습니다. 롤아웃 안의 나를 hard-3 으로 바꾸자 달라졌습니다. 사전 등록한 held-out 시험에서 hard-3 을 −0.0504 [−0.0643, −0.0364] 로 이겼고, easy 대비로는 −0.8465 였습니다. 같은 시험에서 hard-3 의 easy 대비가 −0.7697 이었습니다. 대신 결정 시간 p99 가 1.0ms 에서 14.4ms 로 늘어, 한 수에 쓰는 시간 상한을 100ms 에서 200ms 로 올렸습니다.

첫 시도가 왜 졌는지는 오래된 이론이 잘 설명합니다. 제럴드 테사우로와 그레고리 갈퍼린은 1996년 백개먼에서, 후보 수마다 기존 정책으로 판을 끝까지 여러 번 두어 보고 평균 보상이 가장 큰 수를 고르는 방법으로 기존 정책의 실수를 많게는 5분의 1 아래로 줄였다고 보고했습니다. 이듬해 디미트리 버트세카스 등은 이런 롤아웃 정책이 바탕이 된 정책보다 나빠지지 않는다는 것을 조건을 붙여 증명했습니다. 롤아웃이 개선하는 것은 롤아웃 안에서 나를 두는 바탕 정책입니다. 첫 시도의 바탕은 easy 였으니 탐색이 만든 것은 조금 나아진 easy 였고, 그것은 hard-3 보다 약했습니다. 바탕을 hard-3 으로 바꾸자 조금 나아진 hard-3 이 됐습니다.

다만 이 보장에는 평가가 정확하고 상대가 모형대로 둔다는 조건이 붙습니다. 대부호 봇은 둘 다 아닙니다. 표본은 열여섯 개뿐이고, 롤아웃 속 상대는 실제 상대가 아니라 easy 입니다. 버트세카스 연구진은 2024년 체스 논문에서, 실제 상대 대신 가정한 상대로 롤아웃하면 개선을 증명할 수는 없고 그 가정한 상대가 강한 플레이어일 때 대략 성립한다고 적었습니다. hard-4 에게 그것은 보장이 아니라 기대입니다.

이 탐색이 실제로 얼마나 정확한지 재 봤습니다. 4인 매치 24개를 운영 봇 넷으로 돌리면서, 한 자리가 탐색한 결정 132개마다 운영 봇이 비교한 후보들을 같은 방식으로 뽑은 4,000개 손패로 다시 굴렸습니다. 4,000개 가운데 앞의 16개는 운영 봇이 실제로 쓴 16개와 같아서, 132개 결정 모두에서 후보별 평균이 운영 봇의 기록과 소수점 끝자리까지 같았습니다. 재현은 정확합니다. 그다음 뒤쪽 2,000개로 낸 평균을 기준으로 두고, 앞에서부터 n 개만 썼을 때 고른 수가 기준의 최선과 같은 비율을 셌습니다. 같은 표본을 쓰지 않고 후보마다 손패를 따로 뽑았다면 어땠을지도 함께 셌습니다.

표본 수같은 손패로 비교후보마다 따로 뽑음
476%68%
1680%70%
6488%80%
25692%89%
1,00099%—

열여섯 개로 낸 후보별 평균 순위는 표준오차가 0.13등쯤 됩니다. 후보끼리의 차이가 그보다 작은 결정이 많으니 다섯 번에 한 번은 기준과 다른 수를 고릅니다. 같은 손패로 비교하는 열여섯 개가 따로 뽑는 예순네 개와 정확도가 같다는 것이 공통 난수의 값입니다. 운영 봇은 132개 결정 가운데 31% 에서 hard-3 의 수를 다른 수로 바꿨습니다.

그렇다고 표본을 늘리는 것이 답은 아니었습니다. 시간 여유를 만들어 표본을 16개에서 24개로 늘린 후보도, 탐색하는 손패 범위를 넓힌 후보도 hard-4 보다 강해지지 않았습니다. 11월 초에는 더 근본적인 실험을 했습니다. 시뮬레이터 안에서만, 표본 대신 상대의 실제 손패를 탐색에 넣어 준 것입니다. 손패를 완벽하게 알아도 hard-4 의 범위에서 나아지는 몫은 −0.043 이었고, 4인 판에서 모든 손패 크기로 넓혀도 −0.020 으로 우연과 구별되지 않았습니다. 표본 수를 늘려 줄일 수 있는 것은 표본 평균의 흔들림뿐입니다. 롤아웃 속 상대가 실제 상대처럼 두지 않는다는 모형의 틀림은 표본을 아무리 늘려도 그대로 남습니다. 4인 판의 병목이 정보가 아니라 롤아웃 속 상대의 모형이라는 것이 그 실험의 결론이었습니다. 롤아웃 속 상대를 hard-3 으로 바꾼 후보와, 공개된 패스·받기 기록과 덜 어긋나는 표본을 골라 쓰는 후보도 시험했지만 둘 다 우연의 범위를 넘지 못했습니다.

상대 손패를 뽑아 완전정보 게임처럼 다루는 방법은 카드 게임 AI 에서 오래 쓰였습니다. 매슈 긴즈버그의 브리지 프로그램 GIB 는 비딩과 지금까지 나온 카드에 맞는 딜을 뽑아 딜마다 끝까지 정확히 풀고, 합이 가장 좋은 수를 골랐습니다. 이 방식에는 이름 붙은 함정이 있습니다. 뽑은 세계마다 정답을 따로 구하니, 실제로는 같은 정보 앞에서 같은 수를 둬야 하는데도 세계마다 다른 전략을 쓸 수 있다고 착각하게 됩니다. 1990년대 후반 프랭크(Ian Frank)와 바신(David Basin)이 지적했고, 2010년 롱(Jeffrey Long) 등이 strategy fusion 이라는 이름으로 정리한 문제입니다. 제가 코드를 읽은 바로는 hard-4 는 딜마다 정답을 푸는 대신 정해진 정책으로 두어 보는 쪽이라 이 함정을 대부분 비껴갑니다. 첫 수 뒤의 내 수는 hard-3 이 내 시야만 보고 두므로, 뽑은 손패를 안다고 가정하지 않습니다. 대신 롤아웃 정책의 수준에 묶입니다. GIB 의 표본 뽑기에 테사우로의 롤아웃을 붙인 중간 형태라고 보면 됩니다.

일본에서 2006년부터 열린 UEC 컴퓨터 대빈민 대회에서도 이 방법을 쓰는 프로그램들이 활약했습니다. 2014년 수리해석연구소 강구록의 한 논문은 대회에서 몬테카를로 프로그램들이 활약한다고 적고 그 절차를 소개하는데, 합법 수마다 손패를 나눠 플레이아웃을 여러 번 하고 끝난 순위에 5점에서 1점을 줘 평균이 가장 높은 수를 낸다는 것이 hard-4 와 거의 같습니다. 2016년 대회 우승 프로그램 Glicine 도 학습한 정책으로 몬테카를로 시뮬레이션을 돌려 수를 골랐습니다.

같은 장치는 사람을 재는 데도 쓰였습니다. 숙련 사용자가 hard 봇을 상대로 둔 혼자하기 기록을 다시 두면서, 사람과 봇의 수가 갈라진 결정마다 두 수를 각각 두고 판 끝까지 hard-4 로 이어 사람 자리의 순위를 견줬습니다. 7,185개 결정에서 사람의 수가 hard-4 의 수보다 평균 0.046등 나았습니다. 이득은 리드와 손패가 네 장 이상인 자리에 있었고, 손패가 1~3장일 때는 없었습니다. 탐색이 늘 도는 구간입니다. 그 결과로 세운 가설 다섯 가운데 둘이 시험을 통과해 지금의 가중치가 됐습니다.

백 번 펼치기의 조건#

울람이 솔리테어를 백 번 펼쳐 보자고 했을 때 당연하게 깔려 있던 조건이 있습니다. 한 판 한 판을 진짜 규칙대로 펼쳐야 한다는 것입니다. 대부호 봇의 성적을 재는 시뮬레이터는 운영과 같은 결정 경로를 타야 했고, 위험 점수를 검산하는 표본은 장부와 같은 손패 모형에서 뽑아야 했습니다. 이 둘은 맞췄습니다. 탐색의 롤아웃 속 상대는 실제 상대가 둘 법한 수를 둬야 하는데, 이것은 아직 맞추지 못했습니다. 손패가 다섯 장 이하로 줄어든 뒤 운영 봇이 고르는 수는, easy 가 상대인 열여섯 판의 평균에서 나옵니다.

자료에 대해#

hard-4 이후의 수치는 봇 저장소의 평가 문서에서 옮겼습니다. 저장소가 공개되어 있지 않아 링크를 걸 수 없습니다. 직접 돌린 실험은 2026년 11월 13일 저장소 사본(커밋 5e45c90b, 운영 hard-6)에 실험용 함수만 붙여 돌린 것이고, 4인 판만 쟀습니다. 위험 점수 실험의 “정답” 은 장부와 같은 손패 모형에서의 확률이지, 사람이 실제로 손패를 어떻게 쥐는지가 아닙니다. 패스나 받기로 드러난 정보를 반영하면 둘 다 달라집니다. 탐색 실험의 기준 4,000개 평균도 봇 자신의 모형에서의 최선이라, 실제 게임에서 가장 좋은 수라는 뜻은 아닙니다.

편제목
Part 1솔리테어 한 판의 확률
Part 2대부호 봇이 굴리는 판 (지금 글)

References#

최신 (2024~2026)#

  • Atharva Gundawar, Yuchao Li, Dimitri Bertsekas, “Superior Computer Chess with Model Predictive Control, Reinforcement Learning, and Rollout”, arXiv:2409.06477 (2024), p. 11 (가정한 상대로 한 롤아웃의 개선 조건): https://arxiv.org/abs/2409.06477
  • Dimitri Bertsekas, “Rollout and Approximation in Value Space for Stochastic and Continuous Spaces Problems”, MIT 강의 슬라이드 (2024), 슬라이드 7 (표본 수가 유한할 때의 분산, 후보마다 같은 표본 쓰기): https://web.mit.edu/dimitrib/www/RLTopics_2024_Lect8.pdf
  • Jérôme Arjonilla, Abdallah Saffidine, Tristan Cazenave, “Perfect Information Monte Carlo with Postponing Reasoning”, IEEE CoG (2024): https://arxiv.org/abs/2408.02380

배경 (2023년까지)#

이 블로그의 관련 글#