[alg] poker-hands alghoritme

[Verwijderd]

Ben bezig met het ontwikkelen van een pokergame.
Ik weet van vier personen hun `handen` ( = vijf kaarten die ze in bezit hebben).
De waarden van de vijf kaarten, per speler, heb ik als volgt (opgeslagen in een array);

code:

s6 = schoppen zes
kt = klaver tien (de tien wordt tevens als letter genoteerd, zodat alle combinaties van een dek kaarten uit twee letters/cijfers bestaan)
rh = ruiten heer
ha = harten aas
k3 = etc...

Tevens heb ik alle mogelijke scorende combinaties in een (multidim.) array opgeslagen, waarbij de hoogst winnende combinatie (Royal Flush) de hoogste punten heeft; zie:

code:

// pseudocode:

//royal flush
z = array(sa, sh, sv, sb, st)
waarde[z] = 9999
// straight flush
y = array(kv, kb, kt, k9, k8)
waarde[y] = 9990
// etc...

Wat is met deze gegevens het gemakkelijkste alghoritme om de persoon met de hoogste hand te verkijgen? Ik begrijp dat van bovenaf gewerkt moet worden (geen royal flush gevonden, zoek verder naar straigh flush, etc.).

Daarnaast moet de vergelijking tussen de `handen` van de spelers ook gemaakt worden als ze slechts twee kaarten in de hand hebben, vervolgens bij drie kaarten, etc. Ik heb al heel wat gezocht maar wellicht dat iemand mij even op weg kan helpen; gemakkelijk is het niet.

Mijn eigen bedachte mogelijk oplossing is als volgt;

Maak van iedere persoon zijn `hand` een vaste string:
persoon_a = 's6hvrhsas7';
..waarbij de waarden van de kaarten onderling gesoorteerd zijn op kleur, en vervolgens op waarde.
Vervolgens maak ik van elke scorende combinatie in de array tevens tekststrings. Vervolgens ga ik de user-strings vergelijken met de scorende strings, wel u snapt het, etc. Echter, er zijn dan al een paar problemen te bedenken, want bij bijvoorbeeld een Full House zal er geen match komen.
Een alternatief dan weer is om per persoon elke denkbare string ( maximaal 5 ^ 5 ) van zijn `hand` te maken en daar de vergelijkingen mee te gaan maken.

[ Voor 23% gewijzigd door Verwijderd op 09-12-2005 16:48 ]

[Varienaja]

Goed, je wilt dus handen vergelijken.

Ikzelf bedenk altijd eerst eens hoe ik 't zelf zou doen, en dan vertaal ik 't naar een algoritme.

Wat ik zou doen:
- Eerst maar eens kijken of er groepjes kaarten voorkomen (dus 2 of meer dezelfden; hiermee heb je pair, 2 pair, 3 of a kind, 4 of a kind en full house alvast te pakken)
- Dan eens zien of ern rijtjes te maken zijn, opeenvolgende kaarten dus. Daarmee haal je de grote en kleine staat boven water.
- (ik ben niet zo goed in poker, zijn er nu nog meer goede combinaties??)

In geval 1 is het makkelijk: sorteren op nummer (niet op kleur). Daarna loop je door je 5 kaarten, en kijk je of er paartjes zijn.

Geval 2 is ook vrij simpel: ook weer sorteren, dit keer op nummer, en wederom er doorheen lopen op zoek naar een rijtje.

Aan het eind van je rit weet je welke bijzondere combinaties er waren. Deze weeg je af door een of andere punten-aantal toe te kennen. Klaar is Kees. Nu alleen nog even uitwerken en implementeren.

[Verwijderd]

Heb er nog eens over nagedacht. Een andere stelling voor mezelf is ondertussen;
Moet ik dit brute-force - zie mijn eigen geöpperde idee aan het einde van de beginpost - aanpakken, d.w.z. alle mogelijke combinaties van kaarten maken (per persoon, van een `hand`) en deze allemaal vergelijken (in volgorde van meeste punten, als er wat gevonden wordt stoppen-) met de scorende combinaties?

Dus bijvoorbeeld de hoogste (Royal Flush) combinatie pakken, en kijken of deze in de gegenereerde array (met alle combinaties van de hand) zit? Zo niet, volgende bekijken, etc.

Of moet ik dit pér winnende combinatie anders, en meer doordacht, aanpakken? Dus, in het geval van de Royal Flush, kijken of er opeenvolgende kaarten inzitten, zoniet, kijken of er een carre (4 dezelfde) bestaat, zoniet, etc.

