반사실적 후회 최소화

게임 개발 최적설계 통계 마지막 수정: 2026-08-26 04:48:36

1. 개요[편집]

반사실적 후회 최소화 Counterfactual Regret Minimization (CFR)
제안	Zinkevich · Johanson · Bowling · Piccione (2007)
대상	2인 영합 전개형 불완전정보 게임
핵심 정리	전체 후회 $\le$ 정보집합별 즉시 반사실적 후회의 양수부 합
국소 알고리즘	후회 매칭 — 학습률 없음
수렴률	$\bar R^T_i \le \Delta\,\lvert\mathcal I_i\rvert\sqrt{\lvert A_i\rvert}\,/\,\sqrt{T}$, 평균 전략은 $2\varepsilon$-내시
저장량	트리 크기가 아니라 정보집합 수에 비례
주요 변형	CFR+ · MCCFR(외부·결과 샘플링) · DCFR · Deep CFR
업적	헤즈업 리밋 홀덤 해결(2015) · Libratus/DeepStack(2017)

후회를 게임 전체에 대해 재려니 지수적으로 크다. 그래서 결정 지점 하나하나로 쪼갠 뒤, 쪼갠 것들의 합이 원래 것을 덮는다는 사실만 증명했다. 그게 전부다.

반사실적 후회 최소화(counterfactual regret minimization, CFR)는 전개형 불완전정보 게임의 전체 후회를 정보집합마다 정의한 「반사실적 후회」의 합으로 상계하고, 각 정보집합에서 독립적으로 무후회 학습을 돌려 전체 후회를 부분선형으로 만드는 균형 계산 알고리즘이다. 진케비치·요한슨·볼링·피치오네가 2007년 NIPS 논문 「Regret Minimization in Games with Incomplete Information」에서 발표했고, 이후 10년 만에 헤즈업 포커를 사람 손에서 빼앗아 갔다.

무후회 학습 문서가 후회 개념의 계층과 “왜 시간평균만 수렴하는가”를, 내시 균형 문서가 균형 계산의 복잡도 지형을 이미 다룬다. 여기서는 그 위에 얹히는 알고리즘 자체 — 반사실적 값의 정확한 정의, 분해 정리, 수렴률, 그리고 실제 코드에서 무엇이 터지는가 — 를 본다.

2. 왜 전개형이 문제인가[편집]

포커·브리지·협상 같은 게임은 정규형으로 펴면 순수 전략의 수가 트리 크기에 대해 지수적으로 폭발한다. 헤즈업 리밋 텍사스 홀덤의 결정 상태는 $3 \times 10^{17}$ 규모이고 정보집합은 $3.19 \times 10^{14}$ 규모다. 이 게임을 정규형 행렬로 적어 선형계획법에 넣는다는 것은 상상도 못 할 일이다.

고전적 우회로가 수열형(sequence form) 표현이었다. 전략을 “행동 하나”가 아니라 “정보집합에서 행동으로 이어지는 수열의 실현확률”로 파라미터화하면 제약이 트리 크기에 선형이 되어 LP로 풀린다. 문제는 그 선형이 $10^{14}$ 스케일이라는 것 — 제약 행렬을 메모리에 올릴 수가 없다.

CFR의 관점 전환은 여기서 나온다. 전역 LP를 포기하고, 정보집합마다 행동 수만큼의 후회 벡터 하나씩만 들고 다닌다. 저장량이 트리의 노드 수가 아니라 정보집합 수 × 행동 수에 비례하고, 정보집합끼리 통신할 필요도 없다. 그래서 분산·병렬화가 자연스럽고, 정확히 이 성질이 클러스터 규모의 계산을 가능하게 했다.

3. 도달확률과 반사실적 값[편집]

기호부터 정리하자. 히스토리 $h$ , 종료 히스토리 $z \in Z$ , 전략 조합 $\sigma$ 에 대해 $\pi^\sigma(h)$ 를 $h$ 에 도달할 확률(모든 플레이어와 우연 노드의 기여를 곱한 것)이라 하고, 이를 플레이어별로 쪼개 $\pi^\sigma_i(h)$ 는 플레이어 $i$ 의 기여, $\pi^\sigma_{-i}(h)$ 는 나머지 전원과 우연의 기여라 하자. 정의상 $\pi^\sigma(h) = \pi^\sigma_i(h)\,\pi^\sigma_{-i}(h)$ 다.

