한국야구위원회(KBO)의 2012년 경기일정표 분석 결과, 프로야구 각 구단의 이동거리는 롯데 자이언츠가 9200km로 가장 길고, LG 트윈스가 5500km로 가장 짧은 것으로 나타났다. 사진은 8월 서울 잠실야구장에서 열린 롯데와 LG의 경기 모습.
이처럼 방문 도시가 몇 개 안 되면 일정을 효율적으로 짜는 것이 어렵지 않다. 하지만 대통령선거(대선)가 임박한 대선후보가 우리나라 선거구 250여 곳을 도는 유세 일정을 짜야 한다면, 이는 무척 어려운 문제가 된다. 컴퓨터과학 분야에서는 이것을 ‘돌아다니는 판매원 문제(travelling salesman problem)’라고 부른다.
즉, 어떤 이동경로를 택해야 모든 방문지를 돌아다니는 전체 이동거리를 가장 짧게 만들 수 있을지 찾아야 하는 것이다. 이런 성격의 문제를 최적화 문제라고 한다. 가장 작게 만들고자 하는 어떤 양(목적함수라 부르는데, 위에서는 전체 이동거리의 총합이 바로 이 양이다)을 주면 어떻게 해야 그 목표를 달성할지 해결하는 문제다.
필자가 속한 통계물리학 분야에서는 매년 대학원생을 대상으로 약 일주일간 겨울학교를 연다. 필자는 매년 주제를 바꿔 진행하는 이 겨울학교에서 학생들에게 어떤 모둠 과제를 줄지 고민한 적이 있다. 필자의 강의는 ‘몬테카를로 방법’이라는 통계물리학의 가장 중요한 컴퓨터 계산방법에 대한 것이었다. 주어진 온도에서 물리계의 평형상태가 어떤 것인지를 체계적으로 알아보는 계산법이다.
만약 온도가 절대온도 0도가 되면 모든 물리계는 가장 낮은 에너지를 갖는 ‘바닥상태’에 있게 된다. 물이 아래로 흐르는 이유는 물이 위에 있을 때보다 아래에 있을 때 에너지가 더 낮기 때문이고, 번개가 치는 이유는 번개 치기 전보다 친 후의 에너지가 더 낮기 때문이다. 이처럼 자연에서 일어나는 변화 중에는 에너지의 높고 낮음으로 이해할 수 있는 것이 많다. 사실 더 정확히는 에너지와 함께 엔트로피의 변화도 함께 고려한 자유에너지로 설명하는 것이 맞다.
‘돌아다니는 판매원 문제’
통계물리학의 몬테카를로 방법을 이용한 컴퓨터 프로그램을 실행하면서 온도를 천천히 낮추면(컴퓨터가 있는 방 온도가 아님! 연구실 온도만 내려도 ‘바닥상태’가 찾아지면 얼마나 좋을까) 결국 물리계는 가장 낮은 에너지를 갖는 ‘바닥상태’로 가게 된다. 필자 같은 물리학자에게 최적화 문제는 곧 가장 낮은 에너지를 갖는 절대온도 0도에서 물리계의 바닥상태를 찾는 문제와 동일하다.
앞서 이야기한 떠돌이 보따리장수의 이동경로를 구하는 문제는 이동거리의 총합을 에너지라고 부르기만 하면 이미 절반은 해결된 것이나 마찬가지다. 해결해야 할 문제의 나머지 절반, 즉 몬테카를로 방법으로 에너지가 낮은 상태를 찾아내는 일도 사실 별로 어렵지 않다.
예를 들어 땅 근처에서 중력을 느끼는 돌멩이의 에너지가 가장 낮은 ‘바닥상태’를 찾는 것을 생각해보자. 먼저 돌멩이가 어떤 높이에 있다고 가정한 뒤 동전을 던져서 앞면이 나오면 돌멩이를 현재 높이보다 조금 위로 옮기고, 뒷면이 나오면 조금 아래로 옮기자. 돌멩이의 새로운 위치에서 에너지를 계산한 다음 방금 전 높이에 있었을 때의 에너지와 비교하면, 돌멩이는 지면에 가까워질수록 에너지가 낮아지니 현재 위치보다 위로 옮겨진 돌멩이는 에너지가 높아질 테고 아래로 옮겨진 돌멩이는 에너지가 낮아질 것이다.
몬테카를로 방법에서는 에너지가 높아지는 시도는 그냥 무시해버리고(원래 위치로 돌멩이를 다시 옮겨놓는다), 에너지가 낮아지는 시도는 받아들여 돌멩이를 아래로 옮긴다. 이 과정을 여러 번 반복하면 돌멩이는 조금씩 아래로 옮겨질 것이다. 지면에 닿을 때까지 말이다. 땅에 닿은 돌멩이의 에너지가 가장 낮으므로 이후에는 계속 땅 위에 머물게 된다.
돌멩이의 중력장 안에서의 ‘바닥상태’를 찾는 위 과정에서 ‘돌멩이가 일단 지면에 닿으면 땅속으로 들어가지 못한다’ 같은 조건을 ‘제약 조건’이라고 부른다. 사실 손에서 놓은 돌멩이가 어떻게 될지를 이해하려고 몬테카를로 방법을 이용해 컴퓨터 프로그램을 만드는 물리학자는 없다. 고등학교 물리학에서 배우는 아주 간단한 한 줄의 수식으로 쉽게 이해할 수 있으니까. 하지만 팔도강산 방방곡곡을 돌아다니는 떠돌이 보따리장수의 이동경로 최적화 같은 복잡한 문제의 경우에는 컴퓨터를 이용한 계산이 필수적이다.
필자가 앞서 언급한 겨울학교에서 대학원생들에게 준 모둠 과제는 ‘우리나라 프로야구팀의 이동거리 차이를 최소화하는 경기일정을 만들라’는 것이었다. 이 문제에서 가장 작게 만들고자 하는 ‘에너지’에 해당하는 양은 각 프로야구팀의 이동거리 불평등이다. 한국야구위원회(KBO) 홈페이지에는 경기일정표와 함께 일정표를 만들 때 적용하는 다양한 규칙(예를 들어 개막전 경기는 어떻게 구성하며, 어린이날과 올스타전 경기 규칙은 무엇인지 등)을 게시해놓았다. 이를 참조해 실제로 사용하는 경기일정표보다 이동거리 면에서 더 공평한 경기일정표를 몬테카를로 방법을 이용해 찾으라는 과제였다.
‘그림’의 지도를 보자. 2012년 현재 프로야구 8개 구단 홈구장 중 4개는 인구가 많은 수도권에 오밀조밀 모였고, 나머지 4개는 띄엄띄엄 떨어져 있다. 홈구장 위치에 대한 고민 없이 프로야구 경기일정표를 만들면 당연히 수도권 구단은 다른 지역 구단보다 이동거리가 짧을 것이다. 반면 부산에 홈구장이 있는 롯데는 홈경기와 원정경기를 번갈아 하면 수도권과 부산을 여러 번 왔다 갔다 해야 한다.
롯데 9200km, LG 5500km 이동
2012년 KBO에서 실제로 운영한 경기일정표를 따라 각 구단이 페넌트레이스 동안 이동한 거리를 계산해 그린 것이 ‘그래프1’이다. 아니나 다를까, 실제 경기일정표에 따라 계산해본 각 구단의 이동거리는 구단별로 많이 달랐다. 롯데가 9200km로 가장 길고, LG는 5500km에 불과하다. 흥미롭게도 서울 잠실구장을 LG와 함께 홈구장으로 사용하는 두산의 경우는 이동거리가 LG보다 상당히 긴 6800km였다.
KBO도 롯데의 이동거리가 길다는 사실을 당연히 알아서 원정 9연전을 전혀 허락하지 않는 다른 팀과 달리 롯데의 경우는 원정 9연전을 한 번 하도록 경기일정표에 예외를 뒀다. 하지만 이동거리의 불평등을 해소하기에는 턱없이 부족하다는 점을 알 수 있다.
자, 그럼 어떻게 하면 공평한 경기일정표를 만들 수 있을까. 앞서 이야기한 것처럼 필요한 것은 두 가지뿐이다. 먼저 에너지를 정의하는 것인데, 이는 간단하다. 각 팀 이동거리가 얼마나 많이 다른지 재는 이동거리의 ‘표준편차’를 에너지라고 부르면 된다. 그리고 매번 주어진 제약 조건(앞의 예에서 돌멩이가 땅속으로 들어가지 못하는 것과 같은 조건)을 만족시키며 경기일정표를 조금씩 바꿔보는 과정을 죽어라고 반복하면서 에너지를 줄여나가면 된다.
사람은 지겨워서 이런 일은 못한다. 아무리 대학원생이라 해도(참고로 우리나라에서 코끼리를 냉장고에 넣는 여러 방법 가운데 필자가 실제로 성공을 경험한 것은 ‘대학원생 시킨다’이다). 하지만 통계물리학을 전공하는 우리나라의 우수한 대학원생들에게 몬테카를로 방법을 적용해 이동거리가 공평한 경기일정표를 만들라는 과제를 주면 단 며칠 안에 컴퓨터 프로그램을 만들고 결과를 얻어 발표한다. 그렇게 얻어진 경기일정표에 따라 각 팀의 이동거리를 다시 계산해 ‘그래프2’를 그렸다. 원래 경기일정표(‘그래프1’)에 비해 각 팀의 이동거리 차이가 상당히 줄었음을 알 수 있다.
우리나라 프로야구 경기일정에 대한 이 연구는 겨울학교에서 모둠 과제를 수행한 대학원생 김상우, 정향민, 김아람, 최영욱, 그리고 처음 연구 아이디어를 생각할 때 도움을 준 은종현 박사님과 함께 논문 형태로 출간했다. 재미있는 내용이라 생각했는지 몇몇 언론이 소개하기도 했다. 필자의 연구 중 신문지상에 소개된 논문이 이전에도 간혹 있었다. 그러나 과학면이 아닌 스포츠면에 실린 연구는 아직까지는 (그리고 아마 앞으로도) 이 논문 하나뿐이다. 필자 주변에서 신문 스포츠면에 소개된 물리학 학술지 논문이 있는 물리학자도 보지 못했다. 이 연구가 자랑스러운 이유다.
많은 사람 아이디어 모으는 것도 방법
프로야구 선수들은 홈구장과 원정구장을 버스로 오가며 경기를 치른다. 사진은 두산 베어스 선수들이 한화 이글스의 홈구장인 대전 한밭야구장을 빠져 나가는 모습.
필자가 당장이라도 살펴보고 싶은 또 다른 최적화 문제가 있다. ‘주간동아’ 887호에 게재한 글 ‘학교·병원은 커피점이 아니다’에서 어떻게 학교를 배치하는 것이 좋을지에 대해 이야기한 적이 있다. 이 문제의 앞뒤를 살짝 바꾸면, 학교 위치가 주어졌을 때 어떻게 학생들을 각 학교에 배정하는 것이 소위 ‘근거리 배정원칙’을 가장 잘 따르는 것인지 결정하는 문제가 된다. 이 문제를 자세히 살펴보고 싶은 마음이 있다. 필자의 도움이 필요한 관계자 분이 이 글을 본다면 연락 주시길.
좋은 프로야구 경기일정표를 만드는 다른 방법도 있다. KBO에서 약간의 상금을 걸고 경기일정표를 공모하는 것이다. 우리나라에 프로야구팬이 얼마나 많은가. 경기일정표를 많은 사람으로부터 공모를 통해 제출받고, 이렇게 제출된 경기일정표에 대한 심사 및 선정도 많은 사람에게 맡기면 어떨까. 많은 경우 평범한 대중은 우수한 극소수의 엘리트보다 더 합리적인 결정을 내린다. 다음 글은 ‘대중의 지혜’에 대한 내용이 될 것이다.