Publié vendredi 28 mars 2008 23:00 par Arnault Nouvel

Design d'un simulateur de poker performant grâce à Linq

Dans le cadre du développement d’un robot capable de jouer au Texas Hold’em, j’ai créé une classe RoundInfo qui centralise toutes les informations sur la main en cours. Ce post est dédié à son design car il est amusant, performant en consommation mémoire, et basé entièrement sur Linq.

 

Le projet en quelques mots

Un des gros challenges quand on développe un robot de poker est la performance. A l’ère Bruel ^^, lorsque j’ai développé mon premier robot (en appliquant point par point la méthode de la RACHE), et une fois que suffisamment d’ « intelligence » fut implémentée, il arrivait parfois qu’il mette plus de 20 secondes à réagir lorsque son tour venait. Résultat, il se faisait kicker de la table. Le proof of concept était validé, mais le design méritait d'être revu. Par manque de temps, j'ai alors abandonné le projet.

Quelques générations de micro-processeurs plus tard, lorsque j'ai souhaité tester les nouveautés du Framework 3.5, la motivation était toute trouvée pour reprendre refaire le projet. Cette fois la priorité serait mise sur la performance. Pas seulement au niveau des traitements, mais aussi au niveau mémoire car l’IA devrait conserver en mémoire toutes les mains jouées contre chacun des adversaires afin de mieux les « lire ».

La solution comporte 4 projets :

·         Un projet de type console application qui sert de point d’entrée

·         HoldemSimulator : librairie maison permettant de simuler une table de poker et la partie qui s’y déroule, ainsi que deux implémentations sommaires de IPlayer

·         HoldemInterface : contient l’interface IPlayer à implémenter pour réaliser un robot compatible avec HoldemSimulator

·         Nono le petit robot : implémentation vicieuse de IPlayer

·         HandEvaluator : une librairie C# incontournable lorsque l’on effectue des calculs de probabilité dans le contexte du Poker.

 

Les classes EventInfo

Une main de poker peut se résumer en quelques méta-datas (qui est dans la partie et à quelle place, quels sont les montants des blinds, etc.) ainsi qu’une suite ordonnée d’événements/actions (tel joueur mise tant, tel autre joueur relance, telle carte est découverte au turn, etc.). Tous ces éléments, et leur ordre, définissent une main de poker. Voici pour exemple le log d’une main jouée sur un site de poker en ligne :

Starting Hand #204916231

Game Type: Hold'em

Limit Type: No Limit

Table Type: Ring

Money Type: PLAY MONEY

Blinds are now $50/$100

Button is at seat 10

Seat 3: novembertango - $63757

Seat 4: MoneA - $10000

Seat 6: polak33 - $9000

Seat 7: Kheops - $6000

Seat 9: raceman69 - $0 (away from table)

Seat 10: john83 - $0 (away from table)

Moving Button to seat 7

novembertango posts small blind ($50)

MoneA posts big blind ($100)

Shuffling Deck

Dealing Cards

Dealing [2d Ah] to Kheops

polak33 calls $100

Kheops calls $100

novembertango calls $100

MoneA checks

Dealing Flop [As 5s Qs]

novembertango checks

MoneA checks

polak33 checks

Kheops bets $5900 (all-in)

novembertango folds

polak33 laughs his *** off.

MoneA folds

polak33 folds

Kheops shows [2d Ah]

Kheops has One Pair: Aces

Kheops wins $400

End Of Hand #204916231

 

Afin de décrire chacune de ces informations qui définissent une main, j’ai créé une classe abstraite EventInfo dont héritent tous les types d’information. Ce sont des classes toutes simples composées de rares propriétés et d'une méthode ToString(). C'est la hiérarchie des classes et le typage fort qui sont pertinents. Je vous invite à cliquer sur le diagramme de classes ci-dessous pour en voir une version lisible.

 

 ClassDiagram

 

La classe RoundInfo

 

Dans le contexte d’une utilisation dans le simulateur, cette classe est utilisée par le Dealer (objet qui distribue les cartes), par les 9 instances FishPlayer qui sont les adversaires de Nono, et par Nono en personne. Elle dispose de propriétés permettant de savoir en temps réel combien il y a dans le pot, qui est à la table, qui doit jouer, combien doit-il miser pour suivre, de combien est la relance minimum, etc. Cette classe est donc centrale et de ses performances dépend le nombre de mains que le simulateur peut traiter par seconde. C’est là qu’intervient Linq !

 

