반사실적 후회

개요 반사실적 후회(CFR)는 게임 이론과 인공지능 분야의 중요한 개념입니다. 2008년 Martin Zinkevich 등이 제안했으며, 불완전 정보 게임에서의 전략 최적화 문제를 해결하는 데 사용됩니다. 텍사스 홀덤과 같은 게임에서 CFR은 후회 최소화 알고리즘의 핵심 구성 요소이며, Libratus 및 Pluribus와 같은 고급 AI를 구축하는 데 널리 사용되었습니다. ## 원리 반사실적 후회는 특정 정보 집합(플레이어가 현재 알고 있는 모든 정보)에서 실제로 취한 행동 대신 다른 행동을 선택했다면 얻었을 보상의 차이를 측정합니다. 구체적으로, 각 정보 집합과 각 가능한 행동에 대해 해당 행동의 "반사실적 후회 값"을 계산합니다: 플레이어가 다른 모든 결정 지점에서는 현재 전략을 따르고 이 노드에서만 행동을 변경한다고 가정할 때, 후회 값은 새 행동의 기대 보상에서 현재 전략의 기대 보상을 뺀 값과 같습니다. 각 라운드가 끝난 후, 알고리즘은 실제 결과에 따라 각 정보 집합의 행동에 대한 후회 값을 업데이트합니다. 반복 횟수가 증가함에 따라 후회가 누적되어 전략 조정에 사용됩니다: 후회가 낮은(즉 덜 후회하는) 행동에는 더 높은 확률이 할당됩니다. 결국 모든 정보 집합에서 평균 후회가 0에 가까워지면 전략은 내시 균형에 수렴합니다. ## 텍사스 홀덤에서의 응용 CFR은 숨겨진 정보, 무작위성, 다중 라운드 의사 결정을 포함하는 텍사스 홀덤과 같은 게임에 특히 적합합니다. 전체 게임 트리가 너무 크기 때문에 실제 응용에서는 추상화 기법(상태 클러스터링 및 행동 추상화 등)을 사용하여 복잡성을 줄입니다. 수조 번의 자가 대결 시뮬레이션을 통해 CFR은 거의 최적의 전략을 생성할 수 있으며, 헤즈업 노 리미트 텍사스 홀덤에서 최고의 인간 플레이어를 이겼습니다. ## 관련 용어와의 관계 - 후회 최소화 (RM): CFR은 RM을 다중 플레이어, 불완전 정보 시나리오로 확장한 것으로, 동일한 핵심 아이디어를 공유합니다.

• 내시 균형: CFR의 목표는 혼합 전략 내시 균형을 찾는 것으로, 어떤 플레이어도 일방적으로 전략을 변경하여 이익을 얻을 수 없습니다.
• 전략 반복: CFR은 반복적인 반복을 통해 전략을 업데이트하며, 전통적인 가치 반복 또는 정책 경사 방법과 다릅니다.