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

1946년, 수학자 스타니스와프 울람(Stanisław Ulam)은 병에서 회복하는 동안 솔리테어를 하며 시간을 보냈습니다. 그러다 질문 하나가 떠올랐습니다. 52장으로 펼치는 캔필드 솔리테어가 끝까지 풀릴 확률은 얼마일까. 그는 한동안 조합 계산으로 그 확률을 구해 보려 했습니다. 잘 되지 않았습니다. 1983년에 남긴 회고에서 울람은 그다음에 든 생각을 이렇게 적었습니다. “추상적인 사고” 보다 더 실용적인 방법은, 그냥 백 번쯤 펼쳐 놓고 성공한 판을 세는 것이 아닐까.

이 회고에서 저는 “백 번” 에 오래 머물렀습니다. 백 번 펼쳐 다섯 번 풀렸다면 확률은 5% 라고 해도 되겠습니까? 해도 됩니다. 다만 그 5% 는 앞뒤로 4%포인트쯤 흔들리는 숫자입니다. 무작위로 세어서 답을 얻는 방법, 그리고 그 답이 얼마나 흔들리는지 아는 방법을 합쳐서 몬테카를로 시뮬레이션이라고 부릅니다.

이름은 카지노에서 나왔습니다#

울람은 같은 회고에서, 이 생각이 곧바로 중성자 확산 같은 물리 문제로 옮겨 갔다고 썼습니다. 중성자 하나가 핵물질 안에서 언제 부딪히고 어디로 튀고 언제 흡수되는지는 하나하나가 확률입니다. 미분방정식으로 풀기 어려운 과정을, 무작위로 고른 선택이 이어지는 이야기 하나로 바꿔 끝까지 따라가 보고, 그런 이야기를 많이 모아 세면 됩니다. 울람은 이 생각을 존 폰 노이만에게 이야기했고, 폰 노이만은 1947년 3월 로스앨러모스의 이론 부서장 로버트 리히트마이어에게 이 계산을 전자계산기로 돌리는 계획을 편지로 보냈습니다. 그 편지가 전자계산기를 위한 첫 몬테카를로 계산 설계로 꼽힙니다.

이름은 니컬러스 메트로폴리스가 붙였습니다. 그가 1987년에 쓴 회고에 따르면, 울람에게는 친척들에게 돈을 빌려서라도 “꼭 몬테카를로에 가야 하는” 삼촌이 있었고, 이 방법에 카지노 도시의 이름을 붙인 것이 그 삼촌과 무관하지 않았다고 합니다.

첫 실행은 1948년 봄, 메릴랜드의 애버딘 시험장으로 옮겨진 ENIAC 에서였습니다. 컴퓨터 역사가 토머스 헤이(Thomas Haigh) 등이 2014년에 문서고 자료로 재구성한 바로는, 첫 본 실행이 4월 17일에 있었고 5월 10일에 끝났습니다. 코드의 도식과 작성은 주로 폰 노이만의 아내 클라라 폰 노이만이 맡았던 것으로 보입니다. 폰 노이만은 5월 11일 편지에 일곱 문제를 풀었고 “방법은 분명히 100% 성공” 이라고 적었습니다. 공개 문헌으로는 메트로폴리스와 울람이 1949년 Journal of the American Statistical Association 에 실은 「The Monte Carlo Method」가 첫 논문으로 꼽힙니다.

울람보다 먼저 같은 일을 한 사람도 있었습니다. 메트로폴리스는 엔리코 페르미가 1930년대 초 로마에서 중성자 감속을 연구하며 이미 이 방법으로 계산했다는 에밀리오 세그레의 증언을 옮겨 둡니다. 페르미는 아무것도 발표하지 않았고, 동료들을 놀라게 한 그의 “어림짐작” 이 사실은 잠이 오지 않는 새벽에 가진 계산 도구로 돌린 무작위 표본 계산이었다고 합니다. ENIAC 이 멈춰 있던 1947년 말에는 페르미가 고안하고 퍼시 킹이 만든 FERMIAC 이라는 아날로그 장치가 로스앨러모스에서 같은 일을 했습니다. “몬테카를로 수레” 라고도 불린 이 장치는 2년쯤 중성자 수송 계산에 쓰였습니다.