Kortom, twee opties. Welke zouden jullie kiezen en met welke argumenten?
Wellicht moet ik even een benchmarkje uitvoeren.

[Verwijderd]

Kan je hier niet het beste een bestaande library voor gebruiken? Ik weet niet in welke taal je het maakt, maar als je C/C++/Python gebruikt kan ik je de poker-eval library aanraden.
http://freshmeat.net/projects/poker-eval/
(dat is de C versie, er is ook een Python interface)

[megamuch]

Verwijderd schreef op vrijdag 09 december 2005 @ 18:06:
Heb er nog eens over nagedacht. Een andere stelling voor mezelf is ondertussen;
Moet ik dit brute-force - zie mijn eigen geöpperde idee aan het einde van de beginpost - aanpakken, d.w.z. alle mogelijke combinaties van kaarten maken (per persoon, van een `hand`) en deze allemaal vergelijken (in volgorde van meeste punten, als er wat gevonden wordt stoppen-) met de scorende combinaties?

Dus bijvoorbeeld de hoogste (Royal Flush) combinatie pakken, en kijken of deze in de gegenereerde array (met alle combinaties van de hand) zit? Zo niet, volgende bekijken, etc.

Of moet ik dit pér winnende combinatie anders, en meer doordacht, aanpakken? Dus, in het geval van de Royal Flush, kijken of er opeenvolgende kaarten inzitten, zoniet, kijken of er een carre (4 dezelfde) bestaat, zoniet, etc.

Kortom, twee opties. Welke zouden jullie kiezen en met welke argumenten?
Wellicht moet ik even een benchmarkje uitvoeren.

Wat ik zou doen is het brute forcen, maar dan wel logisch...

Zet de kansen van alle mogelijkheden eens op een rij en begin dan met berekenen van de handen van grootste kans naar kleinste kans.

Ik bedoel dus:

Eerst checken op hoogste kaart
Dan checken op dubbele kaarten
Dan checken op 2 paar dubbele kaarten
dan checken op 3 of a kind
Dan 4 of kind
etc.. (ik weet niet precies hoe de kansverdeling van de mogelijkeheden is).

Het zou stom zijn om bij Royal Flush te beginnen aangezien de kans van een Royal Flush veel kleiner is dan bijv een Pair.

Zit nog ff te denken.. Ik zou denk ik zo iets doen
... * megamuch gaat ff wat code tikken.. brb

[ Voor 3% gewijzigd door megamuch op 09-12-2005 18:24 ]

[joepP]

Precalcen.

Ik zal eerst eens de kleur negeren, die boeit toch alleen als alles gelijk is. Dan kan je met een lookuplist van 13^5 = 371.293 items toe. Als je permutaties negeert (2,3,4,5,6 = 6,5,4,3,2 = ...) door bijvoorbeeld eerst even te sorteren dan heb je nog veel minder ruimte nodig. Voor al deze mogelijkheden bereken je de score gewoon van tevoren.

Over deze score moet je even goed nadenken, maar ik denk dat je met 16 bits wel uit de voeten moet kunnen. Let op dat je alle kaarten hiervoor nodig hebt, aangezien 9,9,A,K,V van 9,9,A,K,B wint.

Tot slot controleer je nog even of alle kaarten van dezelfde soort zijn. Als je een straat hebt wordt het dus een straight-flush, lager dan een straat wordt dus een flush.

Sim-pel

[4of9]

Ik weet niet of het een goede oplossing is maar kun je niet "scores" berekenen aan de hand van de combinatie en die aan de speler mee geven? dan kun je zien wie de hoogste score heeft.

ow volgens mij zei mijn voorganger hetzelfde

[ Voor 16% gewijzigd door 4of9 op 09-12-2005 21:19 ]

[Zoijar]

je wilt het natuurlijk voor 'n' kaarten hebben, eventueel voor 7 card stud hi/lo, en omaha high low... dan is precalcen niet echt een goede manier denk ik. Toch al snel zo'n 120MB oid... (en 8 card stud dus 13 keer zo veel...)

[ Voor 15% gewijzigd door Zoijar op 09-12-2005 21:38 ]

[4of9]

ik heb zelf niet gezocht maar er moeten toch wel algoritmes op internet te vinden zijn over pokeren.

[joepP]

Waar staat dat de topicstarter het "natuurlijk voor n kaarten" wil hebben?

Ook voor 7 kaarten kan precalcen goed, en wel met de eerder beschreven methode. Eerst negeer je de kleur, dan zijn er nog 13^7 = 63M combinaties over. Ik schat dat er minstens een factor 5! = 120 te winnen valt met 7 kaarten als je permutaties ondervangt door eerst te sorteren. Totaal heb je dan dus 500.000 unieke combinaties met negeren van kleur. De flushes zijn eenvoudig te detecteren en te verwerken, dus ook dat is geen probleem.

