Jump to content
This Topic
taamer

Game Theory Optimal : état de l'art en 2016

Recommended Posts

Thread 2016 autour de l'état de l'art des mathématiques et de l'intelligence artificielle, appliqués au poker.

GTO :  adjectif, acronyme signifiant Optimal selon la Théorie des Jeux (Game Theory Optimal).

GTO est devenu une expression à la mode au poker. L'idée principale de l'analyse GTO est de considérer que le No-Limit Texas Hold'em peut être traité et résolu comme un problème de mathématiques. Quelque part dans le Monde Fabuleux des Mathématiques, il y a une Stratégie Optimale, pour le No-Limit Texas Hold'em. Le Saint-Graal des tapis verts. Cette stratégie garantit que vous jouerez de manière inexploitable et que vous exploiterez de manière automatique tout adversaire qui s'écartera lui-même de la Stratégie Optimale. Tels des oncles Picsou, les $€$€$ brillent déjà dans vos yeux.

Courte histoire des résolutions optimales de divers jeux de poker

Oui mais voilà, savoir qu'une solution GTO existe, c'est bien; la connaître afin de pouvoir l'appliquer serait mieux. Il faut donc commencer par la trouver - soit avoir la chance de tomber dessus par hasard et de se rendre compte qu'on ne peut pas faire mieux, soit la déterminer par tâtonnements. Pour prendre la mesure de la complexité du problème, des versions de jeux de poker simplifiés ont été inventés, puis résolus. Quelques exemples ci-dessous de jeux à deux joueurs (A parle en premier, B en dernier) :

- Le jeu clairvoyant : Le pot constitué avant la donne est de 1. A possède une carte parmi les deux du paquet, l'une indique "nuts" et l'autre indique "bluff". B n'a pas de carte. A peut checker (showdown) ou miser en no-limit, B peut payer (showdown : A avait-il les nuts ou bien avait-il un bluff?) ou passer (abandonnant le pot de 1 qui revient à A). Ce jeu a permis de déterminer les ratios optimaux des ranges polarisés.

- Le Kuhn poker (1950) : Le pot constitué avant la donne est de 1. A et B reçoivent chacun une carte d'un paquet qui en contient trois : Roi, Dame ou Valet. Le Roi gagne tout le temps, le Valet perd tout le temps. Ce jeu est une extension du jeu clairvoyant et équilibre les ranges de value et de bluff de A.

- Le Leduc hold'em poker : Le pot constitué avant la donne est de 1. A et B reçoivent chacun une carte d'un paquet qui en contient six : deux Rois, deux Dames ou deux Valets. Un premier tour de mise (relance possible), puis une carte commune est distribuée ouverte, puis un second tour de mise (relance possible) a lieu. Ce jeu permet d'intégrer les concepts de relance en no-limit, de board dynamique et de bloqueur.

- Le Texas hold'em poker en limit : ce jeu est le plus complexe qui soit désormais résolu (2015) par la force brute du calcul. L'arbre des possibilités, incluant toutes les mises possibles (quatre tours de mise, chaque tour pouvant atteindre un cap de quatre mises), toutes les combinaisons de cartes privatives pour les deux joueurs, tous les flops, turns, rivers, représentent un nombre de paramètres en O(10¹⁸), c'est à dire que le nombre de paramètres dépasse le milliard de milliards. Pour résoudre en pratique cet arbre de possibilités, il faut une puissance de calcul de 200 ordinateurs avec un peu de CPU/RAM, proc AMD 2,1GHz et 64Go de RAM (dont 25Go de RAM étaient utilisés en pratique par le programme). Le calcul est orchestré par une machine, qui distribue aux 199 autres un morceau de l'arbre. Outre ce supercalculateur, réaliser le calcul complet a pris un peu de temps.

Le Texas Hold'em, heads-up, no-limit, est encore très loin d'être résolu.

L'ordre de grandeur du nombre de paramètres pour résoudre l'arbre complet d'un jeu de HUNL est de ... O(10¹⁶⁵). 10¹⁶⁵ est un nombre si grand... même en comptant le nombre de périodes de temps infinitésimal de Planck depuis le Big Bang (10⁶⁰), même notre estimation actuelle du nombre d'atomes dans l'univers (10⁸⁰), même le gogol cher à Google (10¹⁰⁰), même le nombre de Shannon, qui estime le nombre de parties d'échecs différentes (10¹²⁰), sont bien plus petits.

Hypothèses de simplification et outils associés

Pour résoudre une situation du jeu, on a plusieurs manières de simplifier les calculs.

