Analyse eines Javascript Poker Hand Evaluators

Nachdem wir uns dem Thema Poker schon in einigen C#-Tutorials (siehe 1, 2, 3, 4) angenommen haben, wollen wir heute den Blick in Richtung Javascript lenken. Und wenn ich sage Javascript, dann meine ich das auch so. Bibliotheken wie jQuery (die dieser Tage viel zu oft fälschlicherweise mit Javascript gleichgesetzt werden) lassen wir heute aus dem Spiel. Doch was genau wollen wir heute eigentlich erstellen?

Im heutigen Artikel wollen wir noch einmal das Thema “Hand Evaluator” beackern. Also jenes Thema, welches wir an dieser Stelle schon in C# umgesetzt haben. Für alle, die den letzten Artikel nicht gelesen haben oder mit C# nichts anfangen können, noch einmal schnell die Zusammenfassung, was ein Poker Hand Evaluator ist und wozu er genutzt wird.

Ein Evaluator ist ein Programm, dass Eingabewerte evaluiert – also Eingabewerte untersucht und bewertet. Ein Poker Hand Evaluator untersucht also eine Poker Hand und bewertet diese. In der Praxis sieht das wie folgt aus. Man übergibt dem Hand Evaluator eine den Handstapel, bestehend aus 5 Spielkarten und der Evaluator gibt dann an, welches die beste Hand (z.B. Paar, Flush oder Full-House) ist, die aus diesen Karten hervorgeht.

Verwendung findet ein solcher Hand Evaluator praktisch in jeder Poker-Implementierung. Sei es Online-Poker, ein Poker-Trainer oder eine Poker-App. Er ist integraler Bestandteil bei der Abbildung der Spiellogik.

In dem heutigen Artikel, wollen wir eine etwas “komplexere” Umsetzung in Javascript eines Hand Evaluators analysieren. Konkret geht es um den Evaluator von subskybox, welchen ihr hier findet. Da ich der Meinung bin, dass der Code absolut genial, jedoch recht schwer zu verstehen ist, wollen wir heute einmal schauen, wie er funktioniert.

Der Einstieg

Die Originalfunktion von subskyboy besteht aus nur 4 Zeilen Code zur Ermittlung der Hand und einer Zeile zur Ausgabe. Das an und für sich ist schon ein Meisterwerk. Bedenke man wie viel Zeilen Code wir für unsere C# Implementierung gebraucht haben, die ich am Anfang dieses Artikel verlinkt habe.

Der Code von subskybox sieht wie folgt aus:

hands=["4 of a Kind", "Straight Flush", "Straight", "Flush", "High Card",
"1 Pair", "2 Pair", "Royal Flush", "3 of a Kind", "Full House" ];
var A=14, K=13, Q=12, J=11, _ = { "♠":1, "♣":2, "♥":4, "♦":8 };

function rankPokerHand(cs,ss) {
var v, i, o, s = 1<<cs[0]|1<<cs[1]|1<<cs[2]|1<<cs[3]|1<<cs[4];
for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}
v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
v -= (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) * ((s == 0x7c00) ? -5 : 1);
document.write("Hand: " + hands[v] + (s == 0x403c?" (Ace low)":"")+"</br>");
}

Da der originale Code schon fast wie C anmutet und extrem kompakt ist, werden wir ihn an vielen Stellen umschreiben, um die Funktionsweisen dahinter zu verstehen. Sicher, subskybox’ anliegen war es, einen möglichst kurzen Code zu schreiben, doch für die Analyse kommen wir nicht umhin, den Code zu erweitern.

Weiter nutzt der originale Code eine Mischung aus Bit- und arithmetischen Funktion, was der Tatsache geschuldet ist, dass Bit-Operationen nur auf 32-Bit-Typen anwendbar sind, wir jedoch 52-Bit benötigen, um den Hand-Evaluator abbilden zu können.

Um die Kartenwerte- und Farben zu speichern, werden zwei verschiedene Formate genutzt. Beide legen die Informationen auf Bit-Ebene ab.

Das erste Format speichert welcher Kartenwert wie oft in der Hand vorkommt. Hierzu werden die 52-Bit verwendet, wobei 4 Bit je Kartenwert verwendet werden, um die einzelnen Farben/Anzahlen jedes Kartenwertes als Bit-Flags abzubilden. (13 Werte * 4 Farben = 52 Kombinationen/Bit.)

