A la quête de la stratégie optimale

Bonsoir,
J'aimerais vous partager une passion que je possède depuis un certain temps, ce sont les algorithmes. Et, plus précisément, de leur application dans les jeux de "semi hasard" où certaines informations sont cachées, comme le poker. On dit qu'il sont à "informations imparfaites".
C'est à dire que vous ne connaissez pas toutes les données concernant votre situation. Dans le cas du Poker, le défi serait d'arriver à générer un bot qui arriverait à calculer, dans chaque situation à partir des données fournies (cartes reçues, actions des adversaires) une stratégie parfaite pour ladite situation (ou branche du jeu). Cette stratégie parfaite est une répartition équilibrée entre les probabilités d'effectuer chaque action possible, de manière à maximiser le gain moyen d'une situation.
Longtemps durant, je me suis penché vers un système complexe où le bot ne prédirait que certaines actions, c'est à dire que, dans le cas du Poker, on espacerait les mises de façon proportionnelle, de sorte à éviter de calculer les relances à 1001 jetons si l'adversaire a misé 1000, ce qui compliquerait inutilement l'arbre de jeu sans apporter de résultat concret. De ce fait, j'ai défini les mises comme des proportions de la relance maximale possible, ce qui semblait sonner juste au vu de la situation de proportionnalité très présente au poker. Pour vous donner un exemple simple, supposons qu'un bot de poker soit entraîné à jouer parfaitement avec 1000 jetons, alors il utilisera les mêmes mises, dans les mêmes situations qu'avec 100 jetons, de manière proportionnelle. J'avais également prédis de créer un score basé sur l'addition du gain obtenu par ce que le bot pouvait espérer en tirer en fonction de la croyance de l'adversaire, c'est à dire un gain à long terme. Et c'est là que j'ai eu tort.
En effet, pour un nombre N de tailles de paris utilisés par le moteur, il faudra envisager 2^(n-1) possibilités à calculer, soit 2*n+1 situations de plus pour une mise supplémentaire, pour n tailles de paris. Ce qui n'est pas envisageable pour calculer un détail supplémentaire.
En bref, il fallait définir une stratégie optimale pour une probabilité de gain. Par exemple, si vous avez 64% ou 36% de chances de gain, vous ne joueriez pas de la même manière ; les répartitions des actions seront différentes. Vous aurez davantage tendance à passer votre tour naturellement, pour ne pas perdre davantage d'argent.
Il y aura donc des tables, résumant les répartitions de chaque action possible selon les probabilités de gain de tel ou tel adversaire. Les probabilités seront elles-mêmes tranchées en groupe similaires, ainsi nous pouvons classer une probabilité de gain de 99% ou de 100% comme étant la même chose. Cela évite de créer 200 groupes pour une simple grappe de probabilités dont la stratégie est quasiment la même.
Maintenant, il y a l'espérance de gain et la construction progressive de la stratégie optimale. Si, par exemple vous savez que vous avez 100% de chances de gagner dans une situation, vous ferez tout afin que votre adversaire mise et vous permette de récolter plus d'argent. Cependant, en dépit du fait que vous avez 100% de chances de gagner le pot, vous ne gagnerez pas forcément la partie à la fin ; c'est à dire que, sur tout l'argent gagnable en fin de partie, vous ne gagnerez pas forcément 100% ; vous ne récolterez pas tout l'argent dès ce tour. Et étant donné que cela s'applique pour toutes les probabilités de gagner, votre gain moyen sera forcément inférieur à celles-ci. Sachant qu'en moyenne, vous avez exactement les MÊMES actions possibles lors de chaque main, cela signifie qu'en moyenne, vous gagnerez le même pourcentage de gain sur votre propre pourcentage de gagner le pot...autrement dit, supposons que vous gagnez en moyenne 30% de votre côte de probabilité par tour. Vous avez 60% de chances de gagner le pot, 40% de le perdre soit un bénéfice de 60-40=20% du pot. Vous avez donc sur ce bénéfice, 30% de gains moyens soit 6%. ce nombre sera votre bénéfice réel en fin de tour, c'est à dire que, à la fin, en supposant que chaque adversaire ait commencé avec le même nombre de jetons, disons 1000, l'un d'entre eux aura un avantage de 6% de jetons par rapport à lui, c'est à dire 1030 contre 970 jetons soit 60 jetons de différence. Je conçois qu'expliquées de cette manière les choses paraissent confuses, mais ceci est parfaitement logique.

Les tableaux de répartitions donnent des stratégies de mise lorsque toute mise est possible, c'est à dire sans relance de votre adversaire. Autrement dit, si votre adversaire mise avant vous ne serait-ce que 0.5% de ses jetons, la stratégie entière ne peut pas s'appliquer car au moins une partie de cette stratégie n'est plus envisageable du fait de la relance minimale obligatoire pour suivre. De ce fait, il suffit d'enlever du tableau une situation qui n'est pas réalisable pour un pourcentage de victoire donné, afin de regrouper toutes les probabilités restantes, de les additionner et de les diviser individuellement par leur total. On obtient ainsi, la nouvelle répartition parfaite des actions pour une situation donnée.

