숫자야구, 그냥 찍고 있지 않으신가요?
숫자야구는 간단해 보이지만 의외로 깊은 전략이 숨어 있는 게임입니다. 상대방이 생각한 3~4자리 숫자(각 자리 숫자는 모두 다름)를 제한된 횟수 안에 맞히는 이 게임, 단순히 감으로 찍으면 10번이 넘게 걸릴 수도 있습니다.
하지만 정보이론(Information Theory)과 최적 소거법을 활용하면 거의 항상 4~5번 안에 정답을 찾을 수 있습니다. 이 글에서 그 전략을 모두 공개합니다.
숫자야구 기본 규칙 복습
혹시 처음 접하시는 분을 위해 규칙부터 정리합니다.
- Strike(스트라이크): 숫자와 위치가 모두 맞음
- Ball(볼): 숫자는 맞지만 위치가 다름
- Out: 해당 숫자가 정답에 없음
예시: 정답이 4 2 7이고, 내가 1 2 3을 불렀다면 → 1S 0B (2의 위치가 맞음)
3자리 숫자야구에서 가능한 경우의 수는 0~9 중 서로 다른 3개를 순서 있게 나열한 것으로 10 × 9 × 8 = 720가지입니다.
정보이론으로 이해하는 최적 첫 수
엔트로피란 무엇인가?
정보이론의 핵심 개념인 엔트로피(Entropy)는 "불확실성의 크기"를 나타냅니다. 게임 초반에는 720가지 가능성이 모두 열려 있으므로 엔트로피가 최대입니다. 좋은 추측은 이 엔트로피를 가장 빠르게 줄이는 것입니다.
즉, 한 번의 추측으로 가능한 경우의 수를 가장 균등하게 분할하는 숫자가 최적의 첫 수입니다.
최적 첫 수: 1 2 3 또는 0 1 2
컴퓨터 시뮬레이션으로 검증된 결과, 3자리 숫자야구에서 최적의 첫 추측은 0 1 2 또는 1 2 3처럼 연속된 작은 숫자 조합입니다.
이 추측의 결과는 총 14가지 패턴(0S0B, 1S0B, 0S1B, ... 3S0B)으로 나뉘는데, 각 패턴이 상대적으로 균등하게 경우의 수를 나눕니다. 특히 3S0B가 나오면 그 즉시 정답이고, 다른 결과들도 남은 경우를 80~150개 수준으로 줄여줍니다.
단계별 최적 전략
1단계: 첫 번째 추측 — 정보 최대화
추천 첫 수: 1 2 3
이 선택의 이유는 가장 많이 쓰이는 숫자 영역(1~3)을 테스트하면서, 결과에 따라 남은 경우의 수를 효율적으로 줄이기 때문입니다.
- 0S 0B → 1, 2, 3이 모두 없음. 남은 후보: 약 60가지
- 1S 0B → 정확히 한 자리만 맞음. 남은 후보: 약 120가지
- 0S 1B → 숫자 하나는 있지만 위치가 틀림. 남은 후보: 약 108가지
- 1S 1B → 스트라이크 1, 볼 1. 남은 후보: 약 80가지
2단계: 두 번째 추측 — 탐색 영역 확장
1단계 결과를 토대로 테스트하지 않은 숫자 영역을 탐색합니다.
1단계에서 0S 0B가 나왔다면(1, 2, 3 모두 없음) → 두 번째 추측: 4 5 6
1단계에서 1S 0B가 나왔다면 → 어떤 위치가 맞는지 특정하는 추측을 설계합니다.
핵심 원칙: 두 번째 추측은 첫 번째와 겹치는 숫자를 최소화해서 새로운 정보를 최대로 얻습니다.
3단계: 소거법으로 범위 압축
1~2번의 추측으로 얻은 정보를 조합하면 이미 가능한 경우가 20~50개 수준으로 줄어듭니다. 이때부터는 적극적인 소거법을 사용합니다.
소거법 4가지 규칙
- Out 처리된 숫자 완전 제거: 결과에서 Ball/Strike가 0개인 숫자는 정답에 절대 없습니다.
- Strike 자리 고정: 스트라이크가 난 자리의 숫자는 그 위치에 반드시 있습니다.
- Ball 숫자 재배치: Ball이 난 숫자는 다른 위치에 있어야 합니다. 시도한 위치는 제외하고 남은 자리에 넣어야 합니다.
- 교차 추론: 여러 번의 결과를 교차해서 더 많은 정보를 추론합니다.
실전 예시: 4번 안에 맞히기
정답을 7 3 9라 가정하고 전략을 따라가 보겠습니다.