CFR 알고리즘과 내쉬 균형 수렴 원리 #1

이번 글에서는 우리가 맨날 돌리는 솔버의 뼈대인 CFR 알고리즘에 대해 다루려고 합니다.
최근 NL25 세션 뛰면서 베리언스 쳐맞고 감이 좀 들쭉날쭉해서,
머리도 식힐 겸 뜬금없지만 GTO 이론적인 부분이나 정리해봄.
(사실 아까 쓰다가 한 번 날려먹어서 다시 쓰는 중임 ㅎ)

STEP 1. CFR과 Regret(후회)의 수치화

CFR은 2007년 앨버타 대학에서 발표된 알고리즘임.
풀어쓰면 Counterfactual Regret Minimization인데 핵심은 단순하다.
"아 그때 체크레이즈 말고 그냥 B75 씨벳 칠걸" 하는 후회를 수치화하는 거임.

특정 노드, 예를 들어 BTN vs BB 3bp T33r 보드에서
선택하지 않은 액션의 '가상 EV'와 실제 선택한 액션의 EV 차이를 regret으로 기록함.
그리고 이 regret 값이 큰 액션일수록 다음 시뮬레이션 반복에서 더 높은 빈도로 선택하게 만듦.
이 짓거리를 수백만 번 반복하면 결국 아무도 전략을 바꿔서 EV를 높일수 없는 상태,
즉 내쉬 균형으로 수렴하게 된다는 게 기본 원리다.

STEP 2. 솔버에 대한 흔한 오해와 버킷팅

여기서 먼저 하나 짚고 넘어갈 게 있음.
가끔 보면 "솔버는 홀덤의 모든 경우의 수를 완벽하게 계산한다"고 생각하는 사람들이 있는데.
완전 틀린 소리다.
텍사스 홀덤의 경우의 수는 우주 원자 수보다 많아서 전체 계산은 불가능함.

그래서 솔버는 복잡한 게임 트리를 단순화하는 과정을 거치는데,
이걸 추상화(Abstraction)라고 부름.
비슷한 에퀴티나 특성을 가진 핸드들을 묶어버리는 버킷팅(Bucketing) 기법을 써서 근사치를 구하는 거임.
그러니까 솔버 결과가 무조건적인 진리라기보단 고도로 계산된 근사값이라고 보는 게 맞음.

STEP 3. MCCFR과 DCFR, 그리고 AI의 발전

오리지널 CFR만으로는 여전히 계산량이 너무 빡셌음.
그래서 2009년에 등장한 게 MCCFR (Monte Carlo CFR)이다.
모든 노드를 탐색하는 대신 특정 경로만 샘플링해서 훑는 방식으로 속도를 수백 배 끌어올림.
우리가 쓰는 PioSolver나 GTO Wizard 같은 툴들이 대부분 이 MCCFR 기반이라고 보면 됨.

여기에 2019년에는 DCFR (Discounted CFR)이 나옴.
이건 시뮬레이션 초반에 발생한 후회값(regret)에 더 큰 가중치를 둬서 수렴 속도를 극한으로 땡긴 버전임.
이런 알고리즘 발전 덕분에 2017년 카네기 멜론 대학의 Libratus가 헤즈업을 정복하고,
2019년 Pluribus가 6max에서 프로들을 다 박살낼수 있었던 거임.
최근 WSOP나 Triton 같은 하이롤러 대회 보면,
직관으로 치던 올드스쿨 프로들도 결국 이 솔버 기반의 폴라라이즈드 레인지나 이런거 장착하고 나오는 게 현실이다.

예상 반박: 어차피 마이크로 풀에서는 이런 GTO보다 익스플로잇이 최고 아닌가요?
답변: 맞음. 나도 철저하게 Exploit 옹호파고 텔 읽는 걸 우선시함.
실제로 최근 세션에서 빌런이 턴에서 콜할 때 타이밍 텔 보고 리버 대응하는 게 수익이 더 좋았음.
근데 상대가 언더블러프 하는지, 레인지 어드밴티지를 어떻게 쓰는지 파악하려면 결국 기준점(GTO)을 알아야 비틀수 있는 거임.