La stratégie dépendra de la probabilité de gain que l'on possède pour une situation donnée, mais s'équilibrera naturellement avec les actions de l'adversaire qui fournissent une indication selon la situation de la probabilité qu'il possède telle ou telle carte. De ce fait la stratégie n'est pas prévisible, et assure un gain moyen maximal. En effet, le bot va simplement jouer selon les indications qu'il possède concernant les probabilités de posséder telle ou telle carte. ar exemple, s'il reçoit une paire d'as, il saura que les probabilités de l'adversaire d'en posséder sera moindre, et que sa main sera plus forte. De ce fait, il va calculer les probabilités initiales d'avoir telle ou telle carte, puis regarder les probabilités que l'adversaire ait joué son action avec chaque combinaison de cartes possibles, puis générer une moyenne pondérée sur la probabilité que l'adversaire détienne chaque carte, en fonction de la probabilité précédemment établie. Les informations induites par le jeu du bot seront également prises en compte, de sorte à comprendre ce que pense l'adversaire en fonction de nos propres actions de jeu passées. Lors du prochain tour, le bot va calculer les nouvelles probabilités de gain de l'adversaire en fonction de ses probabilités de détenir chaque carte, en fonction des cartes présentes sur le tapis. Il reviendra en arrière pour affiner ses calculs en fonction des nouvelles données acquises, afin de mieux comprendre ce que pensait l'adversaire et qu'elles cartes il semble posséder. En effet, certaines cartes dont l'on pouvait suspecter l'adversaire de posséder n'étaient pas dans son jeu, ce qui pousse à corriger le raisonnement précédent à l'aide de toutes les informations disponibles. Le processus continue à chaque fois, avant de créer un tableau de répartition des actions de la manière énoncée plus haut, puis de choisir en fonction de leurs probabilités les futurs actions et tailles de paris à engager. En effet, étant donné que les probabilités s'équilibrent en fonction des actions de l'adversaire, il n'y a pas besoin de rajouter un score en fonction de ce qu'il est censé penser. En effet, une stratégie existe déjà pour notre situation actuelle et permet, sur un très grand nombre de mains d'obtenir un gain maximal, qui tend a gagner le plus d'argent possible a chaque tour. Ce qui signifie que les applications de la stratégie a long terme est exactement la même que sur un seul tour, étant donné qu'en moyenne la probabilité de gain ne change pas. Passons enfin à la construction de la stratégie du bot. Le bot va simplement générer deux stratégies de manière aléatoire, qui se confronteront sur un ensemble de situations différentes. Des parts de leurs stratégies seront utilisées pour des situations spécifiques et comparées selon leur efficacité, déduite de la chance. L'algorithme va donc simuler une valeur, l'espérance de gain qui comme dit plus haut est toujours inférieure à notre probabilité de gagner, qui au départ sera de 1 (100%). Ensuite, après chaque tour le bot va répartir les gains de chaque côté en fonction de leurs probabilités respectives de gagner le pot, ou va le donner à un joueur avec sa stratégie spécifique en cas de situation de "passe" où l'adversaire abandonne la mise. Ensuite, l'algorithme va estimer la performance d'une stratégie en fonction de son bénéfice, déduite de sa chance et de espérance de gain, qui sera d'ailleurs progressivement estimée après chaque tour de jeu de l'IA durant son amélioration. On soustrait alors à la part de la meilleure stratégie utilisée la stratégie la moi s bonne, et on multiplie ce résultat par la valeur obtenue précédemment, avant de l'ajouter à la meilleure stratégie. Ces deux stratégies seront elles-mêmes étudiées dans un autre tour, avec des situations différentes qui permettront d'ajouter une valeur d'amélioration à la meilleure stratégie, de sorte à l'améliorer en fonction de son efficacité. Cette technique s'appliquera sur des situations comprenant uniquement un seul tour de paris, avec des cartes différentes. Cela n'impactera absolument pas la stratégie à avoir dans une situation réelle, qui sera juste calculée en fonction des situations précédentes. Vous allez me dire "mais ça existe déjà des bots pour le poker". C'est vrai, sauf qu'aucun bot n'utilise une telle stratégie d'amélioration pour le moment qui lui garantisse d'obtenir un jeu si proche de la perfection, tout en étant parfaitement applicable dans des situations à plus de 2, 5, 8 voire 10 joueurs. En effet, les seuls algorithmes capables de gérer une telle complexité se contentaient de faire une vague abstraction de l'arbre de jeu pour obtenir un jeu sensiblement meilleur que celui des meilleurs joueurs humains, tout en prenant un temps considérable à s'améliorer car l'arbre devenait exponentiellement plus complexe à chaque joueur supplémentaire.

Ainsi, il est possible de calculer, pour n'importe quel nombre de joueurs présents, une stratégie quasi-parfaite pour chaque situation donnée au poker no-limit Texas holdem rapidement.

Post plus bas.

Pourquoi tu veux créer un bot alors qu'avec les probas tu peux calculer toi même ?

Ta question peut avoir plusieurs sens. Pourrais-tu apporter des précisions ?
Je vais tout de même essayer de répondre, aucun être humain n'est capable d'avoir un jeu statistiquement proche de la perfection, même en ayant les probabilités pour chaque jeu de cartes. Cela nécessite de se souvenir de chaque action de l'adversaire, de connaître par coeur des millions de probabilités et surtout de calculer, pour chacune d'entre leurs chances d'arriver tout en se corrigeant sur chaque résultat précédent après chaque tour, en calculant des milliers de mains. Ce qui est facile pour un bot, mais impossible pour un humain.

Je ne joue pas au poker, mais j'y accorde juste un intérêt mathématique.

Ce n'est pas une IA c'est un moteur.
Et non il ne crée pas d'arbres justement, il trouve la solution quasi instantanément grâce à une technique sans complexifier exponentiellement l'arbre mais faut bien lire les pavés