확률은 평균입니다#

몬테카를로의 뼈대는 한 줄입니다. 어떤 일이 일어날 확률은, 그 일이 일어나면 1 이고 아니면 0 인 값의 평균과 같습니다. 그러니 그 일을 무작위로 여러 번 일으켜 보고 1 이 나온 비율을 세면 확률의 추정값이 됩니다. 확률 대신 평균 점수나 평균 순위 같은 기댓값을 묻는 문제도 똑같이 풉니다. 세는 값이 0 과 1 에서 아무 숫자로 넓어질 뿐입니다.

이것이 맞는 근거는 대수의 법칙입니다. 서로 독립인 시행을 많이 하면 표본 평균은 참값에 가까워집니다. 필요한 것은 시행 한 번을 규칙대로 정확하게 만들어 내는 코드와, 그것을 세는 코드입니다.

// estimate 는 trial 을 n 번 돌려 참이 나온 비율과 그 표준오차를 돌려준다.
func estimate(n int, trial func() bool) (p, se float64) {
	hits := 0
	for range n {
		if trial() {
			hits++
		}
	}
	p = float64(hits) / float64(n)
	return p, math.Sqrt(p * (1 - p) / float64(n))
}

아래 예제는 모두 이 함수 하나로 돌렸습니다. 난수는 Go 표준 라이브러리 math/rand/v2 의 PCG 생성기를 고정한 씨(rand.NewPCG(2026, 1113))로 만들었습니다. 같은 씨로 다시 돌리면 아래 숫자가 한 자리도 다르지 않게 나옵니다.

오차는 √n 으로 줄어듭니다#

두 번째 반환값 se 가 표준오차입니다. 확률이 p 인 일을 n 번 시행해서 센 비율은 참값에서 대략 √(p(1−p)/n) 만큼 흔들립니다. 그 1.96 배를 앞뒤로 붙인 구간이 흔히 말하는 95% 신뢰구간이고, 같은 실험을 백 번 되풀이하면 그중 아흔다섯 번쯤은 이 구간이 참값을 덮습니다. 울람의 백 판에서 다섯 판이 풀렸다면 √(0.05 × 0.95 / 100) ≈ 0.022 이고, 1.96 배 하면 0.043 입니다. 앞에서 말한 4%포인트가 여기서 나옵니다.

분모가 n 이 아니라 √n 이라는 점이 이 방법의 성격을 정합니다. 오차를 10분의 1 로 줄이려면 시행을 100배 해야 합니다. 싸지 않습니다. 대신 이 속도는 문제가 얼마나 복잡한지와 상관이 없습니다. 주사위 하나를 굴리는 문제든, 카드 54장을 네 사람에게 나누고 판 끝까지 두어 보는 문제든, 시행 한 번을 만들 수만 있으면 오차는 같은 비율로 줄어듭니다.

몬티 홀, 셈보다 먼저 납득시키는 것#

세 문 가운데 하나 뒤에 자동차가 있습니다. 참가자가 문 하나를 고르면, 차가 어디 있는지 아는 진행자가 남은 두 문 가운데 염소가 있는 문을 하나 열어 보여 줍니다. 바꾸시겠습니까? 이 블로그의 몬티 홀 시리즈 에서 길게 다룬 문제이고, 답은 바꾸면 3분의 2 입니다.

시뮬레이션으로 옮기면 진행자의 규칙이 그대로 코드가 됩니다.

