CFR

Visão Geral

A Minimização de Arrependimento Contrafactual (CFR) é um algoritmo para resolver equilíbrio de Nash em jogos de soma zero para dois jogadores. Foi proposta por Hart e Mas-Colell e posteriormente introduzida na pesquisa de pôquer da teoria dos jogos por Zinkevich et al. CFR é um marco no pôquer de IA e é uma das principais tecnologias dos principais AIs de pôquer, como Libratus e Pluribus. ## Princípio Central O CFR calcula iterativamente o "arrependimento contrafactual" em cada nó de decisão — o ganho adicional que um jogador poderia ter obtido ao escolher uma ação alternativa em vez da ação real. O algoritmo ajusta as estratégias subsequentes com base nos valores de arrependimento acumulados, convergindo gradualmente para um equilíbrio de Nash. O processo específico inclui:

• Percorrer todos os conjuntos de informações na árvore do jogo.
• Calcular o valor contrafactual de cada ação (assumindo que o jogador atinge aquele conjunto de informações com a estratégia atual).
• Atualizar os valores de arrependimento acumulados e gerar uma nova estratégia de acordo (tipicamente usando regret matching). ## Aplicação no Texas Hold'em O Texas Hold'em é um jogo típico de informação imperfeita com um enorme espaço de estados. O CFR e suas versões melhoradas (por exemplo, CFR+, Deep CFR) reduzem a complexidade computacional por meio de técnicas de abstração (como agrupamento de estados, agrupamento de ações) e depois treinam com computação paralela em larga escala. Por exemplo, o Libratus usou um algoritmo CFR modificado para derrotar jogadores humanos de elite no Texas Hold'em sem limite. ## Características
• Garantia teórica: Em jogos de soma zero, o CFR garante que a estratégia média converge para um equilíbrio de Nash.
• Nenhum conhecimento prévio necessário: Começando de uma estratégia aleatória uniforme, ele aprende automaticamente a estratégia ótima.
• Alto custo computacional: Percorrer a árvore completa do jogo é inviável no Texas Hold'em sem limite e requer abstração e amostragem. ## Limitações O CFR é adequado principalmente para jogos de soma zero para dois jogadores. Em jogos multijogador, a convergência não é teoricamente garantida, mas modificações (como a Minimização de Arrependimento Contrafactual com busca para frente) podem alcançar bons resultados na prática.