d라이브러리

오늘 소개할 ‘마스터마인드’는 ‘스무고개’와 비슷한 방식으로 암호를 맞히는 게임이에요. 단, 스무 번이 아니라 보통 열두 번 만에 암호를 맞혀야 하니까 신중하게 임해야 해요!

오늘 소개할 게임은 상대방이 낸 암호를 맞히는 보드게임인 ‘마스터마인드’예요. 마스터마인드는 1970년 이스라엘의 게임 디자이너이자 통신 기술 전문가인 모데카이 메이로위츠가 개발했어요.

메이로위츠가 마스터마인드를 개발했을 때 여러 게임회사에 찾아가 제작을 부탁했는데, 모두 거절당했어요. 다행히 인빅타 플라스틱스라는 회사가 관심을 보였고, 마침내 보드게임으로 탄생했지요.

마스터마인드 보드판의 각 행에는 작은 구멍 4개와 큰 구멍 4개가 있고, 행은 난이도에 따라 개수가 다른데 보통 12개 있습니다. 그 위에 여섯 종류의 색을 가진 구슬, 그리고 빨간 색과 흰 색의 작은 핀이 있지요.

언뜻 보면 규칙이 복잡할 것 같은데, 그리 복잡하지 않으니 한번 차근차근 살펴볼게요.

마스터마인드는 두 사람이 하는 게임입니다. 한 사람은 암호작성자고, 다른 사람은 암호해독자입니다. 암호작성자는 여섯 색깔의 구슬 중 중복에 상관없이 4개를 선택해 보드판 위에 따로 마련된 자리(그림❶)에 숨겨놓습니다. 이제 암호해독자는 구슬의 색을 추측해 첫 행(그림❷)부터 구슬을 4개씩 놓습니다. 만약 숨겨놓은 구슬의 위치와 색이 맞으면 암호작성자는 빨간 핀(그림❸)을 작은 구멍에 꽂고, 구슬 색은 같고 위치가 다르면 흰색 핀을 꽂습니다. 이 두 경우에 해당하지 않으면 핀을 꽂지 않습니다.

이 과정을 반복해서 12행에 이르기 전에 구슬의 색과 위치를 모두 맞히면 암호해독자가 이기고, 그렇지 않으면 암호작성자가 이깁니다. 한 게임이 끝나면 역할을 바꿔 진행하고, 게임을 몇 번 할지 정해 많이 이긴 사람이 최종 승자가 됩니다.

수학으로 분석한 마스터마인드

마스터마인드를 수학적으로 분석한 사람은 미국의 컴퓨터 과학자이자 스탠퍼드대학교의 명예교수인 도널드 크누스입니다. 수학을 전공한 크누스 교수는 불과 28살에 ‘컴퓨터 프로그래밍의 예술’이라는 책을 썼는데, 이 책은 컴퓨터 과학 분야에서 가장 권위 있는 책으로 꼽힙니다. 또, 수학자가 복잡한 수학 기호를 쉽게 쓸 수 있는 조판 시스템을 만들기도 했지요.

크누스 교수는 1976년 ‘유희수학’에 마스터마인드에 관한 논문을 발표했습니다. 이 논문에서 구슬의 색을 1, 2, 3, 4, 5, 6으로 나타냈고, 구슬 4개로 이뤄진 암호는 중복을 허락해서 숫자를 뽑는 것으로 생각했습니다. 따라서 암호는 총 64=1296개 만들 수 있습니다. 크누스 교수는 이 방법으로 단계별로 제시할 숫자를 알려주는 알고리듬을 만든 뒤 ‘많아야 다섯 번 안에 암호를 맞출 수 있다’는 사실을 증명했지요.

크누스 교수의 증명은 매우 복잡하므로 알고리듬이 제시한 숫자로 어떻게 암호를 알아내는지만 소개해 볼게요. 우선 여러분이 암호해독자고 암호작성자가 숫자 4개를 골라 암호를 만들었다고 해봅시다. 일단 다짜고짜 2211을 시도해 봅시다. 만약 암호작성자가 빨간 핀을 4개 놓으면 숫자와 위치가 모두 맞은 거니까 한 번 만에 암호를 찾은 겁니다.

빨간 핀이 3개면 어떨까요? 4개 중에 3개의 색과 위치를 맞혔으니 암호는 221□, 22□1, 2□11, □211 중에 하나이고, □에는 3, 4, 5, 6 중 하나가 들어가야 합니다. 하나당 4가지 경우가 있으니 후보가 총 4×4=16개로 좁혀졌어요. 이제 이 16개 경우 중에서 어떤 게 진짜 암호인지 알아볼게요. 각 경우에 대해 빨간 핀이 한 개 이상 나올 수 있도록 1213을 시도합니다. 빨간 핀이 n개 꼽힌 경우를 nR, 흰색 핀이 m개 꼽힌 경우를 mW로 나타내서 각각의 경우에 어떤 핀이 꽂힐지 따져봅시다.

예를 들어 2231을 1213과 비교하면 두 번째 2의 위치와 숫자가 같고 1과 3은 숫자만 같으니 1R2W가 됩니다. 오른쪽 표를 보면 각 경우에 어떤 핀이 꽂히는지 잘 정리돼 있어요.

