GM 오락실
← 프로젝트 회고 · Backend
RETROSPECTIVE · 회고

어디서 돌려도 같은 결과: 디펜스 결정론 시뮬레이션과 서버 재검증

Backend

디펜스(PIXEL LUCKY DEFENSE)는 한 판에 수천 tick 동안 유닛 수십 기가 싸우는 게임이다. 시즌 랭킹을 열려면 점수를 믿을 수 있어야 하는데, 결과를 계산하는 곳이 브라우저 하나뿐이면 보낸 점수를 얼마든지 고칠 수 있다. 격투 랭크전 AI전처럼 결과 대신 입력을 받아 서버에서 다시 돌리기로 했다. 디펜스는 여기에 멀티와 밸런스 봇까지 같은 시뮬레이션을 쓴다.

하나의 시뮬레이션, 세 곳

  1. 랭킹: 판을 시작할 때 서버가 시드와 로드아웃(강화·연구·유물)을 정해 준다. 브라우저는 끝나면 결과 대신 명령 기록을 보내고, 서버가 처음부터 다시 돌려 점수를 낸다.
  2. 멀티(최대 4명): 서버는 시뮬을 돌리지 않는다. 100ms마다 모인 명령을 차례 번호와 함께 뿌리고(락스텝), 각자 같은 시뮬을 돌린다.
  3. 밸런스: 봇이 같은 시뮬로 판을 빠르게 많이 돌려 밸런스 표를 만든다.

서버는 웹의 디펜스 엔진 폴더를 그대로 import한다. 셋 다 성립하려면 같은 시드와 같은 명령이 어디서 돌든 끝자리까지 같은 결과를 내야 한다.

같은 기록인데 결과가 조금씩 달랐다

서버에서 기록을 다시 돌렸더니 결과가 브라우저와 조금씩 달랐다. Math.random과 Date는 당연히 안 썼다. 문제는 더 조용한 곳에 있었다. Math.pow, sin, exp 같은 함수는 명세가 결과의 마지막 자리까지 정하지 않아서 엔진마다 끝자리가 다를 수 있다. 한 번은 무시할 만한 차이지만, 수천 tick 동안 체력과 피해에 곱해지면 어느 순간 적 하나가 죽고 안 죽고가 갈리고, 그 뒤로는 다른 판이 된다.

규칙: 사칙연산 · sqrt · 반올림만

시뮬 안에서 쓸 수 있는 연산을 정했다. 사칙연산, sqrt, 비교, 반올림. 이 연산들은 IEEE 754가 결과를 정확히 정해 두어서 어느 엔진에서나 같다. 배열도 늘 같은 순서로 돈다. 이 규칙은 엔진 폴더 맨 위 주석과 작업 문서에 적어 두었다.

  1. 난수: 시드로 도는 mulberry32. 정수 연산(Math.imul, 비트 연산)만 쓰고, 상태가 보드 안의 숫자 하나라 그대로 저장·복제된다.
  2. 거듭제곱: 웨이브별 적 체력은 웨이브마다 배수를 곱해 커진다. Math.pow 대신 0~400웨이브 체력을 곱셈을 차례로 해서 표로 미리 만들어 두고 꺼내 쓴다.
  3. 실패한 명령은 상태를 하나도 바꾸지 않는다. 명령 처리를 '검사 → 변경' 순서로 짜서, 검사에서 걸리면 아무것도 건드리지 않고 끝난다.
// 난수 (mulberry32) — 정수 연산만
export function rnd(s) {
let t = (s.r = (s.r + 0x6d2b79f5) | 0);
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}

// 웨이브별 체력: Math.pow 대신 곱을 차례로 해서 미리
export const HP_TABLE = (() => {
const out = [];
let m = 1;
for (let w = 0; w <= 400; w++) {
out.push(Math.round(B.hp.base * (1 + B.hp.lin * w) * m));
m *= w >= B.hp.from3 ? B.hp.mult3 : w >= B.hp.from2 ? B.hp.mult2 : B.hp.mult;
}
return out;
})();

깨지면 바로 알게

규칙은 언젠가 깨진다. 그래서 깨지는 순간을 잡는 장치를 세 곳에 두었다.

  1. 밸런스 봇이 판을 돌릴 때마다 그 판의 명령 기록을 다시 돌려 결과가 같은지 비교한다.
  2. 멀티에서는 각자 150 tick(5초)마다 게임 상태 해시를 서버로 보낸다. 같은 tick의 해시가 보드마다 다르면 서버 로그에 남기고 방에 desync를 뿌려 화면에 바로 표시한다.
  3. 시뮬 규칙이 바뀌면 판 검증 열쇠가 바뀐다. 열쇠는 손으로 올리는 규칙 번호와 밸런스 수치 표 전체의 해시를 합친 값이다. 서버는 판을 시작할 때 열쇠를 적어 두고, 끝날 때 열쇠가 다르면 다시 돌리지 않고 '판 도중 업데이트됐다'고 돌려보낸다. 옛 판을 새 규칙으로 돌리면 이긴 판이 진 판이 될 수 있어서다.

수치 표는 해시가 알아서 잡지만, 코드로 된 규칙 변경은 해시로 잡을 수 없다. 그래서 규칙 번호는 사람이 올려야 한다. 이 부분은 아직 사람의 기억에 기대고 있다.

서버에서 다시 돌리기

한 판을 처음부터 다시 돌리는 건 가볍지 않다. 서버는 한 프로세스에서 모든 게임과 소켓을 처리하니, 검증이 메인 스레드를 잡고 있으면 다른 게임이 멈춘다. 검증은 작업 스레드(worker_threads)로 보냈고, 그 안에서도 3000 tick씩 끊어 돌리며 사이사이 쉰다.

다시 돌린 결과 말고도 몇 가지를 더 본다.

  1. 판은 1회용이다. 끝내기 요청이 오면 그 판을 '사용됨'으로 바꾸면서 찾기 때문에 같은 판을 두 번 낼 수 없다.
  2. 끝나지 않은 판은 기록하지 않는다.
  3. 실제로 걸린 시간이 최대 배속(3배속)으로도 불가능하게 짧으면 거절한다. 명령 기록이 맞아도 그 판을 실제로 플레이할 시간은 있어야 한다.
  4. 밸런스 버전이 바뀌면 순위표를 따로 쌓는다.

배운 점

  1. 결정론은 Math.random을 안 쓰는 것으로 끝나지 않는다. 표준 수학 함수도 엔진마다 끝자리가 다를 수 있다.
  2. 결정론은 지키는 것보다 깨진 걸 아는 게 중요하다. 해시 비교와 다시 돌리기 비교를 늘 켜 두면 깨진 변경을 바로 찾는다.
  3. 결정론 시뮬 하나가 랭킹 검증, 멀티 동기화, 밸런스 측정을 다 해 줬다. 처음에 제약을 지키는 비용이 세 기능의 비용을 줄였다.
Gunmo Lee
since 2021.07
어디서 돌려도 같은 결과: 디펜스 결정론 시뮬레이션과 서버 재검증 | GM 오락실