Pluribus 스타일의 포커 AI를 처음부터 구축한 방법

포커가 어려운 이유

체스(Chess)와 바둑(Go)은 완전 정보 게임(perfect information games)으로, 두 플레이어 모두 모든 것을 볼 수 있습니다. 이 게임들의 도전 과제는 순수하게 계산적인 문제입니다.

포커는 **불완전 정보 게임 (imperfect information game)**입니다. 상대방의 카드를 볼 수 없습니다. 모든 결정은 상대방이 가질 수 있는 모든 핸드 범위(range)를 고려해야 합니다.

표준 미니맥스 (minimax) 알고리즘은 작동하지 않습니다. 상대방의 핸드를 모르는 상태에서는 포지션을 평가할 수 없기 때문입니다.

해결책은 **내쉬 균형 (Nash equilibrium)**입니다. 이는 어느 플레이어도 일방적으로 자신의 행동을 바꿈으로써 기대 가치(EV)를 개선할 수 없는 전략을 의미합니다. 포커에서는 이를 GTO (Game-Theoretically Optimal, 게임 이론적 최적화)라고 부릅니다. 정의상 착취 불가능(Unexploitable)한 상태입니다.

1단계: 반사실적 후회 최소화 (Counterfactual Regret Minimization)

CFR (Zinkevich et al., 2007)은 강력한 포커 AI를 가능하게 만든 알고리즘입니다.

직관: 자신과 반복해서 대결하십시오. 매 게임이 끝난 후 다음과 같이 질문합니다: "만약 내가 항상 다른 행동을 취했다면 얼마나 더 잘했을까?" 이것이 바로 후회(regret)입니다.

전략을 업데이트합니다: 누적된 양(+)의 후회에 비례하여 행동을 수행합니다. 이를 수천 번 반복합니다. 전략의 **시간 평균 (time-average)**은 내쉬 균형 (Nash equilibrium)으로 수렴합니다.

저는 포커 AI 연구의 표준 테스트베드인 216개의 정보 집합(information sets)을 가진 6-카드 토이 게임인 "Leduc Hold'em"에 이를 구현했습니다.

def get_strategy(self, reach_prob: float) -> list[float]:
    pos = [max(r, 0.0) for r in self.regrets]
    total = sum(pos)
...

10,000번의 반복(2.2초) 후:

King은 99% 확률로 레이즈(raise)함 — 정답, 가장 강력한 핸드
Jack은 혼합 전략(mixed strategy)을 사용함 — 정답, 착취당하지 않기 위해 예측 불가능해야 함

마지막 포인트는 사람들을 놀라게 합니다. GTO는 항상 "옳은" 움직임을 하는 것이 아닙니다. 어떤 상대 전략도 당신을 지속적으로 이길 수 없을 만큼 충분히 예측 불가능해지는 것에 관한 것입니다.

2단계: 몬테카를로 CFR (Monte Carlo CFR)