플레이어 $i$ 의 정보집합 $I$ 에서의 반사실적 값은

v_i(\sigma, I) \;=\; \sum_{h \in I}\ \sum_{z \in Z,\; h \sqsubseteq z} \pi^{\sigma}_{-i}(h)\;\pi^{\sigma}(h, z)\; u_i(z)

로 정의된다. $\pi^\sigma(h,z)$ 는 $h$ 에서 $z$ 까지 가는 확률이다. 핵심은 가중치에 $\pi_{-i}$ 만 쓰고 $\pi_i$ 는 안 쓴다는 것. 해석하면 “플레이어 $i$ 가 이 정보집합에 도달하려고 최선을 다했다면(자기 도달확률을 1로 놓았다면) 여기서 기대할 수 있는 값”이다. 반사실(counterfactual)이라는 이름이 여기서 나온다.

이 한 가지 선택이 알고리즘 전체를 지탱한다. 만약 $\pi_i$ 를 곱해 버리면, 정보집합 $I$ 의 값이 그 위쪽 정보집합들에서 내가 어떤 전략을 썼느냐에 통째로 의존하게 되어 국소 최적화가 서로 얽힌다. $\pi_i$ 를 빼면 각 정보집합의 후회가 다른 정보집합의 전략과 무관하게 정의되고, 그래서 병렬로 독립 최소화하는 것이 정당해진다.

$I$ 에서 행동 $a$ 를 무조건 취하도록 바꾼 전략을 $\sigma|_{I \to a}$ 라 쓸 때, 즉시 반사실적 후회는

R^T_{i,\mathrm{imm}}(I) \;=\; \frac{1}{T}\max_{a \in A(I)} \sum_{t=1}^{T}\Bigl( v_i\bigl(\sigma^t|_{I \to a},\, I\bigr) - v_i\bigl(\sigma^t,\, I\bigr) \Bigr)

이다. 형태를 보면 그냥 외부 후회인데, 손실 대신 반사실적 값을 쓰고 정보집합 하나에 국한했을 뿐이다.

4. 분해 정리 — 이 문서의 전부[편집]

CFR 논문의 정리 3은 다음 한 줄이다.

R^T_i \;\le\; \sum_{I \in \mathcal I_i} \bigl[\,R^T_{i,\mathrm{imm}}(I)\,\bigr]^{+}

즉 게임 전체의 후회는 정보집합별 즉시 반사실적 후회의 양수부 합으로 상계된다. 직관은 이렇다. 전체 후회를 재는 최선반응 이탈은 트리를 따라 내려가며 각 정보집합에서 무언가를 바꾸는 것으로 분해되는데, 반사실적 값이 자기 도달확률을 빼고 정의된 덕분에 각 지점의 개선분이 위쪽 선택과 곱해지지 않고 그냥 더해진다. 양수부를 취하는 이유는 어떤 정보집합에서는 이탈이 손해일 수 있는데 그걸 이득으로 상쇄시키지 않기 위해서다.

따라서 처방이 나온다. 각 정보집합에서 아무 무외부후회 알고리즘이나 독립적으로 돌려라. 전체 후회는 자동으로 부분선형이 된다. 여기서 쓰는 것이 하트·마스콜렐(2000)의 후회 매칭이다.

\sigma^{T+1}(I, a) \;=\; \frac{\bigl[R^T(I,a)\bigr]^{+}}{\sum_{b \in A(I)} \bigl[R^T(I,b)\bigr]^{+}}

(분모가 0이면 균등분포.) 헤지·MWU 대신 굳이 이걸 쓰는 이유는 학습률이 없기 때문이다. 정보집합이 $10^{14}$ 개인데 각각에 $\eta$ 를 맞출 수는 없고, 후회 매칭은 스케일 불변이라 보수의 단위도 신경 쓸 필요가 없다.¹

5. 수렴률과 2ε-내시[편집]

후회 매칭의 후회 상한 $\sqrt{|A|}\,\Delta\sqrt{T}$ 를 정리 3에 대입하면

\bar R^T_i \;\le\; \frac{\Delta_{u,i}\;|\mathcal I_i|\;\sqrt{|A_i|}}{\sqrt{T}}