a) Réduire les possibilités de mises : le jeu push-or-fold est résolu (HU, tapis de moins de 20 blindes), mais il est imparfait car d'autres options stratégiques existent. Le potache ROFL, acronyme stratégique signifiant Raise, Open, Fold, Limp, est déjà loin d'être résolu; en outre on peut imaginer ouvrir parmi différents montants (2x; 2,2x; 2,5x; 3x etc.) ce qui ajoute à la complexité de la résolution. Des outils spécialisés (notamment sur HUsng.com) permettent de créer des ranges et des actions prédéfinies, mais cela ne permet pour l'instant que de tester la robustesse d'une stratégie préflop en HU; l'arbre des flops et les mises subséquentes ne sont pas considérés.

b) Focaliser la résolution sur une partie de l'arbre - board partiel :Js:5s:2h:Qc et lister les rivers possibles - complété par un éventail de ranges pour Hero et Vilain, dépendant d'une évaluation selon l'historique de jeu et d'actions de l'adversaire. C'est le travail classique des joueurs de poker - les plus forts dans ce domaine sont les joueurs de cash-game online; le jeu en tournoi est plus simple car souvent moins deep, ce qui modifie drastiquement les ranges d'attaque et de défense.

c) Certains outils vendent l'idée de résoudre mathématiquement certaines situations (mais c'est bien un concept marketing, et non mathématique). GTORB (Range Builder), Simple PostFlop, PIOsolver etc. sont des outils pouvant résoudre çà-et-là quelques situations. D'un point de vue de résolution mathématique du jeu dans son ensemble, ces outils sont inutiles pour la recherche de la solution générale. Pour le grinder qui a de l'expérience et qui analyse les situations de jeu qu'il rencontre, ces outils sont intéressants.

Comment jouent les ordinateurs au poker?

Depuis plusieurs années, un championnat des ordinateurs est organisé une fois par an. Tous appliquent une stratégie - écrite par leurs concepteurs, humains - et se confrontent les uns aux autres dans des matchs. Ces ordinateurs sont très loin d'un jeu estampillé GTO, mais il abordent de nombreuses problématiques de modélisation qui font progresser notre connaissance du jeu.

L'un des premiers vainqueurs du tournoi des ordinateurs, HyperBorean, avait gagné en appliquant une stratégie qui ne tenait presque pas compte de ses cartes, mais qui était centrée sur l'exploitation des faiblesses stratégiques de ses adversaires, qui eux-mêmes étaient incapables de s'adapter à son jeu d'exploitation. Exemple : l'adversaire d'HyperBorean faisait un probe bet, HyperBorean réalisait systématiquement une grosse relance qui allait être traitée par un fold dans la plupart des cas.

