search

iciamyplant / Poker_CFR

Understanding Poker rules, Game Theory, and CFR algorithms in order to implement my first CFR solving Rock-Paper-Scissors Game and my first Vanilla CFR solving Kuhn Poker
125 stars 19 forks source link

readme

plan

I - Poker - Informations générales

II - Théorie des jeux

I - Poker - Informations générales

Poker = famille de jeux de cartes

Variantes Modes Formats  Types de jeu Tournois
Le Texas Hold'em Low No limit(montant et relances illimité) cash game = joueur peut quitter la table et échanger ses jetons contre de l'argent World Series of Poker
Omaha High Pot Limit (relance maximale égale à la valeur du pot) tournoi = impossible de convertir ses jetons en argent, on gagne de l’argent en ayant bien classés dans le tournoi, à une place payée World Poker Tour
Le Razz High low Limit tournoi bounty = quand j’élimine un joueur je gagne de l’argent European Poker Tour
Le Stud Half pot limit sit and go Asia Pacific Poker Tour
5 Card Draw, ... Latin American Poker Tour

No limit Texas Hold’em, règles de base :

= se joue avec des cartes et des jetons = jeu de combinaisons à 5 cartes = alterne les étapes de distribution de cartes et les enchères = 52 cartes, réparties en 4 couleurs qui chacune comportent 13 cartes, plus forte carte est l'AS la moins forte est le 2 = 2 à 10 joueurs = heads-up = une partie qui ne confronte que deux joueurs

But : gagner les jetons des autres joueurs, être le dernier joueur avec des jetons

Le board = les 5 cartes qu’on met sur la table Objectif d’avoir la meilleure combinaison de 5 cartes (7 cartes en tout)

Cave = nombre minimum de jetons à avoir pour pouvoir jouer sur une table Croupier = celui qui mélange et distribue les cartes Petite Blinde (SB) et Grosse Blinde (BB) = l’un à côté de l’autre, tourne à chaque main, sont obligés de miser (force à jouer) BB = 2x la SB Joueur au cut off = le dealer précédent Dealer (=donneur) = personne qui distribue les cartes, compte les jetons et s'assure du bon déroulement du jeu à la table, Dealer suit joueur Small Blind et Big Blind avant le SB (tourne a chauqe tour) kicker = carte d'accompagnement, qui fait la difference Buying in = ce qu'on paye pour rentrer en tournoi Bakroll = Cagnotte consacrée au poker, matelas d'argent qu'un joueur professionnel ou amateur gagnant possède, généralement sur un compte disjoint de son compte courant, et dans lequel il puise pour payer ses inscriptions de tournois ou pour se caver en cash-game Tells = indices que révèlent le comportement d’un joueur, attitude, tempo des mises, mimiques, émotions Fish = joueur novice limp = Limper, action qui ne peut se produire qu'avant le flop. Si un joueur décide d'aller voir le flop en investissant le moins d'argent possible alors il paye juste le montant de la big blind stratégie push/fold = réduire votre liste d'options à 2, soit partir à tapis, soit se coucher, avant le flop 78o = 7 et 8 offsuit, pas de même couleur 78s = un sept et un huit de même couleur

Tout le vocabulaire du Poker dictionnaire ici

BB ---- SB ---- BOUTON

1. PREFLOP, enchères tour 1 2. FLOP + enchères tour 2 3. TURN + enchères tour 3 4. RIVER + enchères tour 4 5. SHOWDOWN (= Abbatage)
SB et BB mettent leur jetons Le dealer brûle une carte + 3 cartes retournées (=flop) Le dealer brûle une seconde carte + 1 carte retournée (=le turn) Le dealer brûle une troisième carte + 1 dernière carte retournée (=la river) Les 2 joueurs au moins dévoilent leurs cartes. Soit 1 joueur gagne, soit plusieurs joueurs gagnent et on partage le pot
Personne à gauche de la BB qui parle en premier SB qui commence à parler (ou tout joueur encore en jeu, à la gauche immédiate du dealer) SB qui commence à parler (ou tout joueur encore en jeu, à la gauche immédiate du dealer) SB qui commence à parler (ou tout joueur encore en jeu, à la gauche immédiate du dealer)
options: fold (se coucher), check (=parole, que si a déjà misé assez avant), call (suivre, minimum BB pour entrer ds le coup), raise (miser) idem idem idem
dernier joueur à parler est BB dernier joueur à parler est le dealer dernier joueur à parler est le dealer dernier joueur à parler est le dealer
quand tout le monde est ok --> FLOP quand tout le monde est ok --> TURN quand tout le monde est ok --> RIVER quand tout le monde est ok --> SHOWDOWN BB, SB, D se déplacent d'un cran vers gauche : dealer suivant récupère toutes les cartes, les mélanges, puis effectue une nouvelle distribution des cartes de poker, nouveau coup débute