Bottom line: als je permutaties ondervangt kost uitbreiden met één kaart je veel minder dan een factor 13.

[Gerco]

Ligt het aan mij of denken jullie allemaal te moeilijk?

Pseudocode:
Nu hoef je maar aantal_spelers * aantal_winnende_combinaties maal te kijken of de kaarten in die combinatie allemaal voorkomen in de hand van de speler en ben je klaar. aantal_spelers is klein (4), aantal_winnende_combnaties is de lijst van dingen met waarde (kun je nog wat generaliseren door de kleur te negeren voor de meeste combos), die is flink wat groter, maar toch zeker niet te groot?

Of begrijp ik iets verkeerd?

edit:
blijkbaar wel, aangezien ik geen rekening heb gehouden met het feit dat er weleens meer dan 1 winning combo per hand kan zijn (two pairs) en een full house kan ook op veel te veel manieren.

[ Voor 49% gewijzigd door Gerco op 10-12-2005 11:42 ]

[Zoijar]

joepP schreef op zaterdag 10 december 2005 @ 10:53:
Waar staat dat de topicstarter het "natuurlijk voor n kaarten" wil hebben?

Ook voor 7 kaarten kan precalcen goed, en wel met de eerder beschreven methode. Eerst negeer je de kleur, dan zijn er nog 13^7 = 63M combinaties over. Ik schat dat er minstens een factor 5! = 120 te winnen valt met 7 kaarten als je permutaties ondervangt door eerst te sorteren. Totaal heb je dan dus 500.000 unieke combinaties met negeren van kleur. De flushes zijn eenvoudig te detecteren en te verwerken, dus ook dat is geen probleem.

Bottom line: als je permutaties ondervangt kost uitbreiden met één kaart je veel minder dan een factor 13.

Met 63M combinaties heb je al 32bits per entry nodig, dus 252MB geheugen. Een poker programmaatje dat 252MB geheugen gebruikt lijkt me niet echt iets goeds. Bovendien zou het wel eens traag kunnen zijn. Maar misschien als je eerst sorteert dat het dan wel bruikbaar is. Een andere factor is nog: hoe bereken je een index gegeven een hand? En hoe bereken je de hand waarde om de tabel te maken? Eigenlijk liggen alle problemen dus nog open. Als je dat al kan berekenen, dan is het misschien wel efficienter om dat gewoon rechtstreeks te doen. Geheugen is transfer is een bottleneck op het moment, en dat wordt alleen maar erger. beetje warrig verhaal, laat maar

[ Voor 13% gewijzigd door Zoijar op 10-12-2005 11:43 ]

[Zoijar]

Ik zou je hand sorteren en er dan doorheen lopen. Elke keer als je dezelfde kaart als de vorige tegenkomt verhoog je een countertje, als de counter niet 0 is en je vindt een andere kaart, dan sla je het op in een van de 3 arrays: pairs/trips/carre. Tegelijk hou je bij of de reeks opvolgend is, als er meer dan 5 opvolgend zijn sla je de laatste/eerste kaart van de reeks op in de array: straights. Weer tegelijk hou je bij hoeveel van elke kleur je ziet, en sla je steeds de hoogste/allemaal kaart in een kleur op. Als je deze info hebt kan je een tweede fase ingaan. Je sorteert de hoogte van je pairs/trips/carres, etc. Als je een trips hebt kan je kijken of er ook een paar is, samen met het eerste/hoogste pair is dat dan full house. Als er geen trips zijn kan je of de eerste 2, of het eerste paar pakken. Daarvoor moet je even kijken of er straight is, flush, en als allebei, straight en royal flush etc. Op deze manier loop je er 1 keer doorheen, en dan combineer je de resultaten. Misschien is dit niet het allersnelste, maar als je echt een poker server draait, kan je toch misschien precalcen. Dan is het acceptabel om een speciale hash stuctuur van 200MB oid op te slaan in snel geheugen, zoals Joep al zei.

(als je van hoog naar laag sorteert, dan hoef je de pairs/trips/carres etc niet opnieuw te sorteren, want die staan dat dan al. Ook houdt dit geen rekening met kicker cards; je kan ofwel als het gelijk is daar op zoeken, of je kan in de precalc alle kaarten die je niet gebruikt opnieuw sorteren en er achter plakken)

[ Voor 14% gewijzigd door Zoijar op 10-12-2005 11:56 ]

