La machine va-t-elle tuer le poker ?

• 13 mai 2015
• petiteglise
• 3357
•  PA  0
• 9 Commentaires

Les ordinateurs ont résolu le jeu de dames et explosent les meilleurs humains aux échecs. Le limit holdem HU a été résolu a son tour, tandis que les machines rivalisent avec les meilleurs en NL. Est-ce le début de la fin du poker ?

La résolution d’un jeu

On parle de trois manières de résoudre un jeu à deux joueurs à information complète.

1. Résolution très faible : connaître le résultat de la position de départ : “le jeu du morpion 3*3 est nul”
2. Résolution faible : savoir gagner toutes les positions gagnantes et annuler toutes les positions nulles, sans forcément connaître le résultat de chaque coup : au morpion, si votre adversaire joue au milieu au premier coup, vous pouvez retenir que la position est nulle et que jouer en haut à gauche conserve l’égalité, sans vous préoccuper de ce que font les autres coups.
3. Résolution forte ; connaître le résultat de toutes les positions et donc tous les coups légaux.

Dans le cas des jeux à information complète, le jeu parfait consiste à jouer le gain le plus rapide dans une position gagnante, un coup qui fait nulle dans une position égale, et le coup qui retarde le plus la perte dans une position perdante.

Dans le cas des jeux à information incomplète, le jeu parfait consiste à choisir la stratégie avec “la plus haute EV minimum”, indépendemment de la stratégie adverse. Par exemple, à pierre-feuille-ciseaux, le jeu parfait consiste à tirer au sort son prochain coup avec équiprobabilité. Cette stratégie n’est pas battable mais elle ne permet pas d’exploiter un adversaire.

Les jeux simplistes comme le morpion sont évidemment tous résolus fortement. La résolution d’un jeu dépend de sa complexité, c’est à dire du nombre de positions possibles. Voici un ordre d’idées de la complexité de quelques jeux populaires :

Les dames 8*8 (checkers) ont 5*10^20 positions
Les échecs ont 10^50 positions
Le jeu de go 19*19 a 10^170 positions

Les dames sont le jeu le plus complexe jamais résolu. Terminée en 2007, la résolution de ce jeu aura duré 18 ans et demandé pas moins de 200 ordinateurs. Et encore, le jeu n’est que faiblement résolu : le programme ne perdra jamais une partie et si vous faites une erreur il vous battra à coup sûr, mais il ne connaît pas toutes les positions possibles, "seulement" 10^14.

Les échecs sont résolus uniquement pour les positions à moins de 7 pièces, loin des 32 du départ. Sauf révolution informatique, il semble impossible de résoudre ce jeu. Cela dit, les meilleurs programmes sont beaucoup plus forts que les meilleurs humains, et ce depuis la fameuse défaite de kasparov contre Deep Blue en 1997. Mais ils sont encore très loin d’être imbattables et d’ailleurs ils se battent régulièrement entre eux.

Le jeu de go, immensément plus compliqué encore, est un des rares jeux à information complète auquel la machine se fait totalement dominer par l’homme.

La résolution du Holdem

La variante la plus simple du Holdem est évidemment le Limit en format HU. On estime à 3.6 * 10^13 “positions” différentes à ce jeu. Par position, on entend les cartes du joueur, du board, l’argent des joueurs, celui dans le pot et les actions passées.

Pour réduire la complexité du jeu, les programmeurs ont recours à différentes approximations.

Les “isomorphismes” : il y a 52*51/2 = 1326 mains de départ différentes au poker. Mais on peut réduire ce chiffre à 169 car, préflop,     se joue pareil que  
Les équivalence de rang : sur un board   les mains et ont exactement les mêmes équités et peuvent être réduites à un seul cas.
Les quasi équivalences de rang : par exemple, considérer que préflop K7o et K6o se jouent de la même manière.
On peut aussi considérer que chaque décision est indépendante, même si c’est clairement discutable, car ça supprime les stratégies sur plusieurs streets.

En janvier 2015, une équipe de cinq scientifiques a annoncé avoir résolu le Limit Holdem HU. Durant le jeu, leur programme Cepheus  n’a pas grand chose à faire si ce n’est chercher dans sa base la situation dans laquelle il se trouve et la stratégie optimale correspondante.

C’est évidemment créer cette base qui a été fastidieux. Il a d’abord fallu compiler toutes les positions possibles. Ensuite Cepheus a commencé à jouer aléatoirement contre lui même. Puis, pour chaque décision, il essayait par exemple de miser, au lieu de jouer aléatoirement, constatait la différence d’Ev et la notait. Après d’innombrables essais, la décision qui donne la plus grande Ev peut raisonnablement être considérée comme optimale. Au total la base de données de Cepheus pèse quelque 520 000 gigabytes.

Notons donc que le jeu n’est résolu qu’essentiellement et pas entièrement, à cause de l’emploi de quelques approximations comme celles mentionnées plus haut.

Le No Limit, avec tout son éventail de mises, est évidemment beaucoup plus complexe et compte 10^75 positions différentes en format deep stack HU.

Mais ce n’est rien comparé au poker à plusieurs joueurs. D’ailleurs, dès qu’il y a plusieurs joueurs, aucune stratégie ne peut être imbattable à cause des possibilités de collusion.

Autrement dit, à l’inverse du Limit HU, le jeu à plusieurs et surtout le NL pourraient bien ne pas être résolus de notre vivant. Cela dit…

Les bots au poker

Une machine n’a pas besoin de résoudre un jeu pour y être plus forte que les humains. Et au poker, les choses commencent à se gâter pour nous dans le combat neurones vs sicilicium.

Dès février 2013, nous vous parlions des bots qui multitablaient sur Zynga Poker, "dérobant" 1.8 millions de $ en jouant sur des tables de NL 50 à NL 500 Début 2014, PokerSnowie remportait son challenge contre les académiciens, avec un winrate moyen de 14BB/100. Alors certes, ces derniers jours, l’homme a eu un soubresaut, battant largement le programme Claudico.

Cependant, la machine était loin d’être ridicule,considérant qu’elle faisait face à la crème mondiale. Et, cela dit en passant, elle progresse à chaque main jouée... Il est fort possible que cette victoire soit donc le chant du cygne de l’humanité. Dans quelques années au plus tard, aucun joueur ne voudra affronter de programme en HU argent réel.

Un autre problème de la progression des machines, réside dans cette inégalité toute bête : homme + machine > homme. Un joueur se servant habilement d’une intelligence artificielle pourrait sans aucun doute crusher ses limites habituelles. En partageant intelligemment les spots entre lui et la machine, il déchirerait sans doutes des joueurs de son niveau. Ca serait comme jouer avec un super tracker qui équilibre les ranges, diversifie le jeu, empêche le tilt et permet de se reposer…

Bref, si la machine ne risque pas de résoudre le poker, elle pourrait en revanche le tuer...