가 나온다. $\Delta_{u,i}$ 는 보수의 범위, $|\mathcal I_i|$ 는 정보집합 수, $|A_i|$ 는 최대 행동 수다. 평균 후회가 $O(1/\sqrt T)$ 로 떨어지므로 $\varepsilon$ 정확도에는 $T = O(|\mathcal I|^2 |A| \Delta^2 / \varepsilon^2)$ 반복이 필요하다.

여기에 2인 영합 게임의 표준 정리가 붙는다. 두 플레이어의 평균 후회가 모두 $\varepsilon$ 이하이면 평균 전략 조합은 $2\varepsilon$ -내시 균형이다. 즉 최선반응 상대에게 털리는 양(착취가능도, exploitability)이 $2\varepsilon$ 이하로 보장된다. 이 정리 덕에 CFR은 “후회를 줄이는 알고리즘”이면서 동시에 “균형을 계산하는 알고리즘”이 된다.

주의할 점 둘.

답은 평균 전략이지 현재 전략이 아니다. 현재 전략 $\sigma^T$ 는 균형 주위를 영원히 진동할 수 있다. 반드시 별도로 누적 평균을 유지해야 하고, 그 평균은 자기 도달확률로 가중해야 한다.

\bar\sigma^T_i(I,a) \;=\; \frac{\sum_{t=1}^{T} \pi^{\sigma^t}_i(I)\,\sigma^t(I,a)}{\sum_{t=1}^{T} \pi^{\sigma^t}_i(I)}

가중치를 빼먹고 단순평균을 내는 것이 초심자 구현의 1번 버그다. 전개형에서 “그 정보집합에 실제로 얼마나 자주 갔는지”를 반영하지 않으면 평균 전략이 수열형 표현에서 유효한 전략이 아니게 되고, 후회는 잘 줄어드는데 착취가능도가 안 떨어지는 기묘한 상태에 빠진다.

보장은 2인 영합 전용이다. 3인 이상이나 일반합에서는 CFR이 수렴하는 곳이 내시가 아니다 — 무후회 학습의 대응대로 (조대) 상관 균형 쪽이며, 그마저 전개형에서는 개념이 여러 갈래로 갈린다.

6. 쿤 포커 — 손으로 검산할 수 있는 유일한 크기[편집]

CFR 구현의 첫 테스트는 예외 없이 쿤 포커(Kuhn poker, 쿤 1950)다. 카드가 J·Q·K 셋뿐이고 각자 1을 앤티한 뒤 한 장씩 받는다. 플레이어 1이 체크 또는 벳(1), 상대는 그에 응한다. 종료 노드가 딜당 5개, 딜이 6가지이므로 총 30개, 정보집합은 각 플레이어 6개씩 총 12개다. 이 정도면 균형을 해석적으로 적을 수 있고, 그래서 코드가 맞는지 틀리는지를 눈으로 확인할 수 있다.

쿤 포커 게임트리를 매 반복 전 순회하는 바닐라 CFR 과 CFR+ 를 함께 돌린다. 위쪽은 평균 전략의 착취가능도를 정확한 최선응답으로 재서 로그-로그로 그린 것이고(바닐라 실측 기울기 −0.503 으로 O(1/√T) 를 소수점 둘째 자리까지 재현, T = 10⁵ 에서 1.35e−3), 아래쪽은 인포셋 12개의 현재 전략과 평균 전략 막대다. 현재 전략이 [0, 1] 전 구간을 왕복하는 2000반복 동안 평균은 1.4e−3 밖에 움직이지 않고, P(bet|K) = 3α · P(call|Q,pb) = α + 1/3 을 만족하는 균형족의 한 점에 앉는다.

균형의 모양이 재미있다. 플레이어 1의 균형 전략은 하나가 아니라 매개변수 $\alpha \in [0, 1/3]$ 의 1-매개변수족이다.

J를 들고 확률 $\alpha$ 로 벳한다 — 최악의 카드로 하는 블러프다. 체크했다가 벳을 당하면 폴드.
Q를 들면 항상 체크한다. 체크 후 벳을 당하면 확률 $\alpha + 1/3$ 로 콜.
K를 들고 확률 $3\alpha$ 로 벳한다 — 최고의 카드를 일부러 체크해 숨기는(슬로플레이) 것이 나머지 확률이다. 체크 후 벳을 당하면 항상 콜.