La classe est composée d’un seul accesseur, privé, une collection List<EventInfo> _events. En pratique, pour chaque méta-data et à chaque fois qu’une action a lieu à la table, le dealer appelle la méthode AddEventInfo(EventInfo info) en passant une instance d'EventInfo. De son coté, chaque robot fait de même pour maintenir sa propre instance de RoundInfo.

 

Grâce à Linq, cette unique collection permet de fournir une multitude de propriétés. En voici un tout petit extrait :

 

 

        public virtual Int32 BigBlind {

            get { return _events.OfType<PlayerBlindEventInfo>().Where(pm => pm.Type == BlindType.Big).Select(pm => pm.Chips).FirstOrDefault(); }

        }

 

        public virtual String Board {

            get { return _events.OfType<BoardEventInfo>().Select(be => be.Board).LastOrDefault() ; }

        }

 

        public virtual String[] Players {

            get { return _events.OfType<PlayerStartEventInfo>().OrderBy(ps => ps.Seat).Select(ps => ps.PlayerId).ToArray(); }

        }

 

        public virtual StepName CurrentStep {

            get { return _events.OfType<BoardEventInfo>().Select(be => be.Step).LastOrDefault(); }

        }

 

        public virtual String[] RemainingPlayers {

            get { return Events.OfType<PlayerStartEventInfo>().Where(ps => !HasFolded(ps.PlayerId)).OrderBy(ps => (ps.Seat - ButtonSeat - 1 + Utils.SeatsPerTable) % Utils.SeatsPerTable).Select(ps => ps.PlayerId).ToArray(); }

        }

 

        public virtual String[] AllInPlayers {

            get { return Events.OfType<PlayerBetEventInfo>().Where(pb => pb.AllIn).Select(pb => pb.PlayerId).Distinct().ToArray(); }

        }

 

        public virtual String NextPlayer {

            get { return GetNextPlayer(); }

        }

 

        public virtual Int32 ButtonSeat {

            get { return Events.OfType<ButtonEventInfo>().Select(b => b.Seat).Single(); }

        }

 

Le diagramme des classes touffu d'EventInfo prend tout son sens lorsque l'on voit l'utilisation massive de de la méthode OfType<T>() qui ne retourne que les objets du type T .

 

Les rares méthodes privées de la classe sont elles aussi basées sur Linq :

 

 

        private Boolean HasFolded(String playerId) {

 

            return Events.OfType<PlayerFoldEventInfo>().Select(pf => pf.PlayerId).Contains(playerId);

 

        }

 

        private String GetNextPlayer() {

 

            if (Events.Last() is BoardEventInfo)

                return RemainingPlayers.First();

 

            //Last player that moved

            String lastPlayerName = Events.OfType<PlayerMoveEventInfo>().Except(Events.OfType<PlayerFoldEventInfo>().ToArray()).Select(pm => pm.PlayerId).LastOrDefault();

 

            //if null, the next player is the small blind

            if (String.IsNullOrEmpty(lastPlayerName))

                return (RemainingPlayers.Length == 2) ? RemainingPlayers.LastOrDefault() : RemainingPlayers.FirstOrDefault();

 

            //Seat of the last player that moved

            Int32 lastPlayerSeat = Events.OfType<PlayerStartEventInfo>().Where(ps => ps.PlayerId == lastPlayerName).Select(ps => ps.Seat).FirstOrDefault();

 

            String result = Events.OfType<PlayerStartEventInfo>().Where(ps => !HasFolded(ps.PlayerId) && !IsAllIn(ps.PlayerId)).OrderBy(ps => (ps.Seat - lastPlayerSeat - 1 + Utils.SeatsPerTable) % Utils.SeatsPerTable).Select(ps => ps.PlayerId).First();

 

            return result;

 

        }

 

Terminé les 38 collections (souvenir de ma V1) à maintenir en permanence, on requête dynamiquement une seule et unique collection! D’un point de vue mémoire c’est du tout bon car on a l’historique et le statut en temps réel, le tout grâce à une seule collection. Et d’un point de vue maintenance c’est vraiment agréable, le moindre problème s'identifie très facilement.

Certes, la même approche aurait pu être envisagée sans Linq, mais le code aurait été beaucoup trop volumineux et incompréhensible pour que tout cela soit réaliste.

Les seuls reproches que je fais à RoundInfo sont le fait que la classe ne soit pas thread-safe, et le coût processeur injustifié lors d’accès répétés à une même propriété entre deux appels à AddEventInfo().

 

