게임 이론

게임 개발 소프트웨어 마지막 수정: 2026-07-24 04:36:02

1. 개요[편집]

여기서 말하는 “게임”은 재미가 아니라, 여러 의사결정 주체가 서로의 선택에 영향을 받는 상황 전부를 뜻한다. 하필 이름이 게임이라 게임 개발자들이 반가워하는데, 실제로도 꽤 쓸모가 있다.

게임 이론(game theory)은 둘 이상의 의사결정 주체가 각자의 이익을 극대화하려 할 때 나타나는 전략적 상호작용을 수학적으로 분석하는 이론이다. 폰 노이만과 모르겐슈테른의 1944년 저작 Theory of Games and Economic Behavior가 분야를 세웠고, 이후 경제학·생물학·통신·인공지능으로 퍼졌다.

시뮬레이션·게임 개발 쪽에서 게임 이론이 중요한 이유는 두 가지다. 첫째, 체스·바둑 같은 완전정보 2인 제로섬 게임의 최적 전략 개념이 그대로 미니맥스 알고리즘과 몬테카를로 트리 탐색의 이론적 근거가 된다. 둘째, 불확실한 환경에서 “정보를 더 모을까, 지금 아는 최선을 쓸까”를 정량적으로 다루는 탐험-이용 문제가 게임 AI의 탐색 예산 배분과 정확히 같은 구조다.¹

2. 게임의 표현[편집]

게임을 수학적으로 적는 방법은 크게 둘이다.

정규형(normal form) — 플레이어 집합 $N$ , 각자의 전략 집합 $S_i$ , 보수함수 $u_i : S_1 \times \cdots \times S_n \to \mathbb{R}$ 의 3종 세트. 2인 유한 게임이면 보수 행렬 하나로 끝난다.
전개형(extensive form) — 트리로 적는다. 노드가 차례, 간선이 수(move), 잎이 최종 보수. 게임 AI가 실제로 탐색하는 자료구조가 바로 이것이고, 행동 트리와는 이름만 비슷할 뿐 완전히 다른 물건이다.

전개형에서 정보 집합(information set)이 모두 단일 노드면 완전정보 게임이다. 체스·바둑·오목이 여기 속하고, 포커나 안개가 낀 전략 게임은 불완전정보 게임이라 훨씬 어렵다.

3. 내시 균형[편집]

내시 균형(Nash equilibrium)은 모든 플레이어가 “다른 사람의 전략이 고정되어 있다면 나 혼자 바꿔 봐야 손해”인 전략 조합이다.

u_i(s_i^*, s_{-i}^*) \ge u_i(s_i, s_{-i}^*) \quad \forall i,\ \forall s_i \in S_i

내시(1950)는 유한 게임이면 혼합 전략(확률분포로 섞어 내는 전략)까지 허용할 때 균형이 항상 존재함을 증명했다. 가위바위보에는 순수 전략 균형이 없지만 $(1/3, 1/3, 1/3)$ 이라는 혼합 균형이 있는 식이다. 게임 밸런싱에서 “3티어 유닛이 서로 물고 물리게 만들어라”는 조언은 결국 순수 전략 균형이 하나로 굳지 않게 하라는 요구다.

주의할 점은 내시 균형이 전체 최적이 아니라는 것이다. 죄수의 딜레마에서 양쪽 배신은 유일한 내시 균형이면서 동시에 둘 다에게 최악에 가까운 결과다. 파레토 최적과 균형이 어긋나는 이 구조는 다중기준 방법이 다루는 파레토 개념과 함께 두면 이해가 빠르다. 균형이 여러 개 존재할 수도 있어서, “그중 어느 것이 실제로 선택되는가”는 이론이 아니라 관습·학습·진화의 문제로 넘어간다.²

균형을 “누가 계산해서 고르는 답”이 아니라 “개체군의 전략 비율이 시간에 따라 흘러가 도달하는 곳”으로 보는 것이 진화 게임 이론이다. 전략 $i$ 의 비율 $x_i$ 가 평균보다 높은 보수를 얻는 만큼 늘어난다는 복제자 동역학(replicator dynamics)

\dot{x}_i = x_i\left[(Ax)_i - x^{\top} A x\right]

이 그 표준 모형이고, 이 흐름이 끌어당기는 혼합 전략이 곧 진화적 안정 전략(ESS)이다.

3전략 대칭 게임(가위바위보 순환 구조)의 복제자 동역학을 RK4로 적분한 것. 삼각형은 전략 비율의 단체이고, 열두 개의 초기조건에서 출발한 궤적과 배경의 방향장이 함께 그려진다. 슬라이더 e는 같은 전략끼리 만났을 때의 보수로, 내부 혼합 균형 (1/3, 1/3, 1/3)의 안정성을 결정한다. e가 음수면 궤적이 안쪽으로 감겨 그 균형이 ESS가 되고, e=0이면 닫힌 궤도로 영원히 돌며, e가 양수면 바깥으로 밀려나 세 꼭짓점을 순환하는 경계 궤도로 간다. 변이율 μ를 올리면 개체군이 경계에서 되밀려 내부로 복귀한다.

가위바위보처럼 서로 물고 물리는 게임에서는 균형이 점 하나로 수렴하는 대신 개체군 비율이 끝없이 순환할 수 있고, 이 순환이 안으로 감기느냐 밖으로 풀리느냐가 보수행렬의 대각 성분 하나로 뒤집힌다. “균형이 존재한다”와 “균형에 도달한다”가 별개의 문제라는 사실이 이 그림에서 바로 보인다.