II - Théorie des jeux

Theory of Games and Economic Behavior, John von Neumann et Oskar Mergenstern, 1944. La théorie des jeux est un domaine des mathématiques fournissant des outils pratiques pour modéliser et raisonner sur des situations interactives (= des jeux). (Définition : La theorie des jeux permet une analyse formelle des problemes posés par l’interaction strategique d’un groupe d’agents rationnels poursuivant des buts qui leur sont propres).

==> Depuis le début des années 1980, la théorie des jeux occupe une place de plus en plus importante en informatique : application dans la théorie des automates, logique, vérification de programmes, optimisation, et apprentissage par renforcement...

1. Classification des jeux

Les situations interactives peuvent avoir une nature très différente en fonction de nombreux facteurs comme le nombre de joueurs, la structure des utilitaires ou l'ordre des coups, etc. Sur la base de ces caractéristiques, nous pouvons classer les jeux en types (tel que les jeux à somme nulle, jeux simultanés, jeux séquentiels, jeux à information complète et information incomplète, etc.)

Classification Définition Exemple 
Jeux à somme nulle (=strictement compétitifs) / Jeux à somme non-nulle jeu à somme nulle = les jeux où l'intérêt de l'un des deux joueurs est strictement opposé à l'intérêt de l'autre joueur. Si les préférences des joueurs sont représentées par une fonction de gain ou une fonction d'utilité, alors la somme des deux fonctions est toujours égale à 0 A somme nulle : pierre-feuille-ciseaux, Poker, échecs. Non-nulle : dilemme du prisonnier (dans certains cas, les deux joueurs peuvent perdre).
Jeux à information complète / Jeux à information incomplète information complète si chaque joueur connaît lors de la prise de décision : ses possibilités d'action ; les possibilités d'action des autres joueurs ; les gains résultants de ces actions ; les motivations des autres joueurs. Perfect-Information Games : échecs, jeu de Go. Imformation incomplète : Poker, Tarot
Jeux à information parfaite / Jeux à information imparfaite
Jeux finis / Jeux non finis On dit qu'un jeu est fini lorsque l'ensemble des stratégies de chacun des joueurs est fini Jeu fini : dilemme du prisonnier est un jeu fini car chacun des joueurs n'a que deux stratégies possibles. Non fini : jeu du duopole de Cournot (chaque entreprise choisit la quantité de bien qu'elle produit dans l'ensemble des réels positifs)
Jeux coopératifs / Jeux non-coopératifs
Jeux à 2 joueurs / Jeux à n joueurs

Notations :

Dans tous les jeux, les décisions peuvent être représentées par un arbre, dont chaque nœud est associé au joueur qui décide. Les gains de tous les joueurs sont associés aux terminaisons (derniers noeuds) de l'arbre. Dans les Imperfect-Information Games = situations dans lesquelles un joueur qui doit prendre une décision ne connaît pas les choix effectués par les joueurs qui ont joué avant lui : il ne connaît pas parfaitement le noeud auquel il se situe. Une fois que nous avons classifié un jeu, nous pouvons commencer à raisonner à son sujet en utilisant des théorèmes génériques connus qui s'appliquent à notre type de jeu.

2. Stratégies Optimales

Stratégie = décrit comment agir dans toutes les situations possibles. Une strategie pure du joueur i est un plan d’action qui prescrit une action de ce joueur pour chaque fois qu’il est susceptible de jouer. On note par Si l’ensemble des stratégies pures du joueur i et par si une stratégie pure de ce joueur.

2.1 : La stratégie de l'elimination des stratégies dominées (EISD)

