사다리타기를 처음 만들 때 저희도 당연히 이렇게 생각했어요. 가로줄을 무작위로 그으면 그게 곧 추첨이겠지. 그런데 막상 만들어 보니 그렇게만 하면 생각보다 공정하지 않습니다.
가로줄만 무작위로 그으면 생기는 일
세로줄이 5개고 가로줄을 아무렇게나 열 개쯤 그었다고 해 볼게요. 가로줄 하나는 옆 칸 두 사람의 자리를 맞바꾸는 일과 같습니다. 그러니까 사다리 전체는 "옆자리끼리 바꾸기"를 여러 번 한 결과예요.
문제는 바꾸기 횟수가 적으면 자기 자리 근처에서 끝날 확률이 높다는 점입니다. 맨 왼쪽에서 출발한 사람이 맨 오른쪽 결과에 닿으려면 최소 네 번은 오른쪽으로 건너가야 하거든요. 줄이 성기면 그 일이 잘 안 일어납니다. 사다리 그림만 믿으면 "1번 자리가 1번 결과에 걸릴 확률"이 다른 칸보다 확실히 높아져요.
그래서 결과를 먼저 섞습니다
해결은 단순했어요. 사다리 아래에 놓이는 결과(당첨, 꽝)를 먼저 완전히 무작위 순서로 섞어 두고, 사다리는 그 위에 그립니다. 사다리가 어떤 모양이든 결과의 배치 자체가 이미 공평하게 섞여 있으니, 누가 어느 줄에서 출발하든 당첨될 확률이 같아집니다.
// 당첨 2개, 나머지는 꽝으로 채운 뒤 통째로 섞기
results = [];
for (var i = 0; i < n; i++) results.push(i < S.wins ? S.win : S.lose);
results = RT.shuffle(results);여기서 쓰는 shuffle은 피셔-예이츠 방식이에요. 뒤에서부터 한 칸씩, 아직 안 정해진 칸 중 하나를 골라 바꿉니다. 이렇게 하면 가능한 모든 순서가 정확히 같은 확률로 나와요. 흔히 쓰는 sort(() => Math.random() - 0.5)는 브라우저마다 정렬 방식이 달라서 순서가 고르게 안 섞입니다.
function shuffle(arr) {
var a = arr.slice();
for (var i = a.length - 1; i > 0; i--) {
var j = rnd(i + 1), t = a[i];
a[i] = a[j]; a[j] = t;
}
return a;
}그럼 사다리 그림은 장식인가요
반은 맞아요. 결과를 정하는 데에는 필요 없지만, 사람들이 결과를 믿게 만드는 데에는 꼭 필요합니다. 자기 이름에서 줄이 내려가 꺾이고 꺾여 결과에 닿는 걸 눈으로 봐야 "조작 아니야?" 소리가 안 나오거든요.
그래서 가로줄은 보기 좋게 그리는 데 신경을 씁니다. 같은 높이에 붙은 가로줄 두 개가 이어지면 어느 쪽으로 가야 할지 헷갈리니까, 한 칸에 가로줄을 놓았으면 바로 옆 칸 같은 높이에는 놓지 않아요. 각 자리에 가로줄을 놓을 확률은 42%로 두고, 어느 두 줄 사이든 가로줄이 최소 2개는 있도록 마지막에 채워 넣습니다. 세로 칸 수도 사람 수에 맞춰 늘려서(사람 수 + 6, 최소 9칸) 너무 단조롭지 않게 했습니다.
줄을 다 그린 다음에는 각 출발점에서 실제로 줄을 따라 내려가 도착점을 계산합니다. 화면에 그려지는 경로와 결과가 어긋나는 일이 없게요.
정리하면
- 공정함은 결과 배치를 섞는 데서 나옵니다.
- 사다리 그림은 그 결과를 눈으로 확인시키는 역할이에요.
- 섞을 때는 피셔-예이츠, 난수는 편향 없는 정수 난수를 씁니다. 이건 다음 글에서 따로 다뤘어요.
직접 해 보기: 사다리타기