1213을 시도해서 나온 경우의 수 16가지 중 빨간 핀 1개, 흰색 핀 2개를 꽂은 경우(1R2W)를 생각해볼게요. 이 경우 암호가 될 수 있는 수는 빨간색으로 표시한 2231, 2411, 2511, 2611입니다. 암호 후보가 4개로 줄었어요. 이 중 답을 알아내기 위해 1415를 시도해 보죠. 그러면 각 암호에 꽂힌 핀은 순서대로 1W, 2R1W, 1R2W, 1R1W가 나올 겁니다.

이제 곧바로 암호를 찾을 수 있습니다. 암호작성자가 이 4개의 핀 값 중 하나를 알려주면 2231, 2411, 2511, 2611 중에 어떤 게 암호인지 알 수 있지요. 16개 중 1R2W가 아닌 경우도 비슷하게 암호를 알아낼 수 있습니다.

처음에 빨간 핀이 두 개 꽂혔을 때와 한 개 꽂혔을 때, 그리고 전혀 꽂히지 않았을 때는 암호의 후보가 16개보다 많지만, 비슷한 방법으로 후보를 좁히면 마찬가지로 다섯 번 안에 암호를 맞힐 수 있어요. 각 경우에 어떤 수를 제시해야 할지 각자 생각해보세요!

4.34번이면 맞힌다!

크누스 교수 외에도 많은 사람이 암호를 찾는 알고리듬을 개발하기 위해 노력했습니다. 1993년에는 컴퓨터 공학자 켄지 코야마와 토니 라이는 평균 4.34번 만에 암호를 맞힐 수 있는 방법을 발표했습니다. 이 연구에 따르면 많아봐야 6번 만에 맞힐 수 있습니다. 2005년에는 미국 케이스웨스턴리저브대학교 컴퓨터공학과의 제프 스턱만과 구오시 앙 장이 각 단계에 무작위로 구슬과 핀이 있을 때 이에 해당하는 암호가 존재하는지 결정하는 문제가 ‘NP-완전’임을 밝혔습니다.

NP-완전은 문제를 푸는 알고리듬의 복잡도가 비슷한 문제끼리 모아둔 집합 P, NP, NP-하드, PSPACE 중 NP와 NP-하드에 속하는 문제예요. 마스터마인드는 규칙은 간단한데 푸는 방법은 어려운 편에 속하지요.

마스터마인드와 비슷한 게임들

마스터마인드와 비슷한 게임을 소개합니다. 원리는 거의 똑같은데 조금씩 다른 점이 있으니 참고해서 다양한 게임을 즐겨보세요. 첫 번째는 ‘불과 카우’입니다.

불과 카우는 종이와 연필로 하는 게임으로, 마스터마인드보다 먼저 만들어졌습니다. 불과 카우도 두 명이서 하는 게임으로 각자의 역할이 다릅니다. 한 명은 황소를 뜻하는 ‘불’을 맡고, 다른 한 명은 젖소를 뜻하는 ‘카우’를 맡지요.

구슬 대신 0부터 9까지 수 중 4개를 골라 암호를 만드는 점과 중복해서 고를 수 없다는 점이 마스터마인드와 다릅니다. 그리고 핀을 놓는 대신 상대방이 제시한 숫자와 위치가 맞으면 불, 숫자는 맞는데 위치가 다르면 카우라고 합니다. 예를 들어, 암호가 1357일 때 상대방이 1235라고 하면 1불, 2카우가 되는 거지요. 불과 카우는 워낙 인기가 많아서 1960년대 후반에 매사추세츠공과대학교의 한 학생이 ‘MOO’라는 게임 프로그램으로 만들기도 했어요.

두 번째 게임은 ‘단어 마스터마인드’입니다. 단어 마스터마인드는 숫자 대신 알파벳 4개로 만든 단어를 암호로 삼습니다. 규칙은 불과 카우와 비슷합니다. 만약 FOUR라는 암호를 만들고 상대방이 GOOD이라고 하면 1불, 0카우가 됩니다. 한글로 만든 마스터마인드는 아직 없는데, 여러분이 만들어 보는 건 어떨까요?(149페이지 문제 3번)

마스터마인드를 좀 더 어렵게 하고 싶으면, 수퍼 마스터마인드에 도전해 보세요. 수퍼 마스터마인드는 마스터마인드와 규칙은 같은데, 구슬의 색이 8개고 구슬을 놓을 수 있는 구멍과 핀을 꽂을 수 있는 구멍 모두 5개입니다. 행의 총 개수는 그대로 12개이니 머리를 좀 더 써야겠죠?

김종락 서강대학교 수학과 교수는 포스텍 수학과를 졸업하고, 서울대학교에서 석사 학위, 미국 일리노이주립대학교 시카고캠퍼스에서 박사 학위를 받았습니다. 주요 연구 분야는 부호론과 암호론, 산업수학, 인공지능입니다. 2004년 캐나다 조합론연구소에서 주는 커크만 메달을 한국인 최초로 받았습니다. 2016년부터 대한수학회 수학문화 앰배서더로 활동 중이며, ‘감성수학레드’라는 스타트업을 운영하고 있습니다.