플레이어 2의 균형 전략은 반대로 유일하다. 벳을 당했을 때 K는 항상 콜, Q는 확률 $1/3$ 로 콜, J는 폴드. 체크를 당했을 때는 K로 항상 벳, Q는 체크, J는 확률 $1/3$ 로 벳한다. 게임 값은 플레이어 1 기준 $-1/18 \approx -0.0556$ — 선을 잡는 쪽이 구조적으로 손해인 게임이다.

이 작은 예제가 가르쳐 주는 것이 세 가지다. 첫째, 최적 플레이에 블러프와 슬로플레이가 필수로 들어간다. 심리전이 아니라 균형의 산술적 귀결이다. 둘째, J로 블러프하는 비율 $\alpha$ 와 K로 벳하는 비율 $3\alpha$ 의 3배 관계가 균형 조건에서 튀어나온다 — 강한 패로 벳하는 빈도와 약한 패로 벳하는 빈도가 고정 비율로 묶여야 상대가 콜과 폴드 사이에서 무차별해진다. 셋째, 균형이 유일하지 않을 때 CFR이 어느 것으로 가는지는 초기값과 갱신 순서가 정한다. 그러니 “논문의 $\alpha$ 와 내 결과의 $\alpha$ 가 다르다”는 것은 버그가 아니다. 검증해야 할 것은 $\alpha$ 값이 아니라 착취가능도가 0으로 가는지, 그리고 게임 값이 $-1/18$ 로 가는지다.²

7. CFR+ — 상수를 갈아 낸 변형[편집]

2014년 타멜린이 제안한 **CFR+**는 세 가지 변경만으로 실전 수렴 속도를 자릿수 단위로 끌어올렸다.

후회 매칭 $^+$ . 누적 후회를 매 반복 0에서 자른다. $Q^t(I,a) = \bigl[Q^{t-1}(I,a) + r^t(I,a)\bigr]^{+}$ . 원래 CFR에서는 한번 크게 음수가 된 행동이 다시 좋아져도 후회가 0을 넘어 올라오기까지 오래 걸려 “죽은 행동”이 되는데, 그 지연이 사라진다.
선형 평균. 평균 전략을 $t$ 에 비례하는 가중치로 누적한다. 초반의 엉터리 전략이 평균을 오래 오염시키는 것을 막는다.
교대 갱신. 두 플레이어를 동시에 갱신하지 않고 번갈아 갱신한다.

이론적 최악경우 차수는 여전히 $O(1/\sqrt T)$ 지만, 실측 수렴이 워낙 빨라 대부분의 실무 구현이 CFR+ 계열로 갈아탔다. 이후 브라운·샌드홀름의 DCFR(discounted CFR)이 후회와 평균의 감쇠 지수를 파라미터화해 한 번 더 개선했다.

여기에 이 분야 특유의 아이러니가 하나 있다. 1차 최적화 기법(호다·길핀·페냐·샌드홀름의 excessive gap technique 등)은 수열형 LP를 매끄러운 안장점 문제로 보고 $O(1/T)$ 수렴률을 증명했다. CFR보다 차수가 좋다. 그런데 실전에서는 CFR+가 이겼다 — 상수와 반복당 비용, 그리고 파라미터가 없다는 점이 차수 차이를 압도했다. “이론적으로 더 빠른 알고리즘이 실제로는 느린” 표준 사례이며, 최근의 예측적(predictive) CFR 계열은 두 진영을 봉합해 $O(1/T)$ 보장과 CFR+의 실전 성능을 함께 노린다.

8. MCCFR — 트리를 다 걷지 않는다[편집]

바닐라 CFR은 매 반복 게임 트리 전체를 순회한다. 정보집합이 $10^{14}$ 개면 한 반복도 못 끝낸다. 몬테카를로 CFR(랭톳·워·진케비치·볼링 2009)은 트리의 일부만 표본화하고 중요도 가중으로 편향을 제거한다. 표본화 대상에 따라 계열이 갈린다.