Une brève revue de code met en évidence que ce cas ne se présente qu’au moment ou le robot doit prendre une décision. C’est là qu’intervient la classe RoundSnapShot.

 

 

La classe RoundSnapShot

 

Au moment de la prise de décision par le robot (implémentée sous la forme d’un réseau de neurones travaillant en asynchrone), tous les neurones accèderont aux propriétés de l'objet RoundInfo, ce qui peut conduire à une grosse déception côté performance. On va donc utiliser RoundSnapShot, une image de RoundInfo à un instant donné obtenue avec la méthode publique GetSnapShot() de la classe RoundInfo. RoundSnapShot hérite de RoundInfo et surcharge chacune de ses propriétés de la manière suivante :

 

        private Int32? _smallBlind;

 

        public override Int32 SmallBlind {

            get {

                lock (_lockSmallBlind)

                   if (_smallBlind == null)

                       _smallBlind = base.SmallBlind;

                return (Int32)_smallBlind;

            }

        }

 

        private String[] _allInPlayers;

 

        public override String[] AllInPlayers {

            get {

                lock (_lockAllInPlayers)

                   if (_allInPlayers == null)

                      _allInPlayers = base.AllInPlayers;

                return _allInPlayers;

            }

        }

        //et ainsi de suite..

 

J’ai déclaré un objet lock différent pour chaque propriété car les différents neurones accèdent à plusieurs propriétés en même temps, donc un seul objet lock partagé par toutes les propriétés aurait ralenti inutilement la prise de décision.

 

 

Un log simple à implémenter

 

Afin de pouvoir étudier le comportement du robot, et tout simplement débugger le simulateur, j’avais besoin d’un moyen de générer un log similaire à celui d’un site de poker en ligne décrit plus haut, afin de voir l'historique de la main d'un simple coup d'oeil. Avec ce design, rien de plus simple ! J’ai surchargé la méthode ToString() de chaque classe héritant de EventInfo.

 

Exemples :

 

         //BoardEventInfo

        public override string ToString() {

            if(Step == StepName.Flop)

                return String.Format("Flop : [{0}]", Board);

            else

                return String.Format("{0} : [{1}]", Step, Board.Split(' ').Last());

        }

 

        //PlayerRaiseEventInfo

        public override string ToString() {

            return String.Format("{0} raises {1}{2}", PlayerId, Chips, AllIn ? " and is all-in" : null);

        }

 

Pour atteindre mon but final, j’ai aussi surchargé ToString() dans RoundInfo :

 

        public override string ToString() {

            StringBuilder builder = new StringBuilder();

            foreach (EventInfo info in Events)

                builder.AppendLine(info.ToString());

            return builder.ToString();

        }

 

Il n’y a plus qu’à utiliser les classes Trace et Debug du framework pour écrire le log de la main dans un fichier texte ou dans la console de debug.

 

RoundInfoToString

 

Promis, la prochaine fois je parlerai Sharepoint :)

Ce post vous a plu ? Ajoutez le dans vos favoris pour ne pas perdre de temps à le retrouver le jour où vous en aurez besoin :

Les 10 derniers blogs postés

- Merci par Blog de Jérémy Jeanson le 10-01-2019, 20:47

- Office 365: Script PowerShell pour auditer l’usage des Office Groups de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 11:02

- Office 365: Script PowerShell pour auditer l’usage de Microsoft Teams de votre tenant par Blog Technique de Romelard Fabrice le 04-26-2019, 10:39

- Office 365: Script PowerShell pour auditer l’usage de OneDrive for Business de votre tenant par Blog Technique de Romelard Fabrice le 04-25-2019, 15:13

- Office 365: Script PowerShell pour auditer l’usage de SharePoint Online de votre tenant par Blog Technique de Romelard Fabrice le 02-27-2019, 13:39

- Office 365: Script PowerShell pour auditer l’usage d’Exchange Online de votre tenant par Blog Technique de Romelard Fabrice le 02-25-2019, 15:07

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Stream Portal par Blog Technique de Romelard Fabrice le 02-21-2019, 17:56

- Office 365: Script PowerShell pour auditer le contenu de son Office 365 Video Portal par Blog Technique de Romelard Fabrice le 02-18-2019, 18:56

- Office 365: Script PowerShell pour extraire les Audit Log basés sur des filtres fournis par Blog Technique de Romelard Fabrice le 01-28-2019, 16:13

- SharePoint Online: Script PowerShell pour désactiver l’Option IRM des sites SPO non autorisés par Blog Technique de Romelard Fabrice le 12-14-2018, 13:01