Mit dieser Darstellung können wir den Großteil der möglichen Hände wie z.B. Paare oder Drillinge erkennen. Da wir jedoch mit 52-Bit arbeiten, kommen wir in diesem Format auch nicht mehr mit den reinen Bit-Operatoren aus, sondern müssen zusätzlich noch mit arithmetischen Funktionen arbeiten.

Das zweite Format beachtet keine Dopplungen, sondern lediglich, welche Kartenwerte in der Hand vorhanden sind. Hierzu wird ein 13-bittige Darstellung genutzt, wobei jede Stelle einem Kartenwert (2, 3, 4, …, König, Ass) entspricht. Befindet sich ein Wert in der Hand, wird das Bit an entsprechender Position der 13-Bit-Folge auf 1 gesetzt. Da wir mit 13 Bit auskommen, können wir hier auch mit den normalen Bit-Operatoren arbeiten.

Der Code beginnt mit der Deklaration einiger Konstanten. So werden ein Array für die möglichen Hände (wobei die Reihenfolge eine wichtige Rolle spielt – dazu später mehr), ein paar Hilfsvariablen für die Kartenwerte (das Ass bekommt den Wert 14!) und ein weitere Array für die Kartensymbole angelegt.

Die original Funktion besitzt zwei Parameter – cs für die Kartenwerte der Hand und ss für die Farben der Karten in der Hand. Der Lesbarkeit halber sind die Variablen im folgenden als cardRanks und cardSuits benannt.

Im ersten Schritt erstellen wir ein BitArray, um damit später Strassen erkennen zu können. Dieses Array wird im zweiten, der beiden eben vorgestellten Formate gespeichert.

Erstellen des cardValues-BitArray

Für die Erstellung des cardValues-Array benötigen wir ausschließlich Bit-Operationen. Genauer gesagt den sogenannten “Bit-Shift-Operator” sowie den OR-Operator.

Der Bit-Shift-Operator wird in Javascript (und fast allen anderen Programmiersprachen auch) als << und >> dargestellt und verschiebt eine Gruppe von Bits um X Positionen nach rechts oder links.

Hierzu folgende Beispiel: 3 << 1

3 == 0000 0011 //Darstellung von 3 als Binärcode
0000 0011 << 1 == 0000 0110 //Verschiebung der Bits
0000 0110 == 6 //Ergebnis des Bit-Shift

Um nun einen Kartenwert zu Speichern, verschieben wir den Wert 1 um “Kartenwert” Positionen. Wollen wir also die 7 ablegen, würden wir folgenden Code nutzen.

0000 0001 << 7 = 1000 0000

Wollen wir im Anschluss die 4 ablegen, nutzen wir folgenden Code.

0000 0001 << 4 = 0001 0000

Um diese beiden Werte nun platzsparend zu speichern, kann man sie mit einander kombinieren. Dies geht mittels des OR-Operators.

(1000 0000 | 0001 0000) == 1001 0000

Führen wir dieses Beispiel nun fort und schreiben es für die 5 Karten der Pokerhand um, kommen wir auf die erste Zeile von subskybox’ Funktion:

var cardValuesField = 1<<cardRank[0] |1<<cardRank[1]|1<<cardRank[2]|1<<cardRank[3]|1<<cardRank[4];

Wird shiften also für jede Karte der Hand eine 1 um den Wert der Karte nach links und kombinieren alle Werte mittels OR-Operator zu einem einzigen BitArray. Obige Zeile entspricht ziemlich genau der ersten Zeile von subskybox’ Code, mit dem Unterschied, dass wir die Variablen etwas sprechender benannt haben. Im nächsten Schritt nehmen wir uns dem zweiten BitArray an.

Das cardCountBitField-BitArray

Nun kommen wir zum zweiten Array, welches eingangs bei der Format-Beschreibung als erstes Format beschrieben wurde.

Mittels dieses Arrays können wir nicht nur bestimmen, welche Kartenwerte in der Hand sind, sondern auch wie oft diese vorkommen, sodass wir Hände wie z.B. Pärchen oder Drillinge oder Full House erkennen können.

Wie bereits beschrieben, kommen wir nun nicht mehr mit den reinen Bit-Operatoren aus, sondern werden uns auch arithmetische Operatoren zu Nutze machen.

In der Originalfunktion handelt es sich hierbei um die folgende (zweite) Zeile.

for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}

Um diese Zeile zu verstehen, brechen wir den Code in mehrere Zeilen auf. Doch zuerst werfen wir einen Blick auf die verwendeten Variablen. Derer gibt es 3 an der Zahl:

• i => Die Zählvariable der Schleife, welche genutzt wird, um die Position im cs (cardRank) Array anzugeben.
• o => Gibt die aktuelle Nibble Position an. (Als Nibble bezeichnet man in der IT einen 4-Bit-Block, auch Halbbyte genannt.)
• v => Gibt die Anzahl der jeweiligen Karte an. (Der Lesbarkeit halber, geben wir auch dieser Variable einen sprechenden Namen: cardCountBitfield)

Ersetzen wir die Variablennamen in der Originalzeile und fügen Zeilenumbrüche, erhalten wir folgendes, schon etwas besser zu lesendes, Ergebnis:

for (index=-1, cardCountBitField=nibblePosition=0; index<5; index++, nibblePosition=Math.pow(2,cardRank[index]*4)) {
cardCountBitField += nibblePosition*((cardCountBitField/nibblePosition&15)+1);
}

Leider ist das immer noch nicht gerade verständlich, weshalb wir die Funktion noch einmal wie folgt umschreiben:

for (i=0; i<5; i++) {
currCount = getCurrentCountForCardRank(cardCountBitField, cardRank[i]);
cardCountBitField = setValueForCardRank(cardCountBitField, cardRank[i], currCount + 1);
}

Nun sollte schon eher klar sein, was innerhalb der Schleife passiert. Für jeder der fünf Karten ermitteln wir im ersten Schritt die Anzahl (=currCount) des aktuellen Kartenwerts (=cardRank[i]).

Im nächsten Schritt (= zweite Zeile) erhöhen wir die Anzahl um 1 und schreiben das Ergebnis zurück in das BitArray cardCountBitField. Da cardCountBitField 52-Bit lang ist und für jeden Kartenwert 4-Bit vorsieht, können wir mit der Variable in jedem Schleifendurchlauf arbeiten, ohne dass wir bereits ermittelte Werte überschreiben würden.

Was noch auffallen dürfte, ist, dass wir zwei Funktionen in den Code einbaut haben. Diese erhöhen die Lesbarkeit. Innerhalb der Funktionen wird jedoch derselbe Code ausgeführt, den auch subskybox genutzt hat. Die Erklärung der einzelnen Funktionen erfolgt in den nächsten Abschnitten dieses Artikels.

Erkennen der Nibble-Position

Bevor wir zu den beiden neuen Funktionen kommen, beschäftigen wir uns zuerst mit der Halbbyte-Position. In unserem Code ist dies die Variable nibblePosition. (Im Originalcode die Variable o.)

Der Originalcode sieht an dieser Stelle wie folgt aus:

o=Math.pow(2,cs[i]*4))

Jeder Kartenwert benötigt 4-Bit Speicher (1 Bit pro Farbe). Um nun zu ermitteln in welchem Halbbyte der Kartenwert steckt, müssen wir bei 0 beginnen und in Viererschritten durch die 52 Bits des cardCountBitField-Array gehen.

Da wir jedoch nicht mit klassischen Arrays arbeiten, müssen wir später beim Hochzählen 1 Bit an einer bestimmten Stelle setzen. Wie bereits in dem Abschnitt über Bit-Shifting erklärt, müssen wir also eine Zahl nutzen, die das Bit bereits an der richtigen Stelle gesetzt hat und diese per OR-Operator mit dem bestehenden BitArray verbinden. Dies ginge mit reinen Bit-Operatoren wie folgt (wobei value der Zahl entspricht, die wir per OR über das BitArray legen wollen und index der Position entspricht, an der wird das Bit setzen wollen):

var value = 1 << index

Den Wert (=value) könnten wir also wieder mit dem OR-Operator (=|) auf die bestehende Bit-Folge legen. Hierbei gibt es  jedoch einen Haken…

Da wir pro Kartenwert 4 Bits benötigen müssen wir dies natürlich berücksichtigen. So wird der index mit 4 multipliziert.

var value == 1 << (index * 4)

Bei 13 Kartenwerten und 4 Farben (bzw. dem Anzahlwert, der maximal 4 sein kann) kommen wir nun jedoch auf 52-Bit und können somit nicht mehr die Bit-Operationen wie den Bit-Shift nutzen, da diese nur auf 32-Bit Werten funktionieren. (Dieses Problem hatte ich eingangs schon bei der Erklärung der beiden Darstellungsformate angesprochen.)

Mit etwas Trickserei und der Funktionsweise von Binärcode können wir das Problem jedoch umgehen. Bedenkt man, dass man nur eine 1 auf dem Index und an allen anderen Positionen eine 0 haben möchte, so könnte man die gesuchte Position der 1 auch wie folgt darstellen: value = 2^(index*4)

