CFR

개요

반사실적 후회 최소화(CFR)는 2인 제로섬 게임에서 내쉬 균형을 해결하는 알고리즘입니다. Hart와 Mas-Colell이 제안하고 이후 Zinkevich 등이 게임 이론 포커 연구에 도입했습니다. CFR은 AI 포커의 이정표로, Libratus 및 Pluribus와 같은 최고 포커 AI의 핵심 기술 중 하나입니다. ## 핵심 원리 CFR은 각 결정 노드에서 '반사실적 후회'(플레이어가 실제 행동 대신 대안 행동을 선택했을 때 얻을 수 있었던 추가 페이오프)를 반복적으로 계산합니다. 알고리즘은 축적된 후회 값에 따라 이후 전략을 조정하여 점차 내쉬 균형으로 수렴합니다. 구체적인 과정은 다음과 같습니다.

• 게임 트리의 모든 정보 집합을 탐색합니다.
• 각 행동의 반사실적 가치를 계산합니다(플레이어가 현재 전략으로 해당 정보 집합에 도달한다고 가정).
• 축적된 후회 값을 업데이트하고 이에 따라 새로운 전략을 생성합니다(일반적으로 후회 매칭 사용). ## 텍사스 홀덤에서의 응용 텍사스 홀덤은 전형적인 불완전 정보 게임으로 상태 공간이 거대합니다. CFR과 그 개선 버전(예: CFR+, Deep CFR)은 추상화 기법(상태 클러스터링, 행동 그룹화 등)을 통해 계산 복잡성을 줄이고 대규모 병렬 컴퓨팅으로 훈련합니다. 예를 들어, Libratus는 수정된 CFR 알고리즘을 사용하여 노리미트 텍사스 홀덤에서 최고 인간 플레이어를 이겼습니다. ## 특징
• 이론적 보장: 제로섬 게임에서 CFR은 평균 전략이 내쉬 균형으로 수렴함을 보장합니다.
• 사전 지식 불필요: 균일 무작위 전략에서 시작하여 자동으로 최적 전략을 학습합니다.
• 높은 계산 비용: 노리미트 텍사스 홀덤에서 완전한 게임 트리 탐색은 불가능하며 추상화와 샘플링이 필요합니다. ## 한계 CFR은 주로 2인 제로섬 게임에 적합합니다. 멀티플레이어 게임에서는 이론적으로 수렴이 보장되지 않지만, 수정(예: 전방 탐색을 추가한 Counterfactual Regret Minimization)을 통해 실용적으로 좋은 결과를 얻을 수 있습니다.