// montyHall 은 참가자가 문을 바꿀 때 이기는지를 한 판 둔다.
func montyHall(rng *rand.Rand) bool {
	car, pick := rng.IntN(3), rng.IntN(3)
	// 진행자는 참가자가 고르지 않았고 차도 없는 문 가운데 하나를 연다.
	var goats []int
	for door := range 3 {
		if door != pick && door != car {
			goats = append(goats, door)
		}
	}
	opened := goats[rng.IntN(len(goats))]
	// 바꾸면 고른 문도 열린 문도 아닌 남은 문으로 간다.
	switched := 3 - pick - opened
	return switched == car
}

몬티 홀  n=100       바꾸면 이길 확률 0.6400 ± 0.0941
몬티 홀  n=10000     바꾸면 이길 확률 0.6620 ± 0.0093
몬티 홀  n=1000000   바꾸면 이길 확률 0.6666 ± 0.0009

백 판으로도 “반반은 아니다” 까지는 말할 수 있습니다. 구간이 0.546 에서 0.734 까지라 0.5 를 비껴갑니다. 3분의 2 라고 자신 있게 말하려면 만 판쯤은 돌려야 합니다.

몬티 홀 시리즈 Part 1 에 적었듯, 수학자 에르되시 팔도 이 문제를 처음 들었을 때 바꾸든 안 바꾸든 차이가 없다고 했습니다. 동료 앤드루 바존이가 시뮬레이션을 10만 번 돌려 보여 주자 그제야, 이유는 모르겠다면서도 마지못해 받아들였습니다. 이 일화가 몬테카를로의 장점과 한계를 같이 보여 준다고 생각합니다. 숫자는 논쟁을 끝내지만 이유를 알려 주지는 않습니다.

그리고 숫자는 코드에 넣은 규칙만큼만 맞습니다. 위 함수에서 “차도 없는” 이라는 조건 하나를 빼 진행자가 남은 두 문 가운데 아무 문이나 열게 하고, 열린 문이 우연히 염소였던 판만 세면 답은 2분의 1 이 됩니다. 몬티 홀 시리즈 Part 2 가 Go 시뮬레이션으로 확인한 “몬티 폴” 입니다. 시뮬레이션이 무엇을 계산했는지는 결국 시행 한 번을 만드는 함수가 정합니다.

생일 문제로 자를 먼저 잽니다#

스물세 명이 모인 방에서 생일이 같은 두 사람이 있을 확률은 절반을 조금 넘습니다. 이 문제는 손으로 정확히 풀 수 있습니다. 모두 생일이 다를 확률이 365/365 × 364/365 × … × 343/365 이니, 1 에서 이것을 빼면 0.5073 입니다. 윤년은 무시하고 생일이 365일에 고르게 퍼져 있다고 둔 값입니다.

// birthday 는 k 명 가운데 생일이 같은 두 사람이 있는지를 한 번 본다.
func birthday(rng *rand.Rand, k int) bool {
	var seen [365]bool
	for range k {
		day := rng.IntN(365)
		if seen[day] {
			return true
		}
		seen[day] = true
	}
	return false
}

생일 23명 n=100       0.5000 ± 0.0980 (정답 0.5073)
생일 23명 n=10000     0.5003 ± 0.0098 (정답 0.5073)
생일 23명 n=1000000   0.5081 ± 0.0010 (정답 0.5073)

정답이 있는 문제를 굳이 시뮬레이션하는 이유는 자를 재기 위해서입니다. 세 줄 모두 구간이 정답을 덮습니다. 만 판짜리 줄은 아슬아슬합니다. 0.5003 에서 0.5073 까지 0.007 떨어져 있고 구간의 반폭이 0.0098 이니 겨우 안쪽입니다. 운이 나쁜 날의 만 판은 이 정도로 벗어납니다. 이것이 표준오차라는 숫자가 하는 일입니다. 같은 실험을 다시 하면 결과가 얼마나 달라질지를, 실험을 다시 하지 않고도 미리 알려 줍니다.