전체 NLHE(No-Limit Hold'em)는 약 $10^{160}$개의 게임 상태를 가집니다. 매 반복마다 전체 트리를 탐색하는 것은 불가능합니다.

MCCFR은 매 반복마다 하위 집합을 샘플링합니다. 저는 외부 샘플링(external sampling)을 사용했습니다:

Traverser 노드: 모든 (all) 액션을 탐색
Opponent 노드: 상대방의 전략으로부터 하나의 액션을 샘플링 (sample)
결과: 편향되지 않은 가치 추정치 (unbiased value estimates), 다룰 수 있는 수준의 계산량 (tractable computation)

if player == traverser:
    # 모든 액션을 탐색하고, 후회 (regrets)를 업데이트합니다
    for action in actions:
...

Leduc Hold'em 테스트 결과: MCCFR은 일반적인 (vanilla) CFR보다 1.9배 빠른 속도로 동일한 평형 (equilibrium)에 수렴했습니다.

Stage 3: 카드 추상화 (Card Abstraction)

MCCFR을 사용하더라도, 전체 NLHE (No-Limit Hold'em)는 상태 (states)가 너무 많습니다. 해결책은 유사한 핸드들을 버킷 (buckets)으로 그룹화하는 것입니다.

**단순한 접근 방식 (The naive approach)**은 평균 에퀴티 (average equity)를 기준으로 클러스터링을 수행하는데, 이는 중요한 측면에서 잘못된 방식입니다.

플랍에서 플러시 드로우 (flush draw)를 가진 상황과 탑 페어 (top pair)를 가진 상황은 평균 에퀴티는 동일할 수 있지만, 향후 런아웃 (runouts)에 따른 에퀴티 **분포 (distributions)**는 완전히 다를 수 있습니다. 플러시 드로우는 압도적으로 앞서 있거나 혹은 완전히 뒤처져 있습니다. 반면 메이드 핸드 (made hand)는 지속적으로 앞서 있습니다. GTO (Game Theory Optimal) 전략은 이들을 다르게 취급합니다.

올바른 지표: 에퀴티 히스토그램 (equity histograms) 간의 Earth Mover's Distance (EMD).

def emd(hist_a: np.ndarray, hist_b: np.ndarray) -> float:
    """Wasserstein-1 거리 — 평균뿐만 아니라 분포의 형태를 포착합니다."""
    cdf_a = np.cumsum(hist_a)
...

추상화 체계 (Abstraction scheme):

Preflop: 169개의 표준 핸드 (canonical hands) $\rightarrow$ 8개의 에퀴티 백분위 버킷 (equity percentile buckets)
Flop: EMD 클러스터링 $\rightarrow$ 12개 클러스터
Turn: EMD 클러스터링 $\rightarrow$ 12개 클러스터
River: 정확한 강도 백분위 (exact strength percentile) $\rightarrow$ 8개 빈 (bins)

계산량을 절반으로 줄인 최적화: 별도의 몬테카를로 샘플 (Monte Carlo samples)을 실행하는 대신, 동일한 무작위 롤아웃 (random rollouts)으로부터 두 플레이어의 에퀴티 히스토그램을 동시에 계산합니다.

Stage 4: Deep CFR

해시 테이블 (hash table)을 쓰기에는 여전히 정보 집합 (information sets)이 너무 많습니다. Deep CFR (Brown & Sandholm, 2019)은 테이블을 신경망 (neural networks)으로 대체합니다.

플레이어당 두 개의 네트워크:

class AdvantageNetwork(nn.Module):
    """액션당 누적 카운터팩추얼 후회 (cumulative counterfactual regret)를 근사합니다."""
    def regret_matching(self, features):
...

특징 인코딩 (Feature encoding, 373차원):

104: 홀 카드 (hole cards) (2 × 52 원-핫 (one-hot))
260: 보드 카드 (board cards) (5개 슬롯 × 52 원-핫 (one-hot))
4: 스트리트 (street) 원-핫 (one-hot)
5: 정규화된 스칼라 (normalized scalars) (팟 (pot), 스택 (stacks), 콜 금액 (to-call), 레이즈 (raises))

**리저버 버퍼 (Reservoir buffers)**는 모든 과거 반복(iteration)이 학습에 반영되도록 보장하여, 무제한적인 메모리 사용 없이도 파괴적 망각 (catastrophic forgetting)을 방지합니다.

가장 큰 성능 향상 요인: 탐색(traversal) 중에 추론(inference)마다 모드를 전환하는 대신, 네트워크를 eval() 모드로 유지하는 것입니다.

# 이전: 매 추론마다 eval() 호출 ≈ 61ms/탐색
model.eval()
with torch.no_grad():
...

코드 한 줄로 6배의 속도 향상을 이루었습니다. 최적화하기 전에 반드시 프로파일링(profile)을 수행하세요.

5단계: 실시간 탐색 (Real-Time Search)

Deep CFR의 블루프린트 (blueprint) 전략은 많은 정보를 알고 있지만 거친 추상화 (coarse abstractions)를 사용합니다. 실시간 탐색은 이 문제를 해결합니다.

각 결정 지점에서:

현재 상태를 루트로 하는 로컬 게임 트리 (local game tree)를 구축합니다.
해당 서브트리(subtree)에서 정해진 반복 예산(iteration budget) 동안 MCCFR을 실행합니다.
리프 노드 (leaf nodes)에서 블루프린트 (blueprint)에 가치 추정치 (value estimates)를 질의합니다.
탐색을 통해 정교화된 전략을 반환합니다.

def solve(self, gs: GameState, player: int) -> dict:
    self.nodes = {}  # 결정마다 새로운 로컬 트리
    t_start = time.time()
...

**블루프린트 부트스트래핑 (Blueprint bootstrapping)**은 탐색 초기 단계에서 로컬 전략과 블루프린트 전략을 혼합하여 안정성을 높입니다:

blend = min(self._iters / self.config.n_iters, 1.0)
strat = (1 - blend) * blueprint_strat + blend * local_strat

평균 결정 시간: CPU에서 75ms.

결과

300개의 중복 핸드 쌍 (매치업당 총 600개 핸드). 카드 운을 제어하기 위해 중복 점수 산정 방식을 사용했습니다.

매치업 (Matchup)	mBB/hand	유의미함 (Significant)
Blueprint vs Random	+28,403	✅
...

탐색은 블루프린트 전용 플레이보다 일관되게 우수한 성능을 보입니다. 이것이 검증된 Pluribus의 핵심적인 경험적 주장입니다.

Pluribus와의 비교

	본 프로젝트	Pluribus
플레이어 (Players)	2 (헤즈업 (heads-up))	6
...

동일한 아키텍처입니다. 차이점은 규모 (scale)입니다.

내가 다르게 했을 세 가지 사항

1. 더 일찍 프로파일링(Profile)할 것. 평가 모드(eval mode)를 통한 6배의 탐색 속도 향상은 내내 그 자리에 있었습니다. 저는 이것을 발견하기 전까지 알고리즘 최적화에 며칠을 허비했습니다.

2. 더 세밀한 베팅 추상화(bet abstraction)로 시작할 것. 5개의 베팅 사이즈는 기술을 입증하기에는 충분하지만, 실제 전략적 깊이를 구현하기에는 너무 거칩니다(coarse). Pluribus는 14개를 사용했습니다. 전략이 유의미하게 달라집니다.

3. 평가 프레임워크(evaluation framework)를 먼저 구축할 것. 신뢰할 수 있는 착취 가능성(exploitability) 지표를 갖기도 전에 수백 번의 훈련 반복(training iterations)을 수행했습니다. 수렴(Convergence)은 예상과는 다르게 보일 수 있습니다. EV(기댓값)가 0 근처에서 진동하는 것은 Nash 균형으로 수렴하는 것과 같지 않습니다.

코드베이스 (The codebase)

GitHub: github.com/griff-ui/poker-ai

5단계, 40개의 파일, 27개의 테스트 통과, 전체 문서화 완료. MIT 라이선스입니다. 연구, 학습, 또는 여러분만의 솔버(solver)를 위한 기반으로 사용하세요.

라이브 데모: griff-ui.github.io/poker-ai

브라우저 기반의 핸드 분석기(hand analyzer)입니다. 카드를 선택하고 게임 상태를 설정하여 GTO 전략 빈도(frequencies)를 확인하세요. Python은 필요하지 않습니다.

참고 문헌 (References)

Zinkevich et al. (2007) ‚ Regret Minimization in Games with Incomplete Information
Lanctot et al. (2009) ‚ Monte Carlo Sampling for Regret Minimization
Brown & Sandholm (2019) ‚ Deep Counterfactual Regret Minimization
Brown & Sandholm (2019) ‚ Superhuman AI for Multiplayer Poker