d라이브러리

자동차를 몰고 있는 살인마가 한 사람을 쫓습니다. 아직까지 운 좋게 피하고 있지만, 까닥하다가는 자동차에 치여버릴 것만 같습니다. 어떤 원한 관계가 있는지는 모릅니다. 도무지 쫓는 이유도 모르겠습니다. 단지 이 사람이 지금 할 수 있는 건 단 한 가지. 차를 끌고 따라 오는 살인마에게 절대 붙잡히지 않게 도망가기 뿐!

살인마가 몰고 있는 자동차는 달리는 사람보다 훨씬 빠르게 움직일 수 있지만 회전하는 데 제약이 있습니다. 맨몸으로 달리는 사람은 자동차보다 훨씬 느리지만 요리조리 피해 다닐 수 있다는 장점이 있지요. 살인마는 미친 듯이 쫓고, 도망자는 기를 쓰고 도망갑니다. 쫓고 쫓기는 이 긴장감 넘치는 추격전에서 살인마는 도망자를 언제 잡을 수 있을까요?

참여자가 움직이는 게임

이 문제를 일반화하면 어떤 상황에서 두 사람이 참여해 각자의 최선의 방법을 찾는 문제가 됩니다. 그리고 이런 문제를 수학에서 ‘게임 이론’이라고 하지요. 그런데 익히 알고 있던 게임 이론 문제와는 조금 달라 보입니다. 그저 기분 탓일까요?

게임 이론이라 하니 유명한 수학자와 이론이 떠오를 겁니다. ‘내시 균형’을 만든 미국의 수학자 존 내시입니다. 그런데 내시 균형은 게임 이론 중에서도 ‘비협조 게임’에만 적용됩니다. 게임 이론은 10개가 넘는 연구 분야로 갈래가 나뉘며, 종류에 따라 게임 상황은 물론 분석하는 방법도 다 다릅니다. 

그중에 게임 참여자의 전략을 연속적인 시간에 대한 함수로 나타내서 상황을 연구하는 것이 있습니다. 

살인마 운전기사 게임

앞서 소개한 살인마 운전기사와 도망자의 추격전을 다룬 문제가 대표적인 예입니다. 미국 수학자 루퍼스 이삭이 1951년에 ‘살인마 운전기사 게임’이라는 이름을 붙여 소개했는데요. 살인마와 도망자를 각각 추적자와 회피자로, 살인마가 도망자를 잡는 상황을 충돌한 것으로 가정했습니다. 이런 종류의 문제를 ‘추적-회피 게임’이라고 합니다. 

이삭은 살인마가 모는 자동차가 맨몸으로 달리는 도망자를 얼마나 빠른 시간 안에 잡을 수 있는지 궁금해했습니다. 그리고 살인마 운전기사가 타고 있는 자동차와 사람의 상대적 위치를 그림으로 나타냈습니다. 

아무리 빠른 자동차라도 회전 반경에는 한계가 있는데요, 자동차가 한 번에 이동할 수 없는 사각지대가 생기기 때문입니다. 가령 주차장에 주차돼 있는 자동차가 바로 옆 칸으로 이동하는 경우를 생각해 보세요. 자동차는 옆 칸으로 곧바로 이동할 수 없고 크게 돌아와야 합니다. 만약 도망자가 이 위치에 있었다면, 도망가 버리겠죠.

오른쪽 그림은 바로 이런 상황을 나타낸 겁니다. P에서 출발한 살인마의 자동차가 바로 옆에 있는 원 구역에 들어가려면 넓게 한 바퀴 돌아와야 합니다. 즉 이 원이야 말로 도망자에게 안전한 곳이지요. E에서 출발한 도망자는 살기 위해 원 안으로 달려 들어갑니다. 하지만 방심은 금물입니다. 자동차가 a점에 도달하기 전까진 무사하지만, 그 이후에는 직진하는 자동차의 빠른 속도를 견뎌낼 수 없으니 자동차에 치여 버릴 겁니다.

이외에도 이삭은 여러 구간에 대해 방법을 찾아놨는데, 해결하지 못한 부분은 물음표로 남겨 놓았습니다. 더 이상 하지 않겠다고 당당하게 적어놓은 채로요. 이후 1971년에 미국 스탠퍼드대학교 항공공학과 대학원생인 안토니 메르츠가 이삭이 물음표로 남겨놓았던 복잡한 부분까지 해결합니다. 

이런 추적-회피 게임은 자동으로 움직이는 기계를 최적의 상태로 제어할 방법을 연구하는 ‘최적제어이론’ 분야에서 많이 응용되고 있습니다. 예를 들면 군에서 미사일의 탐지 범위를 찾거나 제어하는 방법을 찾을 때 쓰는거죠.