결정론적 시뮬레이션

결정론적 시뮬레이션은 처음 상태와 입력이 같으면 몇 번을 돌려도 똑같은 결과를 냅니다. 그래서 결과 대신 입력만 저장하거나 주고받아도 됩니다. 게임은 이 성질로 경기를 다시 틉니다. 여러 컴퓨터가 같은 세계를 함께 돌리는 데도 씁니다. 분산 시스템을 시험하는 기법도 같은 이름으로 부릅니다.

상세

이 절은 결정론적 시뮬레이션이 무엇인지를 바둑 기보로 먼저 잡습니다. 이어서 시뮬레이션이 한 걸음씩 나아가는 모양을 그림으로 보고, 입력만 남기면 무엇이 되는지를 봅니다.

그다음은 결과를 흔드는 원인들입니다. 난수 · 소수 계산 · 처리 순서 · 바깥 세계를 하나씩 보고 막는 법을 댑니다. 끝으로 어긋남을 찾는 법, 분산 시스템 시험에서 쓰는 뜻, 대가를 봅니다.

바둑 기보와 같은 판

바둑에는 기보가 있습니다. 둔 수를 순서대로 적은 종이입니다. 바둑판 사진을 백 장 찍어 두지 않아도 기보만 있으면 누구나 같은 판을 처음부터 다시 놓을 수 있습니다.

결정론적 시뮬레이션은 컴퓨터 계산을 이 바둑판처럼 만드는 일입니다.

상태와 틱

시뮬레이션은 세계의 지금 모습을 규칙에 따라 다음 모습으로 옮기는 계산입니다. 세계의 지금 모습을 상태라고 부릅니다.

게임 속에서 움직이는 캐릭터나 병사 하나하나를 유닛이라고 합니다. 게임에서는 유닛마다의 위치 · 속도 · 체력이 상태입니다.

시뮬레이션은 시간을 잘게 잘라 한 걸음씩 나아갑니다. 이 한 걸음을 틱이라고 부릅니다. 틱마다 시뮬레이션은 지금 상태와 그 틱의 입력을 받아 다음 상태를 만듭니다. 입력은 플레이어가 누른 버튼처럼 바깥에서 들어온 것입니다.

같은 상태와 같은 입력을 넣었을 때 언제나 같은 다음 상태가 나오면 그 계산을 결정론적이라고 합니다. 이 성질이 모든 틱에서 지켜지면 처음 상태와 입력 목록만으로 마지막 상태가 정해집니다.

flowchart TD
    S0["처음 상태"] --> S1["1틱 뒤 상태"]
    I1["1틱 입력"] --> S1
    S1 --> S2["2틱 뒤 상태"]
    I2["2틱 입력"] --> S2
    S2 --> S3["3틱 뒤 상태"]
    I3["3틱 입력"] --> S3

그림에서 상태 상자들은 기록하지 않아도 됩니다. 처음 상태와 입력 상자 셋만 있으면 3틱 뒤 상태는 언제든 다시 계산됩니다. 입력 목록이 바둑의 기보 노릇을 합니다.

입력만 남기는 쓰임

상태는 크고 입력은 작습니다. 유닛 천 개의 위치와 체력은 틱마다 수천 개의 값입니다. 같은 틱에 플레이어가 누른 버튼은 몇 개뿐입니다.

결정론이 보장되면 큰 상태 대신 작은 입력만 다루면 됩니다. 이 차이에서 쓰임이 셋 나옵니다.

락스텝은 네트워크 게임에서 쓰는 방식입니다. 참여한 컴퓨터가 틱마다 자기 입력을 서로에게 보냅니다. 모든 입력이 모이면 각자 그 틱을 계산합니다. 계산이 결정론적이라서 모두가 같은 상태에 닿습니다.

롤백 넷코드도 이 성질에 기댑니다. 남의 입력이 늦으면 일단 짐작해서 계산을 앞서 나갑니다. 진짜 입력이 오면 그 틱으로 되감아 다시 계산합니다. 되감아 다시 돌린 결과가 상대와 같으려면 계산이 결정론적이어야 합니다.

흔들리는 시간 폭

결과를 흔드는 첫 원인은 한 틱의 시간 폭입니다. 틱마다 흘려보내는 시간이 컴퓨터 성능에 따라 바뀌면 같은 입력에서도 다른 결과가 나옵니다.

움직임을 틱마다 더해 가는 계산은 시간 폭이 달라지면 값도 달라집니다. 한 틱 동안은 속도가 그대로라고 보고 위치에 더하기 때문입니다. 점점 빨라지며 떨어지는 공의 1초 뒤 위치를 0.5초 폭으로 두 번 더해 구할 때와 0.1초 폭으로 열 번 더해 구할 때 값이 서로 다르게 나옵니다.

결정론적 시뮬레이션은 고정 타임스텝을 씁니다. 한 틱이 흘려보내는 시간을 언제나 같은 값으로 묶어 두는 방식입니다.

난수와 시드

