커넥트4(사목 게임)의 완벽한 전략, 알고리즘으로 풀어보기

어릴 때 한 번쯤 해봤을 그 게임, 수학적으로 풀면 어떻게 될까?

커넥트4, 혹시 아시나요? 세로로 세운 격자판에 빨간색과 노란색 원판을 번갈아 떨어뜨려서, 가로·세로·대각선 중 하나로 4개를 먼저 연결하면 이기는 게임이에요. 영어로는 Connect 4, 한국에서는 '사목(四目)' 또는 '포목(四目) 게임'이라고도 불러요. 간단해 보이지만, 이 게임의 "완벽한 전략"을 컴퓨터로 찾아내는 건 꽤 흥미로운 알고리즘 문제거든요.

사실 커넥트4가 선공이 반드시 이기는 게임이라는 건 1988년에 이미 증명됐어요. 하지만 "어떻게" 이기는지, 그 최적 전략의 전체 모습을 직관적으로 보여주는 프로젝트가 새로 등장해서 소개해드릴게요.

게임 트리와 완전 탐색이란?

이 프로젝트를 이해하려면 먼저 게임 트리(Game Tree)라는 개념을 알아야 해요. 이게 뭐냐면, 게임에서 가능한 모든 수를 나무 구조로 펼쳐놓은 거예요. 맨 위가 시작 상태이고, 각 가지(branch)가 "이 칸에 두면?"이라는 선택지, 그리고 끝 노드가 승리·패배·무승부 같은 결과가 되는 거죠.

커넥트4의 표준 보드는 가로 7칸, 세로 6칸이에요. 가능한 게임 상태의 수가 약 4.5조(4.5 × 10¹²)개에 달해요. 이걸 전부 탐색하는 건 단순 무식하게는 불가능하고, 똑똑한 가지치기(pruning) 기법이 필요하거든요.

이 프로젝트가 접근한 방법: Weak Solution

이 프로젝트의 이름이 "WeakC4"인데요, 여기서 Weak은 약하다는 뜻이 아니라 게임 이론 용어예요. 게임의 풀이에는 크게 두 가지가 있어요.

Strong Solution(강한 풀이)은 게임의 어떤 상태에서든 최선의 수를 알려주는 거예요. 상대가 어떤 실수를 하든, 현재 보드 상태만 보고 바로 최적의 수를 계산할 수 있죠. Weak Solution(약한 풀이)은 게임 시작부터 양쪽 모두 최선을 다했을 때의 결과와 그 경로를 알려주는 거예요. 즉, "처음부터 완벽하게 두면 이런 흐름으로 진행된다"를 보여주는 거죠.

이 프로젝트는 Weak Solution에 초점을 맞춰서, 시작부터 최적 플레이를 했을 때 선공이 어떤 경로로 승리에 이르는지를 시각적으로 보여줘요.

핵심 알고리즘: 알파-베타 가지치기

게임 트리를 효율적으로 탐색하는 데 쓰이는 대표적 알고리즘이 알파-베타 가지치기(Alpha-Beta Pruning)예요. 이걸 쉽게 설명하면 이래요. 체스나 바둑에서 "이 수를 두면 상대가 이렇게 대응하고, 그러면 내가 이렇게..." 하고 머릿속으로 시뮬레이션하잖아요? 그런데 어떤 가지는 분석 중간에 "아, 이건 아무리 해도 아까 본 수보다 못하겠다"라고 판단할 수 있거든요. 그러면 그 가지는 더 이상 볼 필요가 없으니 잘라내는(prune) 거예요. 이게 알파-베타 가지치기의 핵심이에요.

이 기법 덕분에 4.5조 개의 상태를 전부 보지 않아도 정답을 찾을 수 있어요. 여기에 전치 테이블(Transposition Table)이라는 것도 활용하는데, 이건 "같은 보드 상태에 다른 순서로 도달할 수 있다"는 점을 이용해서 이미 분석한 상태를 캐싱해두는 거예요. 해시맵을 써서 중복 계산을 피하는 거죠.

결과: 선공은 항상 가운데에 두면 이긴다

이 프로젝트의 분석 결과를 보면 재미있는 패턴이 드러나요. 선공의 첫 수는 가운데 열(4번째 열)에 두는 것이 유일한 최적 시작이에요. 양쪽 모두 최선을 다하면, 선공이 41수 내에 반드시 승리하게 돼요.

이 프로젝트가 멋진 건 이런 분석 결과를 인터랙티브하게 탐색할 수 있게 시각화했다는 점이에요. 각 수마다 "이 수를 두면 결과가 어떻게 바뀌는지"를 트리 형태로 확인할 수 있거든요.

업계 맥락: 게임 AI에서 범용 AI까지

커넥트4 같은 "완전 정보 게임(perfect information game)"의 풀이는 AI와 알고리즘 연구의 클래식한 주제예요. 틱택토는 너무 단순하고, 체스와 바둑은 너무 복잡해서, 커넥트4는 그 사이에서 교육적으로 아주 좋은 위치에 있어요. 실제로 많은 CS 교육과정에서 미니맥스(Minimax)와 알파-베타 가지치기를 가르칠 때 커넥트4를 예제로 쓰거든요.

최근에는 DeepMind의 AlphaZero처럼 게임 트리 탐색(MCTS)과 딥러닝을 결합하는 방식이 대세가 됐지만, 커넥트4처럼 완전 풀이가 가능한 게임에서는 전통적인 알파-베타 가지치기가 여전히 가장 정확하고 효율적이에요.

한국 개발자에게 주는 시사점

알고리즘 공부를 하시는 분이라면 이 프로젝트를 직접 탐색해보시는 걸 추천해요. 알파-베타 가지치기, 전치 테이블, 게임 트리 탐색 같은 개념을 실제 동작하는 예제로 이해할 수 있거든요. 코딩 테스트에서 직접 나오는 주제는 아니지만, 탐색과 최적화의 핵심 원리를 체화하는 데 정말 좋은 재료예요.

또한 이런 류의 프로젝트는 포트폴리오에도 좋아요. 단순히 "알고리즘 문제를 풀었다"가 아니라, 시각화까지 포함해서 "이런 복잡한 문제를 분석하고 설명할 수 있다"를 보여주는 프로젝트는 면접에서도 이야깃거리가 되거든요.