In Javascript-Code abgebildet und in eine Funktion verpackt, ergibt das folgenden Code.

function getPositionForCardRank(cardRank) {
return Math.pow(2,cardRank*4);
}

Mit dem Wissen darüber, wie wir die richtige Index-Position ermitteln können, können wir uns nun mit der ersten, der beiden neuen Funktionen (getCurrentCountForCardRank) beschäftigen.

Auslesen der aktuellen (Anzahl-)Wertes

Um die Anzahl des aktuellen Kartenwerts auszulesen, machen wir noch einmal einen kleinen gedanklichen Exkurs in den Fall, wo wir Bit-Shifting nutzen können. Was wir erreichen möchten, ist die 4 Bits auszulesen, die dem Kartenwert entsprechen.

Wir wissen, dass wir die Bits an der Position index*4 finden werden. Mit Bit-Shifting könnten wir nun um index*4 nach rechts shiften, um die gesuchten 4 Bits zu erhalten.

var value = cardRank >> (index*4)

Nachdem wir nun alle rechtsseitigen Bits vom gesuchten Wert entfernt haben, müssten wir noch die Bits links von unserem gesuchten Halbbyte entfernen. Hierzu kann man den AND-Operator nutzen. Im Gegensatz zum OR-Operator, den wir bereits genutzt haben, gibt der AND-Operator nur eine 1, wenn beide, übereinander gelegten Werte 1 (=true) sind.

Dies können wir uns zu Nutze machen, indem wir eine Maske (=Bitmask) anlegen, die auf allen Positionen, bis auf unseren 4 gesuchten Bit, eine 0 hat.

0000 0000 0000 1111 //Maske = dezimal 15
&0001 0000 0001 0111 //cardRanks nach Bit-Shift
----------------------------
0000 0000 0000 0111

Durch den AND-Operator haben wir nun alle Stellen, außer unseren gesuchten 4 Bits, genullt. Da wir jedoch auf unseren 52-bittigen cardRanks-Wert keine Bit-Operation ausführen können, beenden wir nun diesen gedanklichen Exkurs und schauen uns die Praxislösung an.

Hier machen wir wieder von den arithmetischen Operatoren Gebrauch. Für den Links-Shift, wie wir ihn in der Indexermittlung genutzt haben, haben wir den Exponenten zur Basis zwei multipliziert. (Zur Erinnerung: value=2^index*4)

Ähnlichen können wir nun auch den Rechts-Shift machen. Hierzu nutzen wir lediglich die Division anstelle einer Multiplikation im Exponenten.

Um zum Beispiel ein Bit um 3 Positionen nach rechts zu schieben (0001 0000 => 0000 0010), eignet sich folgender Term: 2^(5-shiftCount) = 2^(5-3) = 2^5/2^3 = 2^2

Nun können wir also die gesuchten 4 Bits auch ohne Shift-Operator ans Ende verschieben. Jetzt, wo wir Sie an der richtigen Position schieben können, können wir auch mittels des AND-Operators wieder die linksseitigen Bits nullen.

Mit dem oben stehenden Wissen, können wir nun die Funktion zum Auslesen des Anzahl-Wertes schreiben. Hierzu nutzen wir zusätzlich die Funktion zur Ermittlung des Indexes (getPositionForCardRank) aus dem vorherigen Abschnitt dieses Artikels.

function getCurrentCountForCardRank(array, cardRank) {
var position = getPositionForCardRank(cardRank);
return array/position&15;
}

Zu diesem Zeitpunkt können wir also die aktuelle Anzahl der Karten eines Wertes auslesen und haben die erste der beiden Funktionen der zweiten Zeile fertig.

Im nächsten Schritt bilden wir nun die zweite Funktion, um den Kartenzähler zu erhöhen.

Erhöhen des aktuellen (Anzahl-)Wertes

Werfen wir zuerst wieder einen Blick auf den Originalcode. Für das setzen des Zählerwerts ist im Original folgender Teil der zweiten Zeile zuständig:

v += o*((v/o&15)+1);

Unser Ziel ist es den Zähler zu erhöhen. Haben wir zum Beispiel bereits zwei Karten des selben Wertes und bekommen eine Dritte, so würden wir im Normalfall einfach value = value+1  schreiben. Aber wie bereits mehrmals erwähnt, arbeiten wir ja mit Bits – und zwar 4 Bits für maximal 4 Karten. Wir wollen also ein Flag setzen.

