수십 m 아래로 추락한 천사는 날개를 펴 사뿐히 바닥에 내려앉았어요. 눈앞에는 끝이 보이지 않는 거대한 체스판이 펼쳐졌어요. 그 위에는 악마가 천사를 기다리고 있었어요. 허락 없이 비밀의 집에 들어온 천사가 치러야 할 한판 대결이 시작된 거예요.
“내가 제시하는 게임을 해서 네가 이기면 여기서 사라져 주지.”
악마는 1940년대에 처음 만들어진 ‘천사 게임’을 제안했어요. 천사 게임을 하는 천사와 악마는 무한히 넓은 체스판 위에서 번갈아가며 이동해야 해요.
이동 규칙은 간단해요. 먼저 천사가 원하는 방향으로 최대 n개의 칸만큼 이동해요. 한쪽 방향으로만 가도 되고 방향을 바꿔 가도 상관없어요. 그 다음 악마가 천사가 서 있지 않은 칸 중 하나를 골라 불태워요. 천사는 악마가 불태운 칸을 밟을 수 없어요.
다시 천사의 차례가 되면 천사는 원하는 방향으로 최대 n개의 칸만큼 이동해요. 이 과정을 반복하면서 악마가 불태운 칸이 천사를 완전히 둘러싸면 악마가 승리하고, 악마의 방해에도 불구하고 천사가 끊임없이 앞으로 나아갈 수 있다면 천사의 승리예요.
1982년에 미국의 수학자 엘윈 벌캄프는 천사가 한 번에 한 칸씩만 이동한다면 33×33 크기의 영역 안에서 악마가 천사를 반드시 가둘 수 있다는 논문을 발표했어요.
“이봐, 천사. 한 칸씩 가봤자 날 못 이겨. 한번 봐줄 테니 날 이길 전략을 새롭게 짜보는 건 어때? 그래봤자 내 손아귀에 있을 테지만….”
무조건 천사가 이기는 전략은?
이번에는 천사가 자신의 차례에 어느 방향으로든 최대 2칸을 갈 수 있다는 조건으로 게임을 한다고 가정해요. 한 번에 갈 수 있는 칸이 많을수록 천사에게 유리할 테니까요. 만약 오른쪽 그림처럼 천사 근처에 악마가 불태운 칸이 4개 있는 상황이라면, 천사는 어떻게 나아가야 할까요?
2006년 노르웨이의 소프트웨어 개발자 오드바 클로스터는 사방으로 최대 2칸씩 이동하는 천사가 절대 갇히지 않는 전략을 찾아냈어요. 특정한 함수로 만든 경로를 따라가기만 하면 되는 단순한 방법으로요.
오른쪽 그림처럼 두 경로가 있을 때 둘 다 장점이 있지만 클로스터가 개발한 함수에 따르면 ‘경로1’보다는 ‘경로2’를 고르는 게 천사에게 더 유리해요. 경로2는 경로1보다 경계선이 변 4개만큼 더 길지만 악마가 불태운 칸 4개를 모두 경로 왼쪽에 둬 갇힐 위험이 적기 때문이에요.
물론 경로2 말고도 다양한 경로를 고려할 수 있어요. 새로운 경로의 변의 개수에서 기준 경로(경로1)의 변의 개수를 뺀 값(A), 새로운 경로의 왼쪽에 포함된 붉은 칸의 개수(B)를 찾아 2B-A를 구해보세요. 이 값이 가장 큰 경로가 천사에게 최적의 경로랍니다.
천사는 매 차례마다 클로스터의 전략을 써서 갈 길을 정했어요. 그 결과 악마가 어떻게 방해하더라도 함정에 갇히지 않을 수 있었지요. 체스판 곳곳에는 불길이 일었지만 천사는 막힘없이 체스판을 누빌 수 있었습니다. 천사를 잡지 못한 악마는 그 자리에서 사라져 버렸습니다. 악마든 수학이든 똑똑한 전략 하나면 문제없군요.