정답을 모르는 어려운 문제에 시뮬레이션을 쓸 때도 순서는 같습니다. 먼저 정답이 있는 작은 문제로 시뮬레이터가 맞는 답을 내는지 확인하고, 그다음에 큰 문제로 갑니다. 시뮬레이터가 틀렸다는 것은 바깥에서 보면 잘 드러나지 않습니다. 이 블로그의 SICP 7편 에서 몬테카를로로 π 를 구하다가 난수 생성기의 결함 때문에 2.72 가 나온 일이 있었는데, 그때도 코드는 아무 오류 없이 자신 있게 틀린 숫자를 내놓았습니다.

드 메레의 두 내기#

1654년 7월 29일, 블레즈 파스칼은 피에르 드 페르마에게 보낸 편지에서 슈발리에 드 메레라는 사람이 겪은 “큰 스캔들” 을 전합니다. 주사위 하나로 네 번 안에 6 을 한 번 내는 데 거는 내기는 유리하고, 주사위 둘로 스물네 번 안에 6 두 개를 한 번 내는 데 거는 내기는 불리하다는 것이었습니다. 그런데 4 대 6 은 24 대 36 과 같은 비율이니 둘은 같아야 하지 않느냐. 드 메레는 이 때문에 산술이 스스로 모순된다고 큰소리로 말하고 다녔다고 합니다.

// atLeastOne 은 rolls 번 던져 hit 이 한 번이라도 나오는지를 본다.
func atLeastOne(rolls int, hit func() bool) bool {
	for range rolls {
		if hit() {
			return true
		}
	}
	return false
}

six := func() bool { return die() == 6 }
doubleSix := func() bool { return die() == 6 && die() == 6 }

doubleSix 는 첫 주사위가 6 이 아니면 두 번째 주사위를 굴리지 않습니다. 결과에는 차이가 없고 난수를 조금 아낄 뿐입니다.

드 메레 n=1000      한 개 4번 0.5020 ± 0.0310 | 두 개 24번 0.4960 ± 0.0310
드 메레 n=10000     한 개 4번 0.5208 ± 0.0098 | 두 개 24번 0.4827 ± 0.0098
드 메레 n=100000    한 개 4번 0.5196 ± 0.0031 | 두 개 24번 0.4930 ± 0.0031
드 메레 n=1000000   한 개 4번 0.5183 ± 0.0010 | 두 개 24번 0.4916 ± 0.0010
드 메레 정답            한 개 4번 0.5177          | 두 개 24번 0.4914

정답은 1 − (5/6)⁴ = 0.5177 과 1 − (35/36)²⁴ = 0.4914 입니다. 파스칼의 편지도 첫 내기를 671 대 625 로 적어 두었습니다. 두 번째 내기가 반반에서 벗어난 폭은 0.86%포인트밖에 되지 않습니다.

천 판으로는 어느 내기가 유리한지 말할 수 없습니다. 첫 줄의 두 값은 0.502 와 0.496 으로 둘 다 반반에 붙어 있고, 구간이 앞뒤 0.031 이라 두 값의 순서가 뒤집혀 나와도 이상하지 않습니다. 만 판이면 두 번째 내기의 구간 위쪽 끝이 0.4925 라서 “반반보다 불리하다” 를 겨우 말할 수 있습니다. 앞의 공식을 거꾸로 풀면, 0.4914 와 0.5 를 95% 구간으로 가르는 데 내기가 대략 1만 3천 번 필요합니다. 한 번에 주사위 둘을 스물네 번 던지니 31만 번이 넘는 던지기입니다.

그래서 드 메레가 도박판의 경험으로 스물네 번이 불리하다는 것을 알아챘다는 오래된 설명을, 수학사가 오이스테인 오레(Øystein Ore)는 1960년 논문에서 믿기 어렵다고 봤습니다. 스물네 번과 스물다섯 번의 차이가 너무 작아서, 어느 쪽이 반반에 못 미치는지 실험으로 가리려면 적어도 수천 번은 던져야 한다는 것이 이유였습니다. 그는 드 메레가 실제로 돈을 잃어서가 아니라, 그럴듯해 보이던 도박 규칙이 이론 계산과 맞지 않는다는 데 혼란스러워했다고 읽었습니다. 파스칼의 편지도 드 메레가 “이런 이유로” 수에서 거짓을 찾았다고 적을 뿐, 잃은 돈 이야기는 하지 않습니다.

