추첨기를 만들었는데 공정하지 않았다

회식 사다리타기가 지겨워서 추첨기를 하나 만들었다. 오락실에 있는 그 코인 밀기 기계다. 참가자 이름을 넣으면 각자 코인이 되어 판 위로 쏟아지고, 밀대가 왔다 갔다 하다가 판 밖으로 제일 먼저 떨어지는 코인의 주인이 당첨이다.

만들고 나서 몇 판 돌려봤다. 코인이 부딪히고 튕기고 낑겨서 어디로 갈지 전혀 모르겠더라. 잘 만들었다고 생각했다.

그런데 이게 공정한지는 눈으로 봐서는 알 수 없다. 무작위처럼 보이는 것과 무작위인 것은 다르다. 그래서 측정했고, 결과가 처참했다.

측정할 수 있게 먼저 만들었다

측정하려면 같은 판을 다시 돌릴 수 있어야 한다. Math.random()을 쓰면 매번 다른 판이 나와서 "이 편향이 진짜인지 우연인지"를 구분할 수 없다.

그래서 시드를 받는 PRNG부터 넣었다. mulberry32다.

export function createRng(seed: number): Rng {
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

25줄짜리다. 같은 시드면 항상 같은 수열이 나오고, 게임 안의 모든 무작위(코인 크기, 초기 위치, 튕기는 세기, 돌발 이벤트)가 전부 이 하나를 통과한다.

이걸 넣고 나서야 시드 0번부터 299번까지 300판을 자동으로 돌리고 당첨자를 세는 일이 가능해졌다. 여기서부터 진짜 이야기가 시작된다.

1차 측정: 먼저 들어온 사람이 이긴다

20명으로 300판을 돌렸다.

χ²=138.7 (자유도 19). 균등 분포와는 거리가 아주 멀다는 뜻이다.

원인은 어이없을 만큼 단순했다. 참가자 코인을 순서대로 하나씩 떨어뜨리고 있었다. 먼저 들어온 코인은 밀대에 그만큼 더 오래 밀린다. 판 밖으로 나가는 데 유리할 수밖에 없다.

이건 게임을 백 번 봐도 안 보인다. 매 판 코인들은 정신없이 부딪히고, 당첨자는 매번 바뀐다. 눈에는 완벽하게 무작위로 보인다. 300판을 세기 전까지는.

고쳤는데 안 고쳐졌다

간단해 보였다. 순차 투입을 없애고 전원을 같은 순간에 쏟으면 "투입 순서"라는 개념 자체가 사라진다.

바꾸고 다시 300판을 돌렸다. 40명 기준 χ²=220. 300판 중 한 번도 못 이긴 참가자가 여전히 있었다.

여기서 한참 헤맸다. 같은 시각에 넣었는데 왜 순서가 남아 있나.

답은 게임 루프에 있었다. 같은 시각의 코인들은 큐에 담긴 순서대로 world.coins 배열에 들어간다. 그리고 충돌 해소가 그 배열 순서대로 돈다. 겹쳐서 시작한 코인 무리에서는 배열 앞쪽 코인이 뒤쪽 코인보다 체계적으로 먼저 밀려난다.

참가자 1번을 배열 0번에 넣고 있었으니, 투입 시각을 똑같이 맞춰도 참가자 번호가 그대로 배열 순서로, 배열 순서가 그대로 유불리로 이어졌다. 순차 투입을 없앤 자리에 똑같은 편향이 다른 옷을 입고 앉아 있던 셈이다.

진짜 고침: 참가자와 자리를 끊는다

배열 순서 자체를 없앨 수는 없다. 배열은 순서가 있는 자료구조다. 그래서 참가자와 배열 위치의 연결을 끊었다.

// 참가자 순서를 섞어, 배열 위치와 시작 자리 둘 다 참가자와 무관하게 만든다.
const order = names.map((_, i) => i);
for (let i = order.length - 1; i > 0; i--) {
  const j = Math.floor(rng() * (i + 1));
  [order[i], order[j]] = [order[j], order[i]];
}

Fisher-Yates로 한 번 섞는다. 이제 참가자 1번이 배열 0번에 앉을 확률은 1/n이다. 배열 앞쪽이 여전히 유리하더라도, 거기 누가 앉는지가 무작위라면 특정 참가자가 유리해지지 않는다.

여기에 하나 더 넣었다. 코인들이 다 들어온 직후 판 위 모든 코인을 한 번 무작위로 흔든다.

export function scrambleCoins(game: Game): void {
  for (const coin of game.world.coins) {
    const angle = game.rng() * Math.PI * 2;
    const power = randRange(game.rng, 90, 240);
    coin.vx += Math.cos(angle) * power;
    coin.vy += Math.sin(angle) * power;
  }
}

줄 맞춰 내려앉은 모양 그대로 밀려가는 걸 막기 위한 것이다. 중요한 건 세기 분포가 모든 코인에 동일하다는 점이다. 특정 코인만 세게 흔들면 그게 또 편향이 된다.

2차 측정

수정 전 20명에서 138.7이던 값이 10.27이 됐다. 시작 등수별 분포, 앞 1/4 승률(26/24/21%, 균등이면 25%)도 전부 균등과 일관됐다. 소요 시간은 8~48초로 그대로다.

세 번째 문제: 40명이 한계였다

분포가 균등해진 뒤에도 걸리는 게 하나 남았다. 사람을 많이 넣으면 어떻게 되나.

판 크기가 420x240이다. 참가자를 계속 늘려봤다.

200명이면 열에 여덟은 자기 코인이 판에 올라가지도 못한 채 게임이 끝난다. 이건 확률이 낮은 게 아니라 애초에 참가하지 못한 것이다. χ²로는 안 잡히는 종류의 불공정이다.

그래서 MAX_PLAYERS를 실측 안전선인 40으로 낮췄다. 입력 화면에서 41명째부터 막는다. 기능을 줄이는 결정이지만, 공정하지 않은 추첨기는 추첨기가 아니다.

남은 것

이 작업에서 제일 오래 걸린 건 물리 엔진도 렌더링도 아니었다. "이게 공정한가"를 확인할 수 있는 상태로 만드는 것이었다.

시드 PRNG 25줄이 없었으면 1차 측정 자체가 불가능했다. 편향은 여전히 거기 있었을 거고, 나는 잘 만들었다고 생각한 채로 배포했을 거다. 실제로 첫 며칠은 그렇게 생각하고 있었다.

무작위로 보이는 것은 검증이 아니다. 눈은 300판을 세지 못한다.

글 쓰면서 12명으로 한 판 돌려봤다. 13초쯤 판이 좌우로 기울었고, 하늘이 코인이 먼저 떨어졌다. 이제는 그게 하늘이가 몇 번째로 입력됐는지와 아무 상관이 없다는 걸 안다.

직접 돌려보실 수 있다. 코인 밀기 추첨기