u v  w
x 3,6 7,1 4,8
y 5,1 8,2 6,1
z 6,0 6,2 3,2

==> Parfois la stratégie dominante de l'un et la stratégie dominante de l'autre amènent à une seule et même réponse ==> Problème majeur de cette méthode: tous les jeux ne sont pas résolvable par EISD

2.2 : L'équilibre de Nash

III - Poker Bots

1. Type de jeu du Heads up NLTH

Heads Up No Limit Texas Hold'em Poker = is an example of two person zero-sum finite game with imperfect information and chance moves

Ce type de jeu implique certains théorèmes ou modèles.

2. Avoir une stratégie au Poker

Dans des jeux comme le poker, les actions choisies via des stratégies ne peuvent pas être entièrement déterministes (Les stratégies doivent être aléatoires, la randomisation est nécessaire, sinon l'adversaire connaît notre modèle de pari). Dans la théorie des jeux, une randomisation des décisions en points de décision est réalisée via des probabilités.

Behavioral Strategy = consiste en une description complète de la façon d'agir via des distributions de probabilités sur les actions aux points de décision. Imaginons pour une main 8/9 au preflop, on peut avoir une distribution de probabilités : 0.15 check, 0.35 bet 5, 0.4 bet 10, 0.05 all-in ... Les probabilités guarantissent la randomization puisqu'à chaque action différente des probabilités différentes, ce qui limite l'exploitabilité.

Behavioral_strategy

3. Nash Equilibrium, la stratégie optimale

Y a t-il une stratégie optimale au Poker ? Selon la théorie des jeux, oui : le profil de stratégie Nash-Equilibrium. Et l'algorithme CFR tente d'en faire une approximation.

Nash Equilibrium = profil de stratégie tel qu'aucun joueur n'a d'incitation à dévier. Equilibre entre les joueurs, point où aucun joueur ne gagne à changer de stratégie. Les deux joueurs jouent un profil de stratégie Nash-Equilibrium si changer sa stratégie pour un joueur n'apporte aucune valeur supplémentaire (en termes d'utilité) lorsque l'autre joueur joue sa stratégie d'origine - les deux joueurs jouent les meilleures réponses l'un à l'autre (c'est le cas en bas à gauche de la figure en dessous).

Exemple : deux marchands de glace, bleu et rouge se partagent la plage. Imagineons que chaque plagiste va au glacier le plus proche.

nash_equilibrium

Est-ce que Nash Equilibrium existe pour le poker ?

Y a-t-il qu'un ou plusieurs NE ?

Si l'on choisi de jouer n'importe quelle stratégie à partir de n'importe quel équilibre de Nash, on est assuré de ne pas perdre. Il est hautement improbable que votre adversaire humain joue la stratégie NE, vous le surpasserez surement car il s'écartera de sa stratégie NE (en bas à droite) et il obtiendra donc un gain inférieur. Or le jeu de poker est un jeu à somme nulle pour deux joueurs, ce qui signifie que nous obtiendrons surement des gains plus élevés.

==> En pratique donc, jouer à Nash Equilibrium permet en principe de gagner (contre des humains sujets aux erreurs) ==> Notre algorithme CFR – produit une approximation du profil de stratégie Nash-Equilibrium

4. Poker Game Tree

Tic-tac-toe game tree (= perfect information game):

tictactoe_game_tree

Kuhn Poker game tree (=imperfect information game):

Poker_game_tree

Le Kuhn Poker est un poker simplifié où seulement 3 cartes différentes sont distribuées (Q,J,K). Pour 2 joueurs, 1 carte est distribuée par joueur (le joueur a soit un K, soit un J, soit un Q). Il n'y a pas de cartes publiques. Celui qui a la carte la plus haute gagne. On ne peut pas re-miser, y a un seul tour.

==> le véritable état du jeu ne peut être observé par aucun des joueurs. Par conséquent, lorsque nous considérons l'arbre de jeu, nous devons séparer l'état réel du jeu de ce que les joueurs observent. Différentes perspectives de l'arbre de jeu :

Perspective d'un joueur = information sets (ensemble d'états de jeux ou nodes qui ne peuvent pas être distingués pour un autre joueur) Les information sets pour les deux joueurs dans tous les points de décision au poker sont différents. Pour le poker, les stratégies comportementales (probabilités sur les actions) sont définies pour des ensembles d'informations, pas pour des états de jeu.

