d라이브러리

‘도트 앤 박스’는 프랑스 수학자 에두아르 뤼카가 만든 게임이에요. 뤼카는 피보나치 수열, 루카스 수열★을 연구한 수학자로, 유희 수학에 관심이 많아 도트 앤 박스, 하노이 탑 등 다양한 수학 놀이를 만들었어요. 뤼카는 1889년 유희 수학에 관해 쓴 책에서 도트 앤 박스를 처음 소개했어요.

루카스 수열★
피보나치 수열의 첫째, 둘째 항을 각각 2, 1로 바꾼 수열. 루카스 수열을 이용하면 어떤 자연수가 소수인지 판정할 수 있다.

도트 앤 박스는 가로와 세로가 점 세 개 이상으로 이뤄진 사각형 격자에서 즐기는 게임이에요. 이름에서 알 수 있듯이 상대와 번갈아 가며 이웃한 점을 이어 선분을 그리고, 이 선분을 변으로 하는 정사각형 상자를 완성하면 됩니다. 방법은 간단하지요? 그런데 추가로 알아둬야 할 규칙이 있어요.

먼저 선분은 반드시 하나씩, 가로 또는 세로 방향으로만 그려야 합니다. 그리고 상자의 모든 변을 자기가 그릴 필요는 없어요. 즉 상대가 세 변을 그렸더라도 내가 마지막 한 변을 그리면 내 상자가 되는 거예요. 마지막 규칙이 가장 중요합니다. 내 차례에 선분을 그려 상자를 완성하면 반드시 선분을 하나 더 그려야 해요. 만약 선분을 그릴 때마다 상자를 연달아 완성하면 계속해서 그려도 됩니다.

게임은 모든 선분을 그렸을 때 끝나고, 상자를 많이 완성한 사람이 이깁니다. 만약 상자 수가 같으면 먼저 시작한 사람이 진 거예요. 바둑에서 흑이 먼저 두지만 집 수가 같으면 백이 이기는 것처럼, 먼저 시작한 사람이 유리한데도 비겼으니 실제로는 졌다고 판단하는 거지요.

아래 3×3 격자에서 하는 도트 앤 박스를 보세요. 먼저 그리는 사람을 레드(빨간색 선분), 나중에 그리는 사람을 블루(파란색 선분)로 정하고 레드가 완성한 상자는 R, 블루가 완성한 상자는 B라고 표시해 자기가 그린 선분과 상자를 구분할 수 있도록 했어요.

1946년 초등학생이었던 얼윈 벌리캄프 미국 UC버클리 수학과 교수는 도트 앤 박스에 흥미를 느껴 전략을 연구하기 시작했어요. 벌리캄프 교수는 1982년 유희 수학자 존 콘웨이, 리처드 가이와 함께 쓴 책 ‘수학 놀이에서 이기는 전략’에서 도트 앤 박스의 전략을 소개했고, 2000년에는 도트 앤 박스에 관한 책을 쓰기도 했죠.

그런데 벌리캄프 교수가 항상 이길 수 있는 전략을 찾은 것은 아니에요. 사실 도트 앤 박스에서 이기는 전략을 찾는 문제는 수학에서 몹시 어려운 문제의 모임인 NP-하드★에 속해요. 그래서 몇 가지 상황에서 이길 수 있는 전략을 찾아냈죠.

NP-하드★
문제를 푸는 알고리듬의 복잡도가 비슷한 문제끼리 모아둔 집합으로 P, NP, NP-하드, PSPACE가 있다. NP-하드는 PSPACE 다음으로 복잡한 문제의 집합이다.

소탐대실! 작은 것에 현혹되지 마라
전략을 그냥 알려주면 재미없으니, 퀴즈를 하나 낼게요. 아래 맨 왼쪽 그림은 4×4 격자에서 하는 도트 앤 박스로, 레드가 먼저 시작한 게임입니다. 완성된 상자가 한 개도 없고 선분이 짝수 개 있으니 레드가 그릴 차례예요. 만약 여러분이 레드라면, 다음 두 가지 전략 중 어떤 전략을 택할 건가요?

선분을 하나씩 추가하면 상자 4개를 연달아 완성할 수 있으니 대부분 첫 번째 전략을 선택하고 싶을 겁니다. 그런데 상자 4개를 완성했어도 여전히 상자가 5개 남았다는 사실을 잊지 마세요. 우선 게임을 계속 진행하면서 어떤 전략을 선택해야 하는지 살펴보도록 하죠.

