Arduino UNO Q의 라이프 게임에서 유전 알고리즘을 이용한 장수 패턴 탐색

Conway's Game of Life(라이프 게임)는 단순한 3가지 규칙으로부터 놀라울 정도로 복잡한 거동을 만들어내는 셀 오토마톤(Cellular Automaton)이다. 초기 패턴에 따라 몇 스텝 만에 소멸하는 것도 있는가 하면, 수백 스텝 동안 복잡한 변화를 지속하는 것도 있다.

Arduino UNO Q에는 8×13 LED 매트릭스가 탑재되어 있어 라이프 게임을 실시간으로 시각화할 수 있다. 하지만 "어떤 초기 패턴이 오래 살아남으면서도 복잡한 거동을 하는가"를 일일이 수작업으로 찾는 것은 비효율적이다.

본 기사에서는 **유전 알고리즘(Genetic Algorithm, GA)과 대리 모델(Surrogate Model)**을 결합하여, 수명이 길고 다양성이 높은 초기 패턴을 자동으로 탐색하는 메커니즘을 구현한다.

라이프 게임의 기본 구현(셀 오토마톤의 규칙·LED 표시)에 대해서는 이전 기사를 참조한다. 본 기사에서는 AI 탐색 부분에 집중하여 해설한다.

※ 추론 및 모델 생성 알고리즘 부분은 Claude Code를 사용하여 구현을 진행했다.

항목	내용
하드웨어	Arduino UNO Q
...
App Lab은 Arduino UNO Q용 애플리케이션 실행 환경이다. Python 스크립트와 Arduino 스케치를 하나로 묶은 zip 파일을 배포하는 것만으로 동작한다.

기본적인 구현은 이전 기사를 참조한다.

토로이드형(Toroidal, 주기적 경계 조건) 채택

8×13 그리드를 **토로이드(Toroid, 도넛 형태)**로 취급한다. 왼쪽 끝과 오른쪽 끝, 위쪽 끝과 아래쪽 끝이 연결되어 있는 이미지이다. 가장자리의 셀도 항상 8개의 이웃(neighbor)을 가지므로, 경계에서의 특별한 처리가 필요하지 않게 된다.

ROWS = 8
COLS = 13
TOROIDAL = True
...

토로이드형을 채택함으로써 작은 그리드에서도 복잡한 패턴이 오래 지속되기 쉬워진다. 고정 경계(가장자리는 항상 죽은 셀)에서는 가장자리에 가까운 셀이 사라지기 쉬워 단명하는 패턴이 늘어나는 경향이 있다.

GA에서는 각 개체(초기 패턴)의 "우수함"을 스칼라 값으로 평가하는 **적합도 함수(Fitness Function)**가 핵심이다. 이번에는 다음 두 지표의 가중치 합을 사용한다.

fitness = 0.6 × (longevity / 1000) + 0.4 × diversity

수명 (Longevity)
초기 패턴으로부터 몇 스텝 만에 사이클(Cycle)에 진입하는지를 측정한다. 정지 상태(Still-life)나 소멸도 사이클로서 검출된다.

• 최대 1000스텝 시뮬레이션
• 사이클 검출 시 해당 스텝 수를 longevity로 설정
• 1000스텝 이내에 사이클 없음 → longevity = 1000 (최댓값)

다양성 (Diversity)
사이클에 진입했을 때의 주기(Period)의 길이를 정규화한 값이다.

패턴 종류	사이클 주기	diversity
still-life (정지)	1	0.01
...

MAX_CYCLE = 100 # 주기의 정규화 상한
def evaluate(pattern, max_gens=1000):
grid = _make_grid(pattern)
...

2가지 지표를 독립시킨 배경

당초에는 다양성을 "사이클 진입 전까지 나타난 유니크한 상태의 수"로 정의했었다. 하지만 이렇게 하면 유니크 상태 수 ≒ 생존 세대 수가 되어버린다. 사이클 검출 시점에 과거의 모든 상태가 seen에 기록되어 있기 때문에, 수학적으로 len(seen) == longevity가 성립하기 때문이다.

사이클 주기를 사용함으로써 독립된 지표가 된다. 예를 들어:

• "500스텝 동안 살아남았지만, 마지막은 blinker(주기 2)" → longevity 높음 · diversity 낮음
• "200스텝 만에 복잡한 진동자(주기 80)로 안착" → longevity 중간 · diversity 높음

이 두 가지는 성질이 다른 패턴이며, 독립된 지표로 각각을 평가할 수 있게 된다.

초기 패턴은 7×7 = 49개 셀의 바이너리 배열이다. 이를 8×13 그리드의 중앙에 배치하여 시뮬레이션한다.

PATTERN_SIZE = 7 # 7×7
def random_pattern(n):
return [random.randint(0, 1) for _ in range(n * n)]

