{"id":7352,"date":"2015-01-19T00:01:59","date_gmt":"2015-01-18T23:01:59","guid":{"rendered":"https:\/\/sciencetonnante.wordpress.com\/?p=7352"},"modified":"2015-01-19T00:01:59","modified_gmt":"2015-01-18T23:01:59","slug":"une-strategie-infaillible-au-poker","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2015\/01\/19\/une-strategie-infaillible-au-poker\/","title":{"rendered":"Une strat\u00e9gie infaillible au poker"},"content":{"rendered":"

\"Poker_cards_and_chips\"<\/a>Depuis la d\u00e9faite du champion du monde Gary Kasparov contre l’ordinateur Deep Blue en 1997, nous nous sommes habitu\u00e9s \u00e0 ce que les machines soient d\u00e9finitivement plus fortes que les humains aux \u00e9checs. Bon apr\u00e8s tout, les \u00e9checs, c’est rien que du pur raisonnement math\u00e9matique.<\/p>\n

Mais le poker ? Ce jeu qui rel\u00e8ve autant du calcul que de la psychologie, o\u00f9 il faut savoir entourlouper et bluffer, prendre des risques parfois, \u00eatre prudent de temps en temps…un ordinateur battrait un champion du monde de poker ?<\/p>\n

Eh bien les amis, sachez que la situation est encore bien pire que \u00e7a. Ce qui vient d’\u00eatre annonc\u00e9 il y a quelques jours, \u00e7a n’est pas qu’un ordinateur peut battre un humain, mais que cet ordinateur est capable de jouer une strat\u00e9gie parfaite, et math\u00e9matiquement<\/em> imbattable<\/strong>.<\/p>\n

R\u00e9soudre les jeux<\/h3>\n

En termes techniques, on dit que le poker est maintenant un jeu r\u00e9solu<\/strong>. R\u00e9soudre un jeu, cela veut dire trouver une strat\u00e9gie qui permette \u00e0 coup s\u00fbr de s’assurer la victoire. Bien s\u00fbr cette strat\u00e9gie ne doit pas n\u00e9cessairement \u00eatre une suite de coups fix\u00e9s \u00e0 l’avance, mais plut\u00f4t une proc\u00e9dure pour r\u00e9agir aux coups de l’adversaire<\/strong> tout en l’amenant \u00e0 une d\u00e9faite certaine.<\/p>\n

\"batonnets\"<\/a>Pour expliquer \u00e7a, prenons un exemple simple : le jeu des b\u00e2tonnets<\/strong>. Ce jeu \u2014 rendu c\u00e9l\u00e8bre par l’\u00e9mission de t\u00e9l\u00e9 Fort Boyard<\/em> \u2014 se joue de la fa\u00e7on suivante. Deux joueurs ont en face d’eux 20 petits b\u00e2tonnets. A chaque fois que c’est son tour, un joueur doit prendre 1, 2 ou 3 b\u00e2tonnets. Celui qui prend le dernier b\u00e2tonnet perd la partie.<\/p>\n

Eh bien si vous \u00eates le premier joueur, il existe une strat\u00e9gie infaillible. Prenez 3 b\u00e2tonnets au premier coup, et ensuite si votre adversaire en a pris N, prenez en 4-N<\/strong>. Je vous laisse essayer pour v\u00e9rifier que \u00e7a vous permet de fumer l’autre joueur \u00e0 coup s\u00fbr !<\/p>\n

Il faut noter que pour les jeux dans lesquels il peut y avoir \u00ab\u00a0\u00e9galit\u00e9\u00a0\u00bb, il n’existe pas forc\u00e9ment de strat\u00e9gie infaillible assurant la victoire. Mais il en existe au moins une qui assure le match nul. C’est le cas par exemple du jeu de Morpion : si vous avez un peu l’habitude, vous pouvez tr\u00e8s facilement faire en sorte que l’adversaire ne puisse pas gagner.<\/p>\n

Il existe un tas de jeux simples qui sont aujourd’hui r\u00e9solus. C’est par exemple le cas du Puissance 4, pour lequel il existe une strat\u00e9gie permettant au premier joueur de gagner; mais aussi du jeu de Dames, dont la \u00ab\u00a0r\u00e9solution\u00a0\u00bb a \u00e9t\u00e9 publi\u00e9e en 2007 [1].<\/p>\n

\"jeux<\/a><\/p>\n

A ce jour, le jeu d’\u00e9checs n’est pas encore r\u00e9solu, et d’ailleurs il est peu probable qu’il le soit dans un jour proche. Donc actuellement quand les ordinateurs battent les humains aux \u00e9checs, \u00e7a n’est pas parce qu’ils disposent d’une strat\u00e9gie math\u00e9matiquement parfaite : ils sont justes tr\u00e8s tr\u00e8s forts.<\/p>\n

Les jeux \u00e0 information incompl\u00e8te<\/h3>\n

Les jeux comme les \u00e9checs ou le jeu des b\u00e2tonnets sont des jeux dits \u00ab\u00a0\u00e0 information compl\u00e8te\u00a0\u00bb. Cela signifie que les deux joueurs poss\u00e8dent tous les deux la m\u00eame information : tout est sur la table, il n’y a rien de cach\u00e9. Mais dans de nombreux jeux, on doit d\u00e9cider de son coup sans poss\u00e9der toutes les informations : c’est ce qu’on appelle les jeux \u00e0 information incompl\u00e8te<\/strong>. D’ailleurs dans les d\u00e9cisions que l’on doit prendre dans la vie courante, nous n’avons jamais toutes les informations. John Von Neumann, un des p\u00e8res de la th\u00e9orie des jeux, disait d’ailleurs :<\/p>\n

Real life is not like chess.\u00a0 Real life consists of bluffing, of little tactics of deception, of asking yourself what is the other man going to think I mean to do.\u00a0 And that is what games are about in my theory.<\/em><\/p>\n

Le poker est certainement l’arch\u00e9type de ces jeux \u00e0 information incompl\u00e8te. Au poker, on doit d\u00e9cider de son coup alors qu’il nous manque des informations cruciales : les cartes qui vont sortir bien s\u00fbr, mais surtout les cartes que poss\u00e8de l’adversaire !<\/p>\n

La version du poker qui vient d’\u00eatre r\u00e9solue par le Computer Poker Research Group<\/em> de l’universit\u00e9 d’Alberta au Canada, c’est ce que l’on appelle le Heads up Limit Hold’em<\/strong>. <\/em>Il s’agit d’un poker \u00e0 deux joueurs, dans sa variante dite \u00ab\u00a0limit\u00a0\u00bb, o\u00f9 la valeur de la relance est fix\u00e9e, et le nombre de relances est limit\u00e9. Dans cette version, chaque fois que c’est votre tour de jouer, vous n’avez que trois choix possibles : vous coucher, suivre ou relancer.<\/p>\n

Le m\u00eame groupe de recherche avait d\u00e9j\u00e0 cr\u00e9\u00e9 dans le pass\u00e9 un programme du nom de Polaris<\/em>, qui en 2008 fut le premier \u00e0 battre des joueurs professionnels. Mais comme je vous l’ai dit, l\u00e0 nous sommes tr\u00e8s au-dessus de \u00e7a puisque leur nouveau programme appel\u00e9 Cepheus<\/em> est math\u00e9matiquement imbattable : il joue une strat\u00e9gie parfaite.<\/strong><\/p>\n

La strat\u00e9gie de Cepheus ne r\u00e9sulte pas de l’ingurgitation de connaissances poss\u00e9d\u00e9es par des experts du poker, mais d’une exploration du jeu que le programme a fait tout seul en jouant contre lui-m\u00eame. En gros, il a essentiellement explor\u00e9 toutes les situations possibles, et fabriqu\u00e9 une strat\u00e9gie parfaite \u00e0 partir de l\u00e0. Pour cela, le programme a jou\u00e9 une moyenne de 6 milliards de parties par seconde pendant plus de deux mois. Autant dire qu’\u00e0 chaque seconde, il a probablement jou\u00e9 plus de parties que l’humanit\u00e9 enti\u00e8re depuis l’invention du poker !<\/strong><\/p>\n

Dans le cas d’un jeu comme le poker, il est important de pr\u00e9ciser ce qu’on entend par \u00ab\u00a0une strat\u00e9gie parfaite\u00a0\u00bb. En effet \u00e9tant donn\u00e9 qu’il y a un facteur chance dans le jeu, si vous jouez seulement 10 coups contre Cepheus et que vous avez une baraka d’enfer, vous allez peut-\u00eatre gagner. Mais au long-terme, quand le facteur chance disparait du fait du grand nombre de parties jou\u00e9es, c’est Cepheus qui gagnera \u00e0 coup s\u00fbr.<\/p>\n

Quelques enseignements<\/h3>\n

La strat\u00e9gie mise au point par Cepheus ne se r\u00e9sume heureusement pas \u00e0 quelques r\u00e8gles simples comme dans le cas du jeu des b\u00e2tonnets. Je dis \u00ab\u00a0heureusement\u00a0\u00bb car \u00e7a rendrait le poker un peu insipide si tout le monde pouvait jouer une strat\u00e9gie parfaite. La strat\u00e9gie est en fait tellement compliqu\u00e9e que pour la stocker il faut 11 T\u00e9ra-octets de m\u00e9moire ! Mais si \u00e7a vous int\u00e9resse, vous pouvez vous rendre sur le site de Cepheus et lui soumettre une situation pr\u00e9cise<\/a> : vous saurez alors quelle est la d\u00e9cision optimale \u00e0 prendre.<\/p>\n

De l’analyse des premiers coups possibles, on peut tirer quelques enseignements int\u00e9ressants pour les joueurs de poker. Par exemple Cepheus d\u00e9montre math\u00e9matiquement ce que l’on savait par exp\u00e9rience : le donneur est avantag\u00e9 car il joue en dernier. Autre le\u00e7on, vous pouvez consulter les d\u00e9cisions que prendrait Cepheus au premier tour en fonction des deux cartes initiales qu’il re\u00e7oit. Le graphique suivant est tir\u00e9 de l’article [2]<\/p>\n

\"cepheus<\/a><\/p>\n

Voici comment lire ce diagramme : \u00e0 gauche, vous avez la strat\u00e9gie \u00e0 suivre en fonction de vos deux cartes initiales<\/strong> si vous \u00eates le premier \u00e0 parler, \u00e0 droite si vous \u00eates le second et que le premier joueur a mis\u00e9. Vert = relancer, Rouge = se coucher, Bleu = Suivre. Si vos deux cartes sont de la m\u00eame couleur, vous prenez la moiti\u00e9 sup\u00e9rieure droite du tableau, si elles sont de couleur diff\u00e9rente, la moiti\u00e9 inf\u00e9rieure gauche.<\/p>\n

Dans le tableau de gauche, on voit par exemple que si vous \u00eates le premier \u00e0 parler, il ne faut jamais \u00ab\u00a0checker\u00a0\u00bb<\/del> \u00ab\u00a0caller\u00a0\u00bb<\/strong> : soit vous y allez en relan\u00e7ant, soit vous vous couchez. Dans celui de droite, on voit que Cepheus ne se couche que si vraiment il est totalement en slip. M\u00eame avec un 3 et un 5 il va suivre !<\/p>\n

Bien s\u00fbr pour les puristes il faut prendre \u00e7a avec des pincettes, car nous parlons ici de la version \u00ab\u00a0Limit\u00a0\u00bb. Comme on ne peut pas choisir le montant de la relance, cela enl\u00e8ve toutes les strat\u00e9gies du genre \u00ab\u00a0je relance de 100 000 !\u00a0\u00bb. Il n’est pas s\u00fbr que la strat\u00e9gie de Cepheus puisse facilement s’adapter au \u00ab\u00a0no limit\u00a0\u00bb. Alors ok, les humains ont encore de beaux jours devant eux face aux machines !<\/p>\n

Les plus grincheux vont nous dire : \u00e0 quoi \u00e7a sert que des chercheurs soient pay\u00e9s \u00e0 \u00e9tudier les strat\u00e9gies gagnantes au poker ! Eh bien chose amusante, dans l’article publi\u00e9 les auteurs concluent en justifiant des applications possibles de leur travail, et en citant les situations pour lesquels on se trouve dans une configuration proche des jeux \u00e0 information incompl\u00e8te, comme certaines ench\u00e8res, ou m\u00eame dans le cas de choix de traitement m\u00e9dicaux. Mais honn\u00eates, les auteurs terminent leur article par cette citation de T\u00fcring, autre p\u00e8re fondateur du domaine :<\/p>\n

\u00ab\u00a0It would be disingenuous of us to disguise the fact that the principal motive which prompted the work was the sheer fun of the thing\u00a0\u00bb<\/em><\/p>\n

Billets reli\u00e9s<\/h4>\n