[Grijze Vos]

Volgens mij kun je aardig wat winst boeken als je een geschikte datastructuur gebruikt. Ik heb niet echt tijd om erop in te gaan, maar wil dit morgen nog wel even bekijken, als er dan nog geen geschikte oplossing gevonden is..

[Verwijderd]

Bedankt voor het meedenken allen. Ben vandaag niet op kantoor, maar zit eraan te denken om het als volgt aan te pakken, ik maak een functie die als volgt te werk gaat.

<De input van de functie is een array met daarin de waarden van de kaarten van de speler, en een variabele met de naam van de speler>

Stap 1: controleer of er vier kaarten in de ontvangen array zitten van dezelfde kleur. Als dit zo is, controleren of er een RF (Royal Flush, Aas tot en met 10, dezelfde kleur) is. Dit kun je controleren door een string van de ontvangen array te maken (bijv. `sashsvsbst`), gesorteerd op hoogste->laagste kaart en vervolgens te kijken of deze string in de array `RF_array` voorkomt. `RF_array`is een array met alle mogelijke combinaties voor een royal flush; slechts vier mogelijkheden dus (elke kleur eenmaal). Niets gevonden? Controleren of er een Straight Flush (SF) bestaat, oftewel, 5 kaarten op een rij.
Stap 2: als uit de eerste stap geen resultaat komt, als er dus geen RF of een SF gevonden is, dan gaan we verder met het zoeken naar een combinatie die daarvoor komt, een Four of a Kind (FOAK) dus. ETc. etc. etc.

In iedere loop worden belangrijke gegevens opgeslagen, zoals 'bestaan er dubbele kaarten' of 'wat is de hoogste kaart' of 'wat is de hoogte dubbele combinatie' zodat nooit dubbel controles gedaan hoeven worden.

Kortom, voor iedere scorende combinatie een individuele check maken, totdat er een combinatie gevonden wordt. Dit lijkt mij uiteindelijk het beste en snelste werken. Alle scorende combinaties worden overigens in een array geplaatst om daar vervolgens mee te gaan vergelijken zodat de scorende combinaties niet on the fly berekend hoeven worden.

Ik zal begin volgende week even enkele tests maken en deze hier plaatsen.
Wellicht dat ik i.p.v. de functie een class maak overigens.

[ Voor 6% gewijzigd door Verwijderd op 10-12-2005 13:19 ]

[joepP]

Zoijar schreef op zaterdag 10 december 2005 @ 11:42:
[...]

Met 63M combinaties heb je al 32bits per entry nodig, dus 252MB geheugen. Een poker programmaatje dat 252MB geheugen gebruikt lijkt me niet echt iets goeds. Bovendien zou het wel eens traag kunnen zijn. Maar misschien als je eerst sorteert dat het dan wel bruikbaar is. Een andere factor is nog: hoe bereken je een index gegeven een hand? En hoe bereken je de hand waarde om de tabel te maken? Eigenlijk liggen alle problemen dus nog open. Als je dat al kan berekenen, dan is het misschien wel efficienter om dat gewoon rechtstreeks te doen. Geheugen is transfer is een bottleneck op het moment, en dat wordt alleen maar erger. beetje warrig verhaal, laat maar

Je komt inderdaad nogal warrig over

De waarde van de hand is relatief eenvoudig. Je hebt dat nothing < pair < ... < straightflush < royalflush. Nothing bevat geen paren, dus heeft (13 boven 5) = 1287 mogelijkheden (minder als je straten negeert). Een one-pair kan 13 verschillende zijn, en dan zijn er nog (12 boven 3) mogelijkheden voor de andere kaarten, dus 2860. Als je zo doortelt zijn er zeker minder dan 2^16 = 65536 uitkomsten, dus de score krijg je altijd in 16 bits gepropt.

Indexeren is ook niet moeilijk, want je kan een ordening van alle mogelijke gesorteerde handen aangeven (lexicografisch). Een boompje van diepte n (voor n kaarten) met de score van de hand in de bladeren doet de rest. De score bepalen van een hand kost met deze methode bijna niets. Je moet eerst sorteren (goh), dan een boompje van diepte 7 doorlopen (goh) en dan nog even op een flush checken (goh). Al met al bijna gratis.

Ik zie echt geen problemen

[Verwijderd]