Depuis, les stratégies ont bien progressé. Les stratégies sont toujours un compromis entre la simplification - recherche de regroupement des mains de mêmes force, compréhension des différences temporelles ou positionnelles, adaptations de la stratégie aux cas non prévus (votre stratégie prévoit que vous savez quoi faire face à un open à 2x et à 3x, mais que faites-vous si l'adversaire ouvre à 2,3x ou à 2,6x?!). En outre, les ordinateurs se battent aujourd'hui pour réaliser un jeu d'exploitation des faiblesses adverses - vouloir bien jouer en GTO n'exclut pas de maximiser ses gains en déviant après avoir identifié un gros leak.

Conclusion du moment

L'analyse GTO des jeux de poker a encore beaucoup de chemin à parcourir. En théorie, elle se concentre essentiellement sur le jeu en heads-up; en pratique le travail sur les ranges permet d'appliquer les mêmes principes à d'autres distributions, par exemple à celles du 6-max, ventilées par position à la table. Les mathématiciens publient articles, abstract et thèses complètes, les informaticiens éditent des logiciels d'aide à la décision pour les joueurs de poker, les joueurs de poker publient des vidéos de coaching et des résultats partiels accessibles à la communauté utilisant telle ou telle plate-forme de résolution GTO.

 

Merci d'avoir lu jusque-là. Au plaisir d'ouvrir la discussion sur les thèses de Computer Science qui ont le poker comme sujet principal.

Share this post


Link to post
Share on other sites

L'ordre de grandeur de l'arbre du  HU Limit est de O(1018 ) si on prend des sequences de bet limitées à 4 bet pour chaque joueur par tour d'enchères.

Cet ordre de grandeur est obtenu sans faire d'abstraction ou simplification

Comment obtient on cet ordre de grandeur O(10165) pour l'arbre du HU NL, cad comment denombre t on les sequences de bet?

Share this post


Link to post
Share on other sites

Comment obtient on cet ordre de grandeur O(10

165

) pour l'arbre du HU NL, cad comment denombre t on les sequences de bet?

C'est détaillé dans les publications de l'Université d'Alberta (Canada), qui est l'hôte des championnats de poker des programmes. Le résultat obtenu est calculé pour un jeu NLHE HU 200bb deep. Ici : http://poker.cs.ualberta.ca/publications/2013-techreport-nl-size.pdf

Bien entendu, la première tâche pour résoudre un jeu complexe est de simplifier le jeu afin de réduire l'arbre - par groupements d'états / d'actions - résoudre l'arbre simplifié, puis dérouler la solution appliquée à l'arbre complet.

Share this post


Link to post
Share on other sites

"Cette stratégie garantit que vous jouerez de manière inexploitable et que vous exploiterez de manière automatique tout adversaire qui s'écartera lui-même de la Stratégie Optimale. Tels des oncles Picsou, les $€$€$ brillent déjà dans vos yeux."

 

Pas d'accord avec ca. On est en GTO quand ni A ni B ne peut augmenter son EV. Si B s'ecarte du jeu GTO, il devient ainsi exploitable, et on perd de l'EV en continuant a jouer GTO sans l'exploiter.

 

Example avec un fish qui ne c/r x3 river que les nuts, le GTO peut nous dicter de call 30% de notre range river pour ne pas etre exploitable, sauf que caller 30% vs ce fish nous coute enormement d'EV au final.

 

Share this post


Link to post
Share on other sites

Pas d'accord avec ca. On est en GTO quand ni A ni B ne peut augmenter son EV. Si B s'ecarte du jeu GTO, il devient ainsi exploitable, et on perd de l'EV en continuant a jouer GTO sans l'exploiter.


 

D'accord sur l'imprécision du vocabulaire, remplace "exploite automatiquement" par "gagne de l'argent automatiquement". La stratégie GTO gagne automatiquement de l'argent lorsque l'adversaire s'écarte de l'équilibre. Ou : Lorsque les deux joueurs jouent GTO, ils empêchent mutuellement l'autre joueur de gagner plus.

Ton exemple est bidon. Si Fish n'a pas de range de c/r en bluff, c'est lui qui sacrifie de l'EV. Et si tu ne peux pas call le top de ton range face au c/r déséquilibré de Fish, c'est que ton range de mise n'était pas GTO 8|

Share this post


Link to post
Share on other sites

Je n'ai pas dit que fish n'a pas de c/r en bluff, seulement qu'un c/r x4 etait seulement avec les nuts.

 

En GTO, tu auras toujours une range de call pour chacun de ses c/r, et donc son x4, sinon tu overfold et vilain peut t'exploiter en c/r x4 tout le temps. Contre le fish, si tu sais que son x4 n'est que les nuts, alors tu a interet a devier du jeu GTO et faire un fold exploitant car il ne va pas exploiter le fait que tu fold X % de ta range > Y% de ta range dictee par le GTO

Share this post


Link to post
Share on other sites

Je n'ai pas dit que fish n'a pas de c/r en bluff, seulement qu'un c/r x4 etait seulement avec les nuts.

 

En GTO, tu auras toujours une range de call pour chacun de ses c/r, et donc son x4, sinon tu overfold et vilain peut t'exploiter en c/r x4 tout le temps. Contre le fish, si tu sais que son x4 n'est que les nuts, alors tu a interet a devier du jeu GTO et faire un fold exploitant car il ne va pas exploiter le fait que tu fold X % de ta range > Y% de ta range dictee par le GTO

Je le répète, ton exemple est bidon car il veut illustrer qu'une stratégie GTO (savoir quand tu mises, quand tu b/f et quand tu b/c) est exploitable par une, voire par deux stratégies déséquilibrées - celui qui te c/r 4x tout le temps et celui qui te c/r 4x en value seulement. Or, par définition de la stratégie optimale, l'adversaire ne peut pas inventer de stratégie qui améliore les chances de Vilain face à la stratégie optimale.

Je parle GTO et tu parles de stratégie exploitante (et elle-même exploitable). Que, si Vilain le permet, Hero puisse exploiter plus pour gagner plus existe, tu en parleras mieux que moi dans la section stratégie. Cette discussion est hors-sujet dans ce thread.

 

Share this post


Link to post
Share on other sites

Je ne te dis pas que y'a une strategie qui peut exploiter le jeu GTO, je dis juste que quand on a l'occasion d'exploiter, alors mieux vaut exploiter (cela implique etre exploitable aussi du coup).

Share this post


Link to post
Share on other sites

Merci pour le thread, cela m'a toujours étonné qu'il n'y ait pas plus de discussions et d'informations concernant l'avancée des travaux universitaires. C'est un peu comme si d'un coté il y avait les joueurs de poker, qui sont dans le coté pratique des choses, et d'un autre coté les chercheurs en théorie des jeux, qui travaillent sur le poker d'un point de vue purement théorique. Et bizarrement les joueurs de poker parlent toute la journée de GTO, de jeu exploitant, d'erreurs, de technique, sans jamais aller voir ce que font les chercheurs alors que ces chercheurs sont parfois LARGEMENT plus avancés sur le coté technique.

 

Il a fallu attendre 2015 pour qu'on ait le premier gros match Homme vs Machine en HUNL alors que ça fait pas mal d'années que les chercheurs organisent entre eux des compétitions de bots au poker.

Share this post


Link to post
Share on other sites

Un papier qui a l'air intéressant publié dans International Game Theory Review vient de sortir. Pas encore récupéré le PDF mais je vais essayer.

http://www.narcis.nl/publication/RecordID/oai:tilburguniversity.edu:publications%2F0d8f6872-6d0e-42d0-9339-d075e1fe656f

L'abstract : 

Citation

The methodology of relative skill, by means of a detailed mathematical analysis of realistic approximations of Texas Hold’em cash games and tournaments as provided in van der Genugten and Borm [2012], and Borm and van der Genugten [2009] respectively, reconfirms the findings of the court in The Hague (cf. [Rechtbank Gravenhage [2011]) that Texas Hold’em in all its practical variants is a game of skill.

 

Share this post


Link to post
Share on other sites
Il y a 2 heures, Pad a écrit :

Un papier qui a l'air intéressant publié dans International Game Theory Review vient de sortir. Pas encore récupéré le PDF mais je vais essayer.

http://www.narcis.nl/publication/RecordID/oai:tilburguniversity.edu:publications%2F0d8f6872-6d0e-42d0-9339-d075e1fe656f

L'abstract : 

 

DOI

https://fr.wikipedia.org/wiki/Sci-Hub

Il y est

Share this post


Link to post
Share on other sites

En effet thx ! J'ai jeté un oeil sur Sci-Hub tout à l'heure mais le site paraissait down. Je viens de me rendre compte qu'en réalité c'est probablement que ma fac l'a blacklisté puisqu'en 3G le site fonctionne parfaitement xD

Share this post


Link to post
Share on other sites
il y a 50 minutes, BV-77 a écrit :

je n'arrive pas à récuperer le pdf, qqn sait pourquoi ?

 

il y a 48 minutes, Pechcore a écrit :

Pareil, je me suis inscrit mais je crois qu'il faut lacher 30e pour y accèder.

Lisez le mode d'emploi ci-dessous pour accéder gratuitement au document.

 

 

 

Share this post


Link to post
Share on other sites

Simple Postflop viennent d'annoncer que leur solver preflop gère désormais "any number of players". Je serais curieux de voir si les premières solutions ressemblent ou non aux ranges proposées par snowie en CG 6 max.

Share this post


Link to post
Share on other sites

J'ai regardé les prix de SPF, je suis étonné de les voir tellement plus intéressants par rapport à l'offre Pio. Tu a un solver preflop pour le tier du prix et qui gère le multiway... Surtout que Pio a plus ou moins reconnu ne plus s'investir dans son solver actuel. J'attends de voir la réponse de punter sur 2+2.

Share this post


Link to post
Share on other sites

J'ai run quelques simu pour comparer les solutions avec celles du pack de pio et ça colle assez bien pour un temps de simulation ridiculement petit, de l'ordre de  20min et moins de 2 gigas de RAM.

Ensuite j'ai pu m'amuser en testant un cas où SB et BB postent le même montant et un autre où je place une straddle. Ce dernier cas m'a pris par contre presque 6h de simulations mais c'est un cas avec 4 joueurs. La RAM reste toujours faible (moins de 4gigas), ce qui est quand même le gros point positif car c'est vite un point limitant pour les autres solvers.

L'UI est assez pourrave en revanche, mais ça n'a jamais été le point fort de SPF (en comparaison avec l'offre Piosolver).

Conclusion : assez positif.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

English
Retour en haut de page
×
PokerStars : SECOOP
PokerStars : SECOOP