Für vorangegangenes Beispiel hätten bei bei zwei Karten also 0011 und wollen daraus 0111 machen. Dies erledigen wir in zwei Schritten. Zuerst erhöhen wir den bestehenden Wert um 1. Aus 0011 wird also 0100. Wenn wir diesen Wert nun mit dem Ausgangswert addieren, erhalten wir den gesuchten Wert: 0011 + 0100 == 0111

Als Funktion bilden wir dies wie folgt ab:

function addValueToCardRank(array, cardRank, value) {
var position = getPositionForCardRank(cardRank);
return array + position * value;
}

Mit dieser Funktion können wir nun auch die zweite, neue Funktion komplettieren. Aus der zweiten Zeile des Originalcodes…

for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,cs[i]*4)) {v += o*((v/o&15)+1);}

wurde nun dieser Code:

for (i=0; i<5; i++) {
currCount = getCurrentCountForCardRank(cardCountBitField, cardRank[i]);
currCount++;
cardCountBitField = addValueToCardRank(cardCountBitField, cardRank[i], currCount);
}

Zeit, einmal kurz “Halbzeit” zu rufen, sich selbst einen Belohnungs-Drink zu servieren und kurz zu feiern, denn wir haben nun die ersten beiden der ingesamt vier Zeilen Code der Originalfunktion analysiert.

Die verbleibenden beiden Zeilen beschäftigen sich mit der Erkennung/Evaluierung der gegebenen Pokerhand.

Pokerhände erkennen – die Königsdisziplin

Nachdem wir unsere Kartewerte und -anzahlen nun vorbereitet haben, können wir uns mit der Erkennung der Hände beschäftigen. In der Originalfunktion geschieht dies in der dritten Zeile, welche wie folgt aussieht:

v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);

Diese kurze Zeile Code übernimmt, wie schon die Zeilen zuvor, wieder mehrere Aufgaben. Sie erkennt fast alle möglichen Hände, bis auf “Straight”, “Straight Flush” und “Royal Flush”. Mit diesen Händen beschäftigen wir uns in einem späteren Abschnitt.

Beginnen wir mit dem Modulo-Operator (%). Normalerweise würden wir erwarten, den Restwert von v bei einer Division durch 15 zu erhalten. Da wir uns jedoch im Bit-Umfeld bewegen erreichen wir mit der Funktion, dass jeder der Kartenwerte, dargestellt durch 4 Bit, zusammengezählt wird. Der Wert 15 wird genutzt, da er dem Maximalwert eines 4-bittigen Kartenwerts (1111) entspricht.

An dieser Stelle kommt das hands-Array ins Spiel. Es zeigt sich, dass für jede mögliche Hand, die summierten Werte einzigartig (=unique) sind. Noch interessanter ist, dass die Reihenfolge der Karten auf der Hand dafür egal ist und die Summe nicht beeinflusst.

Das mag auf den ersten Blick nun verwirrend klingen, doch, wenn wir betrachten, wie die Karten zusammengezählt werden, wird schnell klar, warum dies so ist.

Nehmen wir als Beispiel ein Paar. Hierzu müssten wir zwei gleiche Karten und 3 unterschiedliche Karten haben. In unserer 4-bittigen Darstellung der Anzahlwerte entspräche dies zum Beispiel: 0011 + 0001 + 0001 + 0001 == 0110 == 6

Oben stehendes Beispiel macht deutlich, dass der Kartenwert für die Berechnung der Summe unrelevant ist. Egal ob zwei Asse oder zwei Siebenen – die binäre Darstellung der Anzahl wäre in jedem Fall 0011.

Bedingt durch diese Tatsache können wir einen Großteil der möglichen Hände mittels einem einfachen Array auslesen. Wichtig ist hiebei nur die Reihenfolge der Hände innerhalb des Arrays.

hands = ["4 of a Kind","","","","High Card","1 Pair","2 Pair","","3 of a Kind","Full House"];

Da Arrays Null-Index basiert sind, ziehen wir 1 von der errechneten Summe ab, um den passenden Wert im Array zu finden.

Hat man also zum Beispiel vier mal die 8 und eine 5 auf der Hand, dann wären die 4-bittigen Anzahlwerte mit den Flags 1111 und 0001. Bildet man nun die Summe, erhält man: 1111 + 0001 = 0001 0000 = 16. 16 % 15 ergibt wiederum 1. Zieht man nun noch den einen ab (wegen des 0-basierten Index des Arrays) kommt man auf 0. An Index 0 im Array steht wiederum “4 of a Kind” – also die korrekte Hand.