5. Historique

2019 : Pluribus

2017 : Libratus (20 jours d’affrontements dans un casino de Pittsburgh, 120.000 mains jouées au Heads up no-limit Texas Hold'em, a combattu contre 4 joueurs professionnels de Poker (Dong Kim, Jason Les, Jimmy Chou et Daniel McAulay), affrontés en duel dans des parties simultanées, IA crée par 2 chercheurs de Carnegie Mellon University, Brains vs. AI competition, article cité par un des chercheurs Cernegie site)

2015 : AI Claudico

2015 : Cepheus (University of Alberta too)

2017 : DeepStackAI (University of Alberta Computer Poker Research Group leur site)

2007 : Polaris (s'est mesuré à deux joueurs de poker américains de renommée mondiale, Phil Laak et Ali Eslami, lors de la Conférence annuelle sur l'intelligence artificielle en 2007 à Vancouver. Les deux joueurs humains ont gagné de justesse après quatre parties, avec un match nul, une victoire pour le logiciel et deux victoires pour les hommes)

===> Tous les programmes de Poker utilisent une forme de Counterfactual Regret Minimization comme composante principale (Par ex, DeepStack a utilisé un algorithme de type CFR (aidé par des réseaux de neurones) pour la résolution de sous-jeux, la stratégie de Libratus (équilibre de Nash d'une abstraction de jeu) a été calculé avec le Monte Carlo counterfactual regret minimization).

6. Poker en ligne & bots

IV - Rock-Paper-Scissors with CFR algorithm

1. Principe du Counterfactual Regret Minimization

Counterfactual

Regret :

Minimization :

CFR works by repeatedly playing against itself while minimizing regret. CFR minimizes regret over many iterations until the average strategy over all iterations converges. The average strategy is the approximated Nash equilibrium.

2. Fonctionnement du Rock-Paper-Scissors CFR

2 joueurs jouent au pire feuille ciseaux, le gagnant gagne 1 point le perdant perd 1 point, 0 pour égalité

tour N° Actual Reward Counterfactual Reward Regret (counterfactual rewards - real rewards)
1 reward of 0 for both scissors = -1, Paper = 1 Rock : 0-0 = 0, Paper = 1-0 = 1, Scissors = -1-0 = -1
2 our actual reward is -1 Paper = 0, Scissors = 1 Rock =-1-(-1)=0, Paper = 0-(-1)= 1+1 = 2, Scissors = 1-(-1)-1 = 2-1 = 1

==> on additionne tous les regrets à chaque itération. Donc le tour N°2, Scissors = 1-(-1) = 2 -1 (notre ancien regret) = 1. Et à un moment on se retrouve avec ça :

Rock Paper Scissors
100 50 50

==> Ici on regrette de na pas avoir pris Rock plus souvent. Comment minimiser ce regret ? On va normaliser ces valeurs, ou les transformer en pourcentage. Donc on additionne tous nos regrêt et on divise chaque regret par ce nombre.

100+50+50 = 200.

Rock Paper Scissors
100/200 = 50% 50/200 = 25% 50/200 = 25%

==> Maintenant lorsqu'on prend nos décisions pour le prochain jeu, on va choisir la Pierre 50% du temps, le papier 25% et les ciseaux 25% aussi. En choisissant la pierre plus souvent, on va minimiser le regret qu'on ressent.

Pour trouver la stratégie optimale Nash Equilibrium, on va entraîner deux algorithmes CFR à jouer l'un contre l'autre, jusqu'à ce qu'ils trouvent la stratégie optimale. Pour un jeu comme le rock-paper-scissors, ça va prendre environ 10k itérations. La stratégie optimale au Rock-Paper-Scissors est 1/3 pour chaque, 33,33333% pour rock, pour paper, et pour scissors.

implementation at  /Rock-Paper-Scissors/my_first_cfr_rockpaperscissors.py

V - Kuhn Poker with Vanilla CFR algorithm

1. Rappel des règles du Kuhn Poker

Kuhn_pokergametree

2. Fonctionnement du Kuhn Poker CFR

Principe :

Imaginons :

exemple_regret_kuhnpoker

Player 1 au deuxième noeud bleu, sachant que P1 a un roi et P2 a un valet :

kuhnpoker

Player 1 au premier noeud bleu, sachant que P1 a un roi et P2 a un valet :

==> nous commencons à converger vers une stratégie optimale. Si on reçoit à nouveau le roi, on est + susceptible de parier. Et si on arrive au deuxième noeuf bleu, on ne décidera pas de pass à nouveau.

Nous allons :

Rewards :

treekuhnpoker

==> Même dans un simple Kuh Poker, on va voir des vraies stratégies de Poker émerger. Par exemple avec le Jack bet 20% : c'est du bluff. Donc le bot apprend à bluffer. Avec le King pass 25%, on a la meilleure main mais on essaye d'induire que non, on attend que l'adversaire mise.

3. Vanilla CFR

implementation at  /Kuhn-Poker/first_vanilla_cfr_kuhnpoker.py

Player 1 Stratégies sur 25k itérations :

Carte - Historique Pass  Bet
O (=jack, noeud tout en haut) 0.75 0.25
0 pb (=jack, noeud noeud après que J1 a pass et J2 a bet) 1.00 (normal, si j'ai un jack il faut passer là) 0.00 (et surtout pas bet si sachant que j'ai la pire carte)
1 (=queen, pas d'historique noeud du haut) 0.98 0.02
1 pb (=queen, J1 a pass J2 a bet) 0.40 0.60
2 (=king) 0.23 0.77
2 pb 0.00 1.00
Player 2 Stratégies sur 25 itérations : Carte - Historique Pass  Bet
O b (=jack, J1 a bet) 1.00 0.00
0 p (=jack, J1 a pass) 0.67 0.33
1 b (=queen, J1 a bet) 0.63 0.37
1 p 1.00 0.00
2 p 0.00 1.00
2 b 0.00 1.00

VI - Lancer l'algo dans Microsoft Azure

Azure Machine Learning est une plateforme pour l’exploitation des charges de travail Machine Learning dans le cloud.

1. Créer un espace de travail (=Workspace)

Espace de travail = un contexte pour les expériences, les données, les cibles de calcul et les autres ressources associées à une charge de travail Machine Learning.

Il est possible de créer l'espace de travail de différentes manières : directement dans le portail en ligne, ou avec le SDK Microsoft Azure par exemple. Toute la documentation est disponible ici

Installer le SDK Azure Machine Learning :

pip install azureml-core

Pour créer son espace de travail avec le SDK :

    from azureml.core import Workspace

    ws = Workspace.create(name='aml-workspace', 
                      subscription_id='123456-abc-123...',
                      resource_group='aml-resources',
                      create_resource_group=True,
                      location='eastus'
                     )

Personnellement je l'ai créé sur le portail en ligne, et ensuite je m'y suis connectée :

#connect to my workspace
ws = Workspace(subscription_id="18d9c045-5366-44ac-83f3-a68cb44782c5",
               resource_group="groupe-ressources",
               workspace_name="Poker-YouTubeVideo")

==> Une fois créé, on a accès à Azure Machine Learning Studio. Toggle the ☰ icon at the top left to show and hide the various pages in the interface. You can use these pages to manage the resources in your workspace.

2. Uploader ses données, nettoyer etc

Moi j’ai pas de données, puisque le modèle s'entraîne en jouant contre lui-même.

3. Créer une instance de calcul

En gros les instances de calcul c'est la puissance de calcul qui permet de faire tourner mon modèle. Azure Machine Learning permet de créer des instances de calcul dans un espace de travail afin de fournir un environnement de développement géré avec toutes les autres ressources de l’espace de travail.

Vous pouvez choisir une image d’instance de calcul qui fournit la spécification de calcul dont vous avez besoin, que ce soit de petites machines virtuelles avec CPU uniquement ou de grandes stations de travail compatibles GPU. Étant donné que les instances de calcul sont hébergées dans Azure, vous payez uniquement les ressources de calcul lorsqu’elles sont en cours d’exécution ; ainsi, vous pouvez créer une instance de calcul adaptée à vos besoins et l’arrêter quand votre charge de travail est terminée pour réduire les coûts.

Toute la documentation est disponible ici

Pour créer une instance de calcul :

4. Créer une expérience + la configuration d’exécution du script + soumettre l'experience

Une expérience peut être exécutée plusieurs fois, avec des données, du code ou des paramètres différents. Azure Machine Learning effectue le suivi de chaque exécution, ce qui vous permet de voir l’historique des exécutions et de comparer les résultats de chaque exécution. Toute la documentation est disponible ici

#creer une experiment
experiment_name = 'my_experiment'
experiment = Experiment(workspace=ws, name=experiment_name)

Ensuite, on va créer la configuration d’exécution du script qu'on veut run. Maintenant que vous avez une cible de calcul (my_compute_target par exemple) et un environnement (myenv, voir Créer un environnement), créez une configuration d’exécution de script qui exécute votre script de formation (train.py) dans votre répertoire project_folder :

src = ScriptRunConfig(source_directory=project_folder,
                      script='train.py',
                      compute_target=my_compute_target,
                      environment=myenv)

# Set compute target
# Skip this if you are running on your local computer
script_run_config.run_config.target = my_compute_target

Mon code :

myenv = Environment.get(workspace=ws, name="AzureML-Minimal") #je précise c'est quoi mon env

myscript = ScriptRunConfig(source_directory = './Kuhn-Poker',script ='first_vanilla_cfr_kuhnpoker.py',
compute_target = 'compute-poker', environment = myenv) #configuration d'éxecution du script

Et enfin on soumet l'expérience :

run = experiment.submit(config=src)
run.wait_for_completion(show_output=True)

5. Autres ressources Microsoft Azure intéressantes :

VII - The Monte Carlo Counterfactual Regret Minimization algorithm

1. Concept principal du CFR = le regret

Le concept de regret est central dans les problèmes de prise de décision répétée dans un environnement incertain (= on appelle ça online learning)

Exemple :

Avec le vecteur de perte lt + la distribution de confiance pt, on peut calculer la perte attendue ltH : *ltH = somme pour chaque i de N de pti lti**

En considérant toute la temporalité T on peut calculer la perte totale attendue de notre algorithme LTH = somme pour chaque t de T de ltH

Et on peut calculer la perte totale pour un seule expert i : Lti = somme pour chaque t de T de lti

Le regret au temps t = la différence entre la perte totale de notre algorithme (LtH) et la meilleure perte unique (Lti) d'expert (= l'expert qui a donné les meilleurs conseils). Le regret peut être exprimé par la réflexion suivante : Si seulement j'avais écouté l'expert i tout le temps, la perte totale serait la plus faible.

R = LTH - minLTi

2. No regret learning et l'exemple du Regret Matching

Un online algorithm (algorithms that build predictive models by processing data one at the time) apprend sans regret si quand T tend vers l'infini, la moyenne de son regret tend vers 0 au pire des cas (sinon vers + que 0). ==> dans ce cas, ça veut dire qu'aucun expert n'est meilleur que notre algorithme H. Il n'y a regret envers aucun expert.

Regret Matching = algorithme d'apprentissage sans regret qui emprunte sa logique de mise à jour au Polynomially Weighted Average Forecaster (PWA)

==> Pour résumer, le principe est là d'observer tous nos experts et garder des statistiques sur leurs performances au fil du temps : notamment via les regrets cumulés positifs pour chacun des experts. Ce regret exprime combien nous gagnerions si nous abandonnions notre schéma de distribution de « confiance » actuel et que nous écoutions simplement un seul expert tout le temps.

3. No Regret Learning & Théorie des jeux

Exemple : 2 joueurs jouent à pierre feuille ciseaux de manière répétitive. Du point de vue du joueur A :

==> Si on intègre un algorithme H qui reprend comment le joueur A apprend à distribuer sa confiance aux experts, on retombe sur quelque chose de semblable à ce qui a été vu plus haut, sauf qu'à la place des pertes, on reçoit des récompenses.

regret moyen = regret cumulatif divisé par les pas de temps (nombre de répétitions du jeu) stratégie moyenne = moyenne des stratégies comportementales utilisées à chaque pas de temps

rewards

4. Le regret global moyen

5. Idée générale du MCCFR

information set game state
La perspective d'un joueur. C'est un set de game states. Par exemple dans l'image Kuhn Poker game tree le joueur en bleu a 2 information sets ou les lignes en pointillés rejoignent les deux informations sets (ensemble d'états de jeux ou nodes qui ne peuvent pas être distingués pour un autre joueur) Les information sets pour les deux joueurs dans tous les points de décision au poker sont différents. Chaque noeud est un game state

le CFR est une procédure Regret Matching appliquée pour optimiser ce qu'on appelle le regret contrefactuel immédiat qui, lorsqu'il est minimisé dans chaque information set, est une limite supérieure du regret global moyen. Le regret contrefactuel immédiat est garanti de tendre vers 0 si la procédure de Regret Matching est appliquée.

C'est à dire que le regret global moyen peut être minimisé via un CFR. Minimiser le regret moyen global pour les deux joueurs conduit à l'équilibre de Nash. Or l'équilibre de Nash est la stratégie optimale au Heads up NLTH.

Le CFR se définit par la Counterfactual utility et le Immediate Counterfactual Regret.

6. La Counterfactual utility

On a parlé précédemment des utilités attendues = c'est-à-dire la récompense attendue en choisisant tel chemin. On a dit que c'était un moyen pratique d'évaluer les stratégies des joueurs.

La Counterfactual utility = une autre métrique d'évaluation des stratégies des joueurs. Cette fois, notre métrique est définie pour chaque information set séparément.

imaginez que vous êtes à un point de décision particulier dans le heads up NLTH. Vous ne savez pas quelles cartes votre adversaire détient. Supposons un instant que vous ayez décidé de deviner que la main de votre adversaire était une paire d'as. Cela signifie que vous n'êtes plus dans l'information set parce que vous vous mettez simplement dans un état de jeu spécifique (en supposant la main d'un adversaire particulier). Cela signifie que vous pouvez calculer l'utilité attendue pour un sous-jeu enraciné dans l'état de jeu que vous avez supposé. Cet utilité serait simplement :

counterfactual utility

Si nous faisons ce calcul pour chaque game state possible dans notre information set (chaque main possible que peut avoir l'adversaire), nous nous retrouverons avec un vecteur d'utilités, une pour chaque main que peut avoir l'adversaire. Si nous pondérons maintenant ces utilités en fonction des probabilités d'atteindre le game state correspondant et que nous les additionnons, nous finirons par avoir l'utilité attendue régulière.

Pour obtenir une utilité contrefactuelle, nous devons utiliser un autre schéma de pondération. Pour chaque main de l'adversaire (game state h), utilisons la probabilité d'atteindre h en supposant que nous voulions atteindre h. Ainsi, au lieu d'utiliser notre stratégie habituelle à partir du profil de stratégie, nous la modifions un peu afin qu'elle essaie toujours d'atteindre notre état de jeu actuel h - ce qui signifie que pour chaque ensemble d'informations avant l'état de jeu actuellement supposé, nous prétendons que nous avons toujours joué une stratégie comportementale pure où l'ensemble la masse de probabilité a été placée dans l'action qui a été réellement jouée et a conduit à l'état actuel supposé h - qui est en fait contrefactuel, en opposition aux faits, car nous avons vraiment joué selon σ. En pratique, nous considérons simplement la contribution de notre adversaire à la probabilité d'atteindre l'état de jeu actuellement supposé h. Ces poids (appelons-les probabilités de portée contrefactuelles) expriment l'intuition suivante : "quelle est la probabilité que mon adversaire arrive ici en supposant que j'ai toujours joué pour arriver ici ?"

La Counterfactual utility est ensuite la somme pondérée des utilités pour les sous-jeux (chacun enraciné dans un seul état de jeu) à partir de l'ensemble d'informations actuel, les pondérations étant les probabilités contrefactuelles normalisées d'atteindre ces états.

7. Le Immediate Counterfactual Regret

VIII - Ressources

1. Pour comprendre l'algorithme CFR

2. Autour de la théorie des jeux

3. Pour coder un Vanilla CFR

4. Autour du Monte Carlo CFR & des IA qui ont battu des pros du Poker

5. Autres ressources intéressants sur le sujet

6. Lancer Deepstack pour le Leduc Poker sur son ordi