테트리스를 수학적으로 정복하기, 컴퓨터는 어떻게 게임을 '치트'하는가

익숙한 게임, 낯선 깊이

누구나 어릴 적 한 번쯤 테트리스를 해봤을 거예요. 떨어지는 블록을 빈틈없이 쌓아 한 줄을 채우면 사라지는 그 단순한 게임 말이에요. 그런데 이 단순한 게임이 사실 수학자와 컴퓨터 과학자들 사이에서 오랫동안 진지한 연구 주제였다는 거, 알고 계셨나요? Chalkdust Magazine에 실린 한 글은 "테트리스를 치트한다"는 도발적인 제목으로 이 흥미로운 세계를 풀어냈어요. 여기서 말하는 치트는 메모리를 조작하거나 핵을 쓰는 게 아니라, 수학과 알고리즘으로 게임의 본질을 꿰뚫어보는 일이거든요.

평가 함수라는 마법, 그리고 게임의 한계

이게 뭐냐면, 테트리스를 "최적으로 플레이하는 방법"을 찾는 문제예요. 사람은 직관과 경험으로 블록을 놓지만, 컴퓨터는 매 순간 가능한 모든 위치와 회전을 따져보고 점수를 매길 수 있거든요. 가장 흔히 쓰이는 평가 방식은 보드의 총 높이, 구멍의 개수, 울퉁불퉁한 정도(bumpiness), 지운 줄 수 같은 지표에 가중치를 곱해 합산하는 거예요.

이런 단순한 평가 함수만 잘 튜닝해도 이미 인간 챔피언을 가볍게 뛰어넘는 봇을 만들 수 있어요. 실제로 Pierre Dellacherie라는 연구자가 만든 알고리즘은 단 6개의 가중치만으로 평균 수십만 줄을 지우는 성능을 보여줬거든요. 그런데 더 놀라운 건, 이 게임이 이론적으로는 "유한하다"는 점이에요. 1996년 Heidi Burgiel이라는 수학자가 증명한 결과인데요, 만약 S 블록과 Z 블록만 번갈아 나오면 어떤 천재가 와도 결국엔 게임 오버를 피할 수 없다는 거예요. 즉, 무한한 시퀀스 안에서 충분히 운이 나쁘면 게임은 반드시 끝나는 거죠.

여기서 "치트"라는 표현이 등장해요. 만약 컴퓨터가 다음 블록뿐 아니라 그 다음, 또 그 다음 블록까지 미리 안다면 어떨까요? 더 나아가, 우리가 받을 블록 순서 자체를 우리에게 유리하게 조작할 수 있다면요? 이런 관점에서 테트리스를 분석하면 게임이 완전히 다른 모습으로 보여요. 적대적 환경(블록을 가장 나쁘게 주는 가상의 상대)에서 살아남는 전략과, 자비로운 환경(원하는 블록을 골라 받는)에서 점수를 최대화하는 전략은 알고리즘적으로 완전히 다른 문제거든요.

강화학습 연구의 단골 손님

사실 테트리스는 강화학습 연구자들에게 단골 벤치마크예요. DeepMind가 Atari 게임으로 유명해진 것처럼, 테트리스 역시 보드 상태가 명확하고 보상이 즉각적이어서 학습 환경으로 매력적이거든요. 최근에는 신경망을 평가 함수로 쓰거나, 몬테카를로 트리 탐색(MCTS)을 적용해 사람의 직관을 흉내 내는 연구들도 활발해요. 또 베이지안 최적화로 가중치를 자동 튜닝하는 사례도 있고요. 게임을 푸는 일이 곧 의사결정 문제, 탐색 문제, 그리고 확률 모델링 문제로 일반화되니까 응용 범위가 굉장히 넓죠.

비슷한 맥락에서 NES 시절 테트리스를 99레벨 너머 "킬스크린"까지 클리어해 화제가 됐던 사건도 떠올릴 만해요. 2023년 13살 소년 Blue Scuti가 인간 최초로 도달했고, 이후엔 봇이 200레벨 너머까지 가버렸죠. 인간과 기계가 같은 게임에서 보여주는 한계의 차이가 곧 이 분야의 매력이에요.

토이 문제에서 실무 알고리즘으로

"이런 거 알아서 뭐해?"라고 생각하실 수도 있는데요, 사실 테트리스 같은 단순한 토이 문제에서 배우는 알고리즘 사고가 실무에 직결돼요. 광고 입찰 시스템에서 "다음에 어떤 광고를 띄울까"를 결정할 때, 추천 시스템에서 "다음 콘텐츠는 뭐로 할까"를 정할 때 쓰는 의사결정 로직의 뼈대가 결국 테트리스 봇과 같거든요. 평가 함수를 정의하고, 가능한 행동을 탐색하고, 미래를 시뮬레이션하는 그 흐름 말이에요.

또 면접에서도 종종 등장해요. "테트리스 보드 상태가 주어졌을 때 최적의 위치를 찾아라" 같은 문제는 동적 계획법과 휴리스틱을 함께 묻는 좋은 문제거든요. 주말에 한 번 직접 봇을 만들어보시면, 단순한 수식 몇 줄이 인간을 능가하는 순간을 체험할 수 있어요. 파이썬으로 100줄 정도면 기본 봇은 충분히 만들 수 있고요.

마무리

테트리스라는 익숙한 게임 뒤에 이렇게 깊은 수학과 알고리즘이 숨어 있다는 게 새삼 신기해요. 단순한 규칙에서 출발해 무한히 깊어지는 문제, 그게 컴퓨터 과학의 매력 아닐까요. 여러분은 게임 AI를 만들어본 적 있으신가요? 어떤 게임이 가장 흥미로운 알고리즘 도전이 될 수 있을지 의견을 들려주세요.