4. 제로섬과 미니맥스 정리[편집]

두 플레이어의 보수 합이 항상 0인 제로섬 게임에서는 상황이 극적으로 단순해진다. 폰 노이만의 미니맥스 정리(1928)에 따르면 혼합 전략을 허용할 때

\max_{p} \min_{q} \; p^{\top} A\, q \;=\; \min_{q} \max_{p} \; p^{\top} A\, q

가 성립하고, 이 공통값을 게임의 가치(value)라 부른다. 즉 “내가 최선을 다하고 상대도 최선을 다한다”는 가정이 순서에 무관하게 같은 답을 준다. 이 정리가 있기에 게임 트리를 훑으며 내 차례엔 최댓값, 상대 차례엔 최솟값을 취하는 미니맥스 알고리즘이 정당화된다. 완전정보 유한 게임에서 순수 전략 균형이 후진 귀납(backward induction)으로 항상 구해진다는 체르멜로의 결과도 같은 맥락이다.

물론 이론이 보장하는 것은 게임 트리를 끝까지 볼 수 있을 때의 이야기다. 바둑의 상태 공간은 $10^{170}$ 규모라 끝까지 볼 방법이 없고, 그래서 실전 엔진은 깊이를 자르고 평가함수로 때운다. 그 대가가 지평선 효과다.

5. 탐험과 이용, 그리고 밴딧[편집]

다중 슬롯머신 문제(multi-armed bandit)는 게임 이론과 통계적 의사결정이 만나는 지점이다. $K$ 개의 팔이 각각 미지의 보상 분포를 갖고, 매 라운드 하나만 당길 수 있을 때 누적 후회(regret)를 최소화하는 문제다. 여기서 상대는 사람이 아니라 자연이지만, “정보를 사는 데 얼마를 쓸 것인가”라는 구조는 전략 게임과 동일하다.

UCB1은 각 팔에 대해 표본 평균에 불확실성 보너스를 더한 지표를 최대화한다.

\text{UCB}_i = \bar{x}_i + c\sqrt{\frac{\ln N}{n_i}}

당겨 본 횟수 $n_i$ 가 적은 팔일수록 보너스가 커지므로 자동으로 탐험이 일어나고, $N$ 이 커질수록 로그로만 자라므로 결국 최적 팔에 수렴한다. 이 규칙의 누적 후회는 라운드 수에 대해 $\mathcal{O}(\log N)$ 으로, 하한과 같은 차수라는 것이 증명되어 있다. 몬테카를로 트리 탐색의 UCT는 게임 트리의 각 노드를 하나의 밴딧 문제로 보고 이 식을 그대로 재활용한 것이다.

6. 게임 AI에서의 실제 활용[편집]

턴제 전투·보드게임: 미니맥스 + 알파-베타 가지치기가 여전히 표준이고, 분기수가 크거나 평가함수를 만들기 어려우면 MCTS로 간다.
행동 선택: 유틸리티 AI는 각 행동의 효용을 점수화해 고르는데, 이 효용 개념 자체가 폰 노이만-모르겐슈테른 기대효용 이론에서 왔다. 유한 상태 기계나 행동 트리가 “무엇을 할 수 있는가”의 구조를 준다면, 게임 이론은 “왜 그것을 골라야 하는가”의 근거를 준다.
밸런싱: 유닛 상성표를 보수 행렬로 놓고 혼합 균형을 풀면 “메타에서 각 유닛이 몇 %로 등장해야 균형인지”가 나온다. 실제 픽률이 이론값에서 크게 벗어나면 밸런스 패치의 근거가 된다.
군중·교통: 각 개체가 이기적으로 경로를 고르는 상황은 혼잡 게임(congestion game)으로 모형화되며, 군중 시뮬레이션의 병목 형성이나 브라에스의 역설³이 여기서 나온다.
진화적 안정 전략: 반복 게임에서 학습·복제자 동역학으로 전략 분포가 변해 가는 모형은 유전 알고리즘식 자기대전 학습과 자연스럽게 연결된다.

정리하면 게임 이론은 게임 AI에 알고리즘을 직접 주는 이론이라기보다, 어떤 알고리즘이 무엇을 최적화하고 있는지 말해 주는 언어에 가깝다. 그 언어 없이 짜인 AI는 대체로 “이겼는데 왜 이겼는지 모르는” 상태로 출시된다.⁴

7. 관련 문서[편집]

그래서 “게임 이론 배우면 게임 잘 만드나요?”라는 질문에는 “밸런스 회의에서 말이 세진다” 정도가 정직한 답이다. 균형 개념을 알면 적어도 상성표를 감으로 고치자는 주장에 반박할 근거가 생긴다. ↩
균형이 여러 개일 때 어느 쪽으로 굳는지를 다루는 것이 균형 선택(equilibrium refinement) 문제인데, 반세기 넘게 정답이 없다. 멀티플레이어 게임에서 “메타가 굳었다”는 말은 플레이어 집단이 하나의 균형을 관습으로 골랐다는 뜻이다. ↩
도로를 하나 더 깔았더니 모두의 통행 시간이 늘어나는 현상. 각자가 이기적으로 최단 경로를 고르면 전체 최적보다 나빠질 수 있다는 것이 요점이다. 길찾기 AI를 개별 최적으로만 짜면 게임 안에서도 재현된다. ↩
반대로 이론만 붙들고 있으면 30fps 안에 안 끝나는 완벽한 균형 해를 계산하다가 프레임을 잃는다. 실무에서는 대체로 “이론적으로 옳은 것”보다 “16ms 안에 끝나는 것”이 이긴다. ↩