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.
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.
Promis, la prochaine fois je parlerai Sharepoint :)