우연 샘플링(chance sampling). 우연 노드(딜)만 표본화하고 나머지는 전부 순회. 가장 온건하고 초기 포커 봇의 표준이었다.
외부 샘플링(external sampling). 우연과 상대의 행동을 표본화하고, 갱신 대상 플레이어의 행동은 전부 순회한다. 반복당 비용이 갱신 플레이어의 정보집합 수 정도로 떨어지면서도 분산이 적당해서, 가장 널리 쓰이는 절충안이다.
결과 샘플링(outcome sampling). 종료 노드까지 가는 경로 하나만 표본화한다. 반복이 극도로 싸지만 중요도 가중치가 커져 분산이 크다. 온라인·모델 프리 설정과 궁합이 좋다.

표본 반사실적 값은 불편추정량이므로 후회의 기댓값은 그대로이고, 수렴 보장은 “확률 $1-p$ 로 성립하며 상한에 $1/\sqrt p$ 정도의 상수가 더 붙는다”는 고확률 형태로 바뀐다. 차수는 그대로 두고 반복 비용만 수십~수백 배 줄이는 교환이라, 큰 게임에서는 사실상 선택의 여지가 없다.

몬테카를로 트리 탐색과 이름이 비슷하지만 목표가 다르다. MCTS는 상대 모형 아래에서 최선반응을 찾고, MCCFR은 균형을 찾는다. 불완전정보 게임에 MCTS를 그대로 들이대면 정보집합을 결정화(determinize)하면서 균형에서 벗어난 착취 가능한 전략이 나오는 것이 알려진 실패 양상이다.

9. 추상화와 포커의 함락[편집]

$10^{14}$ 개 정보집합에 각각 후회 벡터를 두면 여전히 수십 테라바이트다. 그래서 실무는 추상화를 먼저 건다.

카드 추상화. 전략적으로 비슷한 핸드를 버킷으로 묶는다. 승률 히스토그램의 거리로 군집화하는 방식, 미래 잠재력까지 고려하는 potential-aware 방식 등이 있다.
행동 추상화. 노리밋에서 가능한 베팅 크기를 몇 개로 줄이고, 실전에서 상대가 추상화 밖 크기를 베팅하면 가까운 것으로 번역한다.

추상화에는 고약한 성질이 하나 있다. 추상화를 더 정교하게 만들면 원래 게임에서의 착취가능도가 오히려 나빠질 수 있다(추상화 병리, 워 등 2009). 추상 게임에서 균형에 더 가까이 가는 것과 진짜 게임에서 덜 털리는 것이 별개의 목적이기 때문이다. 그래서 이 분야의 평가는 “추상 게임의 착취가능도”가 아니라 원 게임 기준의 착취가능도 또는 실전 승률로만 한다.

굵직한 결과들을 시간순으로.

2015 — 헤즈업 리밋 홀덤 해결. 볼링·버치·요한슨·타멜린이 CFR+로 $3.19\times10^{14}$ 정보집합 게임을 200노드 클러스터에서 68일(약 900 코어-년) 돌려 착취가능도를 1 mbb/g 미만으로 낮췄다. 사람이 평생 쳐도 완벽한 플레이와 통계적으로 구분할 수 없는 수준이라 사실상 해결(essentially solved)로 선언됐다.³
2017 — DeepStack. 모라브치크 등이 재귀적 재해결(continual re-solving)과 반사실적 값을 예측하는 심층 학습 신경망을 결합해, 미리 계산한 거대 전략표 없이 실시간으로 노리밋 헤즈업을 플레이했다. 프로 11명과 4만 4천여 핸드를 겨뤄 이겼다.
2017 — Libratus. 브라운·샌드홀름의 시스템이 추상화 기반 청사진 전략 + 중첩 서브게임 재해결 + 밤사이 자기 약점을 메우는 자기개선 모듈로, 최상위 노리밋 헤즈업 프로 4명과 12만 핸드를 겨뤄 100핸드당 14.7 빅블라인드 차이로 이겼다. 통계적으로 유의한 승리였다.
2019 — Pluribus. 6인 노리밋까지 확장됐지만 이론적 보장은 없다. 3인 이상 게임에서 무후회 학습이 가는 곳은 내시가 아니기 때문이다. 그래도 이겼다는 것이 이 결과의 전부이자 한계다.