Als weiteres Beispiel nehmen wir ein Full House. Nehmen wir an, wir haben drei mal die 9 und zweimal die 7. Addiert man die 4-bittigen Anzahlwerte, erhält man: 0111 + 0011 = 0000 1010 = 10. Nun wieder den Modulo: 10 % 15 = 10. Einen für den 0-basierten Index abgezogen ergibt 9. Und an Index 9 im Array steht… natürlich Full House. Ich denke die Funktionsweise sollte bis hierhin klar sein.

Weiter fällt an obigem Array auf, dass mehrere Position des Arrays mit Leer-String (“”) gefüllt sind. Diese Positionen stehen für die Hände, die wir mit obiger Methode nicht abbilden können. Doch dazu sofort mehr…

Straights erkennen

Für die Erkennung der Straßen (=Straights) nutzen wir die andere Darstellung der Karten. (Jene, für die wir keine Anzahlwerte berechnet, sondern uns nur die Werte gemerkt haben.) Bei dieser anderen Darstellung hatten wir nur die Kartenwerte in einer 13 Bit langen Folge gespeichert. (Jede Bit-Position entsprach einem Wert: 2, 3, 4, …, König, Ass.)

Eine Straße ist definiert als eine Folge von 5 Karten. Was wir nun also suchen, ist eine Folge von fünf 1 in unserem 13 Bit langen Bitarray. Hierzu wollen wir alle rechtsseitigen Nullen entfernen. Übrig bliebe bei einer Straße dann nämlich folgende Bitfolge: 11111 welche der Dezimalzahl 31 entspricht. Nach dem Entfernen der Nullen könnten wir also einfach Abfrage machen, ob das Ergebnis = 31 ist und wenn dem so ist, würde eine Straße vorliegen.

Aber wie entfernen wir die Nullen am rechten Rand? Da die Anzahl unbekannt ist, können wir nicht um einen festen Wert shiften. Doch auch hierfür gibt es eine Lösung. (Welche übrigens auch als “Normalisierung eines Bitarrays” bezeichnet wird.)

Zuerst benötigen wir die erste 1 innerhalb des Bytearrays, um danach mittels Bit-Shift die Nullen zu eliminieren. Für die Ermittlung der ersten 1 machen wir uns das sogenannte Zweierkomplement zu nutze. Dieses wird eigentlich genutzt, um negative Zahlen im Binärsystem darzustellen. Gebildet wird es, indem man alle Bits negiert und danach 1 addiert.

0100 //7
1011 //negiert
1100 //+1 entspricht dem Zweierkomplement

Wenn man Ausgangswert und Zweierkomplement mit einem AND-Operator verbindet, erhält man die Position des ersten 1er Bit.

0100
&1100
--------
0100

Teilt man nun den Ausgangswert durch die Position des ersten Bits, so entspricht dies einem abtrennen der rechtsseitigen Nullen. Zur Verdeutlichung folgendes Beispiel:

0 0001 1111 0000 //13-bittige Darstellung; entspricht 496
1 1110 0001 0000 //Zweierkomplement
0 0000 0001 0000 //=Ausgang AND Zweierkomplement = Position

0 0001 1111 0000 //Ausgangswert (496)
/0 0000 0001 0000 //geteilt durch Position (16)
0 0000 0001 1111 //abgeschnitte Nullen (31)

Genau folgendes geschieht in der dritten Zeile des Originalcodes, wobei die Variable s den Ausgangswert (=cardValuesField) enthält.

s/(s&-s)

Zuerst wird s mittels &-Operator mit -s (Komplement) verbunden. Danach wird s durch das Ergebnis der voherigen Rechnung geteilt. Wie bereits gesagt, entsprichteine Straße einer Folge von fünf Einsen, was dezimal 31 entspricht. Somit können wir obige Berechnung direkt abfragen.

(s/(s&-s) == 31)

Wird dieser Ausdruck wahr, liegt bei der Hand eine Straße vor. Dennoch fehlt noch ein Fall zur Bildung einer Straße, der von obiger Berechnung nicht abgedeckt wird. Und zwar jener, wenn die Straße mit einem Ass beginnt (Ass -> 2 -> 3 -> 4 -> 5). In unserer Binärabbildung entspräche dies 1 0000 0000 1111. Nach dem Shift (der nicht stattfindet, da es keine rechtsseitigen Nullen gibt) würden wir im Abgleich gegen 31 ein False erhalten.

Da dies jedoch der einzige Sonderfall bei den Straßen ist, können wir ihn direkt abfragen. Der Wert für diese Hand 1 0000 0000 1111 entspricht der Dezimalzahl 16444 welche sich Hexadezimal als 403c darstellen lässt. Somit lässt sich diese Hand mit folgendem Code abfragen:

(s == 0x403c)

Kombiniert man den Sonderfall mit allen anderen Fällen, erhält man zur Abfrage, ob eine Blatt eine Straße ist, folgenden Code:

(s/(s&-s) == 31) || (s == 0x403c)

Wird obiger Gesamtausdruck wahr (=true), dann handelt es sich um eine Straße. Dies bilden wir nun noch auf das Array der möglichen Hände ab. Wie bereits gesagt, hatten wir im Arrays ein paar Indizes freigelassen, für die Straßen sowie den Royal Flush. Nun belegen wir den Index 2 mit der Straße…

hands=["4 of a Kind", "", "Straight", "", "High Card",
"1 Pair", "2 Pair", "", "3 of a Kind", "Full House" ];

…und kombinieren den Code zur Erkennung der für die meisten Hände gilt mit dem neuen Code für die Straße.

v = v % 15 - ((cardValuesField/(cardValuesField&-cardValuesField) == 31) || (cardValuesField == 0x403c) ? 3 : 1);

Wir erinnern uns: v%15 (- 1) ergab den Index für die Erkennung fast aller Hände. Nun ziehen wir davon folgenden Ausdruck ab:

((cardValuesField/(cardValuesField&-cardValuesField) == 31) || (cardValuesField == 0x403c) ? 3 : 1)

Hierbei nutzen wir den tenären Operator. Dieser gibt den Wert hinter dem ? zurück, wenn der Ausdruck vor dem Fragezeichen wahr ist und den Wert hinter dem Doppelpunkt, wenn der Ausdruck falsch ist.

Ist der Ausdruck falsch, liegt keine Straße vor, geben wir eine 1 zurück. Von v%15 wird also 1 abgezogen. Das ergibt die Rechnung, die wir für fast alle Hände brauchen.

Ist der Ausdruck wahr, weil eine Straße vorliegt, geben wir eine 3 zurück. Liegt eine Straße vor, dann haben wir in v auch fünf Werte mit dem Zähler jeweils auf 1 (0001 + 0001 + 0001 + 0001 + 0001) was 5 ergibt. Zieht man hiervon die 3 ab, erhält man 2 – den Index, in dem “Straight” im hands-Array steht.

Kommen wir zum letzten Schritt. Die Erkennung von Flushes…

Flush, Straigt Flush und Royal Flush

Bisher haben wir nur mit einem der beiden Eingabewerte der Hauptfunktion gearbeitet. Und zwar mit dem cardRanks-Array (in der Originalfunktion “cs”) welches die Kartenwerte der 5 Pokerkarten enthält. Nun benötigen wir das zweite Eingabearray namens cardSuits (in der Originalfunktion “ss”).

Dieses Array enthält die Kartenfarben der 5 Kartern in der Hand. Denn ein Flush besteht per Definition aus fünf Karten der gleichen Spielfarbe.

Für die Ermittlung eines Flushs nutzen wir wieder einmal den OR-Operator. Wenn man zwei identische Zahlen ORed, dann erhält man als Ergebnis die Ausgangszahl. Wendet man den OR-Operator auf zwei unterschiedliche Zahlen an, so erhält man eine komplett andere Zahl.

Für einen Flush müssen alle Farben (die in dem cardSuits-Array als Zahlen übergeben werden) gleich sein. Deshalb kann man einfach überprüfen, ob die Farbe der ersten Karte dem ge-OR-ten Wert der restlichen vier Karten entspricht.

cardSuit[0] == (cardSuit[1] | cardSuit[2] | cardSuit[3] | cardSuit[4]);

Ist obiger Ausdruck wahr, dann handelt es sich um einen Flush.

Doch auch hier gibt es (wie bei den Straßen) eine Ausnahme. Ein Royal-Flush steht noch über dem Flush. Deshalb müssen wir diesen Explizit behandeln. Hierzu vergleichen wir den 13-bittigen String, wie bei den Straßen, wieder mit einem Festwert. (Der Wert für einen Royalflush entspricht in hexadezimaler Darstellung 7c00.)

Abschließend füllen wir unserer hands-Array noch mit den fehlenden Händen:

hands=["4 of a Kind", "Straight Flush", "Straight", "Flush", "High Card",
"1 Pair", "2 Pair", "Royal Flush", "3 of a Kind", "Full House" ];

Die Zeilen zur Berechnung der hands-Array Indexes sehen nun wie folgt aus:

v = v % 15 - ((cardValuesField/(cardValuesField&-cardValuesField) == 31) || (cardValuesField == 0x403c) ? 3 : 1);
v -= (cardSuit[0] == (cardSuit[1]|cardSuit[2]|cardSuit[3]|cardSuit[4])) * ((cardValuesField == 0x7c00) ? -5 : 1);

Nachdem wir in der ersten Zeile den Index v für alle normalen Hände und Straßen berechnet haben, passen wir diesen in der zweiten Zeile für Flushs noch einmal an.

Die Anpassung findet jedoch nur statt, wenn der Ausdruck vor dem *-Zeichen größer 0 ist. Liegt kein Flush vor, so ergibt (ss[0] == (ss[1]|ss[2]|ss[3]|ss[4])) false, was einer 0 entspricht. Die Anpassung wird also nur vorgenommen, wenn ein Flush vorliegt.

Die Höhe der Anpassung wird durch den Ausdruck hinter dem *-Zeichen definiert. Handelt es sich um einen Royal-Flush (s == 0x7c00), dann wird v um 5 erhöht (–5), ist es kein Royal-Flush, wird v um 1 verringert.

Die Verschiebung um +5 bzw. -1 funktioniert aus folgenden Gründen. Ein Royal-Flush ist zeitgleich auch eine Straße. Liegt ein Royal-Flush vor, muss also bereits eine Straße ermittelt worden sein. v steht somit auf 2, dem Index für “Straight” im hands-Array. 2+5 = 7 und entspricht dem Index für “Royal Flush”.

Wurde nur Flush ermittelt, also ohne “Royal” so kann dies nur aus zwei Händen hervorgehen. Einer Straße oder einer High-Card. Alle anderen Hände können per Definition keinen Flush ergeben.

Liegt eine Straße vor steht v auf 2. Zieht man 1 ab, erhält man 1, den Index für “Straight Flush”. Liegt eine High-Card vor, ist v = 4. Zieht man 1 ab, landet bei 3, dem Index für “Flush”.

Und das war es auch schon. Nun können wir sämtliche Hände erkennen. Mehr ist nicht nötig.

Abschluss & Fazit

Ich gebe zu, der Artikel hat mich wesentlich mehr Zeit gekostet als vermutet. Ich hoffe jedoch, dass er den Zeiteinsatz wert war und ihr, als Leser, den Erklärungen folgen konntet und nun auch versteht wie dieses kleine Meisterstück an Javascript-Code funktioniert.

Abschließend zeige ich euch noch einmal den gesamten Code dieses Artikels. Doch zuvor noch ein, zwei Fragen. Kennt ihr ähnliche, kompakte Code-Snippets? Seid ihr selber schon einmal über so einen “Schatz” gestolptert? Wenn ja, dann ab in die Kommentare damit!

Sollten noch Fragen offen sein oder etwas unklar, freue ich mich ebenfalls über eure Kommentare.

Und nun – wie versprochen – der gesamte Code:

function rankPokerHand(cardRank,cardSuit) {
  var cardCountBitField = 0, i, currCount, v;

  //BitArray für die vorhandenen Kartenwerte (vgl. Format 2)
  var cardValuesField = 1<<cardRank[0] |1<<cardRank[1]|1<<cardRank[2]|1<<cardRank[3]|1<<cardRank[4];
 
  //BitArray für die Anzahl der einzelnen Kartenwerte (vgl. Format 1)
  for (i=0; i<5; i++) {
    currCount = getCurrentCountForCardRank(cardCountBitField, cardRank[i]);
    cardCountBitField = addValueToCardRank(cardCountBitField, cardRank[i], currCount + 1);
  }
  
  //normale Hände und Straßen ermitteln
  v = v % 15 - ((cardValuesField/(cardValuesField&-cardValuesField) == 31) || (cardValuesField == 0x403c) ? 3 : 1);

  //Flush, Royal-Flush und Straigt-Flush ermitteln
  v -= (cardSuit[0] == (cardSuit[1]|cardSuit[2]|cardSuit[3]|cardSuit[4])) * ((cardValuesField == 0x7c00) ? -5 : 1);

  document.write("Hand: " + hands[v] + (suitBitField == 0x403c ? " (Ace low)" : "")+"
");
}


function getPositionForCardRank(cardRank) {  
  return Math.pow(2,cardRank*4);
}

function getCurrentCountForCardRank(array, cardRank) {
  var position = getPositionForCardRank(cardRank);
  return array/position&15;
}

function addValueToCardRank(array, cardRank, value) {
  var position = getPositionForCardRank(cardRank);
  return array + position * value;
}