POP_SIZE = 20 # 개체 수
ELITE_N = 2 # 엘리트 보존 수 (상위 2개체를 차세대로 계승)
MUTATION_RATE = 0.05 # 돌연변이율 (각 비트가 5%의 확률로 반전)

def next_generation(population, fitnesses, mutation_rate, elite_n):
    # 엘리트 보존: 상위 2개체를 그대로 차세대로
    sorted_idx = sorted(range(len(population)), key=lambda i: -fitnesses[i])
    ...

evaluate()는 최대 1,000세대 시뮬레이션을 수행하기 때문에 무거운 처리 과정이다. 20개체 모두를 매 세대 CPU로 평가하면 1세대당 수십 초가 소요된다. 따라서 **서로게이트 모델 (Surrogate Model, 대리 모델)**을 사용하여 사전 스크리닝을 수행한다.

• 전체 20개체를 서로게이트 MLP로 고속 예측
• 예측값 상위 TOP K = 5개체만 evaluate()로 정확하게 평가
• 나머지 15개체에는 서로게이트 예측값을 fitness로 사용 (GA의 선택 압력은 유지)

SURROGATE_TOP_K = 5
inputs = [surrogate.pattern_to_input(p) for p in population]
predicted = surrogate.predict(inputs)
...

CPU 평가 횟수를 20회에서 5회로 줄일 수 있어, 1세대당 처리 시간이 대폭 단축된다.

입력은 7×7 패턴을 8×8로 제로 패딩 (Zero-padding) 하여 평탄화한 64차원 벡터이다.

입력 (64) → 전결합 (32) → ReLU → 전결합 (16) → ReLU → 전결합 (1) → Sigmoid

사용 가능한 백엔드를 우선순위에 따라 자동으로 선택한다.

백엔드	조건
ONNX-CPU	onnxruntime 설치됨 (권장)
TFLite-CPU	tflite-runtime 설치됨
NumPy-CPU	항상 사용 가능 (외부 ML 라이브러리 불필요)

trials = [
    ("ONNX-CPU", self._try_onnx_cpu),
    ("TFLite-CPU", self._try_tflite_cpu),
    ...

NumPy 폴백 (Fallback)

model_numpy.json은 가중치 행렬을 JSON화한 것이며, onnxruntime이나 tflite-runtime이 없는 환경에서도 동작한다. NumPy (Python 표준 환경에 포함됨)만으로 MLP의 순전파 (Forward Propagation)를 실행한다.

def _predict_numpy(self, patterns):
    x = np.array(patterns, dtype=np.float32)
    for i, (W, b) in enumerate(zip(self._np_W, self._np_b)):
        ...

동작 중인 LED 매트릭스의 모습을 아래에 나타낸다.

또한, 로그 출력 예시를 아래에 나타낸다.

04:07:51 INFO life_game_ai: [CPU eval] 개체16: fitness=0.095 longevity=159 diversity=0.000
04:07:56 INFO life_game_ai: [CPU eval] 개체04: fitness=0.412 longevity=412 diversity=0.280
04:08:01 INFO life_game_ai: Gen 5: best_fitness=0.412 longevity=412 diversity=0.280 elapsed=5.1s

위 예시에서는 longevity와 diversity가 독립적인 값을 나타내고 있다. 이를 통해 '수명은 길지만 단순하게 진동하는 패턴'과 '중간 정도의 수명을 가지며 복잡하게 진동하는 패턴'이 각각 평가되고 있음을 확인할 수 있다.

Arduino UNO Q의 LED 매트릭스 상에서, GA와 서로게이트 모델을 결합하여 장수 및 고다양성 패턴의 자동 탐색을 구현하였다.

이번에는 테스트적인 구현이지만,

• 피트니스 (Fitness)를 **longevity (생존 세대 수)**와 **diversity (사이클 주기)**라는 독립적인 두 지표로 설계했다
• 서로게이트 모델 (Surrogate model)을 통해 CPU 평가를 전체의 1/4로 단축했다
• 백엔드 자동 선택을 통해 ONNX-CPU부터 NumPy까지 환경에 구애받지 않고 동작한다

등을 통해, Arduino 환경과 Linux 환경을 병렬로 사용한 AI 추론을 실시할 수 있었다.

이는 Arduino UNO Q가 MPU×MCU로 구성되어 있기 때문에, 보드 1개로 구현할 수 있었던 것이다.

다음 기사에서는 이 탐색 프로세스를 브라우저에서 실시간으로 모니터링하는 Web GUI (Flask + Canvas) 제작을 검토하고 있다. 추론 중인 TOP 5 패턴의 시각화 등을 할 수 있는 메커니즘도 구현하고 싶다.