이 계보에서 반복해 등장하는 교훈은 “균형을 미리 다 풀어 두는 것에서 탐색 시점에 관련 부분만 다시 푸는 것으로” 무게중심이 옮겨 갔다는 점이다. 서브게임 재해결은 불완전정보에서 그냥은 성립하지 않는다 — 서브게임의 값이 그 위쪽에서 상대가 어떻게 플레이했는지에 의존하므로, 상대의 반사실적 값에 제약을 걸어 안전성을 보장하는 별도 장치가 필요하다. 완전정보 게임의 미니맥스 알고리즘에서 부분트리를 독립적으로 평가하던 습관이 여기서는 바로 착취로 돌아온다.

10. 구현 함정[편집]

반사실적 도달확률에 자기 확률을 넣지 마라. $\pi_{-i}$ 에 $\pi_i$ 를 곱해 버리는 것이 가장 흔하고 가장 안 보이는 버그다. 후회는 여전히 줄어들고 로그도 예뻐 보이는데 균형으로는 안 간다. 쿤 포커에서 게임 값이 $-1/18$ 에 안 붙으면 이걸 먼저 의심한다.
평균 전략 가중치를 확인해라. 앞서 말한 $\pi^{\sigma^t}_i(I)$ 가중이다. 단순평균은 틀린 답을 준다.
착취가능도를 측정 지표로 삼아라. 작은 게임이라면 양쪽 최선반응을 완전 계산해 실제 착취가능도를 뽑을 수 있다. 이 곡선이 $1/\sqrt T$ 기울기로 내려가지 않으면 어딘가 틀린 것이고, 후회 곡선만 보고 있으면 절대 못 잡는다.
후회 누적에 float32를 쓰면 언젠가 죽는다. $10^9$ 반복 규모에서 누적 후회는 매우 커지고 매 반복의 증분은 매우 작아서, 단정밀도로는 증분이 통째로 흡수된다. 대규모 구현이 후회를 정수형이나 고정소수점으로 저장하는 이유다.
0으로 나누기를 정의해 둬라. 모든 후회가 0 이하인 정보집합에서 후회 매칭의 분모가 0이 된다. 균등분포로 떨어뜨리는 것이 표준이며, 이걸 NaN으로 흘려보내면 트리 전체가 조용히 오염된다.
트리 순회 순서와 재귀 깊이. 반복당 트리 전체를 도는 구현에서 병목은 대개 솔버가 아니라 메모리 접근이다. 정보집합을 배열로 평탄화하고 후회·평균을 연속 메모리에 두는 것만으로 몇 배가 나온다. 희소행렬 코드에서 하던 그 이야기와 같다.

11. 관련 문서[편집]

후회 매칭이 헤지보다 실전에서 사랑받는 이유의 절반은 “튜닝할 게 없다”이고, 나머지 절반은 “보수 스케일을 정규화 안 해도 된다”이다. mbb 단위든 칩 단위든 결과가 같다. 상한에 등장하는 $\Delta_u$ 가 보수 범위인데, 그건 분석에만 나오고 코드에는 안 나온다는 점이 결정적이다. ↩
CFR을 처음 구현하는 사람이 겪는 가장 흔한 좌절은 “쿤 포커는 맞는데 레둑(Leduc) 포커에서 안 맞는다”이다. 쿤은 정보집합이 12개라 도달확률 버그가 있어도 우연히 맞는 경우가 있고, 카드가 두 라운드에 걸쳐 나오는 레둑에서는 그 우연이 사라진다. 테스트는 반드시 두 게임 다 해야 하며, 이 순서를 지키지 않아 며칠을 태우는 것이 통과의례처럼 굳었다. ↩
발표 논문의 제목이 그냥 「Heads-up limit hold’em poker is solved」였다. 여기서 “solved”는 체커처럼 완전히 계산됐다는 뜻이 아니라 약하게 해결(weakly solved), 즉 게임 값과 최적 전략을 실용적 오차 안에서 알아냈다는 뜻이다. 저자들이 붙인 기준이 재미있는데, “한 사람이 평생(70년간, 하루 200핸드) 쳐도 통계적으로 착취를 입증할 수 없는 수준”이었다. 정확도의 정의를 인간 수명으로 잡은 드문 사례. ↩