(컴퓨터과학) 시드와 랜덤
게임의 시드란?
마인크래프트(Minecraft)나 림월드(Rimworld) 같은 무작위 맵 기반 생존 게임을 하다 보면 맵 생성 시 시드(Seed)라는 것을 입력할 수 있다.
이런 게임을 많이 한 사람은 알 수 있듯이, 인터넷에서 ‘OOO 시드’라고 치고 검색한 값을 여기에 넣으면 검색한 결과와 똑같은 맵이 생성된다!
분명 랜덤으로 맵이 생성되는 것인데, 어째서 이게 가능한 것인가?
컴퓨터의 랜덤
사실 컴퓨터는 랜덤을 만들 수 없다.
이는 컴퓨터의 특성상 당연한 것인데,
컴퓨터는 스스로 생각하는 기계가 아닌 현재 상태와 주어진 값에 따라 정해진 결과를 내는 기계이기 때문이다.
이를 전공 용어로 결정론적 유한 오도마타(DFSM-Deterministic Finite State Automata)라고 한다.
결정론적(Deterministic)
결정론적이라는 말은 수학에서의 함수처럼, 입력값에 따른 결과는 항상 일정하다는 말이다.
반대로 비결정론적이면 입력값이 일정해도, 결과는 바뀔 수 있다.
※ 엥? 결정론을 함수에 비유했는데 x2+y2=1(원함수)는 x값에 따라 y값이 2개 나오잖아유?
여기서 말하는 건 결과값의 개수가 아닌, 결과값이 바뀔 수 있나의 여부이다.
원함수에서 x=1이면 y=1 또는 -1 2개가 나올지라도, 1과 -1이 아닌 1과 -2이 되는 경우는 없다.
유한 오도마타(Finite Automata)
이거 아님 근데 아래 설명을 들음 맞을지도?
유한 오도마타라는 말은 유한+오도마타인데
- 유한(!∞): 가질 수 있는 상태의 개수가 정해져 있슴
- 오도마타(자동인형): 입력값에 따라 다음 상태로 가는 기계
즉 유한한(몇 개의) 상태를 기억하고 있는 자동인형한테 입력값 목록을 주면,
자동인형의 현재 상태와 그 입력값에 맞춰 다음 상태로 가고,
입력값 목록이 끝에 다다랐을 때 최종 상태를 보여주는 것을 의미한다.
상태 개수는 정해져 있기 때문에 유한 오도마타는 해당 범위를 벗어나는 상태를 절대 출력할 수 없다.
간단한 예시
kaebalsaebal은 점심시간이 12시라, 11시 정각에서 11시 59분까지 오늘 뭐먹지를 생각하기로 했다.
우선 11시에 짜장면을 먹기로 생각했고 30분이 지났다.
11시 30분. 갑자기 생각이 바뀌어서 짬뽕이 먹고 싶어졌다. 그리고 30분이 지나도 생각이 바뀌지 않아 결국 짬뽕을 먹으러 갔다.
만약 11시 30분에 그대로 짜장면을 먹는다고 생각하면 그대로 짜장면을 먹는다.
여기서 kaebalsaebal이 인간이라면,
12시에 점심을 먹으러 갈 때 위에서처럼 생각해서 짜장면이나 짬뽕을 먹을 수 있고,
아님 전혀 다른 우동을 먹으러 갈 수도 있다.
하지만 kaebalsaebal이 결정론적 유한 오도마타라면 순서와 입력의 조합에 따른 모든 결과는 고정된다.
마치 이것처럼. 이미 본 미래는 결정된다
11시에 짜장면을 먹기로 생각하고, 11시 반에 짬뽕으로 바꾸면 무조건 짬뽕을 먹으러 가야 하고, 11시 반에 짜장면으로 그대로 생각하면 짜장면을 먹으러 가는 것이다.
(출처: https://upcurvewave.tistory.com/406)
전자공학도라면 배우는 논리 회로도 유한 상태 오도마타의 완벽한 예시이다.
위 그림처럼 상태는 A와 B의 조합 4가지로 정해져 있고, 해당 상태의 입력값에 따라 다음 상태는 절대로 변하지 않기 때문이다.
※ 위 글에서는 이해하기 쉽게 인과를 바꾸었는데, 사실 저 유한 상태 오도마타를 구현한 것이 논리 회로이다.
그래서?
아무튼 이 긴 이론을 왜 말했냐면,
컴퓨터의 상태가 정해져 있는 이상 결과는 예측할 수 있고,
따라서 컴퓨터는 순수한 랜덤을 절대 만들 수 없다 를 말하고 싶어서이다.
그럼 rand()나 randint()처럼 우리가 밥 먹듯이 쓰는 랜덤함수는 무엇인가?
이것도 결정적으로 말하면 순수한 랜덤이 아니긴 하지만,
입력값을 기반으로 특정한 수학적 알고리듬(상태 변환)을 통해 출력값이 랜덤인 것처럼 보이게 하는 것이다.
이를 전공언어로 의사(疑仕, Psuedo)난수 유사난수 라고 한다.
그리고 이 알고리듬에 들어가는 최초 입력값이 시드(Seed)인 것이다.
즉 가챠겜의 랜덤 알고리듬을 알 수 있으면, 나는 언제든 SSR를 뽑을 수 있다는 것이다!
이것도 한계가 있지 않나
이 알고리듬도 아까 말했듯이 컴퓨터는 결정적 유한 오토마타라,
입력값에 따른 출력값은 일정할 수 밖에 없다.
위의 가챠 예시도 그렇고, 무작위성이 중요한 로그-라이크(Rogue-Like, 매 판 별로 전개가 불규칙한) 게임에서도 시드와 난수 알고리듬을 잘못 정하면 치명적인 결과로 이어질 수 밖에 없다.
로그라이크야 뭐 공략으로 치부할 수 있다 해도,
현물 결제가 이뤄지는 랜덤박스면 현실 소송까지 이어질 수 있지 않겠는가…!
(출처: https://www.fandomspot.com/best-90s-rpgs/)
(과거 고전 RPG들이 RAM의 한계로 이거에 기반한 버그가 많았다.
요지는 특정 커맨드(상태값 변환과 그에 따른 입력)을 충족하면, 전투가 예측했던 대로 이뤄지는 것이었다)
그래서 이뤄진 것이, 입력값을 랜덤으로 정하면?
숫자는 무한대이기 때문에 결과물도 우리 눈에는 랜덤처럼 보이게 된다.
언어 개발자들도 바보가 아니기 때문에, rand() 같은 코드 상 랜덤 함수는 최대한 입력값을 랜덤으로 뽑아내려고 노력한다.
대표적으로 0.001초까지 측정하는 시간이나, CPU의 클럭, 보유한 기밀 난수표 등을 자체 알고리듬을 통해 조합해서 시드값을 뽑아내는 것이다.
(0.001초인 이유는 대부분의 프로그래밍 언어의 시간 단위가 밀리세컨드(0.001초)여서 그렇습니다~)
마치 군대에서 암구호가 매일매일 다르고, 뭔가 규칙성을 느낄 수도 있겠지만, 그 원리는 취급자 외 아무도 모르는 것과 같다.
다만 이것도 한계가 있으므로, 궁극적으로는 자연의 무작위 현상(아날로그)를 위주로 시드를 뽑아내려고도 한다.
대표적으로 주변 소음, 방사선 계측(!), 심지어는 양자역학까지 쓰이고 있다.
지금도 시판되는 갤럭시 퀀텀 시리즈는, 양자 난수 생성이라는 걸 통해 완벽한 무작위 랜덤을 생성해 낼 수 있다고 주장한다.
양자역학의 핵심이 불확실성이니, 이론상으론 맞지만…과연?
결론
맨 처음에 말한 마인크래프트나, 림월드의 맵 생성은 결국
- 초기 입력값(시드)를 자체적인 기준으로 정한다.
- 입력값을 시작으로, 자체적인 맵 생성 알고리듬을 적용한다.
- 이 알고리듬을 통해, 출력값(맵)은 무작위인 것처럼 보이게 된다.
- 위 게임들은 초기 입력값를 정할 수 있으므로, 결국 같은 시드면 어떤 컴퓨터는 같은 맵이 형성된다.
인 원리이다.
게임하다가 갑자기 삘 받아서 쓴 글이었다. 빨리 미루고 미룬 neutron 구축 글이나 써야지…