게임에는 운이 들어갑니다. 공격이 빗나갈지, 아이템이 무엇이 나올지를 난수로 정합니다. 난수를 뽑을 때마다 다른 값이 나오면 같은 입력에서도 다른 경기가 됩니다.

컴퓨터의 난수는 대개 의사 난수 생성기가 만듭니다. 출발값 하나에서 정해진 계산을 되풀이해 무작위처럼 보이는 수열을 뽑는 장치입니다. 이 출발값을 시드라고 부릅니다. 시드가 같으면 뽑히는 수열도 늘 같습니다.

import random
a = random.Random(42)     # 시드 42
b = random.Random(42)     # 같은 시드
a.random() == b.random()  # True

두 생성기는 따로 만들었는데도 첫 값이 같습니다. 시드가 같기 때문입니다. 그래서 결정론적 시뮬레이션은 시드를 처음 상태에 넣어 둡니다.

생성기가 지금 어디까지 뽑았는지도 상태의 일부로 다룹니다. 중간 틱부터 다시 계산하려면 그 틱에서 생성기가 내놓을 다음 값도 같아야 하기 때문입니다. 롤백 넷코드처럼 지난 틱으로 되감을 때가 이런 경우입니다.

부동소수점 계산의 끝 숫자 차이

부동소수점은 컴퓨터가 소수를 담는 가장 흔한 방식입니다. 값을 정해진 자릿수에 맞춰 반올림해 담습니다. 반올림이 끼어 있어서 덧셈 순서만 바꿔도 결과가 달라질 수 있습니다.

(0.1 + 0.2) + 0.3   # 0.6000000000000001
0.1 + (0.2 + 0.3)   # 0.6

수학으로는 같은 식인데 끝 숫자가 다릅니다. 같은 실행 파일을 같은 종류의 기계에서 돌리면 대개 계산 순서도 같아서 문제가 없습니다. 기계가 달라지면 이야기가 바뀝니다.

첫째, 컴파일러는 빠르게 하려고 계산 순서를 바꾸기도 합니다. 앞에서 본 것처럼 덧셈 순서만 바뀌어도 끝 숫자가 달라집니다.

둘째, 반올림 횟수가 달라질 수 있습니다. 보통은 곱한 뒤 한 번, 더한 뒤 또 한 번 반올림합니다. 어떤 CPU(Central Processing Unit, 중앙 처리 장치)는 곱셈과 덧셈을 한 명령으로 처리하면서 반올림을 마지막에 한 번만 합니다. 반올림을 덜 하면 끝 숫자도 달라질 수 있습니다.

셋째, 삼각함수 같은 수학 함수는 라이브러리마다 계산법이 조금씩 다릅니다. 그래서 같은 값을 넣어도 끝 숫자가 다르게 나올 수 있습니다.

끝 숫자 하나의 차이는 작아 보입니다. 하지만 틱마다 앞 결과 위에 계산을 쌓아서 차이도 함께 쌓입니다. 어느 틱에서 유닛 하나가 벽에 닿느냐 마느냐가 갈리면 그 뒤의 경기는 완전히 달라집니다.

막는 길은 둘입니다. 하나는 고정소수점입니다. 소수를 정수로 바꿔 계산하는 방식입니다. 1.5 를 1500 처럼 정해진 배율을 곱한 정수로 담습니다. 정수 계산은 기계가 달라도 결과가 같습니다.

다른 하나는 모든 참여자가 같은 실행 파일과 같은 컴파일 설정을 쓰고 수학 함수를 직접 구현하는 것입니다.

처리 순서

같은 계산이라도 무엇을 먼저 하느냐에 따라 결과가 달라집니다. 유닛 둘이 한 칸으로 동시에 움직이려 하면 먼저 처리된 쪽이 그 칸을 차지합니다. 처리 순서가 실행마다 바뀌면 칸 주인도 바뀝니다.

순서가 몰래 바뀌는 흔한 곳은 해시 테이블입니다. 해시 테이블은 키로 값을 빨리 찾는 자료구조입니다. 언어에 따라서는 해시 테이블을 처음부터 끝까지 도는 순서가 실행마다 달라집니다. 그래서 유닛을 고유 번호 순으로 정렬해 처리하는 식으로 순서를 못 박습니다.

멀티스레딩도 순서를 흔듭니다. 일을 여러 스레드에 나눠 맡기면 어느 스레드가 먼저 끝날지 매번 다릅니다. 나눠 계산하는 것은 괜찮습니다. 결과를 합칠 때 끝난 순서가 아니라 정해 둔 순서로 합치면 됩니다.

바깥 세계에서 오는 값

시뮬레이션 안에서 지금 시각을 읽으면 돌릴 때마다 다른 값이 나옵니다. 파일 내용이나 네트워크로 메시지가 도착한 때도 마찬가지입니다. 이런 값은 시뮬레이션 바깥에서 정해집니다.

바깥 값은 시뮬레이션 안에서 직접 읽지 않습니다. 바깥에서 읽어 그 틱의 입력으로 넣고 입력과 함께 기록합니다. 이렇게 하면 다시 돌릴 때도 같은 값이 같은 틱에 들어갑니다.