Wat ik zou aanraden is dus het gebruik van nummers in plaats van strings. zo kan je gewoon beginnen met een 1 voor de aas en zo tot en met de koning gaan nummeren en vervolgens weer beginnen met een nummer voor de volgende kleur aas. met modulo 14 kan je dan deze kaarten sorteren zonder dat je de kleur hoeft te weten. je zou dus kunnen zien of je een straat heb als gewoon de getallen steeds 1 groter is dan de voorgaande kaart. Het komt weinig voor dat je ook de kleur hoeft te weten, dat zijn alleen bij een paar mogelijkheden zoals een flush en royal flush en daar kan je dan ook gewoon naar controleren, ik zou trouwens als laatst controleren voor een flush want die komt nauwelijks voor.

[sirdupre]

Eigenlijk is het gewoon een pattern matching probleem.

Ik zou inderdaad altijd de hand eerst sorteren, want dan kun je paren door slechts één keer door de hand te lopen vinden.
Ook zou ik allemaal losse pattern-match functies schrijven voor elke mogelijkheid (met een hand als input en een bool als output, bijvoorbeeld). Vervolgens zou ik deze functies ordenen dusdanig dat het vinden van een bepaalde score, het vinden van andere scores uitsluit (als je 3 dezelfde hebt, ben je een knappe jongen als je een straat hebt van tenminste 4 in een hand van 5) en gewoon in die volgorde je losse functies loslaten op elke hand en stoppen als je iets gevonden hebt.
Ook zou je er functies van hand naar int van kunnen maken en ze een score op kunnen laten leveren, dusdanig dat elke score voor een 2-pair lager is dan die van een 3-pair, maar de score van een 2-pair met 3en lager is dan die van een 2-pair met heren (zo zou je ook nog met de regel kunnen spelen dat de kleur ook de score beïnvloed). Als je een functie aanroept over een hand waar dat patroon niet in voorkomt, kun je gewoon 0 opleveren en dan is de score van een hand gewoon de max van alle functie-resultaten van die functies.

[Verwijderd]

je hoeft toch eigenlijk helemaal geen score bij te houden. gewoon vergelijken. een flush wint van een 2 pair en een fullhouse van een straat dus ik zou niet weten waarom je punten zou moeten geven aan deze handen. iedereen denkt een beetje te moeilijk over het probleem

[Verwijderd]

Verwijderd schreef op zondag 11 december 2005 @ 16:54:
je hoeft toch eigenlijk helemaal geen score bij te houden. gewoon vergelijken. een flush wint van een 2 pair en een fullhouse van een straat dus ik zou niet weten waarom je punten zou moeten geven aan deze handen. iedereen denkt een beetje te moeilijk over het probleem

Ik denk het niet. Als je een geautomatiseerde speler gaat toevoegen ("de computer"), zal diezelfde computer toch moeten kunen begrijpen hoeveel een hand nu werkelijk waard is. Daarvoor zou je per hand de kans op die combinatie kunnen opslaan, en je zou het zelfs zo ingewikkeld kunnen maken dat hij bij stud poker van tevoren kan berekenen wat de kans is dat hij met een bepaalde hand gaat winnen, kijkend naar de zichtbare kaarten van een ander. En hoe zinvol het dus kan zijn om te bluffen, als hij kijkt naar zijn eigen zichtbare kaarten.

Wel zo handig als je dan al van tevoren hebt bepaald wat die kansen zijn, dat scheelt een hoop rekenkracht tijdens het spel

Het kan dus wel degelijk interessant zijn om een databank aan te leggen met winkansen per hand of gedeeltelijke hand.

[Verwijderd]

nou een hand is veel waard als je een hoge combi hebt, daarvoor hoef je geen punten te geven aan een hand (tenzij je verschil maakt tussen 3 drieen en 3 asen) en dat kan je ook in principe makkelijk doen door terplekke te rekenen. Je hoeft echt niet voor elke combinatie punten op te slaan, dat lijkt me meer dom dan efficient. een hand als string opslaan is ook geen goeie manier om poker te programmeren, zoals ik al eerder zij nummer de kaarten gewoon

[joepP]

Je ziet het probleem te simpel. Hoe ga je verschil maken tussen Q,Q,J,T,9 en Q,Q,J,T,8? Ze hebben beide een paartje vrouwen, en de eerste wint op de derde kicker. Daar heb je toch echt wel een score voor nodig.

[Verwijderd]

als je 2 handen gezien hebt met paren dan ga je verder vergelijken op wie de hoogste kaart heeft.
met nummers is dit heel simpel want je vergelijkt gewoon wie de hoogste waarde in een array heeft.
je zou ook de arrays kunnen sorteren met een sorteer algoritme en vervolgens winnende combinaties voor aan te plaatsen, dan hoef je de handen die gelijk zijn eigenlijk alleen maar nummer voor nummer te vergelijken