첫 번째 전략을 택했다고 가정해 봅시다. 레드는 상자 4개를 완성한 뒤 다시 선분 한 개를 그려야합니다. 다른 곳에 그려도 결과는 같으니 151쪽의 그림➊처럼 맨 아래 오른쪽(빨간색 점선)에 그렸다고 가정할게요. 그러면 블루는 맨 아래 오른쪽 상자를 완성한 뒤 이웃한 상자 4개를 연달아 완성할 겁니다. 4-0이었던 점수가 순식간에 4-5가 돼서 레드가 집니다.

두 번째 전략을 선택하면 어떨까요? 그림➋처럼 상자 2개를 완성한 블루는 반드시 어딘가에 선분을 추가로 그려야 합니다(파란색 점선). 레드는 그림➌처럼 블루가 그려놓은 선분을 이용해 상자 5개를 한 번에 완성해 버립니다. 처음엔 불리해 보였지만 상자 2개를 미끼로 5개를 얻어 결국 7-2로 레드가 이깁니다. 이런 전략을 ‘속임수 전략’이라고 해요.

상자 고리를 만들어라!
속임수 전략을 쓰려면 ‘격자가 상자 고리로 채워져 있어야 한다’는 조건이 필요해요. 앞서 레드의 성공적인 속임수 전략을 보면 블루가 선분을 그린 뒤 레드가 상자 5개를 연달아 완성했어요. 이렇게 선분을 한 개 추가하면 n개 이상의 상자를 연달아 완성할 수 있는 모양을 ‘길이가 n인 상자 고리’라고 불러요. 여기서 n은 3 이상인 자연수예요.

상자 고리 전략은 격자가 모두 상자 고리로 채워진 직후 선분을 그리는 사람이 반드시 질 수 밖에 없어요. 위 그림은 가운데 선분 6개가 이어진 선을 기준으로 왼쪽에 길이가 4인 상자 고리, 오른쪽에 길이가 5인 상자 고리가 만들어졌어요. 블루가 그릴 차례라면, 블루는 반드시 두 상자 고리 중 한쪽에 선분을 그려야 해요. 이제 레드는 블루가 그려준 선분을 이용해 잽싸게 상자를 연달아 완성할 거예요.

그런데 게임에서 이기려면 레드는 상자 고리에 있는 모든 상자를 완성하면 안돼요. 모든 상자를 완성하면 선분을 하나 더 그려야 한다는 규칙 때문에 남은 상자 고리에 반드시 선분을 그려야하고, 그러면 블루가 남은 상자 고리의 상자를 완성할 테니까요.

따라서 레드는 일부러 상자 두 개를 남긴 채 블루에게 차례를 넘깁니다. 레드가 남긴 두 상자를 완성한 블루는 다시 남은 상자 고리에 선분을 그려야 하므로 레드에게 기회를 넘겨야 합니다. 이렇게 하면 레드는 상자 2개만 내주고 모든 상자 고리를 차지할 수 있지요.

도트 앤 박스, 다양하게 즐기자!
사각형뿐 아니라 삼각형 혹은 육각형 상자를 만드는 도트 앤 박스도 있어요. 상자가 사각형이면 상자 1개를 만드는 데 선분 4개가 필요하지만, 삼각형은 선분이 3개만 있어도 되니까 상자를 더 빠르게, 많이 만들 수 있어요. 육각형 상자는 선분이 6개나 필요해서 더 복잡하고, 선분 한 개를 그릴 때 더 신중하게 생각해야 합니다. 격자 모양이 달라도 속임수 전략을 사용하거나 상자 고리를 만들어야 한다는 사실에는 변함이 없습니다.

도트 앤 박스와 원리가 같은 ‘끈과 동전’ 게임이 있어요. 격자에서 만들 수 있는 상자 수만큼 동전을 사각형 격자 모양으로 늘어놓고 끈으로 이웃한 동전을 이은 뒤, 변에 있는 동전은 밧줄을 1개 또는 2개 추가해 모든 동전에 연결된 밧줄이 4개가 되도록 합니다. 이제 상대와 번갈아 가며 가위로 끈을 하나씩 끊습니다. 동전과 연결된 끈 4개를 모두 끊으면 그 동전을 가질 수 있고, 도트 앤 박스와 마찬가지로 동전을 얻은 뒤엔 끈 하나를 더 끊어야 합니다. 도트 앤 박스의 상자 한 개가 동전 한 개와 같고, 이웃한 두 상자는 끈으로 연결한 동전과 같습니다. 두 상자가 공유하는 선분을 그리는 것은 동전 사이의 끈을 끊는 것과 같지요.

도트 앤 박스는 준비물도 간단하고 규칙도 쉽지만, 한 수 앞을 내다보고 선분 하나하나를 신중하게 그려야 합니다. 친구와 다양한 크기의 격자에서 게임을 즐기고, 새로운 전략을 찾아보세요!