해시로 찾는 어긋남

여러 컴퓨터가 같은 시뮬레이션을 돌리다 결과가 갈라지는 일을 디싱크(desync)라고 부릅니다. 원인을 하나라도 놓치면 디싱크가 납니다. 갈라진 뒤에도 각 컴퓨터는 아무 오류 없이 계속 돌기 때문에 저절로는 안 보입니다.

디싱크를 찾으려고 틱마다 상태를 해시 함수에 넣어 짧은 값을 만듭니다. 해시 함수는 큰 데이터를 짧은 값으로 줄이는 함수입니다. 데이터가 조금만 달라도 다른 값이 나옵니다. 이 값을 서로 견주면 상태 전부를 보내지 않고도 상태가 같은지 알 수 있습니다.

sequenceDiagram
    participant A as 컴퓨터 A
    participant B as 컴퓨터 B
    A->>B: 10틱 입력
    B->>A: 10틱 입력
    Note over A,B: 둘 다 받은 뒤 10틱을 각자 계산
    A->>B: 10틱 상태의 해시
    B->>A: 10틱 상태의 해시
    Note over A,B: 해시가 다르면 10틱에서 갈라진 것

위는 락스텝의 한 틱입니다. 입력을 주고받고 각자 계산한 뒤 해시를 견줍니다. 해시가 처음 달라진 틱을 알면 원인을 찾을 범위가 그 틱 하나로 좁아집니다.

분산 시스템 시험에서의 결정론적 시뮬레이션

분산 시스템은 여러 서버가 네트워크로 메시지를 주고받으며 함께 일하는 시스템입니다. 이런 시스템의 버그는 메시지가 특정 순서로 도착하거나 특정 순간에 서버가 죽을 때만 납니다. 같은 시험을 다시 돌리면 그 순서가 안 나와서 버그도 안 납니다.

이 분야의 결정론적 시뮬레이션은 시스템 전체를 한 프로그램 안에서 돌립니다. 네트워크 · 디스크 · 시계를 진짜 대신 가짜 부품으로 바꿉니다. 메시지가 언제 도착할지, 어느 서버가 언제 죽을지는 시드를 정한 의사 난수 생성기가 고릅니다.

이렇게 하면 시드 하나가 시험 한 판 전체를 정합니다. 버그가 난 시드를 남겨 두면 개발자가 같은 버그를 몇 번이고 똑같이 다시 볼 수 있습니다. 게임에서 입력을 남기는 것과 같은 생각입니다.

대가와 쓰지 않는 구조

결정론은 계산 전부에 걸리는 약속이라 비쌉니다. 위에서 본 원인을 하나도 빠짐없이 막아야 합니다. 외부 라이브러리 하나가 부동소수점이나 해시 테이블 순회에 기대면 그것만으로 깨집니다. 이미 만든 물리 엔진이 결정론을 보장하지 않으면 그대로 쓸 수 없습니다.

락스텝에는 대가가 더 있습니다. 모든 입력이 모여야 틱을 계산합니다. 그래서 가장 늦게 입력을 보내는 참여자의 속도에 모두가 묶입니다. 도중에 들어온 참여자는 처음부터 입력을 다 다시 돌리거나 따로 받은 상태에서 시작해야 합니다.

모든 게임이 이 길을 가지는 않습니다. 권위 서버 구조에서는 서버 하나가 세계를 계산해 결과 상태를 나눠 줍니다. 다른 컴퓨터는 서버의 계산을 따라 하지 않습니다. 받은 상태를 보여 줄 뿐이라 엄격한 결정론이 덜 필요합니다. 대신 상태를 보내야 해서 네트워크로 오가는 양이 늘어납니다.

관련 항목

결정론적 시뮬레이션이 속하는 상위 분류

시뮬레이션 · 게임 개발 · 게임 루프 · 결정론 · 결정론적 알고리즘 · 재현성

결정론적 시뮬레이션이 기대는 기법

고정 타임스텝 · 틱 · 의사 난수 생성기 · 시드 · 고정소수점 · 순수 함수

결정론적 시뮬레이션을 깨는 원인

부동소수점 · IEEE 754 · 해시 테이블 · 멀티스레딩 · 경쟁 상태 · 부작용

결정론적 시뮬레이션 위에 얹히는 기법

리플레이 · 락스텝 · 롤백 넷코드 · 클라이언트 측 예측 · 입력 예측 · 이벤트 소싱

결정론적 시뮬레이션과 맞세워지는 동기화 방식

권위 서버 · 상태 동기화 · 리플리케이션 · 클라이언트-서버 구조

결정론적 시뮬레이션의 어긋남을 찾는 도구

디싱크 · 해시 함수 · 체크섬 · 게임 상태 직렬화

결정론적 시뮬레이션을 시험에 쓰는 기법

결정론적 시뮬레이션 테스트 · 분산 시스템 · 퍼징 · 카오스 엔지니어링 · 불안정한 테스트 · 장애 주입