무한한 우주를 작은 컴퓨터에 담기: 모던 C++로 만든 Game of Life 시뮬레이터

Game of Life, 60년이 지나도 여전히 흥미로운 이유

Conway의 Game of Life(생명 게임)는 1970년에 수학자 John Conway가 만든 셀룰러 오토마타예요. 이게 뭐냐면, 격자(grid) 위에 점들이 "살아있다/죽었다" 두 상태만 가지고 있고, 아주 단순한 규칙 네 개로 다음 세대의 상태가 결정되는 시뮬레이션입니다. 살아있는 칸 주변에 이웃이 2개나 3개면 살아남고, 죽은 칸 주변에 정확히 3개의 이웃이 살아있으면 새로 태어나고, 그 외에는 죽는다는 식이죠.

규칙은 이렇게 단순한데 만들어지는 패턴은 놀랍도록 복잡해요. 글라이더(glider)라고 부르는 작은 패턴은 격자 위를 대각선으로 영원히 움직이고, 글라이더 건(gun)은 글라이더를 끊임없이 발사합니다. 심지어 Game of Life 안에서 또 다른 Game of Life를 시뮬레이션하는 미친 구현도 있어요. 튜링 완전성(어떤 계산이든 표현 가능)이 증명되어 있어서 이론적으로는 이 위에서 컴퓨터를 만들 수도 있고요.

Ryan JK라는 개발자가 최근에 모던 C++로 Game of Life 시뮬레이터를 만들었는데, 단순한 구현이 아니라 "무한한 격자"를 다루는 방법에 집중한 점이 흥미롭습니다.

무한 격자를 어떻게 메모리에 담을까

순진하게 구현하면 보통 2차원 배열을 잡아요. 1000x1000 배열에 boolean 값을 채워넣고, 매 세대마다 각 칸의 이웃을 세어서 다음 세대를 계산하는 식이죠. 이건 간단하지만 두 가지 큰 문제가 있어요. 첫째, 패턴이 격자 경계를 넘어가면 잘려나가요. 둘째, 빈 공간이 대부분이어도 모든 칸을 매번 검사해야 합니다.

Ryan의 접근법은 다릅니다. 살아있는 셀의 좌표(x, y)만 해시 집합(hash set)에 저장해요. 죽은 셀은 아예 메모리에 없는 거죠. 격자 크기가 무한대로 커져도 살아있는 셀이 1000개면 메모리는 1000개분만 차지합니다. C++로는 std::unordered_set<std::pair<int64_t, int64_t>>처럼 표현하고, 좌표가 64비트 정수라서 사실상 무한에 가까운 영역을 다룰 수 있어요.

다음 세대를 계산할 때도 모든 칸을 보지 않습니다. 살아있는 셀과 그 이웃 8개만 후보로 두고, 그 후보들에 대해서만 규칙을 적용해요. 이렇게 하면 빈 공간이 아무리 넓어도 계산량은 살아있는 셀 수에 비례합니다. 알고리즘 복잡도가 격자 크기가 아니라 패턴 크기에 의존하는 거죠.

모던 C++의 맛

Ryan이 사용한 기능들을 보면 요즘 C++ 트렌드가 한눈에 보입니다. std::unordered_set과 std::pair를 조합해서 해시 컨테이너를 쓰고, 커스텀 해시 함수를 람다나 functor로 정의해요. 좌표 두 개를 하나의 해시값으로 섞을 때 boost::hash_combine 같은 방식을 흉내내서 XOR과 시프트를 조합한 비트 연산을 쓰는 게 정석입니다.

또 한 가지 흥미로운 부분은 메모리 지역성(locality) 최적화예요. 해시셋은 좌표가 메모리상에 흩어져 있어서 캐시 효율이 좋지 않은데요, 패턴이 커지면 이게 병목이 됩니다. 그래서 영역별로 작은 청크(chunk)로 나누고 각 청크 안에서는 비트맵을 쓰는 하이브리드 접근도 시도해볼 만해요. 이게 사실 유명한 HashLife 알고리즘의 출발점이기도 합니다.

HashLife와 비교하면

무한 Game of Life 얘기가 나오면 빼놓을 수 없는 게 Bill Gosper가 1980년대에 만든 HashLife 알고리즘이에요. 이건 격자를 쿼드트리(quadtree)로 표현하고, 같은 패턴의 같은 미래 상태를 메모이제이션(이전 계산 결과 저장)해서 재사용합니다. 결과적으로 시간이 지수적으로 가속되는 마법 같은 알고리즘이에요. Golly라는 유명한 Game of Life 시뮬레이터가 이 방식으로 수십억 세대를 몇 초 만에 계산해냅니다.

Ryan의 해시셋 방식은 HashLife만큼 빠르지는 않지만, 구현이 훨씬 단순하고 이해하기 쉽다는 장점이 있어요. 패턴이 무작위로 생성되거나 계속 변하는 경우에는 HashLife의 메모이제이션 효과가 떨어지기 때문에, 오히려 단순한 해시셋 방식이 비슷한 성능을 낼 수도 있습니다.

한국 개발자에게 무슨 의미가 있을까

사실 Game of Life 시뮬레이터를 실무에서 쓸 일은 거의 없어요. 하지만 이 글이 던지는 교훈은 꽤 보편적입니다. "전체 공간을 다 표현하지 말고, 의미있는 부분만 표현하라"는 원칙은 희소 행렬(sparse matrix), 게임의 보로노이 다이어그램, 그래픽스의 옥트리, 심지어 데이터베이스의 인덱스에도 그대로 적용돼요.

또 C++을 공부하는 입장에서 보면, 이런 작은 프로젝트야말로 std 라이브러리의 컨테이너와 알고리즘, 람다, move semantics 같은 모던 C++ 기능을 자연스럽게 익힐 수 있는 좋은 소재예요. Rust나 Go가 화제지만 C++은 여전히 게임, 임베디드, 고성능 컴퓨팅 분야에서 단단한 자리를 지키고 있으니, 토이 프로젝트 하나 만들어보는 것도 좋은 투자입니다.

마무리

단순한 규칙에서 무한한 복잡성이 튀어나오는 Game of Life는 60년이 지난 지금도 여전히 좋은 학습 소재이자 알고리즘 연습장이에요. 무한 격자를 다루는 방법, 희소 자료구조의 설계, 그리고 모던 C++의 표현력까지 한 프로젝트에 다 들어있거든요.

혹시 여러분이 학습용으로 만들어본 토이 프로젝트 중에 이렇게 단순한데 깊이 파볼수록 재미있었던 게 있나요? 어떤 주제로 시작하면 알고리즘과 언어를 같이 익히기 좋을지 의견 나눠보고 싶네요.