이 예제에서 가져갈 것은 하나입니다. 몇 번 돌려야 하는지는 가르고 싶은 차이의 크기가 정합니다. 차이가 절반으로 줄면 필요한 시행은 네 배가 됩니다.

셀 수 없을 만큼 큰 판#

세 예제는 모두 정답을 손으로 구할 수 있었습니다. 몬테카를로가 정말 필요한 것은 그렇지 않을 때입니다. 울람의 캔필드 솔리테어가 그랬습니다. 52장의 배치 하나하나에 대해 끝까지 풀리는지를 따지는 일은, 배치의 수가 52! 이라 처음부터 셀 대상이 아닙니다.

카드 게임 봇을 만들 때도 같은 벽이 나옵니다. 대부호 한 판의 초반, 내 눈에 보이지 않는 카드 38장이 상대 세 명에게 12장씩, 아무도 받지 않은 블라인드 2장으로 나뉘어 있다고 해 봅시다. 나눌 수 있는 경우의 수는 38! / (12! × 12! × 12! × 2!) 이고, 약 2.4 × 10¹⁸ 입니다. 1초에 10억 가지씩 세어도 75년이 걸립니다. 그런데 이 가운데 무작위로 2만 가지만 뽑아 세면, 어떤 일이 일어날 확률을 앞뒤 0.007 안쪽으로 알 수 있습니다. 경우의 수가 10¹⁸ 이든 10⁸ 이든 표준오차의 공식에는 n 만 들어가기 때문입니다.

이 블로그에서 만든 대부호 CPU 봇은 실제로 이 일을 합니다. 봇의 성적을 재는 장치부터가 몬테카를로이고, 지금 운영 중인 봇은 손패가 다섯 장 이하로 줄면 상대 손패를 열여섯 번 뽑아 판 끝까지 두어 보고 수를 고릅니다. 그 이야기는 다음 편에 따로 적었습니다.

울람이 백 번 펼쳐 보자고 생각한 것은 계산을 포기한 것이 아니었습니다. 계산의 질문을 바꾼 것이었습니다. “정답이 무엇인가” 대신 “정답에 얼마나 가까이 갈 수 있고, 그 가까움을 어떻게 아는가” 를 묻는 쪽으로. 백 판이면 4%포인트, 만 판이면 0.4%포인트. 그 대가가 √n 이라는 것을 아는 순간부터 무작위는 계산의 도구가 됩니다.

자료에 대해#

몬테카를로의 탄생 이야기는 대부분 당사자의 회고에 기댑니다. 울람의 솔리테어 이야기는 1983년의 미발표 발언을 1987년 로스앨러모스 사이언스 특별호에 로저 에크하르트가 옮긴 것이고, 이름의 유래와 페르미의 일화도 메트로폴리스가 같은 호에 40년 뒤 쓴 회고입니다. 페르미의 로마 시절 이야기는 메트로폴리스가 세그레의 증언을 다시 옮긴 것입니다. ENIAC 첫 실행의 날짜와 문제 수는 메트로폴리스의 회고(아홉 문제)와 폰 노이만의 1948년 편지(일곱 문제)가 다르며, 이 글은 당시의 편지와 그것을 문서고 자료로 대조한 헤이 등의 2014년 연구를 따랐습니다. 드 메레의 이야기에서 편지 원문은 그의 이름을 “M…” 으로만 적고 있고, 그것을 드 메레로 읽는 것은 편집자들의 보충입니다. 앞 문단에서 파스칼이 그를 이름으로 부르고 있어 거의 틀림없다고 봅니다. 예제 코드와 출력은 Go 1.26 으로 직접 돌린 것입니다.

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

References#

1차 자료#

역사 연구#

이 블로그의 관련 글#